当前位置：首页 > article >正文

【机器学习】深入无监督学习分裂型层次聚类的原理、算法结构与数学基础全方位解读，深度揭示其如何在数据空间中构建层次化聚类结构

article 2025/1/23 7:30:40

🌟个人主页：落叶

🌟当前专栏: 机器学习专栏

引言

分裂型层次聚类（Divisive Hierarchical Clustering）

1. 基本原理

2. 分裂型层次聚类的算法步骤

Step 1: 初始化

Step 2: 选择分裂的簇

Step 3: 执行分裂操作

Step 4: 计算分裂后的效果

Step 5: 递归进行分裂

Step 6: 构建树形结构

分裂型层次聚类数学描述与公式

3. 优缺点

优点：

缺点：

5. 示例

4.分裂型层次聚类 Python 代码实现

代码解析

主要步骤：

示例输出

总结

引言

分裂型层次聚类（Divisive Hierarchical Clustering，简称DHC）是一种自上而下的聚类方法，它通过从一个包含所有数据点的大簇开始，逐步将其分裂成更小的簇，直到每个簇只包含一个数据点或满足某个停止条件为止。与自下而上的凝聚型层次聚类（Agglomerative Hierarchical Clustering）不同，分裂型层次聚类的过程是逐步分裂而非逐步合并。

好的，让我们更加深入和详细地探讨 分裂型层次聚类（Divisive Hierarchical Clustering），包括算法的每一步、公式的推导过程，以及如何具体实施分裂型聚类的数学框架。

分裂型层次聚类（Divisive Hierarchical Clustering）

分裂型层次聚类是一种自上而下的聚类方法，其基本思想是从一个包含所有数据点的簇开始，逐步将该簇划分为更小的子簇，直到每个子簇包含一个数据点为止。每次分裂时，选择一个簇进行分裂，直到达到停止条件。

1. 基本原理

分裂型层次聚类的核心思路是自上而下的聚类过程：

初始化：将所有数据点放在一个簇中，即把整个数据集视为一个簇。
选择分裂点：在每一轮分裂时，选择一个簇并将其分裂为两个子簇。分裂的标准可以基于某些度量（如最小化误差平方和，SSE）。
分裂操作：通过某种方法（如K-means聚类、主成分分析等）将选择的簇分成两个子簇。
递归分裂：对每一个新的簇重复执行分裂操作，直到满足停止条件（如簇的大小小于某个阈值）。

2. 分裂型层次聚类的算法步骤

分裂型层次聚类算法可以通过以下步骤描述： $C_k^{(2)}$

Step 1: 初始化

将所有数据点视为一个单一的簇 C0C_0（包含所有数据点）。

Step 2: 选择分裂的簇

选择一个簇 CkC_k（通常选择数据量较大的簇）进行分裂。

Step 3: 执行分裂操作

K-means：对簇 $C_k$ 应用 K-means 算法，将其分成两个簇 $C_k^{(1)}$ 和 $C_k^{(2)}$ 。

K-means算法目标是最小化以下误差平方和（SSE）：

其中：
- $N_k$ 和 $M_k$ 分别是簇 $C_k^{(1)}$ 和 $C_k^{(2)}$ 中数据点的数量。
- $\mu_1$ 和 μ2\mu_2 分别是 $mu_2$ 和 Ck(2)C_k^{(2)} 的均值。
其他分裂方法可能包括基于**主成分分析（PCA）或高斯混合模型（GMM）**来选择分裂方式。

Step 4: 计算分裂后的效果

通过计算簇间的距离或相似度来评估当前分裂的质量。常用的距离度量包括欧几里得距离、曼哈顿距离等。

欧几里得距离：
$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$
其中 x 和 y 是两个数据点，n 是数据的维度。

Step 5: 递归进行分裂

对每一个新的子簇 $C_k^{(1)}$ 和 $C_k^{(2)}$ 继续进行分裂操作，直到每个簇只有一个数据点，或直到满足某个终止条件（如簇内的数据点数小于阈值）。

Step 6: 构建树形结构

每次分裂会生成一个新节点，这些节点将会构成一个树形层次结构（如一棵二叉树）。根节点表示整个数据集，叶节点表示单个数据点。

分裂型层次聚类数学描述与公式

簇内误差平方和（SSE）：

对于簇 $C_k$ ，它的SSE是数据点到簇中心（均值）的距离的平方和：

其中：
- $x_i$ 是簇 $C_k$ 中的一个数据点。
- $\mu_k$ 是簇 $C_k$ 的均值（中心点）。
分裂操作：

使用 K-means 算法来分裂簇 $C_k$ 。K-means 目标是最小化每个簇的 SSE，总体SSE最小化目标为：
$\text{SSE}_{\text{total}} = \sum_{k=1}^{K} \text{SSE}(C_k)$
其中 KK 是簇的数量。每次分裂操作都会选择一种方法（如 K-means）来最小化当前簇的 SSE，从而实现最优的分裂。
簇间距离：

分裂型层次聚类有时还会考虑簇间的相似度或距离来指导分裂，常用的度量包括：
- 最小距离法（Single Linkage）：簇间的距离是两个簇中最小距离的点对之间的距离。
- 最大距离法（Complete Linkage）：簇间的距离是两个簇中最远点对之间的距离。
- 平均距离法（Average Linkage）：簇间的距离是两个簇内所有点对的平均距离。

3. 优缺点

优点：

直观的层次结构：分裂型层次聚类自然生成树形结构，能够很好地展示数据的层次关系。
不需要预设簇的数量：与 K-means 等方法不同，分裂型层次聚类不需要预设簇数，用户可以根据树状图的层次决定聚类数量。
适合具有层次结构的数据：如果数据本身存在较明显的层次结构，分裂型层次聚类能够很好地捕捉这种结构。

缺点：

计算复杂度较高：每次分裂时都需要计算簇内数据点的距离，这在数据量大时计算代价较高，特别是在簇数较多时。
对噪声敏感：如果数据中包含大量噪声点，分裂型层次聚类可能会错误地进行分裂，导致不合理的聚类结果。

5. 示例

假设我们有一个二维数据集：

{(1,2),(1,3),(10,10),(10,11)}\{(1, 2), (1, 3), (10, 10), (10, 11)\}

初始簇：将所有点视为一个簇 C0={(1,2),(1,3),(10,10),(10,11)}C_0 = \{(1, 2), (1, 3), (10, 10), (10, 11)\}。
第一步分裂：
- 使用 K-means 对簇 C0C_0 进行分裂，分裂为两个簇：
  - 簇1：{(1, 2), (1, 3)}
  - 簇2：{(10, 10), (10, 11)}
递归分裂：
- 对簇1进行分裂，数据点之间距离很近，无法再分裂。
- 对簇2进行分裂，同样，数据点之间距离很近，无法继续分裂。

最终得到的聚类结果为两个簇：

簇1：{(1, 2), (1, 3)}
簇2：{(10, 10), (10, 11)}

下面是一个简单的分裂型层次聚类算法的 Python 代码实现。该实现基于 K-means 聚类算法来分裂每个簇，并递归地进行分裂，直到每个簇包含一个数据点为止。

4.分裂型层次聚类 Python 代码实现

在这个实现中，我们使用了 scikit-learn 库中的 KMeans 聚类算法。你需要安装 scikit-learn 库来运行以下代码。

pip install scikit-learn

Python 代码实现

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# 计算簇内误差平方和 (SSE)
def compute_sse(X, labels, centers):
    sse = 0
    for i in range(len(centers)):
        cluster_points = X[labels == i]
        sse += np.sum((cluster_points - centers[i]) ** 2)
    return sse

# K-means 分裂操作
def split_cluster(X, cluster):
    kmeans = KMeans(n_clusters=2, random_state=42).fit(X[cluster])
    labels = kmeans.labels_
    centers = kmeans.cluster_centers_
    sse = compute_sse(X[cluster], labels, centers)
    return labels, centers, sse

# 分裂型层次聚类主函数
def divisive_hierarchical_clustering(X, min_cluster_size=1):
    clusters = [np.arange(len(X))]  # 初始簇包含所有数据点
    tree = []  # 保存分裂的层次结构
    while len(clusters) > 0:
        # 从簇列表中选择一个簇进行分裂
        current_cluster = clusters.pop(0)
        
        # 如果簇的大小小于最小簇大小，则停止分裂
        if len(current_cluster) <= min_cluster_size:
            continue

        # 对当前簇进行 K-means 分裂
        labels, centers, sse = split_cluster(X, current_cluster)
        
        # 将分裂结果添加到层次树中
        tree.append((current_cluster, labels, centers))

        # 根据分裂结果生成两个新的子簇
        cluster1 = current_cluster[labels == 0]
        cluster2 = current_cluster[labels == 1]

        # 将子簇加入待分裂簇的列表
        clusters.append(cluster1)
        clusters.append(cluster2)

    return tree

# 绘制数据点及其聚类结果
def plot_clusters(X, tree):
    for i, (cluster, labels, centers) in enumerate(tree):
        plt.figure(figsize=(6, 6))
        plt.scatter(X[:, 0], X[:, 1], c='gray', alpha=0.5, label="All Data Points")
        plt.scatter(X[cluster, 0], X[cluster, 1], c=labels, cmap='viridis', label=f'Cluster {i + 1}')
        plt.scatter(centers[:, 0], centers[:, 1], c='red', marker='x', s=200, label='Centroids')
        plt.legend()
        plt.title(f"Cluster {i + 1} with K-means split")
        plt.show()

# 示例数据生成
from sklearn.datasets import make_blobs

# 生成随机数据
X, _ = make_blobs(n_samples=100, centers=3, random_state=42)

# 调用分裂型层次聚类算法
tree = divisive_hierarchical_clustering(X, min_cluster_size=5)

# 绘制每一步的聚类结果
plot_clusters(X, tree)

代码解析

compute_sse：计算给定簇内的误差平方和（SSE），用来衡量聚类质量。
split_cluster：对一个簇应用 K-means 算法，将其分裂成两个子簇。返回每个子簇的标签、质心和SSE。
divisive_hierarchical_clustering：实现了分裂型层次聚类的核心功能。首先将所有数据点作为一个大簇进行分裂，接着通过递归方法将簇分裂成更小的簇，直到每个簇的大小小于指定的最小簇大小（min_cluster_size）。
plot_clusters：绘制每一步的聚类结果，展示不同层次分裂的效果。