PDF de programación - Heurísticas de selección de atributos para datos de gran dimensionado

H´  ´   

   

D  L  S I´

Memoria de Tesis Doctoral para optar al grado de
Doctor en Informática por la Universidad de Sevilla

presentada por

D. Roberto Ruiz Sánchez

Directores:

Dr. D. José C. Riquelme Santos

Dr. D. Jesús S. Aguilar Ruiz

Sevilla, mayo de 2006

Heurísticas de selección de atributos para entornos altamente dimensionales. Aplicación a bioinformática.
Copyright c 2006, por Roberto Ruiz Sánchez.
Todos los derechos reservados.

Your dedication goes here ... A Tránsito, sin tu paciencia y comprensión esta tesis no habría

sido posible.

Agradecimientos

Your acknowledgement goes here...



Índice general

Índice de figuras

Índice de tablas

Índice de algoritmos

Resumen

1. Introducción

.
.

.
.

. . .

.
.
. .

.
1.1. Planteamiento . .
.
1.2. Objetivos
.
1.3. Período de investigación .

.
.
.
.
.
.
1.3.1. Aportaciones originales
.
1.3.2. Proyectos de investigación . .
.

1.4. Organización . . .

.
.
.
.

.
.
.
.

.
.
.

.
.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Introducción . . .

2. Aprendizaje automático supervisado
.
.
.
.
.
.

2.1.
.
2.2. Representación de los datos .
2.3. Clasificación . . .
.
2.3.1. Naïve Bayes
.
2.3.2. Vecinos más cercanos
2.3.3. Árboles de decisión .

.
.
. .

.
.
.
.

.
.

.

.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

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

.
.
.
.
.
.

.
.
.
.
.
.

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

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

2.4. Evaluación del rendimiento de un clasificador .

.

. .

. .

2.4.1. Precisión . .
. .
2.4.2. Técnicas de evaluación .
.
.
2.4.3. Comparación del rendimiento . .
.
.

2.5. Preparación de los datos
2.5.1. Recopilación. . .

. .
.

. .
.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

. .
. .
. .
.
.
. .











1
1
2
3
3
5
8

11
11
13
14
15
16
17
20
20
21
23
24
24

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

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

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.
.
.
.

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

.
.
.

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

.
.
.

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



ÍNDICE GENERAL

2.5.2. Limpieza .
. . .
2.5.3. Transformación .
.
2.5.4. Reducción . .

.
.
.
.
. .

.
.
.
.
. .

.
.
.
.
. .

.
.
.
.
. .

.
.
.
.
. .

. .
. .
.
.

. .
. .
.
.

.
.
.

3. Selección de atributos
.
Introducción . .

.
. . .

.
3.1.
3.2. Definición . .
.
3.3. Relevancia y redundancia .
.
3.4. Proceso general

. .
. .

. .

.
.

.

.

.

.
.
.
.

. .
.
.
. .
. .

. .
.
.
. .
. .

. .
.
.
. .
. .

. .
.
.
. .
. .

. .

. .

. .

. .

. .
. .

3.5. Algoritmos de selección .

3.4.1. Estudios preliminares .
. .
. .
3.4.2. Generación de subconjuntos .
.
.
3.4.3. Medidas de evaluación de atributos
3.4.4. Objetivos a optimizar .
. .

. .
. .
3.5.1. Descripción de los algoritmos
.
3.5.2. Clasificación de los algoritmos .
. .

. .
.
. .
. .
. .
. .
3.6. Evaluación y comparación .
.
3.7. Aplicaciones de los algoritmos de selección .
.
.
. .
. .

3.7.1. Plataformas y guías .
3.7.2. Campo de aplicación .

3.8. Conclusiones y tendencias

. .
.
.
.
.
. .

. .
.
. .

. .
.
.
. .

. .
.
.
. .

. .
.
.
. .

. .

. .

. .

.

.

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

.
.
.

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

. .
. .
. .

.
.
.

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

25
26
27

31
31
32
33
37
37
40
43
45
45
45
59
60
62
63
65
67

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

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

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

.

.

.

.

.

. .

. .

. .

. .

. .

Introducción . .

4. Criterio de evaluación de atributos basado en proyecciones
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.

.
.
.
.
.
.
.
.
4.4.1. Los primeros k atributos .
4.4.2. Normalizando el ranking . .
.
4.4.3. Evaluación del area bajo la curva de comportamiento de clasificación .

4.1.
4.2. Definiciones de proyecciones .
4.3. NLC: Número de Cambios de Etiqueta .
.
.
4.4. Evaluaciones experimentales .
. .
. .

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

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

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

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

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

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

. .
.
.
.
.
. .

.
.
.
.
.
.

.
.
.
.
.
.

. .

. .

. .

. .

.

4.5. Conclusiones

. .

.

. .

.

.

.

. .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

69
70
73
78
81
83
90
98
. 112

.

.

Introduction . .

5. Búsqueda de un subconjunto de atributos sobre un ranking
.
.
.
.
.

5.1.
. .
. .
5.2. Trabajos relacionados .
. .
5.3. Búsqueda secuencial sobre un ranking .
5.4. Utilidad incremental ordenada .
. .
. .
. .

5.4.1. Algoritmo . . .

. .
. .
. .
. .
. .

. .
. .
. .
. .
.
.

. .
. .

. .
. .

. .
. .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

. .

.
.

.
.

.
.

.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
. .

115
. 116
. 117
. 117
. 119
. 120

ÍNDICE GENERAL

5.5. Utilidad jerárquica ordenada .
. .

5.4.2. Experimentos y resultados . .
.
.
5.5.1. Algoritmo . . .
. .
5.5.2. Experimentos y resultados . .
.

5.6. Conclusiones

.
.
. .

. . .

.

.

.

.

.

.

.

.

.

.

.

. .
.
.
. .
. .
.
.

. .
.
.
. .
. .
.
.

. .
.
.
. .
. .
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.

.

.

.

.

.
.

.
.

.
.

.
.

Introducción . . .

.
.
6.1.
6.2. Bases de datos genómicas .
.
6.3. Aprendizaje supervisado en bioinformática
6.4. Trabajos relacionados .
.
.
.
6.5. Evaluaciones experimentales .

6. Extracción de genes relevantes en bases de datos genómicas
.
.
.
.
.
.
.
.
.

.
.
6.5.1. Descripción de las bases de datos
6.5.2. Descripción de los experimentos .
.
6.5.3. Análisis de los resultados .
.
.

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

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

6.6. Conclusiones

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

. . .

.
.
.
.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.

.

.

.

.

.

.

.

.

7. Conclusiones y Trabajos Futuros

A. Conjuntos de Datos

Bibliografía

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
. .
.
.
.
.
. .

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

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.



. 122
. 136
. 137
. 140
. 145

147
. 147
. 150
. 152
. 153
. 154
. 154
. 155
. 156
. 165

167

173

177

Índice de figuras

2.1. Esquema General de KDD (Knowledge Discovery in Databases).
.
2.2. Fase de preparación de los datos. .
. .
.
2.3. Reducción de los datos en ambos sentidos: ejemplos y atributos.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

12
25
28

.

.

.

.

.

.

.

.

.

.

.

.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

. .
. .
. .
. .

.
.
3.1. Espacion de búsqueda.
37
3.2. Proceso de Selección de Atributos. .
.
38
3.3. Principales dimensiones de la selección de atributos .
45
3.4. División de los datos en carpetas. .
.
61
3.5. Proceso para validar los resultados al aplicar algoritmos de selección de atributos. 61
.
62
3.6. Reducción de un conjunto de datos.
.
.
.
.
3.7. Capacidades de los métodos de selección.
63
.
3.8. Diagrama de flujo de un prototipo de guía de algoritmos de selección.
64
.
3.9. Diagrama de flujo de algoritmos que utilizan consistencia como criterio de eva-
.
.
.

.
3.10. Comparación de algoritmos de selección.
3.11. Plataforma unificada.
.

. . .
.
.
.
.

. .
.
.
.
.

.
.
. .
. .

65
66
66

luación.

. .
. .

. . .

. . .

. .

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
4.1. Proyección de la base de datos IRIS en los atributos Sepalwidth–Sepallength.
. .
4.2. Proyección de la base de datos IRIS en los atributos Sepalwidth–Petalwidth.
.
.
4.3. Proyección de la base de datos IRIS en los atributos Petallength–Petalwidth.
.
.
.
4.4. Proyección de la base de datos WINE en los atributos C8-C7. .
.
.
. .
.
4.5. Base de datos artificial con 12 elementos y 2 etiquetas (P,I) .
.
.
4.6. Técnica SOAP. Subsecuencia del mismo valor. .
.
. .
.
.
.
4.7. Técnica SOAP. Ejemplo de contabilización de etiquetas.
.
.
.
.
. .
.
4.8. Ejemplo ficticio de tres tipos diferentes de curvas de aprendizaje. En el eje de
abscisas el no de atributos utilizados en la clasificación y en el de ordenada la
.
tasa de aciertos.
4.9. Curvas de aprendizaje obtenidas aplicando el clasificador C4 a diferentes ran-
. .

kings para la base de datos Glass2. . .

. .
.
.
.

.
.
. .
.
.

. . .

. . .

. . .

.
.
.
.

.
.
.
.

. .

. .

. .

. .

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

70
71
71
72
73
81
81

. 102

. 102





ÍNDICE DE FIGURAS

4.10. Curvas de aprendizaje obtenidas aplicando el clasificador C4 a diferentes ran-
. .
4.11. Curvas de aprendizaje obtenidas aplicando el clasificador NB a dif