分类决策树

什么是分类决策树？分类决策树能用来干什么？举个例子就明白了。
一位母亲要给她女儿介绍对象，于是有了如下对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。

这里写图片描述

现在对机器来说，假设给了它一系列的“前提”（特征），让它对这件事作出判断，这就是分类决策树。说白了，假设有了树，对机器来说，就是不断的if--else--，如果年龄小于30、长的挺帅、收入挺高，机器就知道了，我要去见他。

显然，决策树也是监督学习的一种，先需要历史数据去构建决策树，再可根据决策树去对一些未知数据惊醒分类。
那么，怎么去构建决策树？
再举个例子，表5.1是贷款申请样本数据表，根据年龄、有工作、有房子、信贷情况4个特征来决定是否给你贷款。表格中的数据都是已知的确定的，也就是历史数据，年轻没工作没房子信贷情况一般的人，就一定不给贷款，而青年有工作没房子信贷情况好的人，就一定给贷款…这15种情况是已知的。
我们可以按照上面的情况同样构建一颗树，最开始的节点“年龄”，后有三个分支，“青年”“中年”“老年”，形成三个节点，每个节点后又可以有两个分支，“有工作”“无工作”，总共形成六个节点，“有房子”“无房子”，“信贷好”“信贷一般”…以此类推，最后总共有24种情况，每种情况对应着一种类别“给贷款”“不给贷款”，很显然，这是一种很差的分类方式，完全没有结合数据自身的信息，只是尽数遍历。
怎样去构建一个好的决策树呢？
关键在于选择分类节点的先后顺序。比如有了表5.1的数据，上面我们是选择了“年龄”作为第一个节点，但这是否更有效的？如果我选择“有房子”作为第一个节点，直观上应该更好（因为有房子都给贷款，一下把很多情况都给覆盖了）。
于是我们要根据把类分的更开的特征作为第一个节点，依次往下。也就是说，在根据节点分类之前，总的数据的信息熵一定（在例子中为15条数据），称为经验熵，根据“有房子”这个节点分类后，15条数据变成两类（6条有房子，9条无房子），这两类的熵加起来，称为经验条件熵（在“有无房子”的条件下是否给你贷款），熵代表信息的不确定程度，熵越大，越混乱，信息越不确定。经验熵-经验条件熵的差值称为信息增益，我们要找的“把数据分的更开”的节点，也就是信息增益最大的节点。也就是有了这个节点分类后，这些数据的不确定性最小。
就拿这个例子来讲，什么条件都没有的情况下，15条数据，给不给贷款的不确定性就很大呀，有了第一个节点“有无房子”，分好类之后，显然，假如你有房子，就确定了一定会给你贷款，假如你没有房子，给你贷款也不确定，但总的来说，这两种情况的不确定加起来，还是要远小于原始的15条数据的不确定性。
如果选择“年龄”作为第一个节点分类，假如你是青年，给你贷款不确定；假如你是中年，给你贷款不确定；假如你是老年，给你贷款不确定。有了“年龄”的条件后的不确定还是要大于“有房子”的条件不确定性。于是我们选择“有房子”作为第一个节点。
**这就是ID3算法的核心：选择信息增益最大的特征作为优先节点。
算法步骤：

1. 找到信息增益最大的特征，以它为节点
2. 递归createTree
3. 类别完全相同或分类到了最后一个节点，结束递归**
   这里写图片描述
   代码如下：
   trees.py

'''
Created on 2017年7月29日

@author: fujianfei
'''
from math import log2
import operator

def calcShannonEnt(dataSet):
    '''
    .计算香农熵
    '''
    numEntries = len(dataSet)
    #提取数据中总共有多少类
    labelCounts = {}
    for featVec in dataSet:#遍历数据集
        currLabel = featVec[-1]#提取每一个样本的最后一列（即标签）
        #为所有可能分类创建数据字典
        if currLabel not in labelCounts.keys():
            labelCounts[currLabel] = 0
        labelCounts[currLabel] += 1
    shannonEnt = 0.0
    #计算香农熵，-Pi*logPi
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -=  prob * log2(prob)
    return shannonEnt

def splitDataSet(dataSet, axis, value):
    '''
    .按照给定特征划分数据集
    dataSet:数据集
    axis:按照哪维特征划分数据
    value:某个特征值
    '''
    reDataSet = []#定义重组后的数据集
    for featVec in dataSet:
        if featVec[axis] == value:#如果某行的数据的标签等于传入的value
            #则对数据进行重组，把axis去掉，留下其他特征
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            reDataSet.append(reduceFeatVec)
    #最后返回的重组后的数据集，reDataSet,特征为除axis维后的dataSet的所有特征，标签全为value
    return reDataSet

def chooseBestFeatureToSplit(dataSet):
    '''
    .在给定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)#Python语言原生的集合，将重复的特征合并，生成唯一的特征列表
        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.iteritems(), key=operator.itemgetter(1), reserve=True)
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    '''
    .创建决策树
    '''
    classList = [example[-1] for example in dataSet]#dataSet的最后一列，类别列
    #结束递归的条件:
    #1.类别完全相同
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    #2.分类到了最后一个节点，用多数投票决定类别
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#找到dataSet最好的特征，来分割数据
    bestFeatLabel = labels[bestFeat]#特征对应的标签
    mytree = {bestFeatLabel:{}}#定义树，用字典类型的结构就足以表示决策树全部的信息
    del(labels[bestFeat])#将用过的标签删除
    featList = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featList)
    for value in uniqueVals:
        subLabels = labels[:]
        mytree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return mytree

init.py

from DecisionTree import trees
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

myDat,labels = createDataSet()
mytree = trees.createTree(myDat, labels)
print(mytree)

运行结果如下，决策树是存放在dict类型里，这周有点事，也懒得准备很多数据了，下周会将画节点图和CART算法补上。

这里写图片描述