La modification d'une fonction de distance pour calculer la distance de Levenshtein entre deux ensembles de coordonnées x-y?

Question

J'ai essayé de travailler sur la modification d'une fonction Levenshtein afin qu'il puisse trouver la distance entre deux lignes, ou des ensembles de coordonnées xy (en d'autres termes, comment semblables ou différentes lignes sont, et non leur distance géométrique) . Je suis en quelques problèmes cependant. Je reçois la façon dont vous prenez la valeur ci-dessus pour obtenir le coût de la suppression, et celui à gauche pour obtenir plus, mais au cours de substitution, je suis en train d'utiliser la distance euchlidian, et il ne fonctionne pas pour moi.

Si vous pouvez indiquer ce que je fais mal, ce serait génial.

Voici le code correspondant dans javascript:

padlock.dtw = {
    _deletionCost: 1,
    _insertionCost: 1,
    levenshtein: function(a,b){
        var l1 = a.length, l2 = b.length;
        if (Math.min(l1, l2) === 0) {
            return Math.max(l1, l2);
        }
        var i = 0, j = 0, d = [];
        for (i = 0 ; i <= l1 ; i++) {
            d[i] = [];
            d[i][0] = i;
        }
        for (j = 0 ; j <= l2 ; j++) {
            d[0][j] = j;
        }
        for (i = 1 ; i <= l1 ; i++) {
            for (j = 1 ; j <= l2 ; j++) {
                d[i][j] = Math.min(
                    d[i - 1][j] + this._deletionCost, /* deletion */
                    d[i][j - 1] + this._insertionCost, /* addition */
                    d[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? 0 : this.euclideanDistance(a[i-1], b[j-1])) /* substitution, use euchlidean distance as cost */
                );
            }
        }
        this._debugPrintMatrix(d);
        return d[l1][l2];
    },
    euclideanDistance: function(a, b){
        var xd = a[0]-b[0];
        var yd = a[1]-b[1];
        return Math.abs(Math.sqrt(Math.pow(xd, 2) + Math.pow(yd, 2)));
    },
    _debugPrintMatrix: function(m){
        for(var i=0;i<m.length;i++){
            console.log.apply(this, m[i]);
        }
    }
}

Exemple de sortie:

>>> padlock.dtw.levenshtein( [ [1,1], [0,9], [3,3], [4,4] ], [ [1,1], [2,2], [3,3], [4,4] ] )

Distance Matrix:
0 1 2                 3 4
1 0 1                 2 3
2 1 2                 3 4
3 2 2.414213562373095 2 3
4 3 3.414213562373095 3 2

Final Distance: 2

Answer 1

Si je comprends bien votre question, vous devez supprimer complètement le code de calcul de la distance euclidienne entre deux points!

Tout d'abord, permettez-moi de reformuler votre question:

Vous avez deux ensembles de points, par exemple.

A = [ [1,1], [0,9], [3,3], [4,4] ]
B = [ [1,1], [2,2], [3,3], [4,4] ]

Vous essayez de calculer une distance de Levenshtein entre ces deux ensembles. Vous remplacez "lettres" avec des "points".

Jusqu'à ce point, il est logique. Il suffit de remplacer les « lettres » dans l'algorithme de levenshtein avec des points et vous avez terminé!

Mais vous avez fait une erreur: L'algorithme de Levenshtein d'origine ne calcule pas les distances entre deux lettres , comme par exemple la distance (a, b) = 1 ou de la distance (a, d) = 3.

Vous avez essayé d'étendre l'algorithme avec une telle chose (en utilisant la fonction euclideanDistance ()). Mais algorithme de levenshtein n'est pas pour de telles choses. Et si vous regardez de près, vous verrez que cela ne fonctionnera pas (les valeurs de la matrice ont un sens, et chaque itération de la boucle utilise des valeurs dans la matrice qui ont été calculés dans une itération précédente).

distance Levenshtein est une distance d'édition, aucune distance géométrique. Vous avez essayé de le changer, de sorte qu'il calcule un mélange de modifier et de la distance géométrique. Ce mélange n'a pas de sens, il est inutile et le mal, à mon humble avis.

Conclusion

Pour calculer la distance levenshtein de deux ensembles de coordonnées x-y , vous devez remplacer votre euclidianDistance () avec une simple comparaison de l'égalité (de a[0]==b[0] && a[1]==b[1]).

Ensuite, l'algorithme de levenshtein vous donnera une "distance d'édition".

Answer 2

Ne serait-il pas plus intelligent d'utiliser pour calculer la geometrics distance entre deux lignes? Ou est-il une raison particulière que vous ne voudriez pas utiliser.

Depuis deux lignes ont toujours un point d'intersection, à moins qu'ils soient parallèles (modifier, merci) , il est facile de calculer la plus petite distance: c'est 0 ou insérer des mathématiques, qui peut être trouvé sur Google

Answer 3

Je ne comprends pas pourquoi vous utiliseriez Levenshtein pour cela, il semble que vous obtiendrez de bien meilleurs résultats des calculs simples.

• Pour la différence d'angle des lignes, vous pouvez simplement trouver l'angle pour chaque ligne (arctan ((x 1-x 2) / (y_1-Y_2))) et les soustraire.
• Pour la distance moyenne des lignes, vous pouvez simplement utiliser la formule de distance avec le premier point de chaque ligne et le deuxième point de chaque ligne et en moyenne ces distances ensemble.

Autre que (à moins que vos lignes sont en 3D), il n'y a rien d'autre pour les vraiment « comparer » avec.

Peut-être que je l'ai mal compris. Cherchez-vous de comparer les valeurs de chaîne pour les lignes?