Affinity Propagation (AP) 聚類是最近在Science雜志上提出的一種新的聚類算法。它根據N個資料點之間的相似度進行聚類,這些相似度可以是對稱的,即兩個資料點互相之間的相似度一樣(如歐氏距離);也可以是不對稱的,即兩個資料點互相之間的相似度不等。這些相似度組成N×N的相似度矩陣S(其中N為有N個資料點)。AP算法不需要事先指定聚類數目,相反它将所有的資料點都作為潛在的聚類中心,稱之為exemplar。以S矩陣的對角線上的數值s(k, k)作為k點能否成為聚類中心的評判标準,這意味着該值越大,這個點成為聚類中心的可能性也就越大,這個值又稱作參考度p (preference)。
在這裡介紹幾個文中常出現的名詞：
exemplar：指的是聚類中心。
similarity：資料點i和點j的相似度記為S(i，j)。是指點j作為點i的聚類中心的相似度。一般使用歐氏距離來計算，如－|| ||。文中，所有點與點的相似度值全部取為負值。因為我們可以看到，相似度值越大說明點與點的距離越近，便于後面的比較計算。
preference：資料點i的參考度稱為P(i)或S(i,i)。是指點i作為聚類中心的參考度。一般取S相似度值的中值。
Responsibility:R(i,k)用來描述點k适合作為資料點i的聚類中心的程度。
Availability:A(i,k)用來描述點i選擇點k作為其聚類中心的适合程度。
下圖是兩者之間的關系：
下面是R與A的計算公式：
計算之前， Availability初始化為0，即A(i,k)=0 文章中的damping factor為設定的阻尼系數，使算法達到收斂，其中lam的範圍是[0.5,1.0)公式如下：
AP算法的具體工作過程如下：先計算N個點之間的相似度值，将值放在S矩陣中，再選取P值(一般取S的中值)。設定一個最大疊代次數(文中設預設值為1000)，疊代過程開始後，計算每一次的R值和A值，根據R(k,k)+A(k,k)值來判斷是否為聚類中心(文中指定當(R(k,k)+A(k,k))＞0時認為是一個聚類中心)，當疊代次數超過最大值( 即maxits值)或者當聚類中心連續多少次疊代不發生改變( 即convits值)時終止計算(文中設定連續50次疊代過程不發生改變是終止計算)。 主程式代碼如下：
//設定疊代次數和收斂域，後者表示當聚類中心不再變化的次數達到coverageIteration算法結束
int maxIteration = 0, coverageIteration = 0;
/*這裡的allTestSampleMap是我的三百多篇文檔形成的文本向量，此算法用來進行文本聚類，實驗結果表明樣本個數較少的情況下，參數合适能
獲得很好的效果*/
int tsLength = allTestSampleMap.size();
// A值和R值
double[][] responsibility = new double[tsLength][tsLength];
double[][] availability = new double[tsLength][tsLength];
//A值初始化為0
for (int i = 0; i < tsLength; i++) {
for (int k = 0; k < tsLength; k++) {
responsibility[i][k] = 0;
availability[i][k] = 0;
}
}
//上一次循環計算的A值和R值
double[][] oldResponsibility = new double[tsLength][tsLength];
double[][] oldAvailability = new double[tsLength][tsLength];
//進行聚類，不斷疊代直到到達預設的疊代次數或者聚類中心始終不再變化，newMarker和oldMarker分别存放新舊聚類中心
ArrayList<Integer> newMarker = new ArrayList<Integer>();
ArrayList<Integer> oldMarker = new ArrayList<Integer>();
while (true) {
for (int i = 0; i < tsLength; i++) {
for (int k = 0; k < tsLength; k++) {
oldResponsibility[i][k] = responsibility[i][k];
double max1 = 0;
for (int j = 0; j < tsLength; j++) {
if (j != k) {
if (availability[i][j] + sim[i][j] > max1) {
max1 = availability[i][j] + sim[i][j];
}
}
}
responsibility[i][k] = sim[i][k] - max1;
// System.out.println(i +"和"+k+": "+responsibility[i][k]);
responsibility[i][k] = (1 - dampingFactor)
* responsibility[i][k] + dampingFactor
* oldResponsibility[i][k];
}
}
for (int i = 0; i < tsLength; i++) {
for (int k = 0; k < tsLength; k++) {
oldAvailability[i][k] = availability[i][k];
if (i == k) {
double max2 = 0;
for (int j = 0; j < tsLength; j++) {
if (j != k) {
if (responsibility[j][k] > 0) {
max2 += responsibility[j][k];
} else {
max2 += 0;
}
}
}
availability[i][k] = max2;
} else {
double max3 = 0;
for (int j = 0; j < tsLength; j++) {
if (j != k && j != i) {
if (responsibility[j][k] > 0) {
max3 += responsibility[j][k];
} else {
max3 += 0;
}
}
}
if (responsibility[k][k] + max3 > 0) {
availability[i][k] = 0;
} else {
availability[i][k] = responsibility[k][k] + max3;
}
}
// System.out.println(i +"和"+k+": "+availability[i][k]);
availability[i][k] = (1 - dampingFactor)
* availability[i][k] + dampingFactor
* oldAvailability[i][k];
}
}
//exemplar表示聚類中心
for (int k = 0; k < tsLength; k++) {
if (responsibility[k][k] + availability[k][k] > 0.0) {
exemplar.put(k,allTestSampleMap.get(testSampleNames[k]));
newMarker.add(k);
}
}
Set<Integer> setA = new HashSet<Integer>(newMarker);
Set<Integer> setB = new HashSet<Integer>(oldMarker);
if (!setA.isEmpty() && !setB.isEmpty() && setA.equals(setB)) {
coverageIteration++;
} else {
coverageIteration = 0;
}
oldMarker.clear();
if (maxIteration > 1000 || coverageIteration > 50) {
break;
} else {
maxIteration++;
for (int j = 0; j < newMarker.size(); j++) {
oldMarker.add(newMarker.get(j));
}
newMarker.clear();
exemplar.clear();
}
}
程式代碼 連結: https://pan.baidu.com/s/1gf22w0r 密碼: 7gp5