「决策树」| Part1—ID3/C4.5决策树
文章来自公众号：AlgorithmDeveloper，专注机器学习与Python，编程与算法，还有生活。
1. 从相亲问题到决策树
决策树是一种常见的机器学习算法，其工作过程类似于人做决策的过程，比如相亲：你大概会根据对方的财富、工作、人品、外貌等特征来决定要不要去会会这个人，根据你的决策，于是就有了以下这颗决策树。图中绿色的节点称为内部节点，表示一个特征或者属性；黄色的节点为叶节点，表示决策结果。
可是这么多特征为什么先选择财富来进行决策，选择完第一个特征后又该选择哪个特征进行决策会找到最满意的对象呢，有没有定量的标准告诉我们先选哪个后选哪个特征，有，这就是决策树的关键，为了解决这个问题，于是就有了ID3、C4.5、CART算法。
2. ID3算法
2.1 信息增益
2.1.1 熵H(X)
熵用来度量事物的不确定性/混乱程度，事物越不确定/越混乱，熵值越大。假设特征X有n种不同的取值，取值i的概率为pi，特征X的煽值计算公式如下：
2.1.2 条件熵H(X|Y)
条件熵表示在已知Y后，X的不确定性：
2.1.3 信息增益
信息增益度量了在已知Y后，X不确定性的减少程度：
ID3算法就是选择信息增益最大的特征来对当前节点进行分类。
2.2 生成ID3决策树
输入：训练数据集D，输出类别C，每个样本有n个离散特征，特征集合为A，阈值e；
输出：决策树T。
Step1：判断样本是否属于同一类别Ci：如果是返回单节点树T，输出类别Ci；
Step2：判断特征是否为空：如果是返回单节点树T，输出类别为样本数最多的类别；
Step3：计算每个特征对数据集D的信息增益，选择信息增益最大的特征Ai；
Step4：如果Ai
Step5：否则，根据特征Ai的取值，对每个取值产生一个子节点，返回增加子节点的树T；
Step6：对第i个子节点，以D=Di，A=A-Ai，递归执行Step2-Step6.
2.3 ID3算法缺点
(1) ID3算法只能用于离散特征，无法处理像身高、体重等连续特征，只能用于分类，不能用于回归；
(2) 没有考虑缺失值的情况；
(3) 不确定性程度相同的特征，其取值越多，信息增益越大。如：变量X1有3个特征值，每个特征值的概率为1/3；变量X2有4个特征值，每个特征值的概率为1/4；其不确定性程度完全相同，但是X2的信息增益大于X1。
3. C4.5算法
3.1 信息增益比
为了校正ID3算法偏向于取特征值较多的特征，C4.5定义信息增益比作为选择特征的依据，其值为信息增益与特征煽的比值，由于特征取值越多的特征其煽值H(X)越大，这样可以校正2.3-(3)的问题。
3.2 处理连续特征
C4.5通过将连续特征离散化，使其可以处理连续特征变量。比如，m个样本，其连续特征X总共有m个取值，顺序排列为a1，a2，…，am：
Step1：取相邻两个样本的平均值作为划分点，这样总共可以得到m-1个划分点；
Step2：依次以每个划分点将数据分为两类，计算信息增益；
Step3：选择信息增益最大的点作为该特征的分类点。
与离散特征不同，如果当前节点选择的特征为连续特征，该特征还可以参与后续节点的划分。
3.3 缺失值处理
3.3.1 选定了划分特征，但是某些样本缺少该特征值
比如：一节点选定特征X进行划分，该特征有三个特征值x1,x2,x3，在某个样本缺少特征X的情况下，将该样本同时划入x1,x2,x3，权重分别为w1,w2,w3；如果x1,x2,x3中包含特征X的样本个数分别为1,2,3，那么w1=1/6,w2=2/6,w3=3/6。
3.3.2 样本某些特征缺失，如何选择划分特征
比如：总共有20个样本，其中含有特征X的样本有10个，这样的话就只用含有特征X的10个样本计算信息增益比，将计算结果乘以0.5，作为特征X的信息增益比，以进行特征选择。
3.4 C4.5算法缺点
(1) C4.5生成多叉树，运算效率低；
(2) 只能用于分类，不能用于回归。
4. ID3/C4.5决策树剪枝
利用递归算法生成决策树，直到不能继续下去为止，容易使决策树太过复杂，导致过拟合，即训练数据集分类正确率很高，但是对测试数据集分类的准确率不高。通过剪枝可以简化决策树模型，通过最小化决策树的损失函数实现剪枝。
决策树的损失函数：
其中：|T|表示叶子节点个数，Nt表示叶子节点中的样本个数，Ht(T)表示叶子节点的煽。
其中：Ntk表示叶子节点中第k类样本点的个数。
最终损失函数表示为：
确定alpha值后，从叶节点往上遍历，如果将一组叶节点减掉之前和之后的损失函数关系为
，则将这组叶节点减掉，其父节点将变为叶节点。
决策树生成时只考虑提高信息增益或者信息增益比从而更好的拟合训练数据，而剪枝通过优化损失函数来减小模型复杂度。
Coding Your Ambition！
