Reference: Brendan J. Frey and Delbert Dueck, “Clustering by Passing Messages Between Data Points”, Science Feb. 2007

输出:

Estimated number of clusters: 3
Homogeneity: 0.872
Completeness: 0.872
V-measure: 0.872
Adjusted Rand Index: 0.912
Adjusted Mutual Information: 0.871
Silhouette Coefficient: 0.753

from sklearn.cluster import AffinityPropagation
from sklearn import metrics
from sklearn.datasets import make_blobs

# #############################################################################
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(
    n_samples=300, centers=centers, cluster_std=0.5, random_state=0
)

# #############################################################################
# Compute Affinity Propagation
af = AffinityPropagation(preference=-50, random_state=0).fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_

n_clusters_ = len(cluster_centers_indices)

print("Estimated number of clusters: %d" % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f" % metrics.adjusted_rand_score(labels_true, labels))
print(
    "Adjusted Mutual Information: %0.3f"
    % metrics.adjusted_mutual_info_score(labels_true, labels)
)
print(
    "Silhouette Coefficient: %0.3f"
    % metrics.silhouette_score(X, labels, metric="sqeuclidean")
)

# #############################################################################
# Plot result
import matplotlib.pyplot as plt
from itertools import cycle

plt.close("all")
plt.figure(1)
plt.clf()

colors = cycle("bgrcmykbgrcmykbgrcmykbgrcmyk")
for k, col in zip(range(n_clusters_), colors):
    class_members = labels == k
    cluster_center = X[cluster_centers_indices[k]]
    plt.plot(X[class_members, 0], X[class_members, 1], col + ".")
    plt.plot(
        cluster_center[0],
        cluster_center[1],
        "o",
        markerfacecolor=col,
        markeredgecolor="k",
        markersize=14,
    )
    for x in X[class_members]:
        plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)

plt.title("Estimated number of clusters: %d" % n_clusters_)
plt.show()

-plot-affinity-propagation-pyhttps://scikit-learn.org/stable/auto_examples/cluster/plot_affinity_propagation.html#sphx-glr-auto-examples-cluster-plot-affinity-propagation-py

Affinity Propagation 算法更新方式很简单就是 更新 r矩阵在更新a矩阵

公式如下：

其中 s是相似度矩阵 一般直接可以采用距离来表示相似度

r 表示吸引度  a归属度

这里就用选举来进行形象讲解下

对于公式1

就好比是一个投票阶段  s(i, k)表示i 选k作为总统(聚类中心)的合适度    用r(i, k) 表示选k作为总统的意向有多大

直观来说  直接用r(i, k) =  s(i, k) -  max(s(i, k'))      k' != k     貌似更加形象，但是人是感性动物，会受别人影响，这里就是a起到的作用，比如 i 的亲人朋友都投了k'当总统，就会来问我你要不要和我们一样投k',  大家都在投k', 你也快点投k'。然后我经过深思熟虑 最终投给k的意向会受到影响(影响的大小取决于a(i, k')的大小)。所以  r(i, k) =  s(i, k) -  max{s(i, k') + a(i, k')}  最终我投给k的意向 

对于公式2

就像是一个拉票，a(i, k)表示形象理解为k对i的影响力而他的大小受k对其他i'的影响力，如果亲人朋友 i' 都投了k, 对于i来说就有很大概率也投k,这就是所谓的随波逐流。越多i'投k, a(i, k)就会也大，也就是说k对i的影响力越大，对于公式1起到的影响就越大。这里加上r(k, k)也很好理解，我自己对自己也有个投票意向，虽然大家都投了我，但是我自己这一票肯定还是要算计来的，万一比别人就差这一票不是亏大了。

迭代停止的条件就是所有的样本的聚类中心都不在变化为止，或者迭代了n次都还没有变化（n的值可以自己取）。

代码如下：

from sklearn.datasets.samples_generator import make_blobs
import matplotlib.pyplot as plt
import numpy as np

centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.4,
                            random_state=0)


def calc_similarity(X):
    m, n = np.shape(X)
    X_copy = np.copy(X)
    X = X.reshape((m, 1, n))
    X_copy = X_copy.reshape(1, m, n)
    sum = np.sum(np.square(X[..., :] - X_copy[..., :]), axis=-1)
    similarity = -1 * np.sqrt(sum)
    median_value = calc_median(similarity)
    for i in range(m):
        # preference设置 非对角线元素中值
        similarity[i, i] = median_value
    return similarity


def calc_median(X):
    data = []
    for i in range(len(X)):
        x = X[i]
        x = np.delete(x, i)
        data += list(x)
    n = len(data)
    return data[n // 2]


def affinityPropagation(similarity, lamda=0.):
    # 定义吸引度矩阵和归属感矩阵
    r = np.zeros_like(similarity, dtype=np.int32)
    a = np.zeros_like(similarity, dtype=np.int32)

    m, n = np.shape(similarity)

    last_change = np.zeros((m, ), dtype=np.int32)
    while True:
        # update r matrix
        for idx in range(m):
            a_s_idx = a[idx] + similarity[idx]
            for idy in range(n):
                a_s_idx_del = np.delete(a_s_idx, idy)
                max_value = np.max(a_s_idx_del)
                r_new = similarity[idx, idy] - max_value
                r[idx][idy] = lamda * r[idx][idy] + (1 - lamda) * r_new
        # update a matrix
        for idx in range(m):
            for idy in range(n):
                r_idy = r[:, idy]
                r_idy = np.delete(r_idy, idx)
                a_new = np.sum(np.maximum(0, r_idy))
                if idx != idy:
                    a_new = min(0, r[idy, idy] + a_new)
                a[idx][idy] = lamda * a[idx][idy] + (1 - lamda) * a_new
        r_a = r + a
        # 当聚类中心不再发生变化时停止
        argmax = np.argmax(r_a, axis=1)
        current_change = argmax
        if (last_change == current_change).all():
            break
        last_change = current_change
    print('r', r)
    print('a', a)
    return r + a


def computeCluster(fitable, data):
    clusters = {}
    num = len(fitable)
    for idx in range(num):
        fit = fitable[idx]
        argmax = np.argmax(fit, axis=-1)
        if argmax not in clusters:
            clusters[argmax] = []
        clusters[argmax].append(tuple(data[idx]))
    return clusters


def plotClusters(clusters, title):
    """ 画图 """
    plt.figure(figsize=(8, 5), dpi=80)
    axes = plt.subplot(111)
    col = []
    r = lambda: np.random.randint(0, 255)
    for index in range(len(clusters)):
        col.append(('#%02X%02X%02X' % (r(), r(), r())))
    color = 0
    for key in clusters:
        cluster = clusters[key]
        for idx in range(len(cluster)):
            cluster_idx = cluster[idx]
            axes.scatter(cluster_idx[0], cluster_idx[1], s=20, c=col[color])
        color += 1
    plt.title(title)
    plt.show()


similarity = calc_similarity(X)
fitable = affinityPropagation(similarity, lamda=0.25)
clusters = computeCluster(fitable, X)
print(len(clusters))
plotClusters(clusters, "clusters by affinity propagation")

结果如下图：

与君共勉~