AP演算法中兩個參數的交替過程怎麼樣通俗的理解？

最近剛好因為一個討論班在看這個論文，展示的時候沒講清楚，剛好搜到這個問題，在知乎答一個也算是記錄一下自己的想法…（嗯以及為了防止萬一以後有人看到這個答案說我當時是抄襲的- -）

演算法名稱：Affinity Propagation
論文名：Clustering by Passing Messages
Between Data Points
著者：Brendan J. Frey and Delbert Dueck
大體思想：通過在點之間傳遞信息，通過不斷地傳遞信息，最終選出代表元以完成聚類。

大致過程：
文中提到的兩個參數 r(responsibility) 和 a(availability)的更新公式如下：

不斷的交替更新a和r的值，達到一定的次數或收斂後，選取使得 r(i,k)+a(i,k) 最大的那個k作為i的代表元。
其中s(i,k)表示similarity，可以翻譯為相似度或度量，表示k當i的代表元的可能性，s越大越可能，這個在幾乎所有的聚類分析中都是最基礎的量，本答案假定大家能理解這個量。

解釋：

可以用一個比喻來理解這兩個量和其之間交替過程：選舉。

將聚類過程看成選舉：

• 所有人都參加選舉（大家都是選民也都是參選人），要選出幾個作為代表
• s(i,k)就相當於i對選k這個人的一個固有的偏好程度
• r(i,k)表示用s(i,k)減去最強競爭者的評分，可以理解為k在對i這個選民的競爭中的優勢程度
• r(i,k)的更新過程對應選民i的各個參選人的挑選（越出眾越有吸引力）
• a(i,k)：從公式里可以看到，所有r(i",k)&>0的值都對a有正的加成。對應到我們這個比喻中，就相當於選民i通過網上關於k的民意調查看到：有很多人（即i"們）都覺得k不錯（r(i",k)&>0），那麼選民i也就會相應地覺得k不錯，是個可以相信的選擇
• a(i,k)的更新過程對應關於參選人k的民意調查對於選民i的影響（已經有了很多跟隨者的人更有吸引力）
• 兩者交替的過程也就可以理解為選民在各個參選人之間不斷地比較和不斷地參考各個參選人給出的民意調查。
• r(i,k)的思想反映的是競爭，a(i,k)則是為了讓聚類更成功。

整個演算法的思想好像是基於置信傳播（Belief Propagation）和對應的sum-product algorithm，可見wiki上對應詞條和詞條的參考文獻。

看論文的時候感覺算式不多，但看他的結果以及拿程序跑的結果來看還確實蠻有效的…