原理推导ap聚类算法代码实现

AP聚类算法基于两个原则：每个点选择一个指定的代表者（即examplar）和最大化examplar之间的总权重。在算法的实现过程中，需要进行以下几个步骤：

步骤1：初始化相似度矩阵S和责任矩阵R。其中相似度矩阵用来存储点之间的相似度，责任矩阵用于表示当前的点与其它点作为examplar时所承担的责任，根据公式R(i,k)=S(i,k)-max{a+s(a,k)}，其中a和k均表示数据点的索引。

步骤2：更新可用性矩阵A和归属矩阵T。可用性矩阵用来表示当前数据点作为examplar时其他数据点可选择的可能性，归属矩阵用于表示当前数据点的examplar。根据公式a(i,k)=min{0,R(k,k)+Σ[max{0,R(j,k)}]，t(i,k)=1(i=j)，0(i≠j)，其中j表示除k之外的所有数据点的索引。

步骤3：更新责任矩阵R和可用性矩阵A。根据公式R(i,k)=S(i,k)-max{a(j,k)+s(i,k)}，a(i,k)=[Σ{max{0,R(j,k)}}-max{0,R(i,k)}](i≠k)，a(k,k)=[Σ{max{0,R(j,k)}}-max{0,R(k,k)}]，其中j表示所有除k和i之外的数据点的索引。

步骤4：判断算法是否收敛。如果可用性矩阵A和归属矩阵T不再发生变化，则算法收敛，可以输出结果。

步骤5：根据归属矩阵T计算每个聚类的examplar。计算公式为max[A(i,k)+R(i,k)](k=1,2,…，N,i≠k)，其中N为聚类数目。

步骤6：分类。如果数据点i分配给了examplar k，则其所在聚类的编号为k。如果某个聚类没有任何数据点分配给该聚类的examplar，则需要将该聚类与其他距离最近的聚类合并。

通过以上6个步骤，即可实现AP聚类算法。