J'ai le problème suivant à portée de main: j'ai une très longue liste de mots, éventuellement des noms, des noms de famille, etc. J'ai besoin de regrouper cette liste de mots, de sorte que des mots similaires, par exemple des mots avec une distance d'édition similaire (Levenshtein) apparaissent dans même cluster. Par exemple, "algorithme" et "alogrithme" devraient avoir de grandes chances d'apparaître dans le même cluster.
Je connais bien les méthodes de clustering non supervisées classiques comme le clustering k-means, le clustering EM dans la littérature sur la reconnaissance de formes. Le problème ici est que ces méthodes fonctionnent sur des points qui résident dans un espace vectoriel. J'ai des mots de cordes à ma main ici. Il semble que la question de savoir comment représenter les chaînes dans un espace vectoriel numérique et calculer les "moyennes" des groupes de chaînes ne soit pas suffisamment répondue, selon mes efforts d'enquête jusqu'à présent. Une approche naïve pour attaquer ce problème serait de combiner le clustering k-Means avec la distance de Levenshtein, mais la question demeure "Comment représenter" les moyens "des chaînes?". Il existe un poids appelé poids TF-IDF, mais il semble qu'il soit principalement lié au domaine du regroupement de "documents texte", et non au regroupement de mots uniques. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf
Ma recherche dans ce domaine se poursuit, mais je voulais aussi avoir des idées d'ici. Que recommanderiez-vous dans ce cas, quelqu'un est-il au courant de méthodes pour ce genre de problème?
la source
It seems that there are some special string clustering algorithms
. Si vous venez d'un domaine spécifiquement text-mining, et non de statistiques / analyse de données, cette déclaration est garantie. Cependant, si vous apprenez la branche de clustering telle qu'elle est, vous constaterez qu'il n'existe aucun algorithme "spécial" pour les données de chaîne. Le «spécial» est la façon dont vous prétraitez ces données avant de les saisir dans une analyse de cluster.Réponses:
Appuyant la recommandation de @ mican pour la propagation d'affinité .
Extrait de l'article: L Frey, Brendan J. et Delbert Dueck. "Clustering en passant des messages entre les points de données." science 315,5814 (2007): 972-976. .
Son super facile à utiliser via de nombreux packages. Cela fonctionne sur tout ce que vous pouvez définir celui de la similitude par paire. Ce que vous pouvez obtenir en multipliant la distance de Levenshtein par -1.
J'ai rassemblé un exemple rapide en utilisant le premier paragraphe de votre question comme entrée. En Python 3:
La sortie était (les exemples en italique à gauche du cluster dont ils sont exemplaires):
L'exécuter sur une liste de 50 prénoms aléatoires :
Ça a l'air très bien pour moi (c'était amusant).
la source
Symmetric
)Utilisez des algorithmes de clustering de graphiques, tels que le clustering de Louvain, le clustering de recherche de voisinage restreint (RNSC), le clustering de propagation d'affinité (APC) ou l'algorithme de Markov Cluster (MCL).
la source
Vous pouvez essayer le modèle d'espace vectoriel avec les n-grammes des mots comme entrées d'espace vectoriel. Je pense que vous devriez utiliser une mesure comme la similitude cosinus dans ce cas au lieu de modifier la distance.
la source