PDF de programación - MEJORAS EN EFICIENCIA Y EFICACIA DE ALGORITMOS EVOLUTIVOS PARA APRENDIZAJE SUPERVISADO

MEJORAS EN EFICIENCIA Y EFICACIA

DE ALGORITMOS EVOLUTIVOS PARA

APRENDIZAJE SUPERVISADO

DEPARTAMENTO DE LENGUAJES Y SISTEMAS INFORMÁTICOS

Memoria del periodo de investigación
presentada por D. Raúl Giráldez Rojo
para optar al Diploma de Estudios Avanzados

Directores: Dr. D. José C. Riquelme Santos
Dr. D. Jesús S. Aguilar Ruiz

Sevilla, Septiembre de 2003

D. José Cristóbal Riquelme Santos, Profesor Titular de Universidad adscrito al área de

Lenguajes y Sistemas Informáticos,

CERTIFICA QUE

D. Raúl Giráldez Rojo, Ingeniero en Informática por la Universidad de Sevilla, ha realizado
bajo mi supervisión el trabajo de investigación titulado:

Mejoras en Eficiencia y Eficacia de Algoritmos Evolutivos

para Aprendizaje Supervisado

Una vez revisado, autorizo la presentación del mismo como Memoria del Periodo de

Investigación al tribunal que habrá de valorarlo.

Fdo. D. José C. Riquelme Santos
Profesor Titular de Universidad adscrito
Área de Lenguajes y Sistemas Informáticos

Agradecimientos

A mis directores de tesis, D. José C. Riquelme Santos y D. Jesus S. Aguilar Ruiz, para

mí, Pepe y Jesús, por iniciarme en el que hoy es mi trabajo y por confiar en mí en todo

momento. A Pepe, por ofrecerme gratuitamente su experiencia, tanto en el campo de la

investigación como en el de la docencia. A Jesús, por su continuo apoyo y no dejar que me

hundiera en los peores momentos.

A D. Miguel Toro Bonilla, ejemplo de persona y de profesional. Sus palabras siempre

me han transmitido tranquilidad.

A Paco, mi vecino más cercano en todos los sentidos, por su calidad como amigo y su

ayuda en el transcurso de mi corta carrera docente e investigadora.

A mis compañeros de investigación, Roberto, Alicia y Daniel, por su colaboración

desinteresada en esta investigación.

A todos mis compañeros del Departamento de Lenguajes y Sistemas Informáticos, Joa-

quín, José Luis, Toñi, Octavio, Fernando, David, Bea, y un largo etcétera, por hacerme

sentir cada día miembro de esta gran familia.

A mis padres, Antonio y María del Carmen, por su enorme sacrificio y constante estí-

mulo al lo largo de toda mi vida.

Y por último, aunque no con menor importancia, a Alicia, por su paciencia y infinita

generosidad.

Raúl Giráldez
Sevilla, Septiembre de 2003

Índice General

1 Introducción

1.1 Planteamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Aportaciones originales . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Relacionadas con la discretización . . . . . . . . . . . . . . . . . .
1.3.2 Relacionadas con la evaluación eficiente . . . . . . . . . . . . . . .
1.3.3 Relacionadas con la codificación genética . . . . . . . . . . . . . .
1.3.4 Otras publicaciones . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Proyectos de investigación . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Organización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2
5
5
6
6
6
7
9

2 Minería de Datos y KDD

11
. . . . . . . . . . . . 12
2.1 Descubrimiento de Conocimiento en Bases de Datos
2.2 Marco de trabajo y Definiciones . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Representación del Conocimiento . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Representación Proposicional
. . . . . . . . . . . . . . . . . . . . 19
2.3.2 Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Reglas de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.4 Reglas Difusas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Preparación de los Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 Depuración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Transformación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

v

vi

ÍNDICEGENERAL

2.4.3 Reducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.4.4 Discretización . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5 Métodos de Aprendizaje Supervisado . . . . . . . . . . . . . . . . . . . . 38

2.5.1 Técnicas Estadísticas . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.5.2 Vecino Más Cercano . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.5.3

2.5.4

Inducción de Árboles de Decisión . . . . . . . . . . . . . . . . . . 41

Inducción de Reglas de Decisión . . . . . . . . . . . . . . . . . . . 48

2.5.5 Aprendizaje de Reglas Mediante Algoritmos Genéticos . . . . . . . 50

2.6 Medidas de Rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.6.1

Precisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.6.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.6.3 Métodos de Validación . . . . . . . . . . . . . . . . . . . . . . . . 52

3 Aprendizaje Evolutivo

55

3.1 Conceptos de Computación Evolutiva . . . . . . . . . . . . . . . . . . . . 56

3.2 Reglas mediante Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . 59

3.2.1 GABIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2.2 GIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3.2.3 GASSIST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.2.4

SIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.3 COGITO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.3.1 Codificaciones

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.3.2 Representaciones de las reglas . . . . . . . . . . . . . . . . . . . . 77

3.3.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4 HIDER

85

4.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

4.2 Representación del conocimiento . . . . . . . . . . . . . . . . . . . . . . . 87

4.2.1 Árboles de decisión vs. reglas jerárquicas . . . . . . . . . . . . . . 88

4.3 Discretización Supervisada No Paramétrica . . . . . . . . . . . . . . . . . 90

ÍNDICEGENERAL

vii

4.4 Codificación Natural

4.3.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3.2 Conclusiones sobre USD . . . . . . . . . . . . . . . . . . . . . . . 100
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.4.1
Individuo Natural . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4.2 Reducción del espacio de búsqueda . . . . . . . . . . . . . . . . . 110
4.4.3 Operadores Genéticos Naturales . . . . . . . . . . . . . . . . . . . 112
4.4.4 Evaluación de individuos naturales . . . . . . . . . . . . . . . . . . 127
4.5 Estructura de Evaluación Eficiente . . . . . . . . . . . . . . . . . . . . . . 129
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.5.1 EES Híbrida
4.5.2 EES Natural
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.5.3 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.6 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.6.1
Inicialización de la población . . . . . . . . . . . . . . . . . . . . 148
4.6.2
Función de Evaluación . . . . . . . . . . . . . . . . . . . . . . . . 148
4.6.3 Reemplazo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.7 Poda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.8 Conclusiones

5 Pruebas

153
5.1 Rendimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
. . . . . . . . . . . . . . 155
5.1.1 Eficacia: HIDER versus C4.5/C4.5Rules
5.1.2 Eficiencia: HIDER versus COGITO . . . . . . . . . . . . . . . . . 161
5.2 Análisis de influencia de la Poda . . . . . . . . . . . . . . . . . . . . . . . 165
5.3 Conclusiones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

6 Conclusiones y Trabajos Futuros

6.1 Conclusiones
6.2 Trabajos Futuros

169
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

Bibliography

173

viii

ÍNDICEGENERAL

Índice de Figuras

2.1 Esquema General de KDD (Knowledge Discovery in Databases) . . . . . . 14
2.2 Fase de Minería de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Árboles de decisión: Paralelo vs. Oblicuo. . . . . . . . . . . . . . . . . . . 21

2.4 Reglas de Decisión. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5 Reglas con excepciones (RDR).

. . . . . . . . . . . . . . . . . . . . . . . 24

2.6 Conjunto de Reglas Jerárquicas de Decisión. . . . . . . . . . . . . . . . . . 25

2.7 Ejemplo de Reglas Jerárquicas de Decisión.

. . . . . . . . . . . . . . . . . 26

2.8 Selección de Atributos.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1 Fenotipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.2 Codificación en GABIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.3 Aprendizaje de reglas por SIA [161]. . . . . . . . . . . . . . . . . . . . . . 69

3.4 Codificación Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.5 Ejemplo de codificación híbrida

. . . . . . . . . . . . . . . . . . . . . . . 76

3.6 Ejemplo de codificación indexada . . . . . . . . . . . . . . . . . . . . . . 78

3.7 Regla Oblicua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.8 Pseudocódigo de COGITO.

. . . . . . . . . . . . . . . . . . . . . . . . . . 81

3.9 Ejemplo de evaluación lineal

. . . . . . . . . . . . . . . . . . . . . . . . . 83

4.1 Árbol de Decisión vs. Reglas de Decisión. . . . . . . . . . . . . . . . . . . 89

4.2 División del espacio: C4.5 vs. HIDER.

. . . . . . . . . . . . . . . . . . . . 89

4.3 Ejemplo de cálculo de un corte simple . . . . . . . . . . . . . . . . . . . . 91

4.4 Algoritmo USD .

. . . . . . . . . . . . . . . . . . .