Dalam metode pengelompokan seperti K-means , jarak euclidean adalah metrik yang digunakan. Akibatnya, kami hanya menghitung nilai rata-rata di dalam setiap kluster. Dan kemudian penyesuaian dilakukan pada elemen-elemen berdasarkan jarak mereka ke setiap nilai rata-rata.
Saya bertanya-tanya mengapa fungsi Gaussian tidak digunakan sebagai metrik? Alih-alih menggunakan xi -mean(X), kita bisa menggunakan exp(- (xi - mean(X)).^2/std(X).^2). Jadi tidak hanya kesamaan di antara cluster diukur (rata-rata), tetapi kesamaan dalam cluster juga dipertimbangkan (std). Apakah ini juga setara dengan model campuran Gaussian ?
Itu di luar pertanyaan saya di sini, tetapi saya pikir pergantian-kejam mungkin muncul pertanyaan yang sama di atas.
Jawaban:
Ada ribuan variasi k-means . Termasuk penugasan lunak, varians, dan kovarian (biasanya disebut sebagai Gaussian Mixture Modeling atau algoritma EM).
Namun, saya ingin menunjukkan beberapa hal:
K-means tidak didasarkan pada jarak Euclidean. Ini didasarkan pada minimasi varians . Karena varians adalah jumlah dari jarak Euclidean kuadrat, penugasan varians minimum adalah yang memiliki Euclidean kuadrat terkecil, dan fungsi akar kuadratnya adalah monoton. Untuk alasan efisiensi, sebenarnya lebih pintar untuk tidak menghitung jarak Euclidean (tetapi gunakan kotak)
Jika Anda memasukkan fungsi jarak yang berbeda ke dalam k-berarti itu mungkin berhenti konvergen. Anda perlu meminimalkan kriteria yang sama di kedua langkah ; langkah kedua adalah menghitung ulang cara. Memperkirakan pusat menggunakan rata-rata aritmatika adalah estimator kuadrat terkecil, dan itu akan meminimalkan varians. Karena kedua fungsi meminimalkan varians, k-means harus konvergen. Jika Anda ingin memastikan konvergensi dengan jarak lain, gunakan PAM (mempartisi sekitar medoid. Medoid meminimalkan jarak dalam-kluster untuk fungsi jarak sewenang-wenang.)
Tetapi pada akhirnya, k-means dan semua variasinya adalah IMHO lebih dari optimasi (atau lebih tepatnya, algoritma kuantisasi vektor ) daripada sebenarnya algoritma analisis cluster. Mereka tidak akan benar-benar "menemukan" struktur. Mereka akan memijat data Anda menjadi partisi k. Jika Anda memberi mereka data yang seragam, tanpa struktur di luar keacakan sama sekali, k-means masih akan menemukan banyak "cluster" yang Anda inginkan. k-means senang dengan hasil yang dikembalikan yang pada dasarnya acak .
sumber
K-means is not based on Euclidean distancetidak cukup tempat yang jelas dalam jawaban Anda. Anda dan saya memiliki diskusi tentang hal itu di masa lalu dan saya menunjukkan bahwa minimalisasi varians adalah terkait dengan jumlah dalam kluster berpasangan euclidean d ^ 2.Ada banyak teknik pengelompokan berbeda di luar sana, dan K-means hanyalah satu pendekatan. Seperti yang dikomentari DL Dahly, algoritma EM dapat digunakan untuk mengelompokkan seperti yang Anda gambarkan. Perlu dicatat bahwa perbedaan utama antara K-means dan menggunakan EM dengan model campuran guassian untuk clustering adalah bentuk cluster: centroid masih akan mendekati perkiraan rata-rata poin dalam kelompok, tetapi K-means akan memberikan cluster bola sedangkan kernel gaussian akan memberikan ellipsoid.
Hierarchical clustering menggunakan pendekatan yang sama sekali berbeda. Pengelompokan berdasarkan kepadatan dimotivasi oleh heuristik yang sama dengan pengelompokan berdasarkan rata-rata, tetapi jelas memberikan hasil yang berbeda. Ada banyak teknik pengelompokan yang tidak mempertimbangkan segala jenis kejam.
Sungguh ketika sampai pada itu, pilihan algoritma adalah fungsi dari domain masalah dan eksperimen (yaitu melihat apa yang berhasil).
sumber