Matriz de puntuación de similitud de cadena

Tengo una carga de documentos, que tienen una carga de pares de valores clave en ellos. Es posible que la clave no sea única, por lo que puede haber varias claves del mismo tipo con valores diferentes.

Quiero comparar la similitud de las claves entre 2 documentos. Más específicamente, la similitud de cadena de estos valores. Estoy pensando en usar algo como el algoritmo Smith-Waterman para comparar la similitud.

Así que dibujé cómo estoy pensando en representar los datos:

Los valores en las celdas son el resultado del algoritmo smith-waterman (o alguna otra métrica de similitud de cadenas).

Imagen de que esta matriz representa un tipo clave de "cosas". Luego necesito agregar el puntaje de similitud de "cosas" en un vector de 0 o 1. Eso está bien.

Lo que no puedo entender es cómo determino si la matriz es similar o no, idealmente quiero convertir la matriz a un número entre 0 y 1 y luego estableceré un umbral para calificarla como 0 o 1)

¿Alguna idea de cómo puedo crear una puntuación de la matriz? ¿Alguien sabe algún algoritmo que haga este tipo de cosas (obviamente, cosas como cómo funciona Smith Waterman es más o menos aplicable).

Como entendí, el Documento 1 y el Documento 2 pueden tener diferentes números de claves. Y desea obtener una evaluación final de similitud entre 0 y 1. Si es así, propondría el siguiente algoritmo:

1. Suma de máx. vals es igual a 0.
2. Seleccione el valor máximo de la matriz doc-doc y agréguelo a la suma de máx. vals
3. Elimine la fila y la columna con el valor máximo de la matriz.
4. Repita los pasos 2-3 hasta que finalicen las filas o columnas.
5. Denominar Suma de máx. vals por número promedio de palabras clave en dos textos.

La estimación final sería igual a 1, si ambos documentos tienen una longitud idéntica, y cada palabra del Doc 1 tiene equivalente en el Doc 2.

No ha mencionado el software que está utilizando, pero aquí hay un ejemplo de función R , que calcula tal similitud (toma el objeto de la matriz de clase como entrada):

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

Si su objetivo es transformar su matriz en un número (su medida de similitud), es posible que desee utilizar una norma de matriz .

Por ejemplo, usar la norma Frobenius en su ejemplo devolvería 1.488086.

Creo que su objetivo es encontrar cuán similares son dos documentos, si ese es el caso, sugiero aplicar el siguiente algoritmo:

Este enfoque proporciona cuánto Doc1 similar es wrt Doc2. (Los valores de similitud serán diferentes para Doc2 wrt Doc1 si no es una matriz cuadrada)

1. En su matriz entre Doc1 y Doc2, obtenga el valor máximo de similitud fila por fila.
   2. Toma la suma y divide por número de filas
   3. Esto te dará el índice de similitud. Por ej. En su imagen matricial, veo que la máxima similitud fila por fila es: 0.88, 1, 0.6 Entonces (0.88 + 1 + 0.6) / 3 = 82.67%

Esto significa que Doc2 es 82.67% similar a Doc1 . La similitud no puede ir más allá de este valor, ya que seleccionamos un máximo de elementos similares en cada fila.