ReaderMX.
原力注入

动手学机器学习层次聚类算法

原GrissomFI约 12 分钟

相关内容

原文：https://github.com/ForceInjection/hands-on-ML/blob/main/nju_software/%E5%8A%A8%E6%89%8B%E5%AD%A6%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%B1%82%E6%AC%A1%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95.md

相关文章

  1. 动手学机器学习 Kmeans 聚类算法

正文

层次聚类算法是一种重要的聚类分析方法，它通过构建一个层次结构（树形结构）来表示数据之间的相似性或距离关系。与划分聚类方法（如K-Means）不同，层次聚类无需预先指定聚类的类别数量，这使得它在某些特定场景下具有独特的优势。

一、层次聚类算法概述

层次聚类算法主要分为两类：自底向上层次聚类法（Agglomerative Clustering）和自顶向下层次聚类法（Divisive Clustering）:

  • 自底向上层次聚类法从每个数据点作为一个单独的聚类开始，然后逐步合并距离最近的聚类，直到达到某个终止条件；
  • 自顶向下层次聚类法则相反，它从所有数据点属于一个聚类开始，然后逐步分裂聚类，直到满足某个终止条件。

这两种方法各有特点，适用于不同的数据集和应用场景。

二、自底向上层次聚类法（Agglomerative Clustering）

1. 基本原理

自底向上层次聚类法的基本步骤如下：

  1. 将数据集中的每个样本初始时视为一个单独的聚类。
  2. 计算所有聚类之间的距离，找出距离最近的两个聚类，并将它们合并成一个新的聚类。
  3. 重复上述步骤，直到只剩下一个聚类或者达到预设的聚类数量。

在这个过程中，我们需要定义一种距离度量方法来计算聚类之间的距离。常见的距离度量方法包括单连接（Single-linkage）、全连接（Complete-linkage）、平均连接（Average-linkage）和中心连接（Center-linkage）。其中，平均连接和中心连接方法较为常用，因为它们在处理噪声点和不均匀分布的数据时表现较好。

2. 距离度量方法

####（1）单连接（Single-linkage）

  • 定义：单连接方法将两个聚类之间的距离定义为这两个聚类中所有样本对之间的最小距离。也就是说，它基于两个聚类中最近的两个样本点的距离来衡量整个聚类之间的距离。
  • 计算方式：对于聚类  和聚类 ，单连接距离为：
  • 特点：
    • 优点：能够较好地处理形状不规则的聚类，因为它只关注最近的样本点。
    • 缺点：容易受到噪声点的影响，因为单个噪声点可能会导致两个聚类之间的距离被低估，从而过早地合并聚类。这种现象被称为“链式效应”。

####（2）全连接（Complete-linkage）

  • 定义：全连接方法将两个聚类之间的距离定义为这两个聚类中所有样本对之间的最大距离。也就是说，它基于两个聚类中最远的两个样本点的距离来衡量整个聚类之间的距离。
  • 计算方式：对于聚类  和聚类 ，全连接距离为：
  • 特点：
    • 优点：能够较好地处理紧凑且大小相近的聚类，因为它考虑了聚类中最远的样本点。
    • 缺点：对噪声点和离群点非常敏感，因为单个离群点可能会导致两个聚类之间的距离被高估，从而延迟聚类的合并。

####（3）平均连接（Average-linkage）

  • 定义：平均连接方法将两个聚类之间的距离定义为这两个聚类中所有样本对之间距离的平均值。它综合考虑了所有样本点之间的距离，而不是仅仅依赖最近或最远的样本点。
  • 计算方式：对于聚类  和聚类 ，平均连接距离为：其中， 和  分别表示聚类  和聚类  中的样本数量。
  • 特点：
    • 优点：相比单连接和全连接，对噪声点和异常值的敏感性较低。此外适应性较好，能处理中等规模的簇形状变化。
    • 缺点：计算量较大，特别是在样本数量较多时，因为需要计算所有样本对之间的距离（时间复杂度：）。

####（4）中心连接（Center-linkage）

  • 定义：中心连接方法将两个聚类之间的距离定义为这两个聚类中心之间的距离。聚类中心可以是均值、中位数或其他中心点的表示。
  • 计算方式：对于聚类  和聚类 ，中心连接距离为：其中， 和  分别表示聚类  和聚类  的中心点。
  • 特点：
    • 优点：计算效率较高，因为它只需要计算两个中心点之间的距离。
    • 缺点：对聚类的形状和分布有较高的假设，如果聚类的形状不规则或中心点不能很好地代表聚类，可能会导致不准确的结果。

####（5）总结

这四种距离度量方法各有优缺点，适用于不同的数据分布和聚类场景：

  • 单连接适合形状不规则的聚类，但容易受到噪声影响。
  • 全连接适合紧凑且大小相近的聚类，但对离群点敏感。
  • 平均连接在处理噪声点和不均匀分布的数据时表现较好，但计算成本较高。
  • 中心连接计算效率高，但对聚类的形状和分布有较高的假设。

在实际应用中，选择合适的距离度量方法需要根据数据的特点和具体需求进行权衡。

3. Python 实现示例

以下是使用 Python 实现自底向上层次聚类的一个简单示例：

ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineimport numpy as npfrom scipy.spatial.distance import pdist, squareformimport matplotlib.pyplot as pltfrom sklearn.datasets import make_blobs
# 生成示例数据X, y = make_blobs(n_samples=10, centers=2, random_state=10)
# 可视化原始数据plt.scatter(X[:, 0], X[:, 1], c=y, s=60)plt.title("Original Data")plt.show()
class AgglomerativeClustering:    def __init__(self, n_clusters=2, linkage='average'):        self.n_clusters = n_clusters        self.linkage = linkage        self.clusters = []
    def _calculate_distance(self, cluster1, cluster2):        distances = []        for i in cluster1:            for j in cluster2:                distances.append(np.linalg.norm(self.X[i] - self.X[j]))        return np.mean(distances)  # Average linkage
    def fit(self, X):        self.X = X        n_samples = X.shape[0]        self.clusters = [[i] for i in range(n_samples)]  # 每个样本初始为一个簇
        while len(self.clusters) > self.n_clusters:            # 计算距离矩阵            dist_matrix = np.zeros((len(self.clusters), len(self.clusters)))            for i in range(len(self.clusters)):                for j in range(i+1, len(self.clusters)):                    dist_matrix[i,j] = self._calculate_distance(self.clusters[i], self.clusters[j])
            # 找到最小距离的簇对            min_val = np.inf            min_idx = (0,1)            for i in range(len(self.clusters)):                for j in range(i+1, len(self.clusters)):                    if dist_matrix[i,j] < min_val:                        min_val = dist_matrix[i,j]                        min_idx = (i,j)
            # 合并簇            merged_cluster = self.clusters[min_idx[0]] + self.clusters[min_idx[1]]            del self.clusters[min_idx[1]]            del self.clusters[min_idx[0]]            self.clusters.append(merged_cluster)
    def predict(self):        labels = np.zeros(len(self.X))        for idx, cluster in enumerate(self.clusters):            for i in cluster:                labels[i] = idx        return labels
# 使用示例model = AgglomerativeClustering(n_clusters=2, linkage='average')model.fit(X)labels = model.predict()
plt.scatter(X[:,0], X[:,1], c=labels, s=60)plt.title("Agglomerative Clustering (Average Linkage)")plt.show()

3. 使用 scikit-learn 完成 Agglomerative 聚类

除了手动实现，我们还可以使用 scikit-learn 库中的 AgglomerativeClustering 类来快速完成聚类任务：

ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(linefrom sklearn.cluster import AgglomerativeClustering
model = AgglomerativeClustering(n_clusters=2, metric="euclidean", linkage="average")clusters = model.fit_predict(data[0])plt.scatter(data[0][:, 0], data[0][:, 1], c=clusters, s=60)plt.title("Agglomerative 聚类结果")plt.show()

三、自顶向下层次聚类法（Divisive Clustering）

自顶向下层次聚类法是一种与自底向上层次聚类法相反的聚类方法。它从所有数据点属于一个聚类开始，然后逐步分裂聚类，直到达到某个终止条件或每个数据点成为一个单独的聚类。这种方法相对复杂，计算量较大，但在某些特定场景下具有独特的优势。

1. 常见的分裂方法

  1. 利用 K-Means 算法进行分割

  • 优点：K-Means 算法本身具有较高的效率，适合处理大规模数据集。
  • 缺点：需要多次应用 K-Means 算法，整体计算量较大。
  • 步骤：
  • 特点：
  1. 将所有数据点初始化为一个单一聚类。
  2. 使用 K-Means 算法将当前聚类划分为两个子聚类。
  3. 递归地对每个子聚类应用 K-Means 算法，直到满足终止条件（例如，达到预设的聚类数量或聚类内的距离小于某个阈值）。

  • 利用平均距离进行分割

    • 优点：能够较好地处理紧凑且大小相近的聚类。
    • 缺点：对噪声点和离群点敏感，计算量较大。
    • 步骤：
    • 特点：
    1. 将所有数据点初始化为一个单一聚类。
    2. 计算每个数据点到其他数据点的平均距离。
    3. 选择距离最远的数据点作为新的聚类中心，将数据点分为两个聚类。
    4. 递归地对每个子聚类应用上述步骤，直到满足终止条件。

    2. 应用场景

    自顶向下层次聚类法适用于以下场景：

    • 数据集具有明显的层次结构，且需要逐步细化聚类结果。
    • 需要对聚类结果进行动态调整，例如在交互式数据分析中。
    • 数据集规模较小，计算资源充足。

    四、BIRCH 聚类算法

    BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）是一种高效的层次聚类算法，特别适用于大型数据集。它通过构建 CF（Clustering Feature）聚类特征树来实现快速聚类。CF 聚类特征包括样本点数量、各特征维度的和向量及平方和，能够有效压缩数据信息。BIRCH 算法具有高效性、内存开销小和可处理流数据等优点。

    1. CF 聚类特征

    CF聚类特征是一个三元组 ，其中：

    •  表示该聚类中样本点的数量。
    •  表示该聚类中样本点各特征维度的和向量。
    •  表示该聚类中样本点各特征维度的平方和。

    例如，对于样本点 、、、、，其 CF 特征为：

    2. CF 聚类特征树

    CF 聚类特征树由根节点、枝节点和叶节点构成。每个节点包含多个 CF 项，用于表示该节点下的聚类特征。CF 树的构建过程如下：

    1. 初始化根节点为空。
    2. 遍历每个数据点，插入到 CF 树中：
    • 从根节点开始，根据数据点与各节点的 CF 特征计算距离，选择最近的子节点。
    • 如果子节点是叶节点，则将数据点插入叶节点；否则，继续递归查找。
    • 如果叶节点已满（超过预设的叶节点容量），则分裂叶节点。
  • 重复上述步骤，直到所有数据点插入完成。

    • 3. BIRCH 聚类算法步骤

    1. 构建 CF 树：遍历数据集，将数据点插入 CF 树中，形成层次化的聚类结构。
    2. 聚类：对 CF 树中的叶节点进行聚类，得到最终的聚类结果。
    3. 可选的细化步骤：对初步聚类结果进行优化，例如使用其他聚类算法进行微调。

    4. BIRCH 聚类实现示例

    以下是使用 BIRCH 算法对数据进行聚类的示例：

    ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(linefrom sklearn.cluster import Birchfrom sklearn.datasets import load_digitsfrom sklearn.decomposition import PCAimport matplotlib.pyplot as plt
    # 加载手写字符数据集digits = load_digits()
    # 使用 PCA 降维pca = PCA(n_components=2)pca_data = pca.fit_transform(digits.data)
    # 使用 BIRCH 算法进行聚类birch = Birch(n_clusters=10)clusters = birch.fit_predict(pca_data)
    # 可视化聚类结果plt.figure(figsize=(10, 8))scatter = plt.scatter(pca_data[:, 0], pca_data[:, 1], c=clusters, cmap='viridis', s=15)plt.title("BIRCH 聚类结果")plt.colorbar(scatter)plt.show()

    5. BIRCH 算法的优势

    1. 高效性：BIRCH 算法在构建 CF 树时只存储原始数据的特征信息，而不需要存储原始数据，内存开销小，计算效率高。
    2. 适用于大规模数据集：BIRCH 算法只需要遍历一遍原始数据，适合处理大规模数据集。
    3. 支持流数据：BIRCH 算法属于在线学习算法，支持对流数据的聚类，可以在数据到达时动态更新聚类结果。

    五、PCA 主成分分析

    在处理高维数据时，为了降低计算复杂度和便于数据可视化，我们常常使用 PCA（Principal Component Analysis，主成分分析）进行降维。PCA 是一种统计技术，通过对协方差矩阵进行特征分解，找到数据中方差最大的方向（即主成分），然后将数据投影到由这些主成分构成的低维空间中。这样既保留了数据的主要特征，又减少了数据的维度。

    1. PCA 的数学原理

    1. 数据标准化：首先将数据的每个特征值减去该特征的均值，并除以该特征的标准差，使得数据的均值为 0，方差为 1。
    2. 计算协方差矩阵：协方差矩阵用于衡量不同特征之间的线性关系。对于标准化后的数据矩阵 ，协方差矩阵  可以表示为：其中， 是样本数量。
    3. 特征分解：对协方差矩阵  进行特征分解，得到特征值和对应的特征向量。特征值表示该特征向量方向上的方差大小。
    4. 选择主成分：根据特征值的大小，选择前  个最大的特征值对应的特征向量，这些特征向量即为主成分。
    5. 数据投影：将原始数据投影到由主成分构成的低维空间中，得到降维后的数据。

    2. PCA 的应用步骤

    1. 数据预处理：对原始数据进行标准化或归一化处理，以消除不同特征之间的量纲差异。
    2. 计算协方差矩阵：根据预处理后的数据计算协方差矩阵。
    3. 特征分解与选择：对协方差矩阵进行特征分解，并选择前  个主成分。
    4. 数据变换：将原始数据变换到由主成分构成的新空间中，完成降维。

    3. PCA 在层次聚类中的作用

    在层次聚类中，PCA 可以帮助我们更好地理解数据结构和聚类效果。通过将高维数据降维到二维或三维空间，我们可以直观地观察数据的分布和聚类情况。此外，降维后的数据可以减少计算复杂度，提高聚类算法的效率。

    4. PCA 实现示例

    以下是使用 Python 和 scikit-learn 库进行 PCA 降维的示例：

    ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(linefrom sklearn.datasets import load_irisfrom sklearn.decomposition import PCAimport matplotlib.pyplot as plt
    # 加载 Iris 数据集iris = load_iris()X = iris.datay = iris.target
    # 创建 PCA 模型，将数据降维到 2 维pca = PCA(n_components=2)X_pca = pca.fit_transform(X)
    # 可视化降维后的数据plt.figure(figsize=(8, 6))scatter = plt.scatter(X_pca[:, 0], X_pca[:, 1], c=y, cmap='viridis', s=50)plt.title("PCA 降维后的 Iris 数据集")plt.xlabel("第一主成分")plt.ylabel("第二主成分")plt.colorbar(scatter, ticks=[0, 1, 2], label='类别')plt.show()

    六、总结

    层次聚类算法是一种强大的聚类分析工具，能够有效避免划分聚类方法中需要预先指定类别数量的问题。自底向上层次聚类法和 BIRCH 算法是其中较为常用的方法，它们在不同场景下各有优势。在实际应用中，选择合适的聚类算法需要综合考虑数据的特点、计算资源以及具体的应用需求。

    七、参考

    动手实战人工智能 AI By Doing - 层次聚类方法实现与应用

    KEEP THE THREAD GOING

    更多来源文章

    Kimi K3 注意力机制深度解析：KDA、Gated MLA 与 AttnRes 的混合架构

    2.8 万亿参数的 Kimi K3 原生支持 1M token 上下文窗口。它的注意力系统不是单一种类的升级，而是三种机制的协同设计：69 层 KDA负责高效长上下文处理，24 层 Gated MLA 提供全局精确检索锚点，Attention Residuals 则将"注意力"从序列维度扩展到模型深度维度

    阅读全文