Pengertian Analisis Cluster

Klastering adalah metode analisis data yang populer dan memainkan peran penting dalam data mining (Jiang et al. 2010). Klastering merupakan sebuah teknik unsupervised learning karena tidak adanya target label dalam prosesnya (He and Tan 2012), yang bertujuan untuk mengelompokkan data ke dalam beberapa kelompok atau klaster (Zhang, Ouyang, and Ning 2010) sehingga data dalam satu kelompok memiliki tingkat kemiripan yang maksimum dan data antar kelompok memiliki tingkat kemiripan yang minimum (Xiang et al. 2015). Kemiripan antar data dapat diketahui dengan menghitung jarak antar data (Han, Kamber, and Pei 2012). Semakin kecil jarak antar data maka semakin tinggi kemiripan antar data tersebut dan sebaliknya (Gan, Ma, and Wu 2007). Analisis klaster telah banyak diaplikasikan dalam berbagai bidang diantaranya riset pasar (Shahbaba and Beheshti 2014), kesehatan dan perbankan (Ammar, Elouedi, and Lingras 2016), segmentasi citra (Xu et al. 2015), pengenalan pola, pengambilan keputusan, machine learning (Yi et al. 2010).

Menurut Han dan Kamber (Han, Kamber, and Pei 2012)terdapat banyak algoritma klastering, tetapi secara umum metode-metode utama dalam analisis klaster dapat dikelompokkan berdasarkan metode partisi, metode hirarki, metode berbasis densitas dan metode berbasis grid. Metode klastering yang paling populer adalah metode hirarki dan metode partisi (A. T. de Carvalho, Lechevallier, and Melo 2012). Metode Hirarki mengelompokkan data menjadi seperti struktur pohon (Krishnasamy, Kulkarni, and Paramesran 2014) dengan cara membuat dekomposisi atau pemecahan objek secara hirarki dengan memisahkan data menjadi subset yang lebih kecil. Metode ini dapat diklasifikasikan menjadi dua, yaitu metode agglomerative dan metode devisive. Metode agglomerative atau disebut juga dengan pendekatan bottom-up, dimulai dengan setiap titik data membentuk kelompok atau klaster yang terpisah. Kemudian secara berturut-turut menggabungkan data yang mempunyai kemiripan hingga semua data berada dalam klaster yang sama. Sedangkan metode devisive atau disebut juga dengan pendekatan top-down, dimana proses pengelompokkan dimulai dengan semua titik data berada dalam satu klaster, kemudian membagi klaster ke dalam klaster yang lebih kecil. Kelebihan metode hirarki adalah tidak membutuhkan informasi jumlah klaster dan juga penentuan nilai-nilai awal sehingga hasil klastering selalu sama , namum membutuhkan waktu komputasi tinggi pada dataset yang besar daripada metode partisi.

Algoritma K-Means

K-means merupakan salah satu metode hard partition yang banyak digunakan untuk pengelompokan data. Algoritma K-means adalah dasar pengelompokan metode partisi yang dipublikasikan oleh Lloyd dari Bell Telephone Laboratories pada tahun 1957. Penelitian pada K-means dapat ditelusuri kembali ke pertengahan abad yang lalu, yang dilakukan oleh berbagai peneliti diseluruh disiplin ilmu yang berbeda terutama oleh Lloyd (1957), Forgey (1965), Friedman dan Robin (1967) dan MacQueen (1967). K-means dapat didefinisikan sebagai algoritma klastering yang mengelompokan data ke dalam k klaster berdasarkan jarak terdekat data dengan pusat klaster. Algoritma K-means sangat efisien untuk mengelompokan dataset yang besar, kemudahan dalam pengaplikasiannya dan metode yang efisien dalam hal komputasi, menjadi alasan utama popularitas K-means, meskipun telah diusulkan lebih dari 50 tahun yang lalu.

Algoritma K-means mengelompokan objek ke dalam kelompok sehingga objek dalam satu klaster memiliki kemiripan yang tinggi dibandingkan dengan objek di dalam klaster yang berbeda. K-means dimulai dengan menentukan jumlah klaster sebanyak k, kemudian membangkitkan k pusat klaster secara acak. Selanjutnya setiap objek akan dikelompokan berdasarkan jarak terdekat dengan pusat klaster, pusat klaster diperbaharui berdasarkan titik data dalam setiap klaster. Proses ini diulangi sampai kriteria konvergen terpenuhi. Berikut ini adalah tahapan dari algoritma K-means:

  1. Menentukan nilai k sebagai jumlah klaster yang dibentuk.

  2. Memilih k pusat klaster secara acak untuk menjadi pusat klaster awal.

  3. Alokasikan semua data ke pusat klaster terdekat dengan matrik jarak.

  4. Hitung kembali pusat klaster baru berdasarkan data yang mengikuti klaster masing-masing.

  5. Ulangi langkah 3 dan 4 hingga kondisi konvergen tercapai atau tidak ada data yang berpindah dari satu klaster ke klaster yang lainnya.

Eksperimen Algoritma K-Means

Pada eksprimen ini algoritma K-Means akan digunakan untuk mengelompokan data kemiskinan di Jawa Tengah yang diambil dari website Tim Percepatan Penanggulangan Kemiskinan (TNP2K)

Read Data

Package readr menyiapkan fungsi read_csv() untuk import data dari file CSV. Pada kasus ini digunakan data Data 40% Kemiskinan di jawa Tengah.

library (readr)
urlfile = "https://raw.githubusercontent.com/dedenistiawan/Dataset/main/BDT.csv"

data<-read.csv(url(urlfile), row.names = "Kabupaten")
data

Memeriksa Missing Value

colSums(is.na(data))
##                       jumlah.penduduk                         KRT.perempuan 
##                                     0                                     0 
##      jumlah.anak.tidak.sekolah.7.18th                 jumlah.indiv.yg.cacat 
##                                     0                                     0 
##          jumlah.indiv.penyakit.kronis              jumlah.indiv.tdk.bekerja 
##                                     0                                     0 
##       sumber.air.minum.tdk.terlindung                penerangan.tdk.listrik 
##                                     0                                     0 
## bahan.bakar.masak.minyak.tanah...kayu                    BAB.tdk.ada.jamban 
##                                     0                                     0

Hasil output di atas menunjukan bahwa tidak missing value di semua variabel

Membuat Matriks Jarak

#Plot Disatance
library(ggplot2)
library(factoextra)
distance <- get_dist(data)
fviz_dist(distance, gradient = list(low = "#00AFBB", mid = "white", high = "#FC4E07"))

Matriks jarak ini berfungsi untuk mengukur jarak antar variabel, semakin merah warnanya maka semakin jauh jarak antar variabel dan semakin biru semakin dekat jarak anntar variabel.

Menentukan Jumlah Cluster

Dalam metode k-means banyaknya klaster ditentukan sendiri oleh pengguna. Maka dari itu perlu dicari jumlah klaster yang optimum yang dapat mengelompokkan objek dengan baik (Perlu diketahui bahwa metode ini relatif subjektif). Salah satu metode yang digunakan adalah Elbow Plot. Elbow Plot merupakan plot antara banyak klaster dengan total within-cluster variation (total dari simpangan per kluster). Banyak klaster yang dipilih adalah bagian “siku” atau titik dimana terdapat penurunan yang tajam sebelum titik tersebut dan disusul penurunan yang tidak tajam setelah titik tersebut. Hal ini karena penambahan jumlah klaster tidak membawa pengaruh banyak atas variasi yang ada di dalam klaster tersebut.

Membuat Plot Cluster

Jumlah klaster yang dibentuk mulai dari 2 sampai 5, untuk melihat sebaran data pada masing-masing cluster

#use several different values of k
k2 <- kmeans(data, centers = 2, nstart = 25)
k3 <- kmeans(data, centers = 3, nstart = 25)
k4 <- kmeans(data, centers = 4, nstart = 25)
k5 <- kmeans(data, centers = 5, nstart = 25)
# plots to compare
p1 <- fviz_cluster(k2, geom = "point", data = data) + ggtitle("k = 2")
p2 <- fviz_cluster(k3, geom = "point",  data = data) + ggtitle("k = 3")
p3 <- fviz_cluster(k4, geom = "point",  data = data) + ggtitle("k = 4")
p4 <- fviz_cluster(k5, geom = "point",  data = data) + ggtitle("k = 5")
library(gridExtra)
grid.arrange(p1, p2, p3, p4, nrow = 2)

Menentukan Jumlah Cluster

Metode Elbow

Metode Elbow merupakan suatu metode yang digunakan untuk menghasilkan informasi dalam menentukan jumlah cluster terbaik dengan cara melihat persentase hasil perbandingan antara jumlah cluster yang akan membentuk siku pada suatu titik. Metode ini memberikan ide/gagasan dengan cara memilih nilai cluster dan kemudian menambah nilai cluster tersebut untuk dijadikan model data dalam penentuan cluster terbaik. Dan selain itu persentase perhitungan yang dihasilkan menjadi pembanding antara jumlah cluster yang ditambah. Hasil persentase yang berbeda dari setiap nilai cluster dapat ditunjukan dengan menggunakan grafik sebagai sumber informasinya. Jika nilai cluster pertama dengan nilai cluster kedua memberikan sudut dalam grafik atau nilainya mengalami penurunan paling besar maka nilai cluster tersebut yang terbaik.

#Determining number Optimal Clusters
##Elbow Method
library(ggplot2)
library(factoextra)
fviz_nbclust(data, kmeans, method = "wss") +
  geom_vline(xintercept = 2, linetype = 2)

Metode elbow menggunakan nilai total wss (whitin sum square) sebagai penentu 𝐾 optimalnya. Dari gambar di atas terlihat garis mengalami patahan yang membentuk elbow atau siku pada saat 𝐾 = 2. Maka dengan menggunakan metode ini diperoleh 𝐾 optimal pada saat berada di 𝐾 = 2.

Metode Silhouette

Silhouette Coefficient digunakan untuk melihat kualitas dan kekuatan cluster, seberapa baik suatu objek ditempatkan dalam suatu cluster. Metode ini merupakan gabungan dari metode cohesion dan separation.

##Average Silhouette Method
fviz_nbclust(data, kmeans, method = "silhouette")

Pendekatan rata-rata nilai metode silhouette untuk menduga kualitas dari klaster yang terbentuk. Semakin tinggi nilai rata-ratanya maka akan semakin baik. Berdasarkan grafik pada gambar di atas banyak klaster optimal yang terbentuk pada 𝐾 = 2.

Jumlah Klaster Optimal

Dari pendekatan metode elbow dan metode Silhouette di dapatkan jumlah cluster optimal adalah K=2. setelah ini dilakukan eksperimen jumlah K=2

#Computing k-means clustering
#Compute k-means with k = 2
set.seed(123)
km.res <- kmeans(data, 2, nstart = 25)
# Print the results
print(km.res)
## K-means clustering with 2 clusters of sizes 22, 13
## 
## Cluster means:
##   jumlah.penduduk KRT.perempuan jumlah.anak.tidak.sekolah.7.18th
## 1        1.917786      2.017477                         1.675955
## 2        4.446831      4.278100                         4.856077
##   jumlah.indiv.yg.cacat jumlah.indiv.penyakit.kronis jumlah.indiv.tdk.bekerja
## 1              1.948245                     1.889941                 1.727609
## 2              4.395277                     4.493946                 4.768662
##   sumber.air.minum.tdk.terlindung penerangan.tdk.listrik
## 1                        1.558414               1.286668
## 2                        5.055008               5.514877
##   bahan.bakar.masak.minyak.tanah...kayu BAB.tdk.ada.jamban
## 1                              1.952068           1.454800
## 2                              4.388800           5.230331
## 
## Clustering vector:
##         CILACAP        BANYUMAS     PURBALINGGA    BANJARNEGARA         KEBUMEN 
##               2               2               2               2               2 
##       PURWOREJO        WONOSOBO        MAGELANG        BOYOLALI          KLATEN 
##               1               1               2               1               2 
##       SUKOHARJO        WONOGIRI     KARANGANYAR          SRAGEN        GROBOGAN 
##               1               1               1               1               2 
##           BLORA         REMBANG            PATI           KUDUS          JEPARA 
##               1               1               2               1               2 
##         DEMAK          SEMARANG      TEMANGGUNG          KENDAL          BATANG 
##               1               1               1               1               1 
##      PEKALONGAN        PEMALANG           TEGAL          BREBES   KOTA MAGELANG 
##               1               2               2               2               1 
##  KOTA SURAKARTA   KOTA SALATIGA   KOTA SEMARANG KOTA PEKALONGAN      KOTA TEGAL 
##               1               1               1               1               1 
## 
## Within cluster sum of squares by cluster:
## [1] 262.6465 465.8942
##  (between_SS / total_SS =  51.3 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Menentukan nilai centroid akhir K-Means untuk melihat karakteristik data

aggregate(data, by=list(cluster=km.res$cluster), mean)

Menggabungkan hasil cluster algoritma K-Means dengan data

dd <- cbind(data, cluster = km.res$cluster)
head(dd)

Melihat hasil cluster akhir pada setiap kabupaten

# Cluster number for each of the observations
km.res$cluster
##         CILACAP        BANYUMAS     PURBALINGGA    BANJARNEGARA         KEBUMEN 
##               2               2               2               2               2 
##       PURWOREJO        WONOSOBO        MAGELANG        BOYOLALI          KLATEN 
##               1               1               2               1               2 
##       SUKOHARJO        WONOGIRI     KARANGANYAR          SRAGEN        GROBOGAN 
##               1               1               1               1               2 
##           BLORA         REMBANG            PATI           KUDUS          JEPARA 
##               1               1               2               1               2 
##         DEMAK          SEMARANG      TEMANGGUNG          KENDAL          BATANG 
##               1               1               1               1               1 
##      PEKALONGAN        PEMALANG           TEGAL          BREBES   KOTA MAGELANG 
##               1               2               2               2               1 
##  KOTA SURAKARTA   KOTA SALATIGA   KOTA SEMARANG KOTA PEKALONGAN      KOTA TEGAL 
##               1               1               1               1               1

Melihat jumlah anggota cluster

# Cluster size
km.res$size
## [1] 22 13

Membuat plot hasil cluster

# Cluster means
km.res$centers
##   jumlah.penduduk KRT.perempuan jumlah.anak.tidak.sekolah.7.18th
## 1        1.917786      2.017477                         1.675955
## 2        4.446831      4.278100                         4.856077
##   jumlah.indiv.yg.cacat jumlah.indiv.penyakit.kronis jumlah.indiv.tdk.bekerja
## 1              1.948245                     1.889941                 1.727609
## 2              4.395277                     4.493946                 4.768662
##   sumber.air.minum.tdk.terlindung penerangan.tdk.listrik
## 1                        1.558414               1.286668
## 2                        5.055008               5.514877
##   bahan.bakar.masak.minyak.tanah...kayu BAB.tdk.ada.jamban
## 1                              1.952068           1.454800
## 2                              4.388800           5.230331
fviz_cluster(km.res, data = data)

fviz_cluster(km.res, data = data,
             palette = c("#2E9FDF", "#00AFBB", "#E7B800", "#FC4E07"),
             ellipse.type = "euclid", # Concentration ellipse
             star.plot = TRUE, # Add segments from centroids to items
             repel = TRUE, # Avoid label overplotting (slow)
             ggtheme = theme_minimal())

Reference

A. T. de Carvalho, Francisco de, Yves Lechevallier, and Filipe M. de Melo. 2012. “Partitioning Hard Clustering Algorithms Based on Multiple Dissimilarity Matrices.” Pattern Recognition 45 (1): 447–64. https://doi.org/10.1016/j.patcog.2011.05.016.
Ammar, Asma, Zied Elouedi, and Pawan Lingras. 2016. “Meta-Clustering of Possibilistically Segmented Retail Datasets.” Fuzzy Sets and Systems 286 (March): 173–96. https://doi.org/10.1016/j.fss.2015.07.019.
Gan, Guojun, Chaoqun Ma, and Jianhong Wu. 2007. “Data Clustering: Theory, Algorithms, and Applications,” January. https://doi.org/10.1137/1.9780898718348.
Han, Jiawei, Micheline Kamber, and Jian Pei. 2012. “Data Mining Concepts and Techniques, Third Edition.” Waltham, Mass.: Morgan Kaufmann Publishers. 2012.
He, Hong, and Yonghong Tan. 2012. “A Two-Stage Genetic Algorithm for Automatic Clustering.” Neurocomputing 81 (April): 49–59. https://doi.org/10.1016/j.neucom.2011.11.001.
Jiang, Hua, Shenghe Yi, Jing Li, Fengqin Yang, and Xin Hu. 2010. “Ant Clustering Algorithm with K-Harmonic Means Clustering.” Expert Systems with Applications 37 (12): 8679–84. https://doi.org/10.1016/j.eswa.2010.06.061.
Krishnasamy, Ganesh, Anand J. Kulkarni, and Raveendran Paramesran. 2014. “A Hybrid Approach for Data Clustering Based on Modified Cohort Intelligence and k-Means.” Expert Systems with Applications 41 (13): 6009–16. https://doi.org/10.1016/j.eswa.2014.03.021.
Shahbaba, Mahdi, and Soosan Beheshti. 2014. “MACE-Means Clustering.” Signal Processing 105 (December): 216–25. https://doi.org/10.1016/j.sigpro.2014.05.036.
Xiang, Wan-li, Ning Zhu, Shou-feng Ma, Xue-lei Meng, and Mei-qing An. 2015. “A Dynamic Shuffled Differential Evolution Algorithm for Data Clustering.” Neurocomputing 158 (June): 144–54. https://doi.org/10.1016/j.neucom.2015.01.058.
Xu, Qin, Chris Ding, Jinpei Liu, and Bin Luo. 2015. “PCA-Guided Search for K-Means.” Pattern Recognition Letters 54 (March): 50–55. https://doi.org/10.1016/j.patrec.2014.11.017.
Yi, Baolin, Haiquan Qiao, Fan Yang, and Chenwei Xu. 2010. “2010 International Conference on Computational Intelligence and Software Engineering (CiSE).” In. IEEE. https://doi.org/10.1109/cise.2010.5676975.
Zhang, Changsheng, Dantong Ouyang, and Jiaxu Ning. 2010. “An Artificial Bee Colony Approach for Clustering.” Expert Systems with Applications 37 (7): 4761–67. https://doi.org/10.1016/j.eswa.2009.11.003.