决策树算法

决策树算法概述

决策树是一种十分常用的分类方法。是一种监督学习。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。决策树的来源朴素，其实就是大量的if-else语句，最终根据这些if-else语句得到结果。

决策树是一种递归的逻辑结构，每个节点都可以作为一棵树，所以我们只需要对每个节点进行优化，就可以保证整个决策树是最优的。构建决策树，就是选择最优的分裂特征属性，即从当前数据的特征中选择一个最优的特征属性作为当前节点的划分标准，进行划分，从而得到最优的子树，进一步得到最优子树。最优决策树。

决策树算法的分类

ID3算法：其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所采用的合适属性。

C4.5算法：C4.5决策树生成算法相对于ID3算法的重要改进是使用信息增益率来选择节点属性。C4.5算法可以克服ID3算法存在的不足：ID3算法只适用于离散的描述属性，而C4.5算法既能够处理离散的描述属性，也可以处理连续的描述属性。

CART算法：CART决策树是一种十分有效的非参数分类和回归方法，通过构建树、修剪树、评估树来构建一个二叉树。终节点是连续变量时，该树为回归树，终节点是分类变量时，该树为分类树。

ID3算法决策树

ID3算法基于信息熵来选择最佳测试属性。信息熵是信息论中的概念，通常简称为熵，表示随机变量不确定性或者说混乱程度。设S是s个数据样本的集合，假定类别属性具有m个不同的值：Ci(i=1,2,…,m)，设S1是类C1中的样本数。对于一共给定的样本，总的信息熵公式为

其中Pi是任意样本Ci的概率，一般可以用Si/s估计

就是假设在事件A分类划分是(A1,A2,A3)，对应发生的概率是(P1,P2,P3)，那信息熵的计算公式为

条件熵H(X|Y)表示在已知随机变量Y的条件下，随机变量X的不确定性。定义为在给定条件Y下，X的条件概率分布的熵对Y的数学期望。

信息增益：使用划分前后集合熵的差值来衡量使用当前特征对于样本集合划分效果的好坏。用G表示。

信息增益越大，说明该属性对于分类提供的信息越大，选择该属性之后对分类的不确定程度越小，通俗的讲就是找到计算后G(X,Y)值最大的情况下所代表的特征。用这个特征进行分类，从而提高分类效率。

ID3算法的核心是在各决策树的各级节点上都用信息增益作为判断标准来进行属性的选择，使得在每个非叶节点上进行测试时，都能获得最大的类别分类增益，使分类后的数据集的熵最小，这样的处理办法使得树的平均深度较小，从而有效地提高了分类效率。这样问题就来了，ID3会去选择子类别多的特征，因为这样分裂出来的结果会更纯，熵会更小。但是这些属性可能没有太多的价值，这样分类可能没有很好的泛化效果。还有个缺点就是无法处理连续型变量。

C4.5算法决策树

C4.5算法决策树使用的时信息增益比进行划分。信息增益比计算公式为

其中Gain(X,Y)就是ID3算法种的信息增益，IV(Y)是Y这个属性的信息熵。需要注意的是：增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的属性作为分支标准，而是先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART算法决策树

CART的损失函数使用了一个与信息增益完全相反特征的损失函数：Gini系数。信息增益描述的是特征的混乱度，也就是信息增益越高特征越不纯净。基尼系数刚好相反，基尼系数越大，不纯度越低。

Gini指数表示在样本集合中一个随机选中的样本被分错的概率。Gini指数越小表示集合中被选中的样本被参错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。当集合中所有样本为一个类时，基尼指数为0。

Gini系数的计算公式为

条件Gini系数跟条件熵的概念类似，Gini指数的计算公式为

如果是二分类，公式为

对于数值型的数据，会从小到大进行排序后，相邻两个取平均数，对这个平均数进行gini系数求值，就是以大于这个数和小于这个数为频率。CART算法决策树一定是二叉树，是信息增益的简化版本。

Cart剪枝

因为决策树考虑了所有的属性特征，这些属性特征不一定是完全需要的，这会导致决策树的过拟合，所以需要进行剪枝操作，即删除一些不必要的属性特征。

两种常见的剪枝方法是预剪枝和后剪枝。

预剪枝方法：

1.设置每个节点所包含的最小样本数量，比如说某一个样本数量已经少于某个值，则不再进行划分。

2.指定树的高度或深度，当高度或深度达到某个值的时候，不再进行划分。

3.指定节点的熵低于某个值的时候，不在进行划分。

后修剪方法：

对过拟合的决策树进行剪枝，得到剪枝后的决策树的简化版本。

决策树算法的优缺点

优势：

1.计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的结果。

2.有一定的可解释性，树的结构可视化。

3.测试数据集时，运行速度比较快。

缺点：

1.属于弱分类器，且容易过拟合。

2.容易忽略数据集中属性的相互关联。

3.样本如果发生变化，则有可能引起决策树结构的巨变。

决策树算法代码

from sklearn import tree  #决策树实践库
import graphviz #决策树可视化
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split,cross_val_score
clf=tree.DecisionTreeClassifier(criterion="gini",min_samples_split=2) #使用gini算法建立决策树模型
clf.fit(x_train, y_train)
tree.plot_tree(clf)  #输出决策树结果
dot=tree.export_graphviz(clf,filled=True) #将决策树可视化
graph=graphviz.Source(dot)

代码功能及参数说明见

https://scikit-learn.org.cn/view/89.html