DBSCAN dan Metode Hierarkis

DBSCAN berbasis kepadatan dan clustering hierarkis sebagai alternatif K-Means.

Daftar isi

Topik ini membahas dua keluarga clustering yang tidak mengandalkan centroid, yaitu DBSCAN yang membentuk cluster dari kepadatan titik dan metode hierarkis yang menggabungkan kelompok terdekat secara bertahap. Keduanya menjadi alternatif K-Means ketika bentuk kelompok tidak bulat atau jumlah kelompok alami belum diketahui. Satu skrip Python membandingkan K-Means, DBSCAN, dan clustering agglomerative pada data dua lengkungan yang saling bertaut, lalu perbedaan hasilnya dibaca dari jumlah anggota setiap label.

Cluster dari kepadatan titik#

DBSCAN, singkatan dari density-based spatial clustering of applications with noise, mendefinisikan cluster sebagai wilayah yang padat titik, bukan sebagai wilayah yang dekat dengan satu titik tengah. Dua hyperparameter menentukan makna kepadatan, yaitu eps sebagai radius tetangga dan min_samples sebagai jumlah tetangga minimum. Sebuah titik dinyatakan titik inti (core point) apabila setidaknya min_samples titik berada dalam radius eps, dengan syarat jarak antara titik dan tetangganya $\lVert x - x' \rVert \le \varepsilon$ . Parameter itu karenanya harus dibaca sebagai satu pasangan, bukan dua angka yang berdiri sendiri.

Cluster kemudian tumbuh dari titik inti. Dua titik inti yang saling berdekatan digabungkan, dan titik yang bukan inti tetapi berada dalam radius suatu titik inti menjadi anggota tepi (border point). Titik yang tidak termasuk keduanya dinyatakan derau (noise) dan diberi label -1, sehingga deteksi outlier diperoleh tanpa alat tambahan. Karena batasnya mengikuti aliran kepadatan, cluster yang dihasilkan boleh memanjang, melengkung, atau berbentuk cincin, bentuk yang mustahil dipotong oleh garis lurus antara dua centroid.

Kekuatan itu membawa risiko pada pemilihan eps, karena nilai yang terlalu kecil membuat seluruh titik dinyatakan derau, sedangkan nilai yang terlalu besar menyatukan seluruh data menjadi satu gumpalan. Pemilihan eps karenanya membutuhkan percobaan pada beberapa tingkat radius, dan hasilnya diperiksa dari jumlah titik derau serta jumlah cluster yang muncul. Kedua ujung kesalahan itu mudah dikenali dari keluaran, sehingga nilai eps yang jauh dari layak cepat terlihat.

Nilai min_samples juga mengatur keketatan definisi ini. Nilai yang lebih besar membuat titik inti semakin sulit terbentuk, sehingga kelompok kecil beranggota sedikit tidak lagi menjadi cluster, sedangkan nilai kecil membuat kelompok tipis mudah muncul. Nilai awal yang lazim untuk data berdimensi rendah adalah 4 atau 5, kemudian disesuaikan dengan memeriksa jumlah derau dan jumlah cluster pada keluaran.

Metode hierarkis agglomerative#

Clustering hierarkis agglomerative membangun cluster dari bawah ke atas. Setiap titik dimulai sebagai satu cluster, lalu dua cluster dengan jarak terdekat digabungkan berulang-ulang hingga tersisa satu cluster besar. Riwayat penggabungan itu membentuk pohon yang disebut dendrogram, dengan ketinggian yang menunjukkan jarak saat dua kelompok disatukan. Memotong pohon pada tingkat tertentu menghasilkan pembagian data, dan jumlah cluster ditentukan oleh tingkat pemotongannya.

Pada scikit-learn, metode ini tersedia sebagai AgglomerativeClustering, dan jumlah cluster ditetapkan melalui argumen n_clusters. Aturan jarak antar cluster disebut linkage, dan bawaannya bernama ward, yang menggabungkan pasangan cluster dengan kenaikan varians terkecil. Karena aturannya berbasis varians, metode agglomerative dengan ward cenderung berperilaku mirip K-Means pada data berbentuk memanjang, sebagaimana terlihat pada percobaan berikutnya. Keunggulan praktisnya adalah tidak membutuhkan radius seperti eps, sedangkan kelemahannya adalah biaya perhitungan yang tumbuh cepat pada data berukuran besar.

Pembacaan dendrogram memberi petunjuk tambahan saat jumlah cluster belum diketahui. Gabungan yang tingginya meloncat jauh menandakan kelompok yang memang terpisah, sedangkan tinggi yang bertambah perlahan menandakan data yang menyatu tanpa batas jelas. Pola itu membantu memilih tingkat pemotongan, dan hasilnya tetap diperiksa terhadap makna kelompok menurut domain.

Perbandingan pada data dua lengkungan#

Data dua lengkungan dari make_moons menjadi uji yang jelas untuk perbedaan ini, karena kedua kelompoknya memanjang dan saling bertaut. Skrip berikut menskalakan data terlebih dahulu, lalu menjalankan tiga algoritma dengan jumlah cluster dua. Yang dicetak hanyalah jumlah anggota setiap label, dan label -1 pada DBSCAN menandai derau. Jalankan skrip dari folder topik dengan perintah python3 -B dbscan-moons.py.

python dbscan-moons.py

"""Membandingkan K-Means, DBSCAN, dan agglomerative pada data dua lengkungan."""

import numpy as np
from sklearn.cluster import AgglomerativeClustering, DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

# data dua lengkungan yang saling bertautan, lalu diskalakan
X, _ = make_moons(n_samples=300, noise=0.06, random_state=42)
X = StandardScaler().fit_transform(X)

label_km = KMeans(n_clusters=2, n_init=10, random_state=42).fit_predict(X)
print("KMeans, jumlah anggota tiap label:")
for label, n in enumerate(np.bincount(label_km, minlength=2)):
    print(f"  label {label}: {n} titik")

label_db = DBSCAN(eps=0.3, min_samples=5).fit_predict(X)
print("DBSCAN, jumlah anggota tiap label unik:")
for label in np.unique(label_db):
    print(f"  label {label}: {int((label_db == label).sum())} titik")

label_ag = AgglomerativeClustering(n_clusters=2).fit_predict(X)
print("Agglomerative, jumlah anggota tiap label:")
for label, n in enumerate(np.bincount(label_ag, minlength=2)):
    print(f"  label {label}: {n} titik")

text Keluaran

KMeans, jumlah anggota tiap label:
  label 0: 150 titik
  label 1: 150 titik
DBSCAN, jumlah anggota tiap label unik:
  label 0: 150 titik
  label 1: 150 titik
Agglomerative, jumlah anggota tiap label:
  label 0: 202 titik
  label 1: 98 titik

K-Means menghasilkan dua cluster berukuran 150 dan 150, dan keseimbangan itu justru tanda kegagalan di sini. Pembagian berbasis centroid membelah data di antara dua titik tengah, sehingga setiap cluster berisi gabungan potongan dari kedua lengkungan, bukan satu lengkungan utuh. Apabila dibandingkan dengan pembagian asli yang dikembalikan make_moons, hasil K-Means hanya cocok sekitar 85 persen. DBSCAN memisahkan kedua lengkungan secara utuh, yaitu dua cluster berisi 150 titik tanpa satu pun titik derau. Radius eps=0.3 pada data yang telah diskalakan cukup untuk menghubungkan titik-titik padat di sepanjang tiap lengkungan tanpa menjembatani celah antar lengkungan.

AgglomerativeClustering dengan linkage ward memberi hasil 202 dan 98, yaitu satu lengkungan utuh yang menyatu dengan separuh lengkungan lainnya. Perilaku ini sesuai dengan aturan penggabungannya yang menekan kenaikan varians, sehingga kelompok yang dihasilkan mirip dengan hasil K-Means. Pelajaran praktisnya adalah bahwa clustering hierarkis bukan solusi otomatis untuk bentuk arbitrer, sedangkan pilihan linkage beserta ukuran jaraknya tetap menentukan.

Ringkasan#

DBSCAN membentuk cluster dari kepadatan titik melalui eps dan min_samples, menangkap bentuk arbitrer, dan menandai derau dengan label -1 tanpa alat tambahan.
Clustering agglomerative menggabungkan kelompok terdekat secara bertahap menjadi dendrogram, dan jumlah cluster ditetapkan saat pohon dipotong.
Pada data dua lengkungan, K-Means membelah kedua lengkungan, DBSCAN memulihkannya secara utuh, sedangkan agglomerative ward ikut tergelincir karena aturannya berbasis varians.
Data diskalakan sebelum DBSCAN, dan pemilihan eps diverifikasi dari jumlah derau serta jumlah cluster yang muncul.

Referensi#

sklearn.cluster.DBSCAN — scikit-learn — Dokumentasi DBSCAN beserta makna eps, min_samples, dan label derau.
sklearn.cluster.AgglomerativeClustering — scikit-learn — Dokumentasi clustering agglomerative dan pilihan linkage.
Clustering — scikit-learn — Panduan resmi yang memuat bagian DBSCAN dan hierarchical clustering.