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

Share on facebook
Share on twitter
Share on linkedin

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

Introducción

Al trabajar con sistemas de Procesamiento de Lenguaje Natural (NLP), es frecuente toparnos con la necesidad de comparar palabras o frases entre sí, o de buscar patrones de caracteres dentro de un texto. En muchos casos es de interés encontrar no solamente las coincidencias exactas entre dos cadenas de texto, sino también tener una medida de aproximación o similitud entre éstas cuando la coincidencia no es perfecta.

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

Una métrica es una función matemática que define una distancia entre cada par de elementos de un conjunto. Cuando los elementos comparados son cadenas de texto entonces se dice que la métrica es una métrica de cadenas (string metric).

Sean xy 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).

Triángulo desigual
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

Hemos definido las métricas en términos de su función de distancia, es decir como una medida de qué tan cerca o lejos se encuentran dos elementos entre sí. En el contexto de comparación de cadenas de caracteres se considera también el concepto distancia de edición, el cual corresponde al número mínimo de operaciones de edición necesarias para convertir una cadena en la otra.

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.

TEXTO ORIGENOPERACIÓNTEXTO RESULTADO
patoInsertar spasto
pastoEliminar tpaso
pasoSustituir p por ccaso
casoTransponer s y ocaos


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

Como se dijo anteriormente, una distancia de edición puede verse como un conteo del número mínimo de operaciones de edición para transformar una cadena de texto en otra, por lo tanto al ser un conteo su valor está restringido a los números enteros no negativos, (existen variantes donde esto no es cierto, pero eso se verá más adelante).

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

En cierto sentido, la similitud puede verse como el inverso de la distancia normalizada, es decir, cuando la distancia entre dos cadenas de texto es pequeña su similitud es grande y cuando la distancia es grande, entonces su similitud es pequeña. Con este concepto en mente podemos definir la similitud como sigue:

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

En esta primera parte se describieron las métricas de distancia y algunos conceptos fundamentales de su aplicación. En la segunda parte se hablará con mayor detalles de algunas de las métricas de edición más comúnmente usadas.

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!