Hierarchy Clustering

Hierarchy clustering berfungsi membagi-bagi data menjadi beberapa klaster menurut urutan kejadiannya (hirarki). Ada dua pendekatan dalam membuat hirarki yaitu 
  • bottom-up: dari klaster kecil menjadi satu klaster besar (Agglomerative)
  • top-down: dari satu klaster besar menjadi klaster-klaster kecil (Divisive)

Step-by-Step Hierarchy Clustering Agglomerative

1. Buat setiap data menjadi satu klaster
2. Cari dan gabungkan 2 klaster dengan jarak terpendek.
3. Ulangi langkah kedua sampai semua data menjadi 1 klaster

Ukuran jarak antar klaster terbagi menjadi beberapa:


  • Single linkage cluster: mengukur a anggota X dan c anggota Y dimana jarak a dan c adalah yang paling pendek.
  • Complete linkage cluster: mengukur b anggota X dan d anggota Y dimana jarak b dan d adalah yang paling panjang. 
  • Centroid linkage cluster: mengukur p centroid X dan q centroid Y dimana jarak p dan q adalah yang paling pendek. 
  • Average linkage cluster: mengukur rata-rata jarak setiap x anggota X ke setiap y anggota Y dimana nilai rata-ratanya adalah yang paling pendek. 


CONTOH SOAL


  • Kita memiliki 10 data yang akan kita bagi-bagi menjadi beberapa klaster.
  • STEP 1: Setiap data adalah sebuah klaster, jadi kita memiliki 10 klaster yaitu {A}, {B},{C}, ... {J}
  • STEP 2: Cari 2 klaster yang paling berdekatan dan gabungkan. Kita temukan {A }dan {B }menjadi {A,B}. Di contoh ini kita menggunakan centroid linkage untuk mengukur jarak terpendek antar klaster.
  • STEP 3: Gabungkan 2 klaster yang paling berdekatan. Kita temukan lagi {I }dan {J} menjadi {I,J}
  • STEP 4: Gabungkan lagi 2 klaster yang paling berdekatan. Kita temukan {C }dan {D }menjadi {C,D}
  • STEP 5: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {A,B} dan {C,D} menjadi {A,B,C,D}
  • STEP 6: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {F} dan {G} menjadi {F,G}
  • STEP 7: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {E } dan {F,G} menjadi {E,F,G}
STEP 8: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {E,F,G} dan {H} menjadi {E,F,G,H}
  • STEP 9: Gabungkan 2 klaster yang paling berdekatan. Kita temukan {A,B,C,D} dan {E,F,G,H} menjadi {A,B,C,D,E,F,G,H}
  • STEP 10: Gabugkan 2 klaster yang paling berdekatan. Kita temukan {A,B,C,D,E,F,G,H} dan {I,J} menjadi {A,B,C,D,E,F,G,H,I,J}

  • Karena semua data sudah menjadi satu klaster, maka proses berhenti sampai disini.
  • Hasilnya adalah sebuah visualisasi yang dinamakan dendrogram yang bentuknya seperti decision tree (pohon keputusan).
  • Dari dendrodram di bawah ini dapat disimpulkan sbb:
    • kalau dibuat 2 klaster maka klaster pertama {I,J}, klaster kedua {A,B,C,D,E,F,G,H}.
    • kalau dibuat 3 klaster maka klaster pertama {I,J}, klaster kedua {E,F,G,H} dan klaster ketiga {A,B,C,D}.
    • dst




illustrated K-means


K-means adalah model data dimana data-data dikelompokkan ke dalam beberapa cluster. Masing-masing cluster memiliki satu centroid, yaitu titik tengah cluster yang dihitung dari jarak eucledian rata-rata masing-masing data yang ada dalam cluster tsb. Menurut Tan (2006) clustering merupakan sebuah proses untuk mengelompokan data ke dalam beberapa cluster sehingga data dalam satu cluster memiliki tingkat kemiripan yang maksimum dan data antar cluster memiliki kemiripan yang minimum.

Jarak Euclidean

Jarak Euclidean adalah perhitungan jarak dari 2 buah titik atau lebih dalam Euclidean space. Euclidean space diperkenalkan oleh Euclid, seorang matematikawan dari Yunani sekitar tahun 300 Sebelum Masehi.

Jarak Euclidean Pada 1 dimensi

Rumus jarak dalam 1 dimensi
rumus1dimensi
Misalkan kita ingin menghitung jarak Euclidean 1 dimensi. Titik pertama adalah 10, titik kedua adalah 30. Caranya adalah kurangkan 30 dengan 10 sehingga menghasilkan 20. Hitung nilai kuadratnya sehingga kita mendapat nilai 400. Kemudian diakarkan sehingga mendapatkan nilai 20. Sehingga jarak euclidean dari 2 titik tersebut adalah 20.


Jarak Euclidean Pada 2 dimensi

Koordinat Jarak
Caranya hampir sama. Misalkan titik pertama mempunyai kordinat (1,2). Titik kedua ada di kordinat (5,5). Caranya adalah kurangkan setiap kordinat titik kedua dengan titik yang pertama. Yaitu, (5-1,5-2) sehingga menjadi (4,3). Kemudian pangkatkan masing-masing sehingga memperoleh (16,9). Kemudian tambahkan semuanya sehingga memperoleh nilai 16+9 = 25. Hasil ini kemudian diakarkan menjadi 5. Sehingga jarak euclideannya adalah 5

Rumus jarak Eucledian untuk dua dimensi antara P(x1,y1) dan Q(x2,y2) adalah:
Euclide heorem


Step by step K-Means

gambarkMeans
Gambar 1 Step by step K means

Contoh Soal:

  • Misalkan kita memiliki 10 data A,B,C,...J seperti tergambar berikut ini:
Gambar 2 plot posisi data

  • STEP 1: Tentukan berapa klaster yang akan dibentuk atau tentukan nilai k. Misalkan kita tentukan saja ada 3 klaster yang akan kita buat. Jadi k=3. 
  • Sampai dengan step 1 ini semua klaster masih kosong atau  C1={}, C2={}, C3={}.

ITERASI 1

  • STEP 2; Tentukan satu wakil data dari setiap klaster secara acak. Wakil  data ini disebut dengan centroid karena letaknya di tengah klaster. Karena klaster ada 3, maka centroid yang kita buat harus tiga juga. Misalkan titik C, G, I.
    Catatan: Titik centroid awal tidak harus merupakan data, boleh juga sembarang titik secara acak. 
Gambar 3 Tiga titik centroid awal


  • STEP 3; Untuk masing-masing anggota, Tentukan centroid mana yang paling dekat dengannya. Masing-masing titik dihitung jarak Euclediannya ke tiap-tiap centroid, dan kemudian kita pilih centroid dengan jarak terdekat.
Gambar 4 Menghitung centroid terdekat pada iterasi 1

  • STEP 4: Buat ketiga klaster 
Gambar 4 Membuat klaster pada iterasi 1

  • STEP 5: Pada iterasi 1, semua klaster mengalamibanyak perubahan. C1 dari kosong menjadi {A,B,C,D,E,H} C2 menjadi {F,G} dan C3 menjadi {I,J}. Sehingga perlu dilakukan iterasi lagi.

ITERASI 2:

  • STEP 2: Sekarang hitung ulang titik-titik centroid masing-masing klaster.
Gambar 5 Menghitung ulang centroid untuk iterasi 2

  • STEP 3: Kalau sudah, untuk setiap anggota, tentukan titik centroid terdekat dengannya.
Gambar 6 Menghitung centroid terdekat di iterasi 2

  • STEP 4: Buat lagi tiga klaster hasil iterasi 2
Gambar 7 Klaster hasil iterasi 2

  • STEP 5: Bila kia bandingkan gambar 4 dan gambar 7, semua klaster masih berubah. C1 kehilangan dua anggota enjadi {A,B,C,D}, C2 bertambah 1 anggota menjadi {E,F,G}, dan C3 bertambah 1 anggota menjadi {H,I,J}. Sehingga masih perlu diperiksa di iterasi berikutnya.

ITERASI 3:

  • STEP 2: Hitung ulang titik centroid
Gambar 8 Hitung 3 centroid di iterasi 3

  • STEP 3: Untuk setiap anggota tentukan lagi titik centroid terdekat.
Gambar 9 Hitung titik centroid terdekat

  • STEP 4: Buat lagi ketiga klaster.
Gambar 10 Hasil klaster di iterasi 3

  • STEP 5: Bila dibandingkan gambar 7 dan gambar 10 perubahan klaster sudah tidak ada sehingga iterasi tidak perlu kita dilanjutkan.
Gambar 11 Hasil Kmeans Clustering

KESIMPULAN

  • Jadi, hasil proses klasterisasi terlihat pada gambar 11. Kesimpulan Data-data dapat dibagi menjadi 3 klaster yaitu {A, B, C, D},{E, F, G}, {H, I, J}.

Daftar Pustaka

Tan, P.N., Steinbach, M., Kumar, V. (2006) Introduction to Data Mining. Boston:Pearson Education.



Instalasi R

  • Cari installation R di google.com

  • Klik download R 3.5.1 berarti versi terbaru saat ini adalah versi 3.5.1. Kemudian muncul halaman dari cran.r-project.org sbb:

  • Klik Download R 3.5.1 for Windows (62 megabytes, 32/64 bit) bila anda mempergunakan windows operating system. Sebuah file installer akan secara otomatis terdownload.
  • Kalau sudah selesai downloadnya temukan dan klik file installer tsb. Saat ini nama filenya adalah R-3.5.1-win.exe.
  • Klik yes pada User Account Control
  • Pilih languange (bahasa) English
  • Klik Next
  • Klik Next lagi
  • Klik Next sampai muncul halaman berikut

  • Pilih No. Kemudian muncul halaman berikut.
  • Bila anda ingin membuat start menu folder silakan diketik di folder mana atau bisa ditentukan dengan menekan tombol Browse. Namun, bila anda tidak mau start menu folder tick option Don't create a Start Menu folder. Bila sudah klik Next.
  • Klik Next lagi
  • R mulai terinstal

  • Tunggu sampai proses instalasi selesai, maka muncul halaman berikut

  • Klik Finish. Sampai disini kita sudah berhasil menginstal R saat ini versi 3.5.1.









Belajar K Means menggunakan R

K Means Clustering adalah sebuah algoritma untuk membagi-bagi data menjadi beberapa klaster berdasarkan kemiripan sifat-sifatnya.

Cara kerja Kmeans membuat klaster di R:
  • Pertama-tama kita tentukan berapa klaster yang ingin dibuat, misalkan k. Nilai k ini bisa 2, 3, 4 dst. Kemudian data yang kita dapatkan akan dibagi-bagi menjadi k klaster.
  • Kedua, satu anggota akan dipilih secara acak menjadi wakil dari klaster pertama, kemudian dipilih lagi satu anggota yang lain sebagai wakil dari klaster kedua. Dan seterusnya sampai setiap klaster memiliki satu wakil. Wakil-wakil klaster ini disebut dengan centroid, karena memang letaknya dianggap sebagai titik central klaster. 
  • Kemudian baru dijalankan proses iterasi dalam 2 langkah:
    • Satu: Setiap data ditentukan masuk ke salah satu klaster berdasarkan centroid mana yang terdekat dengannya.
    • Dua: Hitung ulang centroid untuk tiap-tiap klaster
  • Iterasi tetap dijalankan sampai tidak ditemukan variasi klaster yang baru 
  • Hasilnya adalah sebuah model klaster



Kelebihan Kmeans

  • Cukup teliti karena bisa dilakukan berulang-ulang sampai kepada variasi klaster yang paling kecil.
  • Mudah untuk diimplementasikan.
  • Suatu data masih ada peluang pindah ke klaster yag lebih dekat sehingga masih bisa didapatkan model klaster yang lebih baik lagi. 

Kelemahan Kmeans

  • Karena penunjukkan centroid dilakukan secara acak, maka terkadang hasilnya bagus sekali, kadang bisa juga meleset. Untuk itu langkah-langkah di atas perlu diulang beberapa kali. Pada program R sudah disediakan parameter nstarter untuk kita dapat menentukan berapa kali langkah kerja kmeans diulang.
  • Karena sifatnya yang harus diualng-ulang maka untuk data yang sangat besar akan membutuhkan waktu proses yang lama sehingga kurang efisien. Tetapi, kalau memang tujuannya untuk mencari ketepatan prediksi dan mengabaikan waktu proses, ya nggak apa-apa diulang-ulang.

Tahap Eksplorasi Data


Untuk mempelajari cara kerja Kmeans, kali ini, kita mempergunakan dataset Iris yang sudah ada pada R. Dalam dataset ini, berisi data spesies bunga iris yang diukur dari panjang dan lebar bagian-bagian bunga iris yaitu sepal dan petal.

Mari kita lihat dataset ini. Ketik dan run pada program R berikut:
>library(datasets)
>head(iris)
Hasilnya:

Seperti yang sudah diberikan di atas, dataset iris merupakan sampel bunga iris dimana ada 4 variabel yang dipergunakan untuk mempelajari spesies bunga iris. Keempat variabel diukur dari panjang dan lebar bagian sepal dan panjang dan lebar bagian petal. Hanya ada 3 jenis spesies dalam datset ini yaitu setosa, versicolor, virginica. 

Dalam percobaan kali ini, kita hanya pergunakan 2 buah variabel yaitu Petal.Length (kolom ketiga) dan Petal.Width (kolom keempat) untuk memprediksi spesiesnya apa. Kmeans kita pergunakan untuk membuat 3 klaster sesuai banyaknya klaster bunga iris. Nanti hasil klaster Kmeans kita cocokkan dengan dataset iris untuk mengukur ketepatan algoritma Kmeans  dalam memisahkan spesies bunag iris ini.

Kemudian kita coba lihat lebih detil data bunga iris dengan visualisasi grafik plot yaitu ggplot pada library ggplot2 pada packages ggplot2. Ketik dan run pada program:
>install.packages("ggplot2") #jika belum ada
>library(ggplot2) #menggunakan library ggplot2
>ggplot(iris, aes(Petal.Length, Petal.Width, color = Species)) + geom_point()

Lihat pada bagian plots, akan tampil gambar berikut ini



Bagian yang berwarna merah adalah spesies setosa. Seperti terlihat pada gambar di atas, spesies ini terpisah jauh dari kedua spesies lainnya. Sehingga akan mdah dipisahkan menjadi satu klaster tersendiri. Antara spesies virginica dan versicolor terlihat beberapa titik terlalu berdekatan. Hal ini akan menjadi tantangan tersendiri untuk memisahkan kedua spesies tersebut 100%.  Ok kita pasang target 95% keberhasilan kita membuat klaster spesies bunga iris.


Klasterisasi Spesies Bunga Iris


Tadi kita sudah lihat datanya, sekarang kita coba untuk membuat klasternya. Karena proses awal klaster bersifat acak, kita tentukan seed (1234) dimana kita akan buat tiga klaster k=3, karena spesies bunga  iris memang ada 3 dengan hanya menggunakan variabel petal.length dan petal.width yang merupakan kolom ke 3 dan 4 di dataset iris.

>set.seed(1234)
>irisCluster <- kmeans(iris[, 3:4], 3, nstart = 20)
>irisCluster

Kita tentukan nstart = 20 artinya R akan melakukan proses klasterisasi Kmeans sebanyak 20x secara acak dan menghasilkan klaster dengan variasi terrendah.Kita dapat melihat centroid, data-data dalam klasterdan variasi klaster. 


Hasilnya:


Sekarang, mari kita bandingkan hasil klaster dengan data species bunga iris yang sesungguhnya. Ketik pada program run:
>table(irisCluster$cluster, iris$Species)

Hasilnya adalah sebuah confusion matrix:



Spesies setosa=cluster 1, species versicolor = cluster 2, dan spesiesvirginica=cluster 3. K means gagal memprediksi 2 versicolor, dan 4 virginica totsl 6 kesalahan. Sedangkan yang lainnya benar. yaitu 50+48+46=144. Jadi akurasi Kmeans adalah  144/(144+6)=96%. Berarti target kita tercapai.

Sekarang, mari kita visualisasi hasil klaster ini. Ketik dan run pada program:
irisCluster$cluster <- as.factor(irisCluster$cluster)
ggplot(iris, aes(Petal.Length, Petal.Width, color = irisCluster$cluster)) + geom_point()

Hasil klaster kita terlihat sbb:


Instalasi Rstudio


  • Buka google.com cari Rstudio, klik download Rstudio

  • Kemudian muncul halaman sbb:

  • Klik tombol download dibawah tulisan Free (Gratis), kemudian muncul halaman berikut.

  • Klik RStudio 1.1.456 - Windows Vista/7/8/10 bila anda mempergunakan windows operating system.
  • Kemudian file installer terdownload secara otomatis
  • Kalau sudah selesai, klik pada file installer tsb (RStudio-1.1.456.exe)
  • Klik allow pada user account control
  • Kemudian akan muncul halaman RStudio Setup berikut.
  • klik next
  • klik next
  • klik install, kemudian muncul halaman berikut.
  • tunggu sampai proses instalasi selesai, Bila sudah selesai akan muncul halaman berikut.

  • Klik Finish. Sampai disini proses instalasi Rstudio berhasil kita lakukan.

Model K-Means

K-means adalah model data dimana data-data dikelompokkan ke dalam beberapa cluster. Masing-masing cluster memiliki satu centroid, yaitu titik tengah cluster yang dihitung dari jarak eucledian rata-rata masing-masing data yang ada dalam cluster tsb. Menurut Tan, 2006 clustering merupakan sebuah proses untuk mengelompokan data ke dalam beberapa cluster sehingga data dalam satu cluster memiliki tingkat kemiripan yang maksimum dan data antar cluster memiliki kemiripan yang minimum.

Jarak Euclidean

Jarak Euclidean adalah perhitungan jarak dari 2 buah titik atau lebih dalam Euclidean space. Euclidean space diperkenalkan oleh Euclid, seorang matematikawan dari Yunani sekitar tahun 300 Sebelum Masehi.

Jarak Euclidean Pada 1 dimensi

Rumus jarak dalam 1 dimensi
rumus1dimensi
Misalkan kita ingin menghitung jarak Euclidean 1 dimensi. Titik pertama adalah 10, titik kedua adalah 30. Caranya adalah kurangkan 30 dengan 10 sehingga menghasilkan 20. Hitung nilai kuadratnya sehingga kita mendapat nilai 400. Kemudian diakarkan sehingga mendapatkan nilai 20. Sehingga jarak euclidean dari 2 titik tersebut adalah 20.


Jarak Euclidean Pada 2 dimensi

Koordinat Jarak
Caranya hampir sama. Misalkan titik pertama mempunyai kordinat (1,2). Titik kedua ada di kordinat (5,5). Caranya adalah kurangkan setiap kordinat titik kedua dengan titik yang pertama. Yaitu, (5-1,5-2) sehingga menjadi (4,3). Kemudian pangkatkan masing-masing sehingga memperoleh (16,9). Kemudian tambahkan semuanya sehingga memperoleh nilai 16+9 = 25. Hasil ini kemudian diakarkan menjadi 5. Sehingga jarak euclideannya adalah 5

Rumus jarak Eucledian untuk dua dimensi antara P(x1,y1) dan Q(x2,y2) adalah:
Euclide heorem


Step by step K-Means


gambarkMeans
gambar 1 Step-by-step K-Means




















Contoh Kasus:
Misalkan seorang data analis ingin membuat cluster kepadatan penduduk tinggi dan rendah pada sebuah propinsi dengan mengambil sampel dari 10 kota, didapatkan data kepadatan penduduk dalam ribuan per km persegi sbb:


Kota
 Kepadatan
A 636
B 473
C 487
D 576
E 788
F 639
G 777
H 244
I 511
J 468

Iterasi ke-1


Langkah (1) Tentukan k. Untuk soal di atas jumlah pengelompokan adalah 2 sehingga k=2.

Langkah (2) Hitung Centroid: dipilih 2 centroid secara acak yaitu kota H (244) dan Kota G(777). 

Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1, dan J2 adalah jarak masing-masing kota dengan centroid kedua.

Kota
Kepadatan
J1
J2
Iterasi 1
A
636
392
141
C2
B
473
229
304
C1
C
487
243
290
C1
D
576
332
201
C2
E
788
544
11
C2
F
639
395
138
C2
G
777
533
0
C2
H
244
0
533
C1
I
511
267
266
C2
J
468
224
309
C1

Langkah (4) kolom iterasi1 menunjukkan proses clusterisasi: Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,H,I} dan cluster C2={A,D,E,F,G,J}.

Langkah (5) Hitung banyaknya perubahan: Pada iterasi 1 ini sepuluh kota berubah clusternya sehingga perlu dirasakan untuk menambah iterasi lagi.


Iterasi ke-2


Langkah (2) Hitung Centroid: centroid cluster C1 adalah rata-rata (mean) dari kota B, C, H, dan I yaitu(473+487+244+468)/4=418. Sedangkan centroid cluster C2 didapatkan dengan menghtung mean kota A,D,E,F,G,J, yaitu (636+576+...+511)/6=654.5.

Kota Kepadatan Iterasi 1 Means
B 473 C1 418
C 487
H 244
J 468
A 636 C2 654.5
D 576
E 788
F 639
G 777
I 511


                                                                          
Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1 yang baru, dan J2 adalah jarak masing-masing kota dengan centroid kedua yang baru di iterasi ke-2.

Kota
Kepadatan
J1
J2
Iterasi 1
Iterasi 2
Perubahan
A
636
118
18.5
C2
C2
TIDAK
B
473
45
181.5
C1
C1
TIDAK
C
487
31
167.5
C1
C1
TIDAK
D
576
58
78.5
C2
C1
YA
E
788
270
133.5
C2
C2
TIDAK
F
639
121
15.5
C2
C2
TIDAK
G
777
259
122.5
C2
C2
TIDAK
H
244
274
410.5
C1
C1
TIDAK
I
511
7
143.5
C2
C1
YA
J
468
50
186.5
C1
C1
TIDAK
Langkah (4) kolom iterasi 2 menunjukkan clusterisasi : Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,D,H,I,J} dan cluster C2={A,E,F,G}.
Langkah (5) Hitung banyaknya perubahan: Bila dibandingkan dengan iterasi pertama, maka ada dua kota yang berubah cluster yaitu kota D dan I dari cluster C2 pindah ke cluster C1. Pada iterasi 2 ini tinggal 2 kota saja yang berubah clusternya. Tapi masih perlu dirasakan untuk menambah iterasi lagi untuk memeriksa apakah perubahan bisa diturunkan lagi.

Iterasi ke-3

Langkah (2) Hitung Centroid: centroid cluster C1 centroid adalah rata-rata (mean) dari kota B,C,D,H,I, dan J yaitu (473+487+…+468)/6=459.83. Centrod cluster C2 didapatkan dengan menghtung mean kota A,E,F,G, yaitu (636+788+639+777)/4=710.
KotaKepadatanIterasi 2Means
B473C1    459.83
C487
D576
H244
I511
J468
A636C2710
E788
F639
G777
Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1 yang baru, dan J2 adalah jarak masing-masing kota dengan centroid kedua yang baru di iterasi ke-3.
Kota
Kepadatan
J1
J2
Iterasi 2
Iterasi 3
Perubahan
A
636
176.17
74
C2
C2
TIDAK
B
473
13.17
237
C1
C1
TIDAK
C
487
27.17
223
C1
C1
TIDAK
D
576
116.17
134
C1
C1
TIDAK
E
788
328.17
78
C2
C2
TIDAK
F
639
179.17
71
C2
C2
TIDAK
G
777
317.17
67
C2
C2
TIDAK
H
244
215.83
466
C1
C1
TIDAK
I
511
51.17
199
C1
C1
TIDAK
J
468
8.17
242
C1
C1
TIDAK
Langkah (4) kolom iterasi3 menunjukkan proses clusterisasi : Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,D,H,I,J} dan cluster C2={A,E,F,G}.
Langkah (5) hitung banyaknya perubahan: Bila dibandingkan antara iterasi kedua dan ketiga, maka sudah tidak ada perubahan cluster. Sehingga proses K-mean selesai sampai iterasi ke-3 saja.
Kesimpulan dari kota-kota A, B, C, … J yang termasuk kota dengan kepadatan penduduk tinggi (cluster C2) yaitu A, E, F dan G, sedangkan kota-kota B,C,D,H,I, dan J termasuk kota dengan kepadatan rendah (Cluster C1)

Daftar Pustaka


Tan, P.N., Steinbach, M., Kumar, V. (2006) Introduction to Data Mining. Boston:Pearson Education.