Bagaimana saya tahu algoritma klaster k-means saya menderita kutukan dimensi?

Saya percaya bahwa judul pertanyaan ini mengatakan semuanya.

Ini membantu untuk berpikir tentang apa Kutukan Dimensi itu. Ada beberapa utas yang sangat bagus di CV yang layak dibaca. Inilah tempat untuk memulai: Jelaskan "Kutukan dimensi" kepada seorang anak .

Saya perhatikan bahwa Anda tertarik pada bagaimana ini berlaku untuk berarti pengelompokan. Perlu disadari bahwa k- berarti adalah strategi pencarian untuk meminimalkan (hanya) jarak Euclidean kuadrat. Mengingat hal itu, ada baiknya memikirkan bagaimana jarak Euclidean berhubungan dengan kutukan dimensi (lihat: Mengapa jarak Euclidean bukan metrik yang baik dalam dimensi tinggi? ). $k$$k$

Jawaban singkat dari utas ini adalah bahwa volume (ukuran) ruang meningkat pada tingkat yang luar biasa dibandingkan dengan jumlah dimensi. Bahkan dimensi (yang sepertinya tidak terlalu 'dimensional' bagi saya) dapat menimbulkan kutukan. Jika data Anda didistribusikan secara seragam di seluruh ruang itu, semua objek menjadi kira-kira berjarak sama satu sama lain. Namun, seperti yang dicatat oleh @ Anony-Mousse dalam jawabannya untuk pertanyaan itu, fenomena ini tergantung pada bagaimana data disusun dalam ruang; jika tidak seragam, Anda tidak harus mengalami masalah ini. Ini mengarah pada pertanyaan apakah data berdimensi tinggi yang terdistribusi secara merata sangat umum sama sekali (lihat: Apakah "kutukan dimensi" benar-benar ada dalam data nyata? ). $10$

Saya berpendapat bahwa yang penting belum tentu jumlah variabel (dimensi literal data Anda), tetapi dimensi efektif data Anda. Dengan asumsi bahwa dimensi 'terlalu tinggi' untuk k- berarti, strategi paling sederhana adalah menghitung jumlah fitur yang Anda miliki. Tetapi jika Anda ingin berpikir dalam hal dimensi efektif, Anda bisa melakukan analisis komponen utama (PCA) dan melihat bagaimana nilai eigen turun. Sangat umum bahwa sebagian besar variasi ada dalam beberapa dimensi (yang biasanya memotong dimensi asli dari dataset Anda). Itu akan menyiratkan Anda cenderung memiliki masalah dengan k- berarti dalam arti bahwa dimensi efektif Anda sebenarnya jauh lebih kecil. $10$$k$$k$

Pendekatan yang lebih terlibat adalah memeriksa distribusi jarak berpasangan dalam dataset Anda sepanjang garis @ hxd1011 yang disarankan dalam jawabannya . Melihat distribusi marginal sederhana akan memberi Anda beberapa petunjuk tentang kemungkinan keseragaman. Jika Anda menormalkan semua variabel agar berada dalam interval , jarak berpasangan harus berada dalam interval [ 0 , $[0,\ 1]$. Jarak yang sangat terkonsentrasi akan menyebabkan masalah; di sisi lain, distribusi multi-modal mungkin penuh harapan (Anda dapat melihat contoh dalam jawaban saya di sini:Bagaimana cara menggunakan variabel biner dan kontinu bersama-sama dalam pengelompokan?).$[0,\ \sqrt{\sum D}]$

Namun, apakah berarti 'bekerja' masih merupakan pertanyaan yang rumit. Di bawah asumsi bahwa ada pengelompokan laten yang berarti dalam data Anda, mereka tidak selalu ada di semua dimensi Anda atau dalam dimensi yang dikonstruksi yang memaksimalkan variasi (yaitu, komponen utama). Cluster dapat berada dalam dimensi variasi yang lebih rendah (lihat: Contoh PCA di mana PC dengan varian rendah "berguna" ). Artinya, Anda dapat memiliki kluster dengan titik-titik yang dekat dan dipisahkan dengan baik pada beberapa dimensi Anda atau pada PC dengan variasi lebih rendah, tetapi tidak mirip dengan PC variasi tinggi, yang akan menyebabkan k- berarti untuk mengabaikan kluster yang Anda cari dan pilih kluster palsu sebagai gantinya (beberapa contoh dapat dilihat di sini:$k$$k$Cara memahami kelemahan K-means ).

Jawaban saya tidak terbatas pada K berarti, tetapi periksa apakah kita memiliki kutukan dimensi untuk metode berbasis jarak. K-means didasarkan pada ukuran jarak (misalnya, jarak Euclidean)

$N$$0.5\cdot N\cdot(N-1)$

Jika kita memiliki kutukan masalah dimensionalitas, apa yang akan Anda lihat, adalah bahwa nilai-nilai ini sangat dekat satu sama lain. Ini tampaknya sangat kontra-intuitif, karena itu berarti setiap orang dekat atau jauh dari setiap orang dan ukuran jarak pada dasarnya tidak berguna.

$\frac 1 6$$\int_{x_i=0}^1\int_{x_j=0}^1 (x_i-x_j)^2 dx_i dx_j$runifrnorm

Berikut adalah simulasi untuk dimensi dari 1 hingga 500, fitur-fiturnya adalah distribusi yang seragam dari 0 hingga 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}