Recuperación aproximada de direcciones postales Approximate retrieval of postal addresses Yaiza Temprado Telefónica I+D ytr@creativit.com Resumen: En este artículo se presenta FuMaS (Fuzzy Matching System), un sistema que permite la recuperación eficiente de direcciones postales a partir de consultas con ruido. La recuperación difusa de esta información tiene innumerables aplicaciones, desde encontrar/limpiar duplicados en bases de datos (registros electorales, encontrar nidos de fraude postal, etc.) hasta corregir las entradas de los usuarios en sistemas tales como callejeros o cualquier tipo de formulario dónde haya que introducir una dirección postal. Los resultados de estos experimentos muestran que FuMaS es una herramienta muy útil para recuperar direcciones postales a partir de consultas con ruido, siendo capaz de resolver cerca del 85% de las direcciones con errores introducidas al sistema; una eficacia un 15% mayor que cualquier otro sistema similar probado. Palabras clave: recuperación de información, record linkage, direcciones postales, minería de texto. Abstract: In this article it is introduced FuMaS (Fuzzy Matching System), a system that allows efficient recovery of addresses through noisy queries. The fuzzy retrieval of this information has countless applications, from finding / clean duplicates in databases (voter registration, find nests of mail fraud, etc.) to correct the input from users on systems such as street directories or any type of form where an address has to be filled. The results of these experiments show that FuMaS is a very useful tool for addresses retrieval in noisy queries, being able to resolve about 85% of the addresses with errors which were introduced into the system; a 15% higher efficiency than any other similar system tested. Keywords: information retrieval, record linkage, postal address, text mining. 1 Motivación en todos los registros, pero esto no es algo común, ya que no siempre se tienen los mismos La integración de información es un área identificadores en todas las fuentes de datos a muy importante de investigación dentro de los integrar (por ejemplo, lo que puede ser el dni en campos de las bases de datos y de la minería de una base de datos, en otra puede ser el nombre). datos (Batini, Lenzerini y Navathe Otra fuente de dificultades se debe a la 1986).Integrar múltiples fuentes de información existencia de los mismos identificadores pero distintas, permite obtener una visión más presentando algún tipo de ruido que hace que la completa y precisa del mundo, así como obtener coincidencia entre los mismos no sea perfecta. conocimiento adicional del mismo. Uno de los La expresión record linkage (vinculamiento problemas más usuales a la hora de integrar de regisros) se refiere precisamente al uso de grandes bases de datos es el problema de técnicas algorítmicas para encontrar registros detectar (para posteriormente limpiar o integrar) que, aunque no identifiquen exactamente de la fragmentos de varios registros que tratan de las misma forma a una entidad, sí que se refieren a mismas entidades. Detectar varias registros la misma (Baeza-Yates y Navarro 1997). tratando sobre las mismas entidades puede ser Dentro de la literatura, el proceso de linkado de una tarea simple si la información que identifica registros se encuentra asociado a una gran a las identidades es la misma (y está completa) variedad de nombres: hetereogeneidad de identidad, identificación de identidades, posibles maneras distintas. Esto es posible identificación de instancias, mezclar/purgar, debido a la utilización de abreviaturas, reconciliación de entidades, lavado de listas y sinónimos, contracciones y otras formas limpieza de datos. lingüísticas que permiten generar cierta Las aplicaciones del vinculamiento de ambigüedad o variedad de formas escritas para registros son innumerables, sobre todo en los mismos conceptos. entornos administrativos: desde la gestión de Además de estas formas correctas, también relaciones con los clientes, detección del fraude, se pueden encontrar formas incorrectas que, data warehousing, encontrar registros en pese a referirse a la misma dirección, muestran diversas fuentes pertenecientes a un mismo ciertos errores o datos faltantes. Como paciente, etc. ejemplos: El enfoque general de los algorimtos de vinculación de registros es determinar un • C/ Santa Maria Magdalena, Madrid coeficiente de similitud entre cada par de • C/ Santa Maria Madalena, n. 5, 4B, registros, lo cual es una tarea muy pesada, del 28900, Madrid orden de O(n2). Para poder determinar el • C/ Santa Marai Magdalena, n. 5, 4B, coeficiente de similitud entre dos registros, 28900, Madrid usualmente se han utilizado distancias de • C/ Santa Maria Magdalena, n. 54, B, edición (Navarro y Raffinot 2002) como puedan 28900, Madrid ser la distancia de Levenhstein o el algoritmo de • AV Santa Maria Magdalena, Madrid Smith-Waterman. Estas distancias permiten calcular el número mínimo de operaciones No sólo se pueden encontrar varias formas sobre los caracteres (sustitución, inserción o correctas de escribir una dirección postal, ni eliminación) necesarias para convertir una siquiera se tiene que tener únicamente en cuenta cadena en otra. Existe una gran variedad de el hecho de poder encontrar errores en las algoritmos de cálculo de distancias de dicción direcciones, sino que se pueden encontrar que pueden ser utilizados tanto dentro del combinaciones de ambas, es decir, errores en proceso de vinculación de registros como en direcciones que están ya utilizando formas muchas otras aplicaciones tales como el alternativas: procesamiento de señales con ruido, la recuperación de información con errores • C/ Sta Marai Madalena, Madrid textuales y la biología computacional. • C/ S M Madalena, 5, 4B, 28900, En este artículo se trata la vinculación de Madrid registros aplicada al problema del reconocimiento difuso de direcciones postales. 2 Descripción y Arquitectura del Las direcciones postales pueden considerarse como información estructurada, ya Sistema que contienen varios campos bien conocidos y La arquitectura del sistema de FuMaS es una delimitados (tipo de vía, nombre de la vía, arquitectura dividida en 3 capas, cada una de código postal, municipio, etc.). Ahora bien, ellas representativa de un nivel de abstracción. una dirección postal puede escribirse de FuMaS recibe como entrada una dirección múltiples maneras; de hecho la siguiente lista postal y devuelve como salida un ranking de de direcciones correctas representa la misma posibles direcciones postales, cada una con una dirección postal (calle Santa María Magdalena, medida de la calidad de la solución, ordenadas número 5, 4º B, 28900, Madrid): de mayor a menor relevancia. Como se puede ver en la subfigura 1.A, una • C/ Santa Maria Magdalena, n. 5, 4B, dirección que se introduzca como entrada del 28900, Madrid sistema pasará por los siguientes niveles: • C/ Sta Maria Magdalena, n. 5, 4B, 28900, Madrid • Tokenización: Se puede considerar • C/ Santa M. Magdalena, n. 5, 4B, como un paso de preprocesamiento más 28900, Madrid que como un nivel de abstracción (por eso se contabilizan únicamente 3 Los 3 ejemplos anteriores muestran la capas). Este nivel se encarga de recoger misma dirección postal, pero escrita de 3 una cadena de caracteres conteniendo una dirección de entrada y la separa en etc.), aunque la elección del algoritmo los diferentes elementos constituyentes concreto se ha dejado como un de la misma: tipo de vía, nombre de vía, parámetro del sistema definible por el número de portal, letra, escalera, código usuario. postal y municipio. Actualmente el tokenizador utilizado en FuMaS es un • Nivel de Frase: Esta capa es la tokenizador ad-hoc que espera los encargada de trabajar con las cadenas campos en un determinado orden, de palabras (frases). Principalmente se aunque, gracias a la modularidad del encarga de corregir los fallos debidos a sistema, se puede sustituir por un la eliminación, inserción, sustitución o tokenizador más inteligente capaz de transposición de palabras dentro de una lidiar con diversos tipos de estructuras frase. de dirección postal. • Nivel de Palabra: Es la capa a más bajo • Nivel de Dirección: Constituye la capa nivel. Se encarga de corregir los fallos de mayor abstracción, ya que es la capa debidos a la eliminación, inserción, encargada de estudiar las coherencias sustitución o transposición de letras entre todos los campos de una dirección dentro de una palabra, así como de postal. Ésto incluye las asociaciones normalizar las palabras, tanto a nivel entre códigos postales, municipios y fonético como conceptual. La nombres de calles, el número de portal normalización fonética se encarga de asociado a un determinado domicilio, representar las palabras de una forma etc. Además, es el responsable de más cercana a como se pronuncian para generar la salida del sistema: una lista corregir errores como la falta de una de posibles direcciones postales, ‘h’ o la sustitución de una ‘b’ por una ordenadas de mayor a menor ‘v’. La normalización conceptual se relevancia. Para poder generar el encarga de unificar distintas formas de ranking de salidas del sistema se utiliza escritura referentes a un mismo término un algoritmo de cálculo de distancia de (abreviaturas, sinónimos, etc.). edición entre dos cadenas de caracteres (distancia de Levehnstein, Q-gram, Esta arquitectura basada en niveles de muchos grados de mejora. Por otra parte, los abstracción permite un acercamiento más resultados presentados en este artículo simplista a un problema bastante complejo de representan la piedra de apoyo de una nueva por si. Cada una de las capas puede línea de investigación que pretende abordar el modificarse, añadiendo mayor o menor problema de la recuperación aproximada de complejidad en función de si lo que se busca información estructurada, tanto en el dominio son resultados más precisos o menor tiempo de de las direcciones postales como en otros ejecución. Esto ha permitido tener, en un dominios donde la arquitectura de FuMaS periodo de tiempo relativamente corto, un pueda ser adaptada gracias a su gran prototipo del sistema plenamente funcional flexibilidad. (aunque muy mejorable), para poder evaluar el En este sentido, cabe señalar que de los 3 rendimiento del mismo y, por ende, evaluar las niveles de abstracción de FuMaS, dos de ellos posibilidades de éxito de la arquitectura son muy generales (el de frase y el de palabra) propuesta. y pueden ser reutilizados en su práctica totalidad en otros ámbitos. 3 Experimentos Bibliografía Para poder evaluar el sistema, se ha construido una pequeña colección de 100 Baeza-Yates, R., y Navarro, G., A Practical direcciones postales correctas y se han generado Index for Text Retrieval Allowing Errors, variantes incorrectas de las mismas, CLEI, 1:273-282. 1997. consiguiendo una colección de 300 direcciones Batini, C., Lenzerini, M, y Navathe, S. B., A postales en total. Las direcciones postales comparative analysis of methodologies for incorrectas se han generado teniendo en cuenta database schema integration. ACM Comput. distintos posibles fallos a la hora de escribir las Surv. 18(4):323-364, 1986. direcciones postales. Con esta colección de direcciones, se ha Navarro, G., y Raffinot, M. Flexible Pattern comparado FuMaS con otro sistema similar Matching in Strings – Practical online search (UNISERV), así como con 3 gestores de mapas algorithms for texts and biological online que incluyen algún tipo de corrección sequences. Cambridge University Press automática (Guía Campsa, Google Maps y 2002. LaNetro). Los resultados experimentales muestran que FuMaS es el sistema con mejor funcionamiento, logrando corregir cerca de un 85% de las direcciones postales introducidas en el sistema, seguido de UNISERV con un 70% de errores corregidos, la Guía Campsa con cerca del 60%, Google Maps con poco más del 40% y LaNetro que apenas es capaz de corregir errores básicos. 4 Conclusiones En este artículo se ha presentado FuMaS, un sistema que permite la recuperación eficaz de direcciones postales con ruido. Los resultados experimentales muestran que FuMaS, a pesar de su pronto estado de gestación, es capaz de corregir un 85% de las direcciones erroneas introducidas al sistema, superando por más de 15 puntos a cualquier otro software similar evaluado. FuMaS está lejos de ser un sistema acabado y cerrado; por ahora muestra una arquitectura capaz de lidiar con el sistema, y lo suficientemente modular como para permitir