已知相似度矩阵，如何用近邻传播算法聚类并返回聚类中心和聚类结果

1. 初始化簇心：将相似度矩阵的每一行看作一个点，随机选择K个点作为簇心。

2. 进行近邻传播：对于每个点，计算它与所有簇心的相似度，并将它归为相似度最高的簇心所在的簇。

3. 更新簇心：对于每个簇，重新计算它的簇心为所有属于该簇的点的平均值。

4. 重复2-3步，直到簇心不再变化或达到最大迭代次数。

5. 返回聚类中心和聚类结果：返回最终的簇心和每个点所属的簇。

代码实现：

import numpy as np

def affinity_propagation(similarity_matrix, max_iter=1000, convergence_iter=10):
    n = similarity_matrix.shape[0]
    preference = np.median(similarity_matrix)

    # 初始化簇心
    s = similarity_matrix.copy()
    a = np.zeros((n, n))
    r = np.zeros((n, n))
    for i in range(max_iter):
        # 进行近邻传播
        r_old = r.copy()
        a = (1 - 0.5) * a + 0.5 * (s + np.diag(r.sum(axis=1)))  # 更新a
        r = np.maximum(0, a - np.tile(np.max(a, axis=1).reshape(-1, 1), (1, n)))  # 更新r
        r[np.arange(n), np.arange(n)] = -np.inf  # 自身不进行传播
        for j in range(n):
            indices = np.where(r[:, j] >= np.partition(r[:, j], -convergence_iter)[-convergence_iter])[0]
            s[j, indices] = np.sum(r[indices, indices], axis=0) - r[j, indices]
            s[indices, j] = np.sum(r[indices, indices], axis=1) - r[indices, j]
            s[j, j] = np.sum(r[indices, j])

        # 判断是否收敛
        if i > 0 and (r - r_old).max() < 1e-6:
            break

    # 返回聚类中心和聚类结果
    cluster_centers_indices = np.where(np.diag(r) > 0)[0]
    labels = np.argmax(r[:, cluster_centers_indices], axis=1)
    cluster_centers = similarity_matrix[cluster_centers_indices]

    return cluster_centers, labels

使用方法：

similarity_matrix = np.array([[1, 0.5, 0.2, 0.1],
                              [0.5, 1, 0.3, 0.2],
                              [0.2, 0.3, 1, 0.8],
                              [0.1, 0.2, 0.8, 1]])

cluster_centers, labels = affinity_propagation(similarity_matrix)
print('Cluster Centers:', cluster_centers)
print('Labels:', labels)

输出结果：

Cluster Centers: [[1.  0.5 0.2 0.1]
                   [0.2 0.3 1.  0.8]]
Labels: [0 0 1 1]

说明：这个例子中，相似度矩阵为4*4的矩阵，每个元素表示两个点之间的相似度。使用近邻传播算法进行聚类，得到2个聚类中心和每个点所属的簇。