决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。
每个内部节点（非叶子节点）表示一个属性上的测试条件，每个分支代表一个测试输出结果，每个叶节点代表一种类别
决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。
特征：
一棵决策树的生成过程主要分为以下3个部分:
划分数据集的最大原则是：使无序的数据变的有序。
熵降低的速度越快越好==>树的高度最矮
基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。
可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话，其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性
C4.5是ID3的一个改进算法，继承了ID3算法的优点。
一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值
有人可能会问，信息为啥这样定义啊？答曰：前辈得出的结论。这就跟1+1等于2一样，记住并且会用即可。上述式中的对数以2为底，也可以e为底(自然对数)。
若随机事件发生的结果记为X，且待分类的事物可能划分在N类中，分别是x1，x2，……，xn，每一种取到的概率分别是P1，P2，……，Pn，那么X的熵就定义为：
反映了每一个元素在该类别下的不纯度，如{1,2,3,4}跟{1,1,1,2}相比,每个元素1-4的logPi都很大,因此sum的熵就要大很多。
注：有"某个类别的结果"的熵（某个特征有多个值），也有"某事件结果"的熵（该事件有多个特征）。直观来讲，结果种类越多，熵值越大。
当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empiricalentropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。
根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：
经过计算可知，数据集D的经验熵H(D)的值为0.971。
▲熵值越高，则数据混合的种类越高，其蕴含的含义是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关）
表示在已知随机变量X的条件下随机变量Y的不确定性，其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望:
设特征A有n个不同的取值{a1,a2,···,an}，根据特征A的取值将D划分为n个子集{D1,D2，···,Dn}，|Di|为Di的样本个数。记子集Di中属于Ck的样本的集合为Dik，即Dik=Di∩Ck，|Dik|为Dik的样本个数
信息增益(informationgain)表示得知特征X的信息后，而使得Y的不确定性减少的程度。定义为集合D的经验熵H(D)与给定特征A条件下D的经验条件熵H(D|A)之差:
一般地，熵H(D)与条件熵H(D|A)之差称为互信息(mutualinformation)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
其中|Di|为特征该类别的数量，Pi为该类别下为true（事件发生）的概率
以信息增益进行分类决策时，存在偏向于取值较多的特征的问题。于是有了基于信息增益比的分类决策方法C4.5。C4.5与ID3都是利用贪心算法进行求解，不同的是分类决策的依据不同。
信息增益比率度量:信息增益比率度量Gain(D，X)\分裂信息度量SplitInformation(D，X)
1、是一种不等性度量，表示一个随机选中的样本在子集中被分错的可能性；2、通常用来度量收入不平衡，可以用来度量任何不均匀分布；3、是介于0~1之间的数，0-完全相等，1-完全不相等；4、总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）
上面式子表述的意思就是，加入特征X以后，数据不纯度减小的程度.
如果D被特征A划分为D1、D2两部分，这个时候就是统计均值，样本数据集D的基尼系数：
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元R1,R2,...Rm，并且在每个单元Rm上有一个固定的输出值Cm，于是回归树模型可表示为：
我们希望每个单元上的Cm，可以是的这个平方误差最小化。易知，当Cm为相应单元的所有实际值的均值时，可以到最优：
假设，我们选择变量xj为切分变量，它的取值s为切分点，那么就会得到两个区域：
当j和s固定时，我们要找到两个区域的代表值c1，c2使各自区间上的平方差最小：
前面已经知道c1，c2为区间上的平均：
那么对固定的j只需要找到最优的s，然后通过遍历所有的变量，我们可以找到最优的j，这样我们就可以得到最优对（j，s）,（特征j，特征分类值s），并s得到两个区间。
这样的回归树通常称为最小二乘回归树（leastsquaresregressiontree）。
上述过程表示的算法步骤为:
[图片上传失败...(image-16b3b4-1570443243559)]
C4.5和CART既可以处理离散型属性，也可以处理连续性属性。对于离散型描述属性，处理方法与ID3相同。对于连续分布的特征，其处理方法是：
以C4.5为例子，在C4.5中，对连续属性的处理如下：
1、对特征的取值进行升序排序
2、两个特征取值之间的中点作为可能的分裂点，从分裂点将数据集分成两部分，计算每个可能的分裂点的信息增益（InforGain）。优化算法就是只计算分类属性发生改变的那些特征取值。
3、选择修正后信息增益(InforGain)最大的分裂点作为该特征的最佳分裂点
4、计算最佳分裂点的信息增益率（GainRatio）作为特征的GainRatio。注意，此处需对最佳分裂点的信息增益进行修正：减去log2(N-1)|D|（N是连续特征的取值个数，D是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）
Q：为什么这边是使用的信息增益率？
A：经证明，在决定连续特征的分界点时采用增益这个指标（因为若采用增益率，splittedinfo影响分裂点信息度量准确性，若某分界点恰好将连续特征分成数目相等的两部分时其抑制作用最大），而选择属性的时候才使用增益率这个指标能选择出最佳分类特征。
在构建决策树的过程时，提前停止。
决策树构建好后，然后才开始裁剪。
ID3、C4.5算法中的剪枝原理是给定α，事实上很难一次给出理想的α。CART剪枝不再给定一个α，然后选择最优决策树，而是通过设定不同的α，通过交叉验证选择最优CART树，也就是：
训练集：得到不同的子树;
测试集：交叉验证选择最优树.
1）完全没剪：
2）只剩根节点：
在α较小或者为0时，有：
在α取+∞大时，有：
α是连续变量，因此总有临界点：
为了不混淆变量，重新定义：
α大于g(t)就是该剪。简而言之：
对于同一棵树的结点，α都是一样的，当α从0开始缓慢增大（或者从+∞慢慢减小），总会有某棵子树该剪，其他子树不该剪的情况，即α超过了某个结点的g(t)，但还没有超过其他结点的g(t)。这样随着alpha不断增大，不断地剪枝，就得到了n+1棵子树，接下来只要用独立数据集测试这n+1棵子树，试试哪棵子树的误差最小就知道那棵是最好的方案了。
递归的结束条件：
1.当某集合的值全是同一类时，那么该子集直接可作为叶子节点，为一个类别，此时不再下探。
2.在决策树构造过程中可能会出现这种情况：所有特征都作为分裂特征用光了，但子集还不是纯净集（集合内的元素不属于同一类别）。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点，此时不再下探