Saya menggunakan analisis semantik laten untuk mewakili kumpulan dokumen di ruang dimensi yang lebih rendah. Saya ingin mengelompokkan dokumen-dokumen ini menjadi dua kelompok menggunakan k-means.
Beberapa tahun yang lalu, saya melakukan ini menggunakan gensim Python dan menulis algoritma k-means saya sendiri. Saya menentukan cluster centroid menggunakan jarak Euclidean, tetapi kemudian mengelompokkan setiap dokumen berdasarkan kesamaan cosinus dengan centroid. Tampaknya bekerja dengan cukup baik.
Sekarang saya mencoba melakukan ini pada kumpulan dokumen yang jauh lebih besar. K-means tidak konvergen, dan saya bertanya-tanya apakah itu bug dalam kode saya. Saya membaca baru-baru ini bahwa Anda seharusnya tidak mengelompokkan menggunakan cosinus similarity, karena k-means hanya berfungsi pada jarak Euclidean. Meskipun, seperti yang saya sebutkan, tampaknya berfungsi dengan baik dalam test case saya yang lebih kecil.
Sekarang saya menemukan ini di halaman LSA Wikipedia :
Dokumen dan representasi vektor istilah dapat dikelompokkan menggunakan algoritma pengelompokan tradisional seperti k-means menggunakan langkah-langkah kesamaan seperti cosinus.
Jadi yang mana? Bisakah saya menggunakan persamaan cosinus atau tidak?
I then assigned each document to a cluster based on cosine similarity
- Kosongkan antara doc dan centroid? Dan setelah semua dokumen ditetapkan, Anda memperbarui centroid dengan cara biasa (Euclidean), karena koordinat dokumen dalam ruang diketahui. Apakah begitu?Jawaban:
Ya, Anda bisa menggunakannya. Masalahnya adalah, bahwa kemiripan cosinus bukanlah jarak, itulah mengapa disebut kemiripan. Namun demikian, dapat dikonversi ke jarak seperti dijelaskan di sini .
Bahkan, Anda bisa menggunakan jarak apa saja. Sebuah studi yang sangat bagus tentang sifat-sifat fungsi jarak dalam ruang dimensi tinggi (seperti itu biasanya terjadi dalam pengambilan informasi) adalah Pada Perilaku Mengejutkan Metrik Jarak dalam Ruang Dimensi Tinggi . Itu tidak membandingkan Euclidean vs cosinus.
Saya menemukan penelitian ini di mana mereka mengklaim bahwa dalam ruang dimensi tinggi, kedua jarak cenderung berperilaku sama.
sumber
Yes, you can use it
. (Apakah ide untuk mengubah jarak cosinus ke Euclidean sama dengan jawaban saya ?)Jarak Euclidean tidak cocok untuk membandingkan dokumen atau kumpulan dokumen. Saat membandingkan dokumen, satu masalah utama adalah normalisasi menurut panjang dokumen. Kesamaan cosine mencapai normalisasi seperti ini, tetapi jarak euclidean tidak. Terlebih lagi, dokumen sering dimodelkan sebagai distribusi probabilitas multinomial (disebut kantong kata-kata). Kesamaan cosine adalah perkiraan untuk divergensi JS yang merupakan metode yang dibenarkan secara statistik untuk kesamaan. Salah satu masalah utama dengan dokumen dan kosinus adalah bahwa seseorang harus menerapkan normalisasi tf-idf yang tepat untuk penghitungan. Jika Anda menggunakan gensim untuk mendapatkan representasi LSA, gensim sudah melakukannya.
Pengamatan lain yang bermanfaat untuk use case 2 cluster adalah bahwa Anda bisa mendapatkan inisialisasi non-acak yang baik karena LSA hanya SVD. Anda melakukannya dengan cara berikut:
sumber
Ya, pembaruan centroid yang sama dengan karya rata-rata vektor.
Lihat kasus m = 1 dalam Bagian 2.2 makalah ini . w's adalah bobot dan bobot semua adalah 1 untuk algoritma k-mean dasar.
Makalah ini menggunakan properti dari ketidaksetaraan Cauchy-Schwartz untuk menetapkan kondisi yang meminimalkan fungsi biaya untuk k-mean.
Juga ingat bahwa kesamaan cosinus bukan jarak vektor. Ketidaksamaan cosine adalah. (Ini seharusnya istilah pencarian yang bagus.) Karena itu ketika Anda memperbarui partisi, Anda mencari yang
arg max
bertentanganarg min
.sumber