Ir al contenido principal

TEXT MINING: COMPARAR CONJUNTOS DE DATOS

A veces en las empresas donde trabajamos o en los clientes existen múltiples aplicaciones que manejan los mismos datos. Podemos poner a modo de ejemplo dos aplicaciones que gestionan datos de clientes o las direcciones de los mismos. Al no tener centralizada la gestión de estos datos, en ocasiones trabajamos con datos sucios. Dichos datos es conveniente estandarizarlos o limpiarlos alguna vez sino queremos que nuestras bases de datos sean un completo caos.

¿Cómo podemos medir lo parecidas que son dos cadenas de de datos? La respuesta correcta es con la distancia de Levenshtein, que fue ideada por el ruso Vladimir Levenshtein en 1965.





La distancia de Levenshtein, que es una generalización de la distancia de Hamming y la distancia de Damerau-Levenshtein, mide lo similares que son dos cadenas de caracteres.

¿Cómo se mide? Pues es un valor numérico que indica el número mínimo de operaciones elementales que hay que realizar para transformar una cadena en otra. Se entiende como una operación elemental la inserción de un carácter, el borrado de un carácter o la sustitución de un carácter por otro.

Por ejemplo, supongamos que tenemos dos cadenas C1 y C2.
  • Si C1 = casa y C2 = casa, la D(C1,C2) = 0, porque no hace falta ninguna transformación ya que son iguales.
  • Si C1 = cerdo y C2 = lerdo, la D(C1,C2) = 1, puesto que hace falta realizar una sustitución para que sean iguales.
  • Si C1 = moto y C2 = motas, la D(C1,C2) = 2, ya que necesitamos una sustitución y una inserción para que las dos palabras sean iguales.

A continuación veremos un ejemplo de la tabla que genera el algoritmo cuando queremos comparar las palabras HONDA y ONDAS. 


El algoritmo de tipo bottom-up utiliza una matriz de (m + 1) x (n + 1), siendo m y n la longitud de las cadenas. La primera fila se rellena con los números desde 0 hasta m mientras que la primera columna se rellena con los números del 0 hasta el n. La distancia de cada casilla D(i,j) será el valor mínimo entre sustituir un carácter, añadir un carácter o sustituir un carácter por otro en las cadenas 1..i y 1..j:

D(i,j) = mínimo (D(i-1,j) + 1, D(i,j-1) + 1, D(i-1,j-1) + ((str[i] == str[j])?0:1)) 
D(i,j) = mínimo(borrar un carácter, insertar un carácter, sustituir un carácter)

En cada casilla (i,j) de la matriz se indica el número de pasos elementales que es necesario realizar para transformar la cadena 1..i en la 1..j.

La implementación del algoritmo en java es la siguiente:

public class LevenshteinDistance {
    private static int minimum(int a, int b, int c) {
        if(a<=b && a<=c)
        {
            return a;
        } 
        if(b<=a && b<=c)
        {
            return b;
        }
        return c;
    }
 
    public static int computeLevenshteinDistance(String str1, String str2) {
        return computeLevenshteinDistance(str1.toCharArray(),
                                          str2.toCharArray());
    }
 
    private static int computeLevenshteinDistance(char [] str1, char [] str2) {
        int [][]distance = new int[str1.length+1][str2.length+1];
 
        for(int i=0;i<=str1.length;i++)
        {
                distance[i][0]=i;
        }
        for(int j=0;j<=str2.length;j++)
        {
                distance[0][j]=j;
        }
        for(int i=1;i<=str1.length;i++)
        {
            for(int j=1;j<=str2.length;j++)
            { 
                  distance[i][j]= minimum(distance[i-1][j]+1,
                                        distance[i][j-1]+1,
                                        distance[i-1][j-1]+
                                        ((str1[i-1]==str2[j-1])?0:1));
            }
        }
        return distance[str1.length][str2.length];
 
    }
}

La implementación del algoritmo en otros lenguajes se puede encontrar aquí.

Entre las aplicaciones prácticas de este algoritmo están:

  • Sistemas de reconocimiento de voz
  • Sistemas para el análisis de ADN
  • Sistemas para la detección de plagios
  • Correctores ortográficos automatizados
Espero que la explicación os haya servido para entender el algoritmo y sobre todo para qué podéis utilizarlo en vuestro día a día.

Un saludo


Fuente: webmining | juanm-cv


Comentarios

Entradas populares de este blog

Soluciones Alchemy Classic 389 elementos

Hace algún tiempo salió una actualización del Juego Alchemy Classic en la que aparecían más elementos (389 en lugar de 238). Aparte de añadir elementos mejoran algunas traducciones en castellano y mejoran la interfaz, aunque todavía hay algún error en algunos nombres de elementos.

Aquí os dejo las soluciones para los que estén atascados y no puedan dormir por las noches:


Sustancia primaria
Aire=Elemento primario  Fuego=Elemento primario  Agua=Elemento primario  Tierra=Sustancia Primaria Arena=Piedra + Aire Piedra=Tierra + Fuego Arcilla=Arena + Pantano Caliza=Tierra + Amonitas Carbono=Fuego + Madera Cloro=Fuego + Sal + Electricidad CO2(Dióxido de Carbono)=Ceniza + Ácido nítrico Electricidad=Relámpago+ Metales Gas natural= Yacimiento de gas + Pozo Helio=Refinería de gas + Gas Natural Hidrógeno=Electricidad + Agua Hielo=Frío + Agua Imán=Piedra + Metales Metano=Deshechos Vegetales + Pantano Oxígeno=Electricidad + Agua Petróleo=Unidad de Bombeo + Pozo Plutonio=2 + Radiactividad + Metales Sa…

Matemáticas y cine.

El otro día estaba viendo por la televisión una película llamada 21 blackjack. En una escena de la película el profesor de matemáticas (Kevin Spacey) le presenta a uno de sus alumnos la siguiente situación: se encuentra en un concurso en la que debe escoger entre tres puertas (1,2 y 3). En dos de ellas hay una cabra, sin embargo en una de las 3 hay un flamante coche nuevo. El alumno responde que quiere abrir la puerta. El presentador, conocedor de lo que hay detrás de cada puerta decide abrir otra puerta diferente mostrando detrás de ella una cabra. El profesor se dirige al alumno y le pregunta, ¿cambiarías la puerta o te quedarías con la puerta que tienes? Muchos de nosotros cambiaríamos de puerta pensando que es una treta del presentador para engañarnos. ¿Cual elegiríais vosotros? Al comienzo tenemos 1/3 de probabilidades de acertar la puerta donde está el coche. Una vez que el presentador abre la puerta con una cabra, la mayoría de gente piensa que hay la misma probabilidad de ace…

Soluciones Alchemy Classic 442 elementos

Después de la resaca navideña y de la cuesta de enero, volvemos para informar la agradable sorpresa que nos ha dado a los fans de Alchemy Classic la empresa NIASOF,  tras actualizar el juego Alchemy Classic.


Una nueva versión con 442 elementos, interfaz mejorada de grupos y lo más importante, nuevos elementos que descubrir.


La gran novedad de esta actualización son los puntos que tienes asignados, con los que puedes  conseguir pistas sobre los elementos que no has abierto todavía como:



Conseguir un subelemento de un elemento, con 100 puntos.Conseguir el grupo de un subelemento de un elemento (qué lío , jeje), con 35 puntos.
Me gusta, me gusta el enfoque de esta nueva versión aunque los elementos que han sacado me parecen poco originales. Parece que se van agotando las ideas para los elementos nuevos.


Aquí van las soluciones:




Carbon = Tierra + Turba

Sol = Estrella + Tierra


Espacio = 3 x Estrella
Estrella = Helio + Hidrógeno
Oso Panda = Oso + Bambú


Girasol = Sol + Flor


Animales de pezuña hendida = …