一般树的结构

根据数据集我们可以提取出特征
色泽:青绿、乌黑、浅白
根蒂:蜷缩、稍蜷、硬挺
敲声:浊响、沉闷、清脆
纹理:清晰、稍糊、模糊
脐部:凹陷、稍凹、平坦
触感:硬滑、软粘

如果我们就单纯的使用这些特征构造一棵树

这样的话我们就穷举出西瓜所有可能存在的特征组合。但是这种方法有一下的一些问题：
1.我们使用穷举的方法，树会非常的大。特征向量没增加一维，构造树的空间复杂度和事件复杂度都会呈指数上升。
2.我们数据集中的数据有可能是噪声点。如这个特征组合的西瓜在现实世界中本来是好瓜，但是数据集中将其判断为坏瓜了，这样我们再次遇到同样特征的西瓜可能会误判。
3.模型会过拟合，对现实世界中的西瓜的泛化能力不强。
4.遍历这种树来获取信息的速度很慢。

划分选择

信息熵、信息增益ID3

信息熵本是信息论中表示信息混乱程度的，用来度量样本的纯度。

紧接着引出信息增益，信息增益越大，意味着划分的纯度提升越大。信息增益越大越好。

这样我们构造树的时候，使用信息熵和信息增益来决定下一层使用使用什么特征来进行划分。这样我们构造出来的树看起来就科学很多。
具体划分过程参见西瓜书P75-77

增益率C4.5

信息增益对取值数目较多的属性有偏好(为啥我也不知道，周志华老师是这样说的，那么我们就接受这一个理论吧)，为了减少这种影响，引入新的划分选择“增益率”

具体划分过程参见西瓜书P77-79

基尼指数CART

基尼指数原来是指国际上通用的、用以衡量一个国家或地区居民收入差距的常用指标。基尼系数最大为“1”，最小等于“0”。基尼系数越接近0表明收入分配越是趋向平等。
基尼指数越小代表数据集的纯度越高。


具体划分过程参见西瓜书P79

剪枝处理

剪枝是解决决策树中过拟合的主要手段，需要借助验证集
预剪枝：构造树的时候进行的，自顶向下的
后剪枝：树构造结束后进行操作的，自底向上的

预剪枝

预剪枝是在决策树生成的过程中，使用验证对每个节点划分前先进行估计，若当前划分不能提高决策树的泛化性能，就停止划分并将当前的节点标记为叶子节点。
先计算当前节点的精度，在计算划分后的精度，如果当前的精度比划分后精度高就不划分了。

后剪枝

后剪枝是先使用训练集构造好树，然后自底向上对非叶子节点进行考察，判断将该节点变成叶子节点，能不能带来泛化性能的提升。