《机器学习实战》第一部分 分类 第3章 决策树
决策树的一般流程:
(1)收集数据:可以使用任何方法。
(2)准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。
(3)分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
(4)训练算法:构造树的数据结构。
(5)测试算法:使用经验树计算错误率。
(6)使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。
在构造决策树时,第一个需要解决的问题就是,如何确定出哪个特征在划分数据分类是起决定性作用,或者说使用哪个特征分类能实现最好的分类效果。这样,为了找到决定性的特征,划分最好的结果,我们就需要评估每个特征。当找到最优特征后,依此特征,数据集就被划分为几个数据子集,这些数据自己会分布在该决策点的所有分支中。此时,如果某个分支下的数据属于同一类型,则该分支下的数据分类已经完成,无需进行下一步的数据集分类;如果分支下的数据子集内数据不属于同一类型,那么就要重复划分该数据集的过程,按照划分原始数据集相同的原则,确定出该数据子集中的最优特征,继续对数据子集进行分类,直到所有的特征已经遍历完成,或者所有叶结点分支下的数据具有相同的分类。
相关公式:
香农熵(entropy),简称熵,用来定量表示信息的聚合程度,是信息的期望值。
信息增益指的是划分数据集前后信息发生的变化。
问题描述:
海洋生物数据:
有两个特征:不浮出水面是否可以生存,是否有脚蹼,标签是鱼类和非鱼类,现在我们需要建立一个决策树分类器,根据这个分类器对其它动物进行预测,预测的准确性暂且不讨论。
数据离散化:
python代码实现:
1、创建数据集
def createDataSet():
"""
创建测试数据集
:return:
"""
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
feature = ['no surfacing','flippers']
return dataSet, feature
2、计算给定数据集的熵
def calcShannonEnt(dataSet):
"""
计算香农熵
:param dataSet: 数据集
:return: 香农熵
"""
# 得到数据集的数据行数
numEntries = len(dataSet)
# 创建一个空字典
featureCounts = {}
for featVec in dataSet:
# 获取每行最后一个数值,作为键值
currentFeature = featVec[-1]
# 如果当前键值不存在,则将键值添加进字典,键值对应的数值为0,意思是出现零次
if currentFeature not in featureCounts.keys():
featureCounts[currentFeature] = 0
# 当前键值数值加1,代表出现次数多一次
featureCounts[currentFeature] += 1
# 定义香农熵
shannonEnt = 0.0
for key in featureCounts:
# 键值出现概率
prob = float(featureCounts[key]) / numEntries
# 以2为底求对数
shannonEnt -= prob * log(prob, 2)
return shannonEnt
3、划分数据集
def splitDataSet(dataSet, axis, value):
"""
划分数据集
:param dataSet: 待划分的数据集
:param axis: 每行特征的下标
:param value: 对应的特征值
:return:
"""
# 创建一个空列表
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
# extend 在列表末尾追加另一个序列中的多个值
reducedFeatVec.extend(featVec[axis+1:])
# append 在列表末尾添加新对象
retDataSet.append(reducedFeatVec)
return retDataSet
4、遍历整个数据集,切分数据,求熵,找到最佳的特征划分方式
def chooseBestFeatureToSplit(dataSet):
"""
遍历整个数据集,切分数据,求熵,找到最佳的特征划分方式
:param dataSet:
:return:
"""
# 特征数量,去掉最后的标签
numFeatures = len(dataSet[0]) -1
# 计算整个数据集的原始熵
baseEntropy = calcShannonEnt(dataSet)
# 定义最佳信息增益
bestInfoGain = 0.0
# 定义最佳特征索引
bestFeature = -1
for i in range(numFeatures):
# 取dataSet的第i行的第i列
featList = [example[i] for example in dataSet]
# 列表转集合去重
uniqueVals = set(featList)
# 定义新熵
newEntropy = 0.0
for value in uniqueVals:
# 切分数据
subDataSet = splitDataSet(dataSet, i, value)
# 概率:子集占总集的元素数量百分比
prob = len(subDataSet) / float(len(dataSet))
# 求熵
newEntropy += prob * calcShannonEnt(subDataSet)
# 计算信息增益
infoGain = baseEntropy - newEntropy
# 比较信息增益,得到最大值
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
# 返回最佳特征的索引值
return bestFeature
5、得到每列特征不同值的次数,返回出现次数最多的标签
def majorityCnt(classList):
"""
得到每列特征不同值的次数,返回出现次数最多的标签
:param classList:
:return:
"""
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] +=1
# sorted()函数对所有可迭代的对象进行排序操作
# operator.itemgetter() 指定可迭代对象中的一个元素来进行排序
# reverse=True表示降序
sortedClassConnt = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassConnt[0][0]
6、递归的构建决策树(主函数)
def createTree(dataSet, featureSet):
"""
主函数:递归的构建决策树
:param dataSet: 数据集
:param feature: 特征列
:return:
"""
# 深复制
feature = copy.deepcopy(featureSet)
# 提取数据集最后一列数据
classList = [example[-1] for example in dataSet]
# 当第一个值在列表中出现的次数等于列表长度,表示类别完全相同,则停止继续划分
if classList.count(classList[0]) == len(classList):
return classList[0]
# 当数据集第一行只有一个元素,但是类别不相同,就挑选出现次数最多的作为返回值
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 最佳特征值划分的索引
bestFeat = chooseBestFeatureToSplit(dataSet)
# 得到最佳特征名
bestFeatFeature = feature[bestFeat]
# 使用字典类型存储树的信息
myTree = {bestFeatFeature:{}}
# 从特征列表中删除最佳特征的列
del(feature[bestFeat])
# 得到最佳特征值对应的数据集中的那一列数据组成列表
featValues = [example[bestFeat] for example in dataSet]
# 唯一化
uniqueVals = set(featValues)
for value in uniqueVals:
# 复制,开一块新内存
subFeature = feature[:]
# 递归
myTree[bestFeatFeature][value] = createTree(splitDataSet(dataSet, bestFeat, value), subFeature)
return myTree
7、测试算法
def classify(inputTree, feature, testVec):
"""
测试算法
:param inputTree: 构建好的决策树
:param feature: 特征列
:param testVec: 测试实例
:return:
"""
# 找到树的第一个分类特征,或者说根节点
firstStr = list(inputTree.keys())[0]
# 从树中得到该分类特征的分支
secondDict = inputTree[firstStr]
# 得到对应的索引
featIndex = feature.index(firstStr)
for key in secondDict.keys():
# 测试集的第0个特征值等于第key个子节点
if testVec[featIndex] == key:
# 判断该子节点是否为字典类型
if type(secondDict[key]).__name__ == 'dict':
# 子节点为字典类型,则从该分支树开始继续遍历分类
classFeature = classify(secondDict[key], feature, testVec)
else:
# 子节点不是字典类型,则返回节点取值,就是分类结果
classFeature = secondDict[key]
return classFeature
8、存取决策树
def storeTree(inputTree, filename):
"""
pickle模块序列化决策树对象,保存在磁盘中
:param inputTree:
:param filename:
:return:
"""
# 创建一个可以'写'的文本文件,二进制方式写入
fw = open(filename, 'wb+')
# 将决策树写入文件
pickle.dump(inputTree, fw)
# 关闭
fw.close()
def grabTree(filename):
"""
读取决策树
:param filename:
:return:
"""
# 二进制形式读出数据
fr = open(filename, 'rb+')
return pickle.load(fr)
最终的决策树结构:{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}
图形展示如下:
推荐阅读
-
机器学习实战:基于Scikit-Learn和TensorFlow 读书笔记 第6章 决策树
-
机器学习sklearn实战-----泰坦尼克号分类预测决策树
-
《机器学习实战笔记--第一部分 分类算法:logistic回归1》
-
《机器学习实战笔记--第一部分 分类算法:决策树 4》
-
《机器学习实战》第一部分 分类 第3章 决策树
-
《机器学习实战笔记--第一部分 分类算法:朴素贝叶斯分类1》
-
《机器学习实战笔记--第一部分 分类算法:朴素贝叶斯分类2》
-
《机器学习实战笔记--第一部分 分类算法:logistic回归2》
-
机器学习实战:基于Scikit-Learn和TensorFlow 读书笔记 第6章 决策树
-
机器学习sklearn实战-----泰坦尼克号分类预测决策树