Modelo Oculto de Markov aplicado a Direcciones Postales (página 2)

Enviado por Liudmila Padr�n Torres

Partes: 1, 2

<Punto Cardinal>::= Este | Oeste | Sur | Norte

<Prefijo de Km>::= Km

<Casa>::= [<Prefijo de Casa>] <Nombre de Número> [<Ubicación de Casa>]

<Prefijo de Casa>::= # | Número

<Ubicación de Casa>::= Altos | Bajos | Interior

<Prefijo de entre calles>::= entre

<Prefijo de Esquina>::= Esquina

<Prefijo de Edificio>::= Edificio | Bloque | CMF

<Prefijo de Piso>::= Piso | Nivel

<Prefijo de Escalera>::= Escalera

<Prefijo de Apartamento>::= Apartamento

<Prefijo de Reparto>::= Reparto | Barrio | Batey | Finca

<Prefijo de Zona Postal>::= Z

<Código Postal>::= [<Prefijo de Código Postal>] <5 dígitos>

<Prefijo de Código Postal>::= CP | CPOS | CPostal

<Prefijo de Provincia>::= Provincia

En la descripción anterior hay que aclarar que:

Todos los elementos que forman la dirección son opcionales, puesto que en algunas instancias aparecen o no aparecen indistintamente todos los atributos. Algunas veces esta característica hace que haya direcciones almacenadas que no son válidas.
El orden mostrado es el que se vio con mayor frecuencia, pero no es el único en el que aparecieron los elementos.
Las palabras en negrita o terminales pueden aparecer abreviadas en varias formas o con otros sinónimos. Cualquiera de las abreviaturas tienen variantes en las que aparecen con o sin punto al final. De la misma manera, pueden aparecer escritas con letra inicial mayúscula o minúscula, o pueden estar escritas totalmente en mayúscula.

Aplicación de los Modelos Ocultos de Markov.

El problema de extraer la estructura de textos estructurados o semiestructurados puede ser dirigido a varios niveles de complejidad, entre los cuales se encuentra el problema de extracción semántica desde documentos usando técnicas para el procesamiento del lenguaje natural, la extracción basada en patrones sintácticos y la utilización de sistemas basados en reglas para la extracción de estructuras.

Para el problema de la segmentación de direcciones postales se requiere algo más que lo que proponen las técnicas antes mencionadas. Esto es así debido a que las instancias de este problema son muy irregulares, el orden de los campos no es fijo, no todos los campos están presentes en todos los ejemplos y no siempre existen elementos separadores entre los campos.

Por otro lado, las herramientas profesionales que hay en el mercado para limpiar direcciones son sumamente costosas.

Teniendo en cuenta todos estos elementos, se llega a la conclusión de que se pudiera desarrollar una herramienta que ayude a la segmentación de direcciones postales, se ajuste a las características actuales de las direcciones de la organización estudiada, y que resuelva, si no todos, la mayoría de los problemas de normalización detectados.

Ante esta conclusión se pone especial atención en los Modelos Ocultos de Markov (HMM), poderosa técnica de máquina de aprendizaje estadística que maneja datos nuevos de forma robusta, computacionalmente eficiente y fácil de aprender e interpretar para los humanos.

Este método ha sido utilizado recientemente para la segmentación de textos libres, arrojando resultados excelentes en el procesamiento de direcciones postales. Ha sido probado para dividir un conjunto de direcciones heterogéneas de escala nacional de la India (cuyas características son similares a las aquí tratadas) con una precisión del 89%, y un 99,6% en direcciones de EE. UU., que tienden a ser más estándares.

Después de estudiar las direcciones postales y proponer la estructura que estas deben tener, se pueden utilizar los HMM para segmentar esas direcciones.

El modelo basado en HMM que se propone utilizar consta de un HMM externo y un HMM interno por cada nodo que forma el HMM externo.

La estructura del HMM externo se basa en los elementos en los que se propone sea dividida la dirección. Apoyándose en la estructura descrita anteriormente se pueden definir los nodos siguientes:

Calle
Km
Casa
Entre calle 1
Entre calle 2
Esquina
Edificio
Piso
Escalera
Apartamento
Reparto
Municipio
Zona Postal
Código Postal
Provincia

A partir de estos quince nodos y de las restricciones y relaciones posibles que hay entre ellos se puede construir una primera versión del HMM externo a utilizar. En la figura 1 aparece una versión simplificada del HMM con sus probabilidades de transición. Vale aclarar que en esa versión no aparecen todas las relaciones entre nodos ya que sería muy difícil de representar e interpretar.

Este modelo devolvería como no válidas determinadas direcciones incompletas. Si se quisiera que se aceptaran todas las direcciones, aún teniendo un único elemento, todos los nodos tendrían que tener un arco de transición al nodo Final (F).

En la figura 2 se describe más detalladamente uno de los elementos en sus relaciones con los demás. Para no extender demasiado este trabajo no se adjuntan los 17 esquemas que contempla todo el estudio realizado.

Los HMM internos se implementan para el reconocimiento de la estructura interna de cada elemento de la dirección. Por tanto, por cada nodo del HMM externo descrito en la sección anterior, hay un HMM interno, el cual está compuesto, igualmente al externo, por un nodo Inicial y Final, además de los nodos que representan la secuencia de componentes distintos que forman el elemento al que está asociado.
Algo a tener en cuenta es seleccionar una buena estructura para el HMM interno. Un buen HMM de este tipo sería aquel que aceptara solo los símbolos que pertenecen a él; para lograrlo, el HMM interno no necesariamente tiene que aprender a rechazar todos los componentes que no pertenecen a él, sino solo aquellos que pertenecen a un elemento adyacente.

Fig. 1 Propuesta de HMM externo.
Fig. 2 Relaciones del elemento "calle" con los demás de la
estructura de una dirección postal
Por tanto un HMM interno puede entrenarse en conjunto con otros que son adyacentes a él y de esta forma lograr una buena estructura.
Como conjunto de entrenamiento para cada HMM interno se utilizan los símbolos que pertenecen al elemento en cuestión. En la fase de entrenamiento se construyen las matrices A y B para cada HMM interno.
Se puede utilizar, en lugar de un diccionario para cada nodo, un único diccionario que sería el asociado al elemento.
En la figura 3 se puede ver, a modo de ejemplo, una de las estructuras de los HMM internos de los elementos de una dirección postal. Los nodos "I" representan al nodo inicial. Los nodos "F" representan el nodo final. Los nodos "T" tienen asociados un lazo cada uno, que indica que pueden ser una o más palabras. Estos nodos tienen que verificar en los diccionarios de los elementos adyacentes para salir del lazo. También pudiera existir una condición de parada que fuera la cantidad de componentes que puede tener un elemento de dirección. Por ejemplo, calle no tiene más de 5 componentes, incluyendo al prefijo.
#
Número
Pcas
Prefijo de casa
L
Letra
§
Número, número más letra, número más guión más letra, SN, número entero más número fraccionario.
–
Carácter Guión
Fig. 3. HMM interno del elemento casa.
Definición de los HMM internos.
Conclusiones.

La caracterización de unas 40 mil direcciones permitió establecer una propuesta de estructura que contiene los elementos necesarios para posibilitar una segmentación más ajustada a los intereses de la organización estudiada.
La caracterización de las direcciones hizo posible conocer: los prefijos que identifican cada uno de los elementos de la estructura de la dirección, las abreviaturas más frecuentemente utilizadas, la mayoría de las variantes en que pueden aparecer los diferentes elementos de la dirección, así como la secuencia en que aparecen los diferentes elementos de las direcciones postales.
Con toda esta información se pudo hacer una propuesta de Modelo Oculto de Markov externo para las direcciones postales de la organización estudiada, así como se pudieron elaborar los Modelos Ocultos de Markov internos para cada uno de los elementos que componen la estructura de una dirección postal.
La totalidad del estudio realizado representa un avance en la configuración de un procedimiento para segmentar correctamente las direcciones, como paso previo para conformar con estas un Almacén de Datos confiable, eficiente y eficaz.

BIBLIOGRAFÍA

[1] F. S. Almonacid, "Data Warehouse," vol. 2006. [http://www.monografias.com/trabajos6/dawa/dawa.shtml#impa]

[2] R. Kimball, "Dealing with Dirty Data," vol. 2005, 1996. [http://www.dbmsmag.com/9609d14.html]

[3] RealITech, "Data Warehousing (Data Warehousing, SQL Server.htm)," vol. 2006, 2001. [http://www.sqlmax.com/dataw1.asp]

[4] K. D. Vinayak Borkar, Sunita Sarawagiz, "Automatic segmentation of text into structured," vol. 2006, 2001. [http://www.it.iitb.ac.in/~creena/seminar/sigmod01.pdf]

[5] W. Publications, "Prism Warehouse Manager 2.0 builds, manages data warehouse," vol. 2006, 1993. [http://www.findarticles.com/p/articles/mi_m0SMG/is_n14_v13/ai_14425978]

[6] r. j. orli, "Data Extraction, Transformation, and Migration Tools," vol. 2006, 1996. [http://www.kismeta.com/ex2.html]

[7] H. Galhardas, "Data Cleaning and Integration," vol. 2006, 2000. [http://web.tagus.ist.utl.pt/~helena.galhardas/cleaning.html]

[8] UNISERV, "SOLUCIONES DE SW AL SERVICIO DE LA CALIDAD DE LOS DATOS," vol. 2005. [http://www.uniserv.de/en/download/pdf-download/Generelle-Fact-Sheets/calidad_de_los_datos.pdf]

[9] Acxiom, "Tratamiento de nombres y direcciones.

¿Porqué normalizar sus datos?," vol. 2006. [http://www.acxiom.es/Gestion_de_la_Informacion/Normalizacion_y_agrupacion/Normalizacion/index.html]

[10] E. Corporation, "Calidad de Datos: Fundamento de la Empresa Exitosa," vol. 2006, 2006. [http://www.eniac-corp.com/noticias2.htm]

[11] S. Allen, "Name and Address Data Quality," vol. 2006. [http://www.iqconference.org/Documents/IQ%20Conference%201996/Keynote%20and%20Lunch%20Speeches/Name%20and%20Address%20Data%20Quality.pdf#search=%22%22MasterSoft%20International%20%22%20%2B%20%22NADIS%22%22]

[12] J. C. Kazem Taghva, Ray Pereda, Thomas Nartker, "Address Extraction Using Hidden Markov Models," vol. 2006. [http://www.isri.unlv.edu/publications/isripub/Taghva2005a.pdf]

[13] U. N. d. Colombia, "DEFINICION DE LOS ELEMENTOS DE UN HMM," vol. 2006, 2005. [http://www.virtual.unal.edu.co/cursos/ingenieria/2001832/lecciones/hmm4.html]

[14] T. Kanungo, "Hidden Markov Models." [http://www.cfar.umd.edu/~kanungo/software/hmmtut.pdf]

[15] P. Wiggers, "HIDDEN MARKOV MODELS FOR AUTOMATIC SPEECH RECOGNITION AND THEIR MULTIMODAL APPLICATIONS," vol. 2066, 2001. [http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Wiggers_Pascal/thesis.pdf]

[16] L. M. B. Pascual, "Introducción a los Modelos Ocultos de Markov," vol. 2005. [http://www.depeca.uah.es/docencia/doctorado/cursos04_05/82854/docus/HMM.pdf]

[17] J. C. Kazem Taghva, Ray Pereda, Thomas Nartker, "Address Extraction Using Hidden Markov Models," vol. 2006. [http://www.isri.unlv.edu/publications/isripub/Taghva2005a.pdf]

[18] B. Resch, "Hidden Markov Models," vol. 2006. [http://www.igi.tugraz.at/lehre/CI/tutorials/HMM/HMM.pdf]

DATOS DE LA AUTORA

Liudmila Padrón Torres

Profesión: Especialista Informática. Graduada en Lic. en Ciencias de la Computación.

Entidad donde trabaja: Empresa de Telecomunicaciones de Cuba S.A (ETECSA V.C.)

Fecha de realización del trabajo: 29/09/2006

Categorías del Trabajo: ComputaciónGeneral, Empresa

Partes: 1, 2

Página anterior

Volver al principio del trabajo

Página siguiente

#	Número
Pcas	Prefijo de casa
L	Letra
§	Número, número más letra, número más guión más letra, SN, número entero más número fraccionario.
–	Carácter Guión