机器学习笔记--常见算法(2)--决策树算法介绍及代码实现

教程链接

笔记目录：

• • 1.决策树简介(Decision Tree)
  • 2.决策树构建
    • 2.1 特征选择
    • 2.2 决策树的生成和修剪
  • 3.决策树优缺点

1.决策树简介(Decision Tree)

决策树的结构是树，关键在于如何构建树，给出一个原始数据集，它的属性特征可能有很多，我们需决定特征属性在树的哪个位置(上面or下面)，这里可以根据信息增益、信息增益比、Gini Index等确定出最好的属性，放在树的根节点，依次往下递归构建决策树。（比如，第一次划分，找出最好的属性值，第一次划分之后，数据集被向下传递到树的分支的下一结点。在这个结点上，再次划分数据。）

2.决策树构建

从算法方面看，决策树的构建是我们的核心内容
构建决策树的3个步骤：
特征选择
决策树的生成
决策树的修剪

2.1 特征选择

特征选择就是决定用哪个特征来划分特征空间。
特征选择在于选取对训练数据具有分类能力的特征。
Measures that can be used to capture the purity of split：Information Gain, Gain Ratio and Gini Index are the most common methods of attribute selection
本文中选取信息增益作为特征选择的标准。

信息增益：在划分数据集之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

符号说明：
D:训练数据集D，|D|表示其样本容量，及样本个数
Di: 设特征A有n个不同的取值{a1,a2,…,an}，根据特征A的取值将D划分为n个子集{D1,D2，…,Dn}，|Di|为Di的样本个数。
Ck: 设有K个类Ck, = 1,2,3,…,K,|Ck|为属于类Ck的样本个数。
Dik:记子集Di中属于Ck类的样本的集合为Dik，即Dik = Di ∩ Ck，|Dik|为Dik的样本个数。

2.1.1 香农熵(entropy)

集合信息的度量方式称为香农熵或者简称为熵(entropy)，熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。
如果待分类的事物可能划分在多个分类之中，则符号xi(第i类)的信息定义为：

其中，p(xi)是选择该分类的概率。上述式中的对数以2为底，也可以e为底(自然对数)。
通过上式，我们可以得到所有类别的信息。为了计算熵，我们需计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：

其中，n是分类的数目。熵越大，随机变量的不确定性就越大。

2.1.2 经验熵(empirical entropy)

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。换言之，这个概率是我们根据数据数出来的。
比如有10个数据，一共有两个类别A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。经验熵公式

我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck, = 1,2,3,…,K,|Ck|为属于类Ck的样本个数。
以贷款为例，如下图

公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

2.1.3 条件熵(conditional entropy)

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

2.1.4 条件经验熵(empirical conditional entropy)

条件经验熵(empirical conditional entropy)：当条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的条件熵成为条件经验熵(empirical conditional entropy)

条件经验熵公式：

其中，
D:训练数据集D，|D|表示其样本容量，及样本个数，以贷款为例，|D|=15
Di: 设特征A有n个不同的取值{a1,a2,…,an}，根据特征A的取值将D划分为n个子集{D1,D2，…,Dn}，|Di|为Di的样本个数。以贷款为例，特征A的D1=5，特征A的D2=5，特征A的D3=5
Ck: 设有K个类Ck, = 1,2,3,…,K,|Ck|为属于类Ck的样本个数。以贷款为例，k=2，共有两类(贷款、不贷款)，|C1| = 9（贷款）, |C2| = 6（不贷款）
Dik:记子集Di中属于Ck类的样本的集合为Dik，即Dik = Di ∩ Ck，|Dik|为Dik的样本个数。

2.1.5 信息增益(information gain)

信息增益是相对于特征而言的，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

一般地，熵H(D)与条件熵H(D|A)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

以贷款申请样本数据表为例进行说明。看下年龄这一列的数据，也就是特征A1，一共有三个类别，分别是：青年、中年和老年。我们只看年龄是青年的数据，年龄是青年的数据一共有5个，所以年龄是青年的数据在训练数据集出现的概率是十五分之五，也就是三分之一。同理，年龄是中年和老年的数据在训练数据集出现的概率也都是三分之一。现在我们只看年龄是青年的数据的最终得到贷款的概率为五分之二，因为在五个数据中，只有两个数据显示拿到了最终的贷款，同理，年龄是中年和老年的数据最终得到贷款的概率分别为五分之三、五分之四。所以计算年龄的信息增益，过程如下：

同理，计算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)。分别为：

2.1.6 编写代码计算信息增益

#!/usr/bin/env python3 
# -*- coding: utf-8 -*-
from math import log

"""
函数说明:创建测试数据集

Parameters:
    无
Returns:
    dataSet - 数据集
    labels - 分类属性
"""
def createDataSets():
    dataSet = [[0, 0, 0, 0, 'no'],         #数据集
            [0, 0, 0, 1, 'no'],
            [0, 1, 0, 1, 'yes'],
            [0, 1, 1, 0, 'yes'],
            [0, 0, 0, 0, 'no'],
            [1, 0, 0, 0, 'no'],
            [1, 0, 0, 1, 'no'],
            [1, 1, 1, 1, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [2, 0, 1, 2, 'yes'],
            [2, 0, 1, 1, 'yes'],
            [2, 1, 0, 1, 'yes'],
            [2, 1, 0, 2, 'yes'],
            [2, 0, 0, 0, 'no']]
    labels = ['不放贷', '放贷']
    return dataSet, labels

"""
函数说明:计算给定数据集的经验熵(香农熵)

Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 经验熵(香农熵)
"""
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)                           #返回数据集的行数
    lableCounts = {}                                    #保存每个标签(Label)出现次数的字典
    for featVec in dataSet:                             #对每组特征向量进行统计
        currentLabel = featVec[-1]                      #提取标签(Label)信息
        if currentLabel not in lableCounts.keys():      #如果标签(Label)没有放入统计次数的字典,添加进去
            lableCounts[currentLabel] = 0
        lableCounts[currentLabel] += 1                  #Label计数
    shannonEnt = 0.0                                    #经验熵(香农熵)
    for key in lableCounts:
        porb = float(lableCounts[key]) / numEntries     #选择该标签(Label)的概率
        shannonEnt -= porb * log(porb, 2)
    return shannonEnt

"""
函数说明:按照给定特征划分数据集

Parameters:
    dataSet - 待划分的数据集
    axis - 划分数据集的特征
    value - 需要返回的特征的值
Returns:
    无
"""
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   


"""
函数说明:计算给定数据集的信息增益，并给出最优特征

Parameters:
    dataSet - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值
"""

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1     #获取特征数量,本例中有4个
    baseEntropy = calcShannonEnt(dataSet) #计算数据集的香农熵
    bestInfoGain = 0.0                    #信息增益
    bestFeature = -1                      #最优特征的索引值
    for i in range(numFeatures):          #遍历所有特征
        # 获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        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 bestInfoGain, bestFeature                            #返回信息增益的最大值以及其索引值


if __name__ == '__main__':
    dataSet, features = createDataSets()
    print(dataSet)
    print('shannonEnt =', calcShannonEnt(dataSet))
    bestInfoGain, bestFeature = chooseBestFeatureToSplit(dataSet) 
    print('最大信息增益值 =', bestInfoGain)
    print('最优特征索引值 = ', bestFeature)

2.2 决策树的生成和修剪

3.决策树优缺点