1 算法原理

1.1 基本思想

• 將全部數據點都當作潛在的聚類中心(稱之為 exemplar )
• 然后數據點兩兩之間連線構成一個網絡( 相似度矩陣 )
• 再通過網絡中各條邊的消息( responsibility 和 availability )傳遞計算出各樣本的聚類中心。

1.2 主要概念

Examplar	聚類中心
similarity? S(i,j)	相似度 一般使用負的歐式距離，所以 S(i,j) 越大，表示兩個點距離越近，相似度也就越高
Preference	點 i 作為聚類中心的參考度(不能為0)，取值為 S相似度 對角線的值 此值越大，則為聚類中心的可能性就越大。 如果沒有被設置，則一般設置為 S相似度 值的中值
Responsibility? 吸引度	點?k?適合作為數據點?i?的聚類中心的程度，記為?r(i,k)?。
Availability 歸屬度	點?i?選擇點?k?作為其聚類中心的適合程度，記為?a(i,k) r和a都是第二個參數的點作為聚類中心
Damping factor 阻尼系數	主要是起收斂作用

1.3 算法流程

• 計算相似度矩陣
  • 此時對角線上的值都是0，用某種方法（固定參數/相似度矩陣的中位值/最小值等）填充對角線的值
• 開始時：構造一個全0的歸屬度矩陣a
• 以下不斷迭代更新
  • 更新每一個吸引度矩陣r中的單元格值
    • 
  • 更新歸屬度矩陣a
    • 
    • 
  • 使用阻尼系數更新歸屬度a和吸引度r
    • 使用阻尼系數(damping factor)來衰減吸引度和歸屬度信息，以免在更新的過程中出現數值振蕩
    • 
    • 上面三個公式算出來的是等號右邊的a和r
• 獲取聚類中心
  • 

1.4 舉例

• 假設有如下樣本：共5個維度
  • 
• 計算相似度矩陣
  • 相似度矩陣中每個單元是用兩個樣本對應值的差的平方和取負值得到的，對角線上的除外
  • 
  • 當聚類中心為對角線上的單元格選擇了比較小的值，那么AP算法會快速收斂并得到少量的聚類中心，反之亦然。因此。我們使用表格中最小的值?-22?去填充相似度矩陣中的?0?對角線單元格。
    • 
• 計算吸引度矩陣r
  • 
  • eg：計算 Bob對 Alice的 吸引度（Responsibility）【Alice視Bob為聚類中心的程度，r(Alice,Bob)
    • 這里套用上面的公式即為：用S(Bob,Alice)- max(a(Alice,others)+s(Alice,others))
      • 即 -7-(-6)=-1
    • 
• 計算歸屬度矩陣a
  • 
    • 以alice為例,a(Alice,Alice)就是 所有大于0的 r(others,Alice)的和，即10+11=21
  • 
    • 以Alice支持Bob作為其聚類中心為例
    • a(Alice,Bob)=min(0,r(Bob,Bob)+0)=-15 【沒有r(others,Bob)大于0】
    • 
• 假設迭代一次就結束，那么我們計算評估矩陣
  • c=r+a
  • 
  • 一般將評估矩陣中取得最大值的一些點作為聚類中心
    • Alice，Bob 和 Cary?共同組成一個聚類簇
    • Doug 和 Edna?則組成了第二個聚類

1.5 主要缺點

• Affinity Propagation的主要缺點是其復雜性。該算法的時間復雜度為，其中 N 是樣本數量，I 是直到收斂的迭代次數
• 如果使用密集的相似性矩陣，則內存復雜度為 ，但如果使用稀疏的相似性矩陣則可以降低。
• 這使得Affinity Propagation最適合小到中等大小的數據集

2 sklearn實現

class sklearn.cluster.AffinityPropagation(*, damping=0.5, max_iter=200, convergence_iter=15, copy=True, preference=None, affinity='euclidean', verbose=False, random_state=None)

2.1 主要參數

damping	float，默認為0.5 阻尼因子，取值范圍是[0.5, 1.0)
max_iter	int，默認為200 最大迭代次數
convergence_iter	int，默認為15 估計的簇數量沒有變化的迭代次數，達到該次數則停止收斂
preference	array-like形狀為(n_samples,)或浮點數，默認為None 每個點的偏好 - 具有較大偏好值的點更有可能被選擇為典型樣本 如果沒有傳遞偏好作為參數，它們將被設置為輸入相似度的中值。
affinity	{‘euclidean’, ‘precomputed’}，默認為‘euclidean’ 使用哪種親和力。目前支持‘precomputed’和歐幾里得。‘euclidean’使用點之間的負平方歐幾里得距離。

2.2 主要屬性

from sklearn.cluster import AffinityPropagation
import numpy as npX = np.array([[1, 2], [1, 4], [1, 0],[10, 2], [10, 4], [10, 0]])ap=AffinityPropagation(damping=0.8).fit(X)

cluster_centers_indices_	簇中心的索引
cluster_centers_	簇中心
labels_	每個點的標簽
affinity_matrix_	親和力矩陣
n_iter_	收斂所需的迭代次數

?

參考內容：AP聚類算法(Affinity propagation) - 知乎 (zhihu.com)

常見聚類算法及使用--Affinity Propagation（AP）_af nity propagation 是什么意思-CSDN博客