Clustering method 5
Affinity Propagation
這次要介紹的鄰近傳播分群法（Affinity Propagation）分群方法與最常使用的K-means是基於一樣的 Similarity matrix，也就是以定義的距離來作分群，但此種方法加入了數據間傳遞信息的想法，因此計算複雜度也較高，但能得到較好的平方誤差。常使用在生物基因的分群、文句的提取等等。
以下將會介紹鄰近傳播分群法的基本概念以及會使用到的名詞解釋，依舊以相同例子的結果來比較各種分群法的差異。
－ 基本概念 －
鄰近傳播分群法（Affinity Propagation）是一種基於資料點間信息傳遞的分群算法。依據點間的相似度（Similarity）傳遞所需的消息，進而計算出各點的分群中心。過程中所傳遞的信息分別是吸引度（Responsibility）和歸屬度（Availability）。透過不斷更新此兩種訊息，產生較好的分群中心（Exemplar）得以將資料及分群。
- 相似度（Similarity）
資料點間的相似度一般以點間的距離來計算，距離越近則表示相似度越高，意即
同時相似度也表明 x_j 作為 x_i 的分群中心的適合程度（因為相似度越高，越容易分為同一群）。
- 參考度（Preference）
指的是資料點作為分群中心的參考度，也就是可作為分群中心的適合程度。一般取相似度的中間值作為參考度並取代相似度矩陣的對角值。
因此可以解釋相似度矩陣的元素 S(i, j) 指的是 x_i 選定 x_j 為分群中心的偏好程度。
- 吸引度（Responsibility）
若以 R(i, k) 來表示吸引度，稱資料點 x_k 吸引資料點 x_i 作為分群中心的程度。
- 歸屬度（Availability）
若以 A(i, k) 來表示歸屬度，稱資料點 x_i 選擇資料點 x_k 作為分群中心的適合程度。
因此吸引度及歸屬度對於給定資料點與某欲作為分群中心的資料點間的關係為：
此算法即是不斷更新吸引度以及歸屬度來找到對每個資料點最適合的分群中心。迭代更新的過程如下：
1. x_k 若要吸引 x_i 做為它的分群中心，必須要跟 x_i 有足夠高的相似程度（S(i, k)），並且證明比其他點更適合作為分群的中心，也就是 x_i 認可其他點 x_k' 的程度（A(i, k)）以及 x_k' 作為 x_i 的分群中心的合適度（S(i, k’)）要比對 x_k 的來得低。因此更新吸引度 R(i, k) 的方式為
2. 若 x_k 吸引x_i以外的資料點，x_i 也容易選擇 x_k 作為其分群中心。因此 x_k 對其他點 x_i' 的吸引度（R(i’, k)）表示它成為其他點 x_i' 的分群中心有多適合。R(k, k) 則表示 x_k 自己不適合其他點的程度。最後綜合兩種考慮的想法則能表示歸屬度 A(i, k) 為
可以想像吸引度（Responsibility）是比較分群中心的適合程度，則歸屬度（Availability）是找出較適合成為分群中心的資料點。
－ 演算法 －
輸入：資料集 D，參考度 preference。
輸出：目標分群集合 Clusters
- 根據資料集 D 計算相似度矩陣 S，將 S 對角線上的元素設為給定的參考度 preference，即是 S(i, i) = preference 。
- 初始化吸引度 R 以及歸屬度 A 為 0 矩陣。
- 更新個資料點間的吸引度。
- 更新個資料點間的歸屬度。
- 對資料點 d_i 來說，分群中心 Exemplar 即為 argmax{A(i, k)+R(i, k)} 。
- 重複步驟 3. 4. 5. 直到所有資料點所屬的分群中心不再改變為止。
－ 算法實作 －
使用Sklearn.cluster.AffinityPropagation套件：
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AffinityPropagation
from sklearn import datasets
from sklearn.metrics import pairwise_distances#create datasets
X,y = datasets.make_blobs(n_samples=50, centers=3, n_features=2, random_state= 20, cluster_std = 1.5)#parameter setting
S = -np.square(pairwise_distances(X)) #Affinity matrix
prefer = np.mean(S) #set preference value#Affinity Propagation method
model = AffinityPropagation(preference = prefer)
model.fit(X)
labels = model.fit_predict(X)
cluster_center = model.cluster_centers_#results visualization
plt.figure()
plt.scatter(X[:,0], X[:,1], c = labels)
plt.scatter(cluster_center[:,0], cluster_center[:,1], c = 'r')
plt.axis('equal')
plt.title('Prediction')plt.show()
用於影像分割 …
import numpy as np
import matplotlib.pyplot as plt
from skimage.transform import rescale
from sklearn.cluster import AffinityPropagation
import cv2
from sklearn.metrics import pairwise_distances#load image
img = cv2.imread('AIA.png')
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
img = rescale(img, 0.2)
rows, cols, chs= img.shape#convert image shape [rows, cols, 3] into [rows*cols, 3]
feature_img = np.reshape(img, [-1, 3])#consider the data without density-dependent factor
uni_feature_img, idx = np.unique(feature_img, axis=0, return_inverse = True)#parameters setting
S = -np.square(pairwise_distances(uni_feature_img)) #Affinity matrix
prefer = np.mean(S) #set preference value#Affinity Propagation method
model = AffinityPropagation(preference = prefer)
model.fit(uni_feature_img)
labels = model.labels_#results visualization
fig = plt.figure(figsize = (20, 12))
ax = fig.add_subplot(121)
ax1 = fig.add_subplot(122)
ax.imshow(img)
ax1.imshow(np.reshape(labels[idx], [rows, cols]))plt.show()
－ Affinity Propagation 算法總結－
優點：
- 不需要給定分群的個數，且最終的分群中心為原有的資料點。
- 此方法較不依賴初始值的選定
缺點：
- 此算法雖不須給定分群中心的個數，但所需的參考度（preference）即與分群中心個數有正相關的關係。
- 每次迭代都需要更新資料點吸引度（ Responsibility）和歸屬度（ Availability），因此計算複雜度較高。
－ 參考資料 －
- 原始論文： Dueck, Delbert, and Brendan J. Frey. “Non-metric affinity propagation for unsupervised image categorization.” 2007 IEEE 11th International Conference on Computer Vision. IEEE, 2007.
- Affinity Propagation 維基百科：https://en.wikipedia.org/wiki/Affinity_propagation
- sklearn.cluster.AffinityPropagation套件：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AffinityPropagation.html
