Pertemuan 9 : Algoritma K-Means Clustering

K-Means Clustering adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi.

Terdapat dua jenis data clustering yang sering dipergunakan dalam proses pengelompokan data yaitu Hierarchical dan Non-Hierarchical, dan K-Means merupakan salah satu metode data clustering non-hierarchical atau Partitional Clustering.

Dari banyak siswa diambil 12 siswa sebagai contoh untuk penerapan algoritma    k-means  dalam penjurusan siswa. Percobaan dilakukan dengan menggunakan parameter-parameter berikut:

Jumlah cluster    : 2

Jumlah data        : 12

Jumlah atribut     : 8Berikut merupakan data yang digunakan untuk melakukan percobaan perhitungan manual.

NISNamaMatematikaFisikaKimiaBiologiSejarahAkuntansiSosiologiGeografi
2012173Afgansyah7975758576787680
2012174Denny Sumargo8476797776777581
2012175Lina Nur Aini7784788592897782
2012176Ananda Anugrah7886847778777575
2012177Putri Khadijah8282819190827991
2012178Ika Inayah7575708275757975
2012179Wa Ode Sofia Z.7775758980807575
2012180Budy Santoso7776707777807580
2012181Andi Eka Murti7976758477817677
2012182Ahsan Muhajir8075757575787779
2012183Siswan Sumargo7671757577817984
2012184Anis Fadilah8077757878777780

Iterasi ke-1

1. Penentuan pusat awal cluster

Untuk penentuan awal di asumsikan:

Diambil data ke- 2 sebagai pusat Cluster Ke-1: (84, 76, 79, 77, 76, 77, 75, 81)

Diambil data ke- 5 sebagai pusat Cluster Ke-2: (82, 82, 81, 91, 90, 82, 79, 91)

2. Perhitungan jarak pusat cluster

Untuk mengukur jarak antara data dengan pusat cluster digunakan Euclidian distance, kemudian akan didapatkan matrik jarak yaitu C1 dan C2 sebagai berikut:

Rumus Euclidian distance

MatematikaFisikaKimiaBiologiSejarahAkuntansiSosiologiGeografiC1C2Jarak Terpendek
797575857678768010.4421.72610.44030651
8476797776777581024.0210
778478859289778224.14514.5614.56021978
788684777877757514.17726.03814.17744688
828281919082799124.02100
757570827575797515.65228.8115.65247584
777575898080757516.46222.13616.46207763
777670777780758011.87426.2311.87434209
797675847781767711.13622.47211.13552873
80757575757877796.855727.0926.8556546
767175757781798412.28825.84612.28820573
80777578787777806.557422.9786.557438524

3. Pengelompokkan data

Jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat.

Berikut ini akan ditampilkan data matriks pengelompokkan group, nilai 1 berarti data tersebut berada dalam group.

G1
NoC1C2
110
210
301
410
501
610
710
810
910
1010
1110
1210

4. Penentuan pusat cluster baru

Setelah diketahui anggota tiap-tiap cluster kemudian pusat cluster baru dihitung berdasarkan data anggota tiap-tiap cluster sesuai dengan rumus pusat anggota cluster. Sehingga didapatkan perhitungan sebagai berikut:

NamaMatematikaFisikaKimiaBiologiSejarahAkuntansiSosiologiGeografiCluster baru
Afgansyah797575857678768078.579.5
Denny Sumargo847679777677758176.283
Lina Nur Aini778478859289778275.379.5
Ananda Anugrah788684777877757579.988
Putri Khadijah828281919082799176.991
Ika Inayah757570827575797578.485.5
Wa Ode Sofia Z.777575898080757576.478
Budy Santoso777670777780758078.686.5
Andi Eka Murti7976758477817677  
Ahsan Muhajir8075757575787779  
Siswan Sumargo7671757577817984  
Anis Fadilah8077757878777780  

Iterasi Ke-25. Ulangi langkah ke 2 (kedua) hingga posisi data tidak mengalami perubahan.

Cluster baru yang ke-178.576.275.379.976.978.476.478.6
Cluster baru yang ke-279.58379.5889185.57886.5
MatematikaFisikaKimiaBiologiSejarahAkuntansiSosiologiGeografiC1C2Jarak Terpendek
79757585767876805.55720.5185.556977596
84767977767775817.929722.9567.929691041
778478859289778221.1827.28017.280109889
788684777877757514.08823.1314.08829301
828281919082799123.3817.28017.280109889
75757082757579759.004426.6469.004443348
777575898080757510.66219.59610.66208235
77767077778075806.72923.3246.729041537
79767584778176775.165319.95.165268628
80757575757877795.663924.965.663920903
767175757781798410.00423.85410.0039992
80777578787777803.4756213.475629439

Langkah selanjutnya sama dengan langkah pada nomor 3 jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat.

G2
NoC1C2
110
210
301
410
501
610
710
810
910
1010
1110
1210

Karena G2 = G1 memiliki anggota yang sama maka tidak perlu dilakukan iterasi/perulangan lagi. Hasil clustering telah mencapai stabil dan konvergen.

Contoh Kasus dengan Algoritma K-Medoids

Diketahui sepuluh data dengan k = 2

NoX1X2
126
234
338
447
562
664
773
874
985
1076

Langkah 1

  Data ObjekCost13
426333
438443
447453
462563
464373
473593
4856103
4766

Misalkan kita asumsikan  

Jadi C1 dan C2 dipilih sebagai medoids.Hitung jarak untuk menghubungkan setiap objek data yang terdekat dengan. Nilai yang terdekat dengan medoids dapat dilihat pada tabel.

  Data ObjekCost13
426333
438443
447453
462563
464373
473593
4856103
4766
  Data ObjekCost17
426737
438847
447657
462367
464177
473197
4852107
4762

Sehingga clusternya menjadi:

Langkah 2
Pilih satu cluster yang bukan medoids misalkan 

Jadi sekarang medoidnya adalah 

jika C1 dan 0′ adalah medoid baru, maka hitung totalnya menggunakan rumus pada langkah 1

  Data ObjekCost13
426333
438443
447453
462563
464373
474493
4856103
4766
  Data ObjekCost17
326837
338947
347757
362267
364277
374197
3853107
3763

Sehingga total costnya

Karena Total cost baru > Total cost awal, maka tidak terjadi pertukaran posisi.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s