机器学习与数据挖掘
范式 监督学习 無監督學習 線上機器學習 元学习（英语：Meta-learning (computer science)） 半监督学习 自监督学习 强化学习 基于规则的机器学习（英语：Rule-based machine learning） 量子機器學習
问题 统计分类 生成模型 迴歸分析 聚类分析 降维 密度估计（英语：density estimation） 异常检测 数据清洗 自动机器学习 关联规则学习 語意分析 结构预测（英语：Structured prediction） 特征工程 表征学习 排序学习（英语：Learning to rank） 语法归纳（英语：Grammar induction） 本体学习（英语：Ontology 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 transformer（英语：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）
查 论 编

决策树学习是统计学、数据挖掘和机器学习中使用的一种预测建模方法。它使用决策树作为预测模型（英语：Predictive modelling），从样本的观测数据（对应决策树的分支）推断出该样本的预测结果（对应决策树的叶节点）。

按预测结果的差异，决策树学习可细分两类。（1）分类树，其预测结果仅限于一组离散数值。树的每个分支对应一组由逻辑与连接的分类特征，而该分支上的叶节点对应由上述特征可以预测出的分类标签。（2）回归树，其预测结果为连续值（例如实数）。

在决策分析中，一棵可视的决策树可以向使用者形象地展示决策的结果和过程。在数据挖掘和机器学习中，一棵决策树主要用于描述数据（此后亦可基于习得的预测模型去支持决策)。本页侧重描述数据挖掘中的决策树。

在数据挖掘中决策树训练是一个常用的方法。目标是创建一个模型来预测样本的目标值。例如右图。每个内部节点对应于一个输入属性，子节点代表父节点的属性的可能取值。每个叶子节点代表输入属性得到的可能输出值。

一棵树的训练过程为：根据一个指标，分裂训练集为几个子集。这个过程不断的在产生的子集里重复递归进行，即递归分割。当一个训练子集的类标都相同时递归停止。这种“决策树的自顶向下归纳”（TDITD）^[1]是贪心算法的一种, 也是目前为止最为常用的一种训练方法，但不是唯一的方法。

数据以如下方式表示:

${\displaystyle ({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)}$

其中Y是目标值，向量x由这些属性构成, x₁, x₂, x₃ 等等，用来得到目标值。

在数据挖掘中，决策树主要有两种类型:

• 分类树 的输出是样本的类标（例如花的分類，股票漲跌等）。
• 回归树 的输出是一个实数 (例如房子的价格，病人待在医院的时间等)。

术语分类和回归树 (CART) 包含了上述两种决策树, 最先由Breiman 等提出.^[2] 分类树和回归树有些共同点和不同点—例如处理在何处分裂的问题。^[2]

有些集成的方法产生多棵树：

• 装袋算法（Bagging）, 是一个早期的集成方法，用有放回抽样法来训练多棵决策树，最终结果用投票法产生。^[3]
• 随机森林（Random Forest） 使用多棵决策树来改进分类性能。
• 提升树（Boosting Tree） 可以用来做回归分析和分类决策^[4][5]
• 旋转森林（Rotation forest） – 每棵树的训练首先使用主元分析法 (PCA)。^[6]

还有其他很多决策树算法，常见的有:

• ID3算法
• C4.5算法
• CHi-squared Automatic Interaction Detector (CHAID). 在生成树的过程中用多层分裂.^[7]
• MARS:可以更好的处理数值型数据。

构建决策树时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。^[8] "最好" 的定义是使得子节点中的训练集尽量的纯，表示所分裂出的子节点中的集合越相近。不同的算法使用不同的指标来定义"最好"。本部分介绍一些最常见的指标。

在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。

假设y的可能取值为${\displaystyle J}$个类别，令${\displaystyle i\in \{1,2,...,J\}}$，${\displaystyle p_{i}}$表示被标定为第${\displaystyle i}$类的概率，则基尼不纯度的计算为：

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}p_{i}\sum _{k\neq i}p_{k}=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-{p_{i}}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}{p_{i}}^{2}=1-\sum _{i=1}^{J}{p_{i}}^{2}}$

ID3, C4.5 和 C5.0 决策树的生成使用信息增益。信息增益是基于信息论中信息熵与資訊本體理论。

信息熵定义为：

${\displaystyle \mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}}$

其中${\displaystyle p_{1},p_{2},...}$加和为1，表示当前节点中各个类别的百分比。^[9]

$${\displaystyle \overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Weighted Sum of Entropy (Children)}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{a}{p(a)\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|a)}}}$

例如，数据集有4个属性：outlook (sunny, overcast, rainy), temperature (hot, mild, cool), humidity (high, normal), and windy (true, false), 目标值play（yes, no）, 总共14个数据点。为建造决策树，需要比较4棵决策树的信息增益，每棵决策树用一种属性做划分。信息增益最高的划分作为第一次划分，并在每个子节点继续此过程，直至其信息增益为0。

使用属性windy做划分时，产生2个子节点：windy值为真与为假。当前数据集，6个数据点的windy值为真，其中3个点的play值为真，3个点的play值为假；其余8个数据点的windy为假，其中6个点的play值为真，2个点的play值为假。 windy=true的子节点的信息熵计算为：

${\displaystyle I_{E}([3,3])=-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}=1}$

windy=false的子节点的信息熵计算为：

${\displaystyle I_{E}([6,2])=-{\frac {6}{8}}\log _{2}^{}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}^{}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}^{}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}^{}{\frac {1}{4}}=0.8112781}$

这个划分（使用属性windy）的信息熵是两个子节点信息熵的加权和：

${\displaystyle I_{E}([3,3],[6,2])=I_{E}({\text{windy or not}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.8112781=0.8921589}$

为计算使用属性windy的信息增益，必须先计算出最初（未划分）的数据集的信息熵，数据集的play有9个yes与5个no：

${\displaystyle I_{E}([9,5])=-{\frac {9}{14}}\log _{2}^{}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.940286}$

使用属性windy的信息增益是：

${\displaystyle IG({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.940286-0.8921589=0.0481271}$

与其他的数据挖掘算法相比，决策树有许多优点:

• 易于理解和解释，人们很容易理解决策树的意义。
• 只需很少的数据准备，其他技术往往需要数据归一化。
• 即可以处理数值型数据也可以处理類別變數数据。其他技术往往只能处理一种数据类型。例如关联规则只能处理类别型的而神经网络只能处理数值型的数据。
• 使用白箱模型，输出结果容易通过模型的结构来解释。而神经网络是黑箱模型，很难解释输出的结果。
• 可以通过测试集来验证模型的性能。可以考虑模型的稳定性。
• 強健控制。对噪声处理有好的強健性。
• 可以很好的处理大规模数据。

• 训练一棵最优的决策树是一个完全NP问题。^[10][11] 因此, 实际应用时决策树的训练采用启发式搜索算法例如 贪心算法来达到局部最优。这样的算法没办法得到最优的决策树。
• 决策树创建的过度复杂会导致无法很好的预测训练集之外的数据。这称作过拟合.^[12] 剪枝机制可以避免这种问题。
• 有些问题决策树没办法很好的解决,例如 异或问题。解决这种问题的时候，决策树会变得过大。 要解决这种问题，只能改变问题的领域^[13] 或者使用其他更为耗时的学习算法(例如統計關係學習（英语：Statistical relational learning）或者歸納邏輯程式設計（英语：Inductive logic programming）).

• 对那些有类别型属性的数据，信息增益会有一定的偏置。^[14]

在决策树中, 从根节点到叶节点的路径采用汇合。 而在决策图中, 可以采用最小描述長度（MML）来汇合两条或多条路径。^[15]

演化算法可以用来避免局部最优的问题^[16][17]

• 决策树剪枝
• 二元决策图
• CART
• ID3算法
• C4.5算法

• Building Decision Trees in Python From O'Reilly.
• An Addendum to "Building Decision Trees in Python"（页面存档备份，存于互联网档案馆） From O'Reilly.
• Decision Trees page at aaai.org, a page with commented links.
• Decision tree implementation in Ruby (AI4R)（页面存档备份，存于互联网档案馆）
• Building Decision Tree In Bash（页面存档备份，存于互联网档案馆）