Algoritmo MDR
Extracción de registros de
datos
Christian Marmolejo Gómez
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Conclusiones
INTRODUCCIÓN
 Wrapping
 Extracción de información
 Información estructurada
 Aproximaciones generalistas, malos
resultados
 Cambio de técnica
¿QUÉ ES UN REGISTRO DE DATOS?
 Agrupa datos de un mismo objeto
 Estructura HTML regular
 Suelen mostrarse en listas
 Representación HTML de una fila en una
BD
UN EJEMPLO DE RD
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Conclusiones
DEFICIENCIAS
 Identificación visual de patrones y
programación
- No escalable a muchas páginas
 Cierta automatización + técnicas de
aprendizaje automático
- Etiquetado manual de regiones de la
página (gran intervención humana)
DEFICIENCIAS
 Heurísticas y conocimiento del dominio
- Costoso de conseguir
 Otros: Patricia tree, inducción de
gramáticas, clustering…
- Resultados pobres
UN PROBLEMA COMÚN
 No extraen RDs no contiguos
Columnas de tablas
parte1 de objeto1, parte1 de objeto2,
parte2 de objeto1, parte2 de objeto2
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Conclusiones
CARACTERÍSTICAS DE MDR
 Suposiciones empíricas
 Automático
 Etiquetas y estructuras, no texto
 Zonas similares
 RDs contiguos y no contiguos
 RDs anidados
DOS OBSERVACIONES CLAVE
1. Región de datos
2. Hijos del mismo padre
DOS OBSERVACIONES CLAVE
 5 nodos TR
debajo del nodo
TBODY
 Subárboles
debajo de TBODY
forman una región
de datos
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Árbol de etiquetas
Extracción de regiones de datos
Identificación de RDs
Conclusiones
PASOS DE MDR
1. Tag tree o árbol de etiquetas.
2. Extraer regiones de datos de la página.
3. Identificar los RDs.
ÁRBOL DE ETIQUETAS
 Un par de etiquetas, un nodo.
 Un par de etiquetas anidadas, un nodo
hijo.
1. Preprocesamiento del código HTML
2. Construcción del árbol
Inconvenientes: Errores en el código.
ÁRBOL DE ETIQUETAS
ÁRBOL DE ETIQUETAS
 Información visual de los navegadores
1. Subsistema de parsing y rendering de un
navegador  coordenadas
2. Relación de contenido  árbol
MDR2
ÁRBOL DE ETIQUETAS
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Árbol de etiquetas
Extracción de regiones de
datos
Identificación de RDs
Conclusiones
UN PAR DE DEFINICIONES
 Nodo generalizado: r nodos que
cumplen:
1. Tienen todos el mismo padre
2. Son adyacentes
Un RD, uno o varios hermanos.
Un nodo generalizado, uno o varios RDs.
UN PAR DE DEFINICIONES
 Región de datos: dos o más nodos
generalizados que cumplen:
1. Tienen todos el mismo padre
2. Tienen todos la misma longitud
3. Son todos adyacentes
4. La distancia de edición normalizada
entre ellos es inferior a un umbral
UN PAR DE DEFINICIONES
CÁLCULO DE LA EDIT DISTANCE
 Comparar nodos
1. Comienzo primer nodo generalizado
2. Longitud de los nodos generalizados
 Probar combinaciones
 Cadena de etiquetas del subárbol
 Almacenamos la edit distance
 O(NK)
CÁLCULO DE LA EDIT DISTANCE
 Edit distance
Compara el parecido de dos cadenas
Mutaciones de cadena origen a final
Gran ahorro computacional
CÁLCULO DE LA EDIT DISTANCE
DETERMINACIÓN DE REGIONES DE DATOS
 Identificación de regiones de datos
Recorrido en profundidad
Umbral fijado
Adición de nodos generalizados a la
región de datos actual
Región de datos dentro de otra 
mayor
Nodo generalizado dentro de otro 
menor
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Árbol de etiquetas
Extracción de regiones de datos
Identificación de RDs
Conclusiones
IDENTIFICACIÓN DE RDs
 Muchos tipos de nodos generalizados
 Contiguos, múltiples, no contiguos y sin
región de datos
 Parecidos entre ellos
 Mismo nivel o uno inferior
 Ciertas heurísticas
IDENTIFICACIÓN DE RDs
NODOS GENERALIZADOS
CON UN COMPONENTE
 Una columna, un RD
 Una fila entera, un RD
(tabla de datos o un
solo bloque)
IDENTIFICACIÓN DE RDs
NODOS GENERALIZADOS
MÚLTIPLES
 Nodos hijos no parecidos
o distinto número de
hijos
 Un nodo generalizado,
un RD
 Si no  RD no contiguo
IDENTIFICACIÓN DE RDs
RD NO CONTIGUO:
CASO 1
 Hijos parecidos
entre ellos pero no a
otros
 Mezcla de nodos
IDENTIFICACIÓN DE RDs
RD NO CONTIGUO:
CASO 2
 Regiones
adyacentes no
similares
 Mezcla de nodos
 Arriesgado
IDENTIFICACIÓN DE RDs
RDs SIN REGIÓN DE
DATOS
 Impar, fila no
parecida
 No forma región
 Comparación de
cadenas
Introducción
Sistemas actuales
Características del algoritmo
Pasos del algoritmo
Conclusiones
CONCLUSIONES
 Propósito específico
 Sin intervención humana
 Efectivo
 Rápido
 Mayor casuística
 Abierto a mejoras
 Punto de partida a otras técnicas
CONCLUSIONES
 Deficiencias:
 Subjetivo
 Orientado a tablas
Gracias
Christian Marmolejo Gómez
Más información:
http://www.cs.uic.edu/~liub/publications/kd
d2003-dataRecord.pdf
Descargar

Algoritmo MDR - The Distributed Group