机器学习笔记(2)-决策树

决策数简介

熵（entropy）指的是体系的混乱的程度，是表示随机变量X不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：

则随机变量X的熵定义为：

性质：熵只依赖X的分布，与X的取值无关；熵的范围0≤H(X)≤logn，n为X取值数目；概率分布越均匀，熵取值越大，随机变量不确定性越大。上面公式中的对数以2为底或以e为底，这时熵的单位分别称为比特（bit）或纳特（nat）。
条件熵条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。用于特征选择时，该值越小即不确定性越小，其对应的特征越好。
H(Y|X=xi)为X给定条件下X=xi时，Y的条件概率分布的熵。 H(Y|X)实质为H(Y|X=xi)的数学期望。条件熵计算公式：

信息熵（香农熵）是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。P(x)是变量出现的概率；信息熵越大，变量中包含的信息量就越大。同时，也说明了变量的不确定性也越大。

信息增益是指在划分数据集前后信息发生的变化。

信息增益比信息增益的局限性是偏向于选择取值较多的特征，信息增益可以校正这个问题。 特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即：

决策树生成

构造决策树

检测数据集中的所有数据的分类标签是否相同:
    If so return 类标签
    Else:
        寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
        划分数据集
        创建分支节点
            for 每个划分的子集
                调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
        return 分支节点

ID3算法实现

ID3算法使用信息增益作为特征选择的度量。
结束条件：D中所有实例都属于同一类；信息增益值小于特定的阈值；没有其他特征可以选择了。
构建树的过程中对于选中的某一个特征，其有多少种取值，就分出多少条边。
下层的节点在进行特征选择的时候不会再用到上层用过的特征。
数据处理

def createDataSet():
    dataSet = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]
    labels = ['no surfacing', 'flippers']    # labels  露出水面   脚蹼
    return dataSet, labels

数据集香农熵

def calcShannonEnt(dataSet):
    '''calcShannonEnt(calculate Shannon entropy 计算给定数据集的香农熵)
    :param dataSet: dataSet 数据集
    :return: 返回每一组feature下的某个分类下，香农熵的信息期望
    '''
    numEntries = len(dataSet)   # 求list的长度，表示计算参与训练的数据量
    labelCounts = {}     # 计算分类标签label出现的次数
    for featVec in dataSet:
        currentLabel = featVec[-1]    # 将当前实例的标签存储，即每一行数据的最后一个数据代表的是标签
        if currentLabel not in labelCounts.keys():   # 为所有可能的分类创建字典，如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0    # 对于label标签的占比，求出label标签的香农熵
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries   # 使用所有类标签的发生频率计算类别出现的概率。
        shannonEnt -= prob * log(prob, 2)  # 计算香农熵，以 2 为底求对数
    return shannonEnt

给定特征划分数据集
splitDataSet(dataSet, 0, 1) –> [[1, ‘yes’],[1, ‘yes’],[0, ‘no’ ]]

def splitDataSet(dataSet, index, value):
    '''通过遍历dataSet数据集，求出index对应的colnum列的值为value的行
    :param dataSet: 待划分的数据集
    :param index: 划分数据集的特征
    :param value: 需要返回的特征的值
    :return: retDataSet:index列为value的数据集【该数据集需要排除index列】
    '''
    retDataSet = []
    for featVec in dataSet:
        if featVec[index] == value:
            reducedFeatVec = featVec[:index]
            reducedFeatVec.extend(featVec[index+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
>>> result = []
>>> result.extend([1,2,3])  # [1, 2, 3]
>>> result.append([4,5,6])  # [1, 2, 3, [4, 5, 6]]
>>> result.extend([7,8,9])  # [1, 2, 3, [4, 5, 6], 7, 8, 9]

选择最好的特征集划分方式

def chooseBestFeatureToSplit(dataSet):
    '''选择最好的特征
    :param dataSet: 数据集
    :return: bestFeature:最优的特征列
    '''
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)   # label的信息熵
    bestInfoGain, bestFeature = 0.0, -1   # 最优的信息增益值, 和最优的Featurn编号
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)  # 获取剔重后的集合，使用set对list数据进行去重
        newEntropy = 0.0  # 创建一个临时的信息熵
        for value in uniqueVals:  # 遍历某一列的value集合，计算该列的信息熵 
            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                   

创建树

def majorityCnt(classList):
    '''选择出现次数最多的一个结果
    :param classList: label列的集合
    :return: bestFeature:最优的特征列
    '''
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    # 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果
    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:  # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)  # 选择最优的列，得到最优列对应的label含义
    bestFeatLabel = labels[bestFeat]  # 获取label的名称
    myTree = {bestFeatLabel: {}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]   # 求出剩余的标签label
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)  # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
    return myTree 

C4.5算法

C4.5 对ID3的改进，除了特征选择度量以外，另外两点是可以处理连续值型属性以及处理缺失值。
a,处理连续值型属性

b,处理缺失值