基本概念

决策树是分类算法。

数据类型：数值型和标称型。因为构造算法只适用于标称型，所以数值型数据必须离散化。

工作原理

利用香浓熵找到信息增益最大的特征，按照信息增益最大的特征划分数据，如此反复，让无序的数据变的更加有序。使用ID3算法构建树结构。当传入一个新数据时，按照数据找到对应树节点，直到最后没有叶子节点时，完成分类。

样例

718b33fb-e547-442e-bb2d-bfa463b001ef

不浮出水面是否可以生存？
是否有脚蹼？
是否是鱼类？

通过“不浮出水面是否可以生存”和“是否有脚蹼”这两个特征来判断是否是鱼类。构建一个简单决策树，如果得到一个新的生物，可以用此来判断是否是鱼类。

样例代码

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

香浓熵公式

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

a5c1d771-bce5-4f92-9281-1ec3414a53bc

其中P(Xi)是选择该分类的概率

为了计算熵，需要计算所有类别所有可能值包含的信息期望值总和，公式为：

9375466a-b7a4-4ca4-9afc-04ad5cbc46cc

其中n是分类的数目

香浓熵算法

def calcShannonEnt(dataSet):
    # 选择该分类的概率 就是每个类型/总个数
    # 总数，多少行数据
    numEntries = 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])/numEntries
        # 按照公式
        shannonEnt -= prob * log(prob,2) #log base 2
    return shannonEnt

按照香浓熵划分数据

除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确划分。
循环计算香浓熵和splitDataSet()，找到最好的特征划分方式。

def splitDataSet(dataSet, axis, value):
    # 这个算法返回axis下标之外的列
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
    
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]
        # 利用set去重
        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

数据集需要满足一定的要求：

• 数据必须是一种有列表元素组成的列表。（二维数组）
• 所有列表元素必须有相同长度。
• 最后一列必须是当前实例的标签。

递归构建决策树

b77a957d-ed7d-4a9f-a10a-d3ef70179564

多数表决算法

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决决定该叶子节点。

import operator
def majorityCnt(classList):
    # 排序取出种类最多的
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(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)
    # 根据下标取出标签
    bestFeatLabel = labels[bestFeat]
    # 构建树
    myTree = {bestFeatLabel:{}}
    # 删除取出过的标签，避免重复计算
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]

    # 利用set去重
    uniqueVals = set(featValues)


    for value in uniqueVals:
        # 复制所有的子标签，因为是引用类型，以避免改变原始标签数据
        subLabels = labels[:]
        # 递归的构建树
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree    

使用决策树分类

def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    # print 'featIndex %s' % (featIndex)
    key = testVec[featIndex]
    # print 'key %s' % (key)
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict): 
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

dataSet, labels = createDataSet()
mytree = createTree(dataSet, labels[:]) #因为内部会删除labels里的值所以用这样copy一份
print mytree
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
print classify(mytree, labels, [0,1])
no

决策树的存储

构造决策树是耗时的任务，即使处理很小的数据集。所以我们可以使用构造好的决策树。

def storeTree(inputTree,filename):
    import pickle
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()
    
def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

优点

• 计算复杂度不高
• 输出结果易于理解
• 对中间值缺失不敏感
• 可以处理不相关特侦

缺点

• 可能产生过度匹配问题