精华内容
下载资源
问答
  • 层次聚类算法
    千次阅读
    2018-09-04 15:08:58

    首先介绍聚类中的层次聚类算法。层次法又分为凝聚的层次聚类和分裂的层次聚类。

      凝聚的方法:也称自底向上的方法,首先将每个对象作为单独的一个聚类,然后根据性质和规则相继地合并相近的类,直到所有的对象都合并为一个聚类中,或者满足一定的终止条件。经典的层次凝聚算法以AGNES算法为代表,改进的层次凝聚算法主要以BIRCH,CURE,ROCK,CHAMELEON为代表。(后面详细介绍)

      分裂的方法:也称自顶向下的方法,正好与凝聚法相反,首先将所有的对象都看作是一个聚类,然后在每一步中,上层类被分裂为下层更小的类,直到每个类只包含一个单独的对象,或者也满足一个终止条件为止。分裂算法将生成与凝聚方法完全相同的类集,只是生成过程的次序完全相反。经典的层次分裂算法以DIANA算法为代表。

      AGNES算法

    AGNES(AGglomerative NESting)

    • 算法最初将每个对象作为一个簇,然后这些簇根据某些准则被一步步地合并
    • 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定
    • 聚类的合并过程反复进行直到所有的对象最终满足簇数目

    算法过程

    输入:n个对象,终止条件,簇的数目K

    输出:K个簇,达到终止条件规定簇数目

    1. 将每个对象当成一个初始簇
    2. 根据两个簇中最近的数据点找到最近的两个簇
    3. 合并两个簇,生成新的簇的集合
    4. 直到达到定义的簇的数目

    AGNES算法例题

    序号属性1属性2
    111
    212
    321
    422
    534
    635
    744
    845

     第1步:根据初始簇计算每个簇之间的距离,随机找出距离最小的两个簇进行合并,最小距离为1,合并后1,2两个点合并为一个簇。

     第2步:对上一次合并后的簇计算簇间距离,找出距离最近的两个簇进行合并,合并后3,4两个点成为一个簇,

     第3步:重复第2步,5,6点成为一个簇。

     第4步:重复第2步,7,8点成为一个簇。

     第5步:合并{1,2}、{3,4},使之成为一个包含4个点的簇。

     第6步:合并{5,6}、{7,8},由于合并后的簇的数目达到用户输入的终止条件,程序终止。

     

    步骤最近的簇距离最近的两个簇合并后的新簇
    11{1}、{2}{1、2}、{3}、{4}、{5}、{6}、{7}、{8}
    21{3}、{4}{1、2}、{3、4}、{5}、{6}、{7}、{8}
    31{5}、{6}{1、2}、{3、4}、{5、6}、{7}、{8}
    41{7}、{8}{1、2}、{3、4}、{5、6}、{7、8}
    51{1、2}、{3、4}{1、2、3、4}、{5、6}、{7、8}
    61{5、6}、{7、8} {1、2、3、4}、{5、6、7、8}

    AGNES特点:

    AGNES实现简单,但经常会遇到合并点难以选择的困难。若一旦一组对象被合并,下一步的处理将在新生成的簇上进行。已经做的处理不能撤销,聚类之间也不能交换对象。一步合并错误,可能会导致低质量的聚类结果。 

    层次凝聚改进算法之BIRCH算法

    转载了大牛的博客,在理解MinCluster时,个人觉得树图中最底一层的每一个椭圆形都是一个MinCluster,并不是一个Leaf的所有孩子为一个MinCluster。所以MinCluster的个数不会超过L个,与树图吻合。

    转自:http://www.kuqin.com/algorithm/20111016/312976.html 

      http://www.cnblogs.com/zhangchaoyang/articles/2200800.html

    层次凝聚改进算法之CURE算法

    绝大多数聚类算法或者擅长处理球形与相似大小的聚类,或者在存在孤立点时变得比较脆弱。CURE( Clustering Using Representatives)算法较好的解决了偏好球形和相似大小的问题,在处理孤立点上也更加健壮。CURE 算法采用了一种新颖的层次聚类算法,该算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇,而是选择数据空间中固定数目的具有代表性的点。每一个簇有多于一个的代表点使得 CURE 可以适应非球形的几何形状。簇的收缩或凝聚可以有助于控制孤立点的影响。因此,CURE 对于孤立点的处理更加好,而且能够识别非球形和大小变化较大的簇。对于大型数据库,它也具有良好的伸缩性,而且没有牺牲聚类质量。针对大型数据库,CURE 采用随机取样和划分两种方法的结合:一个随机样本首先被划分,每个划分被部分聚类。这些结果簇然后被聚类产生希望的结果。

    基本步骤:

    ⑴ 对数据库抽样,得到一个样本;
    ⑵ 将样本划分为 p 个分区,每个分区的规模为n/p。因为聚类首先在每个分区上进行,所以这样做可以起到加速算法的作用;
    ⑶ 对每一分区,利用层次算法进行聚类。这提供了关于簇的组成的首次猜测。簇的数目为 n/pq,其中 q为某一常数;
    ⑷ 删除异常点。利用两种不同的技术删除异常点。第一种技术是将增长缓慢的簇删除。当簇的数目低于某一阈值时,将仅含有一两个成员的簇删除。有可能较近的异常点会成为样本的一部分,而不能被第一种异常点删除技术识别出来。第二种技术是在聚类的最后阶段,将非常小的簇删除;
    ⑸ 为了保证可以在内存中处理,输入只包括在步骤 3 中各个分区独自聚类时发现的簇的代表性点;
    ⑹ 使用 c 个点代表每个簇,对磁盘上的整个数据库进行聚类。数据库中的数据项被分配到与其最近的
    代表性点表示的簇中。代表性点的集合必须足够小以适应主存的大小,所以 n 个点中的每一个都要与 ck 个代表性点相比较。

    层次凝聚改进算法之ROCK算法
    ROCK(Robust Clustering using links)算法采用一种新方法来计算相似形,即基于元组之间的连接数目。如果一对元组的相似形超过某一阈值,则称这一对元组为邻居。两个元组之间的连接数目由它们共同的邻居数目来定义。ROCK 属于层次凝聚算法,其相似性度量采用的是连接数目而不是距离的量度。首先数据库中的数据随机取出作为样本,使用“link”将数据进行聚类,最后将数据库中的其余数据指派到样本数据完成的簇中,得到最终的聚类结果。

    为了进一步了解ROCK算法,我们需要定义几个变量,并阐述这些变量的含义。

    定义1.Θ为使用者自定义的邻居阈值,相似度函数sim(pi,pj)>=Θ,其中sim(pi,pj)的相似度取值范围为[0,1],值越大表示越相似。

    定义2.pi,pj这两个数点的相似度采用Jaccard系数,则sim(pi,pj)=(pi∩pj)/(piUpj)。

    定义3.link pi¯,pj¯为集合Ni,Nj交叉连接数,其中Ni,Nj分别为pi,pj的邻居表。

    定义4.适合函数(goodness function)

    g(Ci,Cj)=link[Ci,Cj]/((ni+nj)1+2f(θ)-ni1+2f(θ)-nj1+2f(θ)),其中Ci,Cj是两个簇,ni,nj分别是两个簇中的点的数目,假设以Ci为参考点,每个点概略

    有nif(θ),专家选择的阈值是:f(θ)=(1-θ)/(1+θ)

    层次凝聚改进算法之Chameleon

    Chameleon采用动态建模来确定一对簇之间的相似度。

    在Chameleon中簇的相似度依据如下两点评估:

    1. 簇中对象的连接情况
    2. 簇的邻近性

    也就是说,如果两个簇的互连性都很高并且它们又很靠近就将其合并。

    Chameleon算法的思想是:

    • 首先使用一种图划分算法将k最近邻图划分成大量相对较小的子簇
    • 然后使用凝聚层次聚类算法,基于子簇的相似度反复地合并子簇
    • 为了确定最相似的子簇对,它既考虑每个子簇的互连性,又考虑簇的邻近性
    • 图划分算法划分k最近邻图,使得割边最小化。也就是说,簇C划分为两个子簇Ci,Cj时需要切断的加权和最小。割边用EC(Ci,Cj)表示,用于评估簇Ci,Cj之间的绝对互连性。

    图1 Chameleon工作过程图

    优点:Chameleon在发现高质量的任意形状的簇方面具有很强的能力。

    缺点:高维数据的处理代价较高,对n个对象最坏情况下需要O(n2)的时间。

    聚类算法层次分裂之DIANA

    算法思想:

    输入:n个对象,终止条件簇的数目k

    输出:k个簇,达到终止条件规定簇数目

    1. 将所有对象当成一个初始簇
    2. for(i=1;i≠k;i++) do begin
    3. 在所有簇中挑选出具有最大直径的簇C
    4. 找出C中与其它点平均相异度最大的一个点P并把P放入splinter group,剩余的放在old party中
    5. repeat
    6. 在old party中找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点,并将该点加入splinter group
    7. until没有新的old party的点被分配给spilnter group
    8. spilnter group和old party为被选中的簇分裂成的2个簇与其它簇一起组成新的簇集合
    9. end

    分裂的层次聚类算法一般较少使用。

    更多相关内容
  • 设计了一种基于统计的多层次分类算法 :在一个树状的层次分类体系中,对文档进行自动分类时,首先从根结点开始找到对应的大类,然后递归往下直到找到对应的最底层子类 。每一层中使用支持向量机作为分类模型,并使用类别...
  • 传统的知识库多层次标签分类算法分类精度低,为了解决这一问题,基于最临近模型的知识库研究一种新的多层次标签分类算法。该算法对知识库多层次标签进行特征提取,将提取的对象标签特征进行特征降维,以此获得简化...
  • 基于层次聚类的网络流量异常分类算法.pdf
  • 基于层次聚类的车辆模型数据分类算法
  • 基于YOLO v5与层次分类算法的生活垃圾识别研究.pdf
  • 本文主要侧重数据挖掘中分类算法的效果的对比,通过简单的实验(采用开源的数据挖掘工具-Weka)来验证不同的分类算法的效果,帮助数据挖掘新手认识不同的分类算法的特点,并且掌握开源数据挖掘工具的使用。分类算法...
  • 基于非迭代训练层次循环神经网络的快速文本分类算法.pdf
  • 基于层次聚类算法的静力触探试验土体分类方法及试验研究.pdf
  • 层次分类体系更合理地反映了页面的自然属性,也为设计更为高效的页面分类算法提供了方便。该算法与PageRank在在线计算复杂度方面完全一样,是非查询关键词相关的算法,能够高效地完成在线搜索,具有良好的可伸缩性。
  • 基于层次聚类的支持向量机分类算法.pdf
  • 基于Cloude-Pottier目标分解和聚合的层次聚类算法的全极化SAR数据的非监督分类算法研究.pdf
  • 一种基于量子机制的分类属性数据层次聚类算法.pdf
  • 层次聚类算法在空间数据分类上的研究及仿真.pdf
  • HCLOPE:一种处理分类数据的优化层次聚类算法.pdf
  • 目的 利用层次聚类与人工免疫模式识别相结合的方法解决无监督结构健康监测中对结构故障识别和分类的问题.方法 通过凝聚型层次聚类实现样本...结论 基于层次聚类和人工免疫的无监督结构故障检测与分类算法通过免疫学
  • 基于层次聚类算法的孔压静力触探土体分类方法及试验研究.pdf
  • 大数据-算法-基于层次分类与数据融合的星载激光雷达数据反演.pdf
  • 图像分类算法与应用 研究 报告人:张德园 导师:王晓龙教授 目录 研究背景 相关研究工作 已有工作基础 论文主要研究内容 课题来源 本课题来源于国家八六三计划目标导向类 课题基于LP的智能搜索引擎(项目编 号:2006AA01...
  • 同时,与音频信号所提取到的特征向量进行多模态数据融合,使用深度置信网络已有监督训练的方式,分析混合融合后的特征向量与音乐情感之间的联系,构建出基于特征词位置因素的音乐情感智能分类算法。测试与实验结果...
  • 基于遗传算法的非监督层次分类方法研究-基于遗传算法的非监督层次分类方法研究.pdf 基于遗传算法的非监督层次分类方法研究
  • 为利用开放分类进行百科条目的分类和检索, 提出了基于词共现和语义分析的开放分类聚类算法以及开放分类层次结构树构建方法; 为了进一步提高层次结构树的聚合度, 提出了基于相似度和相关度计算的层次结构树聚类算法。...
  • 中文网络百科开放分类层次结构树及其聚类算法研究.pdf
  • 层次聚类算法的实现

    多人点赞 2022-04-12 16:00:32
    层次聚类算法介绍2.1 层次聚类算法原理2.2 层次聚类算法步骤2.3 层次聚类算法分类3.层次聚类算法实现(代码如下)3.1 相关包导入3.2 生成测试数据集3.3 层次聚类实现&画出树状图3.4 获取聚类结果3.5 对比不同方法...

    1.作者介绍

    杨金花,女,西安工程大学电子信息学院,21级硕士研究生
    研究方向:基于学习方法的运动目标检测
    电子邮件:2902551510@qq.com

    孟莉苹,女,西安工程大学电子信息学院,2021级硕士研究生,张宏伟人工智能课题组
    研究方向:机器视觉与人工智能
    电子邮件:2425613875@qq.com

    2.层次聚类算法介绍

    2.1 层次聚类算法原理

     聚类就是对大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小。
     层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。算法流程展示如图所示。
    

    在这里插入图片描述

    2.2 层次聚类算法步骤

    假设有6个样本点{A,B,C,D,E,F},对于层次聚类来说,步骤如下:
    (1)假设每个样本点都为一个簇类,计算每个簇类间的相似度,得到相似矩阵;
    (2)寻找各个类之间最近的两个类,即若B和C的相似度最高,合并簇类B和C为一个簇类。现在我们还有五个簇类,分别为A,BC,D,E,F;
    (3)更新簇类间的相似矩阵,若簇类BC和D的相似度最高,合并簇类BC和D为一个簇类。现在我们还有四个簇类,分别为A,BCD,E,F;
    (4)更新簇类间的相似矩阵,若簇类E和F的相似度最高,合并簇类E和F为一个簇类。现在我们还有3个簇类,分别为A,BCD,EF。
    (5)重复第四步,簇类BCD和簇类EF的相似度最高,合并该两个簇类,现在我们还有2个簇类,分别为A,BCDEF。
    (6)最后合并簇类A和BCDEF为一个簇类,层次聚类算法结束。
    层次聚类实现过程如图2所示。

    图2. 层次聚类实现过程示例图

    2.3 层次聚类算法分类

    自顶向下的层次聚类算法(Divisive):
    Divisive 层次聚类:又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个cluster,每次按一定的准则将某个cluster 划分为多个cluster,如此往复,直至每个对象均属于某一个cluster。实现过程示意图如下。

    图3. Divisive实现过程示例图

    自底向上的层次聚类算法(Agglomerative):
    Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个cluster,每次按一定的准则将最相近的两个cluster合并生成一个新的cluster,如此往复,直至最终所有的对象都属于一个cluster。

    图4. Divisive实现过程示例图

    3.层次聚类算法实现(代码如下)

    3.1 相关包导入

    from scipy.cluster.hierarchy import linkage     #导入linage函数用于层次聚类
    from scipy.cluster.hierarchy import dendrogram  #dendrogram函数用于将聚类结果绘制成树状图
    from scipy.cluster.hierarchy import fcluster    #fcluster函数用于提取出聚类的结果
    from sklearn.datasets import make_blobs         #make_blobs用于生成聚类算法的测试数据
    from sklearn.cluster import AgglomerativeClustering  #自底向上层次聚类算法
    import matplotlib.pyplot as plt                 #导入matplotlib绘图工具包
    

    3.2 生成测试数据集

    #生成测试数据
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c='b')
    plt.show()
    #from scipy.cluster.hierarchy import linkage
    

    图5. 测试数据可视化展示

    3.3 层次聚类实现&画出树状图

    #层次聚类实现
    #from scipy.cluster.hierarchy import dendrogram
    Z = linkage(X,  method='ward', metric='euclidean')
    print(Z.shape)
    print(Z[: 5])
    
    #画出树状图
    #from scipy.cluster.hierarchy import fcluster
    plt.figure(figsize=(10, 8))
    dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15,
               show_contracted=True)
    plt.show()
    

    图6. 树状图可视化展示

    3.4 获取聚类结果

    #根据临界距离返回聚类结果
    d = 15
    labels_1 = fcluster(Z, t=d, criterion='distance')
    print(labels_1[: 100])  # 打印聚类结果
    print(len(set(labels_1)))  # 看看在该临界距离下有几个 cluster
    
    #根据聚类数目返回聚类结果
    k = 3
    labels_2 = fcluster(Z, t=k, criterion='maxclust')
    print(labels_2[: 100])
    list(labels_1) == list(labels_2)  # 看看两种不同维度下得到的聚类结果是否一致
    
    #聚类的结果可视化,相同的类的样本点用同一种颜色表示
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism')
    plt.show()
    

    图7. 聚类结果可视化展示

    3.5完整代码

    from scipy.cluster.hierarchy import linkage     #导入linage函数用于层次聚类
    from scipy.cluster.hierarchy import dendrogram  #dendrogram函数用于将聚类结果绘制成树状图
    from scipy.cluster.hierarchy import fcluster    #fcluster函数用于提取出聚类的结果
    from sklearn.datasets import make_blobs         #make_blobs用于生成聚类算法的测试数据
    from sklearn.cluster import AgglomerativeClustering  #自底向上层次聚类算法
    import matplotlib.pyplot as plt                 #导入matplotlib绘图工具包
    
    #生成测试数据
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c='b')
    plt.show()
    #from scipy.cluster.hierarchy import linkage
    
    #层次聚类实现
    #from scipy.cluster.hierarchy import dendrogram
    Z = linkage(X,  method='ward', metric='euclidean')
    print(Z.shape)
    print(Z[: 5])
    
    
    #画出树状图
    #from scipy.cluster.hierarchy import fcluster
    plt.figure(figsize=(10, 8))
    dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15,
               show_contracted=True)
    plt.show()
    
    # 根据临界距离返回聚类结果
    d = 15
    labels_1 = fcluster(Z, t=d, criterion='distance')
    print(labels_1[: 100])  # 打印聚类结果
    print(len(set(labels_1)))  # 看看在该临界距离下有几个 cluster
    
    # 根据聚类数目返回聚类结果
    k = 3
    labels_2 = fcluster(Z, t=k, criterion='maxclust')
    print(labels_2[: 100])
    list(labels_1) == list(labels_2)  # 看看两种不同维度下得到的聚类结果是否一致
    
    # 聚类的结果可视化,相同的类的样本点用同一种颜色表示
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism')
    plt.show()
    
    

    3.6 对比不同方法聚类效果

    from time import time
    import numpy as np
    from sklearn.datasets import make_blobs
    from scipy.cluster.hierarchy import linkage, fcluster
    from sklearn.metrics.cluster import adjusted_mutual_info_score
    import matplotlib.pyplot as plt
    
    #生成样本点
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels = make_blobs(n_samples=750, centers=centers,
                           cluster_std=0.4, random_state=0)
    
    
    #可视化聚类结果
    def plot_clustering(X, labels, title=None):
        plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='prism')
        if title is not None:
            plt.title(title, size=17)
        plt.axis('off')
        plt.tight_layout()
    
    #进行 Agglomerative 层次聚类
    linkage_method_list = ['single', 'complete', 'average', 'ward']
    
    plt.figure(figsize=(10, 8))
    ncols, nrows = 2, int(np.ceil(len(linkage_method_list) / 2))
    plt.subplots(nrows=nrows, ncols=ncols)
    for i, linkage_method in enumerate(linkage_method_list):
        print('method %s:' % linkage_method)
        start_time = time()
        Z = linkage(X, method=linkage_method)
        labels_pred = fcluster(Z, t=3, criterion='maxclust')
        print('Adjust mutual information: %.3f' % adjusted_mutual_info_score(labels, labels_pred))
        print('time used: %.3f seconds' % (time() - start_time))
        plt.subplot(nrows, ncols, i + 1)
        plot_clustering(X, labels_pred, '%s linkage' % linkage_method)
    plt.show()
    

    图8. 不同聚类方法结果展示

    AMI评估结果
    该量越接近于 1 则说明聚类算法产生的类越接近于真实情况。从右图的AMI量的表现来看,Single-link 方法下的层次聚类结果最差,它几乎将所有的点都聚为一个 cluster,而其他两个 cluster 则都仅包含个别稍微有点偏离中心的样本点,而另外三种聚类方法效果都还可以。结果如下图

    图9. AMI评估结果

    4.参考链接

    博客参考链接:
    https://cloud.tencent.com/developer/article/1800586

    展开全文
  • 层次化粒子群优化算法及其在分类规则提取中的应用.pdf
  • 利用层次聚类对移动曲面拟合滤波算法快速分类的研究.pdf
  • 图像分类算法和应.ppt

    2020-09-16 03:45:21
    图像分类算法与应用 研究 目录 研究背景 相关研究工作 已有工作基础 论文主要研究内容 图像分类的语义层次 James Wang 1.语义类别(例如照片或者剪贴画,室外) 2物体的罗列(人,篮球架,楼. 3.抽象的语义(运动,打篮球) 4...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,986
精华内容 40,394
关键字:

层次分类算法

友情链接: pwmbasic_lcl.rar