概念： 决策树是机器学习中一种特别常见的算法。决策树是一个预测模型，它在已知各种情况发生的概率下，训练而成的一个学习器，代表着对象属性和对象值的一种映射关系。
决策树结构：
根结点： 代表想要预测的目标的属性
分支： 代表想要预测的目标的属性类别
叶节点： 代表预测结果
在信息论中有一个理论，信息期望越小，信息增益越大。在ID3算法中我们的主要目的就是要找到信息增益最大的属性做为决策树的根结点来进行决策树的建立。
这里我们拿一个例子（相亲满意程度预测）来解释：
身高年龄是否有房工作单位满意程度175偏大有企业满意178偏小无政府满意180偏大无企业不满意178偏大无政府不满意180偏小有企业满意这里满意程度为预测结果，身高，年龄，是否有房，工作单位为构建决策树的属性。
1.信息熵： 度量一个属性的信息量 S 代 表 训 练 样 本 集 合 ， p 代 表 预 测 结 果 在 总 样 本 的 占 比 的 集 合 公 式 ： E n t r o p y ( S ) = − ∑ i = 1 n p i l o g 2 p i 总 样 本 数 ： 5 正 样 本 数 （ 满 意 ） ： 3 负 样 本 数 （ 不 满 意 ） ： 2 实 例 计 算 ： E n t r o p y ( S ) = − 3 5 ⋅ l o g 2 ( 3 5 ) − 2 5 ⋅ l o g 2 ( 2 5 ) S代表训练样本集合，p代表预测结果在总样本的占比的集合\\ 公式：Entropy(S) = -\sum_{i=1}^n{p_i}log_2p_i\\ 总样本数：5\\正样本数（满意）：3 \\ 负样本数（不满意）：2\\ 实例计算：Entropy(S) = -\frac{3}{5}\cdot log_2(\frac{3}{5})-\frac{2}{5}\cdot log_2(\frac{2}{5}) S代表训练样本集合，p代表预测结果在总样本的占比的集合公式：Entropy(S)=−i=1∑npilog2pi总样本数：5正样本数（满意）：3负样本数（不满意）：2实例计算：Entropy(S)=−53⋅log2(53)−52⋅log2(52) 2.条件熵： 表示在已知属性X的情况下它的属性类别Y的不确定性（需要求所有属性的条件熵） 公 式 ： E n t r o p y ( X ∣ Y ) = − ∑ i = 1 n p i l o g 2 p i ( p i = p ( X = X i ) ) 公式：Entropy(X|Y)=-\sum_{i=1}^np_ilog_2p_i (p_i=p(X=X_i)) 公式：Entropy(X∣Y)=−i=1∑npilog2pi(pi=p(X=Xi))
求身高的条件熵 属 性 类 别 数 X 1 ( 175 ) = 1 属 性 类 别 数 X 2 ( 178 ) = 2 属 性 类 别 数 X 3 ( 180 ) = 2 X 1 = 1 ( 满 意 ) X 2 = 1 ( 满 意 ) + 1 ( 不 满 意 ) X 3 = 1 ( 满 意 ) + 1 ( 不 满 意 ) E n t r o p y ( X 1 ) = − 1 1 l o g 2 ( 1 1 ) − 0 1 l o g 2 ( 0 1 ) E n t r o p y ( X 2 ) = − 1 2 l o g 2 ( 1 2 ) − 1 2 l o g 2 ( 1 2 ) E n t r o p y ( X 3 ) = − 1 2 l o g 2 ( 1 2 ) − 1 2 l o g 2 ( 1 2 ) E n t r o p y ( 身 高 ) = 1 5 E n t r o p y ( X 1 ) + 2 5 E n t r o p y ( X 2 ) + 2 5 E n t r o p y ( X 3 ) 属性类别数 X_1(175)=1\\ 属性类别数 X_2(178)=2\\ 属性类别数 X_3(180)=2\\ X1=1(满意)\\ X2=1(满意)+1(不满意)\\ X3=1(满意)+1(不满意)\\ Entropy(X1)=-\frac{1}{1}log_2(\frac{1}{1})-\frac{0}{1}log_2(\frac{0}{1})\\ Entropy(X2)=-\frac{1}{2}log_2(\frac{1}{2})-\frac{1}{2}log_2(\frac{1}{2})\\ Entropy(X3)=-\frac{1}{2}log_2(\frac{1}{2})-\frac{1}{2}log_2(\frac{1}{2})\\ Entropy(身高)=\frac{1}{5}Entropy(X1)+\frac{2}{5}Entropy(X2)+\frac{2}{5}Entropy(X3) 属性类别数X1(175)=1属性类别数X2(178)=2属性类别数X3(180)=2X1=1(满意)X2=1(满意)+1(不满意)X3=1(满意)+1(不满意)Entropy(X1)=−11log2(11)−10log2(10)Entropy(X2)=−21log2(21)−21log2(21)Entropy(X3)=−21log2(21)−21log2(21)Entropy(身高)=51Entropy(X1)+52Entropy(X2)+52Entropy(X3)
求年龄的条件熵 属 性 类 别 数 X 1 ( 偏 大 ) = 3 属 性 类 别 数 X 2 ( 偏 小 ) = 2 X 1 = 2 ( 不 满 意 ) + 1 ( 满 意 ) X 2 = 2 ( 满 意 ) E n t r o p y ( X 1 ) = − 1 3 l o g 2 1 3 − 2 3 l o g 2 2 3 E n t r o p y ( X 2 ) = − 2 2 l o g 2 2 2 − 0 2 l o g 2 0 2 E n t r o p y ( 年 龄 ) = 3 5 E n t r o p y ( X 1 ) + 2 5 E n t r o p y ( X 2 ) 属性类别数X1(偏大)=3\\ 属性类别数X2(偏小)=2\\ X1=2(不满意)+1(满意)\\ X2=2(满意)\\ Entropy(X1)=-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3}\\ Entropy(X2)=-\frac{2}{2}log_2\frac{2}{2}-\frac{0}{2}log_2\frac{0}{2}\\ Entropy(年龄)=\frac{3}{5}Entropy(X1)+\frac{2}{5}Entropy(X2) 属性类别数X1(偏大)=3属性类别数X2(偏小)=2X1=2(不满意)+1(满意)X2=2(满意)Entropy(X1)=−31log231−32log232Entropy(X2)=−22log222−20log220Entropy(年龄)=53Entropy(X1)+52Entropy(X2)
求是否有房的条件熵 属 性 类 别 数 X 1 ( 有 ) = 2 属 性 类 别 数 X 2 ( 无 ) = 3 X 1 = 2 ( 满 意 ) X 2 = 1 ( 满 意 ) + 2 ( 不 满 意 ) E n t r o p y ( X 1 ) = − 2 2 l o g 2 2 2 − 0 2 l o g 2 0 2 E n t r o p y ( X 2 ) = − 1 3 l o g 2 1 3 − 2 3 l o g 2 2 3 E n t r o p y ( 是 否 有 房 ) = 2 5 E n t r o p y ( X 1 ) + 3 5 E n t r o p y ( X 2 ) 属性类别数X1(有)=2\\ 属性类别数X2(无)=3\\ X1=2(满意)\\ X2=1(满意)+2(不满意)\\ Entropy(X1)=-\frac{2}{2}log_2\frac{2}{2}-\frac{0}{2}log_2\frac{0}{2}\\ Entropy(X2)=-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3}\\ Entropy(是否有房)=\frac{2}{5}Entropy(X1)+\frac{3}{5}Entropy(X2) 属性类别数X1(有)=2属性类别数X2(无)=3X1=2(满意)X2=1(满意)+2(不满意)Entropy(X1)=−22log222−20log220Entropy(X2)=−31log231−32log232Entropy(是否有房)=52Entropy(X1)+53Entropy(X2)
求工作单位的条件熵 属 性 类 别 数 X 1 ( 企 业 ) = 3 属 性 类 别 数 X 2 ( 政 府 ) = 2 X 1 = 2 ( 满 意 ) + 1 ( 不 满 意 ) X 2 = 1 ( 满 意 ) + 1 ( 不 满 意 ) E n t r o p y ( X 1 ) = − 2 3 l o g 2 2 3 − 1 3 l o g 2 1 3 E n t r o p y ( X 2 ) = − 1 2 l o g 2 1 2 − 1 2 l o g 2 1 2 E n t r o p y ( 工 作 单 位 ) = 3 5 E n t r o p y ( X 1 ) + 2 5 E n t r o p y ( X 2 ) 属性类别数X1(企业)=3\\ 属性类别数X2(政府)=2\\ X1=2(满意)+1(不满意)\\ X2=1(满意)+1(不满意)\\ Entropy(X1)=-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\\ Entropy(X2)=-\frac{1}{2}log_2\frac{1}{2}-\frac{1}{2}log_2\frac{1}{2}\\ Entropy(工作单位)=\frac{3}{5}Entropy(X1)+\frac{2}{5}Entropy(X2) 属性类别数X1(企业)=3属性类别数X2(政府)=2X1=2(满意)+1(不满意)X2=1(满意)+1(不满意)Entropy(X1)=−32log232−31log231Entropy(X2)=−21log221−21log221Entropy(工作单位)=53Entropy(X1)+52Entropy(X2)
**3.信息增益：**信息熵与条件熵的差 G a i n ( X ∣ Y ) = E n t r o p y ( S ) − E n t r o p y ( X ∣ Y ) G a i n ( 身 高 ) = E n t r o p y ( S ) − E n t r o p y ( 身 高 ) G a i n ( 年 龄 ) = E n t r o p y ( S ) − E n t r o p y ( 年 龄 ) G a i n ( 是 否 有 房 ) = E n t r o p y ( S ) − E n t r o p y ( 是 否 有 房 ) G a i n ( 工 作 单 位 ) = E n t r o p y ( S ) − E n t r o p y ( 工 作 单 位 ) Gain(X|Y)=Entropy(S)-Entropy(X|Y)\\ Gain(身高)=Entropy(S)-Entropy(身高)\\ Gain(年龄)=Entropy(S)-Entropy(年龄)\\ Gain(是否有房)=Entropy(S)-Entropy(是否有房)\\ Gain(工作单位)=Entropy(S)-Entropy(工作单位) Gain(X∣Y)=Entropy(S)−Entropy(X∣Y)Gain(身高)=Entropy(S)−Entropy(身高)Gain(年龄)=Entropy(S)−Entropy(年龄)Gain(是否有房)=Entropy(S)−Entropy(是否有房)Gain(工作单位)=Entropy(S)−Entropy(工作单位)
在求出各属性的信息增益后，将属性增益最大的属性做为决策树的根结点。然后至上向下递归建树。这里简单的距离介绍确定第一个根结点后的步骤。
比如信息增益最大的属性为年龄，它有两个属性类别（即决策树的两个分支）
属性类别为“偏大”时（即分支为“偏大”）
身高年龄是否有房工作单位满意程度175偏大有企业满意178偏大无企业不满意180偏大无政府不满意属性类别为“偏小”时（即分支为“偏小”）
身高年龄是否有房工作单位满意程度178偏小无政府满意180偏小有企业满意在此基础上在通过1.1.2中的基本概念求出各属性的信息增益，求出最大的信息增益在确定为根结点。 这里假设偏大分支下信息增益最大的属性是身高，偏小分支下信息增益最大的属性是工作单位。（如图）
在信息增益的基础上引入分裂率的概念，从而决定决策树根结点的因素变成了信息增益率。
分裂率： 引 用 上 述 例 子 来 计 算 属 性 为 身 高 时 的 分 裂 率 ： 属 性 类 别 X 1 ( 175 ) = 1 属 性 类 别 X 2 ( 178 ) = 2 属 性 类 别 X 3 ( 180 ) = 2 s p l i t = − 1 5 l o g 2 1 5 − 2 5 l o g 2 2 5 − 2 5 l o g 2 2 5 引用上述例子来计算属性为身高时的分裂率：\\ 属性类别X_1(175)=1\\ 属性类别X_2(178)=2\\ 属性类别X_3(180)=2\\ split=-\frac{1}{5}log_2\frac{1}{5}-\frac{2}{5}log_2\frac{2}{5}-\frac{2}{5}log_2\frac{2}{5} 引用上述例子来计算属性为身高时的分裂率：属性类别X1(175)=1属性类别X2(178)=2属性类别X3(180)=2split=−51log251−52log252−52log252 信息增益率： 信 息 增 益 率 等 于 信 息 增 益 除 以 分 裂 率 G a i n . r a t i o = G a i n s p l i t 信息增益率等于信息增益除以分裂率\\ Gain.ratio=\frac{Gain}{split} 信息增益率等于信息增益除以分裂率Gain.ratio=splitGain 其余概念与ID3算法相同。
除了判断根结点属性的依据是信息增益率之外，其余过程与ID3算法相同。
功能菜单： 数据集： 数据集可以自己制作，这里我是用网上常用的数据（偷个懒），但制作时注意进行预处理操作。
代码： 代码是在VS下编写的，我已经将代码的所有相关文件上传到Github上了，有兴趣的同学可以下载来试一下，除了功能6，需要安装配置Graphviz外（在下面有说明），其余功能可以直接实现。一共三个文件的decision_tree.cpp（主控源文件），pch.cpp（功能模块文件），pch.h（头文件）。 代码地址：https://github.com/huangzhaohong123/ID3-C4.5-decision_tree
DOT语言是用来描述图形的一种语言，而Graphviz则是用来处理这种语言的工具，适用于树结构的可视化。 该地址下下载graphviz-2.38.msi https://graphviz.gitlab.io/_pages/Download/Download_windows.html 下载后会出现 然后一直点next，直到出现安装路径时，它会给你默认安装路径（这里个人建议放在你自己熟悉的路径下，方便后面配置环境变量） 安装后 环境变量配置： 搜索—>编辑系统环境变量—>高级—>环境变量—>系统变量中找到path—>添加安装路径加上bin 有的电脑需要重启一下，使得环境变量生效。 bin文件下标注的gvedit可以直接调用该工具 dot语言可参考：https://blog.csdn.net/STILLxjy/article/details/86004519
注意： 该工具在c++环境下不够友好，基本每次运行只能调用一次。
数据集（配置适合你的隐形眼镜）
# -*- coding: UTF-8 -*- from sklearn.preprocessing import LabelEncoder, OneHotEncoder from sklearn.externals.six import StringIO from sklearn import tree import pandas as pd import numpy as np import pydotplus import os if __name__ == '__main__': os.environ["PATH"] += os.pathsep + 'E:/Graphviz-2.38/bin' #若环境配置不成功，则直接代码调用环境，E:/Graphviz-2.38/bin为我的安装路径 with open('D:/desktop/experience/lenses1.txt', 'r') as fr: #加载文件 lenses = [inst.strip().split('\t') for inst in fr.readlines()] #处理文件 #print(lenses) lenses_target = [] #提取每组数据的类别，保存在列表里 for each in lenses: #print(each[-1]) lenses_target.append(each[-1]) #print(lenses_target) lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate'] #特征标签 lenses_list = [] #保存lenses数据的临时列表 lenses_dict = {} #保存lenses数据的字典，用于生成pandas for each_label in lensesLabels: #提取信息，生成字典 for each in lenses: lenses_list.append(each[lensesLabels.index(each_label)]) lenses_dict[each_label] = lenses_list lenses_list = [] #print(lenses_dict) #打印字典信息 lenses_pd = pd.DataFrame(lenses_dict) #生成pandas.DataFrame print(lenses_pd) #打印pandas.DataFrame le = LabelEncoder() #创建LabelEncoder()对象，用于序列化 for col in lenses_pd.columns: #序列化 lenses_pd[col] = le.fit_transform(lenses_pd[col]) print(lenses_pd) #打印编码信息 clf = tree.DecisionTreeClassifier(max_depth = 4) #创建DecisionTreeClassifier()类 clf = clf.fit(lenses_pd.values.tolist(), lenses_target) #使用数据，构建决策树 dot_data = StringIO() tree.export_graphviz(clf, out_file = dot_data, #绘制决策树 feature_names = lenses_pd.keys(), class_names = clf.classes_, filled=True, rounded=True, special_characters=True) graph = pydotplus.graph_from_dot_data(dot_data.getvalue()) graph.write_pdf("tree1.pdf") #保存绘制好的决策树，以PDF的形式存储。决策树可视化：
