5.8.1 近邻传播聚类算法
2007年，Frey和Delbert在Science上发表的Clustering by Passing Messages Between Data Points 一文中首次提到了近邻传播聚类算法(Affinity Propagation clustering，AP)。该算法只需要输入待分类数据集的相似性矩阵，数据点之间就可以自动进行信息传递并最终生成最佳聚类结果。每一个聚类结果是以一个最佳类代表点为中心，AP聚类的目标就是运用近邻信息传播的思想找到最优的类代表点集合，使得所有的数据点到其类代表点的相似度之和最大。
图5.52中左图是待分类的数据集，右图是AP聚类的分类结果。在右图的结果中，所有的数据点被分成三类，其中，黑色框中的数据点就是最佳类代表点，其他属于该类的点都以类代表点为中心，其他的点与中心点相连，它们之间的相似度之和为最大。
图5.52 AP聚类结果图
(a)待分类数据集；(b)AP聚类的分类结果
图5.53为AP聚类算法因子图[45]，AP聚类算法可进行最大乘积法的置信传播[46]。假设有N 个待分类的数据点，数据节点之间的相似度矩阵为[sij]N×N，则AP聚类经过一系列迭代后最终会产生最佳类代表集合c=[c1，…，cN]使得目标方程式(5.54)最大化。
其中，δk(c)是“类中心一致性”约束方程，如公式(5.55)所示。如果数据点i选择数据点k作为类代表，即ci=k，那么也就意味着数据点k必须选择它自身作为自己的类代表，即ck=k。
在AP聚类的迭代过程中，有两种信息ρij和αij在数据点之间进行传递直到它们的值不再发生改变为止。其中，ρij被称为吸引度，由数据点i传递给其候选类代表中心j，反映了和其他候选类代表中心相比，数据点j作为数据点i的类代表中心的合适程度；αij被称为归属度，由候选类代表中心j传递给数据点i，反映了和其他以数据点j为类代表中心的数据点，数据点i选择数据点j作为类代表中心的合适程度。迭代初始化时，ρij和αij取值都为0，迭代公式为：
图5.53 AP聚类算法因子图(https://www.daowen.com)
当ρij和αij的值不再发生改变或者在足够小的范围内变化时，产生的类代表集合K={k|αkk+ρkk＞0}就是最终的聚类结果，每一个非类代表中心数据i将归属于与其相似度最大的类代表中心k=argmaxk∈Ksik。
虽然标准的AP聚类算法最终只需要式(5.56)和式(5.57)进行迭代就可以得到不错的聚类结果，但是如果根据实际的应用需求对标准的AP聚类算法进行修改，比如因子图的结构发生变化或者约束方程不同，那么按照最大乘积法的置信传播原理推导出所需的迭代公式会变得非常烦琐和困难。因此，Givoni对Frey和Delbert的因子图进行了改进，得到了方便修改和扩展标准AP的新模型[73][74]，如图5.54所示。
与图5.53相比，新的因子图有两种约束方程，变量也由原来的N 个扩展到N2个，每个变量与三个方程相连。其中，相似度sij({i，j}⊂{1，…，N})用来描述数据点i和数据点j之间的相似程度(i≠j)，而自相似度sjj称为偏向参数，其大小影响着生成聚类数量的多少，一般情况下令sjj为所有相似度的中值。变量hij(j∈{1，…，N})与数据点i(i∈{1，…，N})相连，如果数据点i选择数据点j作为类代表，那么hij=1，否则hij=0。当i=j时，hjj表示数据点j为类代表。约束方程Ii用来保证在AP迭代的过程中每个数据点只能被赋予唯一的类代表，也称为“1-N 约束”，如公式(5.58)所示。“类中心一致性”约束方程Ej如公式(5.59)所示，相似度方程Sij如公式(5.60)所示。
图5.54 AP二值因子图
(a)二值模型；(b)信息传递图
其中，hi：=hi1，…，hiN，h：j=h1j，…，hNj。
在新的二值模型中，采用最大乘积法的置信传播原理最大化目标方程(5.61)就可以得到和公式(5.56)、公式(5.57)一致的结果。
