機器學習：Python實現聚類演算法之AP演算法

1.演算法簡介

AP(Affinity Propagation)通常被翻譯為近鄰傳播演算法或者親和力傳播演算法，是在2007年的Science雜誌上提出的一種新的聚類演算法。AP演算法的基本思想是將全部數據點都當作潛在的聚類中心(稱之為exemplar)，然後數據點兩兩之間連線構成一個網路(相似度矩陣)，再通過網路中各條邊的消息(responsibility和availability)傳遞計算出各樣本的聚類中心。

2.相關概念(假如有數據點i和數據點j)

（圖1） （圖2） （圖3）

1）相似度：點j作為點i的聚類中心的能力，記為S(i,j)。一般使用負的歐式距離，所以S(i,j)越大，表示兩個點距離越近，相似度也就越高。使用負的歐式距離，相似度是對稱的，如果採用其他演算法，相似度可能就不是對稱的。

2）相似度矩陣：N個點之間兩兩計算相似度，這些相似度就組成了相似度矩陣。如圖1所示的黃色區域，就是一個5*5的相似度矩陣(N=5)

3) preference：指點i作為聚類中心的參考度(不能為0)，取值為S對角線的值(圖1紅色標註部分)，此值越大，最為聚類中心的可能性就越大。但是對角線的值為0，所以需要重新設置對角線的值，既可以根據實際情況設置不同的值，也可以設置成同一值。一般設置為S相似度值的中值。(有的說設置成S的最小值產生的聚類最少，但是在下面的演算法中設置成中值產生的聚類是最少的)

4）Responsibility(吸引度):指點k適合作為數據點i的聚類中心的程度，記為r(i,k)。如圖2紅色箭頭所示，表示點i給點k發送信息，是一個點i選點k的過程。

5）Availability(歸屬度):指點i選擇點k作為其聚類中心的適合程度，記為a(i,k)。如圖3紅色箭頭所示，表示點k給點i發送信息，是一個點k選diani的過程。

6）exemplar：指的是聚類中心。

7）r (i, k)加a (i, k)越大,則k點作為聚類中心的可能性就越大,並且i點隸屬於以k點為聚類中心的聚類的可能性也越大

3.數學公式

1）吸引度迭代公式:

（公式一）說明1：Rt+1(i,k)表示新的R(i,k)，R(i,k)表示舊的R(i,k)，也許這樣說更容易理解。其中λ是阻尼係數，取值[0.5,1)，用於演算法的收斂

說明2：網上還有另外一種數學公式：

（公式二） （公式三）

我試了這兩種公式之後，發現還是公式一的聚類效果最好。同樣的數據都採取S的中值作為參考度，我自己寫的演算法聚類中心是5個，sklearn提供的演算法聚類中心是十三個，但是如果把參考度設置為p=-50，則我自己寫的演算法聚類中心很多，sklearn提供的聚類演算法產生標準的3個聚類中心(因為數據是圍繞三個中心點產生的)，目前還不清楚這個p=-50是怎麼得到的。

2）歸屬度迭代公式

說明：At+1(i,k)表示新的A(i,k)，A(i,k)表示舊的A(i,k)。其中λ是阻尼係數，取值[0.5,1)，用於演算法的收斂

4.詳細的演算法流程

1）設置實驗數據。使用sklearn包中提供的函數，隨機生成以[1, 1], [-1, -1], [1, -1]三個點為中心的150個數據。

2）計算相似度矩陣，並且設置參考度，這裡使用相似度矩陣的中值

3）計算吸引度矩陣，即R值。

如果有細心的同學會發現，在上述求R和求A的公式中，求R需要A，求A需要R，所以R或者A不是一開始就可以求解出的，需要先初始化，然後再更新。(我開始就陷入了這個誤區，總覺得公式有問題，囧)

4）計算歸屬度矩陣，即A值

5）迭代更新R值和A值。終止條件是聚類中心在一定程度上不再更新或者達到最大迭代次數

6）根據求出的聚類中心，對數據進行分類

這個步驟產生的是一個歸類列表，列表中的每個數字對應著樣本數據中對應位置的數據的分類

7）完整代碼及效果圖

迭代11次出結果：

補充說明：這個演算法重點在講解實現過程，執行效率不是特別高，有優化的空間。以後我會補充進來

5.sklearn包中的AP演算法

1）函數：sklearn.cluster.AffinityPropagation

2）主要參數：

damping :阻尼係數，取值[0.5,1)

convergence_iter ：比較多少次聚類中心不變之後停止迭代，默認15

max_iter ：最大迭代次數

preference :參考度

3）主要屬性

cluster_centers_indices_ :存放聚類中心的數組

labels_ :存放每個點的分類的數組

n_iter_ :迭代次數

4）示例

preference(即p值)取不同值時的聚類中心的數目在代碼中註明了。

6.AP演算法的優點

1）不需要制定最終聚類族的個數

2）已有的數據點作為最終的聚類中心，而不是新生成一個族中心。

3）模型對數據的初始值不敏感。

4）對初始相似度矩陣數據的對稱性沒有要求。

5）.相比與k-centers聚類方法，其結果的平方差誤差較小。

7.AP演算法的不足

1）AP演算法需要事先計算每對數據對象之間的相似度，如果數據對象太多的話，內存放不下，若存在資料庫，頻繁訪問資料庫也需要時間。

2）AP演算法的時間複雜度較高，一次迭代大概O(N

3）聚類的好壞受到參考度和阻尼係數的影響。