Silueta (agrupación)

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

El valor de la silueta es una medida de qué tan 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 coincide bien con su propio grupo y no coincide con los grupos vecinos. Si la mayoría de los objetos tienen un valor alto, entonces la configuración de agrupación en clústeres es adecuada. Si muchos puntos tienen un valor bajo o negativo, entonces la configuración de agrupación puede tener demasiados o muy pocos clústeres. Un agrupamiento con un ancho de silueta promedio superior a 0,7 se considera "fuerte", un valor superior a 0,5 "razonable" y superior a 0,25 "débil", pero a medida que aumenta la dimensionalidad de los datos, resulta difícil lograr valores tan altos debido a la maldición de la dimensionalidad , a medida que las distancias se vuelven más similares. La puntuación de silueta está especializada para medir la calidad de los conglomerados cuando los conglomerados tienen forma convexa y puede no funcionar bien si los conglomerados de datos tienen formas irregulares o son de diferentes tamaños. ^[2] La silueta se puede calcular con cualquier métrica de distancia , como la distancia euclidiana o la distancia de Manhattan .

Definición

Un gráfico que muestra puntuaciones de silueta de tres tipos de animales del conjunto de datos del zoológico representados por la suite de minería de datos Orange . En la parte inferior del gráfico, la silueta identifica a los delfines y las marsopas como valores atípicos en el grupo de mamíferos.

Supongamos que los datos se han agrupado mediante cualquier técnica, como k-medoides o k-medias , en $k$ grupos.

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

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

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

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

Para cada punto de datos , ahora definimos ${\ Displaystyle i \ en C_ {I}}$

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 $i$ a todos los puntos en cualquier otro grupo (es decir, en cualquier grupo del cual $i$ no sea miembro). Se dice que el grupo con esta disimilitud media más pequeña es el "grupo vecino" de $i$ porque es el siguiente grupo que mejor se ajusta al punto $i$ . ${\displaystyle\min }$

Ahora definimos una silueta (valor) de un punto de datos $i$

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

, si

|C_{I}|>1

s(i)=0

, si

|C_{I}|=1

Que también se puede escribir como:

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

De la definición anterior queda claro que

-1\leq s(i)\leq 1

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

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

La media $s(i)$ sobre todos los puntos de un grupo es una medida de qué tan estrechamente agrupados están todos los puntos del grupo. Por lo tanto, la media $s(i)$ de todos los datos del conjunto de datos es una medida de cuán apropiadamente se han agrupado los datos. Si hay demasiados o muy pocos conglomerados, como puede ocurrir cuando se utiliza una mala elección de $k en el algoritmo de agrupamiento (por ejemplo,$ k-means ), algunos de los conglomerados normalmente mostrarán siluetas mucho más estrechas que el resto. Por lo tanto, se pueden utilizar gráficos de silueta y medias 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 pesos de características que sean específicos del grupo. ^[3]

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

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

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

Silueta simplificada y silueta medoide

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

a'(i)=d(i,\mu _ {C_{I}})

y ,

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

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

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

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

Si los centros del grupo son medoides (como en la agrupación de k-medoides) en lugar de medias aritméticas (como en la agrupación 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 tanto . ^[7] $a'(i)\leq b'(i)$ $s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'( i)}}$

Agrupación de siluetas

En lugar de utilizar la silueta promedio para evaluar un agrupamiento obtenido, por ejemplo, de 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 generalmente 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:

Elija medioides iniciales usando PAM
Calcule la silueta promedio de esta solución inicial.
Para cada par de un medoide m y un no medoide x
1. intercambiar $m$ y $x$
2. calcular la silueta promedio de la solución resultante
3. recuerda el mejor intercambio
4. anular el intercambio $m$ y $x$ para la siguiente iteración
Realice el mejor intercambio y regrese a 3; de lo contrario, deténgase si no se encuentra ninguna mejora.

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

Debido a que se trata de una operación bastante costosa, los autores proponen utilizar también la silueta basada en medoide y llamar al algoritmo resultante PAMMEDSIL. ^[6] Necesita tiempo $O(N 2 k 2 i)$ .

Batool et al. proponer un algoritmo similar bajo el nombre OSil y proponer 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 en el algoritmo PAM, FastMSC reduce el tiempo de ejecución utilizando la silueta medoide a solo $O(N 2 i)$ . ^[7]

Al comenzar con un número máximo de grupos $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 agrupamiento (silueta medoide más alta). Como las estructuras de datos se pueden reutilizar, esto reduce sustancialmente el costo de cálculo al ejecutar repetidamente el algoritmo para diferentes números de clústeres. ^[9] Este algoritmo necesita distancias por pares y normalmente se implementa con una matriz de distancias por pares. El requisito de memoria $O(N 2)$ es el principal factor limitante para aplicar esto a conjuntos de datos muy grandes.

Ver también

Referencias

^ ab Peter J. Rousseeuw (1987). "Siluetas: una ayuda gráfica para la interpretación y validación del análisis de conglomerados". Matemática Computacional y Aplicada . 20 : 53–65. doi : 10.1016/0377-0427(87)90125-7 .
^ Monshizadeh, Mehrnoosh; Khatri, Vikramajeet; Kantola, Raimo; Yan, Zheng (1 de noviembre de 2022). "Un enfoque de agrupación en clústeres autodeterminante y basado en una densidad profunda para etiquetar el tráfico desconocido". Revista de aplicaciones informáticas y de redes . 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 grupos de forma convexa y no pueden adaptarse a todas las formas de grupo producidas por DBSCAN.
^ RC de Amorim, C. Hennig (2015). "Recuperar la cantidad de grupos 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.
^ Leonard Kaufman; Peter J. Rousseeuw (1990). Encontrar grupos en datos: una introducción al análisis de conglomerados. Hoboken, Nueva Jersey: Wiley-Interscience. pag. 87. doi : 10.1002/9780470316801. ISBN 9780471878766.
^ Hruschka, ER; de Castro, LN; Campello, RJGB (2004). Algoritmos evolutivos para agrupar datos de expresión genética. Cuarta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'04). IEEE. págs. 403–406. doi :10.1109/ICDM.2004.10073.
^ a b C Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003). "Una nueva partición en torno al algoritmo de medoides". Revista de simulación y computación estadística . 73 (8): 575–584. doi :10.1080/0094965031000136012. ISSN 0094-9655. S2CID 17437463.
^ abc Lenssen, Lars; Schubert, Erich (2022). Agrupación por optimización directa de la silueta medoide. Conferencia internacional sobre búsqueda y aplicaciones de similitudes. págs. 190-204. arXiv : 2209.12553 . doi : 10.1007/978-3-031-17849-8_15 . Consultado el 20 de octubre de 2022 .
^ Batool, Fátima; Hennig, Christian (2021). "Agrupación con el ancho medio de la silueta". Estadística computacional y análisis de datos . 158 : 107190. arXiv : 1910.11339 . doi : 10.1016/j.csda.2021.107190. S2CID 219260336.
^ Lenssen, Lars; Schubert, Erich (1 de febrero de 2024). "Agrupación de Medoid Silhouette con selección automática de número de grupo". Sistemas de información . 120 : 102290. arXiv : 2309.03751 . doi :10.1016/j.is.2023.102290. ISSN 0306-4379.