可以看看这个笔记
一、初步认识
理解“信息增益”，就差不多把决策树中的用到的技术理解了。可以参考对熵的理解中，对信息增益的解释。
我们想要构造一个分类器，按照不断地判断一些特征条件，一路走到包含同一类的子集中，就能确定属于哪一类了。
这个分类器的构造，采用西瓜书或者机器学习实战中的递归函数进行构造，直到最终所有具有相同类型的数据均在一个数据子集内为止。此时，就学习好了一个分类器，就可以用来进行分类了。
在这个学习过程中，选择出最优的划分属性，x对y的信息增益最大的那一个作为划分属性（ID3），随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。
二、如何选择最优划分属性
2.1信息熵
信息熵是度量样本集合纯度最常用的一种指标。信息熵越小，则样本D纯度越高。
一个属性能够划分出越纯的信息熵，则这个属性越符合条件：泛化能力 强。比如，大小，太小的一定是坏瓜，那么这个属性就可以很好地 进行判断。
2.2属性划分
2.2.1、ID3，用信息增益划分
假设一个西瓜有的一个属性a有V个可能的取值（比如，a为颜色，V为青绿，乌黑，浅白），那么用这V个属性对样本D进行划分，会产生V个样本分支结点。其中，第v个分支节点包含了D在用颜色属性划分时，颜色为v的样本，这里记为Dv。
我们可以根据公式计算出Dv的信息熵，也可以计算出其余的v的信息熵。最好的情况时 ，所划分出的每个Dv都是同一类别，纯度很高，也就是信息熵很小。
再考虑到划分以后每个结点样本数目不同，样本数越多的分支结点的影响越大，于是给每个结点赋予权重。
于是可以计算出用属性a对样本集D进行划分所得的“信息增益”。
一般来说，信息增益越大，意味着使用属性a来进行划分所获得的“纯度提升”越大，越能符合决策树的要求。
因此，我们采用信息增益来进行决策树的划分属性选择。这就是著名的ID3（Iterative Dichotomiser迭代二分器）决策树学习算法。
2.2.2、 C4.5 用信息增益率划分
上一小节提到过，样本数越多的分支结点影响越大。
实际上，信息增益准则对数目比较多的属性有所偏好。
比如，如果有17个西瓜，那么把“编号”作为一个属性的话，那么这个属性的可取值v有17个，会产生17个分支，利用信息增益准则计算得到的信息增益是0.998，远大于其他的划分属性。因为每个结点仅包含一个样本，那说明这个分支结点的纯度已达到最大。但是，这样的决策树不具有泛化能力，无法对新样本进行有效预测。
为减少这种不利影响，我们采用“增益率”来选择最优划分属性。
即用上一小节的划分属性的信息增益，除以一个IV(a)，其中属性a的可能取值数目越多（V越大），则IV(a)越大。
按照增益率越高的 属性进行划分。
需要注意的：增益率准则对可取值数目比较少的属性有所偏好。因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从计算出每个候选划分属性的信息增益，找出信息增益高于平均水平的属性，再从中选择增益率最高的。
2.2.3、 CART 使用基尼指数进行划分
基尼指数的公式，反映了从数据集D中随机抽取 两个样本，其类别标签 不一致的概率。同样的，基尼指数越小，数据集D的纯度越高。
于是，可以得到属性a的基尼指数。用划分后基尼指数最小的属性用以进行划分。
参考图
三、剪枝处理
剪枝的基本策略有“预剪枝”和“后剪枝”。
预剪枝：指在决策树生成过程中，对每个结点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶节点。
“后剪枝：”先从训练集生成一棵完整的决策树，然后自底向上的对非叶节点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶节点。
判断决策树泛化性能是否提升的方法：可使用西瓜书2.2节介绍的性能评估方法。比如留出法，即预留一部分数据用作“验证集”以进行性能评估。
四、连续与缺失值
5.1 连续值处理
采用连续属性离散化技术。
比如采用二分法。
五、决策树的优缺点
优点：
便于理解，计算量不大，对中间值的缺失不敏感，可以处理不相关特征数据
缺点：
对于不连续值，表现不是很好
容易过拟合
KNN的优缺点
优点：简单有效
缺点：
1必须保存全部数据集，可能会使用大量的存储空间。
2必须对每个数据计算距离，耗时。
3无法给出任何数据的基础结构信息，无法知道平均实例样本和典型实例样本具有什么特征。
