**Algoritmos de Clustering** ![](./img/meanshift2.gif align="right" width=300px)Un **algoritmo de clustering** tiene como objetivo agrupar los objetos de un dataset según su **similaridad**, de forma que los objetos que hay dentro de un grupo (**cluster**) sean más similares que aquellos que caen en grupos distintos. !!!side:1 Sobre las dificultades inherentes al problema, puede ser interesante [leer este blog](http://alexhwilliams.info/itsneuronalblog/2015/09/11/clustering1/). Desde un punto de vista intuitivo, este problema tiene un objetivo muy claro: agrupar adecuadamente un conjunto de datos no etiquetados. A pesar de que intuitivamente no parece ser una idea muy compleja y los humanos agrupamos por similaridad de forma natural, veremos que la noción de **clúster/agrupamiento** no puede ser definido con precisión, y es una de las causas por las que se ha propuesto un rango tan amplio de algoritmos de clustering y por qué no ofrecen soluciones satisfactorias de forma general [1].  Para resolver este problema se han desarrollado muchos algoritmos que se diferencian entre sí según qué se entiende por cluster (que, en esencia, viene dado por cómo definimos que dos objetos son más o menos similares) y por la eficiencia computacional a la hora de conseguir la agrupación final. # Axiomatización !!!side:2 A veces nos conformamos con algo que no llega a cumplir todas las propiedades de una **distancia/métrica** y trabajamos con lo que se conocen como **pseudo-métricas**. Normalmente, para poder hablar de similaridad se suele acudir a algún tipo de **distancia** [2], con el fin de poder asociar la similitud de los objetos analizados con la distancia que hay entre ellos. Por ejemplo, si podemos describir el objeto por medio de un vector numérico de propiedades, es entonces habitual tratar con métricas vectoriales (como la **distancia euclídea**) para medir la similitud entre los objetos. !!!def: Distancias Sea $X = \{1,\dots , n\}$ sea un conjunto de datos. Una función $d:X × X → \mathbb{R}$ es una **función de distancia** si: * $d(x_i , x_i) ≥ 0$ para todo $x_i ∈ X$. * Para todo $x_i, x_j ∈ X$, $d(xi, xj ) > 0$ si y sólo si $x_i \neq x_j$ , y * Para todo $x_i, x_j ∈ X$, $d(x_i , x_j ) = d(x_j , x_i)$. Obsérvese que no necesitamos la desigualdad triangular. !!!def: $k$-Clustering Un **$k$-Clustering**, $C = \{C_1, \dots, C_k\}$ de $X$ es una $k$-partición de $X$, es decir, $C_i ∩ C_j = ∅$ para $i \neq j$ y $∪_{i=1}^k C_i = X$. Un **clustering** de $X$ es un $k$-clustering de $X$ para algún $k ≥ 1$. Para $x, y ∈ X$ y un clustering $C$ de $X$, escribimos $x \sim_C y$ siempre que $x$ e $y$ estén en el mismo cluster del clustering $C$ y $x \sim_C y$, en caso contrario. !!!def:Función de Clustering Una **función de clustering** para un dominio $X$ es una función $f$ que toma una función de distancia $d$ sobre $X$ y produce una partición de $X$. !!!side:3 En *[An impossibility theorem for clustering](https://www.cs.cornell.edu/home/kleinber/nips15.pdf)*, 2002. !!!side:4 Se puede ver una buena [introducción aquí](http://alexhwilliams.info/itsneuronalblog/2015/10/01/clustering2/). Jon Kleinberg [3] propone tres axiomas que destacan las características que debe presentar un problema de agrupamiento y que pueden considerarse buenas, independientemente del algoritmo utilizado, para encontrar la solución. Estos axiomas son [4]: * **Invarianza por escala**: Un algoritmo de clustering no debe dar resultados distintos si se aplica una escala al conjunto de puntos. Es decir, no depende de la escala del observador, sino de la relación intrínseca entre los puntos.  !!!def: Invarianza por Escala Una función $f$ es **invariante por escala** si para cada función de distancia $d$ y $λ > 0$, $f(d) = f(λd)$ (donde $λd$ se define estableciendo, para cada par de puntos de dominio $x$, $y$, como $λd(x, y) = λ \cdot d(x, y)$). * **Consistencia**: Un algoritmo de clustering no debe dar resultados distintos si las distancias dentro de cada clúster se reducen, o si las distancias entre clusters se aumentan.  !!!def: Consistencia Una función de distancia $d'$ es una **variante C-consistente** de $d$, si $d'(x, y) ≤ d(x, y)$ para todo $x \sim_C y$, y $d'(x, y) ≥ d(x, y)$ para todo $x \nsim_C y$. Una función f es **consistente** si $f(d) = f(d')$ siempre que $d'$ sea una variante $f(d)$-consistente de $d$. * **Riqueza**: La función de agrupación debe ser lo suficientemente flexible como para producir cualquier partición/agrupación arbitraria del conjunto de datos de entrada. Es decir, no debe estar sesgado a producir ciertas agrupaciones y evitar otras.  !!!def: Riqueza Una función $f$ es rica si para cada clustering $C$ de $X$, existe una función de distancia $d$ sobre $X$ tal que $f(d) = C$. El resultado más interesante del trabajo de Kleinberg es que, pese al claro carácter intuitivo de estos axiomas, no se puede construir una función de clustering que verifique los tres simultáneamente.  Y ya que los tres axiomas no pueden verificarse simultáneamente, se pueden diseñar algoritmos de clustering que violan uno de los axiomas mientras se verifican los otros dos. Kleinberg ilustra este punto describiendo tres variantes del tipo particular de jerárquico (que veremos más abajo, como ejemplo de algoritmo de clustering): * **Condición de parada del $k$-cluster**: Dejar de unir clústers cuando ya hay $k$ clústers (viola el axioma de riqueza, ya que el algoritmo nunca devolvería un número de clusters diferente a $k$).  * **Condición de parada de la $r$-distancia**: Dejar de unir clústers cuando el par más cercano de ellos está más lejos que $r$ (viola la invarianza de escala, ya que cada clúster contendrá una sola instancia cuando la escala es grande, y un solo clúster con todos los datos cuando la escala es muy pequeña).  * **Condición de detención de la escala**: Dejar de unir clústers cuando el par de clústers más cercano está más lejos que una fracción de la distancia máxima por pares (se satisface la invarianza de escala, pero se viola la consistencia).  # Clasificación Según la forma en que los clusters se relacionan entre sí y con los objetos del dataset, podemos establecer una primera división entre los diversos algoritmos existentes: * **Clustering Duro**: en el que cada punto debe pertenecer a un solo cluster (por lo que los clusters pasarían a ser algo así como una partición del dataset). * **Clustering Blando** (o **difuso**): en el que los puntos pertenecen a los clusters según un grado de confianza (o grado de pertenencia). Pero a veces también podemos encontrar una clasificación más fina atendiendo a cómo se relacionan con detalle: * **Partición estricta**: cada punto pertenece exactamente a un cluster. * **Partición estricta con outliers**: puede haber puntos que no pertenecen a ningún cluster (los outliers). * **Clustering con superposiciones**: un punto puede pertenecer a más de un cluster. * **Clustering Jerárquico**: Los clusters se ordenan jerárquicamente de forma que los puntos que pertenecen a un cluster también pertenecen a su cluster padre. # Representantes Entre la diversidad de aproximaciones existentes en la literatura, en esta entrada nos vamos a centrar en algunas de las más representativas. Concretamente, los algoritmos que veremos a continuación son: * **K-medias**: modelo de centroides.  * **DBSCAN**: modelo de densidad discreto.  * **Mean Shift**: modelo de gradientes en densidad.  * **AGNES**: modelo jerárquico.  ## K-medias Este algoritmo intenta encontrar una partición de las muestras en $K$ (parámetro del algoritmo) agrupaciones, de forma que cada ejemplo pertenezca a una de ellas, concretamente a aquella cuyo centroide esté más cerca. El mejor valor de $K$ para que la clasificación separe lo mejor posible los ejemplos no se conoce a priori, y depende completamente de los datos con los que trabajemos. Este algoritmo intenta minimizar la varianza total del sistema, es decir, si $c_i$ es el centroide de la agrupación $i$-ésima, y $\{x_{ij}\}_j$ es el conjunto de ejemplos clasificados en esa agrupación, entonces intentamos minimizar la función: $$ \sum_i \sum_j d(x_{ij},c_i)^2 $$ que, a veces suele denominarse **función potencial**. Aunque podríamos utilizar cualquier algoritmo de optimización para realizar esta tarea, en este caso existe un algoritmo recursivo que converge a una solución local (un mínimo local de la función potencial) de forma rápida y relativamente eficiente: ~~~~~~~~none K-MEANS(D,K) [D: Dataset, K > 0] C = {c1,...,ck} ⊆ D (cualesquiera) Asignar Di = {P ϵ D: d(P,ci) < d(P,cj), j ≠ i}, i = 1...K Mientras algún ci cambie: Calcular ci = centroide(Di), i=1...K Recalcular Di, i = 1...K Devolver {D1,...,DK} ~~~~~~~~  !!!side:5 Algo muy común cuando se trabaja con un problema de optimización no convexo. El algoritmo anterior es relativamente eficiente, y normalmente se requieren pocos pasos para que el proceso se estabilice. Pero, en su contra, es necesario determinar el número de agrupaciones a priori, y el sistema es sensible a la posición inicial de los $K$ clusters, por lo que una mala selección inicial puede hacer que no se alcance un mínimo global, sino que se sitúe en un mínimo local [5]. Por desgracia, no existe un método teórico global que permita encontrar el valor óptimo de grupos ni las posiciones en las que debemos situar los centros inicialmente, por lo que se suele hacer una aproximación experimental repitiendo el algoritmo con diversos valores y posiciones de centros. Un valor elevado de $K$ hace que el error disminuya, pero a cambio disminuye la cantidad de información que la agrupación resultante proporciona. ## DBSCAN !!!side:6 Pudiendo llegar a ser de tiempo $O(n^2)$ en el peor caso. **DBSCAN** (**Density-Based Spatial Clustering of Applications with Noise**) es un algoritmo de clustering creado en 1996 por [M. Ester y otros](https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf), no paramétrico, basado en densidades, y que marca como outliers aquellos puntos que no superan un umbral de densidad establecido. Constituye uno de los algoritmos de clustering más usados y citados, y también es relativamente eficiente cuando se usan estructuras de datos adecuadas para su implementación [6]. El algoritmo recibe como dato de entrada dos valores que, juntos, determinan la densidad mínima: * $\varepsilon$, que fija el radio de los entornos que se mirarán alrededor de los puntos del conjunto, y * $MinPts$, que establece el número mínimo de puntos que debe haber en el entorno para que se considere que se supera la densidad mínima. Con estos parámetros prefijados, el algoritmo opera como sigue: ~~~~~~~~none DBSCAN(D, ε, MinPts) [D: Dataset; ε > 0; MinPts >0] C = ∅ Para cada P ϵ D no visitado: Marcar P como visitado N = E(P, ε) Si tamaño(N) < MinPts: marcar P como OUTLIER si no: C = C ⋃ {creaCluster(P, N, ε, MinPts)} Devolver C ~~~~~~~~ Donde: ~~~~~~~~none creaCluster(P, N, ε, MinPts) [P ϵ D; N entorno de P; ε > 0; MinPts > 0] Cl = {P} Para cada P' ϵ N: Si P' no ha sido visitado: marcar P' como visitado N' = E(P', ε) Si tamaño(N') ≥ MinPts: N = N ⋃ N' Si P' no está en ningún cluster: Cl = Cl ⋃ {P'} Devolver Cl ~~~~~~~~ y $$ E(P,\varepsilon)=\{P'\in D:\ d(P,P')<\varepsilon\} $$  Esencialmente, el algoritmo comienza por un punto con suficiente densidad y va construyendo un cluster añadiendo puntos cercanos relevantes al mismo. Cuando acaba de construir un cluster, salta a otro punto con suficiente densidad y construye otro cluster independiente. En comparación con K-medias, DBSCAN presenta las siguientes ventajas: * No es necesario especificar el número de clusters deseado. * Puede encontrar clusters con formas geométricas arbitrarias. Gracias al parámetro $MinPts$, se reduce la posibilidad de que aparezcan clusters distintos conectados por una delgada línea de puntos. * Tiene capacidad de detectar outliers (y ruido). !!!side:7 Solo puede haber indeterminismo en los puntos fronterizos entre dos clusters distintos, que pueden acabar asignados a uno u otro, pero no es fácil que ocurra, y el número de puntos involucrados es comparativamente bajo. * Solo necesita dos parámetros y no importa el orden de recorrido de los puntos para la construcción final de los clusters [7]. * Usando estructuras de datos adecuadas se puede dar una implementación bastante más rápida. A cambio, presenta algunas desventajas, que no son específicas, sino comunes a muchos algoritmos de clustering: * El uso de distancias equivalentes a la euclídea puede dar resultados indeseados en dimensiones altas. * Los valores de $(MinPts,\ \varepsilon)$ se pueden adaptar para tratar conjuntos de densidades específicas, por lo que si hay conjuntos con mucha diferencia en sus densidades, no hay combinación de valores que puedan trabajar adecuadamente para todos ellos a la vez. Además, se puede usar en datasets que no se representan necesariamente en espacios vectoriales, ya que solo precisa tener definida una distancia entre puntos, no de la representación completa. ## Mean Shift Esta aproximación se basa en el concepto de **Kernel de Estimación de Densidad** (**KDE**). La idea es suponer que el conjunto de puntos que se quiere procesar proviene del muestreo de una distribución de probabilidad desconocida. KDE proporciona un método para estimar la distribución subyacente. Funciona poniendo una función (**kernel**) en cada uno de los puntos que representa una ponderación. Hay muchas posibles funciones que usar como ponderaciones puntuales, pero quizás la más habitual es el kernel **Gaussiano**: $$ K(x)=e^{-\frac{(x-x_i)^2}{2h^2} } $$ Cambiando la función kernel (o los parámetros de un kernel específico) se obtiene una estimación distinta de la función de densidad. Por ejemplo, si los kernels son muy concentrados en cada punto (en el kernel Gaussiano se consigue haciendo $h\approx 0$ muy pequeño), entonces la función de densidad obtenida separará los puntos entre sí (como pequeños picos que los aíslan), si los kernels son muy suavizados (en el kernel Gaussiano se consigue haciendo $h\approx 1$), entonces la función de densidad se asemejará a una gran meseta que conecta los diversos puntos entre sí.  !!!side:8 De esta forma, se asocia cada cluster con las diversas cuencas de atracción de la función de densidad. Una vez obtenida la función de densidad, asociada a una posible distribución de probabilidad que ha generado del dataset, se puede usar esta densidad para establecer los distintos clusters que se asocian a la distribución de puntos. Para saber qué puntos están en el mismo cluster, el algoritmo **Mean Shift** aplica un proceso de ascenso de la colina para ver cuáles acaban en el mismo máximo [8]. Así pues, el algoritmo se podría describir brevemente como: ~~~~~~~~none MEAN-SHIFT(D,K) [D: Dataset; K: kernel] f(x) = ∑_{P ϵ D} K_P(x) (función de densidad centrada en P a partir de K) M = ∅ Para cada P ϵ D: M = M ⋃ Max(f,P) (aplicando grad(f) desde P) Para cada m ϵ M: C_m = {P ϵ D: Max(f,P) = m} Devolver {C_m: m ϵ M} ~~~~~~~~ El hecho de que Mean Shift no haga suposiciones acerca del número de clusters, o de la forma que tienen estos, lo convierten en un método ideal para trabajar con un número arbitrario de clusters y de formas arbitrarias. Aunque realmente el algoritmo que se ha explicado es realmente un algoritmo de optimización (los clusters se identifican con los máximos de la función de densidad), el uso de las diversas cuencas de atracción como clusters del dataset original proporciona una ingeniosa (y fructífera) identificación entre conceptos provenientes de mundos intuitivamente lejanos. ## AGNES Vamos a ver el que se conoce como algoritmo **AGNES** (**Agglomerative Nesting**), que es un algoritmo de **clustering aglomerativo**, es decir, va construyendo una jerarquía creciente de clusters desde los clusters más pequeños posibles, los puntos aislados, hasta el mayor cluster posible, que agrupa todos los puntos del dataset. En general, este algoritmo sigue los siguientes pasos: ~~~~~~~~none AGNES(D,N) [D: Dataset, N > 0] Cls = { {P} : P ϵ D} (un cluster unitario para cada P ϵ D) Mientras |Cls| > N: Sean C1, C2 en Cls: d(C1,C2) = min {d(Ci,Cj): Ci,Cj ϵ Cls} C12 = C1 ⋃ C2 Cls = Cls - {C1,C2} ⋃ {C12} Devolver Cls ~~~~~~~~  Se pueden introducir variantes en este algoritmo cambiando la forma de medir la distancia entre clusters. Es lo que se conoce como **Métodos de Conexión**: supuesto que tenemos una distancia, $d$, definida entre los puntos del dataset, las distancias entre clusters más habituales son: 1. **Conexión completa**: $d_{max}(C_1,C_2)=max\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$. 2. **Conexión simple**: $d_{min}(C_1,C_2)=min\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$. 3. **Conexión media**: $d_{mean}(C_1,C_2)=mean\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$. 4. **Conexión centroide**: $d_{cent}(C_1,C_2)=d(c_1,c_2)$, donde $c_i=centroide(C_i)$. Se debe tener en cuenta que no hay ninguna elección mejor que otra, y que diferentes distancias ofrecerán diferentes agrupaciones resultantes. Debido a la complejidad de representar simultáneamente toda la jerarquía de clusters que aparece en este tipo de algoritmos, se han ideado formas esquemáticas para mostrarlos atendiendo al orden y dando una idea de la lejanía que hay entre los diversos clusters que aparecen. La más común de ellas es la que se conoce como **dendogramas**, que permiten hacerse una idea de todas las agrupaciones de forma bastante sencilla:  En este tipo de representaciones, además, la altura de los bloques representa la distancia entre los clusters que se unen. En cada altura, el número de ejes verticales indica cuántos clusters hay en ese nivel jerárquico. Este tipo de algoritmos tienen ventajas claras sobre el algoritmo base de K-medias como, por ejemplo, que no necesita que los datasets se representen en espacios vectoriales, ya que solo precisa de la existencia de una distancia entre puntos, no de proyectarlos completamente. Por contra, no es especialmente adecuado cuando el dataset es muy grande, porque hay que calcular muchas distancias cruzadas. Existen variantes similares que siguen el proceso contrario: partiendo del cluster formado por todos los elementos del dataset, van dividiendo sucesivamente los clusters presentes para separar aquellos en los que se encuentra mayor disimilaridad entre sus elementos. # Métricas Determinar la calidad de los resultados proporcionados por un algoritmo de clustering no es un problema fácil. !!!def: Medidas de Calidad Una **medida de calidad** de un clustering es una función que recibe un clustering $C$ sobre $(X, d)$ (donde $d$ es una función de distancia sobre $X$) y devuelve un número real no negativo. Cuando se analizan los resultados de una clusterización se deben tener en cuenta varios aspectos para la validación de los resultados del algoritmo: * La determinación de la tendencia de agrupación de los datos (es decir, si existe realmente una estructura no aleatoria). * Determinar el número correcto de clústers. * Evaluar la calidad de los resultados de la agrupación sin información externa. * Comparar los resultados obtenidos con la información externa. * Comparar dos agrupaciones distintas para determinar cuál es mejor. Las tres primeras cuestiones se abordan mediante una validación interna o no supervisada, ya que no se utiliza información externa. La cuarta cuestión se resuelve mediante una validación externa o supervisada. Por último, la última cuestión puede abordarse mediante técnicas de validación supervisada y no supervisada. En la literatura se ha propuesto una amplia gama de métricas para cuantificar la calidad de los resultados de la agrupación: * Las **métricas de validación interna** no requieren información externa. Estas métricas se centran en la medición de la cohesión y la separación de los clusters, en el análisis estadístico de la matriz de proximidad o en el estudio del dendrograma generado por los algoritmos de clustering jerárquico. * Las **métricas de validación externa** recurren a información externa para evaluar la calidad de los resultados de clustering. Tenemos a nuestra disposición un gran número de métricas de validación externa, que van desde los conjuntos de coincidencia hasta la correlación entre pares y los índices teóricos de información. Las métricas de validación externa también son útiles cuando se comparan los resultados proporcionados por diferentes algoritmos de clustering (o el mismo algoritmo con diferentes conjuntos de valores de parámetros). Encontrar la mejor configuración de los parámetros de un algoritmo se conoce como ajuste de hiperparámetros. Este proceso suele ser necesario, por ejemplo, para determinar el número óptimo de clusters para un problema de clustering concreto. ## Validación Interna Como hemos comentado, las **métricas de validación interna** no requieren información externa, y solo hacen uso de mediciones que pueden obtenerse a partir de los puntos originales del conjunto y los diferentes clusters que devuelve el algoritmo aplicado. En casos como el de la clusterización en espacios métricos se puede medir algo parecido a un **Potencial de estrés** de la agrupación conseguida (tal y como hemos justificado en el modelo de K-medias visto anteriormente), por ejemplo: !!!def:Potencial de Estrés $$Potencial(C)=\sum_{c\in C} \sum_{x\in c} d(x,centroid(c))^2$$ En esta métrica, los valores más próximos a $0$ son mejores, ya que cuanto más se acerque a $0$ la distancia media, más agrupados estarán los datos. Ha de tenerse en cuenta, sin embargo, que esta métrica siempre disminuye si se aumenta el número de clústeres y, en el caso extremo (en el que cada uno de los distintos puntos de datos es su propio clúster) será igual a $0$, así que ha de mantenerse un equilibrio entre el número de clústeres y el potencial obtenido. Otra métrica interesante en este caso es el **Índice de Davies Bouldin**, que se calcula como la relación media entre las distancias dentro del clúster (cohesión) y las distancias entre clústeres (separación). Cuanto más ajustado sea el clúster y más separados estén los clústeres, más bajo será este valor, por lo que los valores más próximos a $0$ son mejores. Los clústeres que estén más separados y menos dispersos generarán una mejor puntuación. !!!def:Índice de Davis Bouldin $$ I_{DB}= \frac {mean{\{d(x,x'):\ x,x' \in c\}_{c\in C} } } { mean{\{d(x,x'):\ x\in c,\ x'\notin c\}_{c\in C} } }$$ donde $C$ es el conjunto de clusters calculados por el modelo. A veces esta métrica se simplifica haciendo uso de los centroides (por ejemplo, en caso de usar K-medias), y en ese caso las cohesiones se calculan como la distancia media de cada punto a su centroide, y las separaciones se calculan como distancias entre centroides. Otras herramientas habituales para evaluar algoritmos de clustering son el **Análisis de Siluetas** o la **regla del codo**, que no veremos aquí (y que cada vez se enfrentan a más críticas). Todas estas métricas son ejemplos de validaciones internas, ya que no usan información externa para evaluar la bondad de la agrupación conseguida. ## Validación Externa Los **métodos de validación externa** pueden asociarse a un problema de aprendizaje supervisado. La validación externa consiste en incorporar información adicional en el proceso de validación del clustering, es decir, etiquetas de clase externas para los ejemplos de entrenamiento. Dado que las técnicas de aprendizaje no supervisado se utilizan principalmente cuando no se dispone de dicha información, los métodos de validación externa no se utilizan en la mayoría de los problemas de clustering. Sin embargo, aún pueden aplicarse cuando se dispone de información externa y también cuando se generan datos sintéticos a partir de uno real. Queremos comparar el resultado de un algoritmo de clustering, $C$, con una partición potencialmente diferente de los datos, $P$, que podría representar el conocimiento experto del analista (su experiencia o intuición), el conocimiento previo de los datos en forma de etiquetas de clase, los resultados obtenidos por otro algoritmo de clustering o, simplemente, una agrupación considerada *correcta*. Para llevar a cabo este análisis, hay que construir una **matriz de confusión** para evaluar los clusters detectados por el algoritmo. Esta matriz de confusión contiene cuatro términos: * $T_P$: El número de pares de datos encontrados en el mismo cluster, tanto en $C$ como en $P$. * $F_P$: El número de pares de datos encontrados en el mismo cluster en $C$ pero en diferentes clusters en $P$. * $F_N$: El número de pares de datos encontrados en diferentes clusters en $C$ pero en el mismo cluster en $P$. * $T_N$: El número de pares de datos encontrados en diferentes clusters, tanto en $C$ como en $P$. Obviamente, el número total de pares debe ser $M = T_P + F_P + F_N + T_N = \frac{n(n - 1)}{2}$, donde $n$ es el número de puntos. La primera familia de métodos de validación externa que puede utilizarse para comparar dos particiones de datos consiste en aquellos métodos que identifican la relación entre cada cluster detectado en $C$ y su correspondencia natural con las clases del resultado de referencia definido por $P$. Se pueden definir varias medidas para medir la similitud entre los clusters en $C$, obtenidos por el algoritmo de clustering, y los clusters en $P$, correspondientes a nuestro conocimiento previo (externo): * La **Precision** cuenta los verdaderos positivos, cuántos ejemplos se clasifican correctamente dentro del mismo cluster: $$Pr = \frac{T_P}{T_P + F_P}$$ * El **Recall** evalúa el porcentaje de elementos que se incluyen correctamente en el mismo clúster: $$R = \frac{T_P}{T_P + F_N}$$ * La **F-métrica** combina las dos anteriores en una sola métrica, su media armónica: $$F =\frac{Pr ∗ R}{Pr + R}$$ * La **Pureza** evalúa si cada cluster contiene únicamente ejemplos de la misma clase ($p_i = n_i/n$, $p_j = n_j/n$, $p_{ij} = n_{ij}/n$, $n_{ij}$ es el número de ejemplos de la clase $i$ que se encuentran en el cluster $j$ y $n_i$ es el número de ejemplos del cluster $i$): $$U = \sum_i p_i \Big(\max_j \frac{p_{ij}}{p_i}\Big)$$ También existe una familia de métricas externas de validación de clusters que se basa en conceptos de **Teoría de la Información**, como la incertidumbre existente en la predicción de las clases naturales proporcionada por la partición $P$. Esta familia incluye medidas básicas como la entropía y la información mutua: * La **entropía** es una medida recíproca de pureza que permite medir el grado de desorden en los resultados de la agrupación: $$H = -\sum_i p_i\Big( \sum_j \frac{p_{ij}}{p_i} \log \frac{p_{ij}}{p_i}\Big)$$ * La **información mutua** permite medir la reducción de la incertidumbre sobre los resultados del clustering a partir del conocimiento de la partición previa: $$MI = \sum_i \sum_j p_j \log \frac{p_{ij}}{p_ip_j}$$ !!!side:9 Se puede encontrar un resumen de las métricas más habituales para clustering [aquí](https://arxiv.org/pdf/1905.05667.pdf). Muchas veces, un proceso de clusterización es correcto en la medida en que facilite la tarea posterior de realizar otros procesos de optimización/aprendizaje sobre la transformación que producen o la agrupación que proponen, por lo que la clusterización se convierte en una primera fase de extracción de información de los datos para posteriormente medir su eficacia de forma conjunta con un clasificador/regresor supervisado del que sí podemos medir su eficacia de forma más objetiva [9]. Aunque, por supuesto, el problema de clustering no es el único problema de Aprendizaje No Supervisado, sí es el más común y usado. Esa es la razón por la que se presenta en esta página como único ejemplo de este tipo de algoritmos en el uso de métricas de rendimiento, pero el lector no debe llevarse la falsa idea de que no hay otros problemas en esta clasificación ni otras métricas para ellos. (insert ../menu.md.html here)