Algoritme Pengelompokan - Ringkasan
Pengantar Clustering
Metode pengelompokan adalah salah satu metode ML tanpa pengawasan yang paling berguna. Metode-metode tersebut digunakan untuk mencari kesamaan serta pola hubungan antar sampel data dan kemudian mengelompokkan sampel tersebut ke dalam kelompok-kelompok yang memiliki kesamaan berdasarkan fitur.
Pengelompokan penting karena menentukan pengelompokan intrinsik di antara data tak berlabel saat ini. Mereka pada dasarnya membuat beberapa asumsi tentang titik data untuk membentuk kesamaan mereka. Setiap asumsi akan membangun cluster yang berbeda tetapi sama validnya.
Sebagai contoh, di bawah ini adalah diagram yang menunjukkan sistem pengelompokan yang dikelompokkan bersama jenis data yang serupa dalam kluster yang berbeda -
Metode Pembentukan Cluster
Cluster tidak perlu dibentuk dalam bentuk bola. Berikut ini adalah beberapa metode pembentukan cluster lainnya -
Berbasis kepadatan
Dalam metode ini, cluster dibentuk sebagai kawasan padat. Keuntungan dari metode ini adalah memiliki akurasi yang baik serta kemampuan yang baik untuk menggabungkan dua cluster. Ex. Pengelompokan Spasial Berbasis Kepadatan dari Aplikasi dengan Kebisingan (DBSCAN), Titik Pemesanan untuk mengidentifikasi struktur Pengelompokan (OPTICS), dll.
Berbasis hierarki
Dalam metode ini, cluster dibentuk sebagai struktur tipe pohon berdasarkan hierarki. Mereka memiliki dua kategori yaitu, Agglomerative (Pendekatan Bottom up) dan Divisive (Pendekatan Top down). Ex. Clustering menggunakan Representatives (CURE), Balanced iterative Reducing Clustering using Hierarchies (BIRCH) dll.
Mempartisi
Dalam metode ini, cluster dibentuk dengan membagi objek menjadi cluster k. Jumlah cluster akan sama dengan jumlah partisi. Ex. K-means, Mengelompokkan Aplikasi Besar berdasarkan Pencarian Acak (CLARANS).
Kotak
Dalam metode ini, cluster dibentuk sebagai struktur seperti grid. Keuntungan dari metode ini adalah bahwa semua operasi pengelompokan yang dilakukan pada kisi ini cepat dan tidak bergantung pada jumlah objek data. Ex. Kisi Informasi Statistik (STING), Pengelompokan dalam Pencarian (KLIQUE).
Mengukur Kinerja Clustering
Salah satu pertimbangan terpenting terkait model ML adalah menilai performanya atau kualitas modelnya. Dalam kasus algoritme pembelajaran yang diawasi, menilai kualitas model kami mudah karena kami sudah memiliki label untuk setiap contoh.
Di sisi lain, dalam kasus algoritma pembelajaran tanpa pengawasan, kami tidak begitu diberkati karena kami menangani data yang tidak berlabel. Namun kami masih memiliki beberapa metrik yang memberikan pemahaman kepada praktisi tentang terjadinya perubahan dalam kluster yang bergantung pada algoritme.
Sebelum kita mendalami metrik tersebut, kita harus memahami bahwa metrik ini hanya mengevaluasi kinerja komparatif model satu sama lain daripada mengukur validitas prediksi model. Berikut adalah beberapa metrik yang dapat kita terapkan pada algoritma clustering untuk mengukur kualitas model -
Analisis Siluet
Analisis siluet digunakan untuk memeriksa kualitas model clustering dengan mengukur jarak antar cluster. Ini pada dasarnya memberi kita cara untuk menilai parameter seperti jumlah cluster dengan bantuanSilhouette score. Skor ini mengukur seberapa dekat setiap titik dalam satu kluster dengan titik-titik di kluster tetangga.
Analisis Skor Silhouette
Kisaran skor Silhouette adalah [-1, 1]. Analisisnya adalah sebagai berikut -
+1 Score - Dekat +1 Silhouette score menunjukkan bahwa sampel berada jauh dari cluster tetangganya.
0 Score - 0 Silhouette score menunjukkan bahwa sampel berada pada atau sangat dekat dengan batas keputusan yang memisahkan dua cluster yang bertetangga.
-1 Score & minusl -1 Silhouette score menunjukkan bahwa sampel telah ditetapkan ke cluster yang salah.
Perhitungan skor Silhouette dapat dilakukan dengan menggunakan rumus berikut -
= (-) / (,)
Di sini, = jarak rata-rata ke titik-titik di cluster terdekat
Dan, = rata-rata jarak intra-cluster ke semua titik.
Indeks Davis-Bouldin
Indeks DB adalah metrik bagus lainnya untuk melakukan analisis algoritme pengelompokan. Dengan bantuan indeks DB, kita dapat memahami poin-poin berikut tentang model pengelompokan -
Cuaca cluster berjarak baik satu sama lain atau tidak?
Seberapa padat cluster tersebut?
Kami dapat menghitung indeks DB dengan bantuan rumus berikut -
$$ DB = \ frac {1} {n} \ displaystyle \ sum \ limit_ {i = 1} ^ n maks_ {j \ neq {i}} \ kiri (\ frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ kanan) $$Di sini, = jumlah cluster
σ i = jarak rata-rata semua titik dalam cluster dari pusat cluster.
Semakin sedikit indeks DB, semakin baik model pengelompokannya.
Indeks Dunn
Ini berfungsi sama seperti indeks DB tetapi ada poin berikut di mana keduanya berbeda -
Indeks Dunn hanya memperhitungkan kasus terburuk yaitu cluster yang berdekatan sedangkan indeks DB mempertimbangkan dispersi dan pemisahan semua cluster dalam model clustering.
Indeks Dunn meningkat seiring dengan peningkatan kinerja sementara indeks DB menjadi lebih baik ketika kluster memiliki jarak yang baik dan padat.
Kami dapat menghitung indeks Dunn dengan bantuan rumus berikut -
$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$Di sini, ,, = setiap indeks untuk cluster
= jarak antar cluster
q = jarak intra-cluster
Jenis Algoritme Pengelompokan ML
Berikut ini adalah algoritme pengelompokan ML yang paling penting dan berguna -
Pengelompokan K-means
Algoritme pengelompokan ini menghitung sentroid dan melakukan iterasi hingga kami menemukan sentroid yang optimal. Ini mengasumsikan bahwa jumlah cluster sudah diketahui. Ini juga disebut algoritma pengelompokan datar. Jumlah cluster yang diidentifikasi dari data oleh algoritma diwakili oleh 'K' dalam K-means.
Algoritma Mean-Shift
Ini adalah algoritma pengelompokan kuat lainnya yang digunakan dalam pembelajaran tanpa pengawasan. Tidak seperti pengelompokan K-means, ia tidak membuat asumsi apa pun sehingga ini adalah algoritme non-parametrik.
Pengelompokan Hierarki
Ini adalah algoritma pembelajaran tanpa pengawasan lain yang digunakan untuk mengelompokkan bersama titik data tak berlabel yang memiliki karakteristik serupa.
Kami akan membahas semua algoritma ini secara rinci di bab-bab selanjutnya.
Aplikasi Clustering
Kami dapat menemukan pengelompokan berguna di area berikut -
Data summarization and compression- Pengelompokan banyak digunakan di area di mana kami memerlukan peringkasan, kompresi, dan pengurangan data juga. Contohnya adalah pemrosesan gambar dan kuantisasi vektor.
Collaborative systems and customer segmentation - Karena pengelompokan dapat digunakan untuk menemukan produk yang serupa atau jenis pengguna yang sama, pengelompokan dapat digunakan di area sistem kolaboratif dan segmentasi pelanggan.
Serve as a key intermediate step for other data mining tasks- Analisis cluster dapat menghasilkan ringkasan data yang ringkas untuk klasifikasi, pengujian, pembuatan hipotesis; karenanya, ini berfungsi sebagai langkah perantara utama untuk tugas data mining lainnya juga.
Trend detection in dynamic data - Clustering juga dapat digunakan untuk deteksi tren dalam data dinamis dengan membuat berbagai cluster tren serupa.
Social network analysis- Clustering dapat digunakan dalam analisis jaringan sosial. Contohnya menghasilkan urutan dalam gambar, video atau audio.
Biological data analysis - Clustering juga dapat digunakan untuk membuat cluster gambar, video sehingga berhasil digunakan dalam analisis data biologis.