Affinity propagation 聚类

来自集智百科
跳转到: 导航搜索

目录

简介

Affinitypropagation figure 1.png


affinity propagation是Frey和Dueck在2007年发表在Science上的聚类算法。从更广义的角度说,它属于message-passing algorithms的一种。原始文献见这里这里有关于AP算法的问答,包括适用的数据量大小和计算速度等细节。和k-means等它聚类算法一样,它的input是一个N * N 的similarity matrix。在这个相似性矩阵上,算法通过在数据点之间传递信息(responsibility和availability,前者决定点i有多大意愿选择k作为自己的代表examplar,后者决定k有多大意愿决定呗i选择做代表),不断修改聚类中心的数量和位置,直到整个数据的net similarity(聚类中心k自己对自己的similarity+所有节点i!=k到k的similarity)达到最大。

Affinitypropagation figure 2.png


Marc Mézard在同期Science对Frey和Dueck的文章给出了一个有趣的评论,他应用了卡拉瓦乔的一幅画,通过人物(data point)之间的手势和眼神的交流来解释AP是如何工作,选出一群人的焦点的(见下图)。

Affinitypropagation figure 4.png

优势

比起k-means方法,这种方法的好处是:

不需要事先指定聚类的数量

在affinity propagation中聚类的数量是由preference的设定和数据的结构共同决定的。一般默认将所有的数据点的preference设为similarity矩阵的median。节点会比较自己的preference和与其他节点之间的相似性,如果后者更高,就选择后者作为exmplar,反之则自己做exmplar。所以一开始如果把所有的preference都设成0或大于0,而similarity矩阵上的元素是负值(例如负的欧式距离),那么每个节点都会成为examplar,也就是最后举出来N类。如果preference被设成一个比较小的值,例如similarity矩阵的median,那么就会在迭代过程中自发形成聚类的团块数量。

聚类的结果不会变化

kmeans方法是先随机抽样生成cluster center或者examplar,但AP则是在每一轮中同时考虑所有的节点,所以后者是一个determinstic model,也就意味着聚类的结果不会随机变化。

适用于非对称相似性矩阵,甚至不满足三角关系的相似性数据

Affinitypropagation figure 3.png

kmeans方法中,相似性矩阵是对称的,即s(i,j)=s(j,i),但是AP并没有这个要求。后者甚至适用于不满足三角关系的情况。在2007年的论文中,作者分析的美国和加拿大的航班网络(网络也可以看做是一个相似性矩阵,相似性权重为网络连边上的流量或者别的统计量,本案例中是一个城市到另一个城市的飞行时间)。在这个网络里,相似性是城市之间的飞行时间,这个变量是不满足三角关系的。例如A->B的平均飞行时间不一定就小于A->C+C->B的平均飞行时间(因为前者可能会没有直达飞机而要中途在别处转机,而且地球是一个球体)。在这个案例中,AP给出了很好的划分结果。

适用于稀疏的相似性矩阵

Affinitypropagation figure 5.png

因为responsibility和availability两种信息是在相似性矩阵的基础上计算和迭代,所以算法只利用了相似性信息。当矩阵中有大量元素为空的时候,AP仍然可以给出聚类,而且速度更快。

劣势

AP的劣势是充分识别了数据内部的结构后,对于许多真实数据,都会聚出比较多的类,因此在聚类数量在1-5时,速度没有K-means快,效果也不一定好。 具体来说,AP算法复杂度为O(N*N*logN),而K-Means是O(N*K)。因此当N比较大时(N>3000),AP聚类算法往往需要算很久。

应用

因为AP只是一种聚类算法,所以在机器学习里是non domain-specific的,文章中给出了四个例子,对生物基因的聚类,对人脸的聚类,对文章主题句的提取(这个比较有意思,作者把自己发表的这篇文章提出四句话),和对城市之间航运网络的聚类。

在python的sklearn包里带了AP算法,应用起来也是很方便的:

首先调用包

    from sklearn.cluster import AffinityPropagation
    from sklearn import metrics
    from sklearn.datasets.samples_generator import make_blobs
    import pylab as pl
    from itertools import cycle

其次生成模拟数据

 
    # 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)

接着拟合AP

 
    # Compute Affinity Propagation
    af = AffinityPropagation(preference=-50).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'))

最后绘制出结果

Affinitypropagation figure 6.png

 
    # Plot result
    pl.close('all')
    pl.figure(1)
    pl.clf()
    colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
    pl.title('Estimated number of clusters: %d' % n_clusters_)
    for k, col in zip(range(n_clusters_), colors):
        class_members = labels == k
        cluster_center = X[cluster_centers_indices[k]]
        pl.plot(X[class_members, 0], X[class_members, 1], col + '.')
        pl.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
                markeredgecolor='k', markersize=14)
        for x in X[class_members]:
            pl.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)

每次运行的结果都是一样的。

相关wiki

个人工具
名字空间
操作
导航
工具箱