Mengelompokkan daftar panjang string (kata-kata) ke dalam kelompok kesamaan

31

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?

Ufuk Can Bicici
sumber
1
Saya telah belajar tentang keberadaan varian k-means yang dinamai "K-medoids". en.wikipedia.org/wiki/K-medoids Tidak berfungsi dengan jarak L2 Euclidian dan tidak perlu perhitungan rata-rata. Ini menggunakan titik data yang paling dekat dengan yang lain dalam sebuah cluster sebagai "medoid".
Ufuk Can Bicici
1
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.
ttnphns
Perhatikan perbedaan antara Afinitas Propagasi dan pengelompokan K-Means dan bagaimana pengaruhnya terhadap waktu komputasi. quora.com/…
Gabriel Alon

Jawaban:

37

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:

import numpy as np
import sklearn.cluster
import distance

words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])

affprop = sklearn.cluster.AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
    exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
    cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
    cluster_str = ", ".join(cluster)
    print(" - *%s:* %s" % (exemplar, cluster_str))

Output tadinya (contoh dalam huruf miring ke kiri dari cluster yang menjadi contohnya):

  • miliki: peluang, edit, tangan, miliki, tinggi
  • berikut: berikut
  • masalah: masalah
  • I: I, a, at, dll, dalam, daftar, dari
  • mungkin: mungkin
  • cluster: cluster
  • kata: Untuk, dan, untuk, panjang, perlu, harus, sangat, kata, kata-kata
  • mirip: mirip
  • Levenshtein: Levenshtein
  • jarak: jarak
  • the: that, the, this, to, with
  • sama: contoh, daftar, nama, sama, seperti, nama keluarga
  • algoritma: algoritma, alogrithm
  • muncul: muncul, muncul

Menjalankannya di daftar 50 nama depan acak :

  • Diane: Deana, Diane, Dionne, Gerald, Irina, Lisette, Minna, Nicki, Ricki
  • Jani: Clair, Jani, Jason, Jc, Kimi, Lang, Marcus, Maxima, Randi, Raul
  • Verline: Takdir, Kellye, Marylin, Mercedes, Sterling, Verline
  • Glenn: Elenor, Glenn, Gwenda
  • Armandina: Armandina, Augustina
  • Shiela: Ahmed, Estella, Milissa, Shiela, Thresa, Wynell
  • Laureen: Musim Gugur, Haydee, Laureen, Lauren
  • Alberto: Albertha, Alberto, Robert
  • Lore: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

Terlihat sangat bagus bagi saya (itu menyenangkan).

Lyndon White
sumber
apakah mungkin untuk memiliki algoritma yang sama hanya menggunakan sklearn? atau gunakan scipy.spatial.distance dengan hamming? apa keuntungan menggunakan levenshtein? Saya kira saya harus mencoba menggunakan pertanyaan ini: stackoverflow.com/questions/4588541/…
pierre
1
@ierre Levenshtein adalah apa yang saya sebut "jarak pemeriksa ejaan", ini adalah proksi yang bagus untuk kemungkinan kesalahan ejaan manusia. Damerau Levenshtein mungkin lebih baik. Saya tidak tahu bahwa Hamming Distance didefinisikan untuk string dengan panjang yang tidak ada bandingannya. Ini hanya memungkinkan swap, bukan penyisipan. menentukan cara memasang / memangkas string yang paling masuk akal hampir sama sulitnya dengan menghitung distensi Levenshtein. Haruskah Anda menutup / memangkas awal? Tamat? Beberapa dari tengah?
Lyndon White
Jika Anda benar-benar ingin menghindari ketergantungan pada jarak. Anda bisa menggunakan Implementasi Kode Rossetta
Lyndon White
membaca en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance saya dapat melihat bagaimana transposisi dapat membuat perbedaan khusus untuk kesalahan ketik dan python memiliki paket baru untuk itu. Saya dapat melihat bagaimana saya dapat menggunakan ini terhadap daftar kata-kata dan mendapatkan "yang paling dekat" tetapi mungkin bukan yang paling penting. Saya harus mendapatkan daftar dan memeriksa dengan tf-idf. Cool terima kasih
pierre
1
@duhaime hampir pasti. Secara umum, Affinity Propagation berfungsi untuk perferensi nonsymatric, tetapi karena ini simetris, silakan saja. Saya yakin sesuatu dalam SciPy memiliki tipe matriks segitiga yang ducktypes sebagai matriks lengkap. Saya sudah terlalu lama di tanah julia-lang dan tidak bisa mengingat bagaimana ini dilakukan dengan python. (Dalam julia Anda akan menggunakannya Symmetric)
Lyndon White
5

Gunakan algoritma pengelompokan grafik, seperti pengelompokan Louvain, Clustering Pencarian Lingkungan Terbatas (RNSC), Clustering Affinity Propgation (APC), atau algoritma Markov Cluster (MCL).

micans
sumber
Bagaimana dengan metode K-medoid yang saya temukan? Saya perlu mengimplementasikan solusi ini sesegera mungkin, jadi sepertinya solusi yang baik untuk saya. Saya sadar akan keberadaan metode berbasis grafik ini tetapi saya takut bahwa saya tidak mampu membayar waktu yang saya butuhkan untuk memahami dan mengimplementasikannya.
Ufuk Can Bicici
Untuk semuanya, perangkat lunak tersedia dengan perjanjian lisensi yang tidak membatasi, seperti GNU GPL. Saya bukan penggemar besar dari jenis algoritma k-mediods sebagian besar karena parameter k tetapi terserah Anda secara alami. Jika Anda membutuhkan implementasi in-house maka saya pikir APC dan MCL mungkin yang paling mudah untuk diterapkan. Jika Anda melakukannya, cobalah dulu tentu saja.
mikrofon
2

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.

peace_within_reach
sumber