Propagación de afinidad

En estadística y minería de datos, propagación de afinidad (AP) es un algoritmo de clusterización basado en el concepto de «mensajeo» entre puntos de datos.^[1] A diferencia de algoritmos de clusterización como k-medias o k-medoides, propagación de afinidad no requiere que el número de grupos estén determinados o estimados antes de correr el algoritmo. Al igual que k-medoides, propagación de afinidad encuentra «ejemplares» miembros del conjunto de entrada que son representantes de los grupos.^[1]

Algoritmo

Sean $x_{1},..,x_{n}$ puntos de un conjunto de datos, sin suposiciones hechas sobre su estructura interna, y sea $s$ una función que cuantifica la similitud entre cualesquiera dos puntos, tal que $s(i,j)>s(i,k)$ sii $x_{i}$ es más similar a $x_{j}$ que a $x_{k}$ . Para este ejemplo, el negativo del cuadrado de la distancia de dos puntos fue utilizado, es decir, para puntos $x_{i}$ y $x_{k}$ , $s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}$ ^[1]

La diagonal de $s$ (es decir, $s(i,i)$ ) es particularmente importante, ya que representa la preferencia, lo que quiere decir cuan probablemente un dato particular se volverá un ejemplar. Asignando el mismo valor para todas las entradas, se controla cuántas clases produce el algoritmo. Un valor cercano a la mínima similitud posible produce menos clases, mientras que un valor cercano a la máxima similitud posible produce muchas clases. Este valor es típicamente inicializado en la mediana de las similitudes de todos los pares de entradas.

El algoritmo procede alternando entre dos pasos de mensajeo, los cuales actualizan dos matrices:^[1]

La "matriz" de responsabilidad $R$ tiene valores $r(i,k)$ que cuantifican cuán conveniente es que $x_{k}$ sea el ejemplar de $x_{i}$ , relativo a otros candidatos a ejemplar de $x_{i}$ .
La "matriz" de disponibilidad $A$ contiene valores $a(i,k)$ que representan cuan «apropiado» sería para $x_{i}$ elegir a $x_{k}$ como su ejemplar, teniendo en cuenta la preferencia de los otros puntos por $x_{k}$ como ejemplar.

Ambas matrices se inician en ceros, y pueden verse como tablas de probabilidad logarítmica. El algoritmo entonces lleva a cabo iterativamente las siguientes actualizaciones:

Primero, las actualizaciones de responsabilidad se realizan del siguiente modo:

$r(i,k)\leftarrow s(i,k)-\max _{k'\neq k}\left\{a(i,k')+s(i,k')\right\}$

Entonces, las disponibilidades se actualizan del siguiente modo:

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

para

i\neq k

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

Las iteraciones se llevan a cabo hasta que las fronteras de grupo quedan sin cambios por un número de iteraciones, o hasta que se alcanza un número predeterminado (de iteraciones). Los ejemplares se extraen de las matrices finales como aquellos cuya essponsibility + disponibilidad' para sí mismos es un número positivo (i.e. $(r(i,i)+a(i,i))>0$ ).

Aplicaciones

Los inventores de propagación de afinidad demostraron que es mejor para ciertas tareas de visión de ordenador y de biología computaciona, p. ej. clustering de imágenes de caras humanas e identificación de transcritos regulados, que k-medias, incluso cuando a k-medias se le permitieron múltiples reinicios aleatorios y se inicializó utilizando PCA.^[1]^[2] Un estudio que compara propagación de afinidad y Markov clustering en partición de gráficas de interacción de proteínas encontró que Markov clustering funciona mejor para aquel problema.^[3] Una variante semi-supervisada ha sido propuesta para aplicaciones de minería de textos.^[4] Otra aplicación reciente fue en economía, cuándo la propagación de afinidad fue usada para encontrar algunos patrones temporales en los multiplicadores de salida de la economía de EE. UU. entre 1997 y 2017.^[5]

Software

Una implementación en Java se incluye en el framework para minería de datos ELKI.
Una implementación de propagación de afinidad de Julia está contenida en el paquete Julia Statistic's Clustering.jl.
Una versión de Python es parte de la librería scikit-aprender.
Una implementación de R está disponible en el paquete "apcluster».

Referencias

↑ ^a ^b ^c ^d ^e Brendan J. Frey; Delbert Dueck (2007). «Clustering by passing messages between data points». Science 315 (5814): 972-976. PMID 17218491. doi:10.1126/science.1136800.
↑ . Int'l Conf. on Computer Vision. 2007. doi:10.1109/ICCV.2007.4408853.
↑ James Vlasblom; Shoshana Wodak (2009). «Markov clustering versus affinity propagation for the partitioning of protein interaction graphs». BMC Bioinformatics 10 (1): 99. PMC 2682798. PMID 19331680. doi:10.1186/1471-2105-10-99.
↑ Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). «Text Clustering with Seeds Affinity Propagation». IEEE Transactions on Knowledge & Data Engineering 23 (4): 627-637. doi:10.1109/tkde.2010.144.
↑ Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (1 de junio de 2020). «Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy». Structural Change and Economic Dynamics (en inglés) 53: 189-207. ISSN 0954-349X. doi:10.1016/j.strueco.2020.02.006.

Datos: Q3407504

[science-1] Brendan J. Frey; Delbert Dueck (2007). «Clustering by passing messages between data points». Science 315 (5814): 972-976. PMID 17218491. doi:10.1126/science.1136800.

[2] . Int'l Conf. on Computer Vision. 2007. doi:10.1109/ICCV.2007.4408853.

[3] James Vlasblom; Shoshana Wodak (2009). «Markov clustering versus affinity propagation for the partitioning of protein interaction graphs». BMC Bioinformatics 10 (1): 99. PMC 2682798. PMID 19331680. doi:10.1186/1471-2105-10-99.

[4] Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang; Yanchun Liang (2011). «Text Clustering with Seeds Affinity Propagation». IEEE Transactions on Knowledge & Data Engineering 23 (4): 627-637. doi:10.1109/tkde.2010.144.

[5] Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (1 de junio de 2020). «Application of multivariate analysis as complementary instrument in studies about structural changes: An example of the multipliers in the US economy». Structural Change and Economic Dynamics (en inglés) 53: 189-207. ISSN 0954-349X. doi:10.1016/j.strueco.2020.02.006.

[1]

[2]

[3]

[4]

[5]