python决策树id3算法_机器学习(2) 决策树python实现（ID3算法）

本文基于李航老师的《统计学习方法》，和Peter Harrington的《机器学习实战》

决策树可以说是对KNN的线性搜索方法的一个改进(其实KNN算法有一个改进的kd tree算法。也是借用了树的这种数据结构来加快搜索效率)。

决策权的理论基础可以参见李航老师的《统计学习方法》第四章的内容。说一下比较重要的点:1.特征选择 2.树的建立 3.树的修剪(由于ID3算法比较古老并没有涉及到树的修剪，后来的学习笔记CART和C4.5会涉及到树的修剪)

1.特征选择

选取合适的特征作为(根)树节点。这里涉及到信息论里面的信息熵和条件信息熵的概念。我对信息熵的理解就是信息的混乱程度，所以如果信息熵(记为H(D))越大，说明还信息的内容越混乱，信息的不确定性就越高。条件信息熵(记作H(D|A))和条件概率的意思差不多，含义为在某一信息特征A确定的情况下数据集D信息熵。那么信息增益g(D,A)定义为：g(D,A)=H(D)-H(D|A)。那么信息增益表示啥意思呢？其实从定义可以看出，信息增益表示为由于特征A使得数据集D的分类的不确定性的减少程度。显然信息增益的大小是依赖与特征的，一般信息增益越大，表示该特征的分类效果就越好。

注：信息熵公式

条件熵

(ai 为特征A的所有取值)

信息增益：g(D,A)=H(D)-H(D|A)

2.树的建立

树的承载方式有很多种，可以构建结点类来添加和删除结点。这里面使用python里面的字典来构建和存储树结构。具体的方法见后面的代码分析。

3.树的修剪

一般按照信息增益构建成的树，对于训练集的表示效果非常好。但是对于测试集的表现确很差。这种情况出现的原因是因为在树的训练过程中出现了过拟合现象。所以算法需要对树的树枝进行修剪。来减轻过拟合的影响(ID3算法没有涉及到树枝的修剪)

——————————————————代码段分析————————————

首先post出数据集的格式：【特征1，特征2，……，类型】(特征表述用0，1，2等标量来表示)

calcShannonEnt函数是用来计算信息熵的：注意这是对类别进行计算信息熵，不是对特征

def calcShannonEnt(dataset): # 计算信息熵

num_of_Entries = 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.keys():

prob = labelCounts[key] / num_of_Entries

shannonEnt -= prob * log2(prob)

return shannonEnt

splitDataSet函数是用来划分数据的：为什么要划分？这是为了我们计算条件信息熵。想想条件信息熵的定义【在某一特征确定的情况下，计算数据集的分类的信息熵】

所以在进行条件信息熵计算时，对于某一个特征A，其所有的取值(a1,a2,a3……)都要被划分为在自己特征取值已经确定情况下(例如A=a1)的子集。

def splitDataSet(dataset, axis, value): # 根据特征划分数据axis表示特征， value表示特征的取值

subDataSet = []

for featVec in dataset:

if featVec[axis] == value:

reduce_featVec = featVec[0:axis]

reduce_featVec.extend(featVec[axis+1:])

subDataSet.append(reduce_featVec)

return subDataSet

chooseBestFeatureToSplit函数是用来划分数据集的。函数返回最佳的划分特征

def chooseBestFeatureToSplit(dataset): #选取最佳的特征来划分数据

num_of_feature = len(dataset[0])-1

baseEntropy = calcShannonEnt(dataset) # 计算数据集D的分类信息熵

best_info_gain = 0.0

bestLabel_index = -1

for i in range(num_of_feature):

feature_vec = [each[i] for each in dataset]

uniqueVals = set(feature_vec) #确保特征取值的唯一性

newEntroy = 0.0

for value in uniqueVals: #开始计算特征确定情况下的条件信息熵

subdataset = splitDataSet(dataset, i, value)

prob = len(subdataset) / float(len(dataset))

newEntroy += prob * calcShannonEnt(subdataset)

info_gain = baseEntropy - newEntroy #信息增益

if info_gain > best_info_gain:

best_info_gain = info_gain

bestLabel_index = i

return bestLabel_index #最后返回最佳特征

majorityVote函数是起多数表决的作用的。如果一个树分类到最后一个子节点的时候，但是这个时候子节点中的数据类别还不是全部一样的，这个时候就要用多数表决方法来强制分类。

#多数表决函数

def majorityVote(classlist):

classcount = {}

for each in classlist:

if each not in classcount.keys():

classcount[each] = 0

classcount[each] += 1

sorted_classcount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True) #按字典中value进行排序，逆序排列

return sorted_classcount[0][0] #输出“得票”最多得分类

creatTree函数用来创建树状结构。这个函数需要被自己递归调用，因此很方便就会完成树得建造。(递归得使用一定要注意设置递归的终止条件，不然会陷入无限递归【血泪得教训

：(】)

def creatTree(dataset, label): # 创建树

t_label = label[:] # 注意！ 传进来得label是个全局量，所以最好不要对它进行直接修改。一般拷贝它得一个副本

classlist = [each[-1] for each in dataset]

# 设置树的终止条件(有两个。其一是当类集合中都是同一种类的时候，其二是当划分到叶节点时，类的集合中的种类不全是相同的，这时要强制性的进行暴力分类)

if classlist.count(classlist[0]) == len(classlist):

return classlist[0]

if len(dataset) == 1:

return majorityVote(classlist)

best_feature_index = chooseBestFeatureToSplit(dataset)

best_feature = t_label[best_feature_index]

myTree = {best_feature: {}} #树的基本架构

del(t_label[best_feature_index])

feature_vec = [each[best_feature_index] for each in dataset]

uniqueValues = set(feature_vec)

for value in uniqueValues:

sublabel = t_label[:]

myTree[best_feature][value] = creatTree(splitDataSet(dataset, best_feature_index, value), sublabel) #递归的调用createTree来创建树

return myTree

classify函数起到分类作用。

def classify(mytree, feat_label, testvec): #测试、分类函数

firstStr = list(mytree.keys())[0]

secondDict = mytree[firstStr]

feat_index = feat_label.index(firstStr) #用index来寻找特定的label的值

for key in secondDict.keys():

if testvec[feat_index] == key:

if isinstance(secondDict[key], dict):

classLabel = classify(secondDict[key], feat_label, testvec) #递归调用来判别检索分类

else:

classLabel = secondDict[key]

return classLabel

storeTree函数和loadTree函数起存储和调用得作用[这两个函数出现是为了效率的提高。因为树的创建是一个缓慢的过程，即便我们这边只用了六组数据都需要运行几秒钟，所以为了避免每次运行时都要重复的进行树的创建。我们用pickle模块函数来对树进行腌制( pickle的翻译就是腌制的意思)]

def storeTree(mytree, filename):#“腌制”树

fw = open(filename, 'wb') #注意，这里面要用二进制进行写入

pickle.dump(mytree, fw)

fw.close() #文件打开别忘了关闭

def loadTree(filename):#“取出树”

fr = open(filename, 'rb') #二进制写入就要二进制读取

return pickle.load(fr)

————————————————完整代码post——————————————

from math import log2

import operator

import pickle

def creatDataset(): # 数据集的形成

dataset = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

labels = ['no surfacing', 'flippers']

return dataset, labels

def calcShannonEnt(dataset): # 计算信息熵

num_of_Entries = 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.keys():

prob = labelCounts[key] / num_of_Entries

shannonEnt -= prob * log2(prob)

return shannonEnt

def splitDataSet(dataset, axis, value): # 根据特征划分数据axis表示特征， value表示特征的取值

subDataSet = []

for featVec in dataset:

if featVec[axis] == value:

reduce_featVec = featVec[0:axis]

reduce_featVec.extend(featVec[axis+1:])

subDataSet.append(reduce_featVec)

return subDataSet

# 选择最佳的划分数据集的特征(ID3的信息增益法)(C4.5)

def chooseBestFeatureToSplit(dataset):

num_of_feature = len(dataset[0])-1

baseEntropy = calcShannonEnt(dataset)

best_info_gain = 0.0

bestLabel_index = -1

for i in range(num_of_feature):

feature_vec = [each[i] for each in dataset]

uniqueVals = set(feature_vec)

newEntroy = 0.0

for value in uniqueVals:

subdataset = splitDataSet(dataset, i, value)

prob = len(subdataset) / float(len(dataset))

newEntroy += prob * calcShannonEnt(subdataset)

info_gain = baseEntropy - newEntroy

if info_gain > best_info_gain:

best_info_gain = info_gain

bestLabel_index = i

return bestLabel_index

#多数表决函数

def majorityVote(classlist):

classcount = {}

for each in classlist:

if each not in classcount.keys():

classcount[each] = 0

classcount[each] += 1

sorted_classcount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)

return sorted_classcount[0][0]

#树的创建

def creatTree(dataset, label):

t_label = label[:]

classlist = [each[-1] for each in dataset]

# 设置树的终止条件

if classlist.count(classlist[0]) == len(classlist):

return classlist[0]

if len(dataset) == 1:

return majorityVote(classlist)

best_feature_index = chooseBestFeatureToSplit(dataset)

best_feature = t_label[best_feature_index]

myTree = {best_feature: {}}

del(t_label[best_feature_index])

feature_vec = [each[best_feature_index] for each in dataset]

uniqueValues = set(feature_vec)

for value in uniqueValues:

sublabel = t_label[:]

myTree[best_feature][value] = creatTree(splitDataSet(dataset, best_feature_index, value), sublabel) #递归调用createTree来创建树

return myTree

#判别函数

def classify(mytree, feat_label, testvec):

firstStr = list(mytree.keys())[0]

secondDict = mytree[firstStr]

feat_index = feat_label.index(firstStr)

for key in secondDict.keys():

if testvec[feat_index] == key:

if isinstance(secondDict[key], dict):

classLabel = classify(secondDict[key], feat_label, testvec)

else:

classLabel = secondDict[key]

return classLabel #这块可能会存在隐藏的bug[系统提示，实际中操作还没遇到]

#腌制树

def storeTree(mytree, filename):

fw = open(filename, 'wb')

pickle.dump(mytree, fw)

fw.close()

#取出树

def loadTree(filename):

fr = open(filename, 'rb')

return pickle.load(fr)

if __name__ == "__main__":

filepath = 'D:/pycharm/PyCharm Community Edition 2018.2.4/Practice/decision tree/storaged_Tree'

#注意我是已经腌制好树了。如果想要在自己的编译器上可以使用。需要先调用storeTree函数，后来再通过filepath来调用loadTree函数来引用创建的树！！！

dataSet, Labels = creatDataset()

Tree = loadTree(filepath)

re = classify(Tree, Labels, [1, 1])

print(re)

#文本的保存一般不会用到pickle。具体pickle的用法可以参考pickle的手册