Bagaimana cara mengetahui apakah data "berkerumun" cukup untuk algoritma pengelompokan untuk menghasilkan hasil yang bermakna?

Bagaimana Anda tahu jika data Anda (dimensi tinggi) menunjukkan pengelompokan yang cukup sehingga hasil dari kmeans atau algoritma pengelompokan lainnya benar-benar bermakna?

Khususnya untuk algoritma k-means, berapa banyak pengurangan dalam varians dalam-cluster yang seharusnya ada untuk hasil clustering aktual menjadi bermakna (dan tidak palsu)?

Haruskah pengelompokan terlihat ketika bentuk data yang direduksi secara dimensi diplot, dan apakah hasil dari kmeans (atau metode lain) menjadi tidak berarti jika pengelompokan tidak dapat divisualisasikan?

Tentang k-means secara khusus, Anda dapat menggunakan statistik Gap. Pada dasarnya, idenya adalah untuk menghitung kebaikan ukuran pengelompokan berdasarkan dispersi rata-rata dibandingkan dengan distribusi referensi untuk peningkatan jumlah cluster. Informasi lebih lanjut dapat ditemukan di koran asli:

Tibshirani, R., Walther, G., dan Hastie, T. (2001). Memperkirakan jumlah cluster dalam satu set data melalui statistik gap . Statistik JR. Soc. B, 63 (2): 411-423.

Jawaban yang saya berikan untuk pertanyaan terkait menyoroti indeks validitas umum lainnya yang dapat digunakan untuk memeriksa apakah dataset yang diberikan menunjukkan semacam struktur.

Ketika Anda tidak tahu apa yang Anda harapkan untuk menemukan jika hanya ada kebisingan, pendekatan yang baik adalah dengan menggunakan resampling dan mempelajari stabilitas cluster. Dengan kata lain, sampel ulang data Anda (melalui bootstrap atau dengan menambahkan noise kecil ke dalamnya) dan hitung "kedekatan" dari partisi yang dihasilkan, yang diukur dengan kesamaan Jaccard . Singkatnya, ini memungkinkan untuk memperkirakan frekuensi cluster yang sama ditemukan dalam data. Metode ini sudah tersedia dalam paket fpc R sebagai clusterboot(). Dibutuhkan sebagai input data mentah atau matriks jarak, dan memungkinkan untuk menerapkan berbagai metode pengelompokan (hierarkis, k-cara, metode fuzzy). Metode ini dibahas dalam referensi terkait:

Hennig, C. (2007) Penilaian klaster untuk stabilitas cluster . Statistik Komputasi dan Analisis Data , 52, 258-271.

Hennig, C. (2008) Titik disolusi dan ketahanan isolasi: kriteria ketahanan untuk metode analisis kluster umum . Jurnal Analisis Multivariat , 99, 1154-1176.

Di bawah ini adalah demonstrasi kecil dengan algoritma k-means.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Hasilnya cukup positif dalam dataset buatan (dan terstruktur dengan baik) ini karena tidak satu pun dari tiga cluster ( krange) yang dilarutkan di seluruh sampel, dan rata-rata kesamaan Jaccard clusterwise adalah> 0,95 untuk semua cluster.

Di bawah ini adalah hasil dari 20 sampel bootstrap. Seperti dapat dilihat, unit statistik cenderung untuk tetap dikelompokkan ke dalam kelompok yang sama, dengan beberapa pengecualian untuk pengamatan yang berada di antaranya.

Anda dapat memperluas gagasan ini ke indeks validitas apa pun, tentu saja: pilih seri pengamatan baru dengan bootstrap (dengan penggantian), hitung statistik Anda (mis., Lebar siluet, korelasi cophenetic, gamma Hubert, dalam jumlah kuadrat) untuk rentang nomor kluster (mis. 2 hingga 10), ulangi 100 atau 500 kali, dan lihat boks kotak statistik Anda sebagai fungsi dari jumlah kluster.

Inilah yang saya dapatkan dengan dataset simulasi yang sama, tetapi menggunakan clustering hierarkis Ward dan mempertimbangkan korelasi cophenetic (yang menilai seberapa baik informasi jarak direproduksi dalam partisi yang dihasilkan) dan lebar siluet (ukuran kombinasi menilai homogenitas intra-cluster dan inter- pemisahan cluster).

Korelasi cophenetic berkisar dari 0,6267 hingga 0,7511 dengan nilai median 0,7031 (500 sampel bootstrap). Lebar siluet tampak maksimal ketika kita mempertimbangkan 3 cluster (median 0,8408, kisaran 0,7371-0,8769).

Salah satu cara untuk dengan cepat memvisualisasikan apakah data dimensi tinggi menunjukkan pengelompokan yang cukup adalah dengan menggunakan t-Distributed Stochastic Neighbor Embedding ( t-SNE ). Ini memproyeksikan data ke beberapa ruang dimensi rendah (misalnya 2D, 3D) dan melakukan pekerjaan yang cukup baik dalam menjaga struktur cluster jika ada.

Misalnya kumpulan data MNIST :

Olivetti menghadapi kumpulan data:

Tentunya, kemampuan untuk secara visual membedakan cluster dalam jumlah dimensi plotable adalah kriteria yang diragukan untuk kegunaan dari algoritma clustering, terutama jika pengurangan dimensi ini dilakukan secara independen dari clustering itu sendiri (yaitu: dalam upaya sia-sia untuk mengetahui apakah clustering akan bekerja).

Bahkan, metode pengelompokan memiliki nilai tertinggi dalam menemukan cluster di mana mata / pikiran manusia tidak dapat melihat cluster.

Jawaban sederhananya adalah: lakukan pengelompokan, kemudian cari tahu apakah itu berhasil (dengan salah satu kriteria yang Anda minati, lihat juga jawaban @ Jeff).

Kapan hasilnya bermakna ? Khususnya hasil k-means?

Faktanya adalah k-means mengoptimalkan statistik matematika tertentu. Tidak ada "bermakna" yang terkait dengan ini.

Khususnya dalam data dimensi tinggi, pertanyaan pertama adalah: apakah jarak Euclidean masih bermakna ? Jika tidak, jangan gunakan k-means. Jarak Euclidean bermakna di dunia fisik, tetapi dengan cepat kehilangan makna ketika Anda memiliki data lain. Secara khusus, ketika Anda mengubah data menjadi ruang vektor secara artifisial, adakah alasan mengapa Euclidean itu?

Jika Anda mengambil kumpulan data "lama setia" klasik dan menjalankan k-means di atasnya tanpa normalisasi, tetapi dengan jarak Euclidean murni, itu sudah tidak lagi berarti. EM, yang notabene menggunakan beberapa bentuk "cluster local" Mahalanobis distance, akan bekerja jauh lebih baik. Secara khusus, ini beradaptasi dengan sumbu yang memiliki skala yang sangat berbeda.

Btw, kekuatan utama dari k-means adalah ia akan benar-benar selalu memartisi data, tidak peduli seperti apa bentuknya. Anda dapat menggunakan k-cara untuk partisi kebisingan seragam ke dalam cluster k . Orang dapat mengklaim bahwa jelas, k-means cluster tidak bermakna. Atau orang dapat menerima ini sebagai: pengguna ingin mempartisi data untuk meminimalkan jarak Euclidean kuadrat, tanpa memiliki persyaratan cluster menjadi "bermakna".

Saya baru saja mulai menggunakan algoritma pengelompokan baru-baru ini, jadi semoga seseorang yang lebih berpengetahuan dapat memberikan jawaban yang lebih lengkap, tetapi berikut adalah beberapa pemikiran:

'Bermakna', seperti yang saya yakin Anda tahu, sangat subjektif. Jadi apakah pengelompokan itu cukup baik sepenuhnya tergantung pada mengapa Anda perlu mengelompokkannya sejak awal. Jika Anda mencoba memprediksi keanggotaan grup, kemungkinan pengelompokan apa pun akan lebih baik daripada kebetulan (dan tidak lebih buruk), sehingga hasilnya harus bermakna sampai batas tertentu.

Jika Anda ingin tahu seberapa dapat diandalkannya pengelompokan ini, Anda perlu beberapa metrik untuk membandingkannya. Jika Anda memiliki seperangkat entitas dengan keanggotaan yang dikenal, Anda dapat menggunakan analisis diskriminan untuk melihat seberapa bagus prediksi itu. Jika Anda tidak memiliki seperangkat entitas dengan keanggotaan yang dikenal, Anda harus mengetahui varian apa yang biasanya dimiliki cluster di bidang Anda. Atribut fisik entitas dengan kategori kaku cenderung memiliki varians dalam-kelompok yang jauh lebih rendah daripada data psikometrik pada manusia, tetapi itu tidak selalu membuat pengelompokan 'lebih buruk'.

Pertanyaan kedua Anda mengacu pada 'Nilai k apa yang harus saya pilih?' Sekali lagi, tidak ada jawaban sulit di sini. Dengan tidak adanya set apriori kategori, Anda mungkin ingin meminimalkan jumlah cluster sementara juga meminimalkan varians cluster rata-rata. Pendekatan sederhana mungkin untuk memplot 'jumlah cluster' vs 'varians cluster rata-rata', dan mencari "siku" - di mana menambahkan lebih banyak cluster tidak memiliki dampak signifikan pada varians cluster Anda.

Saya tidak akan mengatakan hasil dari k-means tidak ada artinya jika tidak dapat divisualisasikan, tetapi tentu saja menarik ketika kluster terlihat secara visual. Ini, sekali lagi, hanya mengarah kembali ke pertanyaan: mengapa Anda perlu melakukan pengelompokan, dan seberapa andal yang Anda butuhkan? Pada akhirnya, ini adalah pertanyaan yang harus Anda jawab berdasarkan pada bagaimana Anda akan menggunakan data.

Untuk mengetahui apakah sebuah clustering bermakna, Anda dapat menjalankan algoritma untuk menghitung jumlah cluster, dan melihat apakah cluster menghasilkan sesuatu yang lebih besar dari 1.

Seperti kata chl, satu algoritma penghitungan cluster adalah algoritma statistik gap. Secara kasar, ini menghitung varians kluster total yang diberikan data aktual Anda, dan membandingkannya dengan varians kluster total data yang seharusnya tidak memiliki kluster sama sekali (misalnya, kumpulan data yang dibentuk dengan pengambilan sampel secara seragam dalam batas yang sama dengan data aktual Anda). Jumlah cluster kemudian dipilih menjadi yang memberikan "celah" terbesar antara dua varian klaster ini.$k$$k$

Algoritma lain adalah algoritma kekuatan prediksi (yang mirip dengan sisa jawaban chl). Secara kasar, ini melakukan banyak pengelompokan k-means, dan menghitung proporsi titik yang tinggal di dalam kluster yang sama. kemudian dipilih sebagai yang terkecil yang memberikan proporsi lebih tinggi dari beberapa ambang batas (misalnya, ambang batas 0,8).$k$$k$