决策树

决策树算法是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

我们使用决策树算法最重要的目的就是为了分类，那么要分成什么样子呢？下面就给我们展示出来了：

这就是我们在一堆原始数据中所要构成的决策树
就比如快要到你和你的女朋友的纪念日了，你在想到底送个什么样的礼物合适，那么加入现在有一颗决策树就可以特别轻松的解决你的问题了，当然这课树上得有不同节日的选项，以及你女朋友所喜欢东西的类型，是喜欢潮流？还是复古。那么你就可以根据你女朋友的特点在决策树中找到最适合你女朋友的礼物。
废话不多说，那么我们怎么要构建一棵决策树呢？
首先我们首先给一些海洋生物的特征的数据

	不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	是	是	是
2	是	是	是
3	是	否	否
4	否	是	否
5	否	是	否

那么我们想根据上面的这5条数据就画出我们上面所展示出的决策树的样子，那么我们就必须要知道，在这些数据里只有三个特征：不浮出水面是否可以生存，是否有脚蹼以及是否属于鱼类。那么我们想画成树首先的一个问题就是 第一个根节点放那个特征？接下来再放那个？

 
 
那么我们要得出这些结论，我们这里就要引入*信息增益*

信息熵：

熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。
在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

那么信息熵是怎么计算呢？

就拿上面的数据来说，我们把是和否用1和0表示

	不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	1	1	是
2	1	1	是
3	1	0	否
4	0	1	否
5	0	1	否

我们根据公式计算：
在属于鱼类中是占2/5,否占3/5，所以计算得到信息熵为0.97
那么我们使用python代码实现一下这个操作，创建tree.py：
首先我们将表格的数据写入：

def creatDataSet():
    dataset = [
        [1, 1, 'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no'],
    ]
    labels = ['no surfacing', 'flippers']
    return dataset, labels

再计算信息熵：这里要做对数运算，所以我们需要导入：from math import log

def calcShannonEnt(dataset):
    numEntries = len(dataset)  # 获得实列数,后来用作充当分母
    labelCount = {}
    for featVec in dataset:
        currentLabels = featVec[-1]  # 获得dataset中的labels，这里是yes和no
      
        if currentLabels not in labelCount: #如果label不在我们定义的labelCount中
            labelCount[currentLabels] = 0  #我们在label中写入这个标签
        labelCount[currentLabels] += 1
        # 上面是要从dataset中获取到labels并存放在字典中并且计算出现的个数
        # 这里统计后的应该是 {yes:2,no:3}
        # 下面开始计算信息熵
    shannonEnt = 0.0
    for key in labelCount:
        prob = float(labelCount[key])/numEntries
        shannonEnt -= prob*log(prob, 2)
    return shannonEnt

在命令行中输入下面代码，计算信息熵

那么我们总的信息熵算出来，那么具体还要怎么分类呢？这里我们要再引入信息增益的概念：

信息增益：

信息增益是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。
在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

我们在这里使用的是ID3算法：

ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
ID3是Ross Quinlan发明的一种决策树算法。
那么我就可以通过信息增益的不同，决定不同特征出现的先后顺序，我们就可以计算其他特征的：

除了ID3算法外我们还有其他算法，我们在下节说一说这些算法区别

	不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	1	1	是
2	1	1	是
3	1	0	否
4	0	1	否
5	0	1	否

H(X1)计算：对于不浮出水面是否可以生存 为1的数据有3个，对应是否属于鱼类有两个是占2/3，一个否占1/3.   
H(X2)计算：对于不浮出水面是否可以生存 为0的数据有两个，对应是否属于鱼类都为否
H(X|T)计算：对于不浮出水面是否可以生存 ，H(X1)占3/5，H(X2)占2/5

计算不浮出水面是否可以生存 的信息增益为：
接下来用代码实现一下，详细使用情况都在代码后有备注：

def splitDataSet(dataset, axis, value):
    retDataSet = []
    for featVec in dataset:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]  # 这里最开始有一个疑问就是为什么当axis=0，value=0我匹配的是第一列的的所有出现的0，但是却要保存这之前或者之后的数据而不保存他自己
            reduceFeatVec.extend(featVec[axis + 1:])  # 是因为这里我们只想保存的是labels，在后面我们只想要labels出现的个数，[0,no]和[1,no]意思都是会给no出现的次数+1
            retDataSet.append(reduceFeatVec)
    return retDataSet

# 获得信息增益的最大分类
def chooseBestFeatureToSplit(dataset):
    numFeatures = len(dataset[0]) - 1  # 获取属性的个数(不包括标签)
    baseEntropy = calcShannonEnt(dataset)
    bestinfoGain = 0.0  # 记录最大的信息增益
    bestFeature = -1  # 获取最大信息增益的属性的下标
    for i in range(numFeatures):
        # 分别列出每个属性的所有值，比如不浮出水面是否可以生存是[1,1,1,0,0]
        fearList = [example[i] for example in dataset]
        uniqueVals = set(fearList)  # 将不同的属性值分类,这里将[1,1,1,0,0]分为[1,0] set函数会删去重复的
        newentropy = 0.0  # 定义每个分开的信息熵
        for value in uniqueVals:  # 因为有外面的大的for循环i固定这，所以就可以把整整一个属性的一列都可以读取到
            sunDataSet = splitDataSet(dataset, i, value)  # i固定是一个数，value的不同取遍一列中的0和1
            prob = len(sunDataSet)/float(len(dataset))
            newentropy += prob*calcShannonEnt(sunDataSet)
        infogain = baseEntropy - newentropy
       
        if infogain > bestinfoGain:
            bestinfoGain = infogain
            bestFeature = i
    return bestFeature

经过上面的代码我们已经找到了信息增益最大的一个值了，那么我们就可以构建我们想象的那棵树了，我们需要不断的寻找最大的信息增益直至全部遍历完。

def majorityCnt(clsaaList):
    classCount = {}
    for vote in clsaaList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        return sortedClassCount[0][0]

classify0部分的投票表决代码非常类似，该函数使用分类名称的列表，
然后创建键值为classList中唯一值的数据字典，字典对象存储了classList中每个类标签出
现的频率，最后利用operator操作键值排序字典，并返回出现次数最多的分类名称。

下面我们构建树：

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)  # 得到最大信息熵的下标
    bestLabels = labels[bestFeat]  # 获取最大熵的label
    myTree = {bestLabels:{}}  # 构建决策树
    del(labels[bestFeat])  # 将已经放在书里面的值删去
    featValues = [example[bestFeat] for example in dataset]  # 获取最优分类的所有值
    uniqueVals = set(featValues)  # 将所有值分类
    for value in uniqueVals:  # 对最优维度的每个值进行操作，每一个值都对应着一个分支，因为上面使用了get方法
        subLabels = labels[:]  # 获得除了最优标签当前的子标签
        myTree[bestLabels][value] = createTree(splitDataSet(dataset, bestFeat, value), subLabels)  # 递归调用不断在树里面添加
    # 递归对每个分支建立子树，递归调用划分函数
    return myTree

之后我们在命令行输入：
就可以得到“树”，但是我们所得到的这个树并不像我们学习了解的树的那个样子，如果我们想要构建成树的图形我们就需要借助matplotlib来实现.