algoritmos de agrupamiento basados en densidad y validación de
TRANSCRIPT
Departament de Llenguatges I Sistemas Informátics Universitat Jaume I
Algoritmos de Agrupamiento basados en densidad y Validación de clusters
Tesis Doctoral
Presentada por:
Damaris Pascual González
Dirigida por:
Dr. Filiberto Pla Bañón Dr. José Salvador Sánchez Garreta
Castellón, Marzo de 2010
Hay un lenguaje en el mundo que todos
entienden. El lenguaje del entusiasmo, de
las cosas hechas con amor y con voluntad,
en busca de algo que se desea o en lo que
se cree.
Paulo Coelho
Resumen
Los algoritmos de clasificación supervisada operan usualmente sobre la información
suministrada por un conjunto de muestras, patrones, ejemplos o prototipos que se
consideran representantes de clases relevantes y, además, se asume que poseen una
etiqueta de clase correcta. Los algoritmos no supervisados, a diferencia de los
anteriores, no disponen del conjunto de entrenamiento y, valiéndose de algoritmos de
agrupamiento, construyen el conjunto de entrenamiento.
Dentro de este contexto, en la presente tesis proponemos dos algoritmos de
agrupamiento que emplean una estrategia híbrida entre los métodos basados en
densidad y los métodos jerárquicos. Estos algoritmos están divididos en dos etapas:
en la primera, se desarrolla una estrategia basada en densidad, en la que se obtiene
un agrupamiento de los datos de modo tal que los grupos están formados por zonas
de alta densidad, separados entre sí por áreas de baja densidad. En la segunda etapa,
se desarrolla una estrategia jerárquica con los grupos obtenidos en la primera etapa,
con el objetivo de unir los grupos más semejantes empleando una función de
disimilaridad propuesta también en este trabajo. La principal ventaja de estos
algoritmos es que se obtienen grupos de diferentes formas y tamaños, en presencia de
ruido y solapamiento.
También en este trabajo, con el objetivo de evaluar el agrupamiento obtenido,
diseñamos e implementamos una estrategia de validación de clusters basada en la
estabilidad de los agrupamientos del conjunto de datos a través de variaciones
producidas por muestreos que tienen en cuenta elementos de la teoría de la
información.
Para medir la efectividad de los algoritmos propuestos, se realizaron
experimentos de comparación con otros algoritmos de clustering y de validación de
clusters, utilizando conjuntos de datos sintéticos y reales. En general, los resultados
experimentales demuestran que los algoritmos aquí propuestos tienen un buen
comportamiento, aún cuando exista gran solapamiento entre los grupos y ruido.
Abstract
Supervised classification algorithms usually operate on the information provided by
a set of samples, patterns, examples or prototypes that are considered representatives
of relevant classes, and have a correct class label. Unsupervised algorithms, unlike
the previous ones, do not have a training set, and they are clustering algorithms to
build the training set.
Within this context, in this thesis we propose two clustering algorithms that
use a hybrid strategy between density-based methods and hierarchical methods.
These algorithms are divided into two stages. First, we develop a strategy based on
density, which yields a grouping of data so that the groups are formed by high
density zones, separated by low density areas. On the second one, we develop a
hierarchical strategy with the groups obtained in the first stage, with the aim of
joining similar groups using a dissimilarity function also proposed in this work. The
main advantage of these algorithms is that they produce groups of different shapes
and sizes, in the presence of noise and overlapping.
Also in this work, in order to evaluate the obtained clustering, we designed
and implemented a strategy for validation of clusters based on the stability of the
clustering of the re-samples of the data set that takes into account elements of
information theory.
With the aim of measuring the performance of the proposed algorithms,
experiments were carried out in order to compare with the results from other
clustering algorithms and cluster validation algorithms, using synthetic and real
dataset. In general, experimental results show that the algorithms here proposed
behave well, even when there is a high overlapping between groups and noise.
Dedicatoria
A mi esposo e hijos.
A mis padres.
A mi abuelita Nana.
Agradecimientos
Quiero agradecer a mi esposo Fernando Daniel y a mis hijos Fernandito y Dayamí
que me han permitido estudiar y desarrollar este trabajo, por su amor, confianza y
apoyo todas las veces que he estado fuera de casa. A Dayamí que tanto ha sufrido
mis ausencias. A mis padres y a mi abuelita Nana, por su amor, sus constantes
preocupaciones y enseñanzas. A mis suegros por su apoyo.
A mis directores los doctores Filiberto Pla Bañón y José Salvador Sánchez
Garreta que con sus ideas, experiencias y comentarios han dirigido este trabajo. Por
su disposición y amabilidad para atenderme.
A María Jesús y Filiberto, Christine y Pablo por su ayuda y todos los
momentos agradables que hemos pasado juntos.
A todos los integrantes del grupo Visión por Ordenador por todos los
momentos compartidos y por su ayuda incondicional, especialmente a Jose, Adolfo y
Tomás.
A todos mis profesores de los cursos de doctorado. A todos los compañeros
del Departamento de Lenguajes y Sistemas Informáticos de esta Universidad, a
Quirós, Badía y Rafa.
A mis compañeros de la Universidad de Oriente.
A la Universidad Jaume I de Castellón por permitirme cursar los estudios de
doctorado y desarrollar las estancias de investigación que han dado lugar a la
presentación de esta memoria de tesis.
A todos los que no he mencionado formalmente que en algún momento me
hayan brindado ayuda y consejos.
A Teresa, Ana, Adolfo, Aurora y Lurdes por su amable acogida, por su cariño
y amistad.
Prólogo
En los últimos años se ha visto un gran crecimiento en la generación de información,
debido principalmente a la automatización de procesos y a los avances en las
capacidades de almacenamiento de información. Cada día, la gente almacena gran
cantidad de información representada como datos para posteriormente realizar un
análisis y administración de estos. En muchas ciencias aplicadas está presente el
problema de revelar la estructura interna de esos datos ya que es imposible
analizarlos directamente. Una manera de interactuar con estos datos es clasificarlos
en pequeños grupos que describan sus características principales, basándose en la
similitud o diferencia entre ellos.
El problema de clasificar o estructurar esta información ha sido intensamente
estudiado en el área del Reconocimiento de Patrones no supervisado, en la que se
desarrollan técnicas de clustering para particionar un conjunto de datos en grupos
que brindan información adicional y conocimiento nuevo acerca de la estructura de
los datos.
El presente trabajo se enmarca dentro de lo que se denomina Reconocimiento
de Formas o Patrones no Supervisado y más concretamente, se centra en el estudio,
análisis y desarrollo de métodos de clustering en espacios métricos. En este sentido,
los algoritmos de clustering existentes en la bibliografía consultada basan su
funcionamiento en una serie de suposiciones acerca de la estructura de los datos, por
lo que tienen limitaciones entre las que podemos mencionar: construyen grupos de
formas específicas, no tienen en cuenta la presencia de ruido y el solapamiento entre
los grupos, etc.
A lo largo del presente trabajo, introducimos dos algoritmos de agrupamiento
jerárquicos basados en densidad sobre espacios métricos, llamados H-Density y
DHG con el objetivo fundamental de obtener grupos de diferentes tamaños y formas,
en presencia de ruido y solapamiento entre los grupos. Con las alternativas aquí
propuestas tratamos de superar algunas de las deficiencias que acabamos de apuntar.
Por otra parte, dada la importancia que tiene la validación de los resultados
del agrupamiento, es decir, la comprobación de que el agrupamiento obtenido
corresponde con la verdadera estructura presente en los datos, estudiamos un
conjunto de métodos de validación de agrupamientos, que en presencia de grupos
solapados y ruido no obtienen buenos resultados. Con el objetivo de superar estas
dificultades, diseñamos un nuevo esquema de validación de clustering capaz de
Prólogo
xiv
reconocer el número óptimo de clusters aún en presencia de ruido y grupos
solapados.
Es importante señalar también que, además de representar una labor de
búsqueda y recopilación sobre las diferentes técnicas de clustering y de validación de
clusters, esta tesis pretende fijar un punto de partida para el establecimiento de una
serie de conceptos, reglas y procedimientos con el fin de alcanzar los objetivos
básicos previamente enunciados. Por último, los diferentes esquemas presentados en
cada uno de los apartados son empíricamente comparados con varias técnicas, en
aras de evaluar y valorar las ventajas e inconvenientes del comportamiento exhibido
por cada uno de ellos.
La presente memoria de Tesis Doctoral se presenta estructurada en tres
módulos principales. El primero de ellos estará destinado íntegramente a la
introducción de los fundamentos teóricos, necesarios para disponer de una visión
global sobre el problema que vamos a tratar. En la segunda parte, se encuentran las
aportaciones de este trabajo, tanto en lo referente a la definición de los nuevos
conceptos, métodos y algoritmos, así como la experimentación y los resultados
obtenidos por cada uno de los métodos que aquí hemos desarrollado. Por último, la
tercera parte de la memoria recogerá las principales conclusiones que se pueden
extraer de los resultados mostrados, así como las posibles extensiones a considerar en
trabajos futuros.
Índice General
Parte I ......................................................................................................................... 29
Introducción y Fundamentos Teóricos ...................................................................... 29
Capítulo 1 ................................................................................................................... 31
Introducción ........................................................................................................... 31
1 Contexto ..................................................................................................... 31
2 Motivación y Objetivos Generales ............................................................ 34
3 Organización de la Memoria de Tesis ....................................................... 35
Capítulo 2 ................................................................................................................... 37
Técnicas de Clasificación no Supervisadas ........................................................... 37
1 Introducción ............................................................................................... 37
2 Formulación General de un Problema de Clasificación No Supervisada .. 39
3 Distancias o Métricas ................................................................................. 41
4 Fundamentos Estadísticos .......................................................................... 43
5 Algoritmos Jerárquicos .............................................................................. 44
6 Algoritmos de Partición ............................................................................. 49
7 Algoritmos Basados en Densidad .............................................................. 52
8 Agrupamiento Basado en Caminos ............................................................ 55
9 Estrategias de Co-ocurrencias .................................................................... 58
10 Otras Estrategias ........................................................................................ 58
Capítulo 3 ................................................................................................................... 61
Validación de Clusters ........................................................................................... 61
1 Introducción ............................................................................................... 61
2 Índices de Validación de Clusters .............................................................. 62
3 Estrategias Basadas en Estabilidad ............................................................ 66
Conclusiones. Introducción y Fundamentos Teóricos ....................................... 73
Parte II ........................................................................................................................ 75
Aportaciones .............................................................................................................. 75
Capítulo 4 ................................................................................................................... 77
Algoritmos de Agrupamiento ................................................................................ 77
1 Introducción ............................................................................................... 77
2 Algoritmo H-Density ................................................................................. 78
3 Algoritmo DHG (Density-based Hierarchical Gaussian) .......................... 83
4 Resultados Experimentales ........................................................................ 87
Bases de datos sintéticas ............................................................................ 88
Bases de datos reales .................................................................................. 90
Índice General
xvi
Algoritmo DBSCAN .................................................................................. 91
Algoritmo CURE ........................................................................................ 92
Algoritmo EM ............................................................................................ 93
Algoritmo k-Means ..................................................................................... 94
Algoritmo Path Based Clustering de Fischer y Buhmann (FB) ................. 95
Algoritmo H-Density .................................................................................. 96
Algoritmo DHG .......................................................................................... 97
5 Conclusiones ............................................................................................. 102
Capítulo 5 ................................................................................................................. 105
Validación de Clusters .......................................................................................... 105
1 Introducción .............................................................................................. 105
2 Indice σ ..................................................................................................... 106
3 Canal de Difusión en un Problema de Validación de Clusters ................. 110
3.1 Estabilidad del agrupamiento como una variación de la tasa de
transmisión de un canal de difusión ............................................................. 111
3.2 Selección del modelo de agrupamiento ............................................ 114
4 Resultados Experimentales ....................................................................... 116
4.1 Resultados de la aplicación del índice σ ........................................... 116
Bases de datos sintéticas ........................................................................... 117
Bases de datos reales ................................................................................ 123
4.2 Comparación con otras estrategias de validación de clusters ........... 124
4.3 Resultados de la aplicación del índice σ-BC para seleccionar el
número k de clusters ..................................................................................... 128
Bases de datos sintéticas ........................................................................... 129
Bases de datos reales ................................................................................ 135
4.4 Resultados de la aplicación del índice σ-BC para seleccionar el
modelo de agrupamiento .............................................................................. 140
Bases de datos sintéticas ........................................................................... 140
Bases de datos reales ................................................................................ 141
5 Conclusiones ............................................................................................. 141
Parte III ..................................................................................................................... 145
Conclusiones y Líneas Futuras ................................................................................. 145
Capítulo 6 ................................................................................................................. 147
Conclusiones Finales ............................................................................................ 147
1 Principales Aportaciones .......................................................................... 147
Aportaciones a los Métodos de Clasificación no Supervisados ............... 148
Aportaciones a los Algoritmos de Validación de Clusters ....................... 148
2 Conclusiones ............................................................................................. 149
Algoritmos de Clustering ......................................................................... 150
Validación de Clusters ............................................................................. 150
3 Publicaciones Relacionadas ..................................................................... 151
4 Posibles Extensiones ................................................................................ 152
Anexo A ................................................................................................................... 153
Descripción de las Bases de Datos Reales ........................................................... 153
Iris ............................................................................................................ 153
Cancer ...................................................................................................... 153
Diabetes ................................................................................................... 154
Liver ......................................................................................................... 154
Phoneme ................................................................................................... 154
Satimage ................................................................................................... 154
Anexo B ................................................................................................................... 157
Algoritmo EM ...................................................................................................... 157
Mixtura de Gausianas .............................................................................. 160
Anexo C ................................................................................................................... 165
Tópicos Fundamentales de Teoría de la Información .......................................... 165
1 Introducción ............................................................................................. 165
2 Cantidad de Información ......................................................................... 166
3 Entropía .................................................................................................... 167
4 Entropía Conjunta y Entropía Condicional .............................................. 168
5 Información Mutua .................................................................................. 168
Referencias Bibliográficas ....................................................................................... 171
Índice de Tablas
Parte I ......................................................................................................................... 29
Introducción y Fundamentos Teóricos ...................................................................... 29
Capítulo 1 ................................................................................................................... 31
Capítulo 2 ................................................................................................................... 37
Tabla 1. Coeficientes de Lance William para los algoritmos aglomerativos. ....... 46
Capítulo 3 ................................................................................................................... 61
Parte II ........................................................................................................................ 75
Aportaciones .............................................................................................................. 75
Capítulo 4 ................................................................................................................... 77
Tabla 2. Breve sumario de las bases de datos. ....................................................... 88
Tabla 3. Porcentaje de clasificación correcta de las diferentes estrategias. ......... 102
Capítulo 5 ................................................................................................................. 105
Tabla 4. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo
de agrupamiento H-Density. ................................................................................ 117
Tabla 5. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo
de agrupamiento EM. ........................................................................................... 118
Tabla 6. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo
de agrupamiento k-Means. ................................................................................... 121
Tabla 7. Índice de estabilidad σ para las bases de datos reales. ........................... 123
Tabla 8. Resultado del algoritmo de Ben-Hur (2002) para todas las bases de datos
usando H-Density. ............................................................................................... 125
Tabla 9. Resultado del algoritmo de Tibshirani (2005) para todas las bases de
datos usando H-Density. ...................................................................................... 126
Tabla 10. Comparación de las diferentes estrategias para todas las bases de datos
usando H-Density. ............................................................................................... 127
Tabla 11. Comparación de las diferentes estrategias para todas las bases de datos
usando EM. .......................................................................................................... 127
Tabla 12. Comparación de las diferentes estrategias para todas las bases de datos
usando k-Means. .................................................................................................. 128
Tabla 13. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento DHG, según las probabilidades marginales (72). .... 129
Tabla 14. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento EM, según las probabilidades marginales (72). ....... 130
Tabla 15. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento k-Means, según las probabilidades marginales (72). 130
Índice de Tablas
xx
Tabla 16. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento DHG, según las probabilidades (73) y un vecino por
clase. ..................................................................................................................... 131
Tabla 17. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento EM, según las probabilidades (73) y un vecino por
clase. ..................................................................................................................... 132
Tabla 18. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento k-Means, según las probabilidades (73) y un vecino
por clase. ............................................................................................................... 132
Tabla 19. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento DHG, según las probabilidades (73) y tres vecinos por
clase. ..................................................................................................................... 133
Tabla 20. Índice de estabilidad σ-BC para las bases de datos sintéticas con el
algoritmo de agrupamiento EM, según las probabilidades (73) y tres vecinos por
clase. ..................................................................................................................... 133
Tabla 21. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el
algoritmo de agrupamiento k-Means, según las probabilidades (73) y tres vecinos
por clase. ............................................................................................................... 134
Tabla 22. Número de clusters seleccionado por el índice σ-BC con cada uno de los
algoritmos de agrupamiento y para cada una de las estrategias para estimar las
probabilidades de transmisión. ............................................................................. 135
Tabla 23. Índice de estabilidad sobre las bases de datos reales empleando el
algoritmo DHG, según fórmula (72). ................................................................... 136
Tabla 24. Índice de estabilidad σ-BC sobre las bases de datos reales empleando el
algoritmo EM, según fórmula (72). ...................................................................... 137
Tabla 25. Índice de estabilidad σ-BC sobre las bases de datos reales empleando el
algoritmo k-Means, según fórmula (72). .............................................................. 138
Tabla 26. Número de clusters seleccionado por el índice σ-BC con cada uno de los
algoritmos de agrupamiento sobre las bases de datos reales y para cada una de las
estrategias para estimar las probabilidades de transmisión. ................................. 139
Tabla 27. Valor de la información mutua promedio en el nivel de mínima varianza
con las probabilidades marginales (72) sobre las bases de datos sintéticas. ........ 140
Tabla 28. Valor de la información mutua promedio en el nivel de mínima varianza
con las probabilidades marginales (72) sobre las bases de datos reales. .............. 141
Parte III ..................................................................................................................... 145
Conclusiones y Líneas Futuras ................................................................................. 145
Capítulo 6 ................................................................................................................. 147
Anexo A .................................................................................................................... 153
Anexo B .................................................................................................................... 157
Anexo C ................................................................................................................... 165
Referencias Bibliográficas ....................................................................................... 171
Índice de Figuras
Parte I ......................................................................................................................... 29
Introducción y Fundamentos Teóricos ...................................................................... 29
Capítulo 1 ................................................................................................................... 31
Figura 1. Procesos de un sistema automático de Reconocimiento de Patrones. .... 32
Capítulo 2 ................................................................................................................... 37
Figura 2. Definiciones de proximidad entre clusters. ............................................ 44
Figura 3. Definiciones de punto central, borde y ruido. ........................................ 53
Capítulo 3 ................................................................................................................... 61
Parte II ........................................................................................................................ 75
Aportaciones .............................................................................................................. 75
Capítulo 4 ................................................................................................................... 77
Figura 4. Estrategia basada en densidad local. ...................................................... 79
Figura 5. Medidas de solapamiento entre clusters. ................................................ 82
Figura 6. Distancia entre los puntos de mayor densidad. ...................................... 85
Figura 7. Bases de datos gausianas: a) G4, b) G6, c) G6-II. .................................. 89
Figura 8. Bases de datos: a) 3AC, b) 2SA ............................................................. 89
Figura 9. Bases de datos: a) DS1, b) DS2 .............................................................. 90
Figura 10. Base de datos House: a) Imagen original, b) Representación en el
espacio ab ............................................................................................................... 90
Figura 11. Resultados del algoritmo DBSCAN sobre la base de datos G6: a)
División en tres clusters, b) Incremento de los puntos ruido, c) Asignación de los
puntos ruido al cluster más cercano. ...................................................................... 91
Figura 12. Resultados del algoritmo DBSCAN: a) Base de datos G4, b) Base de
datos G6-II ............................................................................................................. 92
Figura 13. Resultados del algoritmo CURE: a) Base de datos G4, b) Base de datos
G6-II, c) Base de datos G6. .................................................................................... 93
Figura 14. Resultados del algoritmo EM: a) DS1, b) DS2. ................................... 94
Figura 15. Resultados del algoritmo k-Means: a) DS1, b) DS2. ........................... 94
Figura 16. Resultados del algoritmo k-Means: a) 3AC, b) 2SA. ........................... 95
Figura 17. Resultados del algoritmo FB: a) 3AC, b) 2SA. .................................... 95
Figura 18. Resultados del algoritmo FB: a) G4, b) DS1. ....................................... 96
Figura 19. Resultado del algoritmo FB: DS2. ....................................................... 96
Figura 20. Bases de datos: a) G3, b) G4-II. ........................................................... 97
Figura 21. Resultado del algoritmo DHG sobre la base de datos 3AC-II.............. 98
Índice de Figuras
xxiv
Figura 22. Resultados del algoritmo CURE sobre la base de datos House: a) 5
clusters, b) Trece clusters. ...................................................................................... 99
Figura 23. Resultado del algoritmo k-Means sobre la base de datos House:
a).Imagen original, b) Imagen obtenida después del etiquetado, c) División en 5
clases en el espacio ab. ......................................................................................... 100
Figura 24. Resultados del algoritmo FB sobre la base de datos House: a) 5 clases,
b) 6 clases, c) 7 clases. .......................................................................................... 100
Figura 25. Resultado del algoritmo H- Density sobre la base de datos House: a)
Imagen original, b) Imagen obtenida luego del etiquetado, c) División en 5 clases
en el espacio ab. .................................................................................................... 101
Figura 26. Resultado del algoritmo DHG sobre la base de datos House: a) Imagen
original, b) Imagen obtenida luego del etiquetado, c) División en 5 clases en el
espacio ab. ............................................................................................................ 101
Capítulo 5 ................................................................................................................. 105
Figura 27. Canal de comunicación ....................................................................... 107
Figura 28. Canal de difusión................................................................................. 110
Figura 29. Diagrama de Venn que indica la región ocupada por la información
mutua común I(X;Y1;Y2) del canal de difusión ..................................................... 114
Figura 30. Resultados del algoritmo H-Density en el nivel correspondiente al valor
determinado por el índice σ. Arriba: a) G4, b) G6, c) G6-II. Abajo: d) 3AC, e)
2SA, f) DS1. ......................................................................................................... 118
Figura 31. Resultados del algoritmo EM en el nivel correspondiente al valor
determinado por el índice σ: a) G4, b) G6 (tres clases), c) G6 (seis clases). ........ 119
Figura 32. Resultados del algoritmo EM sobre la base de datos G6-II, en el nivel
correspondiente al valor determinado por el índice σ: a) 5 clases, b) seis clases. 119
Figura 33. Resultados del algoritmo EM sobre la base de datos DS1 en el nivel de
seis clases. ............................................................................................................. 120
Figura 34. Resultado más estable del índice σ empleando el algoritmo EM sobre la
base de datos DS1. ................................................................................................ 120
Figura 35. Nivel seleccionado por el índice σ cuando se aplica el algoritmo EM
sobre 3AC. ............................................................................................................ 120
Figura 36. Resultados del algoritmo k-Means en el nivel correspondiente al valor
determinado por el índice σ: a) G4, b) G6-II. ....................................................... 121
Figura 37. Resultados del algoritmo k-Means sobre la base de datos G6 en el nivel
de seis clases: a) más frecuente, b) y c) menos frecuente. .................................... 122
Figura 38. Resultados del algoritmo k-Means en el nivel correspondiente al valor
determinado por el índice σ sobre las base de datos: a) 3AC, b) 2SA, c) DS1. ... 122
Figura 39. Nivel detectado por el índice σ sobre la base de datos House, para cada
uno de los algoritmos de agrupamiento empleados: a) H-Density, b) EM, c) k-
Means. .................................................................................................................. 123
Figura 40. Imagen BAR: a) Imagen original, b) Resultado del agrupamiento
empleando el algoritmo DHG en el nivel de 10 clases seleccionado por el índice σ-
BC. ....................................................................................................................... 137
Parte III .................................................................................................................... 145
Conclusiones y Líneas Futuras ................................................................................ 145
Capítulo 6 ................................................................................................................. 147
Anexo A ................................................................................................................... 153
Anexo B ................................................................................................................... 157
Anexo C ................................................................................................................... 165
Figura 41. Relación entre información mutua y entropía. ................................... 170
Referencias Bibliográficas ....................................................................................... 171
Notación
Conjunto de datos. ...................................................................................................... X
Conjunto de etiquetas. ................................................................................................. Y
Elemento de la base de datos. ...................................................................................... x
Función de probabilidad. ............................................................................................ p
Función distancia. ....................................................................................................... d
Información mutua. ...................................................................................................... I
Número de grupos. ....................................................................................................... k
Número de modos. ............................................................................................ kmodos
Número de rasgos. ...................................................................................................... n
Número de realizaciones del experimento. ................................................................ M
Número de vecinos. .................................................................................................... K
Radio de la vecindad. .................................................................................................. R
Regla de decisión. ........................................................................................................ δ
Talla del conjunto de datos. ........................................................................................ N
Parte I
Introducción y Fundamentos
Teóricos
Capítulo 1
Introducción
1 Contexto
A lo largo de este tiempo, muchas ciencias han participado en el desarrollo exitoso
de herramientas con el fin de solucionar diversos problemas prácticos y teóricos. El
Reconocimiento de Patrones (Pattern Recognition) es una zona del conocimiento
relativamente joven, de apenas unos 45 años, de carácter interdisciplinario,
encargada de diseñar o programar sistemas automáticos capaces de resolver
problemas de muy diversas áreas. Con la llegada y el desarrollo vertiginoso de los
ordenadores, se abre un nuevo horizonte lleno de posibilidades, pues además de que
pueden almacenar gran cantidad de información, con ellos se pueden diseñar o
programar sistemas automáticos de reconocimiento de gran utilidad para muchas
ciencias.
Siguiendo la definición de Watanabe [Wat, 1985], un patrón es una entidad a
la que se le puede dar un nombre y que está representada por un conjunto de
propiedades mesurables y las relaciones entre ellas (vector de características).
Patrón es sinónimo de objeto, éste es un concepto con el cual representamos
los elementos sujetos a estudio. Por ejemplo, un patrón puede ser una señal sonora y
su vector de características, el conjunto de coeficientes espectrales extraídos de ella
(espectrograma). Otro ejemplo podría ser una imagen de una cara humana de las
cuales se extrae el vector de características formado por un conjunto de valores
numéricos calculados a partir de la misma. El Reconocimiento de Patrones se aplica
en una gran variedad de disciplinas científicas, como biología, psicología, medicina,
geología, visión por computador, inteligencia artificial, teledetección, entre otras.
Un sistema automático de Reconocimiento de Patrones puede ser modelado
de la misma manera que los procesos perceptuales del ser humano: antes del
reconocimiento, nuestros órganos sensitivos deben percibir el objeto, luego, para
obtener un significado de dicho objeto, se debe haber percibido previamente dicho
objeto u otro de la misma clase y, finalmente, se debe recordar la pasada percepción
del objeto para establecer la correspondencia o equivalencia entre la percepción
pasada y la presente. Un sistema automático de Reconocimiento de Patrones se
puede dividir en tres etapas fundamentales [Duda. H, 1973] (ver Figura. 1):
Capítulo 1
32
1. Adquisición de datos, en la que se obtiene una representación del objeto
como resultado de un conjunto de mediciones.
2. Extracción de características, donde se realiza un proceso interpretativo, cuyo
resultado se considera como una nueva representación del objeto de la que se
extrae información relevante sobre el mismo.
3. Toma de decisiones, que corresponde a la clasificación propiamente dicha o
proceso de identificación.
Figura 1. Procesos de un sistema automático de Reconocimiento de Patrones.
La función del sensor es hacer la medición, es decir, dar una representación
concreta de los elementos a ser clasificados, con el objetivo de entender
completamente las propiedades que distinguen al objeto. La extracción de
características se encarga de extraer información discriminatoria con el objetivo de
eliminar información redundante o irrelevante, reducir la dimensionalidad del
problema y maximizar los rasgos discriminatorios. La etapa de clasificación tiene
como objetivo asignar los objetos de clase desconocida a la categoría apropiada, o
sea, es la etapa en la que se asigna al objeto una etiqueta de clase.
Dentro del Reconocimiento de Patrones podemos señalar tres grandes
paradigmas. El primero se refiere al Reconocimiento Sintáctico, en el que se buscan
las relaciones estructurales que guardan los objetos en estudio, es decir, busca la
cantidad de información que una muestra tiene sobre otra muestra y el metalenguaje
con el que este último pudo ser capaz de descubrirlo. Para ello, hace uso de
descriptores sintácticos con la ayuda de la teoría de los lenguajes formales
[Fukuyama, 1982]. Entre las aplicaciones, dentro de este paradigma, podemos
mencionar el análisis de secuencias de proteínas, así como también biosecuencias de
ADN para evaluar la eficacia de alfabetos reducidos de aminoácidos,
correspondientes estas investigaciones al campo de la biología molecular.
La segunda vertiente que existe dentro del Reconocimiento de Patrones es el
Reconocimiento Lógico Combinatorio. Este enfoque se basa en la idea de que la
modelación del problema debe ser lo más cercana posible a la realidad del mismo,
sin hacer suposiciones que carezcan de fundamento. Uno de los aspectos esenciales
de este tipo de enfoque es que las características utilizadas para describir a los
objetos de estudio deben ser tratadas cuidadosamente. Debemos señalar que, para
Introducción
33
realizar el reconocimiento, se auxilian de formalismos matemáticos que le permiten
derivar nuevos conocimientos a partir de conocimientos existentes.
El tercer grupo o paradigma es el Reconocimiento Estadístico de Formas, el
cual es una disciplina científica donde un patrón se representa por un vector
numérico de dimensión n. De esta forma, un patrón es un punto en un espacio n-
dimensional (de características). Un algoritmo de Reconocimiento Estadístico de
Formas (REF) funciona de dos maneras diferentes: entrenamiento y reconocimiento.
En el modo de entrenamiento, se diseña el extractor de características para
representar los patrones de entrada y se entrena al clasificador con un conjunto de
datos de entrenamiento previamente definidos, de forma que el número de patrones
mal identificados se minimice. En el modo de reconocimiento, el clasificador ya
entrenado toma como entrada el vector de características de un patrón desconocido y
lo asigna a una de las clases o categorías según el conocimiento adquirido
previamente en el modo de entrenamiento.
Entre los clasificadores estadísticos también suele haber dos grandes grupos.
Por una parte, los clasificadores paramétricos son aplicados cuando es conocida la
distribución de probabilidades de las clases, siendo el clasificador de Bayes su
máximo representante. El otro grupo está integrado por los métodos de clasificación
no paramétricos, los cuales se aplican en problemas donde no se conoce la
distribución de probabilidades de clases.
También, los algoritmos dedicados al Reconocimiento de Patrones,
dependiendo de las diferentes maneras en que utilizan la información suministrada,
suelen dividirse en tres categorías:
1. Algoritmos de clasificación supervisada
2. Algoritmos de clasificación parcialmente supervisada
3. Algoritmos de clasificación no supervisada
Los algoritmos de clasificación supervisada operan usualmente sobre la
información suministrada por un conjunto de muestras, un conjunto de patrones,
ejemplos o prototipos de entrenamiento que se asumen como representantes de clases
relevantes y poseen una etiqueta de clase correcta. Ese conjunto de patrones recibe el
nombre de conjunto de entrenamiento (Training Set, TS).
Si no se dispone del conjunto de entrenamiento, es decir, no existe
conocimiento acerca de la etiqueta de los patrones, entonces para clasificar patrones
se necesita de un proceso previo de análisis de los datos que se conoce como
Clasificación no Supervisada, Aprendizaje no Supervisado o Técnicas de
Capítulo 1
34
Agrupamiento (clustering), que proporcionan un conocimiento de la estructura de los
datos.
Los algoritmos de clasificación parcialmente supervisada sólo tienen como
información a priori muestras de algunas de las clases, y en algunos casos, se
desconoce el número total de clases del universo en estudio, o, en otros casos, se
dispone de muy pocas muestras por cada clase.
En el mundo real, no siempre se conoce la distribución de las clases e incluso,
aún conociéndola, es difícil extraer objetos representativos de cada clase para
preparar el conjunto de entrenamiento. Dentro del Reconocimiento de Formas, las
técnicas no supervisadas tienen como objetivo la inferencia y extracción de
conocimiento a partir de volúmenes de datos no clasificados, con el fin de poder
extraer relaciones e inferir nuevo conocimiento acerca de la organización interna
para el tratamiento automático de los datos. Este campo está teniendo especial
relevancia en la disciplina de Reconocimiento de Patrones, debido a la necesidad de
tratar grandes volúmenes de datos en la web y otras aplicaciones de gran impacto.
La presente Tesis Doctoral se enmarca dentro del Reconocimiento Estadístico
de Formas o Patrones, específicamente en Aprendizaje no Supervisado. Todo el
trabajo de investigación que ha precedido a esta tesis se ha llevado a cabo dentro del
Grupo de Visión por Computador de la Universidad Jaume I de Castellón.
2 Motivación y Objetivos Generales
En muchas áreas, se incrementa la necesidad de obtener información de un conjunto
de datos. Esto requiere de análisis y clasificación de los datos con el objetivo de
descubrir características comunes en individuos pertenecientes a un mismo grupo.
Los algoritmos de agrupamiento son estrategias encargadas de descubrir la estructura
interna de los datos, pero cada uno de ellos supone condiciones en la base de datos
que los hace eficientes para algunos tipos de datos e ineficientes para otros. Uno de
los objetivos fundamentales de esta Tesis Doctoral es el diseño de un algoritmo de
agrupamiento capaz de etiquetar correctamente los puntos de una base de datos en
presencia de ruido y solapamiento entre los grupos.
Debido a la diversidad de técnicas de agrupamiento, se pueden obtener
diferentes soluciones al intentar dividir en grupos una base de datos, por lo que es
preciso decidir cuál de las estrategias de agrupamiento interpreta mejor la verdadera
estructura presente en la base de datos. Las técnicas encargadas de realizar esta tarea
se conocen por el nombre de validación de clusters. El segundo objetivo de esta
Introducción
35
memoria de tesis está relacionado con la evaluación del algoritmo de agrupamiento
mediante una técnica de validación de clusters.
Más concretamente, los objetivos perseguidos con la presente Tesis Doctoral
son los siguientes:
1. Diseñar un algoritmo de agrupamiento jerárquico basado en densidad, que sea
capaz de encontrar clusters de diferentes tamaños, formas y densidades, en
presencia de ruido y clases solapadas.
2. Diseñar un esquema de validación de clusters para determinar el número
correcto de clusters y el modelo de clustering que mejor se adapta a la
estructura real de la base de datos.
Por último, podemos añadir que esta Tesis Doctoral contiene un apartado de
revisión y recopilación sobre los diferentes métodos de clasificación no supervisada
y validación de clusters, así como también los resultados de la experimentación
realizada sobre bases de datos reales y sintéticas para mostrar la validez de los
algoritmos propuestos.
3 Organización de la Memoria de Tesis
A partir de los objetivos establecidos en la sección anterior, hemos estructurado la
presente memoria de Tesis Doctoral en dos partes principales, cada una de las cuales
se encuentra organizada en una serie de capítulos. Una primera parte se dedica a la
presentación de los fundamentos teóricos sobre los que se basará la totalidad de la
tesis. La segunda parte se refiere a las aportaciones de este trabajo, en consonancia
con los objetivos previamente marcados. En la tercera parte, podemos encontrar las
conclusiones globales y las posibles líneas de investigación futuras. Por último, la
bibliografía utilizada a lo largo de la tesis y los anexos se presentan al final de esta
memoria.
En el Capítulo 2, se hace una introducción general sobre los conceptos
básicos utilizados en el campo del Reconocimiento de Formas, haciendo hincapié
fundamentalmente en las técnicas de clasificación no supervisada. Además, contiene
la revisión bibliográfica de diversos métodos de agrupamiento, enfatizando en los
algoritmos que se utilizaron en los diferentes experimentos explicados en los
capítulos relacionados con las aportaciones del trabajo.
El Capítulo 3 está dedicado a la exposición de diferentes estrategias de
validación de clusters, destacando aquí las tendencias que existen en la literatura
acerca de la estabilidad de los agrupamientos.
Capítulo 1
36
En el Capítulo 4, se exponen dos algoritmos de agrupamiento diseñados con
el objetivo de descubrir clusters de diferentes formas, tamaño y densidades, en
presencia de ruido y solapamientos entre grupos. Este capítulo contiene, además, los
experimentos que permiten evaluar la efectividad de estos nuevos algoritmos sobre
un conjunto de bases de datos reales y sintéticas que contienen clusters de diversas
formas, tamaños y densidades.
En el Capítulo 5, se realiza una presentación de las estrategias de validación
diseñadas, obtenidas a partir del empleo del concepto de información mutua y una
estrategia basada en la estabilidad de los clusters mediante la perturbación de los
datos. Del mismo modo, se valida su comportamiento mediante un exhaustivo
análisis empírico sobre las diferentes bases de datos sintéticas y reales utilizadas a lo
largo del trabajo.
Finalmente, el Capítulo 6 recoge las conclusiones generales referente a la
totalidad de la tesis y pone de manifiesto sus principales aportaciones en el campo
del Reconocimiento Estadístico de Formas. Además, se examinan las diversas
posibilidades de extensión sobre el trabajo ya realizado, y se marcan las direcciones
que podrían tomar las futuras líneas de investigación.
También escribimos tres Anexos en los que se proporcionan ciertos detalles
relacionados con diferentes partes del trabajo desarrollado en esta memoria de tesis.
Capítulo 2
Técnicas de Clasificación no
Supervisadas
1 Introducción
El aprendizaje no supervisado es muy importante cuando tenemos muestras sin
etiquetas de clase, cuando el costo de etiquetarlas por un experto es alto o cuando los
patrones pueden variar con el tiempo, por lo que es necesario primero procesar los
datos para luego clasificar. La principal ventaja que presenta la clasificación no
supervisada es que se puede obtener un conjunto de entrenamiento empleando
muestras no etiquetadas.
Actualmente, en muchas aplicaciones reales (biometría, categorización de
textos, búsqueda en bases de datos multimedia, reconocimiento de imágenes
multiespectrales, etc.), el coste de un conjunto de entrenamiento resulta bastante alto,
por lo que podría ser beneficioso aplicar primero a determinadas muestras cuya clase
se desconoce, un algoritmo de agrupamiento para luego inferir propiedades en la
población en estudio. Se trata de construir clasificadores sin información previa, o
sea, a partir de objetos no etiquetados con el objetivo de descubrir la estructura de los
datos.
Bajo el nombre genérico de algoritmos de agrupamiento, se incluyen todo un
conjunto de procesos cuya finalidad general será dividir un conjunto de objetos en
clases, para obtener un subconjunto representativo del conjunto de entrenamiento
inicial que posteriormente pueda utilizarse en una regla de clasificación supervisada.
En general, la clasificación no supervisada o agrupamiento (clustering)
consiste en dividir el conjunto de objetos en grupos de objetos similares llamados
clusters, de modo tal que objetos pertenecientes a un mismo grupo son más similares
que objetos de grupos diferentes.
El problema de formar grupos en un conjunto de datos es muy importante
para el conocimiento del comportamiento de una población, de la cual sólo se tiene
una cantidad N de sus elementos. Al estudiar el proceso de división en clases, nos
damos cuenta de que cada técnica está diseñada para realizar una clasificación de tal
Capítulo 2
38
modo que cada grupo sea lo más homogéneo y lo más diferente de los demás como
sea posible. El resultado de cada método de agrupamiento dependerá del algoritmo
en concreto, del valor de los parámetros y de la medida de similaridad / disimilaridad
adoptada.
En la literatura consultada, los métodos de agrupamiento suelen dividirse de
diferentes maneras, entre las que mencionaremos:
1. Teniendo en cuenta la existencia o no de una función criterio a optimizar:
1.1. Directos o heurísticos: son los que no optimizan ninguna función
objetivo.
1.2. Indirectos o por optimización: son los que optimizan alguna función
objetivo.
2. Según la construcción del agrupamiento:
2.1. Aglomerativos o incrementales (bottom-up), generalmente parten de
patrones aislados y van uniendo grupos de acuerdo a alguna función
de similaridad / disimilaridad.
2.2. Divisivos o decrementales (top-down), parten de agrupamientos ya
establecidos, generalmente de un solo grupo, y van dividiendo los
grupos de partida hasta obtener grupos adecuados.
2.3. Mixtos, emplean diversas estrategias en su desempeño.
3. Según la información a priori acerca del conocimiento del número de
clusters:
3.1. Si se conoce el número de clusters.
3.2. Si no se conoce el número de clusters.
A partir de aquí, en este capítulo, nos centramos en el análisis de los aspectos
teóricos más relevantes de los métodos de clasificación no supervisada basados en la
estructura geométrica de los grupos, por lo que también haremos una breve
exposición de las métricas más utilizadas en la literatura consultada dedicada a este
tema y, posteriormente, formularemos las bases de los algoritmos de agrupamiento
probabilísticos. Además, haremos énfasis en los algoritmos relacionados con este
trabajo. Para ello, comenzaremos dando una visión general de cada técnica para,
posteriormente, pasar a presentar los diferentes algoritmos. Esta categorización de las
técnicas de agrupamiento nos permitirá distinguir entre los diversos métodos de
agrupamiento.
Técnicas de Clasificación no Supervisadas
39
2 Formulación General de un Problema de Clasificación
No Supervisada
Sea X = {x1, x2, …, xN} el conjunto de datos o, análogamente, objetos, ejemplos,
casos, patrones, n-uplas, puntos, donde ( )iniii xxx=x ,...,, 21 pertenece a un espacio de
atributos, para cada i = 1, …, N, y cada componente xij (j = 1, …, n) es un atributo
(análogamente, rasgo, variable, dimensión o componente) de modo tal que el
conjunto de objetos forma una matriz Nxn empleada por la mayoría de los algoritmos
de agrupamiento.
La meta de todo algoritmo de agrupamiento es asignar cada punto a un
sistema finito de subconjuntos o clusters que usualmente no se intersectan entre sí y
cuya unión es igual al conjunto de datos completo con la posible excepción de
outliers, de modo tal que objetos similares pertenezcan al mismo cluster, mientras
que los objetos de clusters diferentes sean lo menos parecidos posible.
En [Duda y Hart, 1973], aparece la introducción clásica de los algoritmos de
agrupamiento. En [Dempster, 1977] y [Fukunaga, 1990], encontramos el enfoque
estadístico de las técnicas de clasificación no supervisada; en [Jain, 1999], aparece
un resumen de diferentes técnicas de agrupamiento.
Los algoritmos de agrupamiento han sido empleados en reconocimiento del
habla, en segmentación de imágenes y visión por computador [Jain, 1966], [Jain,
2000]; en minería de datos para extraer conocimiento en bases de datos, en
recuperación de información y minería de textos [Salton, 1980], [Zhai, 2004],
[Cutting, 1992], [Dhillon, 2002], en aplicaciones de bases de datos espaciales [Xu,
1998] y [Ester, 2000], en análisis de datos heterogéneos [Cadez, 2001], en
aplicaciones Web [Her, 2001, Foss, 2001], en biología computacional para el análisis
de ADN [Xu, 2002] y muchas otras aplicaciones.
Los algoritmos de agrupamiento pueden dividirse en varias categorías según
el procedimiento que utilizan para agrupar los objetos:
1. Algoritmos jerárquicos, que pueden ser aglomerativos y divisivos.
2. Métodos por partición, entre ellos: algoritmos de reubicación, agrupamientos
probabilísticos, métodos de k-medoides y métodos k-Medias (k-Means).
3. Algoritmos basados en densidad, entre ellos los algoritmos de agrupamiento
por conectividad basados en densidad y los agrupamientos basados en
funciones de densidad.
4. Métodos basados en rejillas.
Capítulo 2
40
5. Métodos basados en co-ocurrencia de datos categóricos.
6. Algoritmos mixtos.
Los algoritmos jerárquicos, como su nombre indica, construyen una jerarquía
de agrupamientos, uniendo o dividiendo los grupos de acuerdo a una cierta función
de similaridad/disimilaridad entre los grupos. En otras palabras, construyen un árbol
de clusters llamado dendograma. Tal enfoque permite estudiar los datos con
diferentes niveles de glanularidad.
Los métodos de agrupamiento jerárquicos se categorizan en aglomerativos
(bottom-up) y divisivos (top-down). Un agrupamiento aglomerativo, generalmente,
comienza con grupos unitarios (singleton clusters) y, recursivamente, une dos o más
clusters apropiados. Un agrupamiento divisivo, generalmente, comienza con un sólo
cluster en el que están todos los puntos o datos y, recursivamente, divide el cluster
más apropiado. El proceso continúa hasta que se alcanza algún criterio de parada
(frecuentemente el número k de clusters).
Entre las ventajas de los algoritmos de agrupamiento jerárquicos se puede
mencionar la flexibilidad con respecto al nivel de granularidad, son fáciles de
manejar y son aplicables a cualquier tipo de atributo. Entre las desventajas se
encuentra la no existencia de un criterio de parada y que, luego de construidos los
clusters, no vuelven a ser visitados para mejorarlos.
Los métodos por partición emplean diferentes técnicas de reubicación para
asignar los puntos o datos a uno de los k clusters; algunos buscan puntos específicos
para luego reubicar los restantes, otros tienen un enfoque probabilístico. A diferencia
de los métodos jerárquicos tradicionales, en algunos casos, los clusters son
revisitados después de construidos y los puntos reubicados para mejorar el
agrupamiento.
Estos algoritmos muchas veces asumen un conocimiento a priori del número
de clusters en que debe ser dividido el conjunto de datos. La idea más usada es hallar
los centroides, uno para cada cluster y, luego, ubicar los restantes puntos en el grupo
del centroide más cercano. Este método tiene como desventaja que fallan cuando los
puntos de un cluster están muy cerca del centroide de otro grupo.
Los algoritmos basados en densidad tratan de identificar clusters en zonas
altamente pobladas. Emplean diferentes técnicas para determinar los grupos: por
grafos, basadas en histogramas, kernels, aplicando la regla K-NN o tratando de
descubrir subgrupos denso-conectados.
Los algoritmos basados en rejillas trabajan con los datos indirectamente,
construyendo resúmenes de los datos sobre el subconjunto del espacio de atributos,
Técnicas de Clasificación no Supervisadas
41
realizan una segmentación del espacio y seleccionan segmentos apropiados, mientras
que los basados en co-ocurrencia consideran que el concepto de similaridad por sí
solo no es suficiente para agrupar algunos datos, por lo que introducen otros
conceptos como, por ejemplo, los vecinos compartidos.
Los algoritmos mixtos vinculan al menos dos de las técnicas antes
mencionadas para realizar el agrupamiento; fundamentalmente, las técnicas
jerárquicas aparecen en muchos de ellos.
Para realizar el agrupamiento de los objetos, es necesario determinar cuándo
dos objetos del espacio son “parecidos” y cuándo no. Con este fin, se definen las
funciones de similaridad o de disimilaridad, entre estas últimas se encuentran las
métricas o distancias.
Muchos de los algoritmos de agrupamiento basan su efectividad en la
distribución de los objetos del conjunto de datos en el espacio y en cuán alejados
están entre ellos. Es por ello que es preciso definir alguna medida de distancia entre
los objetos de X, mediante la cual podamos asignarle a cada muestra, una clase
determinada.
3 Distancias o Métricas
En el Reconocimiento de Patrones, la distancia entre dos objetos cualesquiera del
espacio es una medida de cuán similares son de acuerdo a sus características, ya que
éstas se escogen de forma tal que mientras más parecidos sean los objetos menor
debe ser la distancia entre ellos y, por el contrario, los objetos muy lejanos deben ser
poco similares.
Definición: Un espacio métrico es un par (X, d) donde X es un conjunto (X ≠ ∅) y d
una distancia o métrica definida sobre X. Una función d: XxX → ℜ+, se dice que es
una distancia o métrica si satisface los siguientes axiomas:
1 ( ) 0, ≥yxd ∀ x, y ∈ X, y ( ) 0, =yxd si y solo si x = y
2 ( ) ( )xydyxd ,, = ∀ x, y ∈ X (simetría)
3 ( ) ( ) ( )zydyxdzxd ,,, +≤ ∀ x, y, z ∈ X (desigualdad triangular)
La métrica más frecuentemente utilizada en toda la literatura es la métrica
Euclídea:
Capítulo 2
42
( ) ( )∑ −n
=k
jkikji )(Ox)(OxOOd1
2,
donde Oi y Oj son los objetos para los cuales se desea calcular la distancia, n es el
número de características de los objetos del espacio y xk(Oi), xk(Oj) es el valor del
atributo k-ésimo en los objetos Oi y Oj, respectivamente.
Otras métricas que podemos mencionar son:
1. Minkowsky:
| |p
n
=k
p
jkikji )(Ox)(Ox=)O,d(O
/1
1
−∑ Zp∈ , p ≥ 2.
2. Manhattan:
| |∑ −n
=k
jkikji )(Ox)(Ox=)O,d(O1
3 Chebychev:
| |)(Ox)(Ox=)O,d(O jkiknk
ji −≤≤1
max
4 Camberra:
∑
−n
=k jkik
jkik
ji)(Ox+(Ox
)(Ox)(Ox=)O,d(O
1 )
5 Función de Correlación:
∑ ∑
∑
−−
−−
n
=k
n
=k
kjkkik
n
=k
kjkkik
ji
)µ)(O(x)µ)(O(x
)µ)(O)(xµ)(O(x
=)O,d(O
1 1
22
1
donde µk es el valor promedio para el atributo k en el conjunto de entrenamiento.
6 Distancia de Mahalanobis
)O(O)O(O=)O,d(O ji
T
jiji −Σ− −1
siendo Σ la matriz de covarianzas.
Técnicas de Clasificación no Supervisadas
43
La distancia de Mahalanobis (1936), a diferencia de la distancia Euclídea,
tiene en cuenta las correlaciones del conjunto de datos y no depende de la escala de
las mediciones.
En la literatura, se han propuesto diversas funciones para calcular la distancia
entre objetos con atributos no numéricos, por ejemplo en [Stanfill, 1986], [Wilson,
2000] y [Olvera, 2005].
4 Fundamentos Estadísticos
La teoría de la probabilidad y los métodos bayesianos son algunas de las técnicas que
más se han utilizado en Reconocimiento de Patrones. Según el conocimiento que se
tiene acerca de la distribución de los datos, se puede distinguir entre métodos de
clasificación paramétricos y no paramétricos. En los métodos de clasificación
paramétricos, se supone el conocimiento de la estructura estadística de las clases y se
modelan mediante funciones de densidad conocidas. En el caso no paramétrico, no se
conoce a priori la forma funcional de las funciones de densidad y se trata de estimar
ésta, pues la única información disponible es la suministrada por un conjunto de
prototipos.
En teoría de las probabilidades, el teorema de Bayes es la regla básica para
realizar inferencias y viene representado por la siguiente expresión:
p(x)
p(h)h)p(x=x)p(h
.//
(1)
donde, p(h) y p(x) son la probabilidad a priori de la hipótesis h y de las observaciones
x, respectivamente y p(h| x) y p(x| h) las probabilidades condicionadas. A p(x| h) se le conoce como la verosimilitud (likelihood) de que la hipótesis h haya producido el
conjunto de observaciones x y a p(h| x), probabilidad a posteriori.
El teorema de Bayes nos facilita un método sencillo y con una semántica
clara para resolver el problema de la clasificación pues si se conoce la probabilidad a
posteriori de que un objeto x pertenezca a una clase, se decide escoger aquella que
presente el mayor valor:
iCx∈ si jiMjxcpxcp ji ≠≤≤> 1)/()/( (2)
Este criterio constituye la regla de decisión de Bayes de error mínimo, sobre
la cual se basan la mayoría de los métodos de clasificación pertenecientes al
Reconocimiento Estadístico de Formas, constituye un método práctico para realizar
inferencias a partir de los datos que facilitan la comprensión de los mismos.
Capítulo 2
44
A continuación, desarrollamos los aspectos teóricos más relevantes de los
diferentes métodos de agrupamiento.
5 Algoritmos Jerárquicos
Las estrategias jerárquicas (aglomerativas o divisivas) construyen una jerarquía de
agrupamientos, representada tradicionalmente por un árbol llamado dendograma
[Duda, 2001], [Jain, 1999]. En el caso de las técnicas aglomerativas, el dendograma
parte generalmente de grupos unitarios, hasta que algún criterio de parada se ejecute,
o hasta conseguir el grupo formado por todos los puntos, mientras que las divisivas
comienzan generalmente con todos los puntos en un cluster y van dividiendo en cada
nivel dos grupos de acuerdo a algún criterio prefijado. Las estrategias jerárquicas
aglomerativas más conocidas basadas en distancias son Single Link (SL) [Sibson,
1973], Average Link (AL) [Voorhees, 1986] y Complete Link (CL) [Defays, 1977].
En cada nivel de la jerarquía, unen los dos grupos más cercanos.
Para unir grupos, la métrica entre los puntos debe ser generalizada a los
subconjuntos de puntos. Tal distancia afecta al resultado de los grupos porque ella
refleja el concepto de cercanía y conectividad. En SL, la distancia entre grupos se
define como la distancia entre los dos elementos más cercanos (uno de cada cluster)
o, empleando terminología de grafos, el enlace más corto entre dos nodos en
diferentes subconjuntos de nodos. En el caso del algoritmo AL, la distancia entre dos
grupos es el promedio de las distancias entre todos los pares de puntos (uno de cada
conjunto). Por último, la distancia entre dos grupos en el CL es la máxima distancia
entre los pares de puntos (uno de cada conjunto), es decir, en cada nivel se unirán los
dos grupos cuya unión tiene diámetro mínimo o, empleando terminología de grafos,
el enlace más largo entre dos nodos de diferentes subconjuntos de nodos. Luego, la
medida de disimilaridad (usualmente, distancia) se calcula primeramente entre dos
puntos, uno de un conjunto y otro de otro y, según la estrategia entre grupos se
denominan mínima distancia (single link), distancia promedio (average link) y
máxima distancia (complete link). La Figura 2 ilustra estas estrategias.
Figura 2. Definiciones de proximidad entre clusters.
Técnicas de Clasificación no Supervisadas
45
El algoritmo SL adolece de un efecto encadenante produciendo clusters de
forma alargada y es sensible al ruido, mientras que CL produce clusters muy
compactos y tiende a romper grupos. AL es menos susceptible al ruido y a los
outliers.
Otra estrategia jerárquica que se puede mencionar es el método basado en
centroides, que calcula la proximidad entre grupos como la similaridad entre los
centroides de los grupos. En este caso, se van a unir los grupos cuyos centroides
estén más cercanos.
A continuación, describimos con más detalles el funcionamiento de un
algoritmo jerárquico aglomerativo basado en distancias.
Algoritmo Jerárquico Aglomerativo
Entrada: X → Conjunto de datos
1. Inicialmente, se ubican los puntos de X en un cluster unitario.
2. Se calculan las distancias/disimilaridades entre todos los pares de
puntos.
3. Se calcula la distancia entre todos los pares de grupos.
4. Se unen los dos grupos cuya distancia es mínima.
5. Se actualiza la matriz de las distancias entre grupos.
6. Si todos los puntos están en un mismo cluster, terminar; sino, volver al
paso 3.
Los algoritmos anteriormente descritos tienen como ventajas:
1. Flexibilidad con respecto al nivel de granularidad.
2. Se puede emplear cualquier función de distancia / disimilaridad.
3. Puede aplicarse a cualquier tipo de atributos.
4. Son simples de aplicar.
Entre sus desventajas podemos mencionar:
1. No tiene definido un criterio de terminación, aunque generalmente se toma el
número de clusters.
2. No vuelven a visitar los clusters construidos para mejorarlos.
3. Son sensibles al ruido.
Capítulo 2
46
El método jerárquico de Ward [Ward, 1963], a diferencia de los anteriores,
emplea un enfoque de análisis de varianza para evaluar la similaridad entre los
grupos. Trata de ir agrupando de modo que se minimice la varianza dentro de los
grupos que se van a unir. La idea de este enfoque es que los puntos deben estar
cercanos a la media de su grupo. En cada etapa, se calcula la varianza y se unen los
dos grupos con el menor incremento en la varianza dentro de los grupos. En general,
es un método eficiente pero tiende a crear grupos de tamaño pequeño.
Todas esas funciones de cercanía que emplean los métodos anteriormente
mencionados se pueden ver como una selección de parámetros en la fórmula de
Lance Wiliam [Lance, 1967]. Para la proximidad entre los clusters R y Q, donde R
está formado por los dos clusters A y B que se han unido, o sea, después que hemos
unido los clusters A y B para formar el cluster R, es necesario calcular la distancia
del nuevo cluster R al cluster existente Q; esto se hace a través de una función lineal
de las proximidades del cluster Q a cada uno de los clusters A y B según se expresa
en la fórmula 3.
| |Q)d(B,Q)d(A,γ+B)d(A,β+Q)d(B,α+Q)d(A,α=Q)d(R, BA − (3)
donde d es la función de proximidad entre clusters.
En la Tabla 1 se muestran los valores de los coeficientes para las técnicas
antes mencionadas, donde mA, mB y mQ son el cardinal del grupo A, B y Q,
respectivamente.
Método de
agrupamiento α A α B β γ
Single Link 1/2 1/2 0 -1/2
Complete Link 1/2 1/2 0 1/2
Average Link BA
A
m+m
m
BA
B
m+m
m 0 0
Método de
Centroides BA
A
m+m
m
BA
B
m+m
m
( )2BA
BA
m+m
mm− 0
Método de
Ward QBA
QA
m+m+m
m+m
QBA
QB
m+m+m
m+m
QBA
Q
m+m+m
m−
0
Tabla 1. Coeficientes de Lance William para los algoritmos aglomerativos.
El método jerárquico divisivo, en particular el árbol de mínima expansión
(MST, Minimum Spanning Tree) [Murtagh, 1983], [Zahn, 1971], es un árbol sin
ciclos o un subgrafo que permite conectar todos los vértices (puntos), de modo tal
que la suma de las longitudes de los enlaces (distancia entre los puntos vértice) sea
Técnicas de Clasificación no Supervisadas
47
mínima. Estos árboles se emplean en redes de comunicación y de transporte. Existen
varias estrategias para obtener el MST, entre las que podemos mencionar el
algoritmo de PRIM , el método de Kruskal y el algoritmo de Baruvka.
Se pueden encontrar en la bibliografía otros algoritmos jerárquicos más
recientes. Entre sus características se puede mencionar el empleo de estrategias
mixtas, con el objetivo de disminuir las limitaciones de los algoritmos anteriores, es
decir, emplean el enfoque aglomerativo con nuevas medidas de distancia entre
grupos, medidas de separabilidad y conectividad o mezclados con otro enfoque de
agrupamiento. A continuación, mencionamos algunos de ellos.
En [Guha, 1998], se introdujo el algoritmo jerárquico aglomerativo CURE
(Clustering Using REpresentatives) que, además, emplea una política mixta para el
cálculo de las distancias entre los clusters, entre la estrategia de los centroides,
(calcular la distancia entre sus centros) y la estrategia de distancia mínima entre sus
puntos. CURE va a considerar un número adecuado c de puntos representativos en
cada cluster y, luego, la distancia entre los clusters es igual a la distancia mínima
entre sus puntos representativos. Esta estrategia le permite detectar clusters de
formas arbitrarias, es decir, no necesariamente esféricos o alargados.
Emplea un dispositivo adicional para manejar el ruido: cada punto
representativo es reducido hacia el centroide geométrico del cluster por un factor α
especificado por el usuario. Los c puntos representativos se escogen para capturar la
forma de los clusters, y la contracción en dirección al centro tiene el efecto de
disminuir el ruido, puesto que éste estará lejos del centro. El parámetro α también
sirve para capturar la forma de los clusters. El proceso jerárquico continúa hasta que
se alcanza un número k de clusters.
Capítulo 2
48
Algoritmo CURE
Entrada: X → conjunto de datos
c → número de puntos representativos
α → factor de contracción
k → número de clusters
1. Inicialmente cada objeto pertenece a un cluster unitario.
2. Selección de c puntos representativos en cada cluster.
3. Contraer los puntos representativos hacia el centro geométrico del
cluster empleando el fator α.
4. Calcular la distancia entre los clusters como la distancia mínima entre
los pares de puntos representativos.
5. Unir los dos clusters más próximos.
6. Si hay k clusters, parar; si no, volver al paso 2.
CURE logra descubrir clusters de forma no esférica y tiene especial cuidado
con los outliers. Como CURE hace muestreo, no es importante hallar la complejidad;
en general, para datos de baja dimensión, será O(N2) donde N es el tamaño de la
muestra.
Mientras el algoritmo CURE trabaja con datos de atributos numéricos,
particularmente datos espaciales de baja dimensionalidad, ROCK (RObust Clustering
algorithm using linKs) [Guha, 1999] es un algoritmo jerárquico aglomerativo para
atributos categóricos.
El algoritmo jerárquico aglomerativo Chameleon [Karypis, 1999] emplea
modelos dinámicos en el agregado de los clusters. Chameleon tiene dos etapas: en la
primera, se construyen clusters iniciales que serán el inicio de la segunda etapa, ésta
consiste en una estrategia de particionamiento de grafo, emplea el grafo de los k
vecinos más cercanos, es decir, las aristas de los k vecinos más cercanos se
conservan, las restantes se borran. En la segunda etapa, se desarrolla un proceso
aglomerativo, define dos medidas para el agrupamiento de los clusters: la medida de
interconectividad relativa (RI) y la de cercanía relativa (RC), ambas son localmente
normalizadas por cantidades relacionadas con los clusters, en este sentido el modelo
es dinámico. La normalización envuelve ciertas operaciones de grafos no obvias, el
particionamiento de grafo es implementado en la librería HMETIS. El proceso
Técnicas de Clasificación no Supervisadas
49
aglomerativo depende de umbrales proporcionados por el usuario, y la decisión para
unir depende de dos estrategias: en la primera, se unen dos clusters tales que RI y RC
superen umbrales prefijados y la segunda, que RI*RCα supere un umbral prefijado (si
α > 1, se concede mayor importancia a RC, si α < 1, se concede mayor importancia a
RI, en otro caso, los dos tienen igual importancia). El algoritmo está diseñado para
encontrar clusters de diferentes formas, tamaños y densidades en espacios bi-
dimensionales. El coste computacional es de O(Nm + Nlog(N + m2log(N)), donde m
es el número de clusters de la primera etapa.
Otro algoritmo reciente aparece en [Fred, 2003], donde se integra un criterio
de aislamiento de grupos en un algoritmo de agrupamiento jerárquico aglomerativo.
En éste, se define el incremento de la disimilaridad o gap entre dos grupos Ci y Cj y
se emplea el criterio de aislamiento siguiente: dados dos grupos Ci y Cj candidatos
para unir, µi y µj sus respectivos valores medios de los incrementos de las
disimilaridades en cada cluster, si gapi ≥ ti (gapj ≥ tj), aislar el cluster Ci (Cj ) y
continuar la estrategia de agrupamiento con el resto de los grupos. Si ninguno de los
grupos excede el límite del gap, unirlos. Emplea un umbral dinámico que va
variando a lo largo del algoritmo y en dependencia del grupo Ci. El algoritmo
comienza con cada patrón en un grupo, en cada nivel del algoritmo se determina el
par de grupos más similares según si tienen los dos puntos más similares entre los
puntos de grupos diferentes y se aplica el criterio de aislamiento, los clusters son
entonces o unidos o aislados (uno o ambos).
6 Algoritmos de Partición
Mientras los algoritmos jerárquicos construyen grupos gradualmente, los algoritmos
de partición tratan de descubrir clusters reubicando iterativamente puntos entre
subconjuntos. Por ejemplo, los métodos k-Medias y el de k-Medoides (PAM,
CLARA, CLARANS), también pueden tener un enfoque probabilístico (EM,
autoClass, MClust).
La función criterio más frecuentemente usada en técnicas de agrupamiento
por partición es el error cuadrático (squared error), que generalmente funciona bien
con clusters compactos y bien separados. El error cuadrático de un agrupamiento
formado por k grupos se expresa mediante la fórmula:
∑∑= =
−=k
j
N
i
j
j
i
j
cxSE1 1
2
(4)
Capítulo 2
50
donde j
ix y cj son el i-ésimo patrón y el centroide del j-ésimo cluster,
respectivamente.
El algoritmo k-Medias (k-Means) [Mac Queen, 1967], [Hartigan, 1979] y
[Chen, 1998] es uno de los más simples y conocidos algoritmos de agrupamiento.
Está basado en la optimización del error cuadrático, que sigue una forma fácil para
dividir una base de datos dada en k grupos fijados a priori. La idea principal es
definir k centroides (uno para cada grupo) y, luego, ubicar los restantes puntos en la
clase de su centroide más cercano. El próximo paso es recalcular el centroide de cada
cluster y reubicar nuevamente los puntos en cada grupo. El proceso se repite hasta
que no haya cambios en la distribución de los puntos de una iteración a la siguiente.
k-Medias (clásico)
Entrada: X → conjunto de datos
k → número de clusters
1. Seleccionar aleatoriamente k centros.
2. Repetir mientras haya cambios en la composición de los grupos.
2.1. Asignar los ejemplos al cluster con centro más cercano.
2.2. Calcular los nuevos centroides de los grupos.
Algunos de los principales inconvenientes de estos esquemas son:
1. Fallan cuando los puntos de un cluster están muy cercanos al centroide de
otro grupo.
2. No obtienen buenos resultados cuando los clusters tienen diferentes formas y
tamaños.
3. Son muy susceptibles al problema de la inicialización.
4. Son muy sensibles a los outliers que pueden distorsionar gravemente el
resultado.
5. Sólo pueden emplearse en espacios de atributos numéricos por la necesidad
de calcular el punto medio.
En la literatura, se han definido diferentes versiones difusas de métodos
basados en el error cuadrático, entre ellos el Fuzzy C-Means [Bezdek, 1984].
El algoritmo Bisecting k-Means es una extensión del k-Means, basado en una
idea simple: para obtener k grupos, se divide el conjunto de todos los puntos en dos
Técnicas de Clasificación no Supervisadas
51
grupos y se selecciona uno de éstos para dividirlo en dos utilizando el algoritmo k-
Means, el proceso se repite hasta que hayan k clusters. Para escoger el cluster que se
va a dividir, existen varias estrategias: escoger el cluster más grande, escoger el que
tiene asociado el más grande error cuadrático medio, o emplear un criterio con
ambos, tamaño y error cuadrático medio.
Otro método que emplea una estrategia de partición similar al k-Means es el
de los k-medoides (k-medoids). Los k-medoides son los puntos del conjunto de datos
más representativos de cada grupo. La representación por k-medoides tiene dos
ventajas: no tiene limitaciones sobre el tipo de atributos y la selección de los
medoides se hace según su localización en una porción significante de un grupo, y
por tanto, es menos sensible al ruido que k-Means. Los algoritmos PAM
(Partitioning Around Medoids), CLARA (Clustering LARge Applications) y
CLARANS (Clustering Large Applications based upon RANdomized Search)
emplean este método.
El algoritmo PAM [Kaufman, 1990] emplea una alternativa diferente a la de
centroides, en su lugar toma una instancia real perteneciente a la base de datos a la
que llama medoide. Para seleccionar los medoides de los clusters, emplea una
función de optimización. Obtiene mejores resultados que k-Means porque minimiza
una suma de distancias en lugar de una suma de cuadrados; desarrolla la misma
estrategia de ubicación de los puntos que k-Means. Es más robusto que k-Means ante
ruido y outliers pero es lento en bases de datos grandes, lo que originó la aparición
del algoritmo CLARA.
CLARA [Kaufman, 1990] se basa en muestreos. Los medoides son escogidos
de la muestra usando PAM, minimiza la función de disimilaridad promedio del
agrupamiento para retener los medoides en una de las muestras, de entre todas las
muestras seleccionadas.
CLARANS [Ng, 1994] es una mezcla de PAM y CLARA, trabaja sobre
muestras de la base de datos. Para disminuir la complejidad, considera los vecinos de
los medoides como candidatos a ser nuevos medoides e itera varias veces tomando
distintas muestras en cada vuelta, con el objetivo de evitar la posible selección de
malas muestras. Emplean un grafo cuyos nodos son el conjunto de k medoides, y dos
nodos se conectan si difieren de exactamente un medoide. La complejidad es O(N2).
Las estrategias CLARA y CLARANS tienen entre sus limitaciones la
dependencia del resultado del agrupamiento del orden en que se presentan los objetos
y tienden a crear grupos esféricos.
Otra de las estrategias basadas en partición se refiere a los métodos
probabilísticos. Éstos asumen que los datos vienen de una mixtura de varias
Capítulo 2
52
poblaciones cuyas distribuciones y probabilidades a priori deseamos encontrar; una
ventaja que brindan estos modelos es la fácil interpretación de los grupos obtenidos.
El algoritmo EM (Expectation Maximization) propuesto por [Dempster,
1977] sobre mixturas multimodales es uno de los representantes de esta clase de
algoritmos. Es una optimización iterativa en dos pasos: en el paso E (Expectation),
estima las densidades de probabilidad )/( jCxp , donde Cj son los diferentes modos,
mientras que en el paso M (Maximization), encuentra una aproximación a un modelo
de mixtura. El proceso se repite hasta que se alcanza el criterio de convergencia de la
log-verosimilitud (log- likelihood). Como resultado se obtienen los parámetros que
maximizan la log-verosimilitud. Más detalles de este algoritmo se pueden ver en el
Anexo B.
Este algoritmo tiene varias limitaciones:
1. Es un método local, por tanto, es sensible a la inicialización.
2. Puede converger a la frontera del espacio de parámetros donde la
verosimilitud es no acotada, llevando a estimaciones sin sentido.
3. Si el número de componentes es muy grande, puede sobre-entrenar los datos,
pues éstos son incompletos y, por tanto, se puede obtener una forma más
irregular de lo que en realidad es, mientras que una mixtura con pocas
componentes no es lo suficientemente flexible para aproximar al verdadero
modelo.
4. La finalización también es una limitación, pues llega el momento donde el
proceso deja de evolucionar por lo que se supone que alcanza la localización
óptima, pero esto no nos asegura la verdadera optimización pues lo que se
obtiene es un mínimo local.
El algoritmo que se describe en [Figueiredo, 2002] trata de reducir las
limitaciones antes mencionadas. Comienza por un valor de k grande, con el que
obtiene buenos resultados, debido a que emplean la variante de considerar solamente
las componentes de probabilidad no nula para obtener los estimados de los
parámetros; además, es más robusto al problema de la inicialización.
7 Algoritmos Basados en Densidad
Los algoritmos basados en densidad localizan zonas de alta densidad separadas por
regiones de baja densidad.
Técnicas de Clasificación no Supervisadas
53
DBSCAN (Density Based Spatial Clustering of Aplications with Noise)
[Ester, 1996] es uno de los primeros algoritmos de agrupamiento que emplea este
enfoque. Comienza seleccionando un punto t arbitrario, si t es un punto central, se
empieza a construir un cluster alrededor de él, tratando de descubrir componentes
denso-conectadas; si no, se visita otro objeto del conjunto de datos.
Puntos centrales (core points) son aquellos tales que en su vecindad de radio
Eps, hay una cantidad de puntos mayor o igual que un umbral MinPts especificado.
Un punto borde o frontera tiene menos puntos que MinPts en su vecindad, pero
pertenece a la vecindad de un punto central. Un punto ruido (noise) es aquel que no
es ni central ni borde. La Figura 3 ilustra cada uno de esos conceptos: si MinPts es
mayor o igual a 4 y menor o igual a 6, A es un punto central, B es un punto borde y
C es un punto ruido.
Figura 3. Definiciones de punto central, borde y ruido.
Un punto q es directamente denso-alcanzable desde otro punto t (con relación
a los parámetros MinPts y Eps) si t es un punto central y q pertenece a la vecindad de
t. Un punto q es denso-alcanzable desde un punto t si existe una cadena de puntos t0,
t1, … tm, tales que ti-1 es directamente denso-alcanzable desde ti, 1 ≤ i ≤ m, t0 = q y tm
= t.
En consecuencia, los puntos centrales están en regiones de alta densidad, los
puntos borde en la frontera de regiones densas y los puntos ruido en regiones de baja
densidad. Este algoritmo busca clusters comprobando la vecindad de cada punto de
la base de datos y va añadiendo puntos que son denso-alcanzables desde un punto
central.
Capítulo 2
54
Algoritmo DBSCAN
Entrada: X → conjunto de datos
Eps → radio de la vecindad de cada punto
MinPts → número mínimo de puntos en una vecindad
1. Seleccionar aleatoriamente un punto t.
2. Si t es un punto central se forma un grupo alrededor de t con todos los
puntos denso-alcanzables desde t.
3. Si t es un punto borde o ruido, se visita otro punto.
4. Si todos los puntos han sido visitados, terminar; si no, volver al paso 1.
Entre sus ventajas se pueden mencionar:
1. Descubre clusters de formas arbitrarias.
2. Trata el ruido.
3. Es de una sola pasada.
4. Genera automáticamente el número de clusters.
Entre sus limitaciones:
1. Es sensible a los parámetros.
2. No es bueno para datos de alta dimensionalidad, grupos de diferentes
densidades y grupos muy solapados.
En general, DBSCAN puede manejar clusters de formas y tamaños
diferentes, pero tiene limitaciones cuando los clusters están muy solapados y en
presencia de ruido. La complejidad en el peor de los casos es O(N2).
La motivación para la realización del algoritmo OPTICS (Ordering Points to
Identify the Clustering Strusture) [Ankerst, 1999] se basa en la necesidad de
introducir parámetros de entrada en casi todos los algoritmos de agrupamiento
existentes, que en la mayoría de los casos son difíciles de determinar. En conjuntos
de datos reales, no existe una manera de determinar estos parámetros globales, por lo
que trata de resolver este problema basándose en el esquema del algoritmo
DBSCAN, creando un ordenamiento de la base de datos para representar la
estructura del agrupamiento basada en densidad. Además, puede hacer una
representación gráfica del agrupamiento incluso para conjuntos de datos grandes.
Técnicas de Clasificación no Supervisadas
55
La regla de clasificación de los K vecinos más cercanos (K-NN) ha sido
extensamente empleada en métodos de clasificación supervisada [Vázquez, 2005] y
[Vazquez, 2008]. En [Thanh, 2003], se propone utilizar la regla como estrategia
basada en densidad, para tratar bases de datos de alta dimensionalidad (por ejemplo,
imágenes de satélites). El algoritmo comienza asignando cada punto a un cluster
individual, luego los puntos se van asignando a uno de los grupos según la regla K-
NN, terminando el proceso cuando en dos iteraciones sucesivas ninguno de los
objetos cambia de grupo.
El algoritmo DENCLUE (DENsity-based CLUstEring), propuesto en
[Hinneburg, 1998], es un algoritmo en dos fases. En la primera, divide el hiper-
rectángulo del conjunto de datos en hipercubos de aristas de longitud 2σ, determina
los hipercubos más poblados y los hipercubos que están conectados. En la segunda
fase, considera sólo los hipercubos más poblados y los conectados a hipercubos más
poblados. Posteriormente, para determinar los grupos, evalúa la función de densidad
que define en cada uno de los puntos x de los hipercubos más poblados, pero
considerando sólo aquellos puntos tal que su distancia al centro del hipercubo al que
x pertenece sea igual o menor que 4σ, luego halla el gradiente y el atractor de
densidad de x para el que la función de densidad sea mayor o igual que un valor
prefijado, y clasifica a cada punto en la clase de su atractor. Con este algoritmo se
obtiene el número de clusters de manera automática.
Entre sus ventajas se pueden mencionar:
1. Logra buenos agrupamientos en bases de datos con puntos ruidosos.
2. Es significativamente más rápido que otros algoritmos de agrupamiento.
Entre sus limitaciones está el problema de la selección de sus parámetros σ y
ξ, con σ determina la influencia de un punto en su vecindad y ξ es el umbral de
densidad.
8 Agrupamiento Basado en Caminos
Los algoritmos de agrupamiento basados en camino (Path Based Clustering)
funcionan bajo la idea de asignar dos objetos a un mismo cluster si se encuentran
conectados a un mismo camino de modo tal que la similaridad entre dos objetos
adyacentes de dicho camino sea alta.
Esta estrategia está inspirada en la existencia de bases de datos cuyos grupos
constituyen regiones alargadas, tales como espirales y círculos. Desarrolla una
Capítulo 2
56
estrategia como el SL pero, a diferencia de ésta, evalúa la posibilidad de unir dos
grupos mediante una función de coste.
En [Fisher, 2002], se presenta una estrategia basada en caminos con una
optimización aglomerativa que emplea un algoritmo recursivo, parecido al árbol de
mínima expansión de Kruskal para calcular la función de coste. La función de coste
que emplea es la siguiente:
( ) ( ) ( ){ }∑ ∑∑
∈ ∈ ∈
=k,...,v vo vo
eff
ji
v
pbc
i j
D;cDcO
D;cH1
1
(5)
donde
( )( ) [ ] [ ]
= +−≤≤∈ 1
11hphp
phcPp
eff
ji DmaxminD;cDji
(6)
es la disimilaridad efectiva entre los objetos oi y oj.
En la estrategia SL, por ejemplo, dos objetos oi y oj se asignarían al mismo
cluster si su disimilaridad Dij es pequeña. Este concepto se generaliza asumiendo que
la disimilaridad entre objetos se puede comportar de manera transitiva. Por tanto, se
pueden considerar todos los caminos (paths) del objeto oi al objeto oj, donde todos
los objetos sobre un camino que conecta a los objetos oi y oj, pertenecen al mismo
cluster que éstos. La disimilaridad que existe en un camino en particular se define
por medio de la máxima disimilaridad en ese camino, y la disimilaridad efectiva
entre dos objetos, se calcula mediante el mínimo sobre todas las distancias de los
caminos que unen a oi y oj, tal como se ve en la fórmula (6).
Los costes de los clusters se definen a través de la expresión (7):
( ) [ ] [ ]∑ ∑∈ ∈
+−≤≤∈
=
vi vjjiOo Oo
hphpphPp
v DmaxminD;cC 111
(7)
El algoritmo comienza con tantos clusters como puntos de la base de datos, o
sea, con N clusters unitarios. Inicialmente, el coste de cada cluster es nulo. Se visitan
todas las disimilaridades entre los pares de objetos en forma creciente, si aparece una
disimilaridad tal que los respectivos objetos estén en clusters diferentes, ésta es la
disimilaridad efectiva para cada par de objetos de los dos respectivos subconjuntos a
los que pertenecen los puntos. La multiplicación de este valor de disimilaridad por el
cardinal del primer conjunto y el cardinal del segundo conjunto se suma al coste
Técnicas de Clasificación no Supervisadas
57
interno del posible cluster a obtener por medio de la unión de esos dos. Si queda
solamente un subconjunto, se calcula el coste interno.
El algoritmo se puede resumir en la siguiente forma:
Algoritmo Path Based Clustering
Entrada: X → Conjunto de datos
k → número de clusters
1. Inicialmente, se ubican los puntos de X en un cluster unitario.
2. Se calculan las distancias / disimilaridades entre todos los pares de
puntos.
3. Se ordenan las distancias.
4. Se calculan las disimilaridades efectivas y la función de coste para cada
par posible de grupos a unir.
5. Se unen los dos grupos tal que el valor de la función de coste sea
mínimo.
6. Si existen k clusters terminar; sino volver al paso 5.
Este enfoque, como se dijo antes, es efectivo cuando los objetos de los grupos
forman estructuras alargadas, ya que da la posibilidad de construir caminos que
enlazan puntos de un mismo cluster sin incrementar demasiado el coste de unirlos.
Sin embargo, tiene las siguientes limitaciones:
1. No es funcional en bases de datos de diversas formas.
2. No detecta bien los grupos si hay solapamiento, precisamente por el efecto
encadenante de los caminos, puesto que se crearían caminos entre objetos de
grupos diferentes debido a la cercanía de las clases solapadas.
3. Es sensible al ruido.
4. Requiere un tiempo de ejecución de O(N3 log N), donde N es el número de
objetos.
En relación al ruido, en el trabajo [Fisher, 2003a], los mismos autores
proponen una estrategia para manejar el ruido, incorporando a la función de coste un
Capítulo 2
58
término para los outliers, pero éste depende de un umbral; por tanto, incorpora un
nuevo parámetro al algoritmo, que a su vez es difícil de determinar.
9 Estrategias de Co-ocurrencias
La idea de los métodos de co-ocurrencia para datos categóricos considera que el
concepto de similaridad por sí solo no es suficiente para agrupar este tipo de datos.
El enfoque de los vecinos más cercanos compartidos fue introducido primero en
[Jarvik, 1973]. Los algoritmos ROCK y SNN emplean, además de la similaridad, el
concepto de vecinos compartidos.
La motivación para la creación del algoritmo SNN (vecinos más cercanos
compartidos, Shared Nearest Neighbors) [Ertoz. 2003] es la existencia de bases de
datos de alta dimensionalidad como textos y series temporales, así como la existencia
de grupos de diferentes formas y tamaños. Primero, halla los K vecinos más cercanos
de cada punto, construye un grafo de modo tal que dos puntos son conectados si
ambos pertenecen mutuamente a la lista de sus vecinos más cercanos y redefine la
similaridad entre pares de puntos como el número de vecinos más cercanos que
comparten. Para calcular los pesos del grafo, tiene en cuenta el orden de los vecinos
más cercanos.
Define los puntos centrales y alrededor de ellos forma los clusters. Este
algoritmo no agrupa todos los puntos, como parte de una estrategia que emplea para
eliminar los puntos ruido (outliers). Encuentra de manera natural el número de
clusters. Esta estrategia de vecinos compartidos tiene buenos resultados en el caso de
grupos separados, pero en el caso en que haya ruido o puntos de grupos diferentes
muy cercanos, se podrían mezclar puntos de diferentes grupos en un mismo cluster.
El algoritmo ROCK (Robust Clustering algorithm for Categorical Data)
[Guha, 1999] tiene rasgos communes con CURE, es un algoritmo jerárquico que
realiza un proceso aglomerativo hasta que se obtienen k clusters y realiza muestreo.
Utiliza una función de semejanza y una función objetivo dependiente de las
similaridades y considera dos puntos vecinos si su similaridad supera un umbral
prefijado.
10 Otras Estrategias
Algunos algoritmos trabajan con datos indirectamente, construyendo resúmenes de
datos sobre subconjuntos del espacio de los atributos, ellos realizan una
segmentación del espacio y se suelen llamar Métodos basados en Rejillas.
Técnicas de Clasificación no Supervisadas
59
Frecuentemente usan una aglomeración jerárquica como una de sus fases de
procesamiento, como por ejemplo los algoritmos GRIDCLUST [Schikuta, 1996] y
BANG [Schikuta, 1997] que sortean los bloques de acuerdo a su densidad y unen
bloques adyacentes en el hiperespacio (n – 1)-dimensional.
Esta metodología basada en rejillas también se usa como un paso intermedio
en otros algoritmos como DENCLUE (mencionado antes) y CLIQUE (Clustering In
Quest) [Agrawal, 1998] también basados en densidad, CLIQUE tiene como
limitación la complejidad temporal exponencial en relación a la dimensión de los
datos. MAFIA (Merging of Adaptive Finite Intervals) [Goil, 1999] es una variante
del algoritmo CLIQUE, construye un histograma de la cantidad de puntos en cada
segmento en que divide cada una de sus dimensiones, pero su coste temporal también
depende exponencialmente de la dimensión del espacio de los puntos.
En [Xiao, 2005], se propone un algoritmo basado en la regla K-NN y
DENCLUE, empleando el esquema de DENCLUE como algoritmo de agrupamiento
y la regla K-NN para determinar los parámetros globales del algoritmo DENCLUE.
Otros trabajos emplean técnicas de multiclasificadores, como en [Fred, 2002]
y [Fred, 2005], donde aparece un algoritmo en dos etapas: en la primera, realiza
divisiones en k clusters del conjunto de datos empleando el algoritmo k-Means; en la
segunda etapa, emplean la técnica SL. Para esto, toma la co-ocurrencia de todos los
pares de patrones en un mismo cluster como votos para su asociación, bajo la idea de
que si dos patrones pertenecen a un mismo cluster, ellos serán colocados en el mismo
grupo en diferentes agrupamientos. Los patrones que no pertenezcan a ningún grupo
forman clusters unitarios.
El agrupamiento espectral (Spectral Clustering) es otra técnica que se emplea
para construir particiones de un grafo basada en la búsqueda de los vectores propios
de la matriz de adyacencia. Trabajos como los de [Shi, 2000] y [Meila, 2001b]
aparecen en la bibliografía consultada. Dado un conjunto de datos, se construye un
grafo de similaridad, se hallan los primeros k (número de clusters) vectores propios
de la matriz Laplaciana y se forma una matriz cuyas columnas están formadas por los
vectores propios, para luego agrupar utilizando el algoritmo k-Means los objetos que
forman las filas de dicha matriz. Esta estrategia no hace suposiciones acerca de la
estructura de los grupos, contrario al k-Means que asume clusters convexos, sin
embargo, depende del grafo de similaridad escogido por lo que puede ser inestable
para diferentes selecciones de los parámetros del grafo de vecindad.
Capítulo 3
Validación de Clusters
1 Introducción
El análisis de los agrupamientos es una herramienta importante para investigar e
interpretar datos. Las técnicas de agrupamiento son la herramienta fundamental
empleada para la exploración de datos, específicamente cuando se necesita saber la
estructura interna de los datos sin tener información a priori disponible, pues se
espera que los algoritmos de agrupamiento produzcan particiones que reflejen la
estructura interna de los datos e identifiquen las clases “naturales” y jerarquías
presentes en los mismos.
Un procedimiento de aprendizaje no supervisado es más complejo de evaluar
que uno de aprendizaje supervisado. A través de los años, se han propuesto una
amplia variedad de algoritmos de agrupamiento, algunos tienen su origen en la teoría
de grafos, otros están basados en reconocimiento estadístico de patrones, etc.
Comparar los méritos relativos de cada método es difícil pues, cuando aplicamos
algoritmos de agrupamiento a un conjunto de datos, los resultados difieren.
En algunos casos, tales diferencias se deben a las características del
algoritmo, ya que pueden diferir de manera explícita o implícita en las suposiciones
acerca de la estructura de los datos. Por ejemplo, si el conjunto estudiado consiste de
varias nubes de puntos esféricamente distribuidos alrededor de su centro, los
métodos que asumen tal estructura funcionan bien, mientras que si los datos están
formados por clusters de diferentes formas y tamaños, algunos algoritmos no son
capaces de descubrir esta estructura como, por ejemplo, el k-Means.
Es más difícil aún el hecho de que el resultado del agrupamiento depende
fuertemente de los valores asignados a los parámetros. Por ejemplo, si se desarrolla
un algoritmo de agrupamiento jerárquico, hay que decidir qué nivel refleja mejor las
clases “naturales” presentes en los datos y esto, haciendo uso solamente de los datos
disponibles.
En diversas técnicas de agrupamiento, el número k de clusters a construir es
un parámetro de entrada del algoritmo de agrupamiento, lo que supone un
conocimiento a priori de ese dato. Sin embargo, en la práctica, podemos
Capítulo 3
62
desconocerlo. Muchos métodos e indicadores bajo el nombre de validación de
clusters (cluster validation) permiten evaluar los resultados del agrupamiento de esta
manera.
La noción de validación de clusters se refiere a conceptos o métodos para la
evaluación cuantitativa y objetiva del resultado de un algoritmo de agrupamiento. En
la literatura consultada con relación a esta temática, dichos conceptos y métodos
aparecen publicados en [Rand, 1971], [Milligan and Cooper, 1985], [Jain, 1986],
[Rousseeuw, 1987], [Geva, 2000], [Levine, 2001], [Halkidi, 2002a], [Halkidi,
2002b], [Azuaje, 2003], [Lange, 2004], [Gusarova, 2005], [Mufti, 2005], [Bertrand,
2006], [Bouguessa, 2006], [Barzily, 2008], entre otros.
En este capítulo, haremos un recorrido por el estado del arte de algunos de los
trabajos citados en la literatura acerca de la validación de clusters y, específicamente,
acerca de cómo determinar el valor del parámetro k, nos tomaremos mayor interés en
los métodos relacionados con este trabajo.
2 Índices de Validación de Clusters
En aplicaciones prácticas de algoritmos de agrupamiento, varias cuestiones deben ser
resueltas, entre ellas, la determinación del número de clusters y la evaluación de la
calidad de las particiones.
Un índice de validación (validity index) proporciona una medida objetivo del
resultado de un agrupamiento, y su valor óptimo se usa frecuentemente para indicar
la mejor selección posible de los valores de los parámetros en el algoritmo de
agrupamiento, por ejemplo, el número de clusters. La construcción de tales índices es
una tarea difícil, pues en la vida real se desconoce la distribución verdadera de los
datos. Numerosos trabajos sugieren índices directos o indirectos para evaluar:
agrupamientos duros [Jain y Dubes, 1988], agrupamientos probabilísticos [Duda y
Hart, 1973] y agrupamientos difusos [Pal, 1995], [Pal, 1997], [Rezae, 1998],
[Bezdek, 1998] y [Bouguessa, 2006].
Los agrupamientos duros frecuentemente están basados en alguna motivación
geométrica para estimar cuán compactos y separados están los clusters [Dunn, 1974];
otros están estadísticamente motivados, es decir, comparando la dispersión dentro del
cluster con la separación entre los clusters [Davies, 1979] y [Halkidi, 2000]. Algunos
de los más recientes y exitosos se encuentra en [Tibshirani, 2001], basado en la
localización de un codo (elbow) para indicar el número apropiado de clusters en un
agrupamiento, como en [Sugar, 1998], [Sugar, 1999] y [Yeung, 2001].
Validación de Clusters
63
Algunos índices de validación de clusters evalúan los resultados de un
algoritmo de agrupamiento empleando dos criterios de medida: compacidad y
separación. La compacidad se basa en la suposición de que los elementos de un
mismo cluster deben estar tan cerca como sea posible, mientras que el criterio de
separación considera que los clusters deben estar bien separados. Estos índices
actúan directamente sobre el agrupamiento, o sea, primeramente se obtienen varios
agrupamientos del conjunto de datos con valores del parámetro número de clusters
entre cmin y cmax, luego se calcula el valor del índice para determinar cuál de los
agrupamientos es considerado correcto, lo que implicaría la elección de un número
determinado de clusters.
El índice de Davies Bouldin [Davies, 1979], uno de los representantes de esta
estrategia más empleado en la literatura consultada, emplea como medida de
compacidad de un cluster la media de las distancias de sus puntos a su centroide,
mientras que como medida de separabilidad utiliza la distancia entre los clusters, que
puede ser, por ejemplo, la distancia euclidea entre los centros. Con más detalles, se
define el índice de Davies Bouldin por:
∑=
=k
i
iRk
DB1
1
(8)
siendo k el número de clusters y
jijikj
i RR≠=
=,,...,1
max (9)
Generalmente,
ji
ji
jiM
ssR
+=
(10)
),(,),(1
jiji
Cx
i
i
i vvdMvxdC
si
== ∑∈
(11)
donde, vi (i = 1, …, k) es el centroide del i-ésimo cluster, y d la distancia euclidea.
Para escoger el número de clusters adecuado se toma el valor k que minimiza
el índice de Davies Bouldin porque eso significa que los clusters son más compactos
y están más separados.
Este índice tiene como inconveniente que considera clusters compactos y
bien separados, por lo que al calcular la compacidad según la distancia de los puntos
a los centros, no detecta bien la forma de los clusters y si, además, éstos están
solapados, no es posible determinar las fronteras entre los clusters, dando resultados
erróneos acerca del número de grupos.
Capítulo 3
64
Otros dos índices que aparecen en la literatura que tienen en cuenta esas dos
características (compacidad y separación) son los que aparecen en [Halkidi, 2000] y
[Halkidi, 2001]. El primero de ellos (SD) tiene en cuenta la dispersión de los clusters
para medir la compacidad (Scat) y la separación es calculada mediante la medida a la
que llama separación total de los clusters (Dis). El índice que propone se calcula
mediante la siguiente fórmula:
)()( kDiskScatSD += α (12)
donde Scat(k) es la dispersión promedio de los clusters que se define por:
∑=
=k
i
i
X
v
kkScat
1 )(
)(1)(
σσ
(13)
y Dis(k) es la separación total entre los clusters y se define por:
∑ ∑=
−
=
−=
k
i
k
j
ji vvD
DkDis
1
1
1min
max)( (14)
vi denota la media del cluster i-ésimo y k el número de clusters, ( ) ( )n
xxx σσσ ...,,1= y
( ) ( )n
vvi iiv σσσ ...,,1= , donde n es el número de rasgos,
jikji
vvD −=≤≤ ,1
max max (15)
y
jikji
vvD −=≤≤ ,1
min min (16)
Además,
( ) ( )∑∑==
−=−=i
i
N
k
j
i
j
k
i
j
v
N
k
jj
k
j
x vxN
xxN 1
2
1
2 1,
1 σσ (17)
donde, jx y j
xσ representan la media y la varianza respectivamente de la j-ésima
dimensión; j
iv y j
viσ son la media y varianza, respectivamente, de la j-ésima
dimensión en la clase i-ésima; N es el número de puntos en la base de datos y Ni el
número de puntos en el i-ésimo cluster y
( ) 21
xxx T= (18)
El parámetro α que emplea para pesar la dispersión es igual a )( maxcDis y
cmax es el valor máximo del número de clusters a tener en cuenta.
Es decir, Scat(k) indica la compacidad promedio de los clusters, o sea, la
distancia intra-grupos. Un valor pequeño de esta medida implica que los clusters son
Validación de Clusters
65
compactos ya que cuando aumenta la dispersión dentro de los grupos, el valor de
Scat(k) se incrementa también. El segundo sumando indica la separación total entre
los k clusters, contrario al primer término, Dis(k) está influenciado por la geometría
de los grupos y su valor aumenta con el número de clusters. Como las dos medidas
tienen diferentes rangos, se emplea el peso α para lograr que ambos términos estén
balanceados. El número de clusters que minimiza el índice se considera como el
valor óptimo del número de clusters presentes en los datos.
Este índice, al igual que el anterior, no es capaz de descubrir agrupamientos
donde los clusters tengan diversas formas, debido a la utilización de las varianzas
que más bien corresponden a clusters globulares y también, la dependencia del
segundo sumando de las medias de los clusters para medir la separación, trae como
consecuencia la dificultad de su empleo en bases de datos de grupos muy solapados.
La aparición del otro índice de validación de clusters mencionado antes
(S_Dbw), estuvo motivado por la estrategia basada en densidad de algoritmos de
agrupamiento como DBSCAN, por lo que emplea la misma estrategia de compacidad
de los clusters por medio de la varianza intra-cluster, pero mide la separación entre
los grupos con el empleo de un término que evalúa la densidad entre los clusters.
Este índice se define por:
)(_)(_ kbwDenskScatDbwS += (19)
donde
{ }∑ ∑≠= =
−=
k
iji
k
j ji
ji
vdensityvdensity
udensity
kkkbwDens
1 1 )(),(max
)(
)1(
1)(_
(20)
Igual que antes, vi (i = 1, …, k) representa la media del i-ésimo cluster; ui j es
el punto medio del segmento de línea definido por los centros vi y vj y el término
density(u) se define a través de la siguiente fórmula:
∑=
=jiN
l
l uxfudensity1
),()( (21)
donde Ni j es el número de puntos que pertenecen al cluster Ci o al cluster Cj.
>
=casootroen
stdevuxdsiuxf
1
),(0),( y ∑
=
=k
i
ivk
stdev1
)(1 σ
(22)
De modo que density(u) define el número de puntos de los clusters Ci y Cj
que pertenecen a la hiper-esfera de centro en u y radio stdev.
Capítulo 3
66
Por tanto, este índice funciona bien bajo la suposición de clusters convexos y
bien separados y el valor de k que minimiza el mismo es considerado el óptimo
número de clusters. Pero, si los clusters están solapados y hay puntos ruidosos en la
base de datos, no es una estrategia adecuada para determinar el número “natural” de
clusters.
3 Estrategias Basadas en Estabilidad
Otros métodos para la validación de los clusters utilizan re-muestreo. Éste identifica
como soluciones, agrupamientos estables que indican el correspondiente número de
clusters. Hablando de una manera menos formal, la estabilidad de los clusters ocurre
cuando la estructura de los clusters no se ve afectada por pequeños cambios en el
conjunto de datos [Cheng and Milligan, 1996], [Bertrand, 2005] y [Mufti, 2006].
La idea de usar estabilidad para evaluar soluciones de agrupamientos ha sido
considerada antes por algunos autores en el contexto de agrupamientos jerárquicos
[Smith and Dubes, 1980]. Enfoques recientes [Ben-Hur, 2002], [Fischer, 2003],
[Lange, 2004], [Tibshirani, 2005] sugieren que la estabilidad de los clusters es una
manera de determinar el número de clusters, relacionado con los métodos Bootstrap
y Jacknife [Efron, 1982] en el hecho de usar muestreo para estimar un estadístico
pero, en este caso, el muestreo se usa como una perturbación de los datos, incluso
con la posibilidad de añadir ruido.
El método propuesto en [Ben-Hur, 2002] se basa en la estabilidad de
agrupamientos con respecto a perturbaciones como submuestreo o adición de ruido,
con el objetivo de asegurar la presencia de estructura en los datos agrupados; en
particular, se usa en secuencias de ADN (DNA microarrays). Considera la
estabilidad como una propiedad importante de una solución de agrupamiento porque
los datos y, en particular, datos de gene expression es ruidosa. Consecuentemente,
sugiere la estabilidad como un medio para definir particiones importantes.
Para determinar el número de clusters, genera 100 pares de submuestras de
los datos y, para cada valor de k, cada submuestra se agrupa en k clusters con el
agrupamiento jerárquico Average Link. Con los dos resultados del agrupamiento, se
calcula una medida de similaridad con valores entre 0 y 1. Se representa
gráficamente la medida de similaridad para muchas observaciones en la submuestra
conjunta y un valor cercano a 1 indica que los dos agrupamientos son el mismo. El
número estimado de clusters se toma como el valor de k tal que ocurre una transición
de valores de similaridad concentrados cerca de 1 a una distribución con una
dispersión más amplia inferior a 1.
Validación de Clusters
67
Altos valores de las similaridades indican un patrón de agrupamiento estable,
por tanto, el número óptimo de clusters u otro parámetro empleado en el algoritmo
de agrupamiento se determina por el valor máximo de la similaridad promedio. El
método se puede usar con cualquier algoritmo de agrupamiento y proporciona una
manera de definir un número óptimo de clusters.
Las medidas de similaridad entre particiones empleadas están descritas con la
ayuda de un producto interno en la siguiente forma:
Dado X = {x1, …, xN}, n
ix ℜ∈ representa el conjunto de datos a ser
agrupados, L es una partición de X en k subconjuntos S1, …, Sk. Se construye una
matriz cuyos coeficientes toman valores según la fórmula (23):
≠
=casootroen
jiclustermismoalpertenecenxyxsiC
ji
ij0
,1
(23)
Define el producto interno de dos particiones L1 y L2 por:
∑==ji
ijij CCCCLL,
)2()1()2()1(21 ,, (24)
Este producto interno calcula el número de pares de puntos agrupados juntos
con ambas particiones, o, en teoría de grafos se puede interpretar como el número de
enlaces comunes representados por C(1) y C(2). Como un producto interno satisface la
desigualdad de Cauchy-Schwartz, se normaliza en una correlación o medida de
similaridad coseno:
2211
2121
,,
,),cos(
LLLL
LLLL =
(25)
Otras dos medidas que se pueden expresar por medio del producto interno son
el coeficiente de Jaccard (26) y el coeficiente de emparejamiento (matching)
expresado en la fórmula (27):
)2()1()2()2()1()1(
)2()1(
111001
1121
,,,
,),(
CCCCCC
CC
NNN
NLLJ
−+=
++=
(26)
2)2()1(
211100100
110021
11),( CC
nNNNN
NNLLM −−=
++++
= (27)
donde C(1) y C(2) son matrices de coeficientes 0 y 1, Nij para i, j ϵ {0, 1}, es el
número de coeficientes para los cuales C(1) y C(2) tienen valores i y j respectivamente.
Para determinar el valor óptimo de k, se busca un salto en el área bajo la
función de distribución acumulativa o un salto en P(sk > η), donde sk representa una
Capítulo 3
68
variable aleatoria del resultado de las similaridades. Para cada k y η, se calcula la
probabilidad de que sk sea mayor que un umbral prefijado η.
Algoritmo explorador de modelo
Datos de Entrada: X → conjunto de datos
kmax → número máximo de clusters
num_subm → número de submuestras
Salida: s(i, k) → lista de similaridades para cada par de submuestras
Requiere: cluster(X,k) → algoritmo de agrupamiento en k clusters
s(L1, L2) → medida de similaridad entre etiquetas
f → razón de muestreo o fracción de puntos muestreados
1. f = 0.8
2. para k desde 2 hasta kmax
2.1. para i desde 1 hasta num_subm
2.1.1. sub1 = submuestrear(X, f)
2.1.2. sub2 = submuestrear(X, f)
2.1.3. L1 = cluster(sub1, k)
2.1.4. L2 = cluster(sub2, k)
2.1.5. Intersect = sub1 ∩ sub2
2.1.6. s(i, k) = s(L1(Intersect), L2(Intersect))
Otra propuesta con este enfoque es el que aparece en el artículo [Tibshirani,
2005]; la idea clave es que trata el agrupamiento como un problema de clasificación
supervisada. Para cada k (número de clusters), realiza los siguientes pasos
fundamentales:
1. Divide M veces el conjunto de datos en dos conjuntos, Xtr y Xte, a los que les
llama conjunto de entrenamiento y conjunto de prueba, respectivamente.
2. Aplica un algoritmo de agrupamiento a ambos conjuntos.
3. Etiqueta el conjunto Xte empleando a Xtr como conjunto de entrenamiento.
Validación de Clusters
69
4. Calcula la proporción de pares de puntos asignados al mismo cluster en las
particiones de Xte mediante la clasificación y el algoritmo de agrupamiento.
Para construir los conjuntos de entrenamiento y de prueba, propone la
realización de un m-fold cross-validation. Define el concepto fuerza de la predicción
(prediction strength) del agrupamiento C(., k) que se calcula mediante la siguiente
fórmula:
( ) [ ]( )∑∈≠
≤≤=
−=
kjAjijietrt
kjkjkj
XkXCDNN
Avekps 1),,(11
1min)(1
(28)
donde k es el número de clusters, Akj, j = 1, …, k, son los clusters que se obtienen de
aplicar el algoritmo de agrupamiento al conjunto de prueba, Nkj representa el número
de elementos en el cluster Akj. C(Xtr, k) denota la operación de agrupamiento al
conjunto Xtr.
Para contabilizar la cantidad de pares de observaciones que caen en el mismo
grupo, emplea la notación D[C(…), Xtr] que es una matriz de N x N, tal que el
elemento ij-ésimo D[C(…), Xtr]ij = 1 si las observaciones i y j caen en el mismo
cluster y 0 en el otro caso.
La idea principal de este método es agrupar tanto el conjunto de
entrenamiento como el conjunto de prueba, etiquetar el conjunto de prueba mediante
un algoritmo de clasificación basado en centroides utilizando el conjunto Xtr como
conjunto de entrenamiento, con esto, se predice la co-pertenecia en el conjunto de
prueba determinando los pares de puntos que pertenecen a un mismo cluster,
etiquetados tanto por el algoritmo de agrupamiento como por el algoritmo de
clasificación. Toma como valor óptimo del número de clusters, el mayor k para el
cual la fuerza de la predicción supera un umbral prefijado.
A continuación, mostramos el algoritmo con más detalles:
Capítulo 3
70
Algoritmo para la selección de modelo
Entrada: X → conjunto de datos
1. Para cada k desde 2 hasta kmax hacer:
1.1. Para cada i desde 1 hasta M hacer:
1.1.1. Dividir el conjunto X en conjunto de entrenamiento X´ y
conjunto de prueba Xi.
1.1.2. Aplicar el algoritmo de agrupamiento a X´y obtener A(X´).
1.1.3. Aplicar el algoritmo de agrupamiento a Xi y obtener A(Xi).
1.1.4. Clasificar los elementos de Xi empleando A(X´) como
conjunto de aprendizaje y obtener C(Xi).
1.2. Calcular prediction strength ps(k) entre C(Xi) y A(Xi).
1.3. Tomar como valor óptimo de k, el más alto valor k tal que ps(k) ≥
0.8 ó 0.9.
En [Lange, 2004], se introduce una medida de estabilidad de clusters para
evaluar la validez de un modelo de agrupamiento. El número de clusters preferido se
determina minimizando el riesgo de clasificación como una función del número de
clusters.
La noción de estabilidad que proponen está basada en las disimilaridades
promedio de soluciones calculadas sobre dos conjuntos de datos diferentes X y X´ y
dos soluciones de agrupamiento Y = Ak(X) y Y´= Ak(X´) dependientes del número k
de clusters. Con el propósito de evaluar la similaridad de las soluciones de
agrupamiento, se desarrolla un mecanismo diferente al empleado en [Ben Hur, 2002]
y [Levine, 2001] que operan sobre bases de datos con solapamiento.
Similar al anterior enfoque, emplea como conjunto de entrenamiento a una
solución de agrupamiento Y = Ak(X) y construye un clasificador φ entrenado sobre
(X, Y) que predice etiquetas ´)(Xφ para el otro conjunto de objetos X´, considerando
entonces el nuevo etiquetado, como una extensión de la solución de agrupamiento Y
del conjunto de datos X al conjunto de datos X´. Estas etiquetas se comparan con las
generadas por el algoritmo de agrupamiento sobre X´, lo que haría comparables las
etiquetas de Ak(X) y Ak(X´), utilizando el clasificador como un mecanismo de
transferencia.
Validación de Clusters
71
Para comparar las dos soluciones ´)(Xφ y Y´, para el mismo conjunto de
datos X´ consideran su distancia de Hamming:
{ }∑=
≠=´
1
´´)(1´
1´)´),((
X
i
ii yxX
YXd φφ (29)
donde { } 1´´)(1 =≠ ii yxφ si ´´)( ii yx ≠φ y cero en otro caso, xi´son los puntos de X´ y
yi´ son las etiquetas del conjunto Y´.
Como se trata de un aprendizaje no supervisado, existe un problema de
ambigüedad de las etiquetas, es decir, no existe una información de las etiquetas para
los clusters pues no hay, en general, unicidad de la representación. Para resolver esto,
se modifica la función de disimilaridad entre dos soluciones en comparación
mediante la expresión:
{ }∑=
Π∈Π ≠=´
1
´´))((1´
1min´)´),((
X
i
ii yxX
YXdk
kφπφ
π
(30)
donde π representa el conjunto de todas las permutaciones de las etiquetas del
conjunto Y´. Esta medida es interpretada como el riesgo de error de clasificación de
φ con respecto al generador de etiquetas Ak.
Como índice de estabilidad del algoritmo de agrupamiento Ak, toma el valor
esperado con respecto al par de conjuntos de datos independientes X y X´, es decir:
´)´),(()( ´, YXdASkXXk φΠΕ= (31)
O sea, la disimilaridad promedio entre soluciones de agrupamiento con
respecto a la distribución de los datos. A su vez, el clasificador empleado influye en
el resultado de la estabilidad, por lo que se define una medida para determinar el
mejor clasificador, lo cual se expresa según la fórmula:
{ }∑=
Π∈∈≠=
´
1
´´))((1´
1minminarg*
X
i
iiC
yxXk
φπφπφ
(32)
Por otro lado, para evitar la dependencia del índice (31) del valor de k y hacer
las comparaciones, el mismo es normalizado con el valor del índice sobre un
agrupamiento aleatorio S(Rk). Es decir:
)(
)()(
k
k
kRS
ASAS =
(33)
es la estabilidad de Ak relativa a la estabilidad alcanzada por el agrupamiento
aleatorio.
El algoritmo puede ser descrito de la siguiente manera:
Capítulo 3
72
Algoritmo para la selección de modelo basado en estabilidad
Entrada: S → conjunto de datos
kmin → número mínimo de clusters
kmax → número máximo de clusters
Repetir para cada { }maxmin ,...,kkk ∈
1. Repetir los siguientes pasos para r divisiones de los datos con el objetivo
de obtener un estimado )( kAS promediando:
1.1. Dividir el conjunto de datos en dos mitades X y X´ y aplicar Ak a
ambos.
1.2. Usar (X, Ak(X)) para entrenar el clasificador φ y calcular ´)(Xφ .
1.3. Calcular la distancia entre las dos soluciones ´)(Xφ y Ak(X´).
2. Realizar agrupamiento aleatorio en k clusters y calcular el promedio de
las disimilaridades empíricas para estimar )( kRS .
3. Normalizar cada )( kAS con )( kRS y obtener un estimado para )( kAS .
Regresar )(minargˆk
k
ASk = como el valor estimado del número de clusters.
Este algoritmo tiene tres limitaciones:
1. Necesita hacer todas las permutaciones de las etiquetas inducidas por el
clasificador.
2. Como el índice de estabilidad del algoritmo de agrupamiento depende de k,
normaliza con el coste de la estabilidad de un predictor aleatorio, lo que hace
el proceso más largo.
3. Depende del método de clasificación elegido, por lo que necesita medir la
influencia del clasificador sobre su estrategia.
Por último, mencionamos el índice de validación que aparece en [Fischer,
2003b] y [Roth, 2002], que emplea un esquema de re-muestreo similar al bootstrap
(bagging) para mejorar la calidad del path-based clustering. Este índice escoge como
el número de clusters óptimo aquel que maximiza la diferencia de la media de las
probabilidades de asignación a los clusters según el algoritmo de agrupamiento p y
la media de las probabilidades de asignación a los clusters generados por un
Validación de Clusters
73
agrupamiento aleatorio 0p , relativo al riesgo de error de clasificación del
agrupamiento aleatorio. Más detalladamente,
−−
=≤≤ 0
0
2
*
1maxarg
p
ppk
ki
(34)
siendo
∑∈
=Oo
ocpO
p ))(ˆ(ˆ1
0 y )(ˆmaxarg)(ˆ 01
lpockl ≤≤
= (35)
Para aplicar su estrategia, parten de suponer que tienen M conjuntos
independientes e idénticamente distribuidos de m objetos, a los que aplica un
algoritmo de optimización aglomerativo path-based para etiquetar a los objetos en un
rango de 1, …, k. Con los resultados del agrupamiento, calcula la media de las
probabilidades de pertenencia a las clases según la fórmula (35), empleando para ello
una estrategia Bootstrap que les permite estimar dichas probabilidades, y obtiene el
número de clusters correcto según la fórmula (34).
Conclusiones. Introducción y Fundamentos Teóricos
En la primera parte de esta memoria de Tesis Doctoral, hemos mostrado los
principales aspectos de la clasificación no supervisada, primero desde una
perspectiva general y, luego, centrándonos en algoritmos específicos. De este modo,
en el Capítulo 2 se han introducido conceptos básicos del Reconocimiento
Estadístico de Formas o Patrones, así como algunos fundamentos estadísticos
necesarios para comprender de manera general un problema de clasificación no
supervisada.
Se han presentado varias estrategias de agrupamiento y algunos de los
algoritmos para cada una de ellas, haciendo hincapié en los algoritmos más
estrechamente vinculados al trabajo desarrollado en esta tesis. Como se ha podido
apreciar, las estrategias de agrupamiento son muy diferentes entre sí, dando lugar a
grupos con diferentes características. Entre las limitaciones podemos mencionar:
1. Las estrategias basadas en centroides fallan cuando los puntos están más
cerca del centroide de otra clase.
2. Estrategias como k-Means tienen una alta dependencia de los valores
iniciales.
3. Varias de las estrategias no manejan el ruido por lo que el resultado del
agrupamiento se afecta.
Capítulo 3
74
4. La presencia de clusters de formas irregulares no siempre es detectada
correctamente, dando lugar a clusters globulares (k-Means) o alargados (SL).
5. La diferencia de densidad y tamaño de los clusters afecta el resultado de
algunas de las estrategias basadas en densidad.
6. El solapamiento entre los grupos origina la unión de dos o más grupos.
Del estudio sobre los diversos métodos de validación de clusters y por la
importancia que para nosotros tiene ésta, de acuerdo a los objetivos de esta tesis, en
el Capítulo 3 se han hecho algunos comentarios acerca de esta temática, dedicando
mayor atención a la estrategia basada en la estabilidad de los clusters por ser la
desarrollada por nosotros, y algunos índices de validación con los que comparamos
nuestros resultados y que será presentada en la segunda parte de esta memoria de
tesis.
Algunas de las limitaciones presentes en las diferentes estrategias vistas son:
1. La existencia de clusters solapados causa resultados erróneos de las diferentes
estrategias, sobre todo de los índices de validación que asumen separación
entre los clusters.
2. Estrategias basadas en centroides no funcionan bien en bases de datos de
diversas formas.
3. La presencia de ruido perjudica el resultado de la validación.
4. En algunos métodos basados en estabilidad es necesario realizar muchas
operaciones lo que hace el proceso de validación largo.
5. El proceso de evaluar todas las permutaciones de las etiquetas aportadas por
el algoritmo de agrupamiento es muy costoso.
Parte II
Aportaciones
Capítulo 4
Algoritmos de Agrupamiento
1 Introducción
En los últimos años el Reconocimiento de Patrones ha adquirido cierta popularidad
gracias a la automatización de las soluciones a muchos problemas de la vida real y en
particular, los métodos de agrupamiento (clustering), debido a que cada vez es más
necesario tratar grandes volúmenes de datos que requieren herramientas nuevas para
descubrir información relevante y relación entre los datos.
Cada una de las estrategias de agrupamiento existentes intenta resolver el
problema de la clasificación de los puntos teniendo en cuenta la presencia o no de
determinadas características en la base de datos. Por ejemplo, el algoritmo k-Means
construye grupos globulares, las estrategias jerárquicas tienden a construir grupos
alargados, algunos algoritmos de agrupamiento no manejan el ruido. Todas estas
consideraciones constituyen limitaciones de los algoritmos de agrupamiento ante la
existencia de conjuntos de puntos de diversas formas y densidades, con determinado
grado de solapamiento entre los grupos y en presencia de ruido.
Uno de los objetivos de la presente Tesis Doctoral es el diseño de un
algoritmo de agrupamiento, dirigido a eliminar las desventajas de algunos de los
métodos de clustering. Para conseguir esto, diseñamos un algoritmo de agrupamiento
híbrido en dos etapas, que emplea primero una estrategia basada en densidad local,
para dividir la base de datos en grupos determinados por zonas de alta densidad, aún
cuando hay solapamiento y diversidad de formas. En la segunda etapa, desarrollamos
una estrategia jerárquica con los grupos resultantes de la primera, en la cual se unen
clusters similares de acuerdo a una función de disimilaridad definida.
En este capítulo, introduciremos dos algoritmos de clasificación no
supervisada con las características mencionadas antes, que tenga en cuenta el
solapamiento entre los grupos, la presencia de ruido y la existencia de clusters de
diversas formas, densidad y tamaño con el objetivo de solucionar las limitaciones de
otras estrategias.
Capítulo 4
78
2 Algoritmo H-Density
Las técnicas no supervisadas de Reconocimiento de Patrones son ampliamente
usadas en problemas que requieren herramientas para descubrir información
relevante y relaciones entre los datos. Aunque existe una gran variedad de técnicas,
muchas de ellas tienen como desventaja que cuando los grupos están muy solapados
no son capaces de separarlos, más aún si hay ruido y tienen formas muy irregulares.
Con el objetivo de resolver esta problemática, empleamos una estrategia
híbrida entre algoritmos de agrupamiento jerárquicos y algoritmos de agrupamiento
basados en densidad (density-based). Los algoritmos de agrupamiento jerárquicos
tienen como característica que generalmente obtienen clusters alargados, por lo que
en presencia de solapamiento no serían capaces de distinguir los grupos y por otra
parte, no manejan bien el ruido, mientras que los algoritmos basados en densidad son
capaces de descubrir clusters de formas y tamaños diferentes y algunos presentan
estrategias para manejar el ruido, pero cuando hay solapamiento resulta difícil
determinar las clases.
Para conseguir nuestro algoritmo dividimos el proceso de agrupamiento en
dos etapas, en la primera de ellas se realiza una primera división de los puntos
empleando una estrategia basada en densidad, así, se formarán grupos separados por
zonas de baja densidad, lo que delimitaría de una manera inicial determinados
subconjuntos de puntos y quedarían unidos en un mismo grupo los puntos
pertenecientes a una misma zona de alta densidad local. Luego, aplicamos una
estrategia jerárquica para unir los clusters obtenidos en la primera etapa [Pascual,
2006].
Sea X un conjunto de N puntos de un universo en estudio provisto de una
métrica, de modo que podamos medir la similaridad entre los patrones y sea R un
número mayor que cero.
Definimos la vecindad cerrada de radio R con centro en un punto Xx∈
como:
{ }RxxdXxxVR ≤∈= ´),(/´)( (36)
Para obtener los grupos de la primera etapa, desarrollamos una técnica similar
al movimiento de puntos ascendiendo una montaña hasta llegar a su cima, y como
herramienta auxiliar para lograrlo, definimos la siguiente función de densidad local.
∑∈
−=
)(´2
2 ´),(exp)(
xVx RR
xxdxp
(37)
Algoritmos de Agrupamiento
79
Según se observa en la fórmula (37), el cociente argumento de la exponencial,
es menor o igual a 1, pues los puntos x´ están a una distancia del punto x menor o
igual que R porque pertenecen a la vecindad de centro en x y radio R. A su vez, como
el argumento es negativo, los valores de la exponencial serán menores o iguales a 1,
por tanto, para interpretar la densidad de puntos que existe en la vecindad de x,
sumamos tantos valores de la exponencial como cantidad de puntos en la vecindad de
x, pero empleando el valor de la distancia de modo tal que mientras más cerca esté el
punto x´ de x, más cerca de 1 será el valor de la exponencial. Así, si x pertenece a una
región de alta densidad, el valor de p(x) será alto y cercano al número de puntos que
hay en su vecindad, mientras que si x está en una zona de baja densidad, el valor de
p(x) será pequeño. Si hiciéramos un gráfico de la función p(x) en cada vecindad sería
como una montaña cuya cima se alcanzaría en el punto de la vecindad de mayor
densidad (Figura 4).
En nuestra estrategia, consideramos inicialmente el conjunto X dividido en N
grupos unitarios. Dado un valor especificado R > 0, hallamos para cada punto x de la
base de datos su vecindad de radio R y calculamos el valor p(x).
Luego, verificamos si en la vecindad de x hay un punto x´ diferente de él de
máxima densidad, en nuestra interpretación, esto significa que x´ está en una
posición más alta de la montaña por lo que movemos el punto x y todos los de su
clase hacia la clase de x´, o sea, hacia una posición más alta de la montaña (Figura 4).
Figura 4. Estrategia basada en densidad local.
Inicialmente, cada punto pertenece a un grupo unitario, por lo que los
primeros puntos que se reubican se mueven solos, pero a medida que comienzan a
migrar, aparecerán clusters no unitarios y por tanto migrarán no sólo los puntos
evaluados en ese momento si no también los de su clase, y esta migración se hará
Capítulo 4
80
linealmente, o sea, cada punto es visitado una sola vez y cuando le toque su turno, si
en su clase ya hay puntos que han migrado, todos se moverán hacia el cluster
correspondiente en caso de cumplirse la condición de densidad. Así, todos los puntos
van arrastrando como una cola hacia la cima de una montaña mientras sea posible.
De esta forma, obtendremos una división en clases de alta densidad. Los
puntos que pertenezcan a zonas de baja densidad formarán grupos pequeños y en
algunos casos unitarios. Los grupos obtenidos estarán separados por regiones de
menor densidad y constituyen los clusters resultantes de la primera etapa de nuestro
algoritmo.
La primera etapa de nuestro algoritmo puede resumirse en la siguiente forma:
Primera Etapa Algoritmo H-Density
Entrada: X → conjunto de datos
R → radio de la vecindad de cada punto
U → umbral de densidad
1. Inicialmente cada punto de la base de datos se asigna a un grupo
unitario.
2. Para cada punto x se calcula su vecindad de radio R.
3. Para cada punto x se estima su densidad según la fórmula (37).
4. Cada punto x y todos los puntos de su clase se asignan al grupo del
punto x´ de la vecindad de x que tenga densidad máxima.
5. Marcar todos los grupos tales que el número de sus elementos no supera
el valor U especificado.
Devolver los clusters no marcados.
Debido a que en la primera etapa se obtienen clusters que no consideraremos
directamente en la segunda etapa, hemos dado un nombre auxiliar para no provocar
confusiones. Los grupos que tengan más puntos que el umbral prefijado U se
llamarán clusters o grupos centrales (core clusters), los otros serán para nosotros
clusters ruido (noise clusters).
En la segunda fase del algoritmo comenzaremos con los grupos obtenidos en
la primera etapa, o sea, los core clusters. Para continuar el proceso, efectuamos una
Algoritmos de Agrupamiento
81
estrategia jerárquica aglomerativa con esos grupos iniciales, más exactamente un SL
e iremos uniendo en cada nivel los dos clusters más semejantes.
Con el objetivo de determinar cuáles son los dos clusters más semejantes,
definimos una función de disimilaridad que tiene en cuenta la distancia entre puntos
y la densidad de los mismos, como explicaremos a continuación.
Consideraremos que cada core cluster pertenece a un grupo o cluster unitario,
esto es, Ki denotará los clusters iniciales de la segunda etapa del algoritmo mientras
que Ci denotará los core clusters resultado de la primera etapa, e inicialmente,
{ }ii CK = , i = 1, …, M (M es el número de core clusters obtenidos en la primera
etapa).
Dados dos core clusters Ci y Cj definimos la distancia entre ellos por la
siguiente fórmula:
{ }jjiijiji CxCxxxdCCd ∈∈= ,/),(min),(1 (38)
A su vez, si Ki y Kj son dos grupos, consideramos la misma distancia anterior
viendo ahora a los core clusters como puntos, es decir:
{ }jjiijiji KCKCCCdKKd ∈∈= ,/),(min),( 12 (39)
Finalmente, la disimilaridad entre dos clusters será medida teniendo en
cuenta tanto la distancia entre ellos como la densidad en la zona de solapamiento de
acuerdo a la siguiente expresión:
( )),(1),( 2 ji
c
bc
ji KKdP
PPKKd +
−=
(40)
donde estamos utilizando el factor:
c
bc
P
PPF
−=
(41)
como una medida del solapamiento entre los clusters.
Para determinar los valores Pc y Pb de la ecuación (40), primero buscamos los
dos core clusters más cercanos de entre todas las parejas de core clusters, uno de
cada grupo, luego, determinamos el punto de máxima densidad en cada uno (xn y xm
en la Figura 5) y tomamos como Pc la menor de las densidades de esos dos puntos, es
decir, ( ))(),(min nmc xpxpP = .
Capítulo 4
82
Figura 5. Medidas de solapamiento entre clusters.
Por otro lado, el valor Pb representa la densidad del punto medio entre los dos
clusters (Figura 5), es decir, el punto medio xb entre los dos puntos x´ y x´´ más
cercanos uno de cada cluster. A los puntos x´ y x´´ les llamamos puntos borde.
Finalmente, la densidad Pb la estimamos tomando la densidad del punto borde
perteneciente al core cluster del punto xm en la Figura 5, es decir, el borde del
subconjunto que contiene el punto de mínima densidad entre los dos puntos de
máxima densidad de cada core cluster.
También queremos hacer notar que en el caso de clusters muy separados se
hace una consideración adicional. Si los clusters están muy separados (la distancia
entre ellos mayor que R), el punto xb no tendrá puntos en su vecindad, por lo que su
densidad la consideramos nula, resultando en este caso, que el factor con el que
evaluamos el solapamiento (fórmula (41)) tomaría el valor 1, por lo que, cuando la
distancia entre los puntos borde del par de clusters es mayor que R hacemos:
),(1),( 2 jiji KKdKKd += (42)
Otro comentario acerca del algoritmo está relacionado con los conjuntos
ruido que marcamos en la primera etapa. Como hemos dicho antes, desarrollamos la
estrategia jerárquica únicamente con los core clusters, por lo que quedarían los
puntos de los conjuntos marcados como ruido sin etiquetar, luego, una vez que
llegamos al nivel de k grupos, agregamos los conjuntos ruido al cluster más cercano.
A continuación, mostramos la segunda etapa del algoritmo.
Algoritmos de Agrupamiento
83
Segunda Etapa Algoritmo H-Density
Entrada: S → conjunto de core clusters
k → número de clusters final
1. Inicialmente cada core cluster Ci se asigna a un grupo unitario Ki.
2. Repetir la estrategia SL hasta que hayan k clusters empleando la medida
de disimilaridad de las fórmulas (40) o (42).
3. Asignar los conjuntos ruido al cluster más cercano.
Devolver los k clusters resultantes.
3 Algoritmo DHG (Density-based Hierarchical
Gaussian)
El algoritmo H-Density tiene como limitación los dos parámetros fundamentales de
los que depende, el radio de la vecindad y el umbral de densidad. El radio por
ejemplo, es un valor real por lo que es difícil determinar un intervalo que nos
garantice el resultado correcto para cada una de las bases de datos, y aunque el
umbral de densidad es un valor entero, varía mucho en dependencia de la base de
datos.
Debido a las limitaciones del algoritmo H-Density antes mencionadas,
diseñamos un nuevo algoritmo conservando nuestra estrategia híbrida basada en
densidad y jerárquica. Una de las características que mantuvimos, es la relacionada
con la obtención de los grupos de la primera etapa a través del movimiento de los
puntos por una colina, mediante el empleo de una función de densidad, debido a la
efectividad y simplicidad de esta estrategia.
Entre los algoritmos que nos dan la posibilidad de modelar una función de
densidad está el algoritmo EM (Expectation Maximization). El algoritmo EM
construye una función de densidad suave compuesta por varios modos gaussianos
que emplea como único parámetro, el número de modos que deben conformar la
mixtura. Por tanto, el primer paso del diseño de nuestro algoritmo, consiste en
calcular la función de densidad como una mixtura de gausianas:
Capítulo 4
84
∑=
=osk
i
ii yxpxpmod
1
)/()( α (43)
Para eliminar el parámetro R, que puede ser más complejo de determinar, en
lugar de considerar los vecinos de la vecindad de radio R, tomamos los K vecinos
más cercanos y realizamos la misma operación: mover al punto y todos los de su
clase hacia la clase del vecino de mayor densidad. De esa forma, conseguimos un
agrupamiento inicial.
La primera etapa del algoritmo DHG se puede ver en el siguiente recuadro:
Primera Etapa Algoritmo DHG
Entrada: X → conjunto de datos
kmodos → número de modos
K → número de vecinos
1. Inicialmente cada punto de la base de datos se asigna a un grupo unitario
2. Para cada punto x se buscan sus K vecinos más cercanos.
3. Para cada punto x se estima su densidad según la fórmula (43).
4. Cada punto x y todos los puntos de su clase se asignan al grupo de su
vecino x′ de densidad máxima.
Salida: Devolver los clusters obtenidos.
En la segunda etapa desarrollamos la estrategia jerárquica. Para esto,
definimos una función de disimilaridad entre clusters, que nos permite ejecutar el
algoritmo SL a partir de los grupos obtenidos en la primera etapa, que tiene en cuenta
la distancia entre los grupos, el ruido y la distancia entre los puntos de mayor
densidad de cada cluster.
En el diseño de la función de disimilaridad, manejamos la misma suposición
acerca de los clusters de la segunda etapa: que estarían formados por los clusters de
la primera etapa e igualmente, para no caer en confusiones denotaremos por core
clusters, a los obtenidos en la primera etapa y clusters a los grupos cuyos elementos
son los core clusters. Por tanto, iniciamos la segunda etapa del algoritmo
Algoritmos de Agrupamiento
85
considerando M clusters unitarios, donde M es la cantidad de core clusters de la
primera etapa.
Más claramente, para ajustar nuestro modelo de la función de disimilaridad,
como antes, se propone que esté formada por varios factores, uno de ellos d de la
ecuación (42), que tiene en cuenta la distancia entre los clusters calculada como la
distancia entre el par de core clusters más cercanos (uno de cada cluster). El objetivo
de conservar el factor (42) es medir cuán cercanos están los dos clusters.
Con el factor (42) no se tiene en cuenta la presencia de ruido entre los grupos,
lo que crea confusión, debido a que dichos puntos provocan que la distancia entre los
clusters sea menor, y en la parte jerárquica, se unirían grupos que en realidad
deberían estar separados, ya que hay una zona de baja densidad entre ellos.
Para manejar el ruido, utilizamos otra medida de distancia, la distancia entre
los puntos de mayor densidad de los dos core clusters más cercanos, como se
muestra en la Figura 6 pues, si los core clusters están bien separados es de suponer
que la distancia entre sus centros sea grande, de esta manera, manejamos el hecho de
que los puntos ruidosos puedan engañarnos al estar situados entre dos core clusters.
Es decir, utilizamos el factor:
),(),(ˆ nmji xxdKKd = (44)
donde, xm y xn son los puntos centrales de los modos más cercanos, uno del cluster Ki
y otro del cluster Kj, d es la distancia definida en el espacio de puntos.
Figura 6. Distancia entre los puntos de mayor densidad.
Como en el algoritmo H-Density, necesitamos un factor para medir la
densidad entre los dos core clusters más cercanos, por la misma razón, porque puede
haber una zona de baja densidad entre los clusters que no es detectada por las
distancias antes mencionadas.
Con el objetivo de medir la densidad entre los clusters, tomamos los dos
puntos borde de los dos clusters que se comparan. Para el punto borde del cluster Ki
(Kj), contamos cuántos de sus K vecinos pertenecen al cluster Kj (Ki), y tomamos el
número Ne como el mínimo entre los dos valores anteriores. Además, sumamos el
Capítulo 4
86
valor 1 para evitar que el denominador se anule y tengamos una indeterminación, lo
cual puede suceder cuando los clusters están muy separados.
O sea, en lugar del factor (41) que empleamos en el algoritmo H-Density para
medir la densidad entre los clusters, tomamos el factor:
eNF
+=1
1
(45)
Al dividir por 1 + Ne estamos contrayendo las distancias de tal modo que
mientras más vecinos tengan los puntos borde en la otra clase, menor será el
resultado final de la disimilaridad entre clusters. Consideramos que este factor puede
expresar la densidad entre grupos, ya que, si los clusters están muy solapados es de
esperar que el punto del borde de un cluster tenga muchos vecinos en el otro cluster,
mientras que si los clusters están separados, tendrán pocos o ningún vecino en la otra
clase, luego Ne sería pequeño o cero y el valor 1/(1+Ne) sería 1 o cercano al valor 1,
por lo que la disimilaridad dependería prácticamente sólo de las distancias (42) y
(44). Otra cuestión que se ha tenido en cuenta relacionado con este factor, es que si
por ejemplo, entre dos grupos hay un punto ruido que a su vez es borde de un cluster
con relación a otro, y que está muy cerca del otro cluster, tendría consecuentemente
muchos vecinos en la otra clase, pero en este caso, el punto borde de esa otra clase,
tendría pocos vecinos en la clase contraria, motivo por el cual tomamos el mínimo de
los dos valores como Ne para estimar la densidad existente entre los clusters.
En resumen, la nueva función de disimilaridad se define como:
)),(1(),(ˆ1
1),( 2 jiji
e
ji KKdKKdN
KKd ++
= (46)
La segunda etapa del algoritmo DHG será:
Algoritmos de Agrupamiento
87
Segunda Etapa Algoritmo DHG
Entrada: S → conjunto de core clusters
k → número de clusters final
1. Inicialmente cada core cluster se asigna a un grupo unitario.
2. Repetir la estrategia SL hasta que hayan k clusters empleando la medida
de disimilaridad de la fórmula (46).
Devolver los k clusters resultantes.
4 Resultados Experimentales
En esta sección mostraremos el estudio comparativo que realizamos con algunos de
los algoritmos de agrupamiento existentes en la literatura consultada para evaluar
nuestras estrategias, éstos son: k-Means (clásico), CURE, DBSCAN, EM y el
algoritmo basado en caminos de Fischer y Buhmann.
4.1 Bases de datos
Con el objetivo de mostrar los resultados de los dos algoritmos y hacer un análisis
comparativo con otros métodos, utilizamos tres conjuntos de datos. El primero de
ellos, constituido por tres bases de datos sintéticas de modos gausianos, con
diferentes grados de solapamiento entre sí. El segundo grupo, está formado por bases
de datos sintéticas cuyos clusters tienen formas y tamaños diferentes, y en el tercer
grupo, hemos considerado bases de datos reales.
En la Tabla 2 se resumen las características más importantes de cada una de
las bases de datos consideradas: número de clases, número de rasgos y número de
objetos.
Capítulo 4
88
Nombre No.
clases
No.
rasgos
No.
objetos
G4 4 2 4000
G6 6 2 6000
G6-II 6 2 6000
DS1 6 2 8000
DS2 9 2 10000
3AC 3 2 732
2SA 2 2 355
House 5 3 65536
Cancer 2 9 683
Iris 3 4 150
Diabetes 2 8 678
Liver 2 6 345
Phoneme 2 5 5404
Satimage 6 32 6435
Tabla 2. Breve sumario de las bases de datos.
A continuación mostramos con más detalles cada una de las bases de datos.
Bases de datos sintéticas
En la Figura 7 se muestran las bases de datos sintéticas del primer grupo. La base de
datos G4 (Figura 7a) está constituida por 4 modos gausianos poco solapados. La base
de datos G6 (Figura 7b) consta de seis modos gausianos, dos de ellos bien separados
del resto y entre sí, mientras que los otros cuatro están altamente solapados. La
tercera de las bases de datos G6-II (Figura 7c), también está formada por seis modos
gausianos con cierto grado de solapamiento entre ellos, pero dos están
completamente solapados con la misma media y diferentes matrices de covarianzas.
Algoritmos de Agrupamiento
89
Figura 7. Bases de datos gausianas: a) G4, b) G6, c) G6-II.
El segundo conjunto de datos se aprecia en las Figuras 8 y 9. Los clusters
tienen formas diversas y diferentes tamaños. En la Figura 8, la base de datos 3AC,
tiene 3 anillos concéntricos, mientras que la base de datos 2SA, está formada por dos
semianillos, ambas con muy pocos puntos como se observa en la Tabla 2. En el caso
de la Figura 9 aparecen las bases de datos DS1 y DS2 tomadas de [Karypis, 1999],
cuyos grupos tienen diferentes formas y tamaños y con puntos ruidosos. El objetivo
de utilizar estas dos bases de datos es obtener las seis y nueve figuras relevantes en
DS1 y DS2 respectivamente.
Figura 8. Bases de datos: a) 3AC, b) 2SA
Capítulo 4
90
Figura 9. Bases de datos: a) DS1, b) DS2
Bases de datos reales
En el tercer grupo consideramos las bases de datos reales: House, Iris, Cancer,
Diabetes, Liver, Phoneme y Satimage. La base de datos House consiste en los
valores cromáticos de la representación Lab de la imagen House de 256 x 256 pixels
(Figura 10a). Para realizar los experimentos tomamos solo la representación en el
espacio ab de la que obtuvimos los puntos que se muestran en la Figura 10b.
Figura 10. Base de datos House: a) Imagen original, b) Representación en el espacio ab
Las restantes bases de datos reales fueron tomadas del repositorio UCI
Machine Learning Database Repository [Merz, 1996]. En el Anexo A hacemos un
resumen de las características de estas bases de datos.
4.2 Análisis comparativo de las diferentes estrategias sobre las
bases de datos sintéticas
En este epígrafe mostramos los resultados experimentales sobre las diferentes bases
de datos sintéticas y los comentarios necesarios, describiremos los resultados con
cada método de agrupamiento de manera independiente.
Algoritmos de Agrupamiento
91
Algoritmo DBSCAN
Debido a las características de este algoritmo de ir enlazando las vecindades más
pobladas de los puntos, cuando las bases de datos tienen grupos muy solapados, es
incapaz de detectarlos, lo que ocurre por ejemplo, en el caso de la base de datos G6,
sobre la que no puede obtener los seis modos, pero obtiene los tres grupos separados
con cierta cantidad de puntos ruido en dependencia del valor del radio (los
cuadraditos representan los puntos ruidosos).
Figura 11. Resultados del algoritmo DBSCAN sobre la base de datos G6: a) División en tres
clusters, b) Incremento de los puntos ruido, c) Asignación de los puntos ruido al cluster más
cercano.
En la Figura 11a mostramos uno de los resultados de DBSCAN, se pueden
ver los puntos ruido alrededor de estos clusters. En la Figura 11b mostramos el
resultado luego de haber disminuido el radio de la vecindad, lo que trajo como
consecuencia no la aparición de más clusters sino un aumento de los puntos ruido,
debido a que a medida que el radio disminuye, algunos puntos borde se convierten en
puntos ruido. Sin embargo, se puede manejar el ruido agregando dichos puntos al
cluster más cercano y de ese modo se obtiene el resultado de la Figura 11c que es el
correcto cuando dividimos en tres clases.
Empleando la misma estrategia para manejar el ruido, en el caso de la base de
datos G4, descubre los 4 grupos grandes correspondientes con los modos gausianos y
dos grupos muy pequeños (Figura 12a) mientras que con G6-II no puede separar los
clusters muy solapados (Figura 12b).
Capítulo 4
92
Figura 12. Resultados del algoritmo DBSCAN: a) Base de datos G4, b) Base de datos G6-II
Los resultados sobre las bases de datos DS1 y DS2 se comentan en [Karypis,
1999], para éstas, el algoritmo es capaz de descubrir las figuras destacadas (6 en DS1
y 9 en DS2), además de otros grupos pequeños.
Todos los puntos de las bases de datos 2SA y 3AC fueron correctamente
etiquetados con este algoritmo, lo que demuestra que el algoritmo DBSCAN es capaz
de descubrir clusters de formas arbitrarias. Como se observa, en estas bases de datos
no hay puntos ruido y la separabilidad entre las clases es clara por lo que cuando se
aplica DBSCAN, fácilmente enlaza los puntos de un mismo cluster porque
pertenecen a una misma zona de alta densidad.
Algoritmo CURE
Este algoritmo obtiene mejores resultados que el anterior con las bases de datos
gausianas, descubre los 4 modos de G4 y 5 grupos en la base G6-II, pues no puede
separar los dos modos concéntricos. En el caso de la base de datos G6, no detecta los
6 modos, debido al solapamiento entre cuatro de ellos. Cuando dividimos en tres
clases obtiene los tres clusters bien separados. En la Figura 13 se puede ver el
resultado del algoritmo CURE sobre estas bases de datos, nótese que este algoritmo
maneja bien el ruido.
Algoritmos de Agrupamiento
93
Figura 13. Resultados del algoritmo CURE: a) Base de datos G4, b) Base de datos G6-II, c) Base
de datos G6.
En el caso de las bases de datos DS1 y DS2, CURE no puede descubrir los
clusters verdaderos por tener variadas formas y ruido. Aunque en su estrategia trata
de manejar el ruido, como éste se encuentra también entre las clases, al tratar de
atraerlos hacia el centro del cluster posiblemente deforma las figuras. Además, con la
estrategia de puntos representativos es difícil captar las formas tan variadas que se
muestran en la Figura 9.
Las bases de datos 3AC y 2SA son etiquetadas correctamente por el
algoritmo CURE, a causa de la separación que hay entre las clases, que es detectada
por los representantes de clase y por la estrategia que emplea para manejar el ruido.
Algoritmo EM
Este algoritmo por sus características obtiene muy buenos resultados cuando las
bases de datos están formadas por modos gausianos, o sea, sobre las bases G4, G6 y
G6-II, donde obtiene los clusters correctos incluso cuando hay solapamiento, como
es el caso de G6 que detecta los seis modos, y de G6-II pues descubre los 6 modos
incluidos los dos concéntricos.
Capítulo 4
94
Figura 14. Resultados del algoritmo EM: a) DS1, b) DS2.
Nótese en la Figura 14 cómo en el caso de las bases de datos DS1 y DS2, el
algoritmo EM va colocando modos gausianos que cubren los puntos sin descubrir las
figuras.
Sobre el resto de las bases de datos sintéticas no puede determinar la división
adecuada, y se comporta de manera similar que para las bases DS1 y DS2.
Algoritmo k-Means
Nosotros aplicamos en nuestros experimentos el algoritmo k-Means clásico, cuya
inicialización es aleatoria. Descubre los verdaderos clusters sobre la base de datos
G4 pero no así cuando lo aplicamos sobre G6 y G6-II. En el caso de la base de datos
G6 determina los tres grupos no solapados. Respecto a las restantes bases de datos,
no puede encontrar las figuras de diferentes formas en DS1 y DS2, ni los 3 anillos
concéntricos, ni los dos semianillos en las bases de datos 3AC y 2SA,
respectivamente, porque este algoritmo basa su estrategia en centroides y varianza
dentro de los grupos por lo que su tendencia es de formar clusters globulares. En las
Figuras 15 y 16 mostramos el resultado de k-Means sobre estas bases de datos.
Figura 15. Resultados del algoritmo k-Means: a) DS1, b) DS2.
Algoritmos de Agrupamiento
95
Figura 16. Resultados del algoritmo k-Means: a) 3AC, b) 2SA.
Obsérvese que en todos los casos k-Means establece las fronteras de las clases
de acuerdo al centroide, independientemente de que haya separación entre las clases
como es el ejemplo de las bases de datos 3AC y 2SA (Figura 16).
Algoritmo Path Based Clustering de Fischer y Buhmann (FB)
Este algoritmo debido a la estrategia que emplea de unir clusters de objetos
enlazados por un camino cuya disimilaridad efectiva es baja, tiene buenos resultados
al trabajar sobre bases de datos como 3AC y 2SA como se muestra en la Figura 17.
Figura 17. Resultados del algoritmo FB: a) 3AC, b) 2SA.
También descubre los modos de las bases de datos G4, y DS1, aunque en el
caso de G4 existe un puente entre objetos del borde de los dos clusters en rojo y en
verde debido al solapamiento.
Capítulo 4
96
Figura 18. Resultados del algoritmo FB: a) G4, b) DS1.
El resultado sobre las bases de datos DS2, G6 y G6-II, respectivamente, está
determinado por el ruido que perjudica la verdadera división, Observe, por ejemplo,
en la Figura 19, como se unen las dos barras en marrón en DS2 debido a que hay una
cadena de puntos que las enlazan y que están a poca distancia. Sin embargo, aparece
un cluster en amarillo claro de puntos más dispersos cuyas disimilaridades efectivas
deben ser mayores que las de los puntos de las dos barras en marrón.
Figura 19. Resultado del algoritmo FB: DS2.
Algoritmo H-Density
Para realizar los experimentos, tomamos la distancia euclídea como distancia entre
los puntos. Con nuestra estrategia los grupos presentes en todas las bases de datos
sintéticas y House son descubiertos por la capacidad que tiene de encontrar zonas de
baja densidad entre los clusters aún en el caso de clases muy solapadas pues, de
todas formas, la densidad en el centro del cluster es superior a la densidad en las
fronteras, lo que influye en el valor del factor de solapamiento que se tiene en cuenta
en la medida de disimilaridad escogida.
En cuanto a la base de datos G6-II el algoritmo descubre 5 clases debido a la
estrategia que emplea de mover los puntos hacia la cima de una montaña, en el caso
de los dos modos concéntricos, el punto de mayor densidad de ambos grupos es el
mismo por lo que no puede separar esos dos clusters.
Algoritmos de Agrupamiento
97
Algoritmo DHG
Con el objetivo de evaluar este algoritmo, empleamos las mismas bases de datos
mencionadas antes. Sobre las bases de datos G4, G6 y G6-II (Figura 7) se obtuvo el
resultado adecuado en el primer nivel de la jerarquía para todos los valores de
kmodos y de K empleados. Es decir, en la primera etapa de clasificación, sin importar
el valor de los parámetros, el agrupamiento fue correcto. En el caso de G6-II, el
primer nivel comienza con los 5 modos como en la Figura 13b, pues esta estrategia
de mover los puntos hacia la cima de la montaña no puede diferenciar los dos modos
concéntricos ya que esos dos modos tienen el mismo punto de máxima densidad.
Ejecutamos nuestro algoritmo con valores de K desde 15 hasta 35 y el número de
modos entre 4 y 15 para G4, entre 6 y 15 para G6 y entre 5 y 15 para G6-II.
Con el objetivo de asegurarnos que con las bases de datos compuestas por
modos gausianos el algoritmo consigue esos resultados independientemente de si los
clusters son globulares o elipsoidales, agregamos dos bases de datos más con cierto
grado de solapamiento: G3 formada por tres grupos gausianos, dos de ellos
elipsoidales (Figura 20a) y G4-II formada por 4 grupos gausianos dos de ellos
elipsoidales (Figura 20b) y el resultado fue el mismo, luego de haber ejecutado el
algoritmo con el mismo rango de valores para K que las anteriores y en el caso del
número de modos valoramos para G3 desde 3 hasta 15 y para G4-II entre 4 y 15.
Figura 20. Bases de datos: a) G3, b) G4-II.
A su vez, sobre las bases de datos 3AC y 2SA (Figura 8), a pesar de que
utilizamos la mixtura gausiana que según explicamos en el estudio comparativo que
hicimos antes, el algoritmo EM no puede descubrir los 3 anillos ni los dos
semianillos que forman estas bases de datos, respectivamente, podemos concluir que
nuestra estrategia corrige las limitaciones del EM determinando los clusters
correctos, debido a que entre los anillos y semianillos hay una zona de baja densidad
que es detectada, logrando la separación de los clusters adecuadamente. Estas dos
bases de datos tienen como característica fundamental que están formadas por muy
pocos puntos, por lo que no podemos tomar un número de vecinos muy alto ya que
Capítulo 4
98
ocurriría una gran confusión, debido a que cada punto tendría muchos vecinos en
otra clase y como resultado se obtendría un solo grupo. Según los experimentos
realizados obtuvimos resultados correctos para valores de K desde 5 hasta 27 y
kmodos desde 3 hasta 15 y desde 2 hasta 15 para 3AC y 2SA, respectivamente.
Agregamos otra base de datos a nuestro estudio formada también por tres
anillos concéntricos (3AC-II) pero con más de 6000 puntos (Figura 21), para valorar
lo relacionado con el número de vecinos a tomar en bases de datos pequeñas, y los
resultados fueron correctos para todos los valores de kmodos entre 3 y 15 y de K
entre 15 y 35, en el nivel de tres clases obtuvimos los tres anillos que se muestran en
la Figura 21.
Figura 21. Resultado del algoritmo DHG sobre la base de datos 3AC-II.
La característica fundamental de las bases de datos DS1 y DS2 (Figura 9), es
que las figuras que se destacan están acompañadas de mucho ruido, lo que dificulta
la evolución de la mayoría de los algoritmos, como nuestra estrategia trata de
manejar el ruido y de detectar las zonas de baja densidad entre los grupos, obtuvimos
las figuras relevantes para varios rangos de los parámetros. En el caso de DS1
probamos con valores de kmodos desde 20 hasta 50, y K entre 15 y 35. En el rango
considerado para kmodos con varios valores de K conseguimos el agrupamiento
correcto, entre los que se destacan 27, 28, 34 y 35. La base de datos DS2 es más
compleja, la cantidad de ruido es superior en gran medida pero obtuvimos las 9
figuras con kmodos = 50 y K = 35, además de otros resultados en niveles de más de 9
clases en los que aparecen las 9 figuras acompañadas por otros grupos pequeños.
A continuación presentamos los resultados obtenidos con cada una de las
estrategias de agrupamiento sobre las bases de datos reales.
Algoritmos de Agrupamiento
99
4.3 Análisis comparativo de las diferentes estrategias sobre las
bases de datos reales
Para realizar los experimentos con la base de datos House, tomamos solo la
representación en el espacio ab de la que obtuvimos los puntos que se muestran en la
Figura 10b, sobre ellos aplicamos los diferentes algoritmos y luego al volver al
espacio Lab con las etiquetas obtenidas con el agrupamiento, comprobamos si se
obtiene el etiquetado correcto o no. A igual que en el caso de las bases de datos
sintéticas, mostramos los resultados de cada una de las estrategias sobre la base de
datos House de manera independiente.
Para calcular el porcentaje de error de los algoritmos de agrupamiento para
las restantes bases de datos reales, empleamos uno de los métodos descritos en
[Meila, 2001] con el fin de comparar dos agrupamientos, tomando el resultado del
algoritmo de agrupamiento por un lado y los objetos correctamente etiquetados por
otro. En el caso de la regla K-NN utilizamos el método Holdout.
El algoritmo DBSCAN no reconoce los 5 grupos de la base de datos House,
sólo puede detectar un cluster debido al solapamiento tan grande que existe y a
medida que vamos disminuyendo el radio lo que conseguimos es aumentar los
puntos ruido y resulta imposible obtener más clusters.
Figura 22. Resultados del algoritmo CURE sobre la base de datos House: a) 5 clusters, b) Trece
clusters.
Cuando ejecutamos el algoritmo CURE sobre la base de datos House para
cinco clases, no obtenemos los clusters que deseamos, sino que los puntos de la zona
de gran solapamiento forman 3 grupos (Figura 22a) y los restantes 2 grupos se
obtienen en las zonas de puntos más alejados. Por otro lado, si hacemos la división
en 13 clases obtenemos una aproximación a los clusters deseados como se muestra
en la Figura 22b.
El algoritmo EM sobre House no puede determinar la división adecuada,
comportándose de manera similar que para las bases DS1 y DS2.
Capítulo 4
100
El algoritmo k-Means basa su estrategia en centroides y varianza dentro de
los grupos por lo que su tendencia es de formar clusters globulares, a su vez, House
tiene clusters muy solapados por lo que se obtiene el resultado que se muestra en la
Figura 23.
Figura 23. Resultado del algoritmo k-Means sobre la base de datos House: a).Imagen original, b)
Imagen obtenida después del etiquetado, c) División en 5 clases en el espacio ab.
En la Figura 24, se observa el resultado del algoritmo FB sobre la base de
datos House, en el nivel de 5 clases (Figura 24a), debido al solapamiento existente y
a los puntos dispersos, se obtiene un cluster grande formado por 4 de los clusters, por
lo que no puede descubrir los 5 clusters verdaderos. Extendimos el análisis a los
niveles de 6 y 7 clases para hacer notar que dicha estrategia no se puede emplear en
casos de mucho solapamiento y ruido.
Figura 24. Resultados del algoritmo FB sobre la base de datos House: a) 5 clases, b) 6 clases, c) 7
clases.
En el caso del algoritmo H-Density, obtuvimos los 5 clusters
correspondientes a 5 colores en la imagen, en la Figura 25 mostramos los resultados
obtenidos. Se puede ver en la figura del medio que el resultado de la clasificación
luego de representar los puntos etiquetados en el espacio Lab es bastante cercano a la
imagen original (Figura 25a).
Algoritmos de Agrupamiento
101
Figura 25. Resultado del algoritmo H- Density sobre la base de datos House: a) Imagen original,
b) Imagen obtenida luego del etiquetado, c) División en 5 clases en el espacio ab.
La base de datos real House, consta de 65536 puntos con un nivel de
solapamiento muy alto como se aprecia en la Figura 10b, motivo por el cual es difícil
separar los puntos en clases. Con el empleo de nuestro segundo método, alcanzamos
una división en 5 clases como se muestra en la Figura 26, muy similar a la que
obtuvimos con el algoritmo H-Density. Los valores de kmodos variaron entre 5 y 15
y los de K entre 15 y 35 y obtuvimos el resultado que se muestra para valores de
kmodos iguales a 15 y 16 y K desde 15 hasta 35.
Figura 26. Resultado del algoritmo DHG sobre la base de datos House: a) Imagen original, b)
Imagen obtenida luego del etiquetado, c) División en 5 clases en el espacio ab.
En la Tabla 3 mostramos el porcentaje de puntos correctamente etiquetados
para cada una de las restantes bases de datos reales según los métodos de
agrupamiento antes mencionados; además, incluimos el porcentaje que se obtiene
con la regla de clasificación K-NN para comparar nuestro método también con esa
regla de clasificación supervisada.
Capítulo 4
102
CURE DBSCAN k-
Means EM FB
H-
Density DHG k-NN
Iris 90,00 84,00 89,33 88,00 69,33 96,00 96,66 66,33
Cancer 95,46 94,28 95,04 79,50 96,77 95,46 97,07 96,77
Diabetes 65,88 59,43 66,01 66,01 64,71 66,01 66,01 64,70
Liver 57,68 58,26 55,07 51,01 57,10 59,42 62,31 68,41
Phoneme 70,65 70,74 66,8 70,11 70,74 77,62 74,14
Satimage 51,77 56,67 57,74 55,89 72,05 81,11 83,01
Tabla 3. Porcentaje de clasificación correcta de las diferentes estrategias.
Según se observa en la Tabla 3, en casi todos los casos el porcentaje de
clasificación correcta que se obtiene al aplicar el algoritmo DHG supera al resto de
los algoritmos. Tomamos el clasificador supervisado K-NN por ser una regla de
clasificación ampliamente utilizada en Reconocimiento de Patrones, con el objetivo
de valorar si los porcentajes de clasificación correcta obtenidos con los algoritmos de
clasificación no supervisada, presentados en esta memoria de tesis, con la sola
utilización de un conjunto de objetos de una población en estudio, estaban muy
alejados de los obtenidos con la regla supervisada K-NN. Se puede ver que para
varias bases de datos el resultado del algoritmo DHG es superior al de la regla K-NN,
en el caso de la base de datos Satimage el resultado del algoritmo DHG es el más
cercano al de la regla K-NN.
5 Conclusiones
En este capítulo, hemos presentado dos algoritmos de agrupamiento que se pueden
emplear en distribuciones arbitrarias y sin suposición acerca de la forma y tamaño de
los grupos. El algoritmo H-Density estima una función de densidad local para
clasificar los puntos en conjuntos iniciales y luego, con el resultado de esta primera
etapa desarrolla una estrategia jerárquica hasta obtener el agrupamiento final.
Para aplicar nuestra estrategia jerárquica definimos una función de
disimilaridad entre grupos que tiene en cuenta no solo la cercanía de los clusters sino
también su densidad evaluando la diferencia de densidades entre el punto de mayor
densidad de un cluster y los puntos de la frontera.
Hemos mostrado la validez del método de agrupamiento con los resultados
experimentales sobre bases de datos sintéticas y reales con diferentes características:
solapamiento entre las clases, ruido, clusters de diferentes formas, densidades y
tamaño.
Algoritmos de Agrupamiento
103
Con el objetivo de eliminar las dificultades para determinar el valor de los
parámetros del algoritmo de agrupamiento H-Density para cada una de las bases de
datos, construimos el algoritmo DHG, diseñado con la misma estrategia híbrida
basada en densidad y jerárquica cuyos parámetros son valores enteros fáciles de
manejar.
Otro resultado importante es la definición de la nueva función de
disimilaridad entre clusters para desarrollar la etapa jerárquica del algoritmo. Esta
nueva función de disimilaridad consta de tres factores con el objetivo de tener en
cuenta la distancia entre los clusters, el ruido y la densidad de puntos presentes entre
los grupos.
Los resultados experimentales demuestran el alcance del enfoque empleado y
las ventajas en cuanto al uso de sus parámetros.
Capítulo 5
Validación de Clusters
1 Introducción
La aplicación de los procedimientos de validación de clusters puede ser interesante
no sólo como herramienta para determinar el agrupamiento correcto de la base de
datos sino también para determinar parámetros del algoritmo de agrupamiento.
Algunos de los métodos de validación descritos en el Capítulo 3 de la
presente memoria, utilizan un índice para determinar el número de clusters óptimo en
una base de datos, que se calcula inmediatamente después de ejecutado el algoritmo
de agrupamiento y se toma el valor k que minimice o maximice dicho índice. En
otros casos, se realiza un remuestreo de los datos y se ejecuta el algoritmo de
agrupamiento sobre los diferentes conjuntos de muestras para determinar cierta
convergencia de los agrupamientos, que se evalúa a su vez a través de un índice o
probabilidad, algunos interesados en determinar pares de objetos que pertenecen a un
mismo cluster en dos particiones diferentes, otros aplican pruebas estadísticas sobre
estas variaciones y otros basan su estrategia en transferencia por predicción (transfer
by prediction).
Los índices de validación fundamentalmente tienen entre sus limitaciones la
suposición de bases de datos con clusters bien separados y compactos, lo que en
general no es cierto. Otras estrategias emplean métodos asociados a algoritmos de
agrupamiento que no siempre descubren la verdadera naturaleza de los datos. A su
vez, en estrategias basadas en estabilidad, específicamente en transfer by prediction,
por lo general es necesario evaluar todas las permutaciones de las etiquetas
resultantes con el algoritmo de agrupamiento lo que trae como consecuencia un coste
computacional alto.
Con el objetivo de solucionar los problemas antes mencionados dirigimos
nuestro trabajo a la obtención de una estrategia de validación de clusters sin
suposiciones acerca de la estructura interna de la base de datos, es decir, utilizable
también en bases de datos con grupos solapados y en presencia de ruido, aplicable
con cualquier algoritmo de agrupamiento y evitando la dependencia en alguna de sus
etapas de la determinación de la correspondencia entre las etiquetas mediante
permutaciones.
Capítulo 5
106
En este capítulo expondremos un método basado en estabilidad para
determinar el número de clusters “natural” en una base de datos, después de haber
sido clasificada con algún método de agrupamiento. Este enfoque lo empleamos
inicialmente con el objetivo de determinar cuál es el nivel en la jerarquía de
agrupamientos de nuestros algoritmos H-Density y DHG, que mejor se adapta a la
distribución de los datos, pero puede ser aplicado a cualquier algoritmo de clustering.
2 Indice σ
La idea de nuestro enfoque sigue la línea del remuestreo y más exactamente de la
estabilidad del clustering basada en transferencia por predicción pues empleamos un
clasificador entrenado sobre una partición de un conjunto de datos para predecir las
etiquetas de otro conjunto de datos. Basamos nuestra metodología sobre medidas de
información como un criterio de la estabilidad de los clusters, modelando la partición
de los datos como un canal de comunicación ruidoso, teniendo en cuenta la relación
que existe entre algunas medidas de información con el problema del
Reconocimiento de Patrones [Pascual, 2008], [Pascual, 2009].
Comenzaremos con algunos conceptos del Reconocimiento de Patrones
relacionados con la teoría de la información, con el objetivo de mostrar las bases
teóricas que constituyen la idea central de nuestro método.
Sea X una variable aleatoria que representa el conjunto de datos en un espacio
n-dimensional, cuya distribución está dada por p(x) y sea Y otra variable aleatoria
que representa las k etiquetas de clase de los objetos del conjunto X, que se distribuye
según p(y), { }kyyy ...,,1∈ .
Un problema de clasificación puede ser modelado como un canal de
comunicación ruidoso [Cover, 1991], donde la distribución de probabilidad de
transmisión del canal se representa por las probabilidades condicionales p(x/y), que
expresan la probabilidad de observar el símbolo x dado que se ha enviado el símbolo
y (Figura 27). El proceso de reconocimiento de patrones se puede representar por un
conjunto W de m posibles mensajes { }mwww ...,,1∈ empleando un mn-código
( )nmC n ,)( = construido por secuencias de n etiquetas yn, cuyos valores de código
están distribuidos según las probabilidades de las etiquetas de clase p(y). Cuando el
remitente envía un mensaje constituido por una secuencia yn, el destinatario ve por el
otro lado del canal la correspondiente secuencia xn. Este último emplea una función
de decodificación WXg n →: para descifrar el mensaje enviado wxg n =)( .
Validación de Clusters
107
Figura 27. Canal de comunicación
En un problema de Reconocimiento de Patrones la función de decodificación
puede representarse por la regla de decisión. Si nosotros empleamos la regla de
decisión de Bayes entonces la función de decodificación sería:
{ } { })()/(maxarg)/(maxarg)(...,,1...,,1
jjkj
jkj
ypyxpxypxgy==
=== (47)
Por otro lado, de acuerdo al teorema de capacidad de un canal [Cover, 1991],
la capacidad de un canal se obtiene según la fórmula:
),(max)(
YXICyp
= (48)
Li (1997) demostró que la información mutua ),( YXI entre la distribución
discreta de datos p(x) y la distribución de clases p(y) en un problema de decisión,
está relacionado con el error de Bayes R del problema de decisión según la siguiente
expresión:
( ) ( )),()(2
1),()(
)1(4
1 2YXIYHRYXIYH
k−≤≤−
−
(49)
donde H(X) y H(Y) son las entropías de Shannon de las variables aleatorias X e Y
respectivamente.
La desigualdad (49) proporciona una cota inferior y superior para el error de
Bayes. Por tanto, si nosotros podemos hacer un estimado de estas medidas de
información para un problema de reconocimiento de patrones dado, podríamos tener
una estimación de estas cotas del error de Bayes.
Nuestro enfoque de estabilidad está basado en una medida de la variabilidad
de transferencia por predicción por medio de medidas de información. La
variabilidad de la predicción transmitirá una variabilidad del error de decisión. Con
nuestro método estimaremos esta variabilidad por medio de la evaluación de la
variación de las medidas de información que aparecen en la fórmula (49) y la regla
de decisión (47).
Sean dos subconjuntos de datos extraídos por procesos estadísticamente
independientes L1 y L2 escogidos de una distribución desconocida representante de
los datos p(x), y sea A un algoritmo de agrupamiento. Para un número de clusters k
Capítulo 5
108
dado, el algoritmo A proporcionará una partición de los conjuntos de datos L1 y L2
representadas por las distribuciones p1(y) y p2(y) respectivamente.
Asumamos que para un número k de clusters la partición de los datos
proporcionada por el algoritmo A sobre la distribución verdadera de los datos se
representa por pk(y). Por tanto, si fijamos Hk(Y) en la expresión (49), la variación
debida a dos soluciones de agrupamiento en la estimación de las cotas del error de
Bayes, se podría evaluar estimando la variación en la información mutua, debido al
uso de dos subconjuntos de datos diferentes en la transferencia por predicción entre
las correspondientes dos soluciones de agrupamiento p1(y) y p2(y).
Para estimar la variabilidad de la transferencia por predicción, necesitamos la
medida de información mutua Ik(X, Y) entre la distribución verdadera de los datos X
y la partición de los datos en k clusters Y, proporcionada por el algoritmo de
agrupamiento.
( ){ }∫ ∑ =
=
X y
xpk ypxypKLEdxyp
xypxypxpYXI )()/(
)(
)/(log)/()(),( )(
(50)
La información mutua entre el conjunto de datos X y la partición en k clusters
proporcionada por Y, se puede interpretar en términos de canales de comunicación
como la tasa de transmisión del canal como hemos dicho antes. La ecuación (50)
también puede interpretarse como el valor esperado de acuerdo a p(x) de la
divergencia de Kullback-Leibler entre la distribución de partición de los datos p(y)
generada por el algoritmo de agrupamiento en k clases y las probabilidades a
posteriori p(y/x) empleadas en la regla de decisión (47).
Para estimar Ik(X, Y) dados los subconjuntos de muestras L1 y L2, asumimos
que el conjunto de datos L1 se usa como un estimador empírico de la distribución
verdadera de los datos )()( 1 xpxp ≈ y la partición obtenida por el algoritmo de
agrupamiento sobre L1 como un estimador para la partición de los datos
)()( 1 ypyp ≈ . La distribución empírica del conjunto de datos L1 que contiene N1
muestras, puede expresarse:
( )∑=
=≈1
111 ,
1)()(
N
i
ixxN
xpxp δ (51)
por lo que al sustituir la ecuación (51) en la ecuación (50) obtenemos:
∑∑=
≈1
1
11
1 )(
)/(log)/(
1),(
N
i y
iik
yp
xypxyp
NYXI
(52)
Validación de Clusters
109
Por otro lado, con el objetivo de obtener un estimado de las probabilidades a
posteriori p(y/x), si nosotros hemos usado el subconjunto de muestras L1 para estimar
la verdadera distribución de probabilidad y la distribución de partición de los datos,
vamos a usar el subconjunto de datos L1 y el etiquetado obtenido como solución por
el algoritmo de agrupamiento como conjunto de entrenamiento y el conjunto de datos
L2 como conjunto de prueba. Por tanto, las probabilidades a posteriori se pueden
estimar empleando el conjunto de entrenamiento L1 y el conjunto de prueba L2 por:
∑=
=k
j
j xyp
xypxyp
12
2
)/(
)/()/( ; { }kyyy ,...,1∈
(53)
siendo
( ) ( )∑= +
=K
i i
ixxd
yxyxyp1
12 ,
1),()/(
εδ
(54)
En la ecuación (54), y1(xi) representa la etiqueta de clase asignada a la
muestra xi, (vecino de x en el conjunto L1), y es una etiqueta arbitraria en L2 y K
denota el número de vecinos de la muestra x empleados para estimar p2(y/x).
Finalmente, la estimación de la información mutua usando dos subconjuntos de
muestras independientes L1 y L2, se expresa por:
∑∑= =
=≈1
1 1 1
1212
1 )(
)/(log)/(
1),(ˆ),(
N
i
k
j j
ij
ijkkyp
xypxyp
NYXIYXI
(55)
Ya que kI varía para diferentes conjuntos de muestras, podemos considerarla
una variable aleatoria, por tanto, por la ley de los grandes números, cuando el
número de mediciones tiende a infinito, el valor esperado de ésta tiende al verdadero
valor. Para un número finito de muestras M, el verdadero valor de esa variable se
concentra alrededor de su media con varianza:
( )( )22 ˆˆkkk IEIE −=σ (56)
Esta varianza representa la variabilidad de la información mutua entre el
conjunto de datos X y la partición Yk para los k clusters generados debido a las
fluctuaciones y diferencias en los datos muestrales empleados. Además, las
variaciones en la información mutua está relacionada con las variaciones en la tasa
de transmisión alcanzable a lo largo del canal de comunicación XY → , es decir, en
la tasa del error de clasificación del problema de Reconocimiento de Patrones según
vimos antes.
Capítulo 5
110
La desviación estándar kσ representará el índice de estabilidad de los k
clusters obtenidos con el algoritmo A. Este índice de estabilidad de los clusters es
una estimación de la variación de la transferencia por predicción entre M pares de
soluciones de agrupamiento. Entonces, para un algoritmo de agrupamiento dado, el
número correcto de clusters k* será escogido como el número de clusters que
minimiza el índice de estabilidad (56), es decir:
kk
k σminarg* = (57)
3 Canal de Difusión en un Problema de Validación de
Clusters
Con el objetivo de dar una solución al problema de la validación de clusters,
siguiendo una estrategia basada en estabilidad, que resuelva algunas de las
limitaciones de otros enfoques como por ejemplo: la necesidad de normalizar la
medida de validación, o de realizar permutaciones de las etiquetas de clase obtenidas
con el agrupamiento, hemos presentado nuestra estrategia basada en estabilidad, en la
que se estima el número natural de grupos mediante el estudio de la variabilidad de la
información mutua entre la distribución de los datos y la distribución de las clases.
A su vez, en nuestra estrategia para estimar la probabilidad a posteriori (53),
es necesario establecer una correspondencia entre las etiquetas obtenidas con el
agrupamiento y las obtenidas con la regla de clasificación supervisada. Una manera
de evitar esto, es considerar el problema de validación de clusters basado en medidas
de estabilidad como un canal de difusión.
Un canal de difusión (broadcast channel), es un canal de comunicación con
un solo remitente y dos o más receptores, como se muestra en la Figura 28. El
problema consiste en encontrar el conjunto de tasas de transmisión correctas
alcanzables entre todas las formas de comunicación posibles.
Figura 28. Canal de difusión
Validación de Clusters
111
Es decir, un canal de difusión consiste en un alfabeto de entrada X, dos
alfabetos de salida Y1, Y2 y una función de probabilidad de transmisión )/,( 21 xyyp .
En un canal de difusión se considera un código (W, m) compuesto por un
conjunto de palabras clave definidas como sucesiones de m valores
{ }m
m xxxX ...,, 21= , extraídas de una variable aleatoria X con distribución de
probabilidad p(x) según una función de codificación mXWx →: . Como se ilustra
en la Figura 28, la codificación de X es arbitrariamente tomada por el transmisor para
enviarlas a los receptores 1 y 2, respectivamente. El remitente transmite una
secuencia de valores mX a través de un canal ruidoso, caracterizado por su
probabilidad de transmisión )/,( 21 xyyp y por el otro lado del canal, los receptores
observan una secuencia transformada { } 2,1,...,, 21 == iyyyY imii
m
i , cuyos valores
corresponden a dos variables aleatorias Y1, Y2, con distribuciones de probabilidad
p(y1), p(y2), respectivamente, de acuerdo a dos funciones decodificadores
( )mmm YXWYg 1111 ,ˆ: → y ( )mmm YXWYg 2222 ,ˆ: → independientes.
En general, podemos expresar las distribuciones marginales por:
∑∈
=22
2111Yy
)x/y,y(p)x/y(p (58)
∑∈
=11
2122Yy
)x/y,y(p)x/y(p (59)
donde
( ) ( )∏=
=m
j
jjj xyypxyyp1
2121 /,/, para mXx∈ , mYy 11 ∈ y mYy 22 ∈ (60)
correspondiente a un canal sin memoria (memoryless channel).
3.1 Estabilidad del agrupamiento como una variación de la tasa de
transmisión de un canal de difusión
Con el objetivo de resolver nuestro problema de validación de clusters establecemos
un modelo empleando un canal de difusión. Supongamos que tenemos un remitente
que emite un mensaje codificado que al pasar por el canal es interpretado por los dos
receptores. En nuestro modelo, el proceso de interpretar los resultados
correspondería con el resultado de la aplicación de un algoritmo de agrupamiento
sobre dos muestras diferentes L1 y L2, extraídas por un proceso estadísticamente
independiente, de una distribución de probabilidad verdadera desconocida p(x), de
una variable aleatoria X que representa los datos codificados. Para cada valor de k, el
algoritmo de agrupamiento proporcionará una solución de los conjuntos de datos L1 y
Capítulo 5
112
L2, en k clusters, representados por las distribuciones ( )1yp k y ( )2yp k ,
respectivamente. De este modo, el resultado del agrupamiento a los dos conjuntos de
datos, representará los mensajes interpretados por los receptores para cada valor de k.
De acuerdo a esa idea, la capacidad C12 del canal común se calcula según la
fórmula (48), es decir, a través de la expresión:
( )( )2112 ;;max YYXIC k
xp= (61)
la cual puede interpretarse como la más alta tasa en bits con la cual la información
puede ser enviada con arbitrariamente baja probabilidad de error para ambos
receptores, es decir, significa la más alta tasa de interpretación correcta del mensaje
común a ambos receptores, donde );;( 21 YYXI k representa la tasa de transmisión
común del canal de difusión y k es el número de valores que pueden tomar las
variables aleatorias Y1 y Y2.
De la misma manera, las más altas tasas en bits C1, C2 con las cuales la
información puede ser enviada con baja probabilidad de error a los receptotes Y1, Y2,
respectivamente, se calculan según las expresiones:
( )( )11 Y;XImaxC k
xp= (62)
( )( )22 Y;XImaxC k
xp= (63)
En nuestro caso, no estamos interesados en estimar la capacidad del canal
sino la variabilidad de la tasa de transmisión común del canal de difusión. Dada una
p(x), para estimar la tasa de transmisión común del canal de difusión, o lo que es lo
mismo, la medida de la información mutua del canal común entre los dos receptores,
empleamos la siguiente expresión:
( ) ( ) ( )212121 ,;;;);;( YYXIYXIYXIYYXI kkkk −+= (64)
Por tanto, para cada valor de k, es necesario estimar las informaciones mutuas
respecto a cada uno de los receptores Y1 y Y2, correspondientes a las soluciones de
los conjuntos de datos L1 y L2, respectivamente, en k clusters, para determinar las
tasas de transmisión para una solución concreta del algoritmo de agrupamiento
( )xyyp /, 21 .
Para esto, empleamos las siguientes expresiones si p(x) es una distribución
continua estimada a través de la distribución empírica (51).
( ) ( ) ( )( )∑∑
∈ ∈
=Xx Yy
k
kkk
yp
x/yplogx/yp
NY;XI
11 1
111
1
(65)
Validación de Clusters
113
( ) ( ) ( )( )∑ ∑
∈ ∈
=Xx Yy
k
kkk
yp
x/yplogx/yp
NY;XI
22 2
222
1
(66)
( ) ( ) ( )( )∑∑ ∑
∈ ∈ ∈
=Xx Yy Yy
k
kkk
y,yp
x/y,yplogx/y,yp
NY,Y;XI
11 22 21
212121
1
(67)
Mientras que si p(x) es una distribución discreta, empleamos las expresiones:
( ) ( ) ( )( )∑∑
∈ ∈
=Xx Yy
k
kkk
yp
xypyxpYXI
11 1
111
/log,;
(68)
( ) ( ) ( )( )∑ ∑
∈ ∈
=Xx Yy
k
kkk
yp
xypyxpYXI
22 2
222
/log,;
(69)
( ) ( ) ( )( )∑∑ ∑
∈ ∈ ∈
=Xx Yy Yy
k
kkk
yyp
xyypyyxpYYXI
11 22 21
212121
,
/,log,,,;
(70)
En todos los casos, las probabilidades del canal de difusión se aproximarán
por probabilidades marginales independientes, es decir:
( ) ( ) ( )xypxypxyyp kkk ///, 2121 ≈ (71)
y las probabilidades marginales ( )x/yp k
1 y ( )x/yp k
2 se estimarán de dos maneras
diferentes. La primera de ellas es considerar probabilidades 0 y 1, o sea:
( ) ∈
=...0
)(1/
coe
Cxvecsixyp
j
j
k , j=1, 2, …, k (72)
O sea, la probabilidad será 1 para la clase del vecino de x y 0 para las
restantes clases.
La segunda variante que empleamos para estimar las probabilidades
marginales está dada en la siguiente expresión:
( ) ( )∑= +
=K
i ij
j
k
yxdxyp
1 ,
1/
ε, j=1, 2, …, k
(73)
donde d(x,yji ) es la distancia de x a su i-ésimo vecino más cercano en el cluster Cj, K
el número de vecinos, k el número de clusters y ε es un número positivo pequeño
para evitar que se anule el denominador.
De este modo, nuestro objetivo será utilizar la estimación de la tasa de
transmisión común del canal para obtener el número natural de clusters, evitando la
necesidad de utilizar un algoritmo de clasificación supervisada y de establecer
correspondencias entre las etiquetas de los dos subconjuntos de datos L1 y L2 como
en [Lange, 2004].
Capítulo 5
114
Como la información mutua común I(X;Y1;Y2) varía para diferentes conjuntos
de muestras, igual que para el índice de estabilidad σ, repetiremos el experimento un
número M de veces con el objetivo de estudiar la variabilidad de la misma. Por tanto,
la desviación típica de la información mutua común, representará el índice de
estabilidad de los clusters obtenidos con el algoritmo de agrupamiento. Es decir, para
un algoritmo de agrupamiento dado, el número natural de clusters se escogerá como
el número de clusters que minimice el índice de estabilidad al que llamaremos σ-BC
(σ-Broadcast Channel) para evitar confusiones con el anterior índice de estabilidad:
kk
k σminarg* = (74)
donde kσ representa la variabilidad de la información mutua común entre el
conjunto de datos X y las particiones kY1 y kY2 para los k clusters generados de las
fluctuaciones en los datos muestrales empleados.
Figura 29. Diagrama de Venn que indica la región ocupada por la información mutua común
I(X;Y1;Y2) del canal de difusión
En el diagrama (Figura 29), toda la región sombreada representa la
información mutua I(X;Y1,Y2), que simboliza la información mutua entre la variable
aleatoria X y la variable aleatoria (Y1,Y2). Las flechas indican las restantes
informaciones mutuas presentes en la fórmula (64).
3.2 Selección del modelo de agrupamiento
De acuerdo a nuestro modelo para estimar el número de clusters, el mejor
agrupamiento para las diferentes soluciones de agrupamiento obtenidas por un
algoritmo de clustering estará determinado por la mínima varianza de la información
mutua común (64). Cada estrategia de agrupamiento indica un valor para el índice de
Validación de Clusters
115
validación σ-BC, que significa el nivel más estable de todos los considerados; pero a
su vez, algunos algoritmos de agrupamiento no son capaces de descubrir la verdadera
división presente en los datos, por lo que el valor del índice σ-BC nos puede llevar a
interpretaciones incorrectas si no conocemos si el algoritmo de agrupamiento
descubre realmente la distribución de clases de los datos.
Por tanto, será conveniente resolver el problema de la selección del algoritmo
de agrupamiento más adecuado. Una posibilidad para escoger el algoritmo que mejor
divide en grupos los datos, será tomar el agrupamiento de mayor información mutua
común. Es decir, para cada algoritmo de clustering, entre los diferentes niveles de
agrupamiento considerados, existe uno, tal que la varianza de la información mutua
común es mínima, el cual representará el nivel más estable producido por ese
algoritmo de agrupamiento, o lo que es lo mismo, el nivel que mejor interpreta la
estructura interna de los datos de acuerdo al algoritmo de agrupamiento en cuestión,
sin embargo, necesitamos obtener información adicional: de entre todos esos
resultados (uno por cada algoritmo de agrupamiento) cuál será a su vez, el mejor.
Supongamos que tenemos s algoritmos de agrupamiento A1, A2, …, As, y que
k1, k2, …, ks representan el número de clusters seleccionado por el índice σ-BC para
cada algoritmo, respectivamente. En términos de la variabilidad de la información
mutua común significa que la varianza de la información mutua común en el nivel ki
es la menor de todas las varianzas en los restantes niveles correspondientes a las
soluciones de agrupamiento del algoritmo Ai.
Por otro lado, de entre todas las soluciones indicadas, al menos uno será de
varianza mínima, o sea, existe
)(minarg ik
j kki
σ= (75)
En el nivel correspondiente al valor kj, estimamos el valor esperado de la
información mutua común, que, para un número de experimentos dado, se toma
como estimado el promedio de los valores de la información mutua común en las M
realizaciones del experimento para cada algoritmo de agrupamiento, y consideramos
como el mejor agrupamiento aquel que tenga un estimado del valor esperado de la
información mutua común máximo.
Más claramente, el resultado del algoritmo A* se considera el mejor
agrupamiento de los datos si
( )];;[maxarg 211
* YYXIEA j
i
k
Asi≤≤
= (76)
siendo kj el número de clusters seleccionado según la expresión (75) y Ai (i = 1, … s)
cada uno de los algoritmos de agrupamiento.
Capítulo 5
116
4 Resultados Experimentales
Con el objetivo de mostrar la efectividad de los dos métodos propuestos, realizamos
los experimentos con tres tipos diferentes de bases de datos. En el primer grupo
consideramos las bases de datos constituidas por modos gausianos G4 de 4 modos
con poco solapamiento, G6 formada por 6 modos gausianos, 4 de ellos muy
solapados y G6-II también con seis modos gausianos con cierto nivel de
solapamiento y con dos de los modos completamente solapados con la misma media
y diferentes matrices de covarianzas. Éstas han sido mostradas en la Figura 7 del
capítulo 4.
En el segundo grupo tomamos tres bases de datos cuyos clusters tienen
diferentes formas y tamaño e incluso con puntos ruidosos. Éstas son 3AC formada
por 3 anillos concéntricos y 2SA constituida por dos semianillos (Figura 8) y DS1
(Figura 9a). En el tercer grupo consideramos las bases de datos reales House e Iris.
Con respecto al método de agrupamiento utilizamos cuatro algoritmos de
agrupamiento: k-Means, EM, H-Density y DHG. Estos algoritmos responden a tres
modelos de agrupamiento diferentes, k-Means pertenece al grupo de los algoritmos
por partición que desarrolla una estrategia basada en centroides por lo que obtiene
grupos compactos alrededor de la media, EM también es un algoritmo por partición
pero basado en el enfoque probabilístico y, H-Density y DHG constituyen un
enfoque híbrido entre dos estrategias: jerárquica y basada en densidad. De este modo
evaluaremos nuestra propuesta para la validación de los clusters con tres modelos
diferentes, con el objetivo de validar la aplicación de la misma independientemente
del modelo de agrupamiento que se tome.
Para cada una de las bases de datos, dividimos aleatoriamente en dos
subconjuntos de igual tamaño L1 y L2. Para k = 2, …, 10 realizamos el agrupamiento
de los datos de ambos subconjuntos con los tres algoritmos de clustering, y se evalúa
el índice de estabilidad (índice σ) sobre 10 realizaciones diferentes de L1 y L2.
Invirtiendo el papel de L1 y L2 en la estimación de la información mutua, nos
proporciona un estimado del índice de estabilidad sobre M = 20 realizaciones.
4.1 Resultados de la aplicación del índice σ
Vamos a analizar en primer lugar el comportamiento del índice σ. Cabe mencionar
que en el caso del algoritmo H-Density, como el resultado depende del parámetro R
(radio de la vecindad de cada punto de la base de datos), para algunas bases de datos
el valor máximo de k no es 10, sino un valor menor, debido a que no siempre se
puede garantizar que en el primer nivel de la jerarquía (resultado de la primera etapa)
Validación de Clusters
117
existan 10 clusters o más. Por ejemplo, en la Tabla 4 la base G4. Los números en
negrita indican el valor óptimo de acuerdo a la estrategia explicada.
Bases de datos sintéticas
En esta sección se muestran los resultados de la aplicación del índice σ sobre los
resultados del agrupamiento de las bases de datos sintéticas.
#
Clusters G4 G6 G6-II 3AC 2SA DS1
2 0,00944 0,027000 0,02400 0,0014 0,00001 0,217
3 0,01310 0,000080 0,01000 0,0011 0,02400 0,013
4 0,00004 0,002000 0,00006 0,0547 0,02300 0,023
5 0,01608 0,003000 0,00003 0,0356 0,00900 0,023
6 0,01945 0,000008 0,0210 0,002
7 0,01760 0,0332 0,013
8 0,09400 0,0249 0,042
9 0,015
10 0,015
Tabla 4. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo de agrupamiento H-Density.
En la Tabla 4 mostramos los valores del índice de estabilidad propuesto para
las bases de datos sintéticas, empleando el algoritmo H-Density. Observe que el
valor mínimo del índice coincide con el número correcto de clusters presentes en las
bases de datos de las Figuras 7, 8 y 9 respectivamente, excepto en el caso de la base
de datos G6-II, en la que hay 6 clusters mientras que el índice indica que 5 es el
verdadero número de clusters, debido a que el algoritmo H-Density por la forma en
que agrupa, no es capaz de separar los dos modos concéntricos.
Capítulo 5
118
Figura 30. Resultados del algoritmo H-Density en el nivel correspondiente al valor determinado
por el índice σ. Arriba: a) G4, b) G6, c) G6-II. Abajo: d) 3AC, e) 2SA, f) DS1.
Para cada base de datos sintética, el resultado que se obtiene en el nivel de la
jerarquía indicado por el índice de estabilidad σ, se muestra en la Figura 30. Se puede
observar que en el caso de la base de datos G6-II, los dos modos concéntricos se
funden en uno.
#
Clusters G4 G6 G6-II 3AC 2SA DS1
2 0,010000 0,000020 0,00430 0,0026 0,0130 0,03000
3 0,016000 0,000008 0,00370 0,0017 0,0057 0,00800
4 0,000001 0,000020 0,00780 0,0029 0,0003 0,00140
5 0,012000 0,002000 0,00003 0,0045 0,0027 0,00001
6 0,081000 0,000009 0,00029 0,0480 0,0014 0,00180
7 0,100000 0,00500 0,0065 0,0035 0,0049 0,00003
8 0,037000 0,02600 0,01700 0,0060 0,015 0,00004
9 0,043000 0,03400 0,04000 0,0070 0,0047 0,00110
10 0,049000 0,01000 0,01500 0,0040 0,0059 0,00410
Tabla 5. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo de agrupamiento EM.
En la Tabla 5, aparecen los resultados de evaluar el índice σ sobre las
diferentes bases de datos sintéticas cuando empleamos el algoritmo de agrupamiento
EM. Según se puede ver, se obtuvo el número correcto de clusters para la base de
datos G4, en el caso de G6, el número correcto de clusters que indica es 3, o sea, los
tres grupos bien separados, sin embargo, nótese que la diferencia entre el valor del
Validación de Clusters
119
índice en los casos de tres y seis clases es insignificante, por lo que garantiza que el
nivel de seis clases podría ser seleccionado también.
En la Figura 31 mostramos el nivel de cuatro clases en el caso de la base de
datos G4, y para la base de datos G6, los niveles de tres y seis clases que son los dos
resultados destacados por nuestro índice de estabilidad.
Figura 31. Resultados del algoritmo EM en el nivel correspondiente al valor determinado por el
índice σ: a) G4, b) G6 (tres clases), c) G6 (seis clases).
Algo similar ocurre con la base de datos G6-II, el índice identifica el nivel de
5 clases como el óptimo, pero también el nivel de seis clases es significativo. Ambos
resultados se muestran en la Figura 32.
Figura 32. Resultados del algoritmo EM sobre la base de datos G6-II, en el nivel
correspondiente al valor determinado por el índice σ: a) 5 clases, b) seis clases.
El modelo de mixturas gausianas no puede descubrir los clusters verdaderos
para el resto de las bases de datos (ver Capítulo 4), por lo que el índice de estabilidad
no determina el verdadero número de clusters. Por ejemplo, en la Figura 33,
mostramos dos de los resultados obtenidos por el algoritmo EM en el nivel de seis
clases. Como se aprecia, no existe estabilidad en el agrupamiento, además de que no
se obtiene la división natural de los datos en grupos.
Capítulo 5
120
Figura 33. Resultados del algoritmo EM sobre la base de datos DS1 en el nivel de seis clases.
En la Figura 34 mostramos el nivel escogido por nuestro índice de estabilidad
cuando aplicamos el algoritmo EM a la base de datos DS1, como mencionamos
antes, esta estrategia de agrupamiento no es capaz de descubrir las figuras presentes
en la base de datos DS1.
Figura 34. Resultado más estable del índice σ empleando el algoritmo EM sobre la base de datos
DS1.
En el caso de la base de datos 3AC se obtuvo el nivel de 3 clases aunque el
algoritmo EM no identifica los tres anillos (Figura 35).
Figura 35. Nivel seleccionado por el índice σ cuando se aplica el algoritmo EM sobre 3AC.
Validación de Clusters
121
#
Clusters G4 G6 G6-II 3AC 2SA DS1
2 0,0000026 0,00003 0,0170 0,00009 0,00004 0,0000005
3 0,0131724 0,00012 0,0044 0,00017 0,00260 0,0001000
4 0,0000023 0,00570 0,0042 0,00006 0,00120 0,0015000
5 0,0026520 0,01330 0,0001 0,00020 0,0011 0,0000100
6 0,0065380 0,00160 0,0066 0,00090 0,0008 0,0000040
7 0,0032110 0,00100 0,0160 0,00200 0,0036 0,0010000
8 0,0160700 0,01370 0,0045 0,00100 0,0034 0,0010000
9 0,0095200 0,003800 0,0120 0,00400 0,0047 0,0005000
10 0,0152000 0,08600 0,0090 0,00100 0,0041 0,0006000
Tabla 6. Índice de estabilidad σ para las bases de datos sintéticas con el algoritmo de agrupamiento k-Means.
Con relación al algoritmo de agrupamiento k-Means (Tabla 6), sólo en el caso
de la base de datos G4, se obtiene el número correcto de clusters, y sobre la base G6-
II que de acuerdo a su estrategia se puede considerar el nivel de 5 clases como el
óptimo. En la Figura 36 mostramos ambos resultados.
Figura 36. Resultados del algoritmo k-Means en el nivel correspondiente al valor determinado
por el índice σ: a) G4, b) G6-II.
Para las otras bases de datos, el fallo se debe fundamentalmente a que este
algoritmo de agrupamiento no etiqueta correctamente los puntos si los clusters no
son globulares, y también por el problema de la inicialización, es decir, que se
obtienen agrupamientos diferentes con diferentes inicializaciones del k-Means. Por
ejemplo, la base de datos G6, en el nivel de seis clases, obtiene la mayor parte de las
veces el resultado de la Figura 37a, pero también, en algunas ocasiones divide en
grupos como aparecen en las gráficas de las Figuras 37b y 37c. Algo similar ocurre
con el nivel de tres clases, que algunos puntos se ubican en clusters diferentes, por lo
que encuentra la mayor estabilidad en el nivel de dos clases.
Capítulo 5
122
Figura 37. Resultados del algoritmo k-Means sobre la base de datos G6 en el nivel de seis clases:
a) más frecuente, b) y c) menos frecuente.
En la Figura 38, mostramos los gráficos del nivel seleccionado por el índice σ
para las restantes bases de datos sintéticas. En todos los casos se nota la tendencia del
algoritmo k-Means a crear clusters globulares, en el caso de la base de datos 2SA el
índice detecta el nivel de dos clases como el más importante, pero k-Means no puede
obtener los dos semianillos.
Figura 38. Resultados del algoritmo k-Means en el nivel correspondiente al valor determinado
por el índice σ sobre las base de datos: a) 3AC, b) 2SA, c) DS1.
En la Figura 39 hemos representado la división en grupos de la base de datos
House, en el nivel determinado por nuestra estrategia de validación de clusters, para
cada uno de los algoritmos de agrupamiento. Según se vió en el Capítulo 4, el
algoritmo H-Density es el único de los estudiados que divide correctamente la base
de datos House en 5 clases, por este motivo, el índice σ determina el nivel de 5 clases
como el adecuado sólo en el caso de la aplicación de H-Density (Figura 39a). Las
estrategias EM y k-Means, determinan los niveles de tres (Figura 39b) y dos clases
(Figura 39c), respectivamente, como la división natural de esa base de datos.
Validación de Clusters
123
Figura 39. Nivel detectado por el índice σ sobre la base de datos House, para cada uno de los
algoritmos de agrupamiento empleados: a) H-Density, b) EM, c) k-Means.
Bases de datos reales
En la Tabla 7, hemos resumido el resultado de nuestro índice sobre las bases de datos
reales House e Iris, con los tres algoritmos de agrupamiento. Como se puede
observar, cuando agrupamos con el algoritmo H-Density nuestra estrategia para
determinar el número de clusters correcto acierta incluso en el caso de la base de
datos Iris, que como se sabe está formada por tres clases pero dos de ellas muy
solapadas, por lo que la mayoría de los algoritmos de agrupamiento tienen
dificultades para encontrar las tres clases, pero nótese que la diferencia con el nivel
de dos clases es muy pequeña debido a que en el nivel de dos clases la estabilidad es
alta. Los valores del índice σ con los otros dos algoritmos de clustering están
influenciados por el hecho de que esos dos algoritmos no descubren el agrupamiento
verdadero para esas dos bases de datos. Con la base de datos Iris es lógico que se
obtenga el nivel de dos clases como el verdadero.
House Iris
# Clusters
H-Density
EM K-Means H-
Density EM
K-Means
2 0,01800 0,000010 0,000002 0,0019 0,0042 0,0016
3 0,01700 0,000006 0,000200 0,0018 0,0470 0,0388
4 0,00390 0,000020 0,000020 0,0054 0,0150 0,0513
5 0,00003 0,000100 0,000700 0,1918 0,0090 0,0180
6 0,000400 0,023000 0,1827 0,0200 0,0327
7 0,002100 0,014000 0,1599 0,0400 0,0108
8 0,000800 0,007000 0,2385 0,0100 0,0083
9 0,008000 0,021000 0,3062 0,0100 0,0085
0,015000 0,024000
Tabla 7. Índice de estabilidad σ para las bases de datos reales.
Como un resultado importante podemos concluir, que cuando empleamos un
modelo de agrupamiento adecuado, en general se obtiene el número “natural” de
clusters con el índice de estabilidad σ.
Capítulo 5
124
4.2 Comparación con otras estrategias de validación de clusters
En esta sección describimos los experimentos realizados para comparar nuestra
estrategia de validación de clusters con otros seis métodos explicados en el Capítulo
3. Empleamos las mismas bases de datos sintéticas y reales introducidas en este
capítulo, y los algoritmos de agrupamiento k-Means, EM y H-Density.
Tomamos para nuestra comparativa dos criterios basados en estabilidad. El
primero de ellos es el mostrado en [Ben-Hur, 2002], que utiliza una medida de
similaridad entre dos agrupamientos así como su distribución de probabilidades, y
considera como el número óptimo de clusters, el valor de k para el cual la
distribución está cerca de 1, o lo que es lo mismo, tal que P(sk > η), lo que revela que
ambas particiones son similares. Seleccionamos M = 100 subconjuntos de muestras
con una razón muestral f = 0.8, la medida de similaridad coseno y el umbral η = 0.9.
Como segundo enfoque basado en estabilidad, consideramos el de Tibshirani
(2005). Dividimos M = 50 veces la base de datos en dos subconjuntos disjuntos,
sobre los que se calcula la fuerza de la predicción (ps) para cada valor de k
considerado, y se selecciona el más alto valor de k tal que ps > η con η = 0.8.
El índice (FB) de Fischer y Buhmann (2003), fue otro de los métodos
escogidos para realizar la comparativa. Este calcula una probabilidad empírica de la
distribución de asignación de los objetos a los clusters, basado en un método de
remuestreo (bagging). Nosotros hicimos una adaptación para calcular el índice de
validación, realizamos 10 divisiones de los datos en dos subgrupos disjuntos y
calculamos las probabilidades de asignación de los objetos a las clases de la misma
manera que para nuestro índice σ, es decir, según la fórmula (53). Comparamos
además nuestro método con el índice (DB) de Davies y Bouldin (1979), y los índices
SD y S_Dbw de Halkidi (2002), descritos en el Capítulo 3 de esta memoria de tesis.
Para comentar los resultados relativos a las dos estrategias basadas en
estabilidad (Ben-Hur y Tibshirani), debido a que se escoge el número de clusters no
por la evaluación de un índice del que se puede escoger el valor máximo o mínimo,
mostramos en las Tablas 8 y 9 los valores de la P(sk > η) obtenidos en los
experimentos en el método de Ben-Hur (2002), y los valores de prediction strengh en
el método de Tibshirani (2005) respectivamente, empleando el algoritmo H-Density
que agrupa correctamente todas las bases de datos mencionadas en este capítulo.
Validación de Clusters
125
#
Clusters 3AC G4 G6 G6-II DS1 House Iris 2SA
2 1 0,74 0,47 0,77 0,73 0,31 1,00 1
3 1 0,57 1 0,79 0,65 0,27 0,98 0,37
4 0,62 0,89 0,6 0,33 0,24 0,44 0,98 0,16
5 0,04 0,4 0,47 0,37 0,79 0,99 0,18
6 0,06 1 0,79 0,78 1,00
7 0,15 0,52
8 0,07 0,29
9 0,16
10 0,05
Tabla 8. Resultado del algoritmo de Ben-Hur (2002) para todas las bases de datos usando H-Density.
Como se puede apreciar en la Tabla 8, en algunos casos, tenemos dudas
acerca de cuál nivel de agrupamiento escoger como óptimo. Por ejemplo, sobre la
base de datos G6, se alcanza la máxima probabilidad y hay un salto significativo
entre los niveles de tres y seis clases y los niveles aledaños. Lo mismo ocurre con la
base de datos G6-II con los niveles de 3 y 6 clases. Ambas, como ya hemos
comentado antes, por tener un alto grado de solapamiento son difíciles de tratar.
Cuando analizamos la base de datos 3AC escogemos el nivel de tres clases como
óptimo por tener probabilidad máxima y por la existencia de un salto con relación al
nivel de cuatro clases. Similarmente escogemos el seis como número de clusters
“natural” para la base DS1, por tener la más alta probabilidad, aunque esa
probabilidad no está cerca de 1, lo que demuestra cierta dispersión en la distribución
de probabilidades de las similaridades. La desventaja de este método está en la duda
que provoca a la hora de escoger el verdadero número de clusters ya que puede
aparecer más de una posible solución.
En la Tabla 9, reflejamos los valores de ps del método de Tibshirani (2005), a
partir de este valor la estrategia indica como óptimo valor del número de clusters el
mayor valor de k tal que ps supera el umbral especificado. Según se puede
comprobar, seleccionamos el nivel de cinco clases para la base de datos G6-II,
resultado que consideramos correcto teniendo en cuenta que el algoritmo H-Density
no es capaz de descubrir los 6 modos, sino que une los dos modos concéntricos. En
el caso de la base de datos G6, escogemos el nivel de tres clases por ser el único
valor que supera el umbral especificado, pero nótese que el siguiente valor máximo
se obtiene con seis clases y si el umbral fuese 0.8, entonces el nivel óptimo sería seis
que es el correcto. Para las bases de datos 3AC y DS1, no se puede determinar el
número de clusters porque los valores de ps son todos pequeños.
Capítulo 5
126
La desventaja de este método es que en su estrategia de transferencia por
predicción emplea un algoritmo de clasificación supervisada basado en centroides,
por lo que la estabilidad de la clasificación depende de la posición de esos centroides,
luego en el caso de la base de datos 3AC, por ejemplo, los tres anillos tienen el
mismo centroide, lo que influye en la imposibilidad de poder determinar el número
de clusters correctamente. Similarmente para las bases DS1 y DS2.
#
Clusters 3AC G4 G6 G6-II DS1 House Iris 2SA
2 0,48 0,82 0,76 0,71 0,8 0,34 0,47 0,66
3 0,25 0,70 0,99 0,77 0,52 0,28 0,29 0,49
4 0,3 0,95 0,6 0,89 0,48 0,29 0,22 0,45
5 0,28 0,59 0,49 0,94 0,48 0,38 0,23 0,44
6 0,27 0,84 0,48
7 0,28 0,43
8 0,31 0,38
9 0,33
10 0,36
Tabla 9. Resultado del algoritmo de Tibshirani (2005) para todas las bases de datos usando H-Density.
En la Tabla 10, hacemos un resumen del valor de k estimado por cada uno de
los enfoques utilizados en nuestra comparativa, empleando el algoritmo H-Density
sobre todas las bases de datos mencionadas. El algoritmo Ben-Hur detecta bien el
agrupamiento correcto en las bases de datos 3AC, G4, DS1, House y 2SA. Como
comentamos antes, con las bases de datos G6 y G6-II, tenemos duda acerca del
número de clusters presentes en esas bases de datos. El método Tibshi, solo para las
bases de datos G4 y G6-II es capaz de dar la solución correcta, pues en los otros
casos la prediction strengh no supera el umbral especificado o se obtiene un
resultado erróneo.
Validación de Clusters
127
Estrategia 3AC G4 G6 G6-II DS1 House Iris 2SA
σ 3 4 6 5 6 5 3 2
Ben-Hur 3 4 3 / 6 3 / 6 6 5 - 2
Tibshi - 4 3 5 - - 2 -
FB 2 / 3 4 3 3 6 5 2 2
DB 10 3 3 4 2 2 2 8
SD 9 3 2 3 2 2 2 5
S_Dbw - 4 3 5 5 2 8
Real 3 4 6 6 6 5 3 2
Tabla 10. Comparación de las diferentes estrategias para todas las bases de datos usando H-Density.
El índice FB determina bien el número de clusters de las bases de datos G4,
DS1, House y 2SA. En el caso de 3AC, alcanza el valor máximo 1 tanto en el nivel
de dos clases como en el nivel de 3 clases por lo que en ese caso no podemos decidir
cual es el mejor. Falla en el caso de las bases G4 y G6-II, producto del solapamiento
existente.
Los tres índices restantes tienen muy bajas prestaciones, porque desarrollan
una estrategia bajo la suposición de clusters bien separados y compactos, por lo que
en bases de datos con solapamiento y ruido no pueden determinar el número correcto
de clusters.
Nuestro índice pudo determinar el número verdadero de clusters existentes en
las bases de datos, excepto con G6-II, porque el algoritmo H-Density no puede
separar los modos concéntricos.
Estrategia
3AC G4 G6 G6-II DS1 House Iris 2SA
σ 3 4 3 5 5 3 2 4
Ben-Hur 7 4 7 5 5 / 6 8 2 4
Tibshi 2 4 2 5 2 2 2 4
FB 7 4 4 5 8 2 2 4
DB 7 3 2 5 2 2 2 8
SD 7 4 5 5 2 3 2 6
S_Dbw 10 4 6 5 10 7 2 9
Real 3 4 6 6 6 5 3 2
Tabla 11. Comparación de las diferentes estrategias para todas las bases de datos usando EM.
Con relación al algoritmo EM (Tabla 11), todos los índices proponen que el
nivel de 5 clases es el mejor agrupamiento para G6-II, y en el caso de G4, sólo el
Capítulo 5
128
índice DB no estima el verdadero valor de k. Concerniente a la base de datos G6,
para varios valores de k se obtiene la probabilidad máxima, sin embargo, según se
indica en [Ben-Hur, 2002], debemos escoger como solución de agrupamiento el nivel
de 7 clases. Sobre las bases de datos restantes el resultado está condicionado por el
hecho de que el EM no descubre las clases presentes.
Estrategia
3AC G4 G6 G6-II DS1 House Iris 2SA
σ 4 4 2 5 2 2 2 2
Ben-Hur 3 4 2 3 3 / 5 2 /4 /5 2 2
Tibshi 3 4 2 3 2 2 2 2
FB 7 4 2 3 2 2 2 2
DB 8 4 2 4 2 2 2 6
SD 5 3 2 4 2 5 2 4
S_Dbw 2 5 7 5 10 9 2 10
Real 3 4 6 6 6 5 3 2
Tabla 12. Comparación de las diferentes estrategias para todas las bases de datos usando k-Means.
Similarmente se puede observar en la Tabla 12 que todos los índices dan un
resultado erróneo cuando se emplea k-Means, excepto sobre la base de datos G4,
debido a las características del algoritmo k-Means: funciona bien para clusters
globulares, sus resultados no son correctos si los puntos están más cerca de la media
de su grupo que de la de otro y tiene problemas con diferentes inicializaciones.
4.3 Resultados de la aplicación del índice σ-BC para seleccionar el
número k de clusters
En este epígrafe comentamos los resultados obtenidos al aplicar nuestro índice de
validación σ-BC sobre los algoritmos DHG, EM y k-Means. Al igual que en el caso
del algoritmo H-Density, el resultado del algoritmo DHG depende del valor de los
parámetros y en algunos casos se obtienen menos de 10 clusters en la primera etapa,
por tanto en la parte jerárquica hay menos de 10 niveles. Los valores en negrita
indican el valor óptimo del índice.
Los experimentos se realizaron sobre las mismas bases sintéticas empleadas
para evaluar el índice σ y sobre un conjunto de bases de datos reales tomadas de UCI
(ver Anexo 1) además de la base de datos House.
Debido a la mejor operabilidad del algoritmo DHG en cuanto al uso de sus
parámetros, mostramos los resultados obtenidos con el mismo para estudiar nuestra
Validación de Clusters
129
estrategia de validación de clusters dada por el índice de estabilidad σ-BC, en lugar
del algoritmo H-Density, pero para este último los resultados son similares.
Bases de datos sintéticas
En esta sección se muestran los resultados obtenidos sobre las bases de datos
sintéticas, primero estimando las probabilidades marginales según la fórmula (72) y
después de acuerdo a la fórmula (73) con uno y tres vecinos, respectivamente.
#
Clases 2SA 3AC-II G4 G6 G6-II DS1
2 0,00002 0,11002900 0,08227 0,032366 0,017927 0,0478
3 0,01119 0,00000006 0,03901 0,000005 0,009303 0,0363
4 0,03009 0,00367819 0,00004 0,029385 0,010506 0,0032
5 0,01204 0,01653010 0,020091 0,000017 0,0235
6 0,00506 0,01806860 0,000310 0,0029
7 0,02153270 0,0035
8 0,03007660 0,0065
9 0,03193380 0,0111
10 0,02257500 0,0158
Tabla 13. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento DHG, según las probabilidades marginales (72).
En la Tabla 13 se muestran los valores del índice de estabilidad propuesto
según las probabilidades (72) para las bases de datos sintéticas, empleando el
algoritmo de agrupamiento DHG. Se observa que el valor mínimo del índice coincide
con el número correcto de clusters para todas las bases de datos (Figuras 7, 8 y 9),
excepto G6-II debido a que el algoritmo DHG no puede separar los dos modos
concéntricos y en el caso de G6 el nivel seleccionado es el tercero, pero nótese que
también el nivel de seis clases se considera importante.
Capítulo 5
130
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,0178 0,0221 0,06600 0,002843 0,03912 0,1183
3 0,0457 0,0458 0,04109 0,000010 0,03827 0,0212
4 0,0216 0,0239 0,00004 0,000595 0,00031 0,0206
5 0,0173 0,0158 0,00006 0,000233 0,00006 0,0005
6 0,0116 0,0761 0,00054 0,000370 0,00362 0,0108
7 0,0110 0,0066 0,00063 0,001691 0,00150 0,0070
8 0,0098 0,0018 0,00067 0,001186 0,00259 0,0007
9 0,0090 0,0132 0,00054 0,002427 0,00171 0,0110
10 0,0040 0,0187 0,00109 0,001717 0,00161 0,0129
Tabla 14. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento EM, según las probabilidades marginales (72).
En la Tabla 14 se observan los resultados del índice de estabilidad sobre las
bases de datos sintéticas cuando empleamos el algoritmo EM. En el caso de las bases
de datos G4 y G6-II se obtuvo el resultado correcto si se tiene en cuenta que los dos
modos concéntricos de G6-II son difíciles de separar. Para la base de datos G6 el
nivel de tres clases es el que se considera correcto, o sea, los tres grupos bien
separados.
Para el resto de las bases de datos el índice no determina el número correcto
de clusters debido a que el algoritmo EM no es capaz de detectar los grupos naturales
del conjunto de datos (Capítulo 4).
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,0010 0,0354 0,00010 0,000004 0,000107 0,00003
3 0,0098 0,0266 0,00006 0,000036 0,000054 0,00028
4 0,0066 0,0145 0,00003 0,009435 0,000118 0,00092
5 0,0145 0,0050 0,00320 0,023286 0,000044 0,00032
6 0,0148 0,0322 0,00254 0,067369 0,000949 0,04618
7 0,0232 0,0277 0,00628 0,028484 0,003046 0,05885
8 0,0227 0,0289 0,00720 0,032115 0,003719 0,00082
9 0,0157 0,0260 0,00715 0,002480 0,003856 0,01672
10 0,0142 0,0328 0,00848 0,003019 0,008181 0,04110
Tabla 15. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento k-Means, según las probabilidades marginales (72).
Al aplicar el índice de estabilidad a los resultados del algoritmo k-Means
(Tabla 15), sólo en los casos de G4 y G6-II es detectado el verdadero número de
Validación de Clusters
131
grupos, si tenemos en cuenta que esta estrategia no puede separar los dos modos
concéntricos en el caso de G6-II. Con relación a la base de datos G6, aparece el nivel
de dos clases como el más importante pero también el nivel de tres clases se puede
tener en cuenta. En el nivel de seis clases el índice no alcanza el valor mínimo
porque el algoritmo k-Means no es estable para diferentes inicializaciones.
Con las otras bases de datos el índice no detecta el número de clusters
verdadero, debido a que el algoritmo k-Means no puede descubrir esos clusters de
formas irregulares pues su tendencia es de formar grupos globulares. En el caso de la
base de datos 2SA el índice selecciona como nivel más importante el de dos clases,
aunque el agrupamiento obtenido con el algoritmo k-Means no es el correcto.
Los resultados que se muestran en las Tablas 16, 17 y 18 son los valores del
índice σ-BC estimando las probabilidades marginales según la fórmula (73) y
tomando un solo vecino por clase.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,00003 0,0292218 0,030568 0,050456 0,02412 0,0451
3 0,00067 0,0000006 0,009489 0,000003 0,03033 0,0588
4 0,00147 0,0008854 0,000008 0,003608 0,00918 0,0105
5 0,00058 0,0027876 0,007332 0,00003 0,0093
6 0,00125 0,0025343 0,000013 0,0029
7 0,0028859 0,0128
8 0,0042575 0,0126
9 0,0048507 0,0116
10 0,0035754 0,0126
Tabla 16. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento DHG, según las probabilidades (73) y un vecino por clase.
Se puede observar en la Tabla 16 que los resultados obtenidos empleando la
fórmula (73) para estimar las probabilidades marginales con el algoritmo DHG, son
muy similares al caso anterior, o sea, la estrategia es capaz de determinar el número
correcto de clusters en todos los casos, aunque en el caso de G6, se prioriza el nivel
de tres clases.
Cuando aplicamos el algoritmo EM (Tabla 17), se observa un
comportamiento similar, o sea, sobre las bases de datos G4, G6 y G6-II se puede
considerar el resultado como correcto y en el resto de los casos, debido a que el
algoritmo EM no es capaz de dividir correctamente esas bases de datos, el valor del
índice de estabilidad no es el verdadero número de clusters, además no hay mucha
Capítulo 5
132
variación en cuanto al nivel seleccionado con la primera estrategia para estimar las
probabilidades marginales.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,0025 0,025532 0,058408 0,000291 0,011425 0,0489
3 0,0022 0,009303 0,017643 0,000002 0,014572 0,0099
4 0,0014 0,009856 0,000004 0,000014 0,000017 0,0078
5 0,0002 0,002219 0,019671 0,000010 0,000006 0,0001
6 0,0003 0,004071 0,017706 0,000032 0,000126 0,0023
7 0,0001 0,000029 0,012119 0,000392 0,000394 0,0018
8 0,0002 0,000006 0,012392 0,000381 0,000941 0,0001
9 0,0002 0,000256 0,017918 0,000712 0,004965 0,0040
10 0,0002 0,003475 0,042688 0,000730 0,005664 0,0041
Tabla 17. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento EM, según las probabilidades (73) y un vecino por clase.
Con relación al algoritmo k-Means (Tabla 18), al aplicar el índice σ-BC y la
fórmula (73) tomando sólo un vecino por clase para cada muestra, no se obtuvo el
resultado correcto con ninguna de las bases de datos aunque en los casos de G4, G6 y
G6-II el segundo valor mínimo del índice de estabilidad es el correcto. Esto se debe
al problema de la inicialización del algoritmo k-Means, que genera diferentes
agrupamientos para diferentes inicializaciones, como consecuencia se origina una
inestabilidad de las soluciones de agrupamiento que trae como resultado la selección
del nivel de dos clases (sobre G4 y G6) y el de tres clases (sobre G6-II) como el más
estable. Las otras tres bases de datos sus resultados están condicionados al resultado
erróneo del etiquetado con el algoritmo k-Means.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,0005 0,0265 0,000002 0,000001 0,000084 0,000002
3 0,0002 0,0061 0,000018 0,000002 0,000004 0,000035
4 0,0001 0,0017 0,000012 0,007986 0,000006 0,000144
5 0,0007 0,0012 0,000206 0,015365 0,000006 0,000061
6 0,0013 0,0035 0,001523 0,005925 0,000257 0,013117
7 0,0006 0,0019 0,001286 0,006300 0,000429 0,016868
8 0,0002 0,0017 0,001554 0,000232 0,000205 0,000100
9 0,0002 0,0005 0,002021 0,000766 0,000847 0,003226
10 0,0003 0,0007 0,001365 0,000104 0,001126 0,008953
Tabla 18. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento k-Means, según las probabilidades (73) y un vecino por clase.
Validación de Clusters
133
En la tercera prueba que efectuamos para evaluar el índice propuesto,
empleamos la fórmula (73) para estimar las probabilidades marginales tomando tres
vecinos por clase para cada muestra.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,00001 0,0211772 0,026191 0,045675 0,02082 0,0736
3 0,00048 0,0000002 0,007729 0,000001 0,02552 0,0275
4 0,00143 0,0006117 0,000003 0,002619 0,00736 0,0144
5 0,00066 0,0017948 0,005224 0,00001 0,0146
6 0,00124 0,0015769 0,000004 0,0016
7 0,0017177 0,0033
8 0,0027069 0,0069
9 0,003037 0,0108
10 0,0023118 0,0113
Tabla 19. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento DHG, según las probabilidades (73) y tres vecinos por clase.
En la Tabla 19 se puede ver el valor del índice σ-BC al aplicarlo al evaluar el
resultado del algoritmo de agrupamiento DHG, sobre las bases de datos sintéticas y
estimando las probabilidades (73) tomando 3 vecinos por clase. Sobre la base de
datos G6, selecciona el nivel de tres clases como el correcto, pero también da
importancia al nivel de seis clases. El resto de las bases de datos se comportan de
manera similar que con las estrategias anteriores.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,00143 0,025635 0,049631 0,000174 0,009006 0,04062
3 0,00114 0,009306 0,014226 0,000001 0,012309 0,00862
4 0,00069 0,009864 0,000003 0,000008 0,000009 0,00637
5 0,00004 0,002222 0,019253 0,000004 0,000006 0,00009
6 0,00016 0,004073 0,017039 0,000013 0,000062 0,00175
7 0,00008 0,000029 0,039958 0,000528 0,003095 0,00133
8 0,00017 0,000006 0,014446 0,001840 0,047270 0,00010
9 0,00018 0,000254 0,018518 0,003077 0,036549 0,00302
10 0,00020 0,003469 0,058143 0,003580 0,012370 0,00309
Tabla 20. Índice de estabilidad σ-BC para las bases de datos sintéticas con el algoritmo de agrupamiento EM, según las probabilidades (73) y tres vecinos por clase.
Cuando evaluamos el índice utilizando el algoritmo EM tomando 3 vecinos
por clase en la fórmula (73), el resultado es muy parecido a las anteriores pruebas,
Capítulo 5
134
solo en el caso de los dos semianillos varía el nivel seleccionado. En general el
comportamiento es el mismo, para las bases gausianas reconoce la estructura
presente mientras que para las otras tres el nivel seleccionado está afectado por el
etiquetado incorrecto del algoritmo EM.
#
Clases 2SA 3AC G4 G6 G6-II DS1
2 0,00025 0,0204 0,000002 0,0000005 0,0000492 0,000001
3 0,00011 0,0043 0,000012 0,0000013 0,0000008 0,000027
4 0,00004 0,0010 0,000006 0,0055162 0,0000044 0,000090
5 0,00039 0,0007 0,000148 0,0109351 0,0000033 0,000043
6 0,00050 0,0021 0,000803 0,0039362 0,0001495 0,009719
7 0,00029 0,0011 0,000611 0,0041654 0,0002152 0,012453
8 0,00010 0,0009 0,000817 0,0001237 0,0000987 0,000065
9 0,00013 0,0002 0,001066 0,0004057 0,0004479 0,002127
10 0,00020 0,0003 0,000746 0,0000436 0,0006124 0,006163
Tabla 21. Índice de estabilidad σ-BC para las bases de datos sintéticas sobre el algoritmo de agrupamiento k-Means, según las probabilidades (73) y tres vecinos por clase.
Según se observa en la Tabla 21 al aplicar el índice σ-BC sobre los resultados
del algoritmo k-Means tomando tres vecinos por clase en la fórmula (73), los
resultados son los mismos que en el caso de un solo vecino por clase, en el caso de
las bases gausianas se observa que el segundo mejor resultado es el correcto.
De los resultados mostrados hasta ahora se puede comentar que igual que
cuando se aplicó el índice σ, se descubre el verdadero número de clusters al aplicar el
algoritmo de agrupamiento DHG y en el caso del algoritmo EM para las bases de
datos gausianas. En el caso del algoritmo k-Means se afecta el valor del índice
debido al problema de la inicialización y al hecho de que este algoritmo no descubre
clusters de formas irregulares. Además, la presencia de ruido y solapamiento
perjudica aún más el etiquetado de las muestras.
En el caso de la base de datos G6 con relación al resultado del índice σ-BC, el
nivel de seis clases se considera el segundo en importancia con los algoritmos DHG
y EM. En general, se puede decir que el índice determina el agrupamiento “natural”
si el algoritmo de agrupamiento empleado descubre la estructura presente en los
datos.
En la Tabla 22 resumimos para cada una de las estrategias para estimar las
probabilidades marginales y sobre los tres algoritmos de agrupamiento empleados, el
nivel seleccionado por el índice σ-BC.
Validación de Clusters
135
Probabilidades Algoritmo 2SA 3AC G4 G6 G6-II DS1
DHG 2 3 4 3 5 6
(72) EM 10 8 4 3 5 5
k-Means 2 5 4 2 5 2
DHG 2 3 4 3 5 6
(73) 1-NN EM 7 8 4 3 5 5
k-Means 4 9 2 2 3 2
DHG 2 3 4 3 5 6
(73) 3-NN EM 5 8 4 3 5 5
k-Means 4 9 2 2 3 2
Real 2 3 4 6 6 6
Tabla 22. Número de clusters seleccionado por el índice σ-BC con cada uno de los algoritmos de agrupamiento y para cada una de las estrategias para estimar las probabilidades de
transmisión.
Según se observa en la Tabla 22, con las dos estrategias para estimar las
probabilidades marginales sobre el algoritmo de agrupamiento DHG, el índice de
estabilidad reconoce en todos los casos el número natural de clusters presente en los
datos, excepto en el caso de G6 que en lugar de reconocer el nivel de seis clases, se
considera como el más importante el nivel de tres clases. En el caso de la base de
datos G6-II se considera correcto el nivel de 5 clases teniendo en cuenta que el
algoritmo DHG no puede separar los dos modos concéntricos.
Respecto al resultado de aplicar el algoritmo EM sobre las bases de datos
gausianas, el índice se comporta de la misma manera que cuando se ejecuta el
algoritmo DHG mientras que para las otras bases de datos, el valor indicado por el
índice no corresponde con el verdadero porque el algoritmo EM no es capaz de
descubrir las diversas formas de los clusters.
En cuanto al algoritmo k-Means sólo en el caso de la primera estrategia
(fórmula (72)) para estimar las probabilidades marginales se obtiene el verdadero
número de clusters con las bases G4 y G6-II. Sobre la base de datos G6 el índice no
descubre el nivel de 3 clases tampoco porque como se sabe el algoritmo k-Means
depende de la inicialización y en los niveles de 3 y seis clases no siempre se obtiene
la misma partición por lo que el nivel de dos clases es más estable.
Bases de datos reales
A continuación se hace el análisis de la aplicación del índice σ-BC sobre las bases de
datos reales que se muestran en la Tabla 2, y la imagen multiespectral BAR de 700 x
670 pixels (Figura 40a). De la misma manera, estimamos primero las probabilidades
Capítulo 5
136
marginales según la fórmula (72) y después según la fórmula (73) tomando uno y
tres vecinos por clase, respectivamente.
#
Clases House Cancer
Diabe-
tes Iris Phoneme BAR Satimage
2 0,0569 0,001 0,002 0,000003 0,000004 0,035000 0,0103
3 0,0609 0,065 0,007 0,000020 0,060229 0,100400 0,0271
4 0,0249 0,092 0,005 0,000969 0,053447 0,053800 0,0270
5 0,0072 0,072 0,059 0,004217 0,100619 0,028700 0,0210
6 0,0088 0,049 0,168 0,075312 0,011300 0,0003
7 0,0104 0,000840 0,0401
8 0,0154 0,000360 0,0410
9 0,0123 0,007290 0,0490
10 0,0123 0,000009 0,0605
Tabla 23. Índice de estabilidad sobre las bases de datos reales empleando el algoritmo DHG, según fórmula (72).
En la Tabla 23 se puede observar el resultado de aplicar el índice σ-BC,
estimando las probabilidades marginales según la fórmula (72) sobre las bases de
datos reales, con la solución de agrupamiento del algoritmo DHG. En todos los casos
el nivel indicado por el índice es el correcto (ver Anexo A), excepto sobre la base de
datos Iris con la que se obtuvo el nivel de dos clases como el óptimo, aunque el nivel
de tres clases es el segundo valor importante del índice. El resultado que se obtiene
sobre la base de datos Iris se debe a que el porcentaje de clasificación correcta en el
nivel de tres clases se ve afectado por la baja densidad de puntos, o sea, al tomar en
nuestra estrategia subconjuntos de 75 puntos, la eficacia del algoritmo DHG se ve
afectada. Sobre las bases de datos Cancer, Diabetes también hay dificultades al
escoger los parámetros del algoritmo DHG por la disminución de los puntos debido a
que son bases de datos pequeñas. Con respecto a la base de datos BAR el índice
determina el nivel de 10 clases (Figura 40b), el cual consideramos correcto.
Validación de Clusters
137
Figura 40. Imagen BAR: a) Imagen original, b) Resultado del agrupamiento empleando el
algoritmo DHG en el nivel de 10 clases seleccionado por el índice σ-BC.
#
Clases House Cancer Diabetes Iris Phoneme BAR Satimage
2 0,00002 0,012 0,043 0,00003 0,020 0,000 0,049
3 0,00005 0,004 0,004 0,00072 0,020 0,000 0,100
4 0,00947 0,009 0,003 0,02230 0,024 0,000 0,056
5 0,01654 0,011 0,006 0,01097 0,012 0,000 0,021
6 0,00706 0,012 0,005 0,01007 0,009 0,023 0,027
7 0,00243 0,014 0,006 0,015 0,016 0,018
8 0,00232 0,008 0,004 0,008 0,020 0,014
9 0,00265 0,005 0,004 0,012 0,012 0,024
10 0,00656 0,005 0,006 0,008 0,008 0,023
Tabla 24. Índice de estabilidad σ-BC sobre las bases de datos reales empleando el algoritmo EM, según fórmula (72).
Con relación al algoritmo EM, se puede observar en la Tabla 24 que en todos
los casos el índice indica un agrupamiento incorrecto debido a que el EM no es capaz
de dividir esas bases de datos adecuadamente. Sólo en el caso de la base de datos Iris
se puede considerar el resultado correcto pues como se sabe, el algoritmo obtiene la
división verdadera en dos clases. De todas formas, se observa que tres es el segundo
valor óptimo que es el que corresponde con la estructura natural de esa base de datos.
Con relación a la base de datos BAR, se obtiene una varianza casi nula para los
niveles desde 2 hasta 5 clases debido a que la información mutua común es casi nula
también, y con el mismo valor en todos esos niveles, por lo que preferimos en ese
caso desecharlos y tomar el de 10 clases como el indicado por el índice que es el
mínimo de los restantes valores.
Capítulo 5
138
#
Clases House Cancer Diabetes Iris Phoneme BAR Satimage
2 0,00001 0,0004 0,024 0,003 0,0988 0,00002 0,134
3 0,00004 0,0019 0,006 0,017 0,0001 0,10004 0,017
4 0,00073 0,0033 0,014 0,017 0,0003 0,00045 0,064
5 0,00307 0,0008 0,032 0,015 0,0349 0,00055 0,039
6 0,00009 0,0015 0,009 0,041 0,0182 0,01350 0,044
7 0,00050 0,0023 0,035 0,012 0,0668 0,03440 0,037
8 0,00401 0,0034 0,022 0,008 0,0716 0,03510 0,004
9 0,00509 0,0012 0,026 0,015 0,0203 0,02470 0,016
10 0,00717 0,0011 0,031 0,014 0,0110 0,00680 0,025
Tabla 25. Índice de estabilidad σ-BC sobre las bases de datos reales empleando el algoritmo k-Means, según fórmula (72).
Al aplicar el índice σ-BC sobre los agrupamientos obtenidos con el algoritmo
k-Means (Tabla 25), sólo en el caso de la base de datos Cancer se detecta el nivel de
agrupamiento correcto. Respecto a la base de datos Iris, se comporta como se espera
por las características de esa base de datos. Sobre la base de datos BAR el índice
escoge el nivel de dos clases lo cual es incorrecto.
Con relación al índice de estabilidad cuando estimamos las probabilidades
marginales según la fórmula (73) tomando un vecino solamente por clase, sobre la
base de datos Iris se detecta el nivel de tres clases como el óptimo, seguido del nivel
de dos clases. El valor del índice sobre las bases de datos pequeñas en el nivel
adecuado se distingue del resto de los niveles lo que significa una mayor estabilidad.
En todos los casos se obtiene el nivel adecuado del agrupamiento.
Cuando se estiman las probabilidades marginales tomando tres vecinos en la
fórmula (73), los resultados son correctos excepto sobre la base de datos Iris que
selecciona el nivel de dos clases como el óptimo, pero de la misma manera, la
diferencia es pequeña con relación al nivel de tres clases. El resto de los resultados es
similar al visto en la Tabla 23.
Respecto a los resultados obtenidos sobre los algoritmos EM y k-Means,
cuando se estiman las probabilidades marginales según la fórmula (73), tomando uno
o tres vecinos por clase, el verdadero número de clusters no es identificado por el
índice, debido a que estos algoritmos no son capaces de descubrir la verdadera
división en clases de esas bases de datos. Sólo en el caso de las bases Cancer
empleando el algoritmo k-Means, se considera el nivel de dos clases como el
correcto.
Validación de Clusters
139
En la Tabla 26 resumimos para cada una de las estrategias para estimar las
probabilidades marginales con los tres algoritmos de agrupamiento empleados, el
nivel seleccionado por el índice σ-BC.
Al aplicar el índice σ-BC sobre la solución de agrupamiento que se obtiene
con el algoritmo DHG, como se ve en la Tabla 26, se obtiene el verdadero número de
clusters en todos los casos, excepto para la base de datos Iris. En el caso de la base
de datos Iris, el índice indica el nivel de tres clases como el óptimo cuando
utilizamos la fórmula (73) seleccionando solamente un vecino por clase, en los otros
dos casos es identificado el nivel de dos clases como el verdadero y en segundo lugar
el nivel de tres clases.
Prob Algoritmo House Cancer Diabet Iris BAR Phon Satimag
DHG 5 2 2 2 10 2 6
(72) EM 2 3 4 2 10 8 8
k-Means 2 2 3 2 2 3 8
DHG 5 2 2 3 10 2 6
(73) EM 2 9 4 2 10 6 8
1-NN k-Means 2 2 3 2 2 3 8
DHG 5 2 2 2 10 2 6
(73) EM 2 4 4 2 10 6 8
3-NN k-Means 2 2 9 2 2 3 8
Real 5 2 2 3 12 2 6
Tabla 26. Número de clusters seleccionado por el índice σ-BC con cada uno de los algoritmos de agrupamiento sobre las bases de datos reales y para cada una de las estrategias para estimar las
probabilidades de transmisión.
Sobre los resultados del algoritmo EM el índice indica agrupamientos
erróneos como el óptimo en todos los casos (excepto sobre la base de datos BAR),
debido a que este algoritmo no reconoce bien la estructura presente en esas bases de
datos. En general, indica los mismos niveles de agrupamiento independientemente de
la estrategia empleada para estimar las probabilidades marginales, excepto sobre la
base de datos Cancer. En el caso de la base de datos Iris se considera el nivel de dos
clases como el verdadero.
Respecto a los resultados obtenidos cuando se aplica el algoritmo k-Means
(Tabla 26), sobre la base de datos Cancer, en todos los casos se obtuvo el número
correcto de clusters. Sobre el resto de las bases de datos no se detecta el verdadero
número de clusters debido a las características del algoritmo k-Means.
Capítulo 5
140
4.4 Resultados de la aplicación del índice σ-BC para seleccionar el
modelo de agrupamiento
Otra cuestión importante dentro de la validación de clusters es la determinación del
mejor agrupamiento, o sea, cuál de los algoritmos refleja mejor la estructura interna
de los datos. Una posibilidad para escoger el algoritmo que divide los datos de
manera correcta, sería tomar al agrupamiento de mayor información mutua de entre
los agrupamientos de varianza mínima.
Para cada base de datos, para cada algoritmo de clustering, tomamos el
agrupamiento de mínima varianza y seleccionamos la mejor estrategia como se
indica en la Sección 3.2 de este capítulo.
Bases de datos sintéticas
En la Tabla 27 aparece el valor estimado de la información mutua en el nivel
correspondiente al de varianza mínima de entre todos los algoritmos de
agrupamiento.
2SA 3AC G4 G6 G6-II DS1
EM 0,436 0,702 1,974 1,245 2,197 0,525
k-Means 0,925 0,844 1,970 0,914 2,170 0,980
DHG 1,002 1,575 1,965 1,246 2,190 1,717
Tabla 27. Valor de la información mutua promedio en el nivel de mínima varianza con las probabilidades marginales (72) sobre las bases de datos sintéticas.
Por ejemplo, de los resultados obtenidos sobre la base de datos 2SA entre las
Tablas 13, 14 y 15 el valor mínimo se alcanza con el algoritmo DHG en el nivel de
dos clases; en la Tabla 27, en el caso de la base de datos 2SA mostramos el valor de
la información mutua en el nivel de dos clases para todas las estrategias de
agrupamiento. De la misma manera que, en el caso de 3AC el mínimo valor del
índice σ-BC se obtiene con el algoritmo DHG en el nivel de tres clases, por tanto, en
la Tabla 27 tenemos los valores de la información mutua sobre 3AC en el nivel de
tres clases para cada una de las estrategias de agrupamiento, etc (ver fórmula (76)).
Según se observa en la Tabla 27, el algoritmo de agrupamiento que mayor
información mutua común tiene como promedio en la mayoría de las bases de datos
es DHG. En el caso de las bases de datos gausianas G4 y G5 los tres algoritmos
tienen resultados similares lo que indica que cualquiera de ellas interpreta bien la
estructura de los datos. Sobre la base de datos G6, los algoritmos EM y DHG son las
mejores estrategias, debido a que k-Means es sensible a la inicialización sobre ésta.
Validación de Clusters
141
Al emplear la expresión (73) para estimar las probabilidades marginales,
cuando aplicamos la estrategia para seleccionar el mejor algoritmo de agrupamiento,
en el caso de DS1 se selecciona el algoritmo k-Means, lo que no es adecuado, por lo
que consideramos que esta variante no es conveniente para seleccionar el mejor
modelo de clustering.
Bases de datos reales
A continuación se hace el análisis de la aplicación del índice σ-BC sobre las bases de
datos reales que se muestran en la Tabla 2 y la imagen BAR, con el objetivo de
determinar el modelo de agrupamiento que mejor refleja la estructura de los datos.
House Cancer Diabetes Iris Phoneme BAR Satimage
EM 0,880 0,47 1,45 0,92 0,68 1,87 1,47
k-M 0,972 0,78 1,01 0,82 0,66 1,77 1,63
DHG 0,974 0,73 0,52 1,83 0,74 2,25 0,69
Tabla 28. Valor de la información mutua promedio en el nivel de mínima varianza con las probabilidades marginales (72) sobre las bases de datos reales.
En la Tabla 28 se puede observar el resultado de la estrategia propuesta sobre
los tres algoritmos de agrupamiento empleados cuando se utiliza la expresión (72)
para estimar las probabilidades marginales. El algoritmo DHG se considera el mejor
método de agrupamiento sobre las bases de datos House, Iris, Phoneme y BAR,
aunque sobre Phoneme prácticamente las tres estrategias de agrupamiento son
adecuadas. En el caso de la base de datos Diabetes, se selecciona el algoritmo de
agrupamiento EM como la mejor estrategia, mientras que sobre Satimage y Cancer
se determina que el algoritmo k-Means es la mejor técnica para dividir los datos en
grupos. En el caso de Cancer, las estrategias k-Means y DHG son las que mejor
modelan la estructura verdadera de los datos. Con relación a la base de datos BAR, el
algoritmo DHG es el que mejor interpreta su estructura interna, seguido del
algoritmo EM.
Cuando aplicamos nuestra propuesta para seleccionar el modelo de
agrupamiento utilizando las probabilidades marginales (73), se observa un
comportamiento similar con relación a los resultados anteriores.
5 Conclusiones
En este Capítulo 5, hemos presentado dos alternativas para la validación de clusters.
Estos nuevos enfoques basados en estabilidad, tratan de superar algunas deficiencias
de otros métodos, como por ejemplo, el empleo de clasificadores basados en
Capítulo 5
142
centroides, la necesidad de hacer permutaciones en el conjunto de etiquetas, o de
emplear clustering aleatorio, o de optimizar alguna función para seleccionar el
clasificador.
Haciendo uso de la teoría de la información que nos permite acotar el error de
Bayes, hemos introducido dos nuevos índices (σ y σ-BC) que miden la variabilidad
de la información mutua entre la distribución de probabilidades de los datos y la
distribución de probabilidades de las clases.
Hemos mostrado los resultados experimentales en dos formas: primero, el
valor de nuestro índice para cada una de las bases de datos, cada uno de los valores
del parámetro k y cada uno de los algoritmos de agrupamiento considerados, con el
objetivo de explicar cómo determinamos el verdadero valor de k. Segundo, de
manera similar, hemos presentado los valores de las probabilidades de los dos
métodos basados en estabilidad con los que nos comparamos, para luego mostrar el
número de clusters “natural” que cada método de validación de clusters estima.
Según se ha podido observar, nuestros métodos son capaces de determinar el
número correcto de clusters en bases de datos de características distintas, con
diversos grados de solapamiento entre las clases, ruido y clusters de diferentes
formas y tamaño. Para el resto de los métodos hemos comentado sus deficiencias,
según se observa en los resultados obtenidos en la comparación, entre ellas:
1. Los métodos que emplean clasificación supervisada basada en centroides no
obtienen buenos resultados en bases de datos de formas irregulares.
2. En algunos casos es necesario hallar todas las permutaciones de las etiquetas,
lo que significa mayor coste cuando el número k de clases es alto.
3. El método de [Lange, 2004] por ejemplo, realiza agrupamientos aleatorios
para normalizar su índice de estabilidad debido a la gran dependencia de éste
del número k de clusters.
4. En el caso de la estrategia de Fischer y Buhmann los resultados se afectan
cuando los clusters están muy solapados.
5. Los índices de validación estudiados asumen propiedades en las bases de
datos como compacidad de los clusters y separación entre ellos, lo que en
general no es cierto, por lo que en el caso de bases de datos con grupos muy
solapados y en presencia de ruido no funcionan bien.
Además, en el caso del índice σ-BC, indicamos una estrategia para determinar
el mejor algoritmo de agrupamiento para cada una de las bases de datos mediante el
valor promedio de la información mutua común del resultado de agrupamiento de
mínima variabilidad. De acuerdo a los resultados obtenidos, podemos concluir que es
Validación de Clusters
143
un método adecuado cuando se utilizan las probabilidades marginales (72). En el
caso de las probabilidades (73) no siempre los resultados son los esperados. Además,
la fórmula (72) tiene ventajas pues sólo es necesario buscar un vecino para cada
punto de la base de datos, mientras que la otra introduce un nuevo parámetro que es
el número de vecinos por clase y según el valor introducido serán tantos vecinos
como número de clases por el valor del parámetro, lo que hace el proceso de
validación más lento.
En resumen, las estrategias empleadas para la selección del nivel de
agrupamiento para cada método de agrupamiento y la utilizada para determinar el
algoritmo de agrupamiento que mejor divide los datos en grupos, obtienen resultados
satisfactorios en general, en bases de datos con grupos de diversas formas y tamaño,
en presencia de ruido y solapamiento entre grupos, en bases de datos de diferentes
dimensionalidades y número de clases.
Parte III
Conclusiones y Líneas Futuras
Capítulo 6
Conclusiones Finales
1 Principales Aportaciones
El objetivo fundamental de esta Tesis Doctoral se ha centrado, dentro del
Reconocimiento Estadístico de Formas, en el estudio y análisis de un conjunto de
técnicas de clasificación no supervisadas. A lo largo de los primeros capítulos de esta
memoria, se ha llevado a cabo una importante recopilación bibliográfica y revisión
teórica sobre algunos aspectos básicos relacionados con el tema.
La primera aportación de este trabajo se centra en diseñar dos reglas de
clasificación no supervisada (H-Density y DHG) con una estrategia híbrida entre los
enfoques basado en densidad y jerárquico. Los algoritmos están divididos en dos
etapas, en la primera se forman grupos según la estrategia basada en densidad, por
medio de una función de densidad, en la segunda etapa se define una función de
disimilaridad entre clusters, que tiene en cuenta tanto el solapamiento como la
cercanía entre los grupos, para unir los dos grupos más cercanos en cada nivel de la
jerarquía que comienza a partir de los grupos obtenidos en la primera etapa.
La segunda aportación de esta Tesis Doctoral constituye dos propuestas de
algoritmo para evaluar un agrupamiento (índices σ y σ-BC). En ellas, se integran de
forma homogénea algunos tópicos acerca de la teoría de la información, la regla de
clasificación K-NN (en el caso del índice σ) y el algoritmo de agrupamiento en
cuestión.
Finalmente, cabe destacar el hecho de que todas las aproximaciones
propuestas en los diferentes capítulos han sido evaluadas sobre bases de datos
sintéticas y reales, comparando sus resultados con los obtenidos de diferentes
procedimientos. Por medio de este análisis experimental, hemos tenido la posibilidad
de comprobar que, en la mayoría de los casos, los esquemas introducidos en este
trabajo presentan un mejor comportamiento que otros algoritmos de clasificación no
supervisada y de validación de clusters.
A continuación, haremos un rápido recorrido por los capítulos que han
significado algún tipo de aportación en los campos previamente mencionados,
Capítulo 6
148
comentando en cada caso los principales resultados obtenidos a partir del
correspondiente análisis empírico.
Aportaciones a los Métodos de Clasificación no Supervisados
En el Capítulo 4, se ha diseñado una nueva estrategia de agrupamiento, que emplea
un enfoque híbrido entre los algoritmos de agrupamiento basados en densidad y los
algoritmos de agrupamiento jerárquicos aglomerativos. La idea de este algoritmo es
usar las ventajas de las estrategias basadas en densidad, que son capaces de detectar
zonas de baja densidad, para lograr una primera división en zonas de mayor
densidad. Luego, se unen los grupos obtenidos en la primera etapa según un criterio
que tiene en cuenta la cercanía y el solapamiento de esos primeros grupos. De esta
forma, el nuevo algoritmo es capaz de detectar la división correcta en bases de datos,
cuyos grupos tienen diferente densidad, formas y tamaño.
También se ha diseñado un segundo algoritmo, debido a la dificultad del
primero con relación a la determinación de los parámetros adecuados para conseguir
el agrupamiento correcto. Esta nueva variante introduce, en lugar del parámetro R
(radio de la vecindad), los K vecinos más cercanos de cada punto y sustituye la
función de densidad local de la primera etapa por un modelo generativo basado en
mixtura de gausianas, o sea, empleamos una función paramétrica de densidad global
que nos permite establecer las zonas de alta densidad en la base de datos. En la
segunda parte del algoritmo, se ajusta una nueva función de disimilaridad formada
por tres factores, con el objetivo de tener en cuenta la cercanía y solapamiento entre
los grupos así como la presencia de ruido. En la etapa jerárquica se desarrolla, al
igual que en el primer algoritmo, una estrategia SL con el empleo de la nueva
función de disimilaridad.
Aportaciones a los Algoritmos de Validación de Clusters
Respecto a las diferentes aproximaciones propuestas a lo largo del Capítulos 5, cabe
destacar que las estrategias de validación de clusters tienen dificultades cuando los
grupos en la base de datos están muy solapados. Para mejorar esto, seguimos la línea
de validación de clusters basada en estabilidad y, más exactamente, la estrategia
basada en transferencia por predicción porque los índices estudiados de la literatura
generalmente tienen en cuenta determinadas propiedades que, si no están presentes
en la base de datos, no consiguen el resultado adecuado, como es el caso de los
índices de validación que suponen separación y compacidad de los clusters.
Nuestra principal aportación ha sido emplear la información mutua como un
criterio para acotar el error de clasificación de Bayes. Con nuestro enfoque basado en
Conclusiones Finales
149
remuestreo, obtenemos una variabilidad de la predicción que transmitirá una
variabilidad del error de decisión. Esta variabilidad se estima por medio de la
evaluación de la variación de las medidas de información, dando lugar a dos nuevos
índices de estabilidad que permiten determinar el número correcto de clusters en una
base de datos.
El índice σ se estima a través del modelo de un canal ruidoso y, más
exactamente, a través de la variabilidad de la información mutua entre el conjunto de
datos y el conjunto de las etiquetas, mientras que el índice σ-BC se estima
modelando el proceso de validación a través de un canal de difusión, para evitar el
uso de clasificadores supervisados y de establecer correspondencias entre etiquetas
de clase.
Para estimar ambos índices de estabilidad, se definieron probabilidades a
posteriori que a su vez fueron estimadas por medio de los diferentes subconjuntos de
muestras etiquetados por el algoritmo de agrupamiento.
También indicamos una estrategia para determinar el algoritmo de
agrupamiento que mejor modela la estructura presente en la base de datos mediante
el índice σ-BC.
2 Conclusiones
En esta memoria de tesis hemos presentado dos estrategias de clustering basadas en
densidad (H-Density y DHG), con el objetivo de eliminar algunas de las limitaciones
presentes en otros algoritmos de agrupamiento como, por ejemplo: resultados
dependientes de la inicialización y de la posición de los centroides de cada clase
(como k-Means), imposibilidad de descubrir clusters de formas arbitrarias (como EM
y k-Means que dan lugar a clusters globulares y SL cuyos clusters son más bien
alargados), problemas para manejar el ruido (como DBSCAN, k-Means), resultados
erróneos en presencia de grupos solapados (como DBSCAN, k-Means, FB), las
estrategias basadas en centroides fallan cuando los puntos están más cerca del
centroide de otra clase, entre otras.
Algunos de los métodos de validación de clusters vistos en la literatura
consultada tienen desventajas tales como: desarrollan estrategias basadas en
centroides por lo que en bases de datos de grupos con formas irregulares no pueden
descubrir los verdaderos clusters, en presencia de solapamiento no pueden separar
los grupos existentes, necesitan hacer permutaciones de las etiquetas, los índices de
validación, por ejemplo, suponen grupos compactos y bien separados, etc.
Capítulo 6
150
A continuación, hacemos nuestras conclusiones acerca de los resultados
obtenidos.
Algoritmos de Clustering
El algoritmo H-Density utiliza una función de densidad local que permite descubrir
clusters de formas, densidades y tamaño diferentes, lo que elimina las limitaciones
de otras estrategias como k-Means, EM, SL y DBSCAN.
Emplea una función de disimilaridad en la etapa jerárquica que tiene en
cuenta tanto la cercanía como el solapamiento entre los grupos, por lo que descubre
los verdaderos grupos en bases de datos con gran solapamiento como G6 y House, a
diferencia de otras estrategias de clustering.
Se establece una estrategia para manejar el ruido, de esta forma se descubren
los verdaderos grupos en bases de datos ruidosas como DS1 y DS2.
El algoritmo DHG emplea una mixtura de gausianas para descubrir zonas de
alta densidad en las bases de datos, lo que favorece la formación de grupos de
densidades y formas arbitrarias al igual que H-Density. Tiene ventajas respecto al
algoritmo H-Density en cuanto al empleo de sus parámetros.
La función de disimilaridad definida para medir las disimilaridades entre los
grupos resultantes de la primera etapa está diseñada no sólo para medir cercanía entre
clusters sino también para manejar el ruido y obtener los resultados adecuados a
pesar de la existencia de grupos solapados en la base de datos.
De los resultados experimentales, se observa que ambos métodos obtienen
agrupamientos adecuados en bases de datos sintéticas y reales de diversas
características.
En las comparativas que se hicieron con otros métodos de clasificación no
supervisada, se observan resultados superiores cuando se emplean las dos estrategias
presentadas en este trabajo sobre bases de datos sintéticas y reales porque resuelven
algunas de las limitaciones de los otros métodos.
Los dos algoritmos tienen en común la estrategia para formar los grupos de la
primera etapa y la estrategia jerárquica de la segunda etapa.
Validación de Clusters
En la primera de las estrategias, se eliminan algunas de las limitaciones de los otros
enfoques, por ejemplo, el uso de clasificadores basados en centroides, por lo que
conseguimos buenos resultados sobre bases de datos con grupos de formas
irregulares.
Conclusiones Finales
151
Se evita hacer permutaciones de las etiquetas y agrupamientos aleatorios; en
su lugar, se emplea la teoría de la información y el índice σ para determinar la
variabilidad de la información mutua entre los datos y las etiquetas de clase, lo que
hace el proceso de validación más rápido.
La segunda estrategia de validación de clusters está modelada a través de un
canal de difusión. Con el índice σ-BC, evitamos el empleo de un clasificador
supervisado y de establecer correspondencias entre las etiquetas de clase originadas
por el algoritmo de agrupamiento, lo que hace que esta estrategia sea aún más
conveniente.
Los resultados experimentales sobre bases de datos sintéticas y reales
demuestran que ambas descubren los agrupamientos adecuados incluso si los grupos
tienen formas diversas, si hay solapamiento y ruido. Se obtiene el número de clusters
“natural” de cada base de datos si el algoritmo de agrupamiento empleado para
dividir los datos en grupos reconoce la estructura real de los datos. En el caso del
índice σ-BC, indicamos también una estrategia para seleccionar el algoritmo de
agrupamiento que mejor funciona de entre varios algoritmos.
Diseñamos dos maneras para estimar las probabilidades relacionadas con el
canal de difusión en el índice σ-BC. Una de ellas produce mejores resultados
(fórmula (72)) en tres aspectos: los resultados obtenidos satisfacen nuestras
expectativas, sólo es necesario buscar un vecino para cada punto y no hay que
introducir el parámetro número de vecinos por clase, en cuyo caso el proceso de
validación además es más costoso computacionalmente.
Al aplicar la estrategia para determinar el mejor algoritmo de agrupamiento,
los algoritmos EM y DHG fueron seleccionados como los más adecuados en el caso
de bases de datos gausianas. Para bases de datos como 3AC y 2SA que están
formadas por grupos bien separados pero de formas irregulares, la mejor técnica para
agruparlos es DHG. Sobre las bases de datos reales, los algoritmos DHG y k-Means
resultaron ser las mejores estrategias de agrupamiento. Por tanto, esta estrategia se
revela como una línea experimental adecuada para la selección del modelo de
clustering.
3 Publicaciones Relacionadas
De los diferentes resultados obtenidos a partir del trabajo de Tesis Doctoral, han
podido surgir varias publicaciones, tanto en forma de artículos en revistas nacionales
e internacionales como participaciones en congresos. A continuación, enumeramos
las que se han originado hasta este momento.
Capítulo 6
152
• Pascual, D. Pla, F. and Sánchez, J. S. Cluster Validation using Information
Stability Measures. Pattern Recognition Letters (aceptado para publicar,
2009).
• Pascual, D. Pla, F. and Sánchez, J. S. “Cluster Stability Assessment based on
Theoretic Information Measures”. CIARP 2008, LNCS 5197, pp. 219 – 226.
• Pascual, D., Pla, F. and Sánchez, J. S. “Non Parametric Local Density-based
Clustering for Multimodal Overlapping Distributions”. 7th Int. Conf on
Intelligent Data Engineering and Automated Learning LNCS 4224. Springer-
Verlag 2006, pp. 671 - 678.
• Pascual, D., Pla, F. and Sánchez, J. S. “Hierarchical-based Clustering using
Local Density Information for Overlapping Distributions”. Pattern
Recognition Progress, Directions and Applications. Eds. F. Pla, J. Vitriá and
P. Radeva. ISBN 84-933652-6-2, 2006, pp. 303 – 312.
• Pascual, D., Pla, F. y Sánchez J. S. “Algoritmos de Agrupamiento”.
Memorias de la Jornada de Seguimiento UO-UJI. Enero 2006.
4 Posibles Extensiones
Fundamentalmente, el trabajo desarrollado en esta Tesis Doctoral permite establecer
nuevas perspectivas en cuanto a los métodos de clasificación no supervisada, entre
ellos, multi-clasificadores no supervisados y semisupervisados.
En cuanto a trabajos futuros, podemos sugerir varias líneas de investigación:
1. Desarrollar esquemas similares a los propuestos en esta tesis, considerando
otras métricas para establecer las disimilaridades entre los grupos.
2. Introducir la clasificación no supervisada en esquemas de aprendizaje
continuo con el objetivo de disminuir los puntos etiquetados en los mismos.
3. Profundizar y desarrollar la línea de validación de modelos de clustering
propuesta, dado que se han obtenido resultados muy prometedores.
En general, consideramos que existen diversas líneas de investigación que
pudieran incluirse, relacionadas con los algoritmos de agrupamiento, que aún no
están desarrolladas en el actual estado del arte, de forma que el proceso se acerque lo
más posible al aprendizaje humano y a la capacidad de adaptarse a nuevas
condiciones.
Anexo A
Descripción de las Bases de Datos
Reales
En esta sección, describiremos las bases de datos reales empleadas para realizar los
experimentos para evaluar los algoritmos de agrupamiento utilizados en este trabajo.
La elección de estas bases de datos se ha realizado en función de parámetros muy
variados, tales como las diferentes tallas de los conjuntos, la dimensión del vector de
características, el número de posibles clases y el grado de solapamiento entre las
regiones de clases distintas. Se han escogidos varias bases de datos pertenecientes al
repositorio de UCI, UCI Repository of Machine Learning Database and Domain
Theories [Merz, 1996]. A continuación se pasa a describir brevemente cada uno de
los corpus utilizados.
Iris
Esta es quizás la base de datos más conocida en la literatura de Reconocimiento de
Patrones. El conjunto de datos consta de 3 clases de 50 ejemplos cada una, donde
cada clase se refiere a un tipo de planta Iris. Una clase está separada linealmente de
las otras dos, mientras que dos no son linealmente separables. Consta de cuatro
atributos: longitud y ancho del sépalo de la flor y longitud y ancho de los pétalos en
centímetros. Los tres tipos de planta Iris son: Iris Setosa, Iris Virginica e Iris
Versicolor.
Cancer
Esta base de datos como su nombre lo indica ha sido obtenida de pacientes que
presentan tumoraciones en el Hospital Universitario de Wisconsin. Se compone de
un total de 683 pacientes (prototipos) con diversas tumoraciones, clasificando los
mismos en dos clases, pacientes con tumores benignos o pacientes con tumores
malignos. Para representar cada paciente se utilizaron 9 características, las cuales son
las siguientes: Clump Thickness, Uniformity of Cell Size, Uniformity of Cell Shape,
Marginal Adhesion, Single Epithelial Cell Size, Bare Nuclei, Bland Chromatin,
Normal Nucleoli y Mitoses.
Anexo A
154
Diabetes
Esta base de datos pretende predecir la diabetes. Para ello de cada individuo se
conocen 8 características, entre las que podemos mencionar: edad, presión arterial,
índice de masa corporal, etc. La misma posee 768 individuos descritos mediante los
8 rasgos antes mencionados, agrupados los mismos en dos clases.
Liver
Estos datos corresponden a un problema de clasificación de desórdenes en el hígado
en 2 clases. Las muestras se representan mediante 6 características, las 5 primeras
provenientes de un análisis de sangre, mientras que la última representa la cantidad
de alcohol que consume en promedio el paciente en un día. Para la confección de
esta base fueron tomadas muestras de 345 pacientes.
Phoneme
La presente base de datos está formada por vocales tomadas a partir de 1.809 sílabas
aisladas (por ejemplo, /ar/,/gen/, /list/,/bult/, …), de manera que el objetivo central de
este problema será distinguir entre las vocales nasales y las vocales orales, por lo
cual la base de datos constará de dos clases. Cada vocal se encuentra caracterizada
por cinco atributos correspondientes a la amplitud de los cinco primeros armónicos
normalizados por la energía total. Se tomaron observaciones para cada sílaba en tres
instantes distintos, correspondiente al momento de máxima energía total y, a 8 mseg
antes y después de alcanzar dicho valor máximo. A partir de las 5.427
representaciones obtenidas mediante este procedimiento, se eliminaron las 23
muestras para las que las amplitudes de los cincos primeros armónicos eran nulas,
resultando un conjunto final con 5.404 muestras disponibles.
Satimage
Esta base de datos fue generada a partir de las imágenes captadas mediante el escáner
multi-espectral de un satélite “Landsat”, con el objetivo de analizar el
comportamiento de diferentes métodos de clasificación basados en redes neuronales
y clasificadores estadísticos sobre datos procedentes de diversas áreas industriales.
Una imagen de dicho escáner consta de cuatro imágenes digitales
pertenecientes a una misma escena, pero en distintas bandas espectrales (dos
correspondientes a la región visible y, las otras dos, próximas a la región de
infrarrojos). Por otra parte, cabe indicar que cada una de estas imágenes tiene una
resolución de 2.340x3.380 pixeles. El vector de características corresponde a una
región cuadrada de 3x3 pixeles. El conjunto contiene un total de 6.435 muestras con
Descripción de las Bases de Datos Reales
155
36 atributos cada una (4 bandas espectrales por cada uno de los 9 pixeles en aquella
región cuadrada), pertenecientes a seis posibles clases.
Anexo B
Algoritmo EM
En esta sección, describiremos el algoritmo EM para determinar los parámetros de
una mixtura de gausianas mediante el método de máxima verosimilitud.
En inferencia estadística se llama estimación al conjunto de técnicas que
permiten dar un valor aproximado de un parámetro de una población a partir de los
datos proporcionados por una muestra. Un estimador de un parámetro poblacional es
una función de los datos muestrales, también llamado estadístico.
La estimación puede dividirse en tres grandes bloques:
1. Estimación puntual
2. Estimación por intervalos
3. Estimación bayesiana
La estimación puntual consiste en la estimación del valor del parámetro
mediante un solo valor obtenido de una fórmula determinada, puede realizarse
mediante diferentes métodos:
1. Método de los momentos
2. Método de la máxima verosimilitud
3. Método de los mínimos cuadrados.
La estimación por intervalos consiste en la obtención de un intervalo dentro
del cual estará el valor del parámetro estimado con una cierta probabilidad.
La estimación bayesiana es un tipo de inferencia estadística, en la que las
evidencias u observaciones se emplean para actualizar o inferir la probabilidad de
que una hipótesis pueda ser cierta. Su nombre se debe al amplio empleo del conocido
teorema de Bayes en las decisiones, matemáticamente, se trata de obtener las
probabilidades de las hipótesis condicionadas a las evidencias que se conocen. Tiene
aplicaciones en ramas como: Visión por Computador, Teoría de la Decisión,
Reconocimiento de Patrones, etc.
Nosotros solo nos referiremos al método de máxima verosimilitud (method of
maximum likelihood), abreviado a menudo como MLE.
Anexo B
158
La idea principal detrás del método de máxima verosimilitud, es determinar el
parámetro que maximiza la probabilidad (likelihood) de los datos muestrales. Más
detalladamente:
Sea X una variable aleatoria con función de densidad o función de
probabilidad ( )θ/xp donde θ representa el parámetro que se desea estimar usando
una muestra aleatoria X1, X2, …, XN, donde cada Xi tiene la misma distribución de X y
son independientes entre sí.
Se define la función de verosimilitud por:
( ) ( ) ∏=
==N
i
ixpxLL1
)/(/ θθθ (77)
El estimador máximo verosímil θ del parámetro θ es aquel valor que
maximiza la función de verosimilitud, es decir:
( )θθθ
Lmaxargˆ = (78)
Es más frecuente maximizar )(LLn)(likelog θθ =− , debido a que Ln es una
función monótona del valor de θ que alcanza su máximo en el mismo valor de θ
que ( )θL .
Como el objetivo del método de máxima verosimilitud es encontrar el valor
de θ que maximiza la función de verosimilitud, el valor del estimador se consigue
derivando e igualando a cero la Log-verosimilitud, es decir:
( ) 0=∂∂ θθ
LLn (79)
El algoritmo EM (Expectation Maximization), inicialmente propuesto por
Dempster (1977), presenta una técnica iterativa general para realizar una estimación
de máxima verosimilitud de parámetros, en problemas en los que existen ciertos
datos ocultos, es decir, en situaciones en las que se desea estimar un conjunto de
parámetros θ, que describen una distribución de probabilidad, dada únicamente una
parte observada de los datos completos producidos por la distribución.
Denotemos por X={x1, x2, …, xn}, al conjunto de datos observados en n
realizaciones del experimento, similarmente por Z={z1, z2, …, zn}, al conjunto de
datos no observados. La función de log-verosimilitud (log-likelihood) toma la forma:
( ) ( )
= ∑Z
/Z,XpLn/XpLn θθ (80)
La presencia de la suma imposibilita al logaritmo actuar directamente sobre la
distribución conjunta, lo que resulta en expresiones complicadas para la solución de
Algoritmo EM
159
máxima verosimilitud. Todo lo anterior puede aplicarse igualmente al caso de
variables continuas sustituyendo la suma sobre Z por la integral.
En la práctica, se desconoce el conjunto de datos completo {X, Z}, sino
solamente el conjunto de datos incompleto X. Nuestro conocimiento acerca de las
variables ocultas en Z, está dado solamente por la distribución a posteriori
( )θ,X/Zp . Luego, la distribución de probabilidad de la variable Y=Z∪X está dada
por:
( ) ( ) ( ) ( )θθθθ /Xp,X/Zp/Z,Xp/Yp == (81)
Dado que el conjunto de datos completo Y es una variable aleatoria, que
contiene datos Z no observados, no podemos usar la log-verosimilitud de la misma,
en su lugar, se consideran todos los posibles valores de X, ponderándolos según su
probabilidad, en otras palabras, se calcula su valor esperado bajo la distribución a
posteriori de la variable oculta, lo cual corresponde al paso E del algoritmo EM. En
el paso siguiente, se maximiza este esperado, lo que constituye el paso M.
En el paso E, se emplea un parámetro actual aθ para encontrar la distribución
a posteriori de las variables ocultas dada por ( )a,X/Zp θ , y se usa esta distribución
a posteriori, para encontrar el esperado de la log-verosimilitud de los datos
completos, evaluado para algún valor general del parámetro θ. Este esperado se
denota por ( )a,Q θθ y está dado por:
( ) ( )[ ] ( ) ( )∑==Z
aaa /Z,XpLn,X/Zp,Z/YpLogE,Q θθθθθθ (82)
En el paso M, se determina el parámetro estimado nθ maximizando esa
función, es decir:
( )an ,Qmaxarg θθθθ
= (83)
El algoritmo EM puede resumirse como sigue:
Dada una distribución conjunta ( )θ/Z,Xp sobre variables observadas X y
variables ocultas Z, gobernada por parámetros θ , la meta es maximizar la función de
verosimilitud ( )θ/Xp con respecto a θ .
1. Escoger un valor inicial para los parámetros aθ .
2. Paso E: evaluar ( )a,X/Zp θ
3. Paso M: Evaluar nθ dada por:
( )an ,Qmaxarg θθθθ
= (84)
Anexo B
160
donde ( ) ( ) ( )∑=Z
aa /Z,XpLn,X/Zp,Q θθθθ
4. Verificar la convergencia o de la log-verosimilitud, o de los valores de los
parámetros. Si el criterio de convergencia no se cumple entonces poner
an θθ ← y volver al paso 2.
El algoritmo EM también puede usarse para obtener soluciones máximo a
posteriori (MAP), para modelos en los cuales se define una prior ( )θp sobre los
parámetros. En este caso, el paso E es el mismo mientras que en el paso M la
cantidad a ser maximizada está dada por ( ) ( )θθθ pLn,Q a + .
Mixtura de Gausianas
Una distribución de mixtura de gausianas se puede escribir como una superposición
de gausianas en la forma:
( ) ( )∑=
Σ=k
j
jjj ,/xNxp1
µπ (85)
donde
1101
=≤≤ ∑=
k
j
jj , ππ (86)
Supongamos que tenemos N observaciones {x1, …, xN}, y deseamos modelar
estos datos empleando una mixtura de gausianas. Este conjunto de datos lo podemos
representar como una matriz X de NxD en la cual la n-ésima fila está dada por xnT.
Similarmente, las correspondientes variables ocultas serán denotadas por una matriz
Z de NxK con filas znT. Si asumimos que los puntos o datos son escogidos
independientemente de la distribución, entonces podemos expresar el modelo de
mixtura de gausianas por este conjunto de datos independiente e idénticamente
distribuido y la función log-verosimilitud está dada por:
( ) ( )∑ ∑= =
Σ=ΣN
n
K
k
kknk ,/xNLn,,/xpLn1 1
µπµπ (87)
Si calculamos la derivada de ( )Σ,,/xpLn µπ con respecto a kµ e igualamos
a cero obtenemos
( )( )
( )∑∑=
=
−ΣΣ
Σ−=
N
n
knkK
j
jjnj
kknk x
,/xN
,/xN
1
1
0 µµπ
µπ
(88)
Algoritmo EM
161
Multiplicando por 1−Σ k , la cual asumimos que es no singular y despejando
obtenemos:
( )∑=
=N
n
nnk
k
k xzN 1
1 γµ (89)
donde
( ) ( )( )∑
=
Σ
Σ=
K
j
jjnj
kknk
nk
,/xN
,/xNz
1
µπ
µπγ
(90)
y
( )∑=
=N
n
nkk zN1
γ (91)
Podemos interpretar Nk como el número efectivo de puntos asignado al
cluster k. Como se observa, la media kµ de la k-ésima componente gausiana, se
obtiene tomando una media pesada de todos los puntos del conjunto de datos, en la
cual el peso para el punto nx está dado por la probabilidad a posteriori ( )nkzγ de que
la componente k fuera responsable de generar nx .
Si derivamos ( )Σ,,/xpLn µπ con respecto a kΣ e igualamos a cero, y
siguiendo un razonamiento análogo, obtenemos:
( )( )( )∑=
−−=ΣN
n
T
knknnk
k
k xxzN 1
1 µµγ (92)
que tiene la misma forma que el correspondiente resultado para una gausiana simple
ajustada al conjunto de datos, pero de nuevo con cada punto pesado por la
correspondiente probabilidad a posteriori y con el denominador dado por el número
efectivo de puntos asociados con la correspondiente componente.
Finalmente, maximizamos ( )Σ,,/xpLn µπ con respecto a los coeficientes de
mixtura kπ . Aquí debemos tener en cuenta la consideración sobre kπ que requiere
que la suma de los coeficientes de mixtura sea 1.
Esto se realiza empleando el método de multiplicadores de Lagrange y
maximizando la siguiente expresión:
( )
−+Σ ∑
=
K
k
k,,/xpLn1
1πλµπ (93)
lo que nos lleva a:
Anexo B
162
( )( )
λµπ
µ+
Σ
Σ=∑
∑=
=
N
nK
j
jjnj
kkn
,/xN
,/xN
1
1
0 (94)
Si multiplicamos ambos lados por kπ y sumamos sobre k, haciendo uso de
las condiciones sobre kπ , nos queda que N−=λ . Empleando esto para eliminar
λ obtenemos:
N
N kk =π
(95)
Así que el coeficiente de la mixtura para la k-ésima componente, está dado
por la responsabilidad promedio que toma esa componente por explicar los puntos de
los datos.
Es digno de mencionar que los resultados obtenidos no constituyen una
solución cerrada para los parámetros del modelo de mixtura, porque las
responsabilidades ( )nkzγ dependen de los parámetros en una forma compleja. Sin
embargo, estos resultados sugieren un esquema iterativo simple para encontrar una
solución al problema de máxima verosimilitud, la cual es un ejemplo del algoritmo
EM para el caso particular del modelo de mixtura gausiana.
Primero, escogemos algún valor inicial para las medias, covarianzas y
coeficientes de mixtura. Luego, alternamos entre las dos siguientes actualizaciones
que llamaremos paso E y paso M.
En el paso E (Expectation), empleamos los valores actuales de los parámetros
para evaluar las probabilidades a posteriori o responsabilidades dadas por las
fórmulas (90) y (91). Luego, utilizamos estas probabilidades en el paso M
(Maximization) para re-estimar las medias, covarianzas y coeficientes de mixtura
usando los resultados (89), (92) y (95).
Cada actualización de los parámetros, resultante de los pasos E y M,
incrementa la función log-verosimilitud. En la práctica, el algoritmo se considera que
converge cuando el cambio en la función de verosimilitud o alternativamente de los
parámetros cae debajo de algún umbral.
El algoritmo EM para mixturas de gausianas puede resumirse en la siguiente
forma:
Dado un modelo de mixtura de gausianas, el objetivo es maximizar la función
de verosimilitud con respecto a los parámetros (medias, covarianzas y coeficientes de
la mixtura).
Algoritmo EM
163
1. Inicializar las medias kµ , covarianzas kΣ y coeficientes de mixtura kπ y
evaluar el valor inicial de la log-verosimilitud.
2. Paso E: Evaluar las responsabilidades usando los valores actuales de los
parámetros.
( ) ( )( )∑
=
Σ
Σ=
K
j
jjnj
kknk
nk
,/xN
,/xNz
1
µπ
µπγ
(96)
3. Paso M: Re- estimar los parámetros usando las responsabilidades actuales.
( )∑=
=N
n
nnk
k
nuevo
k xzN 1
1 γµ (97)
( )( )( )∑=
−−=ΣN
n
Tnuevo
kn
nuevo
knnk
k
nuevo
k xxzN 1
1 µµγ (98)
N
N knuevo
k =π (99)
donde
( )∑=
=N
n
nkk zN1
γ (100)
4 Evaluar la log-verosimilitud
( ) ( )∑ ∑= =
Σ=ΣN
n
K
k
kknk ,/xNLn,,/xpLn1 1
µπµπ (101)
y chequear la convergencia o de los parámetros o de la log-verosimilitud. Si el
criterio de convergencia no se satisface retornar al paso 2.
Anexo C
Tópicos Fundamentales de Teoría de la
Información
1 Introducción
El concepto de entropía fue introducido primero en termodinámica, donde se empleó
para enunciar la segunda ley de la termodinámica [Cover, 1991]. En el año 1930,
Hartley introdujo una medida logarítmica de la información para la comunicación.
La teoría de la información fue iniciada por Claude E Shannon en su artículo
[Shannon, 1948], éste fue el primero en definir entropía e información mutua como
se define en este capítulo y muchas de sus propiedades. La entropía relativa fue
definida primero en [Kullback, 1959] y es conocida por una variedad de nombres
entre ellos, distancia de Kullback-Leibler.
La teoría de la información es una rama de la teoría matemática de la
probabilidad y la estadística, que estudia la información y todo lo relacionado con
ella: canales, compresión de datos, criptografía, aprendizaje, etc. Forma la piedra
angular sobre la que se ha desarrollado toda la teoría actual de la comunicación y la
codificación. Por ejemplo: establece cuánto se puede comprimir la información y de
cuánto es la velocidad de transmisión de la misma, el estudio de secuencias de ADN,
código genético y otros temas relacionados.
La codificación puede referirse tanto a la transformación de voz o imagen en
señales eléctricas o electromagnéticas, como al cifrado de mensajes para asegurar su
privacidad. La necesidad de una base teórica para la tecnología de la comunicación
surgió del aumento de la complejidad y de la masificación de las vías de
comunicación tales como el teléfono, las redes de teletipo y los sistemas de
comunicación por radio. La teoría de la información abarca todas las formas de
transmisión y almacenamiento de información, incluyendo la televisión y los
impulsos eléctricos que se transmiten en las computadoras y en la grabación óptica
de datos e imágenes.
El término información se refiere a los mensajes transmitidos: voz o música
transmitida por teléfono, radio o televisión, imágenes transmitidas por sistemas de
Anexo C
166
televisión, información digital en sistemas y redes de computadoras, e incluso a los
impulsos nerviosos en organismos vivientes.
2 Cantidad de Información
El tipo de sistema de comunicación más estudiado consta de varios componentes. El
primero es una fuente de información (por ejemplo, una persona hablando) que
produce un mensaje o información que será transmitida; el segundo es un transmisor
(por ejemplo, un teléfono o un micrófono) que convierte el mensaje en señales
electrónicas o electromagnéticas. Estas señales son transmitidas a través de un canal
o medio, que es el tercer componente (por ejemplo, puede ser un cable o la
atmósfera). Este canal es especialmente susceptible a interferencias procedentes de
otras fuentes que distorsionan y degradan la señal, que son conocidas como ruido. El
cuarto componente es el receptor (por ejemplo, el de radio que transforma de nuevo
la señal recibida en el mensaje original). El último componente es el destinatario, por
ejemplo, la persona que está escuchando el mensaje.
Un concepto fundamental en la teoría de la información es la cantidad de
información contenida en un mensaje, ésta es un valor matemático bien definido y
medible. El término cantidad no se refiere a la cuantía de datos sino a la probabilidad
de que un mensaje, dentro de un conjunto de mensajes posibles sea recibido.
En lo que se refiere a la cantidad de información, el valor más alto se le
asigna al mensaje que menos probabilidad tiene de ser recibido, y si se sabe con
certeza que un mensaje va a ser recibido, su cantidad de información es 0. Cuanto
más probable es un suceso, menor cantidad de información aporta. Si por ejemplo, se
lanza una moneda al aire, el mensaje conjunto cara o cruz que describe el resultado
no tiene cantidad de información, sin embargo, los dos mensajes por separado tienen
probabilidades iguales.
Para relacionar la cantidad de información con la probabilidad, Shannon
presentó la siguiente fórmula:
)/1(log 2 pI = (102)
donde p es la probabilidad del mensaje que se transmite.
La cantidad de información puede ser entendida como el número de símbolos
posibles que representan el mensaje. En el ejemplo de la moneda se puede
representar el mensaje por 0 y 1. El 0 y el 1 son los dígitos del sistema binario, y la
elección entre estos dos símbolos corresponde a la llamada unidad de información
binaria o bit. Si se lanzara la moneda tres veces seguidas, los ocho resultados o
Tópicos Fundamentales de Teoría de la Información
167
mensajes igualmente probables pueden ser representados por 000, 001, …, ó 111; la
probabilidad de cada mensaje es de 1/8 y su cantidad de información es 3, que es el
número de bits que se necesitan para representar cada mensaje.
3 Entropía
En la mayoría de las aplicaciones prácticas, hay que elegir entre mensajes que tienen
diferentes probabilidades de ser enviados. El término Entropía ha sido definido para
designar la cantidad de información media de esos mensajes, puede ser entendida
intuitivamente como el grado de “desorden” en un sistema.
Si en un conjunto de mensajes, sus probabilidades son iguales, la fórmula
para calcular la entropía sería:
NH 2log= (103)
donde N es el número de mensajes posibles en el conjunto.
Si por ejemplo, se transmiten mensajes que están formados por
combinaciones aleatorias de las 26 letras del alfabeto inglés, el espacio en blanco y
cinco signos de puntuación, y si suponemos que la probabilidad de cada mensaje es
la misma, la entropía sería: 532log2 = , lo que significa que se necesitan 5 bits para
codificar cada caracter o mensaje. Una transmisión y almacenamiento eficiente de la
información exige la reducción del número de bits utilizados en su codificación.
Para definir formalmente la entropía de una variable, consideremos: X una
variable aleatoria discreta con posibles valores x1, …, xN, y con probabilidades
asociadas p(x1), …, p(xN), I(X) la variable aleatoria cantidad de información asociada
a X. Se define la entropía de Shannon (1948) de la variable aleatoria X, como la
esperanza matemática de la variable aleatoria I(X) asociada:
∑=
−==N
i
ii xpxpXIEXH1
2 )(log)()]([)( (104)
Si p(xi) = 0 para algún valor de i, la indeterminación se resuelve asignándole
el valor 0.
La entropía de X se interpreta como el valor esperado de )(
1log2
xp, donde X
es tomada de acuerdo a la densidad de probabilidad p(x).
Propiedades de la entropía:
1. NXH 2log)(0 ≤≤
Anexo C
168
2. 1)(0)( =∃⇔= ii xpconxXH
En particular, para una variable aleatoria discreta con dos valores, la entropía
es igual a 1 bit cuando p = ½, en este caso, la incertidumbre es máxima. Cuando p =
0 ó 1, la variable no es aleatoria y no existe incertidumbre.
4 Entropía Conjunta y Entropía Condicional
En el epígrafe anterior aparece la definición de entropía de una variable aleatoria
simple. Cuando estamos en presencia de dos variables aleatorias, se define la
entropía conjunta considerando la variable aleatoria (X,Y) como una variable simple,
luego, la entropía conjunta de un par de variables aleatorias discretas con distribución
conjunta p(x,y) se define por:
∑∑= =
−==N
i
M
j
jiji yxpyxpYXIEYXH1 1
2 ),(log),()],([),( (105)
La entropía condicional de una variable aleatoria dada otra, se define como el
valor esperado de la entropía de la distribución condicional, promediado sobre la
variable aleatoria, la siguiente fórmula expresa esta relación:
∑∑∑= ==
===N
i
M
j
ijji
N
i
ii xypyxpxXYHxpXYH1 1
21
)/(log),()/()()/( (106)
La entropía conjunta y entropía condicional se relacionan según indican las
siguientes propiedades:
1 )/()(),( XYHXHYXH +=
2 )/()/( YXHXYH ≠
3 Si X e Y son variables aleatorias independientes:
3.1 )()/( YHXYH =
3.2 )()(),( YHXHYXH +=
5 Información Mutua
La entropía de una variable aleatoria es una medida de la incertidumbre de la
variable aleatoria, es decir, es una medida de la cantidad de información promedio
requerida para describir la variable aleatoria.
La entropía relativa, es una medida de la distancia entre dos distribuciones, en
estadística ésta se ve como el esperado del logaritmo de la razón de verosimilitud
Tópicos Fundamentales de Teoría de la Información
169
(likelihood). Es una medida de la ineficiencia de asumir que la distribución es q
cuando la verdadera distribución es p. Por ejemplo, si conocemos la verdadera
distribución de la variable aleatoria, podríamos construir un código con descripción
de longitud promedio H(p). Si en su lugar, usamos un código con una distribución q,
podríamos necesitar )()( qpDpH + bits como promedio para describir la variable
aleatoria.
La entropía relativa o distancia de Kullback-Leibler entre dos probabilidades
con funciones de probabilidad p(x) y p(y) se define por:
∑=
==N
i
p
i
i
iXq
XpE
xq
xpxpqpD
122 )(
)(log
)(
)(log)()(
(107)
En la definición anterior, se usa la convención basada en la continuidad de los
argumentos que 00
log0 2 =q
y ∞=0
log2
pp .
La entropía relativa es siempre no negativa y es cero si y solo si p = q. Sin
embargo, no es realmente una distancia entre distribuciones porque no es simétrica y
no satisface la desigualdad triangular, pero frecuentemente se emplea como una
distancia entre distribuciones.
La información mutua al igual que la entropía, es una medida de gran
importancia dentro de la teoría de la información, pues define la información
aportada por una variable aleatoria sobre otra, es decir, la reducción en la
incertidumbre de una variable aleatoria debido al conocimiento de la otra. Esto se
expresa de la siguiente manera:
Sean X e Y variables aleatorias con una distribución conjunta p(x,y), y
distribuciones marginales p(x) y p(y) respectivamente. La información mutua es la
entropía relativa entre la distribución conjunta y el producto de las distribuciones, lo
cual se define según la fórmula:
),()()(
),(log),(),(
1 12 XYI
ypxp
yxpyxpYXI
N
i
M
j ji
ji
ji ==∑∑= =
(108)
Re-escribiendo la definición de información mutua y empleando propiedades
de las probabilidades se obtienen las siguientes ecuaciones que relacionan la
información mutua con la entropía.
1. )/()()/()(),( XYHYHYXHXHYXI −=−=
2. ),()()(),( YXHYHXHYXI −+=
3. )(),( XHXXI =
Anexo C
170
4. { })(),(min),(0 YHXHYXI ≤≤
Esas propiedades pueden observarse gráficamente en el siguiente diagrama de
Venn:
Figura 41. Relación entre información mutua y entropía.
Como se puede apreciar en la Figura 41, la información mutua corresponde
con la intersección de la información en X con la información en Y.
Referencias Bibliográficas
[Agrawal, 1998] Agrawal, R., Gehrke, J. Gunopulos, D. and Raghavan, P.
Automatic Subspace Clustering of High Dimensional
Data for Data Mining Applications. In Proceeding of the
ACM SIGMOD Conference, Seatle, 94 – 105 (1998).
[Ankerst, 1999] Ankerst, M., Breunig, M., Kriegel, H. P. and Sander, J.
OPTICS: Ordering Points To Identify the Clustering
Structure. ACM SIGMOD International Conference on
Management of Data. 49 – 60 (1999).
[Azuaje, 2003] Bolshakova, N., Azuaje, F. Cluster Validation
Techniques for genome expresión data. Signal
Processing, 83, 825 – 833 (2003).
[Barzily, 2008] Barzily, Z., Volkovich, Z., Akteke-Örtürk, B. and Weber,
G-W. Cluster Stability Using Minimal Spanning Trees.
International Conference 20th EURO Mini Conference
Continuous Optimization and Knowledge-Based
Technologies (EurOPT-2008), pp. 248 – 252 (2008).
[Ben Hur, 2002] Ben Hur, A.; Elisseeff, A. & Guyon, I., A stability based
method for discovering structure in clustered data.
Proceedings og the pacific Symposium on Biocomputing
pp. 6-17, (2002).
[Bertrand, 2006] Bertrand, P. and Mufti, G. B. Loevinger’s measures of
rule quality for assessing cluster stability. Computational
Statistics and Data Analysis. Vol 50, No. 4, pp. 992 –
1015 (2006).
[Bezdek, 1984] Bezdek, J. C., Ehrlich, R. and Full, W. FCM: Fuzzy c-
means algorithm. Computers and Geoscience (1984).
Referencias Bibliográficas
172
[Bezdek, 1998] Bezdek, J. C. and Pal, N. R. Some New Indexes of
Cluster Validity. IEEE Transactions on Systems, Man
and Cybernetics – Part B: Cybernetics, Vol 28 No. 3, pp.
301 – 315 (1998).
[Bishop, 2006] Bishop Christopher M. Pattern Recognition and Machine
Learning. Springer Science+Business Media. NY, USA
(2006).
[Bouguessa, 2006] Bouguessa, M., Wang, S. and Sun, H. An Objective
Approach to Cluster Validation. Pattern Recognition
Letters, 27 (13), 1419 – 1430 (2006).
[Cadez, 2001] Cadez, I. Smyth, P. and Mannila, H. Probabilistic
modelling of transactional data with applications to
Profiling, Visualization and Prediction. In Proceedings of
the 7th ACM SIGKDD, 37 – 46, San Francisco, CA,
(2001).
[Chen, 1998] Chen, C. W., Luo, J. B, y Parker, K. J., Image
Segmentation via Adaptive K-Means Clustering and
Knowledge-based Morphological Operations with
Biomedical Operations, IEEE Trans. Image Processing, 7
(12), 1673 – 1683 (1998).
[Cover, 1991] Cover, T. M. and Thomas J. A. Elements of Information
Theory. John Wiley & Sons, New York (1991).
[Cutting, 1992] Cutting, D., Karger, D., Pedersen, J. and Tukey, J.
Scatter/gather: a cluster-based approach to browsing
large document collection. In Proceeding of the 15th
ACM SIGIR Conference, 318 – 329, Copenhagen,
Denmark (1992).
Referencias Bibliográficas
173
[Davies, 1979] Davies, D. L. and Bouldin, D. W. Cluster Separation
Measure, IEEE Transactions on Pattern Analysis and
Machine Intelligence, Vol 1, No. 2, pp. 95 – 104, (1979).
[Defays, 1977] Defays, D. An efficient algorithm for a complete link
method. The Computer Journal, 20, 364 – 366 (1977).
[Dempster, 1977] Dempster, A., Laird, N. and Rubin, D., Maximum
likelihood from incomplete data via the EM algorithm.
Journal of the Royal Statistical Society, Series B, (1997).
[Dhillon, 2002] Dhillon, I., Mallela, S. and Kumar, R. Enhanced Word
Clustering for Hierarchical Text Classification, in
Proceeding of the 8th ACM SIGKDD, 191 – 200,
Edmonton, Canada (2002).
[Duda, 1973] Duda, R.O. and Hart, P.E., Pattern Classification, and
Scene Analysis. John Wiley & Sons, New York, (1973).
[Duda, 2000] Duda, R. O., Hart, P. E. & Store, D. G. Pattern
Classification. New York: Wiley (2000).
[Efron, 1982] Efron, B. The Jacknife, the Bootstrap and Other
Resampling Plans. SIAM, Philadelphia (1982).
[Ertoz, 2003] Ertoz, L., Steinbach M. and Kumar, V. Finding Clusters
of Different Sizes, Shapes and Densities in Noise (2003).
[Ester, 1996] Ester, M., Kriegel, H. P., Sander, J. and Xu, X. A
density-based algorithm for discovering clusters in large
special databases with noise. International Conference on
Knowledge Discovery and Data Mining (KDD´96). 226 –
231 (1996).
[Ester, 2000] Ester, M., Frommelt, A. and Kriegel, H-P. and Sander, J.
Spatial data mining: database primitives, algorithms and
efficient DBMS support. Data Mining and Knowledge
Referencias Bibliográficas
174
Discovery, Kluwer Academic Publishers, 4, 2 – 3, 193 –
216 (2000).
[Figueiredo, 2002] Figueiredo, M. A. and Jain, A. K. Unsupervised Learning
of Finite Mixture Models. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 24 (3), 381 – 396
(2002).
[Fischer, 2002] Fischer, B. and Buhmann, J. M. Data Resampling for
Path Based Clustering. Proceedings of the 24th DAGM
Symposium on Pattern Recognition. LNCS. Vol 2449,
pp. 513 – 518. (2003)
[Fischer, 2003a] Fischer, B. and Buhmann, J. M. Path-Based Clustering of
Smooth Curves and Texture Segmentation. IEEE
Transactions on Pattern Analysis and Machine
Intelligence. Vol 25, No. 4, pp.1411 – 1415 (2003).
[Fischer, 2003b] Fischer, B. and Buhmann, J. M. Bagging for Path-Based
Clustering. IEEE Transactions on Pattern Analysis and
Machine Intelligence. Vol 25, No. 11, pp.1411 – 1415
(2003).
[Foss, 2001] Foss, A., Wang, W. and Zaane, O. A non-parametric
approach to Web log analysis, 1st SIAM ICDM,
Workshop on Web Mining, 41 – 50, Chicago, IL (2001).
[Fowlkes, 1983] E. B. Fowlkes and C. L. Mallows, A method for
comparing two hierarchical clusterings. Journal of the
American Statistical Association , 78 (383), 553 – 584
(1983).
[Fred, 2002] Fred, A. L. N. y Jain, A. K. Data Clustering Using
Evidence Accumulation. Proc. 16th Int’l Conf. Pattern
Recognition, pp. 276 – 280 (2002).
Referencias Bibliográficas
175
[Fred, 2003] Fred, A. L. N. and Leitao, J. M. N. A New Cluster
Isolation Criterion Based on Dissimilarity Increments.
IEEE Transaction on Pattern Analysis and Machine
Intelligence, 25 (8), (2003).
[Fred, 2005] Fred, A. L. N. y Jain, A. K. Combining Multiple
Clusterings Using Evidence Accumulation. IEEE
Transactions on Pattern Analysis and Machine
Intelligence, Vol 27, No. 6, pp. 835 – 850 (2005).
[Fukunaga, 1990] Fukunaga, K., Introduction to Statistical Pattern
Recognition. Academic Press, San Diego, CA (1990).
[Fuyama, 1982] Fuyama, S., Syntactic Pattern Recognition and
Application, New Jersey Prentice-Hall, Inc (1982).
[Goil, 1999] Goil, S., Nagesh, H. and Choudhary, A. MAFIA:
Efficient and scalable subspace clustering for very large
data sets. Technical Report No. CPDC-TR-9906-010.
Center for Parallel and Distributed Computing (1999).
[Guha, 1998] Guha, S., Rastogi R. and Shim, K., CURE: An efficient
clustering algorithm for large databases. ACM
SIGMOD´98, 73 – 84.
[Guha, 1999] Guha, S., Rastogi, R. and Shim, K. ROCK: A robust
clustering algorithm for categorical attributes. IEEE
Conference of Data Engineering (1999).
[Gusarova, 2005] Yatskiv, I. and Gusarova, L. Methods of Cluster Analysis
Results Validation. Proceedings of International
Conference RelStat’ 2004. Transport and Comunication.
Vol 6, No. 1, pp 775 – 80 (2005).
[Halkidi, 2000] Halkidi, M., Vazirgiannis, M and Batistakis, Y. Quality
Scheme Assessment in the Clustering Process, Proc. of
Referencias Bibliográficas
176
the 4th European Conference on Principles of Data
Mining and Knowledge Discovery, pp. 265 – 276 (2000).
[Halkidi, 2001] Halkidi, M., Vazirgiannis, M and Batistakis, Y.
Clustering Validity Assessment: Finding the Optimal
Partitioning of a Data Set, Proc. of ICDM 2001, pp. 187
– 194 (2001).
[Halkidi, 2002a] Halkidi, M., Batistakis, Y. and Vazirgiannis, M. Cluster
validity methods part I, SIGMOD Rec., vol 31, No. 2, pp
40 – 45 (2002).
[Halkidi, 2002b] Halkidi, M., Batistakis, Y. and Vazirgiannis, M. Cluster
validity methods part II, SIGMOD Rec., vol 31, No. 3, pp
19 – 27 (2002).
[Hartigan, 1979] Hartigan, J. and Wong, M. Algorithm AS136: A k-means
clustering algorithm. Applied Statistics, 28, 100 – 108
(1979).
[Heer, 2001] Heer, J. and Chi, E. Identification of Web user traffic
composition using multimodal clustering and information
scent. 1st SIAM ICDM, Workshop on Web Mining, 51 –
58, Chicago, IL (2001).
[Hinneburg, 1998] Hinneburg, A. and Keim, D. A. An efficient Approach to
Clustering in Large Multimedia Databases with Noise.
Knowledge Discovery and Data Mining, 58 – 65 (1998).
[Jain, 1966] Jain, A. K. and Flynn, P. J. Image segmentation using
clustering. In Advances in Image Understanding: A
Festchrift for Azriel Rosenfeld, IEEE Press, 65 – 83
(1966).
[Jain, 1986] Jain, A. and Moreau, J. Bootstrap technique in cluster
analysis. Pattern Recognition, 20, 547 – 569 (1986).
Referencias Bibliográficas
177
[Jain, 1999] Jain, A. K., Murty, M. N. and Flynn, P. J. Data
Clustering: A Review. ACM Computing Surveys, Vol.
31, No. 3, 264 - 323 (1999).
[Jain, 2000] Jain, A. K., Duin, R. and Mao, J. Statistical Pattern
Recognition: A Review. IEEE Transactions on Pattern
Analysis and Machine Intelligence. Vol 22, No. 1, pp. 4 –
37 (2000).
[Jarvik, 1973] Jarvik, R. A. and Patrick, E. Clustering using a similarity
measure based on shared nearest neighbors. IEEE
Transaction on Computers, C-22 (11), (1973).
[Karypis, 1999] Karypis, E, Han, H. and Kumar, V. Chameleon: A
hierarchical clustering algorithm using dinamic
modelling. IEEE Computer, 32 (8), 68 – 75 (1999).
[Kaufman, 1990] Kaufman, L. and Rousseuw, P. J. Finding Groups in
Data: An Introduction to Cluster Analysis. Wiley, NY
(1990).
[Kittler, 1986] Kittler, J., Feature selection and extraction, In Handbook
of Pattern Recognition and Image Processing. T.Y.Young
and K.S. Fu (ed.), Academic Press, San Diego, CA pp 59
- 83, (1986).
[Kullback, 1959] Kullback, S. Information Theory and Statistics. Wiley,
New York (1959).
[Lance, 1967] Lance, G. and Williams W. A general theory of
classificatory sorting strategies. Computer Journal. 9, 373
– 386 (1967).
[Lange, 2004] Lange, T., Roth, V., Braun, M. L., Buhmann J. M.
Stability-Based Validation of Clustering Solutions.
Neural Computation 16, 1299-1323 (2004).
Referencias Bibliográficas
178
[Levine, 2001] Levine, E. & Domany, E: Resampling method for
unsupervised estimation of cluster validity. Neural
Computation, 13, 2573-2593 (2001).
[Li, 1997] Li, J. Divergence measures based on Shannon Entropy.
IEEE Transactions on Information Theory. Vol. 37, No.
1, pp. 145 – 151 (1997).
[Mac Queen, 1967] Mac Queen, J. Some Methods for Classification and
Analysis of Multivariate Observations. In Proceedings of
the Fifth Berkeley Symposium on Mathematical Statistics
and Probability, 1, 281 – 297 (1967).
[Meila, 2001a] Meila, M. and Heckerman, D. An experimental
comparison of model-based clustering methods. Machine
Learning, 42 (1/2): 9 – 29 (2001).
[Meila, 2001b] Meila, M. and Shi, J. A random walks view of spectral
segmentation. In 8th International Workshop on Artificial
Intelligence and Statistics (AISTATS).
[Merz, 1996] Merz. C.J. and Murphy, P.M., UCI Repository of
Machine Learning Databases, University of California
Irvine, (1996).
[Mufti, 2005] Mufti, G. B., Bertrand, P. and Moubarki, L. E.
Determining the number of groups from measures of
clusters validity. In Proceedings of ASMDA2005, 404 –
414 (2005).
[Murtagh, 1983] A survey of recent advances in hierarchical clustering
algorithms. Computer Journal, 26, 4, 354 – 359.
[Ng, 1994] Ng, R. and Han, J. Efficient and effective clustering
methods for special data mining. In Proceeding of the
Referencias Bibliográficas
179
20th Conference on VLDB, 144 – 155, Santiago de Chile
(1994).
[Olvera, 2005] Olvera, J.A. and Martinez, F.T., Edition schemes based
on BSE, Lectura Note in Computer Science, Progress in
Pattern Recognition Image Analysis and Applications,
10th Iberoamerican Congress on Pattern Recognition,
CIARP, pp 360 - 368, (2005).
[Pal, 1995] Pal, N. R. and Bezdek, J. C. On Cluster Validity for the
Fuzzy c- Means Model. IEEE Transactions on Fuzzy
Systems, Vol 3, No. 3, pp.370 – 379 (1995).
[Pal, 1997] Pal, N. R. and Biswas, J. Cluster Validation Using Graph
Theoretic Concepts. Pattern Recognition, 30 (6), 847 –
857 (1997).
[Pascual, 2006a] Pascual, D., Pla, F. y Sánchez, J. S. Algoritmos de
Agrupamiento. Memorias de la Jornada de seguimiento
UO – UJI. Enero 2006.
[Pascual, 2006b] Pascual, D., Pla, F. y Sánchez, J. S. Hierarchical-based
Clustering using Local Density Information for
Overlapping Distributions. Pattern Recognition Progress,
Directions and Applications. Pp. 303-312 (2006).
[Pascual, 2006c] Pascual, D., Pla, F. y Sánchez, J. S. Non Parametric
Local Density-based Clustering for Multimodal
Overlapping Distributions. 7th Int Conf on Intelligent
Data Engineering and Automated Learning 2006. LNCS
4224. Springer-Verlag, pp. 671-678 (2006).
[Pascual, 2008] Pascual, D., Pla, F. y Sánchez, J. S. Cluster Stability
Assessment based on Theoretic Information Measures.
CIARP 2008, LNCS 5197, pp. 219 – 226 (2008).
Referencias Bibliográficas
180
[Pascual, 2009] Pascual, D., Pla, F. y Sánchez, J. S. Cluster Validation
using Information Stability Measures. Pattern
Recognition Letters (aceptada para publicar).
[Rand, 1971] Rand, W. M. Objective Criteria for the Evaluation of
Clustering Methods. Journal of the American Statistical
Association, vol 66, No. 336, pp. 846 – 850 (1971).
[Rezae, 1998] Rezae, R., Lelieveldt, B. P. F. and Reiber, J. H. C. A new
Cluster Validity Index for the Fuzzy c-Mean. Pattern
Recognition Letters, 19, 237 – 246 (1998).
[Roth, 2002] Roth, V., Lange, T., Braun, M. y Buhmann, J. A
Resamplig Approach to Cluster Validation. In Proc.
COMPSTAT02, Internatioonal Conference on
Computational Statistics, pp. 123 – 128 (2002).
[Rousseeeuw, 1987] Rousseeuw, P. J. Silhouttes: A Graphical Aid to the
Interpretation and Validation of Cluster Analysis. Journal
of Computational and Applied Mathematics. 20, 53 – 65
(1987).
[Salton, 1980] Salton, G. Automatic Information Retrieval. Computer
Publication. Vol 13, No. 9, pp. 41 – 56 (1980).
[Schikuta, 1996] Schikuta, E. Grid-clustering: a fast hierarchical clustering
method for very large data sets. In Proceedings 13th
International Conference on Pattern Recognition, 2, 101
– 105 (1996).
[Schikuta, 1997] Schikuta, E., Erhart, M. The BANG-clustering system:
grid-based data analysis. In Proceeding of Advances in
Intelligent Data, IDA´97, London, UK, 513 – 524 (1997).
[Shannon, 1948] Shannon C. E. A Mathematical Theory of Comunication.
The Bell System Technical Journal, 379 – 423 (1948).
Referencias Bibliográficas
181
[Shi, 2000] Shi, J. and Malik, J. Normalized cuts and image
segmentation. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 22 (8), 888-905 (2000).
[Shulcloper, 2002] Shulcloper, J.R., Formación Integral de Especialistas en
Reconocimiento de Patrones, Research on Computing
Science, Reconocimiento de Patrones Avances y
Perspectivas, VII Congreso Iberoamericano de
Reconocimiento de Patrones, CIARP, pp 245 - 256,
(2002).
[Sibson, 1973] Sibson, R. SLINK: An optimally efficient algorithm for
the single link cluster method. Computer Journal, 16, 30
– 34 (1973].
[Stanfill, 1986] Stanfill, C. and Waltz, D., Toward memory-based
reasoning. Communications of the ACM, 29, pp 1213 -
1228, (1986).
[Sugar, 1998] Sugar, C. Techniques for clustering and classification
with applications to medical problems, PhD. Dissertation
Stanford University, Stanford 81998).
[Sugar, 1999] Sugar, C. Lenert, L. and Olshen, R. An Application of
cluster analysis to health services research: empirically
defined health states for depression from the sf-12.
Technical Report Stanford University. Stanford (1999).
[Thanh, 2003] Thanh, T., N., Wehrens, R. y Widen, L. M. C. KNN
Density-Based Clustering for High Dimensional
Multispectral Images. Segunda GRSS/ISPRS Joint
Worshop on Remote Sensing and Data Fusion over
Urban Areas, URBAN 3002, Berlin (2003)
Referencias Bibliográficas
182
[Tibshirani, 2001] Tibshirani, R., Walter G. & Hastie, T. Estimating the
number of clusters in a dataset via the gap statistic. J.
Royal Statist. Soc. B, 32 (2), 411-423 (2001).
[Tibshirani, 2005] Tibshirani, R. and Walter G. Journal of Computational &
Graphical Statistics 14, 511-528 (2005).
[Vázquez, 2005] Vázquez, F. D., Sánchez, J. S. and Pla, F. A stochastic
approach to Wilson´s editing algorithm. Pattern
Recognition and Image Analysis, LNCS, Springer-
Verlag, 3523, 35 – 42 (2005).
[Vázquez, 2008] Vázquez, F. D. Tesis Doctoral. Universidad Jaume I,
Castellón, España (2008).
[Ward, 1963] Ward, J. H. Hierarchical Grouping to Optimize an
Objective Function. Journal of the American Statistical
Association, . 58, 301, 236 – 244 (1963).
[Watanabe, 1985] Watanabe, S., Pattern Recognition: Human and
Mechanical-Wiley. New York (1985).
[Wilson, 2000] Wilson, D.R. and T.R. Martinez, Reduction techniques
for instance based learning algorithms, Mach Learn 38,
pp 257 - 286, (2000).
[Xiao, 2005] Xiao, G. Y and Yin, J. A New Clustering Algorithm
Based on KNN and DENCLUE. Proceeding of the 4th
International Conference on Machine Learning and
Cybernetics, 18 – 25 (2005).
[Xu, 1998] Xu, X., Ester, M. and Kriegel, H-P. and Sander, J. A
distribution-based clustering algorithm for mining large
spatial datasets. In Proceedings of the 14th ICDE, 324 –
331, Orlando, FL. (1998).
Referencias Bibliográficas
183
[Xu, 2002] Xu, Y., Olman, V. and Xu, Do. Clustering gene
expression data using a graph-theoretic approach: an
application of minimum spanning trees. Bioinformatics
Vol. 18, No. 4, pp. 536 – 545 (2002).
[Yeung, 2001] Yeung, K. Y. Haynor, D. R. and Ruzzo, W. L. Validating
clustering for gene expression data. Bioinformatics Vol
17 No. 4, 309 – 318 (2001).
[Zahn, 1971] Zahn, C. T. Graph Theoretical Methods for Detecting and
Describing Gestalt Clusters. IEEE Transactions on
Computer, 20, 1, 68 – 86 (1971).
[Zeev, ] Zeev, V., Zeev, B, Basak, A-O and Wilhelm, G. Cluster
Stability Using Minimal Spanning Trees.
[Zhai, 2004] Zhai, C. and Lafferty, J. A study of smoothing methods
for language models applied to information retrieval.
ACM Transactions on Information Systems (TOIS), Vol
22, No. 2, pp. 179 – 214 (2004).
[Fukunaga, 1990] Fukunaga, K., Introduction to Statistical Pattern
Recognition. Academic Press, San Diego, CA (1990).
[Yarowsky, 1995] Yarowsky, D., Unsupervised work sense disambiguation
rivaling supervised methods. Proceeding of the 33rd
Annual Meeting of the Association for Computational
Linguistics, pp 189 - 196, (1995).