决策树案例：是否打⽹球
决策树的划分依据之⼀是信息增益的⼤⼩
对于下⾯这个例⼦，使⽤ID3算法，ID3：使⽤信息增益g(D,A)进⾏特征选择
⼀个特征的信息增益(或信息增益率，或基尼系数)越⼤，表明特征对样本的熵的减少能⼒更强，这个特征使得数据由不确定性到确定性的能⼒越强
下⾯就以⼀个经典的打⽹球的例⼦来说明如何构建决策树。我们今天是否去打⽹球（play）主要由天⽓（outlook）、温度（temperature）、湿度（humidity）、是否有风（windy）来确定。样本中共14条数据
那么在计算的时候，会先计算H（play）的值，然后在计算每个特征的g（play|A），⽐较后记录下来信息增益最⼤的特征，然后把它作为根节点，接着在计算各个⼦节点的分⽀。
代码如下：
import operator
from math import log
from operator import *
"""
这个算法是迭代好⼏次最后求出这个决策树，那么在下⾯分析的过程中，只分析第⼀次迭代的情况
"""
def storeTree(inputTree, filename):
import pickle
fw = open(filename, 'wb')  # pickle默认⽅式是⼆进制，需要制定'wb'
pickle.dump(inputTree, fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename, 'rb')  # 需要制定'rb'，以byte形式读取
return pickle.load(fr)
return pickle.load(fr)
def createDataSet():
'''
dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
labels = ['no surfacing','flippers']
'''
dataSet = [['sunny', 'hot', 'high', 'False', 'no'],
['sunny', 'hot', 'high', 'True', 'no'],
['overcast', 'hot', 'high', 'False', 'yes'],
['rain', 'mild', 'high', 'False', 'yes'],
['rain', 'cool', 'normal', 'False', 'yes'],
['rain', 'cool', 'normal', 'True', 'no'],
['overcast', 'cool', 'normal', 'True', 'yes'],
['sunny', 'mild', 'high', 'False', 'no'],
['sunny', 'cool', 'normal', 'False', 'yes'],
['rain', 'mild', 'normal', 'False', 'yes'],
['sunny', 'mild', 'normal', 'True', 'yes'],
['overcast', 'mild', 'high', 'True', 'yes'],
['overcast', 'hot', 'normal', 'False', 'yes'],
['rain', 'mild', 'high', 'True', 'no']]
labels = ['outlook', 'temperature', 'humidity', 'windy']
return dataSet, labels
def calcShannonEnt(dataSet):  # 计算⾹农熵
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]  # 取得最后⼀列数据，该属性取值情况有多少个
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
# 计算熵
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
# 定义按照某个特征进⾏划分的函数splitDataSet
# 输⼊三个变量（待划分的数据集，特征，分类值）
# axis特征值中0代表no surfacing，1代表flippers
# value分类值中0代表否，1代表是
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:  # 取⼤列表中的每个⼩列表
if featVec[axis] == value:
reduceFeatVec = featVec[:axis]
d(featVec[axis + 1:])
retDataSet.append(reduceFeatVec)
"""
返回出⾃⾝的value外的其他特征的全部情况，⽐如说如果是第⼀次迭代时，然后传递进来的参数是整个dataSet，那么axis是0，value是sunny 那么就会得到value是sunny的全部的情况，并且把这个元组保存下来，但是不包括sunny
就是下⾯这张结果：
[['hot', 'high', 'False', 'no'], ['hot', 'high', 'True', 'no'], ['mild', 'high', 'False', 'no'], ['cool', 'normal', 'False', 'yes'], ['mild', 'normal', 'True', 'yes']]    """
return retDataSet  # 返回不含划分特征的⼦集
def chooseBestFeatureToSplit(dataSet):
numFeature = len(dataSet[0]) - 1
"""
在这⾥要说明⼀下，因为dataSet[0]是指每次迭代后的数据集，第⼀次时dataSet[0]值是：
['sunny', 'hot', 'high', 'False', 'no']
那么，numFeature的值应该是4
"""
baseEntropy = calcShannonEnt(dataSet)
bestInforGain = 0
bestFeature = -1
for i in range(numFeature):
"""
如果第⼀次numFeature=4，那么range(4)=[0,1,2,3]，因此实际上就是依次统计列的值，然后存⼊featList中
"""
featList = [number[i] for number in dataSet]  # 得到某个特征下所有值（某列）
uniquelVals = set(featList)  # set⽆重复的属性特征值，得到所有⽆重复的属性取值
"""
那么第⼀次迭代时，uniquelVals的值是：
{'overcast', 'rain', 'sunny'} 对应第0列的⽆重复的值
{'cool', 'mild', 'hot'}  对应第1列的⽆重复的值
{'high', 'normal'}  对应第2列的⽆重复的值
{'False', 'True'}  对应第3列的⽆重复的值
"""
# 计算每个属性i的概论熵
newEntropy = 0
for value in uniquelVals:
subDataSet = splitDataSet(dataSet, i, value)  # 得到i属性下取i属性为value时的集合
prob = len(subDataSet) / float(len(dataSet))  # 每个属性取值为value时所占⽐重
newEntropy += prob * calcShannonEnt(subDataSet)
inforGain = baseEntropy - newEntropy  # 当前属性i的信息增益
if inforGain > bestInforGain:
bestInforGain = inforGain
bestFeature = i
return bestFeature  # 返回最⼤信息增益属性下标
# 递归创建树,⽤于出出现次数最多的分类名称
def majorityCnt(classList):
classCount = {}
for vote in classList:  # 统计当前划分下每中情况的个数
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items, key=operator.itemgetter(1), reversed=True)  # reversed=True表⽰由⼤到⼩排序
# 对字典⾥的元素按照value值由⼤到⼩排序
return sortedClassCount[0][0]
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]  # 创建数组存放所有标签值，取dataSet⾥最后⼀列（结果）
"""
第⼀次迭代时，这个classList应该是个列表，那么具体的值应该是下⾯显⽰的
['no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
"""
# 类别相同，停⽌划分
unt(classList[-1]) == len(classList):  # 判断classList⾥是否全是⼀类，count() ⽅法⽤于统计某个元素在列表中出现的次数        return classList[-1]  # 当全是⼀类时停⽌分割
# 长度为1，返回出现次数最多的类别
if len(classList[0]) == 1:  # 当没有更多特征时停⽌分割，即分到最后⼀个特征也没有把数据完全分开，就返回多数的那个结果        return majorityCnt(classList)
# 按照信息增益最⾼选取分类特征属性
bestFeat = chooseBestFeatureToSplit(dataSet)  # 返回分类的特征序号，按照最⼤熵原则进⾏分类
bestFeatLable = labels[bestFeat]  # 该特征的label, #存储分类特征的标签
myTree = {bestFeatLable: {}}  # 构建树的字典
del (labels[bestFeat])  # 从labels的list中删除该label
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
print(uniqueVals)
for value in uniqueVals:
subLables = labels[:]  # ⼦集合 ，将labels赋给sublabels，此时的labels已经删掉了⽤于分类的特征的标签
# 构建数据的⼦集合，并进⾏递归
myTree[bestFeatLable][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLables)
return myTree
if __name__ == "__main__":
my_Data, labels = createDataSet()
# print(calcShannonEnt(my_Data))
Mytree = createTree(my_Data, labels)
print(Mytree)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。