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