机器学习2——决策树

摘要：决策树是一种十分常用的分类方法，作为一个预测模型，决策树表示对象属性与对象值之间的一种映射关系。判断类型测试评价以上决策树的的实现方式，没有剪枝的步骤，容易发生过度拟合，导致决策树过高。

决策树(Decision Tree）是一种十分常用的分类方法，作为一个预测模型，决策树表示对象属性与对象值之间的一种映射关系。

公式表示为：其中S表示样本集，c表示样本集合中类别个数，Pi表示第i个类别的概率。

信息熵的意思就是一个变量i（就是这里的类别）可能的变化越多（只和值的种类多少以及发生概率有关），它携带的信息量就越大（因为是相加累计），即类别变量i的信息熵越大。

二分类问题中，当X的概率P(X)为0.5时，表示变量的不确定性最大，此时的熵达到最大值1。

信息熵反映系统的确定程度：信息熵越低，系统越确定；信息熵越高，系统越不确定

公式表示为：其中ti表示属性T的取值。条件熵的直观理解：假设多带带计算明天下雨的信息熵：H(Y)=2，而在已知今天阴天情况下计算明天下雨的条件熵：H(Y|X)=0.5（熵变小，确定性变大，明天下雨的概率变大，信息量减少），这样相减后为1.5，在获得阴天这个信息后，下雨信息不确定性减少了1.5，信息增益很大，所以今天是否时阴天这个特征信息X对明天下雨这个随机变量Y的来说是很重要的。

公式表示为：
信息增益考察某个特征对整个系统的贡献。

通过“不浮出水面能否生存 no surfacing” 和 “是否有脚蹼 flippers”来判断5种海洋生物是否属于鱼类。

from math import log

def calcInforEnt(dataSet):
    num = len(dataSet)
    labelCount = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCount.keys():
            labelCount[currentLabel] = 0
        labelCount[currentLabel] += 1  # 统计类别数目，labelCount = {"yes": 2, "no": 3} 
    inforEnt = 0.0
    for key in labelCount:
        prob = float(labelCount[key]) / num
        inforEnt -= prob * log(prob, 2)
    return inforEnt

测试：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
calcInforEnt(dataSet)  # 0.9709505944546686

按照给定特征值划分数据集

def splitDataSet(dateSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

测试：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
splitDataSet(dataSet, 0, 1)  # [[1, "yes"], [1, "yes"], [0, "no"]]
splitDataSet(dataSet, 0, 0)  # [[1, "no"], [1, "no"]]

遍历整个数据集，循环计算信息熵和splitDataSet()函数，找到最好的特征划分方式。

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 数据集的最后一列表示类标签
    baseEntropy = calcInforEnt(dataSet)
    bestInforGain = 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 * calcInforEnt(subDataSet)
        inforGain = bestInforGain - newEntropy
        if inforGain > bestInforGain:
            bestInforGain = inforGain
            bestFeature = i
    return bestFeature

测试：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
chooseBestFeatureToSplit(dataSet)  # 0

工作原理：得到原始数据集，基于最佳的属性划分数据集，由于属性存在两个或以上属性值，因此存在两个或以上的数据分支。第一次划分结束后，数据向下传递到树分支中，每个分支按照条件继续分叉。
递归结束条件：程序遍历完所有划分数据集的属性，或者每一个分支下的实例属于相同分类

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.items(), key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]

# 创建树
def ctrateTree(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]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = ctrateTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree 

测试：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
labels = ["no surfacing", "flippers"]
ctrateTree(dataSet, labels)  # {"no surfacing": {0: "no", 1: {"flippers"：{0: "no", 1: "yes"}}}}

比较测试数据与决策树上的值，递归执行该过程直到进入叶子节点，最后将测试数据定义为叶子节点所属的类型。

def classify(inputTree, featLabels, testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    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

测试：

inputTree = {"no surfacing": {0: "no", 1: {"flippers"：{0: "no", 1: "yes"}}}}
featLabels = ["no surfacing", "flippers"]
classify(inputTree, featLabels, [1, 0])  # "no"
classify(inputTree, featLabels, [1, 1])  # "yes"

以上决策树的ID3的实现方式，没有剪枝的步骤，容易发生过度拟合，导致决策树过高。C4.5决策树的改进策略：

用信息增益率来选择属性，克服了用信息增益选择属性偏向选择多值属性的不足

在构造树的过程中进行剪枝，参考剪枝算法

对连续属性进行离散化

能够对不完整的数据进行处理

《机器学习实战》

信息熵与信息增益