1.1 Clustering

     Clustering merupakan salah satu bagian dari unsupervised learning. Clustering memiliki tujuan untuk membagi data ke dalam beberapa kelompok berdasarkan kemiripan antar data. Cluster (kelompok) yang baik adalah cluster yang memiliki kemiripan yang besar antar anggota clusternya dan memiliki perbedaan yang signifikan dengan anggota cluster yang berbeda. Clustering dapat diterapkan dalam berbagai bidang seperti segmentasi pasar, cluster profiling, data spatial dll. Metode clustering sangat beragam, namun bila ingin dikelompokkan secara general berdasarkan metodenya, clustering dapat dibagi menjadi beberapa kelompok seperti gambar dibawah.

Gambar diatas membagi metode cluster kedalam 4 metode dengan karakter dari masing masing metode. Artikel ini akan membahas salah satu algoritma yang menggunakan metode kerapatan (density-based) yaitu DBSCAN.

1.2 Setup

DBSCAN dapat digunakan pada R dengan menginstall package dbscan terlebih dahulu.

install.packages("dbscan")

Berikut beberapa packages yang digunakan pada artikel ini.

library(dplyr)
# clustering libs
library(dbscan)
library(factoextra)
library(cluster)
# visualization libs
library(ggplot2)
library(leaflet)
library(ggthemes)
library(fishualize)

2.1 Terminologi

    DBSCAN memerlukan dua parameter input sebelum melakukan proses clustering yaitu epsilon (eps) dan minimum points (minPts). Epsilon merupakan jarak maksimal antara dua data dalam satu cluster yang diizinkan, dan minimum points adalah banyaknya data minimal dalam jarak epsilon agar terbentuk suatu cluster. Metode jarak yang digunakan dalam DBSCAN adalah jarak Euclidian. Selain epsilon dan MinPts ada beberapa terminologi lain dalam metode DBSCAN yaitu :

• directly density-reachable : Observasi q berhubungan langsung dengan p, jika p adalah core point dan q merupakan tetangga dari p dalam jangkauan epsilon.
  
• density-reachable : Observasi q dan x dalam satu cluster namun x bukan tetangga dari q dalam jangkauan epsilon.
  
• core point : Core point merupakan observasi yang memiliki jumlah tetangga lebih dari sama dengan dari MinPts pada jangkauan Eps.
  
• border point : Border point memiliki tetangga lebih sedikit dari Minpts namun ia merupakan tetangga dari core point.
  
• outlier/noise point : Observasi yang bukan border points atau core points.

2.2 Cara Kerja DBSCAN

     Dalam proses pembuatan cluster menggunakan DBSCAN sebuah data akan dikelompokkan dengan tetangganya. Sepasang amatan dikatakan bertetangga apabila jarak antara dua amatan tersebut kurang dari sama dengan nilai epsilon. Secara sederhana cara kerja DBSCAN adalah sebagai berikut :
1. Tentukan nilai minPts dan epsilon (eps) yang akan digunakan.
2. Pilih data awal “p” secara acak.
3. Hitung jarak antara data “p” terhadap semua data menggunakan Euclidian distance.
4. Ambil semua amatan yang density-reachable dengan amatan “p”.
5. Jika amatan yang memenuhi nilai epsilon lebih dari jumlah minimal amatan dalam satu gerombol maka amatan “p” dikategorikan sebagai core points dan gerombol terbentuk.
6. Jika amatan “p” adalah border points dan tidak ada amatan yang density-reachable dengan amatan “p”, maka lanjutkan pada amatan lainnya.
7. Ulangi langkah 3 sampai 6 hingga semua amatan diproses.

3.1 Data Eksplorasi

    Data yang digunakan dalam proses clustering ini adalah data multishape dari packages factoextra. Data multishape memiliki 1100 observasi dan 3 variabel yaitu x, y, dan shape. Variabel yang digunakan pada proses clustering ini adalah x dan y.

data("multishapes")
multishapes <- multishapes[,1:2]
dim(multishapes)

#> [1] 1100    2

    Secara visual data multishape dapat dilihat seperti plot dibawah. Pada plot tersebut terlihat bahwa kerapatan antar data membentuk beberapa bentuk seperti lingkaran dan persegi panjang.

ggplot(data = multishapes, aes(x = x, y = y)) +
  geom_point(col = "firebrick4") +
  theme_pander()

3.2 Clustering

    Tahap awal sebelum melakukan clustering adalah memilih nilai minpts dan epsilon (eps). Nilai minpts dan eps yang optimum dapat dicari menggunakan fungsi kNNdistplot dari packages dbscan. Ide utama dari fungsi ini adalah menghitung jarak rata2 untuk setiap data ke k tetangga terdekatnya (nearest neighbors). Nilai dari K ditentukan oleh user yang nantinya akan digunakan sebagai minPts pada proses clustering. Rata rata jarak yang sudah didapat divisualisasikan dalam plot secara ascending untuk mendapatkan “knee” yang menunjukkan nilai optimal dari eps berdasarkan K yang ditentukan.

kNNdistplot(multishapes, k = 4)
abline(h = 0.15, col = "red", lty = 2)

    Berdasarkan plot diatas dengan menggunakan K = 4 didapat jarak yang optimal yaitu sekitar 0.15. Nilai 0.15 didapat dari posisi “knee” yang terbentuk pada plot. Hasil pencarian nilai eps yang optimal diatas dapat digunakan dalam proses clustering yang mana nilai eps adalah 0.15 dengan minPts 4. Tahap selanjutnya adalah pembuatan cluster menggunakan function dbscan dengan parameter yang sudah didapat.

db_clust <- dbscan(multishapes, eps = 0.15, minPts = 4)
db_clust

#> DBSCAN clustering for 1100 objects.
#> Parameters: eps = 0.15, minPts = 4
#> The clustering contains 5 cluster(s) and 29 noise points.
#> 
#>   0   1   2   3   4   5 
#>  29 411 405 105  99  51 
#> 
#> Available fields: cluster, eps, minPts

    Hasil clustering dari data multishape dengan 1100 observasi adalah 5 cluster dan sebanyak 29 data diidentifikasi sebagai noise. Cluster 1 merupakan cluster dengan anggota cluster terbanyak sedangkan cluster 5 merupakan cluster dengan anggota cluster paling sedikit. Hasil cluster yang sudah dibentuk dapat dilakukan visualisasi agar terlihat pola dari cluster yang didapat.

multishapes <- multishapes %>% 
  mutate(clust = db_clust$cluster, 
         clust = ifelse(clust==0,"Noise",clust)) 

ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")

    Dari hasil visualisasi diatas bisa dilihat bahwa cluster yang dihasilkan dbscan dapat mengelompokkan data sehingga bisa menangkap beberapa bentuk dari data. Noise yang terdeteksi pada data terlihat menyebar, hal ini dikarenakan data noise tidak berhasil ditangkap oleh eps yang ditentukan.

    DBSCAN merupakan metode clustering yang sangat sensitif terhadap perubahan parameter. Perbedaan kecil pada parameter yang ada (minPts, Eps) dapat menghasilkan cluster yang berbeda. Sebagai contoh pada data multishapes yang sebelumnya digunakan nilai eps 0.15 apabila diubah yang awalnya menjadi 0.2 akan menghasilkan cluster yang berbeda.

db_clust <- dbscan(multishapes[,1:2], eps = 0.2, minPts = 4)
db_clust

#> DBSCAN clustering for 1100 objects.
#> Parameters: eps = 0.2, minPts = 4
#> The clustering contains 4 cluster(s) and 20 noise points.
#> 
#>   0   1   2   3   4 
#>  20 820 106 102  52 
#> 
#> Available fields: cluster, eps, minPts

Mengubah parameter eps yang semula 0.15 menjadi 0.2 menghasilkan 4 cluster dan noise yang dihasilkan menjadi semakin berkurang menjadi 20. Cluster 1 merupakan cluster yang mengalami penambahan anggota cluster secara signifikan, yang semula 411 menjadi 820. Pola cluster yang sudah dibuat dapat divisualisasikan agar dapat melihat perbedaan dengan proses clustering sebelumnya.

multishapes <- multishapes %>% 
  mutate(clust = db_clust$cluster, 
         clust = ifelse(clust==0,"Noise",clust)) 

ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")

Dari hasil visualisasi diatas bisa dilihat bahwa cluster 1 yang baru menggabungkan cluster 1 dan 2 pada proses cluster sebelumnya, serta noise yang awalnya berada disekitar cluster 1 menjadi anggota cluster 1.