PDF de programación - Reducción de Datos basada en Selección Evolutiva de Instancias para Minería de Datos

Universidad de Granada

Departamento de Ciencias de la Computación

e Inteligencia Artificial

Reducción de Datos basada en

Selección Evolutiva de Instancias

para Minería de Datos

Tesis Doctoral

José Ramón Cano de Amo

Granada, Julio de 2004

Universidad de Granada

Reducción de Datos basada en

Selección Evolutiva de Instancias

para Minería de Datos

MEMORIA QUE PRESENTA

José Ramón Cano de Amo

PARA OPTAR AL GRADO DE DOCTOR EN INFORM ÁTICA

Julio de 2004

DIRECTORES

Francisco Herrera Triguero y Manuel Lozano Márquez

Departamento de Ciencias de la Computación

e Inteligencia Artificial

La memoria titulada “Reducción de Datos basada en Selección Evolutiva
de Instancias para Minería de Datos”, que presenta D. José Ramón Cano de Amo
para optar al grado de doctor, ha sido realizada dentro del programa de doctorado
“Diseño, Análisis y Aplicaciones de Sistemas Inteligentes” del Departamento de
Ciencias de la Computación e Inteligencia Artificial de la Universidad de Granada
bajo la dirección de los doctores D. Francisco Herrera Triguero y D. Manuel
Lozano Márquez.

Granada, Julio de 2004

El Doctorando

Los Directores

Fdo: José Ramón Cano de Amo

Fdo: F. Herrera Triguero y M. Lozano Márquez

Tesis Doctoral parcialmente subvencionada por la Comisión

Interministerial de Ciencia y Tecnología con el proyecto

TIC2002-04036-C05-01

CICYT

TIC2002-04036-C05-01

Agradecimientos

Esta memoria esta dedicada a todas aquellas personas sin las cuales no hubiera

sido posible.

Ante todo a mis padres, por que todo lo que se ha conseguido ha sido gracias
a su cariño y apoyo y de los que estoy muy orgulloso. Esta memoria es por y para
vosotros.

Si en el ámbito familiar he tenido suerte por el aliento y ánimo recibidos, ésta
no ha sido menor con respecto a mis directores de tesis. Ambos, tanto Francis-
co Herrera como Manuel Lozano, han sido capaces de, mediante su paciencia,
dedicación e inestimables consejos, ayudarme a llevar a buen puerto este viaje.
Por supuesto no me podría olvidar de todas aquellas personas que han estado
a mi lado, y no ha sido fácil, durante todo este camino. Muchas gracias a Rafael
Alcalá por toda la ayuda proporcionada, y así como Oscar Cordón y Jorge Casillas
por servirme de modelo. Gracias Iñaki por las pequeñas charlas telefónicas.

Quiero así mismo expresar mi gratitud a aquellos compañeros que me han
acompañado en mi peregrinar andaluz y me han suavizado los rigores de la dis-
tancia. De entre mis onubenses favoritos citar a Francisco Márquez, quién me
hizo sentir como en casa, muchas gracias. Pero no fue el único, allí estuvieron
Antonio Peregrín, Alfredo Sainz, Estefanía Cortés y el más recreativo, Manuel de
la Villa. De Córdoba, citar a Sebastián Ventura por su cariñoso recibimiento y
su comprensión. Y de Jaén, a mis compañeros Mari Lina y Jose María por hacer
agradable el trabajo diario.

No quiero dejar de mencionar a los amigos por lo vivido y lo que nos queda
por vivir: Fernando, Pedro, Moncho, Manolo, y al resto del equipo de Linares,
que han reacogido al hijo pródigo.

Mi agradecimiento a todas aquellas personas que no por no citarlas han sido

menos importantes para el término de esta memoria. Quiero dedicaros el esfuerzo
de este nuestro trabajo.

GRACIAS A TODOS

Índice

Introducción

A
B
C

Planteamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Extracción de Conocimiento, Reducción de Datos y

Selección de Instancias
1.1.
1.2. El Proceso de Descubrimiento de Conocimiento en Bases de Datos

Introducción a la Extracción de Conocimiento . . . . . . . . . . . .

1
1
4
5

7
8

o KDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Minería de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4. Preparación de los Datos . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5. Reducción de Datos
. . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1. Selección de Características . . . . . . . . . . . . . . . . . . 17
1.5.2. Selección de Instancias . . . . . . . . . . . . . . . . . . . . . 22
1.5.3. Discretización de Características
. . . . . . . . . . . . . . . 22
1.5.4. Agrupamiento de Datos . . . . . . . . . . . . . . . . . . . . 25
1.5.5. Compactación de Datos . . . . . . . . . . . . . . . . . . . . 27
1.6. Selección de Instancias . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.7. Selección de Prototipos
. . . . . . . . . . . . . . . . . . . . . . . . 31

ix

x

ÍNDICE

1.8. Algoritmos Evolutivos y la Extracción de Conocimiento . . . . . . 33
1.8.1. Algoritmos Evolutivos . . . . . . . . . . . . . . . . . . . . . 33
1.8.2. Algoritmos Evolutivos y Reducción de Datos
. . . . . . . . 35
1.8.3. Algoritmos Evolutivos y Aprendizaje . . . . . . . . . . . . . 37

2. Selección Evolutiva de Instancias para la Reducción de Datos
2.1. Estrategias Seguidas en Selección de Instancias: Clasificación ba-

41

sada en Prototipos y Selección de Conjuntos de Entrenamiento . . 42
2.2. Técnicas No Evolutivas de Selección de Instancias
. . . . . . . . . 44
2.3. Algoritmos Evolutivos Aplicados a Selección de Instancias . . . . . 47
2.3.1. Algoritmos Evolutivos Utilizados . . . . . . . . . . . . . . . 48
2.3.2. Esquema de Representación . . . . . . . . . . . . . . . . . . 52
2.3.3. Función Objetivo . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4. Metodología de Experimentación . . . . . . . . . . . . . . . . . . . 54
. . . . . . . . . . . . . . . . . . . . . . 54
. . . . 57
. . . . . . . . . . . . . . . . . . . . . . . . . 58
. . . . . . . . . . . 58
2.5.1. Estructura de las Tablas de Resultados
2.5.2. Resultados y Análisis en Clasificación . . . . . . . . . . . . 61

2.4.1. Conjuntos de Datos
2.4.2. Validación Cruzada y Parámetros de los Algoritmos

2.5. Estudio Experimental

2.5.2.1. Resultados en Clasificación para Conjuntos de Ta-

maño Pequeño . . . . . . . . . . . . . . . . . . . . 61

2.5.2.2. Resultados en Clasificación para Conjuntos de Ta-

maño Mediano . . . . . . . . . . . . . . . . . . . . 62
2.5.2.3. Análisis de los Resultados en Clasificación . . . . 64
2.5.3. Resultados en Selección de Conjuntos de Entrenamiento . . 65

2.5.3.1. Resultados en Selección de Conjuntos de Entre-

namiento para Conjuntos de Tamaño Pequeño . . 65

2.5.3.2. Resultados en Selección de Conjuntos de Entre-

namiento para Conjuntos de Tamaño Mediano . . 67

ÍNDICE

xi

2.5.3.3. Análisis de Resultados en Selección de Conjuntos

2.6. Análisis de los Algoritmos Evolutivos en Selección de Prototipos

de Entrenamiento . . . . . . . . . . . . . . . . . . 68
. 69
2.6.1. Tiempos de Ejecución . . . . . . . . . . . . . . . . . . . . . 70
2.6.2. Análisis del Mecanismo de Selección de los Algoritmos Evo-

lutivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.7. Comentarios Finales . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.A Tablas de Resultados de Conjunto de Datos de Tamaño Pequeño

en Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

2.B Tablas de Resultados de Conjunto de Datos de Tamaño Mediano

en Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

2.C Tablas de Resultados de Conjunto de Datos de Tamaño Pequeño

en Selección de Conjuntos de Entrenamiento . . . . . . . . . . . . . 90

2.D Tablas de Resultados de Conjunto de Datos de Tamaño Mediano

en Selección de Conjuntos de Entrenamiento . . . . . . . . . . . . . 100

3. Selección Evolutiva Estratificada de Instancias en Conjuntos de

103
Datos de Gran Tamaño Aplicada a Clasificación
3.1. El Problema de Escalado en Selección de Prototipos
. . . . . . . . 104
3.2. Estrategia de Estratificación . . . . . . . . . . . . . . . . . . . . . . 106
3.3. Selección de Prototipos Evolutiva Estratificada . . . . . . . . . . . 107
3.4. Metodología de Experimentación . . . . . . . . . . . . . . . . . . . 108
. . . . . . . . . . . . . . . . . . . . . . 108
3.4.1. Conjuntos de Datos
3.4.2. Algoritmos y Parámetros
. . . . . . . . . . . . . . . . . . . 109
3.4.3. Estratificación y Particiones . . . . . . . . . . . . . . . . . . 110
. . . . . . . . . . . . . . . . . . . . . . . . . 112
. . . . . . . . . . . . 112
3.5.1. Estructura de la Tabla de Resultados
. . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.5.2. Resultados
3.5.3. Análisis de Resultados . . . . . . . . . . . . . . . . . . . . . 118
3.6. Comentarios Finales . . . . . . . . . . . . . . . . . . . . . . . . . . 121

3.5. Estudio Experimental

xii

ÍNDICE

4. Selección de Conjuntos de Entrenamiento Evolutiva Estratifica-
da en Conjuntos de Datos de Gran Tamaño para la Generación
de Modelos Predictivos y Descriptivos
123
4.1. Aprendizaje de Modelos Predictivos y Descriptivos . . . . . . . . . 124
4.1.1. Modelos Predictivos: Reglas de Clasificación . . . . . . . . . 125
. . 126
4.1.2. Modelos Descriptivos: El Descubrimiento de Subgrupos

4.2. Selección de Conjuntos de Entrenamiento Evolutiva Estratificada

para la Extracción de Modelos Predictivos y Descriptivos

. . . . . 131

4.3. Estudio Experimental de los Algoritmos de Selección de Conjuntos

de Entrenamiento para la Extracción de Modelos . . . . . . . . . . 133
4.3.1. Metodología de Experimentación . . . . . . . . . . . . . . . 133
4.3.1.1. Conjuntos de Datos . . . . . . . . . . . . . . . . . 133
4.3.1.2. Algoritmos y Parámetros . . . . . . . . . . . . . . 134
4.3.1.3. Estratificación y Particiones
. . . . . . . . . . . . 135
4.3.2. Estructura de las Tablas de Resultados
. . . . . . . . . . . 137
4.3.3. Resultados y Análisis de los Modelos Predictivos . . . . . . 138
4.3.4. Resultados y Análisis de los Modelos Descriptivos para Des-

cubrimiento de Subgrupos . . . . . . . . . . . . . . . . . . . 143

4.4. Anális