一起来《机器学习实战》决策树

    jwolf 

2324  0  0   2018-5-24 9:56

• 想了很久还是先从实际问题出发

是的，还是之前小甜（美女妹子）填写的那份报告，现在表达方式稍微变了一下，关于是否愿意对方当男朋友的，你在想自己能否得到小甜的青睐呢？

好了，敲黑板，我们来说重点-------> 大家来评评理，假设现在只知道我的人品是大于75的， 那么大家觉得小甜甜愿意当我女朋友吗？

我知道大家都觉得她愿意，嗯，谢谢大家，不过这很明显了，在人品值大于75个结果里，2/3是愿意的，而在人品值低于75的结果中，100%是不愿意的，说明小甜选男朋友的时候，比较看重人品啊！

倘若你当个媒人帮小甜找对象，相信你会先问对方的人品如何，而从决策树思想的角度，在小甜选男朋友这个事件上，选择人品这个特征的原因是：人品 这个特征的信息量就相对比较大，人品 这个特征的好坏对结果（小甜是否愿意）能造成比较大的影响，或者说，相对其他特征，较大地消除了结果的不确定性，理解这点对于决策树的思想非常关键。

• 熵

熵被定义为信息的期望值，通俗点的表达，就是预计的信息量的大小。 《机器学习实战》中是这样描述信息的：

如果待分类的事务可能划分在多个分类之中，则信息号xi的信息定义为：

表示方式1：

$l(xi) = -\log_2 p(xi)$

其中p(xi)是选择该分类的概率 为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的式子得到：

表示方式2：

$H = -\sum_{i=1}^{m}p(xi)\log_2 p(xi)$

对于这是否为“公式”，笔者水平有限，自身姑且没有证明上面式子的唯一性（都怪老板，天天让我赶进度，还没时间做这研究）但是从“结果导向”的角度，这方式描述信息的“不确定性”是符合“不确定性”的特征的。至于为什么，有兴趣的朋友可以到知乎凑凑热闹： 信息熵是什么

香农（信息学之父）从数学上证明满足上述性质的信息熵函数，具有唯一的如下的形式：

根据上面的式子，计算给定数据集的熵的代码如下：

from math import log

def calcShannonEnt(dataSet):
    labels = {}
    shannon = 0
    numEnt = len(dataSet)
    for data in dataSet:
        currentLabel = data[-1]
        if (currentLabel not in labels.keys()):
            labels[currentLabel] = 0
        labels[currentLabel] = labels[currentLabel] + 1
    for label in labels.keys():
        p = labels[label]/float(numEnt)
        shannon = shannon - p * log(p, 2)
    return shannon

• 利用熵判断如何划分数据

上面我们量化了在一个数据集中，各个特征值对结果造成的不确定性影响的大小。决策树需要我们构造出类似这样的一个选择判断：

怎么选择划分数据的特征依据呢？这里我们使用的方式是每次选取特征，使按照该特征分类的数据“纯度”为最高的，也就是我们刚刚量化的单位，能最大化减少数据的不确定性的那个特征。举上面的例子，我们只看人品的特征和结果：

4个人品值大于75的数据中，只有一个结果是“不愿意”，而人品值小于75的数据中，全都是“不愿意”；

再看看颜值的特征和结果：

两个颜值都大于75的数据中，一个“愿意”，一个“不愿意”；剩下5个颜值不大于75的数据中，有两个“愿意”，三个“不愿意”，数据就比较难归为一类，显得“纯度”不高

所以我们先选择“人品”这个作为分类的特征。好了，是时候写代码实现上面的思路了，核心代码如下，首先计算某个数据集的熵：

def calcShannonEnt(dataSet):
    labels = {}
    shannon = 0
    numEnt = len(dataSet)    
    for data in dataSet:
        currentLabel = data[-1]        
        if (currentLabel not in labels.keys()):
            labels[currentLabel] = 0
        labels[currentLabel] = labels[currentLabel] + 1
    for label in labels.keys():
        p = labels[label]/float(numEnt)
        shannon = shannon - p * log(p, 2)    
    return shannon

判断选取哪一个特征做分类：(思路是分别算出按照各个特征值分类后数据的熵，也就是不稳定性，选取信息量最大也就是能让余下数据纯度最高的作为分类特征)

def chooseBestFeatureToSplit(dataSet):
    num = len(dataSet[0]) - 1
    baseShannon = calcShannonEnt(dataSet)
    bestFeatureIndex = -1
    bestShannon = 0.0
    totalLen = len(dataSet)    
    for i in range(num): 
        featureList = [item[i] for item in dataSet]
        uniqueFeatures = set(featureList)
        shannon = 0.0
        for feature in uniqueFeatures: 
            subDataSet = splitDataSet(dataSet, i, feature)
            p = float(len(subDataSet))/totalLen
            shannon += p * calcShannonEnt(subDataSet)        print "by feature %d, shannon is %f" % (i, shannon)
        gainShannon = baseShannon - shannon        
        if gainShannon > bestShannon:
            bestShannon = gainShannon
            bestFeatureIndex = i    
    return bestFeatureIndex

• 能解决什么问题

对的，单身问题。口误口误，不好意思，是这样的，刚刚那个数据呢，我们就可以画出一个关于甜甜择偶的树状图：（怎么画源码见github源码） 

从图中可见颜值似乎没起什么作用，这是因为我们初始的数据单调地变成“是否大于75”丢了部分数据的特性（上一章是数值型的数据，本章对数据简单做了处理）。我们再用本章的思路处理上一章的另一个问题：

识别数字

00000000000001100000000000000000
00000000000000111000000000000000
00000000000111111100000000000000
00000000000111111110000000000000
00000000011111111110000000000000
00000000001111100111100000000000
00000000011111000111100000000000
00000001111110000011100000000000
00000000111111000001110000000000
00000000111111000001111100000000
00000001111111000001111100000000
00000000111110000000011110000000
00000000111100000000011110000000
00000000111100000000011110000000
00000001111100000000001110000000
00000001111110000000000111000000
00000001111100000000000111000000
00000001111100000000000111000000
00000000111110000000000011100000
00000000111110000000000011100000
00000000111110000000000111100000
00000000111110000000001111100000
00000000011111100000001111110000
00000000011111100000001111100000
00000000011100000000111111000000
00000000001110000000111111000000
00000000011111000111111110000000
00000000001111111111111100000000
00000000000111111111111100000000
00000000000111111111110000000000
00000000000011111111000000000000
00000000000000100000000000000000

还是上一章的问题，我们有多个这样的数据文件（见github源码中的digits)， 已经知道每个文件对应的数字，现在有一个相同规格的数据文件，怎么识别出里面的数字呢？ 上一章我们使用kNN的方式已经实现了达到98%准确率的识别，下面讲讲使用决策树的思路，没错，就是这么粗暴简单：

每个数据文件都是 1024个“0”或“1”组成，把每个位看成是影响结果的特征值,也就是有1024个特征：

def img2vector(filename):
    returnVect = []
    fr = open(filename)    
    for i in range(32):
        lineStr = fr.readline()
        line = [int(lineStr[j]) 
        for j in range(32)]
        returnVect.extend(line)    
    return returnVect
    
def getTraningMat():
    hwLabels = []
    trainingFileList = listdir('../chapter2/digits/trainingDigits/')           #load the training set
    m = len(trainingFileList)
    trainingMat = []    
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        item = img2vector('../chapter2/digits/trainingDigits/%s' % fileNameStr)
        item.append(classNumStr)
        trainingMat.append(item)    
    return trainingMat

获取数据转换完的数据：

dataSet = trees.getTraningMat()

建立决策树的时候需要有特征的名称，比如上面择偶例子中的颜值和人品，在这里，我们把1024位的位置作为这个特征的名称：

labels = [str(item) for item in range(1024)]

然后调用上面的之前的思路构造树结构：（这块需要参照github源码方便理解）

mytree = trees.createTree(dataSet,labels)    #  wait for 210 s

生成的树是这样的 生成的过程用了大概210s(我是最低配的air), 一大坨，有点看不清，数据比较多，大家理解思路就好，那做判断就比较简单了，先看“681”位是0还是1，要是0，就看362位是0还是1，如此类推，到叶子节点即可。

我还特意算了下准确率,这样算：

def predictByTree(myTree, data):
    isLeaf = False
    root = myTree    
    while not isLeaf:
        label = root.keys()[0]
        indi = data[int(label)]
        root = root[label][indi]
        isLeaf = isinstance(root, int)    
    return root
    
def testPredictByTree(tree):
    testFileList = listdir('../chapter2/digits/testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)    
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('../chapter2/digits/testDigits/%s' % fileNameStr)
        classifierResult = int(predictByTree(tree, vectorUnderTest))        
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)        if (classifierResult != classNumStr): errorCount += 1.0
    print "\nthe total number of errors is: %d" % errorCount    
    print "\n %f %% are right" % ((1-errorCount/float(mTest))*100)

判断的过程显然非常快，准确率达到：88.054968 %，没有knn高，但是好处是只是生成树的过程慢一点，把这个树结构保存下来，下次直接使用，判断的效率就非常快。

github源码

• ← Back