PDF de programación - Nuevos Retos en la Selección Evolutiva de Instancias: Escalabilidad, Aprendizaje con Clases no Balanceadas y Caracterización de la Eficacia

Universidad de Granada

Departamento de Ciencias de la Computaci´on

e Inteligencia Artificial

Nuevos Retos en la Selecci´on

Evolutiva de Instancias: Escalabilidad,

Aprendizaje con Clases no Balanceadas y

Caracterizaci´on de la Eficacia

Tesis Doctoral

Salvador Garc´ıa L´opez

Granada, Octubre de 2008

Universidad de Granada

Nuevos Retos en la Selecci´on

Evolutiva de Instancias: Escalabilidad,

Aprendizaje con Clases no Balanceadas y

Caracterizaci´on de la Eficacia

MEMORIA QUE PRESENTA

Salvador Garc´ıa L´opez

PARA OPTAR AL GRADO DE DOCTOR EN INFORM ´ATICA

Octubre de 2008

DIRECTOR

Francisco Herrera Triguero

Departamento de Ciencias de la Computaci´on

e Inteligencia Artificial

La memoria titulada “Nuevos Retos en la Selecci´on Evolutiva de Instancias: Escalabilidad,
Aprendizaje con Clases no Balanceadas y Caracterizaci´on de la Eficacia”, que presenta D. Salvador
Garc´ıa L´opez para optar al grado de doctor, ha sido realizada dentro del programa de doctorado
“Dise˜no, An´alisis y Aplicaciones de Sistemas Inteligentes” del Departamento de Ciencias de la
Computaci´on e Inteligencia Artificial de la Universidad de Granada bajo la direcci´on del doctor D.
Francisco Herrera Triguero.

Granada, Octubre de 2008

El Doctorando

El Director

Fdo: Salvador Garc´ıa L´opez

Fdo: Francisco Herrera Triguero

Tesis Doctoral Parcialmente Subvencionada por el Ministerio de Educaci´on y Ciencia bajo el
Proyecto Nacional TIN2005-08386-C05. Tambi´en ha sido Subvencionada bajo el Programa de Becas
de Formaci´on de Profesorado Universitario, en la Resoluci´on del 30 de Marzo de 2005, bajo la
referencia AP2005-4197.

Agradecimientos

Esta memoria est´a dedicada a todas aquellas personas sin las cuales no hubiera sido posible.
Ante todo a mis padres, Mar´ıa y Salvador, porque todo lo que he conseguido ha sido gracias a
ellos, a su apoyo, cari˜no y compresi´on en las dificultades por las que he pasado desde que empec´e en
este viaje. Estoy muy orgulloso de ellos por brindarme las oportunidades que me han dado y que
ellos no tuvieron en su vida. Esta memoria es por y para vosotros.

Tambi´en agradezco en cantidad los ´animos y consejos que me han dado mis hermanos, Alfonso,
Manolo y Miguel ´Angel, que han visto como he ido evolucionando y aprendiendo y siempre han
estado para ayudarme a enfrentarme a cualquier obst´aculo. A˜nado en este agradecimiento a un
buen amigo, que siempre ha estado ah´ı y con el que he compartido gran parte del tiempo hasta
lograr este objetivo. Diego, siempre has sido para m´ı como un hermano y te agradezco todo el
tiempo que has dedicado a darme un buen consejo, sea a la hora que sea.

Si en el ´ambito familiar he tenido mucha suerte por los ´animos y apoyos recibidos, ´estos no
han sido menores con respecto a mi director de tesis. Francisco Herrera me ha guiado en todos
los aspectos relacionados con el mundo profesional y muestro mi m´as sincero agradecimiento a su
gran dedicaci´on e inter´es hacia m´ı as´ı como a los valiosos consejos que me ha dado, me da, y me
seguir´a dando.

No puedo olvidarme de todas aquellas personas que han estado a mi lado desde el principio de
este viaje y me han aguantado durante todo el camino, a pesar de mis d´ıas de mal humor. Muchas
gracias a los hermanos Alcal´a, Rafa y Jes´us, a Antonio Gabriel, a Jos´e Ram´on por mostrarme la
otra cara de la moneda en momentos de mucho estr´es, a Alberto y Juli´an, con los que he formado el
tr´ıo de becarios imparables de Paco, a Alicia por su eterna simpat´ıa y a mi amigo de fiestas y ahora
tambi´en amigo en el entorno profesional, Manolo Cobo. Gracias tambi´en a ´Oscar C´ordon, Enrique
Herrera y Manuel Lozano por ayudarme a empezar en este viaje. Tambi´en, quisiera agradecer los
momentos buenos que he pasado con el resto de mis compa˜neros ya sea fuera o dentro de la vida
laboral, y no me olvido de ninguno: Sergio, Jorge, Javi, Coral, Roc´ıo, Cristina, Carlos Porcel, Carlos
Garc´ıa, Carlos Mantas, Dani, Jos´e Santamar´ıa, Ana, Perico, Igor, Nacho y ´Oscar Harari.

Quiero tambi´en expresar mi gratitud a los compa˜neros con los que he compartido reuniones,
seminarios y congresos y me han ayudado tambi´en a estar en donde estoy. De Ja´en, cabe citar a
Mar´ıa Jos´e del Jesus, a Pedro Gonz´alez, a Chequin y a Paco Berlanga, de C´ordoba no me olvido
de Sebasti´an Ventura, de Pedro Antonio, Amelia y Juan Carlos, de Barcelona, Ester y Albert y de
Gij´on, a Luciano y a Pepe.

No quiero dejar de mencionar a los amigos por lo vivido y lo que nos queda por vivir: Jorge,

Juanda, Tomy, Edu, Rafi, Mar´ıa, Luisa y al resto del grupo de Linares.

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

para el t´ermino de esta memoria. Quiero dedicaros el esfuerzo de este, nuestro trabajo.

GRACIAS A TODOS

´Indice

1. Memoria

1.1.

Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Clasificaci´on, Aprendizaje basado en Instancias y Selecci´on de Prototipos . .
1.1.2. Algoritmos Evolutivos en Miner´ıa de Datos. Selecci´on Evolutiva de Prototipos.
1.1.3. Problemas de Clasificaci´on con Clases no Balanceadas . . . . . . . . . . . . .
1.1.4. Medidas de Complejidad de Datos en Clasificaci´on . . . . . . . . . . . . . . .
1.1.5. An´alisis y Comparaci´on de Algoritmos: Tests Estad´ısticos . . . . . . . . . . .

1
1
4
6
8
9
9
1.2. Justificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5. Discusi´on Conjunta de los Resultados

1.5.1. Un Algoritmo Mem´etico para la Selecci´on Evolutiva de Prototipos: Un En-

foque para la Escalabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5.2. Diagn´ostico de la Efectividad de la Selecci´on Evolutiva de Prototipos usando

una Medida de Solapamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5.3. Bajo-Muestreo Evolutivo para la Clasificaci´on en Problemas no Balanceados:
Propuestas para Aprendizaje basado en Instancias y Selecci´on de Conjuntos
de Entrenamiento

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5.4. Dise˜no de Experimentos en Inteligencia Computacional: Sobre el Uso de la

Inferencia Estad´ıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6. Comentarios Finales: Breve Resumen de los Resultados Obtenidos y Conclusiones . . 15

1.6.1. Un Algoritmo Mem´etico para la Selecci´on Evolutiva de Prototipos: Un En-

foque para la Escalabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2. Diagn´ostico de la Efectividad de la Selecci´on Evolutiva de Prototipos usando

una Medida de Solapamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.3. Bajo-Muestreo Evolutivo para la Clasificaci´on en Problemas no Balanceados:
Propuestas para Aprendizaje basado en Instancias y Selecci´on de Conjuntos
de Entrenamiento

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6.4. Dise˜no de Experimentos en Inteligencia Computacional: Sobre el Uso de la

Inferencia Estad´ıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

vii

viii

´INDICE

1.7. Perspectivas Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2. Publicaciones: Trabajos Publicados, Aceptados y Sometidos

23

2.1. Un Algoritmo Mem´etico para la Selecci´on Evolutiva de Prototipos: Un Enfoque
para la Escalabilidad - A Memetic Algorithm for Evolutionary Prototype Selection:
A Scaling Up Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2. Diagn´ostico de la Efectividad de la Selecci´on Evolutiva de Prototipos usando una
Medida de Solapamiento - Diagnose of Effective Evolutionary Prototype Selection
using an Overlapping Measure

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.3. Bajo-Muestreo Evolutivo para la Clasificaci´on en Problemas no Balanceados: Pro-
puestas para Aprendizaje basado en Instancias y Selecci´on de Conjuntos de Entrena-
miento - Evolutionary Under-Sampling for Classification with imbalanced Data Sets:
Proposals for Instance-Based Learning and Training Set Selection . . . . . . . . . . . 69
2.3.1. Evolutionary Under-Sampling for Classification with Imbalanced Data Sets:

Proposals and Taxonomy

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

2.3.2. Enhancing the Effectiveness and Interpretability of Decision Tree and Rule
Induction Classifiers with Evolutionary Training Set Selection over Imbalan-
ced Problems

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

2.4. Dise˜no de Experimentos en Inteligencia Computacional: Sobre el Uso de la Inferencia
Estad´ıstica - Design of Experiments in Computational Intelligence: On the Use of
Statistical Inference
2.4.1. A Study on the Use of Non-Parametric Tests for Analyzing the Evolutionary
Algorithms’ Behaviour: A Case Study on the CEC’2005 Special Session on
Real Parameter Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

2.4.2. An Extension on “Statistical Comparisons of Classifiers over Multiple Data

Sets” for all Pairwise Comparisons . . . . . . . . . . . . . . . . . . . . . . . . 149

2.4.3. A Study of Statistical Techniques and Performance Measures for Genetics-

Based Machine Learning: Accuracy and Interpretability . . . . . . . . . . . . 169

Bibliograf´ıa

193

Cap´ıtulo 1

Memoria

1.1.

Introducci´on

La revoluci´on digital ha posibilitado que la captura de datos sea f´acil y su almacenamiento tenga
un coste pr´acticamente nulo. Con el desarrollo del software y el hardware y la r´apida informatizaci´on
de los negocios, enormes canti