决策树的构造的本质是利用训练数据构造一棵决策树，然后利用这棵树所提炼出来的规则进行预测。算法过程大体分为两步：1.利用训练数据构造决策树 2.利用构造的决策树进行预测

分类相关知识

信息熵

信息熵由香农提出，用来衡量事件的不确定性的大小，定义为：

x表示事件，p(x)是事情发生的概率。随机量的不确定性越大熵也就越大。信息熵是随机变量不确定性的度量，常用单位是比特。

信息熵具有可加性，即多个期望信息：

X代表多个时间，Xi表示第 i 个事件，m是事件数。

参考：书P158

信息增益

信息增益表示某一特征的信息对类标签的不确定性减少的程度，定义为数据集D的信息熵与在特征A给定条件下数据集合D的信息熵之差：

 

ID3算法

ID3算法在分裂结点处将信息增益作为分裂准则进行特征选择，递归地构建决策树。

具体例子（算法步骤）

清华大学出版社《数据分析与数据挖掘 第2版》P166

数据处理

因为ID3算法只能对标称类型数据进行处理，而题目给的年龄属性是数值类型，因此首先对数据进行离散化。（因为这个不是重点所以略过，解答过程如下）

离散化后得到数据：

构造决策树

首先对样本集计算信息熵：

然后对于样本集中每一个属性求在其特征给定条件下对数据集合进行划分所需要的期望信息，A、B、C、D分别代表特征“年龄”“吸烟史”“有无家族病史”“体重范围”：

这里以A为例子，即年龄。青年4个，中年6个，老年5个

对于青年的结果有3个“是”和1个“否”

青年：4/15 * （ -3/4 * log2(3/4)  -  1/4 * log(1/4) )

然后计算信息增益，

 可以看到信息增益最大的是属性D，因此将它作为根结点的分裂属性，得到

继续对以这个五个子集作为数据集对剩余ABC三个属性进行计算：

 接着对Z5进行分裂

可以看到最大的是C有无家族病史，因此以这个属性分裂，得到：

继续往下分裂： 

到这里就成功根据训练数据构造了一棵决策树。

决策树预测

对于ID1：得到否

对于ID2：得到否

对于ID3：得到是

均与结果符合，正确率为100%。

Python实现

1.10. 决策树 — scikit-learn 1.5.1 文档 - scikit-learn 中文

from sklearn.datasets import load_iris
from sklearn import treeiris = load_iris()
dt_clf = tree.DecisionTreeClassifier()
dt_clf = dt_clf.fit(iris.data,iris.target)y_pred = dt_clf.predict(iris.data)
y_pred

可视化，我这里用了graphviz这个包，需要去下载，可以参考：(详解)下载安装Graphviz+配置环境+解决报错+验证成功-CSDN博客。

import graphviz
dot_data = tree.export_graphviz(dt_clf,out_file = None)
graph = graphviz.Source(dot_data)
graph.render("iris_tree")
graph.view()

运行成功会自动打开一个pdf文件。 

C4.5算法

采用信息增益比来替代信息增益作为寻找最优划分特征，信息增益比的定义是信息增益和特征熵的比值。

对于连续值的问题，将连续值离散化，在这里只作二类划分，即将连续值划分到两个区间，划分点取两个临近值的均值，因此对于m个连续值总共有m-1各划分点，对于每个划分点，依次算它们的信息增益，选取信息增益最大的点作为离散划分点。

具体例子（算法步骤）

清华大学出版社《数据分析与数据挖掘 第2版》P174

这里还是以ID3算法具体例子的数据进行计算。

刚刚这里是采用分箱法将连续性数据离散化，对于C4.5算法，我们找分裂点，将所有可能的分裂点分裂算出信息增益。

使用其中信息增益最大的作为分裂点，进行二分类。

然后对所有的属性计算信息增益率：

重复此过程，不再赘述。

参考

机器学习算法总结(二)——决策树（ID3, C4.5, CART） - 微笑sun - 博客园

清华大学出版社-图书详情-《数据分析与数据挖掘（第2版）》