PDF de programación - Nuevos métodos híbridos de computación flexible para clasificación multietiqueta

Nuevos métodos híbridos de
computación flexible para
clasificación multietiqueta

Francisco Charte Ojeda

<[email protected]>

Tesis para la obtención del título de doctor

por la Universidad de Granada

Tecnologías de la Información y la

Programa Oficial de Doctorado en

Comunicación

Departamento de Ciencias de la Computación e Inteligencia Artificial

Escuela Técnica Superior de Ingenierías Informática y de Telecomunicación

Universidad de Granada

Directores de tesis

Dr. D. Antonio Jesús Rivera Rivas

Grupo de Sistemas Inteligentes y Minería de Datos, Universidad de Jaén

Dra. Da María José del Jesus Díaz

Grupo de Sistemas Inteligentes y Minería de Datos, Universidad de Jaén

Dr. D. Francisco Herrera Triguero

Grupo de Soft Computing y Sistemas de Información Inteligentes, Universidad de

Granada

Granada, abril de 2015

Tesis doctoral subvencionada por el programa predoctoral de Formación del
Profesorado Universitario (FPU) del Ministerio de Educación (Ref. AP2010-
0068) según convocatoria publicada en BOE de 24 de enero de 2011 y resolución
publicada en BOE de 20 de diciembre de 2011.

El doctorando Francisco Charte Ojeda y los directores de la tesis Dr. D.
Antonio Jesús Rivera Rivas, Dra. Da María José del Jesus Díaz y Dr. D.
Francisco Herrera Triguero. Garantizamos, al firmar esta tesis doctoral, que
el trabajo ha sido realizado por el doctorando bajo la dirección de los directores
de la tesis y hasta donde nuestro conocimiento alcanza, en la realización del
trabajo, se han respetado los derechos de otros autores a ser citados, cuando se
han utilizado sus resultados o publicaciones.

Granada, 1 de abril de 2015

Doctorando

Francisco Charte Ojeda

Directores de la tesis

Dr. D. Antonio J. Rivera Rivas

Dra. Da María J. del Jesus Díaz

Dr. D. Francisco Herrera Triguero

i

Lo que sabemos es una gota de agua, lo que ignoramos es el océano.
(Isaac Newton)

iii

Resumen

La presente tesis aborda el estudio de nuevas técnicas de tratamiento de los
datos con el objetivo de mejorar el funcionamiento de los sistemas de clasificación
multietiqueta. La motivación de este trabajo está en el cada vez mayor número
de campos de aplicación de dicho tipo de clasificación, a raíz de la necesidad
de etiquetar documentos de todo tipo: textos, imágenes, vídeos, música, etc., y
su utilidad en otros campos como la medicina y la genética, especialmente la
predicción de funciones de proteínas.

En el desarrollo de la tesis se siguen fundamentalmente dos estrategias: apro-
vechar la información de correlación entre etiquetas a fin de reducir la dimensiona-
lidad del espacio de salida, por una parte, y analizar las características específicas
de los conjuntos de datos multietiqueta a fin de proponer algoritmos de prepro-
cesamiento a medida, para reducir el desequilibrio entre etiquetas y mejorar el
rendimiento de los clasificadores. El trabajo en estas dos vías ha llevado al diseño
y desarrollo de múltiples algoritmos recogidos en la tesis, cuya finalidad se resume
a continuación:

LI-MLC: Es un método en el que se hibrida un algoritmo de minería de
reglas de asociación con métodos de clasificación multietiqueta existentes,
reduciendo la dimensionalidad del espacio de etiquetas a fin de mejorar el
rendimiento y la eficiencia.
LP-ROS/LP-RUS: Métodos de remuestreo aleatorio basados en la técnica
de transformación para conjuntos de datos multietiqueta conocida como LP
(Label Powerset).
ML-ROS/ML-RUS: Métodos de remuestreo aleatorio basados en el análisis
individual de la frecuencia de aparición de cada etiqueta en el conjunto de
datos.
MLSMOTE: Algoritmo de generación de instancias sintéticas para conjun-
tos de datos multietiqueta.
MLeNN: Algoritmo de eliminación de instancias basado en la regla del ve-
cino más cercano.
REMEDIAL: Método de preprocesamiento que permite mejorar el rendi-
miento en clasificación mediante la separación de etiquetas con desbalanceo.
Además de los citados algoritmos, junto con su correspondiente experimenta-
ción, la tesis también propone múltiples medidas de caracterización para conjun-
tos de datos multietiqueta y el análisis justificado sobre su utilidad y aplicación.
Toda esta información puede obtenerse fácilmente gracias al paquete mldr para
el entorno R, desarrollado asimismo como parte de la presente tesis.

v

Índice general

Agradecimientos

Introducción

1. Fundamentos

1.1. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. El proceso de KDD . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Preprocesamiento y transformación . . . . . . . . . . . . .
1.1.3. Minería de datos
. . . . . . . . . . . . . . . . . . . . . . .
1.1.4. Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Clasificación multietiqueta . . . . . . . . . . . . . . . . . . . . . .
1.3. Características de los conjuntos de datos multietiqueta . . . . . .
1.3.1. Distribución de las etiquetas . . . . . . . . . . . . . . . . .
1.3.2. Distribución de los conjuntos de etiquetas
. . . . . . . . .
1.3.3. Otras características de los MLD . . . . . . . . . . . . . .
1.4. Aplicaciones multietiqueta y sus conjuntos de datos . . . . . . . .
1.4.1. Categorización de textos . . . . . . . . . . . . . . . . . . .
1.4.2. Etiquetado de recursos multimedia . . . . . . . . . . . . .
1.4.3. Genética/Biología . . . . . . . . . . . . . . . . . . . . . . .
1.4.4. Otras aplicaciones . . . . . . . . . . . . . . . . . . . . . . .
1.5. Clasificadores multietiqueta . . . . . . . . . . . . . . . . . . . . .
1.5.1. Métodos basados en técnicas de transformación . . . . . .
1.5.2. Métodos basados en adaptación de algoritmos . . . . . . .
1.5.3. Métodos basados en multi-clasificadores . . . . . . . . . . .
1.6. Métricas de evaluación . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1. Métricas basadas en ejemplos
. . . . . . . . . . . . . . . .
1.6.2. Métricas basadas en etiquetas . . . . . . . . . . . . . . . .
1.7. Tareas relacionadas . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
1.8. Problemática específica objeto de estudio

vii

1

3

11
12
12
13
17
22
23
24
25
26
27
28
29
30
31
32
32
33
38
50
56
58
62
64
66

Índice general

1.8.1. Dimensionalidad en el espacio de etiquetas . . . . . . . . .
1.8.2. Desequilibrio en la distribución de etiquetas
. . . . . . . .
1.8.3. Caracterización de conjuntos de datos multietiqueta . . . .

66
68
68

2. Tratamiento de la dimensionalidad en el espacio de etiquetas

2.1.

Información de dependencia entre etiquetas

2.5. Trabajos previos
2.6.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Preprocesamiento en el espacio de etiquetas
. . . . . . . .
2.1.2. Presentación de la propuesta . . . . . . . . . . . . . . . . .
2.2. Reducción de dimensionalidad . . . . . . . . . . . . . . . . . . . .
2.3.
. . . . . . . . . . . .
2.4. Reglas de asociación . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Conceptos generales y medidas
. . . . . . . . . . . . . . .
2.4.2. Minería de reglas de asociación . . . . . . . . . . . . . . .
2.4.3. El algoritmo FP-Growth . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
Inferencia de etiquetas para clasificación multietiqueta . . . . . .
2.6.1. El algoritmo LI-MLC . . . . . . . . . . . . . . . . . . . . .
2.6.2. Aplicación de LI-MLC a conjuntos multietiqueta . . . . . .

71
72
73
75
77
78
81
83
86
87
89
93
94
97
2.7. Experimentación y validación . . . . . . . . . . . . . . . . . . . . 101
2.7.1. Conjuntos de datos . . . . . . . . . . . . . . . . . . . . . . 101
2.7.2. Algoritmos de clasificación . . . . . . . . . . . . . . . . . . 103
2.7.3. Métricas de evaluación de rendimiento . . . . . . . . . . . 103
2.7.4. Tests estadísticos . . . . . . . . . . . . . . . . . . . . . . . 104
2.7.5. Caracterización de los conjuntos de datos . . . . . . . . . . 105
2.7.6. Resultados de clasificación . . . . . . . . . . . . . . . . . . 106
2.7.7. Estudio estadístico . . . . . . . . . . . . . . . . . . . . . . 108
2.8. Conclusiones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
2.9. Publicaciones asociadas a este trabajo . . . . . . . . . . . . . . . 112

3. Desbalanceo en conjuntos de datos multietiqueta

3.3.1. Aprendizaje con MLD desbalanceados

115
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.1.
3.2. Desbalanceo en clasificación tradicional . . . . . . . . . . . . . . . 117
3.3. Desbalanceo en clasificación multietiqueta . . . . . . . . . . . . . 119
. . . . . . . . . . . 122
3.4. Medida del desbalanceo en multietiqueta . . . . . . . . . . . . . . 126
3.4.1. Ratio de desbalanceo por etiqueta . . . . . . . . . . . . . . 126
3.4.2. Ratio de desbalanceo medio . . . . . . . . . . . . . . . . . 127
3.4.3. Coeficiente de variación del ratio de desbalanceo . . . . . . 127
3.4.4. Análisis del nivel desbalanceo en MLD . . . . . . . . . . . 128

viii

Índice general

3.5. Técnicas de remuestreo aleatorio . . . . . . . . . . . . . . . . . . 129
3.5.1. Remuestreo basado en la transformación LP . . . . . . . . 129
3.5.2. Remuestreo con evaluación individual de etiquetas . . . . . 133
3.5.3. Experimentación . . . . . . . . . . . . . . . . . . . . . . . 135
3.6. Conclusiones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.7. Publicaciones asociadas a este trabajo . . . . . . . . . . . . . . . 143
3.8. Tablas de resultados . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.1.

4. Técnicas de remuestreo heurístico

153
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.1.1. Generación de instancias sintéticas
. . . . . . . . . . . . . 154
4.1.2. La regla k-NN . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.1.3. Concurrencia entre etiquetas en conjuntos multietiqueta

desbalanceados

. . . . . . . . . . . . . . . . . . . . . . . . 156
4.2. El algoritmo MLSMOTE . . . . . . . . . . . . . . . . . . . . . . 157
4.2.1. Selección de instancias minoritarias . . . . . . . . . . . .