机器学习决策树算法学习笔记

基本概念
决策树是分类算法。
数据类型：数值型和标称型。因为构造算法只适用于标称型，所以数值型数据必须离散化。
工作原理
利用香浓熵找到信息增益最大的特征，按照信息增益最大的特征划分数据，如此反复，让无序的数据变的更加有序。使用ID3算法构建树结构。当传入一个新数据时，按照数据找到对应树节点，直到最后没有叶子节点时，完成分类。
样例

不浮出水面是否可以生存？ 是否有脚蹼？ 是否是鱼类？
通过“不浮出水面是否可以生存”和“是否有脚蹼”这两个特征来判断是否是鱼类。构建一个简单决策树，如果得到一个新的生物，可以用此来判断是否是鱼类。
样例代码
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的信息定义为：

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

为了计算熵，需要计算所有类别所有可能值包含的信息期望值总和，公式为：
其中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 retDataSetdef 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
数据集需要满足一定的要求：
    数据必须是一种有列表元素组成的列表。（二维数组）
    所有列表元素必须有相同长度。
    最后一列必须是当前实例的标签。

递归构建决策树

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

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)
优点
    计算复杂度不高
    输出结果易于理解
    对中间值缺失不敏感
    可以处理不相关特侦
缺点
    可能产生过度匹配问题