3.1 决策树的基本思想

　　3.1.1 从一个实例开始（略）

　　3.1.2 决策树的算法框架（略）

　　3.1.3 信息熵测度（略）

　　3.2 ID3决策树

　　3.2.1 ID3算法（略）

　　3.2.2 ID3的实现（Python实现）

　　定义一个ID3DTree的类来封装算法：

　　

#coding:utf-8from numpy import *import mathimport copyimport cPickle as pickle# 定义一个ID3DTree的类来封装算法：class ID3DTree(object):    def __init__(self):        #构造方法        self.tree    = {}      #生成的树        self.dataSet = []      #数据集        self.label   = []      #标签集

　　（1） 数据导入函数

　　

#数据导入函数def loadDataSet(self,path,labels):    recordlist   = []    fp           = open(path,"rb")    content      = fp.read()    fp.close()       rowlist      = content.splitlines() #按行转换为一维表    recordlist   = [row.split("\t") for row in rowlist if row.strip()]    self.dataSet = recordlist    self.labels  = labels

　　（2）执行决策树函数

　　

#执行决策树函数def train(self):    labels    = copy.deepcopy(self.labels)    self.tree = self.buildTree(self.dataSet,labels)

　　3.2.3 决策树主方法

　　（1）构建决策树：创建决策树主程序

　　

# 3.2.3 决策树主方法# （1）构建决策树：创建决策树主程序def buildTree(self,dataSet,labels):    cateList = [data[-1] for data in dataSet]  #抽取源数据集的决策标签列    #程序的终止条件1：如果classList只有一种决策标签，停止划分，返回这个决策标签    if cateList.count(cateList[0]) == len(cateList):        return cateList[0]    #程序的终止条件2：如果数据集的第一个决策标签只有一个，则返回这个决策标签    if len(dataSet[0]) == 1:        return self.maxCate(cateList)    #算法核心：    bestFeat      = self.getBestFeat(dataSet)  #返回数据集的最优特征轴    bestFeatLabel = labels[bestFeat]    tree          = {bestFeatLabel:{}}    del(labels[bestFeat])    #抽取最优特征轴的列向量    uniqueVals = set([data[bestFeat] for data in dataSet]) #去重    for value in uniqueVals:  #决策树递归生长        subLabels = labels[:]  #将删除后的特征类别接建立子类别集        #按最优特征列和值分割数据集        splitDataset = self.splitDataSet(dataSet,bestFeat,value)        subTree      = self.buildTree(splitDataset,subLabels)        tree[bestFeatLabel][value] = subTree    return tree

 　　（2）计算出现次数最多的类别标签

　

#计算出现次数最多的类别标签def maxCate(self,catelist):    items = dict([(catelist.count(i),i) for i in catelist])    return items([max(items.keys())])

（3）计算最优特征

　　

#计算最优特征def getBestFeat(self,dataSet):    #计算特征向量维，其中最后一列用于类别标签，因此要减去    numFeatures  = len(dataSet[0])-1             #特征向量维数=行向量维数-1    baseEntropy  = self.computeEntropy(dataSet)  #基础熵：源数据香农熵    bestInfoFain = 0.0                           #初始化最优的信息增益    bestFeature  = -1                            #初始化最优特征轴    #外循环：遍历数据集各列，计算最优特征轴    # i 为数据集列索引：取值范围0~（numFeatures-1)    for i in xrange(numFeatures):               #抽取第i列的列向量        uniqueVals = set([data[i] for data in dataSet]) #去重：该列唯一值集        newEntropy = 0.0                         #初始化该列的香农熵        for value in uniqueVals:                #内循环：按列和唯一值计算香农熵            #按选定列i和唯一值分割数据集            subDataSet = self.splitDataSet(dataSet,i,value)            prob       = len(subDataSet)/float(len(dataSet))            newEntropy += prob*self.computeEntropy(subDataSet)        infoGain = baseEntropy -newEntropy      #计算最大增益        if(infoGain > bestInfoFain):            #如果信息增益>0            bestInfoFain = infoGain             #用当前的信息增益替代之前的最优增益值            bestFeature  = i                    #重置最优特征为当前列    return bestFeature

 （4）计算信息熵

　　

#计算信息熵def computeEntropy(self,dataSet):              #计算香农熵    datalen  = float(len(dataSet))    cateList = [data[-1] for data in dataSet]  #从数据集中得到类别标签    #得到类别为key，出现次数value的字典    items    = dict([(i,cateList.count(i)) for i in cateList])    infoEntropy = 0.0    for key in items: #香农熵：=-p*log2(p) --infoEntropy = -prob*log(prob,2)        prob = float(items[key])/datalen        infoEntropy -= prob*math.log(prob,2)    return infoEntropy

　（5）划分数据集：分割数据集；删除特征轴所在的数据列，返回剩余的数据集

　　

#（5）划分数据集：分割数据集；删除特征轴所在的数据列，返回剩余的数据集def splitDataSet(self,dataSet,axis,value):    rtnList = []    for featVec in dataSet:        if featVec[axis] == value:            rFeatVec     = featVec[:axis]    #list操作：提取0~（axis-1）的元素            rFeatVec.extend(featVec[axis+1:])#lsit操作：将特征轴（列）之后的元素加回 　　　　　　　rtnList.append(rFeatVec)

　　return rtnList

　　3.2.4 训练决策树

　　代码如下：

　　

#coding:utf-8from numpy import *from ID3DTree import *dtree = ID3DTree()'''Sepal.Length Sepal.Width Petal.Length Petal.Width'''dtree.loadDataSet('iris.txt',['Sepal.Length','Sepal.Width','Petal.Length','Petal.Width'])dtree.train()print dtree.tree

 　　3.2.5 持久化决策树

　　ID3类也提供了专门的方法用于保存决策树到文件，并可从文件读取决策树到内存

def storeTree(self,inputTree,filename):     #存储树到文件        fw = open(filename,'w')        pickle.dump(inputTree,fw)        fw.close()    def grabTree(self,filename):               #从文件抓取树        fr = open(filename)        return pickle.load(fr)

　　执行代码：

dtree.storeTree(dtree.tree,"data.tree")mytree = dtree.grabTree("data.tree")print mytree

　　3.2.6 决策树的分类

def predict(self,inputTree,featLabels,testVec): #分类器        root      = inputTree.keys()[0]         #树根节点        seconDict = inputTree[root]             #value-子树结构或分类标签        featIndex = featLabels.index(root)      #根节点在分类标签中的位置        key       = testVec[featIndex]        valueOfFeat = seconDict[key]        if isinstance(valueOfFeat,dict):       #判断是否仍然是字典的类型            classLabel = self.predict(valueOfFeat,featLabels,testVec) #递归分类        else:            classLabel = valueOfFeat        return classLabel

　　测试代码：

dtree  = ID3DTree()labels = ['Sepal.Length','Sepal.Width','Petal.Length','Petal.Width']vector = ['5.1000000e+00', '3.5000000e+00' ,'1.4000000e+00','2.0000000e-01']mytree = dtree.grabTree('data.tree')print u"真实输出",u"no",u"->",u"决策树输出",dtree.predict(mytree,labels,vector)

输出结果：

真实输出 no -> 决策树输出 0.0000000e+00