Perbandingan Clustering KMeans dengan DBSCAN

Perbandingan Clustering KMeans dengan DBSCAN – Postingan ini akan memberikan kalian perbandingan kinerja mengenai algoritma Clustering KMeans dengan DBSCAN. Untuk menilai berapa jumlah cluster yang terbaik, bisa kalian baca disini atau disini.

Algoritma KMeans telah banyak dibahas dan banyak digunakan secara umum karena sangat mudah, namun demikian algoritma ini kurang begitu tahan ketika terjadi overlapping data. Kalian bisa melihat plot dataset berikut

Kalian melihat, setidaknya ada 5 cluster atau grouping, dengan 2 diantaranya overlapping. Kalau pun kita paksa menggunakan KMeans Clustering, hasilnya tidak bagus.

jangan lupa untuk instal library terlebih dahulu

install.packages("factoextra")
install.packages("fpc")

Loading library yang digunakan yaitu

library(dbscan)
library(factoextra)
library(fpc)
library(dplyr)
library(cluster)

Kode untuk perhitungan Kmeans Clustering

data("multishapes")
df <- multishapes[, 1:2]
set.seed(123)
result_kmeans = kmeans(df, 5, nstart = 25)
fviz_cluster(result_kmeans, df,  geom = "point", 
             ellipse= FALSE, show.clust.cent = FALSE,
             palette = "jco", ggtheme = theme_classic())

Kode untuk perhitungan DB Clustering

Untuk dibutuhkan algoritma clustering yang lain seperti Fuzzy C-Means Clustering. Namun saat ini, saya tidak menggunakan algoritma tersebut dan menggunakan algoritma DBSCAN saja untuk melihat kinerjanya.  Kita akan menggunakan package fpc.

db <- fpc::dbscan(df, eps = 0.15, MinPts = 2)
fviz_cluster(db, data = df, stand = FALSE,
             ellipse = FALSE, show.clust.cent = FALSE,
             geom = "point",palette = "jco", ggtheme = theme_classic())

Kalian bisa melihat hasil sebagai berikut

Sekilas Algoritma dbcan

Tujuannya adalah untuk mengidentifikasi daerah padat-dense region, yang dapat diukur dengan jumlah objek yang mendekati titik tertentu. Dua parameter penting diperlukan untuk DBSCAN: epsilon (“eps”) dan poin minimum (“MinPts”).

1. Parameter eps mendefinisikan radius lingkungan sekitar titik x. Ini disebut ϵ-sebuah lingkungan dari x.
2. Parameter MinPts adalah jumlah minimum tetangga dalam radius “eps”.

Setiap titik x dalam kumpulan data, dengan jumlah tetangga lebih besar dari atau sama dengan MinPts, ditandai sebagai titik inti. Kita katakan bahwa x adalah titik batas, jika jumlah tetangganya kurang dari MinPts, tetapi itu milik ϵ – punya tetangga lainnya / neighborhood dari beberapa poin inti z. Akhirnya, jika suatu titik bukan merupakan titik inti atau batas, maka itu disebut titik kebisingan atau pencilan.

Untuk langkah demi langkah, bisa kalian Lebih lanjut, bisa baca disini, atau disini  atau disini. Bila menggunakan Python bisa baca disini.

Adapun bila suka menggunakan Python bisa disini

Lebih jauh mengenai algoritma clustering sebagai berikut

ref: https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html

Pemilihan  nilai Eps dan MinObj pada DB Clustering

Perbedaan mendasar antara KMeans Clustering dengan DBClustering yaitu

1. KMeans Clustering diawal kita harus menentukan jumlah grup/clusternya sedangkan
2. DB Clustering hasil grup/clustering ditentukan oleh paramater
   1. Eps adalah radius clustering
   2. MinObj adalah minimal anggota dalam 1 cluster yang sama

Pada DBSCAN pemilihan parameter Eps (ε) dan MinObj yang optimal

Berdasarkan k-dist graph. Komputasi dilakukan untuk mendapatkan nilai kdist untuk seluruh titik pada k=2 dan k=3 karena jika nilai k terlalu besar akan membentuk cluster yang kecil dan salah memberi label noise. Mari kita coba untuk menggunakan Kdist dengan nilai berikut

kNNdistplot(df,k=2)
abline(h=0.15,col="red",lty=2)
abline(h=0.2,col="red",lty=2)

Dapat dilihat bahwa plot k-dist k=2 terjadi perubahan tajam di antara titik 0.15 sampai dengan 0.2; sekarang kita ubah mengikuti aturan diatas menjadi

db <- dbscan(df, eps = 0.15, MinPts = 2)
db
fviz_cluster(db, data = df, stand = FALSE,
             ellipse = FALSE, show.clust.cent = FALSE,
             geom = "point",palette = "jco", ggtheme = theme_classic())

hasilnya dbclustering sebagai berikut menghasilkan 7 cluster

dengan jumlah noise sebanyak 21 titik

> print(db)
dbscan Pts=1100 MinPts=2 eps=0.15
        0   1   2   3   4  5 6 7
border 21   0   0   0   0  0 0 0
seed    0 411 406 106 100 52 2 2
total  21 411 406 106 100 52 2 2

Cara mendapatkan Hasil Output nilai K-dist

Gunakan cara berikut

hasil_knn = kNNdist(df,k=2,all=TRUE)

hasilnnya yaitu nilai KNN disetiap no cluster

               1           2
   [1,] 0.027913305 0.078903262
   [2,] 0.060163113 0.062075385
   [3,] 0.036480601 0.057775331
   [4,] 0.020556013 0.038467772
   [5,] 0.038254475 0.042164909
   [6,] 0.029051082 0.076752443
   [7,] 0.067305346 0.070088447
   [8,] 0.046111395 0.063442200

dst....

Cara mendapatkan index data setiap cluster

untuk mengetahui index mana saja yang termasuk noise, gunakan slicing berikut

df[db$cluster==0,]

berikut index dari dataset df yang termasuk noise

                 x           y
71    0.0008941857  0.83613574
915  -0.7576114777 -2.68320624
1005 -0.1322602804 -3.35346216
1006  1.3421913749 -1.58451781
1007  1.1502225716  1.25387415
1008  0.8325215487 -1.77402106
1013 -1.3772744536  0.08204886
1019 -1.4011699820 -0.37216610
1020  1.2231038811 -0.69938675
1022  1.1991267088 -1.20864946
1023 -1.0205484722  1.04797323
1025  0.3506553636 -2.27722931
1030 -0.0207804192  0.16480524
1031  1.0420065990 -1.46527734
1034 -1.1227718834  0.77914433
1035  0.2774274121 -1.82534272
1036 -0.6010712371 -1.22887995
1041  1.0043356537 -1.22721692
1046  1.4112614938 -2.10041582
1047  1.4922076233 -0.40878007
1048 -0.5824017988 -0.26628743

kamu bisa menggunakan cara diatas untuk mengetahui index yang termasuk cluster 1,2,3,4,5,6 dan 7; Misalkan untuk mengetahui index yang masuk ke cluster 7

df[db$cluster==7,]
             x         y
1029 -1.195652 -1.511433
1044 -1.176208 -1.537821
>

Mengapa Kinerja Dbscan lebih baik?

DBSCAN lebih baik daripada algoritma. Hasil ini masuk akal karena DBSCAN dapat dengan mudah mengelompokkan titik data ke dalam cluster bentuk arbitrer,
berdasarkan kepadatan dan koneksi dan juga jarak di antara mereka. ref: T. Vo-Van, A. Nguyen-Hai, M. V. Tat-Hong and T. Nguyen-Trang, “A New Clustering Algorithm and Its Application in Assessing the Quality of Underground Water,” Scientific Programming Volume 2020, Article ID 6458576, pp. 1-12, 2020.

Density-Based Spatial Clustering of Application with Noise (DBSCAN) adalah salah satu contoh pelopor perkembangan teknik pengelompokan berdasarkan kepadatan atau yang biasa dikenal dengan sebutan density based clustering. Density-Based Spatial Clustering of Application with Noise (DBSCAN) merupakan sebuah metode clustering yang membangun area berdasarkan kepadatan yang terkoneksi (density connected). Setiap objek dari sebuah radius area (cluster) harus mengandung setidaknya sejumlah minimum data. Semua objek yang tidak termasuk di dalam cluster dianggap sebagai noise Ada beberapa komponen atau istilah yang terdapat di algoritme DBSCAN : 

1. Eps : merupakan jumlah titik dalam radius tertentu
2. Noise Point : titik terluar dari density atau (Eps)
3. Border Point : titik perbatasan memiliki kurang dari MinPts dalam Eps, tetapi masih dalam lingkungan titik inti.
4. Min pts : jumlah tetangga terdekat yang digunakan untuk mendefinisikan local neighborhood suatu obyek
5. Core Point : Point atau titik yang berada di interior cluster

ref: R. Pratama, “Review of Density-Based Spatial Clustering,” Jurnal Informatika, pp. 1-3, 2016.

Silhouette Coefficient

Setelah dilakukan pengelompokkan, maka selanjutnya mengevaluasi hasil pengelompokkan menggunakan validasi klaster. Validasi klaster dilakukan untuk mengukur seberapa baik hasil pengelompokkan yang didapat. Dalam penelitian ini digunakan salah satu internal validation index yaitu Silhouette Coefficient. Dengan langkah sebagai berikut : ref: D. F. Azuri, Zulhanif and R. S. Pontoh, “Pengelompokkan Kabupaten/Kota Di Pulau Jawa Berdasarkan Pembangunan Manusia Berbasis Gender Menggunakan Bisecting K-Means,” ISBN 978-602-72216-1-1 , pp. 78-83, 2016

Hitung nilai silhouette dengan rumus sebagai berikut:

1. Hitung nilai silhouette dengan rumus sebagai berikut:

Keterangan :
a(i) = Rata-rata jarak i terhadap semua objek di klaster A

b(i) = Rata-rata jarak i terhadap semua objek pada klaster lain

Nilai silhouette berada pada interval -1 ≤ s(i) ≤ 1

2. Menghitung nilai silhouette width, yaitu nilai rata-rata silhouette pada semua objek yang berada dalam masing-masing klaster

3. Menghitung nilai Silhouette Coefficient

Dimana Silhouette Coefficient didapat dari nilai terbesar dari masing-masing nilai silhouette dan berikut merupakan tabel interpretasi nilai silhouette coefficient

Interpretasi silhouette coefficient

Sebenarnya untuk melihat optimal pada kasus diatas, saya memilih menggunakan epsilon = 0.2 dan minPts=10

db <- dbscan(df, eps = 0.2, MinPts = 10)

dengan hasil sebagai berikut

dbscan Pts=1100 MinPts=10 eps=0.2
        0   1   2   3   4  5
border 24  30   2  10  11  3
seed    0 381 405  95  90 49
total  24 411 407 105 101 52

artinya

1. cluster 0 sebagai noise dengan jumlah 24
2. cluster 1 berjumlah 411
3. cluster 2 berjumlah 407
4. cluster 3 berjumlah 105
5. cluster 4 berjumlah 101
6. cluster 5 berjumlah 52

untuk menghitung Silhouette clustering yaitu https://www.rdocumentation.org/packages/cluster/versions/2.1.2/topics/silhouette

nilai_silhouette<-silhouette(db$cluster,dist(df))
summary(nilai_silhouette)

hasil

Silhouette of 1100 units in 6 clusters from silhouette.default(x = db$cluster, dist = dist(df)) :
 Cluster sizes, ids = (0, 1, 2, 3, 4, 5), and average silhouette widths:
        24        411        407        105        101         52 
-0.4003234 -0.1922239  0.5037402  0.5074141  0.5511435  0.8894448 
Individual silhouette widths:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
-0.7411 -0.1757  0.4800  0.2469  0.5195  0.9238

nilai rerata/average masing-masing Silhouette untuk setiap cluster/kelas yaitu

1. cluster 0 : -0.4003234
2. cluster 1 : -0.1922239
3. cluster 2 : 0.5037402
4. cluster 3 : 0.5074141
5. cluster 4 : 0.5511435
6. cluster 5 : 0.8894448

untuk cluster 0 dan 1 ternyata nilainya sangat rendah bahkan minus

ref:

https://rstudio-pubs-static.s3.amazonaws.com/375287_5021917f670c435bb0458af333716136.html