顶[0] 分享评论[0] 编辑

层次聚类分析

层次聚类分析（英文：Hierarchical clustering analysis， HC）是一种旨在通过构建嵌套的簇层次结构来揭示数据内在分组模式的无监督机器学习（英文：Unsupervised machine learning）方法。其最终输出通常以树状图（英文：Dendrogram）表示，展示了数据点从个体逐步合并为一个大簇的全过程。该方法广泛应用于数据挖掘（英文：Data mining）、生物信息学（英文：Bioinformatics）、社会网络分析（英文：Social network analysis）和图像分割（英文：Image segmentation）等领域。

核心概念与类型

层次聚类根据构建层次的方向，主要分为两种策略：

凝聚式层次聚类（英文：Agglomerative hierarchical clustering）：
- 最常见的类型，采用“自底向上”的策略。
- 起始点：将每个数据点视为一个独立的簇。
- 过程：迭代地找出两个最相似的簇，将其合并为一个新簇。
- 终点：直到所有点合并为一个大簇。
分裂式层次聚类（英文：Divisive hierarchical clustering）：
- 采用“自顶向下”的策略。
- 起始点：将所有数据点视为一个大簇。
- 过程：迭代地将现有簇分裂为两个子簇。
- 终点：直到每个数据点都成为一个独立的簇。计算上通常比凝聚法更复杂。

表1：两种层次聚类策略的比较

特征	凝聚式层次聚类	分裂式层次聚类
策略	自底向上（合并）	自顶向下（分裂）
起始状态	N个簇（每个点一个簇）	1个簇（所有点）
计算复杂度	通常为 O(n³) 或优化后 O(n² log n)	通常更高，可达 O(2ⁿ)
常见程度	非常常见，实现广泛	较少使用
优势	概念直观，对小数据集有效	可能在高层分裂时做出更全局的决策

算法流程（以凝聚法为例）

凝聚式层次聚类的标准流程包含以下关键步骤：

计算距离矩阵：计算所有 $n$ 个数据点两两之间的距离（英文：Distance metric）（如欧氏距离、曼哈顿距离）或不相似度（英文：Dissimilarity），形成一个 $n \times n$ 的对称矩阵。
初始化：将每个数据点视为一个独立的簇。
迭代合并：
a. 寻找最近簇对：在距离矩阵中，找出当前所有簇之间距离最小的两个簇 $C_{i}$ 和 $C_{j}$ 。
b. 合并簇：将簇 $C_{i}$ 和 $C_{j}$ 合并为一个新簇 $C_{n e w}$ 。
c. 更新距离矩阵：删除与 $C_{i}$ 和 $C_{j}$ 相关的行和列，并计算新簇 $C_{n e w}$ 与其他所有簇之间的距离。
终止：重复步骤3，直到所有数据点合并为一个簇，或达到预设的簇数量。

关键：连接准则

连接准则（英文：Linkage criterion）决定了如何计算合并后的新簇与其他簇之间的距离，它显著影响最终的聚类形状。

单连接（英文：Single linkage）：取两个簇中最近两点之间的距离。易产生“链状”结构，对噪声敏感。
全连接（英文：Complete linkage）：取两个簇中最远两点之间的距离。倾向于产生紧凑的、直径相似的簇。
平均连接（英文：Average linkage）：取两个簇中所有点对距离的平均值。平衡了单连接和全连接的倾向。
沃德法（英文：Ward's method）：最小化合并后导致的簇内方差总增量。倾向于产生大小均匀的簇，是最小方差法。

输出、解读与应用

输出：树状图

层次聚类的结果通过树状图可视化。分支长度表示簇间合并时的距离或不相似度。通过“切割”树状图（在特定高度画一条水平线），可以得到不同粒度的聚类结果。

主要应用领域

基因表达数据分析：对基因或样本进行聚类，发现共表达模式。
系统发育学：构建反映物种或基因进化关系的系统发育树。
文档与文本聚类：对文档或关键词进行层次分类。
市场细分：对消费者行为数据进行分层分组。
化学信息学：对化合物结构进行相似性分组。

优点与局限性

优点

直观易懂：树状图提供了数据层次结构的清晰视觉表示。
无需预设簇数：可以获得所有可能聚类数的结果，用户可根据需要选择切割点。
丰富的相似性信息：保留了数据点之间成对距离或相似性的详细信息。

局限性

计算复杂度高：对于大规模数据集（ $n$ 很大），计算和存储距离矩阵开销巨大。
不可逆性：一旦合并或分裂，决策不能撤销，可能导致局部最优。
对噪声和异常值敏感：特别是单连接法。
算法敏感性：不同的距离度量和连接准则可能产生差异很大的结果。

实现与软件

层次聚类是主流统计和数据分析软件的标准功能：

编程语言/库：
- R语言：stats 包中的 hclust() 函数（凝聚法）和 diana() 函数（分裂法）。
- Python：SciPy 库的 scipy.cluster.hierarchy 模块，或 scikit-learn 的 AgglomerativeClustering 类。
- MATLAB：linkage 和 cluster 函数。
专业软件：SPSS, SAS, Cluster 3.0, MeV 等。

参考文献

Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. （经典教材，对层次聚类有权威论述）
Müllner, D. (2011). Modern hierarchical, agglomerative clustering algorithms. arXiv preprint arXiv:1109.2378. （系统回顾了现代高效的凝聚聚类算法，如最近邻链算法）
Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244. （提出了著名的沃德法连接准则的原始论文）
Kaufman, L., & Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons. （聚类分析的经典入门书，包含对层次方法的深入讨论）
R Core Team (2023). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. URL https://www.R-project.org/. （作为实现层次聚类的主要工具之一，其文档和众多扩展包提供了丰富的实践指南）

词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。

如果您认为本词条还有待完善，请编辑