精华内容
下载资源
问答
  • 层次聚类可以用什么
    千次阅读
    2020-05-07 10:47:25



    基于层次的聚类方法 简介



    1 . 基于层次的聚类方法 : 将 数据集样本对象 排列成 聚类树 , 在 指定 的层次 ( 切割点 ) 进行切割 , 切割点 时刻 的聚类分组 , 就是 最终需要的聚类分组 ; 也就是这个切割点的切割的时刻 , 互相关联的样本 , 划分到一个聚类分组中 ;


    2 . 基于层次聚类方法 的两种方式 :


    ① 聚合层次聚类 : 开始时 , 每个对象都是一个聚类分组 ( 原子聚类 ) , 根据 聚类之间的相似性 , 对原子聚类逐渐合并 , 最终会合并成一个聚类 ; 其 本质是 由 多个聚类分组 切割成 成少数 聚类分组 ;


    ② 划分层次聚类 : 开始时 , 所有的样本都在一个聚类中 , 根据聚类间相似性 , 对聚类进行划分 , 最终 每个样本 都会被划分成一个聚类分组 ( 原子聚类 ) ; 本质是 由 少数 聚类分组 划分成多个 聚类分组 ;



    基于层次的聚类方法 概念



    1 . 基于层次的聚类方法 概念 : 将数 据集样本对象 排列成 树结构 , 称为 聚类树 , 在指定的层次 ( 步骤 ) 上切割数据集样本 , 切割后时刻的 聚类分组 就是 聚类算法的 聚类结果 ;


    2 . 基于层次的聚类方法 : 一棵树可以从叶子节点到根节点 , 也可以从根节点到叶子节点 , 基于这两种顺序 , 衍生出两种方法分支 , 分别是 : 聚合层次聚类 , 划分层次聚类 ;


    3 . 聚合层次聚类 ( 叶子节点到根节点 ) : 开始时 , 每个样本对象自己就是一个聚类 , 称为 原子聚类 , 然后根据这些样本之间的 相似性 , 将这些样本对象 ( 原子聚类 ) 进行 合并 ;

    常用的聚类算法 : 大多数的基于层次聚类的方法 , 都是 聚合层次聚类 类型的 ; 这些方法从叶子节点到根节点 , 逐步合并的原理相同 ; 区别只是聚类间的相似性计算方式不同 ;


    4 . 划分层次聚类 ( 根节点到叶子节点 ) : 开始时 , 整个数据集的样本在一个总的聚类中 , 然后根据样本之间的相似性 , 不停的切割 , 直到完成要求的聚类操作 ;


    5 . 算法性能 : 基于层次的聚类方法的时间复杂度为 O ( N 2 ) O(N^2) O(N2) , 如果处理的样本数量较大 , 性能存在瓶颈 ;



    聚合层次聚类 图示



    1 . 聚合层次聚类 图示 :

    在这里插入图片描述

    ① 初始状态 : 最左侧 五个 数据对象 , 每个都是一个聚类 ;

    ② 第一步 : 分析相似度 , 发现 a , b a , b a,b 相似度很高 , 将 { a , b } \{a ,b\} {a,b} 分到一个聚类中 ;

    ③ 第二步 : 分析相似度 , 发现 d , e d, e d,e 相似度很高 , 将 { d , e } \{d, e\} {d,e} 分到一个聚类中 ;

    ④ 第三步 : 分析相似度 , 发现 c c c d , e d,e d,e 相似度很高 , 将 c c c 数据放入 { d , e } \{d, e\} {d,e} 聚类中 , 组成 { c , d , e } \{c,d, e\} {c,d,e} 聚类 ;

    ⑤ 第四步 : 分析相似度 , 此时要求的相似度很低就可以将不同的样本进行聚类 , 将前几步生成的两个聚类 , 合并成一个聚类 { a , b , c , d , e } \{a, b, c, d, e\} {a,b,c,d,e} ;


    2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;


    ① 切割点 1 1 1 : 在切割点 1 1 1 停止 , 会得到 5 5 5 个聚类分组 , { a } \{a\} {a} , { b } \{b\} {b}, { c } \{c\} {c}, { d } \{d\} {d} , { e } \{e\} {e} ;

    ② 切割点 2 2 2 : 在切割点 2 2 2 停止 , 会得到 4 4 4 个聚类分组 , { a , b } \{a, b\} {a,b} , { c } \{c\} {c}, { d } \{d\} {d} , { e } \{e\} {e} ;

    ③ 切割点 3 3 3 : 在切割点 3 3 3 停止 , 会得到 3 3 3 个聚类分组 , { a , b } \{a, b\} {a,b} , { c } \{c\} {c}, { d , e } \{d, e\} {d,e} ;

    ④ 切割点 4 4 4 : 在切割点 4 4 4 停止 , 会得到 2 2 2 个聚类分组 ; { a , b } \{a, b\} {a,b} , { c , d , e } \{c, d, e\} {c,d,e} ;

    ⑤ 走完整个流程 : 会得到 1 1 1 个聚类分组 , { a , b , c , d , e } \{a, b ,c, d, e\} {a,b,c,d,e} ;



    划分层次聚类 图示



    1 . 划分层次聚类 图示 :

    在这里插入图片描述


    ① 初始状态 : 最左侧 五个 数据对象 , 属于一个聚类 ;

    ② 第一步 : 分析相似度 , 切割聚类 , 将 { c , d , e } \{c,d, e\} {c,d,e} { a , b } \{a ,b\} {a,b} 划分成两个聚类 ;

    ③ 第二步 : 分析相似度 , 将 { c , d , e } \{c,d, e\} {c,d,e} 中的 { c } \{c\} {c} { d , e } \{d, e\} {d,e} 划分成两个聚类 ;

    ④ 第三步 : 分析相似度 , 将 { d , e } \{d, e\} {d,e} 拆分成 { d } \{d\} {d} { e } \{e\} {e} 两个聚类 ;

    ⑤ 第四步 : 分析相似度 , 将 { a , b } \{a ,b\} {a,b} 拆分成 { a } \{a\} {a} { b } \{b\} {b} 两个聚类 , 至此所有的数据对象都划分成了单独的聚类 ;


    2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;


    ① 切割点 1 1 1 : 在切割点 1 1 1 停止 , 会得到 1 1 1 个聚类分组 , { a , b , c , d , e } \{a, b ,c, d, e\} {a,b,c,d,e} ;

    ② 切割点 2 2 2 : 在切割点 2 2 2 停止 , 会得到 2 2 2 个聚类分组 ; { a , b } \{a, b\} {a,b} , { c , d , e } \{c, d, e\} {c,d,e} ;

    ③ 切割点 3 3 3 : 在切割点 3 3 3 停止 , 会得到 3 3 3 个聚类分组 , { a , b } \{a, b\} {a,b} , { c } \{c\} {c}, { d , e } \{d, e\} {d,e}$ ;

    ④ 切割点 4 4 4 : 在切割点 4 4 4 停止 , 会得到 4 4 4 个聚类分组 , { a , b } \{a, b\} {a,b} , { c } \{c\} {c}, { d } \{d\} {d} , { e } \{e\} {e} ;

    ⑤ 走完整个流程 : 会得到 5 5 5 个聚类分组 , { a } \{a\} {a} , { b } \{b\} {b}, { c } \{c\} {c}, { d } \{d\} {d} , { e } \{e\} {e} ;



    基于层次的聚类方法 切割点选取



    1 . 算法终止条件 ( 切割点 ) : 用户可以指定聚类操作的算法终止条件 , 即上面图示中的切割点 , 如 :


    ① 聚类的最低个数 : 聚合层次聚类中 , n n n 个样本 , 开始有 n n n 个聚类 , 逐步合并 , 聚类个数逐渐减少 , 当聚类个数达到最低值 m i n min min , 停止聚类算法 ;

    ② 聚类最高个数 : 划分层次聚类中 , n n n 个样本 , 开始有 1 1 1 个聚类 , 逐步划分 , 聚类个数逐渐增加 , 当聚类个数达到最大值 m a x max max , 停止聚类算法 ;

    ③ 聚类样本的最低半径 : 聚类的数据样本范围不能无限扩大 , 指定一个阈值 , 只有将该阈值内的样本放入一组 ; 半径指的是所有对象距离其平均点的距离 ;


    2 . 切割点回退问题 : 切割点一旦确定 , 便无法回退 ; 这里以聚合层次聚类为例 :


    ① 处于切割点 4 4 4 : 如已经执行到了步骤三 , 此时处于切割点 4 4 4 , 聚类分组为 { a , b } \{a, b\} {a,b} , { c , d , e } \{c, d, e\} {c,d,e} ;

    ② 试图回退到 切割点 3 3 3 : 想要会回退到切割点 3 3 3 的状态 , 视图将聚类分组恢复成 { a , b } \{a, b\} {a,b} , { c } \{c\} {c}, { d , e } \{d, e\} {d,e} ;

    ③ 无法回退 : 该操作是无法实现的 , 聚类分组一旦 合并 或 分裂 , 此时就无法回退 ;



    族间距离 概念



    族间距离 :


    ① 作用: 族间距离 , 就是聚类分组之间的距离 , 之前的距离计算都是 样本 之间的距离 , 这里的基于层次聚类时 , 不管是聚合层次聚类 , 还是划分层次聚类 , 其都要进行 聚类分组 间的相似度比较 ,

    ② 聚合层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行合并 ;

    ③ 划分层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行划分 ( 拆分 ) ;



    族间距离 使用到的变量



    公式中 用到的 变量 :


    ① 样本表示 : p p p q q q 表示 分别 处于两个聚类分组中的 两个样本 ;

    ② 样本距离表示 : d ( p , q ) d(p, q) d(p,q) 表示 p p p 样本对象 与 q q q 样本对象的距离 ;

    ③ 聚类 ( 族 ) 表示 : C i C_i Ci C j C_j Cj 分别表示两个 聚类 / 族 / 聚类分组 ;

    ④ 聚类距离表示 : d ( C i , C j ) d(C_i, C_j) d(Ci,Cj) 表示 C i C_i Ci 聚类 与 C j C_j Cj 聚类 之间的距离 ;

    ⑤ 聚类中心点 : m i m_i mi C i C_i Ci 聚类的中心点 , m j m_j mj C j C_j Cj 聚类的中心点 ;

    ⑥ 样本个数 : n i n_i ni C i C_i Ci 聚类的样本个数 , n j n_j nj C j C_j Cj 聚类的样本个数 ;



    族间距离 最小距离



    C i   , C j C_i \,, C_j Ci,Cj 族间距离 最小距离 公式 :


    d m i n ( C i , C j ) = m i n p ∈ C i , q ∈ C j d ( p , q ) d_{min}(C_i , C_j) = min _{p \in C_i , q \in C_j} d(p, q) dmin(Ci,Cj)=minpCi,qCjd(p,q)


    d m i n ( C i , C j ) d_{min}(C_i , C_j) dmin(Ci,Cj) 表示两个聚类的最小距离 ;

    p p p 是属于 C i C_i Ci 聚类中的任意样本 ;

    q q q 是属于 C j C_j Cj 聚类中的任意样本 ;


    总结 : 两个聚类中两个最近的样本之间的距离就是 聚类间的 最小距离 ;



    族间距离 最大距离



    C i   , C j C_i \,, C_j Ci,Cj 族间距离 最大距离 公式 :


    d m a x ( C i , C j ) = m a x p ∈ C i , q ∈ C j d ( p , q ) d_{max }(C_i , C_j) = max _{p \in C_i , q \in C_j} d(p, q) dmax(Ci,Cj)=maxpCi,qCjd(p,q)


    d m a x ( C i , C j ) d_{max }(C_i , C_j) dmax(Ci,Cj) 表示两个聚类的最大距离 ;

    p p p 是属于 C i C_i Ci 聚类中的任意样本 ;

    q q q 是属于 C j C_j Cj 聚类中的任意样本 ;


    总结 : 两个聚类中两个最远的样本之间的距离就是 聚类间的 最大距离 ;



    族间距离 中心点距离



    C i   , C j C_i \,, C_j Ci,Cj 族间距离 中心点距离 公式 :


    d m e a n ( C i , C j ) = d ( m i , m j ) d_{mean }(C_i , C_j) = d(m_i, m_j) dmean(Ci,Cj)=d(mi,mj)


    d m e a n ( C i , C j ) d_{mean }(C_i , C_j) dmean(Ci,Cj) 表示两个聚类的 中心点距离 ;

    m i m_i mi C i C_i Ci 聚类的中心点 ;

    m j m_j mj C j C_j Cj 聚类的中心点 ;

    d ( m i , m j ) d(m_i, m_j) d(mi,mj) 表示 m i m_i mi 样本 和 m j m_j mj 样本 之间的距离 ;


    总结 : 两个聚类中的中心点样本之间的距离就是 聚类间的 中心点距离 ;



    族间距离 平均距离



    C i   , C j C_i \,, C_j Ci,Cj 族间距离 平均距离 公式 :


    d a v g ( C i , C j ) = 1 n i n j ∑ p ∈ C i ∑ q ∈ C j d ( p , q ) d_{avg}(C_i , C_j) = \frac{1}{n_i n_j}\sum_{p \in C_i}\sum_{q \in C_j} d(p, q) davg(Ci,Cj)=ninj1pCiqCjd(p,q)


    d m e a n ( C i , C j ) d_{mean }(C_i , C_j) dmean(Ci,Cj) 表示两个聚类的 中心点距离 ;

    p p p 是属于 C i C_i Ci 聚类中的任意样本 ;

    q q q 是属于 C j C_j Cj 聚类中的任意样本 ;

    n i n_i ni C i C_i Ci 聚类的样本个数 ;

    n j n_j nj C j C_j Cj 聚类的样本个数 ;

    ∑ p ∈ C i ∑ q ∈ C j d ( p , q ) \sum_{p \in C_i}\sum_{q \in C_j} d(p, q) pCiqCjd(p,q) 表示 聚类 C i C_i Ci 中每一个点 到 聚类 C j C_j Cj 中所有点的距离 , 这里 C i C_i Ci 中每个点都对应 n j n_j nj 个距离 , n i n_i ni 个点 , 对应 n i × n j n_i \times n_j ni×nj 个距离 ;


    总结 : 两个聚类中的 平均距离 就是 聚类间的 所有点的距离的平均距离 ;



    基于层次聚类 ( 聚合层次聚类 ) 步骤



    聚合层次聚类步骤 :


    ① 原理 : 根据 聚类分组 的 族间距离 对相似的 聚类分组 进行 逐步合并 ;

    ② 步骤一 : 每个样本都构成 聚类分组 , 称为 原子聚类 ;

    ③ 步骤二 : 计算所有 聚类 之间的距离 ; 可以采用 最小距离 , 最大距离 , 中心点距离 , 平均距离 中的一个 ;

    ④ 步骤三 : 将距离最近的两个 聚类分组 合并 , 聚类的个数 减少 1 1 1 个 ;

    ⑤ 步骤四 : 转到 步骤二 计算聚类间距离 , 步骤三 合并近距离聚类 ; 如果满足算法终止条件 , 那么停止聚类 , 否则一直循环迭代 , 最终合并成一个聚类 ;



    基于层次聚类 ( 聚合层次聚类 ) 算法终止条件



    算法终止条件 : 是由 用户 指定的 , 如 :

    ① 聚类分组 ( 族 ) 个数 : 当聚类的个数达到阈值 , 算法终止 ;

    ② 聚类半径 : 每个 聚类的半径 都超过某个阈值 ;



    族半径 计算公式



    族 ( 聚类 ) 半径计算公式 :


    R = 1 n ∑ i = 1 n d ( p i − m ) R=\frac{1}{n}\sum _{i=1}^n d(p_i - m) R=n1i=1nd(pim)


    R R R 表示聚类半径 ;

    n n n 表示聚类中的 样本 个数 ;

    m m m 代表聚类中心点 ;

    d ( p i − m ) d(p_i - m) d(pim) 表示聚类中第 i i i 个样本距离中心点的距离 ;



    基于层次聚类总结



    1 . 基于层次聚类 的核心 : 是计算 两个 聚类分组 ( 族 ) 之间的距离 , 根据 族间距离 进行 聚类合并 ;


    2 . 适用场景 : 如果 每个 聚类 密度差不多 , 族间距离 分离的很清晰 , 那么使用不同的 族间距离 进行聚类 产生的聚类结果 基本一致 ;


    3 . 算法缺陷 : 基于层次距离不适用于以下情况 ; 聚类分组 分离的不明显 ; 形状不是球形 , 凹形的 ; 聚类间大小不等 ; 各个聚类间样本密度不同 ;

    更多相关内容
  • 上篇博客介绍的层次聚类,尤其是AGNES这一传统的层次聚类算法。这篇博客介绍层次聚类的优化算法。 优化算法 BIRCH算法 BIRCH算法(平衡迭代削减聚类法):聚类特征使用3元组进行一个簇的相关信息,通过构建满足分枝...
  • 层次聚类和Kmeans

    2020-12-21 20:56:12
    文章目录层次聚类层次聚类流程层次聚类优缺点Kmeans聚类Kmeans聚类流程K-Means的优缺点 层次聚类 层次聚类流程 (1) 计算两两样本之间的距离; (2) 将距离最小的两个类合并成一个新类; (3) 重新计算新类与所有类之间...
  • 基本的层次聚类算法matlab实现 简单明了 是我以前上课时记下的笔记内容 代码在15b上实验证实可用
  • 主要为大家详细介绍了Python实现简单层次聚类算法以及可视化,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 层次聚类代码

    2018-05-02 16:26:22
    自己做的层次聚类 有可视化 有数据集 基于熵特征的聚类
  • matlab实现层次聚类法,不是库函数实现的,而是一步步根据算法原理完成的
  • 这个是一个简单的聚类分析matlab代码实现,通过matlab对数据进行了简单的层次聚类分析
  • 聚类,就是单纯的聚类算法,别的我也不知道啊
  • 层次聚类算法

    2018-03-30 09:10:18
    关于层次聚类的一些算法的vvvvvv 懂得而奥迪哥如果该打发额而发阿打发
  • 使用 PHA 方法执行快速层次聚类。 该函数将从输入距离矩阵生成层次聚类树 (Z)。 输出 Z 类似于 Matlab 函数“linkage”的输出。 [主要特征] 1.比matlab联动功能更快。 2. 对混合正态分布的集群具有出色的性能。 3. ...
  • 包括最长、最短欧式距离法、重心法(标准欧式、平方欧式、精度加权)、平均法、权重法等等
  • 基于层次聚类的复杂网络社区检测方法
  • 基于层次聚类的多策略未知协议分类方法.docx
  • 关于层次聚类(hierarchical clustering)的基本步骤: 1、假设每个样本为一类,计算每个类的距离,也就是相似度 2、把最近的两个合为一新类,这样类别数量就少了一个 3、重新新类与各个旧类(去了那两个合并的类)之间...
  • 层次聚类AHP

    2018-06-05 11:12:11
    一般通过给定网络的拓扑结构定义网络节点间的相似性或距离,然后采用单连接层次聚类或全连接层次聚类将网络节点组成一个树状图层次结构
  • HypHC:双曲层次聚类

    2021-04-01 01:14:42
    基于相似性的层次聚类(HC)是一种经典的无监督机器学习算法,传统上已使用诸如平均链接之类的启发式算法进行了求解。 最近,Dasgupta通过引入衡量给定树质量的全局成本函数,将HC重新构架为离散的优化问题。 在这...
  • 主要介绍了Python聚类算法之凝聚层次聚类的原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 层次聚类算法 MATLAB实现,没有调用函数
  • 层次聚类分析

    2015-07-06 12:02:27
    从txt读取样本数据(坐标点),通过计算样本之间的距离,选取最小值进行合并。以样本数据的平均值作为该样本的质点。输出结果为txt。
  • 层次聚类matlab程序

    2016-01-05 20:25:12
    层次聚类的matlab程序,数据来源为80个平面点坐标。
  • 层次聚类算法的实现

    千次阅读 多人点赞 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

    展开全文
  • 广告关闭腾讯云11.11云上盛惠 ,精选... 层次聚类分为两种:合并(自下而上)聚类(agglomerative)分裂(自上而下)聚类(divisive)目前使用较多的是合并聚类 ,本文着重讲解合并聚类的原理。 agens层次聚类原理合并聚...

    o55g08d9dv.jpg广告关闭

    腾讯云11.11云上盛惠 ,精选热门产品助力上云,云服务器首年88元起,买的越多返的越多,最高返5000元!

    单点聚类处在树的最底层,在树的顶层有一个根节点聚类。 根节点聚类覆盖了全部的所有数据点。 层次聚类分为两种:合并(自下而上)聚类(agglomerative)分裂(自上而下)聚类(divisive)目前使用较多的是合并聚类 ,本文着重讲解合并聚类的原理。 agens层次聚类原理合并聚类主要是将n个元素当成n个簇,每个簇与其 欧氏...

    对于库表可以直接勾选,对于普通路径,可填形式如 a - b、c 或者它们的混合,用英文逗号分割(例如0 - 10,15,17 - 19表示第0到10列、15、17到19列总共15列作为特征)。 输出结果路径:路径。 结果格式:结果数据格式,默认为 parquet。 二分 kmeans二分 k 均值算法属于层次聚类,详情可参考 官方文档 。 训练节点...

    l5254rp6hz.jpeg

    层次聚类怎么算层次聚类分为自底向上和自顶向下两种,这里仅采用scikit-learn中自底向上层次聚类法。 将数据集中每一个样本都标记为不同类计算找出其中距离最近的2个类别,合并为一类依次合并直到最后仅剩下一个列表,即建立起一颗完整的层次树以下为看图说话~ 感谢 laugh’sblog借用下说明图把所有数据全部分为不...

    层次聚类(hierarchical clustering算法)层次聚类算法又称为树聚类算法,它根据数据之间的距离,透过一种层次架构方式,反复将数据进行聚合,创建一个层次以分解给定的数据集。 常用于一维数据的自动分组层次聚类方法 hclust(dist)dist样本的距离矩阵距离矩阵的计算方式 dist(data)data 样本数据层次聚类的代码实现...

    前面我们在教程:使用r包deconstructsigs根据已知的signature进行比例推断,顺利的把508个病人,根据11个signature进行了比例推断,得到的比例矩阵以普通的热图,以及pheatmap包自带的层次聚类如下:? 代码是:rm(list=ls())options(stringsasfactors = f)load(file = mut.wt_from_denovo.rdata)a2=mut.wt##...

    hngalg7tx5.png

    假设有n个待聚类的样本,对于层次聚类来说,步骤:1、(初始化)把每个样本归为一类,计算每两个类之间的距离,也就是样本与样本之间的相似度; 2、寻找各个类之间最近的两个类,把他们归为一类(这样类的总数就少了一个); 3、重新计算新生成的这个类与各个旧类之间的相似度; 4、重复2和3直到所有样本点都归为一类...

    3upn7votme.jpeg

    有人不理解分类和聚类的差别,其实这个很简单:分类是一个已知具体有几种情况的变量,预测它到底是哪种情况; 聚类则是尽量把类似的样本聚在一起,不同的样本分开。 举个例子,一个人你判断他是男是女这是分类,让男人站一排女人站一排这是聚类。 聚类分析算法很多,比较经典的有k-means和层次聚类法。 k-means聚类...

    首先抛出了聚类理论中两个关键问题:何为类,何为相似,同时介绍了聚类中常用两种评价指标:内部指标和外部指标。 然后介绍了层次聚类算法:凝聚层次聚类和分裂层次聚类算法,两者皆以样本集作为类表示,常用欧式距离作为相似性度量,分层次聚类。 最后介绍了层次聚类算法的特点,可视化,复杂度。 作者 | 文杰编辑 ...

    之前也做过聚类,只不过是用经典数据集,这次是拿的实际数据跑的结果,效果还可以,记录一下实验过程。 首先:确保自己数据集是否都完整,不能有空值,最好也不要出现为0的值,会影响聚类的效果。 其次:想好要用什么算法去做,k-means,层次聚类还是基于密度算法,如果对这些都不算特别深入了解,那就都尝试一下吧...

    前文说了k均值聚类,他是基于中心的聚类方法,通过迭代将样本分到k个类中,使每个样本与其所属类的中心或均值最近。 今天我们看一下无监督学习之聚类方法的另一种算法,层次聚类:层次聚类前提假设类别直接存在层次关系,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。 在聚类树中,不同类别的原始...

    6pzpq2hab1.jpeg

    比如说,聚类内平方和(within-cluster sum-of-squares)可以测量每个聚类内的方差。 聚类越好,整体 wcss 就越低。 层次聚类(hierarchical clustering)何时使用? 当我们希望进一步挖掘观测数据的潜在关系,可以使用层次聚类算法。 工作方式首先我们会计算距离矩阵(distance matrix),其中矩阵的元素(i,j)...

    mwnrl0o4jw.jpeg

    而且聚类能够作为一个独立的工具获得数据的分布状况,观察每一簇数据的特征,集中对特定的聚簇集合作进一步地分析。 聚类分析还可以作为其他算法(如分类和定性归纳算法)的预处理步骤。 2. 层次聚类分析层次聚类分为凝聚式层次聚类和分裂式层次聚类。 凝聚式层次聚类,就是在初始阶段将每一个点都视为一个簇...

    常用密度聚类算法:dbscan密度最大值算法(1)dbscan算法 dbscan(density-based spatial clusteringof applications with noise)是一个比较有代表性的基于密度的聚类算法,相比于基于划分的聚类方法和层次聚类方法,dbscan算法将簇定义为密度相连的点的最大集合,能够将足够高密度的区域划分为簇,并且在具有噪声的...

    z8r4cd1vu9.png

    层次聚类结果的比较和评估及r操作 层次聚类是探索性分析,而非统计检验的过程。 通过前文对层次聚类的简介,可知数据集的预处理方式、关联系数或距离测度的选择以及聚类方法的选择等将直接影响聚类结果。 因此,选择与分析目标一致的方法非常重要。 本篇简介一些用于比较和评估层次聚类结果的方法,以帮助理解关联...

    duojdlup4a.png

    顾名思义就是要一层一层地进行聚类,可以由上向下把大的类别(cluster)分割,叫作分裂法; 也可以由下向上对小的类别进行聚合,叫作凝聚法; 但是一般用的比较多的是由下向上的凝聚方法。 二、具体1、大致过程:层次聚类方法对给定的数据集进行层次的分解,直到某种条件满足为止。 在已经得到距离值之后,元素间可以...

    层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构,层次聚类一般有两种划分策略:自底向上的聚合(agglomerative)策略和自顶向下的分拆(divisive)策略,本文对层次聚类算法原理进行了详细总结。 1. 层次聚类算法原理层次聚类根据划分策略包括聚合层次聚类和拆分...

    3ndid84ub5.png

    k-means算法却是一种方便好用的聚类算法,但是始终有k值选择和初始聚类中心点选择的问题,而这些问题也会影响聚类的效果。 为了避免这些问题,我们可以选择另外一种比较实用的聚类算法-层次聚类算法。 顾名思义,层次聚类就是一层一层的进行聚类,可以由上向下把大的类别(cluster)分割,叫作分裂法; 也可以由下...

    9jlooizqm6.jpeg

    这里再来看看另外一种常见的聚类算法birch。 birch算法比较适合于数据量大,类别数k也比较多的情况。 它运行速度很快,只需要单遍扫描数据集就能进行聚类。 什么是流形学习birch的全称是利用层次方法的平衡迭代规约和聚类(balanced iterativereducing and clustering using hierarchies),其实只要明白它是用层次...

    xe8zf01xdw.jpeg

    实例44 层次聚类分析功能与意义又称系统聚类分析,先将每一个样本看作一类,然后逐渐合并,直至合并为一类的一种合并法,层次聚类分析的优点很明显,他可对样本进行聚类,样本可以为连续或是分类变量,还可以提供多种距离测量方法和结果表示的方法。 数据来源? 分析过程分析-分类-系统聚类? 统计量? 绘制? 保存? 结果...

    1496654823663_5455_1496654823826.png

    所以,讨论数据集应该聚类成多少个簇,通常是在讨论我们在什么尺度上关注这个数据集。 层次聚类算法相比划分聚类算法的优点之一是可以在不同的尺度上(层次)展示数据集的聚类情况。 基于层次的聚类算法(hierarchical clustering)可以是凝聚的(agglomerative)或者分裂的(divisive),取决于层次的划分是“自底...

    展开全文
  • 层次聚类(AGNES)算法(Python) 是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。AGNES是常用的一种...
  • 层次聚类算法,matlab程序,是一种基于层次聚类法的算法。
  • 聚类算法之层次聚类

    千次阅读 2021-10-27 16:19:09
    层次聚类 1. 基本介绍 层次聚类有聚合(自下而上)和分裂(自上而下)两种方式。 聚合聚类开始将每个样本各自分到 个类:之后将相距最近的两类合井,建立一个新的类,重复此操作直到满足停止条件 分裂聚类开始将所有...

    层次聚类

    1. 基本介绍

    层次聚类有聚合(自下而上)和分裂(自上而下)两种方式。

    聚合聚类开始将每个样本各自分到 个类:之后将相距最近的两类合井,建立一个新的类,重复此操作直到满足停止条件

    分裂聚类开始将所有样本分到一个类之后将己有类中相距最远的样本分到两个新的类,重复此操作直到满足停止条件

    2. 聚合聚类

    对于给定的样本集合,开始将每个样本分到一个类,然后按照一定规则,例如类间距离最小,将最满足规则条件的两个类进行合并 如此反复进行,每次减少一个类,直到满足停止条件

    聚合聚类需要预先确定下面三个要素:

    • 距离或相似度:欧氏距离、曼哈顿距离、夹角余弦等
    • 合并规则:最短距离,最长距离,中心距离,平均距离等
    • 停止条件:类的个数达到阈值、类的直径超过阈值等

    3. 聚合聚类算法流程

    如果采用欧氏距离作为样本间的距离,类间距离最小作为合并规则,类的个数为1作为停止条件,那么聚合聚类算法流程如下:

    输 入 : n 个 样 本 组 成 的 样 本 集 合 及 样 本 之 间 的 距 离 输入: n 个样本组成的样本集合及样本之间的距离 :n

    输 出 : 对 样 本 集 合 的 个 层 次 化 聚 类 输出:对样本集合的 个层次化聚类 :

    1. 计算 n n n个样本两两之间的欧氏距离 d i j d_{ij} dij
    2. 构造 n n n个类,每个类只包含一个样本
    3. 合井类间距离最小的两个类,其中最短距离为类间距离,构建一个新类。
    4. 计算新类与当前各类的距离。若类的个数为1,终止计算,否则回到步骤3

    4. Scipy中的层次聚类

    from scipy.cluster.hierarchy import dendrogram, linkage
    from matplotlib import pyplot as plt
    
    X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
    
    Z = linkage(X, 'average')
    
    fig = plt.figure(figsize=(5, 3))
    dn = dendrogram(Z)
    plt.show()
    

    在这里插入图片描述

    scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)

    • y:是距离矩阵,可以是1维压缩向量(距离向量),也可以是2维观测向量(坐标矩阵)。若y是1维压缩向量,则y必须是n个初始观测值的组合,n是坐标矩阵中成对的观测值。
    • method:是指计算类间距离的方法
      1. single
        d ( u , v ) = m i n ( d i s t ( u [ i ] , v [ j ] ) ) d(u,v)=min(dist(u[i],v[j])) d(u,v)=min(dist(u[i],v[j]))
      2. complete
        d ( u , v ) = m a x ( d i s t ( u [ i ] , v [ j ] ) ) d(u,v)=max(dist(u[i],v[j])) d(u,v)=max(dist(u[i],v[j]))
      3. average
        d ( u , v ) = ∑ i j d i s t ( u [ i ] , u [ j ] ) ( ∣ u ∣ ⋅ ∣ v ∣ ) d(u,v)=\sum_{ij}\frac {dist(u[i],u[j])} {(|u| \cdot |v|)} d(u,v)=ij(uv)dist(u[i],u[j])
      4. ward
        d ( u , v ) = ∣ v ∣ + ∣ s ∣ N d i s t ( v , s ) 2 + ∣ v ∣ + ∣ t ∣ N d i s t ( v , t ) 2 − ∣ v ∣ N d i s t ( s , t ) 2 d(u,v)=\sqrt {\frac {|v|+|s|}{N}dist(v,s)^2+\frac {|v|+|t|}{N}dist(v,t)^2-\frac {|v|} {N}dist(s,t)^2} d(u,v)=Nv+sdist(v,s)2+Nv+tdist(v,t)2Nvdist(s,t)2
        其中, u u u s 和 t s和t st组成的新类, v v v初始时的类。 N = ∣ v ∣ + ∣ s ∣ + ∣ t ∣ N=|v|+|s|+|t| N=v+s+t

    返回值: ( n − 1 , 4 ) (n-1,4) (n1,4)的矩阵 Z Z Z
    在这里插入图片描述

    5. Sklearn中的层次聚类

    from sklearn.cluster import AgglomerativeClustering
    from scipy.cluster.hierarchy import dendrogram
    from matplotlib import pyplot as plt
    import numpy as np
    
    X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
    
    def plot_dendrogram(model, **kwargs):
        counts = np.zeros(model.children_.shape[0])
        n_samples = len(model.labels_)
        for i, merge in enumerate(model.children_):
            current_count = 0
            for child_idx in merge:
                if child_idx < n_samples:
                    current_count += 1
                else:
                    current_count += counts[child_idx - n_samples]
            counts[i] = current_count
    
        linkage_matrix = np.column_stack(
            [model.children_, model.distances_, counts]
        ).astype(float)
    
        dendrogram(linkage_matrix, **kwargs)
    
    model = AgglomerativeClustering(n_clusters=None, distance_threshold=0, linkage='average')
    
    model.fit(X)
    
    
    plot_dendrogram(model)
    
    plt.show()
    

    在这里插入图片描述

    sklearn.cluster.AgglomerativeClustering

    • n_clusters:聚类数目
    • linkage: 计算类间距离的方法

    返回值的属性

    • labels_: 每一点的聚类标签

    • children_:每个非叶节点的子节点。小于n_samples的值对应于原始样本树的叶子。大于或等于n_samples的节点i是一个非叶节点,具有子节点children_[i - n_samples]。或者,在第i次迭代时,将children[i][0]children[i][1]合并成节点n_samples + i
      在这里插入图片描述

    • 数据X一共有8个样本,那么在进行层次聚类是,这8个样本各自一类,类别名称是0、1、2、3、4、5、6、7

    • 第一行:[5, 6]意思是类别5和类别6距离最近,首先聚成一类,并自动定义类别为8(=8-1+1)

    • 第二行:[2, 7]意思是类别2和类别7距离最近,聚成一类,类别为9(=8-1+2)

    • 依次类推

    6. 实例演示

    import numpy as np 
    import matplotlib.pyplot as plt 
    
    from sklearn import cluster, datasets
    from sklearn.preprocessing import StandardScaler
    
    np.random.seed(0)
    
    # 构建数据
    n_samples = 1500
    noisy_circles = datasets.make_circles(n_samples=n_samples, factor=0.5, noise=0.05)
    noisy_moons = datasets.make_moons(n_samples=n_samples, noise=0.05)
    blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)
    
    data_sets = [
        (
            noisy_circles,
            {
                "n_clusters": 2
            }
        ),
        (
            noisy_moons,
            {
                "n_clusters": 2
            }
        ), 
        (
            blobs, 
            {
                "n_clusters": 3
            }
        )
    ]
    colors = ["#377eb8", "#ff7f00", "#4daf4a"]
    linkage_list = ['single', 'average', 'complete', 'ward']
    
    plt.figure(figsize=(20, 15))
    
    for i_dataset, (dataset, algo_params) in enumerate(data_sets):
        # 模型参数
        params = algo_params
    
        # 数据
        X, y = dataset
        X = StandardScaler().fit_transform(X)
    
        for i_linkage, linkage_strategy in enumerate(linkage_list):
            # 创建AgglomerativeCluster
            ac = cluster.AgglomerativeClustering(n_clusters=params['n_clusters'], linkage=linkage_strategy)
    
            # 训练
            ac.fit(X)
    
            # 预测
            y_pred = ac.labels_.astype(int)
    
            y_pred_colors = []
    
            for i in y_pred:
                y_pred_colors.append(colors[i])
            
            plt.subplot(3, 4, 4*i_dataset+i_linkage+1)
            plt.title(linkage_strategy)
            plt.scatter(X[:, 0], X[:, 1], color=y_pred_colors)
    
    plt.show()
    

    在这里插入图片描述

    7. 层次聚类小结

    优点:

    1. 距离和规则的相似度容易定义,限制少
    2. 不需要预先制定聚类数
    3. 可以发现类的层次关系
    4. 可以聚类成其它形状

    缺点:

    1. 计算复杂度太高,的复杂度是 O ( n 3 m ) O(n^3m) O(n3m)其中 m m m是样本的维数, n n n是样本个数。

    2. 奇异值也能产生很大影响

    3. 算法很可能聚类成链状

    展开全文
  • 一种层次聚类和自适应加权K近邻组合的室内定位算法.pdf
  • 提出一种基于维度概率摘要模型的凝聚层次聚类算法.实验分析发现,所提模型和算法能够产生高质量的聚类,能够避免噪声点的影响并发现离群点,能够自动发现聚类,算法稳定可靠且对高维数据集聚类效果很好.
  • 凝聚聚类与层次聚类

    2022-03-06 10:48:28
    凝聚聚类(agglomerative clustering)指的是许多基于相同原则构建的聚类算法,这一原则是:算法首先声明每个点是自己的簇,然后合并两个最相似的簇,直到满足某种停止准则为止。scikit-learn 中实现的停止准则是簇...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,059
精华内容 13,223
关键字:

层次聚类可以用什么