Explicación de los algoritmos de coincidencia difusa
La imagen de arriba puede haberle dado una idea suficiente de lo que trata este post.
Este post cubre algunos de los importantes algoritmos de coincidencia de cadenas fuzzy(no exactamente iguales, pero lumpsum las mismas cadenas, decir RajKumar & Raj Kumar) que incluye:
Distancia de Hamming
Distancia de Levenstein
Distancia de Levenstein de Damerau
Coincidencia de cadenas basada en N-Gram
Árbol de BK
Algoritmo de Bitap
Pero primero debemos saber por qué la coincidencia difusa es importante considerando un escenario del mundo real. Siempre que se permite a un usuario introducir cualquier dato, las cosas pueden volverse realmente complicadas, como en el siguiente caso.
Dejemos,
Su nombre es ‘Saurav Kumar Agarwal’.
Le han dado una tarjeta de biblioteca (con una identificación única, por supuesto) que es válida para cada miembro de su familia.
Va a una biblioteca para sacar algunos libros cada semana. Pero para esto, primero tiene que hacer una entrada en un registro en la entrada de la biblioteca donde se introduce su ID & nombre.
Ahora, las autoridades de la biblioteca deciden analizar los datos en este registro de la biblioteca para tener una idea de los lectores únicos que visitan cada mes. Ahora, esto se puede hacer por muchas razones (como para ir a la expansión de la tierra o no, debe el número de libros aumentó? etc).
Ellos planean hacer esto por el recuento (nombres únicos, ID de la biblioteca) pares registrados para un mes. Así que si tenemos
123 Mehul
123 Rajesh
123 Mehul
133 Rajesh
133 Sandesh
Esto debería darnos 4 lectores únicos.
Hasta ahora todo va bien
Estimaron que este número sería alrededor de 10k-10.
Pero los números aumentaron hasta ~50k después del análisis por la coincidencia exacta de los nombres.
¿O se perdieron un truco aquí? Recuerde su nombre, ‘Saurav Agarwal’. Encontraron algunas entradas que conducen a 5 usuarios diferentes a través de su ID de la biblioteca familiar:
Saurav K Aggrawal (noten la doble ‘g’, ‘ra-ar’, Kumar se convierte en K)
Saurav Kumar Agarwal
Sourav Aggarwal
SK Agarwal
Agarwal
Existen algunas ambigüedades ya que las autoridades de la biblioteca no saben
¿Cuántas personas de su familia visitan la biblioteca? si estos 5 nombres representan un solo lector, 2 o 3 lectores diferentes. Se trata de un problema no supervisado en el que tenemos una cadena que representa nombres no estandarizados, pero sus nombres estandarizados no se conocen (por ejemplo, Saurav Agarwal: Saurav Kumar Agarwal no se conoce)
¿Deberían fusionarse todos ellos con ‘Saurav Kumar Agarwal’? no se puede decir, ya que SK Agarwal puede ser Shivam Kumar Agarwal (digamos el nombre de su padre). Además, el único Agarwal puede ser cualquiera de la familia.
Los 2 últimos casos (SK Agarwal & Agarwal) requerirían alguna información extra (como el género, la fecha de nacimiento, los libros emitidos) que se alimentará a algún algoritmo de ML para determinar el nombre real del lector & debe ser dejado por ahora. Pero una cosa que estoy bastante seguro es que los 3 primeros nombres representan la misma persona & No debería necesitar información adicional para fusionarlos con un solo lector, es decir, ‘Saurav Kumar Agarwal’.
¿Cómo se puede hacer esto?
Aquí viene la coincidencia de cadenas fuzz que significa una coincidencia casi exacta entre las cadenas que son ligeramente diferentes entre sí (sobre todo debido a la ortografía incorrecta) como ‘Agarwal’ & ‘Aggarwal’ & ‘Aggrawal’. Si obtenemos una cadena con un porcentaje de error aceptable (digamos una letra errónea ), la consideraríamos como una coincidencia. Así que vamos a explorar →
La distancia de Hamming es la distancia más obvia calculada entre dos cadenas de igual longitud que da un recuento de los caracteres que no coinciden correspondientes a un índice dado. Por ejemplo: ‘Bat’ & ‘Bet’ tiene distancia hamming 1 como en el índice 1, ‘a’ no es igual a ‘e’
Distancia Levenstein/ Distancia de Edición
Aunque asumo que te sientes cómodo con la distancia Levenstein & Recursión. Si no es así, lee esto. La siguiente explicación es más bien una versión resumida de la distancia de Levenstein.
Deja que ‘x’= longitud(Str1) & ‘y’=longitud(Str2) para todo este post.
La distancia de Levenstein calcula el número mínimo de ediciones necesarias para convertir ‘Str1’ en ‘Str2’ realizando caracteres de adición, eliminación o reemplazo. Por lo tanto, ‘Cat’ & ‘Bat’ tiene una distancia de edición ‘1’ (Reemplazar ‘C’ por ‘B’) mientras que para ‘Ceat’ & ‘Bat’, sería 2 (Reemplazar ‘C’ por ‘B’; Eliminar ‘e’).
Lo que estamos haciendo es empezar a leer cadenas desde el 1er carácter
Si el carácter en el índice ‘x’ de str1 coincide con el carácter en el índice ‘y’ de str2, no se requiere edición & calcula la distancia de edición llamando
LevensteinDistance(str1,str2)
Si no coinciden, sabemos que se requiere una edición. Así que añadimos +1 a la distancia_de_edición actual & calcula recursivamente la distancia_de_edición para 3 condiciones & toma la mínima de las tres:
Levenstein(str1,str2) →inserción en str2.
Levenstein(str1,str2) →borrado en str2
Levenstein(str1,str2)→reemplazo en str2
Si alguna de las cadenas se queda sin caracteres durante la recursión, la longitud de los caracteres restantes en la otra cadena se añaden a la distancia de edición (las dos primeras sentencias if)
Demerau-Levenstein Distance
Considera ‘abcd’ & ‘acbd’. Si nos guiamos por la distancia Levenstein, esto sería (reemplazar ‘b’-‘c’ & ‘c’-‘b’ en las posiciones de índice 2 & 3 en str2) Pero si nos fijamos bien, ambos caracteres se intercambiaron como en str1 & si introducimos una nueva operación ‘Swap’ junto a ‘adición’, ‘ eliminación’ & ‘reemplazo’, este problema puede ser resuelto. Esta introducción puede ayudarnos a resolver problemas como ‘Agarwal’ & ‘Agrawal’.
Esta operación se añade mediante el siguiente pseudocódigo
Ejecutamos la operación anterior para ‘abcd’ & ‘acbd’ donde asumimos
initial_x=1 & initial_y=1 (Empezando la indexación desde 1 & no desde 0 para ambas cadenas).
actualidad x=3 &y=3 por lo tanto str1 & str2 en ‘c’ (abcd) & ‘b’ (acbd) respectivamente.
Límites superiores incluidos en la operación de corte mencionada a continuación. Por lo tanto, ‘qwerty’ significará ‘qwer’.
last_matching_index_y será el último índice de str2 que coincida con str1, es decir, 2 como ‘c’ en ‘acbd’ (índice 2)que coincida con ‘c’ en ‘abcd’.
last_matching_index_x será el último índice de str1 que coincida con str2 i.e 2 ya que ‘b’ en ‘abcd’ (índice 2)coincidió con ‘b’ en ‘acbd’.
Por lo tanto, siguiendo el pseudocódigo anterior, DemarauLevenstein(‘abc’,’acb’)=
1+(4-3-1) + (4-3-1)+LevensteinDistance(‘a’,’a’)=1+0+0=1. Habría sido 2 si siguiéramos la Distancia Levenstein
N-Grama
El n-grama no es básicamente más que un conjunto de valores generados a partir de una cadena emparejando secuencialmente ‘n’ caracteres/palabras. Por ejemplo: n-grama con n=2 para ‘abcd’ será ‘ab’,’bc’,’cd’.
Ahora, estos n-gramas pueden ser generados para cadenas cuya similitud tiene que ser medida &se pueden utilizar diferentes métricas para medir la similitud.
Dejemos que ‘abcd’ & ‘acbd’ sean 2 cadenas a emparejar.
n-gramas con n=2 para
‘abcd’=ab,bc,cd
‘acbd’=ac,cb,bd
Comparación de componentes (qgramas)
Cuento de n-gramas emparejados exactamente para las dos cadenas. En este caso, sería 0
Similaridad del coseno
Calcular el producto de puntos después de convertir los n-gramas generados para las cadenas en vectores
Coincidencia de componentes (sin tener en cuenta el orden)
Coincidencia de componentes de n-gramas ignorando el orden de los elementos dentro, es decir, bc=cb.
Existen muchas otras métricas como la distancia de Jaccard, el índice de Tversky, etc. que no se han tratado aquí.
El árbol BK
El árbol BK es uno de los algoritmos más rápidos para encontrar cadenas similares (de un conjunto de cadenas) para una cadena dada. El árbol BK utiliza una
Distancia de Levenstein
desigualdad de triángulos (lo veremos al final de esta sección)
para averiguar cadenas similares (&no sólo una cadena mejor).
Un árbol BK se crea utilizando un conjunto de palabras de un diccionario disponible. Digamos que tenemos un diccionario D={Book, Books, Cake, Boo, Boon, Cook, Cape, Cart}
Un árbol BK se crea mediante
Seleccione un nodo raíz (puede ser cualquier palabra). Que sea ‘Libros’
Recorrer cada palabra W del Diccionario D, calcular su distancia Levenstein con el nodo raíz, y hacer la palabra W hija de la raíz si no existe ninguna hija con la misma distancia Levenstein para el padre. Insertando Libros & Pastel.
Levenstein(Libros,Libro)=1 & Levenstein(Libros,Pastel)=4. Como no se ha encontrado ningún hijo con la misma distancia para ‘Libro’, hazlos nuevos hijos para la raíz.
Si existe un hijo con la misma distancia Levenstein para el padre P, ahora considere ese hijo como un padre P1 para esa palabra W, calcule Levenstein(padre, palabra) y si no existe ningún hijo con la misma distancia para el padre P1, haga que la palabra W sea un nuevo hijo para P1 sino continúe bajando por el árbol.
Considera la inserción de Boo. Levenstein(Libro, Boo)=1 pero ya existe un hijo con lo mismo es decir Libros. Por lo tanto, ahora calcular Levenstein(Libros, Boo)=2. Como no existe ningún hijo con la misma distancia para Books, haz que Boo sea hijo de Books.
Una vez preparado el Árbol BK, para buscar palabras similares para una palabra dada (palabra de consulta) necesitamos establecer un umbral_de_tolerancia digamos ‘t’.
Este es el máximo edit_distance que consideraremos para la similitud entre cualquier nodo & query_word. Cualquier cosa por encima de esto se rechaza.
Además, vamos a considerar sólo los hijos de un nodo padre para la comparación con Query donde el Levenstein(Child, Parent) está dentro de
¿por qué? se discutirá esto en breve
Si esta condición es verdadera para un hijo, entonces sólo estaremos calculando Levenstein(Hijo, Consulta) que se considerará similar a la consulta si
Levenshtein(Hijo, Consulta)≤t.
Por lo tanto, no estaremos calculando la distancia Levenstein para todos los nodos/palabras del Diccionario con la palabra de la consulta &por lo que se ahorra mucho tiempo cuando el conjunto de palabras es enorme
Por lo tanto, para que un Hijo sea similar a la Consulta si
Dejemos que la palabra para la que necesitamos encontrar palabras similares sea ‘Cuidado’ (Palabra de consulta)
Levenstein(Libro,Cuidado)=4. Como 4>1, se rechaza ‘Libro’. Ahora consideraremos sólo los hijos de ‘Libro’ que tengan una LevisteinDistancia(Hijo,’Libro’) entre 3(4-1) & 5(4+1). Por lo tanto, estaríamos rechazando ‘Libros’ & todos sus hijos ya que 1 no se encuentra en el conjunto de límites
Como Levenstein(Pastel, Libro)=4 que se encuentra entre 3 & 5, estaremos comprobando Levenstein(Pastel, Cuidado)=1 que es ≤1 por lo tanto una palabra similar.
Reajustando los límites, para los hijos de Cake, se convierten en 0(1-1) & 2(1+1)
Como ambos Cape & Cart tiene Levenstein(Child, Parent)=1 & 2 respectivamente, ambos son elegibles para ser comprobados con ‘Care’.
Como Levenstein(Cape,Care)=1 ≤1& Levenstein(Cart,Care)=2>1, sólo Cape se considera como palabra similar a ‘Care’.
Por lo tanto, encontramos 2 palabras similares a ‘Care’ que son: Cake & Cape
¿Pero en qué nos basamos para decidir sobre los límites
Esto se deduce de la desigualdad del triángulo que establece
Distancia (A,B) + Distancia(B,C)≥Distancia(A,C) donde A,B,C son lados de un triángulo.
Cómo esta idea nos ayuda a llegar a estos límites, veamos:
Dejemos que Query,=Q Parent=P & Child=C forme un triángulo con la distancia de Levenstein como longitud de arista. Sea el umbral_de_tolerancia. Entonces, por la desigualdad anterior
Levenstein(P,C) + Levenstein(P,Q)≥Levenstein(C,Q)as Levenstein(C, Q) can't exceed 't'(threshold set earlier for C to be similar to Q), HenceLevenstein(P,C) + Levenstein(P,Q)≥ t OrLevenstein(P,C)≥|Levenstein(P,Q)-t| i.e the lower limit is set
De nuevo, por la desigualdad del triángulo,
Levenstein(P,Q) + Levenstein(C,Q) ≥ Levenstein(P,C) or Levenstein(P,Q) + t ≥ Levenstein(P,C) or the upper limit is set
Algoritmo Bitap
También es un algoritmo muy rápido que se puede utilizar para la coincidencia de cadenas difusas con bastante eficiencia. Esto se debe a que utiliza operaciones a nivel de bits & ya que son bastante rápidas, el algoritmo es conocido por su velocidad. Sin perder un poco, vamos a empezar:
Digamos que S0=’ababc’ es el patrón que se va a emparejar con la cadena S1=’abdababc’.
Primero de todo,
Descubrir todos los caracteres únicos en S1 & S0 que son a,b,c,d
Formar patrones de bits para cada carácter. ¿Cómo?
Invertir el patrón S0 a buscar
Para el patrón de bits para el carácter x, colocar 0 donde ocurre en el patrón sino 1. En T, ‘a’ ocurre en el 3er & 5to lugar, colocamos 0 en esas posiciones & resto 1.
De manera similar, forme todos los otros patrones de bits para diferentes caracteres en el diccionario.
S0=ababc S1=abdababc
Tome un estado inicial de un patrón de bits de longitud(S0) con todos los 1’s. En nuestro caso, sería 11111 (Estado S).
Como empezamos a buscar en S1 y pasamos por cualquier carácter,
desplazar un 0 en el bit más bajo es decir el 5º bit por la derecha en S &
Operación en S con T.
Por lo tanto, como nos encontraremos con la primera ‘a’ en S1, vamos a
Desplazar un 0 en S en el bit más bajo para formar 11111 →11110
11010 | 11110=11110
Ahora, cuando pasamos al segundo carácter ‘b’
Desplazar un 0 en S i.e para formar 11110 →11100
S |T=11100 | 10101=11101
Al encontrar ‘d’
Cambia 0 a S para formar 11101 →11010
S |T=11010 |11111=11111
Observa que como ‘d’ no está en S0, el estado S se reinicia. Una vez que se recorre todo el S1, se obtienen los siguientes estados en cada carácter
¿Cómo puedo saber si he encontrado alguna coincidencia falsa/completa?
Si un 0 llega al bit más alto del patrón de bits del Estado S(como en el último carácter ‘c’), tiene una coincidencia completa
Para la coincidencia fuzz, observe 0 en diferentes posiciones del Estado S. Si el 0 está en el 4º lugar, encontramos 4/5 caracteres en la misma secuencia que en S0. Del mismo modo para el 0 en otros lugares.
Una cosa que usted puede haber observado que todos estos algoritmos trabajan en la similitud ortográfica de las cadenas. ¿Puede haber algún otro criterio de coincidencia difusa? Sí,
Fonética
¡Cubriremos los algoritmos de coincidencia difusa basados en la fonética (como Saurav & Sourav, debería tener una coincidencia exacta en la fonética) a continuación!
Reducción de dimensiones (3 partes)
Algoritmos de PNL(5 partes)
Básicos del aprendizaje por refuerzo (5 partes)
Empezando por lasSeries (7 partes)
Detección de Objetos usando YOLO (3 partes)
Tensorflow para principiantes (conceptos + Ejemplos) (4 partes)
Preprocesamiento de Series Temporales (con códigos)
