美文网首页
决策树(decisionTree)

决策树(decisionTree)

作者: 霞客环肥 | 来源:发表于2019-02-22 15:02 被阅读0次
    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规则,简单来说就是 :
    如果A,那么B

    举例:对于一个苹果,外表是红色的是红苹果,外表是绿色的是青苹果。可以表示为:
    if 红色,then 红苹果 if 绿色,then 青苹果

    if-then规则集合具有一个重要的性质:
    互斥且完备

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

    1.3 决策树学习

    给定数据集:
    D = \{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}
    其中,x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})为输入实例(特征向量),含有n个特征,y_i = \{ 1, 2,...,K\}为类标记,i = 1,2,..,N, N为样本容量。

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

    2.0 特征选择

    2.1 特征选择问题

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

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

    这样的特征可以扔掉

    那么问题来了,怎么选择特征呢?

    通常特征选择的准则是
    信息增益或信息增益比
    下面通过例子来说明一下。

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    1 青年 一般
    2 青年
    3 青年
    4 青年 一般
    5 青年 一般
    6 中年 一般
    7 中年
    8 中年
    9 中年 非常好
    10 中年 非常好
    11 老年 非常好
    12 老年
    13 老年
    14 老年 非常好
    15 老年 一般

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

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

    2.2 信息增益

    知识储备1熵(entropy)
    熵是表示随机变量不确定性的度量。

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

    X是一个取有限个值的随机变量,其概率分布为
    P(X = x_i) = p_i, i = 1,2,...,n
    则随机变量X的熵定义为
    H(X) = -\sum_{i =1}^n p_i \log p_i
    p_i = 0,则定义0 log 0 = 0。通常对数取以2为底,或是以e为底,熵的单位分布为比特(bit)或是纳特(nat)。
    由上式可知,熵只依赖X的分布,而已X的值无关,则X的熵还可记作H(p),即
    H(p) = -\sum_{i =1}^n p_i \log p_i
    则从定义可知
    0 \leq H(p) \leq \log{n}

    当随机变量只取2个值的时候,例如0,1时,X的分布为
    P(X = 1) = p, P(X = 0) = 1-p, 0 \leq p \leq 1
    熵为
    H(p) = p \log_2 p + (1-p) \log_2 (1-p)

    熵随概率变化的曲线为


    image.png

    p = 0p=1H(p) =0,随机变量完全没有不确定性,当p = 0.5H(p) = 1,熵取值最大,随机变量不确定性最大。

    设随机变量(X, Y),其联合概率分布
    P(X=x_i, Y=y_i) = p_{ij}, i = 1,2,...,n

    条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定条件下随机变量Y的条件熵(conditional entropy),定义为X给定条件下Y的条件概率分布的熵对X的数学期望
    H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i)

    信息增益
    特征A对训练集D的信息增益g(D, A)
    g(D, A) = H(D) - H(D|A)

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

    前期定义各个量:

    训练集 D 特征A,有n个可能值,\{ a_1, a_2, ..., a_n\} C_kK个可能值,\{ C_1, C_2, ..., C_K \}
    根据A的取值,划分为n个子集,D_1,D_2,..,D_n, | D_i|D_i的样本数 |C_k|为属于类C_k的样本数
    |D_{ik}|为特征A的取值为a_i,又属于类C_k的样本数

    信息增益的算法
    输入:训练集D和特征A
    输出:特征A对训练集D的信息增益g(D, A)

    1. 计算训练集D的熵H(D)
      H(D) = -\sum_{k =1}^K \frac { \vert{C_k} \vert}{\vert{D} \vert} \log_2 \frac { \vert{C_k} \vert}{\vert{D} \vert}
    2. 计算特征A对数据集D的条件熵H(D|A)
      H(D|A) = -\sum_{i =1}^n\frac { \vert{D_i} \vert}{\vert{D} \vert} \sum_{k=1}^K \frac { \vert{D_{ik}} \vert}{\vert{D_i} \vert} \log_2 \frac { \vert{D_{ik}} \vert}{\vert{D_i} \vert}
    3. 计算信息增益
      g(D, A) = H(D) - H(D|A)

    回看刚才的例子,

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    1 青年 一般
    2 青年
    3 青年
    4 青年 一般
    5 青年 一般
    6 中年 一般
    7 中年
    8 中年
    9 中年 非常好
    10 中年 非常好
    11 老年 非常好
    12 老年
    13 老年
    14 老年 非常好
    15 老年 一般

    1. 计算训练集D的熵H(D)
      H(D) = - \frac {9}{15} \log_2 \frac {9} {15} - \frac {6}{15} \log_2 \frac {6} {15} = 0.971
    2. 计算特征各个A对数据集D的信息增益g(D|A),年龄,有工作,有自己的房子,信贷情况这4个特征分别以A_1, A_2, A_3, A_4表示。
      g(D|A_1) = -\frac { 5}{15} H(D_1) --\frac { 5}{15} H(D_2)--\frac { 5}{15} H(D_3)
      = 0.083

    g(D|A_2) = -\frac { 5}{15} H(D_1) --\frac { 10}{15} H(D_2)
    = 0.324

    g(D|A_3) = -\frac { 6}{15} H(D_1) --\frac { 9}{15} H(D_2)
    = 0.420

    g(D|A_4)=0.363

    1. 比较各个特征的信息增益,A_3(有自己的房子)的信息增益最大,选择A_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'为我们一直在说的特征A,而最后一个标签'label'是我们所说的类C_k,所以要处理一下这些标签,

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



    第三步,计算训练集D的熵H(D)
    H(D) = -\sum_{k =1}^K \frac { \vert{C_k} \vert}{\vert{D} \vert} \log_2 \frac { \vert{C_k} \vert}{\vert{D} \vert}

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

    image.png

    那么计算训练集D的熵H(D)

    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



    第四步,计算特征A对数据集D的条件熵H(D|A)
    H(D|A) = -\sum_{i =1}^n\frac { \vert{D_i} \vert}{\vert{D} \vert} \sum_{k=1}^K \frac { \vert{D_{ik}} \vert}{\vert{D_i} \vert} \log_2 \frac { \vert{D_{ik}} \vert}{\vert{D_i} \vert}

    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



    第五步 ,计算信息增益
    g(D, A) = H(D) - H(D|A)

    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算法

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

    还是那个例子

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    1 青年 一般
    2 青年
    3 青年
    4 青年 一般
    5 青年 一般
    6 中年 一般
    7 中年
    8 中年
    9 中年 非常好
    10 中年 非常好
    11 老年 非常好
    12 老年
    13 老年
    14 老年 非常好
    15 老年 一般

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

    第一次迭代

    1. 计算训练集D的熵H(D)
      H(D) = - \frac {9}{15} \log_2 \frac {9} {15} - \frac {6}{15} \log_2 \frac {6} {15} = 0.971
    2. 计算特征各个A对数据集D的信息增益g(D|A),年龄,有工作,有自己的房子,信贷情况这4个特征分别以A_1, A_2, A_3, A_4表示。
      g(D|A_1) = -\frac { 5}{15} H(D_1) --\frac { 5}{15} H(D_2)--\frac { 5}{15} H(D_3)
      = 0.083

    g(D|A_2) = -\frac { 5}{15} H(D_1) --\frac { 10}{15} H(D_2)
    = 0.324

    g(D|A_3) = -\frac { 6}{15} H(D_1) --\frac { 9}{15} H(D_2)
    = 0.420

    g(D|A_4)=0.363

    1. 比较各个特征的信息增益,A_3(有自己的房子)的信息增益最大,选择A_3作为最优特征。

    【特征:有自己的房子】将数据集D划分为2个子集D_1(有自己的房子)和D_2(没有自己的房子),观察一下D_1D_2

    D_1

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    4 青年 一般
    8 中年
    9 中年 非常好
    10 中年 非常好
    11 老年 非常好
    12 老年

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

    D_2

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    1 青年 一般
    2 青年
    3 青年
    5 青年 一般
    6 中年 一般
    7 中年
    13 老年
    14 老年 非常好
    15 老年 一般

    对于D_2则需从特征A_1(年龄),A_2(有工作),A4(信贷情况)中选择新的特征。

    第二次迭代

    1. 计算训练集D_2的熵H(D_2)
      H(D_2) = - \frac {6}{9} \log_2 \frac {6} {9} - \frac {3}{9} \log_2 \frac {3} {9} = 0.918

    2. 计算剩余特征各个(A-A_1)对数据集D_2的信息增益g(D_2|A),年龄,有工作,信贷情况这3个特征分别以A_1, A_2, A_4表示。
      g(D_2|A_1) = H(D_2) - H(D_2|A_1) = 0.918 - 0.669 =0.251
      g(D_2|A_2) = H(D_2) - H(D_2|A_2) = 0.918
      g(D_2|A_4) = H(D_2) - H(D_2|A_4) = 0.474

    3. 比较各个特征的信息增益,A_2(有自己的工作)的信息增益最大,选择A_2作为最优特征。

    D_2看作新的数据集D。【特征:有工作】有2个可能值,划分为2个子集D_1(有工作)和D_2(没有工作),观察一下D_1D_2

    D_1

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    3 青年
    13 老年
    14 老年 非常好

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

    D_2

    ID 年龄 有工作 有自己的房子 信贷情况 类别(是否同意贷款)
    1 青年 一般
    2 青年
    5 青年 一般
    6 中年 一般
    7 中年
    15 老年 一般

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

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


    image.png

    代码

    接上面代码
    第六步,每一次判断完信息增益之后,我们都需要对原始数据进行切割
    比如上述第一次迭代之后,【特征:有自己的房子】将数据集D划分为2个子集D_1(有自己的房子)和D_2(没有自己的房子),和第二次迭代之后,D_2看作新的数据集D。【特征:有工作】有2个可能值,划分为2个子集D_1(有工作)和D_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算法只有树的生成,所以该算法生成的树容易过拟合。关于树的修剪,后面会补齐。

    相关文章

      网友评论

          本文标题:决策树(decisionTree)

          本文链接:https://www.haomeiwen.com/subject/ypzcyqtx.html