聚类算法_聚类算法总结 - CSDN
精华内容
参与话题
  • 聚类的四种算法

    万次阅读 2018-06-11 17:13:40
    最近看了一篇论文,涉及到数据挖掘的聚类算法,这里总结一下一、聚类算法的简介 聚类算法是一种典型的无监督学习算法,主要用于将相似的样本自动归到一个类别中。聚类算法与分类算法最大的区别是:聚类算法是无监督...

    最近看了一篇论文,涉及到数据挖掘的聚类算法,这里总结一下

    一、聚类算法的简介

     聚类算法是一种典型的无监督学习算法,主要用于将相似的样本自动归到一个类别中。聚类算法与分类算法最大的区别是:聚类算法是无监督的学习算法,而分类算法属于监督的学习算法。在聚类算法中根据样本之间的相似性,将样本划分到不同的类别中,对于不同的相似度计算方法,会得到不同的聚类结果,常用的相似度计算方法有欧式距离法。

    1、K-Means算法的概述

      基本K-Means算法的思想很简单,事先确定常数K,常数K意味着最终的聚类类别数,首先随机选定初始点为质心,并通过计算每一个样本与质心之间的相似度(这里为欧式距离),将样本点归到最相似的类中,接着,重新计算每个类的质心(即为类中心),重复这样的过程,知道质心不再改变,最终就确定了每个样本所属的类别以及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度,故在大规模的数据集上K-Means算法的收敛速度比较慢。

    1.1、K-Means算法的流程

    初始化常数K,随机选取初始点为质心

    重复计算一下过程,直到质心不再改变

    计算样本与每个质心之间的相似度,将样本归类到最相似的类中

    重新计算质心

    输出最终的质心以及每个类

    2. DBSCAN算法

    2.1基本概念

    1Eps邻域:给定对象半径Eps内的邻域称为该对象的Eps邻域;

    2)核心点(core point):如果对象的Eps邻域至少包含最小数目MinPts的对象,则称该对象为核心对象;

    3)边界点(edge point):边界点不是核心点,但落在某个核心点的邻域内;

    4)噪音点(outlier point):既不是核心点,也不是边界点的任何点;

    5)直接密度可达(directly density-reachable):给定一个对象集合D,如果pqEps邻域内,而q是一个核心对象,则称对象p从对象q出发时是直接密度可达的;

    6)密度可达(density-reachable):如果存在一个对象链  p1, ,pi,.., pn,满足p1 = p pn = qpi是从pi+1关于EpsMinPts直接密度可达的,则对象p是从对象q关于EpsMinPts密度可达的;

    7)密度相连(density-connected):如果存在对象OD,使对象pq都是从O关于EpsMinPts密度可达的,那么对象pq是关于EpsMinPts密度相连的。

    8)类(cluster:设非空集合,若满足:从(a)到(b)和密度相连。则称构成一个类簇

    1红色为核心点,黄色为边界点,蓝色为噪音点,minPts = 4Eps是图中圆的半径大小有关“直接密度可达”和“密度可达”定义实例如图2所示[5]其中,Eps用一个相应的半径表示,设MinPts=3,请分析Q,M,P,S,O,R5个样本点之间的关系。

    2  “直接密度可达”和“密度可达”概念示意描述。根据前文基本概念的描述知道:由于有标记的各点­MPOREps近邻均包含3个以上的点,因此它们都是核对象;是从P“直接密度可达”;而Q则是从­M“直接密度可达”;基于上述结果,Q是从P“密度可达”;但PQ无法“密度可达”(非对称)。类似地,SRO是“密度可达”的;ORS均是“密度相连”(对称)的。


    2.2 DBSCAN算法原理

    1DBSCAN通过检查数据集中每点的Eps邻域来搜索簇,如果点pEps邻域包含的点多于MinPts个,则创建一个以p为核心对象的簇;

    2)然后,DBSCAN迭代地聚集从这些核心对象直接密度可达的对象,这个过程可能涉及一些密度可达簇的合并;

    3)当没有新的点添加到任何簇时,该过程结束。

    2.3 DBSCAN算法优缺点

    优点:

    1)聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类;

    2)与K-MEANS比较起来,不需要输入要划分的聚类个数;

    3)聚类簇的形状没有偏倚;

    4)可以在需要时输入过滤噪声的参数。

    缺点:

    1)当数据量增大时,要求较大的内存支持I/O消耗也很大;

    2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数MinPtsEps选取困难。

    3)算法聚类效果依赖与距离公式选取,实际应用中常用欧式距离,对于高维数据,存在“维数灾难”。

    2.4. 算法描述

    输入:包含n个对象的数据库,半径,最少数目MinPts

    输出:所有生成的簇,达到密度要求

    (1)  Repeat

    (2)  从数据库中抽取一个未处理的点

    (3)  IF抽取的点是核心点THEN找出所有从该点密度可达的对象,形成一个簇

    (4)  ELSE抽出的点是边缘点,跳出本次循环,寻找下一点

    (5)UNTIL所有的点都被处理

    3.BIRCH算法

    3.1 算法思想

    阶段1:BIRCH扫描数据库,建立一个初始存放于内存的CF树,它可以被看作数据的多层压缩,试图保留数据内的聚类结构。随着对象的插入,CF树被动态的构造,不要求所有的数据读入内存,而可在外层上逐个读入数据项。因此,BIRTCH方法对增量或动态聚类也非常有效

    阶段2:BIRCH采用某个聚类算法对CF树的叶节点进行聚类,在这个阶段可以执行任何聚类算法。   

    CF tree的结构类似于一棵B-树,它有两个参数:内部节点平衡因子B,叶节点平衡因子L,簇半径阈值T。树中每个节点最多包含B个孩子节点,记为(CFi,CHILDi),1<=i<=B,CFi是这个节点中的第i个聚类特征,CHILDi指向节点的第i个孩子节点,对应于这个节点的第i个聚类特征。

     一棵CF树是一个数据集的压缩表示,叶子节点的每一个输入都代表一个簇C,簇C中包含若干个数据点,并且原始数据集中越密集的区域,簇C中包含的数据点越多,越稀疏的区域,簇C中包含的数据点越少,簇C的半径小于等于T。随着数据点的加入,CF树被动态的构建,插入过程有点类似于B-树。

    4  MeanShift算法

    4.1 Meanshift算法基本思想

    均值漂移的基本概念:沿着密度上升方向寻找聚簇点

    设想在一个有N个样本点的特征空间

    1.初始确定一个中心点center,计算在设置的半径为D的圆形空间内所有的点(xi)与中心点center的向量

    2.计算整个圆形空间内所有向量的平均值,得到一个偏移均值

    3.将中心点center移动到偏移均值位置

    4.重复移动,直到满足一定条件结束


     



     






    展开全文
  • 常见的六大聚类算法

    万次阅读 多人点赞 2019-09-24 15:29:03
    1. K-Means(K均值)聚类 算法步骤: (1) 首先我们选择一些类/组,并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。 (2) 计算每个数据点到...

    1. K-Means(K均值)聚类


    算法步骤:
    (1) 首先我们选择一些类/组,并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。
    (2) 计算每个数据点到中心点的距离,数据点距离哪个中心点最近就划分到哪一类中。
    (3) 计算每一类中中心点作为新的中心点。
    (4) 重复以上步骤,直到每一类中心在每次迭代后变化不大为止。也可以多次随机初始化中心点,然后选择运行结果最好的一个。
    下图演示了K-Means进行分类的过程:

    è¿éåå¾çæè¿°

    优点:
    速度快,计算简便
    缺点:
    我们必须提前知道数据有多少类/组。
    K-Medians是K-Means的一种变体,是用数据集的中位数而不是均值来计算数据的中心点。
    K-Medians的优势是使用中位数来计算中心点不受异常值的影响;缺点是计算中位数时需要对数据集中的数据进行排序,速度相对于K-Means较慢。

     

    2. 均值漂移聚类


    均值漂移聚类是基于滑动窗口的算法,来找到数据点的密集区域。这是一个基于质心的算法,通过将中心点的候选点更新为滑动窗口内点的均值来完成,来定位每个组/类的中心点。然后对这些候选窗口进行相似窗口进行去除,最终形成中心点集及相应的分组。
    具体步骤:
    1. 确定滑动窗口半径r,以随机选取的中心点C半径为r的圆形滑动窗口开始滑动。均值漂移类似一种爬山算法,在每一次迭代中向密度更高的区域移动,直到收敛。
    2. 每一次滑动到新的区域,计算滑动窗口内的均值来作为中心点,滑动窗口内的点的数量为窗口内的密度。在每一次移动中,窗口会想密度更高的区域移动。
    3. 移动窗口,计算窗口内的中心点以及窗口内的密度,知道没有方向在窗口内可以容纳更多的点,即一直移动到圆内密度不再增加为止。
    4. 步骤一到三会产生很多个滑动窗口,当多个滑动窗口重叠时,保留包含最多点的窗口,然后根据数据点所在的滑动窗口进行聚类。
    下图演示了均值漂移聚类的计算步骤:

    è¿éåå¾çæè¿°

    下面显示了所有滑动窗口从头到尾的整个过程。每个黑点代表滑动窗口的质心,每个灰点代表一个数据点。

    è¿éåå¾çæè¿°

    优点:(1)不同于K-Means算法,均值漂移聚类算法不需要我们知道有多少类/组。
    (2)基于密度的算法相比于K-Means受均值影响较小。
    缺点:(1)窗口半径r的选择可能是不重要的。

    3. 基于密度的聚类方法(DBSCAN)


    与均值漂移聚类类似,DBSCAN也是基于密度的聚类算法。
    具体步骤:
    1. 首先确定半径r和minPoints. 从一个没有被访问过的任意数据点开始,以这个点为中心,r为半径的圆内包含的点的数量是否大于或等于minPoints,如果大于或等于minPoints则改点被标记为central point,反之则会被标记为noise point。
    2. 重复1的步骤,如果一个noise point存在于某个central point为半径的圆内,则这个点被标记为边缘点,反之仍为noise point。重复步骤1,知道所有的点都被访问过。
    优点:不需要知道簇的数量
    缺点:需要确定距离r和minPoints

    4. 用高斯混合模型(GMM)的最大期望(EM)聚类


    K-Means的缺点在于对聚类中心均值的简单使用。下面的图中的两个圆如果使用K-Means则不能作出正确的类的判断。同样的,如果数据集中的点类似下图中曲线的情况也是不能正确分类的。

    è¿éåå¾çæè¿°

    使用高斯混合模型(GMM)做聚类首先假设数据点是呈高斯分布的,相对应K-Means假设数据点是圆形的,高斯分布(椭圆形)给出了更多的可能性。我们有两个参数来描述簇的形状:均值和标准差。所以这些簇可以采取任何形状的椭圆形,因为在x,y方向上都有标准差。因此,每个高斯分布被分配给单个簇。
    所以要做聚类首先应该找到数据集的均值和标准差,我们将采用一个叫做最大期望(EM)的优化算法。下图演示了使用GMMs进行最大期望的聚类过程。

    è¿éåå¾çæè¿°

    具体步骤:
    1. 选择簇的数量(与K-Means类似)并随机初始化每个簇的高斯分布参数(均值和方差)。也可以先观察数据给出一个相对精确的均值和方差。
    2. 给定每个簇的高斯分布,计算每个数据点属于每个簇的概率。一个点越靠近高斯分布的中心就越可能属于该簇。
    3. 基于这些概率我们计算高斯分布参数使得数据点的概率最大化,可以使用数据点概率的加权来计算这些新的参数,权重就是数据点属于该簇的概率。
    4. 重复迭代2和3直到在迭代中的变化不大。
    GMMs的优点:(1)GMMs使用均值和标准差,簇可以呈现出椭圆形而不是仅仅限制于圆形。K-Means是GMMs的一个特殊情况,是方差在所有维度上都接近于0时簇就会呈现出圆形。
    (2)GMMs是使用概率,所有一个数据点可以属于多个簇。例如数据点X可以有百分之20的概率属于A簇,百分之80的概率属于B簇。也就是说GMMs可以支持混合资格。

    5. 凝聚层次聚类


    层次聚类算法分为两类:自上而下和自下而上。凝聚层级聚类(HAC)是自下而上的一种聚类算法。HAC首先将每个数据点视为一个单一的簇,然后计算所有簇之间的距离来合并簇,知道所有的簇聚合成为一个簇为止。
    下图为凝聚层级聚类的一个实例:

    è¿éåå¾çæè¿°

    具体步骤:
    1. 首先我们将每个数据点视为一个单一的簇,然后选择一个测量两个簇之间距离的度量标准。例如我们使用average linkage作为标准,它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
    2. 在每次迭代中,我们将两个具有最小average linkage的簇合并成为一个簇。
    3. 重复步骤2知道所有的数据点合并成一个簇,然后选择我们需要多少个簇。
    层次聚类优点:(1)不需要知道有多少个簇
    (2)对于距离度量标准的选择并不敏感
    缺点:效率低

    6. 图团体检测(Graph Community Detection)


    当我们的数据可以被表示为网络或图是,可以使用图团体检测方法完成聚类。在这个算法中图团体(graph community)通常被定义为一种顶点(vertice)的子集,其中的顶点相对于网络的其他部分要连接的更加紧密。下图展示了一个简单的图,展示了最近浏览过的8个网站,根据他们的维基百科页面中的链接进行了连接。

    è¿éåå¾çæè¿°

    模块性可以使用以下公式进行计算:


    其中L代表网络中边的数量,Aij代表真实的顶点i和j之间的边数, ki,kj代表每个顶点的degree,可以通过将每一行每一列的项相加起来而得到。两者相乘再除以2L表示该网络是随机分配的时候顶点i和j之间的预期边数。所以代表了该网络的真实结构和随机组合时的预期结构之间的差。当Aij为1时,且很小的时候,其返回值最高。也就是说,当在定点i和j之间存在一个非预期边是得到的值更高。
    是克罗内克δ函数(Kronecker-delta function). 下面是其Python解释:

    def Kronecker_Delta(ci,cj):
        if ci==cj:
            return 1
        else:
            return 0


    通过上述公式可以计算图的模块性,且模块性越高,该网络聚类成不同团体的程度越好,因此通过最优化方法寻找最大模块性就能发现聚类该网络的最佳方法。
    组合学告诉我们对于一个仅有8个顶点的网络,就存在4140种不同的聚类方式,16个顶点的网络的聚类方式将超过100亿种。32个顶点的网络的可能聚类方式更是将超过10^21种。因此,我们必须寻找一种启发式的方法使其不需要尝试每一种可能性。这种方法叫做Fast-Greedy Modularity-Maximization(快速贪婪模块性最大化)的算法,这种算法在一定程度上类似于上面描述的集聚层次聚类算法。只是这种算法不根据距离来融合团体,而是根据模块性的改变来对团体进行融合。
    具体步骤:
    1. 首先初始分配每个顶点到其自己的团体,然后计算整个网络的模块性 M。
    2. 第 1 步要求每个团体对(community pair)至少被一条单边链接,如果有两个团体融合到了一起,该算法就计算由此造成的模块性改变 ΔM。
    3. 第 2 步是取 ΔM 出现了最大增长的团体对,然后融合。然后为这个聚类计算新的模块性 M,并记录下来。
    4. 重复第 1 步和 第 2 步——每一次都融合团体对,这样最后得到 ΔM 的最大增益,然后记录新的聚类模式及其相应的模块性分数 M。
    5. 重复第 1 步和 第 2 步——每一次都融合团体对,这样最后得到 ΔM 的最大增益,然后记录新的聚类模式及其相应的模块性分数 M。


    ————————————————
    版权声明:本文为CSDN博主「诗蕊」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/Katherine_hsr/article/details/79382249

    展开全文
  • 各种聚类算法(原理+代码+对比分析)最全总结

    万次阅读 多人点赞 2020-05-26 15:52:19
    二、聚类算法分类 1.基于划分 给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K<N。 特点:计算量大。很适合发现中小规模的数据库中小规模的数据库中的球状簇。 算法:K-...

    序言

    还是要持续总结,持续积累。


    一、聚类的目标

    使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小。


    二、聚类算法分类

    1.基于划分

    给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K<N。
    特点:计算量大。很适合发现中小规模的数据库中小规模的数据库中的球状簇。
    算法:K-MEANS算法、K-MEDOIDS算法、CLARANS算法

    2.基于层次

    对给定的数据集进行层次似的分解,直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
    特点:较小的计算开销。然而这种技术不能更正错误的决定。
    算法:BIRCH算法、CURE算法、CHAMELEON算法

    3.基于密度

    只要一个区域中的点的密度大过某个阈值,就把它加到与之相近的聚类中去。
    特点:能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
    算法:DBSCAN算法、OPTICS算法、DENCLUE算法

    4.基于网格

    将数据空间划分成为有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象的。
    特点:处理速度很快,通常这是与目标数据库中记录的个数无关的,只与把数据空间分为多少个单元有关。
    算法:STING算法、CLIQUE算法、WAVE-CLUSTER算法

    三、DBscan聚类

    1.算法原理

    DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法,在DBSCAN算法中将数据点分为一下三类:
    核心点:在半径Eps内含有超过MinPts数目的点
    边界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内
    噪音点:既不是核心点也不是边界点的点
    在这里有两个量,一个是半径Eps,另一个是指定的数目MinPts
    这里写图片描述

    2.代码
    #  encoding=utf-8
    
    import numpy as np
    from sklearn.cluster import DBSCAN
    from sklearn import metrics
    from sklearn.datasets.samples_generator import make_blobs
    from sklearn.preprocessing import StandardScaler
    import matplotlib.pyplot as plt
    
    
    class DBScan (object):
        """
        the class inherits from object, encapsulate the  DBscan algorithm
        """
        def __init__(self, p, l_stauts):
            
            self.point = p
            self.labels_stats = l_stauts
            self.db = DBSCAN(eps=0.2, min_samples=10).fit(self.point)
    
        def draw(self):
         
            coreSamplesMask = np.zeros_like(self.db.labels_, dtype=bool)
            coreSamplesMask[self.db.core_sample_indices_] = True
            labels = self.db.labels_
            nclusters = jiangzao(labels)
    
            # 输出模型评估参数,包括估计的集群数量、均匀度、完整性、V度量、
            # 调整后的兰德指数、调整后的互信息量、轮廓系数
            print('Estimated number of clusters: %d' % nclusters)
            print("Homogeneity: %0.3f" % metrics.homogeneity_score(self.labels_stats, labels))
            print("Completeness: %0.3f" % metrics.completeness_score(self.labels_stats, labels))
            print("V-measure: %0.3f" % metrics.v_measure_score(self.labels_stats, labels))
            print("Adjusted Rand Index: %0.3f"
                  % metrics.adjusted_rand_score(self.labels_stats, labels))
            print("Adjusted Mutual Information: %0.3f"
                  % metrics.adjusted_mutual_info_score(self.labels_stats, labels))
            print("Silhouette Coefficient: %0.3f"
                  % metrics.silhouette_score(self.point, labels))
    
            # 绘制结果
            # 黑色被移除,并被标记为噪音。
            unique_labels = set(labels)
            colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
            for k, col in zip(unique_labels, colors):
                if k == -1:
                    # 黑色用于噪声
                    col = 'k'
    
                classMemberMask = (labels == k)
    
                # 画出分类点集
                xy = self.point[classMemberMask & coreSamplesMask]
                plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                         markeredgecolor='k', markersize=6)
    
                # 画出噪声点集
                xy = self.point[classMemberMask & ~coreSamplesMask]
                plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                         markeredgecolor='k', markersize=3)
            # 加标题,显示分类数
            plt.title('Estimated number of clusters: %d' % nclusters)
            plt.show()
    
    
    def jiangzao (labels):
        
        # 标签中的簇数,忽略噪声(如果存在)
        clusters = len(set(labels)) - (1 if -1 in labels else 0)
        return clusters
    
    def standar_scaler(points):
        
        p = StandardScaler().fit_transform(points)
        return p
    
    if __name__ == "__main__":
         """
         test class dbScan
         """
         centers = [[1, 1], [-1, -1], [-1, 1], [1, -1]]
         point, labelsTrue = make_blobs(n_samples=2000, centers=centers, cluster_std=0.4,
                                        random_state=0)
         point = standar_scaler(point)
         db = DBScan(point, labelsTrue)
         db.draw()
    
    3.图形输出

    这里写图片描述
    如图算法自动将数据集分成了4簇,用四种颜色代表。每一簇内较大的点代表核心对象,较小的点代表边界点(与簇内其他点密度相连,但是自身不是核心对象)。黑色的点代表离群点或者叫噪声点。

    4.控制台输出
    Estimated number of clusters: 4
    Homogeneity: 0.928
    Completeness: 0.862
    V-measure: 0.894
    Adjusted Rand Index: 0.928
    Adjusted Mutual Information: 0.862
    Silhouette Coefficient: 0.584
    

    四、K-means聚类

    1.算法原理

    这里写图片描述

    2.代码
    #coding=utf-8
    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.cluster import KMeans
    
    #从磁盘读取城市经纬度数据
    X = []
    f = open('city.txt')
    for v in f:
        X.append([float(v.split(',')[1]), float(v.split(',')[2])])
    #转换成numpy array
    X = np.array(X)
    #类簇的数量
    n_clusters = 5
    #现在把数据和对应的分类书放入聚类函数中进行聚类
    cls = KMeans(n_clusters).fit(X)
    #X中每项所属分类的一个列表
    cls.labels_
    #画图
    markers = ['^', 'x', 'o', '*', '+']
    for i in range(n_clusters):
      members = cls.labels_ == i
      plt.scatter(X[members, 0], X[members, 1], s=60, marker=markers[i], c='b', alpha=0.5)
    plt.title(' ')
    plt.show()
    
    3.图像输出

    这里写图片描述

    五、层次聚类

    1.算法简介

    凝聚层次聚类:所谓凝聚的,指的是该算法初始时,将每个点作为一个簇,每一步合并两个最接近的簇。另外即使到最后,对于噪音点或是离群点也往往还是各占一簇的,除非过度合并。对于这里的“最接近”,有下面三种定义。我在实现是使用了MIN,该方法在合并时,只要依次取当前最近的点对,如果这个点对当前不在一个簇中,将所在的两个簇合并就行:

    • 单链(MIN):定义簇的邻近度为不同两个簇的两个最近的点之间的距离。
    • 全链(MAX):定义簇的邻近度为不同两个簇的两个最远的点之间的距离。
    • 组平均:定义簇的邻近度为取自两个不同簇的所有点对邻近度的平均值。
    2.代码
    # scoding=utf-8
    # Agglomerative Hierarchical Clustering(AHC)
    import pylab as pl
    from operator import itemgetter
    from collections import OrderedDict,Counter
    points = [[int(eachpoint.split('#')[0]), int(eachpoint.split('#')[1])] for eachpoint in open("points","r")]
    # 初始时每个点指派为单独一簇
    groups = [idx for idx in range(len(points))]
    # 计算每个点对之间的距离
    disP2P = {}
    for idx1,point1 in enumerate(points):
      for idx2,point2 in enumerate(points):
        if (idx1 < idx2):
          distance = pow(abs(point1[0]-point2[0]),2) + pow(abs(point1[1]-point2[1]),2)
          disP2P[str(idx1)+"#"+str(idx2)] = distance
    # 按距离降序将各个点对排序
    disP2P = OrderedDict(sorted(disP2P.iteritems(), key=itemgetter(1), reverse=True))
    # 当前有的簇个数
    groupNum = len(groups)
    # 过分合并会带入噪音点的影响,当簇数减为finalGroupNum时,停止合并
    finalGroupNum = int(groupNum*0.1)
    while groupNum > finalGroupNum:
      # 选取下一个距离最近的点对
      twopoins,distance = disP2P.popitem()
      pointA = int(twopoins.split('#')[0])
      pointB = int(twopoins.split('#')[1])
      pointAGroup = groups[pointA]
      pointBGroup = groups[pointB]
      # 当前距离最近两点若不在同一簇中,将点B所在的簇中的所有点合并到点A所在的簇中,此时当前簇数减1
      if(pointAGroup != pointBGroup):
        for idx in range(len(groups)):
          if groups[idx] == pointBGroup:
            groups[idx] = pointAGroup
        groupNum -= 1
    # 选取规模最大的3个簇,其他簇归为噪音点
    wantGroupNum = 3
    finalGroup = Counter(groups).most_common(wantGroupNum)
    finalGroup = [onecount[0] for onecount in finalGroup]
    dropPoints = [points[idx] for idx in range(len(points)) if groups[idx] not in finalGroup]
    # 打印规模最大的3个簇中的点
    group1 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[0]]
    group2 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[1]]
    group3 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[2]]
    pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or')
    pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy')
    pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og')
    # 打印噪音点,黑色
    pl.plot([eachpoint[0] for eachpoint in dropPoints], [eachpoint[1] for eachpoint in dropPoints], 'ok')
    pl.show()
    
    3.图像输出

    这里写图片描述

    展开全文
  • 【聚类】五种主要聚类算法

    万次阅读 多人点赞 2018-08-22 22:07:11
    给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上,同一组中的数据点应该具有相似的属性和/或特征,而不同组中的数据点应该具有高度不同的属性和/或特征。聚类是一种无监督学习的方法,...

    原博文:

    聚类是一种机器学习技术,它涉及到数据点的分组。给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上,同一组中的数据点应该具有相似的属性和/或特征,而不同组中的数据点应该具有高度不同的属性和/或特征。聚类是一种无监督学习的方法,是许多领域中常用的统计数据分析技术。

    在数据科学中,我们可以使用聚类分析从我们的数据中获得一些有价值的见解。在这篇文章中,我们将研究5种流行的聚类算法以及它们的优缺点。

    K-MEANS聚类算法

    K-Means聚类算法可能是大家最熟悉的聚类算法。它出现在很多介绍性的数据科学和机器学习课程中。在代码中很容易理解和实现!请看下面的图表。

    K-Means聚类

    1.首先,我们选择一些类/组来使用并随机地初始化它们各自的中心点。要想知道要使用的类的数量,最好快速地查看一下数据,并尝试识别任何不同的分组。中心点是与每个数据点向量相同长度的向量,在上面的图形中是“X”。

    2.每个数据点通过计算点和每个组中心之间的距离进行分类,然后将这个点分类为最接近它的组。

    3.基于这些分类点,我们通过取组中所有向量的均值来重新计算组中心。

    4.对一组迭代重复这些步骤。你还可以选择随机初始化组中心几次,然后选择那些看起来对它提供了最好结果的来运行。

    K-Means聚类算法的优势在于它的速度非常快,因为我们所做的只是计算点和群中心之间的距离;它有一个线性复杂度O(n)。

    另一方面,K-Means也有几个缺点。首先,你必须选择有多少组/类。这并不是不重要的事,理想情况下,我们希望它能帮我们解决这些问题,因为它的关键在于从数据中获得一些启示。K-Means也从随机选择的聚类中心开始,因此在不同的算法运行中可能产生不同的聚类结果。因此,结果可能是不可重复的,并且缺乏一致性。其他聚类方法更加一致。

    K-Medians是另一种与K-Means有关的聚类算法,除了使用均值的中间值来重新计算组中心点以外,这种方法对离群值的敏感度较低(因为使用中值),但对于较大的数据集来说,它要慢得多,因为在计算中值向量时,每次迭代都需要进行排序。

    均值偏移聚类算法

    均值偏移(Mean shift)聚类算法是一种基于滑动窗口(sliding-window)的算法,它试图找到密集的数据点。而且,它还是一种基于中心的算法,它的目标是定位每一组群/类的中心点,通过更新中心点的候选点来实现滑动窗口中的点的平均值。这些候选窗口在后期处理阶段被过滤,以消除几乎重复的部分,形成最后一组中心点及其对应的组。请看下面的图表。

    单滑动窗口的均值偏移聚类

    1.为了解释这一变化,我们将考虑二维空间中的一组点(就像上面的例子)。我们从一个以点C(随机选择)为中心的圆形滑窗开始,以半径r为内核。均值偏移是一种爬山算法(hill climbing algorithm),它需要在每个步骤中反复地将这个内核移动到一个更高的密度区域,直到收敛。

    2.在每一次迭代中,滑动窗口会移向密度较高的区域,将中心点移动到窗口内的点的平均值(因此得名)。滑动窗口中的密度与它内部的点的数量成比例。自然地,通过移向窗口中点的平均值,它将逐渐向更高的点密度方向移动。

    3.我们继续根据均值移动滑动窗口,直到没有方向移动可以容纳内核中的更多点。看看上面的图表;我们一直在移动这个圆,直到我们不再增加密度(也就是窗口中的点数)。

    4.步骤1到3的过程是用许多滑动窗口完成的,直到所有的点都位于一个窗口内。当多个滑动窗口重叠的时候,包含最多点的窗口会被保留。然后,数据点根据它们所在的滑动窗口聚类。

    下面展示了从端到端所有滑动窗口的整个过程的演示。每个黑点代表一个滑动窗口的质心,每个灰色点都是一个数据点。

    均值偏移聚类的整个过程

    与K-Means聚类相比,均值偏移不需要选择聚类的数量,因为它会自动地发现这一点。这是一个巨大的优势。聚类中心收敛于最大密度点的事实也是非常可取的,因为它非常直观地理解并适合于一种自然数据驱动。缺点是选择窗口大小/半径r是非常关键的,所以不能疏忽。

    DBSCAN聚类算法

    DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法,类似于均值转移聚类算法,但它有几个显著的优点。

    DBSCAN笑脸聚类

    1.DBSCAN以一个从未访问过的任意起始数据点开始。这个点的邻域是用距离ε(所有在ε距离的点都是邻点)来提取的。

    2.如果在这个邻域中有足够数量的点(根据 minPoints),那么聚类过程就开始了,并且当前的数据点成为新聚类中的第一个点。否则,该点将被标记为噪声(稍后这个噪声点可能会成为聚类的一部分)。在这两种情况下,这一点都被标记为“访问(visited)”。

    3.对于新聚类中的第一个点,其ε距离附近的点也会成为同一聚类的一部分。这一过程使在ε邻近的所有点都属于同一个聚类,然后重复所有刚刚添加到聚类组的新点。

    4.步骤2和步骤3的过程将重复,直到聚类中的所有点都被确定,就是说在聚类附近的所有点都已被访问和标记。

    5.一旦我们完成了当前的聚类,就会检索并处理一个新的未访问点,这将导致进一步的聚类或噪声的发现。这个过程不断地重复,直到所有的点被标记为访问。因为在所有的点都被访问过之后,每一个点都被标记为属于一个聚类或者是噪音。

    DBSCAN比其他聚类算法有一些优势。首先,它不需要一个预设定的聚类数量。它还将异常值识别为噪声,而不像均值偏移聚类算法,即使数据点非常不同,它也会将它们放入一个聚类中。此外,它还能很好地找到任意大小和任意形状的聚类。

    DBSCAN的主要缺点是,当聚类具有不同的密度时,它的性能不像其他聚类算法那样好。这是因为当密度变化时,距离阈值ε和识别邻近点的minPoints的设置会随着聚类的不同而变化。这种缺点也会出现在非常高维的数据中,因为距离阈值ε变得难以估计。

    使用高斯混合模型(GMM)的期望最大化(EM)聚类

    K-Means的一个主要缺点是它对聚类中心的平均值的使用很简单幼稚。我们可以通过看下面的图片来了解为什么这不是最好的方法。在左边看起来很明显的是,有两个圆形的聚类,不同的半径以相同的平均值为中心。K-Means无法处理,因为聚类的均值非常接近。在聚类不是循环的情况下,K-Means也会失败,这也是使用均值作为聚类中心的结果。

    K-Means的两个失败案例

    高斯混合模型(GMMs)比K-Means更具灵活性。使用高斯混合模型,我们可以假设数据点是高斯分布的;比起说它们是循环的,这是一个不那么严格的假设。这样,我们就有两个参数来描述聚类的形状:平均值和标准差!以二维的例子为例,这意味着聚类可以采用任何形式的椭圆形状(因为在x和y方向上都有标准差)。因此,每个高斯分布可归属于一个单独的聚类。

    为了找到每个聚类的高斯分布的参数(例如平均值和标准差)我们将使用一种叫做期望最大化(EM)的优化算法。看看下面的图表,就可以看到高斯混合模型是被拟合到聚类上的。然后,我们可以继续进行期望的过程——使用高斯混合模型实现最大化聚类。

    使用高斯混合模型来期望最大化聚类

    1.我们首先选择聚类的数量(如K-Means所做的那样),然后随机初始化每个聚类的高斯分布参数。通过快速查看数据,可以尝试为初始参数提供良好的猜测。注意,在上面的图表中可以看到,这并不是100%的必要,因为高斯开始时的表现非常不好,但是很快就被优化了。

    2.给定每个聚类的高斯分布,计算每个数据点属于特定聚类的概率。一个点离高斯中心越近,它就越有可能属于那个聚类。这应该是很直观的,因为有一个高斯分布,我们假设大部分的数据都离聚类中心很近。

    3.基于这些概率,我们为高斯分布计算一组新的参数,这样我们就能最大程度地利用聚类中的数据点的概率。我们使用数据点位置的加权和来计算这些新参数,权重是属于该特定聚类的数据点的概率。为了解释这一点,我们可以看一下上面的图,特别是黄色的聚类作为例子。分布在第一次迭代中是随机的,但是我们可以看到大多数的黄色点都在这个分布的右边。当我们计算一个由概率加权的和,即使在中心附近有一些点,它们中的大部分都在右边。因此,自然分布的均值更接近于这些点。我们还可以看到,大多数点都是“从右上角到左下角”。因此,标准差的变化是为了创造一个更符合这些点的椭圆,从而使概率的总和最大化。

    步骤2和3被迭代地重复,直到收敛,在那里,分布不会从迭代到迭代这个过程中变化很多。

    使用高斯混合模型有两个关键的优势。首先,高斯混合模型在聚类协方差方面比K-Means要灵活得多;根据标准差参数,聚类可以采用任何椭圆形状,而不是局限于圆形。K-Means实际上是高斯混合模型的一个特例,每个聚类在所有维度上的协方差都接近0。其次,根据高斯混合模型的使用概率,每个数据点可以有多个聚类。因此,如果一个数据点位于两个重叠的聚类的中间,通过说X%属于1类,而y%属于2类,我们可以简单地定义它的类。

    层次聚类算法

    层次聚类算法实际上分为两类:自上而下或自下而上。自下而上的算法在一开始就将每个数据点视为一个单一的聚类,然后依次合并(或聚集)类,直到所有类合并成一个包含所有数据点的单一聚类。因此,自下而上的层次聚类称为合成聚类或HAC。聚类的层次结构用一棵树(或树状图)表示。树的根是收集所有样本的唯一聚类,而叶子是只有一个样本的聚类。在继续学习算法步骤之前,先查看下面的图表。

    合成聚类

    1.我们首先将每个数据点作为一个单独的聚类进行处理。如果我们的数据集有X个数据点,那么我们就有了X个聚类。然后我们选择一个度量两个聚类之间距离的距离度量。作为一个示例,我们将使用平均连接(average linkage)聚类,它定义了两个聚类之间的距离,即第一个聚类中的数据点和第二个聚类中的数据点之间的平均距离。

    2.在每次迭代中,我们将两个聚类合并为一个。将两个聚类合并为具有最小平均连接的组。比如说根据我们选择的距离度量,这两个聚类之间的距离最小,因此是最相似的,应该组合在一起。

    3.重复步骤2直到我们到达树的根。我们只有一个包含所有数据点的聚类。通过这种方式,我们可以选择最终需要多少个聚类,只需选择何时停止合并聚类,也就是我们停止建造这棵树的时候!

    层次聚类算法不要求我们指定聚类的数量,我们甚至可以选择哪个聚类看起来最好。此外,该算法对距离度量的选择不敏感;它们的工作方式都很好,而对于其他聚类算法,距离度量的选择是至关重要的。层次聚类方法的一个特别好的用例是,当底层数据具有层次结构时,你可以恢复层次结构;而其他的聚类算法无法做到这一点。层次聚类的优点是以低效率为代价的,因为它具有O(n³)的时间复杂度,与K-Means和高斯混合模型的线性复杂度不同。

    展开全文
  • [552]python实现聚类算法(6种算法)

    万次阅读 多人点赞 2019-12-14 19:32:44
    1、Mean-shift 1)概述 Mean-shift(即:均值迁移)的基本思想:在数据集中选定一个点,然后以这个点为圆心,r为半径,画一个圆(二维下是圆),求出这个点到所有点的向量的平均值,而圆心与向量均值的和为新的圆心,...
  • 聚类之详解FCM算法原理及应用

    万次阅读 多人点赞 2020-09-24 11:12:09
    模糊C均值(Fuzzy C-means)算法简称FCM算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。理论成熟,应用广泛,是一种优秀的聚类算法。本文关于FCM算法的一些原理推导部分介绍等参考下...
  • 高维数据的聚类算法

    万次阅读 多人点赞 2019-02-27 15:04:07
     聚类算法是人工智能、数据挖掘等领域的关键技术之一,有着广泛的应用。随着大数据时代的到来,产生了大量不一致数据、混合类型数据和部分值缺失的数据等。典型的聚类算法对这些数据集聚类时遇到难题。...
  • 四种聚类算法

    万次阅读 多人点赞 2016-05-22 16:09:04
    聚类分析是一种重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如用于模式识别、数据分析、图像处理、市场...
  • 聚类及聚类算法的分类

    万次阅读 多人点赞 2018-09-05 15:49:44
    一、聚类 1、聚类概念 聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的...
  • Kmeans聚类算法详解

    万次阅读 多人点赞 2020-04-14 12:35:50
    摘要:本文通过图文详细介绍Kmeans聚类算法的原理和程序实现,以及如何选取类簇中心点。本文首先介绍利用该算法的原理及理解,详细介绍基于MATLAB设计一个自定义的Kmeans函数过程,然后利用该函数对UCI的数据集进行...
  • k-means聚类算法原理简析

    万次阅读 多人点赞 2019-01-26 23:06:44
    k-means聚类算法原理简介概要算法思想算法流程图解代码实现 概要 K-means算法是最普及的聚类算法,也是一个比较简单的聚类算法,所以刚接触的同学不要感到害怕。算法接受一个未标记的数据集,然后将数据聚类成不同...
  • 聚类算法

    千次阅读 2018-10-05 23:36:49
    1 聚类简述  聚类就是按照某个特定标准(如距离准则,即数据点之间的距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。我们...
  • Affinity Propagation (AP) 聚类是最近在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的 进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即两个...
  • 常见聚类算法总结

    万次阅读 2018-09-07 18:24:42
    常见聚类算法总结 1.常见算法 1.原型聚类 “原型”是指样本空间中具有代表性的店。此类算法假设聚类结构能够通过一组原型刻画,通常情形下,算法先对原型进行初始化,然后对原型进行迭代更新求解。–西瓜书 ...
  • K-means聚类算法和模糊C-means聚类算法

    万次阅读 多人点赞 2020-06-23 21:33:42
    K-means聚类算法和模糊C-means聚类算法 1.K-means聚类算法 K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代...
  • 各种聚类算法的系统介绍和比较

    万次阅读 多人点赞 2017-11-16 08:42:54
    一、简要介绍1、聚类概念聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的...
  • 1. 典型聚类算法 1.1 基于划分的方法 代表:kmeans算法 ·指定k个聚类中心 ·(计算数据点与初始聚类中心的距离) ·(对于数据点,找到最近的{i}ci(聚类中心),将分配到{i}ci中) ·(更新聚类中心点,是新类别...
  • 浅谈AP聚类算法-matlab

    万次阅读 热门讨论 2020-10-21 19:28:43
    AP(Affinity Propagation)算法,称为仿射传播聚类算法、近邻传播聚类算法、亲和传播聚类算法,是根据数据点之间的相似度来进行聚类,可以是对称的,也可以是不对称的。 该算法不需要先确定聚类的数目,而是把所有的...
  • 聚类算法——近邻聚类算法

    千次阅读 2018-02-04 21:03:05
    每篇一句: Time is always too short for those who need it, ... 近邻聚类法同样是一种基于距离阈值的聚类算法。问题:有N个待分类的模式{X1,X2,…,Xn},要求按距离阈值T分类到以Z1,Z2,…为聚类中心的模式类中。
  • 数据挖掘——常用聚类算法总结

    千次阅读 多人点赞 2019-06-24 17:20:30
    概述 数据挖掘常又被称为价值发现或者是数据勘探,一般是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用...聚类算法 聚类是在一群未知类别标号的样本上,用某种算法将他们分成若干类别,这是一种无监督学...
1 2 3 4 5 ... 20
收藏数 96,194
精华内容 38,477
关键字:

聚类算法