机器学习与数据挖掘
范式 监督学习 無監督學習 線上機器學習 元学习（英语：Meta-learning (computer science)） 半监督学习 自监督学习 强化学习 基于规则的机器学习（英语：Rule-based machine learning） 量子機器學習
问题 统计分类 生成模型 迴歸分析 聚类分析 降维 密度估计（英语：density estimation） 异常检测 数据清洗 自动机器学习 关联规则学习 語意分析 结构预测（英语：Structured prediction） 特征工程 表征学习 排序学习（英语：Learning to rank） 语法归纳（英语：Grammar induction） 本体学习（英语：Ontology learning） 多模态学习（英语：Multimodal learning）
监督学习 (分类 · 回归) 学徒学习（英语：Apprenticeship learning） 决策树学习 集成学习 Bagging 提升方法 随机森林 k-NN 線性回歸 朴素贝叶斯 人工神经网络 邏輯斯諦迴歸 感知器 相关向量机（RVM） 支持向量机（SVM） 迁移学习 微调
聚类分析 BIRCH CURE算法（英语：CURE algorithm） 层次 k-平均 Fuzzy 期望最大化（EM） DBSCAN OPTICS 均值飘移（英语：Mean shift）
降维 因素分析 CCA ICA LDA NMF（英语：Non-negative matrix factorization） PCA PGD（英语：Proper generalized decomposition） t-SNE（英语：t-distributed stochastic neighbor embedding） SDL
结构预测（英语：Structured prediction） 圖模式 貝氏網路 條件隨機域 隐马尔可夫模型
异常检测 RANSAC k-NN 局部异常因子（英语：Local outlier factor） 孤立森林（英语：Isolation forest）
人工神经网络 自编码器 認知計算 深度学习 DeepDream（英语：DeepDream） 多层感知器 RNN LSTM GRU（英语：Gated recurrent unit） ESN（英语：Echo state network） 储备池计算（英语：reservoir computing） 受限玻尔兹曼机 GAN SOM CNN U-Net Transformer Vision transforme（英语：Vision transformer） 脉冲神经网络（英语：Spiking neural network） Memtransistor（英语：Memtransistor） 电化学RAM（英语：Electrochemical RAM）（ECRAM）
强化学习 Q学习 SARSA 时序差分（TD） 多智能体（英语：Multi-agent reinforcement learning） Self-play（英语：Self-play (reinforcement learning technique)） RLHF
与人类学习 主动学习（英语：Active learning (machine learning)） 众包 Human-in-the-loop（英语：Human-in-the-loop）
模型诊断 学习曲线（英语：Learning curve (machine learning)）
数学基础 内核机器（英语：Kernel machines） 偏差–方差困境（英语：Bias–variance tradeoff） 计算学习理论（英语：Computational learning theory） 经验风险最小化 奥卡姆学习（英语：Occam learning） PAC学习（英语：Probably approximately correct learning） 统计学习 VC理论
大会与出版物 NeurIPS ICML（英语：International Conference on Machine Learning） ICLR ML（英语：Machine Learning (journal)） JMLR（英语：Journal of Machine Learning Research）
相关条目 人工智能术语（英语：Glossary of artificial intelligence） 机器学习研究数据集列表（英语：List of datasets for machine-learning research） 机器学习概要（英语：Outline of machine learning）
查 论 编

在数据挖掘和统计学中，层次聚类（英語：Hierarchical clustering）是一种旨在建立聚类的层次结构的聚类分析方法。层次聚类的策略通常有两种：

• 凝聚（Agglomerative clustering）：一种自底向上方法，从小集群开始，逐渐将其合并，形成更大的集群；
• 分裂（Divisive clustering）：一种自顶向下方法，从单个集群开始，递归地将其拆分成更小的集群。

凝聚和分离的操作通常用贪心算法实现，结果通常用树状图展示。^[1]

标准的凝聚层次聚类（Hierarchical agglomerative clustering，HAC）算法的时间复杂度为${\displaystyle {\mathcal {O))(n^{3})}$，空间复杂度为${\displaystyle \Omega (n^{2})}$，这使它甚至难以应用于中等规模的数据集中。对于一些特殊情况，效率最优的算法（复杂度为${\displaystyle {\mathcal {O))(n^{2})}$）包括SLINK（用于单连接聚类，Single-linkage clustering）^[2]和CLINK（用于全连接聚类，Complete-linkage clustering）^[3]。当使用堆（Heap）时，一般情况下的时间复杂度降至${\displaystyle {\mathcal {O))(n^{2}\log n)}$，该改进以更多的内存需求为代价。这种改进方法的内存开销很多时候大到难以实际使用。

除了单连接聚类的特殊情况，除了穷举算法（复杂度${\displaystyle {\mathcal {O))(2^{n})}$）外，没有算法可以保证找到最优解。

使用穷举算法的分裂方法的复杂度为${\displaystyle {\mathcal {O))(2^{n})}$，不过可以通过更快的启发式方法（例如k-均值算法）进行分裂。

层次聚类的优点是可以采用任何有效的距离测量。当给定距离矩阵时，观测本身是没有必要的。

本节将对上图所示的原始数据进行聚集层次聚类（Agglomerative clustering），采取欧几里得距离度量距离。

下图展示了聚类结果的树状图：

在给定高度切割树，会得到一个特定精度的聚类结果。例如，在从上往下数的第二行切割会得到四个集群：{a}、{b, c}、{d, e}和{f}；在第三行切割会得到{a}、{b, c}、{d, e, f}，相比之前，这是一个更粗糙（coarser）的聚类结果，集群的数量更少但集群更大。

该方法合并单独的元素形成集群并得到层次（Hierarchy）。本例有六个元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步确定哪些元素合并到一个集群，判定标准通常是元素间的距离，选取两个最近的形成集群。

也可以在该步构建距离矩阵（矩阵的第i行第j列的数值为i-j元素之间的距离）。在聚类过程中，行、列被合并并形成新的距离。该方法为实现聚集层次聚类的通用方法，同时对缓存集群之间的距离有益。单连接聚类（英语：Single-linkage_clustering）是一个简单的聚集层次聚类方法。

在完成对距离最短元素b和c的合并后，形成的集群为：{a}、{b, c}、{d}、{e} 、{f}，对其进行进一步的合并需要度量集群{a}和{b, c}之间的距离（即两个集群间的距离）。通常将集群${\displaystyle {\mathcal {A))}$和${\displaystyle {\mathcal {B))}$之间的距离定义为：

• 两个集群的元素间的最大距离（又称全连接聚类（英语：Complete-linkage_clustering））：

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A)),\,y\in {\mathcal {B))\,\}.}$

• 两个集群的元素间的最小距离（又称单连接聚类（英语：Single-linkage_clustering））：

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A)),\,y\in {\mathcal {B))\,\}.}$

• 两个集群的元素间的平均距离（又称平均连接聚类（Average linkage clustering），在UPGMA方法中有应用）：

${\displaystyle {1 \over {|{\mathcal {A))|\cdot |{\mathcal {B))|))\sum _{x\in {\mathcal {A))}\sum _{y\in {\mathcal {B))}d(x,y).}$

• 所有聚类内方差的总和
• 被合并的集群方差的增加量 （Ward法（英语：Ward%27s_method）^[4]）
• 候选聚类从同一分布函数生成的概率（V-linkage）

当若干对组合具有同样的距离且为最小时，可以随机选取一对形成集群（生成不同的树状图）；也可以同时形成不同的集群（生成唯一的树状图）。^[5]

聚类算法的停止准则可以取决于数量（当形成足够少的集群时停止）；也可以取决于距离（当两个集群之间的距离足够远，以至于不能形成新集群时停止）。

DIANA（DIvisive ANAlysis Clustering）是分裂层次聚类的基础算法。^[6] 首先，所有元素归属同一个集群，然后分裂集群，直到所有元素都独立成群。由于存在${\displaystyle O(2^{n})}$种方法进行分裂，因此需要启发式（Heuristics）算法实现。DIANA选择平均异同度（Average dissimilarity）最大的元素，然后将所有与新集群相似度高于其余集群的元素划分到该集群。

• ALGLIB用C++和C#实现了多种层次聚类算法
• ELKI实现了多种层次聚类算法
• Julia在Clustering.jl包中实现了层次聚类^[7]
• Octave（GNU对MATLAB的兼容实现）实现了层次聚类（函数linkage）
• Orange（一个数据挖掘软件套件）实现了带有交互式树状图可视层次聚类
• R有内置的函数和包^[8]，提供层次聚类的函数
• SciPy在Python中实现了层次聚类
• Scikit-learn也在Python中实现了层次聚类
• Weka实现了层次聚类

• MATLAB中有层次聚类分析
• SAS在PROC CLUSTER中包含层次聚类分析
• Mathematica有一个层次聚类包
• NCSS中实现了层次聚类分析
• SPSS中包括层次聚类分析
• Qlucore Omics Explorer中包括分层聚类分析
• Stata中包括层次聚类分析
• CrimeStat中实现了近邻层次聚类算法