Score de similitude des chaînes de matrice

8

J'ai une charge de documents, qui ont une charge de paires de valeurs clés en eux. La clé peut ne pas être unique, il peut donc y avoir plusieurs clés du même type avec des valeurs différentes.

Je veux comparer la similitude des clés entre 2 documents. Plus précisément la similitude des chaînes de ces valeurs. Je pense utiliser quelque chose comme l' algorithme Smith-Waterman pour comparer la similitude.

J'ai donc dessiné une image de la façon dont je pense à représenter les données -

entrez la description de l'image ici

Les valeurs dans les cellules sont le résultat de l'algorithme smith-waterman (ou d'une autre métrique de similitude de chaîne).

Image que cette matrice représente un type clé de "choses" J'ai ensuite besoin d'ajouter le score de similitude "choses" dans un vecteur de 0 ou 1. C'est correct.

Ce que je ne peux pas comprendre, c'est comment déterminer si la matrice est similaire ou non similaire - idéalement, je veux convertir la matrice en un nombre compris entre 0 et 1, puis je vais simplement définir un seuil pour le marquer comme 0 ou 1.

Des idées sur la façon dont je peux créer une partition de la matrice? Quelqu'un connaît-il des algorithmes qui font ce genre de chose (évidemment, des choses comme le fonctionnement de Smith Waterman sont applicables).

David
la source
2
Il serait peut-être plus facile de répondre à votre question si vous donniez un exemple de matrice que vous jugeriez similaire à la première et expliquiez les qualités que vous recherchez en termes de similitude. Ou s'il y a un objectif général ici, quelle est la tâche que vous entendez accomplir?
Air
Oui, j'aimerais voir un exemple de ce à quoi ressemblerait un 1 et à quoi ressemblerait un 0.
Ben

Réponses:

2

Si j'ai bien compris, le Document 1 et le Document 2 peuvent avoir un nombre différent de clés. Et vous voulez obtenir une évaluation finale de la similitude entre 0 et 1. Si oui, je proposerais l'algorithme suivant:

  1. Somme de max. vals est égal à 0.
  2. Sélectionnez la valeur maximale dans la matrice doc-doc et ajoutez-la à la somme de max. vals.
  3. Supprimez la ligne et la colonne avec la valeur maximale de la matrice.
  4. Répétez les étapes 2-3 jusqu'à la fin des lignes ou des colonnes.
  5. Dénomination Somme de max. vals par nombre moyen de mots clés dans deux textes.

L'estimation finale serait égale à 1, si les deux documents ont une longueur identique, et que chaque mot du Doc 1 a son équivalent dans le Doc 2.

Vous n'avez pas mentionné de logiciel, vous l'utilisez, mais voici un exemple de fonction R , calculant une telle similitude (il faut en entrée l'objet de la matrice de classe):

eval.sim <- function(sim.matrix){
  similarity <- 0
  denominator <- sum(dim(sim.matrix)) / 2
  for(i in 1:(min(c(nrow(sim.matrix), ncol(sim.matrix))) - 1)){
    extract <- which(sim.matrix == max(sim.matrix), arr.ind=T)[1, ]
    similarity <- similarity + sim.matrix[extract[1], extract[2]]
    sim.matrix <- sim.matrix[-extract[1], -extract[2]]
  }
  similarity <- similarity + max(sm.copy)
  similarity <- similarity / denominator
}

En python -

import numpy as np

def score_matrix(sim_matrix):
    similarity = 0
    denominator = sum(sim_matrix.shape) / 2
    for i in range(min(sim_matrix.shape)):
        x, y = np.where(sim_matrix == np.max(sim_matrix))[0][0], np.where(sim_matrix == np.max(sim_matrix))[1][0]
        similarity += sim_matrix[x, y]
        sim_matrix = np.delete(sim_matrix,(x),axis=0)
        sim_matrix = np.delete(sim_matrix,(y),axis=1)
    return similarity / denominator
sobach
la source
Cela semble fonctionner assez bien, sauf la mise à l'échelle des nombres entre 0 et 1. Vous ne savez pas si la version python est comme prévu?
David
J'ai simplifié votre version python. Et quel est le problème avec la mise à l'échelle? En supposant que toutes les valeurs de la matrice d'origine se situent entre 0 et 1, le résultat devrait également être de la même échelle.
sobach
Il n'y a rien de mal avec la mise à l'échelle maintenant ... J'ai dû avoir un bug dans mon code. Merci pour l'aide qui fonctionne très bien sur mon jeu de données
David
2

Si votre objectif est de transformer votre matrice en nombre (votre mesure de similitude), vous pouvez utiliser une norme matricielle .

Par exemple, l'utilisation de la norme Frobenius sur votre exemple retournerait 1,488086.

merours
la source
Certes, j'avais oublié les normes, je vais examiner ces remerciements.
David
0

Je pense que votre objectif est de trouver à quel point deux documents sont similaires, si c'est le cas, je suggère d'appliquer l'algorithme suivant:

Cette approche donne à quel point Doc1 est similaire à Doc2. (Les valeurs de similarité seront différentes pour Doc2 par rapport à Doc1 s'il ne s'agit pas d'une matrice carrée)

  1. Dans votre matrice entre Doc1 et Doc2, obtenez la valeur de similitude maximale ligne par ligne.
    1. Prenez la somme et divisez par le nombre de lignes
    2. Cela vous donnera l'indice de similitude. Par exemple. Dans votre image matricielle, je vois que la similitude maximale ligne par ligne est: 0,88, 1, 0,6 Donc (0,88 + 1 + 0,6) / 3 = 82,67%

Cela signifie que Doc2 est similaire à 82,67% à Doc1 . La similitude ne peut pas dépasser cette valeur car nous avons sélectionné un maximum d'articles similaires dans chaque ligne.

Shravan Shetty
la source