Pengelompokan dengan DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) adalah algoritma pengelompokan yang mengelompokkan titik-titik yang berdekatan satu sama lain berdasarkan kriteria kepadatan. Berbeda dengan model Clustering lainnya seperti K-means, DBSCAN dapat mengidentifikasi cluster dengan bentuk sembarang dan tidak memerlukan jumlah cluster untuk ditentukan sebelumnya. Itu kurang sensitif terhadap kebisingan dan dapat menangani kelompok dengan kepadatan berbeda.

Untuk mendapatkan hasil yang memuaskan dengan menggunakan algoritma DBSCAN diasumsikan bahwa cluster yang berbeda dalam data memiliki kerapatan yang relatif sama, dimana kerapatan yang dimaksud adalah jumlah titik yang ada di setiap lingkungan N(x, ε) yang didefinisikan dengan radius ε dan titik data x. Klaim ini dapat diverifikasi secara optik dengan mengamati contoh DBSCAN di tengah gambar di atas, di mana titik-titik di sekitar gugus biru, yang memiliki kerapatan berbeda, dianggap sebagai bagian dari gugus jingga.

Satu-satunya parameter yang diperlukan untuk mengimplementasikan DBSCAN adalah:

• MinPts = Titik minimum yang harus dimiliki oleh lingkungan titik data agar titik data dianggap sebagai titik inti klaster
• ε = Jari-jari lingkungan (yaitu seberapa besar "lingkaran" yang kita inginkan di sekitar titik data pusat)

1. Core Point : Jenis titik data ini memiliki densitas ≥ MinPts. Artinya jumlah titik data dalam N(x, ε) lebih besar atau sama dengan MinPts.

2. Border Point : Jenis titik data ini memiliki kepadatan < MinPts tetapi jarak (y, cp) ≤ ε dimana cp adalah titik inti. Artinya titik-titik tersebut tidak memiliki kepadatan yang diperlukan untuk menjadi titik inti tetapi juga tidak terlalu jauh dari titik inti untuk dianggap sebagai kebisingan.

Contoh : MinPts = 4, ε = 3 maka y adalah titik batas

3. Titik Kebisingan : Jenis titik data ini memiliki densitas < MinPts dan, jarak(z, cp) ≥ ε. Artinya tidak memiliki kepadatan yang diperlukan untuk menjadi titik inti dan jauh dari titik inti mana pun.

Contoh : MinPts = 4, ε = 3 maka z adalah noise point

Dan berdasarkan proses kategorisasi poin data tersebut, algoritma DBSCAN berjalan sebagai berikut:

1. Ulangi setiap titik data dan klasifikasikan dalam salah satu dari tiga kategori tersebut
2. Hilangkan semua titik kebisingan
3. Pertimbangkan semua titik inti yang berdekatan satu sama lain berada di cluster yang sama (Artinya jika cp_1 dan cp_2 adalah titik inti dan jarak (cp_1, cp_2) ≤ ε maka cp_1 dan cp_2 dianggap berada di cluster yang sama.)
4. Tetapkan setiap titik perbatasan dalam sekelompok titik inti berdasarkan jaraknya (titik perbatasan yang terletak tepat di tengah antara dua kelompok harus diselesaikan secara terpisah, mungkin dengan melempar koin ;D )