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

JAXB: Leer y escribir ficheros XML

Muchas veces en nuestras aplicaciones debemos manejar documentos XML ( Extensible Markup Language ). Este lenguaje se ha convertido en un estándar para intercambio de datos entre programas y aplicaciones a través de Internet. En un esquema XML (o  XSD ) podemos definir los elementos que pueden aparecer en un documento XML así como las relaciones entre los mismos. JAXB ( Java Architecture for XML Binding ) es un estándar Java para transformar un esquema XML (o  XSD ) en una representación a objetos java. Mediante la API de JAXB podemos mapear un objeto Java a un documento XML ( "marshall" ) y el proceso contrario, es decir, a partir de un esquema XML crear su conjunto de objeto Java asociado ( "unmarshall" ). JAXB Resumiendo lo que nos proporciona JAXB es: Generación de objetos Java a partir de un XSD a través de un compilador Proporciona capacidades de marshall/unmarshall (escribir fichero XML desde java y al contrario) Integración con Maven a través de xj

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