Saya memiliki masalah berikut: Saya memiliki daftar kata yang sangat panjang, mungkin nama, nama keluarga, dll. Saya perlu mengelompokkan daftar kata ini, sehingga kata-kata yang serupa, misalnya kata-kata dengan jarak pengeditan (Levenshtein) yang serupa muncul di cluster yang sama. Misalnya "algoritma" dan "alogrithm" harus memiliki peluang tinggi untuk muncul di cluster yang sama.
Saya sangat menyadari metode pengelompokan tanpa pengawasan klasik seperti k-means clustering, EM clustering dalam literatur Pattern Recognition. Masalahnya di sini adalah bahwa metode ini bekerja pada titik-titik yang berada dalam ruang vektor. Saya memiliki kata-kata string di tangan saya di sini. Tampaknya, pertanyaan tentang bagaimana merepresentasikan string dalam ruang vektor numerik dan untuk menghitung "berarti" cluster string tidak cukup dijawab, menurut upaya survei saya sampai sekarang. Pendekatan naif untuk menyerang masalah ini adalah dengan menggabungkan pengelompokan k-Means dengan jarak Levenshtein, tetapi pertanyaannya tetap "Bagaimana untuk mewakili" berarti "dari string?". Ada bobot yang disebut bobot TF-IDF, tetapi tampaknya sebagian besar terkait dengan area pengelompokan "dokumen teks", bukan untuk pengelompokan kata tunggal. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf
Pencarian saya di area ini masih berlangsung, tetapi saya juga ingin mendapatkan ide dari sini. Apa yang akan Anda rekomendasikan dalam kasus ini, adakah yang mengetahui metode apa pun untuk masalah seperti ini?
sumber
It seems that there are some special string clustering algorithms
. Jika Anda berasal dari bidang penambangan teks khusus, bukan statistik / analisis data, pernyataan ini dibenarkan. Namun, jika Anda mempelajari cabang pengelompokan seperti itu, Anda akan menemukan bahwa tidak ada algoritma "khusus" untuk data string. "Khusus" adalah cara Anda melakukan pra-proses data tersebut sebelum Anda memasukkannya ke dalam analisis cluster.Jawaban:
Rekomendasi Seconding @ mican untuk propagasi afinitas .
Dari kertas: L Frey, Brendan J., dan Delbert Dueck. "Clustering dengan mengirimkan pesan antar titik data." ilmu 315.5814 (2007): 972-976. .
Sangat mudah digunakan melalui banyak paket. Ini bekerja pada apa pun yang Anda dapat menentukan satu kesamaan berpasangan. Yang bisa Anda dapatkan dengan mengalikan jarak Levenshtein dengan -1.
Saya mengumpulkan contoh cepat menggunakan paragraf pertama dari pertanyaan Anda sebagai masukan. Dengan Python 3:
Output tadinya (contoh dalam huruf miring ke kiri dari cluster yang menjadi contohnya):
Menjalankannya di daftar 50 nama depan acak :
Terlihat sangat bagus bagi saya (itu menyenangkan).
sumber
Symmetric
)Gunakan algoritma pengelompokan grafik, seperti pengelompokan Louvain, Clustering Pencarian Lingkungan Terbatas (RNSC), Clustering Affinity Propgation (APC), atau algoritma Markov Cluster (MCL).
sumber
Anda dapat mencoba model ruang vektor dengan n-gram kata-kata sebagai entri ruang vektor. Saya pikir Anda harus menggunakan ukuran seperti cosinus similarity dalam hal ini alih-alih jarak sunting.
sumber