Revista Digital de Tecnologías de la Información y Comunicación. Vol. 10, No. 2. Semestre julio-diciembre de 2014. ISSN: 1870-7505

 

Los Registros Duplicados y su Papel en la Calidad de Datos:
Estado del Arte

Roberto Rosario Cruz 1
Ricardo Peña Galeana.2

Resumen

En cierto sentido, se puede decir que a lo largo de la historia, la humanidad ha estado vinculada al tratamiento de la información. Pero el sentido especial que adquiere en esta nueva etapa de la sociedad se refiere al hecho de que la inmensa mayoría de las funciones sociales básicas están influenciadas por los archivos electrónicos, el procesamiento de la información y las tecnologías de procesamiento del conocimiento.

Palabras Clave

Registros Duplicados, Comparación de Cadenas, Bases de Datos, ADN

Introducción

En esta época, es indudable que el desarrollo vertiginoso de las tecnologías de la información y de la comunicación, así como sus aplicaciones, presentan a la comunidad mundial no solamente oportunidades sino también nuevos retos. En los últimos años se han producido notables adelantos en materia de tecnologías de la información y la comunicación, gracias a los cuales cada nueva generación de equipos y programas computacionales ha suscitado rápidamente innovaciones y posibilidades importantes de convergencia con otras tecnologías. Han aparecido combinaciones imprevistas de medios de alcance mundial que han configurado la sociedad de la información y que representan un desafío para todos los que viven en ella. La evolución hacia el Internet y sus efectos económicos, sociales, culturales y educacionales asociados, han causado cambios considerables en las formas de conducción, cooperación e intercambio de ideas y de conocimiento así como en la creatividad y diversidad de métodos y enfoques en las más disímiles formas de la vida diaria.


Ante este fenómeno, se abren nuevas perspectivas. No obstante, es preciso realizar un examen crítico, puesto que se debe tener en cuenta que las tecnologías tienden a desarrollarse más rápidamente que la capacidad que tienen los sistemas educacionales, productivos o sociales de utilizarlas. Por otro lado, una avalancha cada vez más creciente de datos está potencialmente disponible en cualquier lugar del mundo. Es imprescindible valorar el impacto que ello produce sobre la formación y la utilización de los recursos humanos, en los empleos, tanto novedosos como ya existentes, y hasta en la vida cotidiana.

La necesidad de la representación y manipulación de grandes volúmenes de información, así como su presentación y tratamiento para el apoyo a la toma de decisiones, se enmarca en este contexto. El desarrollo continúo de diferentes conceptos y técnicas que constituyen la expresión más concreta de su evolución, algunos de los cuales se han mantenido como pilares del avance ulterior de estas tecnologías y herramientas. Dentro del área de las bases de datos, el enfoque relacional, junto con su lenguaje estándar SQL, se presenta como uno de los fundamentos de las tendencias actuales más innovadoras, tales como el desarrollo de aplicaciones de bases de datos para Internet y las intranets de las organizaciones, los sistemas de administración de bases de datos relacionales/objetos, sistemas distribuidos, sistemas basados en conocimiento, e incluso, la integración de diferentes paradigmas y plataformas. De ahí, la importancia del estudio de su evolución en el momento actual.

Justificación

Desde que surgieron las bases de datos, el interés siempre ha estado centrado en que deben ser una fuente de información que cubra una serie de características mínimas, como son, la simplicidad, la seguridad y la privacidad, la integridad, la accesibilidad, la eliminación de redundancia, etc. En la actualidad, y dada la inmensa cantidad de información que puede contener una base de datos (de muchos terabytes), el objetivo prioritario se han convertido en obtener las medidas que aseguren la calidad de los datos contenidos en las bases de datos. Lo que queremos decir con esto, es que dada una base de datos tenemos que plantearnos varias preguntas, por ejemplo podríamos plantearnos las siguientes interrogantes: ¿Son correctos los datos?, ¿Son preciso y exactos los datos contenidos?, ¿Existe la posibilidad de que diferentes referencias apunten a un mismo objeto o entidad?

Las bases de datos juegan un papel importante en la tecnología de la información de hoy, que se encuentra muy ligadas con la economía. Muchas industrias y sistemas de información, dependen de la exactitud de bases de datos para llevar a cabo operaciones. Por consiguiente, la calidad de la información (o la carencia de esta) almacenada en las bases de datos, puede tener implicaciones con costos significativos para un sistema que confía en su información para funcionar y conducir el negocio.

En un sistema libre de errores con  datos perfectamente limpios, la construcción de una visión global de los datos consiste en enlazar - en términos relacionales, junta (join)- dos o más tablas con sus campos clave (llave primaria). Desafortunadamente, a los datos, a menudo les falta un identificador único que le permita tales operaciones. Además, los datos no son controlados cuidadosamente para fines de calidad, ni definidos en una forma coherente a través de diferentes fuentes de datos.

Así, la calidad de datos es a menudo comprometida debido a muchos factores, incluyendo errores  tipográficos de datos (ejemplo, Microsft en lugar de Microsoft), con esto se pierden las restricciones de integridad (ejemplo, Cuando se permiten entradas  como EdadEmpleado = 567), y las múltiples convenciones utilizadas para guardar la información (Ejemplo, Calle Dragos 44. vs. C. Dragos 44).

Para empeorar las cosas, en las bases de datos que son administradas de forma independiente no sólo tenemos problemas con los valores, sino con la estructura, la semántica y las suposiciones subyacentes acerca de que los datos pueden diferir también.

A menudo, mientras los datos se integran de orígenes diferentes para implementar un Data Warehouse, los organismos caen en la cuenta de que siguen teniendo diferencias sistemáticamente potenciales o en su defecto conflictos. Tales problemas se relacionan con la heterogeneidad de datos [Chatterjee 1991]. La limpieza de datos (Data Cleaning ) [Kimball 2004], [Han 2011], [Erhard  2000] se refiere al proceso de resolver tales problemas de la identificación en los datos. Distinguimos entre dos tipos de heterogeneidad de datos: la estructural y la léxica. La heterogeneidad estructural ocurre cuando los campos en las tuplas de la base de datos están estructurados de manera diferente en las diferentes bases de datos. Por ejemplo, en una base de datos, la dirección del cliente podría registrarse en un campo nombrado dirección, mientras que, en otra base de datos la misma información podría ser almacenada en campos múltiples como calle, ciudad, estado y CP. La heterogeneidad léxica ocurre cuando las tuplas idénticas de una base de datos le proveen una estructura diferente a los campos en otra base de datos, pero los datos usan representaciones diferentes para referirse al mismo objeto del mundo real (ej. Calle= Dragos 44, Calle = Dragos 44 entre calle Alejandro Cervantes y Cañada de los amates).

En este artículo enfocaremos la atención en el problema de heterogeneidad léxica y examinamos técnicas diversas que han sido desarrolladas para ocuparse de este problema. Enfocamos la atención en el caso donde el aporte es un conjunto de registros estructurados, en este caso, la atención se centra en casos de registros (tuplas) en  bases de datos.

El problema que estudiamos es conocido desde hace más de cinco décadas como enlace de registros (record Linkage) o coincidencia de registros (record Matching) [Newcombe 1959], [Newcombe 1962], [Newcombe 1967], [Tepping 1968], [Fellegi 1969], [Newcombe 1988].
 El propósito de la coincidencia de registros es identificar registros en las mismas o diferentes bases de datos que se refieren a la misma entidad del mundo real, aunque los registros no sean totalmente idénticos. En la comunidad de las bases de datos, el mismo problema tiene nombres múltiples y las comunidades de investigación, el problema es descrito como merge-purge (algoritmo mezcla - purga) [Hernández 1998], deduplicación de datos (data deduplication) [Qinlu 2010], [Russ 2009], e identificación de instancia (instance identification) [Wang 1989]. Usaremos el término detección de registros duplicados.

Estado del Arte

Este proyecto nace bajo la perspectiva de poner en claro que es lo que existe dentro de la “caja negra”,  llamada herramienta ETL (Extraction, Transformation and Load) [Kimball 2004], a la cual hacen referencia los textos de Data Warehousing, la cual nos sirve propiamente para homogeneizar la estructura de las bases de datos cuya heterogeneidad nos representa un problema cuya solución se encuentra dentro de este tipo de herramientas, una vez que este problema se resuelve, otro problema de tipo léxico es el que ahora tenemos que resolver y sin ninguna herramienta como la ya mencionada, el problema se multiplica, por supuesto que aquí suponemos que los diferentes orígenes de datos se encuentran en diferentes plataformas, diferentes SABD, y por tanto este trabajo se enfoca en la solución de los problemas de heterogeneidad léxica, cuya solución característica se encuentra en la solución de los problemas de distancias de edición.

El hombre desde sus comienzos, ha sentido la necesidad de comunicarse y de representar la realidad que le rodea, es por eso precisamente que creó el lenguaje como medio para realizar ambas tareas. Sin embargo, el gran problema existente es que nuestro lenguaje es “ambiguo”, es decir, diferentes personas, pueden definir los objetos o entidades del mundo real de forma diferente, o con términos diferentes, todo esto depende del punto de vista del que se mire o de la persona que lo describa. Si este hecho es trasladado al campo de las bases de datos, podemos considerar que según la cantidad de información que ésta contenga, crece la probabilidad de que existan casos que contengan datos que hagan referencia al mismo objeto o entidad, esto es lo que se conoce como “Identificación de Objetos” (Object Identification), Enlace de Registros (record linkage).
Identificación de objetos: “Se le llama identificación de objetos a la actividad que nos permite determinar si los datos en la misma o diferente fuente, representan el mismo objeto del mundo real” (“We call “Object Identification” the data quality activity needed to identify whether data in the same source or in different ones represent the same object of the real world”) [Batini 2006]

Detección de registros duplicados

Los términos, aún y cuando son formas diferentes de llamar a esta misma tarea, esto definitivamente no es otra cosa que la búsqueda de coincidencias entre los registros de una o múltiples fuentes de datos con el único objetivo de unificar aquellos que representen a una misma entidad del mundo real. Esto último también es conocido como: Deduplicación o Identificación de Duplicados. A pesar de que se consideran como sinónimos, cada autor utiliza uno u otro debido a que consideran que cada cual tiene diferentes matiz. A continuación haremos una recopilación de las diferentes definiciones, más destacadas.

Record Linkage

Según [Batini, 2006], “Record linkage” se denomina al proceso de búsqueda de  coincidencias entre los registros de estructuras de datos simples (archivos o relaciones). La  finalidad es producir, a partir de dos entradas, un nuevo archivo donde cada registro referencie a la misma entidad del mundo real. También se puede realizar este mismo proceso sobre una única entrada con el objeto de agrupar las coincidencias de registros sin elegir tuplas representativas del grupo, con la única finalidad de unificarlos. 

Los trabajos hasta ahora existentes que abordan estos conceptos, son muchos, debiendo destacar los realizados por Jaro [Jaro 1989], William E. Winkler [Winkler 1990] y otros, además otro trabajo por demás interesante es el del grupo de trabajo e investigación DAMA-UPC, de la Universidad Politécnica de Cataluña (http://www.dama.upc.edu). Su trabajo sobre record linkage consiste en un software llamado DALINK, DEX y el proyecto llamado DAURUM, cuya utilización se centra en el sistema de salud de Cataluña, mientras que DEX, es una software que permite hacer búsquedas asistidas para la detección de fraudes, este tipo de software permite al usuario buscar coincidencias entre los registros de una base de datos, en función de la similitud con los valores introducidos por el usuario para una serie de campos concretos de las respectivas tablas. Su estudio y desarrollo investigativo está centrado en la reducción del tiempo de ejecución sin descuidar los aspectos de precisión y esfuerzo de revisión, por ello, utilizan técnicas de comparación que permiten la agrupación de registros (Ej: Blocking, Sliding Window, Clustering…), asignándoles a cada uno de ellos un porcentaje de similitud con los valores introducidos.

Object Identification

La diferencia con lo anterior según [Batini, 2006], es que el término “object identification” es evolutivamente más complejo, ya que trabaja sobre datos del tipo de documentos XML donde se representan los objetos del mundo real.
Otros autores como Mattis Neiling (http://cis.cs.tu-berlin.de/~mneiling) utilizan el término de object identification como concepto global, donde se integran el record linkage y sorted neighborhood method como métodos para llevar a cabo la agrupación de registros que representan a la misma entidad. Podemos destacar entre sus trabajos [Neiling, 2003 (1)] y [Neiling, 2003 (2)].

Otras concepciones acerca del record linkage

Record matching, entity resolution y sorted neighborhood method son otras concepciones que habitualmente son empleadas por muchos autores para referirse a las técnicas empleadas para Object Identification (identificación de objetos) como podemos ver en [Verykios, 1999], [Cochinwala, 2001], [Lehti, 2005] o en la página del grupo de investigación SERF de Standford (http://infolab.stanford.edu/serf/).
El concepto de Integración de Datos (data integration) está un poco más alejado de los anteriores, aun y cuando se relaciona con la identificación de objetos. Su función se encuentra más centrada en la unión de información de registros que se encuentran referenciando a la misma entidad desde múltiples orígenes de datos independientes y heterogéneos. Podemos encontrar información y referencias en: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Chomicki:Jan.html.

Conclusiones

Este marco de trabajo, en conclusión puede servir para la búsqueda de duplicados en bases de datos, y sería una herramienta eficiente en la solución de la calidad de datos en diversas entes educativos, financieros y empresariales, para de esta forma mejorar la calidad, de la información, el desafío actual es poder probar todos estos conceptos teóricos en bases de datos reales, mismo que se hace necesario conseguir dicha información en las entidades ante mencionadas.

Trabajos futuros

Es necesario hacer la programación respectiva de este marco de trabajo, en el lenguaje de programación C#, mismo que será presentado en otro artículo, haciendo referencia a un estudio, y comparación de la calidad de los algoritmos de comparación de cadenas y de esta forma buscar el mejor rendimiento de los algoritmos.

Bibliografía

  1.  [Batini 2006] Batini, C., and Scannapieco, M. (2006). Data Quality: Concepts, Methodologies and Techniques. Springer Verlag.
  2. [Bilenko 2003] Bilenko, Mikhail; Raymond J. Mooney and William Weston Cohen and Pradeep Ravikumar and Stephen E. Fienberg (2003). "Adaptive Name Matching in Information Integration". IEEE Intelligent Systems 18 (5): 16--23.
  3. [Chatterjee 1991] Chatterjee, Abhirup; Arie Segev (1991). "Data Manipulation in Heterogeneous Databases". ACM SIGMOD Record 20 (4): 64--68.
  4. [Cochinwala 2001] M. Cochinwala and S. Dalal and A.K. Elmagarmid and V.S. Verykios, "Record Matching: Past, Present and Future",(2001) citeseer.ist.psu.edu/588173.html
  5. [Cohen 1998] Cohen , W. William (1998): The WHIRL Approach to Integration: An Overview in IIWeb 1998 (informal proceedings).
  6. [Erhard  2000] Erhard Rahm, Hong Hai Do. Data Cleaning: Problems and Current Approaches,  University of Leipzig, Germany, 2000
  7. [Fellegi 1969] Fellegi, Ivan Peter (dec 1969). "A theory for record linkage". Journal of the American Statistical Association 64 (328): 1183--1210.
  8. [Han 2011] Han, J., Kamber, M. Data Mining: Concepts and Techniques, 3a Edition, Morgan Kaufmann, 2011. ISBN  978-0123814791
  9. [Hernández 1998] Hernández, Mauricio Antonio; Salvatore Joseph Stolfo (jan 1998). "Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem". Data Mining and Knowledge Discovery 2 (1): 9--37.
  10.  [Jaro 1976 (2)] Jaro, Matthew A. (1976), UNIMATCH: A Record Linkage System: User's Manual, U.S. Bureau of the Census, Washington, D.C.
  11. [Jaro 1989] Jaro, Mathew A. (1989), "Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida," Journal of the American Statistical Association, 89, pp. 414-420.
  12. [Kimball 2004] Kimball, R., Caserta, J. The Data Warehouse ETL Toolkit, Wiley and Sons, 2004. ISBN 978-0764567575.
  13.  [Lehti 2005] Patrick Lehti, Peter Fankhauser, “A Precise Blocking Method for Record Linkage”, Data Warehousing and Knowledge Discovery, LNCS, Volume 3589/2005, 210-220, Springer Verlag, (2005).
  14. [Levenshtein 1965] Levenshtein, Vladimir I. (1965). "Binary Codes Capable of Correcting Deletions, Insertions and Reversals". Doklady Akademii Nauk SSSR 163 (4): 845--848.
  15.  [Needleman 1970] Needleman, Saul Ben; Christian Dennis Wunsch (mar 1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology 48 (3): 443--453.
  16.  [Neiling 2003 (1)] Mattis Neiling, Steffen Jurk: The Object Identification Framework. KDD03,Workshop on Data Cleaning, Record Linkage, and Object Consolidation. (extended version).
  17. [Neiling 2003 (2)] Mattis Neiling, Steffen Jurk, Hans-J. Lenz, and Felix Naumann: Object Identification Quality. Intl. Workshop onData Quality in Cooperative Information Systems, Siena, Italy, January 11-13, 2003.
  18. [Newcombe 1959]  Newcombe, Howard B.; James M. Kennedy and S.J. Axford and A.P. James (oct 1959). "Automatic Linkage of Vital Records". Science 130 (3381): 954--959.
  19. [Newcombe 1962]Newcombe, Howard B.; James M. Kennedy (nov 1962). "Record Linkage: Making Maximum Use of the Discriminating Power of Identifying Information". Communications of the ACM 5 (11): 563--566.
  20. [Newcombe 1967] Newcombe, Howard B. (may 1967). "Record Linking: The Design of Efficient Systems for Linking Records into Individual and Family Histories". American Journal of Human Genetics 19 (3): 335--359.
  21. [Newcombe 1988] Newcombe, Howard B. (1988). Handbook of Record Linkage. Oxford University Press.
  22.  [Qinlu 2010] Qinlu He, Zhanhuai Li, Xiao Zhang,Data deduplication techniques. Future Information Technology and Management Engineering (FITME), 2010 International Conference on  (Volume:1 )
  23.  [Russ 2009] Russ Fellows, Data De-Duplication –Why, When Where and How?, (October 14th, 2009), Evaluator Group.
  24.  [Tepping 1968] Tepping, Benjamin J. (dec 1968). "A Model for Optimum Linkage of Records". Journal of the American Statistical Association 63 (345): 1321--1332.
  25.  [Verykios, 1999] Vassilios S. Verykios, Ahmed K. Elmagarmid, and Elias N. Houstis, "Automating the approximate record matching process", Information Sciences 126 (2000), no. 1-4, 83--98. citeseer.ist.psu.edu/verykios99automating.html
  26. [Wang 1989] Wang, Y.R.;Madnick S.E.; Horton D.C.; Inter-database instance identification in composite information systems, MIT, Cambridge, MA, USA System Sciences, 1989. Vol.III: Decision Support and Knowledge Based Systems Track, Proceedings of the Twenty-Second Annual Hawaii International Conference on  (Volume:3 )
  27.  [Winkler 1990] Winkler, W. E. (1990), "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage,"Proceedings of the Section on Survey Research Methods,American Statistical Assn., pp. 354-359.
  28. [Winkler 1991] Winkler, William E. (1991), "An Application of the Fellegi-Sunter Model of Record Linkage to the 1990 U.S. Decennial Census", Statistical Research Report Series RR91/09 (U.S. Bureau of the Census, Washington, D.C.)
  29.  [Winkler 2006] Winkler, William E. (2006), "Overview of record linkage and current research directions", Statistical Research Report Series RRC2006/02 (U.S. Bureau of the Census, Washington, D.C.)

También conocido como data cleansing, data scrubbing, es el proceso de descubrimiento, corrección o eliminación de datos erróneos de una base de datos. El proceso de data cleansing permite identificar datos incompletos, incorrectos, inexactos, no pertinentes, etc. y luego substituir, modificar o eliminar estos datos sucios ("dirty data”). Además de ser un término utilizado en el proceso ETL, para diseñar Data Warehouse, ya que se encarga de la heterogeneidad Estructural y Léxica.

a Galeana.2eña Galeana.2