PDF de programación - Extracción de Conocimiento en Grandes Bases de Datos Utilizando Estrategias Adaptativas

Extracción de Conocimiento en

Grandes Bases de Datos Utilizando

Estrategias Adaptativas

Waldo Hasperué

UNIVERSIDAD NACIONAL DE LA PLATA

FACULTAD DE INFORMÁTICA

Tesis DocToral en ciencias informáTicas

Extracción de Conocimiento en

Grandes Bases de Datos Utilizando

Estrategias Adaptativas

Waldo Hasperué

Directores:

Ing. Armando De Giusti

Lic. Laura Lanzarini

La Plata, marzo de 2012

Hasperué, Waldo
Extracción de conocimiento en grandes bases de datos
utilizando estrategias adaptativas. - 1a ed. - La Plata: EDULP,
2014.
210 p.; 24x16 cm.

ISBN 978-987-1985-29-6

1. Informática. 2. Tesis Doctoral. I. Título.
CDD 004

Extracción de Conocimiento en Grandes Bases
de Datos utilizando Estrategias Adaptativas
Waldo Hasperué

Diagramación: Andrea López Osornio

Editorial de la Universidad Nacional de La Plata (Edulp)
47 N° 380 / La Plata B1900AJP / Buenos Aires, Argentina
+54 221 427 3992 / 427 4898
[email protected]
www.editorial.unlp.edu.ar

Edulp integra la Red de Editoriales Universitarias (REUN)

Primera edición, 2014
ISBN Nº 978-987-1985-29-6

Queda hecho el depósito que marca la Ley 11.723
©2014 - Edulp
Impreso en Argentina

Agradecimientos

A los dos amores de mi vida, Virginia y Sofía, quienes me brindaron su
apoyo en todo momento, me dieron ánimo para terminar este trabajo y
supieron, en este último tiempo, quedar en un segundo plano para que
pudiera terminar de escribir esta tesis.
A mis directores, Tito y Laura, quienes con sus comentarios, sugerencias
y valiosos consejos lograron que esta empresa llegara a su fin.

Índice

Resumen
Motivación
Desarrollos y aportes
Publicaciones derivadas de esta tesis doctoral

2.2.1. Limpieza y transformación



2.2.2. Exploración y selección

Capítulo 1. Introducción a la Minería de Datos
1. Minería de datos
1.1. Tipos de datos
1.2. Tipos de modelos
2. Extracción de conocimiento
2.1. Fase de integración y recopilación
2.2. Fase de selección, limpieza y transformación





2.3. Fase de minería de datos

2.3.1. Tareas predictivas
2.3.2. Tareas descriptivas

2.3.3. Técnicas


2.3.4. Aprendizaje inductive

2.3.5. Grandes bases de datos
2.4. Fase de evaluación e interpretación

2.4.1. Técnicas de evaluación







2.4.2. Medidas de evaluación de modelos

2.4.3. Interpretación y contextualización
2.5. Fase de difusión, uso y monitorización
3. Arboles de decisión

2.4.1.1. Validación simple
2.4.1.2. Validación cruzada con k pliegues
2.4.1.3. Bootstrapping

2.2.1.1. Discretización
2.2.1.2. Numerización
2.2.1.3. Normalización de rango: escalado y centrado




















15
15
16
19

21
21
24
26
26
28
29
30
32
32
33
33
34
36
37
38
40
40
41
42
42
42
42
43
44
44
46

3.1. Particiones
3.2. Criterio de selección de particiones
3.3. Poda y reestructuración
3.4. Extracción de reglas
4. Algoritmos evolutivos
5. Minado de datos incremental
5.1. Adaptabilidad del modelo
6. Toma de decisiones
7. Hiper-rectángulos
7.1. El uso de los hiper-rectángulos en minería de datos

2.1.1. Superposición sin datos involucrados
2.1.2. Superposición con datos de una clase
2.1.3. Superposición con datos de ambas clases

2.2.1. Sin datos involucrados
2.2.2. Con datos de una clase en la superposición
2.2.3. Con datos de ambas clases

Capítulo 2. Clasificación utilizando hiper-rectángulos.
Armado del modelo de datos y obtención de reglas
de clasificación
1. Hiper-rectángulos
1.1. Creación de hiper-rectángulos a partir de una base de datos
2. Superposiciones
2.1. Tipos de superposiciones



2.2. Eliminación de superposiciones



3. Índices
3.1. Índices de superposición
















3.1.1. Z1i – Proporción del ancho de la intersección de área

3.1.2. Z2i – Proporción del ancho del intervalo de la


3.1.3. Z3i – Proporción del ancho del intervalo del


3.1.4. Z4i – Proporción del ancho del intervalo del


3.1.5. Z5i – Desplazamiento del intervalo del subconjunto




de datos intersectados de un hiper-rectángulo en relación
al mínimo del intervalo de subconjunto de datos
participantes del otro hiper-rectángulo.

respecto al ancho del hiper-rectángulo

























intersección de datos con respecto al ancho del intervalo
del subconjunto de datos participante

subconjunto de datos intersectados en relación al ancho
del intervalo del subconjunto de datos participante

subconjunto de datos participantes en relación al
ancho de la superposición de área

47
49
50
51
52
55
56
57
58
59

61
62
64
66
68
68
69
71
73
75
76
77
78
80

81

81

83

84

85

















3.1.6. Z6i – Desplazamiento del intervalo del subconjunto




de datos intersectados de un hiper-rectángulo en
relación al máximo del intervalo de subconjunto de
datos participantes del otro hiper-rectángulo.

3.2.1. Ponderando por la cantidad de datos participantes








3.2.2. Ponderando los índices por otros criterios

3.2.1.1. Z1i
3.2.1.2. Z2i
3.2.1.3. Z3i
3.2.1.4. Z4i
3.2.1.5. Z5i
3.2.1.6. Z6i
3.2.1.7. Re-definición del cálculo de Ωi ponderado
por los pesos V





3.2. Índice de separabilidad Ω










3.3. Una estrategia de clasificación flexible
4. CLUHR 96
4.1. Inicialización del algoritmo

4.2. Eliminar todas las superposiciones








4.3. Finalizar con el armado del modelo de datos
4.4. Estructura del modelo de datos
4.5. Datos faltantes
4.6. Una metodología determinista
4.7. Limitaciones de CLUHR
5. Extracción de las reglas
5.1. Método greedy
6. Uso del modelo. Predicción
7. Intervención del experto

4.1.1. Detectar superposiciones iniciales

4.2.2.1. Método alternativo para la división de
hiper-rectángulos cuando hay datos de ambas clases
en la superposición

4.2.1. Calcular los índices Ω
4.2.2. Realizar el ajuste



4.2.3. Actualizar los hiper-rectángulos representativos

4.2.4. Detectar las nuevas superposiciones

mínimos












88
89
91
92
92
92
92
94
94

94
95
95

99
100
100
100
101

101

102
103
105
106
106
107
108
109
111
112
115

Capítulo 3. Adaptabilidad y actualización del modelo de datos 117
118
1. Adaptabilidad del modelo
119
1.1. Precondiciones
2. Actualización en línea
119

122

124
127

hiper-rectángulo

representante de otra clase

entre dos hiper-rectángulos

120
2.1.1. El nuevo dato está incluido en un único hiper-rectángulo 121
2.1.2. El nuevo dato está incluido en una superposición

2.1.3. El nuevo dato no está incluido en ningún


2.2.1. El dato está incluido en un hiper-rectángulo

2.2.2. El dato está incluido en un hiper-rectángulo


2.1. Agregando nuevos datos





2.2. Eliminando datos existentes




representante de su misma clase
2.3. Modificación de la clase de los datos




2.4. Sub-clasificando muestras
2.5. Realizando varios cambios simultáneamente
3. Actualizando reglas de clasificación
4. Intervención del experto
5. Análisis de rendimiento
5.1. Costo en hallar el hiper-rectángulo (u hoja)
5.2. Re-estructuración del hiper-rectángulo (u hoja)
5.3. Conclusiones

2.3.1. El dato está incluido en un hiper-rectángulo de la

2.3.2. El dato está incluido en un hiper-rectángulo que


misma clase a la cual cambia el dato

representa a otra clase distinta







1.2.1. Descripción del ejemplo
1.2.2. Resultado

Capítulo 4. Resultados y Comparaciones
1. Ejemplos ficticios en 2D
1.1. Configuración de la estrategia
1.2. Dos clases separadas


1.3. Una clase entremedio de otra
1.3.1. Descripción del ejemplo


1.3.2. Resultado
1.4. Una clase envolviendo parcialmente a otras dos


1.5. Envolturas sucesivas


1.6. Tres clases con varias zonas de superposición


1.4.1. Descripción del ejemplo
1.4.2. Resultado

1.5.1. Descripción del ejemplo
1.5.2. Resultado

1.6.1. Descripción del ejemplo

























128

128
130

131

131
132
133
135
136
137
139
139
140

143
144
145
146
146
146
147
147
147
148
148
149
150
150
150
152
152

1.6.2. Resultado





































1.7.1. Descripción del ejemplo
1.7.2. Resultado

1.9.1. Descripción del ejemplo
1.9.2. Resultado

1.11.1. Descripción del ejemplo
1.11.2. Resultado

1.12.1. Descripción del ejemplo
1.12.2. Resultado

1.10.1. Descripción del ejemplo
1.10.2. Resultado

152
154
154
154
156
156
156
157
157
157
158
158
158
159
159
160
161
161
161
162
163
165
165
2.1.1. Ecoli data set
165
2.1.2. Glass data set
165
2.1.3. Haberman's Survival data set
165
2.1.4. Image segmentation data set
166
2.1.5. Ionosphere data set
166
2.1.6. Iris data set
166
2.1.7. Liver disorders data set
2.1.8. Pima indians diabetes data set
166
2.1.9. Connectionist bench (Sonar, mines vs. rocks) data set 166
2.1.10. Statlog (Vehicle silhouettes) data set
167
2.1.11. Connectionist bench

2.1.12. Wine data set
2.1.13. Breast cancer Wisconsin (Original) data set
2.1.14. Forest Covertype data set


1.7. Doble espiral


1.8. Una clase que encierra a otra
1.8.1. Descripción del ejemplo


1.8.2. Resultado
1.9. Una clase que encierra a otra de manera más ajustada


1.10. División en diagonal


1.11. Dos clases compartiendo un sector del espacio


1.12. Mezcla total de dos clases


1.13. Resumen
2. Bases de datos del repositorio UCI
2.1. Bases de datos usadas















2.2. Resultados
3. Comparaciones con otros métodos
3.1. C4.5
3.2. EHS-CHC
3.3. PSO/ACO2

(Vowel recognition – Deterding data) data set

167
167
167
167
167
169
169
171
171

3.4. Resultados
3.5. Análisis de rendimiento
3.5.1. C4.5

3.5.2. EHS-CHC

3.5.3. PSO/ACO2


3.5.4. Resultados
4. Minería incremental






Capítulo 5. Discusión y trabajo a futuro
1. CL