AP(Affinity Propagation)算法,称为仿射传播聚类算法、近邻传播聚类算法、亲和传播聚类算法,是根据数据点之间的相似度来进行聚类,可以是对称的,也可以是不对称的。

特征的处理与提取用于构建功率数据特征集以识别负荷的特征,作为数据挖掘过程的聚类算法,其提取出的数据特征向量应全面地反映出数据样本的本质特征,同时对于负荷数据特征集中的样本特征应具有足够的置信度,提取出的样本作为匹配模板是不应该有波动的,对于负荷而言,通过算法得到样本特征过程中不应有过多的人为主观因素干扰。因此需要选择一个足够合适的算法以满足我们的需求,这种聚类算法需要具有客观选取参数,能够自动确定聚类数目,对数据样本的输入顺序不敏感以及尽可能避免陷入局部最优解等特点。因此,使用AP聚类代替了最流行的K-means聚类技术,因为传统的K-means聚类有着对初始聚类中心选择较为敏感的局限性。

AP聚类算法

AP聚类算法是由B J Frey和D D ueck于2007年提出的一种新的聚类算法,此算法并不需要人工定义类数,主要根据输入样本点之间的相似度进行聚类处理。

样本点i和点j的相似度记为s(i, j),是指点j作为点i的聚类中心的相似度。一般使用欧氏距离来计算,一般点与点的相似度值全部取为负值;因此,相似度值越大说明点与点的距离越近。

而矩阵s的参考度称为p(i)s(i,i),是指点i作为聚类中心的参考度,以S矩阵的对角线上的数值s (k, k)作为k点能否成为聚类中心的评判标准,这意味着该值越大,这个点成为聚类中心的可能性也就越大。

AP算法主要依靠一种“信息传递“的机值实现数据集的聚类,其传递机制中主要包含吸引度Responsibility和归属度Availability两类信息

吸引度Responsibility表示为r(i,k),用来描述点k适合作为数据点i的聚类中心的程度,值表示候选中心成为类中心的适合度

归属度Availability表示为a(i,k),用来描述点i选择点k作为其聚类中心的适合程度,值表示样本可能属于一类的程度。

算法通过不断迭代来更新每一个点的吸引度Responsibility和归属度Availability值,直到自动产生若干个类中心,同时将其余的数据点分配到对应的类团中。

AP算法的步骤如下:

  • 算法初始将吸引度r和归属度矩阵初始化为0矩阵
  • 计算吸引度Responsibility矩阵
  • 计算归属度Availability矩阵
  • 根据衰减系数 对吸引度Responsibility和归属度Availability进行更新(Lamda为衰减系数,主要调整算法收敛速度和迭代过程的稳定性)
  • 如果聚类中心在若干次迭代中不发生改变时或者达到最大迭代次数时结束计算,取a+r最大的k作为聚类中心;否则返回第二步继续计算。

To capture the forces of nature.