stringtranslate.com

Agrupación de consenso

La agrupación por consenso es un método para agregar resultados (potencialmente conflictivos) de múltiples algoritmos de agrupación . También llamado conjunto de clusters [1] o agregación de clustering (o particiones), se refiere a la situación en la que se han obtenido varios clusterings (de entrada) diferentes para un conjunto de datos particular y se desea encontrar un clustering único (de consenso). que, en cierto sentido, encaja mejor que las agrupaciones existentes. [2] La agrupación por consenso es, por tanto, el problema de conciliar información de agrupación sobre el mismo conjunto de datos procedente de diferentes fuentes o de diferentes ejecuciones del mismo algoritmo. Cuando se plantea como un problema de optimización, la agrupación por 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] La agrupación por consenso para el aprendizaje no supervisado es análoga al aprendizaje conjunto en el aprendizaje supervisado.

Problemas con las técnicas de agrupación existentes

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 conoce el número de conglomerados. 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 repetitivos. Una cuestión extremadamente importante en el análisis de conglomerados es la validación de los resultados de la agrupación, es decir, cómo ganar confianza sobre la importancia de los conglomerados proporcionada por la técnica de agrupación (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 agrupamiento de descenso iterativo, como el SOM y el agrupamiento de k-medias, evitan algunas de las deficiencias del agrupamiento jerárquico al proporcionar grupos y límites de grupo definidos unívocamente. La agrupación por consenso proporciona un método que representa el consenso entre múltiples ejecuciones de un algoritmo de agrupación, para determinar la cantidad de grupos en los datos y evaluar la estabilidad de los grupos descubiertos. 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.), para tener en cuenta su sensibilidad a las condiciones iniciales. . Puede proporcionar datos para que una herramienta de visualización inspeccione el número, la membresía y los límites del grupo. Sin embargo, carecen del atractivo intuitivo y visual de los dendrogramas de agrupamiento jerárquico, y el número de grupos debe elegirse a priori.

El algoritmo de agrupamiento por 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 con el número total de puntos para agrupar, este algoritmo funciona remuestreando y agrupando los datos, para cada uno y se calcula una matriz de consenso, donde cada elemento representa la fracción de veces dos muestras agrupadas. Una matriz perfectamente estable estaría compuesta enteramente de ceros y unos, lo que representaría todos los pares de muestras siempre agrupados o no juntos durante 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, sea la lista de conjuntos de datos perturbados (remuestreados) del conjunto de datos original , y denotemos la matriz de conectividad resultante de aplicar un algoritmo de agrupación al conjunto de datos . Las entradas de se definen de la siguiente manera:

Sea la matriz de identificador donde la -ésima entrada es igual a 1 si los puntos y están en el mismo conjunto de datos perturbados , y 0 en caso contrario. La matriz de indicadores se utiliza para realizar un seguimiento de qué muestras 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 uno .

Es decir, la entrada en la matriz de consenso es el número de veces que los puntos se agruparon dividido por el número total de veces que se seleccionaron juntos. La matriz es simétrica y cada elemento está definido dentro del rango . Se calcula una matriz de consenso para cada una de las que se va a probar, y la estabilidad de cada matriz, es decir, qué tan lejos está la matriz de una matriz de estabilidad perfecta (solo ceros y unos), se utiliza para determinar el valor óptimo . Una forma de cuantificar la estabilidad de la matriz de consenso es examinar su curva CDF (ver más abajo).

Potencial de sobreinterpretación del algoritmo de agrupamiento por consenso de Monti

Explicación de la medida PAC (proporción de agrupamiento ambiguo). La K óptima es la K con el valor de PAC más bajo.

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 agrupamiento por consenso de Monti es capaz de afirmar una estabilidad aparente 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 sobreinterpretación de la estabilidad del grupo en un estudio real. [6] [7] Si los grupos no están bien separados, el agrupamiento por consenso podría llevar a uno a concluir una estructura aparente cuando no la hay, o declarar la estabilidad del grupo cuando es sutil. La identificación de conglomerados de falsos positivos es un problema común en toda la investigación de conglomerados [8] y se ha abordado mediante 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 que la métrica delta K original para decidir en el algoritmo de Monti funcionó mal y propusieron 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 pares de muestras que rara vez se agrupan, la parte superior derecha representa aquellas que casi siempre se agrupan, mientras que el segmento medio representa aquellos con asignaciones ambiguas en diferentes ejecuciones de agrupación. La medida de puntuación de proporció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 y u 2 = 0,9). Un valor bajo de PAC indica un segmento medio plano y una tasa baja de asignaciones discordantes en ejecuciones de agrupamiento permutadas. Por lo tanto, se puede inferir el número óptimo de conglomerados por el valor 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 lo reducen a un problema de partición de hipergráficos . 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 k -partición del gráfico, que no tiene en cuenta la penalización por fusionar dos nodos que están muy separados. [1]
  2. Agregación de agrupaciones (Fern y Brodley) : aplicaron la idea de agregación de agrupaciones a una colección de agrupaciones suaves que obtuvieron mediante proyecciones aleatorias. Utilizaron un algoritmo aglomerativo y no penalizaron por fusionar nodos diferentes. [10]
  3. Fred y Jain : propusieron utilizar un algoritmo de enlace único para combinar múltiples ejecuciones del algoritmo k -means. [11]
  4. Dana Cristofor y Dan Simovici : Observaron la conexión entre la agregación en clústeres 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. [12]
  5. Topchy et al. : Definieron la agregación de agrupamientos como un problema de estimación de máxima verosimilitud y propusieron un algoritmo EM para encontrar el agrupamiento de consenso. [13]

Agrupación de conjuntos difíciles

Este enfoque de Strehl y Ghosh introduce el problema de combinar múltiples particiones de un conjunto de objetos en un único cluster 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 factible evaluar cada una de las técnicas que se analizan 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 de similitud basado en conglomerados (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 están agrupados. La intuición es que cuanto más similares sean dos puntos de datos, mayor será la probabilidad de que los agrupamientos de 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. [14] 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 como la partición del hipergrafo cortando un número mínimo de hiperfilos. Hacen uso de hMETIS, que es un sistema de paquete de partición de hipergrafos.
  3. Algoritmo de metaagrupación (MCLA) : El algoritmo de metaagrupación (MCLA) se basa en la agrupación de clústeres. Primero, intenta resolver el problema de correspondencia de los grupos y luego utiliza la votación para colocar puntos de datos en los grupos de consenso finales. El problema de correspondencia de conglomerados se resuelve agrupando los conglomerados identificados en los agrupamientos individuales del conjunto. La agrupación se realiza utilizando METIS y agrupación espectral.

Conjuntos de agrupamiento 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 membresía posterior obtenidas de los algoritmos de agrupamiento de constituyentes. Podemos definir una medida de distancia entre dos instancias utilizando la divergencia de Kullback-Leibler (KL) , que calcula la "distancia" entre dos distribuciones de probabilidad. [15]

  1. 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 que pertenezca 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 : extiende MCLA aceptando agrupaciones suaves como entrada. El funcionamiento de sMCLA se puede dividir en los siguientes pasos:
    • Construya un metagráfico suave de conglomerados
    • Agrupe los clústeres en metaclústeres
    • Contraer metagrupos mediante ponderación
    • Competir por objetos
  3. sHBGF : 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. [16] Este enfoque puede adaptarse 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 van a dividir. En sHBGF, el gráfico tiene n  +  t vértices, donde t es el número total de grupos subyacentes.
  4. Agrupación de consenso bayesiano (BCC) : define un modelo completamente bayesiano para agrupación de consenso suave en el que se supone que 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. [17] La ​​parte posterior completa para los agrupamientos separados y el agrupamiento por consenso se infieren simultáneamente mediante el muestreo de Gibbs .
  5. Medios de fuzzificación de agrupamiento en clústeres (ECF-Means) : ECF-means es un algoritmo de agrupamiento que combina diferentes resultados de agrupamiento en conjunto, logrados mediante diferentes ejecuciones de un algoritmo elegido ( k-means ), en una única configuración de agrupamiento final. [18]

Referencias

  1. ^ ab Strehl, Alejandro ; Ghosh, Joydeep (2002). "Conjuntos de clústeres: un marco de reutilización de conocimientos para combinar varias particiones" (PDF) . Revista de investigación sobre aprendizaje automático (JMLR) . 3 : 583–617. doi :10.1162/153244303321897735. S2CID  3068944. Este artículo presenta el problema de combinar múltiples particiones de un conjunto de objetos en un único clúster consolidado sin acceder a las funciones o algoritmos que determinaron estas particiones. Primero identificamos varios escenarios de aplicación para el marco de 'reutilización de conocimiento' resultante que llamamos conjuntos de clústeres. Luego, el problema del conjunto de conglomerados se formaliza como un problema de optimización combinatoria en términos de información mutua compartida.
  2. ^ VEGA-PONS, SANDRO; RUIZ-SHULCLOPER, JOSÉ (1 de mayo de 2011). "Un estudio de algoritmos de conjuntos de agrupamiento". Revista Internacional de Reconocimiento de Patrones e Inteligencia Artificial . 25 (3): 337–372. doi :10.1142/S0218001411008683. S2CID  4643842.
  3. ^ Filkov, Vladimir (2003). "Integración de datos de microarrays mediante agrupación por consenso". Actas. 15ª Conferencia Internacional IEEE sobre Herramientas con Inteligencia Artificial . págs. 418–426. CiteSeerX 10.1.1.116.8271 . doi :10.1109/TAI.2003.1250220. ISBN  978-0-7695-2038-4. S2CID  1515525.
  4. ^ Bonizzoni, Paola; Della Vedova, Gianluca; Dondi, Ricardo; Jiang, Tao (2008). "Sobre la aproximación de la agrupación por correlación y la agrupación por consenso". Revista de Ciencias de la Computación y de Sistemas . 74 (5): 671–696. doi : 10.1016/j.jcss.2007.06.024 .
  5. ^ Monti, Stefano; Tamayo, Pablo; Mesirov, Jill; Golub, Todd (1 de julio de 2003). "Agrupación de consenso: un método basado en remuestreo para el descubrimiento de clases y la visualización de datos de microarrays de expresión genética". Aprendizaje automático . 52 (1): 91-118. doi : 10.1023/A:1023949509487 . ISSN  1573-0565.
  6. ^ abcd Şenbabaoğlu, Y.; Michailidis, G.; Li, JZ (2014). "Limitaciones críticas de la agrupación por 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. 
  7. ^ ab Şenbabaoğlu, Y.; Michailidis, G.; Li, JZ (febrero de 2014). "Una reevaluación de la agrupación por consenso para el descubrimiento de clases". bioRxiv 10.1101/002642 . 
  8. ^ ab Liu, Yufeng; Hayes, David Neil; Nobel, Andrés; Marrón, JS (1 de septiembre de 2008). "Importancia estadística de la agrupación para datos de alta dimensión y 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.
  9. ^ Tibshirani, Robert; Walther, Günther; Hastie, Trevor (2001). "Estimación del número de grupos en un conjunto de datos mediante 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. S2CID  59738652.
  10. ^ Helecho, Xiaoli; Brodley, Carla (2004). "Conjuntos de clusters para clustering de alta dimensión: un estudio empírico". J Mach Aprender Res . 22 .
  11. ^ Fred, Ana LN; Jainista, Anil K. (2005). "Combinación de múltiples agrupaciones mediante acumulación de evidencia" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 27 (6): 835–850. doi :10.1109/tpami.2005.113. ISSN  0162-8828. PMID  15943417. S2CID  10316033.
  12. ^ Dana Cristofor, Dan Simovici (febrero de 2002). "Encontrar particiones medianas utilizando algoritmos genéticos basados ​​en la teoría de la información" (PDF) . Revista de Informática Universal . 8 (2): 153–172. doi :10.3217/jucs-008-02-0153.
  13. ^ Alexander Topchy, Anil K. Jain, William Punch. Conjuntos de agrupación: modelos de consenso y particiones débiles. Conferencia Internacional IEEE sobre Minería de Datos, ICDM 03 y Conferencia Internacional SIAM sobre Minería de Datos, SDM 04
  14. ^ Kiselev, Vladimir Yu; Kirschner, Kristina; Schaub, Michael T; Andrews, Tallulah; Yiu, Andrés; Chandra, Tamir; Natarajan, Kedar N; Reik, Lobo; Barahona, Mauricio; Verde, Antonio R; Hemberg, Martín (mayo de 2017). "SC3: agrupación por consenso de datos de RNA-seq unicelulares". Métodos de la naturaleza . 14 (5): 483–486. doi :10.1038/nmeth.4236. ISSN  1548-7091. PMC 5410170 . PMID  28346451. 
  15. ^ Kunal Punera, Joydeep Ghosh. Conjuntos de agrupaciones blandas basadas en el consenso
  16. ^ Resolución de problemas de conjuntos de conglomerados mediante partición de gráficos bipartitos, Xiaoli Zhang Fern y Carla Brodley , Actas de la vigésimo primera conferencia internacional sobre aprendizaje automático
  17. ^ Bloquear, EF; Dunson, DB (2013). "Agrupación de consenso bayesiano". Bioinformática . 29 (20): 2610–2616. arXiv : 1302.7280 . Código Bib : 2013arXiv1302.7280L. doi : 10.1093/bioinformática/btt425. PMC 3789539 . PMID  23990412. 
  18. ^ Zazzaro, Gaetano; Martone, Angelo (2018). "ECF-means - Medios de fuzzificación de agrupación en conjuntos. Un algoritmo novedoso para la agregación, fuzzificación y optimización de agrupaciones". IMM 2018: Octava Conferencia Internacional sobre Avances en Minería y Gestión de Información .[1]