Memilih metode pengelompokan

Ketika menggunakan analisis klaster pada kumpulan data untuk mengelompokkan kasus-kasus serupa, seseorang perlu memilih di antara sejumlah besar metode pengelompokan dan ukuran jarak. Terkadang, satu pilihan mungkin memengaruhi yang lain, tetapi ada banyak kemungkinan kombinasi metode.

Apakah ada yang punya rekomendasi tentang bagaimana memilih di antara berbagai algoritma / metode dan pengukuran jarak ? Bagaimana ini terkait dengan sifat variabel (misalnya, kategorikal atau numerik) dan masalah pengelompokan? Apakah ada teknik yang optimal?

Tidak ada jawaban pasti untuk pertanyaan Anda, karena bahkan dalam metode yang sama pilihan jarak untuk mewakili individu (dis) kesamaan dapat menghasilkan hasil yang berbeda, misalnya ketika menggunakan euclidean vs kuadrat euclidean dalam pengelompokan hierarkis. Sebagai contoh lain, untuk data biner, Anda dapat memilih indeks Jaccard sebagai ukuran kesamaan dan melanjutkan dengan pengelompokan hierarki klasik; tetapi ada pendekatan alternatif, seperti Mona ( Analisis Monothetic) algoritma yang hanya mempertimbangkan satu variabel pada satu waktu, sedangkan pendekatan hierarkis lainnya (misalnya HC klasik, Agnes, Diana) menggunakan semua variabel pada setiap langkah. Pendekatan k-means telah diperluas dengan berbagai cara, termasuk mempartisi sekitar medoid (PAM) atau objek yang representatif daripada centroid (Kaufman dan Rousseuw, 1990), atau fuzzy clustering (Chung dan Lee, 1992). Sebagai contoh, perbedaan utama antara k-means dan PAM adalah bahwa PAM meminimalkan jumlah ketidaksamaan daripada jumlah jarak euclidean kuadrat; fuzzy clustering memungkinkan untuk mempertimbangkan "keanggotaan parsial" (kami mengaitkan setiap observasi dengan bobot yang mencerminkan keanggotaan kelas). Dan untuk metode yang mengandalkan kerangka kerja probabilistik, atau yang disebut model-based clustering (atau analisis profil latenuntuk para psikometri), ada paket bagus: Mclust . Jadi secara definitif, Anda perlu mempertimbangkan bagaimana mendefinisikan kemiripan individu serta metode untuk menghubungkan individu bersama (pengelompokan rekursif atau berulang, keanggotaan kelas yang ketat atau tidak jelas, pendekatan tanpa pengawasan atau semi-diawasi, dll.).

Biasanya, untuk menilai stabilitas cluster, menarik untuk membandingkan beberapa algoritma yang pada dasarnya "berbagi" beberapa kesamaan (misalnya k-means dan hierarchical clustering, karena jarak euclidean berfungsi untuk keduanya). Untuk menilai kesesuaian antara dua solusi klaster, beberapa petunjuk disarankan dalam menanggapi pertanyaan ini, Di mana harus memotong dendrogram? (lihat juga referensi silang untuk tautan lain di situs web ini). Jika Anda menggunakan R, Anda akan melihat bahwa beberapa paket sudah tersedia di Tampilan Tugas tentang Analisis Cluster, dan beberapa paket termasuk sketsa yang menjelaskan metode tertentu atau memberikan studi kasus.

Analisis Cluster: Konsep Dasar dan Algoritma memberikan gambaran yang baik tentang beberapa teknik yang digunakan dalam Analisis Cluster. Adapun buku baru yang bagus dengan ilustrasi R, saya akan merekomendasikan bab 12 dari Izenman, Teknik Statistik Multivariat Modern (Springer, 2008). Beberapa referensi standar lainnya diberikan di bawah ini:

• Cormack, R., 1971. Tinjauan klasifikasi. Jurnal Masyarakat Statistik Kerajaan, A 134, 321-367.
• Everitt, B., 1974. Analisis cluster . London: Heinemann Educ. Buku.
• Gordon, A., 1987. Tinjauan klasifikasi hierarkis. Jurnal Royal Statistics Society, A 150, 119–137.
• Gordon, A., 1999. Klasifikasi , Edisi ke-2. Chapman dan Hall.
• Kaufman, L., Rousseuw, P., 1990. Menemukan Grup dalam Data: Pengantar Analisis Cluster . New York, Wiley.

Kutipan dari Hastie, Tibshirani dan Friedman, Elements of Statistics Learning , hal. 506:

"Ukuran ketidaksamaan yang tepat jauh lebih penting dalam memperoleh kesuksesan dengan pengelompokan daripada pilihan algoritma pengelompokan. Aspek masalah ini ... tergantung pada pengetahuan khusus domain dan kurang dapat diterima untuk penelitian umum."

(Yang mengatakan, bukankah akan menyenangkan jika (wibni) ada situs di mana siswa dapat mencoba beberapa algoritma dan metrik pada beberapa dataset standar kecil?)

Anda tidak dapat mengetahui terlebih dahulu algoritma pengelompokan mana yang lebih baik, tetapi ada beberapa petunjuk, misalnya jika Anda ingin mengelompokkan gambar ada algoritma tertentu yang harus Anda coba terlebih dahulu seperti Fuzzy Art, atau jika Anda ingin mengelompokkan wajah Anda harus mulai dengan (GGCI) pengelompokan geometris global untuk gambar.

Pokoknya ini tidak menjamin hasil terbaik, jadi apa yang akan saya lakukan adalah menggunakan program yang memungkinkan Anda untuk menjalankan algoritma cluster yang berbeda, seperti weka, RapidMiner atau bahkan R (yang bukan visual), Di sana saya akan mengatur program untuk luncurkan semua algoritma pengelompokan berbeda yang saya bisa, dengan semua jarak yang mungkin berbeda, dan jika mereka membutuhkan parameter, bereksperimenlah masing-masing dengan berbagai nilai parameter yang berbeda (selain itu jika saya tidak tahu jumlah cluster, jalankan masing-masing dengan berbagai jumlah itu). Setelah Anda menyelesaikan percobaan, biarkan tetap berjalan, tetapi ingat untuk menyimpan di suatu tempat hasil dari setiap pengelompokan berjalan.

Kemudian bandingkan hasilnya untuk mendapatkan pengelompokan yang dihasilkan terbaik. Ini rumit karena ada beberapa metrik yang dapat Anda bandingkan dan tidak semua disediakan oleh setiap algoritma. Misalnya algoritma cluster fuzzy memiliki metrik yang berbeda dari non-fuzzy, tetapi mereka masih dapat dibandingkan dengan mempertimbangkan kelompok yang dihasilkan fuzzy sebagai non-fuzzy, saya akan tetap menggunakan perbandingan dengan metrik klasik seperti:

• SSE: jumlah kesalahan kuadrat dari item setiap cluster.

• Jarak antar kluster: jumlah jarak kuadrat antara setiap sentroid kluster.

• Jarak intra cluster untuk setiap cluster: jumlah jarak kuadrat dari item masing-masing cluster ke pusat massa.

• Radius Maksimum: jarak terbesar dari sebuah instance ke centroid clusternya.

• Radius Rata-Rata: jumlah jarak terbesar dari instance ke centroid klusternya dibagi dengan jumlah cluster.

Memilih jarak yang tepat bukanlah tugas dasar. Ketika kita ingin membuat analisis kluster pada kumpulan data, hasil yang berbeda dapat muncul dengan menggunakan jarak yang berbeda, jadi sangat penting untuk berhati-hati dalam memilih jarak mana karena kita dapat membuat artefak palsu yang bagus yang menangkap dengan baik variabilitas, tetapi sebenarnya tanpa merasakan masalah kita.

The jarak Euclidean adalah tepat ketika saya memiliki variabel numerik terus menerus dan saya ingin merefleksikan jarak mutlak. Jarak ini memperhitungkan setiap variabel dan tidak menghapus redudansi, jadi jika saya memiliki tiga variabel yang menjelaskan hal yang sama (berkorelasi), saya akan menimbang efek ini dengan tiga. Selain itu, jarak ini bukan skala invarian, jadi umumnya saya harus skala sebelumnya untuk menggunakan jarak tersebut.
Contoh ekologi: Kami memiliki pengamatan berbeda dari banyak daerah, di mana para ahli telah mengambil sampel dari beberapa faktor mikrobiologis, fisik dan kimia. Kami ingin menemukan pola dalam ekosistem. Faktor-faktor ini memiliki korelasi tinggi, tetapi kami tahu semua orang relevan, jadi kami tidak ingin menghapus redudansi ini. Kami menggunakan jarak Euclidean dengan data yang diskalakan untuk menghindari efek unit.

The Mahalanobis jarak yang tepat ketika saya memiliki variabel numerik terus menerus dan saya ingin merefleksikan jarak mutlak, tapi kami ingin menghilangkan redudansi. Jika kita memiliki variabel berulang, efek berulangnya akan menghilang.

Keluarga Hellinger , Profil Spesies dan jarak Chord sesuai ketika kita ingin menekankan perbedaan antara variabel, ketika kita ingin membedakan profil. Jarak-jarak ini berbobot dengan jumlah total dari setiap pengamatan, sedemikian rupa sehingga jaraknya kecil ketika variabel demi variabel individu lebih mirip, meskipun dalam besaran absolut sangat berbeda. Awas! Jarak ini mencerminkan perbedaan profil dengan sangat baik, tetapi kehilangan efek besarnya. Mereka bisa sangat berguna ketika kita memiliki ukuran sampel yang berbeda. Contoh ekologi: Kami ingin mempelajari fauna dari banyak tanah dan kami memiliki matriks data inventarisasi gastropoda (lokasi pengambilan sampel dalam baris dan nama spesies dalam kolom). Matriks ini ditandai dengan memiliki banyak nol dan besaran yang berbeda karena beberapa lokasi memiliki beberapa spesies dan yang lainnya memiliki spesies lain. Kita bisa menggunakan jarak Hellinger.

Bray-Curtis sangat mirip, tetapi lebih tepat ketika kita ingin membedakan profil dan juga mempertimbangkan besaran relatif.

Sejauh yang saya ketahui, jika Anda menginginkan pilihan yang aman, metode pengelompokan spektral telah mencapai tingkat akurasi tertinggi dalam beberapa tahun terakhir - setidaknya dalam pengelompokan gambar.

Adapun metrik jarak, itu sangat tergantung pada bagaimana data Anda diatur. Pilihan yang aman adalah jarak euclidean sederhana tetapi jika Anda tahu data Anda berisi manifold, Anda harus memetakan titik-titik melalui metode kernel.

PS: semuanya terkait dengan nilai numerik, bukan kategoris. Saya tidak yakin bagaimana cara mengelompokkan data kategori.

Berikut ini adalah ringkasan dari beberapa algoritma pengelompokan yang dapat membantu menjawab pertanyaan

"Teknik pengelompokan mana yang harus saya gunakan?"

Tidak ada algoritma pengelompokan yang objektif "benar" Ref

Algoritma cluster dapat dikategorikan berdasarkan "model cluster" mereka. Algoritma yang dirancang untuk jenis model tertentu umumnya akan gagal pada model yang berbeda. Untuk misalnya, k-means tidak dapat menemukan kelompok non-cembung, ia hanya dapat menemukan kelompok berbentuk lingkaran.

Oleh karena itu, memahami "model klaster" ini menjadi kunci untuk memahami bagaimana memilih di antara berbagai algoritma / metode pengelompokan. Model kluster yang umum meliputi:

[1] Model konektivitas: Membangun model berdasarkan konektivitas jarak. Misalnya pengelompokan hierarkis. Digunakan ketika kita membutuhkan partisi yang berbeda berdasarkan ketinggian pohon. Fungsi R: paket hclust dalam statistik.

[2] Model Centroid: Membuat model dengan merepresentasikan setiap klaster dengan vektor rata-rata tunggal. Digunakan ketika kita membutuhkan partisi yang tajam (bukan fuzzy clustering yang dijelaskan nanti). Fungsi R: km artinya dalam paket statistik.

[3] Model distribusi: Membangun model berdasarkan distribusi statistik seperti distribusi normal multivarian yang digunakan oleh algoritma maksimisasi-harapan. Digunakan ketika bentuk-bentuk cluster dapat berubah-ubah tidak seperti k-means yang mengasumsikan cluster bundar. Fungsi R: emcluster dalam paket emcluster.

[4] Model kepadatan: Membangun model berdasarkan kelompok sebagai wilayah padat yang terhubung dalam ruang data. Misalnya DBSCAN dan OPTICS. Digunakan ketika bentuk-bentuk cluster dapat berubah-ubah tidak seperti k-means yang mengasumsikan cluster bundar .. Fungsi R dbscan dalam paket dbscan.

[5] Model ruang bagian: Membangun model berdasarkan anggota cluster dan atribut yang relevan. Misalnya biclustering (juga dikenal sebagai co-clustering atau two-mode-clustering). Digunakan saat pengelompokan baris dan kolom secara simultan diperlukan. Fungsi R biclust dalam paket biclust.

[6] Model grup: Membuat model berdasarkan informasi pengelompokan. Misalnya pemfilteran kolaboratif (algoritme rekomendasi). Fungsi R Recommender dalam paket recommenderlab.

[7] Model berbasis grafik: Membuat model berdasarkan klik. Algoritma pendeteksian struktur komunitas mencoba menemukan subgraph padat dalam grafik langsung atau tidak langsung. Misalnya fungsi R cluster_walktrap dalam paket igraph.

[8] Kohonen Self-Organizing Feature Map: Membangun model berdasarkan jaringan saraf. Fungsi R som dalam paket kohonen.

[9] Spectral Clustering: Membangun model berdasarkan struktur kluster non-cembung, atau ketika ukuran pusat bukan deskripsi yang sesuai dari kluster lengkap. Specc fungsi R dalam paket kernlab.

[10] pengelompokan ruang bagian: Untuk data dimensi tinggi, fungsi jarak bisa menjadi masalah. model kluster menyertakan atribut yang relevan untuk klaster. Misal, fungsi hddc dalam paket R HDclassif.

[11] Pengelompokan urutan: Sekuens grup yang terkait. Paket terakhir.

[12] Perambatan afinitas: Membangun model berdasarkan pesan yang lewat di antara titik data. Itu tidak memerlukan jumlah cluster yang harus ditentukan sebelum menjalankan algoritma. Lebih baik untuk visi komputer dan tugas-tugas biologi komputasi tertentu, misalnya mengelompokkan gambar wajah manusia dan mengidentifikasi transkrip yang diatur, daripada k-means, Ref Rpackage APCluster.

[13] Pengelompokan aliran: Membuat model berdasarkan data yang tiba terus menerus seperti catatan telepon, transaksi keuangan, dll. Misalnya paket R BIRCH [ https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Pengelompokan dokumen (atau pengelompokan teks): Membuat model berdasarkan SVD. Ini telah digunakan dalam ekstraksi topik. Misalnya Carrot [ http://search.carrot2.org] adalah mesin pencarian hasil pencarian open source yang dapat mengelompokkan dokumen ke dalam kategori tematik.

[15] Model kelas laten: Ini menghubungkan satu set variabel multivariat yang diamati dengan satu set variabel laten. LCA dapat digunakan dalam penyaringan kolaboratif. Function R Recommender dalam paket recommenderlab memiliki fungsionalitas filtering kolaboratif.

[16] Biclustering: Digunakan untuk secara bersamaan mengelompokkan baris dan kolom data dua mode. Misalnya fungsi R biclust dalam paket biclust.

[17] Soft clustering (fuzzy clustering): Setiap objek milik masing-masing cluster hingga tingkat tertentu. Misalnya fungsi R Fclust dalam paket fclust.