机器学习实战（二）决策树

前言

如果说k-邻近算法还比较简单，那么决策树的构造就涉及到比较多的函数调用，所以我自己将流程画出来，防止自己在各种各样的调用中晕头转向

决策树

k-邻近算法可以完成很多分类任务，但是它存在最大的缺点在于无法给出数据的内在含义

决策树的主要优势在于数据形式非常容易理解

决策树的一个重要任务是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。

决策树的构造

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据

缺点：可能会产生过度匹配问题

使用数据类型：数值型和标称型

概念：信息增益

划分数据集的大原则是：将无序的数据变得更加有序。

在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择

集合信息的度量方式称为香农熵或者简称为熵。

熵就是信息量如果我们根据它公式来形容这个概念的话，那么对于一个事物，它的分类越多，越复杂则表明他的熵更大。计算熵的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def calcShannonEnt(dataSet):
    numEntires=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])/numEntires
        shannonEnt-=prob*log(prob,2)
    return shannonEnt

上面的代码主要用于计算yes和no这两种分类的熵，用到的dataset定义如下

1
2
3
4
5
6
7
8
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

划分数据集

我们将每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式

划分数据集只需要构造一个dataset每个特征的子集即可

1
2
3
4
5
6
7
8
def splitDataSet(dataSet,axis,value):
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

创建一个选择最好数据集划分方式的函数，将划分数据集和计算熵的过程加进去，对每一个特征都进行划分数据集和计算熵，把计算出来的熵减去基础熵，算出信息增益，信息增益最多的就是最好的数据集划分方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def chooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1
    baseEntropy=calcShannonEnt(dataSet)
    bestInfoGain=0.0;bestFeature=-1
    for i in range(numFeatures):
        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>bestInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature

上面所述的为寻找最佳特征，流程图如下

1

递归构建决策树

递归函数停止的条件有两个，一：所有分类标签完全相同，则直接返回该类标签。二：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)
    print bestFeat
    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

这个递归有点绕需要仔细阅读，我表达能力有限也说不清楚。总之我们就是建立了一个决策树，最后一步就是使用这个决策树来完成分类啦。

分类函数也是一个递归函数，在存储带有特征的数据会面临一个问题：程序无法确定特征在数据集中的位置，例如前面例子的第一个用于划分数据集的特征是no surfacing属性，但是在实际数据集中该属性存储在哪个位置？第一个属性还是第二个属性？特征标签列表将帮助我们处理这个问题。使用index方法查找当前列表中第一个匹配firstStr变量的元素。然后代码递归遍历整棵树，比较testVec变量中的值与树节点的值，如果达到叶子节点，则返回当前节点的分类标签。

1
2
3
4
5
6
7
8
9
10
11
def classify(inputTree,featLabels,testVec):
    firstStr=inputTree.keys()[0]
    secondDict=inputTree[firstStr]
    featIndex=featLabels.index(firstStr) #由于不知道决策树第一个特征在label中为第几个，所以需要index定位特征的位置
    for key in secondDict.keys():
        if testVec[featIndex]==key:
            if type(secondDict[key]).__name__=='dict':
                classLabel=classify(secondDict[key],featLabels,testVec)
            else:
                classLabel=secondDict[key]
    return classLabel

Comments

⬆︎TOP