KAL
Menu

DBSCAN

Clustering kepadatan dan penanganan noise.

Daftar isi

DBSCAN mengelompokkan sampel berdasarkan kepadatan wilayahnya, sehingga bentuk klaster tidak dibatasi oleh asumsi bundar seperti pada KMeans. Topik ini menjelaskan dua parameternya, makna label -1 bagi noise, keunggulan dan kelemahannya, serta demonstrasi lengkap pada data make_moons yang menggagalkan KMeans. Pentingnya scaling sebelum DBSCAN juga dibuktikan dengan kode.

Cara kerja DBSCAN#

Nama lengkap DBSCAN adalah Density-Based Spatial Clustering of Applications with Noise, yaitu pengelompokan berbasis kepadatan yang sekaligus menandai titik yang tidak tergolong kelompok mana pun. Algoritmanya berjalan dengan dua parameter. Parameter eps adalah radius tetangga di sekitar sebuah sampel, sedangkan parameter min_samples adalah banyaknya sampel minimum yang harus berada dalam radius tersebut agar sampel itu disebut core point, yakni titik inti yang berada di wilayah padat. Sampel yang berjarak kurang dari eps dari sebuah core point, tetapi sendirian tidak memenuhi syarat inti, disebut titik batas, dan sampel yang tidak memenuhi keduanya diberi label -1 sebagai noise, yakni titik yang tidak termasuk klaster mana pun.

Satu klaster DBSCAN terbentuk dari core point yang terhubung satu sama lain dalam rentang eps, lalu titik batasnya diserap ke klaster terdekat. Konsekuensinya, jumlah klaster tidak ditentukan di depan seperti k pada KMeans, melainkan muncul sendiri dari struktur kepadatan data. Klaster boleh berbentuk lengkung, pipih, atau tidak beraturan, selama kepadatannya menerus.

Label -1 menuntut pembacaan yang berbeda dari label klaster. Angka 0, 1, dan seterusnya adalah penanda klaster, sedangkan -1 adalah status khusus yang berarti ditolak, sehingga statistik seperti np.bincount perlu digunakan dengan hati-hati karena fungsi itu menolak bilangan negatif.

Demonstrasi pada make_moons#

Data make_moons menghasilkan dua lengkungan yang saling menyusup, sehingga menjadi uji standar untuk asumsi bentuk klaster. KMeans dijalankan dengan k sama dengan 2, kemudian dibandingkan dengan DBSCAN yang tidak memerlukan jumlah klaster sama sekali. Karena jarak antartitiknya kecil, kedua algoritma dijalankan pada data hasil StandardScaler.

python moons-dbscan.py 
import numpy as np
from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, DBSCAN
from sklearn.metrics import adjusted_rand_score
from sklearn.preprocessing import StandardScaler

X, y = make_moons(n_samples=400, noise=0.06, random_state=42)
Xs = StandardScaler().fit_transform(X)

kmeans = KMeans(n_clusters=2, random_state=42, n_init=10).fit(Xs)
dbscan = DBSCAN(eps=0.25, min_samples=5).fit(Xs)

print("KMeans (k=2):", np.bincount(kmeans.labels_))
for c in sorted(set(dbscan.labels_)):
    n = int(np.sum(dbscan.labels_ == c))
    nama = "noise" if c == -1 else f"klaster {c}"
    print(f"DBSCAN {nama}: {n} sampel")
print("ARI KMeans vs label :", round(adjusted_rand_score(y, kmeans.labels_), 3))
print("ARI DBSCAN vs label :", round(adjusted_rand_score(y, dbscan.labels_), 3))
text Keluaran 
KMeans (k=2): [200 200]
DBSCAN noise: 1 sampel
DBSCAN klaster 0: 200 sampel
DBSCAN klaster 1: 199 sampel
ARI KMeans vs label : 0.475
ARI DBSCAN vs label : 0.995

Ukuran klaster KMeans tampak seimbang pada 200 dan 200, tetapi ARI 0.475 mengungkap bahwa pembagiannya memotong tiap lengkungan di tengah dan menyatukan potongan dua lengkungan yang letaknya berdekatan. DBSCAN mengikuti kepadatan lengkungnya, menemukan kedua bulan sabit secara utuh dengan ARI 0.995, dan menolak satu sampel sebagai noise. Anggota noise itu tidak dipaksakan masuk ke klaster mana pun, dan pelaporannya menggunakan penjumlahan boolean alih-alih np.bincount karena label -1 tidak dapat dihitung oleh fungsi tersebut.

Memilih eps#

Nilai eps menentukan ketebalan wilayah yang dianggap padat, sehingga hasilnya sangat peka terhadap nilai ini. min_samples ikut berperan sebagai ambang kepadatan, tetapi eps yang paling sering menjadi penentu bentuk hasilnya. Sapuan berikut menjalankan DBSCAN pada data yang sama dengan empat nilai eps dan mencatat jumlah klaster serta banyaknya noise.

python eps-scan.py 
import numpy as np
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

X, _ = make_moons(n_samples=400, noise=0.06, random_state=42)
Xs = StandardScaler().fit_transform(X)

for eps in [0.1, 0.2, 0.3, 0.5]:
    db = DBSCAN(eps=eps, min_samples=5).fit(Xs)
    n_klaster = len(set(db.labels_)) - (1 if -1 in db.labels_ else 0)
    noise = int(np.sum(db.labels_ == -1))
    print(f"eps={eps}  jumlah klaster={n_klaster}  noise={noise}")
text Keluaran 
eps=0.1  jumlah klaster=26  noise=114
eps=0.2  jumlah klaster=3  noise=1
eps=0.3  jumlah klaster=2  noise=1
eps=0.5  jumlah klaster=2  noise=0

Pola pada sapuan itu berlaku umum. Nilai eps yang terlalu kecil memecah data menjadi banyak klaster kecil dan memproduksi noise dalam jumlah besar, yaitu 26 klaster dan 114 noise pada eps 0.1. Nilai yang terlalu besar menyatukan klaster yang semestinya terpisah. Titik tengahnya ditemukan lewat peninjauan jarak setiap sampel ke tetangganya sampai urutan min_samples, yaitu jarak yang biasa disebut k-distance, dan nilai eps yang layak biasanya berada di sekitar belokan jarak tersebut. Peninjauan semacam ini menggantikan tebakan awal dengan pengamatan jarak yang nyata pada data.

Keunggulan dan kelemahan#

Tiga keunggulan DBSCAN muncul langsung dari cara kerjanya. Bentuk klasternya bebas karena hanya kepadatan yang diperhitungkan, jumlah klasternya ditemukan sendiri tanpa parameter k, dan sampel yang menyendiri ditolak sebagai noise alih-alih dipaksakan masuk ke kelompok terdekat. Kombinasi ini membuat DBSCAN cocok sebagai alat pembersihan data sekaligus alat pengelompokan.

Kelemahannya berasal dari satu nilai eps yang digunakan untuk seluruh data. Klaster yang kepadatannya berbeda jauh sulit ditangani, karena radius yang cocok untuk wilayah padat akan terlalu besar untuk wilayah jarang atau sebaliknya. Pada dimensi tinggi, jarak antarsampel kehilangan daya pembeda sehingga pemilihan eps menjadi sulit. DBSCAN juga mengukur jarak dalam satuan absolut, sehingga skala fitur harus disetarakan terlebih dahulu.

python skala-fitur.py 
import numpy as np
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

X, _ = make_moons(n_samples=400, noise=0.06, random_state=42)

# fitur pertama diperbesar sepuluh kali tanpa scaling
X2 = X.copy()
X2[:, 0] *= 10.0

db_mentah = DBSCAN(eps=0.3, min_samples=5).fit(X2)
db_scaling = DBSCAN(eps=0.3, min_samples=5).fit(StandardScaler().fit_transform(X2))

for nama, db in [("Tanpa scaling", db_mentah), ("Dengan scaling", db_scaling)]:
    n_klaster = len(set(db.labels_)) - (1 if -1 in db.labels_ else 0)
    noise = int(np.sum(db.labels_ == -1))
    print(f"{nama}: klaster={n_klaster}  noise={noise}")
text Keluaran 
Tanpa scaling: klaster=26  noise=73
Dengan scaling: klaster=2  noise=1

Fitur pertama yang diperbesar sepuluh kali membuat radius 0.3 terlalu kecil relatif terhadap jarak utama data, sehingga DBSCAN menghasilkan 26 klaster kecil dan 73 noise. Setelah skala disetarakan dengan StandardScaler pada data yang sama, hasilnya kembali menjadi dua klaster dengan satu noise. Satu eps yang sama menghasilkan keluaran yang berbeda hanya karena skala fiturnya.

Kesalahan umum#

Kesalahan pertama adalah menghitung label DBSCAN dengan np.bincount secara langsung. Fungsi itu menolak bilangan negatif dan melempar error pada label -1, sehingga perhitungan menggunakan np.unique dengan return_counts=True atau penjumlahan boolean seperti pada demonstrasi.

Kesalahan kedua adalah memperlakukan -1 sebagai nomor klaster dalam analisis lanjutan. Rata-rata fitur per klaster yang dihitung tanpa menyaring label -1 akan mencampur sampel yang ditolak ke dalam kelompok yang tidak ada, sehingga seluruh statistiknya menyesatkan. Pencucian label dilakukan lebih dahulu sebelum agregasi apa pun.

Kesalahan ketiga adalah menggunakan DBSCAN pada data yang kepadatan antarklasternya timpang tanpa penyesuaian. Satu eps global tidak dapat melayani wilayah padat dan jarang sekaligus, dan tanda kegagalannya berupa banyak noise pada wilayah jarang atau klaster yang menyatu pada wilayah padat.

Ringkasan#

  • DBSCAN mengelompokkan berdasarkan kepadatan melalui eps dan min_samples, dengan label -1 untuk sampel yang ditolak sebagai noise.
  • Jumlah klaster muncul otomatis dari data, dan bentuk klasternya bebas, sehingga dua lengkungan make_moons ditemukan utuh dengan ARI 0.995 sementara KMeans hanya 0.475.
  • Nilai eps yang terlalu kecil menghasilkan banyak noise, sedangkan yang terlalu besar menyatukan klaster.
  • DBSCAN membutuhkan scaling karena eps diukur dalam satuan fitur yang absolut, dan satu nilai eps sulit melayani kepadatan yang berbeda.

Referensi#