Press "Enter" to skip to content

机器学习 – 决策树

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

决策树,听名字就知道跟树有关,而且很容易猜到是一种类似依靠树形结构来辅助决策过程的策略。所以重点就是如何构建这个树,如何依次选取树的各个节点,以便能在测试集中有较好的表现。

 

信息熵与信息增益

 

说到如何选取节点,就要引入信息熵的概念。我以前一看到“熵”这个字就头疼,以为是跟高深的物理学相关,其实很好理解,简单说就是纯度。假设有一罐混合了氧气和二氧化碳的气体:

我们通常会说这罐气体不纯,那幺怎幺来度量这个纯度呢?假设氧气占20%,二氧化碳占80%,则可以看做是二氧化碳里混入了少量的氧气,二氧化碳相对纯一些;如果看做是氧气中混入了大量的二氧化碳,那幺这个氧气也太不纯了。我们在这里所讨论的纯度,都是针对某一特定对象而言,而又不适用于这个系统里的其他对象。如果把这个罐子当做整个系统的话,信息熵就可以看做是系统级的纯度。一般这样度量信息熵,系统纯度越低,信息熵越大,反之,系统纯度越高,信息熵越小。如果罐子里只剩一种气体,则信息熵为0。

 

信息熵的计算公式如下:

其中k表示系统中特征的数量,p(xi)表示每个特征再系统中的占比。所以我们可以算出此时的信息熵为:

假设由于保存不当,罐子中混入了一种有色气体(比如二氧化硫):

假设目前三种气体的占比为:氧气15%,二氧化碳50%,二氧化硫35%,根据信息熵的理论,现在整个系统的信息熵应该比原先更大了(纯度降低)。我们不妨再算一下此时的信息熵:

可以看到信息熵增大了,符合之前的理论。那幺如果我们现在要分离这三种气体,就需要选择一个标准,或者说,选择能够区分这三种气体的特征进分离。最直观的特征就是有色跟无色:

如果按这个特征对系统进行划分,则会将系统划分为有色气体跟无色气体两个子集。划分后的系统,已经由最初较为混沌的状态(三种气体混合)变成了有色跟无色两部分,所以,此时的信息熵就变成了有色子集的信息熵与无色子集信息熵的加和。但考虑到这两类气体在系统中的占比,需要将占比作为子集信息熵的权重,所以此时的信息熵为:

所以经过对气体颜色这一特征的划分,系统的信息熵由1.125变成了0.418,说明系统纯度有所提升。为了准确的表示提升的具体情况,就把这个提升空间叫做 信息增益 。

写成标准式:

其中,D表示整个样本数据集,a表示所选的用户划分系统样本的特征,Ent(D)表示划分前的信息熵,|Di|表示划分后的每个子集的样本个数,|D|表示划分前的样本总数,Ent(Di)表示每个子集各自的信息熵。后面一项实际上就是子集信息熵的期望。

 

从公式可以看出,如果选取不同的特征,划分后的信息熵可能会有大小之分,而系统当前的信息熵是不变的,所以划分后的信息熵如果越小,信息增益就越大,说明系统纯度提升的幅度就越大,反之亦然。所以,我们就需要遍历所有已知特征,找出能够提升幅度最大的那个特征,作为首选的划分特征。

 

至此,就把信息熵和信息增益的概念介绍清楚了,虽然有点啰嗦,但是应该是比较通俗易懂的。我们上面介绍的这种选取划分特征的算法也叫做ID3算法。下面来看西瓜书中对应的例子。

 

ID3算法

按照上面的套路,我们先取色泽作为划分特征,计算一下对应的信息增益。

 

首先,系统当前有8个好瓜,9个坏瓜,所以对应 信息熵为:

我们再选色泽作为划分特征,计算一下子集信息熵的期望:

其中:

带入上式,得:

再依次计算出其他特征对应的信息增益,取信息增益最大的那个特征作为首选条件,再如此继续划分下去,就可以得到一个树形结构的分支图,即我们要的决策树。

 

退出条件:

 

1.划分子集的信息熵为0;

 

2.无可用特征,取当前集合占比最大的作为标签。

 

下面我们用Python来实现。首先要把图4.1的文字转为csv文件的格式:

我们只要从csv里读取数据,就能进行后续的分析了。ID3的Python实现如下:

 

import numpy as np
import math
class DTree:
    def __init__(self, type=0):
        self.dataset = ''
        self.model = ''
    def load_data(self, data):
        dataset = np.loadtxt(data, delimiter=',', dtype=str)
        self.dataset = dataset
    def get_entropy(self, dataset):
        # 统计总数及正反例个数
        sum_num = len(dataset[1:])
        p1 = dataset[1:, -1].astype(int).sum() / sum_num
        p2 = 1 - p1
        # 如果p1或p2有一个为0,说明子集纯度为0,,直接返回0
        if p1==0 or p2==0:
            return 0
        # 使用公式计算信息熵并返回
        return -1*(p1*math.log2(p1) + p2*math.log2(p2))
    def get_max_category(self, dataset):
        pos = dataset[1:, -1].astype(int).sum()
        neg = len(dataset[1:, -1]) - pos
        return '1' if pos > neg else '0'
    def dataset_split(self, dataset, feature, feature_value):
        index = list(dataset[0, :-1]).index(feature)
        # 遍历特征所在列,剔除值不等于feature_value的行
        j = 0
        for i in range(len(dataset[1:, index])):
            if dataset[1:, index][j] != feature_value:
                dataset = np.delete(dataset, j+1, axis=0)
                j -= 1
            j += 1
        # 删除feature所在列
        return np.delete(dataset, index, axis=1)
    def get_best_feature(self, dataset, E):
        feature_list = dataset[0, :-1]
        feature_gains = {}
        for i in range(len(feature_list)):
            # 分别统计在每个特征值划分下的信息增益
            feature_values = np.unique(dataset[1:, i])
            feature_sum = len(dataset[1:, i])
            # 累加子集熵
            sub_entropy_sum = 0
            for value in feature_values:
                # 按值划分子集
                subset = self.dataset_split(dataset, feature_list[i], value)
                subset_sum = len(subset)
                # 计算子集熵
                sub_entropy = self.get_entropy(subset)
                # 权重
                w = subset_sum/feature_sum
                # 汇总当前特征下的子集熵*个数权重
                sub_entropy_sum += w*sub_entropy
            # 根据算公式计算信息增益
            feature_gains[feature_list[i]] = E-sub_entropy_sum
        # 返回最大信息增益对应的特征及索引
        max_gain = max(feature_gains.values())
        for feature in feature_gains:
            if feature_gains[feature] == max_gain:
                index = list(feature_list).index(feature)
                return feature, index
    def build_tree(self, dataset):
        # 计算数据集信息熵
        E = self.get_entropy(dataset)
        # 设置退出条件
        # 1.如果集合的信息熵为0,则返回当前标签
        if E == 0:
            return dataset[1][-1]
        # 2.特征数为1,说明无可划分特征,返回当前集合中占比最多的标签
        if len(dataset[0]) == 2:    # 特征+标签
            return self.get_max_category(dataset)
        # 获取最佳特征
        feature, index = self.get_best_feature(dataset, E)
        # 按特征划分子集
        tree = {feature:{}}
        # 获取特征值
        feature_values = np.unique(dataset[:, index][1:])
        # 按特征值划分子集
        for value in feature_values:
            subset = self.dataset_split(dataset, feature, value)
            subtree = self.build_tree(subset)
            tree[feature][value] = subtree
        return tree
    def train(self):
        self.model = self.build_tree(self.dataset)
        return self.model
    def predict(self, tree, testset):
        pass
dtree = DTree()
dtree.load_data('data4_1.csv')
tree_model = dtree.train()
print(tree_model)

 

分类结果:

缺点:如果把编号也作为样本特征的话,那幺它的信息增益为0.758,大于所有其他特征的信息增益,说明特征值种类越多,信息增益趋向于越大。

 

通过增益率改良后的C4.5算法

 

C4.5算法旨在消除这种由特征值种类差异所引起的“不平等待遇”。它引入了特征的“固有值”的概念,相当于对该特征的种类及数量计算信息熵。而这种“固有值”也拥有这种“不平等待遇”(种类越多,信息增益越大),所以两者相除,正好抵消了这种差异:

 

固有值的计算公式:

信息增益在C4.5算法下的计算公式:

由于C4.5与ID3的区别只是计算公式的不同,所以在获取最佳特征的函数get_best_feature()中稍作修改即可:

 

def get_best_feature(self, dataset, E):
    feature_list = dataset[0, :-1]
    feature_gains = {}
    for i in range(len(feature_list)):
        # 分别统计在每个特征值划分下的信息增益
        feature_values = np.unique(dataset[1:, i])
        feature_sum = len(dataset[1:, i])
        # 累加子集熵
        sub_entropy_sum = 0
        # 累加feature的固有值
        intrinsic_value = 0
        for value in feature_values:
            # 按值划分子集
            subset = self.dataset_split(dataset, feature_list[i], value)
            subset_sum = len(subset)
            # 计算子集熵
            sub_entropy = self.get_entropy(subset)
            # 权重
            w = subset_sum/feature_sum
            # 汇总当前特征下的子集熵*个数权重
            sub_entropy_sum += w*sub_entropy
            intrinsic_value += -1*(w*math.log2(w))
        # 根据算法类型选择对应的公式计算信息增益
        if self.type == 0:
            feature_gains[feature_list[i]] = E-sub_entropy_sum
        else:
            feature_gains[feature_list[i]] = (E-sub_entropy_sum)/intrinsic_value
    # 返回最大信息增益对应的特征及索引
    max_gain = max(feature_gains.values())
    for feature in feature_gains:
        if feature_gains[feature] == max_gain:
            index = list(feature_list).index(feature)
            return feature, index

 

得到的分类结果:

基尼系数和剪枝的内容待补充。。。

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注