Python数据分析之决策树（基础篇）

已介绍了两种分类算法，可点击题目回顾：

---

本文参考于《机器学习实战》

决策树(decision tree)是一种基本的分类与回归方法。以下图为例，它就是一颗决策树。长方形代表判断模块(decision block)，椭圆形代表终止模块(terminating block)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。

我们可以把决策树看成一个if-then规则的集合。创建分支的伪代码函数createBranch()如下所示：

检测数据集中的每个子项是否属于同一分类：

        If so return 类标签；

                Else

                       寻找划分数据集的最好特征

                       划分数据集

                       创建分支节点

                               for 每个划分的子集

                                     调用函数createBranch并增加返回结果到分支节点中

                        return 分支节点

 决策树的一般流程 

---

• 收集数据：可以使用任何方法。

• 准备数据：收集完的数据需要进行整理，树构造算法只适用于标称型数据，因此数值型数据必须离散化。

• 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。

• 训练算法：构造树的数据结构。

• 测试算法：使用经验树计算错误率。

• 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

 信息增益 

---

划分数据集的大原则是：将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。集合信息的度量方式称为香农熵或者简称为熵。熵定义为信息的期望值。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为：

其中p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：

其中n是分类的数目。下面给出计算给定数据集的熵的代码：

from math import log
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) #返回数据集的行数
    labelCounts = {}   #保存每个标签(Label)出现次数的字典
    for featVec in dataSet: 
        currentLabel = featVec[-1]  #提取标签(Label)信息
        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

得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集。下面给出划分数据集的代码：

def splitDataSet(dataSet, axis, value):    #待划分的数据集、划分数据集的特征、特征的返回值
    retDataSet = []      #创建返回的数据集列表
    for featVec in dataSet:   #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]   #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])    #将符合条件的添加到返回的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet   

接下来我们将遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。下面是选择最好数据划分方式的代码：

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]
        uniqueVals = set(featList)  #创建set集合{},元素不可重复
        newEntropy = 0.0    #经验条件熵
        for value in uniqueVals:   #计算信息增益
            subDataSet = splitDataSet(dataSet, i, value)   #subDataSet划分后的子集
            prob = len(subDataSet) / float(len(dataSet))     #计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)  #根据公式计算经验条件熵
        infoGain = baseEntropy - newEntropy    #信息增益
        print("第%d个特征的增益为%.3f" % (i, infoGain)) #打印每个特征的信息增益
        if (infoGain > bestInfoGain):    #计算信息增益
            bestInfoGain = infoGain  #更新信息增益，找到最大的信息增益
            bestFeature = i   #记录信息增益最大的特征的索引值
    return bestFeature   

我们可以通过简单的数据集进行测试：

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

if __name__ == '__main__':
    dataSet, features = createDataSet()
    print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

结果：

 结语 

---

本文介绍了如何计算数据集的熵和如何选择最优特征作为分类特征。下一节我们将介绍如何将这些函数功能放在一起，构建决策树，以及如何修建和可视化。