La agrupación por consenso es un método para agregar resultados (potencialmente conflictivos) de múltiples algoritmos de agrupación. También llamado conjuntos de conglomerados [1] o agregación de agrupaciones (o particiones), se refiere a la situación en la que se han obtenido varias agrupaciones (de entrada) diferentes para un conjunto de datos en particular y se desea encontrar una agrupación única (de consenso) que se ajusta mejor en cierto sentido que las agrupaciones existentes. [2] La agrupación por consenso es, por tanto, el problema de conciliar la información agrupada sobre el mismo conjunto de datos procedente de diferentes fuentes o de diferentes ejecuciones del mismo algoritmo. Cuando se presenta como un problema de optimización, la agrupación de consenso se conoce como partición mediana y se ha demostrado que es NP-completa, [3] incluso cuando el número de agrupaciones de entrada es tres. [4] El agrupamiento por consenso para el aprendizaje no supervisado es análogo al aprendizaje por conjuntos en el aprendizaje supervisado.
Problemas con las técnicas de agrupación en clústeres existentes
- Las técnicas actuales de agrupación en clústeres no abordan todos los requisitos de manera adecuada.
- Tratar con un gran número de dimensiones y un gran número de elementos de datos puede resultar problemático debido a la complejidad del tiempo;
- La eficacia del método depende de la definición de "distancia" (para la agrupación basada en la distancia)
- Si no existe una medida de distancia obvia, debemos "definirla", lo que no siempre es fácil, especialmente en espacios multidimensionales.
- El resultado del algoritmo de agrupamiento (que, en muchos casos, puede ser arbitrario en sí mismo) se puede interpretar de diferentes formas.
Justificación para utilizar la agrupación por consenso
Existen posibles deficiencias en todas las técnicas de agrupación existentes. Esto puede dificultar la interpretación de los resultados, especialmente cuando no se tiene conocimiento sobre el número de agrupaciones. Los métodos de agrupación también son muy sensibles a la configuración de agrupación inicial, lo que puede hacer que los datos no significativos se amplifiquen en métodos no reiterativos. Un tema extremadamente importante en el análisis de conglomerados es la validación de los resultados del conglomerado, es decir, cómo ganar confianza sobre la importancia de los conglomerados que proporciona la técnica de conglomerado (números de conglomerados y asignaciones de conglomerados). Al carecer de un criterio objetivo externo (el equivalente a una etiqueta de clase conocida en el análisis supervisado), esta validación se vuelve algo esquiva. Los métodos de agrupación de clústeres de descendencia iterativa, como el SOM y la agrupación de k-medias, eluden algunas de las deficiencias de la agrupación jerárquica al proporcionar clústeres y límites de clústeres definidos unívocamente. La agrupación por consenso proporciona un método que representa el consenso en varias ejecuciones de un algoritmo de agrupación, para determinar el número de agrupaciones en los datos y para evaluar la estabilidad de las agrupaciones descubiertas. El método también se puede utilizar para representar el consenso sobre múltiples ejecuciones de un algoritmo de agrupamiento con reinicio aleatorio (como K-medias, agrupamiento bayesiano basado en modelos, SOM, etc.), a fin de tener en cuenta su sensibilidad a las condiciones iniciales . Puede proporcionar datos para que una herramienta de visualización inspeccione el número de clúster, la membresía y los límites. Sin embargo, carecen del atractivo visual e intuitivo de los dendrogramas de agrupación jerárquica, y el número de agrupaciones debe elegirse a priori.
El algoritmo de agrupación de consenso de Monti
El algoritmo de agrupación por consenso de Monti [5] es uno de los algoritmos de agrupación por consenso más populares y se utiliza para determinar el número de agrupaciones,. Dado un conjunto de datos de número total de puntos para agrupar, este algoritmo funciona remuestreando y agrupando los datos, para cada y un Se calcula la matriz de consenso, donde cada elemento representa la fracción de veces que dos muestras se agrupan. Una matriz perfectamente estable consistiría enteramente en ceros y unos, representando todos los pares de muestras siempre agrupados o no juntos en todas las iteraciones de remuestreo. La estabilidad relativa de las matrices de consenso se puede utilizar para inferir el óptimo.
Más específicamente, dado un conjunto de puntos para agrupar, , dejar ser la lista de conjuntos de datos perturbados (remuestreados) del conjunto de datos original , y deja denotar el matriz de conectividad resultante de la aplicación de un algoritmo de agrupación en clústeres al conjunto de datos . Las entradas de se definen de la siguiente manera:
Dejar ser el matriz de identificador donde el -th entrada es igual a 1 si puntos y están en el mismo conjunto de datos perturbados y 0 en caso contrario. La matriz del indicador se utiliza para realizar un seguimiento de las muestras que se seleccionaron durante cada iteración de remuestreo para el paso de normalización. La matriz de consenso se define como la suma normalizada de todas las matrices de conectividad de todos los conjuntos de datos perturbados y se calcula una diferente para cada .
Esa es la entrada en la matriz de consenso es el número de puntos de tiempo y se agruparon dividido por el número total de veces que se seleccionaron juntos. La matriz es simétrica y cada elemento se define dentro del rango. Se calcula una matriz de consenso para cada a probar, y la estabilidad de cada matriz, es decir, qué tan lejos está la matriz hacia una matriz de estabilidad perfecta (solo ceros y unos) se usa para determinar el óptimo . Una forma de cuantificar la estabilidad de laLa matriz de consenso está examinando su curva CDF (ver más abajo).
Potencial de sobreinterpretación del algoritmo de agrupación de consenso de Monti
La agrupación por consenso de Monti puede ser una herramienta poderosa para identificar agrupaciones, pero debe aplicarse con precaución, como lo demuestran Şenbabaoğlu et al. [6] Se ha demostrado que el algoritmo de agrupación de consenso de Monti es capaz de afirmar la aparente estabilidad de la partición aleatoria de conjuntos de datos nulos extraídos de una distribución unimodal y, por lo tanto, tiene el potencial de conducir a una interpretación excesiva de la estabilidad de la agrupación en un estudio real. [6] [7] Si los conglomerados no están bien separados, el agrupamiento por consenso podría llevar a uno a concluir una estructura aparente cuando no la hay, oa declarar la estabilidad del conglomerado cuando es sutil. La identificación de grupos de falsos positivos es un problema común en toda la investigación de grupos, [8] y ha sido abordado por métodos como SigClust [8] y la estadística GAP. [9] Sin embargo, estos métodos se basan en ciertos supuestos para el modelo nulo que pueden no siempre ser apropiados.
Şenbabaoğlu et al [6] demostraron la métrica delta K original para decidiren el algoritmo de Monti tuvo un desempeño deficiente y propuso una nueva métrica superior para medir la estabilidad de las matrices de consenso utilizando sus curvas CDF. En la curva CDF de una matriz de consenso, la parte inferior izquierda representa los pares de muestras que rara vez se agrupan, la parte superior derecha representa los que casi siempre están agrupados, mientras que el segmento medio representa los que tienen asignaciones ambiguas en diferentes ejecuciones de agrupación. La proporción de medida de puntuación de agrupamiento ambiguo (PAC) cuantifica este segmento medio; y se define como la fracción de pares de muestras con índices de consenso que caen en el intervalo (u 1 , u 2 ) ∈ [0, 1] donde u 1 es un valor cercano a 0 y u 2 es un valor cercano a 1 (por ejemplo u 1 = 0,1 yu 2 = 0,9). Un valor bajo de PAC indica un segmento medio plano y una tasa baja de asignaciones discordantes entre ejecuciones de agrupamiento permutadas. Por tanto, se puede inferir el número óptimo de conglomerados por elvalor que tiene el PAC más bajo. [6] [7]
Trabajo relacionado
1. Conjunto de agrupamiento (Strehl y Ghosh) : Consideraron varias formulaciones para el problema, la mayoría de las cuales reducen el problema a un problema de particiones hipergráficas. En una de sus formulaciones consideraron el mismo gráfico que en el problema de agrupamiento de correlaciones. La solución que propusieron es calcular la mejor partición k del gráfico, que no tiene en cuenta la penalización por fusionar dos nodos que están muy separados. [ cita requerida ]
2. Agrupación de agrupaciones (Fern y Brodley) : aplicaron la idea de agrupación de agrupaciones a una colección de agrupaciones blandas que obtuvieron mediante proyecciones aleatorias. Utilizaron un algoritmo de aglomeración y no penalizaron la fusión de nodos diferentes. [ cita requerida ]
3. Fred y Jain : Propusieron utilizar un algoritmo de enlace único para combinar múltiples ejecuciones del algoritmo de k- medias. [ cita requerida ]
4. Dana Cristofor y Dan Simovici : observaron la conexión entre la agregación de agrupaciones y la agrupación de datos categóricos. Propusieron medidas de distancia teóricas de la información y proponen algoritmos genéticos para encontrar la mejor solución de agregación. [ cita requerida ]
5. Topchy et al. : Definieron la agregación de agrupamiento como un problema de estimación de máxima verosimilitud y propusieron un algoritmo EM para encontrar el agrupamiento de consenso. [ cita requerida ]
Agrupación de conjuntos duros
Este enfoque de Strehl y Ghosh introduce el problema de combinar múltiples particiones de un conjunto de objetos en un solo clúster consolidado sin acceder a las características o algoritmos que determinaron estas particiones. Discuten tres enfoques para resolver este problema para obtener funciones de consenso de alta calidad. Sus técnicas tienen bajos costos computacionales y esto hace que sea factible evaluar cada una de las técnicas discutidas a continuación y llegar a la mejor solución comparando los resultados con la función objetivo.
Funciones de consenso eficientes
1. Algoritmo de partición por similitud basado en clústeres (CSPA)
En CSPA, la similitud entre dos puntos de datos se define como directamente proporcional al número de agrupaciones constituyentes del conjunto en el que se agrupan. La intuición es que cuanto más similares sean dos puntos de datos, mayor será la probabilidad de que los agrupamientos constituyentes los coloquen en el mismo grupo. CSPA es la heurística más simple, pero su complejidad computacional y de almacenamiento son cuadráticas en n . SC3 es un ejemplo de un algoritmo de tipo CSPA. [10] Los dos métodos siguientes son computacionalmente menos costosos:
2. Algoritmo de partición de hipergráficos (HGPA)
El algoritmo HGPA adopta un enfoque muy diferente para encontrar la agrupación de consenso que el método anterior. El problema del conjunto de conglomerados se formula dividiendo el hipergráfico cortando un número mínimo de hipergrafias. Hacen uso de hMETIS, que es un sistema de paquetes de particiones hipergráficas .
3. Algoritmo de metaagrupación (MCLA)
El algoritmo meta-clustering (MCLA) se basa en clústeres de clústeres. Primero, intenta resolver el problema de la correspondencia de los conglomerados y luego usa la votación para colocar los puntos de datos en los conglomerados de consenso finales. El problema de la correspondencia de conglomerados se resuelve agrupando los conglomerados identificados en los conglomerados individuales del conjunto. La agrupación se realiza mediante METIS y agrupación espectral.
Conjuntos de agrupación suave
Punera y Ghosh extendieron la idea de conjuntos de agrupamiento duro al escenario de agrupamiento suave. Cada instancia en un conjunto suave está representada por una concatenación de r distribuciones de probabilidad de pertenencia posterior obtenidas de los algoritmos de agrupamiento constituyentes. Podemos definir una medida de distancia entre dos instancias usando la divergencia de Kullback-Leibler (KL) , que calcula la "distancia" entre dos distribuciones de probabilidad.
1. SCSPA
sCSPA amplía CSPA calculando una matriz de similitud. Cada objeto se visualiza como un punto en el espacio dimensional, y cada dimensión corresponde a la probabilidad de pertenecer a un grupo. Esta técnica primero transforma los objetos en un espacio de etiquetas y luego interpreta el producto escalar entre los vectores que representan los objetos como su similitud.
2. sMCLA
sMCLA extiende MCLA aceptando agrupaciones suaves como entrada. El trabajo de sMCLA se puede dividir en los siguientes pasos:
- Construir metagráficos blandos de clústeres
- Agrupar los clústeres en meta-clústeres
- Contraer metaclústeres mediante ponderación
- Compite por los objetos
3. sHBGF
HBGF representa el conjunto como un gráfico bipartito con clústeres e instancias como nodos, y bordes entre las instancias y los clústeres a los que pertenecen. [11] Este enfoque se puede adaptar trivialmente para considerar conjuntos blandos, ya que el algoritmo de partición de gráficos METIS acepta pesos en los bordes del gráfico que se va a dividir. En sHBGF, el gráfico tiene n + t vértices, donde t es el número total de conglomerados subyacentes.
4. Agrupación de consenso bayesiano (BCC)
BCC define un modelo totalmente bayesiano para la agrupación de consenso suave en el que se supone que las agrupaciones de múltiples fuentes, definidas por diferentes datos de entrada o diferentes modelos de probabilidad, se adhieren libremente a una agrupación de consenso. [12] El posterior completo para los agrupamientos separados y el agrupamiento de consenso se infieren simultáneamente a través del muestreo de Gibbs.
Fuentes
- ↑ Strehl, Alexander; Ghosh, Joydeep (2002). "Conjuntos de clústeres: un marco de reutilización de conocimientos para combinar varias particiones" (PDF) . Revista de investigación en aprendizaje automático (JMLR) . 3 : 583–617.
- ^ VEGA-PONS, SANDRO; RUIZ-SHULCLOPER, JOSÉ (1 de mayo de 2011). "Una encuesta de algoritmos de conjuntos de agrupación". Revista Internacional de Reconocimiento de Patrones e Inteligencia Artificial . 25 (3): 337–372. doi : 10.1142 / S0218001411008683 . S2CID 4643842 .
- ^ Filkov, Vladimir (2003). "Integración de datos de microarrays por agrupación de consenso". Actas. 15ª Conferencia Internacional IEEE sobre Herramientas con Inteligencia Artificial . In Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence . págs. 418–426. CiteSeerX 10.1.1.116.8271 . doi : 10.1109 / TAI.2003.1250220 . ISBN 978-0-7695-2038-4. S2CID 1515525 .
- ^ Bonizzoni, Paola; Della Vedova, Gianluca; Dondi, Riccardo; Jiang, Tao (2008). "Sobre la aproximación de la agrupación de correlación y la agrupación de consenso". Revista de Ciencias de la Computación y Sistemas . 74 (5): 671–696. doi : 10.1016 / j.jcss.2007.06.024 .
- ^ Monti, Stefano; Tamayo, Pablo; Mesirov, Jill; Golub, Todd (1 de julio de 2003). "Agrupación de consenso: un método basado en el remuestreo para el descubrimiento de clases y la visualización de datos de microarrays de expresión génica" . Aprendizaje automático . 52 (1): 91-118. doi : 10.1023 / A: 1023949509487 . ISSN 1573-0565 .
- ^ a b c d Şenbabaoğlu, Y .; Michailidis, G .; Li, JZ (2014). "Limitaciones críticas de la agrupación de consenso en el descubrimiento de clases" . Informes científicos . 4 : 6207. Código Bibliográfico : 2014NatSR ... 4E6207. . doi : 10.1038 / srep06207 . PMC 4145288 . PMID 25158761 .
- ^ a b Şenbabaoğlu, Y .; Michailidis, G .; Li, JZ (febrero de 2014). "Una reevaluación de la agrupación de consenso para el descubrimiento de clases". bioRxiv 10.1101 / 002642 .
- ^ a b Liu, Yufeng; Hayes, David Neil; Nobel, Andrew; Marron, JS (1 de septiembre de 2008). "Importancia estadística de la agrupación para datos de alta dimensión, tamaño de muestra bajo". Revista de la Asociación Estadounidense de Estadística . 103 (483): 1281-1293. doi : 10.1198 / 016214508000000454 . ISSN 0162-1459 . S2CID 120819441 .
- ^ Tibshirani, Robert; Walther, Guenther; Hastie, Trevor (2001). "Estimación del número de conglomerados en un conjunto de datos a través de la estadística de brecha". Revista de la Royal Statistical Society, Serie B (Metodología estadística) . 63 (2): 411–423. doi : 10.1111 / 1467-9868.00293 . ISSN 1467-9868 .
- ^ Kiselev, Vladimir Yu; Kirschner, Kristina; Schaub, Michael T; Andrews, Tallulah; Yiu, Andrew; Chandra, Tamir; Natarajan, Kedar N; Reik, Wolf; Barahona, Mauricio; Green, Anthony R; Hemberg, Martin (mayo de 2017). "SC3: agrupación de consenso de datos de secuencia de ARN de una sola célula" . Métodos de la naturaleza . 14 (5): 483–486. doi : 10.1038 / nmeth.4236 . ISSN 1548-7091 . PMC 5410170 . PMID 28346451 .
- ^ Resolución de problemas de conjuntos de clústeres mediante la partición de gráficos bipartitos, Xiaoli Zhang Fern y Carla Brodley , Actas de la vigésimo primera conferencia internacional sobre aprendizaje automático
- ^ Lock, EF; Dunson, DB (2013). "Agrupación de consenso bayesiano" . Bioinformática . 29 (20): 2610–2616. arXiv : 1302.7280 . Código Bibliográfico : 2013arXiv1302.7280L . doi : 10.1093 / bioinformatics / btt425 . PMC 3789539 . PMID 23990412 .
Referencias
- Alexander Strehl y J. Ghosh, Conjuntos de clústeres: un marco de reutilización del conocimiento para combinar varias particiones , Journal on Machine Learning Research (JMLR) 2002, 3, 583–617.
- Kunal Punera, Joydeep Ghosh. Conjuntos de agrupamientos blandos basados en consenso .
- Aristides Gionis, Heikki Mannila , Panayiotis Tsaparas. Agrupación de agrupaciones . 21a Conferencia Internacional sobre Ingeniería de Datos (ICDE 2005)
- Hongjun Wang, Hanhuai Shan, Arindam Banerjee. Conjuntos de clústeres bayesianos [ enlace muerto permanente ] , SIAM International Conference on Data Mining, SDM 09
- Nam Nguyen, Rich Caruana. Agrupaciones de consenso. Séptima Conferencia Internacional IEEE sobre Minería de Datos.
- Alexander Topchy, Anil K. Jain, William Punch. Agrupación de conjuntos: modelos de consenso y particiones débiles . IEEE International Conference on Data Mining, ICDM 03 & SIAM International Conference on Data Mining, SDM 04