机器学习算法（二）——基于决策树的分类预测
1. 理论篇
1.1 决策树的介绍
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
分类树（决策树）是一种十分常用的分类方法。他是一种监督学习，所谓监督学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
1.2 基本流程
1.2.1 不纯度（GINI系数&Entropy熵）
- 熵 信息 噪音
熵：一种事物的不确定性（比如说买西瓜的时候不知道甜不甜）
信息：消除不确定性，排除干扰，确定情况（卖西瓜的人保证很甜）
噪音：也是一种消息，但是不能消除你对某件事的不确定性。
- 不纯度（impurity）–GINI系数：
一个简单的计算示例如下图：（GINI值越小，纯度越高）
3. 不纯度（impurity）–Entropy熵：
信息熵是一种衡量数据混乱程度的指标，信息熵越小，则数据的“纯度”越高。
设X是一个取有限个值的离散随机变量，其概率分布为：
则随机变量X的熵定义为 ：
1.2.2 划分选择
- 划分选择
划分选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
信息增益法：选择具有最高信息增益的特征作为测试特征，利用该特征对节点样本进行划分子集，会使得各子集中不同类别样本的混合程度最低，在各子集中对样本划分所需的信息（熵）最少。
（信息增益既可以用熵也可以用GINI系数来计算）
信息增益计算：
给出如下示例更好的理解计算过程：
- 逻辑过程
根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。
-
从根节点出发，根节点包括所有的训练样本。一个节点（包括根节点），若节点内所有样本均属于同一类别，那么将该节点就成为叶节点，并将该节点标记为样本个数最多的类别。
-
采用信息增益法来选择用于对样本进行划分的特征，该特征即为测试特征，特征的每一个值都对应着从该节点产生的一个分支及被划分的一个子集。决策树中特征均为符号值，即离散值。若非连续值则要将其离散化。
-
递归上述划分子集及产生叶节点的过程，这样每一个子集都会产生一个决策（子）树，直到所有节点变成叶节点。
-
递归操作的停止条件：
- 一个节点中所有的样本均为同一类别，即产生叶节点
- 没有特征可以用来对该节点样本进行划分，此时也强制产生叶节点
- 没有样本能满足剩余特征的取值，此时也强制产生叶节点
1.2.3 剪枝处理
决策树容易过拟合，理论上可以完全分得开数据。所以一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。
-
预剪枝(Pre-Pruning)：边建立决策树边进行剪枝 ---->更实用在决策树生成分支的过程中，设定一些规则来避免树过度生长：
- 信息增益（率）小于阈值就不再分裂
- 节点样本数小于阈值（例如1%）就不再分裂
- 若分裂后叶节点样本数少于阈值（例如0.5%）就不再分裂
- 树深度大于阈值（例如8层）就不再分裂
-
后剪枝(Post-Pruning)：当建立完决策树后来进行剪枝
- 根据每个分支的分类错误率及每个分支的权重，计算该节点不修剪时预期分类错误率。
- 对于每个非叶节点，如果修剪后分类错误率变大，即放弃修剪；否则将该节点强制为叶节点，并标记类别。
- 产生一系列修剪过的决策树候选之后，利用测试数据对各候选决策树的分类准确性进行评价，保留分类错误率最小的决策树。
1.2.4 连续与缺失值
1.2.5 多变量决策树
1.3 算法
1.3.1 ID3算法/基本决策树
ID3算法是最早提出的一种决策树算法，ID3算法的核心是在决策树各个节点上应用信息增益准则来选择特征，递归的构建决策树。
具体方法：
从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点
再对子节点递归的调用以上方法，构建决策树
直到所有的特征信息增益均很小或没有特征可以选择为止。
选择ID作为特征，信息增益最大，可是这个特征意义不大，每个ID必然只对应一个类别。
故信息增益的问题的就从这里引发出来，它的缺点就是偏向选择取值较多的属性。
1.3.2 C4.5算法
首先介绍下什么是信息增益率：
信息增益率（比）：信息增益除以该属性本身的熵
利用信息增益率对多分叉进行惩罚，避免了ID3算法中的归纳偏置问题。
C4.5算法与ID3算法决策树的生成过程相似， 改用信息增益率（比）来选择特征。主要是改进了样本特征部分：
- 基本决策树要求特征A取值为离散值，对连续值可采用如将连续值按段进行划分，然后设置哑变量等方式。
- 特征A的每个取值都会产生一个分支，可能会因为划分出的子集样本量过小停止继续分支，强制标记类别后可能会产生局部错误。可采用A的一组取值作为分支条件；或采用二元决策树，每一个分支代表一个特征取值的情况（只有是否两种取值)。
- 某些样本在特征A上值缺失，可用其他样本中特征A出现最多的值来填充，或均值、中值等，有些也可用样本内部的平滑来补值，当样本量很大时也可丢弃缺失值样本。
- 数据集不断减小，子集样本量也越来越小，所构造出的决策树就可能出现碎片、重复、复制等问题，可以利用样本的原有特征构造新的特征进行建模。
- 信息增益法会倾向于选择取值比较多的特征（这是信息熵的定义决定了的）。增益比率法（gain ratio）将每个特征取值的概率考虑在内，及gini索引法，χ2χ2条件统计表法和G统计法等。
问题：
模型是用较为复杂的熵来度量，使用了相对较为复杂的多叉树，只能处理分类不能处理回归等
1.3.3 CART
既可以做分类，也可以做回归，只能形成二叉树。
CART算法稍微复杂一些，马一篇写的很好的博文来学习。CART算法详解