Tesis

´ CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS ´ DEL INSTITUTO POLITECNICO NACIONAL ´ DEPARTAMENTO DE INGENIER´ ELECTRICA IA ´ DE COMPUTACION ´ SECCION

Algoritmo de clustering basado en entrop´ para ıa descubrir grupos en atributos de tipo mixto

Tesis que presenta Hern´ndez Valadez Edna a Para obtener el grado de Maestro en Ciencias En la especialidad de Ingenier´ El´ctrica ıa e Opci´nComputaci´n o o Director: Dra. Xiaoou Li Zhang Co-director: Dr. Luis E. Rocha Mier

M´xico, D.F., Agosto de 2006 e

ii

iv

Agradecimientos
Quiero agradecer a mis padres, hermanos y seres queridos, por su apoyo constante y por sus incontables ense˜anzas y valores. n A ti enrique, por tu cari˜o, apoyo y consejos, gracias por acompa˜arme en momentos n n dif´ ıciles y ser la motivaci´npara seguir adelante. o 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 disponibilidad para atenderme a discutir temas de la tesis. Al Dr. Joshua Huang de la Universidad de Hong Kong por enviarnos amablemente el c´digo fuente del algoritmo k-prototype y al Dr. Zengyou He del InstitutoHarbin de o Tecnolog´ en China por enviarnos informaci´n util para realizar las evaluaciones de ıa o ´ error y la medici´n de calidad en los resultados del proceso de clustering. o A todos mis maestros de la Secci´n de Computaci´n, que me brindaron sus conocio o mientos y experiencia y sentaron las bases para poder desarrollar correctamente ´ste e trabajo de tesis y a las secretarias de la secci´n,principalmente a Sof´ porque sin su o ı, ayuda no podr´ titularme. ıa A mis amigos de siempre: Mario, Mireya y Noel, por ´star ah´ por ayudarme en e ı, m´ltiples situaciones y ser parte de mi formaci´n. u o A mis dem´s compa˜eros de la secci´n, por su amistad y compa˜erismo. a n o n Al CINVESTAV por permitirme cursar los estudios de maestr´ facilit´ndome el uso ıa a de sus instalaciones. Al CONACyTpor apoyarme con la beca econ´mica durante toda mi estancia en el o programa de maestr´ ıa.

vi

´ Indice general
´ Indice de tablas ´ Indice de figuras Resumen Abstract 1. Introducci´n o 1.1. Antecedentes . . . . 1.2. Trabajo Relacionado 1.3. Motivaci´n . . . . . . o 1.4. Objetivos . . . . . . 1.5. Organizaci´n . . . . o
XI XIII

1 1 3 3 5 7 8 8 11 11 12 13 14 14 15 16 16 18 21 21 22 2223 25

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2. Datos y Mediciones 2.1.Representaci´n de datos . . . . . . . . . . . . . o 2.1.1. Tipos de atributos . . . . . . . . . . . . 2.1.2. Tipos de datasets . . . . . . . . . . . . . 2.1.3. Conversi´n datos categ´ricos a num´ricos o o e 2.1.4. Conversi´n datos num´ricos a categ´ricos o e o 2.2. Calidad de datos . . . . . . . . . . . . . . . . . 2.3. Mediciones . . . . . . . . . . . . . . . . . . . . . 2.3.1. Medidas dedistancia y similitud . . . . . 2.4. Comentarios . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

3. Miner´ de Datos y Clustering ıa 3.1.Descubrimiento de Conocimiento en Bases de Datos 3.2. Miner´ de Datos . . . . . . . . . . . . . . . . . . . ıa 3.2.1. Concepto de Miner´ de Datos . . . . . . . . ıa 3.2.2. Componentes b´sicos . . . . . . . . . . . . . a 3.2.3. T´cnicas de Miner´ de Datos . . . . . . . . e ıa

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. ....