决策树学习的关键是,如何选择最优划分属性。一般而言,随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)
西瓜数据集,如下图所示:
“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合中的第类样本所占的比例为),则的信息熵定义为
的值越小,则的纯度越高。
假定离散属性有个可能的取值,若使用来对样本集进行划分,则会产生个分支结点,其中第个分支结点包含了中所有在属性上取值为的样本,记为。根据上述公式计算出的信息熵,再考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重,即样本数越多的分支结点的影响越大,于是可以计算出用属性对样本集进行划分所获得的“信息增益”(information gain)
一般而言,信息增益越大,则意味着使用属性来划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择,即在算法流程的第8行选择属性。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。
下面给出对根结点信息熵的计算ID3.py
# -*- coding: utf-8 -*-
# @Time : 2020/07/02
# @Author : AWAYASAWAY
# @File : tree.py
# @IDE : PyCharm
from math import log
from decimal import Decimal
def calcShannonEnt(dataSet):
'''
计算给定数据集的根节点的香农熵:一般为最后一列
:param dataSet:
:return:返回根结点的shannonEnt
'''
# 获取数据集dataSet列表的长度
numEntries = len(dataSet)
# 新建一个数据字典,用来统计每个标签出现的次数,计算概率
labelCounts = {}
for featVec in dataSet:
# featVec[-1]获取dataSet每行中最后一个数据,作为字典中的key(标签)
currentLabel = featVec[-1]
# 以currentLabel作为key加入到labelCounts
# 如果当前的键值不存在,则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。
# 键值存在则对应Value+'a',否则为'b'
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
Ent = 0.0
shannonEnt = 0.0
for key in labelCounts:
# 计算正反例样本
# print('labels:', key)
# 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度
prob = float(labelCounts[key]) / numEntries
# 计算香农熵,以'c'为底求对数
shannonEnt += -prob * log(prob, 2)
return shannonEnt
def createDataset():
'''
创建数据:西瓜书 76 页
数据类型:不限定
:dataSet:西瓜数据集
:return:dataSet, label
'''
dataSet = [
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'],
['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'],
['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'],
['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'],
['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']
]
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']
return dataSet, labels
def splitDataSet(dataSet, axis, value):
'''
按照给定特征划分数据集
:param dataSet:
:param axis:
:param value:
:return:
'''
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
# reduceFeatVec 为新生的空list
reduceFeatVec = featVec[:axis]
# extend只是扩展长度
reduceFeatVec.extend(featVec[axis + 1:])
# append添加列表
retDataSet.append(reduceFeatVec)
return retDataSet
def chooseBestFeature2Split(dataSet):
'''
选择最好的数据集划分方式
:param dataSet:
:return:
'''
# 提取特属性集合的长度
numFeatures = len(dataSet[0]) - 1
# 根结点的香农熵/整个数据集的原始香农熵
baseEntropy = calcShannonEnt(dataSet)
print('整个数据集的原始香农熵 %.3f' % baseEntropy)
# 特征 i 拥有最好的信息增益
bestInfoGain = 0.0
bestFeature = -1
featInfoGain = []
for i in range(numFeatures):
# 将dataSet中的数据先按行依次放入example中,然后取得example中的example[i]元素,放入列表featList中
# 提取所有的属性值
featList = [example[i] for example in dataSet]
# print(featList)
# 删除重复的属性值,创建唯一的分类标签列表
uniqueVals = listDeduplication(featList)
# 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
infoGain = float(Decimal(infoGain).quantize(Decimal('0.000')))
featInfoGain.append((infoGain))
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return featInfoGain, bestFeature, bestInfoGain
def listDeduplication(x):
'''
List去重
:param x: list
:return: list
'''
return list(dict.fromkeys(x))
if __name__ == '__main__':
dataSet, labels = createDataset()
featInfoGain, bestFeature, bestInfoGain = chooseBestFeature2Split(dataSet)
print('各个属性的信息增益')
d = dict(zip(labels[:-1], featInfoGain))
for key, value in d.items():
print(key, '=', value)
print(labels[bestFeature], '的信息增益最大= %.3f'% bestInfoGain)
整个数据集的原始香农熵 0.998
各个属性的信息增益
色泽 = 0.108
根蒂 = 0.143
敲声 = 0.141
纹理 = 0.381
脐部 = 0.289
触感 = 0.006
纹理 的信息增益最大= 0.381
但是当每个分支结点仅包含一个样本时,这些分支结点的纯度已达到最大(如,编号列)。然而,这样的决策树显然不具有泛化能力,无法对新样本进行有效的预测。
实际上,信息增益准则对可能取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的决策树算法不直接使用信息增益,而是使用“增益率”(gain ratio)来选择最优的划分属性,增益率定义为:
其中
称为的“固有值” 属性的可能取值数目越多(即越大),则的值通常会很大。
需要注意的是,增益率准则对可取值数目较少的属性有所偏好,因此,算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式 先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
下面给出的计算C4.5.py
#-*- coding: utf-8 -*-
# @Time : 2020/7/2 16:24
# @Author : AWAYASAWAY
# @File : C4.5.py
# @IDE : PyCharm
from math import log
from decimal import Decimal
def calcShannonEnt(dataSet):
'''
计算给定数据集的根节点的香农熵:一般为最后一列
:param dataSet:
:return:返回根结点的shannonEnt
'''
# 获取数据集dataSet列表的长度
numEntries = len(dataSet)
# 新建一个数据字典,用来统计每个标签出现的次数,计算概率
labelCounts = {}
for featVec in dataSet:
# featVec[-1]获取dataSet每行中最后一个数据,作为字典中的key(标签)
currentLabel = featVec[-1]
# 以currentLabel作为key加入到labelCounts
# 如果当前的键值不存在,则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。
# 键值存在则对应Value+'a',否则为'b'
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
Ent = 0.0
shannonEnt = 0.0
for key in labelCounts:
# 计算正反例样本
# print('labels:', key)
# 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度
prob = float(labelCounts[key]) / numEntries
# 计算香农熵
shannonEnt += -prob * log(prob, 2)
return shannonEnt
def createDataset():
'''
创建数据:西瓜书 76 页
数据类型:不限定
:dataSet:西瓜数据集
:return:dataSet, label
'''
dataSet = [
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'],
['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'],
['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'],
['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'],
['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']
]
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']
return dataSet, labels
def splitDataSet(dataSet, axis, value):
'''
按照给定特征划分数据集
:param dataSet:
:param axis:
:param value:
:return:
'''
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
# reduceFeatVec 为新生的空list
reduceFeatVec = featVec[:axis]
# extend只是扩展长度
reduceFeatVec.extend(featVec[axis + 1:])
# append添加列表
retDataSet.append(reduceFeatVec)
return retDataSet
def chooseBestFeature2Split(dataSet):
'''
选择最好的数据集划分方式
:param dataSet:
:return:
'''
# 提取特属性集合的长度
numFeatures = len(dataSet[0]) - 1
# 根结点的香农熵/整个数据集的原始香农熵
baseEntropy = calcShannonEnt(dataSet)
print('整个数据集的原始香农熵 %.3f' % baseEntropy)
# 特征 i 拥有最好的信息增益
bestInfoGain = 0.0
bestGainRatio = 0.0
bestFeature = -1
featInfoGain = []
featGainRatio = []
for i in range(numFeatures):
# 将dataSet中的数据先按行依次放入example中,然后取得example中的example[i]元素,放入列表featList中
# 提取所有的属性值
featList = [example[i] for example in dataSet]
# print(featList)
# 删除重复的属性值,创建唯一的分类标签列表
#uniqueVals = listDeduplication(featList)
uniqueVals = set(featList)
newEntropy = 0.0
intrinsicValue = 0.0
# 计算每种划分方式的信息熵
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
intrinsicValue += -prob * log(prob, 2)
newEntropy += prob * calcShannonEnt(subDataSet)
# 计算每个属性的信息增益,添加到列表featInfoGain
print('固有值:IV(a)=%.3f' % intrinsicValue)
infoGain = baseEntropy - newEntropy
infoGain = float(Decimal(infoGain).quantize(Decimal('0.000')))
featInfoGain.append((infoGain))
# 计算每个属性的信息增益率,添加到列表featGainRatio
gainRatio = infoGain / intrinsicValue
gainRatio = float(Decimal(gainRatio).quantize(Decimal('0.000')))
featGainRatio.append(gainRatio)
if gainRatio > bestGainRatio:
bestGainRatio = gainRatio
bestFeature = i
return featInfoGain, featGainRatio, bestFeature, bestInfoGain, bestGainRatio, newEntropy
def listDeduplication(x):
'''
set函数就可以
:param x: list
:return: list
'''
return list(dict.fromkeys(x))
if __name__ == '__main__':
dataSet, labels = createDataset()
# 输出
featInfoGain, \
featGainRatio, \
bestFeature,\
bestInfoGain,\
bestGainRatio,\
newEntropy = chooseBestFeature2Split(dataSet)
print('各个属性的信息增益')
d = dict(zip(labels[:-1], featInfoGain))
for key, value in d.items():
print(key, '=', value)
print('各个属性的信息增益率')
c = dict(zip(labels[:-1], featGainRatio))
for key, value in c.items():
print(key, '=', value)
print(labels[bestFeature], '的信息增益率最大= %.3f'% bestGainRatio)
计算结果如下:
整个数据集的原始香农熵 0.998
固有值:IV(a)=1.580
固有值:IV(a)=1.402
固有值:IV(a)=1.333
固有值:IV(a)=1.447
固有值:IV(a)=1.549
固有值:IV(a)=0.874
各个属性的信息增益
色泽 = 0.108
根蒂 = 0.143
敲声 = 0.141
纹理 = 0.381
脐部 = 0.289
触感 = 0.006
各个属性的信息增益率
色泽 = 0.068
根蒂 = 0.102
敲声 = 0.106
纹理 = 0.263
脐部 = 0.187
触感 = 0.007
纹理 的信息增益率最大= 0.263
):
本文地址:https://blog.csdn.net/weixin_40922982/article/details/107114947
如对本文有疑问, 点击进行留言回复!!
Python | 用Python爬取LOL所有的英雄信息以及英雄皮肤
荐 Python之数据分析(坐标刻度定位器、散点图、柱状图、颜色区域填充)
剑指offer JZ31 整数中1出现的次数 Python 解
荐 opencv进阶学习笔记3:像素运算和图像亮度对比度调节
荐 Python全栈(八)Flask项目实战之5.CMS后台权限验证
在Python中使用moviepy进行音视频剪辑混音合成时输出文件无声音问题
Python基础核心经典教程(029)——面向对象特征之多态
网友评论