En estadística i mineria de senyes, propagació d'afinitat (AP) és un algoritme de clusterisació basat en el concepte de «mensajeo» entre punts de senyes.[1] A diferència d'algoritmes de clusterisació com a k-miges o k-medoides, propagació d'afinitat no requerix que el número de grups estiguen determinats o estimats abans de córrer l'algoritme. De la mateixa manera que k-medoides, propagació d'afinitat troba «eixemplars» membres del conjunt d'entrada que són representants dels grups.[1]

Algoritme

Sean x1,..,xn punts d'un conjunt de senyes, sense suposicions fetes sobre la seua estructura interna, i siga s una funció que quantifica la similitut entre qualssevol dos punts, tal que s(i,j)>s(i,k) sii xi és més similar a xj que a xk. Per a este eixemple, el negatiu del quadrat de la distància de dos punts va ser utilisat, és dir, per a punts xi i xk, s(i,k)=−‖xi−xk‖2[1]

La diagonal de s (és dir, s(i,i)) és particularment important, ya que representa la preferència, lo que vol dir cuan provablement una senya particular es tornarà un eixemplar. Assignant el mateix valor per a totes les entrades, es controla quàntes classes produïx l'algoritme. Un valor propenc a la mínima similitut possible produïx menys classes, mentres que un valor propenc a la màxima similitut possible produïx moltes classes. Este valor és típicament inicializado en la mijana de les similituts de tots els parells d'entrades.

L'algoritme procedix alternant entre dos passos de mensajeo, els quals actualisen dos matrius:[1]

  • La "matriu" de responsabilitat R té valors r(i,k) que quantifiquen cuán convenient és que xk siga l'eixemplar de xi, relatiu a atres candidats a eixemplar de xi.
  • La "matriu" de disponibilitat A conté valors a(i,k) que representen cuan «apropiat» seria per a xi elegir a xk com el seu eixemplar, tenint en conte la preferència dels atres punts per xk com a eixemplar.

Abdós matrius s'inicien en zeros, i poden vore's com a taules de provabilitat logarítmica. L'algoritme llavors porta a terme iterativamente les següents actualisacions:

  • Primer, les actualisacions de responsabilitat es realisen del següent modo:

r(i,k)←s(i,k)−maxk′≠k{a(i,k′)+s(i,k′)}

  • Llavors, les disponibilitat s'actualisen del següent modo:
a(i,k)←min⁡(0,r(k,k)+∑i′∉{i,k}max⁡(0,r(i′,k))) per a i≠k
a(k,k)←∑i′≠kmax⁡(0,r(i′,k))

Les iteraciones es porten a terme fins que les fronteres de grup queden sense canvis per un número de iteraciones, o fins que s'alcança un número predeterminat (de iteraciones). Els eixemplars s'extrauen de les matrius finals com aquells que la seua essponsibility + disponibilitat' per a sí mateixos és un número positiu (i.i.(r(i,i)+a(i,i))>0).

Aplicacions

Els inventors de propagació d'afinitat varen demostrar que és millor per a certes tasques de visió d'ordenador i de biologia computaciona, p. eix. clustering d'imàgens de cares humanes i identificació de transcritos regulats, que k-miges, inclús quan a k-miges se li varen permetre múltiples reinicis aleatoris i es inicializó utilisant PCA.[1] Un estudi que compara propagació d'afinitat i Markov clustering en partició de gràfiques d'interacció de proteïnes va trobar que Markov clustering funciona millor per a aquell problema.[2] Una variant semi-supervisada ha segut proposta per a aplicacions de mineria de texts.[3] Una atra aplicació recent va ser en economia, quàn la propagació d'afinitat va ser usada per a trobar alguns patrons temporals en els multiplicadors d'eixida de l'economia de EE. UU. entre 1997 i 2017.[4]

Referències

  1. ↑ 1,0 1,1 1,2 1,3 1,4 Brendan J. Frey; Delbert Dueck(2007).«Clustering by passing messages between data points».Science.315(5814): 972–976.doi:10.1126/science.1136800.
  2. ↑ James Vlasblom; Shoshana Wodak(2009).«Markov clustering versus affinity propagation for the partitioning of protein interaction graphs».BMC Bioinformatics.10(1): 99.doi:10.1186/1471-2105-10-99.
  3. ↑ Renchu Guan; Xiaohu Shi; Maurizio Marchese; Chen Yang(2011).«Text Clustering with Seeds Affinity Propagation».IEEE Transactions on Knowledge & Data Engineering.23(4): 627–637.doi:10.1109/tkde.2010.144.
  4. ↑ Almeida, Lucas Milanez de Llima; Balanco, Paulo Antonio de Freitas(2020-06-01).«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.53: 189–207.ISSN 0954-349X.doi:10.1016/j.strueco.2020.02.006.(en en)

 


Referències