Density-Based Spatial Clustering of Applications with Noise (DBSCAN)

    DBSCAN diperkenalkan oleh Ester, algoritma ini merupakan teknik clustering non-parametrik (Tran et al, 2012). DBSCAN merupakan salah satu algoritma clustering yang mengelompokkan obyek ke dalam cluster dimana kategori atau class data ujinya belum diketahui (unsupervised learning). Algoritma ini cukup populer dan mendapatkan penghargaan the test of the time award, yaitu penghargaan yang diberikan untuk algoritma yang memperoleh perhatian khusus dalam hal teori maupun prakteknya, pada konferensi tentang data mining yang diselenggarakan oleh Associacion for Computing Machinery (ACM) pada tahun 2014 (ACM, 2014 dalam Furqon dan Muflikhah, 2016).

    Algoritma DBSCAN membutuhkan dua parameter penting, yaitu Eps (ε) dan jumlah data tetangga minimal untuk membentuk kelompok (MinPts). Adapun algoritma dari DBSCAN adalah sebagai berikut (Devi et al, 2015):

1.   Pilih titik awal r secara acak.

2.   Inisialisasi parameter input MinPts dan Eps.

3.   Hitung Eps atau semua jarak densitas terjangkau terhadap r menggunakan jarak euclidean

Dimana x adalah variabel ke-a dari obyek i (i=1, ..., n; a=1, ...., p) dan d adalah nilai Euclidean Distance.

4.  Jika jumlah titik yang memenuhi Eps lebih dari MinPts maka titik r adalah titik pusat (core) dan cluster terbentuk.

5.  Ulangi langkah 3 – 4 hingga semua titik diproses. Jika r adalah titik border dan tidak ada titik yang densitas terjangkau terhadap r, maka proses dilanjutkan ke titik yang lain.

    Beberapa keuntungan yang dimiliki oleh algoritma DBSCAN, yaitu (Scitovski, 2017):
    1. Mengenali cluster non-konveks

          2. Partisi dengan jumlah cluster yang paling tepat diperoleh secara otomatis.

        3. Tidak perlu menggunakan indeks untuk menentukan jumlah cluster yang sesuai dalam sebuah partisi.

Reference:

- Devi, N.M.A.S., et al. "Implementasi Metode Clustering DBSCAN pada Proses Pengambilan     Keputusan," Lontar Komputer. Vol. 6, No. 3, hal. 655-661, Desember 2015
- Furqon, M. T., dan L. Muflikhah. "Clustering The Potential Risk of Tsunami Using Density-Based Spatial Clustering of Application with Noise (DBSCAN)," Journal of Environmental Engineering & Sustainable Technology. Vol. 3. No. 1, hal. 1-8, 2016
- Mumtaz, K. and Duraiswamy, K. “An Analysis On Density Based Clustering Of Multi Dimensional Spatial Data,” Indian Journal of Computer Science and Engineering. Vol. 1, No. 1, hal 8-12. 2010
- Tran, T.N., K. Drab, dan M. Daszykowski. "Revised DBSCAN algorithm to cluster data with dense adjacent clusters," Elsevier : Chemometrics and Intelligent Laboratory Systems. Hal. 92-96. 2012
- Scitovski, Sanja. "A Density-Based Clustering Algorithm for Earthquake Zoning," Elsevier : Computers and Geosciences. Hal 1-12. Agustus 2017