Pengelompokan Data Menggunakan Algoritma K-Means

Algoritma K-means merupakan jenis pengelompokkan partisi. Setiap cluster yang terbentuk dihubungkan oleh sebuah centroid (titik pusat). Melalui centroid inilah setiap data kemudian ditempatkan berdasarkan jarak yang paling dekat. Untuk itulah, jumlah Kcluster yang akan terbentuk harus ditentukan terlebih dahulu. Berikut ini adalah algoritma dasar dari K-means :

1.      Masukan sejumlah dataset sebanyak N

2.      Tentukan K sebagai pusat klaster, K ini sekaligus merupakan banyaknya klaster yang akan terbentuk. (pusat klaster/centroid dapat diperoleh dari dataset secara random atau ditentukan)

3.      Hitung jarak data sebanyak N terhadap pusat klaster menggunakan Eucledian Distance sebagai berikut :

Dimana :

d(x,y)        : jarak antara data pada titik x dan y

x                : titik data pertama (pusat klaster)

y                : titik data kedua (data dari N)

n                : jumlah atribut data

4.      Ulangi

a.       Bentuk cluster K dengan menempatkan semua titik terdekat.

b.      Hitung ulang centroid untuk setiap cluster.

5.      Sampai centroid tidak berubah

Berikut ini diberikan ilustrasi pengelompokkan data dengan K-means :

CONTOH 1 :

Misalkan diberikan data X = {2,3,4,10,11,12,20,25,35}. Data ini akan dibagi ke dalam dua buah cluster  (K=2). Untuk itu ditentukan dua buah initial centroid yaiut µ₁= 2 dan µ₂ = 4. Perhitungan jarak dilakukan dengan teknik city-block distance.

Iterasi 1 :

X	2	3	4	10	11	12	20	25	30
d(x,µ1)	0	1	2	8	9	10	18	23	33
d(x,µ2)	2	1	0	6	7	8	16	21	31
Min(d(x,µ1), d(x,µ2))	C1	C1	C2	C2	C2	C2	C2	C2	C2

            Diperoleh        : Cluster 1 (C1) = {2,3}

                                      Cluster 2 (C2) = {4,10,11,12,20,25,35}

            Perhitungan centroid baru :

Iterasi 2 :

X	2	3	4	10	11	12	20	25	30
d(x,µ1)	0.5	0.5	1.5	7.5	8.5	9.5	17.5	22.5	32.5
d(x,µ2)	14	13	12	6	5	4	4	9	19
Min(d(x,µ1), d(x,µ2))	C1	C1	C1	C2	C2	C2	C2	C2	C2

            Diperoleh        : Cluster 1 (C1) = {2,3,4}

                                      Cluster 2 (C2) = {10,11,12,20,25,35}

            Perhitungan centroid baru :

            

Iterasi 3 :

X	2	3	4	10	11	12	20	25	30
d(x,µ1)	1	0	1	7	8	9	17	22	32
d(x,µ2)	16	15	14	8	7	6	2	7	17
Min(d(x,µ1), d(x,µ2))	C1	C1	C1	C1	C2	C2	C2	C2	C2

            Diperoleh        : Cluster 1 (C1) = {2,3,4,10}

                                      Cluster 2 (C2) = {11,12,20,25,35}

            Perhitungan centroid baru :

Proses iterasi terus berlanjut selama centroid terus berubah. Iterasi akan berhenti jika µ_baru = µ_lama. Dengan kata lain, setiap elemen dalam cluster tidak berubah.

CONTOH 2 :

Diberikan data nilai mahasiswa untuk mata kuliah Kecerdasan Buatan (KCB) dan Metodologi Penelitian (MP) sebagai berikut :

Nama	KCB	MP
Udin	70	80
Nana	60	50
Jaja	70	60
Jaka	50	70
Ujang	80	50
Jarna	90	70
Asep	70	80

Kelompokan data nilai mahasiswa tersebut menggunakan k-means ke dalam 2 (dua) kelompok. Artinya nilai k = 2, dengan centroid awal adalah µ₁ = (60,50) dan µ₂= (80,70).

Penyelesaian :

Langkah pertama :

1.      Hitung jarak antar data dengan pusat klaster menggunakan persamaan :

Dalam hal ini, x_imerupakan pusat klaster (centroid awal) sedangkan y_i adalah data yang diambil dari data nilai mahasiswa. Dengan menggunakan persamaan di atas, berikut perhitungan jarak antara data pertama (Udin) dengan centorid awal :

Dengan cara yang sama lakukan perhitungan jarak untuk data nilai Nana, Jaja, Jaka, Ujang, Jarna dan Asep. Sehingga diperoleh hasil perhitungan jarak sebagai berikut :

d(x,y)¹ =

Nama	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	31,62	0,00	14,14	22,36	20,00	36,06	31,62
C2	14,14	28,28	14,14	30,00	20,00	10,00	14,14

Baris kedua dan ketiga dari matriks di atas menunjukkan jarak data dengan pusat klaster.

2.      Kelompokkan data berdasarkan jarak terdekat (jarak paling kecil/pendek nilainya), sehingga diperoleh matriks pengelompokkan data sebagai berikut :

Hasil pengelompokan iterasi - 1

	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	0	1	1	1	1	0	0
C2	1	0	0	0	0	1	1

Nilai 0 pada matriks di atas menunjukkan bawa data tersebut bukan anggota dari klaster bersangkutan, sedangkan nilai 1 menunjukan anggota pada klaster tersebut. Dengan demikian untuk sementara klaster pertama (C1) memiliki anggota = Nana, Jaja, Jaka, Ujang; sedangkan klaster kedua (C2) memiliki anggota = Udin, Jarna, Asep.

3.      Langkah selanjutnya adalah menghitung pusat klaster baru berdasarkan hasil klaster pada tahap 2. Berikut perhitungan pusat klaster tersebut :

• Untuk C1 :

Nama	KCB	MP
Udin	70	80
Nana	60	50
Jaja	70	60
Jaka	50	70
Ujang	80	50
Jarna	90	70
Asep	70	80

Karena pada klaster pertama (C1) anggota datanya adalah Nana, Jaja, Jaka, Ujang, maka perhitungan pusat klaster baru dilakukan dengan mencari nilai rata-rata data nilai KCB dan MP dari sebanyak anggota pada C1, sehingga diperoleh :

• Untuk C2 :

Nama	KCB	MP
Udin	70	80
Nana	60	50
Jaja	70	60
Jaka	50	70
Ujang	80	50
Jarna	90	70
Asep	70	80

Karena pada klaster pertama (C2) anggota datanya adalah Udin, Jarna, Asep, maka perhitungan pusat klaster baru dilakukan dengan mencari nilai rata-rata data nilai KCB dan MP dari sebanyak anggota pada C2, sehingga diperoleh :

Dengan demikian kita memiliki nilai centroid baru untuk µ₁ = (65 ; 57.5) dan µ₂= (76.7 ; 76.7).

4.      Ulangi langkah 1 untuk menghitung nilai jarak data nilai mahasiswa terhadap centroid baru yang diperoleh pada langkah 3. Sehingga diperoleh matriks jarak sebagai berikut :

Nama	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	23,05	9,01	5,59	19,53	16,77	27,95	23,05
C2	7,47	31,49	17,99	27,53	26,90	14,89	7,47

Diperoleh kelompok baru hasil iterasi 2:

	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	0	1	1	1	1	0	0
C2	1	0	0	0	0	1	1

5.      Bandingkan antara hasil klaster iterasi saat ini dengan iterasi sebelumnya :

Hasil iterasi 1 :

	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	0	1	1	1	1	0	0
C2	1	0	0	0	0	1	1

Hasil iterasi 2 :

	Udin	Nana	Jaja	Jaka	Ujang	Jarna	Asep
C1	0	1	1	1	1	0	0
C2	1	0	0	0	0	1	1

Karena posisi anggota klaster tidak mengalami perubahan lagi, maka proses klaster berhenti. Sehingga hasil akhir dari pengklasteran nilai mahasiswa ini adalah bahwa Kelompok 1 (C1) beranggotakan Nana, Jaja, Jaka, Ujang; sedangkan kelompok 2 (C2) beranggotakan Udin, Jarna, Asep.

6.      Selesai.