Press "Enter" to skip to content

决策树4:构建算法之ID3、C4.5

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

0x01 ID3算法介绍

 

1.1 简介

 

ID3算法是一种分类预测算法,算法以信息论中的“信息增益”为基础。核心是通过计算每个特征的信息增益,每次划分选取信息增益最高的属性为划分标准,递归地构建决策树。

 

ID3相当于用极大似然法进行概率模型的选择。

 

具体方法是:

 

 

从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征。

 

由该特征的不同取值建立子节点,再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止;

 

最后得到一个决策树。

 

 

从ID3的构建树过程而言,它可以看成使用贪心算法得到近似最优的一颗决策树,它无法保证是最优的。

 

1.2 构建流程

 

以递归的方式构建一棵决策树,其算法流程如下:

 

:createTree(dataSet,featList,bestFeatLists)。由给定的训练数据产生一棵判定树。

输入:

dataSet:训练数据集

featList:分类属性标签

bestFeatLists:存储选择的最优特征标签

输出:

myTree:一棵判定树。

方法:

createTree(dataSet,featList,bestFeatLists)

1)从传入的数据集dataSet中切割出分类标签,yList

2)如果yList中只有同一种标签,说明已经递归到分类边界了,则返回该标签

3)如果已经处理了dataSet中所有属性(列),但是类标签依然不是唯一的,采用多数判决的方法决定该子节点的分类

4)找出dataSet最优划分(信息增益最大)的特征所在位置bestFeatVec

5)在分类属性标签featList找出该位置所对应的特征值bestFeatLabel,并将该特征值存储到bestFeatLists中

6)将最优划分特征值作为当前(子)树的根节点,生成初始决策树myTree(用字典表示一个树结构)

7)在featList中删除当前已经使用过的特征标签(因为每次选择特征作为条件,dataSet会删掉这一列,形成新的子类,因此对应的featList中的值也要删掉)

8)确定子树分支:获取已选择的最优划分特征所对应的值分类categories(如“年龄”是最优特征,则“老”“中”“青”三个子类)

9)遍历每一个当前特征下的子类,在每个子类中,递归地调用创建决策树的方法,将递归调用的结果作为当前树节点的一个分支(构建树的方法是:特征作为字典的key,所得到的分类结果作为value;子树进行嵌套)

 

 

0x02 代码实例

 

现在我们以银行贷款申请业务为例,模拟四个特征,分别是:年龄、有工作、有房子、信贷情况。

 

 

“””

函数说明:数据集已经处理了所有属性,但是类标签依然不是唯一的,采用多数判决的方法决定该子节点的分类

即统计yList中出现次数最多的元素(类标签)

Parameters:

yList:类标签列表

Returns:

sortedClassCount[0][0]:出现次数最多的元素(类标签)

“””

def majorityCnt(yList):

yCount={}

#统计yList中每个元素出现的次数

for vote in yList:

if vote not in yCount.keys():

yCount[vote]=0

yCount[vote]+=1

#根据字典的值降序排列

sortedYCount=sorted(yCount.items(),key=operator.itemgetter(1),reverse=True)

return sortedYCount[0][0]

“””

函数说明:创建决策树

Parameters:

dataSet:训练数据集

featList:分类属性标签

bestFeatLists:存储选择的最优特征标签

Returns:

myTree:决策树

“””

def createTree(dataSet,featList,bestFeatLists):

# 取训练数据集最后一列,即分类标签

yList=[example[-1] for example in dataSet]

# 如果类别完全相同,则停止继续划分,

# 即yList中所有类别都是同一数据值(该类别数值个数等于列表长度)

if yList.count(yList[0])==len(yList):

# 返回该类别数值

return yList[0]

# 数据集已经处理了所有属性,但是类标签依然不是唯一的,

# 则采用多数判决的方法决定该子节点的分类

# 为什幺要如此判断?dataSet的列是不断减少的,dataSet某一行的长度,就是列

if len(dataSet[0])==1:

return majorityCnt(yList)

# 选择最优划分的特征index

bestFeatVec = optimalPartition(dataSet)

# 最优特征index所对应的分类标签,作为树的根节点

bestFeatLabel=featList[bestFeatVec]

# 存储选择的最优特征标签

bestFeatLists.append(bestFeatLabel)

# 将最优划分特征值作为当前(子)树的根节点,生成初始决策树(用字典表示一个树结构)

myTree={bestFeatLabel:{}}

# 删除已经使用的特征标签(del删除变量,解除引用)

# 因为每次选择特征作为条件,dataSet会删掉这一列,形成新的子类,因此对应的featList中的值也要删掉

del(featList[bestFeatVec])

print(‘featList: ‘,featList)

# 得到训练集中所有最优特征那一列所对应的值

featValues=[example[bestFeatVec] for example in dataSet]

# 去掉重复的属性值,得到最优特征下的子类

categories=set(featValues)

# 遍历最优特征列所对应的值,创建决策树

# 如“年龄”是最优特征,则遍历“老”“中”“青”三个子类

for category in categories:

# 根据当前数据集、最优划分的特征index以及每个分类(条件)得到(条件下的子集)

subDataSet = np.array(currentConditionSet(dataSet,bestFeatVec,category))

# 递归地调用创建决策树的方法,将递归调用的结果作为当前树节点的一个分支

myTree[bestFeatLabel][category]=createTree(subDataSet,featList,bestFeatLists)

return myTree

if __name__==’__main__’:

#print(‘featLabels’,featLabels)

bestFeatLists = []

myTree=createTree(dataSet,featList,bestFeatLists)

print(myTree)

 

输出:第0个特征的增益为0.083第1个特征的增益为0.324第2个特征的增益为0.420第3个特征的增益为0.363最佳的划分为第2个特征,是”有自己的房子“,信息增益为0.420第0个特征的增益为0.252第1个特征的增益为0.918第2个特征的增益为0.474最佳的划分为第1个特征,是”有工作“,信息增益为0.918{‘有自己的房子’: {0: {‘有工作’: {0: 0, 1: 1}}, 1: 1}}

 

解读结果:

 

 

0x03 ID3算法总结

 

3.1 优缺点:

 

相对于其他数据挖掘算法,决策树在以下几个方面拥有优势:

 

 

决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。

 

对于决策树,数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化,比如去掉多余的或者空白的属性。

 

能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。

 

是一个白盒模型如果给定一个观察的模型,那幺根据所产生的决策树很容易推出相应的逻辑表达式。

 

易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。

 

在相对短的时间内能够对大型数据源做出可行且效果良好的结果

 

 

ID3算法可用于划分标准称型数据,但存在一些问题:

 

 

没有剪枝过程,为了去除过渡数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点;

 

信息增益的方法偏向选择具有大量值的属性,也就是说某个属性特征索取的不同值越多,那幺越有可能作为分裂属性,这样是不合理的;

 

只可以处理离散分布的数据特征

 

ID3算法只考虑了树的生成,即尽可能的是模型拟合当前训练数据集,所以该算法生成的树容易过拟合。

 

 

3.2 总结

 

总结基本思想:

 

 

初始化属性集合和数据集合

 

计算数据集合信息熵S和所有属性的信息熵,选择信息增益最大的属性作为当前决策节点

 

更新数据集合和属性集合(删除掉上一步中使用的属性,并按照属性值来划分不同分支的数据集合)

 

依次对每种取值情况下的子集重复第二步

 

若子集只包含单一属性,则为分支为叶子节点,根据其属性值标记。

 

完成所有属性集合的划分

 

 

注意:该算法使用了贪婪搜索,从不回溯重新考虑之前的选择情况。

 

0x04 C4.5算法

 

C4.5算法是数据挖掘十大算法之一,它是对ID3算法的改进,相对于ID3算法主要有以下几个改进

 

 

用 信息增益比
来选择属性

 

在决策树的构造过程中对树进行剪枝

 

对非离散数据也能处理

 

能够对不完整数据进行处理

 

 

C4.5算法与ID3算法过程相似,仅在特征选择时,使用 信息增益比
作为特征选择准则。

 

其伪代码如下:

 

 

0xFF 总结

 

一、

 

熵表示的是数据中包含的信息量大小。熵越小,数据的纯度越高,也就是说数据越趋于一致,这是我们希望的划分之后每个子节点的样子。

 

信息增益 = 划分前熵 – 划分后熵。信息增益越大,则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说,用属性 a 来划分训练集,得到的结果中纯度比较高。

 

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

 

二、

 

C4.5 克服了 ID3 仅仅能够处理离散属性的问题,以及信息增益偏向选择取值较多特征的问题,使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

 

C4.5 处理连续特征是先将特征取值排序,以连续两个值中间值作为划分标准。尝试每一种划分,并计算修正后的信息增益,选择信息增益最大的分裂点作为该属性的分裂点。

 

三、信息增益 vs 信息增益比:

 

之所以引入了信息增益比,是由于信息增益的一个缺点。那就是:信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项,解决了这个问题。

 

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注