Affinity Propagation算法簡介
AP(Affinity Propagation)通常被翻譯為近鄰傳播算法或者親和力傳播算法。AP算法的基本思想是將全部數據點都當作潛在的聚類中心(稱之為exemplar)，然後數據點兩兩之間連線構成一個網絡(相似度矩陣)，再通過網絡中各條邊的消息(responsibility和availability)傳遞計算出各樣本的聚類中心。
AP算法中的特殊名詞：
- Exemplar：指的是聚類中心，K-Means中的質心。
- Similarity（相似度）：點j作為點i的聚類中心的能力，記為S(i,j)。一般使用負的歐式距離，所以S(i,j)越大，表示兩個點距離越近，相似度也就越高。使用負的歐式距離，相似度是對稱的，如果採用其他算法，相似度可能就不是對稱的。
- Preference：指點i作為聚類中心的參考度(不能為0)，取值為S對角線的值(圖1紅色標註部分)，此值越大，最為聚類中心的可能性就越大。但是對角線的值為0，所以需要重新設置對角線的值，既可以根據實際情況設置不同的值，也可以設置成同一值。一般設置為S相似度值的中值。
- Responsibility（吸引度）：指點k適合作為數據點i的聚類中心的程度，記為r(i,k)。如圖2紅色箭頭所示，表示點i給點k發送信息，是一個點i選點k的過程。
- Availability(歸屬度)：指點i選擇點k作為其聚類中心的適合程度，記為a(i,k)。如圖3紅色箭頭所示，表示點k給點i發送信息，是一個點k選點i的過程。
- Damping factor(阻尼係數)：主要是起收斂作用的。
在實際計算應用中，最重要的兩個參數（也是需要手動指定）是Preference和Damping factor。前者定了聚類數量的多少，值越大聚類數量越多；後者控制算法收斂效果。
AP算法流程：
- 步驟1：算法初始，將吸引度矩陣R和歸屬度矩陣初始化為0矩陣；
- 步驟2：更新吸引度矩陣
rt+1(i,k)={S(i,k)−maxj≠k{at(i,j)+rt(i,j)},i≠kS(i,k)−maxj≠k{S(i,j)},i=krt+1(i,k)={S(i,k)−maxj≠k{at(i,j)+rt(i,j)},i≠kS(i,k)−maxj≠k{S(i,j)},i=k
- 步驟3：更新歸屬度矩陣步驟4：根據衰減係數 對兩個公式進行衰減
at+1(i,k)={min{0,rt+1(k,k)+∑j≠i,kmax{rt+1(j,k),0}},i≠k∑j≠kmax{rt+1(j,k),0},i=kat+1(i,k)={min{0,rt+1(k,k)+∑j≠i,kmax{rt+1(j,k),0}},i≠k∑j≠kmax{rt+1(j,k),0},i=k
- 步驟4：根據衰減係數λλ對兩個公式進行衰減
rt+1(i,k)=λ∗rt(i,k)+(1−λ)∗rt+1(i,k)at+1(i,k)=λ∗at(i,k)+(1−λ)∗at+1(i,k)rt+1(i,k)=λ∗rt(i,k)+(1−λ)∗rt+1(i,k)at+1(i,k)=λ∗at(i,k)+(1−λ)∗at+1(i,k)
- 重複步驟2，3,4直至矩陣穩定或者達到最大迭代次數，算法結束。
- 最終取a+r最大的k作為聚類中心。
Python下AP算法使用
Python的機器學習庫sklearn中已經實現了AP算法，可以直接調用。
<code>class sklearn.cluster.AffinityPropagation(damping=0.5, max_iter=200, convergence_iter=15, copy=True, preference=None, affinity='euclidean', verbose=False)
/<code>
參數設置介紹：
- damping : 衰減係數，默認為5
- convergence_iter : 迭代次後聚類中心沒有變化，算法結束，默認為
- max_iter : 最大迭代次數，默認
- copy : 是否在元數據上進行計算，默認True，在複製後的數據上進行計算。
- preference : S的對角線上的值
- affinity :S矩陣（相似度），默認為euclidean（歐氏距離）矩陣，即對傳入的X計算距離矩陣，也可以設置為precomputed，那麼X就作為相似度矩陣。
訓練完AP聚類之後可以獲得的結果有
- cluster_centers_indices_ : 聚類中心的位置
- cluster_centers_ : 聚類中心
- labels_ : 類標籤
- affinity_matrix_ : 最後輸出的A矩陣
- n_iter_ ：迭代次數
AP（Affinity Propagation）算法演示：
<code>from sklearn.cluster import AffinityPropagation
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
import numpy as np
# 生成測試數據
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=0)
# AP模型擬合
af = AffinityPropagation(preference=-50).fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_
new_X = np.column_stack((X, labels))
n_clusters_ = len(cluster_centers_indices)
print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
% metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
% metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
% metrics.silhouette_score(X, labels, metric='sqeuclidean'))
print('Top 10 sapmles:', new_X[:10])
# 圖形展示
import matplotlib.pyplot as plt
from itertools import cycle
plt.close('all')
plt.figure(1)
plt.clf()
colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
for k, col in zip(range(n_clusters_), colors):
class_members = labels == k
cluster_center = X[cluster_centers_indices[k]]
plt.plot(X[class_members, 0], X[class_members, 1], col + '.')
plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=14)
for x in X[class_members]:
plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()
/<code>
AP與K-Means對比
AP聚類算法與經典的K-Means聚類算法相比，具有很多獨特之處：
- 無需指定聚類“數量”參數。AP聚類不需要指定K（經典的K-Means）或者是其他描述聚類個數（SOM中的網絡結構和規模）的參數，這使得先驗經驗成為應用的非必需條件，人群應用範圍增加。
- 明確的質心（聚類中心點）。樣本中的所有數據點都可能成為AP算法中的質心，叫做Examplar，而不是由多個數據點求平均而得到的聚類中心（如K-Means）。
- 對距離矩陣的對稱性沒要求。AP通過輸入相似度矩陣來啟動算法，因此允許數據呈非對稱，數據適用範圍非常大。
- 初始值不敏感。多次執行AP聚類算法，得到的結果是完全一樣的，即不需要進行隨機選取初值步驟（還是對比K-Means的隨機初始值）。
- 算法複雜度較高，為O(N*N*logN)，而K-Means只是O(N*K)的複雜度。因此當N比較大時(N>3000)，AP聚類算法往往需要算很久。
- 若以誤差平方和來衡量算法間的優劣，AP聚類比其他方法的誤差平方和都要低。（無論k-center clustering重複多少次，都達不到AP那麼低的誤差平方和）
AP算法相對K-Means魯棒性強且準確度較高，但沒有任何一個算法是完美的，AP聚類算法的主要缺點：
- AP聚類應用中需要手動指定Preference和Damping factor，這其實是原有的聚類“數量”控制的變體。
- 算法較慢。由於AP算法複雜度較高，運行時間相對K-Means長，這會使得尤其在海量數據下運行時耗費的時間很多。
AP和K-Means運行時間對比
<code>import numpy as np
import matplotlib.pyplot as plt
import time
from sklearn.cluster import KMeans, AffinityPropagation
from sklearn.datasets.samples_generator import make_blobs
# 生成測試數據
np.random.seed(0)
centers = [[1, 1], [-1, -1], [1, -1]]
kmeans_time = []
ap_time = []
for n in [100, 500, 1000]:
X, labels_true = make_blobs(n_samples=n, centers=centers, cluster_std=0.7)
# 計算K-Means算法時間
k_means = KMeans(init='k-means++', n_clusters=3, n_init=10)
t0 = time.time()
k_means.fit(X)
kmeans_time.append([n, (time.time() - t0)])
# 計算AP算法時間
ap = AffinityPropagation()
t0 = time.time()
ap.fit(X)
ap_time.append([n, (time.time() - t0)])
print('K-Means time', kmeans_time[:10])
print('AP time', ap_time[:10])
# 圖形展示
km_mat = np.array(kmeans_time)
ap_mat = np.array(ap_time)
plt.figure()
plt.bar(np.arange(3), km_mat[:, 1], width=0.3, color='b', label='K-Means', log='True')
plt.bar(np.arange(3) + 0.3, ap_mat[:, 1], width=0.3, color='g', label='AffinityPropagation', log='True')
plt.xlabel('Sample Number')
plt.ylabel('Computing time')
plt.title('K-Means and AffinityPropagation computing time ')
plt.legend(loc='upper center')
plt.show()
/<code>
圖中為了更好的展示數據對比，已經對時間進行log處理，但可以從輸出結果直接讀取真實數據運算時間。由結果可以看到：當樣本量為100時，AP的速度要大於K_Means；當數據增加到500甚至1000時，AP算法的運算時間要大大超過K-Means算法。
分享到:
閱讀更多 sandag 的文章
