机器学习——决策树（ID3和C4.5）
⽬录
1. 决策树的概念
决策树（Decision Tree）是⼀种⽤于监督学习的层次模型，是最早的机器学习算法之⼀。
决策树可以是⼆叉树，也可以是多叉树，每个⾮叶结点表⽰⼀个特征属性上的测试，每个分⽀代表该特征属性在某个值域上的输出，⽽每个叶结点存放⼀个（分类）类别。 使⽤决策树决策时，从根节点开式测试待分类项中相应的特征属性，并按照其值选择输出分⽀，直到到达叶⼦结点，将叶⼦结点存放的类型作为决策结果。
2. 决策树的基本思想
决策树主要由两类结点组成：
长⽅形结点代表判断模块（Decision Block），椭圆形结点代表终⽌模块（Terminating Block）。
判断模块是中间结点，引出的箭头可以到达另⼀个判断模块或终⽌模块，也可称其为分⽀（Branch）。
终⽌模块是叶结点，表⽰已经得出结论，可以终⽌运⾏。
（最早的决策树就是利⽤条件分式结构if-then分割数据的分类学习⽅法） 3. 决策树的构造
决策树的构造过程不依赖于领域知识 ，它通过属性选择度量来将元组“最好地”划分为不同的类的属性。
决策树的构造，就是进⾏决策选择度量，确定各个特征属性之间的拓扑结构。
构造决策树的关键步骤是分裂属性。所谓分裂属性，就是在某个结点处按照某⼀特征属性的不同划分构造不同的分⽀，其⽬标是让各个分裂属性尽可能地“纯” 。 所谓尽可能地“纯”，就是尽量让⼀个分裂⼦集中的待分类项属于同⼀类别。
分裂属性分为3种不同的情况：
（1）属性是离散值，且不要求⽣成⼆叉决策树。此时⽤属性的每⼀个划分作为⼀个分⽀。
（2）属性是离散值，且要求⽣成⼆叉决策树。此时使⽤属性划分的⼀个⼦集进⾏测试，按照“属于此⼦集”和“不属于此⼦
集”将属性的⽀持集分成两个分⽀。
（3）属性是连续值。此时确定⼀个值作为分裂点（split_point），按照⼤于split_point和⼩于split_point⽣成两个分⽀。
构造决策树的关键是进⾏属性选择度量。属性选择度量是⼀种选择分裂准则，将给定的类标记的训练集合的数据划分成“最好的”个体类，它决定了拓扑结构及分裂点的选择。（属性选择度量算法有很多，⼀般使⽤⾃顶向下的递归分治法，并采⽤不回溯的贪⼼策略）
4. 决策树的算法框架
（1）决策主函数
决策树的主函数是⼀个递归函数，其主要功能是按照某种规则⽣长出决策树的各个分⽀节点，并根据种植条件结束算法，。主要包括以下内容：
输⼊需要分类的数据集和类别标签。
计算最优特征⼦函数。根据某种分类规则得到最优划分特征，并创建特征的划分结点。
划分数据集⼦函数。按照该特征的每个取值划分数据集为若⼲部分。
根据划分⼦函数的计算结果构建出新的结点，作为决策树⽣长出新分⽀。溶血栓疗法
检验是否终⽌
将划分的新节点包含的数据及和类别标签作为输⼊，递归执⾏上述个步骤。
（2） 计算最优特征⼦函数
在计算最优特征⼦函数时，3种典型的决策树采⽤了3种不同的策略：
C4.5算法——信息增益率
吉祥满族网CART算法——最⼩剩余⽅差
（3）划分数据集函数
要分割数据，有时需要删除某个特征轴所在的数据类，返回剩余的数据集；有时则直接将数据集⼀分为⼆。
（4）分类器
通过遍历整棵决策树，使测试集数据到决策树中叶⼦结点对应的类别标签。
5. ID3算法
（1）信息增益
⽤来衡量⼀个随机变量出现的期望值。
⼀个变量的信息熵越⼤，那么它蕴含的情况就越多，也就是说需要更多的信息才能完全确定它。
1948年，⾹农（C.E. Shannon）在A Mathematical Theory of Communication（《通信的数学理论》）⼀书中第⼀次提出了信息熵。⾹农认为，信息就是对不确定性的消除。⼀般⽽⾔，当某种信息
出现更⾼概率的时候，表明它被传播得更⼴泛，或者说被引⽤的程度更⾼。
对于随机变量集 ，若任意的⼀个随机变量 , ，其发⽣概率为 ，那么信息熵可以表⽰为如下公式：
(5.1)
在决策树中，信息熵不仅能⽤来度量类别的不确定性，还可以⽤来度量包含不同特征的数据样本与类别的不确定性。某个特征列向量的信息熵越⼤，则该向量的不确定性就越⼤，即其混乱程度就越⼤，就应该优先考虑从该特征向量⼊⼿进⾏划分。
（2）ID3算法实现步骤：
① ⾸先，⽤信息熵度量类别标签对样本整体的不确定性。
设 是数据样本集合，其类别标签 。类别标签 对数据样本 的划分为
，
其中且
，此处的表⽰样本 的标签。
根据式（5.1），样本分类的信息熵公式如式（5.2）所⽰：
（5.2）
其中，，是样本属于类别 的概率。
表⽰样本 中类别 的元素个数；表⽰样本集 的元素个数，即样 本总数。
② 然后，使⽤信息熵度量每个特征不同取值的不确定性。
、 假设属性 有 个不同的取值，那么使⽤属性 就可以将样本集 划分为 个互不相交的⼦集 ，
其中，。如果选择属性A做最优划分特征，那么划分的⼦集就是样本集 节点中⽣长出来的决策树分⽀。
由属性 划分的⼦集的信息熵如式（5.3）和（5.4）所⽰：
（5.3）
（5.4）
其中， 表⽰⼦集 中的元素个数； 是 中样本属于类别 的概率，其值等于
中类别 的样本个数与 个数的⽐值。
③ 最后，使⽤信息增益决定决策树分⽀的划分依据。
决策树上某个分⽀上的整个数据集信息熵与当前结点信息熵的差值如式（5.5）所⽰：
（5.5）
对样本集 中的每个属性（未选取的属性）进⾏上述计算，具有最⾼信息增益的特征就可选为给定样本集 的测试属性。为选取的样本属性创建⼀个结点，并以该 特征标记，对特征的每个值创建分⽀，并据此划分样本。
from numpy import *
def calcShannonEnt(dataSet):
"""
输⼊：数据集
输出：数据集的⾹农熵
描述：计算给定数据集的⾹农熵
"""
num = len( dataSet ) # 样本集总数
classList = [c[-1] for c in dataSet] # 抽取分类信息
labelCounts = {} # 词典形式存储类别计数
for cs in set(classList): # 对每个类别计数
labelCounts[cs] = unt( cs )
中岛敦
shannonEnt = 0.0 # 信息熵
for key in labelCounts:
prob = labelCounts[key] / float(num)
shannonEnt -= prob * math.log2(prob)
return shannonEnt
# 给定数据集
def CreateDataSet():
dataSet = [[1, 1, ' Yes'],
[1, 1, ' Yes'],
[1, 0, 'No'],
[0, 1, 'No'],
[0, 1, 'No']]
labels = ['no surfacing', 'flippers']
return dataSet, labels
myDat, labels = CreateDataSet()
汽水热交换器print(calcShannonEnt(myDat))
（3）ID3算法
ID3算法由Ross Quinlan发明，建⽴在“奥卡姆剃⼑”的基础上。
奇瑞农机
永田晴康⼩型的决策树优于⼤型的决策树。
ID3算法根据信息论的信息增益评估和特征选择，每次选择信息增益最⼤的特征作为判断模块。
ID3算法可⽤于划分标称型数据集，没有剪枝的过程。为了去除过度数据匹配的问题，可裁剪及合并相邻的⽆法产⽣⼤量信息增益的叶⼦结点（如设置信息增益阈值）
信息增益与属性的值域范围⼤⼩成正⽐，也就是说在训练集中，某个属性所取得不同值的个数越多，就越有可能将它作为分裂属性。然⽽，有时这样选择是⽆效的。
ID3不能处理连续分布的数据特征。
6. C4.5算法
ID3算法存在⼀个问题，就是偏向于多值属性。例如，如果存在唯⼀标识属性ID，则ID3会选择它作为
分裂属性，这样虽然使得划分充分纯净，但这种划分对分类⼏乎毫⽆⽤处。
1993年，Quinlan将ID3改进为C4.5算法。C4.5算法使⽤信息增益率（Gain Ratio）代替信息增益，进⾏特征选择，克服了信息增益选择特征时偏向特征值个数较多的不⾜。
（1）信息增益率
⾸先定义“分裂信息”，其定义如式（6.1）所⽰：
（6.1）
其中， 是样本集 在特征 上的划分，此处假定 有 个不同的取值。
信息增益率定义如式（6.2）所⽰：
（6.2）（2）C4.5算法
C4.5选择具有最⼤信息增益率的属性作为分裂属性，具体算法步骤与ID3类似。
C4.5是ID3的⼀个改进算法，继承了ID3算法的优点。C4.5算法使⽤信息增益率代替信息增益，进⾏特征选择，克服了信息增益选择特征时偏向特征值个数较多的不⾜。
C4.5算法在树构造过程中进⾏了剪枝，能够完成对连续属性的离散化处理，能够对不完整的数据进⾏处理。
C4.5算法产⽣的分类规则易于理解，准确率较⾼，但效率低，这是因为在树的构造过程中，需要对数据进⾏多次的顺序扫描和排序。
正是因为必须进⾏多次的顺序扫描和排序，C4.5才只适合能够驻留于内存的数据集。
本⽂学习总结⾃李克清、时允⽥主编的《机器学习及应⽤》
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议