Métricas de similitud para cadenas de texto. Parte I: Introducción.

Image for post
Image for post

En esta serie de artículos se explora el concepto de métricas de distancia y similitud, describiéndose algunas de las más comunes usadas al comparar cadenas de texto en el contexto del Procesamiento de Lenguaje Natural, la Extracción de Información y otras aplicaciones.

Introducción

Para dichos casos resulta de utilidad apoyarse en las medidas de similitud o distancia en cadenas de caracteres, así como para secuencias de palabras o tokens. Existe un buen número de métricas de este tipo, cada una con diferentes peculiaridades que la hacen más adepta para alguna aplicación en particular.

En este primer artículo vamos a presentar el concepto de métrica y sus propiedades de forma sencilla y en artículos posteriores analizaremos a detalle algunas de ellas, con la finalidad de que el lector pueda identificarlas y seleccionar la más apropiada para la aplicación que desee desarrollar.

Concepto de métrica

Sean x, y y z elementos a comparar, las propiedades que debe cumplir la función de distancia para ser considerada una métrica son las siguientes:

  • No negatividad
    d(x,y) ≥ 0
  • Identidad de coincidencia
    d(x,y) = 0 ⟺ x = y
  • Simetría
    d(x,y) = d(y,x)
  • Desigualdad del triángulo
    d(x,y) ≤ d(x,z) + d(y,z)

El propósito de este artículo no es profundizar en los detalles matemáticos, por lo que de manera informal podemos describir las propiedades de una métrica tal como sigue:

La No negatividad indica que el valor de la distancia entre dos elementos cualquiera tiene que ser un número positivo o cero, en caso de ser cero, la propiedad de Identidad de coincidenciaimplica que los elementos son idénticos entre sí y a su vez que la distancia de un elemento consigo mismo o su idéntico siempre será igual a cero.

La Simetría dice que la distancia entre dos elementos es independiente del sentido o dirección en la que se mida, de x a y o a la inversa, aunque existe un tipo de métricas llamadas asimétricas que no cumplen con este requerimiento (más adelante hablaremos de algunas de ellas)

Image for post
Image for post
Desigualdad del triángulo

Por último la Desigualdad del triángulo podemos asociarla con la idea de que la línea más corta entre dos puntos (x, y) es la línea recta entre ellas, es decir si pasamos por un punto z en el camino, necesariamente la distancia total recorrida se incrementa (si necesitamos desviarnos) o permanece igual (en caso de que no necesitemos desviarnos) pero nunca disminuye.

Distancia de edición

Las tres operaciones de edición tradicionalmente consideradas son la inserción, la eliminación y la sustitución, aunque algunas métricas también incorporan la transposición como operación válida. La tabla siguiente muestra como ejemplo el resultado de realizar dichas operaciones en secuencia a partir de la palabra pato para obtener la palabra caos.

Image for post
Image for post
Tabla 1. Secuencia de operaciones de edición para transformar la palabra “pato” en la palabra “caos”.

La distancia de edición más usada es la distancia de Levenshtein, por ese motivo hay quienes usan el término genérico distancia de edición para referirse a esta métrica en específico. En este artículo nos referimos como distancia de edición a cualquier métrica que utilice las operaciones de edición y distancia de Levenshtein a la versión particular que describiremos más adelante.

Distancia normalizada

Ahora bien, mientras más largas sean las cadenas de texto a comparar es mayor el número de diferencias que podemos encontrar entre ellas, por lo tanto no es lo mismo una distancia de edición d = 3 cuando comparas cadenas pequeñas, por ejemplo de 5 letras o menos, a cuando comparas cadenas largas con más de 10 caracteres.

  • d(“pato”, “carro”) = 3
    Sustituyendo p por c y t por r. Insertando la segunda r.
  • d(“El pato al patio”, “El pato va al patio”) = 3
    Insertando los tres caracteres de la cadena ‘va ‘. Nótese que se necesita un espacio adicional en la cadena final por lo que al contar la inserción del espacio, la distancia es 3 (en algunas aplicaciones los espacios son omitidos y únicamente se hace el cálculo sobre las letras u otros caracteres).

Intuitivamente se observa que a pesar de tener la misma distancia, las dos comparaciones no son equivalentes. Es decir, en la primera comparación una distancia de 3 representa un cambio proporcional importante en el texto, mientras que en la segunda comparación la frase original cambia poco en su totalidad.

Lo anterior provoca que para algunas aplicaciones la distancia de edición absoluta no sea la mejor opción, surgiendo así la necesidad de una medida de distancia de edición normalizada.

La normalización de la distancia de edición tiene como objetivo escalar el valor de la distancia a un rango común, usualmente entre cero y uno [0, 1], de tal manera que valores cercanos a cero corresponden a cadenas de texto semejantes, con d = 0 para cadenas iguales y valores cercanos a uno para cadenas de texto muy diferentes, con d = 1 implicando diferencia total entre las cadenas comparadas, es decir que no existen caracteres comunes entre ellas.

Existen diferentes métodos de normalización, estos varían de acuerdo al tipo de distancia y al dominio de aplicación, incluso se han propuesto esquemas que usan algoritmos genéticos para encontrar los parámetros de normalización.

Una forma simple de normalización que se usa con frecuencia, es dividir la distancia obtenida entre el tamaño en caracteres de la cadena más larga comparada, por ejemplo:

  • dnorm(“pato”, “carro”) = 3 / 5 = 0.6
  • dnorm(“El pato al patio”, “El pato va al patio”) = 3 / 19 = 0.16

Usando la distancia normalizada se aprecia fácilmente la diferencia relativa entre las cadenas comparadas, pues un valor de 0.6 en la primera comparación es considerablemente mayor al 0.16 obtenido en la segunda, lo cual corresponde aproximadamente con nuestra intuición.

Similitud

sim(x,y) = 1 − dnorm(x,y)

Aplicando la fórmula a los ejemplos anteriores tenemos:

  • sim(“pato”, “carro”) = 1–0.6 = 0.4
  • sim(“El pato al patio”, “El pato va al patio”) = 1–0.16 = 0.84

Como se puede ver, la similitud en el segundo ejemplo es mucho mayor que en el primero, lo cual coincide con la intuición.

Conclusiones

Publicado originalmente en el blog de SoldAI

SoldAI

Le damos a las computadoras la habilidad de interactuar y colaborar con las personas

Diego Campos Sobrino

Written by

Machine Learning Human Learner at SoldAI Research

SoldAI

SoldAI

Nuestra misión es dar a las computadoras la habilidad de interactuar y colaborar con las personas para mejorar su vidas

Diego Campos Sobrino

Written by

Machine Learning Human Learner at SoldAI Research

SoldAI

SoldAI

Nuestra misión es dar a las computadoras la habilidad de interactuar y colaborar con las personas para mejorar su vidas

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store