PDF de programación - Algoritmo de clustering basado en entropía para descubrir grupos en atributos de tipo mixto

CENTRO DE INVESTIGACI ´ON Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLIT´ECNICO NACIONAL
DEPARTAMENTO DE INGENIER´IA EL´ECTRICA

SECCI ´ON DE COMPUTACI ´ON

Algoritmo de clustering basado en entrop´ıa para

descubrir grupos en atributos de tipo mixto

Tesis que presenta

Hern´andez Valadez Edna

Para obtener el grado de

Maestro en Ciencias

En la especialidad de

Ingenier´ıa El´ectrica

Opci´on Computaci´on

Director: Dra. Xiaoou Li Zhang

Co-director: Dr. Luis E. Rocha Mier

M´exico, D.F., Agosto de 2006

ii

iv

Agradecimientos

Quiero agradecer a mis padres, hermanos y seres queridos, por su apoyo constante y
por sus incontables ense˜nanzas y valores.

A ti enrique, por tu cari˜no, apoyo y consejos, gracias por acompa˜narme en momentos

dif´ıciles y ser la motivaci´on para seguir adelante.

A mis asesores la Dra. Xiaoou Li y el Dr. Luis Enrique Rocha, por sus valiosas ideas
y comentarios aportados al trabajo de tesis, por su amabilidad y sobre todo disponibi-
lidad para atenderme a discutir temas de la tesis.

Al Dr. Joshua Huang de la Universidad de Hong Kong por enviarnos amablemente
el c´odigo fuente del algoritmo k-prototype y al Dr. Zengyou He del Instituto Harbin de
Tecnolog´ıa en China por enviarnos informaci´on ´util para realizar las evaluaciones de
error y la medici´on de calidad en los resultados del proceso de clustering.

A todos mis maestros de la Secci´on de Computaci´on, que me brindaron sus conoci-
mientos y experiencia y sentaron las bases para poder desarrollar correctamente ´este
trabajo de tesis y a las secretarias de la secci´on, principalmente a Sof´ı, porque sin su
ayuda no podr´ıa titularme.

A mis amigos de siempre: Mario, Mireya y Noel, por ´estar ah´ı, por ayudarme en

m´ultiples situaciones y ser parte de mi formaci´on.

A mis dem´as compa˜neros de la secci´on, por su amistad y compa˜nerismo.

Al CINVESTAV por permitirme cursar los estudios de maestr´ıa facilit´andome el uso

de sus instalaciones.

Al CONACyT por apoyarme con la beca econ´omica durante toda mi estancia en el

programa de maestr´ıa.

vi

´Indice general

´Indice de tablas

´Indice de figuras

Resumen

Abstract

1. Introducci´on

1.1. Antecedentes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Trabajo Relacionado . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Organizaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Datos y Mediciones

2.1. Representaci´on de datos

. . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Tipos de atributos
. . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Tipos de datasets . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Conversi´on datos categ´oricos a num´ericos . . . . . . . . . . . . .
2.1.4. Conversi´on datos num´ericos a categ´oricos . . . . . . . . . . . . .
2.2. Calidad de datos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Mediciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1. Medidas de distancia y similitud . . . . . . . . . . . . . . . . . .
2.4. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Miner´ıa de Datos y Clustering

3.1. Descubrimiento de Conocimiento en Bases de Datos . . . . . . . . . . .
3.2. Miner´ıa de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Concepto de Miner´ıa de Datos . . . . . . . . . . . . . . . . . . .
3.2.2. Componentes b´asicos . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. T´ecnicas de Miner´ıa de Datos . . . . . . . . . . . . . . . . . . .

XI

XIII

1

1

3
3
5
7
8
8

11
11
12
13
14
14
15
16
16
18

21
21
22
22
23
25

vii

´Indice general

3.2.3.1. T´ecnicas descriptivas . . . . . . . . . . . . . . . . . . .
3.2.3.2. Tareas predictivas
. . . . . . . . . . . . . . . . . . . .
3.3. Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Concepto de clustering . . . . . . . . . . . . . . . . . . . . . . .
3.3.2. An´alisis de clustering . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3. Caracter´ısticas de los algoritmos de clustering . . . . . . . . . .
3.4. T´ecnicas de Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1. Clustering jer´arquico . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2. Clustering particional . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3. Clustering basado en densidad . . . . . . . . . . . . . . . . . . .
3.4.4. Clustering basado en grid . . . . . . . . . . . . . . . . . . . . .
3.4.5. Clustering difuso . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.6. Clustering de redes neuronales artificiales . . . . . . . . . . . . .
3.4.7. Clustering de algoritmos evolutivos . . . . . . . . . . . . . . . .
3.4.8. Clustering basado en entrop´ıa . . . . . . . . . . . . . . . . . . .
3.5. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Algoritmo Propuesto ACEM

4.1. Algoritmo de inspiraci´on . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Algoritmo ROCK . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Modelo inicial alternativo
. . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Estructura del algoritmo propuesto . . . . . . . . . . . . . . . . . . . .
4.3.1. Fase 1 - Datos categ´oricos . . . . . . . . . . . . . . . . . . . . .
4.3.2. Fase 2 - Datos mixtos . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Algoritmo ACEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1. Evaluaci´on de vecinos . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2. Evaluaci´on de ligas . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3. Medida de efectividad . . . . . . . . . . . . . . . . . . . . . . .
4.4.4. Evaluaci´on de entrop´ıa . . . . . . . . . . . . . . . . . . . . . . .
4.4.5. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Algoritmos de comparaci´on . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1. Algoritmo de clustering para datos categ´oricos . . . . . . . . . .
4.5.2. Algoritmo de clustering para datos mixtos . . . . . . . . . . . .

5. Evaluaci´on de Resultados

5.1. Medida de exactitud del cl´uster . . . . . . . . . . . . . . . . . . . . . .
5.2. Comparaci´on de ACEM respecto al modelo inicial alternativo . . . . .
5.3. Comportamiento de variabilidad . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .

5.3.1. Variabilidad en las instancias

26
26
28
28
28
30
31
32
33
34
35
36
37
38
39
42

43
43
44
46
47
47
48
49
49
51
52
53
54
55
56
57

61
61
62
63
64

viii

´Indice general

5.3.2. Variabilidad en los atributos . . . . . . . . . . . . . . . . . . . .
5.4. Par´ametros de entrada . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5. Experimentos Fase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1. Resultados del dataset Breast Cancer
. . . . . . . . . . . . . .
5.5.2. Resultados del dataset Congressional Votes . . . . . . . . . . .
5.5.3. Resultados del dataset Soybean . . . . . . . . . . . . . . . . . .
5.5.4. Resultados del dataset Zoo . . . . . . . . . . . . . . . . . . . .
5.6. Experimentos Fase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1. Resultados del dataset Bridges . . . . . . . . . . . . . . . . . .
5.6.2. Resultados del dataset Cylinder Bands . . . . . . . . . . . . . .
5.6.3. Resultados del dataset Cleve . . . . . . . . . . . . . . . . . . .
5.6.4. Resultados del dataset Flag . . . . . . . . . . . . . . . . . . . .
5.6.5. Resultados del dataset Post-operative . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
5.7.1. Valores de θ en datasets de tipo categ´orico . . . . . . . . . . . .
5.7.2. Valores de θ en datasets de tipo mixtos . . . . . . . . . . . . . .
5.8. An´alisis de experimentos . . . . . . . . . . . . . . . . . . . . . . . . . .

5.7. Evaluaci´on del par´ametro θ

6. Conclusiones y Trabajo Futuro

A. M´etricas de Distancia

B. Algoritmos de cl´ustering

B.1. Algoritmos de cl´ustering jer´arquicos . . . . . . . . . . . . . . . . . . . .
B.2. Algoritmos de cl´ustering particional . . . . . . . . . . . . . . . . . . . .
B.3. Algoritmos de cl´ustering basados en densidad . . . . . . . . . . . . . .
B.4. Algoritmos de cl´ustering basados en grid . . . . . . . . . . . . . . . . .

64
66
67
68
70
71
72
74
76
77
78
81
82
83
84
87
90

91

93

95
95
96
97
98

C. Descripci´on de Datasets

99
99
C.1. Datasets con tipos de datos categ´orico . . . . . . . . . . . . . . . . . .
C.1.1. Dataset Breast Cancer . . . . . . . . . . . . . . . . . . . . . . .
99
C.1.2. Dataset Congressional Votes . . . . . . . . . . . . . . . . . . . . 100
C.1.3. Dataset Soybean . . . . . . . . . . . . . . . . . . . . . . . . . . 100
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
C.1.4. Dataset Zoo
C.2. Datasets con tipos de datos mixto . . . . . . . . . . . . . . . . . . . . . 103
C.2.1. Dataset Cilinder bands . . . . . . . . . . . . . . . . . . . . . . . 103
C.2.2. Dataset Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.2.3. Dataset Cleveland clinic heart disease . . . . . . . . . . . . . . . 104
C.2.4. Dataset Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

ix

´Indice general

C.2.5. Dataset Post-operative . . . . . . . . . . . . . . . . . . . . . . . 106

Bibliograf´ıa

109

x

´Indice de tablas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Tipos de atributos.
2.2. Mediciones para variables cuantitativas. . . . . . . . . . . . . . . . . . .

3.1. Casos de partida para el an´alisis de clustering . . . . . . . . . . . . . .
3.2. Medici´on de entrop´ıa en clustering.
. . . . . . . . . . . . . . . . . . . .

4.1. Caracter´ısticas ROCK . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
18

29
41

44

62

63

65

butos de entrada.

t