Propagación de afinidad

En estadística y minería de datos , la propagación por afinidad (AP) es un algoritmo de agrupación basado en el concepto de "transmisión de mensajes" entre puntos de datos. ^[1] A diferencia de los algoritmos de agrupamiento en clústeres, como k- medias o k -medoides , la propagación por afinidad no requiere que se determine o estime el número de clústeres antes de ejecutar el algoritmo. De manera similar a los k -medoides, la propagación por afinidad encuentra "ejemplares", miembros del conjunto de entrada que son representativos de agrupaciones. ^[1]

Algoritmo

Sea x ₁ a x _n un conjunto de puntos de datos, sin suposiciones sobre su estructura interna, y sea s una función que cuantifique la similitud entre dos puntos cualesquiera, tal que s ( i , j )> s ( i , k ) si f x _i es más similar ax _j que ax _k . Para este ejemplo, se utilizó la distancia al cuadrado negativo de dos puntos de datos, es decir, para los puntos x _i y x _k , ^[1]${\displaystyle s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}}$

La diagonal de s (ie ) es particularmente importante, ya que representa la preferencia de instancia, es decir, la probabilidad de que una instancia particular se convierta en un ejemplo. Cuando se establece en el mismo valor para todas las entradas, controla cuántas clases produce el algoritmo. Un valor cercano a la similitud mínima posible produce menos clases, mientras que un valor cercano o mayor que la similitud máxima posible produce muchas clases. Por lo general, se inicializa con la similitud mediana de todos los pares de entradas.${\displaystyle s(i,i)}$

El algoritmo procede alternando entre dos pasos de paso de mensajes, que actualizan dos matrices: ^[1]

• La matriz de "responsabilidad" R tiene valores r ( i , k ) que cuantifican cuán adecuado es x _k para servir como modelo para x _i , en relación con otros ejemplos candidatos para x _i .
• La matriz de "disponibilidad" A contiene valores a ( i , k ) que representan cuán "apropiado" sería para x _i elegir x _k como su ejemplo, teniendo en cuenta la preferencia de otros puntos por x _k como ejemplo.

Ambas matrices se inicializan a todos los ceros y se pueden ver como tablas de probabilidad logarítmica . A continuación, el algoritmo realiza las siguientes actualizaciones de forma iterativa:

• Primero, se envían actualizaciones de responsabilidad: ${\displaystyle r(i,k)\leftarrow s(i,k)-\max _{k'\neq k}\left\{a(i,k')+s(i,k')\right\}}$
• Luego, la disponibilidad se actualiza por

${\displaystyle a(i,k)\leftarrow \min \left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)}$para y${\displaystyle i\neq k}$

${\displaystyle a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k))}$.

Las iteraciones se realizan hasta que los límites del clúster permanecen sin cambios durante una serie de iteraciones o hasta que se alcanza un número predeterminado (de iteraciones). Los ejemplares se extraen de las matrices finales como aquellos cuya 'responsabilidad + disponibilidad' para sí mismos es positiva (es decir ).${\displaystyle (r(i,i)+a(i,i))>0}$

Aplicaciones

Los inventores de la propagación por afinidad demostraron que es mejor para ciertas tareas de visión por computadora y biología computacional, por ejemplo, agrupación de imágenes de rostros humanos e identificación de transcripciones reguladas, que k -medias, ^[1] incluso cuando k -medias se permitieron muchos reinicios aleatorios e inicializados. utilizando PCA . ^[2] Un estudio que comparó la propagación por afinidad y la agrupación de Markov en la partición de gráficos de interacción de proteínas encontró que la agrupación de Markov funciona mejor para ese problema. ^[3] Se ha propuesto una variante semi-supervisada para aplicaciones de minería de texto . ^[4]Otra aplicación reciente fue en economía, cuando se utilizó la propagación por afinidad para encontrar algunos patrones temporales en los multiplicadores de producción de la economía estadounidense entre 1997 y 2017. ^[5]

Software

• Se incluye una implementación de Java en el marco de minería de datos ELKI .
• El paquete Clustering.jl de Julia Statistics contiene una implementación de Julia de la propagación por afinidad.
• Una versión de Python es parte de la biblioteca scikit-learn .
• Una implementación de R está disponible en el paquete "apcluster".

Referencias

1. Brendan J. Frey; Delbert Dueck (2007). "Agrupación pasando mensajes entre puntos de datos". Ciencia . 315 (5814): 972–976. CiteSeerX  10.1.1.121.3145 . doi : 10.1126 / science.1136800 . PMID  17218491 .
2. Delbert Dueck; Brendan J. Frey (2007). Propagación de afinidad no métrica para la categorización de imágenes sin supervisión . Conf. Int. en Visión por Computadora. doi : 10.1109 / ICCV.2007.4408853 .
3. James Vlasblom; Shoshana Wodak (2009). "Agrupación de Markov versus propagación de afinidad para la partición de gráficos de interacción de proteínas" . BMC Bioinformática . 10 (1): 99. doi : 10.1186 / 1471-2105-10-99 . PMC 2682798 . PMID 19331680 .  
4. Renchu ​​Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). "Agrupación de texto con propagación de afinidad de semillas". Transacciones IEEE sobre conocimiento e ingeniería de datos . 23 (4): 627–637. doi : 10.1109 / tkde.2010.144 . hdl : 11572/89884 .
5. Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (01/06/2020). "Aplicación del análisis multivariado como instrumento complementario en estudios sobre cambios estructurales: un ejemplo de los multiplicadores en la economía estadounidense" . Cambio estructural y dinámica económica . 53 : 189-207. doi : 10.1016 / j.strueco.2020.02.006 . ISSN 0954-349X .