Perbedaan antara algoritma k-means standar dan spheris

Saya ingin memahami, apa perbedaan implementasi utama antara algoritma klaster standar dan k-means.

Dalam setiap langkah, k-means menghitung jarak antara vektor elemen dan centroid cluster, dan menugaskan kembali dokumen ke cluster ini, yang centroid adalah yang terdekat. Kemudian, semua centroid dihitung ulang.

Dalam k-means bola, semua vektor dinormalisasi, dan ukuran jarak adalah perbedaan cosinus.

Apakah hanya itu, atau ada yang lain?

Pertanyaannya adalah:

Apa perbedaan antara k-means klasik dan k-means bola?

K-means Klasik:

Dalam k-means klasik, kami berusaha untuk meminimalkan jarak Euclidean antara pusat cluster dan anggota cluster. Intuisi di balik ini adalah bahwa jarak radial dari pusat-cluster ke lokasi elemen harus "memiliki kesamaan" atau "sama" untuk semua elemen dari cluster itu.

Algoritme adalah:

• Setel jumlah cluster (alias jumlah cluster)
• Inisialisasi dengan menetapkan secara acak titik-titik di ruang untuk indeks cluster
• Ulangi sampai bertemu
  • Untuk setiap titik, temukan cluster terdekat dan tetapkan point ke cluster
  • Untuk setiap cluster, temukan rata-rata poin anggota dan rata-rata pusat pembaruan
  • Kesalahan adalah norma jarak cluster

K-means bola:

Dalam k-means bola, idenya adalah untuk mengatur pusat masing-masing klaster sehingga membuat seragam dan meminimalkan sudut antara komponen. Intuisi seperti melihat bintang - titik-titik harus memiliki jarak yang konsisten antara satu sama lain. Jarak itu lebih mudah untuk dikuantifikasi sebagai "cosine similarity", tetapi itu berarti tidak ada galaksi "milky-way" yang membentuk petak-petak besar yang terang melintasi langit data. (Ya, saya mencoba berbicara dengan nenek di bagian deskripsi ini.)

Versi lebih teknis:

Pikirkan tentang vektor, hal-hal yang Anda gambarkan sebagai panah dengan orientasi, dan panjang tetap. Itu dapat diterjemahkan di mana saja dan menjadi vektor yang sama. ref

Orientasi titik dalam ruang (sudutnya dari garis referensi) dapat dihitung dengan menggunakan aljabar linier, terutama produk titik.

Jika kita memindahkan semua data sehingga ekornya berada pada titik yang sama, kita dapat membandingkan "vektor" dengan sudutnya, dan mengelompokkan yang serupa ke dalam satu cluster.

Untuk kejelasan, panjang vektor diskalakan, sehingga lebih mudah "dibandingkan".

Anda bisa menganggapnya sebagai rasi bintang. Bintang-bintang dalam satu cluster dekat satu sama lain dalam beberapa hal. Ini adalah bola mata saya yang dianggap rasi bintang.

Nilai dari pendekatan umum adalah bahwa hal itu memungkinkan kita untuk merancang vektor yang dinyatakan tidak memiliki dimensi geometris, seperti dalam metode tf-idf, di mana vektor adalah frekuensi kata dalam dokumen. Dua "dan" kata yang ditambahkan tidak sama dengan "the". Kata-kata itu tidak kontinu dan non-numerik. Mereka non-fisik dalam arti geometris, tetapi kita dapat membuatnya secara geometris, dan kemudian menggunakan metode geometris untuk menanganinya. Spherical k-means dapat digunakan untuk mengelompokkan berdasarkan kata-kata.

$$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Beberapa poin:

• Mereka memproyeksikan ke unit sphere untuk menjelaskan perbedaan panjang dokumen.

Mari kita bekerja melalui proses yang sebenarnya, dan lihat bagaimana (buruk) "eyeballing" saya.

Prosedurnya adalah:

1. (Tersirat dalam masalah) menghubungkan ekor vektor pada asal
2. memproyeksikan ke unit sphere (untuk memperhitungkan perbedaan panjang dokumen)
3. gunakan pengelompokan untuk meminimalkan " ketidakseimbangan kosinus "

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(suntingan lainnya segera hadir)

Tautan:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-means-algorithm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediksi-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf