决策树，从名字上看，就知道其模型的结构为树结构，决策树既可以用于分类，也可以用于回归之中。在分类问题中，我们可以认为其是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。在学习过程中，利用训练数据和损失函数最小化的原则来构建决策树模型，在分类过程，利用模型对新数据进行分类。直接构建模型，说明决策树是一个判别模型。在学习过程，决策树有主要的三个步骤：特征选择，决策树的生成，决策树的修剪。根据三个步骤的不同，出现了三种决策树的算法：ID3,C4,5,CART.
决策树模型是树结构，树中存在二种结点，一种是分支结点，对于分支结点，代表了特征或属性，另一种是叶子结点，对于叶子结点，代表了类别。分支结点代表了属性对于特征空间的划分。决策树与if-then规则紧密联系，对于从根结点到叶节点的一条路径对应一条规则。决策树学习到的模型其实也可以转变为给定特征条件下类的条件概率分布。P(Y|X)，X为特征条件，Y为类结合，不同的P(Y|X)对应于划分的一个单元，最终实现对于特征空间的划分。 决策树的学习过程，就是从训练数据中学习一个决策树模型，而本质是从训练数据中总结出一套分类规则，我们希望得到一棵决策树与训练数据的矛盾比较小，并且具有不错的泛化能力的结构。换个角度，也可以是学习这样一个条件概率，使条件概率的模型对于训练数据具有很好的拟合效果，并且对于未知数据也有很好的预测。
决策树的损失函数：正则化的极大似然函数，使损失函数最小化为优化目标来得到模型。但选择最优决策树模型使NP完全问题，所以一般采用的是启发式的方法，近似求解最优化问题，这样得到的决策树是次最优的。
决策树学习的算法，通常是一个递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集进行判断，如果子数据集大多被分为一类，也就是基本被分类正确，然后就可以结束判断，如果子数据不能基本正确分类，则继续选择特征对子数据集继续进行分隔，直到数据集基本被分类正确或没有多余的特征可以被选择，最终生成一棵决策树。对决策树而言，很可能发生过拟合的现象，我们需要对已生成的树进行剪支，使树变得简单，然后使其具有很好的泛化能力。对于决策树而言，就是一个条件概率分布，不同深浅的决策树，对应于模型的全局选择，决策树的生成只考虑局部最优，相对的，决策树的剪支则需要靠全局最优。
【特征选择】根据什么标准哪个特征，然后对数据进行了划分。有几种方式，信息增益，信息率，基尼指数。
信息增益，采用了训练集中的特征和类的互信息来进行度量g(D,A)=H(D)-H(D|A)。缺点在于可能会偏向于多值属性，也就是取值比较多的特征。 对数据集（或子集）D，计算其每个特征的信息增益（对数据集进行划分），选择信息增益最大的特征。
增益率，解决信息增益容易偏向于多值属性的情况，在分母上增加了特征熵，也是就缓解了多值属性的压力。但容易产生不平衡的划分。
Gini指数，对应于不纯度的问题。Gini指数越小，说明纯度越高。对于Gini指数而言，是一种二元划分，形成的树是二叉树。最小基尼指数的子集，也就是最大化不纯度的降低。倾向于多值属性，并且在类的数量比较多的情况下，倾向于产生相等大小的分区和纯度。
三者的不同之处在于，对于信息增益与增益率而言，是通过计算熵来得到的值，而基尼指数则是通过多项式计算得到的，所以前二种运算量大，计算速度小。在ID3中，采用了信息增益，对于C4，5中，采用了增益率，在CART中，采用了基尼指数。
【决策树的生成以及决策树的剪支】
对于ID3算法，这个是最开始的算法，最开始也代表其是最粗略的一种算法。在这个算法中，采用具有最大信息增益的特征来作为划分的特征。具体过程是：从根节点（全部数据）开始利用信息增益最大的特征来对数据进行划分，得到结点（子数据），然后判断结点是否有资格来作为叶子结点，如果不具有资格成为叶子结点，则继续重复根结点划分的操作，对于成为叶子结点的资格在于结点中的数据可以基本被分类正确，或者没有多余的特征（所有特征的信息增益都很小）可以被选择的时候，也就是最后全部分支都到了叶子结点的位置，就可以结束决策树的构建过程，这个时候决策树就生成了。
从ID3的生成过程，我们可以看出，要求其特征都是离散的情况，没有考虑到连续的特征情况，也没有对特征如果有缺失值的情况下考虑，并且仅仅考虑生成的过程，没有考虑树的剪支，很可能产生过拟合，并且对于信息增益这种特征度量方式而言，是偏向于多值属性，这个也没有解决。
对于C4，5算法，是对于ID3的改进，改进说明有了进步，可以说质的飞跃，但最终还是会被拍死在沙滩上。对于C4,5而言，采用了增益率来进行特征的选择。具体过程是：从根结点开始（全部数据），根据增益率最大的特征将数据划分，形成结点（子数据），在特征选择中，考虑到了连续值的情况，对于连续值得情况，取连续值得中间平均点来计算信息增益，此时将最大信息增益点来作为离散分类点，并且连续的特征在之后还是可以作为特征来进行选择；考虑到了缺失值的情况，缺失值是特征缺失的情况下，如何选择划分的属性，划分的了属性，缺失的特征的处理。。在有缺失值的属性上计算增益率时？可以忽略，或利用特定值来填充（均值，特殊值），对有缺失值的样本进行分裂时，分配给哪个子数据集？可以忽略，也可以采用特定值来填充（均值，最有可能的值），可以单独的分支，对新样本的有缺失值进行分类时？可以走单独分支，可以分配最常见的分支，可以分配最有可能的值，可以不进行分类，给缺失值分配最有可能的值。并且在C4,5 中考虑了剪支，可以说是人群中最闪耀的那颗星了，哈哈。
C4,5中的剪支，是通过正则化系数来实现，也叫做悲观剪支。树的生成过程是一个局部优化的过程，剪支的过程是一个全局优化的过程，利用了极小化决策树整体的代价函数(cost function)或损失函数(loss function)来实现。
在这个中，主要是通过正则化参数来进行调节。主要流程是，确定参数后，判断，每条边是否需要被剪支。因为只需考虑局部的差的情况，所以我们可以通过动态规划来实现。
从C4,5的生成过程，我们看出他的努力，但仍有一些遗留问题没有解决，比如特征选用采用的是熵模型，运算量比较大，剪支算法还可以更优化一点，过拟合的问题仍然存在，形成的树为多分叉的树，而二叉树的处理更快，并且仅仅能用于分类操作，对于回归操作没有办法解决。
CART（Classification and regression tree），可以说是集大成者呀，特征选择采用了gini指数，既可以用于分类，也可以用于回归问题。首先，我们谈一下分类的情况，对于分类而言，具体过程为：对于根节点(全部数据)，同样利用最大化纯度的降低的特征来作为（最小基尼指数的特征）来作为特征，此处注意的是二分类的情况，也就是处理需要寻找最优特征，以及划分点，除此之外与上面的构建过程没有二异。对于CART对于连续值得处理过程与C4,5类似，只是度量方式不同，而对于离散值得处理又不同，对于C4,5而言，离散的特征只会被选择一次，而对于CART而言，离散的特征因为没有完全被使用，所以在后续中还是可以选择用于划分的。然后，我们考虑回归的问题，回归是连续的情况，尤其对于输出是连续的情况。回归就类似于对空间进行划分R1,R2..Rm，然后对每个划分中都有一个固定的输出值cm，我们利用每个空间中的平方误差来表示训练误差，也就是让训练误差最小，所以我们采用了利用在这个区域的均值来作为了这个区域最好的输出值。所以这个关键的问题，就在于如何划分区间。思路就是，假定我们已经有了划分的变量，以及划分的点，然后由此得到二个区域，然后求最小化的情况，最终得到真实的划分变量以及划分点，然后不断的对空间进行划分，最终得到一棵回归树。对于CART，回归问题中，采用的最小平方误差来寻找特征和特征的划分点，而在分类问题中，采用了gini指数来寻找特征和特征的划分点。
对于CART的剪支，是一种后剪支的策略，从完全生长的决策树的底端剪去一些子树，使决策树变小。剪支的过程分为二个过程：第一个是得到具体的候选的决策树序列，具体是指，不断的剪支直到根节点，形成子树序列{T0,T1,T2,...,Tn}，然后通过交叉验证法在独立的验证数据集上进行测试，选出最优子树。从上图，我们可以看出，正则化参数alpha权衡了训练数据的拟合以及模型复杂度之间的关系。alpha=0时，说明完全生长的决策树就是目前最优子树；alpha增大时，不断的剪支以使决策树模型的复杂度减低最终实现达到固定的参数情况下的最优子树；alpha无穷大时，说明只有单结点树时最优子树。也就是{T0,T1,...Tn}是在alpha不断改变的基础上求出的当前最优子树，也就是每一个都是C4,5中剪支操作的结点，需要将C4,5动起来，得到最终的结果。如果我们采用C4,5中的那种操作，实在是太低效了，所以，人的智慧都是无穷无尽的。先人是怎么考虑这个问题的呢？首先，对于一个结点，如果这个结点作为根的子树，以及只有这个结点的树的损失函数相等的情况下，那么就可以把这个结点为根的其余部分简直了，因为是一样的。。然后对每个内部结点，计算相等时的alpha的值，然后内部结点计算的最小的alpha的值，对其进行响应的内部结点的剪支，然后得到当前alpha状态下的最优子树，最终得到最优子树的序列，然后通过验证集来对最优子树的序列来进行交叉验证，最终选取最优子树。在CART的剪支中，我们与C4，5的不同之处在于C4,5确定了一个alpha的值，然后依此判断树的每一个结点是否应该被去除，而CART的alpha则是一个需要计算的可以变化的量，也就是对于每个内部结点计算如果要剪掉这个内部结点的分支部分时的alpha，然后依此排列出一个按照alpha大小排列的子树的集合，最终通过交叉验证，然后从这个子树的集合中，最终得到最优的那个。。
