image.png

本文基于李航博士的【统计学习方法】第五章 决策树，包含ID3代码。

决策树(decisionTree)是一种基本的分类和回归方法。此文仅讨论用于分类方法的决策树。

决策树的学习通常分为3步：

• 特征选择
• 决策树生成
• 决策树修剪

决策树的学习的思想主要源于

• 1986年，Quinlan提出的ID3算法
• 1993年，Quinlan提出的C4.5算法
• 1984年，Beriman等人提出的CART算法

1.0 决策树的模型与学习

1.1 决策树模型

定义决策树：

结点和有向边.png

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
形如：

image.png

其中，圆表示内部结点，方框表示叶结点。

1.2 决策树与if-then规则

if-then规则，简单来说就是 ：

举例：对于一个苹果，外表是红色的是红苹果，外表是绿色的是青苹果。可以表示为：

if-then规则集合具有一个重要的性质：

这就是说每一个实例都被一条路径或规则覆盖，并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。

1.3 决策树学习

给定数据集：

其中，为输入实例（特征向量），含有个特征，为类标记，, 为样本容量。

目标：
根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。

2.0 特征选择

2.1 特征选择问题

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。

如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话，则称这个特征没有分类能力。

那么问题来了，怎么选择特征呢？

通常特征选择的准则是

下面通过例子来说明一下。

目标：
希望通过所给的训练集数据，学习一个贷款申请的决策树。当新的客户提出贷款申请的时候，根据申请人的特征利用决策树决定是否批准贷款申请。

可见这里共有4个特征可供选择。用特征选择的准则是。接下来介绍。

2.2 信息增益

：
熵是表示随机变量不确定性的度量。

这里我想说一个熵的比较形象的比喻。
我第一次学习到熵这个概念，是在高中的化学课熵。老师讲完熵的概念之后，全班进入无言的状态，大家都不理解。当时的化学老师也是我们班的班主任，他虽然平时不太靠谱，讲课还是挺有意思的。他说，不用把熵想的那么复杂，熵就是你房间的杂乱程度，那么可以想见，熵只会越来越大，即使你刚刚收拾房间，你的房间还是会越来越乱...
我 ...深以为然。

设是一个取有限个值的随机变量，其概率分布为

则随机变量的熵定义为

若，则定义。通常对数取以2为底，或是以为底，熵的单位分布为比特（bit）或是纳特（nat）。
由上式可知，熵只依赖的分布，而已的值无关，则的熵还可记作，即

则从定义可知

当随机变量只取2个值的时候，例如时，的分布为

熵为

熵随概率变化的曲线为

image.png

当或时，随机变量完全没有不确定性，当时，熵取值最大，随机变量不确定性最大。

设随机变量，其联合概率分布

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

信息增益
特征对训练集的信息增益

根据信息增益准则的特征选择方法：对训练集，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征。

前期定义各个量：

训练集 特征,有个可能值，	类有个可能值，
根据的取值，划分为个子集，, 为的样本数	为属于类的样本数
	为特征的取值为，又属于类的样本数

信息增益的算法
输入：训练集和特征；
输出：特征对训练集的信息增益

1. 计算训练集的熵
   
2. 计算特征对数据集的条件熵
   
3. 计算信息增益
   

回看刚才的例子，

解：

1. 计算训练集的熵
   
2. 计算特征各个对数据集的信息增益，年龄，有工作，有自己的房子，信贷情况这4个特征分别以表示。
   
   

3. 比较各个特征的信息增益，（有自己的房子）的信息增益最大，选择作为最优特征。

代码讲解

这一次我很无聊的想用一下.csv文件类型。

CSV是一种通用的、相对简单的文件格式，被用户、商业和科学广泛应用。包括kaggle的一个基础算法比赛【泰坦尼克之灾】给的数据库也是写在.csv文件里的。
简单来说.csv文件就是能用excel打开的文件。

所以训练数据集部分如下，我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。

image.png

第一步，导入相关模块

import numpy as np
import pandas as pd

第二步，读入数据

data = pd.read_csv('loan.csv')

若是使用jupyter，可以即刻查看一下数据，和数据标签。

image.png

image.png

可以看出，除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征，而最后一个标签'label'是我们所说的类，所以要处理一下这些标签，

label = data.columns
features = list(label[1: -1]) #如上图，label并不是是列表，为了方便下面引用，将它变为列表形式
classes = label[-1]

第三步，计算训练集的熵：

这里会用到pandas的一个统计数据的功能，groupby(by = [列]).groups，将数据统计成字典的形式，这么说比较抽象，看下图，将我们用pandas读入的data，分为2类，，Index表示索引，即第0，1，4，5，6，14（python计数从0开始）个数据的，第2，3，7，8，9，10，11，12，13个数据的.

image.png

那么计算训练集的熵

def empricalEntropy(data, classes):
    
    #计算每个类的样本数
    C = {}#记录每个类样本数的字典
    C_temp = data.groupby(by = [classes]).groups#记录每个类索引的字典
    for key in C_temp.keys():
        C[key] = len(C_temp[key])
    
    H_D = 0#初始化熵
    for key in C.keys():#key取0，1
        H_D -= C[key]/len(data) * np.log2(C[key]/len(data))
        
    return H_D

image.png

第四步，计算特征对数据集的条件熵

def empricalConditionalEntropy(data, feature, classes):
    D_temp = data.groupby(by = [feature]).groups #返回统计特征A的数据字典，它的key是特征A的各个取值，value是索引
    C_temp = data.groupby(by = [classes]).groups#返回统计分类的字典，它的key是分类的各个取值，value是索引
    
    H_DA = 0#初始化条件熵
    for key, i_index in D_temp.items():# D_temp的key是特征的各个取值
        D_i = len(i_index)#索引的长度，即为某个特征值的样本个数
        
        classConditionalEntropy = 0#H初始化H(Y|X=x_i)
        for label, k_index in C_temp.items():#key为0或者1
            D_ik = len(list(set(i_index).intersection(set(k_index))))#set(A).intersection(B)取集合A和B的交集
            if D_ik == 0:#计算机会在计算log0时返回nan，所以要把0的情况单独处理
                classConditionalEntropy += 0
            else:
                classConditionalEntropy += (D_ik/D_i) * (np.log2(D_ik/D_i))
        
        D = len(data)
        H_DA -= D_i/D * classConditionalEntropy
        
    return H_DA

image.png

第五步 ，计算信息增益

def infoGain(data, features, classes):
    
    H_D = empricalEntropy(data, classes)
    
    #初始化
    maxEntropy = 0
    maxFeature = ''
    
    for feature in features:
        H_DA = empricalConditionalEntropy(data, feature, classes)
        
        G = H_D - H_DA

        print(feature, G)#输出各个特征和G，方便查看

        #选出最优特征
        if G > maxEntropy:
            maxEntropy = G
            maxFeature = feature  
    
    return maxEntropy, maxFeature

image.png

3.0 决策树的生成

3.1 ID3算法

输入：训练集和特征和阈值；
输出：决策树
(1) 中所有实例都属于同一类，则为单结点树，并将类作为该结点的类标记，返回；
(2) 若，则为单结点树，并将中实例数最大的类作为该结点的类标记，返回；
(3)否则，按照上述信息增益的算法，计算中各个特征对的信息增益，选择信息增益最大的特征；
(4)如果特征的信息增益小于阈值，将置为单结点树，并将中实例数最大的类作为该结点的类标记，返回；
(5)否则，对的每一个可能值，依 将分割为若干非空子集 ，将 中实例数最大的类作为该结点的类标记，构建子结点，由结点及其子结点构成树 ，返回 ；
(6)对第个子结点，以为训练集，以为特征集，递归的调用步骤(1)~步骤(5)，得到子树 ，返回 。

还是那个例子

对上述表的训练集数据，利用ID3算法建立决策树。

解：

第一次迭代：

1. 计算训练集的熵
   
2. 计算特征各个对数据集的信息增益，年龄，有工作，有自己的房子，信贷情况这4个特征分别以表示。
   
   

3. 比较各个特征的信息增益，（有自己的房子）的信息增益最大，选择作为最优特征。

【特征：有自己的房子】将数据集划分为2个子集（有自己的房子）和（没有自己的房子），观察一下和：

：

由于所有实例都属于同一类，所以它是一个叶结点，结点的类标记为“是”。

：

对于则需从特征中选择新的特征。

第二次迭代：

1. 计算训练集的熵
   

2. 计算剩余特征各个对数据集的信息增益，年龄，有工作，信贷情况这3个特征分别以表示。
   
   
   

3. 比较各个特征的信息增益，（有自己的工作）的信息增益最大，选择作为最优特征。

将看作新的数据集。【特征：有工作】有2个可能值，划分为2个子集（有工作）和（没有工作），观察一下和：

：

由于所有实例都属于同一类，所以它是一个叶结点，结点的类标记为“是”。

：

由于所有实例都属于同一类，所以它也是一个叶结点，结点的类标记为“否”。

这样就生成了下图所示的决策树。

image.png

代码

接上面代码
第六步，每一次判断完信息增益之后，我们都需要对原始数据进行切割。
比如上述第一次迭代之后，【特征：有自己的房子】将数据集划分为2个子集（有自己的房子）和（没有自己的房子），和第二次迭代之后，将看作新的数据集。【特征：有工作】有2个可能值，划分为2个子集（有工作）和（没有工作）。

def splitdataset(data, index):
    data_slice = data.iloc[index, :]#.iloc(pands)对数据切片
    print(data_slice)#方便查看
    return data, data_slice

这里说一下为什么要返回原始数据data。因为如果对切片之后的data_slice再次做统计分类，它会返回一个新的字典，这个字典中的value表示的虽然还是索引，但是依旧是data的索引而不是data_slice的，所以要保留data才能找到你想要的数据。

image.png

第七步，利用上述所有辅助functions实现ID3算法.

def ID3(data, newData, features, classes, epsilon):
    
    print(features)
    
    C_temp = newData.groupby(by = [classes]).groups
    
    #D中所有实例都属于同一类C_k，则T为单结点树，并将类C_k作为该结点的类标记，返回T；
    if len(C_temp) == 1:
        for i in C_temp.keys():
            leafNode = i
        return leafNode
  
    #若A 为空，则T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T；
    if len(features) == 0:
        count = 0
        for key, index in C_temp.items():
            if count < len(index):
                count = len(index)
                maxClass = key
        leafNode = maxClass
        return leafNode
   
     #否则，按照上述信息增益的算法，计算A中各个特征对D的信息增益，选择信息增益最大的特征A_g；
    maxEntropy, maxFeature = infoGain(newData, features, classes)
    print(maxFeature)
    
    #如果特征A_g的信息增益小于阈值，将置T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T
    if maxEntropy < epsilon:
        count = 0
        for key, index in C_temp.items():
            if count < len(index):
                count = len(index)
                maxClass = key
        leafNode = maxClass
        return leafNode
    
    #否则，对A_g的每一个可能值a_i，依 A_g=a_i将D分割为若干非空子集 D_i，将 D_i中实例数最大的类C_k作为该结点的类标记，构建子结点，由结点及其子结点构成树 T，返回 T
    T = {maxFeature: {}}
    D_temp = newData.groupby(by = [maxFeature]).groups
    print(D_temp)
    
    features.remove(maxFeature)
   
    for i, index in D_temp.items():
        print(i)
        index = list(index)
        data, newData = splitdataset(data, index)
        print("newData",newData)
        T[maxFeature][i] = ID3(data, newData, features, classes, epsilon)
       
    print('\n') 
    return T

image.png

注：ID3算法只有树的生成，所以该算法生成的树容易过拟合。关于树的修剪，后面会补齐。