Home > Serba-serbi > Algoritma Clustering K-Means

Algoritma Clustering K-Means

14 November 2008

Clustering merupakan suatu teknik data mining yang membagi-bagikan data ke dalam beberapa kelompok (grup atau cluster atau segmen) yang tiap cluster dapat ditempati beberapa anggota bersama-sama. Setiap obyek dilewatan ke grup yang paling mirip dengannya. Ini menyerupai menyusunan binatang dan tumbuhan ke dalam keluarga ā€“ keluarga yang para anggotanya mempunyai kemiripan.


Clustering tidak mensyaratkan pengetahuan sebelumnya dari grup yang dibentuk, juga dari para anggota yang harus mengikutinya.

Algoritma K-Means diperkenalkan oleh J.B. MacQueen pada tahun 1976, salah satu algoritma clustering sangat umum yang mengelompokkan data sesuai dengan karakteristik atau ciri-ciri bersama yang serupa. Grup data ini dinamakan sebagai cluster. Data di dalam suatu cluster mempunyai ciri-ciri (atau fitur, karakteristik, atribut, properti) serupa dan tidak serupa dengan data pada cluster lain.

Algoritma K-Means

Berikut ini adalah bagaimana algoritma K-Means mempartisi suatu dataset ke dalam cluster-cluster:

1. Algoritma menerima jumlah cluster untuk mengelompokkan data ke dalamnya, dan dataset yang akan dicluster sebagai nilai input.

2. Algoritma kemudian membuat sebanyak K cluster awal (K= jumlah cluster yang diperlukan) dari dataset, sekaligus memilih K record data secara acak (random) dari dataset. Sebagai contoh, jika terdapat 10,000 baris data di dalam dataset dan 3 cluster perlu dibentuk, maka K=3 cluster awal pertama akan dibuat dengan mengambil 3 record secara random dari dataset, sebagai cluster permulaan. Setiap cluster awal yang dibentuk tersebt mempunyai hanya satu record data.

3. Algoritma K-Means menghitung rata-rata aritmatika dari setap cluster yang dibentuk dalam dataset. Rata-rata dari suatu cluster adalah rata-rata dari semua record yang terdapat di dalam cluster tersebut. Karena di dalam semua K cluster pertama hanya ada satu record maka rata-ratanya adalah rata-rata record tersebut. Rata-rata dari suatu record adalah kumpulan nilai-nilai yang membangun record tersebut. Sebagai contoh jika di dalam dataset S terdapat record P yang menerima nilai-nilai untuk field Tinggi, Berat dan Usia, maka dapat ditulis P = {Usia, Tinggi, Berat). Jika John mempunyai Usia John = 20 tahun, Tinggi = 1.70 meter dan Berat = 80 Pon maka ditulis John = {20, 170, 80}. Karena terdapat hanya satu record di dalam setiap cluster awal maka rata-rata dari cluster dimana John berada adalah = {20, 170, 80}.

4. Selanjutnya, K-Means mengirim K record di dalam dataset ke hanya salah satu dari cluster awal. Record ke-4 sampai ke-6 dilewatkan ke cluster terdekat (nearest cluster, yaitu cluster yang sangat mirip dengan record tersebut) menggunakan suatu ukuran jarak atau kemiripan seperti ukuran jarak Euclidean atau Manhattan/City-Block.

5. K-Means mengkalkulasi ulang rata-rata aritmatika dari semua cluster. Rata-rata dari suatu cluster adalah rata-rata dari semua record di dalam cluster tersebut. Sebagai contoh, jika suatu cluster mengandung dua record John = {20, 170, 80} dan Henry = {30, 160, 120}, maka rata-rata P(rata-rata) dinyatakan sebagai P(rata-rata) = {Usia(rata-rata), Tinggi(rata-rata), Berat(rata-rata)). Usia(rata-rata) = (20 + 30)/2, Tinggi(rata-rata) = (170 + 160)/2 dan Berat(rata-rata) = (80 + 120)/2. Rata-rata aritmatik dari cluster ini adalah {25, 165, 100}. Rata-rata tersebut menjadi pusat dari cluster baru ini. Mengikuti prosedur yang sama, pusat-pusat cluster baru dibentuk untuk semua cluster yang telah ada.

6. K-Means mengirimkan lagi setiap record di dalam dataset ke hanya salah satu dari cluster-cluster baru yang terbentuk. Suatu record atau titik-titik data dilewatkan ke cluster terdekat, seperti sebelumnya.

7. Langkah-langkah sebelumnya diulang sampai terbentuk cluster-cluster stabil dan prosedur K-Means selesai. Cluster stabil terbentuk ketika iterasi atau perulangan dari K-Means tidak membuat cluster baru sebagai pusat cluster atau nilai rata-rata aritmatika dari semua cluster baru sama dengan cluster lama. Terdapat beberapa teknik untuk menentukan kapan suatu cluster stabil terbentuk atau kapan algoritma K-Means berakhir.

Definisi matematis jarak Euclidean dan Manhattan

Ukuran Jarak Euclidean antara dua titik atau obyek atau item X dan Y didefinisikan oleh persamaan:

Jarak Euclidean (X,Y) = ( |X1-Y1|2 + |X2-Y2|2 + … + |XN-1-YN-1|2 + |XN-YN|2 )1/2

Sedangkan ukuran jarak Manhattan atau City Block didefinisikan sebagai berikut:

Jarak Manhattan (X,Y) = ( |X1-Y1| + |X2-Y2| + … + |XN-1-YN-1| + |XN-YN| )

Bagaimana? Semoga bermanfaat untuk lebih memahami konsep penting dalam data mining dan berbagai aplikasinya, seperti web mining dan collaborative filtering.

%d bloggers like this: