Silueta (agrupamiento)

Medida de calidad en el análisis de conglomerados

Silhouette es un método de interpretación y validación de la consistencia dentro de grupos de datos . La técnica proporciona una representación gráfica sucinta de cuán bien se ha clasificado cada objeto. ^[1] Fue propuesta por el estadístico belga Peter Rousseeuw en 1987.

El valor de silueta es una medida de cuán similar es un objeto a su propio grupo (cohesión) en comparación con otros grupos (separación). La silueta varía de −1 a +1, donde un valor alto indica que el objeto está bien emparejado con su propio grupo y mal emparejado con los grupos vecinos. Si la mayoría de los objetos tienen un valor alto, entonces la configuración de agrupamiento es apropiada. Si muchos puntos tienen un valor bajo o negativo, entonces la configuración de agrupamiento puede tener demasiados o muy pocos grupos. Un agrupamiento con un ancho de silueta promedio de más de 0,7 se considera "fuerte", un valor superior a 0,5 "razonable" y superior a 0,25 "débil", pero con el aumento de la dimensionalidad de los datos, se vuelve difícil lograr valores tan altos debido a la maldición de la dimensionalidad , ya que las distancias se vuelven más similares. La puntuación de silueta está especializada para medir la calidad del grupo cuando los grupos tienen forma convexa y puede no funcionar bien si los grupos de datos tienen formas irregulares o son de tamaños variables. ^[2] La silueta se puede calcular con cualquier métrica de distancia , como la distancia euclidiana o la distancia de Manhattan .

Definición

Gráfico que muestra las puntuaciones de silueta de tres tipos de animales del conjunto de datos Zoo, tal como las representó la suite de minería de datos Orange . En la parte inferior del gráfico, la silueta identifica al delfín y la marsopa como valores atípicos en el grupo de mamíferos.

Supongamos que los datos se han agrupado mediante alguna técnica, como k-medoides o k-medias , en grupos. ${\displaystyle k}$

Para el punto de datos (punto de datos en el clúster ), sea ${\displaystyle i\in C_{I}}$ ${\displaystyle i}$ ${\displaystyle C_{I}}$

${\displaystyle a(i)={\frac {1}{|C_{I}|-1}}\sum _{j\in C_{I},i\neq j}d(i,j)}$

sea ​​la distancia media entre y todos los demás puntos de datos en el mismo grupo, donde es el número de puntos que pertenecen al grupo , y es la distancia entre los puntos de datos y en el grupo (dividimos por porque no incluimos la distancia en la suma). Podemos interpretar como una medida de qué tan bien está asignado a su grupo (cuanto menor sea el valor, mejor será la asignación). ${\displaystyle i}$ ${\displaystyle |C_{I}|}$ ${\displaystyle C_{I}}$ ${\displaystyle d(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle C_{I}}$ ${\displaystyle |C_{I}|-1}$ ${\displaystyle d(i,i)}$ ${\displaystyle a(i)}$ ${\displaystyle i}$

Luego definimos la disimilitud media de un punto con respecto a algún grupo como la media de la distancia desde todos los puntos en (donde ). ${\displaystyle i}$ ${\displaystyle C_{J}}$ ${\displaystyle i}$ ${\displaystyle C_{J}}$ ${\displaystyle C_{J}\neq C_{I}}$

Para cada punto de datos , definimos ahora ${\displaystyle i\in C_{I}}$

${\displaystyle b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\sum _{j\in C_{J}}d(i,j)}$

ser la distancia media más pequeña (de ahí el operador en la fórmula) de a todos los puntos de cualquier otro grupo (es decir, en cualquier grupo del cual no sea miembro). El grupo con esta menor disimilitud media se dice que es el "grupo vecino" de porque es el siguiente grupo que mejor se ajusta al punto . ${\displaystyle \min }$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

Ahora definimos una silueta (valor) de un punto de datos ${\displaystyle i}$

${\displaystyle s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}}$, si ${\displaystyle |C_{I}|>1}$

y

${\displaystyle s(i)=0}$, si ${\displaystyle |C_{I}|=1}$

Lo cual también se puede escribir como:

${\displaystyle s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{if }}a(i)<b(i)\\0,&{\mbox{if }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{if }}a(i)>b(i)\\\end{cases}}}$

De la definición anterior se desprende claramente que

${\displaystyle -1\leq s(i)\leq 1}$

Tenga en cuenta que no está claramente definido para los clústeres con tamaño = 1, en cuyo caso establecemos . Esta elección es arbitraria, pero neutral en el sentido de que se encuentra en el punto medio de los límites, -1 y 1. ^[1] ${\displaystyle a(i)}$ ${\displaystyle s(i)=0}$

Para que esté cerca de 1, necesitamos . Como es una medida de cuán diferente es de su propio grupo, un valor pequeño significa que está bien emparejado. Además, un valor grande implica que está mal emparejado con su grupo vecino. Por lo tanto, un valor cercano a 1 significa que los datos están agrupados apropiadamente. Si está cerca de -1, entonces por la misma lógica vemos que sería más apropiado si estuviera agrupado en su grupo vecino. Un valor cercano a cero significa que el dato está en el límite de dos grupos naturales. ${\displaystyle s(i)}$ ${\displaystyle a(i)\ll b(i)}$ ${\displaystyle a(i)}$ ${\displaystyle i}$ ${\displaystyle b(i)}$ ${\displaystyle i}$ ${\displaystyle s(i)}$ ${\displaystyle s(i)}$ ${\displaystyle i}$ ${\displaystyle s(i)}$

La media de todos los puntos de un grupo es una medida de cuán estrechamente agrupados están todos los puntos del grupo. Por lo tanto, la media de todos los datos de todo el conjunto de datos es una medida de cuán apropiadamente se han agrupado los datos. Si hay demasiados o muy pocos grupos, como puede ocurrir cuando se utiliza una mala elección de en el algoritmo de agrupamiento (por ejemplo, k-means ), algunos de los grupos mostrarán típicamente siluetas mucho más estrechas que el resto. Por lo tanto, los gráficos de silueta y las medias se pueden utilizar para determinar el número natural de grupos dentro de un conjunto de datos. También se puede aumentar la probabilidad de que la silueta se maximice en el número correcto de grupos reescalando los datos utilizando ponderaciones de características que sean específicas del grupo. ^[3] ${\displaystyle s(i)}$ ${\displaystyle s(i)}$ ${\displaystyle k}$

Kaufman et al. introdujeron el término coeficiente de silueta para el valor máximo de la media de todos los datos del conjunto de datos completo, ^[4] es decir, ${\displaystyle s(i)}$

${\displaystyle SC=\max _{k}{\tilde {s}}\left(k\right),}$

donde representa la media de todos los datos del conjunto de datos completo para un número específico de clústeres . ${\displaystyle {\tilde {s}}\left(k\right)}$ ${\displaystyle s(i)}$ ${\displaystyle k}$

Silueta simplificada y silueta medoide

Para calcular el coeficiente de silueta se necesitan todas las distancias por pares, lo que hace que esta evaluación sea mucho más costosa que la agrupación con k-medias. Para una agrupación con centros para cada grupo , podemos utilizar la siguiente silueta simplificada para cada punto , que se puede calcular utilizando solo distancias: ${\displaystyle {\mathcal {O}}(N^{2})}$ ${\displaystyle \mu _{C_{I}}}$ ${\displaystyle C_{I}}$ ${\displaystyle i\in C_{I}}$ ${\displaystyle {\mathcal {O}}(Nk)}$

${\displaystyle a'(i)=d(i,\mu _{C_{I}})}$y , ${\displaystyle b'(i)=\min _{C_{J}\neq C_{I}}d(i,\mu _{C_{J}})}$

que tiene el beneficio adicional de que siempre está definido, entonces defina en consecuencia la silueta simplificada y el coeficiente de silueta simplificado ^[5] ${\displaystyle a'(i)}$

${\displaystyle s'(i)={\frac {b'(i)-a'(i)}{\max\{a'(i),b'(i)\}}}}$

${\displaystyle SC'=\max _{k}{\frac {1}{N}}\sum _{i}s'\left(i\right)}$.

Si los centros de los grupos son medoides (como en el agrupamiento de k-medoides) en lugar de medias aritméticas (como en el agrupamiento de k-medias), esto también se denomina silueta basada en medoides ^[6] o silueta medoide. ^[7]

Si cada objeto se asigna al medoide más cercano (como en la agrupación de k-medoides), sabemos que , y por lo tanto . ^[7] ${\displaystyle a'(i)\leq b'(i)}$ ${\displaystyle s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}}$

Agrupamiento de siluetas

En lugar de utilizar la silueta promedio para evaluar un agrupamiento obtenido a partir de, por ejemplo, k-medoides o k-medias, podemos intentar encontrar directamente una solución que maximice la silueta. No tenemos una solución de forma cerrada para maximizar esto, pero normalmente será mejor asignar puntos al grupo más cercano como se hace con estos métodos. Van der Laan et al. ^[6] propusieron adaptar el algoritmo estándar para k-medoides, PAM, para este propósito y llamar a este algoritmo PAMSIL:

1. Elija medoides iniciales mediante PAM
2. Calcular la silueta promedio de esta solución inicial
3. Para cada par de un medoide m y un no medoide x
   1. Intercambiar m y x
   2. Calcular la silueta media de la solución resultante
   3. Recuerda el mejor intercambio
   4. Deshacer el intercambio de m y x para la siguiente iteración
4. Realice el mejor cambio y regrese a 3, de lo contrario, deténgase si no encuentra ninguna mejora.

El bucle del paso 3 se ejecuta para pares e implica calcular la silueta en , por lo tanto, este algoritmo necesita tiempo, donde i es el número de iteraciones. ${\displaystyle {\mathcal {O}}(Nk)}$ ${\displaystyle {\mathcal {O}}(N^{2})}$ ${\displaystyle {\mathcal {O}}(N^{3}ki)}$

Como se trata de una operación bastante costosa, los autores proponen utilizar también la silueta basada en medoides y llamar al algoritmo resultante PAMMEDSIL. ^[6] Requiere tiempo. ${\displaystyle {\mathcal {O}}(N^{2}k^{2}i)}$

Batool et al. proponen un algoritmo similar bajo el nombre de OSil, y proponen una estrategia de muestreo similar a CLARA para conjuntos de datos más grandes, que resuelve el problema solo para una submuestra. ^[8]

Al adoptar mejoras recientes al algoritmo PAM, FastMSC reduce el tiempo de ejecución utilizando la silueta medoide a solo . ^[7] ${\displaystyle {\mathcal {O}}(N^{2}i)}$

Al comenzar con un número máximo de clústeres k _max y eliminar iterativamente el peor centro (en términos de un cambio en la silueta) y volver a optimizar, se puede determinar automáticamente el mejor clúster (la silueta medoide más alta). Como las estructuras de datos se pueden reutilizar, esto reduce sustancialmente el costo de cálculo en comparación con la ejecución repetida del algoritmo para diferentes cantidades de clústeres. ^[9] Este algoritmo necesita distancias por pares y generalmente se implementa con una matriz de distancia por pares. El requisito de memoria es el principal factor limitante para aplicar esto a conjuntos de datos muy grandes. ${\displaystyle {\mathcal {O}}(N^{2})}$

Véase también

• Análisis de conglomerados
• Índice de Davies-Bouldin
• Índice de Calinski-Harabasz
• Índice de Dunn
• Determinar el número de clústeres en un conjunto de datos

Referencias

1. Peter J. Rousseeuw (1987). "Siluetas: una ayuda gráfica para la interpretación y validación del análisis de conglomerados". Matemáticas computacionales y aplicadas . 20 : 53–65. doi : 10.1016/0377-0427(87)90125-7 .
2. Monshizadeh, Mehrnoosh; Khatri, Vikramajeet; Kantola, Raimo; Yan, Zheng (1 de noviembre de 2022). "Un enfoque de agrupamiento basado en densidad profunda y autodeterminante para etiquetar tráfico desconocido". Journal of Network and Computer Applications . 207 : 103513. doi : 10.1016/j.jnca.2022.103513 . ISSN  1084-8045. Sin embargo, ambas medidas [coeficiente de silueta y correlación de bordes] prefieren clústeres con forma convexa y no pueden adaptarse a todas las formas de clúster producidas por DBSCAN.
3. RC de Amorim, C. Hennig (2015). "Recuperación del número de clústeres en conjuntos de datos con características de ruido utilizando factores de reescalado de características". Ciencias de la información . 324 : 126–145. arXiv : 1602.06989 . doi :10.1016/j.ins.2015.06.039. S2CID  315803.
4. Leonard Kaufman; Peter J. Rousseeuw (1990). Encontrar grupos en los datos: una introducción al análisis de conglomerados. Hoboken, NJ: Wiley-Interscience. p. 87. doi :10.1002/9780470316801. ISBN 9780471878766.
5. Hruschka, ER; de Castro, LN; Campello, RJGB (2004). Algoritmos evolutivos para agrupar datos de expresión génica. Cuarta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'04). IEEE. págs. 403–406. doi :10.1109/ICDM.2004.10073.
6. Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003). "Un nuevo algoritmo de partición en torno a medoides". Revista de computación estadística y simulación . 73 (8): 575–584. doi :10.1080/0094965031000136012. ISSN  0094-9655. S2CID  17437463.
7. Lenssen, Lars; Schubert, Erich (2022). Agrupamiento mediante optimización directa de la silueta medoide. Conferencia internacional sobre búsqueda de similitud y aplicaciones. págs. 190–204. arXiv : 2209.12553 . doi :10.1007/978-3-031-17849-8_15 . Consultado el 20 de octubre de 2022 .
8. Batool, Fatima; Hennig, Christian (2021). "Agrupamiento con el ancho de silueta promedio". Estadística computacional y análisis de datos . 158 : 107190. arXiv : 1910.11339 . doi :10.1016/j.csda.2021.107190. S2CID  219260336.
9. Lenssen, Lars; Schubert, Erich (1 de febrero de 2024). "Agrupamiento de siluetas medoides con selección automática de número de clúster". Sistemas de información . 120 : 102290. arXiv : 2309.03751 . doi :10.1016/j.is.2023.102290. ISSN  0306-4379.