《机器学习实战》3：决策树

    上一篇博文讲的k-NN算法是最简单的一种分类算法，精度高。但是，时间复杂度和空间复杂度都比较大，还有一个重要的缺点就是它无法给出数据的知识信息。说白了，就是不能为分类提供一个模型。这篇中讲到的决策树则能够从数据中提取规则，这些机器根据数据集创建规则时就是机器学习的过程。

1.决策树算法：
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
2.ID3算法
决策树的关键就是进行数据划分，数据划分有两种算法：ID3和C4.5。我们这里使用ID3算法。
简单的说，ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。
关于信息增益的计算，可以参照以下博文，讲的简单明了：

http://shiyanjun.cn/archives/417.html

这里只列出公式，数据集的信息熵通过下式计算：

按照某一属性进行数据划分，得到的新的信息熵：

信息增益即为两者的差值：


要想计算信息增益，首先需要计算熵。
新建trees.py编辑代码如下：

from math import *
import operator
#计算信息熵
def calcShannonEnt(dataSet):
    #数据数量
    numEntries = len(dataSet)
    labelCounts = {}
	#统计每个属性出现的次数
    for featVec in dataSet: #the the number of unique elements and their occurance
        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) #log base 2
    return shannonEnt

同样，我们创建简单的训练数据，测试该函数：

#产生简单的训练数据
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

进入python界面，执行一下命令
>>>import trees
>>>myData,labels=trees.createDataSet()
>>>trees.calcShannonEnt(myData)
输出训练数据的熵值：
0.97.95.5944546686
3 现在得到了测试信息上的方法，我们下一步需要划分数据集。我们将要对每个特真正划分的数据结果进行熵的计算，通过信息增益的大小，判断那个属性划分数据集是最好的方式。我们有限系一个划分数据集的函数：

#划分数据集合，参数dataSet：待划分的数据集，axis表示划分数据集的属性在第几列
#value表示属性的值
#返回值：数据集合中属性axis列，属性值为value的数据集合，新集合的属性个数变为N-1
def splitDataSet(dataSet,axis,value):
    #创建一个新的数据集，用于存放划分之后的数据集合
    reDataSet=[]
    for featVec in dataSet:
        if featVec[axis]== value:
            #如何有符合条件的属性，添加到新的数据集中
            #注意，这里面去掉了用于划分的属性列
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            reDataSet.append(reducedFeatVec)
    return reDataSet

测试数据集合：
>>>reload(trees)
>>>myData,Labels=trees.createDataSet()
按照第一列属性进行划分，划分的值为1
>>>trees.splitDataSet(myData,0,1)

返回[[1,'yes'],[1,'yes'],[0,'no']]

4.接下来我们就可以循环使用上面的函数，选择最好的划分属性，继续编辑代码如下：

#选择最好的划分属性
def chooseBestFeatureToSplit(dataSet):
    #属性个数
    numFeatures=len(dataSet[0])-1
    #原始数据的信息熵
    baseEntropy=calcShannonEnt(dataSet)
    #初始化信息增益、最好划分属性
    baseInfoGain=0.0
    bestFeature=-1
    #遍历所有属性
    for i in range(numFeatures):
        #统计第i个属性的值,注意python的这种写法，简直太强大了！
        featList=[example[i] for example in dataSet]
        #去重
        uniqueVals=set(featList)
        #初始化划分后的信息熵
        newEntropy=0.0
        #计算划分之后的信息熵,对应第二个公式
        for value in uniqueVals:
            subDataset=splitDataSet(dataSet,i,value)
            prob=len(subDataset)/float(len(dataSet))
            newEntropy+=prob*calcShannonEnt(subDataset)
        infoGain=baseEntropy-newEntropy;
        #获得最大信息增益的为最好的划分属性
        if(infoGain>baseInfoGain):
            baseEntropy=infoGain;
            bestFeature=i
    return bestFeature

5 上一步我们其实实现了决策树是如何划分树枝的。下面我们将以上的方法整合起来，构建一个真正的决策树。
构建树的过程是一个递归过程：首先我们根据最好的属性进行数据划分，由于数据的特征值可能不止两个，因此可能存在大于两个的分支，第一次划分之后，数据将被传递到下一节点。在这个节点上，我们继续进行数据划分。递归进行下去。递归终止的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点。当然，我们也可以设置算法可以划分的最大分组数目。先写一个统计函数：

#统计分类名称列表中每个类标签出现的频率
def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():classCount[vote]=0
        classCount[value]+=1
    sortedClassCount=sorted(classCount.iteritems(),\
                            key=operator.iteritems(1),reverse=True)
    return sortedClassCount[0][0]

接下来，我们就可以按照刚才的递归方式及递归结束时间构建决策树了：

#构建决策树
def createTree(dataSet,labels):
    #获得分类名称列表
    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)
    #这里的labels表示属性列表，并不是类标签
    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

测试我们的决策树
>>>reload(trees)
>>>myData,Labels=trees.createDataSet()
>>>myTree=createTree(myData,Labels)
得到如下结果：

评论

1 楼 monkeyVon 2015-02-02  

感谢楼主分享~不过有个地方有点错误，majorityCnt(classList)函数里调用的sorted函数参数有点问题，应该是operator.itemgetter(1)，而不是operator.iteritems(1)