🥈HDBSCAN

HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) adalah algoritma klasterisasi berbasis kepadatan yang merupakan pengembangan dari metode DBSCAN (Density-Based Spatial Clustering of Applications with Noise). HDBSCAN menambahkan elemen klasterisasi hierarkis pada DBSCAN, yang memungkinkan algoritma ini untuk lebih fleksibel dalam mengidentifikasi klaster dengan kepadatan yang bervariasi. Salah satu perbedaan utama antara HDBSCAN dan DBSCAN adalah cara algoritma ini menangani parameter kepadatan dan fungsi jarak yang digunakan untuk membentuk klaster.

Perbedaan Utama HDBSCAN dan DBSCAN

1. Parameter Radius (eps)

   • DBSCAN memerlukan penentuan parameter radius (eps) untuk mengukur kedekatan antar titik dan membentuk klaster. Pengguna harus menentukan seberapa besar radius yang diperlukan agar titik data dapat digabungkan ke dalam klaster yang sama.

   • HDBSCAN tidak memerlukan penentuan parameter radius yang eksplisit, karena algoritma ini secara otomatis mengidentifikasi klaster dengan bervariasi kepadatan dan menangani noise lebih efektif tanpa memerlukan input radius dari pengguna.

2. Fungsi Jarak (Distance Function)

   • Pada DBSCAN, fungsi jarak yang paling umum digunakan adalah Euclidean distance, yang mengukur jarak langsung antara dua titik data.

   • HDBSCAN, di sisi lain, menggunakan fungsi jarak yang lebih kompleks yang disebut mutual reachability distance. Fungsi jarak ini menggabungkan dua komponen jarak yang berbeda:

     1. Metric Distance (misalnya, Euclidean distance), yang mengukur jarak langsung antara dua titik.

     2. Core Distance (Jarak Inti), yang mengukur jarak terdekat titik xp ke titik lain xq dalam radius yang mencakup jumlah titik minimum. Ini berarti, jarak inti menunjukkan seberapa rapat titik xp berada dalam klaster berdasarkan kepadatan titik di sekitarnya.

3. Mutual Reachability Distance

   • Fungsi jarak yang digunakan oleh HDBSCAN ini dinamakan mutual reachability distance. Ini adalah kombinasi dari jarak core distance dan metric distance yang dihitung dengan formula sebagai berikut:

$$d(x_p, x_q) = \max\left(d_{\text{core}}(x_p), d_{\text{core}}(x_q), d(x_p, x_q)\right)$$

Di mana:

$$d(x_p, x_q) \quad \text{adalah jarak antara dua titik} \quad x_p \quad \text{dan} \quad x_q.$$

$$d_{\text{core}}(x_p) \quad \text{adalah core distance dari titik} \quad x_p$$

$$d_{\text{core}}(x_q) \quad \text{adalah core distance dari titik} \quad x_q$$

$$d(x_p, x_q) \quad \text{adalah metric distance antara titik} \quad x_p \quad \text{dan} \quad x_q$$

Jika jarak antara kedua titik lebih kecil daripada salah satu core distance keduanya, maka jarak yang lebih kecil akan dipilih sebagai jarak antar kedua titik tersebut. Pendekatan ini memastikan bahwa titik dengan kepadatan lebih tinggi akan tetap dikelompokkan bersama meskipun keduanya tidak saling berdekatan langsung.

Hirarki Klaster dalam HDBSCAN

Perbedaan lain yang signifikan antara DBSCAN dan HDBSCAN adalah pada penambahan konsep klasterisasi hierarkis. Pada HDBSCAN, data yang akan dikelompokkan pertama-tama akan ditransformasikan menjadi graf.

Perbedaan fundamental antara DBSCAN (Density-Based Spatial Clustering of Applications with Noise) dan HDBSCAN (Hierarchical DBSCAN) terletak pada pendekatan keduanya terhadap parameter kepadatan dan penemuan struktur cluster dengan kepadatan bervariasi.

Inti dari perbedaan ini adalah implementasi Hierarchical Clustering pada HDBSCAN, yang secara efektif mengeliminasi kebutuhan penentuan parameter radius kepadatan global ($ϵ$) yang menjadi kelemahan DBSCAN.

Untuk memahami bagaimana proses klasterisasi ini berjalan, kita bisa menggunakan visualisasi dengan data yang telah dibagi menjadi beberapa klaster. Misalnya, data dengan bentuk bulan sabit dan titik data yang tersebar akan menunjukkan bagaimana algoritma ini memisahkan dan mengidentifikasi pulau kepadatan tinggi, dengan titik-titik yang lebih jarang didorong menjauh.

Gambar A

Pada Gambar A, sebuah titik data dikelilingi oleh lingkaran yang menggambarkan core distance. Lingkaran ini menggambarkan jarak dari titik tersebut ke titik tetangga terdekatnya yang ke-6, dengan asumsi k=6. Dalam hal ini, jika sebuah titik memiliki lebih dari k-1 tetangga dalam jangkauan core distance-nya, maka titik tersebut dapat dianggap sebagai bagian dari core point dalam klaster. Sebaliknya, jika titik berada di luar lingkaran dan tidak memiliki cukup tetangga dalam jarak core distance, titik tersebut cenderung dianggap sebagai noise atau titik yang tidak relevan untuk membentuk klaster.

Konsep ini sangat bergantung pada pemilihan nilai k, yang menentukan seberapa besar lingkaran core distance yang digunakan untuk mengevaluasi hubungan antara titik data. Dengan memilih nilai k yang lebih besar, lebih banyak titik yang akan dianggap sebagai bagian dari klaster yang lebih besar, sedangkan dengan nilai k yang lebih kecil, klaster akan lebih padat dan hanya titik-titik yang sangat terhubung yang akan dianggap sebagai bagian dari klaster inti.

Gambar B

Selanjutnya, Pada Gambar B, dua lingkaran dengan warna yang berbeda masing-masing menggambarkan core distance dari titik yang dipilih ke dua set tetangga yang berbeda. Setiap titik dalam klaster memiliki nilai core distance yang dihitung berdasarkan seberapa jauh titik tersebut dari tetangga terdekatnya, dengan memperhitungkan jumlah tetangga yang ada dalam jarak tersebut. Dalam konteks HDBSCAN (Hierarchical DBSCAN), dua set tetangga ini menggambarkan bagaimana algoritma ini berfungsi untuk mengidentifikasi apakah suatu titik dapat menjadi bagian dari klaster inti atau tidak.

Dengan mengambil nilai core distance yang lebih besar, kita dapat memastikan bahwa lebih banyak titik yang dapat dianggap sebagai bagian dari klaster besar. Sebaliknya, jika nilai core distance yang lebih kecil dipilih, hanya titik yang sangat terhubung yang dapat dianggap sebagai bagian dari klaster inti, menciptakan klaster yang lebih padat.

Gambar C

Selanjutnya, pada Gambar C memperkenalkan konsep core distance, yang diukur sebagai jarak dari suatu titik data ke tetangga terdekatnya yang ke-6, dengan asumsi k=6. Lingkaran yang mengelilingi titik data tersebut menggambarkan core distance, yang menentukan batas seberapa jauh titik tersebut dapat terhubung dengan tetangganya untuk dapat dianggap sebagai core point dalam klaster. Titik yang memiliki lebih dari k−1 tetangga dalam jangkauan core distance-nya dapat dianggap sebagai bagian dari klaster inti. Namun, jika titik berada di luar lingkaran core distance dan tidak memiliki cukup tetangga dalam jangkauan tersebut, maka titik tersebut cenderung dianggap sebagai noise dan tidak relevan untuk membentuk klaster. Dalam gambar ini, kita dapat melihat hubungan langsung antara core distance dan keberadaan tetangga yang cukup untuk membentuk klaster.Dan pada Gambar F memperlihatkan situasi yang lebih kompleks di mana terdapat lebih banyak titik yang saling terhubung dan berada dalam jangkauan satu sama lain. Gambar ini menggambarkan bagaimana titik data yang lebih banyak dalam jangkauan core distance dapat membentuk klaster yang lebih padat, dengan lebih banyak titik yang dianggap sebagai bagian dari klaster inti. Titik yang tidak memiliki cukup tetangga dalam jangkauan core distance akan tetap dianggap sebagai noise. Dengan semakin banyak titik yang terhubung dalam jangkauan core distance, klaster yang terbentuk akan semakin kuat dan padat. Konsep ini menunjukkan bahwa klasterisasi bergantung pada interaksi antar titik yang memiliki cukup tetangga dalam jangkauan core distance untuk dianggap sebagai bagian dari klaster inti.

1. Kelemahan Mendasar DBSCAN

DBSCAN memerlukan penentuan dua parameter global: $ϵ$ (radius) dan $MinPts$ (jumlah minimum titik).

• Asumsi Kepadatan Tunggal: Penggunaan $ϵ$ sebagai ambang batas kepadatan yang seragam untuk seluruh dataset mengimplikasikan asumsi bahwa semua cluster memiliki kepadatan yang serupa.

• Ketidakmampuan Mengatasi Variasi Kepadatan: Dalam dataset yang kompleks, jika terdapat cluster yang sangat padat dan cluster yang lebih renggang, sulit untuk memilih $ϵ$ yang optimal.

  • $ϵ$ kecil $→$ Cluster renggang dianggap noise.

  • $ϵ$ besar $→$ Cluster padat digabungkan.

2. Solusi HDBSCAN: Transformasi Ruang dan Hirarki

HDBSCAN mengatasi keterbatasan ini melalui tiga langkah prosedural utama yang Anda sebutkan, yang semuanya berpusat pada dinamika kepadatan lokal:

2.1. Transformasi Ruang: Jarak Mutual Reachability

HDBSCAN memulai dengan mengubah metrik jarak menjadi Jarak Mutual Reachability ($dmreach​$).

• Jarak Core ($core_distancek​(p)$): Diukur sebagai jarak dari titik $p$ ke tetangga terdekat ke-$k$ ($k$ biasanya sama dengan $min_cluster_size$). Ini berfungsi sebagai estimasi kepadatan lokal di sekitar titik tersebut.

• Definisi dmreach​:

  dmreach​(a,b)=max(core_distancek​(a),core_distancek​(b),distance(a,b))

• Implikasi: Metrik ini secara efektif menjaga jarak antara titik-titik di wilayah padat (karena $core_distance$ kecil) dan memperbesar jarak antara titik-titik di wilayah jarang (karena $core_distance$ besar). Hal ini menyebabkan wilayah dengan kepadatan rendah "terdorong" menjauh dan diidentifikasi lebih mudah sebagai noise.

Gambar D

Pada Gambar D, diperkenalkan konsep mutual reachability distance, yang memberikan pendekatan berbeda dalam mengukur jarak antar titik data. Pada gambar ini, jarak antar titik merah dan hijau lebih besar dari core distance masing-masing, sehingga jarak yang digunakan untuk mengukur hubungan antar kedua titik tersebut adalah jarak aktual di antara keduanya, bukan sekadar core distance. Konsep mutual reachability distance ini berarti bahwa untuk dua titik yang jaraknya lebih besar dari core distance mereka, kita menggunakan jarak aktual di antara kedua titik tersebut untuk menilai apakah mereka dapat dianggap saling terhubung. Hal ini menjadi penting dalam penentuan hubungan antar titik yang lebih jauh dari core distance namun masih relevan untuk membentuk klaster.

2.2. Konstruksi Graf: Minimum Spanning Tree (MST)

Pada Gambar B, ditunjukkan struktur pohon merentang minimum (MST) yang dibangun menggunakan metrik jarak keterjangkauan mutual antara titik-titik data. Pohon ini merupakan bagian dari proses klasterisasi, yang digunakan untuk mengidentifikasi kelompok-kelompok padat dalam sebuah dataset.

Gambar E

• Titik Data sebagai Titik (Vertex): Setiap node atau titik pada gambar menggambarkan sebuah titik data dalam dataset. Titik-titik ini berfungsi sebagai vertex dalam graf.

• Mutual reachability distance: Garis-garis yang menghubungkan titik-titik tersebut mewakili sisi yang menghubungkan dua titik data. Bobot dari sisi tersebut ditentukan oleh jarak keterjangkauan mutual antara kedua titik yang dihubungkannya. Gradasi warna yang ditampilkan pada gambar (dari ungu ke kuning) menunjukkan nilai jarak, di mana warna ungu menggambarkan jarak yang lebih pendek, sedangkan warna kuning menggambarkan jarak yang lebih panjang.

• Minimum Spanning Tree (MST): Diagram ini menunjukkan pohon merentang minimum dari graf yang terhubung, yaitu sekumpulan sisi yang menghubungkan seluruh vertex tanpa membentuk siklus dan dengan total bobot sisi terkecil. Pohon ini dibangun menggunakan algoritma Prim, yang secara efisien menambahkan sisi dengan bobot terendah untuk menghubungkan vertex yang belum terhubung. MST ini memainkan peran penting dalam mengidentifikasi klaster dengan menghubungkan titik data berdasarkan jarak keterjangkauan mutual mereka.

• Thresholding dan Pemisahan Komponen: Dengan menurunkan nilai ambang batas (threshold) secara bertahap, sisi-sisi yang memiliki bobot lebih besar dari ambang tersebut akan dihapus, yang menyebabkan graf terpecah menjadi beberapa komponen terhubung. Proses ini menghasilkan hierarki komponen terhubung yang dapat dievaluasi pada berbagai tingkat ambang batas. Penggunaan MST membantu mengurangi jumlah sisi yang perlu dihitung untuk memisahkan komponen-komponen tersebut.

Secara keseluruhan, Gambar E tersebut menggambarkan Minimum Spanning Tree yang dibangun berdasarkan metrik jarak keterjangkauan mutual, yang berbeda dari jarak biasa dalam graf. Pohon ini digunakan untuk memetakan hubungan antar titik data dan memisahkan daerah-daerah padat dalam dataset untuk tujuan klasterisasi.

2.3. Hirarki dan Stabilitas Cluster (Excess of Mass)

• Pembentukan Hirarki: MST dikonversi menjadi struktur hirarki (dendrogram) dengan secara berturut-turut "memecah" sisi-sisi, dimulai dari bobot terbesar ke terkecil. Pemecahan ini menunjukkan bagaimana cluster terpisah atau bergabung seiring dengan perubahan tingkat kepadatan (atau seiring $λ=1/jarak$ berubah).

• Ekstraksi Cluster Stabil: Daripada memilih ambang batas pada hirarki (seperti pada linkage clustering tradisional), HDBSCAN menggunakan kriteria Excess of Mass (EOM) untuk menentukan cluster terbaik.

  • Setiap cluster dalam hirarki diberi skor Persistence (Stabilitas), yang diukur dari rentang perubahan $λ$ di mana cluster tersebut tetap eksis dan terpisah.

  • Cluster final yang diekstrak adalah yang memiliki skor stabilitas lebih tinggi dibandingkan sub-cluster turunannya.

HDBSCAN adalah algoritma klasterisasi berbasis kepadatan yang menggabungkan keuntungan dari DBSCAN dan klasterisasi hierarkis. Dengan menggunakan mutual reachability distance, HDBSCAN memungkinkan penanganan klaster dengan kepadatan yang sangat bervariasi tanpa memerlukan penyetelan parameter radius yang sulit, serta dapat mengidentifikasi dan menangani noise atau outlier dengan lebih baik. Konsep hierarchical clustering yang diterapkan dalam HDBSCAN membuatnya sangat cocok untuk dataset yang memiliki struktur klaster yang kompleks dan beragam.