（三）决策树

决策树

决策树的特点

计算复杂度不高，输出结果易于理解，对于中间值的缺失不敏感
可能会出现过度匹配的问题

决策树的构造

在构造决策树时，我们遇到的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。

因此，为了找到决定性的特征，我们必须评估每一个特征，并且以量化的方式评估

信息增益

划分数据集的大原则就是：将无序的数据变得更加有序。

组织杂乱无章数据的一种办法就是使用信息度量信息。信息论是量化处理信息的分支科学。我们可以在划分数据前或者后使用信息论度量信息的变化情况。

在划分数据集之前之后发生的信息的变化称为信息增益，知道如何计算信息增益，我们就可以知道哪个特征是最具有决定性的。

集合信息的度量方式称为熵，对，就和我们高中所学的那个熵是一个字。这个名字来源于信息论之父克劳德-香农，又是一个熟悉的名字。

熵被定义为信息的期望值，根据我的理解对于每一个特征来说，每个特征存在多个分类，则我们有如下定义

其中p(xi)是每个特征中选择每个分类的概率。（不理解看后面的代码样例）

所以，对于每个特征，都有一个期望

通过比较这个期望，我们可以得到哪一个特征是最重要的。

# 计算给定数据集的香农熵
def calShannoEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt # 熵越高，表示混合的数据也越多

划分数据集

当我们学会了如何度量数据集的无序程度以后，分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以判断当前是否正确地划分了数据集。

我们将要对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

# 按照给定的特征axis，划分数据集
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVector in dataSet:
        if featVector[axis] == value:
            reducedFeatVec = featVector[:axis]
            reducedFeatVec.extend(featVector[axis + 1:])  # extend是把list中的每一个元素加入到集合中
            retDataSet.append(reducedFeatVec)  # append是把list本身加入到集合中
    return retDataSet

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

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 去掉标签那一列得到的长度
    baseEntropy = calShannoEnt(dataSet)
    bestInfoGain = 0.0;
    bestFeature = -1
    # 对每一列，也就是每一个特征进行操作
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]  # 具体作用是取出每一列，实现的话自己看吧
        uniqueVals = set(featList)  # 创建一个set对象，具有相同的值
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)  # 返回一个list
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calShannoEnt(subDataSet)
        infoGain = baseEntropy - newEntropy  # 信息增益是熵的减少，或者说是信息无序性的减少
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

对于上面的代码，有几点需要强调：

上面的函数实现选取特征，划分数据集，计算得出最好的划分数据集的特征。
需要满足的数据要求
- 数据必须是由list组成的list，也就是[[],[]...]类型
- 所有的list必须具有相同的长度
- 数据的最后一列是类别标签
- 而list中的数据类型没必要去限定，无论是String、数字类型，并没有影响
在baseEntropy = calShannoEnt(dataSet)中，我们计算了整个数据集的原始香农熵，这是最初的无序度量值，用于和后来划分完数据集计算的熵值进行比较。
第一个for循环，我们遍历了数据集中所有的特征，使用List Comprehension（可以百度一下，现在应用的比较多）创建了新的列表。将第i个特征的所有值写入到新的list中去（换句话说，就是取出来了第i列的）
然后我们使用了set，这一python内置的数据类型。从list中创建set是得到list中唯一元素值比较方便的办法。
遍历当前特征（列）的所有唯一属性，对于每一个唯一属性划分一次数据集，然后计算数据集的新熵值，并且对所有唯一特征值得到的熵计算期望。
信息增益是熵的减少或者是数据无序程度的减少。然后使用打擂台的方式，比较所有特征中的信息增益，返回最好特征划分的索引值

我们来运行一下程序，看一下结果

我们数据是按照如下数据来生成的

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

我们的程序告诉我们，第0列，其实是第1列，也就是不浮出水面是否可以生存这一属性对于划分具有最好的效果，这一结果也符合我们的认知。

看到这里，可能会对熵有更深刻的认识了，数据的种类越多，也就是信息的无序程度越高，熵越大，我们试图努力找到熵最小的划分。

github地址

待添加

小结

学习了有关决策树的相关知识
学会了如何在markdown中添加数学公式，添加图片、写表格