基于层次的聚类算法（Hierarchical Clustering）
当不知道应该分为几类时，使用层次聚类比较适合。层次聚类会构建一个多层嵌套的分类，类似一个树状结构。可以选择一个聚类数量，根据需求对树状图中画一条水平线,得到对应的聚类。 但层次聚类法容易受到噪声和数据维度过高的影响。
; 自底向上的聚类
从点作为个体簇开始，迭代时每一步合并两个最接近的簇，直到所有样本合并为一簇。
算法步骤：
- 每个样本点自成一类。
- 选择最近的两个类聚成一类。
- 计算新的类与类之间的距离。
- 重复第 2、3 步直至所有的样本点聚为一类。
初始时，每个簇只有一个样本，搜索相似度矩阵就可以找到距离最短的两个簇，然后合并它们；当簇中不止一个样本时，可以采用Min、Max、群平均、Ward’s等方法计算两个簇之间的相似性（距离）。
该方法的优点是思想简单，但分裂点的选择不太容易，计算量大，不适应于大数据集的聚类，且空间要求较大，时间复杂度也较高，时间复杂度 O ( m 2 ) O(m_2)O (m 2 )，空间复杂度 O ( m 2 ⋅ l o g m ) O(m_2\cdot {log}_m)O (m 2 ⋅l o g m ) ，m为样本个数。
两个簇之间的距离度量
1. Min:不同簇中两个最近的样本的距离，作为簇之间的距离；考虑两个簇 A，B，其中，x i ∈ A , y j ∈ B \mathbf x_i\in A, \mathbf y_j\in B x i ∈A ,y j ∈B，则簇间最小距离 d ( A , B ) = m i n { d ( x i , y j ) } \displaystyle d(A,B)=min{d(\mathbf x_i,\mathbf y_j)}d (A ,B )=m i n {d (x i ,y j )}
优点：可以处理非椭圆型的样本集合；
缺点：容易收噪声和奇异值的影响。
2. Max：不同簇中两个最远的样本的距离，作为簇之间的距离；簇间最大距离 d ( A , B ) = m a x { d ( x i , y j ) } \displaystyle d(A,B)=max{d(\mathbf x_i,\mathbf y_j)}d (A ,B )=m a x {d (x i ,y j )}
优点：不容易受噪声和奇异值的影响；倾向对具有大量样本的簇进行分割；
缺点：对球状簇的样本分割容易有偏差。
3. 群平均：将不同簇中所有的样本点之间的距离求平均值；是一种介于 Min 和 Max 之间的方法；簇间平均距离 d ( A , B ) = 1 n A ⋅ n B ∑ x i ∈ A , y i ∈ B d ( x i , y j ) \displaystyle d(A,B)=\frac{1}{n_A\cdot n_B}\sum_{\mathbf x_i\in A,\mathbf y_i\in B}d(\mathbf x_i,\mathbf y_j)d (A ,B )=n A ⋅n B 1 x i ∈A ,y i ∈B ∑d (x i ,y j )
优点：不容易受噪声和奇异值的影响；
缺点：对球状簇的样本分割容易有偏差。
4. Ward法(离差平方和):两个类合并后增加的类内离差平方和最小。
优点：不容易受噪声和奇异值的影响；
缺点：对球状簇的样本分割容易有偏差。
; 自顶向下的聚类
从包含所有样本点的某个簇开始。迭代时每一步分裂一个个体簇，直到所有簇都为个体簇。
算法步骤
- 将样本集中的所有的样本归为一个簇；
- 在同一个簇（计为簇C C C ）中计算两两样本之间的距离，找出距离最远的两个样本x a , x b \mathbf x_a,\mathbf x_b x a ,x b ；
- 将样本x a , x b \mathbf x_a,\mathbf x_b x a ,x b 分配到不同的类簇C 1 C_1 C 1 和C 2 C_2 C 2 中；
- 计算原类C C C 中剩余的其他样本点x i \mathbf x_i x i 和x a , x b \mathbf x_a,\mathbf x_b x a ,x b 的距离，若是d ( x a , x i ) < d ( x b , x i ) d(\mathbf x_a,\mathbf x_i) ，则将样本点归到 C 1 C_1 C 1 中，否则归到 C 2 C_2 C 2 中；
- 重复以上步骤，直到达到聚类的数目或者达到设定的条件。
该方式的缺陷是 受噪点影响大，容易产生长条状的簇。
Original: https://blog.csdn.net/qq_41536160/article/details/122113065
Author: 有梦想的雨
Title: 聚类——基于层次的聚类算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/560349/
转载文章受原作者版权保护。转载请注明原作者出处！