决策树例子与python实现

决策树的划分依据之一是信息增益的大小

对于下面这个例子，使用ID3算法，ID3：使用信息增益g(D,A)进行特征选择 

一个特征的信息增益(或信息增益率，或基尼系数)越大，表明特征对样本的熵的减少能力更强，这个特征使得数据由不确定性到确定性的能力越强

下面就以一个经典的打网球的例子来说明如何构建决策树。我们今天是否去打网球（play）主要由天气（outlook）、温度（temperature）、湿度（humidity）、是否有风（windy）来确定。样本中共14条数据。那么具体讲解参照这篇博客

那么在计算的时候，会先计算H（play）的值，然后在计算每个特征的g（play|A），比较后记录下来信息增益最大的特征，然后把它作为根节点，接着在计算各个子节点的分支。

那么，具体实现如下，参考了博客.html

import operatorfrom math import log
from operator import *
"""
这个算法是迭代好几次最后求出这个决策树，那么在下面分析的过程中，只分析第一次迭代的情况
"""def storeTree(inputTree, filename):import picklefw = open(filename, 'wb')  # pickle默认方式是二进制，需要制定'wb'pickle.dump(inputTree, fw)fw.close()def grabTree(filename):import picklefr = open(filename, 'rb')  # 需要制定'rb'，以byte形式读取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, labelsdef calcShannonEnt(dataSet):  # 计算香农熵numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]  # 取得最后一列数据，该属性取值情况有多少个if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1# 计算熵shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntriesshannonEnt -= 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]reduceFeatVec.extend(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 = 0bestFeature = -1for 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 = 0for 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 = inforGainbestFeature = ireturn bestFeature  # 返回最大信息增益属性下标# 递归创建树,用于找出出现次数最多的分类名称
def majorityCnt(classList):classCount = {}for vote in classList:  # 统计当前划分下每中情况的个数if vote not in classCount.keys():classCount[vote] = 0classCount[vote] += 1sortedClassCount = 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']"""# 类别相同，停止划分if classList.count(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中删除该labelfeatValues = [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 myTreeif __name__ == "__main__":my_Data, labels = createDataSet()# print(calcShannonEnt(my_Data))Mytree = createTree(my_Data, labels)print(Mytree)

那么程序运行的结果是：

那么画成树就是下面的样子：

决策树例子与python实现

决策树的划分依据之一是信息增益的大小

对于下面这个例子，使用ID3算法，ID3：使用信息增益g(D,A)进行特征选择 

一个特征的信息增益(或信息增益率，或基尼系数)越大，表明特征对样本的熵的减少能力更强，这个特征使得数据由不确定性到确定性的能力越强

下面就以一个经典的打网球的例子来说明如何构建决策树。我们今天是否去打网球（play）主要由天气（outlook）、温度（temperature）、湿度（humidity）、是否有风（windy）来确定。样本中共14条数据。那么具体讲解参照这篇博客

那么在计算的时候，会先计算H（play）的值，然后在计算每个特征的g（play|A），比较后记录下来信息增益最大的特征，然后把它作为根节点，接着在计算各个子节点的分支。

那么，具体实现如下，参考了博客.html

import operatorfrom math import log
from operator import *
"""
这个算法是迭代好几次最后求出这个决策树，那么在下面分析的过程中，只分析第一次迭代的情况
"""def storeTree(inputTree, filename):import picklefw = open(filename, 'wb')  # pickle默认方式是二进制，需要制定'wb'pickle.dump(inputTree, fw)fw.close()def grabTree(filename):import picklefr = open(filename, 'rb')  # 需要制定'rb'，以byte形式读取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, labelsdef calcShannonEnt(dataSet):  # 计算香农熵numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]  # 取得最后一列数据，该属性取值情况有多少个if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1# 计算熵shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntriesshannonEnt -= 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]reduceFeatVec.extend(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 = 0bestFeature = -1for 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 = 0for 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 = inforGainbestFeature = ireturn bestFeature  # 返回最大信息增益属性下标# 递归创建树,用于找出出现次数最多的分类名称
def majorityCnt(classList):classCount = {}for vote in classList:  # 统计当前划分下每中情况的个数if vote not in classCount.keys():classCount[vote] = 0classCount[vote] += 1sortedClassCount = 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']"""# 类别相同，停止划分if classList.count(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中删除该labelfeatValues = [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 myTreeif __name__ == "__main__":my_Data, labels = createDataSet()# print(calcShannonEnt(my_Data))Mytree = createTree(my_Data, labels)print(Mytree)

那么程序运行的结果是：

那么画成树就是下面的样子：