决策树是一种树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本做拆分。

常见的决策树算法如下：

决策树算法	算法描述
ID3算法	在决策树各级节点上，使用信息增益的方法作为属性的选择标准
C4.5算法	ID3的改进版，使用信息增益率来选择节点属性。ID3只适用于离散的描述属性，而C4.5算法既能够处理离散的描述属性，也可以处理连续的描述属性
CART算法	通过构建树、修剪树、评估树来构建一个二叉树。当终节点为连续变量时，该树为回归树，当终节点是分类变量时，该树为分类树

一、信息熵与信息增益

pi一般可以用某一类下面的样本数/总样本数来估计（si/s）

 更具体的介绍可以参考：机器学习实战（三）——决策树_呆呆的猫的博客-程序员宅基地_决策树

二、ID3算法

ID3算法基于信息熵来选择最佳测试属性。它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时决策树上与该样本集相应的节点长出新的叶子节点。

1.ID3具体实现步骤：

（1）对当前样本集合，计算所有属性的信息增益；

（2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划分为同一子样本集；

（3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应符号，然后返回调用处；否则对子样本集递归调用本算法。

2.在Python中实现ID3决策树算法：

import pandas as pd
filename = './Python数据分析与挖掘实战（第2版）/chapter5/demo/data/sales_data.xls'
data = pd.read_excel(filename, index_col ="序号")
data.head(10)

数据如下 

#数据是类别标签，将它转换为数据
data[data == "好"] = 1
data[data == "是"] = 1
data[data == "高"] = 1
data[data != 1] = -1
x = data.iloc[:,:3].astype(int)
y = data.iloc[:,3].astype(int)

astype的用法参考：Python Pandas DataFrame.astype()用法及代码示例 - 纯净天空 

#构建基于信息熵的决策树
from sklearn.tree import DecisionTreeClassifier as DTC
dtc = DTC(criterion = "entropy")
dtc.fit(x,y)

输出如下：

 

参数说明如下：

class_weight：类别权重，可选参数，默认是None，也可以字典、字典列表、balanced。指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。类别的权重可以通过{class_label：weight}这样的格式给出，这里可以自己指定各个样本的权重，或者用balanced，如果使用balanced，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果你的样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的None。

criterion：特征选择标准，可选参数，默认是gini，可以设置为entropy。gini是基尼不纯度，是将来自集合的某种结果随机应用于某一数据项的预期误差率，是一种基于统计的思想。entropy是香农熵，也就是上篇文章讲过的内容，是一种基于信息论的思想。Sklearn把gini设为默认参数，应该也是做了相应的斟酌的，精度也许更高些？ID3算法使用的是entropy，CART算法使用的则是gini。

splitter：特征划分点选择标准，可选参数，默认是best，可以设置为random。每个结点的选择策略。best参数是根据算法选择最佳的切分特征，例如gini、entropy。random随机的在部分划分点中找局部最优的划分点。默认的”best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐”random”。

min_impurity_split：节点划分最小不纯度,可选参数，默认是1e-7。这是个阈值，这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点 。

presort：数据是否预排序，可选参数，默认为False，这个值是布尔值，默认是False不排序。一般来说，如果样本量少或者限制了一个深度很小的决策树，设置为true可以让划分点选择更加快，决策树建立的更加快。如果样本量太大的话，反而没有什么好处。问题是样本量少的时候，我速度本来就不慢。所以这个值一般懒得理它就可以了。

更多说明可见：机器学习实战（三）——决策树_呆呆的猫的博客-程序员宅基地_决策树
sklearn.tree.DecisionTreeClassifier()提供了一些方法供我们使用，如下图所示：

#得到模型的平均准确度
dtc.score(x,y)

#导入相关函数，可视化决策树
#导出的文件是一个dot文件，需要安装graphviz才能将它转换为pdf等格式
from sklearn.tree import export_graphviz
x = pd.DataFrame(x)
with open("./Python数据分析与挖掘实战（第2版）/chapter5/demo/data/tree.dot","w",encoding='utf-8') as f:
    f = export_graphviz(dtc,feature_names = x.columns, out_file =f)

安装好graphviz后，在dot所在目录下运行：

$ dot -Tpdf tree.dot -o tree.pdf

如果中文字没法正常显示，可以把原来的

node [shape=box] ;改为

node [shape=box, fontname="Microsoft YaHei"] ;

即可得到生成的结果图 

三、C4.5算法与CART算法

C4.5算法与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。 

关于C4.5对ID3的改进可以看：决策树算法原理(ID3，C4.5) - 做梦当财神 - 博客园

这里主要介绍CART算法。

1.CART分类树

CART分类树预测分类离散型数据，采用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类过程中，假设有K个类，样本点属于第k个类的概率为Pk，则概率分布的基尼指数定义为

根据基尼指数定义，可以得到样本集合D的基尼指数，其中Ck表示数据集D中属于第k类的样本子集。

如果数据集D根据特征A在某一取值a上进行分割，得到D1,D2两部分后，那么在特征A下集合D的基尼系数如下所示。其中基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。

对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gain_Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。

 比如：

 

2.CART回归树 

具体例子可以参考：决策树（ID3、C4.5、CART）的原理、Python实现、Sklearn可视化和应用 - 知乎 

CART算法在Python中的实现跟前面ID3差不多，不同的是dtc = DTC(criterion = "entropy")中entropy改为gini

三者的区别： 

参考：决策树算法原理(CART分类树) - 做梦当财神 - 博客园 

四、决策树剪枝

决策树算法本身的执行过程决定了它对训练集的分类是十分精确的，由于考虑到了绝大部分属性，一般都能对训练集中的数据进行比较精确的判断。但是这样所生成的树一般非常复杂，层数较多，有可能将本身并不具显著意义的属性也加以考虑，导致面对未见的新样本时泛化能力较差，产生过拟合问题。因此，有必要在一定程度上降低决策树的复杂度，即消除一些代表性不强的决策路径。即便这样可能会导致模型对训练集的分类精度下降，但决策树的泛化性能会有效提高。

在进行剪枝时，主要有预剪枝和后剪枝两种思路。

预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。

后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。

关于剪枝介绍可以参考：CART决策树原理（分类树与回归树） - 云+社区 - 腾讯云

关于剪枝在Python中的实现可以参考：Python——决策树分类模型剪枝 - 知乎 

 目前，决策树已演化发展为GBDT、XGBoost等模型：

可以参考：

GBDT的原理、公式推导、Python实现、可视化和应用 - 知乎

XGBoost的原理、公式推导、Python实现和应用 - 知乎