前言
- 决策树在我们的生活中应用非常广泛，甚至可以说无处不在。
- 小实例：下午要上课，但是女友来找，我是上课呢，还是陪女友，想想那个重要，就选哪个！
- 决策树绝大多数用来分类，也可以用于回归(取节点平均值即可)。
- 决策树划分数据集常用算法有 ID3算法， C4.5算法，本章节使用 ID3 算法划分数据集。
ID3 算法
- 从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。所以 ID3 算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。
- 设 D 为用类别对训练元组进行的划分，则 D 的熵表示为:
其中 pi 表示第 i 个类别在整个训练元组中出现的概率，可以用此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是 D 中元组的类标号所需要的平均信息量。 -
现在我们假设将训练元组 D 按属性 A 进行划分，则 A 对 D 划分的数学期望信息为：
-
信息增益即为两者的差值:
- ID3 算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。
1，准备数据如下
- 图表中的数据用编程实现如下
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
-
计算给定数据集的香农熵，代码实现
from math import log
def calcShannonEnt(dataSet):
# 数据集样本数
numEntries = len(dataSet)
# 定义字典，用于计数
labelCounts = {}
# 从数据集中，每次取出一行
for featVec in dataSet:
# 取出每一行的最后一列，即 'yes' or 'no'
currentLabel = featVec[-1]
# 判断 'yes' or 'no' 是否在字典中，不在加入计数为0，在则计数加1
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
# 定义容器，存放 熵
shannonEnt = 0.0
# 依据信息熵公式，计算该 dataSet 的信息熵
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2)
# 返回 dataSet 的信息熵
return shannonEnt
- 测试一下
myDat, labels = createDataSet()
print(myDat)
print(labels)
print(calcShannonEnt(myDat))
# [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
# ['no surfacing', 'flippers']
# 0.9709505944546686
# 数据越混乱，熵越高，增加更多分类，观察熵值变化
myDat[0][-1] = 'maybe' # 熵越高，则混合的数据也越多
print(calcShannonEnt(myDat))
# 1.3709505944546687
- 按照给定特征划分数据集
# dataSet 数据集
# axis 列号
# value 将列号为axis，值为value的 其他数据分个出来，看实例
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis + 1 : ])
retDataSet.append(reducedFeatVec)
return retDataSet
- 测试一下
myDat, labels = createDataSet()
print(myDat)
print(splitDataSet(myDat, 0, 1))
print(splitDataSet(myDat, 0, 0))
print(splitDataSet(myDat, 1, 1))
print(splitDataSet(myDat, 1, 0))
# [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
# [[1, 'yes'], [1, 'yes'], [0, 'no']]
# [[1, 'no'], [1, 'no']]
# [[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
# [[1, 'no']]
-
选择最好的数据集划分方式
现在我们假设将训练元组 D 按属性 A 进行划分，则 A 对 D 划分的数学期望信息为：
信息增益即为两者的差值:
def chooseBestFeatureToSplit(dataSet):
# 每一行最后一列为 label,计算 feature 列数
numFeatures = len(dataSet[0]) - 1
# 计算整个数据集的信息熵
baseEntropy = calcShannonEnt(dataSet)
# bestInfoGain 信息增益预先设为为 0.0
# bestFeature 最好划分的列标签，预先设为 -1
bestInfoGain = 0.0; bestFeature = -1
# 依据 feature 数进行循环
for i in np.arange(numFeatures):
# 将每一行数据取出，存为list，次数为feature数，即没有最后一列label
featList = [example[i] for example in dataSet]
# set 去冗余
uniqueVals = set(featList)
# 定义熵容器
newEntropy = 0.0
# 从 uniqueVals 集合中迭代
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
- 测试一下
myDat, labels = createDataSet()
print(chooseBestFeatureToSplit(myDat)) # 0
测试结果为 0，即选择第0列进行划分。
- 多数表决的方法决定该叶子节点的分类
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用 多数表决的方法决定该叶子节点的分类
def majorityCnt(classList):
# 定义一个用于计数的字典
# 注，此时classList 只有一列，为类标签，因为类标签不唯一，才用此方法找最多的label
classCount = {}
# 从 classList 迭代取值
for vote in classList:
# 如果从classList中取出的值不在classCount字典中，则将该值放入字典，
# 计数为1，否则在字典中的该值计数加1
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
# 找到字典中 value 最大的 key 并返回
newvalue = -1
for key in classCount:
if newvalue < classCount[key]:
newkey = key
newvalue = classCount[key]
return newkey
- 创建树的函数代码
# 两个输入参数-- 数据集， 标签列表
def createTree(dataSet, labels):
# 将 dataSet 最后一列放入 classList
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)
# 将 信息增益最大的列的列名存入 bestFeatLabel
bestFeatLabel = labels[bestFeat]
# 定义树，存为字典形式
myTree = {bestFeatLabel:{}}
# 将信息增益最大的列名删除
del(labels[bestFeat])
# 将信息增益最大的列取出
featValues = [example[bestFeat] for example in dataSet]
# 去除冗余
uniqueVals = set(featValues)
# 迭代取值
for value in uniqueVals:
# 这行代码复制了类标签
subLabels = labels[:]
# 递归创建树 方法：字典的嵌套
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# 返回创建好的树
return myTree
- 测试一下
myDat, labels = createDataSet()
myTree = createTree(myDat, labels)
print(myTree)
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
- 使用决策树执行分类
# inputTree 创建好的决策树
# featLabels 存放feature名的list
# testVec 预测的feature
def classify(inputTree, featLabels, testVec):
# 取出决策树的key，存为list，并取第一个key
firstStr = list(inputTree.keys())[0]
# 取出第一个key所对应的value
secondDict = inputTree[firstStr]
# 取出 firstStr 所在的列号
featIndex = featLabels.index(firstStr)
# 这段代码为递归找到类别，依次递归向下找
for key in secondDict.keys():
if testVec[featIndex] == key:
if isinstance(secondDict[key], dict):
classLabel = classify(secondDict[key], featLabels, testVec)
else:
classLabel = secondDict[key]
return classLabel
- 测试分类效果
myDat, labels = createDataSet()
print(labels)
# ['no surfacing', 'flippers']
myTree = createTree(myDat, labels)
print(myTree)
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
# 经过 createTree 已经把labels给破坏了，所以现在要从新获取labels
myDat, labels = createDataSet()
print(classify(myTree, labels, [1, 0])) # no
print(classify(myTree, labels, [1, 1])) # yes
