motivation：

·手頭有幾個(gè)list，每個(gè)list中有一些對象（string），將一個(gè)list看做一個(gè)節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)（list）之間的“相似度”定義為：兩個(gè)list中包含的對象的重合程度（ (listA∩listB) / (listA∪listB) ）。

·現(xiàn)在基于節(jié)點(diǎn)和節(jié)點(diǎn)之間的相似度，想現(xiàn)有的節(jié)點(diǎn)聚類（相似度更高的節(jié)點(diǎn)聚在一起）

算法簡介：

Affinity Propagation 算法簡稱AP，是2007年發(fā)表在Science上的聚類算法。

Brendan J. Frey and Delbert Dueck, “Clustering by Passing Messages Between Data Points”, Science Feb. 2007

AP算法的基本思想是將全部樣本看做網(wǎng)絡(luò)的節(jié)點(diǎn)，然后通過網(wǎng)絡(luò)中各條邊的消息傳遞計(jì)算出個(gè)樣本的聚類中心。聚類過程中，共有兩種消息在各節(jié)點(diǎn)間傳遞，分別是吸引度（responsibility）和歸屬度（availability）。AP算法通過迭代過程不斷更新每一個(gè)點(diǎn)的吸引度和歸屬度，直到產(chǎn)生m個(gè)高質(zhì)量的Exemplar（相當(dāng)于質(zhì)心），同時(shí)將其余的數(shù)據(jù)點(diǎn)分配到相應(yīng)的聚類中。

? ? 在實(shí)際的使用中，AP有兩個(gè)需要手動設(shè)置的重要參數(shù)，preference和damping factor。前者定了聚類數(shù)量的多少，值越大聚類數(shù)量越多；后者控制算法的收斂效果

AP算法相比于K-means算法，魯棒性強(qiáng)，準(zhǔn)確度較高，但算法復(fù)雜度高，運(yùn)算消耗時(shí)間多

算法使用

sklearn中已經(jīng)實(shí)現(xiàn)了AP算法，可以直接調(diào)用（當(dāng)然，首先需要安裝）。

安裝完成之后，導(dǎo)入AffinityPropagation

from ?sklearn.cluster ?import ?AffinityPropagation

模擬輸入數(shù)據(jù)為一個(gè)矩陣，M(i, j)表示i節(jié)點(diǎn)和j節(jié)點(diǎn)的相關(guān)度

M =?

[[1, 0.8, 0.1, 0.1, 0.1],

[0.8, 1, 0.1, 0.1, 0.1],

[0.1, 0.1, 1, 0.9, 0.1],

[0.1, 0.1, 0.9, 1, 0.1],

[0.1, 0.1, 0.1, 0.1, 1]]

此時(shí)，可以將矩陣M直接輸入

af = AffinityPropagation(affinity='precomputed').fit(X)

label = af.fit_predict(X)

此處

affinity='precomputed'

表示AP算法設(shè)置的參數(shù)，affinity參數(shù)表示節(jié)點(diǎn)之間相似度的計(jì)算方法，'precomputed'表示相似度已經(jīng)計(jì)算完畢，所以輸入的矩陣M是相似度矩陣。當(dāng)設(shè)置為'euclidean'時(shí)，輸入的不是相似度矩陣，而且一個(gè)節(jié)點(diǎn)的list，每個(gè)節(jié)點(diǎn)可以通過多維坐標(biāo)表示（所以是個(gè)二維list）。

輸出的label是一個(gè)lsit：

[1 1 0 0 1]

每一維表示一個(gè)聚類標(biāo)簽，長度n即為之前輸入的矩陣M（n*n）的n。

至此，聚類完成！