I . 聚类主要算法

聚类主要算法 :

① 基于划分的聚类方法 : K-Means 方法 ;

② 基于层次的聚类方法 : Birch ;

③ 基于密度的聚类方法 : DBSCAN ( Density-Based Spatial Clustering of Applications with Noise ) ;

④ 基于方格的方法 ;

⑤ 基于模型的方法 : GMM 高斯混合模型 ;

II . 基于划分的聚类方法

基于划分的方法 简介 : 基于划分的方法 , 又叫基于距离的方法 , 基于相似度的方法 ;

① 概念 : 给定 n nn 个数据样本 , 使用划分方法 , 将数据构建成 k kk 个划分 ( k ≤ n ) (k \leq n)(k≤n) , 每个划分代表一个聚类 ;

② 分组 : 将数据集 分成 k kk 组 , 每个分组至少要有一个样本 ;

③ 分组与样本 对应关系 : 每个分组有 1 11 个或多个样本对象 ( 1 11 对多 ) , 每个对象同时只能在 1 11 个分组中 ( 1 11 对 1 11 ) ;

④ 硬聚类 与 软聚类 : 每个数据对象只能属于一个组 , 这种分组称为硬聚类 ; 软聚类每个对象可以属于不同的组 ;

III . 基于层次的聚类方法

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

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

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

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

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

5 . 算法性能 : 基于层次的聚类方法的时间复杂度为 O ( N 2 ) O(N^2)O(N

2

) , 如果处理的样本数量较大 , 性能存在瓶颈 ;

IV . 聚合层次聚类 图示

1 . 聚合层次聚类 图示 :

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

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

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

④ 第三步 : 分析相似度 , 发现 c cc 与 d , e d,ed,e 相似度很高 , 将 c cc 数据放入 { 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 11 : 在切割点 1 11 停止 , 会得到 5 55 个聚类分组 , { a } \{a\}{a} , { b } \{b\}{b}, { c } \{c\}{c}, { d } \{d\}{d} , { e } \{e\}{e} ;

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

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

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

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

V . 划分层次聚类 图示

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 11 : 在切割点 1 11 停止 , 会得到 1 11 个聚类分组 , { a , b , c , d , e } \{a, b ,c, d, e\}{a,b,c,d,e} ;

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

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

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

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