吃瓜学习笔记3-第四章决策树（ID3决策树、C4.5决策树、CA
决策树就是一个判别的过程，比如说我想知道这是一个好瓜还是坏瓜，怎么做呢？你可以从瓜的属性进行划分，可能纹理模糊的是坏瓜，纹理清晰的是好瓜。决策树就是通过一系列的属性不断去划分，最终得到这个是好瓜还是坏瓜。
西瓜数据集2.0上基于信息增益生成的决策树
决策树学习基本算法
ID3决策树
我们划分的目的是希望分支结点所包含的样本尽可能属于同一类别，也就是结点的纯度越来越高。一说到纯度，我们都可以用信息熵来计算。
"信息熵" (information entropy)是度量样本集合纯度最常用的一种指标.假定当前样本集合D 中第k 类样本所占的比例为Pk (k = 1, 2,. . . , IγI) ，则D的信息熵定义为
公式4.1
Ent(D) 的值越小，则D 的纯度越高.
举个例子，如果好瓜是1/2，坏瓜1/2，则Ent(D)值是最大的，但如果好瓜是1，坏瓜是0，Ent(D)值是最小的，为0.因为都是好瓜，纯度肯定是最高的，没有其他杂质。
解释了纯度，接下来是如何找到最优的属性划分。像上图，它是认为纹理是最优属性，就划分。
ID3决策树是用信息增益为准则来选择划分属性的。
假定离散属性a有V 个可能的取值{}，若使用a来对样本集D 进行划分，则会产生V 个分支结点,其中第v个分支结点包含了D 中所有在属性a 上取值为
的样本, 记为
. 我们可根据式(4.1) 计算出
的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重
，即样本数越多的分支结点的影响越大，于是可计算出用属性a 对样本集D 进行划分所获得的"信息增益" (information gain)
信息增益
一般而言，信息增益越大，则意味着使周属性a 来进行划分所获得的"纯度提升"越大.最优属性就是信息增益最大的那个属性。
西瓜书上P75-P77有个完整的例子说明。
C4.5决策树
实际上，信息增益准则对可取值数目较多的属性有所偏好(比如“编号”这个属性可取值很多，且样本数太少，容易过拟合)，为减少这种偏好可能带来的不利影响，我们采用"增益率" (gain ratio) 来选择最优划分属性.
增益率定义为：
4.3
其中
4.4
IV(a)称为属性a 的"固有值".增益率的公式可以了解到，IV(a)越大，则增益率越小。IV(a)的公式实际上就是信息熵的公式，如果属性a*的取值太多，不确定性就很高。
C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于信息增益平均水平的属性，再从中选择增益率最高的。
CART决策树
CART 决策树使用"基尼指数" 来选择划分属性,数据集D 的纯度可用基尼值来度量:
Gini(D) 越小，则数据集D 的纯度越高.因为Gini(D)主要反映在数据集D中随机抽取的两个样本是异类的概率。
属性a的基尼指数定义为
我们在候选属性集合A 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性.
但是，一般CART决策树是二叉树，这个公式并不适合，为此这个属性a的基尼指数应该写成：
就是a=V和a≠V这两种情况来算。把全部情况都算出来，然后把最小的基尼指数属性作为划分点。南瓜书有最详细的例子。
总结
决策树最主要的步骤就是找到最优属性。
ID3决策树是取信息增益最大的属性作为最优属性。
C4.5决策树最优属性：先从候选划分属性中找出信息增益高于信息增益平均水平的属性，再从中选择增益率最高的。
CART决策树是最小的基尼指数属性作为最优属性。
感谢datawhale提供的学习交流平台和资源，学习视频可以参照：Datawhale吃瓜教程
