Los criterios de calidad internos suelen medir la compacidad de los grupos utilizando una medida de similitud. Por lo general, mide la homogeneidad intragrupo, la separabilidad entre grupos o una combinación de estas dos. No utiliza información externa junto con los datos en sí.
Lista
- Suma del error cuadrático
- Criterios de dispersión
- Métrica de utilidad de categoría
- Medidas de corte
- salón de baile
- Banfeld-Raftery
- Criterio de Condorcet
- Criterio C
- Calinski-Harabasz
- Davies-Bouldin
- Relación_detonación
- Dunn
- GDImn
- Gama
- G+
- Ksq_DetW
- Log_Det_Ratio
- Log_SS_Ratio
- McClain-Rao
- PBM
- punto biserial
- Lanza Ratkawsky
- Ray Turi
- Scott Simons
- SD_Scat
- SD_Dis
- S_Dbw
- Silueta
- Traza W
- rastreo WiB
- Wemmert-Gançarski
- Xie-Beni
Cómo leer métricas de calidad interna
Para encontrar la mejor partición de los datos, generalmente ejecutamos una algoritmo de agrupamiento con diferentes valores del número esperado de clusters K: digamos que Km ≤ K ≤ KM. El algoritmo de agrupamiento aplicado podría ser el agrupamiento jerárquico ascendente (AHC) o el algoritmo k-means o cualquier otra técnica. Luego calculamos un índice de calidad QK para cada valor de K y seleccionamos la partición que condujo al "mejor" valor de QK.
En esta sección se explica cuál se considera el “mejor” valor para los diferentes índices de calidad.
La tabla resume, para cada índice, qué regla se debe aplicar para determinar el mejor valor del índice. Por ejemplo, en el caso del índice Calinski-Harabasz, si el índice de calidad se ha calculado para diferentes particiones de los datos, la mejor partición es la correspondiente al mayor valor del índice.
Las reglas de decisión llamadas max y min en la tabla significan seleccionar el valor de índice más grande o más pequeño, respectivamente. La regla de decisión denominada max diff significa que el mejor valor de K es el correspondiente a la mayor diferencia entre dos pendientes sucesivas. En un gráfico que representa los valores del índice versus número de grupos seleccionado, esto corresponde a un codo.
Suma del error cuadrático
Las métricas de calidad internas suelen medir la compacidad del clúster mediante una medida de similitud (como la Suma del error cuadrático). Por lo general, mide la homogeneidad dentro del grupo, la separabilidad entre grupos o una combinación de estos dos. No utiliza información externa junto con los propios datos.
La suma del error al cuadrado es la medida de criterio más simple y más utilizada para la agrupación. Se calcula como:
donde C_k es el conjunto de instancias del clúster k; μ_k es la media vectorial del grupo k. Los componentes de μ_k se calculan como:
donde N_k = | C_k | es el número de instancias que pertenecen al clúster k.
Los métodos de fraccionamiento que minimizan el criterio SSE a menudo se denominan particiones de varianza mínima, porque mediante una simple manipulación algebraica el criterio SSE se puede escribir:
La función de criterio SSE es adecuada para los casos en los que los clústeres forman nubes compactas bien separadas entre sí.
Se pueden generar criterios mínimos adicionales para SSE reemplazando el valor de S_k con expresiones como:
Criterios de dispersión
Las métricas de calidad interna generalmente miden la compacidad de los clústeres utilizando una medida de similitud (como los criterios de dispersión: seguimiento, determinante, invariancia). Por lo general, mide la homogeneidad dentro del grupo, la separabilidad entre grupos o una combinación de estos dos. No utiliza información externa junto con los propios datos.
Los criterios de difusión escalar se derivan de las matrices de difusión, reflejando la difusión intra-cluster, la difusión entre-cluster y su suma: la matriz de difusión total. Para el grupo k-ésimo, la matriz de difusión se puede calcular de la siguiente manera:
La matriz de dispersión intra-conglomerados se calcula como la suma de la última definición sobre todos los conglomerados W:
La matriz de difusión entre conglomerados se puede calcular de la siguiente manera:
donde μ es el vector medio total y se define como:
La matriz de difusión total debe calcularse de la siguiente manera:
Se pueden derivar tres criterios escalares de S_W, S_B y S_T.
La traza es la suma de los elementos diagonales de una matriz. Minimizar el rastro de S_W es similar a minimizar HSE y por lo tanto es de uso común. Este criterio, que representa la dispersión intra-cluster, se calcula de la siguiente manera:
Otro criterio, que se puede maximizar, es el criterio entre clusters:
El determinante de una matriz de dispersión mide aproximadamente el cuadrado del volumen de dispersión. Dado que S_B será singular si el número de grupos es menor o igual que la dimensionalidad, o si mc es menor que la dimensionalidad, su determinante no es un criterio apropiado. Si asumimos que S_W no es singular, la función del criterio determinante es:
Los valores propios λ_1, λ_2,. . . , λ_d de S_W * S_B son las invariantes lineales básicas de las matrices de difusión. Las particiones buenas son aquellas para las que los valores propios distintos de cero son grandes. Como resultado, se pueden derivar varios criterios, incluidos los valores propios. Tres de estos criterios son:
Utilidad de categoría
La utilidad de categoría se define como el aumento del número esperado de valores de entidad que pueden predecirse correctamente dada una determinada agrupación. Esta métrica es útil para problemas que contienen un número relativamente pequeño de características nominales, cada una de las cuales tiene una cardinalidad pequeña.
Medición de corte
En algunos casos, es útil representar el problema de agrupamiento como un problema de corte mínimo. En tales casos, la calidad se mide como la relación entre los pesos restantes y los pesos totales de corte. Si no hay restricciones sobre el tamaño de los clústeres, es fácil encontrar el valor óptimo. Por lo tanto, se revisa la medición del min-cut para penalizar las estructuras desequilibradas.
salón de baile
La dispersión promedio de un grupo es el promedio de los cuadrados de las distancias de los puntos del grupo a su baricentro. El índice de Ball-Hall es el promedio, en todos los conglomerados, de su dispersión media:
En el caso particular donde todos los clusters tienen el mismo tamaño N/K, esta suma se reduce a WGSS/N.
Banfeld-Raftery
Este índice es la suma ponderada de los logaritmos de las trazas de la matriz de varianza-covarianza de cada conglomerado.
El índice se puede escribir de la siguiente manera:
La cantidad Tr(WG{k})/nk se puede interpretar como el promedio de los cuadrados de las distancias entre los puntos del cluster Ck y su baricentro G{k}. Si un grupo contiene un solo punto, esta traza es igual a 0 y el logaritmo no está definido.
Concordeto
Otro enfoque adecuado es aplicar la solución de Condorcet al problema de agrupamiento. En este caso, el criterio se calcula de la siguiente manera:
donde s (x_j, x_k) y d (x_j, x_k) miden la similitud y la distancia de los vectores x_j y x_k.
Criterio C
El criterio C es una extensión del criterio de Condorcet y se define como (donde γ es un valor umbral):
Si consideramos las distancias NT entre pares de puntos como una serie de valores ordenados en orden ascendente, el índice C utiliza los valores NW más pequeños y los valores NW más grandes para calcular las sumas Smin y Smax: la suma S implica las distancias NW en esta secuencia que corresponden a pares presentes en un grupo (es decir, pares cuyos dos puntos están en el mismo grupo). Como máximo, las distancias 3NW se retienen efectivamente en el cálculo de este índice.
El criterio C se escribe entonces de la siguiente manera:
Calinski-Harabasz
Rendimiento basado en HSE media intra e inter-cluster (Tr):
donde B_k es la matriz de dispersión entre conglomerados y W_k es la matriz de dispersión intraconglomerado definida por:
con N el número de puntos en nuestros datos, C_q el conjunto de puntos en el grupo q, c_q el centro del grupo q, c el centro de E, n_q el número de puntos en el grupo q.
Davies-Bouldin
Este índice trata a cada grupo individualmente y busca medir qué tan similar es al grupo más cercano. El índice DB se formula de la siguiente manera:
I (c_i) representa el promedio de las distancias entre los objetos que pertenecen al grupo C_i y su centro. Y I (c_i, c_j) representa la distancia entre los centros de los dos grupos C_i y C_j.
Para cada conglomerado i de la partición, buscamos el conglomerado j que maximiza el índice descrito a continuación:
Por lo tanto, la mejor partición es la que minimiza el promedio del valor calculado para cada clúster. En otras palabras, la mejor partición es la que minimiza la similitud entre los clústeres.
Relación_detonación
El índice Det_Ratio se define así:
T denota la matriz de difusión total. Es la suma de las matrices BG y WG.
Dunn
El índice de Dunn es otra métrica de validación de clúster interna que se puede calcular de la siguiente manera:
- Para cada grupo, calcule la distancia entre cada uno de los objetos del grupo y los objetos de los otros grupos
- Utilice el mínimo de esta distancia por par como separación entre grupos (separación mínima)
- Para cada grupo, calcule la distancia entre los objetos del mismo grupo.
- Use la distancia máxima intra-cluster (es decir, el diámetro máximo) como compacidad intra-cluster
- Calcule el índice de Dunn (D) de la siguiente manera:
GDImn
El Índice Generalizado de Dunn (GDI) da un valor basado en el “buen comportamiento” de los conglomerados y sus miembros, medido en función de las distancias entre los conglomerados y dentro de los conglomerados.
Denotemos con la letra δ una medida de la distancia entre grupos y con Δ una medida de la distancia dentro de los grupos (que también se llama diámetro del grupo). El índice GDI, relativo a estas distancias, se define de la siguiente manera:
Con k y k' entre 1 y K.
Se han sugerido seis definiciones diferentes de δ (denotadas δ1 a δ6) y tres definiciones de Δ (denotadas Δ1 a Δ3). Esto conduce a 18 índices diferentes denominados Cuv: aquí u es un número entero que designa la distancia entre los grupos (1 ≤ u ≤ 6) yv un número entero que designa la distancia dentro de los grupos (1 ≤ v ≤ 3). Las definiciones de las distancias Δ dentro del grupo son:
Aquí d es la distancia euclidiana. El factor 2 en la definición de Δ3 permite interpretar el valor como un diámetro en lugar de un radio. Las definiciones de las distancias entre conglomerados δ son:
Las primeras cuatro distancias (δ1 a δ4) aparecen en los algoritmos de agrupamiento ascendente y se denominan enlace único, enlace completo, enlace promedio y enlace centroide, respectivamente. La medida δ5 es el promedio ponderado (con los pesos nk y nk′) de las distancias promedio entre los puntos de los clusters Ck y Ck′ y su respectivo baricentro. La medida δ6 es la distancia de Hausdorff DH.
Baker-Hubert Gamma
El índice Baker-Hubert Gamma es una adaptación, en el marco del clustering, del índice Γ de correlación entre dos vectores de datos A y B del mismo tamaño.
Generalmente, para dos índices i y j tales que ai < aj, decimos que los dos vectores son concordantes si bi < bj, es decir si los valores se clasifican en el mismo orden en los dos vectores. Calculamos el número s+ de pares concordantes {i, j} y el número s− de pares discordantes. Tenga en cuenta que las desigualdades son estrictas, lo que significa que se eliminan los vínculos. En este contexto, el índice Γ se define clásicamente de la siguiente manera:
El valor está entre -1 y 1.
En el contexto de una partición, el primer vector A se elige como el conjunto de distancias dij entre pares de puntos {Mi,Mj} (con i < j). El segundo vector B es un vector binario: en este vector, la coordenada correspondiente a un par {Mi,Mj} vale 0 si los dos puntos están en el mismo grupo y 1 en caso contrario. Estos dos vectores tienen una longitud NT = N(N − 1)/2.
El número s+ representa el número de veces que una distancia entre dos puntos que pertenecen al mismo grupo (es decir, una pareja para la cual el valor del vector B es 0) es estrictamente menor que la distancia entre dos puntos n que no pertenecen al mismo grupo. grupo (es decir, una pareja para la cual el valor del vector B es 1).
El número s− representa el número de veces que ocurre la situación contraria, es decir que una distancia entre dos puntos pertenecientes al mismo cluster (valor 0 en B) es estrictamente mayor que una distancia entre dos puntos que no pertenecen al mismo grupo. (valor 1 en B). No se tendrán en cuenta los casos en los que exista empate (empate o ex-aequos).
Hay distancias NB entre conglomerados y, para cada una de ellas, comparamos con las distancias intra-conglomerados NW: finalmente realizamos comparaciones NB × NW. Podemos escribir los números s+ y s− de la siguiente forma:
G+
Utilizando las mismas notaciones que para el índice Γ de Baker-Hubert, el índice G+ se define de la siguiente manera:
Es la proporción de pares discordantes entre todos los pares de puntos distintos.
Ksq_DetW
Como su nombre indica, su fórmula es K²|WG|.
Log_Det_Ratio
El índice Log_Det_Ratio se define así:
donde T es la matriz de difusión y WG. Esta es una variante logarítmica del índice Det_Ratio.
Log_SS_Ratio
El índice Log_SS_Ratio se define así:
donde BGSS y WGSS son las trazas de las matrices BG y WG respectivamente.
McClain-Rao
En cuanto al índice C, sea SW la suma de las distancias dentro del grupo:
Recuerde que el número total de distancias entre pares de puntos que pertenecen al mismo grupo es NW. Denotaremos SB la suma de las distancias entre grupos:
El número total de distancias entre pares de puntos que no pertenecen al mismo grupo es NB = N(N − 1)/2 − NW. El índice de McClain-Rao se define como el cociente entre las distancias medias dentro de un conglomerado y entre conglomerados:
PBM
El índice PBM (acrónimo formado por las iniciales de los nombres de sus autores, Pakhira, Bandyopadhyay y Maulik) se calcula a partir de las distancias entre los puntos y sus baricentros y de las distancias entre los propios baricentros.
Denotemos por DB la mayor distancia entre dos baricentros del cúmulo:
Por otro lado, denotamos EW la suma de las distancias de los puntos de cada grupo a su baricentro y ET la suma de las distancias de todos los puntos al baricentro G de todos los datos:
El índice PBM se define así:
ET es una constante que no depende de la partición ni del número de clústeres.
Punto-Biserial
En términos generales, en estadística, el coeficiente biserial puntual es una medida de correlación entre una variable continua A y una variable binaria B (es decir, una variable cuyos valores son 0 o 1). A y B son conjuntos de la misma longitud n.
Los valores de A se dividen en dos grupos A0 y A1 dependiendo de si el valor correspondiente en B es 0 o 1. Sean MA0 y MA1 los promedios en A0 y A1, y nA0 y nA1 el número de elementos de cada grupo. . El coeficiente de correlación punto-biserial se define como la cantidad:
donde sn es la desviación estándar de A.
En el contexto de una comparación entre diferentes agrupaciones, el término sn se puede omitir porque no depende de las particiones sino sólo del conjunto de datos completo.
Como en el caso del índice Γ, adaptamos esta definición eligiendo A como el conjunto de NT distancias entre pares de puntos Mi y Mj. El valor correspondiente en B es 1 si los dos puntos están en el mismo grupo y 0 en caso contrario:
MA1 es el promedio de todas las distancias dentro del grupo y MA0 es el promedio de todas las distancias entre grupos. Por tanto, la definición del índice biserial puntual es:
Lanza Ratkowsky
Calculamos el promedio ¯R de los cocientes entre BGSS y TSS para cada dimensión de los datos, es decir para cada columna de la matriz A. Nota:
BGSSj es de hecho el j-ésimo término diagonal de la matriz BG. El índice Ratkowsky-Lance (¯c/√K) se define de la siguiente manera:
Ray Turi
El índice de Ray-Turi se define como un cociente:
– el numerador es la media de los cuadrados de las distancias de todos los puntos con respecto al baricentro del cúmulo al que pertenecen:
– el denominador es el mínimo de los cuadrados de las distancias Δkk′ entre todos los baricentros del cluster:
Por tanto, el índice de Ray-Turi se puede escribir de la siguiente manera:
Scott Simons
Este índice es la suma ponderada de los logaritmos de los determinantes de la matriz de varianza-covarianza de cada conglomerado. Esto se puede escribir de la siguiente manera:
Los determinantes de las matrices WG{k} son mayores o iguales a 0 porque estas matrices son semidefinidas positivas. Si alguno de ellos es 0, el índice no está definido.
SD_Scat y SD_Dis
Definimos dos cantidades S y D llamadas respectivamente difusión media de conglomerados y separación total entre conglomerados.
La difusión promedio de los grupos, denominada S, se define de la siguiente manera. Considere el vector de varianzas para cada variable en el conjunto de datos. Es un vector V de tamaño p definido por:
De manera similar, definimos vectores de varianza V{k} para cada grupo Ck:
La cantidad S es la media de las normas de los vectores V{k} dividida por la norma del vector V:
Por otro lado, la separación total entre conglomerados, denotada como D, se define de la siguiente manera. Denotaremos Dmax y Dmin respectivamente como la distancia más grande y más pequeña entre los baricentros de los grupos:
El índice SD finalmente se define así:
donde α es un peso igual al valor de D obtenido para la partición con mayor número de clusters. Para comparar varias particiones de los datos, primero es necesario calcular el valor de D correspondiente al mayor número de conglomerados para encontrar el valor del coeficiente α y luego calcular los demás índices a partir de este coeficiente.
S_Dbw
Este índice se basa en la noción de densidad de puntos pertenecientes a dos conglomerados. Primero definimos un valor límite σ igual a la raíz cuadrada de la suma de las normas de los vectores de varianza V{k} dividida por el número de clusters:
La densidad γkk′ para un punto dado, en relación con dos grupos Ck y Ck′, es igual al número de puntos en estos dos grupos cuya distancia desde este punto es menor que σ. Geométricamente, esto equivale a considerar la bola de radio σ centrada en un punto dado y contar el número de puntos de Ck ∪ Ck′ ubicados en esta bola.
Para cada par de conglomerados, evalúemos las densidades de los baricentros G{k} y G{k′} de los conglomerados y de su punto medio Hkk′. Formamos el cociente Rkk' entre la densidad en el medio y la mayor densidad en los dos baricentros:
Por otro lado, definimos una densidad entre conglomerados G como el promedio de los cocientes Rkk′:
El índice S-Dbw se define como la suma de la dispersión promedio en los conglomerados S y la densidad entre conglomerados G:
Silueta
Valida el rendimiento basado en distancias intra e inter-clúster:
con a (i) la disimilitud promedio con los otros datos del conglomerado yb (i) la disimilitud más débil con cualquier conglomerado no miembro para cada x_i y centro del conglomerado y:
El coeficiente de silueta varía entre -1 (peor clasificación) y 1 (mejor clasificación). A menudo se calcula el promedio general de Silhouette.
Tau
Utilizando las mismas notaciones que para el índice Gamma, el índice τ de Kendall entre dos vectores de datos de longitud NT se define clásicamente en estadística como la cantidad:
Los números s+ y s− no cuentan los enlaces, por lo que si una distancia entre grupos y una distancia dentro de un grupo son iguales, no ingresan en el numerador. Para tener en cuenta las igualdades modificamos el denominador y definimos el índice corregido τc así:
con
donde ti es el número de valores en el i-ésimo grupo de enlaces para el vector A y uj es el número de valores en el j-ésimo grupo de enlaces para el vector B. Aquí el vector B consta solo de valores 0 y 1 (correspondientes respectivamente a los pares inter-cluster e intra-cluster) y así tenemos:
Un cálculo simple muestra que ν0 − ν2 = NBNW. Si asumimos razonablemente que el vector A contiene pocos valores idénticos, podemos estimar que ν2 es insignificante en comparación con ν0. Esto justifica la siguiente definición del índice de agrupamiento Tau:
traza_W
El índice Trace_W se define así:
traza_WiB
El índice Trace_WiB se define así:
Wemmert-Gançarski
El índice de Wemmert-Gançarski se construye a partir de los cocientes de distancias entre los puntos y los baricentros de todos los conglomerados.
Para un punto M perteneciente al grupo Ck, formamos el cociente R(M) entre la distancia de este punto al baricentro del grupo al que pertenece y la distancia más pequeña desde este punto a los baricentros de todos los demás grupos:
Luego promediamos estos cocientes en cada grupo. Si este promedio es mayor que 1 lo ignoramos, en caso contrario tomamos su complemento a 1. Específicamente definamos:
El índice de Wemmert-Gançarski se define como el promedio ponderado, para todos los grupos, de las cantidades Jk así:
Que se puede reescribir como:
Xie-Beni
El índice Xie-Beni es un índice de agrupación difusa, pero también se aplica a la agrupación aguda.
Se define como el cociente entre el error cuadrático medio y el mínimo de las distancias cuadráticas mínimas entre los puntos de los conglomerados. El error cuadrático medio, en el caso del clustering neto, es simplemente la cantidad 1/N*WGSS, es decir, el promedio de los cuadrados de las distancias de todos los puntos con respecto al baricentro del cluster al que pertenecen.
y el índice Xie-Beni se puede escribir de la siguiente manera:
ES 
FR 
EN