精华内容
下载资源
问答
  • 【数据挖掘】基于层次的聚类方法 ( 聚合层次聚类 | 划分层次聚类 | 族间距离 | 最小距离 | 最大距离 | 中心...
    千次阅读
    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 . 算法缺陷 : 基于层次距离不适用于以下情况 ; 聚类分组 分离的不明显 ; 形状不是球形 , 凹形的 ; 聚类间大小不等 ; 各个聚类间样本密度不同 ;

    更多相关内容
  • 包括最长、最短欧式距离法、重心法(标准欧式、平方欧式、精度加权)、平均法、权重法等等
  • 基于层次聚类的复杂网络社区检测方法
  • 主要为大家详细介绍了Python实现简单层次聚类算法以及可视化,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 使用 PHA 方法执行快速层次聚类。 该函数将从输入距离矩阵生成层次聚类树 (Z)。 输出 Z 类似于 Matlab 函数“linkage”的输出。 [主要特征] 1.比matlab联动功能更快。 2. 对混合正态分布的集群具有出色的性能。 3. ...
  • 主要介绍了Python聚类算法之凝聚层次聚类的原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 层次聚类和Kmeans

    2020-12-21 20:56:12
    文章目录层次聚类层次聚类流程层次聚类优缺点Kmeans聚类Kmeans聚类流程K-Means的优缺点 层次聚类 层次聚类流程 (1) 计算两两样本之间的距离; (2) 将距离最小的两个类合并成一个新类; (3) 重新计算新类与所有类之间...
  • 上篇博客介绍的层次聚类,尤其是AGNES这一传统的层次聚类算法。这篇博客介绍层次聚类的优化算法。 优化算法 BIRCH算法 BIRCH算法(平衡迭代削减聚类法):聚类特征使用3元组进行一个簇的相关信息,通过构建满足分枝...
  • 层次聚类代码

    2018-05-02 16:26:22
    自己做的层次聚类 有可视化 有数据集 基于熵特征的聚类
  • 2.6:聚类分析—层次聚类法.do
  • 层次聚类matlab代码

    2017-09-16 11:33:47
    层次聚类matlab代码,数据要求字符串格式,数据类型一致,便于计算和使用,提高数据准确度和可用性,简单实用。
  • 基于PCA和K-均值聚类的有监督分裂层次聚类方法.pdf
  • 层次聚类算法(HCA)是一种聚类分析方法,它通过层次结构搜索聚类的最佳分布。层次聚类的策略通常有两种类型:使用自下而上的过程进行聚集,而使用自上而下的过程进行分裂。但是,大多数聚类方法都有两个缺点:使用...
  • 层次聚类matlab程序

    2016-01-05 20:25:12
    层次聚类的matlab程序,数据来源为80个平面点坐标。
  • 这个是一个简单的聚类分析matlab代码实现,通过matlab对数据进行了简单的层次聚类分析
  • 层次聚类(AGNES)算法(Python) 是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。AGNES是常用的一种...
  • 层次聚类算法

    2018-03-30 09:10:18
    关于层次聚类的一些算法的vvvvvv 懂得而奥迪哥如果该打发额而发阿打发
  • 关于层次聚类(hierarchical clustering)的基本步骤: 1、假设每个样本为一类,计算每个类的距离,也就是相似度 2、把最近的两个合为一新类,这样类别数量就少了一个 3、重新新类与各个旧类(去了那两个合并的类)之间...
  • 大数据中一种基于语义特征阈值的层次聚类方法.pdf
  • 层次聚类算法C++

    2016-06-22 11:33:59
    层次聚类算法C++ VS2010 调试运行成功
  • 提出了一种基于层次聚类(HCCG)的复杂网络粗粒度方法。 通过使用层次聚类方法对网络节点进行分组,然后更新聚类之间边缘的权重以提取粗粒度网络。 在几个典型的复杂网络上进行的大量仿真实验表明,HCCG方法可以...
  • 层次聚类AHP

    2018-06-05 11:12:11
    一般通过给定网络的拓扑结构定义网络节点间的相似性或距离,然后采用单连接层次聚类或全连接层次聚类将网络节点组成一个树状图层次结构
  • BIRCH,CURE,ROCK,CHAMELEON。关于层次聚类的papers,5篇
  • 聚类方法2.1 划分式聚类方法k-meansk-means++bi-kmeans基于密度的方法DBSCANOPTICS算法层次聚类算法 参考文档:参考 1.什么是聚类 定义 聚类(Clustering) 是按照某个特定标准(如距离)把一个数据集分割成不同的类或...

    参考文档:参考

    1.什么是聚类

    定义

    聚类(Clustering) 是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起,不同类数据尽量分离。

    聚类和分类

    1. 聚类(Clustering):是指把相似的数据划分到一起,具体划分的时候并不关心这一类的标签,目标就是把相似的数据聚合到一起,聚类是一种**无监督学习(Unsupervised Learning)**方法。
    2. 分类(Classification):是把不同的数据划分开,其过程是通过训练数据集获得一个分类器,再通过分类器去预测未知数据,分类是一种监督学习(Supervised Learning)方法。

    一般过程

    1. 数据准备:特征标准化和降维
    2. 特征选择:从最初的特征中选择最有效的特征,并将其存储在向量中
    3. 特征提取:通过对选择的特征进行转换形成新的突出特征
    4. 聚类:基于某种距离函数进行相似度度量,获取簇
    5. 聚类结果评估:分析聚类结果,如距离误差和(SSE)等

    数据对象之间相似度度量
    在这里插入图片描述

    聚类之间的相似度度量
    在这里插入图片描述

    • Single-link定义两个cluster之间的距离为两个cluster之间距离最近的两个点之间的距离,这种方法会在聚类的过程中产生链式效应,即有可能会出现非常大的cluster
    • Complete-link定义的是两个cluster之间的距离为两个cluster之间距离最远的两个点之间的距离,这种方法可以避免链式效应,对异常样本点(不符合数据集的整体分布的噪声点)却非常敏感,容易产生不合理的聚类
    • UPGMA正好是Single-link和Complete-link方法的折中,他定义两个cluster之间的距离为两个cluster之间所有点距离的平均值
    • 最后一种WPGMA方法计算的是两个 cluster 之间两个对象之间的距离的加权平均值,加权的目的是为了使两个 cluster 对距离的计算的影响在同一层次上,而不受 cluster 大小的影响,具体公式和采用的权重方案有关。

    2.聚类方法

    分类如下
    在这里插入图片描述

    2.1 划分式聚类方法

    划分式聚类方法需要事先指定簇类的数目或者聚类中心,通过反复迭代,直至最后达到"簇内的点足够近,簇间的点足够远"的目标。

    经典的划分式聚类方法有k-means及其变体k-means++bi-kmeanskernel k-means等。

    k-means

    流程
    在这里插入图片描述
    演示:
    在这里插入图片描述
    在这里插入图片描述
    k-means的问题:

    1. 需要提前确定k值
    2. 对初始质心点敏感
    3. 对异常数据敏感

    k-means++

    k-means++是针对k-means中初始质心点选取的优化算法。该算法的流程和k-means类似,改变的地方只有初始质心的选取,该部分的算法流程如下:
    在这里插入图片描述

    bi-kmeans

    一种度量聚类效果的指标是SSE(Sum of Squared Error),他表示聚类后的簇离该簇的聚类中心的平方和,SSE越小,表示聚类效果越好

    bi-kmeans是针对kmeans算法会陷入局部最优的缺陷进行的改进算法。该算法基于SSE最小化的原理,首先将所有的数据点视为一个簇,然后将该簇一分为二,之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否能最大程度的降低SSE的值

    流程
    在这里插入图片描述

    基于密度的方法

    k-means算法对于凸性数据具有良好的效果,能够根据距离来讲数据分为球状类的簇,但对于非凸形状的数据点,就无能为力了,在环形数据的聚类时:
    在这里插入图片描述
    基于密度的聚类方法 在这里插入图片描述

    DBSCAN

    可以看看这个博客:DBSCAN

    特点在于:

    1. 需要提前确定密度邻域半径领域密度阈值
    2. 不需要提前设置聚类的个数
    3. 对初值选取敏感,对噪声不敏感
    4. 密度不均的数据聚合效果不好

    可视化

    OPTICS算法

    在这里插入图片描述
    所以问题是如何选择合适的邻域密度值

    OPTICS(Ordering Points To Identify the Clustering Structure, OPTICS)实际上是DBSCAN算法的一种有效扩展,主要解决对输入参数敏感的问题。即选取有限个邻域参数[公式] 进行聚类,这样就能得到不同邻域参数下的聚类结果。

    可以看看这个

    层次化聚类算法

    在这里插入图片描述
    层次聚类算法 (hierarchical clustering) 将数据集划分为一层一层的 clusters,后面一层生成的 clusters 基于前面一层的结果。层次聚类算法一般分为两类:

    1. Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个 cluster,每次按一定的准则将最相近的两个 cluster 合并生成一个新的 cluster,如此往复,直至最终所有的对象都属于一个 cluster。这里主要关注此类算法。
    2. Divisive 层次聚类: 又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个 cluster,每次按一定的准则将某个 cluster 划分为多个 cluster,如此往复,直至每个对象均是一个 cluster。

    层次聚类是一种贪心算法

    核聚类

    主要思想:通过一个非线性映射,将输入空间中的数据点映射到高维特征空间中,并选取合适的Mercer核函数代替非线性映射的内积,在特征空间中进行聚类

    优点:

    1. 普适的
    2. 通过非线性映射增加了数据点线性可分的概率,即能较好地分辨、提取并放大有用的特征,从而实现更为准确的聚类,算法收敛速度也较快。

    支持向量聚类

    支持向量聚类(Support Vector Clustering, SVC)属于核聚类的一种,它以支持向量机(Support Vector Machine, SVM)为工具进行聚类。

    基本思想:利用高斯核,将数据空间中的数据点映射到一个高维的特征空间中。再在特征空间中寻找一个能包围所有数据点象的半径最小的球,将这个球映回到数据空间,则得到了包含所有数据点的等值线集。这些等值线就是簇的边界。每一条闭合等值线包围的点属于同一个簇

    两个阶段:

    1. SVC训练阶段
      SVC训练阶段包括高斯核宽度系数的确定、核矩阵的计算、Lagrange乘子的计算、支持向量的选取和高维特征空间中特征球半径的计算
    2. 聚类分配阶段
      聚类分配阶段首先生成邻接矩阵,然后根据邻接矩阵进行聚类分配

    优势:

    1. 能产生任意形状的簇边界;
    2. 能分析噪声数据点且能分离相互交叠的簇。这是许多聚类算法无法做到的

    谱聚类

    参考

    引言

    谱聚类想法的起源:如何在给定长度的线条下围出一个最大的面积,也可理解为,在给定面积下如何使用更短的线条。如何在给定一张图,拿出**“更短”**的边来将其“更好”地切分。

    • “更短”的边,正是对应了spectral clustering中的极小化问题,
    • “更好”地切分,则是对应了spectral clustering中的簇聚类效果

    优缺点

    优点:

    1. 过程对数据结构并没有太多的假设要求,如kmeans则要求数据为凸集。
    2. 可以通过构造稀疏similarity graph,使得对于更大的数据集表现出明显优于其他算法的计算速度。
    3. 由于spectral clustering是对图切割处理,不会存在像kmesns聚类时将离散的小簇聚合在一起的情况。
    4. 无需像GMM一样对数据的概率分布做假设。

    缺点:

    1. 对于选择不同的similarity graph比较敏感(如 epsilon-neighborhood, k-nearest neighborhood,fully connected等)。
    2. 对于参数的选择也比较敏感(如 epsilon-neighborhood的epsilon,k-nearest neighborhood的k,fully connected的 )。

    步骤

    第一步是构图,将采样点数据构造成一张网图,表示为G(V,E),V表示图中的点,E表示点与点之间的边,如下图:
    在这里插入图片描述
    第二步是切图,即将第一步构造出来的按照一定的切边准则,切分成不同的图,而不同的子图,即我们对应的聚类结果,举例如下:
    在这里插入图片描述
    构图的三种方式

    1. ε-neighborhood
    2. k-nearest neighborhood
    3. fully connected
    展开全文
  • 2.代码支持的凝聚层次聚类算法 通过简要的修改代码中函数的参数,代码可以支持不同的凝聚方法,支持的凝聚方法如下,默认的为代码本身算法: 单连接算法(默认,最近邻聚类算法,最短距离法,最小生成树算法);全...
  • 为解决该聚类算法对初始中心敏感的问题,常用的方法是层次化初始聚类中心。然而,层次初始的聚类算法仍然需要将聚类个数作为输入参数,在高维数据和海量数据中不易应用。基于能够自动确定聚类数目的目的,采用DBI...
  • 层次聚类分析

    2015-07-06 12:02:27
    从txt读取样本数据(坐标点),通过计算样本之间的距离,选取最小值进行合并。以样本数据的平均值作为该样本的质点。输出结果为txt。
  • 文章目录基于层次聚类方法的流量异常检测1.模型框架2.数据预处理3.异常流量检测模型4.实验与分析 基于层次聚类方法的流量异常检测 链接:百度网盘链接 提取码:9trx 1.模型框架 2.数据预处理 流量格式转换 在网络...

    基于层次聚类方法的流量异常检测

    链接:百度网盘链接
    提取码:9trx

    1.模型框架

    在这里插入图片描述

    2.数据预处理

    1. 流量格式转换

      在网络中捕获的流量数据包的初始格式通常为pcap格式,内容表现形式为 16进制的数据
      为了将其转化为安全分析人员熟知的IP、端口等内容,需要将pcap格式转换成netflow格式
      pacp ----> netflow

      (1)pcap格式

      pcap:Global Header(24B)、Packet Header(16B)、Packet Data(共n个字节)

       Global Header:定义了该文件的最大存储长度、读取规则等内容
       Packet Header:数据包包头。定义了数据包的时间戳、长度等内容
       Packet Data:数据
      

      在这里插入图片描述

      (2)netflow格式

      7元组:源IP地址、目的IP地址、源端口号、目的端口号、协议种类、服务种类、输入接口

       如果两段流量的7元组相同,则属于同一个数据流,否则属于不同的数据流
      

      (3)转换方法

      在ubuntu环境下,借助3种工具,分别是softflowd、nfcapd、nfdump

       softflowd:读取pcap文件,并将其转换为netflow,输出至指定端口,包含老化时间、抽样等多项参数
       nfcapd:在指定端口接收netflow数据,并输出为netflow文件
       nfdump:读取netflow文件
      
    2. 层次聚类

      主要思想:计算各个数据点的相似度,最终形成树形分布图,对数据集在不同的层次上进行划分

      根据聚类树划分的不同,分为:

       分裂法:自顶向下的分割方法
       凝聚法:自底向上的聚合方法(使用更广泛)
      

      凝聚法:将每个数据点作为一个初始聚类簇,每次都寻找相似度最高的2个类别进行合并,并不断迭代合并的过程,直至分类数目达到预期设定的值。

      簇间距离测量算法:

       (1)单连接算法:2个簇的距离是由这2个簇中最近的2个样本点之间的距离决定,会受到极端值的影响
       (2)全连接算法:2个簇的距离是由这2个簇中最远的2个样本点之间的距离决定,会受到极端值的影响
       (3)均连接算法:2个簇的距离是这2个簇中的所有样本点两两之间距离求均值的结果,计算量较大,结果更合理一些
      

    在这里插入图片描述
    结果为:
    在这里插入图片描述

    3.异常流量检测模型

    使用了七种常用的机器学习算法:决策树、随机森林、SVM、AdaBoost、GBDT、GNB、MNB

    4.实验与分析

    在这里插入图片描述
    分析可得:基于约减的SVM算法效果最佳,因为SVM算法具有较强的鲁棒性,且泛化能力较好

    基于约减的SVM算法对不同数据量的约减率:
    在这里插入图片描述

    分析可得:当流量数据为20万条时,数据约减量达到峰值,因此,基于层次聚类的流量异常检测模型的最佳数据量处理切片为20万条。对于新的需预测的流量数据,以20万条数据量作为划分区间,将其划分为多段流量信息,再使用基于层次聚类的流量异常检测模型进行检测,能到达比较好的约减效果

    展开全文
  • 为了便于用户浏览搜索引擎产生的搜索结果,结H-合STC算法和变色龙算法提出了一种中文网页的层次聚类方法-STCC算法。该方法采用雅可比系数修改了STC算法中基本类相似度的计算方法,然后根据基本类相似度矩阵,利用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,789
精华内容 12,315
关键字:

属于层次聚类方法的是