Propagación por afinidad

Algoritmo en minería de datos

En estadística y minería de datos , la propagación por afinidad (AP) es un algoritmo de agrupamiento basado en el concepto de "paso de mensajes" entre puntos de datos. ^[1] A diferencia de los algoritmos de agrupamiento como k -means o k -medoids , 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 k -medoids, la propagación por afinidad encuentra "ejemplares", miembros del conjunto de entrada que son representativos de los clústeres. ^[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 cuantifica la similitud entre dos puntos cualesquiera, de modo que s ( i , j ) > s ( i , k ) si y solo si x _i es más similar a x _j que a x _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 (es decir, ) es particularmente importante, ya que representa la preferencia de instancia, es decir, la probabilidad de que una instancia en particular se convierta en un ejemplar. 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 media de todos los pares de entradas. ${\displaystyle s(i,i)}$

El algoritmo avanza 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 qué tan adecuado es x _k para servir como ejemplo 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 con todos los valores cero y pueden verse como tablas de probabilidad logarítmica . A continuación, el algoritmo realiza las siguientes actualizaciones de forma iterativa:

• En primer lugar, se envían actualizaciones de responsabilidad: ${\displaystyle r(i,k)\gets s(i,k)-\max _{k'\neq k}{\left\{a(i,k')+s(i,k')\right\}}}$
• Luego, la disponibilidad se actualiza por y $${\displaystyle a(i,k)\gets \min {\left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)}\quad {\text{ for }}i\neq k}$$ $${\displaystyle a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k)).}$$

Se realizan iteraciones hasta que los límites del grupo permanecen inalterados a lo largo de 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 artificial y biología computacional , por ejemplo, la agrupación de imágenes de rostros humanos y la identificación de transcripciones reguladas, que k -means, ^[1] incluso cuando se permitieron muchos reinicios aleatorios a k -means y se inicializó 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 semisupervisada 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 .
• Una implementación de Julia de la propagación de afinidad está contenida en el paquete Clustering.jl de Julia Statistics.
• 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). "Agrupamiento mediante el paso de mensajes entre puntos de datos". Science . 315 (5814): 972–976. Bibcode :2007Sci...315..972F. CiteSeerX  10.1.1.121.3145 . doi :10.1126/science.1136800. PMID  17218491. S2CID  6502291.
2. Delbert Dueck; Brendan J. Frey (2007). Propagación de afinidad no métrica para la categorización de imágenes no supervisada . Conferencia Internacional sobre Visión Artificial. doi :10.1109/ICCV.2007.4408853.
3. James Vlasblom; Shoshana Wodak (2009). "Agrupamiento de Markov versus propagación de afinidad para la partición de gráficos de interacción de proteínas". BMC Bioinformatics . 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). "Agrupamiento de texto con propagación de afinidad de semillas". IEEE Transactions on Knowledge and Data Engineering . 23 (4): 627–637. doi :10.1109/tkde.2010.144. hdl : 11572/89884 . S2CID  14053903.
5. Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (1 de junio de 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. S2CID  216406772.