Tutorial ini membahas algoritma DBSCAN dengan contoh perhitungan manual lengkap untuk clustering berbasis kepadatan. Contoh menggunakan data dua dimensi dengan parameter \(\varepsilon=0.5\) dan \(MinPts=4\).
DBSCAN berbeda dari K-Means dan K-Medoids karena tidak harus menentukan jumlah cluster di awal. Cluster dibentuk dari wilayah yang memiliki kepadatan data cukup tinggi, sedangkan titik yang tidak memenuhi struktur kepadatan dapat ditandai sebagai noise.
Daftar Isi
- Pengertian DBSCAN
- Konsep Core, Border, dan Noise
- Parameter Epsilon dan MinPts
- Rumus Euclidean Distance
- #01 Menentukan Data
- #02 Menentukan Epsilon dan MinPts
- #03 Menghitung Matriks Jarak
- #04 Menentukan Epsilon-Neighborhood
- #05 Menentukan Core, Border, dan Noise
- #06 Membentuk Cluster Pertama
- #07 Membentuk Cluster Kedua
- #08 Menentukan Noise
- #09 Hasil Clustering DBSCAN
- Alur Algoritma DBSCAN
- Cara Memilih Epsilon dan MinPts
- Perbedaan DBSCAN dan K-Means
- Kelebihan dan Kekurangan DBSCAN
- Ringkasan
- FAQ DBSCAN
- Referensi
- Source Code DBSCAN
Pengertian DBSCAN
DBSCAN adalah singkatan dari Density-Based Spatial Clustering of Applications with Noise. Algoritma ini membentuk cluster berdasarkan kepadatan titik pada suatu wilayah.
Sebuah titik dianggap berada pada wilayah padat jika terdapat cukup banyak titik lain di dalam radius tertentu. Dua parameter utamanya adalah epsilon (\(\varepsilon\)) dan MinPts.
DBSCAN dapat menemukan cluster dengan bentuk yang tidak harus bulat dan dapat memisahkan titik yang dianggap noise.
Konsep Core, Border, dan Noise
Core Point
Titik disebut core jika jumlah titik dalam \(\varepsilon\)-neighborhood memenuhi:
$$ |N_{\varepsilon}(p)| \geq MinPts $$
Pada tutorial ini titik \(p\) sendiri ikut dihitung dalam MinPts.
Border Point
Border point tidak memiliki neighbor yang cukup untuk menjadi core, tetapi berada dalam epsilon-neighborhood dari suatu core point.
Noise
Noise adalah titik yang tidak menjadi core dan tidak dapat dimasukkan sebagai border ke cluster yang terbentuk.
Parameter Epsilon dan MinPts
Epsilon menentukan radius pencarian tetangga. Semakin besar epsilon, semakin banyak titik yang dapat dianggap bertetangga.
MinPts menentukan jumlah minimum titik dalam radius epsilon agar titik tersebut menjadi core.
Kombinasi kedua parameter ini sangat menentukan hasil clustering.
Rumus Euclidean Distance
Untuk dua data dua dimensi:
$$ d(p,q) = \sqrt{ (x_p-x_q)^2 + (y_p-y_q)^2 } $$
Jika atribut mempunyai skala berbeda jauh, lakukan normalisasi atau standardisasi sebelum menggunakan Euclidean Distance.
#01 Menentukan Data
Dataset contoh DBSCAN. Kode Nama X1 X2 A1 Pelanggan A1 1 1 A2 Pelanggan A2 1.2 1.1 A3 Pelanggan A3 0.8 1.2 A4 Pelanggan A4 1.1 0.8 A5 Pelanggan A5 1.55 1 B1 Pelanggan B1 5 5 B2 Pelanggan B2 5.2 5.1 B3 Pelanggan B3 4.8 5.2 B4 Pelanggan B4 5.1 4.9 N1 Pelanggan N1 8 1Data A1 sampai A5 berada di sekitar koordinat \((1,1)\), data B1 sampai B4 berada di sekitar \((5,5)\), sedangkan N1 berada cukup jauh dari kelompok lainnya.
#02 Menentukan Epsilon dan MinPts
Parameter yang digunakan:
$$ \varepsilon = 0.5 $$
$$ MinPts = 4 $$
Artinya, dua titik dianggap bertetangga jika jaraknya tidak lebih dari 0.5. Suatu titik menjadi core jika memiliki minimal 4 anggota pada epsilon-neighborhood, termasuk dirinya sendiri.
#03 Menghitung Matriks Jarak
Contoh Jarak A1 ke A2
$$ d(A1,A2) = \sqrt{ (1-1.2)^2 + (1-1.1)^2 } $$
$$ d(A1,A2) = 0.223607 $$
Karena 0.223607 \(\leq 0.5\), A1 dan A2 termasuk tetangga.
Contoh Jarak A1 ke A5
$$ d(A1,A5) = 0.55 $$
Karena jaraknya lebih besar dari epsilon, A5 bukan neighbor langsung A1.
Matriks Euclidean Distance DBSCAN. Data A1 A2 A3 A4 A5 B1 B2 B3 B4 N1 A1 0 0.224 0.283 0.224 0.55 5.657 5.869 5.664 5.659 7 A2 0.224 0 0.412 0.316 0.364 5.445 5.657 5.456 5.445 6.801 A3 0.283 0.412 0 0.5 0.776 5.664 5.88 5.657 5.673 7.203 A4 0.224 0.316 0.5 0 0.492 5.731 5.941 5.749 5.728 6.903 A5 0.55 0.364 0.776 0.492 0 5.282 5.489 5.311 5.274 6.45 B1 5.657 5.445 5.664 5.731 5.282 0 0.224 0.283 0.141 5 B2 5.869 5.657 5.88 5.941 5.489 0.224 0 0.412 0.224 4.965 B3 5.664 5.456 5.657 5.749 5.311 0.283 0.412 0 0.424 5.28 B4 5.659 5.445 5.673 5.728 5.274 0.141 0.224 0.424 0 4.86 N1 7 6.801 7.203 6.903 6.45 5 4.965 5.28 4.86 0#04 Menentukan Epsilon-Neighborhood
Epsilon-neighborhood suatu titik adalah semua titik dengan jarak tidak lebih dari epsilon.
Contoh A1
Jarak dari A1 ke:
- A1 = 0
- A2 = 0.223607
- A3 = 0.282843
- A4 = 0.223607
- A5 = 0.55
Dengan \(\varepsilon=0.5\):
$$ N_{\varepsilon}(A1) = \{ A1, A2, A3, A4 \} $$
Jumlah neighbor:
$$ |N_{\varepsilon}(A1)| = 4 $$
Contoh A5
$$ N_{\varepsilon}(A5) = \{ A2, A4, A5 \} $$
$$ |N_{\varepsilon}(A5)| = 3 $$
Epsilon-neighborhood setiap titik. Titik Neighbor dalam ε Jumlah A1 A1, A2, A3, A4 4 A2 A1, A2, A3, A4, A5 5 A3 A1, A2, A3, A4 4 A4 A1, A2, A3, A4, A5 5 A5 A2, A4, A5 3 B1 B1, B2, B3, B4 4 B2 B1, B2, B3, B4 4 B3 B1, B2, B3, B4 4 B4 B1, B2, B3, B4 4 N1 N1 1#05 Menentukan Core, Border, dan Noise
Contoh Core Point: A1
A1 mempunyai 4 titik pada epsilon-neighborhood.
Karena:
$$ 4 \geq 4 $$
maka A1 adalah Core Point.
Contoh Border Point: A5
A5 memiliki:
$$ |N_{\varepsilon}(A5)| = 3 $$
Karena nilainya kurang dari MinPts, A5 bukan core. Namun A5 berada dalam epsilon-neighborhood dari A2 yang merupakan core point.
Maka A5 adalah Border Point.
Contoh Noise: N1
$$ N_{\varepsilon}(N1) = \{ N1 \} $$
N1 tidak memiliki neighbor yang cukup untuk menjadi core dan tidak berada dalam epsilon-neighborhood core point lainnya. Maka N1 adalah Noise.
Klasifikasi titik DBSCAN. Titik Jumlah Neighbor Tipe Cluster A1 4 Core C1 A2 5 Core C1 A3 4 Core C1 A4 5 Core C1 A5 3 Border C1 B1 4 Core C2 B2 4 Core C2 B3 4 Core C2 B4 4 Core C2 N1 1 Noise Noise#06 Membentuk Cluster Pertama
Proses dimulai dari A1. Karena A1 adalah core, DBSCAN membentuk cluster baru.
Neighbor A1:
A1, A2, A3, A4.
A2, A3, dan A4 juga merupakan core point. Karena core-core tersebut saling terhubung melalui epsilon-neighborhood, cluster terus diperluas.
A5 bukan core, tetapi berada dalam neighborhood A2. Karena itu A5 dimasukkan sebagai border point ke cluster yang sama.
Anggota cluster pertama. Titik Tipe A1 Core A2 Core A3 Core A4 Core A5 Border#07 Membentuk Cluster Kedua
Setelah cluster pertama selesai, algoritma melanjutkan ke titik yang belum menjadi bagian cluster.
Contoh B1
$$ N_{\varepsilon}(B1) = \{ B1, B2, B3, B4 \} $$
Jumlah neighbor B1:
$$ |N_{\varepsilon}(B1)| = 4 $$
Karena memenuhi MinPts, B1 merupakan core point dan membentuk cluster kedua.
Anggota cluster kedua. Titik Tipe B1 Core B2 Core B3 Core B4 Core#08 Menentukan Noise
Setelah seluruh wilayah padat diperiksa, N1 tetap tidak terhubung ke core point mana pun.
Neighbor N1 hanya:
N1.
Jumlahnya:
$$ 1 < 4 $$
sehingga N1 menjadi noise.
#09 Hasil Clustering DBSCAN
Dengan parameter \(\varepsilon=0.5\) dan \(MinPts=4\), DBSCAN menghasilkan 2 cluster.
Hasil akhir clustering DBSCAN. Titik X1 X2 Tipe Hasil A1 1 1 Core C1 A2 1.2 1.1 Core C1 A3 0.8 1.2 Core C1 A4 1.1 0.8 Core C1 A5 1.55 1 Border C1 B1 5 5 Core C2 B2 5.2 5.1 Core C2 B3 4.8 5.2 Core C2 B4 5.1 4.9 Core C2 N1 8 1 Noise Noise Ringkasan cluster DBSCAN. Kelompok Anggota Jumlah C1 A1, A2, A3, A4, A5 5 C2 B1, B2, B3, B4 4 Noise N1 1Core point: A1, A2, A3, A4, B1, B2, B3, B4.
Border point: A5.
Noise: N1.
Alur Algoritma DBSCAN
- Pilih satu titik yang belum dikunjungi.
- Cari seluruh titik pada radius epsilon.
- Jika jumlah neighbor kurang dari MinPts, tandai sementara sebagai noise.
- Jika jumlah neighbor memenuhi MinPts, buat cluster baru.
- Masukkan seluruh density-reachable point ke cluster.
- Core point baru memperluas cluster melalui neighbor-nya.
- Border point masuk cluster tetapi tidak memperluas cluster.
- Ulangi sampai seluruh titik telah diperiksa.
Titik yang semula ditandai noise dapat berubah menjadi border apabila kemudian ditemukan berada dalam neighborhood suatu core point.
Cara Memilih Epsilon dan MinPts
Memilih MinPts
MinPts tidak memiliki satu nilai universal untuk semua dataset. Nilainya perlu disesuaikan dengan jumlah dimensi, ukuran dataset, tingkat noise, dan karakter distribusi data.
Pada data dua dimensi, nilai kecil seperti 4 sering digunakan sebagai titik awal eksplorasi, tetapi bukan aturan wajib.
Memilih Epsilon
Salah satu pendekatan yang sering digunakan adalah k-distance plot. Untuk setiap titik, hitung jarak menuju tetangga ke-k, urutkan jarak tersebut, kemudian cari area perubahan tajam atau elbow.
Nilai epsilon yang terlalu kecil dapat menghasilkan banyak noise, sedangkan epsilon terlalu besar dapat menggabungkan cluster yang seharusnya terpisah.
Perbedaan DBSCAN dan K-Means
Perbandingan DBSCAN dan K-Means. Aspek DBSCAN K-Means Jumlah cluster Tidak harus ditentukan di awal Harus menentukan k Dasar clustering Kepadatan Jarak ke centroid Noise Dapat diidentifikasi secara eksplisit Semua data biasanya masuk cluster Bentuk cluster Dapat mengikuti bentuk tidak beraturan Cenderung cocok untuk cluster kompak Parameter utama Epsilon dan MinPts Jumlah cluster kKelebihan dan Kekurangan DBSCAN
Kelebihan DBSCAN
- Tidak harus menentukan jumlah cluster di awal.
- Dapat menemukan cluster dengan bentuk tidak beraturan.
- Dapat mendeteksi noise secara langsung.
- Tidak bergantung pada centroid awal seperti K-Means.
- Cocok untuk data yang cluster-nya terbentuk berdasarkan kepadatan.
Kekurangan DBSCAN
- Hasil sensitif terhadap pemilihan epsilon dan MinPts.
- Sulit ketika density antarcluster sangat berbeda.
- Distance menjadi kurang informatif pada dimensi yang sangat tinggi.
- Skala fitur yang berbeda dapat mengganggu hasil jika tidak dinormalisasi.
- Pemilihan parameter yang kurang tepat dapat menghasilkan terlalu banyak noise atau cluster yang menyatu.
Ringkasan
DBSCAN merupakan clustering berbasis kepadatan dengan dua parameter utama, epsilon dan MinPts.
Pada contoh ini digunakan:
$$ \varepsilon=0.5, \qquad MinPts=4 $$
Hasilnya adalah 2 cluster, dengan core point A1, A2, A3, A4, B1, B2, B3, B4, border point A5, dan noise N1.
DBSCAN tidak menghitung centroid. Cluster berkembang melalui hubungan density-reachable dari core point ke core point dan dapat menyertakan border point.
FAQ DBSCAN
Apa kepanjangan DBSCAN?
DBSCAN adalah Density-Based Spatial Clustering of Applications with Noise.
Apakah DBSCAN termasuk supervised learning?
Tidak. DBSCAN merupakan algoritma unsupervised learning untuk clustering.
Apakah DBSCAN harus menentukan jumlah cluster?
Tidak. Jumlah cluster muncul dari struktur kepadatan data berdasarkan epsilon dan MinPts.
Apa itu epsilon?
Epsilon adalah radius maksimum yang digunakan untuk menentukan apakah suatu titik termasuk neighbor titik lain.
Apa itu MinPts?
MinPts adalah jumlah minimum titik dalam epsilon-neighborhood agar sebuah titik dikategorikan sebagai core point.
Apakah titik itu sendiri dihitung pada MinPts?
Pada definisi yang digunakan dalam tutorial ini, ya. Titik itu sendiri termasuk anggota epsilon-neighborhood.
Apa itu core point?
Core point adalah titik yang memiliki jumlah neighbor minimal sebesar MinPts dalam radius epsilon.
Apa itu border point?
Border point tidak memenuhi syarat sebagai core, tetapi berada dalam epsilon-neighborhood suatu core point.
Apa itu noise?
Noise adalah titik yang tidak masuk ke wilayah density-reachable dari cluster mana pun.
Bisakah noise berubah menjadi border?
Bisa. Dalam proses DBSCAN, titik yang sementara ditandai noise dapat dimasukkan ke cluster apabila kemudian ditemukan sebagai neighbor dari core point.
Apakah DBSCAN harus menggunakan Euclidean Distance?
Tidak selalu. Ukuran jarak atau dissimilarity dapat dipilih sesuai tipe data dan implementasi, selama definisi neighborhood tetap konsisten.
Apakah data harus dinormalisasi?
Sangat disarankan jika fitur mempunyai skala berbeda, karena DBSCAN sangat bergantung pada perhitungan jarak.
Apa perbedaan DBSCAN dan K-Means?
DBSCAN membentuk cluster berdasarkan kepadatan dan dapat mendeteksi noise. K-Means membentuk sejumlah k cluster berdasarkan kedekatan terhadap centroid.
Apa perbedaan DBSCAN dan K-Medoids?
K-Medoids menentukan k cluster menggunakan objek aktual sebagai pusat. DBSCAN tidak membutuhkan pusat cluster dan membentuk cluster berdasarkan density connectivity.
Kapan DBSCAN cocok digunakan?
DBSCAN cocok ketika data diperkirakan memiliki cluster berbasis kepadatan, bentuk cluster tidak beraturan, dan terdapat kemungkinan noise atau outlier.
Referensi
- Ester, M., Kriegel, H.-P., Sander, J. & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD), 226–231.
- Schubert, E., Sander, J., Ester, M., Kriegel, H. P. & Xu, X. (2017). DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN. ACM Transactions on Database Systems, 42(3).
- Han, J., Kamber, M. & Pei, J. (2011). Data Mining: Concepts and Techniques, Third Edition. Morgan Kaufmann.
Source Code DBSCAN
Berikut adalah beberapa source code yang menggunakan algoritma DBSCAN untuk clustering berbasis kepadatan.
