belajar mudah algoritma data mining k means
DESCRIPTION
Belajar mudah algoritma data mining k-means by ilmubinerTRANSCRIPT
[email protected] Data Mining http://ilmubiner.blogspot.com
Page 1 of 5
Belajar Mudah Algoritma Data Mining Clustering : k-means
Clustering atau analisis cluster adalah : • Proses pembentukan kelompok data (cluster) dari himpunan data yang tidak diketahui
kelompok-kelompok atau kelas-kelasnya. • Proses menentukan data-data termasuk ke dalam cluster yang mana. Bisa dibilang, clustering merupakan proses untuk mengetahui kelas-kelas atau taksonomi atau botryologi, atau analisis topologi dari data-data yang ada. Dilihat dari kacamata data mining, clustering bukanlah proses klasifikasi. Karena dalam proses klasifikasi, data dikelompokkan ke dalam kelas-kelas yang telah diketahui sebelumnya. Ada beberapa metode atau model untuk melakukan clustering, antara lain : • Model connectivity. • Model centroid. • Model density. • Model subspace. • Model group. • Model graph based. Algoritma k-means merupakan model centroid. Model centroid adalah model yang menggunakan centroid untuk membuat cluster. Centroid adalah “titik tengah” suatu cluster. Centroid berupa nilai. Centroid digunakan untuk menghitung jarak suatu objek data terhadap centroid. Suatu objek data termasuk dalam suatu cluster jika memiliki jarak terpendek terhadap centroid cluster tersebut. Secara umum algoritma k-means adalah : 1. Menentukan banyaknya cluster (k). 2. Menentukan centroid. 3. Apakah centroid-nya berubah?
a. Jika ya, hitung jarak data dari centroid. b. Jikat tidak, selesai.
4. Mengelompokkan data berdasarkan jarak yang terdekat.
Diagram alir (flowchart) algoritma k-means ada pada Gambar 1. Sedangkan Gambar 2 merupakan contoh posisi titik-titik data dan centroid-centroid-nya (lingkaran yang lebih besar. Gambar 1. Diagram Alir Algoritma k-means
[email protected] Data Mining http://ilmubiner.blogspot.com
Page 2 of 5
Gambar 2. Contoh Cluster
Untuk lebih jelasnya, berikut pembahasan pemakaian algoritma k-means. Tabel 1 berisi data sumber yang akan dianalisis cluster-nya :
Tabel 1. Data Sumber n a b
1 1 1
2 2 1
3 4 3
4 5 4
1. Tentukan banyaknya cluster adalah dua (k = 2) yang akan dibuat. Banyaknya cluster
harus lebih kecil dari pada banyaknya data (k < n).
2. Tentukan centroid setiap cluster. Untuk menentukan centroid awal (initial centroid) banyak metode yang dapat digunakan. Di sini metode yang digunakan adalah mengambil data dari data sumber, secara acak atau random (Sel yang berwarna kuning dan hijau di Tabel 1).
Tabel 2. Centroid pada Pengulangan ke-0
a b c1 1 1 c2 2 1
Untuk pengulangan berikutnya (pengulangan ke-1 sampai selesai), centroid baru dihitung dengan menghitung nilai rata-rata data pada setiap cluster. Jika centroid baru berbeda dengan centroid sebelumnya, maka proses dilanjutkan ke langkah berikutnya. Namun jika centroid yang baru dihitung sama dengan centroid sebelumnya, maka proses clustering selesai.
3. Hitung jarak data dengan centroid. Rumus-rumus untuk menghitung jarak antara lain :
a. Euclidean. b. Manhattan / City Block. c. Minkowski.
Rumus yang digunakan di sini adalah rumus Euclidean Distance :
[email protected] Data Mining http://ilmubiner.blogspot.com
Page 3 of 5
���� , ��� = �(�� − ��)�����
� = ����� � = ������������� � = �������� � = ���� � = �������� Jarak data dengan cluster 1 adalah : �(��, ��) = �(�� − ���)� + (�� − ��!)�= �(1 − 1)� + (1 − 1)� = 0 �(��, ��) = �(�� − ���)� + (�� − ��!)�= �(2 − 1)� + (1 − 1)� = 1 �(��, ��) = �(�% − ���)� + (�% − ��!)�= �(4 − 1)� + (3 − 1)� = 3.605551 �(�+, ��) = �(�+ − ���)� + (�+ − ��!)�= �(5 − 1)� + (4 − 1)� = 5 Jarak data dengan cluster 2 adalah : �(��, ��) = �(�� − ���)� + (�� − ��!)�= �(1 − 2)� + (1 − 1)� = 1 �(��, ��) = �(�� − ���)� + (�� − ��!)�= �(2 − 2)� + (1 − 1)� = 0 �(��, ��) = �(�% − ���)� + (�% − ��!)�= �(4 − 2)� + (3 − 1)� = 2.828427 �(�+, ��) = �(�+ − ���)� + (�+ − ��!)�= �(5 − 2)� + (4 − 1)� = 4.242641 Untuk seterusnya, hitung jarak pada setiap baris data, dan hasilnya seperti pada Tabel 3.
Tabel 3. Hasil Perhitungan Jarak
n a b dc1 dc2
1 1 1 0 1
2 2 1 1 0
3 4 3 3.605551 2.828427
4 5 4 5 4.242641
4. Kelompokkan data sesuai dengan cluster-nya, yaitu data yang memiliki jarak terpendek.
Contoh; karena �(��, ��) < �(��, ��) maka �� masuk ke dalam cluster 1. Pada Tabel 4, data n = 1 masuk ke dalam cluster 1 karena dc1 < dc2, sedangkan data n = 2, 3, 4 masuk ke dalam cluster 2 karena dc2 < dc1.
[email protected] Data Mining http://ilmubiner.blogspot.com
Page 4 of 5
Tabel 4. Hasil Perhitungan Jarak dan Pengelompokkan Data n a b dc1 dc2 c1 c2
1 1 1 0 1 Ok
2 2 1 1 0
Ok
3 4 3 3.605551 2.828427
Ok
4 5 4 5 4.242641 Ok
5. Proses kembali lagi ke langkah no. 2.
Untuk hasil clustering yang lebih lengkap, berikut tabel-tabel hasil analisis dan perhitungan dari awal sampai selesai : Inisialisasi
n a b
1 1 1
2 2 1
3 4 3
4 5 4
a b
c1 1 1
c2 2 1
n a b dc1 dc2 c1 c2
1 1 1 0 1 Ok
2 2 1 1 0 Ok
3 4 3 3.605551 2.828427 Ok
4 5 4 5 4.242641 Ok
Pengulangan ke-1
a b Nilai pada sel diperoleh dari menghitung
rata-rata pada tabel di atasnya sesuai
dengan warna sel
c1 1 1
c2 3.666667 2.666667
n a b dc1 dc2 c1 c2
1 1 1 0 3.14466 Ok
2 2 1 1 2.357023 Ok
3 4 3 3.605551 0.471405 Ok
4 5 4 5 1.885618 Ok
[email protected] Data Mining http://ilmubiner.blogspot.com
Page 5 of 5
Pengulangan ke-2
a b
c1 1.5 1
c2 4.5 3.5
n a b dc1 dc2 c1 c2
1 1 1 0.5 4.301163 Ok
2 2 1 0.5 2.357023 Ok
3 4 3 3.201562 0.471405 Ok
4 5 4 4.609772 1.885618 Ok
Pengulangan ke-3
a b
c1 1.5 1
c2 4.5 3.5
Karena centroid tidak mengalami perubahan (sama dengan centroid
sebelumnya) maka proses clustering selesai
[EoF]