机器学习笔记(二)之决策树

机器学习之决策树

基本概念

决策树算法是机器学习中一个非常经典的算法，既能够解决分类问题，也能够解决回归问题。
一般的，一颗决策树包含一个根节点、若干个内部结点和若干个叶子节点；叶子结点对应于决策结果，其他的结点则对应一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子节点中。根节点包含样本全集，从根结点到每一个叶子节点表示的是一个判定结果。决策树学习的目的是为了产生一颗泛化能力强的得决策树。

决策树案例

图1

图 1 是一棵结构简单的决策树，用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性：是否拥有房产，是否结婚，平均月收入。每一个内部节点都表示一个属性条件判断，叶子节点表示贷款用户是否具有偿还能力。例如：用户甲没有房产，没有结婚，月收入 5K。通过决策树的根节点判断，用户甲符合右边分支 (拥有房产为“否”)；再判断是否结婚，用户甲符合左边分支 (是否结婚为否)；然后判断月收入是否大于 4k，用户甲符合左边分支 (月收入大于 4K)，该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

基本算法流程

一般流程
1. 收集数据:可以使用任何方法。
2. 准备数据:树构造算法只适用于标称型数据，因此数据类型鼻血离散化。
3. 分许数据:可以使用任何方法，属构造完成之后，我们应该检查图形是否符合预期
4. 训练数据:构造输的数据结构。
5. 测试数据:利用经验树计算错误率。
6. 使用算法:此步骤适用于任何监督学习算法，而使用决策树能够更好的理解数据的内在含义。

决策树的优点与缺点

优点：计算复杂度不高，输出结果易于理解，对于中间值缺失不敏感
缺点：可能产生过度匹配的问题
适用数据类型：数值型和标称型

注:
标称型数据：标称型目标变量的结果只在有限目标集中取值，如真与假(标称型目标变量主要用于分类)

划分选择

决策树学习的关键在于如何选择最优的划分属性。一般而言，我们希望决策树的分支包含的样本尽可能的属于同一类别。即结点的纯度越来越高

信息增益

信息熵是度量样本集合的纯度的一种最常用的指标。熵指的是不确定性的度量而不是确定性的度量。

信息熵的计算公式

假定当前样本集合D中第K类样本所占的比率为pk，则D的信息熵定义为

Ent(D)=−∑k=1γpklog2pk

info(D)的值越小，数据的纯度越高。

信息增益熵计算

假定离散属性a有V个可能的取值(a1,a2,a3…av),若使用a对样本D进行划分，则会产生V个分支。其中第v个分支包含了样本D中所有在a属性取值为av的所有样本，记为Dv。根据上面的公式可以计算出Dv的信息熵，给分支结点赋予权值|Dv/D|，所以可以得出样本数越多的分支结点影响越大。因此用a属性对于数据集D进行划分的信息增益为

Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)

信息增益越大，则意味着使用属性a提升的纯度越大。

下面是用代码实现一个简单的决策树思路

计算数据集的香农熵

def calcShannonEnt(dataSet):#计算香农熵
numEntris = len(dataSet)#求出数据集的长度
labelCounts = {}# dict变量，保存键值对
for featVec in dataSet:
    #print(featVec)
    currentLabel = featVec[-1]#表示读取featVec最后一项
    if currentLabel not in labelCounts.keys():#判断currentlabel是否在labelCount的键里面
        labelCounts[currentLabel] = 0#如果不在，统计为0
    labelCounts[currentLabel]+=1#在的情况下就+1
shannoEnt=0.0
for key in labelCounts:
    prob = float(labelCounts[key])/numEntris#prob表示该公式出现的概率
    shannoEnt -= prob*log(prob,2)#对应上面的求熵公式
return shannoEnt

划分数据集

def splitDataSet(dataSet,axis,value):#
    reDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:#如果第axia个元素等于value，则将value剔除重新组成数据集
            reduceFeatVec = featVec[:axis]#将featVec从0开始取出axis个值，取括号
            reduceFeatVec.extend(featVec[axis+1:])#从axis+1开始，一直取到最后一个值
            reDataSet.append(reduceFeatVec)#append和extend的区别
    return reDataSet

输入的三个参数分别是：带划分的数据集，划分数据集的特征，需要返回的特征值。
找到在特征项的值等于value的几项数据，然后将其加入到reDataSet,相当于在原始数据项上面删除了特征项，然后将其他特征值保存到新的数据集reDataSet中
需要注意一下append和extend的用法

选择最好的数据集划分方式

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]#将每一个数据集的第i位取出来
    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

计算属性的信息增益，从中选择最大的保存下特征

统计出现次数最多的标签

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)
    print(sortedClassCount)
return sortedClassCount[0][0]

然后是利用递归创建决策树

def createTree(dataSet,labels):
label_copy=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 = label_copy[bestFeat]
myTree = {bestFeatLabel: {}}
del (label_copy[bestFeat])#删除掉出现次数最多的类别的标签
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
    subLabels = label_copy[:]#获取其他的标签，继续进行分类,进行深拷贝
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree

利用决策树预测隐形眼镜类型
提供一个lenses.txt文件，将里面数据图取出来，然后对应生成决策树

下图是利用递归生成的决策树效果图

源代码