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

Question

Tengo el siguiente problema: Tengo una lista muy larga de palabras, posiblemente nombres, apellidos, etc. Necesito agrupar esta lista de palabras, de manera que palabras similares, por ejemplo, palabras con una distancia de edición (Levenshtein) similar, aparezcan en el mismo clúster. Por ejemplo, "algoritmo" y "alogrithm" deberían tener muchas posibilidades de aparecer en el mismo clúster.

Conozco bien los métodos clásicos de clustering no supervisado como el clustering de k-means, el clustering de EM en la literatura de reconocimiento de patrones. El problema es que estos métodos trabajan con puntos que residen en un espacio vectorial. En este caso, tengo a mano palabras de cuerda. Parece que, la cuestión de cómo representar las cadenas en un espacio vectorial numérico y calcular las "medias" de los clusters de cadenas no está suficientemente contestada, según mis esfuerzos de estudio hasta ahora. Un enfoque ingenuo para atacar este problema sería combinar la agrupación k-Means con la distancia Levenshtein, pero la pregunta sigue siendo "¿Cómo representar las "medias" de las cadenas?". Existe un peso llamado como peso TF-IDF, pero parece que está relacionado principalmente con el área de clustering de "documentos de texto", no para el clustering de palabras individuales. Parece que existen algunos algoritmos especiales de agrupación de cadenas, como el de http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

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

Answer 1

Secundo la recomendación de @micans de Propagación de afinidad .

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

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

He elaborado un ejemplo rápido utilizando el primer párrafo de su pregunta. En Python 3:

import numpy as np
from sklearn.cluster import AffinityPropagation
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 = 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 (los ejemplares en cursiva a la izquierda del cluster del que son ejemplares):

• tener: posibilidades, editar, mano, tener, alta
• siguiente: siguiente
• problema: problema
• I: I, a, en, etc, en, lista, de
• posiblemente: posiblemente
• racimo: clúster
• palabra: Para, y, para, largo, necesita, debe, muy, palabra, palabras
• similar: similar
• Levenshtein: Levenshtein
• distancia: distancia
• el: que, el, esta, a, con
• Lo mismo: ejemplo, lista, nombres, mismos, tales, apellidos
• algoritmo: algoritmo, alograma
• Aparecerá: aparecer, aparece

Ejecutándolo en una lista de 50 nombres de pila al azar :

• 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: Autumn, Haydee, Laureen, Lauren
• Alberto: Albertha, Alberto, Robert
• Lore: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

A mí me parece muy bien (ha sido divertido).

Answer 2

Utilizar algoritmos de clustering de grafos, como el Louvain clustering, Restricted Neighbourhood Search Clustering (RNSC), Affinity Propgation Clustering (APC), o el algoritmo Markov Cluster (MCL).

Answer 3

Puede probar el modelo de espacio vectorial con los n-gramas de las palabras como entradas del espacio vectorial. Creo que en este caso habría que utilizar una medida como la similitud del coseno en lugar de la distancia de edición.