一、决策树原理
决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成，一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。
内部节点：对应于一个属性测试
叶节点：对应于决策结果
根节点包含样本全集；
每个节点包括的样本集合根据属性测试的结果被划分到子节点中；
根节点到每个叶节点的路径对应对应了一个判定测试路径；
决策树的结构还是比较好理解的，如果不明白，可以看一下图中的例子，这是一个简单判断这个键盘我喜不喜欢的决策树模型：
目标变量可以采用一组离散值的树模型称为分类树(常用的分类树算法有ID3、C4.5、CART)，而目标变量可以采用连续值（通常是实数）的决策树被称为回归树(如CART算法)。
决策树算法本质上就是要找出每一列的最佳划分以及不同列划分的先后顺序及排布。
优点：分类速度快，能在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
缺点：对未知的测试数据未必有好的分类、泛化能力，即可能发生过拟合现象，此时可采用剪枝或随机森林。
二、决策树学习算法：
1、特征选择
特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。我们希望在不断划分的过程中，决策树的分支节点所包含的样本尽可能属于同一类，即节点的“纯度”越来越高。而选择最优划分特征的标准不同，也导致了决策树算法的不同。
为了找到最优的划分特征，我们需要先了解一些信息论的知识：
（1）熵（混乱程度）
在信息论和概率统计中，熵(entropy)是表示随机变量不确定性的度量，熵越大，随机变量的不确定性越大。
设X是一个取有限值的离散随机变量，其概率分布为：
则随机变量X的熵定义：
为了能够更好地理解熵的意义，举一个例子来说明。A集合：[1,2,3,1,1,4,5]，B集合：[1,1,1,1,1,1,2]，A集合的熵更大。
（2）条件熵
设有随机变量(X,Y)，条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。
随机变量X给定的条件下随机变量Y的条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望。
其中：
（3）信息增益
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少程度。
特征A对训练数据集D的信息增益g(D,A),为集合D的熵H(D)与特征A给定条件下D的条件熵H(D|A)之差，即：
（4）信息增益率
特征A对训练数据集D的信息增益率gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即：
，注意区别H(D|A)、HA(D)。
（5）基尼指数
基尼指数Gini(D)表示集合D不确定性，基尼指数Gini(D，A=a)表示集合D经A=a分割后的不确定性(类似于熵)，基尼指数越小，样本的不确定性越小。
分类问题中，假设有K个类，样本点属于第k类的概率为pk,则概率分布的基尼指数定义为：
如果样本集合D根据特征A是否取某一可能值aa被分割成D1和D2两部分，即
则在特征A的条件下,集合D的基尼指数定义为
（6）相对熵 KL散度
相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求pp与qq之间的对数差在pp上的期望值
（7）交叉熵
2、决策树生成
（1）ID3算法原理
ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征递归地构建决策树。
（1）熵：在信息论中，熵是随机变量不确定性的度量，也就是熵越大，则随机变量的不确定性越大。
（2）条件熵：条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。
（3）信息增益定义为：，即集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(H|A)之差。
选择划分后信息增益大的作为划分特征，说明使用该特征后划分得到的子集纯度越高，即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。
缺点：信息增益偏向取值较多的特征。原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分后的熵更低，即不确定性更低，因此信息增益更大。
ID3算法：
（2）C4.5算法原理
C4.5算法是对ID3算法做了改进，在生成决策树过程中采用信息增益比来选择特征。我们知道信息增益会偏向取值较多的特征，使用信息增益比可以对这一问题进行校正。
信息增益比定义：特征A对训练数据集D的信息增益比GainRatio(D,A)定义为其信息增益Gain(D,A)与训练数据集D的经验熵H(D)之比。
C4.5算法过程与ID3算法一样，区别就是将选择特征的方法由信息增益改成信息增益比。
（3）CART算法原理
基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点跟熵相似。
CART算法：
（4）回归树
回归树是可以用于回归的决策树模型，一个回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。与分类树不同的是，回归树对输入空间的划分采用一种启发式的方法，会遍历所有输入变量，找到最优的切分变量j和最优的切分点s，即选择第j个特征xj和它的取值s将输入空间划分为两部分，然后重复这个操作。
而如何找到最优的j和s是通过比较不同的划分的误差来得到的。
一个输入空间的划分的误差是用真实值和划分区域的预测值的最小二乘来衡量的，即
举个例子，我们要对南京市各地区的房价进行回归预测，我们将输入空间不断的按最小误差进行划分，得到类似下图的结果，将空间划分后，我们会用该单元内的均值作为该单元的预测值，如图中一片区域的平均房价作为该划分单元内房价的预测值。
3、决策树的剪枝
剪枝是决策树学习过程中处理过拟合的方法，剪枝分为预剪枝和后剪枝。
预剪枝是在生成过程中，对节点进行估计，如果当前划分不能提升系统的泛化能力，则停止分割。
后剪枝是先生成一颗完整的树，自底向上对非叶节点进行考察，如果该叶节点替换成的子树能带来泛化性能的提升，则用该节点替换为叶节点。
