Agrupación de correlación

La agrupación es el problema de dividir puntos de datos en grupos en función de su similitud. La agrupación por correlación proporciona un método para agrupar un conjunto de objetos en el número óptimo de grupos sin especificar ese número de antemano. ^[1]

Descripción del problema

En el aprendizaje automático , la agrupación por correlación o la edición de agrupaciones opera en un escenario donde 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 de los bordes indica si dos nodos son similares (peso de los bordes positivos) o diferentes (peso de los bordes negativos), la tarea es encontrar una agrupación que maximice los acuerdos (suma de los pesos de los bordes positivos dentro de un clúster). 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 agrupamiento, este no requiere elegir el número de grupos de antemano porque el objetivo, minimizar la suma de los pesos de los bordes cortados, es independiente del número de grupos. ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

Puede que no sea posible encontrar una agrupación perfecta, donde todos los elementos similares estén en un grupo mientras que todos los diferentes estén en grupos diferentes. Si el gráfico realmente admite una agrupación perfecta, simplemente eliminando todos los bordes negativos y encontrando los componentes conectados en el gráfico restante se obtendrán los grupos requeridos.

Pero, en general, es posible que un gráfico no tenga una agrupación perfecta. Por ejemplo, dados nodos a,b,c tales que a, by a,c son similares mientras que b,c son diferentes, no es posible una agrupación perfecta. En tales casos, la tarea es encontrar una agrupación que maximice el número de acuerdos (el número de aristas + dentro de los conglomerados más el número de aristas - entre conglomerados) o minimice el número de desacuerdos (el número de aristas - dentro de los conglomerados más el número de + aristas entre clusters). Este problema de maximizar los acuerdos es NP-completo (el problema de corte multidireccional se reduce a maximizar los acuerdos ponderados y el problema de la partición en triángulos ^[2] se puede reducir a la versión no ponderada).

Definiciones formales

Sea un gráfico con nodos y aristas . Una agrupación de es una partición de su conjunto de nodos con y para . Para una agrupación dada , denotemos el subconjunto de aristas cuyos puntos finales están en diferentes subconjuntos de la agrupación . Ahora, sea una función que asigna un peso no negativo a cada borde del gráfico y sea una partición de los bordes en bordes atractivos ( ) y repulsivos ( ). ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle \Pi =\{\pi _{1},\dots ,\pi _{k}\}}$ ${\displaystyle V=\pi _{1}\cup \dots \cup \pi _{k}}$ ${\displaystyle \pi _{i}\cap \pi _{j}=\emptyset }$ ${\displaystyle i\neq j}$ ${\displaystyle \Pi }$ ${\displaystyle \delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}}$ ${\displaystyle G}$ ${\displaystyle \Pi }$ ${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$ ${\displaystyle E=E^{+}\cup E^{-}}$ ${\displaystyle E^{+}}$ ${\displaystyle E^{-}}$

El problema de agrupamiento de correlación de desacuerdo mínimo es el siguiente problema de optimización:

$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in E^{+}\cap \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{aligned}}}$$

${\displaystyle E^{+}\cap \delta (\Pi )}$ ${\displaystyle \Pi }$ ${\displaystyle E^{-}\setminus \delta (\Pi )}$ ${\displaystyle \Pi }$ ${\displaystyle \Pi }$

De manera similar al problema de agrupamiento de correlación de desacuerdo mínimo, el problema de agrupamiento de correlación de acuerdo máximo se define como

$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{aligned}}}$$

${\displaystyle E^{+}\setminus \delta (\Pi )}$ ${\displaystyle \Pi }$ ${\displaystyle E^{-}\cap \delta (\Pi )}$ ${\displaystyle \Pi }$ ${\displaystyle \Pi }$

En lugar de formular el problema de agrupamiento de correlación en términos de pesos de aristas no negativos y una partición de las aristas en aristas atractivas y repulsivas, el problema también se formula en términos de costos de aristas positivas y negativas sin dividir explícitamente el conjunto de aristas. Para pesos dados y una partición dada de los bordes en bordes atractivos y repulsivos, los costos de los bordes se pueden definir por ${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$ ${\displaystyle E=E^{+}\cup E^{-}}$

$${\displaystyle {\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}}$$

${\displaystyle e\in E}$

Se dice que una arista cuyos puntos finales están en diferentes grupos está cortada. El conjunto de todas las aristas que se cortan suele denominarse multicorte ^[3] de . ${\displaystyle \delta (\Pi )}$ ${\displaystyle G}$

El problema multicorte de costo mínimo es el problema de encontrar una agrupación tal que la suma de los costos de los bordes cuyos puntos finales están en diferentes agrupaciones sea mínima: ${\displaystyle \Pi }$ ${\displaystyle G}$

$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

De manera similar al problema multicorte de costo mínimo, la generación de estructuras de coalición en juegos de gráficos ponderados ^[4] es el problema de encontrar una agrupación tal que la suma de los costos de los bordes que no se cortan sea máxima:

$${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

^[5]

Se puede demostrar que los cuatro problemas formulados anteriormente son equivalentes. Esto significa que una agrupación que sea óptima con respecto a cualquiera de los cuatro objetivos es óptima para los cuatro objetivos.

Algoritmos

Bansal et al. ^[6] analizan la prueba de completitud NP y también presentan un algoritmo de aproximación de factor constante y un esquema de aproximación de tiempo polinomial para encontrar los grupos en este entorno. Ailon et al. ^[7] proponen un algoritmo aleatorio de 3 aproximaciones para el mismo problema.

Pivote CC (G=(V,E + ,E − )) Elija pivote aleatorio i ∈ V Conjunto , V'=Ø Para todo j ∈ V, j ≠ i; Si (i,j) ∈ E + entonces ${\displaystyle C=\{i\}}$  Añadir j a C De lo contrario (Si (i,j) ∈ E − ) Sumar j a V' Sea G' el subgrafo inducido por V' Agrupación de retorno C,CC-Pivot(G')

Los autores muestran que el algoritmo anterior es un algoritmo de 3 aproximaciones para agrupamiento de correlación. El mejor algoritmo de aproximación en tiempo polinomial conocido hasta el momento para este problema logra una aproximación de ~2,06 redondeando un programa lineal, como lo muestran Chawla , Makarychev, Schramm y Yaroslavtsev . ^[8]

Karpinski y Schudy ^[9] 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 grupos.

Número óptimo de grupos

^{En 2011, Bagon y Galun [10]} demostraron que la optimización de la función de agrupamiento de correlación está estrechamente relacionada con métodos de optimización discretos bien conocidos . En su trabajo propusieron un análisis probabilístico del modelo implícito subyacente que permite que la correlación funcional de agrupamiento estime el número subyacente de conglomerados. Este análisis sugiere que lo funcional supone un previo uniforme sobre todas las particiones posibles, independientemente de su número de grupos. Así, surge una previa no uniforme sobre el número de clusters.

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 clusters en varias aplicaciones.

Agrupación de correlación (minería de datos)

La agrupación por correlación también se relaciona con una tarea diferente, donde se supone que existen correlaciones entre atributos de 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 grupos. Por tanto, la similitud entre los objetos del clúster se define teniendo en cuenta los patrones de correlación locales. Con esta noción, el término se ha introducido en ^[11] simultáneamente con la noción comentada anteriormente. En ^[12] se analizan diferentes métodos para la agrupación por correlación de este tipo y en ^[13] se analiza la relación con los diferentes tipos de agrupación. Consulte también Agrupación de datos de alta dimensión .

Se puede demostrar que el agrupamiento por correlación (según esta definición) está estrechamente relacionado con el biclustering . 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 grupos individuales.

Referencias

1. Becker, Hila, "Una encuesta sobre agrupación de correlación", 5 de mayo de 2005
2. Garey, M. y Johnson, D (WH Freeman and Company). (2000). Computadoras e intratabilidad: una guía para la teoría de la integridad NP .{{cite conference}}: CS1 maint: multiple names: authors list (link)
3. Deza, M .; Grötschel, M .; Laurent, M. (1992). "Facetas Clique-Web para politopos multicorte". Matemáticas de la Investigación de Operaciones . 17 (4): 981–1000. doi :10.1287/moor.17.4.981.
4. Bachrach, Yoram; Kohli, Pushmeet; Kolmogorov, Vladimir; Zadimoghaddam, Morteza (2013). "Generación de estructura de coalición óptima en juegos de gráficos cooperativos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . vol. 27. págs. 81–87.{{cite conference}}: CS1 maint: multiple names: authors list (link)
5. Grötschel, G.; Wakabayashi, Y. (1989). "Un algoritmo de plano de corte para un problema de agrupamiento". Programación Matemática . 45 : 59–96. doi :10.1007/BF01589097.
6. 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 .
7. Ailon, N.; Charikar, M.; Newman, A. (2005). "Agregar información inconsistente". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la informática - STOC '05 . pag. 684. doi :10.1145/1060590.1060692. ISBN 1581139608.
8. Chawla, Shuchi ; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigori . "Algoritmo de redondeo LP casi óptimo para agrupaciones de correlación en gráficos k-partitos completos y completos". Actas del 46º Simposio Anual ACM sobre Teoría de la Computación .
9. Karpinski, M.; Schudy, W. (2009). "Esquemas de aproximación en tiempo lineal para el juego Gale-Berlekamp y problemas de minimización relacionados". Actas del 41º simposio anual de ACM sobre Simposio sobre teoría de la informática - STOC '09 . pag. 313. arXiv : 0811.3244 . doi :10.1145/1536414.1536458. ISBN 9781605585062.
10. Bagón, S.; Galun, M. (2011) "Optimización de agrupación en clústeres de correlación a gran escala" arXiv :1112.2903v1
11. Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Cálculo de grupos de objetos conectados por correlación". Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos - SIGMOD '04 . pag. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN  978-1581138597. S2CID  6411037.
12. Zimek, A. (2008). Agrupación de correlación (Texto.Tesis doctoral). Universidad Ludwig-Maximilians de Múnich.
13. Kriegel, HP ; Kröger, P.; Zimek, A. (2009). "Agrupación de datos de alta dimensión". Transacciones ACM sobre descubrimiento de conocimiento a partir de datos . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.