De meilleures métriques de distance en dehors de Levenshtein pour les ensembles de mots ordonnés et le clustering suivant

Question

J'essaie de résoudre un problème qui consiste à comparer un grand nombre d'ensembles de mots, chacun contenant un grand nombre ordonné de mots d'un ensemble de mots (totalisant 600+, très haute dimensionnalité!) Pour la similarité et ensuite les regrouper en groupes distincts. La solution doit être aussi non supervisée que possible.

Les données ressemble

[Apple, banane, orange ...]
[Pomme, Banane, Raisin ...]
[Jelly, Anise, Orange ...]
[Fraise , banane, orange ...]
... etc

L'ordre des mots dans chaque matière set ([Apple, banane, orange] est distinct de [Apple, orange, banane]

Le approche que j'ai b Jusqu'à présent, l'utilisation de la distance de Levenshtein (limitée par un seuil de distance) était une métrique calculée dans un script Python, chaque mot étant l'identifiant unique, générant une matrice de similarité à partir des distances et lançant cette matrice dans k-Mediods. KNIME pour les groupements.

Mes questions sont les suivantes:

• est-Levenshtein la distance la plus appropriée métrique à utiliser pour ce problème?
• Est-ce que le regroupement de prototypes moyen/médio est le meilleur moyen de contourner les regroupements?
• Je n'ai pas encore beaucoup réfléchi à la validation du choix de 'k' dans le clustering. L'évaluation d'une courbe SSE de la classification serait-elle le meilleur moyen d'y parvenir?
• Y a-t-il des failles dans ma méthodologie?
• En tant qu'extension de la solution à l'avenir, étant donné les données d'entraînement, quelqu'un aurait-il des idées pour attribuer des probabilités aux affectations de cluster? Par exemple, l'ensemble 1 a 80% de chance d'être dans le groupe 1, etc.

J'espère que mes questions ne sembleront pas trop bêtes ou les réponses douloureusement évidentes, je suis relativement nouveau à l'exploration de données.

Merci!

Answer 1

Oui, Levenshtein est un moyen très approprié de le faire. Mais si les séquences varient beaucoup en taille, vous devriez peut-être normaliser ces distances en divisant par la somme des longueurs de séquence - sinon vous constaterez que les distances observées tendent à augmenter pour les paires de longues séquences dont la "distance moyenne" (dans le sens de la distance moyenne entre les sous-chaînes de longueur k correspondantes, pour un petit k) est constante. Exemple: On peut dire que la paire ([Apple, Banana], [Carrot, Banana]) a la même distance «moyenne» que ([Apple, Banana, Widget, Xylophone], [Carrot, Banana, Yam, Xylophone]) puisque chaque 2ième élément correspond aux deux, mais la distance brute de Levenshtein de cette dernière paire sera deux fois plus grande.

Gardez aussi à l'esprit que Levenshtein ne fait pas les allocations spéciales pour « bloc se déplace »: si vous prenez une chaîne, et déplacer l'un de ses sous-chaînes suffisamment loin, puis la paire résultante (de chaînes originales et modifiées) aura le même score de Levenshtein que si la 2ème chaîne avait des éléments complètement différents à la position où la sous-chaîne a été déplacée. Si vous voulez en tenir compte, pensez à utiliser un compression-based distance à la place. (Bien que j'y dise qu'il est utile pour calculer les distances sans respecter l'ordre, il favorise bien entendu la similitude ordonnée avec la similarité désordonnée.)

Answer 2

Découvrez SimMetrics sur sourceforge pour une plate-forme prenant en charge une variété de métriques pouvant être utilisées pour évaluer le meilleur pour une tâche.

pour une version commercialement valide consultez K-Similarity de K-Now.co.uk.