View
5
Download
0
Category
Preview:
Citation preview
Analisis de algoritmos de clusteringpara datos categoricos
Juan Felipe Ceron Uribe
Proyecto de grado de Matematicas
Asesor: Adolfo Jose Quiroz SalazarDepartamento de Matematicas
Universidad de los AndesBogota, Colombia
5 de diciembre de 2018
Analisis del ROCKy otros algoritmos de clustering
de datos categoricos
Juan Felipe Ceron Uribe
Resumen
En el campo de la estadıstica, el analisis de clusters se puede definir como la
tarea de encontrar grupos relevantes de una poblacion a partir de una muestra, de
modo que los miembros de cada grupo sean mas similares entre si que con respecto a
los miembros de otros grupos en algun sentido. Nuestro objetivo principal para este
proyecto fue analizar algoritmos de clustering adaptados a datos con atributos ca-
tegoricos. Con este fin, realizamos una lectura crıtica del planteamiento del algoritmo
ROCK, un algoritmo moderno basado en la atractiva idea de considerar la vecindad
que rodea a cada uno de los datos. Finalmente, propusimos una modificacion a este
algoritmo y comparamos su desempeno con el original (y otros algoritmos clasicos
de clustering) mediante conjuntos de datos simulados.
Agradecimientos
Gracias a mis papas, a mis amigos y a mis hermanos por hacer de mi mundo un
lugar feliz y tranquilo. A Adolfo Quiroz, gracias por guiarme en este y tantos otros
proyectos academicos; te debo mucho.
iii
Indice general
Abstract ii
Acknowledgements iii
1. El problema de analisis de clusters 1
1.1. Definiciones del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1. Homogeneidad y separacion . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2. Identificacion de subpoblaciones . . . . . . . . . . . . . . . . . . . . 4
1.1.3. El problema de plantear el problema . . . . . . . . . . . . . . . . . 5
1.2. Clasificacion del analisis de clusters . . . . . . . . . . . . . . . . . . . . . . 6
1.3. Algoritmos Clasicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1. Algoritmos jerarquicos . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2. Clustering the k medias . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Determinacion del numero de clusters . . . . . . . . . . . . . . . . . . . . . 11
1.5. Medidas de similaridad de datos categoricos . . . . . . . . . . . . . . . . 13
2. ROCK: Un algoritmo robusto de clustering de datos categoricos 16
2.1. Modelos de clusters de canastas de mercado . . . . . . . . . . . . . . . . 17
2.2. Caracterizacion de homogeneidad y separacion . . . . . . . . . . . . . . . 18
2.2.1. El numero de enlaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2. Criterio de bondad de un clustering . . . . . . . . . . . . . . . . . 20
2.2.3. Aproximacion de E[links(C)] . . . . . . . . . . . . . . . . . . . . . . . 20
2.3. Algoritmo aglomerativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4. Reevaluacion de la aproximacion de E[links(C)] . . . . . . . . . . . . . . . 23
2.4.1. Factibilidad del modelo . . . . . . . . . . . . . . . . . . . . . . . . . 23
iv
Indice general v
2.4.2. Calculo de E[links(C)] . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5. Modificacion del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3. Comparacion de algoritmos de clustering de datos categoricos 31
3.1. Distancia entre clusterings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.1. El concepto de entropıa . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.2. La entropıa condicional . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.3. La variacion de la informacion . . . . . . . . . . . . . . . . . . . . . 36
3.2. Enunciado del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3. Descripcion de las simulaciones . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4. Algoritmos a comparar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6. Discusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.1. Single linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.2. Complete linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.3. Average linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6.4. CROCK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6.5. ROCK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 de diciembre de 2018
Indice de figuras
1.1. Dendrogramas del clustering de la base de datos simulada obtenidos
a partir de single, average y complete linkage. . . . . . . . . . . . . . . . 8
1.2. Dendrograma de la ejecucion de complete linkage sobre un conjunto
de datos de distribucion normal, la mitad con media 0 y la otra con
media 50. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Suma interna de cuadrados total en el resultado del algoritmo de
k-medias. Los datos corresponden a una mezcla de 4 distribuciones
normales con medias 10, 20, 30 y 40. . . . . . . . . . . . . . . . . . . . . . . 11
2.1. Valores empıricos de links(C)/ logn para clusters de cada modelo,
con θ fijo y n variable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2. Error relativo del numero de links observado en cada uno de los clus-
ters simulados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1. Ultimas 25 aglomeraciones de la ejecucion de average linkage con el
numero de enlaces como medida. . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2. Comparacion del ındice V I del resultado de cada algoritmo al variar
el tamano del conjunto de datos. . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3. Comparacion del ındice V I del resultado de cada algoritmo al variar
el grado de exclusividad de cada cluster. . . . . . . . . . . . . . . . . . . . 44
3.4. Indice V I del resultado de cada algoritmo en cuatro escenarios de
sobrerrepresentacion de algunas de las poblaciones. . . . . . . . . . . . 46
vi
Capıtulo 1
El problema de analisis de clusters
Este capıtulo es una introduccion a la teorıa basica del analisis de clusters. Da-
do que este tipo de problema suele presentarse informalmente, comenzaremos por
presentar algunas de las formas disponibles en la literatura de definirlo con rigor ma-
tematico. En particular, estableceremos definiciones de cluster y de clustering. Luego
presentaremos algunos algoritmos comunes de clustering. Finalmente, discutiremos
las caracterısticas de diferentes medidas de similaridad entre datos categoricos. Es-
to ultimo servira de introduccion al contexto del clustering de datos con atributos
categoricos, que es el tema central de este trabajo.
Para este capıtulo, considere X un multiconjunto de datos en Rd de tamano n
(contando multiplicidades).
1.1. Definiciones del problema
El analisis de clusters o clustering se puede describir informalmente como la
tarea de presentar una particion informativa de un conjunto de datos. Formalmente:
Definicion 1.1 Sea X un multiconjunto de datos. Un clustering de X es una particion
de X . Llamamos clusters a cada uno de sus elementos.
Para facilitar el lenguaje a lo largo de este trabajo, en adelante utilizaremos los
terminos conjunto y subconjunto para referirnos a multiconjuntos y submulticonjuntos
de datos u observaciones.
1
1.1. Definiciones del problema 2
Notablemente, la anterior descripcion no delimita el problema satisfactoriamente;
¿que tipo de particion estamos buscando? Existen varias posibilidades porque la
necesidad de particiones informativas ha surgido en varios contextos. De modo que
se tienen varias formas de especificar (totalmente) el problema, ninguna de las cuales
pretende ser aplicable en todos los contextos de lo que actualmente se considera
analisis de clusters.
A lo largo de la literatura consultada, existen dos perspectivas principales a par-
tir de las cuales es posible formalizar el problema. La primera consiste en buscar un
clustering que maximice criterios tanto de cohesion interna como de mutua exclusion
de los clusters. La segunda consiste en identificar subpoblaciones en la distribucion
de la cual provienen los datos. En las proximas subsecciones citaremos algunas de
las definiciones formales que surgen a partir de cada una de estas perspectivas. Fi-
nalmente discutiremos La dificultad de plantear un problema matematico de analisis
de clusters que se adapte a las necesidades de una aplicacion en particular.
1.1.1. Homogeneidad y separacion
Varios criterios de la calidad de un clustering se basan en los conceptos de
homogeneidad y separacion. En un clustering, el primero se refiere a la cohesividad
interna de cada uno de los clusters, y el segundo a su mutuo aislamiento. Podemos
juzgar la calidad de un clustering a traves de ındices que midan estas propiedades.
En el cuadro 1.1 citamos algunos de estos ındices, los cuales se definen a partir de
una medida de disimilitud entre datos δ ∶ X × X → R. Con respecto a la seleccion
de la ultima, Gower y Legendre senalan que esta debe estar bien adaptada a la
naturaleza de los datos y al tipo de analisis que se pretende realizar [5].
Los primeros; h1, h2 y h3, miden la heterogeneidad, o ausencia de homogeneidad
de un cluster. Los ultimos; s1 y s2, miden la separacion de un cluster del resto en una
particion. La agregacion de estos ındices a traves de los clusters de un clustering
resulta en indicadores de la homogeneidad y de separacion del mismo. Cualquiera
de estos, o una agregacion de ellos, podrıa utilizarse para formalizar el problema de
analisis de clusters:
5 de diciembre de 2018
1.1. Definiciones del problema 3
Criterio Medida de
h1(C) = ∑p,q∈C
δ(p, q) Heterogeneidad
h2(C) = maxp,q∈C
δ(p, q) Heterogeneidad
h3(C) = mınp∈C∑q∈C
δ(p, q) Heterogeneidad
s1(Ci) = ∑p∈Ci∑j/=i∑q∈Cj
δ(p, q) Separacion
s2(Ci) = mınp∈Ci,q∈Cj
j/=i
δ(p, q) Separacion
Cuadro 1.1: Criterios de bondad de un cluster C de un clustering C = {C1, . . . ,Ck},segun los describe Everitt [1].
Ejemplo 1.1 Dado un conjunto de datos X y k ∈ N, hallar el clustering C = {C1, . . . ,Ck}que minimice
c1(C) = ∑C∈C
h(C).
En el anterior ejemplo buscamos un clustering de tamano k de clusters altamente
homogeneos. Existe una descripcion famosa del problema que sigue este formato,
conocida como el clustering the k medias:
Ejemplo 1.2 Dado un conjunto de datos x1, . . . , xn ∈ Rd y k ∈ N, hallar el clustering
C = {C1, . . . ,Ck} que minimice la suma interna de cuadrados en los clusters. Esta
esta dada por
c2(C) = ∑C∈C
∑x∈C
∥x − µC∥2,
donde µC es el promedio de los puntos de C .
En este la medida de heterogeneidad h(C) es la suma de cuadrados interna de
cada cluster. Tambien es posible formular criterios que tengan en cuenta tanto la
homogeneidad como la separacion de los clusters.
Ejemplo 1.3 Dado un conjunto de datos X y α,β ∈ R≥0, hallar el clustering C ={C1, . . . ,Ck} que minimice
c3(C) = α maxi=1,...,k
h(Ci) − β mıni=1,...,k
s(Ci).
5 de diciembre de 2018
1.1. Definiciones del problema 4
1.1.2. Identificacion de subpoblaciones
Desde esta perspectiva, el problema de analisis de clusters consiste en identificar
las clases naturales de individuos en la poblacion de la cual provienen los datos, si es
que estas existen [12]. Siguiendo este paradigma, Meila y Heckerman [8] presentan
el problema de analisis de clusters mediante su modelo de clustering, en el cual, si
X se compone de observaciones de la variable aleatoria X , la distribucion de esta
ultima es de la forma
P (X ∈ A) =k
∑i=1
λiP (X ∈ A∣clase = i) (1.1.1)
k
∑i=1
λi = 1 , λi > 0.
El problema se describe entonces como, dada la muestra X , encontrar el modelo
(numero de clases y distribucion de cada una) que mejor se acomode a la muestra
segun algun criterio. En el siguiente ejemplo veremos una instancia de este problema,
tomado del libro de Duda [10].
Ejemplo 1.4 Suponga que la muestra X proviene de la densidad mezclada
pX(x, θ) =k
∑i=1
pX(x∣ci, θi)P (ci)
acerca de la cual:
Conocemos el numero de clases y la probabilidad P (ci) de pertenencia a cada
clase.
Conocemos la forma de cada funcion de densidad pX(x∣ci, θi), dependiente de
ci y θi.
No conocemos ninguno de los parametros θi.
Estime el vector de parametros θ. Una aproximacion natural a este problema es
buscar el vector de parametros θ que maximiza la funcion de verosimilitud de los
datos.
En muchas aplicaciones del analisis de clustering, definir a priori la forma de la
distribucion de cada clase, como se hace en el ejemplo anterior, puede no ser factible.5 de diciembre de 2018
1.1. Definiciones del problema 5
Sin embargo, de no imponer restricciones sobre las distribuciones P (X ∈ A∣clase = i),las soluciones que encontremos para el problema de clustering (segun lo plantea
Meila) son vulnerables al sobreajuste. Suponga, por ejemplo, que seleccionamos
cualquier particion C1, . . . ,Ck de X y, para cada Ci, declaramos que este corresponde
a los representantes de una clase (es un cluster). Luego afirmamos que la distribucion
de esta clase es la distribucion muestral de Ci. Bajo muchos criterios, incluyendo la
maxima verosimilitud, el modelo se ajusta mejor a los datos que cualquier modelo con
densidades continuas. Sin embargo, esta metodologıa no describira una estructura
presente en la distribucion de los datos en casi ningun caso.
Una forma de restringir estas distribuciones es exigirles cierto tipo de suavidad.
Teniendo esto en cuenta, la optimizacion de criterios de homogeneidad y separacion
se puede ver como una heurıstica para encontrar las subpoblaciones presentes en una
muestra. En este caso nos limitarıamos a la busqueda de subpoblaciones unimodales
y bien separadas entre si.
1.1.3. El problema de plantear el problema
En la mayorıa de sus aplicaciones por fuera de las matematicas, un investigador
aplica el analisis de clusters para ganar alguna intuicion util sobre un conjunto
de datos. Sin embargo, puede ser imposible dar una nocion general de lo que un
investigador considere util. Por esta razon, varios autores coinciden en que una
definicion formal del analisis de clusters no vendrıa al caso. Bonner [2], por ejemplo,
considera que una concepcion de cluster o de clustering es buena si produce una
respuesta valiosa para un investigador.
Hemos visto varios ejemplos de como plantear matematicamente un problema
de analisis de clustering. Sin embargo, en cualquier contexto de aplicacion, una de
las dificultades principales es precisamente especificar un problema matematico de
analisis de clusters cuya solucion sea subjetivamente valiosa para el investigador.
En este sentido se podrıa decir que el problema de analisis de clusters consiste en
primero plantear el problema matematicamente, y despues resolverlo.
5 de diciembre de 2018
1.2. Clasificacion del analisis de clusters 6
1.2. Clasificacion del analisis de clusters
El analisis de clusters pertenece a la categorıa de aprendizaje no supervisado. En
este tipo de problema se busca describir la estructura de un conjunto de datos que no
cuentan con una clasificacion. Otros ejemplos de esta son el analisis de componentes
principales (PCA) y el aprendizaje por refuerzo (mejor conocido como reinforcement
learning).
Tambien guarda una relacion con el problema de clasificacion estadıstica, pues un
clustering puede verse tambien como una clasificacion de los datos. Sin embargo es
importante tener en cuenta que una poblacion puede tener muchas subclasificaciones
relevantes. Por ejemplo, una poblacion de personas se puede clasificar segun su
etnicidad, grupo de edad, nivel de ingreso economico, etc. Por esta razon, juzgar
la calidad de un clustering mediante una clasificacion preexistente en los datos no
siempre es apropiado.
1.3. Algoritmos Clasicos
En esta seccion discutimos algunos algoritmos clasicos de clustering. Recuerde
que X es un multiconjunto de datos en Rd de tamano n (contando multiplicidades).
1.3.1. Algoritmos jerarquicos
Se trata de una familia de algoritmos que generan iterativamente una secuencia
de clusterings C1, . . . ,Cn de X donde Ck se obtiene de Ck+1 al unir dos de sus
elementos ∀k = 1, . . . ,m − 1. En particular C1 = {X} y Cn = {{x} ∶ x ∈ X}. Estos
buscan optimizar heurısticamente medidas de homogeneidad y separacion en los
clusterings resultantes mediante algoritmos greedy, los cuales se caracterizan por
tomar desiciones localmente optimas en la busqueda de un optimo global. En el
caso de los algoritmos jerarquicos estas desiciones locales pueden ser aglomerar
dos clusters o dividir uno en dos, con la expectativa de al final obtener un clustering
que maximice alguna medida globalmente.
Esta categorıa se subdivide en metodos aglomerativos y divisivos:
5 de diciembre de 2018
1.3. Algoritmos Clasicos 7
Algoritmo aglomerativo
Aglomera puntos cercanos de X sucesivamente segun alguna nocion de distancia
entre clusters D ∶ 2X × 2X → R (no necesariamente es una metrica). El siguiente
algoritmo fue tomado del libro de Hardle [12]:
1. Inicialmente declarar que cada observacion en X es un cluster de un elemento.
Se obtiene un primer clustering C de X .
2. Calcular la distancia D entre cada par de clusters en C.
3. Encontrar dos clusters con la menor distancia D y juntarlos.
4. Iterar sobre los pasos 2, 3 y 4 hasta haber combinado todas las observaciones
en un solo cluster.
La mayorıa de distancias entre clusters D en la literatura provienen de una
distancia entre puntos δ ∶ Rd × Rd → R. Esta, a su vez, suele tomarse como la
distancia euclidiana. Sean C1,C2 ∈ 2X , algunas formas comunes de definir D, vistas
en el libro de Everitt [1], son:
Single linkage: D(C1,C2) = mın{δ(x, y) ∶ x ∈ C1, y ∈ C2}.
Complete linkage: D(C1,C2) = max{δ(x, y) ∶ x ∈ C1, y ∈ C2}.
Average linkage: D(C1,C2) = 1∣C1∣∣C2∣
∑x∈C1,y∈C2δ(x, y).
Centroid : Podemos definir el centroide de Ci como µ(Ci) = 1∣Ci∣∑x∈Ci x. A partir
de esto definimos D(C1,C2) = δ(µ(C1), µ(C2)).
Median: D(C1,C2) = δ(c(C1), c(C2)) donde c se define ası: Si en una iteracion
unimos C1 y C2 para formar C3, entonces c(C3) = c(C1)+c(C2)
2 . Para un singleton
definimos c({x}) = x. Esto previene que los elementos del cluster mas numeroso
entre C1 y C2 dominen a los elementos del otro.
5 de diciembre de 2018
1.3. Algoritmos Clasicos 8
Algoritmos divisivos
Los algoritmos divisivos proceden en el orden contrario; dividiendo un elemento
de la actual particion de X en dos en cada iteracion. No discutimos ningun algoritmo
divisivo pues son poco comunes en la literatura.
Dendrogramas
El procedimiento habitual tras la ejecucion de estos algoritmos es visualizar la
estructura jerarquica de particiones resultante. Esto es posible mediante un den-
drograma; un diagrama en forma de arbol que muestra cada aglomeracion o division
realizada durante la ejecucion y el valor de D entre los clusters aglomerados, lo cual
se conoce como su altura.
A modo de ejemplo presentamos los dendrogramas obtenidos al aplicar los algo-
ritmos de single, average y complete linkage a un conjunto de datos cuyos primeros
10 elementos son observaciones de la distribucion normal estandar y los siguientes
10 de la normal con media 3 y desviacion estandar 5.
Figura 1.1: Dendrogramas del clustering de la base de datos simulada obtenidos a
partir de single, average y complete linkage.
El comportamiento observado en los dendrogramas es el tıpico al comparar estos
algoritmos. En single linkage los clusters grandes tienden a unirse rapidamente y
5 de diciembre de 2018
1.3. Algoritmos Clasicos 9
los puntos mas lejanos son aislados hasta el final. Esto nos impide identificar las dos
poblaciones presentes en el conjunto de datos, pero puede ser util para identificar
datos aislados o outliers. Complete linkage favorece clusters de tamano similar en
cada particion. Average linkage es un punto intermedio entre single y complete
linkage en cuanto al tamano relativo de los clusters que se forman.
Seleccion de una particion
El clustering jerarquico resulta en una estructura de varias particiones, de las
cuales nos interesa elegir una por como hemos planteado el problema de clustering.
En la seccion 1.4 discutiremos algunos metodos formales para determinar el numero
de clusters que existe en la muestra. Ahora veremos como utilizar el dendrograma
informalmente para este proposito.
Esta tecnica consiste en identificar las lıneas verticales mas largas en el dendro-
grama, y declarar que lo que hay debajo de cada una es un cluster. La longitud de
cada vertical representa el cambio de altura entre la aglomeracion que conformo a un
cluster y la que lo unirıa a otro. Entonces una vertical larga indica que la siguiente
aglomeracion de un cluster (los elementos debajo de la linea) implico una perdida
de cohesividad relativamente mayor a las aglomeraciones que lo conformaron.
Para ejemplificar este proceso simulamos un conjunto de 40 datos provenientes
de distrubuciones normales de varianza 1, la mitad con media 0 y la otra mitad
con media 50. La figura 1.2 muestra el dendrograma obtenido de la ejecucion de
complete linkage sobre estos datos. Note que los cambios de altura asociados a
las aglomeraciones de cada submuestra son pequenos con respecto al cambio de
altura asociado a la aglomeracion de las dos, lo cual ocurre en el ultimo paso.
Esto nos indica que en la penultima iteracion del algoritmo quedaban dos clusters
internamente cohesivos y mutuamente separados, lo cual como vimos es un criterio
comun en el analisis de clusters.
1.3.2. Clustering the k medias
Este termino se utiliza para referirse tanto a un problema de analisis de clus-
tering, como a su solucion heurıstica mas conocida. En este problema, buscamos un5 de diciembre de 2018
1.3. Algoritmos Clasicos 10
Figura 1.2: Dendrograma de la ejecucion de complete linkage sobre un conjunto de
datos de distribucion normal, la mitad con media 0 y la otra con media 50.
clustering C de X que minimice la suma interna de cuadrados de cada cluster, es
decir, buscamos
arg mın∣C∣=k∑C∈C
∑x∈C
∥x − µC∥2.
Como antes, µC es el promedio de las observaciones del cluster C . Este problema es
NP-complejo, sin embargo se han planteado algoritmos heurısticos de complejidad
computacional razonable. El algoritmo estandar se conoce como el algoritmo de k
medias. En este, los clusters Ci ∈ C son representados por sus medias µC . Dado
un conjunto inicial de centroides m1, . . . ,mk, el algoritmo consiste en la iteracion
de un paso de asignacion, seguido de un paso de actualizacion, hasta alcanzar la
convergencia:
Paso de asignacion: Asignar cada x ∈ X al cluster cuyo centroide se encuentra
a menor distancia euclidiana de x.
Paso de actualizacion: Calcular el promedio de cada cluster y actualizar los
centroides con estos valores, es decir, mi ← µCi .
Consideramos que el algoritmo ha convergido cuando las nuevas asignaciones no
cambian el conjunto de centroides. En cuanto a la eleccion inicial del conjunto de
centroides, los metodos mas comunes son la eleccion aleatoria de k elementos de X , y
la particion aleatoria de X en k clusters, seguida de un paso inicial de actualizacion.
5 de diciembre de 2018
1.4. Determinacion del numero de clusters 11
1.4. Determinacion del numero de clusters
En muchas de las aplicaciones del analisis de clusters, no se tiene una preferencia
sobre el tamano k que debe tener el clustering resultante. Existen metodos formales
e informales de seleccion del parametro k, comenzaremos por uno informal.
Si contamos con un algoritmo de clustering que tiene a k como parametro, una
estrategia razonable es obtener clusterings de varios tamanos (por ejemplo a traves
del metodo de k-medias) y compararlos segun alguna medida de homogeneidad. Sin
embargo, la gran mayorıa de medidas de homogeneidad disponibles en la literatura
decrecen trivialmente a medida que incrementamos k; mientras mas clusters podamos
formar, mayor sera la homogeneidad interna de cada uno. La figura 1.3 ejemplifica
este fenomeno en la aplicacion del algoritmo de k-medias.
Figura 1.3: Suma interna de cuadrados total en el resultado del algoritmo de k-
medias. Los datos corresponden a una mezcla de 4 distribuciones normales con me-
dias 10, 20, 30 y 40.
El conjunto de datos que corresponde a esta figura es una mezcla de 4 distribu-
ciones normales. En esta, note que la disminucion en la suma interna de cuadrados
al aumentar k en 1 se hace muy pequena para k ≥ 4. Esto implica que los clusters
obtenidos no se hacen mucho mas homogeneos de lo que ya eran al aumentar k mas
5 de diciembre de 2018
1.4. Determinacion del numero de clusters 12
alla de 4, y por lo tanto sugiere la seleccion informal de k = 4. Podemos aplicar este
metodo siempre que contemos con una medida de homogeneidad bien adaptada al
problema en cuestion.
En cuanto a metodos formales de seleccion de k, Milligan y Copper [9] realizaron
un extenso analisis comparativo, incluyendo 30 procedimientos diferentes. La mayorıa
de estos son aplicables unicamente si los datos toman valores continuos. Ya que este
trabajo esta dirigido al clustering de datos con atributos categoricos, presentaremos
el ındice con el mejor desempeno segun el estudio de Milligan y Copper que ademas
es aplicable a este tipo de datos.
El ındice Gamma de Baker-Hubert se basa en el ordenamiento de las similia-
ridades entre cada par de puntos en el conjunto de datos. Este se define, para un
clustering C de un conjunto de datos X dada una medida de similaridad entre datos
s. Sea a el vector de similaridades sij entre parejas de datos en X . Un segundo
vector b es un vector binario de la misma longitud de a tal que, en la coordenada
que corresponde al par (i, j) de datos, este es 1 si los datos pertenecen al mismo
cluster en C, y 0 de lo contrario.
Definicion 1.2 Sean a y b dos vectores de igual longitud. Para dos ındices i y j,
decimos que (i, j) son concordantes si ai < aj∧bi < bj , o discordante si ai < aj∧bi > bj .
En otras palabras, C cuenta el numero de ocasiones en las cuales una pareja de
datos del mismo cluster en C es mas similar que una pareja de diferentes clusters.
Analogamente, D cuenta en numero de ocasiones en las cuales dos datos de dife-
rentes clusters son mas similares entre si que dos que estan en el mismo cluster. Ya
que es deseable un clustering en el cual el mayor grado de similaridad se encuen-
tra entre parejas de datos del mismo cluster, es quisieramos que C sea grande con
respecto a D.
Definicion 1.3 Sean a y b vectores como los describimos anteriormente (a es el vector
de similaridades, . . . ). Sea C el numero de pares de ındices concordantes entre a y
b, y D el numero de pares discordantes. El ındice de Gamma de Baker-Hubert del
clustering C y la medida s esta dado por
Γ(C, s) = C −DC +D.
5 de diciembre de 2018
1.5. Medidas de similaridad de datos categoricos 13
Este ındice toma valores en [−1,1]. Su valor maximo corresponde a la situacion
en la cual la similaridad entre cualquier pareja de puntos de un mismo cluster es
mayor a la de cualquier pareja de puntos de clusters diferentes. Para utilizarlo como
regla de desicion del parametro k (el numero de clusters presentes en un conjunto
de datos), primero obtenemos el clustering optimo para varios tamanos ∣Cj ∣ = j. Luego
seleccionamos k como
arg mınj
Γ(Cj, s).
1.5. Medidas de similaridad de datos categoricos
La gran mayorıa de los metodos de clustering disponibles en la literatura parten
de una nocion de similaridad entre las observaciones en X . De modo que contar con
una que refleje la similaridad intuitiva entre dos datos juega un papel fundamental
en el analisis de clustering, considerando que queremos que los clusters resultantes
sean intuitivamente similares internamente.
En una proporcion considerable de las aplicaciones del analisis de clusters, el
conjunto de observaciones se compone de vectores de variables categoricas. El si-
guiente ejemplo busca ilustrar la importancia de elegir una nocion de similaridad
bien adaptada a las caracterısticas de los datos, en lugar de utilizar la distancia
euclidiana por defecto.
Ejemplo 1.5 Suponga que las observaciones de X ⊂ {0,1}3 corresponden a los pro-
ductos comprados por los clientes de un supermercado que ofrece tres productos,
donde un 1 en la coordenada i significa que el cliente adquirio el producto i. Con-
sidere las observaciones x = (1,0,0), y = (0,0,1), u = (1,1,0) y v = (0,1,1). Si d es
la distancia euclidiana tendremos que
d(x, y) = d(u, v) =√
2.
Sin embargo, las transacciones u y v tienen un producto en comun, mientras que x
y y no tienen nada en comun. De modo que, intuitivamente, dirıamos que u y v son
mas similares entre si que x y y, lo cual no es reflejado por la distancia d.
5 de diciembre de 2018
1.5. Medidas de similaridad de datos categoricos 14
Una variable categorica X de c categorıas se puede expresar como un vector
binario Xb ∈ {0,1}c, donde Xbi = 1 ⇐⇒ X = i. Por esta razon restringiremos esta
discusion a vectores binarios. Sean x y y vectores binarios de dimension n.
Para este tipo de datos, tal vez el factor mas importante que diferencia a una
medida de similaridad de otra es el efecto de las coincidencias xi = yi = 0. Por
ejemplo, en el contexto de las transacciones de un supermercado que ofrece miles
de productos, que dos transacciones coincidan en la no compra de un producto (xi =yi = 0) no las hace tan similares como la coincidencia en una compra (xi = yi = 1). En
cambio, si los datos representan una encuesta de preguntas de respuesta positiva o
negativa, es razonable que cualquier coincidencia, sea negativa o positiva, tenga el
mismo peso sobre el nivel de similaridad.
Por lo discutido anteriormente, las medidas de similaridad presentadas en el
cuadro 1.2 se expresan en terminos de los siguientes conteos:
a es el numero de ındices i tales que xi = yi = 1.
b es el numero de ındices i tales que xi = 1 ∧ yi = 0.
c es el numero de ındices i tales que xi = 0 ∧ yi = 1.
d es el numero de ındices i tales que xi = yi = 0.
Medida Formula
S1: Coeficiente de coincidencia (a + d)/(a + b + c + d)S2: Coeficiente de Jaccard a/(a + b + c)S3: Rogers y Tanimoto (a + d)/[a + 2(b + c) + d]S4: Sneath y Sokal a/[a + 2(b + c)]
Cuadro 1.2: Medidas de similaridad entre datos binarios descritas por Everitt [1].
El coeficiente de coincidencia describe la proporcion de coincidencias sobre el
numero total de bits. Es aplicable cuando la ausencia de un bit en x y y es tan infor-
mativa como su presencia en ambos, como en el caso de la encuesta. El coeficiente de
Jaccard, en cambio, no considera informativas las mutuas ausencias de un bit. Este5 de diciembre de 2018
1.5. Medidas de similaridad de datos categoricos 15
serıa mas apropiado para datos como los del supermercado. Podemos enunciar este
coeficiente de forma intuitiva si consideramos a x y y como subconjuntos A y B de
{1, . . . , n}, donde i ∈ A ⇐⇒ xi = 1 y B se define analogamente. Entonces podemos
escribir el coeficiente de Jaccard como
J(x, y) = ∣A ∩B∣∣A ∪B∣ .
Las medidas S3 y S4 son muy similares a S1 y S2, respectivamente. Sin em-
bargo estas dan un peso mayor a las no coincidencias. Como estos, existen muchos
coeficientes que asignan diferentes pesos a las coincidencias y no coincidencias,
siguiendo las necesidades de los diferentes contextos de aplicacion del analisis de
clusters. En la seccion ?? veremos una ultima medida de similaridad entre datos ca-
tegoricos, en la cual no solo son relevantes los dos puntos en cuestion, sino tambien
sus vecindades.
5 de diciembre de 2018
Capıtulo 2
ROCK: Un algoritmo robusto de
clustering de datos categoricos
En este capıtulo presentamos el algoritmo de clustering de datos categoricos
ROCK (A Robust Clustering Algorithm for Categorical Attributes), desarrollado por
Sudipto Guha, Rajeev Rastogi y Kyuseok Shim [11]. Este es de particular interes
pues, ademas de ser reciente, se apoya en la idea intuitiva de considerar la inter-
seccion entre las vecindades de dos puntos para medir su similaridad. Esta idea,
ademas, ha sido aplicada con gran exito fuera del analisis de clustering, por ejemplo
en la identificacion de la dimensionalidad intrınseca de un conjunto de datos [3] y
como aproximacion al problema de dos muestras [6].
Este algoritmo fue disenado para tratar el problema de clustering de canastas de
mercado, el cual podemos enunciar de la siguiente manera: Sea X un conjunto de
datos en {0,1}M . Llamaremos transacciones a estas observaciones, y diremos que
x ∈ X contiene al i-esimo producto si y solo si xi = 1. De modo que podemos ver cada
transaccion como un vector en {0,1}M o como un conjunto de productos. Queremos
obtener un clustering informativo de este multiconjunto de observaciones.
Como vimos en la seccion 1.1.3, el primer paso es definir un problema matematico
que se ajuste a nuestra intuicion de lo que podrıa ser un buen clustering de las
transacciones de un supermercado. ROCK, en particular, es una heurıstica de maxi-
mizacion de un criterio de homogeneidad y mutua separacion de los clusters en C,el cual presentaremos en la seccion 2.2.2.
16
2.1. Modelos de clusters de canastas de mercado 17
2.1. Modelos de clusters de canastas de mercado
Como lo hace Guha [11], un tipo razonable de cluster que podrıamos buscar en el
contexto de canastas de mercado es un conjunto de transacciones C cuyos productos
se tomaron aleatoriamente de un subconjunto de tamanom ≤M del conjunto de todos
los productos disponibles. Este modelo de cluster es congruente con la concepcion
probabilıstica del analisis de clusters vista en la seccion 1.1.2, pues describe (aunque
incompletamente) la distribucion de una subpoblacion. En esta seccion planteamos
tres modelos simples pero razonables de dicha aleatoreidad. En cada uno de ellos,
el cluster C se compone de observaciones iid de una variable aleatoria T . Dado su
tamano ∣T ∣ = t ≤ m, T se distribuye uniformemente sobre todos los subconjuntos de
tamano t del conjunto de m productos que define a C . En cada uno de los modelos
asumiremos que cada transaccion tiene al menos un producto, pues no es razonable
registrar una compra vacıa. En todos los casos E[∣T ∣] = t.
Modelo con tamano de transaccion constante
El modelo mas simple de este tipo es aquel en el cual todas las transacciones
en C tienen un tamano fijo 0 < t ≤m. Este es el modelo considerado por Guha en la
construccion del algoritmo ROCK [11].
Modelo con tamano de transaccion binomial
En este modelo, el tamano de cada transaccion tiene una distribucion binomial
(pero no permitimos transacciones vacıas) con m ensayos, cada uno con probabilidad
t/m de exito, independiente de los demas. La logica detras de este modelo es que
cada uno de los m productos que definen a C tiene una probabilidad igual de ser
incluıda en la transaccion T , independientemente de los demas productos y bajo la
condicion de que al menos un producto sea incluıdo en la canasta.
Modelo con tamano de transaccion Poisson
En este ultimo modelo concebimos a T como el resultado de un proceso de
compra durante el cual un cliente atraviesa un supermercado, y en cada instante
5 de diciembre de 2018
2.2. Caracterizacion de homogeneidad y separacion 18
tiene una probabilidad infinitesimal de encontrar un producto que quiere anadir a su
canasta, permaneciendo en el supermercado por un tiempo fijo para todos los clientes.
Entonces ∣T ∣ tiene una distribucion de Poisson con media t, sujeta a 0 < ∣T ∣ ≤m. Por
esta razon definimos la distribucion de ∣T ∣ por
P (∣T ∣ = k) =⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩
0 k /∈ N ∨ k = 0 ∨ k >mP (Poisson(t)=k)
P (Poisson(t)>m)+P (Poisson(t)=0) 0 < k ≤m.
En las siguientes secciones discutiremos el algoritmo ROCK de clustering de datos
categoricos.
2.2. Caracterizacion de homogeneidad y separacion
Queremos construir un algoritmo de clustering basado en un criterio de homoge-
neidad y separacion de un cluster que refleje nuestra intuicion acerca de la bondad
de un clustering en el contexto de canastas de mercado. Como vimos en la seccion
1.1.1, estos suelen definirse a partir de una medida de similaridad entre datos.
2.2.1. El numero de enlaces
Comenzaremos por definir una medida de similaridad bien adaptado al contexto
del problema. Sean x, y ∈ {0,1}M dos transacciones. Segun vimos en la seccion 1.5,
debemos considerar la relevancia de las coincidencias xi = yi = 0. Un supermercado
ofrece una enorme variedad de productos, por lo cual es de esperarse que el ta-
mano de las transacciones sea muy pequeno con relacion al numero de productos M .
Entonces para cualquier par de transacciones tendremos un gran numero de coinci-
dencias de este tipo, lo cual indica que estas no son muy informativas y por lo tanto
no debemos tenerlas en cuenta. Esto descarta a las medidas S1 y S3 de la seccion
1.5.
Por otro lado, dos clientes con patrones muy similares de compra pueden haber
adquirido conjuntos pequenos de productos sin interseccion, pero que pertenecen a
una clase de productos que definen un patron de compra. Veamos un ejemplo de esta
situacion.5 de diciembre de 2018
2.2. Caracterizacion de homogeneidad y separacion 19
Ejemplo 2.1 Suponga que el producto 1 es un jabon y el producto 2 es un shampoo,
y que x = (1,0, . . . ,0) y y = (0,1,0, . . . ,0). Suponga, ademas, que el conjunto de
datos contiene un gran numero de transacciones z1 = ⋅ ⋅ ⋅ = zN = (1,1,0, . . . ,0). Por
virtud de las transacciones zi, es razonable pensar que x y y son representantes de
un patron de compra de elementos de aseo personal, a pesar de que x ∩ y = ∅.
Para capturar este tipo de asociacion entre datos, Guha [11] formulo el concepto
de numero de enlaces o numero de links. En la siguiente definicion, recuerde que
los datos en X estan en {0,1}M .
Definicion 2.1 Considere una medida de similaridad entre datos binarios sim ∶{0,1}M × {0,1}M → [0,1] y θ ∈ [0,1]. Decimos que el dato x es un vecino de y,
lo cual denotaremos por x ∼ y, si
sim(x, y) ≥ θ.
Definimos el numero de enlaces entre x y y como su numero de vecinos en comun
en el conjunto total de datos X :
links(x, y) = #{z ∈ X ∣x ∼ z ∧ y ∼ z}.
Definicion 2.2 Para C ⊂ X , definimos su numero interno de enlaces por
links(C) = ∑(x,y)∈C2
links(x, y).
En la anterior definicion, note que, ya que x ∈ X es vecino de si mismo en todas
las definiciones razonables de sim, x tiene un enlace con si mismo, a traves de si
mismo. Entonces links(C) ≥ ∣C ∣. Para datos de canasta de mercado, tomaremos el
coeficiente de Jaccard descrito en la seccion 1.5 como medida de similaridad:
sim(x, y) = J(x, y) = ∣x ∩ y∣∣x ∪ y∣ .
Esta eleccion se debe a que el coeficiente de Jaccard ignora las coincidencias xi =yi = 0, las cuales vimos que no suelen ser informativas para datos de canastas de
mercado. A continuacion definiremos un criterio de homogeneidad para un clustering
C basado en el numero interno de enlaces de cada cluster.5 de diciembre de 2018
2.2. Caracterizacion de homogeneidad y separacion 20
2.2.2. Criterio de bondad de un clustering
Sea C un clustering de X . La funcion criterio descrita por Guha [11] para el
problema en cuesion esta dada por
El = ∑C∈C
nClinks(C)n1+2f(θ)C
, (2.2.1)
donde nC = ∣C ∣. Analicemos este criterio. Comenzamos por sumar el numero de links
internos de cada cluster, pues queremos una alta conectividad entre los puntos de
cada uno. Esta suma es maxima si agrupamos todos los puntos en un solo cluster,
por lo cual normalizamos cada termino links(C) por n1+2f(θ)C . Este termino es una
aproximacion gruesa del valor esperado de links(C), dado que C es un cluster ho-
mogeneo y bien separado de los demas. En adelante denotaremos esta esperanza
por E[links(C)]. En la siguiente seccion explicaremos la derivacion de esta aproxi-
macion. Finalmente, multiplicamos cada termino por nC para favorecer la formacion
de clusters grandes, los cuales suelen ser mas informativos.
2.2.3. Aproximacion de E[links(C)]
En esta seccion discutimos la aproximacion E[links(C)] ≈ n1+2f(θ)C segun aparece
en [11], la cual se basa en nociones intuitivas de homogeneidad y separacion en
cuanto al numero de enlaces en C . Suponga que existe una funcion f(θ), dependiente
del tipo de clusters que buscamos, tal que cada punto de un cluster homogeneo C
tiene aproximadamente nf(θ)C vecinos en C (en un cluster no homogeneo este numero
sera menor con relacion a nC). Si, ademas, C esta bien separado de los demas
clusters, podemos asumir que existen pocos enlaces entre dos puntos de C que
pasan por un punto fuera de este conjunto. Entonces cada punto de C contribuye
n2f(θ)C enlaces a traves de si mismo al numero total de enlaces internos, uno por cada
pareja de sus vecinos. Sumamos esta cantidad para cada uno de los puntos de C
para obtener E[links(C)] ≈ n1+2f(θ)C .
Una derivacion informal de f(θ)
Guha [11] presenta una posible derivacion de f(θ), la cual buscaremos contro-
vertir. Esta se obtiene al asumir que todas las transacciones en C son del mismo5 de diciembre de 2018
2.3. Algoritmo aglomerativo 21
tamano t, y se distribuyen uniformemente entre m productos que definen al cluster
C . El autor comienza por afirmar que existe una constante c ≤ 1 tal que nC ≈ (mct).
Sin embargo, para que el coeficiente binomial tenga sentido, debe ser el caso que
mc ∈ N. Para mc grande, aun la mınima variacion de c tal que mc′ ∈ N causa una
gran variacion de (mct), de modo que muy probablemente no exista dicho c para nC
y t dados. La tabla 2.1 busca ilustrar este fenomeno.
mc=16, t=5 mc=15, t=10 mc=25, t=20
(165) = 4368 (15
10) = 3003 (25
20) = 53130
(155) = 3003 (14
10) = 1001 (24
20) = 10626
(145) = 2002 (13
10) = 286 (23
20) = 1771
(135) = 1287 (12
10) = 66 (22
20) = 231
Cuadro 2.1: Impacto de la variacion de c en (mct) para ciertos valores de mc y t.
Observe, por ejemplo, que entre (2520) y (24
20) hay una diferencia de mas de 40000.
De modo que si t = 20 y nC = 30000, no es posible afirmar que existe c tal que (mct)
aproxima a nC para algun m. Luego, el autor utiliza otras aproximaciones gruesas
para concluir que, si C sigue el modelo de cluster descrito, cada punto de C tiene
≈ n1−θ1+θ
C vecinos en C , de donde se obtiene que f(θ) = 1−θ1+θ .
De modo que, hasta el momento, queda por resolver el problema de como encontrar
una funcion f(θ) que tenga la caracterıstica de aproximacion deseada (para un cluster
homogeneo y bien separado de los demas, E[links(C)] ≈ n1+2f(θ)C ). En la seccion
2.4.1 exploraremos experimentalmente si en realidad existe una funcion como esta
para los modelos de cluster presentados en la seccion 2.1.
2.3. Algoritmo aglomerativo
El algoritmo ROCK es un algoritmo jerarquico que busca, heurısticamente, un
clustering de X con un alto valor del criterio El. Con este proposito, en cada iteracion
aglomeramos dos clusters con un gran numero de enlaces entre puntos en cada uno.
Definicion 2.3 Sean C1,C2 dos clusters de un clustering de X . Definimos su numero5 de diciembre de 2018
2.3. Algoritmo aglomerativo 22
de enlaces cruzados por
links[C1,C2] = ∑p∈C1q∈C2
links(p, q).
Como en todos los algoritmos aglomerativos, en su k-esima iteracion habremos ob-
tenido un clustering C1, . . . ,Ck de X . Aglomeramos el par de clusters que maximiza
la medida de bondad
g(Ci,Cj) =links[Ci,Cj]
(ni + nj)1+2f(θ) − n1+2f(θ)i − n1+2f(θ)
j
. (2.3.2)
Esta medida de bondad sigue una logica similar a la de la funcion criterio, pues el
denominador busca aproximar la esperanza de links[Ci,Cj], dados sus tamanos ni y
nj , y suponiendo que Ci ∪Cj es un cluster homogeneo y bien separado del resto de
los datos. Si la anterior suposicion es cierta, podemos aproximar E[links(Ci,Cj)]por (ni + nj)1+2f(θ). Por otro lado, si Ci ∪ Cj es un cluster homogeneo, tambien Ci
lo es, luego cada punto de Ci tiene ≈ nf(θ)i vecinos en Ci. Quisieramos seguir la
logica de la seccion anterior para afirmar que E[links(Ci)] ≈ n1+2f(θ)i , sin embargo
no podemos afirmar la separacion de Ci de Cj bajo la hipotesis de que Ci ∪ Cj es
un cluster. No obstante, dada la naturaleza aglomerativa del algoritmo, esperamos
que, si ya han ocurrido varias iteraciones, la mayorıa de los puntos a traves de los
cuales pasan enlaces de Ci ya hayan sido agregados a Ci. Entonces la aproxima-
cion E[links(Ci)] ≈ n1+2f(θ)i se hace cada vez mas apropiada. Finalmente, al restar
E[links(Ci)] y E[links(Cj)] de E[links(Ci ∪Cj)] obtenemos el doble del numero
de enlaces cruzados entre los clusters. Se trata del doble porque la definicion de
links(C) toma en cuenta pares ordenados de puntos, mientras que links[Ci,Cj] solo
suma sobre pares no ordenados con un punto en Ci y otro en Cj . El autor puede haber
omitido esta constante dado que afecta uniformemente la medida g entre cada par
de clusters, de modo que no hace ninguna diferencia en un algoritmo aglomerativo.
5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 23
2.4. Reevaluacion de la aproximacion de E[links(C)]
2.4.1. Factibilidad del modelo
Como vimos en las anteriores secciones, el exito de la implementacion de este
algoritmo en un problema de analisis de clusters depende de nuestra capacidad pa-
ra encontrar una funcion f(θ) tal que E[links(C)] ≈ n1+2f(θ) sea una aproximacion
razonable para un cluster C de tamano n. En esta seccion ponemos a prueba, empıri-
camente, la existencia de una funcion como esta para cada uno de los modelos de
clusters presentados en la seccion 2.1. Para n > 0, las siguientes afirmaciones son
equivalentes:
E[links(C)] = n1+2f(θ)
⇔ log(E[links(C)]) = (1 + 2f(θ)) logn
⇔ log(E[links(C)])logn
= 1 + 2f(θ).
De modo que, si E[links(C)] ≈ n1+2f(θ) es una aproximacion razonable, debe ser
el caso que log(E[links(C)]/ logn sea aproximadamente constante para clusters de
diferentes tamanos n, con θ ∈ [0,1] fijo. Para evaluar esta afirmacion empıricamente,
simulamos clusters de diferentes tamanos (entre 100 y 12500) de los tres modelos.
Luego calculamos links(C) para cada uno, y graficamos links(C)/ logn separada-
mente para cada modelo. La figura 2.1 muestra las graficas obtenidas. Como podemos
ver, links(C)/ logn tiene una evidente dependencia con respecto a n, de modo que
no es razonable asumir la existencia de una funcion f(θ) como la descrita.
2.4.2. Calculo de E[links(C)]
Para remediar los problemas en la aproximacion de E[links(C)] que vimos en
las anteriores secciones, en esta mostramos que es posible calcular esta esperanza
exactamente para los tres modelos probabilısticos de clusters descritos en la seccion
2.1. Recuerde que lo que queremos calcular es E[links(C) ∣ C esta bien separado
de los demas datos, ∣C ∣ = n], e interpretamos esta condicion de separacion como que
cualesquiera dos elementos de C no tienen vecinos en comun fuera de C . Entonces,
5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 24
Figura 2.1: Valores empıricos de links(C)/ logn para clusters de cada modelo, con
θ fijo y n variable.
para efectos de este calculo, podemos considerar los enlaces de C sin hacer referencia
al conjunto total de datos X . Como ultima observacion, asumiremos que cada dato
en C es al menos vecino de si mismo (J(X,X) ≥ θ).Sea C un cluster aleatorio (una muestra aleatoria) con alguna de las distri-
buciones en 2.1 (tamano de transaccion fija, binomial, o Poisson) de tamano n.
Nuestro calculo se basa en las siguientes dos observaciones fundamentales. Sean
X0, Y0, Z0 ∈ C tres datos diferentes.
Observacion 2.1 Dados los tamanos de dos transacciones, ∣X0∣ = tX y ∣Y0∣ = tY ,
el tamano de su interseccion ∣X0 ∩ Y0∣ tiene una distribucion hipergeometrica con
parametros (tX , tY ,m − tY ), donde esta distribucion esta definida por
Definicion 2.4 Considere un experimento en el cual, de una caja con b bolas blan-
cas y c negras, sacamos a bolas sin remplazo. Decimos que la variable aleatoria
que describe el numero de bolas blancas que sacamos tiene una distribucion hiper-
geometrica con parametros (a, b, c). Denotaremos por Hiper(a, b, c) a una variable
aleatoria con estos parametros.
La distribucion hipergeometrica surge en muchos contextos, de modo que esta
implementada en casi cualquier software de programacion estadıstica.
5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 25
Observacion 2.2 Dado ∣Z0∣ = tZ , los eventos X0 ∼ Z0 y Y0 ∼ Z0 son independientes,
esto es,
P (X0 ∼ Z0, Y0 ∼ Z0 ∣ ∣Z0∣ = tZ) = P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ)P (Y0 ∼ Z0 ∣ ∣Z0∣ = tZ).
Demostracion: Procedemos mediante el desarrollo del lado izquierdo de la anterior
igualdad.
P (X0 ∼ Z0, Y0 ∼ Z0 ∣ ∣Z0∣ = tZ)
= 1
P (∣Z0∣ = tZ)P (X0 ∼ Z0, Y0 ∼ Z0, ∣Z0∣ = tZ)
= 1
P (∣Z0∣ = tZ)P
⎛⎜⎜⎜⎝⊍
z∈{0,1}m
∣z∣=tZ
{X0 ∼ z, Y0 ∼ z,Z0 = z}⎞⎟⎟⎟⎠
= 1
P (∣Z0∣ = tZ)∑
z∈{0,1}m
∣z∣=tZ
P (X0 ∼ z, Y0 ∼ z,Z0 = z).
Recuerde que los elementos de una muestra aleatoria son mutuamente independien-
tes. Por otro lado, P (X0 ∼ z) es constante para todo z ∈ {0,1}m tal que ∣z∣ = tZ ,
lo cual se debe a que todos los productos que definen al cluster tienen la misma
probabilidad de ser anadidos a una canasta. Entonces, si z0 ∈ {0,1}m tiene tamano
tZ , lo anterior es igual a
= 1
P (∣Z0∣ = tZ)∑
z∈{0,1}m
∣z∣=tZ
P (X0 ∼ z)P (Y0 ∼ z,Z0 = z)
= 1
P (∣Z0∣ = tZ)P (X0 ∼ z0) ∑
z∈{0,1}m
∣z∣=tZ
P (Y0 ∼ z,Z0 = z)
= 1
P (∣Z0∣ = tZ)P (X0 ∼ z0)P (Y0 ∼ Z0, ∣Z0∣ = tZ)
= P (X0 ∼ z0)P (Y0 ∼ Z0 ∣ ∣Z0∣ = tZ).
Para finalizar la demostracion comprobamos el hecho intuitivo de que P (X0 ∼ z0) =
5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 26
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ), utilizando la independencia de X0 y Z0:
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ) =1
P (∣Z0∣ = tZ)P (X0 ∼ Z0, ∣Z0∣ = tZ)
= 1
P (∣Z0∣ = tZ)∑
z∈{0,1}m
∣z∣=tZ
P (X0 ∼ z,Z0 = z)
= 1
P (∣Z0∣ = tZ)∑
z∈{0,1}m
∣z∣=tZ
P (X0 ∼ z)P (Z0 = z)
= 1
P (∣Z0∣ = tZ)P (X0 ∼ z0) ∑
z∈{0,1}m
∣z∣=tZ
P (Z0 = z)
= 1
P (∣Z0∣ = tZ)P (X0 ∼ z0)P (∣Z0∣ = tZ)
= P (X0 ∼ z0).
◻Ahora calcularemos E[links(C)] exactamente, para lo cual nos valdremos de las
dos observaciones realizadas.
E[links(C)] = E⎡⎢⎢⎢⎢⎣∑
(X,Y )∈C2
links(X,Y )⎤⎥⎥⎥⎥⎦
= E [∑X∈C
links(X,X)] +E⎡⎢⎢⎢⎢⎢⎢⎣∑
(X,Y )∈C2
X /=Y
links(X,Y )⎤⎥⎥⎥⎥⎥⎥⎦
(2.4.3)
Recuerde que cada dato en el cluster es vecino de si mismo, y por tanto tiene
un enlace con si mismo a traves de si mismo. Entonces el primer sumando de esta
ecuacion es igual a
E [∑X∈C
links(X,X)] = nE[links(X0,X0)]
= n(1 + ∑Y /=X0∈C
P (X0 ∼ Y ))
= n(1 + (n − 1)P (X0 ∼ Y0))
= n + (n2 − n)P (X0 ∼ Y0).
5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 27
Veamos como calcular P (X0 ∼ Y0). Esta condicion es equivalente a
X0 ∼ Y0
⇔ J(X0, Y0) =∣X0 ∩ Y0∣∣X0 ∪ Y0∣
≥ θ
⇔ ∣X0 ∩ Y0∣∣X0∣ + ∣Y0∣ − ∣X0 ∩ Y0∣
≥ θ
⇔ ∣X0 ∩ Y0∣ ≥ θ(∣X0∣ + ∣Y0∣ − ∣X0 ∩ Y0∣)
⇔ (1 + θ)∣X0 ∩ Y0∣ ≥ θ(∣X0∣ + ∣Y0∣)
⇔ ∣X0 ∩ Y0∣ ≥θ
1 + θ(∣X0∣ + ∣Y0∣).
Recuerde que no permitimos transacciones vacıas, de modo que en lo anterior ningun
denominador es 0. Entonces la probabilidad de que X0 ∼ Y0 esta dada por
P (X0 ∼ Y0) =m
∑tX=1
m
∑tY =1
P (X0 ∼ Y0 ∣ ∣X0∣ = tX , ∣Y0∣ = tY )P (∣X0∣ = tX , ∣Y0∣ = tY )
=m
∑tX=1
m
∑tY =1
P (Hiper(tX , tY ,m − tY ) ≥θ
1 + θ(tX + tY ))
× P (∣X0∣ = tX)P (∣Y0∣ = tY ),
lo cual completa el calculo del primer sumando de la ecuacion 2.4.3. En cuanto al
segundo sumando vemos que
E
⎡⎢⎢⎢⎢⎢⎢⎣∑
(X,Y )∈C2
X /=Y
links(X,Y )⎤⎥⎥⎥⎥⎥⎥⎦
=(n2 − n)E[links(X0, Y0)]
=(n2 − n) ∑Z∈C
P (X0 ∼ Z,Y0 ∼ Z)
=(n2 − n)⎛⎜⎜⎝
2P (X0 ∼ Y0) + ∑Z∈C
Z /=X0,Z /=Y0
P (X0 ∼ Z,Y0 ∼ Z)⎞⎟⎟⎠
=(n2 − n)[2P (X0 ∼ Y0) + (n − 2)P (X0 ∼ Z0, Y0 ∼ Z0)].
Previamente calculamos P (X0 ∼ Y0), luego solo falta calcular P (X0 ∼ Z0, Y0 ∼ Z0),para lo cual nos apoyaremos en la observacion 2.2.
P (X0 ∼ Z0, Y0 ∼ Z0)5 de diciembre de 2018
2.4. Reevaluacion de la aproximacion de E[links(C)] 28
=m
∑tZ=1
P (X0 ∼ Z0, Y0 ∼ Z0 ∣ ∣Z0∣ = tZ)P (∣Z0∣ = tZ)
=m
∑tZ=1
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ)P (Y0 ∼ Z0 ∣ ∣Z0∣ = tZ)P (∣Z0∣ = tZ)
=m
∑tZ=1
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ)2P (∣Z0∣ = tZ),
donde P (X0 ∼ Z0 ∣ ∣X0∣ = tX) esta dado por
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ)
=m
∑tX=1
P (X0 ∼ Z0 ∣ ∣Z0∣ = tZ , ∣X0∣ = tX)P (∣X0∣ = tX ∣ ∣Z0∣ = tZ)
=m
∑tX=1
P (Hiper(tX , tZ ,m − tZ) ≥θ
1 + θ(tX + tZ))P (∣X0∣ = tX)P (∣Z0∣ = tZ)
P (∣Z0∣ = tZ)
=m
∑tX=1
P (Hiper(tX , tZ ,m − tZ) ≥θ
1 + θ(tX + tZ))P (∣X0∣ = tX).
Esto concluye el calculo de E[links(C)], el cual podemos resumir como
E[links(C)] = E [∑X∈C
links(X,X)] +E⎡⎢⎢⎢⎢⎢⎢⎣∑
(X,Y )∈C2
X /=Y
links(X,Y )⎤⎥⎥⎥⎥⎥⎥⎦
= n + (n2 − n)P (X0 ∼ Y0)
+ (n2 − n)[2P (X0 ∼ Y0) + (n − 2)P (X0 ∼ Z0, Y0 ∼ Z0)]
= n + (n2 − n)[3P (X0 ∼ Y0) + (n − 2)P (X0 ∼ Z0, Y0 ∼ Z0)]
= P (X0 ∼ Z0, Y0 ∼ Z0)n3
+ 3(P (X0 ∼ Y0) − P (X0 ∼ Z0, Y0 ∼ Z0))n2
+ (1 − 3P (X0 ∼ Y0) + 2P (X0 ∼ Z0, Y0 ∼ Z0))n.
(2.4.4)
Para finalizar esta seccion comprobaremos empıricamente el calculo realizado.
Para este fin, utilizaremos los mismo clusters simulados que en la seccion 2.4.1,
clusters de tamanos entre 100 y 12500 de cada uno de los tres modelos presentados
en la seccion 2.1. Para cada uno de estos, calculamos el error relativo de su numero
interno de enlaces, el cual esta dado por
links(C) −E[links(C)]E[links(C)] .
5 de diciembre de 2018
2.5. Modificacion del algoritmo 29
Figura 2.2: Error relativo del numero de links observado en cada uno de los clusters
simulados.
La figura 2.2 presenta graficamente el error relativo de cada uno de los clusters
simulados. Observamos que este esta centrado al rededor de 0 y que, ademas, se
hace menor a medida que aumenta el tamano del cluster. De modo que el calculo
realizado es compatible con lo observado en las simulaciones.
2.5. Modificacion del algoritmo
Podemos utilizar el calculo realizado para modificar el algoritmo descrito en la
seccion 2.3. Recuerde que este es un algoritmo aglomerativo que, en cada iteracion,
junta la pareja de clusters que maximiza la medida de bondad
g(Ci,Cj) =links[Ci,Cj]
(ni + nj)1+2f(θ) − n1+2f(θ)i − n1+2f(θ)
j
,
donde θ ∈ [0,1] y n1+2f(θ) aproxima el valor de E[links(C)] para un cluster C de
tamano n. En lugar de esta aproximacion, usaremos el calculo realizado en la seccion
anterior. Notablemente, el calculo tiene mas parametros que la aproximacion; este
ademas depende del valor esperado t del tamano de las transacciones en C y del5 de diciembre de 2018
2.5. Modificacion del algoritmo 30
numero de productos m que lo definen. Estos parametros los estimaremos de la union
de los clusters que estemos comparando, dado que pretendemos estimar el numero
de enlaces cruzados que deberıan tener si realmente conforman un solo cluster.
Denotaremos por
C(t,m,n)
un cluster aleatorio de tamano n, cuyo tamano de sus transacciones tiene valor
esperado t, definido por m productos. Definimos una nueva medida de bondad entre
Ci y Cj por
g(Ci,Cj) =links[Ci,Cj]
E[links(C∪)] −E[links(Ci)] −E[links(Cj)], (2.5.5)
donde
C∪ = C(tij, mij, ni + nj)),
Ci = C(tij, mij, ni)),
y
Cj = C(tij, mij, nj)).
Para un problema de analisis de clusters particular, podemos tomar los valores
esperados de la definicion de g con respecto a alguno de los modelos de clusters
discutidos en la seccion 2.1. Tambien es posible realizar un calculo o aproximacion
de E[links(C)] para un modelo diferente. Esta nueva medida de bondad de la union
de dos clusters define una version modeificada del algoritmo aglomerativo ROCK, el
cual en adelante llamaremos CROCK (calculated ROCK ).
5 de diciembre de 2018
Capıtulo 3
Comparacion de algoritmos de
clustering de datos categoricos
En este capıtulo realizaremos una comparacion empırica de algunos algoritmos de
clustering de datos categoricos. Nuestros objetivos principales seran poner a prueba
tanto la idea del numero de enlaces introducida por [11] como la correccion al calculo
de de E[links(C)] propuesta en el anterior capıtulo en el contexto de canastas de
mercado. Para este fin, emplearemos conjuntos de datos simulados con una estructura
de clusters segun uno de los modelos descritos en la seccion 2.1. Compararemos,
empıricamente, el nivel de exito de diferentes algoritmos para revelar la estructura
de subpoblaciones presente en los datos. Como comparar un clustering calculado
con el clustering verdadero (aquel que introdujimos durante la simulacion) no es una
pregunta trivial; en la seccion 3.1 describiremos un criterio moderno de comparacion
de clusterings de un conjunto de datos comun, llamado variacion de informacion.
Ademas de este criterio cuantitativo, analizaremos las caracterısticas de la eje-
cucion y el resultado de los algoritmos. El objetivo de este ejercicio es explicar que
hace a algunos algoritmos mas exitosos que otros. Utilizando estos dos tipos de
analisis buscaremos dar respuesta a las siguientes preguntas:
1. ¿Como se compara el nivel de exito de cada uno de los algoritmos analizados
para revelar la estructura correcta de subpoblaciones en un conjunto de datos
como el descrito?
31
3.1. Distancia entre clusterings 32
2. ¿Cual es el impacto de la modificacion sugerida para el algoritmo ROCK en el
capıtulo anterior?
3. ¿Que consecuencia tiene la variacion del tamano del conjunto de datos en el
resultado de cada uno de los algoritmos?
4. ¿Que consecuencia tiene la sobreposicion de los conjuntos de productos que
definen a cada cluster?
5. ¿Que efecto tiene la sobrerpresentacion de algunos de los clusters?
3.1. Distancia entre clusterings
En esta seccion presentamos la variacion de informacion, una metrica entre clus-
terings de un conjunto comun de datos basada en el concepto de entropıa de la
informacion. Comenzaremos por definir este concepto y presentar la intuicion nece-
saria. A lo largo de esta seccion considere X una variable aleatoria de imagen finita
Im(X) = {x1, . . . , xn} con funcion de masa de probabilidad p(x).
3.1.1. El concepto de entropıa
El concepto de entropıa busca cuantificar la informacion contenida en una varia-
ble aleatoria de imagen finita. Para facilitar su presentacion, primero definimos el
contenido de informacion; la informacion asociada a una posible observacion de una
variable aleatoria discreta.
Definicion 3.1 Sea x ∈ Im(X). El contenido de informacion IX asociado a la rea-
lizacion del evento x se define por
IX(x) = − log2 p(x).
En esta definicion, adoptamos la convencion 0 log 0 = 0 [4], lo cual no es absurdo
pues x log(x) → 0 cuando x → 0. En adelante asumiremos que todos los logaritmos
se toman en base 2. Para darle sentido a esta definicion, suponga que x ocurre
5 de diciembre de 2018
3.1. Distancia entre clusterings 33
con probabilidad 1. Entonces obtener x como observacion de X solo confirma al-
go que ya sabıamos acerca de X , y es razonable que IX(x) = 0. Analogamente, si
p(x) es muy pequeno, podemos decir que observar x es muy informativo pues indi-
ca la ocurrencia de un evento altamente inesperado. En general, vemos que IX(x)es inversamente proporcional a p(x); mientras mas probable sea un evento, menos
informativa consideraremos su observacion.
Definicion 3.2 La entropıa de la informacion, o simplemente entropıa H de X se
define por
H(X) = E[IX(X)].
De modo queH(X) indica, intuitivamente, el grado de informatividad que espera-
mos de las observaciones de X . Tambien es posible justificar esta nocion de cantidad
de informacion formalmente: A continuacion veremos como H(X) tiene una relacion
muy cercana con el ınfimo numero de bits que debemos usar, en promedio, para comu-
nicar una observacion de X . En seguida presentaremos un teorema de la teorıa de la
informacion que describe esta relacion. Sea F = {f ∶ Im(X) → {0,1}∗, f invertible}el conjunto de funciones que codifican, de forma invertible, las posibles realizaciones
de X como secuencias binarias finitas. Para f ∈ F , denotamos por lf(xi) la longitud
de la secuencia f(xi).
Teorema 3.1
i)
H(X) ≤ ınff∈F
E[lf(X)] <H(X) + 1.
ii)
H(X) = E[lf(X)]
si y solo si
lf(xi) = − log p(xi) ∀i = 1 . . . n.
iii) Dado un conjunto de longitudes positivas {l1, . . . , ln} que satisface la desigual-
dad
∑i
2−li ≤ 1,
5 de diciembre de 2018
3.1. Distancia entre clusterings 34
existe f ∈ F tal que lf(xi) = l + i.
Omitimos la demostracion de este teorema pues esta fuera del alcance de este
trabajo. Sin embargo, el lector puede consultarla en el Capıtulo 5 de la referencia [4].
El gran aporte del teorema 3.1 a esta discusion es que el ınfimo numero de bits que
requerimos para comunicar una observacion de X (en promedio, pues X es aleatoria)
es una nocion intuitiva sobre la cantidad de informacion que esta contiene. El primer
inciso del teorema indica que H(X) esta muy cerca (a un bit, como mucho) de este
ınfimo. ¿Por que, entonces, utilizamos H(X) como nocion de informacion en lugar del
ınfimo? Los incisos ii y iii indican que este ınfimo alcanza su cota inferior si y solo si
− log p(xi) es un entero ∀i. Entonces el hecho de que la cotaH(X) ≤ ınff∈F E[lf(X)]no se alcance para ciertas distribuciones es una consecuencia de la imposibilidad de
comunicar secuencias de bits longitud no entera. Ya que no es deseable senir nuestra
nocion de cantidad de informacion a esta restriccion, inducida por el mecanismo
elegido de comunicacion, preferimos a H(X) sobre ınff∈F E[lf(X)].
3.1.2. La entropıa condicional
Sea Y otra variable aleatoria de imagen finita. Ademas de cuantificar la informa-
cion contenida en X , puede interesarnos cuantificar que tanta informacion, en pro-
medio, nos dice Y acerca de X . La entropıa condicional mide una cantidad recıproca,
la cantidad de informacion queda en X , en promedio, dado Y .
Definicion 3.3 La entropıa condicional de X con respecto a Y se define como
H(X ∣Y ) =∑y
pY (y)H(X ∣Y = y)
= −∑y
pY (y)∑x
pX(x∣Y = y) log pX(x∣Y = y)
= −∑x,y
pX,Y (x, y) log pX(x∣Y = y)
= −EX,Y [log pX(X ∣Y )],
donde pY es la funcion de masa de probabilidad de Y .
Ahora demostraremos algunos teoremas que seran utiles mas adelante. Comen-
zaremos por un hecho intuitivo: que H(X ∣Y ) ≤H(X). Esto significa que el condicio-5 de diciembre de 2018
3.1. Distancia entre clusterings 35
namiento de una variable aleatoria reduce su entropıa. Esta demostracion se apoya
en la desigualdad de Jensen.
Teorema 3.2 (Desigualdad de Jensen) Si X es una variable aleatoria y ϕ una fun-
cion convexa, entonces
ϕ(E[X]) ≤ E[ϕ(X)].
Teorema 3.3 H(X ∣Y ) ≤H(X)
Demostracion: Comenzamos por desarrollar la expresion
H(X) −H(X ∣Y ) = −∑x
pX(x) log pX(x) −∑y
pY (y)H(X ∣Y = y)
= −∑x
(∑y
pX,Y (x, y)) log pX(x)
+∑y
pY (y)(∑x
pX(x∣Y = y) log pX(x∣Y = y))
= −∑x,y
pX,Y (x, y) log pX(x) +∑x,y
pX,Y (x, y) log pX(x∣Y = y)
= −∑x,y
pX,Y (x, y) log pX(x) +∑x,y
pX,Y (x, y) logpX,Y (x, y)pY (y)
=∑x,y
pX,Y (x, y) logpX,Y (x, y)pY (y)pX(x)
=∑x,y
pX,Y (x, y) − logpY (y)pX(x)pX,Y (x, y)
.
La ultima expresion es un valor esperado tomado con respecto a la distribucion
conjunta de X y Y . Ya que el logaritmo negativo es claramente una funcion convexa,
podemos aplicar la Desigualdad de Jensen para ver que
− log(EX,Y [pY (y)pX(x)pX,Y (x, y)
]) ≤ EX,Y [− log(pY (y)pX(x)pX,Y (x, y)
)] =H(X) −H(X ∣Y ).
Finalmente, note que
EX,Y [pY (y)pX(x)pX,Y (x, y)
] =∑x,y
pY (y)pX(x) = 1,
luego
0 = − log(EX,Y [pY (y)pX(x)pX,Y (x, y)
]) ≤H(X) −H(X ∣Y ).
◻5 de diciembre de 2018
3.1. Distancia entre clusterings 36
Por ultimo, demostramos un teorema que, a su vez, nos permitira demostrar que
la medida de similaridad entre clusterings que estamos a punto de plantear de hecho
es una metrica.
Teorema 3.4 (Regla de la cadena)
H(X,Y ) =H(Y ) +H(X ∣Y ).
En particular,
H(X,Y ) ≥H(X).
Demostracion:
H(X,Y ) = −∑x,y
pX,Y (x, y) log pX,Y (x, y)
= −∑x,y
pX,Y (x, y) log pX(x∣Y = y)pY (y)
= −∑x,y
pX,Y (x, y) log pY (y) −∑x,y
pX,Y (x, y) log pX(x∣Y = y)
= −∑y
pY (y) log pY (y) −∑x,y
pX,Y (x, y) log pX(x∣Y = y)
=H(Y ) +H(X ∣Y ).
Ademas, H(X ∣Y ) ≥ 0 pues es un valor esperado tomado sobre terminos positivos
(−pX,Y (x, y) log pX(x∣Y = y)). Entonces H(X,Y ) ≥H(X). ◻
3.1.3. La variacion de la informacion
Sea X un conjunto de datos. En esta seccion definiremos una metrica en el espacio
de clusterings de X . Para un clustering C = {Ci}, considere la siguiente variable
aleatoria: Seleccionamos, con aleatoreidad uniforme, un dato X ∈ X . Definimos la
variable aleatoria CX como el cluster en C al cual X pertenece. Entonces la funcion
de masa de probabilidad de CX esta dada por
P (CX = C) = P (X ∈ C) = ∣C ∣∣X ∣ .
Sea D un segundo clustering de X y DX la variable aleatoria analoga a CX .
Como vimos en la seccion anterior, la entropıa condicional H(CX ∣DX) indica, en
5 de diciembre de 2018
3.1. Distancia entre clusterings 37
promedio, la incertidumbre que tenemos acerca del cluster del punto X en C dado
que sabemos su cluster en D. Esta entropıa condicional esta dada por
H(CX ∣DX) = ∑D∈D
P (X ∈D)H(CX ∣X ∈D)
= ∑D∈D
P (X ∈D)∑C∈C
−P (X ∈ C ∣X ∈D) logP (X ∈ C ∣X ∈D).(3.1.1)
Consideremos algunos ejemplos para ilustrar el significado de H(CX ∣DX). Su-
ponga que cada elemento de D es un subconjunto de algun elemento de C. Entonces,
∀C ∈ C y ∀D ∈ D, D ⊂ C ∨D ∩ C = ∅. En el primer caso logP (X ∈ C ∣X ∈D) = 0,
y en el segundo P (X ∈ C ∣X ∈ D) = 0. Al remplazar estos valores en la ante-
rior ecuacion vemos que H(CX ∣DX) = 0. Esto era de esperarse pues al observar
DX podemos deducir CX automaticamente, luego no queda informacion en CX tras
observar DX . Ahora veamos un caso en el cual DX no revela ningun tipo de in-
formacion acerca de CX . Suponga que D = {X} /= C. En este caso la primera su-
matoria de la ecuacion 3.1.1 es una suma de un solo elemento, P (DX = X ) = 1 y
P (X ∈ C ∣X ∈ D) = P (X ∈ C ∣X ∈ X ) = P (X ∈ C) ∀D ∈ D. Remplazando en la
ecuacion obtenemos que
H(CX ∣DX) =H(CX).
Esto es intuitivo pues significa que, en este caso, la informacion contenida en
CX permanece igual aun despues de conocer DX . Estos son los dos casos extremos
de H(CX ∣DX). La variacion de la informacion es una forma de hacer simetrizar la
entropıa condicional de estas variables.
Definicion 3.4 La variacion de la informacion entre los clusterings C y D de un
conjunto X de datos, denotada V I(C,D) esta dada por
V I(C,D) =H(CX ∣DX) +H(DX ∣CX),
donde CX y DX son variables aleatorias como las que definimos anteriormente para
C y D.
En la practica, podemos calcular H(CX ∣DX) y H(DX ∣CX) facilmente a partir
del tamano de cada cluster y de cada interseccion entre un cluster de cada uno de
los clusterings en cuestion.5 de diciembre de 2018
3.1. Distancia entre clusterings 38
Terminaremos esta seccion con la demostracion de que V I es una metrica. Para
esta, haremos referencia a una generalizacion del teorema 3.3, citada por [7]. Es-
ta asegura que si Z es una tercera variable aleatoria, H(X ∣Y,Z) ≤ H(X ∣Y ). No
presentamos una prueba de este teorema pues esta requiere maquinaria sofisticada
propia de la teorıa de la informacion, lo cual no es el foco principal de este trabajo.
Teorema 3.5 V I es una metrica en el espacio de clusterings de un conjunto de datos
X .
Demostracion: Sean A, B y C clusterings de X , y A, B y C las variables aleato-
rias asociadas a estos, respectivamente. La simetrıa de V I es evidente, y su no-
negatividad se debe a que H(A∣B) es un valor esperado tomado sobre valores no
negativos. Para comprobar que V I(A,A) = 0, calculamos
H(A∣A) = ∑a∈Im(A)
pA(a)H(A∣A = a)
= − ∑a∈Im(A)
pA(a) ∑a∈Im(a)
pA(a∣A = a) log pA(a∣A = a)
= 0.
En cuanto a la desigualdad triangular, buscaremos primero demostrar la desigual-
dad
H(B∣A) +H(C ∣B) −H(C ∣A) ≥ 0. (3.1.2)
Ya que el condicionamiento de una variable aleatoria reduce su entropıa, tenemos
que
H(B∣A) +H(C ∣B) −H(C ∣A)
≥H(B∣A) +H(C ∣A,B) −H(C ∣A).
Mediante dos aplicaciones consecutivas del teorema 3.4, podemos reescribir la
suma H(B∣A) +H(C ∣A,B) como
H(B∣A) +H(C ∣A,B)
=H(A,B) −H(A) +H(A,B,C) −H(A,B)
=H(A,B,C) −H(A)
=H(B,C ∣A),5 de diciembre de 2018
3.2. Enunciado del problema 39
con lo cual la desigualdad toma la forma
H(B∣A) +H(C ∣B) −H(C ∣A) ≥H(B,C ∣A) −H(C ∣A).
Ahora mostraremos que el termino de la derecha es no-negativo. Fije a ∈ Im(A).El teorema 3.4 implica que
H(B,C ∣A = a) =H(B∣A = a,C ∣A = a) ≥H(C ∣A = a).
Entonces vemos que
H(B,C ∣A) = ∑a∈Im(A)
pA(a)H(B,C ∣A = a)
≥ ∑a∈Im(A)
pA(a)H(C ∣A = a)
=H(C ∣A).
De modo que
H(B,C ∣A) −H(C ∣A) ≥ 0,
con lo cual queda demostrada la desigualdad 3.1.2. Para mostrar el teorema, sumamos
esta desigualdad con ella misma, pero con A y B invertidos. Obtenemos la expresion
H(B∣A) +H(C ∣B) −H(C ∣A) +H(B∣C) +H(A∣B) −H(A∣C) ≥ 0
⇐⇒ H(A∣B) +H(B∣A) +H(B∣C) +H(C ∣B) ≥H(A∣C) +H(C ∣A)
⇐⇒ V I(A,B) + V I(B,C) ≥ V I(A,C).◻
3.2. Enunciado del problema
En los experimentos que presentaremos mas adelante en este capıtulo juzgare-
mos la capacidad de cada algoritmo para resolver el siguiente problema: Sea X un
conjunto de N datos en {0,1}M de canastas de mercado compuesto por k clusters,
cada uno de los cuales sigue el modelo con tamano de transaccion binomial descrito
en la seccion 2.1. Buscamos un k-clustering (un clustering de k elementos) C de Xque se aproxime al clustering natural dado por la estructura de subpoblaciones de
X , donde esta aproximacion se mide mediante el criterio de distancia de variacion
de informacion.5 de diciembre de 2018
3.3. Descripcion de las simulaciones 40
∣C1∣ ∣C2∣ ∣C3∣ ∣C4∣ ∣C5∣ ∣C6∣
Escenario 1 300 300 150 150 150 150
Escenario 2 450 150 150 150 150 150
Escenario 3 500 300 100 100 100 100
Escenario 4 800 80 80 80 80 80
Cuadro 3.1: Tamano de cada cluster bajo los escenarios de sobrerrepresentacion
planteados.
3.3. Descripcion de las simulaciones
Las caracterısticas de cada uno de los conjuntos de datos simulados correspon-
den a las preguntas planteadas al comienzo de este capitulo. Sin embargo, estas
parten de una base comun. Cada conjunto consta de 6 clusters del modelo binomial.
Los parametros de cada cluster son las combinaciones de t = 5,15 (promedio del ta-
mano de las transacciones) y m = 110,130,150 (numero de productos que definen al
cluster). La intencion de estos parametros es emular patrones de compra razonables
para un supermercado pequeno. Un porcentaje constante p = 40 % de los m produc-
tos que definen a cada cluster son necesariamente exclusivos a este. El porcentaje
restante se toma aleatoriamente de un pool de productos compartido por todos los
clusters. Note que esta aleatoreidad hace posible que el porcentaje de productos
exclusivos a un cluster sea mayor que 40 %. Finalmente, cada cluster se compone de
200 transacciones, de modo que cada conjunto de datos consta de 1200.
Sobre esta base, realizamos una serie de variaciones que permitiran el analisis
de las preguntas planteadas al inicio de este capıtulo. Las primeras se tratan de
variaciones en el tamano del conjunto de datos, entre las cuales tenemos conjuntos
de tamanos N = 300,600,900,1200,3000. Las segundas son variaciones de la sobre-
posicion de los clusters. Esto corresponde a la variacion del parametro p, que define
que porcentaje de los productos que definen a un cluster son exclusivos a este. Si-
mulamos datos con p = 5 %,20 %,40 % y 50 %. Finalmente, planteamos conjuntos en
los cuales algunos de los clusters estan mas representados que otros. El cuadro 3.1
describe cada uno de los escenarios planteados.
5 de diciembre de 2018
3.4. Algoritmos a comparar 41
Algoritmo Abreviacion
ROCK ROCK
CROCK CROCK
Average linkage con el coeficiente de
Jaccard como medida de similaridadAvg(J)
Average linkage con el numero de
enlacesAvg(links)
Complete linkage con el coeficiente
de JaccardCompl(J)
Complete linkage con el numero de
enlacesCompl(links)
Single linkage con el coeficiente de
JaccardSingle(J)
Single linkage con el numero de
enlacesSingle(links)
Cuadro 3.2: Abrevacion del nombre de cada algoritmo.
3.4. Algoritmos a comparar
Ademas de los algoritmos ROCK y CROCK (su modificacion), incluiremos en este
analisis los algoritmos clasicos de single, complete, y average linkage. Ya que estos
ultimos permiten la escogencia de una medida de similaridad arbitraria, analizaremos
cada uno tanto con el ındice de Jaccard como con el numero de enlaces como medida.
El cuadro 3.2 muestra la abreviacion con la cual nos referiremos a cada algoritmo.
Esta comparacion dara lugar a una serie de discusiones interesantes. En primer
lugar, podremos comparar a los algoritmos clasicos con aquellos que se apoyan en la
medida del numero de enlaces entre datos. Por otro lado, podremos analizar si esta
es lo suficientemente robusta en si misma como para inducir buenos resultados en los
esquemas clasicos de linkage. Finalmente, esta comparacion nos permitira evaluar la
pertinencia de la normalizacion por E[links[Cj,Cj]] de ROCK y la correccion que
hemos propuesto para esta en CROCK.
5 de diciembre de 2018
3.4. Algoritmos a comparar 42
Manejo de datos atıpicos
Una dificultad comun que enfrentan los algoritmos jerarquicos (todos los men-
cionados lo son) en el problema en cuestion es el impacto de los datos atıpicos.
Este tipo de dato tiene el potencial de permanecer fuera del proceso aglomerativo
hasta sus ultimas iteraciones. El resultado de este fenomeno es que, para alcan-
zar un k-clustering, el algoritmo se ve forzado a juntar clusters que corresponden a
subpoblaciones diferentes. La figura 3.1 muestra el dendrograma de las ultimas 25
aglomeraciones realizadas durante la ejecucion de average linkage con el numero de
enlaces como medida en un conjunto de 300 datos. Si realizamos el corte horizontal
senalado, que equivale a detener el algoritmo cuando tenemos 6 clusters, uno de los
clusters que obtendremos constara de tan solo 4 puntos. Entonces necesariamente
habremos unido clusters que no debıamos.
Figura 3.1: Ultimas 25 aglomeraciones de la ejecucion de average linkage con el
numero de enlaces como medida.
Al respecto de esta problematica, Guha [11] sugiere detener la ejecucion del
algoritmo cuando a este le resta un multiplo pequeno del numero esperado de clusters
por aglomerar. En este momento se filtran los clusters muy pequenos, y luego se
continua con la aglomeracion. En nuestra implementacion de ROCK, detenemos el
algoritmo con 18 clusters restantes y filtramos los clusters que contienen menos de
un 3 % del numero total de datos. Utilizaremos esta estrategia para automatizar el
manejo de datos atıpicos en todos los algoritmos mencionados anteriormente. Esto
5 de diciembre de 2018
3.5. Resultados 43
completa la descripcion de los algoritmos que pondremos a prueba a continuacion.
3.5. Resultados
Medimos el ındice V I de proximidad entre el clustering obtenido de la ejecucion
de cada algoritmo en cada uno de los conjuntos simulados. Las graficas de esta
seccion presentan estas mediciones; para cada criterio de variacion (tamano del
conjunto de datos, grado de exclusividad de los clusters y desbalance de la muestra)
utilizamos una grafica para comparar la bondad del clustering producido por cada
algoritmo al variar dicho criterio.
Como punto de comparacion para los ındices V I observados, hemos agregado
a cada una de las graficas una linea punteada que indica la entropıa de la varia-
ble aleatoria asociada al verdadero clustering. Equivalentemente, esta representa
el ındice V I entre el verdadero clustering y un clustering compuesto por un unico
cluster que contiene la totalidad del conjunto de datos.
Tamano del conjunto de datos variable
Figura 3.2: Comparacion del ındice V I del resultado de cada algoritmo al variar el
tamano del conjunto de datos.
Los algoritmos basados en el coeficiente de Jaccard no parecen beneficiarse de la
5 de diciembre de 2018
3.5. Resultados 44
presencia de una gran cantidad de datos. Esto no es sorprendente pues esta medida
de similaridad no tiene en cuenta las caracterısticas del conjunto de datos al cual una
pareja pertenece. Por otro lado, aquellos basados en el numero de enlaces parecen
presentar un patron: una reduccion inicial de V I al incrementar N , seguida por el
comportamiento contrario con respecto a N (presenta ”valles”). Podemos interpretar
este comportamiento de la siguiente manera. Inicialmente, los incrementos de N
hacen mas informativas a las vecindades al rededor de cada punto, incrementando la
capacidad de los algoritmos de asociar puntos del mismo cluster. Posteriormente, N
se hace tan grande que estas vecindades son tan informativas como pueden llegar
a serlo. Sin embargo, mientras mayor sea N , mayor es el problema de clasificacion
que enfrenta el algoritmo, de modo que su ındice V I incrementa con N .
Sobreposicion de los clusters variable
Figura 3.3: Comparacion del ındice V I del resultado de cada algoritmo al variar el
grado de exclusividad de cada cluster.
Como era de esperarse, cada disminucion en el grado de sobreposicion implico,
para todos los algoritmos, una disminucion en su distancia al verdadero clustering.
Bajo el menor grado de sobreposicion, incluso un algoritmo poco sofisticado como
Avg(J) fue exitoso en reconocer la estructura de los datos. Por otro lado podemos
ver que, en los casos no extremos, los algoritmos basados en el numero de enlaces
5 de diciembre de 2018
3.6. Discusion 45
fueron mas robustos con respecto a esta variable. Esto se debe a que las medidas
de similaridad locales (que solo tienen cuenta la pareja de puntos en cuestion)
son sensibles a coincidencias en escenarios de clusters sobrepuestos. El numero de
enlaces, en cambio, es una medida de similaridad global. Aun si dos transacciones de
clusters diferentes coincidencialmente contengan conjuntos similares de productos,
probablemente no habra una vecindad al rededor de ambas de ellas para evidenciar
su conexion, y por ende presentaran un bajo numero de enlazamiento. Esta es una
de las bondades fundamentales del numero de links como medida de similaridad.
Desbalance de la muestra
Puede encontrar una descripcion de cada uno de los escenarios de sobrerrepre-
sentacion analizados en el cuadro 3.1. Cada uno pretende ser mas extremo que los
anteriores. Note que, a mayor grado de desbalance en la muestra, menor sera la
entropıa asociada al clustering verdadero, cuyo maximo se alcanza en una muestra
perfectamente balanceada. Como concecuencia, en esta grafica observamos cierta
proporcionalidad entre el ındice V I y cantidad de informacion contenida en el clus-
tering verdadero. Esto no es sorprendente, dado que uno de los sumandos de V I
involucra a esta entropıa. Sin embargo, esta puede ser una consideracion importante
si queremos comparar valores de V I bajo clusterings de referencia diferentes; es mas
facil tener un ındice V I bajo si el clustering verdadero tiene una baja entropıa.
3.6. Discusion
3.6.1. Single linkage
En las graficas parece solo haberse graficado el algoritmo de single linkage que
utiliza el coeficiente de Jaccard. En realidad, este y Single(links) producen resultados
tan similares que es imposible distinguirlos por su ındice V I . Por otro lado notara
que su ındice V I suele estar muy cerca de la linea que indica un clustering trivial.
Esto se debe a que, en la totalidad de sus ejecuciones, el algoritmo produjo un unico
cluster de tamano considerable. Segun Everitt [1], este algoritmo no suele tener en
5 de diciembre de 2018
3.6. Discusion 46
Figura 3.4: Indice V I del resultado de cada algoritmo en cuatro escenarios de so-
brerrepresentacion de algunas de las poblaciones.
cuenta la estructura de clusters de una poblacion. Sin embargo, puede ser aplicado
en el analisis de clusters como metodo de deteccion de valores atıpicos.
3.6.2. Complete linkage
Consistentemente, estos algoritmos tuvieron un mal desempeno segun este ındice.
Una de las razones principales puede ser que, dado que estamos tratando con datos
de atributos categoricos, las medidas que utilizamos casi siempre son discretas y
pueden tomar el valor 0. Por ejemplo, en la simulacion base (N = 1200), Compl(J)
no consiguio agrupar mas de 36 datos en un solo cluster antes de que su medida
de bondad se hiciera 0 para todas las parejas de clusters. En la misma simula-
cion, Compl(links) solo consiguio agrupar 372 de los datos en clusters de tamano
considerable.
Este bajo desempeno tambien es atribuible a la naturaleza del ındice V I . Segun
vimos, V I(C,D) es proporcional a la entropıa asociada a cada uno de los cluste-
rings. Por otro lado, en el Capıtulo 1 vimos que complete linkage tiende a generar
particiones altamente balanceadas (vea, por ejemplo, el dendrograma de la figura
1.2). Como consecuencia, los clusterings que generan suelen presentar una entropıa
alta, lo cual a su vez tiende a incrementar el valor de V (C,D).5 de diciembre de 2018
3.6. Discusion 47
N = 900 N = 1200 N = 1800
0 1 146 0 0 0 193 1 0 287 0
149 0 1 0 0 200 0 0 297 3 0
2 0 143 0 0 0 187 0 0 300 0
0 149 0 1 198 0 2 0 298 2 0
0 0 112 4 0 1 189 1 2 259 0
0 0 1 149 0 0 4 196 1 4 293
Cuadro 3.3: Matrices de confusion del resultado de algunas ejecuciones de Avg(links).
3.6.3. Average linkage
En el caso de Avg(links), este mostro, consistentemente, el mejor desempeno con
respecto al ındice V I . Esto muestra el potencial de la idea intuitiva de aglomerar dos
clusters si, en promedio, presentan un alto numero de enlaces entre puntos de cada
cluster. Esto es razonable si buscamos clusters con un alto nivel de enlazamiento
interno.
Lo anterior no significa que sea un algoritmo ideal. De hecho, su grado de exito en
este analisis puede ser atribuido parcialmente a la utilizacion de V I como medida de
bondad. Para una simulacion, podemos analizar relacion entre el clustering verdadero
y el producido por Avg(links) a traves de una confusion. En el ındice (i, j), la matriz
de confusion informa el tamano de la interseccion entre el i-esimo cluster verdadero
y el j-esimo producido por Avg(links). Solo tendremos en consideracion los clusters
calculados cuyo tamano supera el 3 % de N . El cuadro 3.3 muestra la matriz de
confusion correspondiente a tres simulaciones.
Note como, por ejemplo, los clusters verdaderos 1, 3 y 5 fueron unidos en los tres
casos. Estos son los clusters de menor parametro t, por lo cual son los mas difusos. Los
algoritmos los aglomeraron de diferentes formas, pero ninguno realmente fue exitoso
en capturar alguno de estos clusters. Avg(links) opto por unirlos en muchos casos,
resultando en clusterings conformados por clusters grandes de tamano similar. Como
vimos anteriormente, V I guarda cierto grado de proporcionalidad con la entropıa de
cada clustering que compara. De modo que podemos atribuir, al menos parcialmente,
5 de diciembre de 2018
3.6. Discusion 48
C1 C2 C3 C4 C5 C6
n 175 160 185 30 115 154
t 13.6 14.4 4.8 6.4 4.9 14.84
m 185 134 257 100 184 159
b 4.13 2.13 4.28 2 3.14 1.16
Cuadro 3.4: Caracterısticas de los clusters generados por CROCK en el conjunto de
datos con N = 900.
los bajos valores de V I obtenidos por Avg(links) a las caracterısticas de los clusters
que genera.
3.6.4. CROCK
En comparacion con ROCK y Avg(links), CROCK no fue muy exitoso en la tarea de
revelar la estructura de clusters en los diferentes conjuntos de datos, al menos segun
el ındice V I . Para entender el tipo de clusters generados por CROCK, es pertinente
recordar la medida de bondad de un cluster a la cual responde. La heurıstica ROCK,
y por consiguiente CROCK, busca generar un clustering cuyos clusters tengan altos
valores de la medida de bondad
b(C) = links(C)E[links(C)] .
El cuadro 3.4 resume las caracterısticas de los clusters generados por CROCK
en el conjunto de datos con N = 900. El cluster con la mayor medida de bondad,
C3, esta definido sobre muchos mas productos de los que esperabamos (maximo
150). Dado que, ademas, tiene un tamano promedio de transaccion pequena, este
define un cluster muy disperso, por lo cual E[links(C3)] es pequeno. Dadas estas
caracterısticas, una posible forma de que b(C3) sea alto es que C3 este compuesto
por aglomeraciones de diferentes clusters, lo cual elevarıa el valor de links(C3). La
matriz de confusion en el cuadro 3.6 parece sugerir que este es el caso; observe como
la columna 3 de la matriz evidencia que C3 contiene tres subconjuntos de tamano
considerable de diferentes clusters verdaderos.
5 de diciembre de 2018
3.6. Discusion 49
C1 C2 C3 C4 C5 C6
n 175 160 185 30 115 154
t 13.6 14.4 4.8 6.4 4.9 14.84
m 186 243 270 199 279 150
b 4.1 9.29 26.6 4.27 14.94 1.19
Cuadro 3.5: Caracterısticas de los clusters generados por CROCK en el conjunto de
datos con N = 1200.
N = 900 N = 1200
4 3 103 3 3 0 8 51 16 47 77 0
0 150 0 0 0 0 0 0 199 0 1 0
17 0 41 0 87 0 49 54 46 3 15 0
149 0 1 0 0 0 1 0 1 1 197 0
5 7 40 27 25 4 32 43 28 46 12 0
0 0 0 0 0 150 0 0 1 1 3 195
Cuadro 3.6: Matrices de confusion del resultado de algunas ejecuciones de CROCK.
5 de diciembre de 2018
3.7. Conclusiones 50
Este fenomeno parece estar presente en todos los clusterings generados por
CROCK. Los clusters C2, C3 y C5 del clustering correspondiente al conjunto de datos
con N = 1200 son ejemplos adicionales del mismo. Esta caracterıstica de CROCK
podrıa llegar a hacerlo util en un contexto en el cual se cuente con clusters altamente
dispersos. Sin embargo, para el presente problema, podemos considerar este tipo de
estructura un artefacto de la medida de bondad b(C).
3.6.5. ROCK
Dada la estrecha relacion entre ROCK y CROCK, es razonable pensar que la
problematica identificada para CROCK en la seccion anterior aparecera tambien en
ROCK cuando la aproximacion de E[links[Ci,Cj]] sea cercana a su valor exacto.
3.7. Conclusiones
A traves de la evaluacion empırica realizada, se evidencio el potencial del numero
de enlaces para revelar la similaridad entre dos datos a partir de las propiedades del
conjunto total de datos. En cuanto al uso de la metrica V I , tomada entre un clustering
de referencia y uno de interes para validar el mecanismo que genero el segundo,
notamos que esta tiende a favorecer clusterings con una menor entropıa asociada.
Finalmente, identificamos una problematica en la heurıstica CROCK, introducida por
la medida de bondad de clusters, b(C), que el algoritmo pretende maximizar. Como
consecuencia de esta, el algoritmo genera clusters que difıcilmente corresponden a
una subpoblacion del conjunto de datos en cuestion, pero que por sus caracterısticas
presentan altos valores de b(C).
5 de diciembre de 2018
Bibliografıa
[1] M. Leese D. Stahl B. S. Everitt, S. Landau. Cluster Analysis. John Wiley &
Sons, Ltd, 5 edition, 2011.
[2] R. E. Bonner. On some clustering techniques. IBM J. Res. Dev., 8(1):22–32,
January 1964.
[3] M. R. Brito, A. J. Quiroz, and Joseph E. Yukich. Intrinsic dimension identification
via graph-theoretic methods. J. Multivariate Analysis, 116:263–277, 2013.
[4] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley
Series in Telecommunications and Signal Processing). Wiley-Interscience, New
York, NY, USA, 2006.
[5] Legendre P. Gower, J. C. Metric and euclidean properties of dissimilarity coef-
ficients. Journal of Classification, 3(1):5–48, Mar 1986.
[6] Norbert Henze. A multivariate two-sample test based on the number of nearest
neighbor type coincidences. The Annals of Statistics, 16(2):772–783, 1988.
[7] M. Meila. Comparing clusterings - an information based distance. Journal of
Multivariate Analysis, 2007.
[8] Heckerman David Meila, Marina. An experimental comparison of several clus-
tering and initialization methods. In Proceedings of the Fourteenth Conference
on Uncertainty in Artificial Intelligence, UAI’98, pages 386–395, San Francisco,
CA, USA, 1998. Morgan Kaufmann Publishers Inc.
51
Bibliografıa 52
[9] Glenn W. Milligan and Martha C. Cooper. An examination of procedures for
determining the number of clusters in a data set. Psychometrika, 50(2):159–
179, Jun 1985.
[10] D.G. Stork R.O. Duda, P.E. Hart. Pattern Classification. Wiley, 2001.
[11] K. Shim S. Guha, R. Ratogi. Rock: A robust clustering algorithm for categorical
attributes. Proceedings 15th International Conference on Data Engineering,
1999.
[12] Z. Hlavka W. Hardle. Mutivariate Statistics. Springer Science+Business Media,
2007.
5 de diciembre de 2018
Recommended