文章目录
层次聚类
- 层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构，
- 数据集的划分可采用”自底向上（合并）”的聚合策略，也可采用”自顶向下（拆分）”的分析策略。依据采用的策略可以将层次聚类方法分为：
- 聚合式聚类（agglomerative clustering）
- 分拆式聚类（divisive clustering）
- 两种方法均是启发式的策略，没有去优化一个明确的目标函数来实现聚类，很难严格评价聚类的效果。
- 层次聚类得到的结果是 *“树状图”
根据不同虚线的位置，可以得到不同数量的聚类
; 聚合式聚类
- 在开始时把每个样本都每个样本都当成一簇，然后在每一次迭代中将最相似的（距离最近）的两个簇合并，直到把所有簇合并为包含所有样本的一簇
流程：
- 将每个样本看做一个簇:C i ← { i } , i = 1 , 2 , . . . , n C_i \leftarrow {i}, i = 1,2,…,n C i ←{i },i =1 ,2 ,…,n
- 初始化可供合并的簇集：S ← { 1 , 2 , . . . , n } S \leftarrow {1,2,…,n}S ←{1 ,2 ,…,n }
- 计算出簇间距离矩阵
- 重复迭代如下步骤直至没有可供合并的簇：
- 选择两个最相似的簇进行合并：( j , k ) ← a r g min j , k ∈ S d j , k (j,k) \leftarrow arg\min_{j,k \in S} d_{j,k}(j ,k )←a r g min j ,k ∈S d j ,k
- 创建新簇C l ← C j ∪ C k C_l \leftarrow C_j \cup C_k C l ←C j ∪C k
- 从S S S 中取出已合并的j j j和k k k：S ← S ∖ { j , k } S \leftarrow S\setminus{ j,k}S ←S ∖{j ,k }
- 如果C l ≠ { 1 , 2 , . . . , n } C_l \neq { 1,2,…,n}C l ={1 ,2 ,…,n }，那么增加一个可合并集S ← S ∪ { l } S \leftarrow S \cup {l}S ←S ∪{l }
- 对于每个i ∈ S i \in S i ∈S ，更新簇间距离矩阵d ( i , l ) d(i,l)d (i ,l )
簇间距离的计算
单链接(single-linkage)
也称为 最近邻距离，即簇G G G 和簇H H H之间的距离定义为两簇之间最近的成员之间的距离：
d s l ( G , h ) = min i ∈ G , i ′ ∈ H d i , i ′ d_{sl}(G,h) = \min_{i \in G, i^{‘} \in H}d_{i,i^{‘}}d s l (G ,h )=i ∈G ,i ′∈H min d i ,i ′
; 全链接(complete-linkage)
也称为 最远邻距离，即簇G和簇H之间的距离定义为两簇之间最远的成员之间的距离。
d c l ( G , H ) = max i ∈ G , i ′ ∈ H d i , i ′ d_{cl}(G,H) = \max_{i \in G, i^{‘} \in H}d_{i,i^{‘}}d c l (G ,H )=i ∈G ,i ′∈H max d i ,i ′
平均链接(average-linkage)
- 表示两簇之间所有成员对的平均距离
d a v g ( G , H ) = 1 n G n H ∑ i ∈ G ∑ i ′ ∈ H d i , i ′ d_{avg}(G,H) = \frac 1{n_Gn_H}\sum_{i \in G}\sum {i^{‘} \in H}d{i,i^{‘}}d a v g (G ,H )=n G n H 1 i ∈G ∑i ′∈H ∑d i ,i ′
- n G n_G n G 和n H n_H n H 是簇G和簇H的样本个数。
; 三种距离方式的比较
- 单链接(single-linkage)
- 只需要考虑两簇之间有成员对距离足够近就将两簇合并，而并没有考虑其他簇内其他成员的距离。因此单连接法形成的簇很有可能 违背紧致性特征，即簇内成员应该尽可能相似
- 全连接法（complete-linkage）：
- 只有两簇的联合的成员间的距离相对较小时，才将两簇合并，因此完整连接法倾向于生成紧致簇
- 均连接法（average-linkage）
- 介于单连接和全连接之间的方法
- 易于生成相对紧致的簇同时簇间距离较远。
分拆式聚类
分拆聚类将所有样本集合看作一簇，以自上而下的方式，递归地将现有的簇分拆为两个子簇。
利用不同的启发式方法进行分拆方式的选择：
- 二分K-means聚类
- 选择半径最大的簇，对该簇进行K（2）-means聚类分为两个子簇
- 重复此过程直到到达想要的簇个数
- 最小生成树法
- 将每个样本看作一个图节点，将样本间距离看作节点边的权重，根据此图建立最小生成树。
- 从权重最大处将该簇分拆为两簇，然后重复此过程直到达到想要的簇个数。实际上，该方法得到的聚类结果和单连接的聚合聚类得到的结果一致。
层次聚类算法总结
- 层次聚类一次性地得到了整个聚类的过程，想要分多少个簇都可以直接根据”树状图”来得到结果，改变簇的数目不再需要再次计算数据点的归属类别；
- 单连接和全连接代表了簇间距离度量的两个极端，它们对离群点或噪声数据过分敏感
- 平均连接时一种计算量大，而且错分在层次聚类中时不可修正的，一旦某个样本被分到某个聚类中，则该样本永远停留在该聚类中。
- 层次聚类的缺点是：
- 计算量大
- 而且错分在聚合式聚类中是不可修正的，一旦某个样本被分到某个聚类中，则该样本永远停留在该聚类中。
Original: https://blog.csdn.net/WWWzq_/article/details/124234976
Author: WWWzq_
Title: 层次聚类概述
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/696985/
转载文章受原作者版权保护。转载请注明原作者出处！