决策树(descision tree)

一：决策树的基础介绍

决策树(descision tree)是一种基本的分类与回归的方法。决策树是一种对实例进行预测的树型结构。

下面是一个完整的二叉决策树，根据西瓜的几个特征判断西瓜的好坏。

纹理<=1.5代表第一个判断条件，根据纹理<=1.5是否小于1.5将整个样本集分为两边。

左边True代表左侧的所有的样本都满足判断条件，右侧False相反。

𝑔𝑖𝑛𝑖代表分类收获的提升(关于决策树分裂的算法，后续会介绍)。

samples=17代表样本的数量为17。value=[9,8]代表好瓜坏瓜的数量为9个和8个。

class=好瓜代表如果在该节点进行预测，那么预测的结构是好瓜。

通过树不断地分裂我们就可以得到一个完整决策树，然后就可以使用该决策树对西瓜的好坏进行预测啦

二、决策树的分裂算法

上面关于一个分类决策树的介绍中有关于决策树分裂的算法相信大家会有疑问。怎么进行分裂，为什么要这样进行分类，怎么选择特征分裂？常见的分类决策树分裂算法有：

1：信息增益

2：信息增益比

3：gini指数

1：信息增益

为了解释信息增益，我们先来介绍下熵与条件熵。在信息论中，熵(entropy)是表示随机变量不确定性的度量。假设Y是一个有限个值得离散随机变量，其概率分布为：

则随机变量Y的熵为：

通常log的底我们会取2或者e。为了防止    ，我们定义0𝑙𝑜𝑔0=0。

从熵的定义中我们可以知道熵越大，那么随机变量的不确定性就越大：

当随机变量Y的取值为0,1时，即只有2个类别。假设Y的分布为：

 , 其中：

此时随机变量Y的熵为：

当𝑝越接近于0.5时，熵越大，反之熵越小。

上面时关于熵的介绍，下面我们介绍下条件熵：

假设有随机变量(X,Y)，其联合概率分布为：

条件熵𝐻(𝑌|𝑋)表示在已知随机变量𝑋的情况下随机变量𝑌的不确定性。其公式为：

这里

熵和条件熵都介绍完毕了，现在到我们的信息增益了。信息增益就是得知特征X的信息而使得Y的信息不确定性减少的程度。说人话就是当我们知道了特征X之后我们对Y预测的把握提升有多少。完整的定义如下：

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

下面我们举个小例子用代码来计算信息增益。数据来自于西瓜书决策树章节

import pandas as pd
import numpy as np
from math import log
data=pd.read_csv(r"/home/mw/input/data2794/西瓜数据集.csv")
data.head()

def calShanEnt(dataset,col):
    tarset=set(dataset[col])
    res=0
    for i in tarset:
        pi=np.sum(dataset[col] == i)/len(dataset)
        res=res-pi* log(pi, 2)
    return res


def ID3(dataset,fea):
    baseEnt = calShanEnt(dataset, "target")
    newEnt = 0
    value_set=set(dataset[fea])
    for v in value_set:
        newEnt += np.sum(dataset[fea] == v) / len(dataset) * calShanEnt(dataset[dataset[fea] == v],"target")
    return baseEnt-newEnt
ID3(data,"根蒂")
# 0.14267495956679288

可以看到，在给定西瓜"根蒂"条件的基础上，信息增益为0.142

关于信息增益的介绍也已经介绍，该回到我们开始的环节了，怎么进行分裂，选择什么特征进行分裂。

使用信息增益进行分裂时我们的特征选择方法是：对训练集(或者子集)D,计算其每个特征的信息增益，并且比较大小，选择信息增益最大的特征。

方法也是很直接，既然给定每个特征都可以得到一个新增增益，那哪个特征的信息增益大，我们选择哪个特征不就好了？于是：

def chooseBestFea(dataset):
    features=[i for i in dataset.columns if i!='target']
    bestFet=features[0]
    bestInfoGain=-1
    for fea in features:
        gain=ID3(dataset,fea)
        if gain>bestInfoGain:
            bestInfoGain=gain
            bestFet=fea
    print(set(dataset[bestFet]))
    print(bestInfoGain)
    return bestFet


chooseBestFea(data)

'''
{'清晰', '模糊', '稍糊'}
0.3805918973682686
'纹理'
'''

可以看到，选择"纹理"进行分裂信息增益最大(0.38059189736826)。因此我们可以根据特征"纹理"将整个样本集分为三份,分别是"纹理=模糊"，"纹理=清晰"，"纹理=稍糊"

2：信息增益比

在使用信息增益的时候，可能存在这样一种情况，它的特征类别特别的多。(极端情况下，特征类别数量等于样本数据)。这种情况下，在该特征的情况下，信息增益变得很大，但是其实这种情况下，泛化能力会变低。考虑到这种情况，还有一种修正的方法，那就是信息增益比。

定义：

特征A对训练数据集D的信息增益比    为信息增益g(D,A)与训练集D关于特征A的值的熵 之比，即：

其中，    ,n是特征A取值的个数。可以看到当特征A越分散时HA(D)𝐻𝐴(𝐷)即特征A的熵越大。相对应的该特征就越不会被选择。

def C4_5(dataset,fea):
    gain=ID3(dataset,fea)
    IVa=calShanEnt(dataset,fea)
    return gain/IVa
C4_5(data,"纹理")
# 0.2630853587192754



def chooseBestFea(dataset):
    features=[i for i in dataset.columns if i!='target']
    bestFet=features[0]
    bestInfoGain=-1
    for fea in features:
        gain=C4_5(dataset,fea)
        if gain>bestInfoGain:
            bestInfoGain=gain
            bestFet=fea
    print(set(dataset[bestFet]))
    print(bestInfoGain)
    return bestFet
chooseBestFea(data)

'''
{'清晰', '模糊', '稍糊'}
0.2630853587192754
'纹理'
'''

可以看到采用这种方法来分裂，"纹理"还是最先分裂得特征。不过此时信息增益比为0.2630853

3：Gini指数(基尼指数)

除了上述得信息增益和信息增益比之外，还有一个别的常见分裂方法，那就是基尼指数。

定义：

分类问题中，假设有K个类，样本属于第k个类别得概率为    ，则概率分布得基尼指数为：

对于给定样本集合D,其基尼指数为：

其中    表示的是属于第𝑘类样本的集合，K是样本类别的个数。

如果样本集合D根据特征A是否取某一可能的值𝛼被分割成    和    两个部分,即：

则在特征A的条件下，集合D的基尼指数为：

注：使用Gini指数指导一般只分裂为二叉树。

与上面的两个方法相比，Gini指数进行分裂不仅要选择特征，而且要选择特征值。还是用代码来表示：

def Gini(dataset,col):
    tarset = set(dataset[col])
    gini=1
    for i in tarset:
        gini=gini-(np.sum(dataset[col] == i)/len(dataset))**2
    return gini



Gini(data,"target")
# 0.49826989619377154



def CART(dataset,fea):
    value_set=set(dataset[fea])
    Gini_min= 100
    fea_min=""
    for v in value_set:
        Gini_index=np.sum(dataset[fea] == v) / len(dataset) * Gini(dataset[dataset[fea] == v],"target")+ \
        np.sum(dataset[fea] != v) / len(dataset) * Gini(dataset[dataset[fea] != v],"target")
        if Gini_index<Gini_min:
            Gini_min=Gini_index
            fea_min=v
        
    return Gini_min,fea_min

使用"纹理"特征时，最优的分裂特征值为"清晰",可以通过该"纹理==清晰"和"纹理!=清晰"将样本分为两个区间

CART(data,"纹理")
# (0.28594771241830064, '清晰')



def chooseBestFea(dataset):
    features=[i for i in dataset.columns if i!='target']
    bestFet=features[0]
    bestFetFea=""
    bestInfoGain=1
    
    for fea in features:
        value_set=set(dataset[fea])
        gain,value_fea=CART(dataset,fea)
        if gain<bestInfoGain:
            bestInfoGain=gain
            bestFet=fea
            bestFetFea=value_fea
    return bestFet,bestFetFea


chooseBestFea(data)
# ('纹理', '清晰')



### 使用三种方法建立一个决策树

import pandas as pd
from math import log
import numpy as np

class DT:
    def __init__(self, data, model):
        self.data = data
        self.model = model

    def calShanEnt(self, dataset, col):
        tarset = set(dataset[col])
        res = 0
        for i in tarset:
            pi = np.sum(dataset[col] == i) / len(dataset)
            res = res - pi * log(pi, 2)
        return res

    def ID3(self, dataset, fea):
        baseEnt = self.calShanEnt(dataset, "target")
        newEnt = 0
        value_set = set(dataset[fea])
        for v in value_set:
            newEnt += np.sum(dataset[fea] == v) / len(dataset) * self.calShanEnt(dataset[dataset[fea] == v], "target")
        return baseEnt - newEnt

    def C4_5(self, dataset, fea):
        gain = self.ID3(dataset, fea)
        IVa = self.calShanEnt(dataset, fea)
        return gain / IVa

    def Gini(self, dataset, col):
        tarset = set(dataset[col])
        gini = 1
        for i in tarset:
            gini = gini - (np.sum(dataset[col] == i) / len(dataset)) ** 2
        return gini

    def CART(self, dataset, fea):
        value_set = set(dataset[fea])
        Gini_min = 100
        fea_min = ""
        for v in value_set:
            Gini_index = np.sum(dataset[fea] == v) / len(dataset) * self.Gini(dataset[dataset[fea] == v], "target") + \
                         np.sum(dataset[fea] != v) / len(dataset) * self.Gini(dataset[dataset[fea] != v], "target")
            if Gini_index < Gini_min:  # 越小越好
                Gini_min = Gini_index
                fea_min = v
        return -Gini_min, fea_min  ##由于另外连个方法都是最大的值进行分裂，而Gini指数是最小，因此取负数，这样-Gini_min越大越好

    def chooseBestFea(self, dataset):
        features = [i for i in dataset.columns if i != 'target']
        bestFet = features[0]
        bestFetFea = ""
        bestInfoGain = -1
        value_fea = ""
        for fea in features:
            if self.model == "C4_5":
                gain = self.C4_5(dataset, fea)
            elif self.model == "ID3":
                gain = self.ID3(dataset, fea)
            elif self.model == "CART":
                gain, value_fea = self.CART(dataset, fea)
            else:
                raise ("输入的model值之只能是：C4_5,ID3,CART,但是实际输入的值为：", self.model)
            if gain > bestInfoGain:
                bestInfoGain = gain
                bestFet = fea
                bestFetFea = value_fea
        return bestFet, bestFetFea

    def creatTree(self, dataset):
        if len(dataset.columns) == 1:
            return dataset['target'].value_counts().index[0]
        if len(set(dataset['target'])) == 1:
            return list(dataset['target'])[0]
        bestFea, bestFetFea = self.chooseBestFea(dataset)
        myTree = {bestFea: {}}
        if bestFetFea == "":
            for i in set(dataset[bestFea]):
                new_data = dataset[dataset[bestFea] == i].reset_index(drop=True)
                myTree[bestFea][i] = self.creatTree(new_data)
        else:
            new_data = dataset[dataset[bestFea] == bestFetFea].reset_index(drop=True)
            myTree[bestFea][bestFetFea] = self.creatTree(new_data)
            new_data2 = dataset[dataset[bestFea] != bestFetFea].reset_index(drop=True)
            myTree[bestFea]["不等于" + bestFetFea] = self.creatTree(new_data2)

        return myTree
data_path=r"../input/data2794"
data = pd.read_csv(r"../input/data2794"+"/西瓜数据集.csv")    
model = DT(data, "CART")
tree=model.creatTree(data)