精华内容
下载资源
问答
  • affinity propagation
    2020-03-03 16:06:47

    1.概要

    Affinity Propagation聚类算法简称AP,2007年Brendan J Frey和Delbert Dueck发表于Science期刊。AP算法思想是,网络中所有样本点作为节点,通过节点间传递归属度和吸引度两类信息来计算聚类中心,迭代计算出最优的数个聚类中心,并将剩余节点划分到相应的类中。

    2.比较

    AP算法和K-Means算法相比,优点是:鲁棒性强,准确度高;缺点是:算法复杂度高,运行时间长。

    3.概念

    1. Exemplar 聚类中心
    2. Similarity 相似度,记作s(i,j),即数据点j作为i聚类中心的相似度,一般用欧氏距离计算,值为负,值越大数据点距离越近
    3. Responsibility 吸引度,记作r(i,k),即k作为i聚类中心的适合程度
    4. Availability 归属度,记作a(i,k),即i选择k作为聚类中心的适合程度
    5. Preference 参考度,记作p(i)或s(i,i),需手动设定,值越大聚类数越多
    6. Damping factor 阻尼系数,控制算法收敛性,值越小,收敛速度越快

    4.实例

    R语言中的apcluster包提供了AP算法封装

    更多相关内容
  • 基于Affinity Propagation算法的半监督微博水军识别.docx
  • 亲和传播聚类 (AP) 是“Brendan J. Frey and Delbert Dueck. Clustering by Passing Messages between Data Points. Science 315, 972 (2007)”中提出的一种聚类算法。 它有一些优点:速度快,适用性强,适用于大量...
  • cluster_std=0.5, random_state=0 ) # ############################################################################# # Compute Affinity Propagation af = AffinityPropagation(preference=-50, random_state=...

    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-pyicon-default.png?t=M3K6https://scikit-learn.org/stable/auto_examples/cluster/plot_affinity_propagation.html#sphx-glr-auto-examples-cluster-plot-affinity-propagation-py

    展开全文
  • 借助近邻传播算法改进K-means初始化方法,朱岩,于剑,K-means聚类方法因为具有快速的收敛速度而被广泛应用,但是该算法对初始值的敏感性却是人们所不期望的。很多学者都提出了不同的初��
  • Affinity Propagation聚类算法详解

    千次阅读 2021-03-25 00:52:28
    欢迎关注”生信修炼手册”!Affinity Propagation简称AP, 称之为近邻传播算法, 是一种基于图论的聚类算法。将所有样本点看做是一个网络中的节点,图示如下在样本点构成的网络...

    欢迎关注”生信修炼手册”!

    Affinity Propagation简称AP, 称之为近邻传播算法, 是一种基于图论的聚类算法。将所有样本点看做是一个网络中的节点,图示如下

    在样本点构成的网络中,每个样本点都是潜在的聚类中心,同时也归属于某个聚类中心点,对应这样的两面性,提出了以下两个概念

    1. responsibility, 吸引度,对于(i, k)而言,定量描述样本k作为样本i的聚类中心的程度

    2. availability,归属度,对于(i, k)而言,定量描述样本i支持样本k作为其聚类中心的程度

    具体的定义方式如下

    1. Similarity

    相似度,这里的定量方式是欧氏距离的负数,公式如下

    之所以如此定义,是为了对称性的考量,图这个数据结构的最常见表示方式就是邻接矩阵了,图示如下

    基于相似度,我们可以得到样本点之间的相似度矩阵。在该相似度矩阵中,对角线的值为样本自身的距离,理论上是0,但是为了后续更好的应用相似度来更新吸引度和归属度,引入了preference参数。

    这个参数就是定义相似度矩阵中对角线上的值,是认为设定的,比如可以取相似度的均值或者中位数。在scikit-learn中,默认用的就是中位数。

    这个参数会影响聚类的类别数目,该值越大,聚类的类别数越多。

    2. Responsibility

    吸引度,公式如下

    3. Availability

    归属度,公式如下

    对于网络中的所有节点,借助邻接矩阵的思想,我们可以计算得到吸引度矩阵R和归属度矩阵A。

    AP算法通过迭代的方式来达到聚类效果,每次迭代其实就是更新上述两个矩阵的值, 在更新的时候,引入了一个叫做dumping  factor的参数来控制更新的幅度,公式如下

    r(i,k)new = λ*r(i,k)old + (1-λ)*r(i,k)
    a(i,k)new = λ*a(i,k)old + (1-λ)*a(i,k)

    这个系数的值是需要人为指定的, 建议设置范围为0.5到1。迭代收敛之后,需要挑选作为聚类中心的样本点,选取的标准是样本点的R+A>0, 确定了聚类中心之后,在确定对应的归属点即可。

    在scikit-learn中,进行AP聚类的代码如下

    >>> from sklearn.cluster import AffinityPropagation
    >>> import numpy as np
    >>> X = np.array([[1, 2], [1, 4], [1, 0],[4, 2], [4, 4], [4, 0]])
    >>> clustering = AffinityPropagation(random_state=5).fit(X)
    >>> clustering
    AffinityPropagation(random_state=5)
    >>> clustering.labels_
    array([0, 0, 0, 1, 1, 1], dtype=int32)
    >>> clustering.predict([[0, 0], [4, 4]])
    array([0, 1], dtype=int32)
    >>> clustering.cluster_centers_
    array([[1, 2],
           [4, 2]])

    作为一种基于图论的聚类算法,该算法适用范围广,不需要事先指定聚类的类别数目K, 而且聚类效果稳定,多次运行的结果一致,但是,该算法也需要人为指定preference和dump factor两个参数,而且算法复杂度比较高,运算时间比较久。

    ·end·

    —如果喜欢,快分享给你的朋友们吧—

    原创不易,欢迎收藏,点赞,转发!生信知识浩瀚如海,在生信学习的道路上,让我们一起并肩作战!

    本公众号深耕耘生信领域多年,具有丰富的数据分析经验,致力于提供真正有价值的数据分析服务,擅长个性化分析,欢迎有需要的老师和同学前来咨询。

      更多精彩

      写在最后

    转发本文至朋友圈,后台私信截图即可加入生信交流群,和小伙伴一起学习交流。

    扫描下方二维码,关注我们,解锁更多精彩内容!

    一个只分享干货的

    生信公众号

    展开全文
  • Affinity propagation clustering matlab code.
  • Affinity Propagation 算法更新方式很简单就是 更新 r矩阵在更新a矩阵 公式如下: 其中 s是相似度矩阵 一般直接可以采用距离来表示相似度 r 表示吸引度 a归属度 这里就用选举来进行形象讲解下 对于公式1 ...

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

    结果如下图:

    与君共勉~

    展开全文
  • 1.概述 机器学习中 AP(Affinity Propagation)通常被称为近邻传播算法或者密切度传播或类同传播算法,由 Frey 与Dueck于2007年在Science首次提出。AP算法的基本思想是将全部数据点都当作潜在的聚类中心(称之为...
  • AP(affinity propagation)聚类算法

    千次阅读 2021-09-16 21:39:44
    AP(affinity propagation)聚类算法 引言 AP(affinity propagation)聚类算法是用来解决什么问题的 AP(affinity propagation)聚类算法具体是怎么实现的 AP(affinity propagation)聚类算法在我们算法中的应用 AP...
  • Affinity Propagation Clustering

    千次阅读 2018-12-05 21:07:06
    AP聚类算法是基于数据点间的“信息传递"的一种聚类算法。AP算法不需要在运行算法之前确定聚类的个数。AP算法寻找数据集合中实际存在的点为聚类中心点,作为每类的代表。 基本概念 相似性矩阵S(similarity...
  • Affinity Propagation

    千次阅读 2016-08-13 21:34:20
    Affinity propagation 其中两点相似度s(i, j)的度量默认采用负欧氏距离。 sklearn.cluster.AffinityPropagation 有参数preference(设定每一个点的偏好,将偏好于跟其他节点的相似性进行比较,选择 高的作为exmplar...
  • 在统计和数据挖掘里,affinity propagation(AP)是一种基于数据点之间的“信息传递”的聚类算法。与k-means等其它聚类算法不同的是,AP不需要在聚类前确定或估计类的个数。类似于k-medoids, AP需要寻找原型(exemplars...
  • aterials and Methods: In this study, we developed an automatic AIF detection method using an accelerated version (Fast-AP) of affinity propagation (AP) clustering. The validity of this Fast-AP-based ...
  • 这是近邻传播聚类算法创始人Frey & Dueck在2007年Science杂志上面发表的“Clustering by Passing Messages between data points”论文里面方法的MATLAB实现程序代码,俗称AP聚类代码。里面包含两个版本:一个是普通...
  • 最近看了聚类传播算法,对于Affinity Propagation算法,大家可以参考以下链接,个人推荐的阅读顺序是: Affinity Propagation: AP聚类算法:先简要了解一下大概的流程; 浅谈AP聚类算法-matlab:与论文一起阅读这篇...
  • AP聚类算法是基于数据点间的"信息传递"的一种聚类算法。与k-均值算法或k中心点算法不同,AP算法不需要在运行算法之前确定聚类的个数。AP算法寻找的"examplars"即聚类中心点是数据集合中实际存在的点,作为每类的代表...
  • 近邻传播算法是一种基于代表点的聚类方法,它会同时考虑所有数据点都是潜在的代表点,通过结点之间的信息传递,最后得到高质量的聚类。这个信息的传递,是基于sum-product或者说max-product的更新原则,在任意一个...
  • 本文提出了一种基于快速Affinity Propagation聚类算法的木材缺陷识别方法.通过提取木材图像的颜色矩特征,建立样本特征集X,以平均平方残基为阈值降低样本特征集X及距离矩阵S的维数,自动识别木材缺陷位置并标记....
  • 想象这样一个场景:  小A同学今天刚入职。刚进入办公室人脸还不熟就被通知下楼进行消防演习。----背景 ...经过这个场景,对于Affinity Propagation算法算是有一个比较具体的认识了。    
  • 计算机研究 -基于先验聚类中心和消息反馈的Affinity Propagation算法.pdf
  • It is used to cluster by the method of Affinity Propagation. Its area is data mining-clustering.
  • Affinity Propagation聚类算法的实现

    千次阅读 多人点赞 2022-04-08 10:22:52
    本博文实现了Affinity Propagation聚类算法的应用
  • R语言Affinity Propagation+AP聚类实战 目录 R语言Affinity Propagation+AP聚类实战 #仿真数据 #AP(Affinity Propagation)AP聚类 #仿真数据 n = 100 g = 6 set.seed(g) d <- data.frame(x = unlist...
  • affinity propagation算法

    2011-11-30 13:40:00
    介绍affinity propagation算法的基本原理,步骤及应用
  • Active semi-supervised affinity propagation clustering algorithm based on pair-wise constraints
  • preference: 结点参考度,可以是一个数值或一个数组(每个样本有各自的参考度) affinity: 相似度计算的方法 一些重要的聚类结果的属性: cluster_centers_indices 质心样本在训练集中的索引号 cluster_centers_: 质心...
  • Affinity Propagation (AP) 聚类是2007年在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即...
  • Optimizing radial basis function neural network based on rough sets and affinity propagation clustering algorithm

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,844
精华内容 737
关键字:

affinity propagation