目录
4.1基本流程
4.2划分的选择
4.2.1信息增益
4.2.2增益率
4.2.3基尼指数
4.3剪枝处理
4.4连续与缺失值
4.4.1连续值处理
4.4.2缺失值处理
4.5多变量决策树
4.1基本流程
一颗决策树包括一个根结点、若干个内部结点和若干个叶结点；叶结点对于决策结果，其他每个节点对应属性测试，根结点包含样本全集。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，基本流程遵循分而治之策略。
决策树的生成是一个递归过程.在决策树基本算法中，有三种情形会导致递归返回: (1) 当前结点包含的样本全属于同一类别，无需划分; (2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分; (3) 当前结点包含的样本集合为空，不能划分.
4.2划分的选择
4.2.1信息增益
"信息熵"是度量样本集合纯度最常用的一种指标. 
假定当前样本集合D 中第k 类样本所占的比例为 Pk ，则D的信息熵定义为
Ent(D) 的值越小，则D 的纯度越高.
信息增益越大，则意味着使用离散属性a来进行划分所获得的"纯度提升"越大.
ID3 决策树学习算法 就是以信息增益为准则来选择划分属性.
4.2.2增益率
如果每个分支结点仅包含一个样本，这些分支结点的纯度己达最大.然而，这样的决策树显
然不具有泛化能力，无法对新样本进行有效预测.
信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5 决策树算法 不直接使用信息增益，而是使用"增益率" 来选择最优划分属性。
增益率定义为：
属性 a 的可能 取值数目越多(即V 越大)，则 IV(α) 的值通常会越大.
增益率准则对可取值数目较少的属性有所偏好
4.2.3基尼指数
CART 决策树使用"基尼指数" 来选择划分属性.数据集 D的纯度可用基尼值来度量:
Gini(D) 越小，则数据集D 的纯度越高.
4.3剪枝处理
剪枝是决策树学习算法对付"过拟合"的主要手段.决策树剪枝的基本策略有"预剪枝" 和"后剪枝"
预剪枝是指在决策树生成过程中，对每个结点在划 分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
后剪枝则是先从训练集生成一棵完整的决策树， 然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.
4.4连续与缺失值
4.4.1连续值处理
由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结 进行划分.此时，连续属性离散化技术可派上用场 最简单的策 略是采用 二分法对连续属性进行处理，这正 C4.5 决策树算法中采用的机制。
给定样本集D和连续属性a，取a的中位点作为候选划分点，然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。
其中 Gain(D ， a , t) 是样本集D 基于划分点t二 分后的信息增益.于是，我们就可选择使 Gain(D，a， t) 最大化的划分点.
4.4.2缺失值处理
现实任务中常会遇到不完整样本，即样本的某些属性值缺失.
我们需解决两个问题:
(1) 如何在属性值缺失的情况 进行划分属性选择?
(2) 给定划分属性?若样本在该属性上的值缺失，如何对样本进行划分?
给定训练集D 和属性a ，令 D1 表示 D 中在属性a 上没有缺失值的样本子集.对问题(1) ，显然我们仅可根据 D1 来判断属性a 的优劣.
对问题 (2) ，若样本x 在划分属性a 上的取值己知,则将 x 划入与其取值对应的子结点，且样本权值在于结点中保持为 Wx. 若样本x 在划分属性a 上的取值未知，则将x 同时划入所有子结点,且样本权值在与属性值 av 对应的子结点 中调整为凡 rv,Wx ，直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去.
4.5多变量决策树
多变量决策树结合了决策树的结构和多变量分析的特点，用于处理多个输入变量之间复杂的非线性关系。它通过递归地将数据集划分为不同的子集，并在每个节点处根据多个输入变量进行决策，从而生成一个可以预测或分类目标变量的模型。与传统的决策树不同，多变量决策树在每个划分点可以考虑多个变量的组合，从而更准确地捕捉输入变量之间的交互作用和复杂的关联关系。这种模型适用于需要考虑多个变量对最终结果影响的复杂问题。