• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

开发技术 开发技术 6天前 7次浏览

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

前面我们已经详细讲解了线性SVM以及SMO的初步优化过程,具体可看:

  • 《Machine Learning in Action》—— 剖析支持向量机,优化SMO
  • 《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM

关于SVM非线性相关的内容,我们留着下个星期来撕

这篇文章我们先来看看决策树的内容,决策树相对于SVM来讲要简单不少,也没有多么复杂的公式。我理解的决策树,简单来说就是通过已有的数据集训练出一个树形结构的模型,以便我们能够依据该模型对不知分类结果的数据进行预测。简单的决策树就有点类似于我们在学习数据结构时候的二叉排序树。当然了,决策树除了能够进行分类之外,还能进行回归,这里主要讨论的是分类问题。

关于决策树相关的内容,可能会肝两篇文章来介绍。第一篇主要是讲解决策树先关的基本知识,及其决策训练的过程,也就是我们的这篇文章,重在理论及推导,也重在理解。而第二篇文章写的主要内容是决策树的代码实战,而代码实战是在熟悉理论基础的前提之下来进行的,所以对于决策树相关的理论知识还是有必要了解的。可能的话,还会有第三篇,主要是关羽防止决策树过拟合的剪枝操作的内容。

一、什么是决策树

关于决策树的定义,李航——《统计学习方法》(第二版)这本书中是这样描述的:

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

上述提到的内部节点可以理解成样本的属性特征,而叶节点可以理解成样本的标签,而有向边可以理解成不同的属性特征结果。一般我们在绘制决策树的时候,内部节点用方框或长方形表示,而叶节点用圆形或椭圆表示。(注意:这个并不是绝对的,在不同资料中可能有不同的表示方法,比如《统计学习方法》一书中用圆表示内部节点,用方形表示叶子节点,而在《机器学习实战》一书中表示方式正好相反

枯燥的文字说明总是会降低读者的阅读欲望,下面我们不妨通过一个实际的例子来说明下,从而加强读者对决策树的理解。

比如说,形容女生美与丑的时候一般会存在多个指标,这个例子感觉有点危险,还是换个吧。

例子来源:李航——《统计学习方法》(第二版)

比如说,我们没Money用了,想要去银行贷款,这个时候银行就会根据你自己的个人附带特征来决定是否给你放款。假设这里的属性特征有四个,分别是年纪、是否工作、是否有房子、信用情况,这些属性特征就相当于是内部节点,标签(结果)是否放款相当于叶子节点,而不同属性特征的结果表示有向边,像年纪中有青年、中年、老年,信用情况有好、一般、非常好等表示不同的有向边。

对此,我们可以根据自己的感觉来手动绘制一个简单的决策树模型:

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

我们知道,上述决策树仅仅是我们自己手动来实现的,不一定能够运用于解决实际问题。而决策树的任务,则是根据已有的数据样本集训练得到这么一颗树形结构模型,以此来对未知分类的数据进行类别预测。对此,我们要向得到这么一颗尽可能理想的决策树,则不得不考虑以下几个问题:

  • 决策树的指标(属性特征)选择的顺序应该是怎样的的?哪个特征应当被优先考虑呢?
  • 如果构建出的决策树出现了过拟合问题,也就说我们的训练的时候还不错,但是一测试就GG,这个时候我们应当怎么解决呢?

本篇文章,主要内容是属性特征的优先选取问题。

二、属性特征的选择

对于属性特征的选择,我们应当优先选取对训练数据集具有明显分类能力的特征,这样可以提高我们决策树的学习效率。假如说一个属性特征的分类结果与随机分类基本没什么差别,则我们可以说这个属性特征基本是没有分类能力的。

比如说,我们这里有12个关于女生美与丑的数据样本,其中六个是丑女,另外六个是美女,六个丑女身高有三个是165cm、三个是185cm,而另外六个美女身高同样如此,这样的话,我们仅仅通过身高来对女生美貌的判断基本是没有分类能力的。(仅仅是个例子,不代表任何观点

所以,我们理想情况下决策树的生成理应是这样的:随着决策过程的不断进行,我们希望决策树的分支节点所包含的样本尽可能的属于同一类别(标签相同),也就是节点的“纯度”越来越高。

所以,决策树的关键技术在于属性特征的选择。对于属性特征的选择,我们通常有三个准则:信息增益、信息增益比(增益率)和基尼指数。

2.1 信息增益

上面提到了样本浓度,比如说我这里有10个女生,10个都是美女,那就说此时的样本浓度高,假如美女和丑女五五分,那这个时候的浓度就比较低了。这里的“浓度”表达的就是这个意思,它主要针对的是标签(结果)

而表示样本“浓度”的指标,最常用的就是“信息熵”了。假定当前样本集合(D)中第(k)类(总共(n)类)样本所占的比例(p_k),则此时样本(D)的信息熵为:

[Ent(D) = -sum_{k=1}^np_klog_2(p_k) tag{2-1}
]

通过上述公式,我们可以知道10个美女(一个类别)的信息熵为

[Ent(D)=-1 * log_21=0
]

美女丑女五五分(两类)的信息熵为:

[Ent(D) = -frac{1}{2}log_2frac{1}{2}-frac{1}{2}log_2frac{1}{2}=1
]

通过上面信息熵的简单计算,我们可以知道,信息熵的值越小,则纯度越高。

既然我们已经了解了信息增益的计算公式及其所表达的意义,那么对于一个数据样本集,我们应当如何用代码来进行计算呢?下面我们来试试吧。

本次使用到的数据样本来自 李航——《统计学习方法》(第二版),数据是关于贷款申请的,具体如下:

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

那么现在我们来通过代码形式计算下这个数据样本集的信息熵吧:

首先创建一个establish_data方法来建立一个二维数组用于存储上述数据样本集的相关信息(关于属性特征所对于的值0,1,2之类的,大家可以参考上述表格对号入座,这里就不做过多解释了):

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:创建训数据集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息,前面几项代表属性特征,最后一项表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

随后,我们创建一个calc_information_entropy方法用于计算信息熵,计算过程的代码可结合上述的公式来看。另外,需要说一点的是,为了方便对放款结果进行分类,我们使用pandas包进行处理,关于pandas的使用,大伙可以参考文档,Taoye后期也会整理一份。当然了,不用pandas模块也能实现这个功能,有兴趣的读者可自行尝试,也不难。calc_information_entropy具体代码如下:

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        print(item[1])
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

我们运行上述代码,来看看具体的信息熵结果:

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

相比大家都了解了信息熵的概念,并能够手动计算样本集的信息熵了,现在我们再来把信息增益搬出来吧。

假设一个属性特征(a)(V)个可能的取值({a^1, a^2,.., a^V}),若使用(a)来对样本集(D)进行划分,这样的话就会产生(V)个分支节点,其中第(v)个 分支节点包含了(D)中所有在属性(a)上取值为(a^V)的样本,记为(D^V)。于是可计算出用属性特征(a)对样本集(D)进行划分所获得的“信息增益”(information gain)为:

[Gain(D, a)=Ent(D)-sum_{v=1}^Vfrac{D^v}{D}Ent(D^v) tag{2-2}
]

以上是周志华——《机器学习》一书中对信息增益的相关说明。

枯燥的文字说明总是会降低读者的阅读欲望,上述符号也是有点多,我们不妨拿上面的贷款数据来进一步理解下上述信息增益的内容:

我们单独拿年龄这一个属性特征来计算其信息增益吧,其有青年、中年、老年三个可能的值,也就是说上述的(a=年龄)({a^1,a^2,…,a^V}={青年,中年,老年}),而数据样本集(D)为上述15个数据样本,由于年龄有三个可能的值,所以此时会产生三个分支,即(V=3)。之前我们已经计算得到(Ent(D)=0.971),现在我们只要计算出后一项(sum_{v=1}^Vfrac{D^v}{D}Ent(D^v))的值即可得到该属性特征所对应的信息增益

通过数据,我们观察得到如下信息:

  • 对于年龄这个属性特征来讲,青年、中年、老年分别有5个。
  • 5个青年中有2个允许贷款,有三个不允许贷款;中年中有3个允许贷款,2个不允许贷款;老年中有4个允许贷款,有1个不允许贷款。

对此,我们可以计算:

[begin{aligned}
sum_{v=1}^Vfrac{D^v}{D}Ent(D^v) & = frac{5}{15}(-frac{2}{5}log_2frac{2}{5}-frac{3}{5}log_2frac{3}{5})\
& +frac{5}{15}(-frac{3}{5}log_2frac{3}{5}-frac{2}{5}log_2frac{2}{5}) \
& +frac{5}{15}(-frac{4}{5}log_2frac{4}{5}-frac{1}{5}log_2frac{1}{5}) \
& = 0.883
end{aligned}
]

对此,我们的计算处年龄这个属性特征所对应的信息增益值为:

[Gain(D, 年龄) = 0.971-0.883=0.083
]

我们可以把后一项的内容理解成条件概率。另外,信息增益越大,则其所对应的属性特征的分类能力也就越强,也就是我们应当优先选取的特征。

同理,我们可以计算出工作、房子、信用属性特征所对应的信息增益:

[begin{aligned}
& Gain(D, 工作)=0.324 \
& Gain(D, 房子)=0.420 \
& Gain(D, 信用)=0.363
end{aligned}
]

我们比较哥哥属性特征的信息增益值,可以发现房子这个属性特征最大,所以它应该是我们优先选择的属性特征。

了解了信息增益的计算及其意义,下面我们来通过代码计算一下(代码含义见注释):

import numpy as np
import pandas as pd

np.__version__
pd.__version__

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:创建训数据集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息,前面几项代表属性特征,最后一项表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:找出对应属性特征值的样本,比如找出所有年纪为青年的样本数据集
"""
def handle_data(data, axis, value):
    result_data = list()
    for item in data:
        if item[axis] == value: result_data.append(item)
    return result_data

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算最大的信息增益,并输出其所对应的特征索引
"""
def calc_information_gain(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和对应的特征索引
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy = 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        print("第%d个属性特征所对应的的增益为%.3f" % (index + 1, temp_information_gain))            # 输出每个特征的信息增益
        if (temp_information_gain > max_information_gain):
            max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益,确定的最大的信息增益对应的索引
    return best_feature

if __name__ == "__main__":
    data = establish_data()
    print("属性特征对应的最大的信息增益对应的索引为:%d" % calc_information_gain(data))

运行上述代码,可见输出的各个属性特征的信息增益,以及最大信息增益对应的特征索引

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

可以发现,和我们手动计算的如出一辙,所以此时我们应当优先选取索引为2的属性特征作为决策标准,也就是房子。

2.2 信息增益比(增益率)

我们使用信息增益作为选取特征指标的时候,存在偏向于选择取值较多的特征的问题。

比如我们将id作为上述数据集的一个分类属性,通过计算可以发现该信息增益最大,但实际上该id对类别不具有什么分类能力,所以这样得到的决策树不具有泛化能力,无法对新样本进行有效预测。

为了解决信息增益存在的这个问题,我们就引入了信息增益比(增益率)的概念,著名的C4.5算法就是用“增益率”来作为选取最优划分属性。增益率定义为:

[Gain_ratio(D, a)=frac{Gain(D, a)}{IV(a)} tag{2-3}
]

[其中,IV(a)=-sum_{v=1}^Vfrac{|D^v|}{|D|}log_2frac{|D^v|}{|D|} tag{2-4}
]

(IV(a))称为(a)的“固有值”(intrinsic value)。通常(a)的取值数目越多,则(IV(a))的值会越大。其中的(a)的取值比如说:上述的年纪有青年、中年、老年三种取值。

对于上述的贷款数据集来说,信用情况有一般、好和非常好三种,比例分为是(frac{5}{15}、frac{6}{15}、frac{4}{15})。毒刺,我们可以计算信用情况的“固有值”:

[begin{aligned}
IV(信用) & =-sum_{v=1}^Vfrac{|D^v|}{|D|}log_2frac{|D^v|}{|D|} \
& =-frac{5}{15}log_2frac{5}{15}-frac{6}{15}log_2frac{6}{15}-frac{4}{15}log_2frac{4}{15} \
& = 1.566
end{aligned}
]

所以,对于信用属性来讲,其增益率为:

[begin{aligned}
Gain_ratio(D, 信用) & =frac{Gain(D, 信用)}{IV(信用)} \
& = frac{0.363}{1.566} \
& = 0.232
end{aligned}
]

同理,我们可以计算出其他属性特征的增益率:

[begin{aligned}
Gain_ratio(D, 年龄) & =0.052 \
Gain_ratio(D, 工作) & =0.352 \
Gain_ratio(D, 房子) & =0.433 \
end{aligned}
]

计算增益率的具体代码可参考如下:

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算增益率
"""
def calc_gain_ratio(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv = 0.0, 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d个属性特征所对应的增益率为%.3f,信息增益为%.3f" % (index + 1, gain_ratio, temp_information_gain))            # 输出每个特征的信息增益

运行结果如下:

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

在C4.5算法中,并不是直接单一的使用增益率来对属性特征的选取进行决策,而是先在信息增益中选取高于平均水平的属性作为候选,然后从候选中选取增益率最高的。

关于C4.5算法,我们后期会讲到。

2.3 基尼指数

基尼指数是另外一种选取属性的指标。

前面我们提到了,信息熵是描述数据样本纯度一个标准,而在基尼指数中的基尼值同样可以体现数据样本的纯度。数据样本集(D)的基尼值可以用(Gini(D))来表示(其中(k)表示有(k)个标签结果):

[Gini(D)=1-sum_{k=1}^{|y|}p_k^2 tag{2-5}
]

基尼值(Gini(D))越小,说明数据样本纯度越高。而属性(a)对应的基尼指数(Gini_index(D,a))可以定义为:

[Gini_index(D, a)=sum_{v=1}^Vfrac{|D^v|}{|D|}Gini(D^v) tag{2-6}
]

我们同样来分别计算下上述贷款数据集的基尼指数。

对于信用情况这一属性特征来讲,其基尼指数的手动计算过程如下所示:

[begin{aligned}
Gini_index(D, 信用) & = sum_{v=1}^{V}frac{|D^v|}{|D|}Gini(D^v) \
& = frac{5}{15}(1-(frac{4}{5})^2 – (frac{1}{5})^2)+frac{6}{15}(1-(frac{2}{6})^2 – (frac{4}{6})^2)+frac{4}{15}(1-(frac{4}{4})^2 – (frac{0}{4})^2) \
& =
end{aligned}
]

对于其他属性的基尼指数,读者可自行根据上述过程进行计算(真的很简单)。关于基尼指数的计算代码,可参考如下:

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算基尼指数
"""
def calc_gini_index(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv, gini_index = 0.0, 0.0, 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            temp_df = pd.DataFrame(sub_data)
            yes_proportion = temp_df[temp_df[temp_df.shape[1]-1] == "Y"].shape[0] / len(sub_data)
            gini_value = 1 - (yes_proportion ** 2) - ((1- yes_proportion) ** 2)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
            gini_index += gini_value * proportion     # 计算基尼指数
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d个属性特征所对应的信息增益为%.3f,增益率为%.3f, 基尼指数为%.3f" % (index + 1, temp_information_gain, gain_ratio, gini_index))

运行结果:

《Machine Learning in Action》—— Taoye给你讲讲决策树到底是支什么“鬼”

以上就是基尼指数的计算及其相关代码,一般来讲,基尼指数越小就优先被划分。

上述内容的完整代码如下:

import numpy as np
import pandas as pd

np.__version__
pd.__version__

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:创建训数据集
"""
def establish_data():
    data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息,前面几项代表属性特征,最后一项表示是否放款
            [0, 0, 0, 1, 'N'],
            [0, 1, 0, 1, 'Y'],
            [0, 1, 1, 0, 'Y'],
            [0, 0, 0, 0, 'N'],
            [1, 0, 0, 0, 'N'],
            [1, 0, 0, 1, 'N'],
            [1, 1, 1, 1, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [1, 0, 1, 2, 'Y'],
            [2, 0, 1, 2, 'Y'],
            [2, 0, 1, 1, 'Y'],
            [2, 1, 0, 1, 'Y'],
            [2, 1, 0, 2, 'Y'],
            [2, 0, 0, 0, 'N']]
    return np.array(data)

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算信息熵
"""
def calc_information_entropy(data):
    data_number, _ = data.shape
    information_entropy = 0
    for item in pd.DataFrame(data).groupby(_ - 1):
        proportion = item[1].shape[0] / data_number
        information_entropy += - proportion * np.log2(proportion)
    return information_entropy

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:找出对应属性特征值的样本,比如找出所有年纪为青年的样本数据集
"""
def handle_data(data, axis, value):
    result_data = list()
    for item in data:
        if item[axis] == value: result_data.append(item)
    return result_data

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算最大的信息增益,并输出其所对应的特征索引
"""
def calc_information_gain(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和对应的特征索引
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy = 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        print("第%d个属性特征所对应的的增益为%.3f" % (index + 1, temp_information_gain))            # 输出每个特征的信息增益
        if (temp_information_gain > max_information_gain):
            max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益,确定的最大的信息增益对应的索引
    return best_feature

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算增益率
"""
def calc_gain_ratio(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv = 0.0, 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d个属性特征所对应的增益率为%.3f,信息增益为%.3f" % (index + 1, gain_ratio, temp_information_gain))            # 输出每个特征的信息增益

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain:计算基尼指数
"""
def calc_gini_index(data):
    feature_number = data.shape[1] - 1                    # 属性特征的数量
    base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
    for index in range(feature_number):
        feat_list = [item[index] for item in data]
        feat_set = set(feat_list)
        new_entropy, iv, gini_index = 0.0, 0.0, 0.0
        for set_item in feat_set:                         # 计算属性特征划分后的信息增益
            sub_data = handle_data(data, index, set_item)
            temp_df = pd.DataFrame(sub_data)
            yes_proportion = temp_df[temp_df[temp_df.shape[1]-1] == "Y"].shape[0] / len(sub_data)
            gini_value = 1 - (yes_proportion ** 2) - ((1- yes_proportion) ** 2)
            proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
            new_entropy += proportion * calc_information_entropy(np.array(sub_data))
            iv += -proportion * np.log2(proportion)
            gini_index += gini_value * proportion
        temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
        gain_ratio = temp_information_gain / iv
        print("第%d个属性特征所对应的信息增益为%.3f,增益率为%.3f, 基尼指数为%.3f" % (index + 1, temp_information_gain, gain_ratio, gini_index))
        
if __name__ == "__main__":
    data = establish_data()
    calc_gini_index(data)

优先选取属性特征的指标主要有三个,分别是信息增益、增益率、基尼指数。对上述内容做个简单的总结吧:

  • 属性特征的信息增益越高,按道理来讲应当被优先选取,常用于(ID3)算法
  • 属性特征的增益率越高,按道理来讲应当被优先选取,常用与(C4.5)算法
  • 属性特征的尼基指数低,按道理来讲应当被优先选取,常用于(CART)算法

本文主要是决策树的理论部分内容,介绍了什么决策树,以及生成决策树时所需要优先选取的三种决策标准。有学习的过SVM,或阅读过Taoye之前写的几篇SVM内容的文章可以发现,决策树相对于SVM来讲要简单很多,没有太多且复杂的公式推导。关于决策树的其他内容,比如决策树的生成、可视化、剪枝等,我们放在后面几篇文章来写。

我是Taoye,爱专研,爱分享,热衷于各种技术,学习之余喜欢下象棋、听音乐、聊动漫,希望借此一亩三分地记录自己的成长过程以及生活点滴,也希望能结实更多志同道合的圈内朋友,更多内容欢迎来访微信公主号:玩世不恭的Coder


喜欢 (0)