FiVaTech:
Extracción de datos
Web a partir de
plantillas de páginas
Antonio R. Gómez Sotelo
Índice
Introducción
Algoritmo
Experimentos
Conclusiones
Índice
Introducción
Algoritmo
Experimentos
Conclusiones
Introducción
 Generación de Páginas Web:
Datos
Plantilla
Páginas Web
Introducción
 Definición 1: Datos Estructurados
1. Tipo Básico β = Cadena de tokens.
2. Listas ordenadas T=< T1, T2, ..., Tn>.
a. Tupla  <T>
b. Opcional  (T)?
c. Conjunto  {T}
d. Disyunción  T1| T2| ...| Tn
Introducción
A
Ejemplo:
{2-set}
<2-tuple>
{1-set}
(1-optional)?
Br a
D
br
G
br span
C
Br a
tr
|
td
br
G
D
F
br span
Now $7.50
E
tr
|
td
|
table
|
tr
|
td
Product_2
br
Save 5%
Now $3.79
Product_1
β
C
B
tr
|
td
Feature 2_2
β
F
Feature 2_1
<2-tuple>
β
tr
|
td
|
table
|
tr
|
td
Feature 1_1
β
B
Html
|
Body
|
table
{<“Product_1”, <“now $3,79”, “save 5%”>>, {“Feature1_1”},
<“Product_2”, <“now $7,50”, >>, {“Feature1_1”, “Feature2”}}
br
G
Introducción
 Características de FiVaTech
- Entrada: Árboles DOM de páginas Web.
- Objetivo: Deducir la plantilla y el esquema de datos
del sitio Web.
- Modo: Combinando múltiples árboles DOM
- Automático
- Problema: ¿Cómo fusionar múltiples árboles al mismo
tiempo?
- Solución: Tratar árboles como cadenas.
Árbol patrón.
Índice
Introducción
Algoritmo
Experimentos
Conclusiones
Algoritmo
Algoritmo
 Suposiciones Iniciales:
1. Nodos internos  Pertenecen a plantilla
 Datos en nodos hojas
2. Toda instancia de un conjunto  mismo nodo padre
Algoritmo
 Pasos:
1. Tomar Raíz común
2. Reconocimientos nodos iguales
3. Expandir
3.1 Alineación de la matriz par
3.2 Extracción de Patrones
3.3 Fusionar nodos opcionales
4. Extraer plantilla y esquema
Crear Árbol patrón
Algoritmo (Paso 1)
 1. Tomar nodo raíz común:
Trivial  Tomar R = <html>
Árbol vacío
Paso 1.
R
Algoritmo (Paso 2)
 2. Identificación nodos iguales:
Comparar si dos nodos (con la misma raíz) son
similares  Distancia de edición
Umbral d  Asignar símbolo a cada subárbol (nodo).
Algoritmo (Paso 3)
 3. Expandir:
- Hacer los siguientes 3 pasos por cada nodo interno n.
- De forma recursiva.
3.1 Alineación de la matriz par
3.2 Extracción de Patrones
3.3 Fusionar nodos opcionales
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par:
- Crear matriz de nodos:
M
p
p
a
b
c
d
b
a
c
b
c
d
b
e
c
d
a
p
e
b
c
b
c
d
e
1
a
a
a
2
b
b
b
3
c
c
c
4
d
d
b
5
b
e
c
6
c
d
7
b
e
8
c
9
d
10
e
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
row = 1
Mientras M no alineada
Mientras filaNoAlineada (row, M)
Obtener shiftColumn y shiftLength
Desplazar (row, shiftColumn,shiftLength,M)
row ++
childList = alignmentResult
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
- Conceptos:
- Matriz Alineada
- Fila alineada
- shiftColumn  nodo nrc
- shiftLength
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
- Selección de shiftColumn y shiftLength:
- span (nrc) = ciclo de máxima longitud (sin rep.) + 1
1, si (r-rup) > span (nrc)
- checkSpan (nrc) = 0, si (r-rup) = span (nrc)
-1, si (r-rup) < span (nrc)
1, en otro caso
M[r][c] = M[up][c’] ?
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
M
p
p
a
b
c
d
b
a
c
b
c
d
b
e
c
d
a
p
e
b
c
b
c
d
span(b)= span(c)= span(d)= 3
span(a)= span(e)= 0  nodos libres
checkSpan(n41) = checkSpan(n42)=1
e
1
a
a
a
2
b
b
b
3
c
c
c
4
d
d
b
5
b
e
c
6
c
d
7
b
e
8
c
9
d
10
e
checkSpan (n43) = -1  r-rup = 4 – 2 = 2 < 3 (span b)
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
- Selección de shiftColumn y shiftLength:
- Una vez tenemos span y checkSpan de los nodos,
- Aplicar Reglas (en orden):
R1 - izq. checkSpan = -1  shiftLength = 1
R2 - checkSpan = 1 y M[r][c]=M[rdown][c’] 
 shiftLength = rdown - r
R3 – R1 y R2 fallan  Dividir fila en 2 partes
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
Ej.
M
Filas 1, 2, 3  Alineadas
M
1
a
a
a
1
a
a
a
2
b
b
b
2
b
b
b
3
c
c
c
3
c
c
c
4
d
d
b
4
d
d
-
5
b
e
c
5
b
e
b
6
c
d
6
c
c
7
b
e
7
b
d
8
c
8
c
e
9
d
9
d
10
e
10
e
Fila 4: span(d) = 3
span(b) = 3
checkSpan(n41) = 1
checkSpan(n42)=1
checkSpan (n43) = -1  r-rup =
=4 – 2 = 2 < 3
Aplicar R1 sobre n43
Algoritmo (Paso 3.1)
 3.1 Alineación Matriz Par :
Ej.
M
ChildList
M
M
1
a
a
a
1
a
a
a
1
a
a
a
2
b
b
b
2
b
b
b
2
b
b
b
3
c
c
c
3
c
c
c
3
c
c
c
4
d
d
b
4
d
d
-
4
d
d
-
5
b
e
c
5
b
e
b
5
b
-
b
6
c
d
6
c
c
6
c
-
c
d
7
-
-
d
e
8
b
-
-
d
9
c
-
-
e
10
d
-
-
11
e
e
e
7
8
9
10
b
c
d
e
e
7
8
9
10
b
c
…
a
b
c
d
b
c
d
b
c
d
e
Algoritmo (Paso 3.2)
 3.2 Extracción Patrones Repetitivos :
- Descubrir patrones repetitivos  datos Tipo conjunto
- Patrones anidados dentro de otros.
- Desde longitud pequeña a longitud grande.
- Ej. abcdbcdbcde  abcde + nodo padre virtual
tipo conjunto bcd
Algoritmo (Paso 3.3)
 3.3 Agrupar nodos opcionales :
- Vector ocurrencia  (b1,b2,…, bn)
- Regla:
1. nodos adyacentes mismo vect. ocurrencia o comp.
V(a)=(1,1,1)
V(b) = (1,1,1,1,1,1)
p
p
a
b
c
d
b
a
c
b
c
d
b
e
c
d
a
p
e
b
c
b
V(d) = (1,0,1,1,0,1)
c
d
e
Algoritmo (Ejemplo)
- b4 y 2º asterisco mismo vector de ocurrecia  nodo
virtual común
Algoritmo (Paso 4)
 4. Detección Esquema de Datos :
- Pasos anteriores: Detección datos tipo básico,
conjuntos y opcionales.
- Paso actual: Centrarnos en detección de tuplas y
obtener el esquema común.
- Ignorar datos no variantes.
- Cada nodo interno no virtual  Considerar para
Tupla
Algoritmo (Paso 4)
 4. Detección Esquema de Datos :
<“database”, { <Johan,7>}>
<“data mining”, { <Jeff,5>, <Jane>}>
Índice
Introducción
Algoritmo
Experimentos
Conclusiones
Experimentos
1. FiVaTech como extractor de esquema
2. FiVaTech como extractor de SRRs
Nota: Siempre 2 ó 3 páginas web como entrada
Experimentos
1. FiVaTech como extractor de esquema
Experimentos
1. FiVaTech como extractor de SRRs
Índice
Introducción
Algoritmo
Experimentos
Conclusiones
Conclusiones
 Combinar múltiples árboles DOM.
 No supervisado.
 Nuevo algoritmo alineación cadenas (datos
opcionales y datos tipo conjunto).
 Fácil extracción del esquema y la plantilla de un
sitio Web.
 Eficiencia  2 o 3 páginas Web como entrada
¡Gracias!
¿Preguntas?
Descargar

Introduction to the GAIA methodology