Agrupando una larga lista de cadenas (palabras) en grupos de similitud

31

Tengo a mano el siguiente problema: tengo una lista muy larga de palabras, posiblemente nombres, apellidos, etc. Necesito agrupar esta lista de palabras, de modo que palabras similares, por ejemplo palabras con una distancia de edición similar (Levenshtein) aparezcan en el mismo grupo Por ejemplo, "algoritmo" y "alogritmo" deberían tener altas posibilidades de aparecer en el mismo grupo.

Conozco los métodos clásicos de agrupación no supervisada, como la agrupación k-means, la agrupación EM en la literatura de reconocimiento de patrones. El problema aquí es que estos métodos funcionan en puntos que residen en un espacio vectorial. Tengo palabras de cuerdas en mi mano aquí. Parece que la pregunta de cómo representar cadenas en un espacio vectorial numérico y calcular "medias" de grupos de cadenas no está suficientemente respondida, según los esfuerzos de mi encuesta hasta ahora. Un enfoque ingenuo para atacar este problema sería combinar el agrupamiento de k-medias con la distancia de Levenshtein, pero la pregunta sigue siendo "¿Cómo representar" medios "de cuerdas?". Hay una ponderación denominada ponderación TF-IDF, pero parece que está relacionada principalmente con el área de agrupación de "documentos de texto", no para la agrupación de palabras individuales. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Mi búsqueda en esta área aún continúa, pero también quería obtener ideas de aquí. ¿Qué recomendaría en este caso? ¿Alguien conoce algún método para este tipo de problema?

clustering k-means pattern-recognition Ufuk Can Bicici
fuente
1
Aprendí sobre la existencia de una variante de k-means llamada "K-medoids". en.wikipedia.org/wiki/K-medoids No funciona con la distancia Euclidiana L2 y no necesita el cálculo de medias. Utiliza el punto de datos más cercano a otros en un clúster como el "medoide".
Ufuk Can Bicici
1
It seems that there are some special string clustering algorithms. Si proviene específicamente del campo de minería de texto, no de estadísticas / análisis de datos, esta declaración está garantizada. Sin embargo, si aprende la rama de agrupación tal como está, encontrará que no existen algoritmos "especiales" para los datos de cadena. El "especial" es cómo preprocesar dichos datos antes de ingresarlos en un análisis de clúster.
ttnphns
relacionado: stackoverflow.com/questions/21511801/…
Andre Holzner
Observe la diferencia entre la Propagación de afinidad y la agrupación de K-medias y cómo afectará el tiempo de cálculo. quora.com/…
Gabriel Alon

Respuestas:

37

Recomendación de @ mican para la propagación de afinidad .

Del documento: L Frey, Brendan J. y Delbert Dueck. "Agrupación al pasar mensajes entre puntos de datos". Science 315.5814 (2007): 972-976. .

Es super fácil de usar a través de muchos paquetes. Funciona en cualquier cosa que pueda definir la similitud por pares. Lo que puedes obtener multiplicando la distancia de Levenshtein por -1.

Creé un ejemplo rápido usando el primer párrafo de su pregunta como entrada. En 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))

La salida fue (ejemplos en cursiva a la izquierda del clúster del que son ejemplares):

  • tener: posibilidades, editar, mano, tener, alto
  • siguiente: siguiente
  • problema: problema
  • I: I, a, at, etc., en, lista, de
  • posiblemente: posiblemente
  • cluster: cluster
  • palabra: para, y, por, largo, necesidad, debe, muy, palabra, palabras
  • similar: similar
  • Levenshtein: Levenshtein
  • distancia: distancia
  • the: that, the, this, to, with
  • same: ejemplo, lista, nombres, same, such, apellidos
  • algoritmo: algoritmo, alogritmo
  • aparece: aparece, aparece

Ejecutándolo en una lista de 50 nombres aleatorios :

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

Se ve muy bien para mí (eso fue divertido).

Lyndon White
fuente
¿es posible tener el mismo algoritmo usando solo sklearn? o usar scipy.spatial.distance con hamming? ¿Cuál es la ventaja de usar levenshtein? Supongo que tendré que intentar usar esta pregunta: stackoverflow.com/questions/4588541/…
pierre
1
@pierre Levenshtein es lo que yo llamaría una "distancia del corrector ortográfico", es un buen indicador de la posibilidad de un error de ortografía humana. Damerau Levenshtein podría ser aún mejor. No sé si Hamming Distance se define para cadenas de longitudes no iguales. Solo permite intercambios, no inserciones. determinar cómo acolchar / recortar la cuerda de manera más razonable es casi tan difícil como calcular la distensión de Levenshtein. ¿Deberías rellenar / recortar el inicio? ¿El fin? ¿Algunos del medio?
Lyndon White
Si realmente quisieras evitar la dependencia de las distancias. puede usar la implementación del código de Rossetta
Lyndon White el
leyendo el en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance puedo ver cómo la transposición puede marcar la diferencia especialmente para el error tipográfico y python tiene un paquete completamente nuevo. Puedo ver cómo puedo usar esto contra una lista de palabras y obtener la "más cercana", pero puede que no sea la más importante. Tengo que obtener mi lista y consultar con el tf-idf. Genial gracias
Pierre
1
@dduhaime casi seguro. En general, la Propagación de afinidad funciona para las perferencias no simétricas, pero dado que esto es simétrico, adelante. Estoy seguro de que algo en SciPy tiene un tipo de matriz triangular que ducktypes como una matriz completa. He pasado demasiado tiempo en tierra de julia-lang y no puedo recordar cómo se hace esto en Python. (En julia lo usarías Symmetric)
Lyndon White
5

Utilice algoritmos de agrupación de gráficos, como la agrupación de Lovaina, la agrupación de búsqueda de vecindad restringida (RNSC), la agrupación de propagación de afinidad (APC) o el algoritmo de agrupación de Markov (MCL).

micanos
fuente
¿Qué pasa con el método K-medoides que he encontrado? Necesito implementar esta solución lo antes posible, por lo que me pareció una buena solución. Soy consciente de la existencia de estos métodos basados ​​en gráficos, pero me temo que no puedo permitirme el tiempo que necesito para comprenderlos e implementarlos.
Ufuk Can Bicici
Para todos ellos, el software está disponible con acuerdos de licencia bastante no restrictivos, como la GNU GPL. No soy un gran admirador del tipo de algoritmo k-mediods, principalmente debido al parámetro k, pero depende de usted naturalmente. Si necesita una implementación interna, creo que APC y MCL son probablemente los más fáciles de implementar. Si tuviera que hacer eso, pruébelos primero, por supuesto.
micans
2

Puede probar el modelo de espacio vectorial con los n-gramos de las palabras como entradas de espacio vectorial. Creo que tendría que usar una medida como la similitud de coseno en este caso en lugar de editar la distancia.

Peace_within_reach
fuente