决策树分裂

什么是决策树

举个校园相亲的例子，今天校园的小猫(女)和小狗(男)准备配对，小猫如何才能在众多的优质????的心仪的狗呢？于是呢？有一只特乖巧的小猫找到了你，你正在学习机器学习，刚好学习了决策树，准备给这只猫猫挑选优质狗，当然，你不仅仅是直接告诉猫哪些狗是合适你的？你更应该详细的给猫讲解决策树是如何根据它提出的标准选出的符合要求的狗呢？
猫给出如下信息：
年龄<0.5 不心仪；年龄大于>=0.5 6.5<=体重<=8.5;心仪; 年龄>=0.5 体重>8.5 长相好 心仪;其余情况不心仪; 根据上述条件可以构造一颗树：

上面的图就是决策树，最终的结果是心仪或者不心仪。决策树算法以树形结构表示数据分类的结果

基本概念

决策树属于也只能非参数学习算法、可以用于解决(多)分类问题，回归问题。 回归问题的结果，叶子结点的平均值是回归问题的解。
根节点：决策树具有数据结构里面的二叉树、树的全部属性
非叶子节点 ：（决策点） 代表测试的条件，数据的属性的测试
叶子节点 ：分类后获得分类标记，最后没有异议条件的节点
分支： 测试的结果

训练算法

基于信息熵的构造

当选择某个特征作为节点时，我们就希望这个特征的信息熵越小越好，那么不确定性越小

njnj: 第j个类别，在样本中出现的频数
SS: 样本个数
对于离散属性，直接计算信息熵，连续属性，就需要划分区间，按区间计算信息熵。

1. 基于某一层的数据集 a. 遍历计算所有属性，遍历相应属性以不同值为分截点的信息熵 b. 选择信息熵最小的作为节点

2. 如果到达终止条件，返回相应信息，否则，按照分支重复步骤1    

        ID3算法： 信息增益最大化

决策树构建过程：

1、将所有训练数据集放在根节点上；

2、遍历每种属性的每种分割方式，找到最好的分割点；

3、根据2中最好的分割点将根节点分割成多个子节点（大于等于2个）；

4、对剩下的样本和属性重复执行步骤2、3，直到每个子节点中的数据都属于同一类为止。

C4.5算法：

C4.5算法是采用信息增益率来进行节点的分裂的，公式为：,

其中,     ,

而,    ,并且要求信息增益率越大越好。

下面举例具体计算，如下图为各种天气下是否打高尔夫球的表格。

Day	Outlook	Temperature	Humidity	Windy	Play Golf
1	Sunny	85	85	F	N
2	Sunny	80	90	T	N
3	Overcast	83	78	F	Y
4	Rainy	70	96	F	Y
5	Rainy	68	80	F	Y
6	Rainy	65	70	T	N
7	Overcast	64	65	T	Y
8	Sunny	72	95	F	N
9	Sunny	69	70	F	Y
10	Rainy	75	80	F	Y
11	Sunny	75	70	T	Y
12	Overcast	72	90	T	Y
13	Overcast	81	75	F	Y
14	Rainy	71	80	T	N

步骤1：将所有的节点放在根节点上，计算此时根节点的信息熵为：

步骤2：遍历每种属性的每种分割方式，先看Outlook属性，它有三种取值Sunny, Rainy, Overcast,

故,

  

  

  

故按照Outlook属性分裂的话信息增益为：

而Outlook属性本身的分裂信息熵为：

故最终的信息增益率为：

 

接下来计算Humidity的信息增益率。因为Humidity为连续型的属性，故其计算方法相对于离散型的属性计算会复杂很多。

对于Humidity属性，我们先对其进行升序排列如下：

Day	Humidity	Play Golf
7	65	Y
6	70	N
9	70	Y
11	70	Y
13	75	Y
3	78	Y
5	80	Y
10	60	Y
14	80	N
1	85	N
2	90	N
12	90	Y
8	95	N
4	96	Y

然后就是选取分裂节点，那么对于连续型属性，它的分裂节点是任意相邻的两个取值的中点，我们从第一个开始，取65和70的加权均值：，解释一下，对于65和70这两个数值，

因为65只有一个，70有3个，所以分别乘以1/4和3/4，然后在计算按68.75来分裂的信息熵：

再选取第二个分裂点：

同理可得所有的分裂点的信息熵：

分裂点	68.75	71.25	76.5	79.5	81.25	88.333	91.667	95.5
信息熵	0.893	0.925	0.895	0.850	0.838	0.915	0.930	0.893

 由表可知，节点81.25作为分裂节点时，其信息熵最小，所以信息增益最大，故将此节点作为分裂点。这里用信息增益最大而不是信息增益率最大作为连续型属性分裂节点的评判标准，

是为了防止连续型属性每个取值都对应了一个样本，这样的分裂信息熵就最大了。对于分裂点81.25，其对应的信息增益率的计算如下：

同理对于属性Temperature也是如上的操作，先排序，再算信息熵，结果如下：

分裂点	64.5	66.5	68.5	69.5	70.5	71.667	73.5	76.667	80.5	82	84
信息熵	0.893	0.93	0.94	0.925	0.895	0.939	0.939	0.915	0.94	0.93	0.827

其信息增益率为：

最终得到所有的属性的信息增益率为：

属性	Outlook	Windy	Humidity	Temperature
信息增益率	0.156	0.049	0.109	0.305

选取信息增益率最大的Temperature属性作为分裂属性，分类结果如下：

对于Temperature <=84的节点继续进行分裂，只不过分裂的时候去掉Temperature属性以及Temperature>84的节点里的样本，重复上面步骤。