🐒DBSCAN Clustering

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

Definisi

DBSCAN adalah algoritma klasterisasi berbasis kepadatan (density-based clustering algorithm) yang bertujuan menemukan kelompok data (klaster) sebagai wilayah dengan kepadatan tinggi yang dipisahkan oleh wilayah berkepadatan rendah. Berbeda dengan algoritma berbasis centroid (misalnya K-Means), DBSCAN tidak memerlukan informasi jumlah klaster sejak awal, dan dapat mengenali bentuk klaster yang tidak teratur.

Algoritma DBSCAN memandang klaster sebagai wilayah dengan kepadatan tinggi yang terpisah oleh wilayah dengan kepadatan rendah. Karena definisi yang cukup umum ini, DBSCAN mampu menemukan klaster dengan bentuk apa saja, berbeda dengan k-means yang hanya mampu mengenali klaster berbentuk konveks. Komponen utama dari DBSCAN adalah konsep core sample, yaitu data yang berada di area padat. Dengan demikian, sebuah klaster dalam DBSCAN terbentuk dari kumpulan core sample yang saling berdekatan, ditentukan berdasarkan ukuran jarak tertentu, serta kumpulan non-core sample yang posisinya dekat dengan core sample, meskipun tidak termasuk core sample itu sendiri.

Algoritma DBSCAN memiliki dua parameter:

• min_samples

• eps (epsilon)

Kedua parameter ini mendefinisikan secara formal apa yang dimaksud dengan “padat”. Nilai min_samples yang lebih tinggi atau eps yang lebih rendah menunjukkan bahwa diperlukan kepadatan yang lebih tinggi untuk membentuk sebuah klaster.

Secara formal, sebuah core sample didefinisikan sebagai data dalam sebuah dataset yang memiliki setidaknya min_samples tetangga dalam radius eps. Sampel-sampel tetangga ini disebut sebagai neighbors dari core sample tersebut. Hal ini menunjukkan bahwa core sample berada di area dengan kepadatan tinggi dalam ruang vektor. Klaster kemudian dibangun secara rekursif, dimulai dari satu core sample, lalu mencari semua neighbors yang juga core sample, kemudian mencari neighbors mereka, dan seterusnya. Selain core sample, sebuah klaster juga mencakup non-core sample, yaitu data yang merupakan tetangga dari core sample di dalam klaster, tetapi bukan core sample itu sendiri. Data semacam ini dapat dianggap berada di pinggiran klaster.

Setiap core sample secara definisi akan selalu menjadi bagian dari sebuah klaster. Sebaliknya, jika sebuah data bukan core sample dan berjarak lebih dari eps terhadap seluruh core sample, maka data tersebut dianggap sebagai outlier oleh algoritma.

Dari sisi parameter, min_samples berfungsi untuk mengatur seberapa toleran algoritma terhadap noise. Pada dataset yang besar dan penuh noise, biasanya nilai ini dibuat lebih tinggi agar hasil klasterisasi lebih stabil. Sementara itu, parameter eps memiliki peran yang sangat krusial. Nilai ini menentukan ukuran lingkungan lokal dari setiap titik, sehingga pemilihannya harus disesuaikan dengan dataset dan fungsi jarak yang digunakan.

• Jika eps terlalu kecil, sebagian besar data tidak akan masuk ke klaster (dan diberi label –1 untuk “noise”).

• Jika eps terlalu besar, klaster yang berdekatan bisa bergabung menjadi satu klaster besar, bahkan seluruh dataset bisa dianggap sebagai satu klaster tunggal.

Beberapa literatur menyarankan heuristik untuk memilih parameter ini, misalnya dengan mencari “siku” (knee) pada grafik jarak nearest neighbor. Pada ilustrasi berikut menunjukan bahwa:

• Warna menunjukkan keanggotaan klaster.

• Lingkaran besar → core sample yang ditemukan algoritma.

• Lingkaran kecil → non-core sample yang tetap menjadi bagian dari klaster.

• Titik hitam → outlier yang terdeteksi.

Cara Kerja DBSCAN

1. Untuk setiap data (instance), algoritma menghitung berapa banyak data lain yang berada dalam jarak tertentu epsilon (ε / eps). Wilayah ini disebut ε-neighborhood dari data tersebut.

2. Jika sebuah data memiliki paling sedikit min_samples data di dalam ε-neighborhood (termasuk dirinya sendiri), maka data tersebut disebut core instance. Core instance adalah data yang berada di wilayah padat.

3. Semua data yang berada dalam neighborhood dari core instance dimasukkan ke dalam klaster yang sama. Jika neighborhood ini mencakup core instance lain, maka mereka akan bergabung menjadi satu klaster besar.

4. Data yang tidak memenuhi kriteria sebagai core instance, dan juga tidak berada dalam neighborhood core instance lain, dianggap sebagai anomali (outlier).

DBSCAN clustering using two different neighborhood radiuses

Gambar diatas menunjukkan bagaimana sebuah algoritma klastering DBSCAN bekerja untuk mengelompokkan data. Tujuan utamanya adalah untuk menemukan kelompok-kelompok data yang padat, sekaligus mengabaikan data-data yang terisolasi atau berada di luar kelompok tersebut.

Pada gambar, kita melihat dua skenario dengan pengaturan yang berbeda:

• Gambar Kiri (Terlalu Sensitif): Algoritma terlalu "pelit" dalam mengelompokkan data. Akibatnya, data yang seharusnya menjadi satu kelompok justru terpecah-pecah menjadi banyak kelompok kecil. Titik-titik yang terpisah dari kelompok lain (ditandai x merah) dianggap sebagai titik noise atau data yang tidak termasuk kelompok mana pun.

• Gambar Kanan (Pengaturan Tepat): Algoritma diatur dengan lebih "longgar." Dengan pengaturan ini, ia berhasil mengenali dan menggabungkan data yang seharusnya menjadi satu kelompok besar, membentuk dua klaster utama yang akurat (dua bulan sabit). Titik-titik yang sebelumnya dianggap noise kini berhasil dimasukkan ke dalam kelompok yang sesuai.

Secara umum, gambar tersebut menjelaskan bahwa keberhasilan algoritma DBSCAN sangat bergantung pada pengaturan parameternya. Pengaturan yang tidak tepat bisa membuat algoritma gagal mengenali kelompok yang sebenarnya, sementara pengaturan yang pas akan menghasilkan pengelompokan yang akurat dan logis.

Karakteristik DBSCAN

• Tidak perlu menentukan jumlah klaster di awal, berbeda dengan K-Means.

• Mampu mengenali klaster berbentuk bebas (tidak terbatas pada bentuk lingkaran atau bola).

• Robust terhadap outlier, karena data yang tidak cocok dengan klaster manapun otomatis ditandai sebagai anomali.

• Memiliki dua hyperparameter utama:

  • epsilon (ε / eps) → jarak maksimum untuk menentukan tetangga.

  • min_samples → jumlah minimum data di dalam neighborhood untuk membentuk sebuah klaster.

• Kompleksitas komputasi DBSCAN adalah sekitar O(m log m) namu, kebutuhan memori bisa sangat tinggi jika nilai epsilon (ε) terlalu besar.

Perbandingan DBSCAN dan K-Means

Aspek	K-Means	DBSCAN
Jumlah Klaster	Harus ditentukan sejak awal (kk).	Tidak perlu ditentukan; klaster terbentuk berdasarkan kepadatan.
Bentuk Klaster	Baik untuk klaster berbentuk bulat/sferis.	Bisa mengenali klaster dengan bentuk bebas dan tidak beraturan.
Outlier	Tidak ditangani, outlier dipaksa masuk ke klaster.	Outlier otomatis ditandai sebagai anomali (−1-1).
Parameter	Hanya jumlah klaster (kk).	Dua parameter: ε\varepsilon (eps) dan min_samples.
Kompleksitas	Cepat dan efisien, tetapi sensitif pada inisialisasi centroid.	Sedikit lebih berat komputasi, tetapi lebih stabil terhadap variasi data.
Kepadatan Berbeda	Tidak bisa menangani variasi kepadatan dengan baik.	Bisa gagal juga jika perbedaan kepadatan antar klaster terlalu besar.

• Gunakan K-Means jika: jumlah klaster sudah diketahui, data relatif seimbang, dan bentuk klaster mendekati bulat.

• Gunakan DBSCAN jika: jumlah klaster tidak diketahui, bentuk klaster tidak teratur, dan ingin mendeteksi outlier secara otomatis.