DBSCAN: Metode Clustering pada Data Berpotensi Noise
Density-based Spatial Clustering of Applications with Noise (DBSCAN) merupakan salah satu teknik clustering yang banyak digunakan dalam berbagai kasus sains data. Melalui DBSCAN, kita dapat memitigasi masukknya noise menjadi bagian dari suatu kluster. Berbeda dengan K-means yang mengharuskan adanya jumlah kluster terlebih dahulu, DBSCAN melalui estimasi kepadatan pada titik data dapat menemukan jumlah klusternya sendiri. Tergantung kasus, DBSCAN bisa menjadi pilihan yang cocok.
Hasil kluster dari DBSCAN dipengaruhi oleh jarak antar titik data dalam radius tertentu dan jumlah titik minimal yang berada pada ruang lingkup radius. Kedua pengaruh tersebut dapat menentukan hasil kualitas clustering yang menjadi parameter penting.
Pada parameter radius (jarak maksimal antar titik data), besarnya nilai mempengaruhi banyaknya jumlah titik yang tercakup namun amat rentan dengan masukknya anomali atau noise kedalam kluster. Dilain sisi, radius yang terlalu kecil akan memicu terbentuknya banyak kluster yang mempengaruhi hasil kualitas penemuan pola pada data.
Jumlah titik minimal sendiri merupakan jumlah titik yang terdapat pada suatu radius termasuk titik itu sendiri. Untuk mempersingkat kepenulisan, kita sebut saja jumlah minimal titik yang ada pada cakupan radius dengan m yang menjadi salah satu parameter inti dari DBSCAN selain parameter radius.
Pembentukan kluster pada DBSCAN dipengaruhi oleh tiga jenis titik (data) yaitu:
- Titik inti (core points): merupakan titik yang memiliki titik tetangga dengan jumlah minimal m (termasuk titik itu sendiri)
- Titik batas (border points): merupakan titik yang berada pada radius titik inti namun tidak memenuhi jumlah minimal m
- Titik anomali (noise points): merupakan titik yang tidak berada pada lingkup titik inti dan tidak memenuhi jumlah minimal m
Ilustrasi dari ketiga jenis titik diatas dapat dilihat pada ilustrasi dibawah. Dengan m = 3, titik berwarna oranye menjadi titik inti, dikarenakan di dalam jangkauan radius titik tersebut terdapat tiga titik data lain. Sedangkan titik berwarna hijau merupakan titik batas yang masuk dalam jangkauan salah satu titik inti namun tidak memenuhi jumlah mimial titik yang ada pada radius dimana m < 3. Sedangkan warna merah menunjukkan titik anomali yang tidak memiliki jumlah minimum titik pada ruang lingkup radius atau dengan kata lain tidak terhubung dengan titik manapun dalam radius yang ditentukan.
Semua titik yang berada pada titik inti menjadi satu kluster yang sama. Titik-titik tersebut secara langsung memiliki kepadatan yang terhubung satu sama lain, dalam istilah asing disebut direct density reachable. Sedangkan suatu titik inti yang merupakan bagian dari radius titik inti lain, titik-titik pada titik inti tersebut dapat dikatakan secara transitif saling terhubung (transitively density reachable). Baik titik yang tergolong direct density reachable atau transitively density reachable akan membentuk suatu kluster yang memiliki kepadatan yang saling terhubung (density-connected).
Untuk menentukan apakah titik tetangga berada pada radius suatu titik, diperlukan fungsi yang dapat menghitung jarak satu sama lain (distance metric). Fungsi jarak yang paling umum digunakan adalah Euclidan distance. Namun, DBSCAN tidak berpatok hanya pada Euclidan saja, berbagai macam jenis metric dapat digunakan sesuai kebutuhan.
(kita akan masuk kedalam pengkongkretan konseptualitas diatas melalui definisi matematis dan algoritme, dapat di skip jika tidak suka 😃)
Untuk lebih dapat meraba bentuk dari ketiga jenis titik tersebut, ada lebih baiknya kita memahami definisi dibawah.
Kita tentukan e = jarak radius, m = jumlah minimum titik, X = {x1, …, xn} merupakan titik data, dan d(xp, xq) merupakan metric distance (seperti Euclidan distance). Maka dapat diambil definisi berukut:
- Definisi 1: Suatu titik xp dikatakan titik inti jika titik lain yang berada pada radius xp setidaknya memiliki jumlah titik m, |N(xp)| ≥ m, dimana N(xp) = {x ∈ X | d(x, xp) ≤ e} dan |.| menunjukkan kardinalitas (jumlah elemen pada suatu himpunan)
- Definisi 2: Dua titik inti xp dan xq dikatakan saling terjangkau (e-reachable) jika xp ∈ N(xq) dan xq ∈ N(xp)
- Definisi 3: Dua titik inti xp dan xq dikatakan density-connected apabila secarang langsung atau transitif e-reachable
- Definisi 4: Suatu cluster C merupakan himpunan tidak kosong bagian dari X (dataset) sehingga setiap pasangan titik di C density-connected.
Algoritme original DBSCAN dapat dilihat pada deskripsi pseudocode diatas. Terdapat empat masukan yaitu DB berupa database yang berisi titik data yang dapat terurut berdasarkan jarak atau berapasangan dengan tetangganya dengan nilai dari suatu fungsi jarak. Sedangkan nilai radius dinotasikan dengan e, minimal jarak dalam suatu radius e dinotasikan dengan minPts, lalu fungsi jarak dinotasikan dengan dist. Setiap data pada DB diinisialisasi tidak memiliki label atau undefined.
DBSCAN melakukan perulangan pada tiap titik p pada database DB. Perulangan akan dilanjutkan tanpa mengeksekusi perintah dibawahnya apabila titik p sudah diberi label atau ≠ undefined. Lalu, fungsi RangeQUERY digunakan untuk mendapatkan himpunan titik tetangga N pada radius e untuk titik p. Jika |N| tidak memenuhi jumlah minimum minPts, maka untuk sementara p dimuat sebagai titik anomali.
Selanjutnya, kluster baru c dibentuk untuk titik p. Dalam kasus ini, setiap titik q yang merupakan tetangga dalam radius p akan ditelaah lebih lanjut melalui perulangan. Titik anomali q akan dimuat sebagai kluster c. Untuk tiap titik q yang belum terdefinisi, tetangga titik q akan didapatkan melalui fungsi RangeQUERY, label q dimuat sebagai kluster c dikarenakan tergolong density-connected. Jika tetangga titik q memiliki jumlah minimum minPts, maka akan dimasukkan kembali kedalam perulangan. Proses ini berlanjut sampai tidak ada titik yang memiliki kepadatan yang saling terhubung untuk kluster c.
Dari langkah algoritme diatas, waktu komputasi yang diperlukan adalah Θ(n². D). Kompleksitas diperoleh dari perulangan bersarang pada algoritme DBSCAN yang mengeksekusi fungsi RangeQUERY. Jika setiap kali fungsi tersebut dijalankan, dan dilakukan pencarian secara berurutan (sequential) dalam implementasinya, maka terdapat n eksekusi. Sedangkan D, merupakan waktu eksekusi jarak antar titik.
Pada implementasinya, DBSCAN dapat digunakan secara langsung melalui pustaka scikit-learn. Berikut contoh yang saya ambil dari dokumentasi scikit-learn. Sangat direkomendasikan untuk berkunjung ke laman sklearn.cluster.DBSCAN — scikit-learn 1.2.1 documentation
Scikit-learn menyediakan beberapa jenis distance metric yang siap digunakan dengan mengganti argumen pada parameter metric. Opsi yang dapat dipilih adalah [‘cityblock’, ‘cosine’, ‘euclidean’, ‘l1’, ‘l2’, ‘manhattan’]
from sklearn.cluster import DBSCAN
import numpy as np
X = np.array([[1, 2], [2, 2], [2, 3], [8, 7], [8, 8], [25, 80]])
clustering = DBSCAN(eps=3, min_samples=2, metric='euclidean').fit(X)
clustering.labels_>> array([ 0, 0, 0, 1, 1, -1])Hasil keluaran label tiap titik data dapat dilihat pada kotak diatas yang didapatkan melalui properti labels_. Nilai 0 dan 1 menunjukkan bahwa data tersebut berada pada kluster yang berbeda yang menghasilkan dua kluster. Sedangkan -1 tergolong sebagai titik anomali sehingga titik data tersebut tidak termasuk kedalam salah satu kluster baik dengan label 0 atau 1.
Referensi
Pei, Jian, Vincent S. Tseng, Longbing Cao, Hiroshi Motoda, and Guandong Xu, eds. Advances in Knowledge Discovery and Data Mining. Vol. 7819. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. https://doi.org/10.1007/978-3-642-37456-2.
Schubert, Erich, Jörg Sander, Martin Ester, Hans Peter Kriegel, and Xiaowei Xu. “DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN.” ACM Transactions on Database Systems 42, no. 3 (September 30, 2017): 1–21. https://doi.org/10.1145/3068335.
https://hdbscan.readthedocs.io/en/latest/comparing_clustering_algorithms.html
