决策树
决策树就像金角大王银角大王问孙猴子问题，他们先问“孙悟空，我叫你一声你敢答应吗？”，倘若孙猴子答应那么就被收到葫芦里，倘若孙猴子不答应他们又接着问“孙行者，我叫你一声你敢答应吗？”
依次类推无穷尽也，直到将孙猴子抓起来为止。
决策树是一个树形接口，我们知道对一颗树来说他有这些基本的元素 根节点 叶子节点 内部节点等，对决策树来说根节点包含了所有的样本数据，而叶子节点则包含着分类的结果，其中最重要的乃是内部节点。
内部节点包含了对属性的判断，在挑西瓜问题中就是根绝样本数据对瓜的色泽 纹理 敲击声音 瓜蒂 等属性的判断。
对于一个瓜来说，其有多个可判定属性，那么又应该从哪一个属性开始呢？我们使用增益来进行判断
信息增益
我们可以使用信息熵来表示信息的混乱程度
信息熵越那么信息越混乱信息上越小那么信息越单一，那么我们分类的目的就是使得分类后的数据更单一即信息熵越小，分类前的信息熵与分类后的信息熵的差值我们称为这个分类行为的信息增益
对分类后的信息熵的描述我们使用分类后每个分组样本数量占所有样本数量的比例乘以每个分组计算的信息熵的和来描述
我们的目标是选出最优的分类属性即
然后依次选出每一次分类的最优属性 直到所有样本都被分类完成
信息增益率
使用信息增益来进行属性选择面临一个问题，即信息增益更偏向属性可选择值多的属性，让所我又17个样本 而属性a恰好又17个属性 且每一个属性都有一个对应的样本那么如果按照属性a进行分类那么得到的信息增益就是
整个样本的信息熵，也就是按照属性a进行划分得到的信息增益达到最大，那么就没有必要再进行进一步的划分了，这样的划分结果虽然对样本数据来说是一个很好的分类结果，但是对与真实的预测数据来说往往就不是那么好用了
将导致过拟合的问题，而我们进行模型训练的最终目标并不是对样本数据能有100%的拟合度，而是需要模型提供很好的泛化能力对未知样本也有很好的预测能力，所以需要在这两者之间进行折衷。于是使用了惩罚项来对模型
训练过程中的过拟合问题进行约束。所以诞生了信息增益率的概念。
其中
信息增益率更偏向属性可选择值小的结果，所以在进行训练的时候并不是一股脑地使用信息增益率，而是先使用信息增益选出信息增益较大的属性再使用信息增益率在这些属性中进行选择这种启发式的手段。
基尼指数
使用基尼指数来衡量信息的纯度
基尼指数表明了随机从样本中抽取两个值其类别不一致的概率，因此基尼系数越小，样本的纯度越高
按照属性a进行分类的基尼指数定义为
最终的目标数选择基尼指数最小的结果
剪枝处理
剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning) [Quinlan, 1993]。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
连续值处理
使用二分法对连续值进行认为的划分 比如又1-10的连续值，且样本中的的取值又1，3，5，6，7，9 那么选择的划分点为每两个取值的中点即 2 ，4， 5.5， 6.5， 8 然后按照这些重点进行分类对每个分类结果计算信息增益
选择信息增益最大的划分点进行最后的划分。举例如果以划分点2进行分类计算的信息增益为0.98 以划分点5.5计算的信息增益为0.99且为最大值 那么就选择划分呢点5.5进行分类 将小于不大于5.5的划分为1类而大于5.5的划分为另一类。
缺失值处理
缺失值处理的方式是先对没有缺失的属性计算信息增益 然后乘以无缺失值样本所占比例作为整体样本的信息增益。然后引入权值的概念，如果样本属性值无缺失定义权值为1，如果有缺失将该样本划入到每一个子节点并对每一个
子节点定义权值为 该属性在样本中的概率分布，比如 有西瓜样本数据 其纹理等于清晰的样本有 5 个 等于模糊的有 4 个 等于稍微模糊的有 2 个 那么对于缺失纹理数据的样本在其子节点中的权值分别为 5/11 4/11 2/11 。
多变量决策树
使用线性方程将两个属性关联起来作为一个整体来参与分类决策。
