Agrupamiento de correlación

Método de partición de puntos de datos en grupos según su similitud

La agrupación es el problema de dividir los puntos de datos en grupos según su similitud. La agrupación por correlación proporciona un método para agrupar un conjunto de objetos en la cantidad óptima de grupos sin especificar esa cantidad de antemano. ^[1]

Descripción del problema

En el aprendizaje automático , la agrupación por correlación o la edición de conglomerados funciona 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 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 conglomerado más el valor absoluto de la suma de los pesos de los bordes negativos entre conglomerados) o minimice los desacuerdos (valor absoluto de la suma de los pesos de los bordes negativos dentro de un conglomerado más la suma de los pesos de los bordes positivos entre conglomerados). A diferencia de otros algoritmos de agrupación, esto no requiere elegir el número de conglomerados de antemano porque el objetivo, minimizar la suma de los pesos de los bordes cortados, es independiente del número de conglomerados. ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

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

Pero, en general, un grafo puede no tener una agrupación perfecta. Por ejemplo, dados los nodos a, b, c tales que a, b y 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 (número de aristas + dentro de los grupos más el número de aristas − entre los grupos) o minimice el número de desacuerdos (el número de aristas − dentro de los grupos más el número de aristas + entre los grupos). 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 partición en triángulos ^[2] se puede reducir a la versión no ponderada).

Definiciones formales

Sea un grafo 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 , sea el subconjunto de aristas de cuyos extremos están en diferentes subconjuntos de la agrupación . Ahora, sea una función que asigna un peso no negativo a cada arista del grafo y sea una partición de las aristas en aristas atractivas ( ) y repulsivas ( ). ${\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 por correlación de desacuerdo mínimo es el siguiente problema de optimización: Aquí, el conjunto contiene las aristas atractivas cuyos puntos finales están en diferentes componentes con respecto al agrupamiento y el conjunto contiene las aristas repulsivas cuyos puntos finales están en el mismo componente con respecto al agrupamiento . Juntos, estos dos conjuntos contienen todas las aristas que están en desacuerdo con el agrupamiento . $${\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 por correlación de desacuerdo mínimo, el problema de agrupamiento por correlación de acuerdo máximo se define como Aquí, el conjunto contiene los bordes atractivos cuyos puntos finales están en el mismo componente con respecto al agrupamiento y el conjunto contiene los bordes repulsivos cuyos puntos finales están en diferentes componentes con respecto al agrupamiento . Juntos, estos dos conjuntos contienen todos los bordes que concuerdan con el agrupamiento . $${\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 por 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 positivos y negativos sin particionar el conjunto de aristas explícitamente. Para pesos dados y una partición dada de las aristas en aristas atractivas y repulsivas, los costos de aristas se pueden definir mediante para todos . ${\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 extremos se encuentran en diferentes grupos está cortada. El conjunto de todas las aristas que están cortadas se suele denominar multicorte ^[3] de . ${\displaystyle \delta (\Pi )}$ ${\displaystyle G}$

El problema de corte múltiple 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}}}$$

Similar al problema de corte múltiple de costo mínimo, la generación de estructura 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: esta formulación también se conoce como el problema de partición de camarillas. ^[5] $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

Se puede demostrar que los cuatro problemas que se formularon anteriormente son equivalentes. Esto significa que una agrupación que sea óptima con respecto a cualquiera de los cuatro objetivos es óptima para todos 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 clústeres en este contexto. Ailon et al. ^{[7] proponen un} algoritmo de aproximación 3- aleatorio para el mismo problema.

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

Los autores demuestran que el algoritmo anterior es un algoritmo de aproximación de 3- para la agrupación por correlación. El mejor algoritmo de aproximación de tiempo polinomial conocido en la actualidad para este problema logra una aproximación de ~2,06 redondeando un programa lineal, como lo demostraron Chawla , Makarychev, Schramm y Yaroslavtsev . ^[8]

Karpinski y Schudy ^[9] demostraron la existencia de un esquema de aproximación temporal polinomial (PTAS) para ese problema en gráficos completos y un número fijo de clústeres.

Número óptimo de clústeres

^{En 2011, Bagon y Galun [10]} demostraron que la optimización de la función de agrupamiento por 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 función de agrupamiento por correlación estime el número subyacente de clústeres. Este análisis sugiere que la función supone una distribución previa uniforme sobre todas las particiones posibles independientemente de su número de clústeres. Por lo tanto, surge una distribución previa no uniforme sobre el número de clústeres.

En este trabajo se proponen varios algoritmos de optimización discretos que escalan de forma elegante 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 eficacia de la recuperación del número subyacente de clústeres en varias aplicaciones.

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

La agrupación por correlación también se relaciona con una tarea diferente, en la que 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 agrupaciones, por lo que una decorrelación global no puede reducir esto a una agrupación tradicional (no correlacionada).

Las correlaciones entre subconjuntos de atributos dan como resultado diferentes formas espaciales de los clústeres. Por lo 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 discutida anteriormente. Diferentes métodos para la agrupación por correlación de este tipo se discuten en ^[12] y la relación con diferentes tipos de agrupación se discute en ^[13] . Véase también Agrupamiento de datos de alta dimensión .

Se puede demostrar que la agrupación por correlación (según esta definición) está estrechamente relacionada con la biagrupación . Al igual que en la biagrupación, 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 para los grupos individuales.

Referencias

1. Becker, Hila, "Un estudio sobre agrupamiento de correlaciones", 5 de mayo de 2005
2. Garey, M.; Johnson, D. (2000). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman and Company.
3. Deza, M. ; Grötschel, M. ; Laurent, M. (1992). "Facetas de red de clics para politopos de corte múltiple". 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 óptima de estructura de coalición 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 (1–3): 59–96. doi :10.1007/BF01589097.
6. Bansal, N.; Blum, A.; Chawla, S. (2004). "Agrupamiento 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). "Agregación de información inconsistente". Actas del trigésimo séptimo simposio anual de la ACM sobre teoría de la computación – STOC '05 . p. 684. doi :10.1145/1060590.1060692. ISBN 1581139608.
8. Chawla, Shuchi ; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory . "Algoritmo de redondeo de LP casi óptimo para agrupamiento de correlación en gráficos k-partitos completos y completos". Actas del 46.º Simposio anual de la ACM sobre teoría de la computación .
9. Karpinski, M.; Schudy, W. (2009). "Esquemas de aproximación de tiempo lineal para el juego de Gale-Berlekamp y problemas de minimización relacionados". Actas del 41.º simposio anual de la ACM sobre teoría de la computación – STOC '09 . pág. 313. arXiv : 0811.3244 . doi :10.1145/1536414.1536458. ISBN 9781605585062.
10. Bagon, S.; Galun, M. (2011) "Optimización de agrupamiento de correlación a gran escala" arXiv :1112.2903v1
11. Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Computing Clusters of Correlation Connected Objects". Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos – SIGMOD '04 . pág. 455. CiteSeerX 10.1.1.5.1279 . doi :10.1145/1007568.1007620. ISBN  978-1581138597.S2CID6411037  .​
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). "Agrupamiento de datos de alta dimensión". ACM Transactions on Knowledge Discovery from Data . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.