文章原创,最近更新：2018-08-16
学习参考链接:
1.机器学习(9)之ID3算法详解及python实现
2.机器学习实战-第3章《决策树》
本章节的主要内容是:
重点介绍项目案例1:判定鱼类和非鱼类递归构建决策树的函数代码。
1.决策树项目案例介绍:
项目案例1:
判定鱼类和非鱼类
项目概述:
- 根据以下 2 个特征，将动物分成两类：鱼类和非鱼类。
- 特征： 1. 不浮出水面是否可以生存 2. 是否有脚蹼
开发流程：
- 收集数据：可以使用任何方法
- 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
- 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
- 训练算法：构造树的数据结构
- 测试算法：使用决策树执行分类
- 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义
数据集介绍
2.递归构建决策树的函数代码
2.1筛选出现次数最多的分类标签名称
如果数据集已经处理了所有的属性,但是类标签依然不是唯一的,此时我们需要决定如何定义该叶子节点,在这种情况下,我们通常会采用多数表决的方法决定该叶子节点的分类.
在trees.py文件顶部增加一行代码:import operator,然后添加下面的代码到trees.py文件中.
#筛选出现次数最多的分类标签名称
def majorityCnt(classList):
"""
majorityCnt(筛选出现次数最多的分类标签名称)
Args:
classList 类别标签的列表
Returns:
sortedClassCount[0][0] 出现次数最多的分类标签名称
假设classList=['yes', 'yes', 'no', 'no', 'no']
"""
classCount={}
for vote in classList:
if vote not in classCount.keys():classCount[vote]= 0
classCount[vote] += 1
"""
print(classCount[vote])的结果为:
{'yes': 1}
{'yes': 2}
{'yes': 2, 'no': 1}
{'yes': 2, 'no': 2}
{'yes': 2, 'no': 3}
"""
sortedClassCount =sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
"""
print(sortedClassCount)的结果为:
[('no', 3), ('yes', 2)]
"""
return sortedClassCount[0][0]
测试代码及其结果如下:
import trees
classList=['yes', 'yes', 'no', 'no', 'no']
majorityCnt(classList)
Out[45]: 'no'
2.3递归构建决策树
所以决策树是一个递归算法，伪代码如下：
def createBranch():
检测数据集中的所有数据的分类标签是否相同:
If so return 类标签
Else:
寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
划分数据集
创建分支节点
for 每个划分的子集
调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
return 分支节点
构建决策树的算法流程如下：
- 得到原始数据集，
- 基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。
- 第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。我们可以采用递归的原则处理数据集。
- 递归结束的条件是，程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。
参见如下图所示:
决策树一般使用递归的方法生成。
编写递归函数有一个好习惯，就是先考虑结束条件。生成决策树结束的条件有两个：其一是划分的数据都属于一个类，其二是所有的特征都已经使用了。在第二种结束情况中，划分的数据有可能不全属于一个类，这个时候需要根据多数表决准则确定这个子数据集的分类。
在非结束的条件下，首先选择出信息增益最大的特征，然后根据其分类。分类开始时，记录分类的特征到决策树中，然后在特征标签集中删除该特征，表示已经使用过该特征。根据选中的特征将数据集分为若干个子数据集，然后将子数据集作为参数递归创建决策树，最终生成一棵完整的决策树
# 创建树的函数代码
def createTree(dataSet, labels):
"""
createTree(创建树)
Args:
dataSet 数据集
labels 标签列表:标签列表包含了数据集中所有特征的标签。最后代码遍历当前选择
Returns:
myTree 标签树:特征包含的所有属性值，在每个数据集划分上递归待用函数createTree()，
得到的返回值将被插入到字典变量myTree中，因此函数终止执行时，字典中将会嵌套很多代
表叶子节点信息的字典数据。
"""
#取得dataSet的最后一列数据保存在列表classList中
classList = [example[-1] for example in dataSet]
#如果classList中的第一个值在classList中的总数等于长度,也就是说classList中所有的值都一样
#也就等价于当所有的类别只有一个时停止
if classList.count(classList[0])==len(classList):
return classList[0]
#当数据集中没有特征可分时也停止
if len(dataSet[0])==1:
#通过majorityCnt()函数返回列表中最多的分类
return majorityCnt(classList)
#通过chooseBestFeatTopSplit()函数选出划分数据集最佳的特症
bestFeat = chooseBestFeatTopSplit(dataSet)
#最佳特征名 = 特征名列表中下标为bestFeat的元素
bestFeatLabel=labels[bestFeat]
# 构造树的根节点，多级字典的形式展现树，类似多层json结构
myTree={bestFeatLabel:{}}
# 删除del列表labels中的最佳特征(就在labels变量上操作)
del(labels[bestFeat])
#取出所有训练样本最佳特征的值形成一个list
featValues = [example[bestFeat] for example in dataSet]
# 通过set函数将featValues列表变成集合,去掉重复的值
uniqueVals = set(featValues)
for value in uniqueVals:
#复制类标签并将其存储在新列表subLabels中
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
测试代码及其结果如下:
import trees
myDat,labels=createDataSet()
myTree =createTree(myDat,labels)
myTree
Out[55]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
3.决策树相关知识点补充
3.1决策树算法的过程
算法的过程为：
- 初始化信息增益的阈值ϵ
- 判断样本是否为同一类输出Di，如果是则返回单节点树T。标记类别为Di
- 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征Ag
- 如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
- 对于所有的子节点，令D=Di,A=A−{Ag}递归调用2-6步，得到子树Ti并返回。
3.2 ID3算法的不足
ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。
- ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
- ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
- ID3算法对于缺失值的情况没有做考虑
- 没有考虑过拟合的问题
ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法。
