Métricas de similitud para cadenas de texto. Parte III: Métricas de conjuntos y emparejamiento de caracteres.

Share on facebook
Share on twitter
Share on linkedin

En la segunda parte de esta serie, se describieron algunas métricas basadas en operaciones de edición. En este artículo se revisará algunas métricas que utilizan enfoques alternativos, por ejemplo, las operaciones de conjuntos o la posición donde ocurre la concordancia entre caracteres.

Jaccard

A diferencia de otras métricas revisadas hasta ahora, el índice de Jaccard opera sobre conjuntos, por lo cual, es común que se utilice para comparar sentencias o párrafos completos como un conjunto de palabras, sin embargo también puede ser utilizado para comparar palabras considerándolas como conjuntos de letras o caracteres. Cualquiera que sea el nivel de tokenización sobre el que se utilice, es interesante notar que la posición que ocupa el elemento no tiene relevancia y que los elementos repetidos son considerados como uno solo dentro del conjunto.

El índice de Jaccard está definido como la intersección sobre la unión de los conjuntos y es una medida de la similitud entre ambos. Es decir, es la división entre el número de elementos en común que tienen los dos conjuntos sobre el número de elementos únicos que tiene la unión de ambos conjuntos.

Fórmula del índice de similitud de Jaccard

Por su parte, la distancia de Jaccard es el resultado de restarle a 1 el valor de la similitud.

Distancia de Jaccard

Algunos ejemplos de aplicar esta métrica a cadenas de texto se muestran a continuación:

Dice

El coeficiente de Sorensen-Dice o simplemente Dice es una métrica relacionada con el índice de Jaccard. Debido a esta relación y al hecho de que no satisface la desigualdad del triángulo al coeficiente de Dice, se le considera la versión semimétrica del índice de Jaccard.

Se define de la siguiente manera para medir la similitud entre dos conjuntos:

De manera análoga al índice de Jaccard la medida de distancia se obtiene al restarle a 1 el valor de la similitud.

Dado un valor del coeficiente de Dice (D) es posible calcular el índice de Jaccard (J) y viceversa mediante las siguientes ecuaciones:

De cierta forma, se puede ver que el coeficiente de Dice le da mayor peso a los elementos comunes entre ambos conjuntos, lo que se puede apreciar al comparar los resultados de calcular la similitud por ambos métodos.

Jaro

La similitud de Jaro de dos cadenas s1 y s2, se basa el número de caracteres (m) que hacen match en ambas cadenas y el número (t) de transposiciones entre ellos. En este contexto, el match se refiere a los caracteres que están presentes en ambas cadenas pero tomando en cuenta la cercanía de su posición, es decir, caracteres lejanos en posición no se considera que hacen match.

Pero, ¿qué tan cercanos deben estar en su posición dos caracteres para hacer match? Esta pregunta se responde de acuerdo con la siguiente fórmula:

Si un caracter está presente en ambas cadenas y su posición se aleja a lo más el resultado de la fórmula anterior (más o menos la mitad de la cadena mas larga), entonces hay un match.

Para hacerlo más claro veamos un ejemplo entre las cadenas s1 = “cargo” y s2=”grado”. El tamaño de ambas cadenas es 5, así que al aplicar la fórmula de distancia máxima entre caracteres matcheados el resultado es igual a 1.

Esto indica que sólo harán match aquellos caracteres iguales cuya posición difiera a lo más en 1.

Caracteres comunes que hacen match (azul) y que no hacen match (rojo)

Como puede verse en la imagen de arriba la “a” de cargo y la “a” de grado hacen match al estar en las posiciones 2 y 3 respectivamente. Algo análogo ocurre con las letras “r” de ambas cadenas y también las letras “o” del final hacen match pues coinciden en su posición, sin embargo las letras “g” no hacen match al estar alejadas por más de una posición. Así, para este ejemplo el número de matches (m) es igual a 3 (a, r, o).

El número de matches es solo un elemento para calcular la similitud de Jaro y si m=0, es decir que no hay matches, entonces la similitud de Jaro es igual a cero. De otro modo se aplica la siguiente fórmula:

El valor de t (transposiciones) es el número de elementos en desorden entre los caracteres matcheados dividido entre 2. En el ejemplo la “a” y la “r” son los 2 caracteres matcheados que no se encuentran en el mismo orden por lo que t=1. Así, la similitud de Jaro entre las palabras “cargo” y “grado” es:

Como es común, la distancia de Jaro se define como la resta de 1 menos la similitud.

La métrica de Jaro fue creada en el contexto de aplicaciones de Record Linkage, al igual que la variante que veremos a continuación.

Jaro-Winkler

La similitud de Jaro-Winkler es una adaptación de la similitud de Jaro que le da mayor importancia a la concordancia entre dos cadenas cuando los caracteres en común se encuentran al principio. Este criterio va con la intuición de que al pensar en alguna palabra o frase normalmente recordamos mejor lo que va al principio y por tanto es más fácil equivocarse con lo que va al final.

La fórmula de Jaro-Winkler es un reajuste de la similitud de Jaro de la siguiente forma:

Como se muestra, a la similitud de Jaro se le aumenta un valor dependiente de dos cantidades, el valor de λ que es el número de caracteres idénticos al inicio de la cadena hasta un máximo de 4 y el parámetro p que es un valor de escalamiento entre 0 y 0.25 (usualmente se utiliza p=0.1).

Si las cadenas a comparar no concuerdan en el primer caracter, entonces la similitud de Jaro-Winkler es simplemente la similitud de Jaro, ya que al ser λ=0 el segundo término de la ecuación se convierte en cero.

Por otro lado, si utilizamos el máximo valor de p=0.25, entonces todas las cadenas que coincidan en los primeros 4 caracteres tendrán una similitud igual a 1. Veamos el efecto del parámetro p al comparar dos cadenas con el mismo prefijo de 4 caracteres, s1 = ‘abcd01234’ y s2 = ‘abcd56789’.

Revisemos ahora el efecto que tiene la posición en la que se encuentran los caracteres diferentes en ambas cadenas. Primero notemos que la similitud de Jaro al comparar cadenas que difieren en un solo caracter es la misma independiente de la posición del caracter diferente.

Al usar la similitud de Jaro-Winkler el valor de similitud cambia dependiendo de la posición del caracter que no coincide.

Notemos que el valor de similitud disminuye cuando el caracter diferente se encuentra cerca del principio de la cadena.

Conclusiones

En la tercera parte de esta serie hemos continuado con la revisión de algunas métricas o semimétricas (aquellas que no cumplen con la desigualdad del triángulo) de utilidad en la comparación de cadenas. La cuarta y última parte de esta serie describirá la biblioteca para python hermetrics que permite el uso de las métricas ya descritas, así como la construcción de métricas configurables por el usuario.

Share on facebook
Share on twitter
Share on linkedin

No hay comentarios

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

¡Conozcámonos mejor!

Te haremos llegar las novedades de SoldAI, ofertas exclusivas, notificaciones, y mucho más.

¡Deja tu correo, tenemos mucho que contarte!