DBSCAN Clustering



1. Pendahuluan

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. DBSCAN

     Algoritma Density-based Spatial Clustering of Application with Noise (DBSCAN) merupakan metode clustering yang berbasis kepadatan (density-based) dari posisi amatan data dengan prinsip mengelompokkan data yang relatif berdekatan. DBSCAN sering diterapkan pada data yang banyak mengandung noise, hal ini dikarenakan DBSCAN tidak akan memasukkan data yang dianggap noise kedalam cluster manapun.

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. DBSCAN pada R

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.

4. DBSCAN pada Spatial Dataset

    Metode DBSCAN sering diimplemtasikan pada data spatial hal ini dikarenakan dimensi dari data spasial yang cukup sederhana yaitu longitide dan latitude. Data yang digunakan pada artikel ini adalah data kebakaran di Australia pada awal tahun 2020. Anda dapat mengunduh data lengkapnya pada link berikut

nasa_fire <- readr::read_csv('data_input/nasa_fire.csv')
head(nasa_fire)
#> # A tibble: 6 x 3
#>   latitude longitude confidence
#>      <dbl>     <dbl>      <dbl>
#> 1    -32.2      151.         76
#> 2    -32.2      151.         76
#> 3    -32.2      151.         90
#> 4    -32.6      151.         70
#> 5    -32.6      151.         84
#> 6    -32.6      151.         84

Data nasa_fire memiliki 3 variabel yaitu latitude, longitude, dan confidence. Nilai confidence berkisar dari 0 hingga 100 yang menunjukkan tingkat keyakinan kebakaran terjadi. Sebelum masuk pada proses pembuatan cluster, data nasa_fire akan divisualisasikan dalam bentuk peta menggunakan packages leaflet.

leaflet(data = nasa_fire) %>% 
  addTiles() %>% 
  setView(lng = 133.7751,lat = -25.2744,zoom =  4) %>% 
  addCircleMarkers(lng = ~longitude, 
                   lat = ~latitude, 
                   radius =1)

Dari visualisasi diatas bisa dilihat bahwa titik kebakaran menggerombol pada beberapa area, dan beberapa titik kebakaran berada jauh dari kerumunan yang ada. Tahap selanjutnya adalah menentukan nilai MinPts dan Eps yang optimum dengan menggunakan fungsi KNNdistplot.

kNNdistplot(nasa_fire[,1:2], k = 10)
abline(h= 0.8, col = "red", lty = 3)

Dengan menggunkan k = 10 maka didapat nilai eps sebesar 0.8 berdasarkan “knee” yang terbentuk dari plot. Selanjutnya proses pembuatan cluster menggunakan fungsi dbscan dengan parameter yang sudah didapat yaitu minPts = 10 dan eps = 0.8.

nasa_clust <- dbscan(nasa_fire[,1:2], eps = 0.8, minPts = 10)
nasa_clust
#> DBSCAN clustering for 25937 objects.
#> Parameters: eps = 0.8, minPts = 10
#> The clustering contains 44 cluster(s) and 251 noise points.
#> 
#>     0     1     2     3     4     5     6     7     8     9    10    11    12 
#>   251 18333   603   159    47   367    10    16    17   203   847    47   242 
#>    13    14    15    16    17    18    19    20    21    22    23    24    25 
#>   656   907  1060   247    28    53    23    69    27    78    57    51    15 
#>    26    27    28    29    30    31    32    33    34    35    36    37    38 
#>    11   661    54    17   150    60    15    19    20   195   124    32    32 
#>    39    40    41    42    43    44 
#>    16    13    24    12    11    58 
#> 
#> Available fields: cluster, eps, minPts

Clustering yang dilakukan menghasilkan 44 cluster dan 251 data noise. Cluster dengan jumlah anggota terbanyak dimiliki cluster 1 dengan 18333 anggota cluster dan cluser 43 dan 26 sebagai cluster dengan anggota cluster paling sedikit yaitu 11. Hasil Cluster dapat divisualisasikan dalam peta untuk melihat persebaran cluster yang dibentuk.

# membuat kolom baru untuk cluster
nasa_fire <- nasa_fire %>% 
  mutate(clust = nasa_clust$cluster)

# membuat pallet color untuk setiap cluster
pallet <- fishualize::fish(n = length(unique(nasa_fire$clust)), option = "Bryaninops_natans")
pal <- colorFactor(pallet, domain = unique(nasa_fire$clust))

# visualisasi cluser tanpa data noise
leaflet(data = nasa_fire[nasa_fire$clust !=0,]) %>% 
  addTiles() %>% 
  setView(lng = 133.7751,lat = -25.2744,zoom =  4) %>% 
  addCircleMarkers(lng = ~longitude, 
                   lat = ~latitude, 
                   radius =1,
                   color = ~pal(clust))