La agrupación en clústeres es el problema de dividir los puntos de datos en grupos en función de su similitud. La agrupación en clústeres de correlación proporciona un método para agrupar un conjunto de objetos en el número óptimo de clústeres sin especificar ese número por adelantado. [1]
Descripción del problema
En el aprendizaje automático , la agrupación en clústeres de correlación o la edición de clústeres opera en un escenario en el que se conocen las relaciones entre los objetos en lugar de las representaciones reales de los objetos. Por ejemplo, dado un gráfico ponderado donde el peso del borde indica si dos nodos son similares (peso del borde positivo) o diferentes (peso del borde negativo), la tarea es encontrar un agrupamiento que maximice los acuerdos (suma de los pesos del borde positivo dentro de un grupo más el valor absoluto de la suma de los pesos de los bordes negativos entre grupos) o minimiza los desacuerdos (valor absoluto de la suma de los pesos de los bordes negativos dentro de un grupo más la suma de los pesos de los bordes positivos entre los grupos). A diferencia de otros algoritmos de agrupación, esto no requiere elegir el número de agrupaciones. de antemano porque el objetivo, minimizar la suma de pesos de los bordes cortados, es independiente del número de racimos.
Puede que no sea posible encontrar un agrupamiento perfecto, donde todos los elementos similares están en un grupo mientras que todos los diferentes están en grupos diferentes. Si el gráfico admite un agrupamiento perfecto, entonces simplemente borrando todos los bordes negativos y encontrando los componentes conectados en el gráfico restante, se devolverán los grupos requeridos.
Pero, en general, es posible que un gráfico no tenga una agrupación perfecta. Por ejemplo, dada nodos a, b, c de tal manera que a, b y a, c son similares, mientras que b, c son diferentes, una agrupación perfecto no es posible. En tales casos, la tarea es encontrar un agrupamiento que maximice el número de acuerdos (número de bordes + dentro de los grupos más el número de bordes - entre grupos) o minimice el número de desacuerdos (el número de bordes dentro de los grupos más el número de bordes + entre grupos). Este problema de maximizar los acuerdos es NP-completo (el problema del corte de múltiples vías se reduce a maximizar los acuerdos ponderados y el problema de dividir en triángulos [2] se puede reducir a la versión no ponderada).
Algoritmos
Bansal y col. [3] discuten la prueba de NP-completitud y también presentan un algoritmo de aproximación de factor constante y un esquema de aproximación de tiempo polinómico para encontrar los conglomerados en esta configuración. Ailon y col. [4] proponen un algoritmo de aproximación aleatoria de 3 para el mismo problema.
CC-Pivote (G = (V, E + , E - )) Elija pivote aleatorio i ∈ V Colocar , V '= Ø Para todo j ∈ V, j ≠ i; Si (i, j) ∈ E + entonces Suma j a C Else (Si (i, j) ∈ E - ) Agregar j a V ' Sea G 'el subgrafo inducido por V' Clúster de retorno C, CC-Pivot (G ')
Los autores muestran que el algoritmo anterior es un algoritmo de 3 aproximaciones para la agrupación de correlaciones. El mejor algoritmo de aproximación de tiempo polinomial conocido en este momento para este problema logra una aproximación de ~ 2.06 al redondear un programa lineal, como lo muestran Chawla , Makarychev, Schramm y Yaroslavtsev . [5]
Karpinski y Schudy [6] demostraron la existencia de un esquema de aproximación de tiempo polinomial (PTAS) para ese problema en gráficos completos y un número fijo de conglomerados.
Número óptimo de clústeres
En 2011, Bagon y Galun [7] demostraron que la optimización de la función de agrupación en clústeres de correlación está estrechamente relacionada con métodos de optimización discreta bien conocidos . En su trabajo, propusieron un análisis probabilístico del modelo implícito subyacente que permite a la agrupación de correlación funcional para estimar el número subyacente de agrupaciones. Este análisis sugiere que el funcional asume un antecedente uniforme sobre todas las particiones posibles independientemente de su número de clústeres. Por lo tanto, surge un a priori no uniforme sobre el número de conglomerados.
En este trabajo se proponen varios algoritmos de optimización discretos que escalan elegantemente con el número de elementos (los experimentos muestran resultados con más de 100.000 variables). El trabajo de Bagon y Galun también evaluó la efectividad de la recuperación del número subyacente de clústeres en varias aplicaciones.
Agrupación en clústeres de correlación (minería de datos)
La agrupación de correlaciones también se relaciona con una tarea diferente, donde se supone que existen correlaciones entre los atributos de los vectores de características en un espacio de alta dimensión que guían el proceso de agrupación . Estas correlaciones pueden ser diferentes en diferentes grupos, por lo que una descorrelación global no puede reducir esto a un agrupamiento tradicional (no correlacionado).
Las correlaciones entre subconjuntos de atributos dan como resultado diferentes formas espaciales de conglomerados. Por lo tanto, la similitud entre los objetos del clúster se define teniendo en cuenta los patrones de correlación local. Con esta noción, el término se ha introducido en [8] simultáneamente con la noción discutida anteriormente. Diferentes métodos para el agrupamiento de correlación de este tipo se discuten en [9] y la relación con los diferentes tipos de agrupamiento se discute en. [10] Véase también la agrupación de datos de alta dimensión .
Se puede demostrar que la agrupación en clústeres de correlación (según esta definición) está estrechamente relacionada con la agrupación en dos . Al igual que en el biclustering, el objetivo es identificar grupos de objetos que comparten una correlación en algunos de sus atributos; donde la correlación suele ser típica de los conglomerados individuales.
Referencias
- ^ Becker, Hila, "A Survey of Correlation Clustering", 5 de mayo de 2005
- ^ Garey, M. y Johnson, D (WH Freeman and Company). (2000). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Bansal, N .; Blum, A .; Chawla, S. (2004). "Agrupación de correlación" . Aprendizaje automático . 56 (1-3): 89-113. doi : 10.1023 / B: MACH.0000033116.57574.95 .
- ^ Ailon, N .; Charikar, M .; Newman, A. (2005). "Agregando información inconsistente". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la computación - STOC '05 . pag. 684. doi : 10.1145 / 1060590.1060692 . ISBN 1581139608.
- ^ Chawla, Shuchi ; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory . "Algoritmo de redondeo LP casi óptimo para el agrupamiento de correlación en gráficos completos y completos de k-partitas". Actas del 46º Simposio Anual de ACM sobre Teoría de la Computación .
- ^ Karpinski, M .; Schudy, W. (2009). "Esquemas de aproximación de tiempo lineal para el juego Gale-Berlekamp y problemas de minimización relacionados". Actas del 41º simposio anual de ACM sobre el Simposio sobre teoría de la computación - STOC '09 . pag. 313. arXiv : 0811.3244 . doi : 10.1145 / 1536414.1536458 . ISBN 9781605585062.
- ^ Bagon, S .; Galun, M. (2011) "Optimización de agrupación en clústeres de correlación a gran escala" arXiv : [https://arxiv.org/abs/1112.2903v1 1112.2903v1]
- ^ Böhm, C .; Kailing, K .; Kröger, P .; Zimek, A. (2004). "Computación Clústeres de objetos conectados de correlación". Actas de la conferencia internacional 2004 ACM SIGMOD sobre Gestión de datos - SIGMOD '04 . pag. 455. CiteSeerX 10.1.1.5.1279 . doi : 10.1145 / 1007568.1007620 . ISBN 978-1581138597.
- ^ Zimek, A. (2008). "Agrupación de correlación" . Cite journal requiere
|journal=
( ayuda ) - ^ Kriegel, HP ; Kröger, P .; Zimek, A. (2009). "Agrupación de datos de alta dimensión". Transacciones de ACM sobre descubrimiento de conocimientos a partir de datos . 3 : 1-58. doi : 10.1145 / 1497577.1497578 .