propagación de la afinidad

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

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 negativa de dos puntos de datos, es decir, para los puntos x _i y x _k ,${\displaystyle s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}}$. ^{[ 1 ]}

La diagonal de s (es decir,${\displaystyle s(i,i)}$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 con 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. Normalmente se inicializa con la similitud mediana de todos los pares de entradas.

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 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 ejemplar, teniendo en cuenta la preferencia de otros puntos por x _k como ejemplar.

Ambas matrices se inicializan con ceros y pueden considerarse 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 responsabilidades:${\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$${\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{ para }}i\neq k}$$y$${\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 permanezcan sin cambios durante un número determinado de iteraciones, o se alcance 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}$).

Los inventores de la propagación de 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 a k -means se le permitieron muchos reinicios aleatorios y se inicializó usando PCA . ^{[ 2 ]} Un estudio que comparó la propagación de afinidad y la agrupación de Markov en la partición de grafos 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 la propagación de afinidad se usó para encontrar algunos patrones temporales en los multiplicadores de producción de la economía estadounidense entre 1997 y 2017. ^{[ 5 ]}

• El marco de minería de datos ELKI incluye una implementación en Java .
• Una implementación en Julia de la propagación de afinidad se encuentra en el paquete Clustering.jl de Julia Statistics.
• La biblioteca scikit-learn incluye una versión en Python .
• Existe una implementación en R disponible en el paquete "apcluster".