决策树算法

1.决策树

　　在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

　　分类树（决策树）是一种十分常用的分类方法。它是一种监督学习，所谓监督学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。1986年 Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。通常使用的分类回归树（class and regress tree）是一个二叉树,所有的输入从根节点一步一步走到叶子结点，也就是所有的数据最总都会落到叶子结点，既可以做分类也可以做回归。

　　比如，有如下信息，前四列分别为天气情况、、温度、湿度、风。最后一列为标签列，是否出去玩。

　　通过上面信息，我们可以根据不同划分构造不同决策树。

　　(1)基于天气划分

　　(2)基于温度划分

 　　(3)基于湿度划分

　　(4)基于是否有风划分

　　上面的树很简单，只做了一次划分，如何构造一颗好的决策树呢？就没那么容易了,需要考虑的问题有很多。

2.信息熵与信息增益

　　信息熵（information entropy）是信息论的基本概念。描述信息源各可能事件发生的不确定性。最早由1948年香农提出，并给出数学表达式。信息熵是用于衡量不确定性的指标，也就是离散随机事件出现的概率，简单地说“情况越混乱，信息熵就越大，反之则越小”。

　公式如下:

　具体理解如下：

　　上式中，一般底数b为2。P表示事件发生的概率。其信息熵与概率的关系图如下图所示，当随件变量取值n=2时，表示i取1到2。此时P=1/n=0.5时，取最大值熵，此时混乱度最大，事件发生的不确定性最大。通过证明还可以发现信息熵的范围为[0,log(n)]。概率与信息熵的图大致为

　　信息增益是表示特征X使得类Y的不确定性减少的程度，信息增益 = 熵 – 条件熵。计算公式如下：

 　　式子中，后一项H(Y|X)为条件熵，其计算公式如下：

　　上式中P为x发生的概率。

3.基尼指数(Gini Index)

　　P为概率，P越接近1，系数越接近0，表明划分越纯。Gini系数用于CART算法中。

4.ID3决策树

　　ID3使用了信息增益的方式构造决策树，通过信息增益来划分数据属性。到底选择哪个特征作为第一个根节点，需要计算各自的信息增益。在给的数据列表中，标签列有9天玩，5天不玩，整体信息熵(2为底)为：

　　H(X)=－9/14 *log(9/14)－5/14 *log(5/14)＝0.940 bits

　　对四个特征outlook、Temp、Humidity、Windy四个特征逐一分析，找出信息增益最大的作为根节点。先对outlook特征开始计算：

　　H(outlook=sunny)＝－2/5*log(2/5)－3/5*log(3/5)＝0.971 bits

　　H(outlook=overcast)=0

　　H(outlook=rainy)=－3/5*log(3/5)－2/5 *log(2/5)＝0.971 bits

　　则选择outlook作为条件熵的信息熵值为：

　　H(Y|X=outlook)＝5/14 *0.971＋4/14 * 0＋5/14 *0.971＝0.693 bits

　　选择Outlook作为划分的决策树信息增益为

　　Gain(outlook)=0.940-0.693=0.247

　　同样的方式，计算剩下三个特征的信息增益，如下：

　　Gain(temperature)=0.029

　　Gain(humidity)=0.152

　　Gain(windy)=0.048

　　所以选择outlook作为根节点。

　　继续根据不同分支按照剩下三个特征进行划分：

　　第一个分支:

　　Gain(temperature|sunny)=0.571

　　Gain(humidity|sunny)=0.971

　　Gain(windy|sunny)=0.420

　　所以对该部分数据按湿度进行划分。

　　第二个分支：

　　标签全部为yes,信息熵为0，无需划分。

　　第三个分支：

　　Gain(temperature|rainy)=0.020

　　Gain(humidity|rainy)=0.020

　　Gain(windy|rainy)=0.971

　　所以对该部分数据按照是否有风进行划分。

　　通过划分可以得到如下的决策树：

划分后，每一个叶子结点的标签类型相同，不用再划分了。

5.C4.5决策树

　　使用信息增益率（解决ID3问题考虑自身熵）来选择属性分裂，能处理连续型数据和不完整数据, 采用信息增益比选择特征，减少因特征值多导致信息增益大的问题。现在假设这样一种情况，如果每个属性每种类别只有一个样本，那么属性信息熵就为0.（或者增加一列ID，为样本的编号）此时，信息增益为类别熵，无法选择有效的分类特征。信息增益率用信息增益/内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它）。信息增益率公式如下：

IGR=Gain/H

　　Gain为信息每个属性的信息增益，H为每个属性的信息熵。分别计算outlook、temperature、humidity、windy的属性信息熵(以2为底)。

　　H(outlook)=-5/14*log(5/14)-5/14*log(5/14)-4/14*log(4/14)=1.577

　　H(temperature)= -4/14*log(4/14)-6/14*log(6/14)-4/14*log(4/14)=1.556

　　H(humidity)=-7/14*log(7/14)-7/14*log(7/14)=1.0

　　H(windy)= -6/14*log(6/14) -8/14*log(8/14)-8/14*log(8/14)=0.985

　　计算信息增益率：

　　IGR(outlook)=Gain(outlook)/H(outlook)=0.247/1.577=0.156

　　IGR(temperature)=Gain(temperature)/H(temperature)=0.029/1.556=0.0186

　　IGR(humidity)=Gain(humidity)/H(humidity)=0.152/1.0=0.151

　　IGR(windy)=Gain(windy)/H(windy)=0.048/0.985=0.049

　　Outlook的信息增益率最高，选择它作为分裂属性，也就是第一个根节点。最后对子节点根据信息增益率不断重复划分的过程，其结果与前面ID3算法得到的图一样。

　　这里举个例子，只是便于简单理解C4.5算法。如下：

　　C4.5算法倾向于选取属性的类别少的，这里是windy(与windy信息增益率最高一致)属性。

6.CART决策树(Classification and Regression Tree)

　　使用GINI系数来当做衡量标准。CART分类树算法每次仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。CART使用了 ​ ​CCP代价复杂度剪枝算法​​，对C4.5的剪枝方法进行了优化。关于CART算法目前没有详细研究，后续补充。

7.决策树剪枝

　　决策树在不断重复划分过程中，有时会造成决策树分支过多导致过拟合.因此需要剪枝降低过拟合风险。决策树剪枝策略包括预剪枝与后剪枝。

　　预剪枝：限制深度，叶子节点个数，叶子结点样本数，信息增益量等。

　　后剪枝：通过一定的衡量标准判断是否需要分裂。衡量标准损失如下：

　　C(T)为gini系数与样本数乘积，α为系数，T(leaf)为叶子结点阈值，叶子节点越多，损失越大。如果分裂后C变大，就不需要分裂。

8.决策树生成的终止条件

　　(1) 当子节点中的样本属于同一类

　　(2) 子节点没有样本

　　(3) 特征已经用完了

参考资料:

https://zhuanlan.zhihu.com/p/493238757

https://blog.csdn.net/zjsghww/article/details/51638126

https://blog.51cto.com/u_14974790/5284485

不足或错误之处，恳请指正，有帮助请点赞，谢谢！