Texte de clustering avec Levenshtein distances
J'ai un (2k - 4k) de petites chaînes (de 3 à 6 caractères) et je tiens à les regrouper. Depuis que j'utilise les cordes, les réponses précédentes sur Comment clustering (en particulier de la Chaîne de clustering) de travail?, m'a informé que Levenshtein est bon d'être utilisé comme une fonction de distance pour les chaînes. Aussi, puisque je ne sais pas à l'avance le nombre de clusters, le clustering hiérarchique est le chemin à parcourir et pas de k-means.
Bien que j'ai eu le problème dans sa forme abstraite, je ne sais pas quelle est la easie façon de le faire réellement. Par exemple, MATLAB ou R un meilleur choix pour la mise en œuvre effective de la classification hiérarchique avec la fonction personnalisée (Levenshtein).
Pour les deux logiciels, on peut facilement trouver un Levenshtein mise en œuvre. Le regroupement partie semble plus difficile. Par exemple Clustering de texte dans MATLAB calcule la distance de tableau pour toutes les chaînes, mais je ne comprends pas comment utiliser la distance de tableau pour obtenir effectivement le clustering. Pouvez-vous tout de vous les gourous de me montrer le chemin à la façon de mettre en œuvre la classification hiérarchique dans MATLAB ou R avec une fonction personnalisée?
- Il peut dépendre du type de clustering hiérarchique que vous utilisez. Seul lien & complet de liaison HC peut être effectuée w/ juste une matrice de distance, donc une fois que vous avez que quel que soit la méthode, normale de clustering fonctions (par exemple,
hclust
) devrait fonctionner correctement. Otoh, que, liaison moyenne ou de la méthode de Ward besoin de recalculer les distances à chaque étape, de sorte qu'ils seraient plus compliqués à mettre en œuvre. - Donc dans MATLAB Z = lien(Y,méthode) serait de travailler avec une matrice de distance calculée et la méthode complète par exemple. Droit?
- J'aurais du deviner que la réponse est "oui". Il a été un long temps depuis que je l'ai utilisé MATLAB, & je n'ai jamais fait de regroupement w/ elle.
Vous devez vous connecter pour publier un commentaire.
Cela peut être un peu simpliste, mais voici un exemple de code qui utilise la classification hiérarchique basée sur la distance de Levenshtein, dans R.
Dans cet exemple, nous créons un ensemble de 30 aléatoire char(5) les chaînes de caractères artificiellement en 3 groupes (commençant par "aa", "bb", et "cc"). Nous calculons la distance de Levenshtein de la matrice à l'aide de
adist(...)
, et nous courons heirarchal de clustering à l'aide dehclust(...)
. Nous avons ensuite coupé le dendrogramme en trois groupes aveccutree(...)
et ajouter l'id du cluster est à l'origine des chaînes de caractères.adist(...)
est dans leutils
package qui, normalement, se charge par défaut lorsque vous démarrez un R de session. Il calcule une distance totale de la matrice, qui est pourquoi vous avez besoin deas.dist(d)
pour le convertir en quelque chose dehclust(...)
comprend comme la distance de l'objet. Type?adist
de la documentation.ELKI comprend Levenshtein, et propose un large choix de avancée des algorithmes de clustering, par exemple OPTIQUE de clustering.
Texte prise en charge des clusters a été contribué par Felix Stahlberg, dans le cadre de son travail sur:
Nous sommes évidemment d'apprécier les contributions supplémentaires.
O(n^2)
ou pour le pire. Si je veux essayer quelque chose rapidement, je trouve scipy généralement pour être le meilleur langage de script, et le plus souvent il est étonnamment rapide en raison de Cython code.Alors que la réponse dépend en partie de l' sens des chaînes de caractères, en général, votre problème est résolu par l'analyse de la séquence de la famille de techniques. Plus précisément, l'Optimal Matching Analysis (OMA).
Le plus souvent l'OMA est réalisée en trois étapes. Tout d'abord, vous définissez vos séquences. À partir de votre description, je peux supposer que chaque lettre est un "état", le bloc de construction dans une séquence. La seconde, vous utilisez l'un des plusieurs algorithmes pour calculer les distances entre toutes les séquences dans le jeu de données, donc l'obtention de la matrice de distance. Enfin, vous permettra de nourrir cette matrice de distance dans un algorithme de clustering, telles que le clustering hiérarchique ou le Partitionnement Autour de Medoids (PAM), qui semble gagner en popularité en raison de l'information supplémentaire sur la qualité des clusters. Ce dernier vous guide dans le choix du nombre de clusters, l'un des plusieurs subjective étapes de l'analyse de la séquence.
Dans
R
le plus pratique package avec un grand nombre de fonctions estTraMineR
, le site web peut être trouvé ici. Son guide de l'utilisateur est très accessible, et les développeurs sont plus ou moins actif sur ainsi.Vous êtes susceptibles de trouver que le regroupement n'est pas la partie la plus difficile, sauf pour la décision sur le nombre de clusters. Le guide pour
TraMineR
montre que la syntaxe est très compliquée, et les résultats sont faciles à interpréter basée sur la séquence visuelle des graphiques. Voici un exemple à partir du guide de l'utilisateur:dist.om1
est la matrice de distance obtenue par l'OMA, l'appartenance au cluster est contenue dans leclusterward1
objet, qui que vous pouvez faire ce que vous voulez: le traçage, le recodage de variables etc. Lediss=TRUE
option indique que l'objet de données est la dissemblance (ou la distance) de la matrice. Facile, hein? Le plus difficile choix (pas du point de vue syntaxique, mais du point de vue méthodologique) est de choisir la bonne distance de l'algorithme, adapté à votre application. Une fois que vous avez que, être en mesure de justifier ce choix, le reste est assez facile. Bonne chance!Si vous souhaitez une explication claire de la façon d'utiliser partitional de clustering (qui sera sûrement plus rapide) afin de résoudre votre problème, consultez ce document: efficacité de la Vérification de l'Orthographe des Méthodes Utilisant des Algorithmes de Clustering.
https://www.researchgate.net/publication/255965260_Effective_Spell_Checking_Methods_Using_Clustering_Algorithms?ev=prf_pub
Les auteurs expliquent comment cluster un dictionnaire en utilisant une version modifiée (PAM) et la version de l'iK-Moyens.
Bonne Chance!