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

La diagonal de ${\displaystyle s}$ (es decir, ${\displaystyle 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 ${\displaystyle R}$ tiene valores ${\displaystyle r(i,k)}$ que cuantifican cuán conveniente es que ${\displaystyle x_{k}}$ sea el ejemplar de ${\displaystyle x_{i}}$, relativo a otros candidatos a ejemplar de ${\displaystyle x_{i}}$.
• La "matriz" de disponibilidad ${\displaystyle A}$ contiene valores ${\displaystyle a(i,k)}$ que representan cuan «apropiado» sería para ${\displaystyle x_{i}}$ elegir a ${\displaystyle x_{k}}$ como su ejemplar, teniendo en cuenta la preferencia de los otros puntos por ${\displaystyle 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:

${\displaystyle 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:

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

${\displaystyle 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.${\displaystyle (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