基本流程
决策树（decision tree）是基于树结构进行决策的，是一种符合人类面临决策问题时的思考方式。采用了分而治之（divide-and-conquer）的策略。
决策树建立的基本流程
决策树的构建是一个递归的 过程，决策树生成算法中有三种情形会导致递归：
- 当前结点包含的样本全属于同一类别，无需划分
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
- 当前结点包含的样本集合为空，不能划分
划分选择
一般而言，随着划分过程不断进行，希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。有一些用来衡量和选择划分方式的基准与方法。
信息增益
信息熵（information entropy）是度量样本集合纯度最常用的一种指标。
假定当前样本集合D中第k类样本所占的比例为pk(k=1,2,…, |y|)，则D的信息熵定义为：
Ent(D)的值越小，D的纯度越高
假设离散属性a有V个可能的取值{a1, a2, a3, …, aV}，若使用a来对样本集D进行划分，则会产生V个分支节点。可以计算用属性a对样本集D进行划分所获得的信息增益（information gain）为：
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大，因此，如果选择信息增益进行决策树划分属性的选择，则选择属性满足：
信息增益准则对可取值数目较多的属性有所偏好
增益率
为了减少信息增益准则对可取值数目较多的属性有所偏好而带来的不利影响，可以使用增益率（gain ratio）来选择最优化分属性。增益率定义为：
其中
成为属性a的固有值（intrinsic value）。属性a的可能取值数目越多，IV(a)的值通常也会越大。
基于增益率的属性划分采用一个启发式判定：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性
信息增益率准则对可取值数目较少的属性有所偏好
基尼指数
CART****决策树（Classfication and Regression Tree）使用基尼指数（Gini index）选择划分属性。数据集D的纯度可以使用基尼值来衡量：
Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，数据集D的纯度越高。
属性a的基尼指数定义：
属性划分时选择：
剪枝处理
剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。
- 预剪枝（prepruning）：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
- 后剪枝（postpruning）：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
两种剪枝处理的优缺点比较：
- 预剪枝显著减少了决策树的训练时间开销和测试时间开销；后剪枝的训练时间开销比未剪枝和预剪枝都大得多
- 预剪枝基于贪心算法本质禁止一些分支展开，给预剪枝决策树带来了欠拟合的风险；后剪枝决策树通常比预剪枝决策树保留了更多的分支，且其欠拟合风险很小，泛化性能往往优于预剪枝
连续与缺失值
连续值处理
由于连续属性的可取值数目不在有限，所以需要进行连续属性的离散化技术。
连续值处理的最常用方式：二分法（bi-partition）
将连续属性值使用一个划分点t进行划分，划分成Dt+和Dt-两个子集，对于相邻的两个属性值ai和ai+1，t可以去其中间值，对于连续属性a，可以考察包含n-1个元素的候选划分点集合：
然后像离散属性值一样考察这些划分点，选取最优的划分点进行样本集合的划分，例如Gain公式可以修改成：
计算后选择使得Gain(D, a, t)最大化的划分点
缺失值处理
当样本数据中有些样本在某些属性下出现数据缺失的情况是，需要有两个问题进行解决：
- 如何在属性值缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
给定训练集D和属性a，令D'a表示D中在属性a上没有缺失值的样本子集。对于问题第一点，仅可根据D'a来判断属性a的优劣。
假定我们为每个样本x赋予一个权重wx，并定义：
从而可以将信息增益推广为：
其中
对于问题的第二点，若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为wx，若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，且样本权值在与属性值av对应的子结点中调整为 rv×wx，即让同一个样本以不同的概率划入到不同的子结点中去。
多变量决策树
当把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成：
若使用斜线划分边界，则可以视为多变量决策树（multivariate decision tree），实现“斜划分”甚至更复杂的划分，即每个非叶节点变为属性的线性组合，形如
的一个线性分类器，学习的过程也是确定wi的过程
全文参考：周志华 著 《机器学习》
转载请注明出处，本文永久更新链接：小天才的杂货铺-个人博客
