【数据挖掘】基于层次的聚类方法 ( 聚合层次聚类 | 划分层次聚类 | 族间距离 | 最小距离 | 最大距离 | 中心距离 | 平均距离 | 基于层次聚类步骤 | 族半径 )
【数据挖掘】基于层次的聚类方法 ( 聚合层次聚类 | 划分层次聚类 | 族间距离 | 最小距离 | 最大距离 | 中心距离 | 平均距离 | 基于层次聚类步骤 | 族半径 )
文章目录
基于层次的聚类方法 简介
1 . 基于层次的聚类方法 : 将 数据集样本对象 排列成 聚类树 , 在 指定 的层次 ( 切割点 ) 进行切割 , 切割点 时刻 的聚类分组 , 就是 最终需要的聚类分组 ; 也就是这个切割点的切割的时刻 , 互相关联的样本 , 划分到一个聚类分组中 ;
2 . 基于层次聚类方法 的两种方式 :
① 聚合层次聚类 : 开始时 , 每个对象都是一个聚类分组 ( 原子聚类 ) , 根据 聚类之间的相似性 , 对原子聚类逐渐合并 , 最终会合并成一个聚类 ; 其 本质是 由 多个聚类分组 切割成 成少数 聚类分组 ;
② 划分层次聚类 : 开始时 , 所有的样本都在一个聚类中 , 根据聚类间相似性 , 对聚类进行划分 , 最终 每个样本 都会被划分成一个聚类分组 ( 原子聚类 ) ; 本质是 由 少数 聚类分组 划分成多个 聚类分组 ;
基于层次的聚类方法 概念
1 . 基于层次的聚类方法 概念 : 将数 据集样本对象 排列成 树结构 , 称为 聚类树 , 在指定的层次 ( 步骤 ) 上切割数据集样本 , 切割后时刻的 聚类分组 就是 聚类算法的 聚类结果 ;
2 . 基于层次的聚类方法 : 一棵树可以从叶子节点到根节点 , 也可以从根节点到叶子节点 , 基于这两种顺序 , 衍生出两种方法分支 , 分别是 : 聚合层次聚类 , 划分层次聚类 ;
3 . 聚合层次聚类 ( 叶子节点到根节点 ) : 开始时 , 每个样本对象自己就是一个聚类 , 称为 原子聚类 , 然后根据这些样本之间的 相似性 , 将这些样本对象 ( 原子聚类 ) 进行 合并 ;
常用的聚类算法 : 大多数的基于层次聚类的方法 , 都是 聚合层次聚类 类型的 ; 这些方法从叶子节点到根节点 , 逐步合并的原理相同 ; 区别只是聚类间的相似性计算方式不同 ;
4 . 划分层次聚类 ( 根节点到叶子节点 ) : 开始时 , 整个数据集的样本在一个总的聚类中 , 然后根据样本之间的相似性 , 不停的切割 , 直到完成要求的聚类操作 ;
5 . 算法性能 : 基于层次的聚类方法的时间复杂度为
, 如果处理的样本数量较大 , 性能存在瓶颈 ;
聚合层次聚类 图示
1 . 聚合层次聚类 图示 :
① 初始状态 : 最左侧 五个 数据对象 , 每个都是一个聚类 ;
② 第一步 : 分析相似度 , 发现
相似度很高 , 将
分到一个聚类中 ;
③ 第二步 : 分析相似度 , 发现
相似度很高 , 将
分到一个聚类中 ;
④ 第三步 : 分析相似度 , 发现
与
相似度很高 , 将
数据放入
聚类中 , 组成
聚类 ;
⑤ 第四步 : 分析相似度 , 此时要求的相似度很低就可以将不同的样本进行聚类 , 将前几步生成的两个聚类 , 合并成一个聚类
;
2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;
① 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
,
,
,
,
;
② 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
,
,
,
;
③ 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
,
,
;
④ 切割点
: 在切割点
停止 , 会得到
个聚类分组 ;
,
;
⑤ 走完整个流程 : 会得到
个聚类分组 ,
;
划分层次聚类 图示
1 . 划分层次聚类 图示 :
① 初始状态 : 最左侧 五个 数据对象 , 属于一个聚类 ;
② 第一步 : 分析相似度 , 切割聚类 , 将
与
划分成两个聚类 ;
③ 第二步 : 分析相似度 , 将
中的
与
划分成两个聚类 ;
④ 第三步 : 分析相似度 , 将
拆分成
和
两个聚类 ;
⑤ 第四步 : 分析相似度 , 将
拆分成
和
两个聚类 , 至此所有的数据对象都划分成了单独的聚类 ;
2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;
① 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
;
② 切割点
: 在切割点
停止 , 会得到
个聚类分组 ;
,
;
③ 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
,
,
$ ;
④ 切割点
: 在切割点
停止 , 会得到
个聚类分组 ,
,
,
,
;
⑤ 走完整个流程 : 会得到
个聚类分组 ,
,
,
,
,
;
基于层次的聚类方法 切割点选取
1 . 算法终止条件 ( 切割点 ) : 用户可以指定聚类操作的算法终止条件 , 即上面图示中的切割点 , 如 :
① 聚类的最低个数 : 聚合层次聚类中 ,
个样本 , 开始有
个聚类 , 逐步合并 , 聚类个数逐渐减少 , 当聚类个数达到最低值
, 停止聚类算法 ;
② 聚类最高个数 : 划分层次聚类中 ,
个样本 , 开始有
个聚类 , 逐步划分 , 聚类个数逐渐增加 , 当聚类个数达到最大值
, 停止聚类算法 ;
③ 聚类样本的最低半径 : 聚类的数据样本范围不能无限扩大 , 指定一个阈值 , 只有将该阈值内的样本放入一组 ; 半径指的是所有对象距离其平均点的距离 ;
2 . 切割点回退问题 : 切割点一旦确定 , 便无法回退 ; 这里以聚合层次聚类为例 :
① 处于切割点
: 如已经执行到了步骤三 , 此时处于切割点
, 聚类分组为
,
;
② 试图回退到 切割点
: 想要会回退到切割点
的状态 , 视图将聚类分组恢复成
,
,
;
③ 无法回退 : 该操作是无法实现的 , 聚类分组一旦 合并 或 分裂 , 此时就无法回退 ;
族间距离 概念
族间距离 :
① 作用: 族间距离 , 就是聚类分组之间的距离 , 之前的距离计算都是 样本 之间的距离 , 这里的基于层次聚类时 , 不管是聚合层次聚类 , 还是划分层次聚类 , 其都要进行 聚类分组 间的相似度比较 ,
② 聚合层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行合并 ;
③ 划分层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行划分 ( 拆分 ) ;
族间距离 使用到的变量
公式中 用到的 变量 :
① 样本表示 :
和
表示 分别 处于两个聚类分组中的 两个样本 ;
② 样本距离表示 :
表示
样本对象 与
样本对象的距离 ;
③ 聚类 ( 族 ) 表示 :
和
分别表示两个 聚类 / 族 / 聚类分组 ;
④ 聚类距离表示 :
表示
聚类 与
聚类 之间的距离 ;
⑤ 聚类中心点 :
是
聚类的中心点 ,
是
聚类的中心点 ;
⑥ 样本个数 :
是
聚类的样本个数 ,
是
聚类的样本个数 ;
族间距离 最小距离
族间距离 最小距离 公式 :
表示两个聚类的最小距离 ;
是属于
聚类中的任意样本 ;
是属于
聚类中的任意样本 ;
总结 : 两个聚类中两个最近的样本之间的距离就是 聚类间的 最小距离 ;
族间距离 最大距离
族间距离 最大距离 公式 :
表示两个聚类的最大距离 ;
是属于
聚类中的任意样本 ;
是属于
聚类中的任意样本 ;
总结 : 两个聚类中两个最远的样本之间的距离就是 聚类间的 最大距离 ;
族间距离 中心点距离
族间距离 中心点距离 公式 :
表示两个聚类的 中心点距离 ;
是
聚类的中心点 ;
是
聚类的中心点 ;
表示
样本 和
样本 之间的距离 ;
总结 : 两个聚类中的中心点样本之间的距离就是 聚类间的 中心点距离 ;
族间距离 平均距离
族间距离 平均距离 公式 :
表示两个聚类的 中心点距离 ;
是属于
聚类中的任意样本 ;
是属于
聚类中的任意样本 ;
是
聚类的样本个数 ;
是
聚类的样本个数 ;
表示 聚类
中每一个点 到 聚类
中所有点的距离 , 这里
中每个点都对应
个距离 ,
个点 , 对应
个距离 ;
总结 : 两个聚类中的 平均距离 就是 聚类间的 所有点的距离的平均距离 ;
基于层次聚类 ( 聚合层次聚类 ) 步骤
聚合层次聚类步骤 :
① 原理 : 根据 聚类分组 的 族间距离 对相似的 聚类分组 进行 逐步合并 ;
② 步骤一 : 每个样本都构成 聚类分组 , 称为 原子聚类 ;
③ 步骤二 : 计算所有 聚类 之间的距离 ; 可以采用 最小距离 , 最大距离 , 中心点距离 , 平均距离 中的一个 ;
④ 步骤三 : 将距离最近的两个 聚类分组 合并 , 聚类的个数 减少
个 ;
⑤ 步骤四 : 转到 步骤二 计算聚类间距离 , 步骤三 合并近距离聚类 ; 如果满足算法终止条件 , 那么停止聚类 , 否则一直循环迭代 , 最终合并成一个聚类 ;
基于层次聚类 ( 聚合层次聚类 ) 算法终止条件
算法终止条件 : 是由 用户 指定的 , 如 :
① 聚类分组 ( 族 ) 个数 : 当聚类的个数达到阈值 , 算法终止 ;
② 聚类半径 : 每个 聚类的半径 都超过某个阈值 ;
族半径 计算公式
族 ( 聚类 ) 半径计算公式 :
表示聚类半径 ;
表示聚类中的 样本 个数 ;
代表聚类中心点 ;
表示聚类中第
个样本距离中心点的距离 ;
基于层次聚类总结
1 . 基于层次聚类 的核心 : 是计算 两个 聚类分组 ( 族 ) 之间的距离 , 根据 族间距离 进行 聚类合并 ;
2 . 适用场景 : 如果 每个 聚类 密度差不多 , 族间距离 分离的很清晰 , 那么使用不同的 族间距离 进行聚类 产生的聚类结果 基本一致 ;
3 . 算法缺陷 : 基于层次距离不适用于以下情况 ; 聚类分组 分离的不明显 ; 形状不是球形 , 凹形的 ; 聚类间大小不等 ; 各个聚类间样本密度不同 ;