聚类_聚类分析 - CSDN
聚类 订阅
将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。在数据挖掘中,聚类也是很重要的一个概念。 展开全文
将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。在数据挖掘中,聚类也是很重要的一个概念。
信息
定    义
将物理或抽象对象的集合分成
对象相异
物以类聚,人以群分
中文名
聚类
群分析
聚类分析
聚类典型应用
“聚类的典型应用是什么?”在商务上,聚类能帮助市场分析人员从客户基本库中发现不同的客户群,并且用购买模式来刻画不同的客户群的特征。在生物学上,聚类能用于推导植物和动物的分类,对基因进行分类,获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定,汽车保险单持有者的分组,及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类,以发现信息。
收起全文
  • 各种聚类算法(原理+代码+对比分析)最全总结

    万次阅读 多人点赞 2020-05-26 15:52:19
    一、聚类的目标 使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小。 二、聚类算法分类 1.基于划分 给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K<N...

    序言

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


    一、聚类的目标

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


    二、聚类算法分类

    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.图像输出

    这里写图片描述

    展开全文
  • 聚类介绍五个类型相似度、距离计算1. 距离2.相似度额外知识K-means算法原理计算步骤优缺点优点缺点DBSCAN算法一些概念算法步骤优缺点优点缺点密度最大值聚类DPCA概念聚类过程计算关键点 介绍 聚类算法对大量未标注...

    介绍

    聚类算法对大量未标注数据,按照数据的内在相似性将数据集划分为多个类别,一种无监督算法。
    /N个对象,K个簇,K<=NK<=N

    五个类型

    • 基于分层的聚类(hierarcal methods)
      思想:对数据集进行逐层,直到某条件满足为止。
      自下而上的分裂型和合并型
      代表:BIRCH、CURE、CHAMELEON

    • 基于划分的聚类 (partitioning methods)
      思想:给定K值,给出一个初始分组方法,然后反复迭代改变分组
      标准:同一分组的记录越近越好,不同分组的记录越远越好
      代表:k=-means, k-medoids、CLARANS

    • 基于密度的聚类(density-based methods)
      思想:不是基于距离,而是基于密度,克服距离算法只能发现“类圆形”的缺点。只要一个区域的点的密度大于某个阈值,就把它加到与之相近的聚类中。
      代表:DBSCAN、OPTICS、DENCLUE

    • 基于网格的聚类(grid-based methods)
      思想:把数据空间划分为有限个单元的网格结构,所有处理都以单个单元为对象。
      优点:处理速度很快,只与有多少个单元有关
      代表:STING、CLIQUE、WaveCluster

    • 基于模型的聚类(model-based methods)
      思想:给每个聚类假定一个模型,去找能够满足这个模型的数据集。
      潜在假设:目标数据集是由一系列的概率分布所决定
      两个尝试方案:统计方法和神经网络

    相似度、距离计算

    1. 距离

    在n维空间中,由两个向量X=(x1,x2,..,xn)TX=(x_1,x_2,..,x_n)^TY=(y1,y2,..,yn)TY=(y_1,y_2,..,y_n)^T,它们之间的距离反映两者的相似度,一般采用LpL_p距离

    dist(X,Y)=(i=1nxiyiP)1pdist(X,Y) = (\sum_{i=1}^{n} |x_i - y_i|^P)^{\frac{1}{p}}

    p1p\ge1,我们称其为闵可夫斯基距离(Minkowski)距离

    • p=1,曼哈顿距离
      在这里插入图片描述
    • p=2,欧几里得距离
      在这里插入图片描述
    • p=+p=+\infty,最大值距离
      在这里插入图片描述

    2.相似度

    在这里插入图片描述

    额外知识

    在这里插入图片描述

    • 余弦相似度的细节公式:
      在这里插入图片描述
    • pearson系数
      在这里插入图片描述
      相关系数就是把向量各自平移到原点后的夹角余弦

    K-means算法

    原理

    每一次迭代都确定K个类别中心,将数据点归到与之距离最近的中心点所在的簇,将类别中心更新为它的簇中所有样本的均值,反复迭代,直到类别中心不再变化或小于某个阈值

    存在的基本假设:
    我们认为可以选到一个中心点,使得cluster中所有点到该点的距离小于到其他cluster中心的距离。但是现实可能存在一些问题本身不可分,例如两个分布有重叠的部分,通常我们会选左边的分布,即使左右两边概率相等。

    计算步骤

    1. 选择初始K个类别中心μk\mu_k,选取方法可以针对具体问题或者采用随机方法,初始值对收敛到全局最优解有很大关系,通常我们会试多个K值。
    2. 对于每个样本x,找到距离最近的cluster中心,标记为此类别
      在这里插入图片描述
    3. 将类别中心更新为所有样本均值
      在这里插入图片描述
    4. 重复2、3步骤,直到类别中心变化小于某阈值,或者达到最大迭代次数

    优缺点

    优点

    • 简单、快速、经典
    • 处理大数据集时,保持可伸缩性和高效率
    • 当簇近似高斯分布时,它的效果较好

    缺点

    • 簇的平均值可被定义才能使用,不适合某些应用
    • 必须事先定K值,对初值敏感
    • 只能发现球状cluster,不适合非凸形状的簇,或者大小差别很大的簇
    • 对噪声和孤立点数据敏感,导致均值偏离严重(K-mediods改善这个问题,修改均值为中位数)

    DBSCAN算法

    此为密度聚类方法,为了克服基于距离算法只能发现凸的聚类的缺点,可以发现任意形状聚类,且对噪声数据不敏感。只要样本点密度大于某个阈值,可以把样本添加到最近的簇中。
    但是计算复杂度较大,需要建立空间索引来降低计算量。

    一些概念

    • 全名:Density-Based Spatial Clustering of Applications with Noise
    • 对象的 ε\varepsilon领域:给定对象在半径ε\varepsilon内的区域
    • 核心对象:给定数目m,若一个对象的领域至少包含m个对象,则称为该该对象的核心对象
    • 直接密度可达:一个对象集合D,如果p时在q的ε\varepsilon领域内,而q是一个核心对象,可以说对象p从对象q出发时直接密度可达。直观的说就是两个cluster重叠了
    • 密度可达:一条对象链,有一个对象p是从对象q和m密度可达的,衔接过去。
    • 密度相连:对象集合D中存在一个对象O,使得对p和q是从O关于ε\varepsilon和m密度可达的,那么对象p和q关于ε\varepsilon和m密度相连
    • 噪声,不包含在任何簇中的对象
    • 簇:最大的密度相连对象的集合

    算法步骤

    在这里插入图片描述

    1. 随机选择一个点A,设置ε\varepsilon区域为半径区域,对象个数m为4,A点的区域有4个,所以A作为核心对象创建新簇,其他点标记为边缘点。
    2. 在边缘点上选取一个重复上面的步骤,寻找并合并核心对象直接密度可达的对象。反复上面过程,直到没有新的点可以更新簇,算法结束。形成以A为初始的一个簇,包括红点和黄点。
    3. 如果发现还有一些数据点未处理,再次产生一个类别来重启这个算法,遍历所有数据,若此点不是边缘点也不是中心点,标记为噪音。

    优缺点

    优点

    • 无需确定聚类个数
    • 可以发现任何形状的聚类
    • 对噪声有鲁棒性,可有效处理噪声
    • 只需要两个参数,对数据输入顺序不敏感
    • 加快区查询
    • 参数可由领域专家设置

    缺点

    • 边界点不完全确定性
    • 维度灾难导致Euclidean距离度量失效
    • 不能处理密度差异过大(密度不均匀)的聚类
    • 参数选择在数据与规模不能很好理解的情况下,很难选择,选取不当容易导致聚类质量下降

    密度最大值聚类DPCA

    克服DBSCAN中不同类的密度差别大,领域范围难以设定的问题。
    Density Peaks Clustering Algorithm基于一种假设:对于数据集,聚类中心被一些低局部密度的数据点包围,而这些点距离其他由高局部密度的点的距离都比较大

    概念

    • 局部密度
      在这里插入图片描述
      dcd_c为截断距离,pip_i就是离对象ii的距离小于dcd_c的对象个数

    • 高局部密度点距离
      在这里插入图片描述
      局部密度高于对象ii的所有对象中,到对象ii的最近距离

    聚类过程

    1. 计算每一个点的局部密度
    2. 对每一个点ii计算在局部密度高于对象ii的所有对象中,到对象ii的最近距离
    3. 对每一个点,绘制局部密度与高局部密度点距离的关系散点图
      在这里插入图片描述
    4. 图中异常点为簇中心,1和10的局部密度和高局部密度距离都很大,将其作为中心
    5. 将其他的点分配给距离其最近的有着更高的局部密度的簇
    6. 26、27、28的高局部密度点距离比较大,但局部密度比较小,所以是异常点。
      在这里插入图片描述

    计算关键点

    那些有着⽐较⼤的局部密度ρi 和很⼤的⾼局部密度δi的点被认为是簇的中⼼; ⽽⾼局部
    密度距离δi较⼤但局部密度ρi 较⼩的点是异常点;

    对于那些在决策图中⽆法⽤⾁眼判断出聚类中⼼的情形,给出了⼀种确定聚类中⼼个数的提醒:计算⼀个将ρ值和δ值综合考虑的量:
    γi=ρiδi\gamma_i = \rho_i \delta_i

    显然γ值越⼤,越有可能是聚类中⼼。

    • ⼀种推荐做法是选择dcd_c,使得平均每个点的邻居数为所有点的1%~2%。

    评价标准

    轮廓系数silhouette

    对于一个样本集合,它的轮廓系数是所有样本轮廓系数的平均值。
    轮廓系数取值范围是[−1,1],同类别样本越距离相近且不同类别样本距离越远,分数越高。
    轮廓系数最高的簇的数量表示簇的数量的最佳选择
    一般来说,平均轮廓系数越高,聚类的质量也相对较好
    适用于实际类别信息未知的情况
    s=bamax(a,b)s=\frac{b−a}{max(a,b)}

    兰德系数

    兰德指数(Rand index)需要给定实际类别信息C,假设K是聚类结果,a表示在C与K中都是同类别的元素对数,b表示在C与K中都是不同类别的元素对数,则兰德指数为:

    RI=a+bC2nsamplesRI=\frac{a+b}{C_{2}^{nsamples}}

    分母部分指的是数据集中可以组成的总元素对数。RI取值范围为[0,1],值越大意味着聚类结果与真实情况越吻合。
    还有ARI,这里不阐述,可以去搜索了解一下,都是描述两个数据分布的吻合度

    互信息

    也是用来衡量两个数据分布的吻合程度

    Calinski-Harabaz Index

    在这里插入图片描述
    也是值越大,效果越好。类别内部数据的协方差越小越好,类别之间的协方差越大越好,这样的Calinski-Harabasz分数会高。

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

    千次阅读 2018-03-25 11:27:27
    转载自:... 1. K-Means(K均值)聚类 算法步骤: (1) 首先我们选择一些类/组,并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这...

    转载自:https://blog.csdn.net/Katherine_hsr/article/details/79382249



    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个网站,根据他们的维基百科页面中的链接进行了连接。
    这里写图片描述
    模块性可以使用以下公式进行计算:
    M=12L&#x2211;i,j=1N(Aij&#x2212;kiKj2L)&#x03B4;Ci,Cj” role=”presentation”>M=12LNi,j=1(AijkiKj2L)δCi,CjM=12L∑i,j=1N(Aij−kiKj2L)δCi,Cj
    其中L代表网络中边的数量,Aij” role=”presentation” style=”position: relative;”>AijAij很小的时候,其返回值最高。也就是说,当在定点i和j之间存在一个非预期边是得到的值更高。
    &#x03B4;Ci,Cj” role=”presentation” style=”position: relative;”>δCi,CjδCi,Cj函数(Kronecker-delta function). 下面是其Python解释:

    def Kronecker_Delta(ci,cj):
        if ci==cj:
            return 1
        else:
            return 0
    • 1
    • 2
    • 3
    • 4
    • 5

    通过上述公式可以计算图的模块性,且模块性越高,该网络聚类成不同团体的程度越好,因此通过最优化方法寻找最大模块性就能发现聚类该网络的最佳方法。
    组合学告诉我们对于一个仅有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。

    展开全文
  • 四种主流聚类方法

    万次阅读 多人点赞 2016-02-06 16:31:51
    四种聚类方法之比较 2015-07-29 SOTON数据分析 聚类分析是一种重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功...

    四种主流聚类方法

    2015-07-29 

           聚类就是按照某个特定标准(如距离准则,即数据点之间的距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。我们可以具体地理解为,聚类后同一类的数据尽可能聚集到一起,不同类数据尽量分离。
           聚类技术[2]正在蓬勃发展,对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进,而不同的方法适合于不同类型的数据,因此对各种聚类方法、聚类效果的比较成为值得研究的课题。

           本篇博文面向对聚类方法具有入门知识,但是没有总结对比过的朋友们。


    1 聚类算法的分类
           目前,有大量的聚类算法[3]。而对于具体应用,聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具,可以对同样的数据尝试多种算法,以发现数据可能揭示的结果。
           主要的聚类算法可以划分为如下几类:划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[4-6]。
           目前,聚类问题的研究不仅仅局限于上述的硬聚类,即每一个数据只能被归为一类,模糊聚类[10]也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶属函数来确定每个数据隶属于各个簇的程度,而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出,如著名的FCM算法等,此方法后面会提及。

    2 四种常用聚类算法研究


    2.1 k-means聚类算法

           k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。
           k-means算法目标是,以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。

           k-means算法的处理过程如下:首先,随机地 选择k个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如下:
     
          这里E是数据库中所有对象的平方误差的总和,p是空间中的点,mi是簇Ci的平均值[9]。该目标函数使生成的簇尽可能紧凑独立,使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下:
    输入:包含n个对象的数据库和簇的数目k;
    输出:k个簇,使平方误差准则最小。
    步骤:
      (1) 任意选择k个对象作为初始的簇中心;
      (2) repeat;
      (3) 根据簇中对象的平均值,将每个对象(重新)赋予最类似的簇;
      (4) 更新簇的平均值,即计算每个簇中对象的平均值;
      (5) until不再发生变化。

    总结:

           优点:简单直接(体现在逻辑思路以及实现难度上),易于理解,在低维数据集上有不错的效果(简单的算法不见得就不能得到优秀的效果)。

           缺点:对于高维数据(如成百上千维,现实中还不止这么多),其计算速度十分慢,主要是慢在计算距离上(参考欧几里得距离,当然并行化处理是可以的,这是算法实现层面的问题),它的另外一个缺点就是它需要我们设定希望得到的聚类数k,若我们对于数据没有很好的理解,那么设置k值就成了一种估计性的工作。


    2.2 层次聚类算法
           根据层次分解的顺序是自底向上的还是自上向下的,层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。
           凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下:

    这里给出采用最小距离的凝聚层次聚类算法流程:
     (1) 将每个对象看作一类,计算两两之间的最小距离;
     (2) 将距离最小的两个类合并成一个新类;
     (3) 重新计算新类与所有类之间的距离;
     (4) 重复(2)、(3),直到所有类最后合并成一类。

    总结:

           优点:1,距离和规则的相似度容易定义,限制少;2,不需要预先制定聚类数;3,可以发现类的层次关系(在一些特定领域如生物有很大作用);

           缺点:1,计算复杂度太高(考虑并行化);2,奇异值也能产生很大影响;3,算法很可能聚类成链状(一层包含着一层);4,算法不需要预定聚类数,但是我们选择哪个层次的聚类作为我们需要的聚类效果,这需要我们按照实际客观情况以及经验来完成,毕竟就凝聚聚类来说,从最底层的每个个体作为一个个体,到最顶层所有个体合并为一个个体,其中的聚类结果可能有许许多多种。当然针对这个问题也有许多解决方案,其中一个常用的就是凝聚到某个程度其聚类之间的距离都大于某个阈值k,就停止凝聚。



    2.3 SOM聚类算法
           SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的,该算法假设在输入对象中存在一些拓扑结构或顺序,可以实现从输入空间(n维)到输出平面(2维)的降维映射,其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。
           SOM网络包含输入层和输出层。输入层对应一个高维的输入向量,输出层由一系列组织在2维网格上的有序节点构成,输入节点与输出节点通过权重向量连接。 学习过程中,找到与之距离最短的输出层单元,即获胜单元,对其更新。同时,将邻近区域的权值更新,使输出节点保持输入向量的拓扑特征。
     算法流程:
     (1) 网络初始化,对输出层每个节点权重赋初值;
     (2) 将输入样本中随机选取输入向量,找到与输入向量距离最小的权重向量;
     (3) 定义获胜单元,在获胜单元的邻近区域调整权重使其向输入向量靠拢;
     (4) 提供新样本、进行训练;
     (5) 收缩邻域半径、减小学习率、重复,直到小于允许值,输出聚类结果。


    2.4 FCM聚类算法
        1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展,模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点,出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析,就是模糊聚类分析[12]。
      FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。
     
    算法流程:
     (1) 标准化数据矩阵;
     (2) 建立模糊相似矩阵,初始化隶属矩阵;
     (3) 算法开始迭代,直到目标函数收敛到极小值;
     (4) 根据迭代结果,由最后的隶属矩阵确定数据所属的类,显示最后的聚类结果。

    总结:

        优点:相比起前面的”硬聚类“,FCM方法会计算每个样本对所有类的隶属度,这给了我们一个参考该样本分类结果可靠性的计算方法,我们可以这样想,若某样本对某类的隶属度在所有类的隶属度中具有绝对优势,则该样本分到这个类是一个十分保险的做法,反之若该样本在所有类的隶属度相对平均,则我们需要其他辅助手段来进行分类。

       缺点:KNN的缺点基本它都有。

    3 四种聚类算法试验
    3.1 试验数据

           实验中,选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集,IRIS数据集包含150个样本数据,分别取自三种不同 的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性,即萼片长度、萼片宽度、花瓣长度,单位为cm。 在数据集上执行不同的聚类算法,可以得到不同精度的聚类结果。
    3.2 试验结果说明
     文中基于前面所述各算法原理及算法流程,用matlab进行编程运算,得到表1所示聚类结果。


           如表1所示,对于四种聚类算法,按三方面进行比较:(1)聚错样本数:总的聚错的样本数,即各类中聚错的样本数的和;(2)运行时间:即聚类整个 过程所耗费的时间,单位为s;(3)平均准确度:设原数据集有k个类,用ci表示第i类,ni为ci中样本的个数,mi为聚类正确的个数,则mi/ni为 第i类中的精度,则平均精度为:
                                                                           


    3.3 试验结果分析
          四种聚类算法中,在运行时间及准确度方面综合考虑,k-means和FCM相对优于其他。但是,各个算法还是存在固定缺点:k-means聚类算法的初始点选择不稳定,是随机选取的,这就引起聚类结果的不稳定,本实验中虽是经过多次实验取的平均值,但是具体初始点的选择方法还需进一步研究;层次聚类虽然 不需要确定分类数,但是一旦一个分裂或者合并被执行,就不能修正,聚类质量受限制;FCM对初始聚类中心敏感,需要人为确定聚类数,容易陷入局部最优 解;SOM与实际大脑处理有很强的理论联系。但是处理时间较长,需要进一步研究使其适应大型数据库。


    参考文献
    [1] HAN Jia Wei, KAMBER M.数据挖掘概念与技术[M].范明,孟晓峰,译.北京:机械工业出版社,2001.
    [2] 杨小兵.聚类分析中若干关键技术的研究[D]. 杭州:浙江大学,2005.
    [3] XU Rui, Donald Wunsch 1 1. survey of clustering algorithm[J].IEEE.Transactions on Neural Networks, 2005,16(3):645-67 8.
    [4] YI Hong, SAM K. Learning assignment order of instances for the constrained k-means clustering algorithm[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics,2009,39 (2):568-574.
    [5] 贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007,24(1):10-13.
    [6] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
    [7] 孔英会,苑津莎,张铁峰,等.基于数据流管理技术的配变负荷分类方法研究.中国国际供电会议,CICED2006.
    [8] 马晓艳,唐雁.层次聚类算法研究[J].计算机科学,2008,34(7):34-36.
    [9] 汪海波,张海臣,段雪丽.基于MATLAB的自组织竞争神经网络聚类研究[J].邢台职业技术学院学报,2005,22(1):45-47.
    [10] 吕晓燕,罗立民,李祥生.FCM算法的改进及仿真实验研究[J].计算机工程与应用,2009,45(20):144-147.
    [11] 李戈,邵峰晶,朱本浩.基于神经网络聚类的研究[J].青岛大学学报,2001,16(4):21-24.
    [12] 戈国华,肖海波,张敏.基于FCM的数据聚类分析及matlab实现[J].福建电脑,2007,4:89-90.
    [13] FISHER R A. Iris Plants Database//http://www.ics.uci.edu/~mlearn /MLRepository.Html.Authorized license.

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

    万次阅读 多人点赞 2018-08-22 22:07:11
    聚类是一种机器学习技术,它涉及到数据点的分组。给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上,同一组中的数据点应该具有相似的属性和/或特征,而不同组中的数据点应该具有高度...
  • 数学基础-相关性和相似度度量

    千次阅读 2018-12-25 17:12:01
    许多数据分析算法会涉及相似性度量和相关性度量,如聚类、KNN等。 相关性度量 相关性用相关系数来度量,相关系数种类如下图所示。相关系数绝对值越大表是相关性越大,相关系数取值在-1–1之间,0表示不相关。各...
  • 常用相似性度量(距离 相似系数)

    千次阅读 2018-05-22 10:32:03
    在分类聚类算法,推荐系统中,常要用到两个输入变量(通常是特征向量的形式)距离的计算,即相似性度量.不同相似性度量对于算法的结果,有些时候,差异很大.因此,有必要根据输入数据的特征,选择一种合适的相似性度量方法.令...
  • 聚类中的相似性度量:以下方法适用于直接对raw data进行相似性的度量,或者对比提取features之后的dada的相似性。1:距离1)Lr norm距离: 如果是L1 norm,那就是绝对值/曼哈顿距离(Manhattan distance),d(i...
  • 相似性度量—聚类

    千次阅读 2007-07-27 22:38:00
    图像分割与特征提取相似性度量—聚类 前面介绍的分类问题是利用已知类别的样品来构造分类器。其训练集样品是已知类别的,所以又称为有监督学习。在已知类别样品的指导下对单个待测样品进行分类。聚类问题则不同,它...
  • 海量数据相似性度量与聚类: LHS-MinHash   写本文的原因是近期在涉猎用户画像相关的无监督学习理论,刚好看到一篇运用LHS-MinHash做用户聚类的文章,却讲得过于笼统,对我这样的萌新(菜鸡)不太友好。于是我去...
  • 聚类聚类算法的分类

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

    万次阅读 多人点赞 2020-07-14 10:42:57
    说到聚类,应先理解聚类和分类的区别,很多业务人员在日常分析时候不是很严谨,混为一谈,其实二者有本质的区别。 分类:分类其实是从特定的数据中挖掘模式,作出判断的过程。比如Gmail邮箱里有垃圾邮件分类器,...
  • 所谓聚类,就是将相似的事物聚集在一 起,而将不相似的事物划分到不同的类别的过程,是数据分析之中十分重要的一种手段。比如古典生物学之中,人们通过物种的形貌特征将其分门别类,可以说就是 一种朴素的人工聚类。...
  • 让你看懂聚类分析

    万次阅读 多人点赞 2017-12-28 19:53:10
    聚类分析概述 2.各种距离的定义 2.1 样本相似性度量 2.2 类与类间的相似性度量 2.3 变量间的相似度度量 3.划分聚类 4.层次聚类 1.聚类分析概述 聚类分析是一种定量方法,从数据分析的角度看,它是对多个样本...
  • 深入理解K-Means聚类算法

    万次阅读 多人点赞 2016-12-18 20:50:05
    概述什么是聚类分析聚类分析是在数据中发现数据对象之间的关系,将数据进行分组,组内的相似性越大,组间的差别越大,则聚类效果越好。不同的簇类型聚类旨在发现有用的对象簇,在现实中我们用到很多的簇的类型,使用...
  • 之前一直用R,现在开始学python之后就来...有三类比较常见的聚类模型,K-mean聚类、层次(系统)聚类、最大期望EM算法。在聚类模型建立过程中,一个比较关键的问题是如何评价聚类结果如何,会用一些指标来评价。 ....
  • Kmeans聚类算法详解

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

    万次阅读 2018-04-30 01:13:32
    一、原型聚类和层次聚类原型聚类也称基于原型的聚类(prototype-based clustering),这类算法假设聚类结构能够通过一组原型刻画,先对原型进行初始化,然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解...
  • 聚类系列-层次聚类(Hierarchical Clustering)

    万次阅读 多人点赞 2017-03-23 16:09:17
    上篇k-means算法却是一种方便好用的聚类算法,但是始终有K值选择和初始聚类中心点选择的问题,而这些问题也会影响聚类的效果。为了避免这些问题,我们可以选择另外一种比较实用的聚类算法-层次聚类算法。顾名思义,...
  • 一、系统聚类 选中系统聚类并把变量移入变量框内,聚类选择按照个案聚类 在Display栏中选择Statistics和Plots复选框,这样在结果输出窗口中可以同时得到聚类结果统计量和统计图。 选中绘图中的谱系图 单击...
1 2 3 4 5 ... 20
收藏数 117,773
精华内容 47,109
关键字:

聚类