04.决策树介绍

程序员文章站 2022-04-02 10:52:52

【数学基础】信息熵越低，纯度越高。信息熵通俗来说，就是用来度量包含的信息量，如果样本的属性都是一样的，那么它的信息就很单一没有差异化，相反，如果样本属性都不一样，那么它包含的信息就很多。其中信息熵公式如下：Ent(D)=−∑k=1∣y∣pk∗log2pkEnt(D)=-\displaystyle\sum_{k=1}^{|y|}p_k*log_2^{p_k}Ent(D)=−k=1∑∣y∣pk∗log2pkpk表示当前集合D中，第k类样本所占的比例。信息增益公式：Gain(D,a)=Ent(...

【数学基础】

多少信息使用信息量来衡量。信息的大小跟随机事件的概率有关，越小概率的事件发生了产生的信息量越大（比如湖南发生地震）；越大概率的时间发生了产生的信息量越小（比如太阳从东边升起来）。
$h (x)$ 可用来表示信息量：
当概率 $p (x)$ 为1发生，那么 $h (x) = 0$ ；
当概率 $p (x)$ 为0发生，那么 $h(x)=\infty$ ；
当概率 $p (x)$ 在0~1之间发生，那么 $h(x)=-log_2^{p(x)}$ ；
信息量度量的是一个具体的事件发生了所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望，即所有可能发生事件所带来的信息量的期望：
$H(X)=-\displaystyle\sum_{i=1}^{n}p(x_i) * log_2^{p(x_i)}$
伯努利分布下的信息熵：（当随机变量只取两个值，例如0和1）
$H(P)=-(p * log_2^p + (1 - p) * log_2^{(1-p)})$
期望与平均数的关系：平均数是实验后根据实验结果统计得到的样本的平均值；而期望是实验之前根据概率分布预测的样本的平均值。
信息熵越低，纯度越高。信息熵通俗来说，就是用来度量包含的信息量，如果样本的属性都是一样的，那么它的信息就很单一没有差异化，相反，如果样本属性都不一样，那么它包含的信息就很多。其中信息熵公式如下：
$Ent(D)=-\displaystyle\sum_{k=1}^{|y|}p_k*log_2^{p_k}$
pk表示当前集合D中，第k类样本所占的比例。

【ID3算法】

信息增益公式：
$Gain(D,a)=Ent(D)-\displaystyle\sum_{v=1}^{V}\frac{|D^v|}{|D|}*Ent(D^v)$
简单一句话就是：划分前的信息熵–划分后的信息熵。表示的是向纯度方向迈出的“步长”。
原理：在根节点处计算信息熵，然后根据属性依次划分并计算其节点的信息熵，使用根节点信息熵 - 属性节点信息熵 = 信息增益，根据信息增益降序排列，排在前面的就是第一个划分的属性，其后以此类推，这样就得到决策树的形状。

【信息增益示例】

描述：以西瓜数据集为例，该数据集包含17个训练样本，结果有2个类别|y| = 2，其中正例占 $p_1=\frac{8}{17}$ ，反例占$p_2=\frac{9}{17}。

根节点信息熵计算为：
$-\displaystyle\sum_{k=1}^2p_k*log_2^{p_k}$
$p_1*log_2^{p_1} + p_2*log_2^{p_2})$
$-(\frac{8}{17}*log_2^{\frac{8}{17}} + \frac{9}{17}*log_2^{\frac{9}{17}})$
$= 0.998$
以属性“色泽”为例，对应3个数据子集，分别为：
$D^1(色泽=青绿)，D^2(色泽=乌黑)，D^3(色泽=浅白)$
子集 $D^1$ 包括编号为{1,4,6,10,13,17}的6个样本，其中正例 $p_1=\frac{3}{6}$ ，反例占 $p_2=\frac{3}{6}$ ， $D^2D^3$ 同理计算，这3个节点的信息熵分别为：
$Ent(D^1)=-(\frac{3}{6}*log_2^{\frac{3}{6}}+\frac{3}{6}*log_2^{\frac{3}{6}})=1.000$
$Ent(D^2)=-(\frac{4}{6}*log_2^{\frac{4}{6}}+\frac{2}{6}*log_2^\frac{2}{6})=0.918$
$Ent(D^3)=-(\frac{1}{5}*log_2^{\frac{1}{5}}+\frac{4}{5}*log_2^\frac{4}{5})=0.722$
属性“色泽”的信息增益为：
$Gani(D,色泽)=Ent(D)-\displaystyle\sum_{v=1}^3\frac{|D^v|}{D}*Ent(D^v)$
(以上v代表1、2、3，所以就是 $D^1|D^2|D^3$ )
$=0.998-(\frac{6}{17}*1.000+\frac{6}{17}*0.918+\frac{5}{17}*0.722)=0.109$
采用同样的方式计算其他属性的信息增益：
$G a n i (D, 根蒂) = 0.143$
$G a n i (D, 敲声) = 0.141$
$G a n i (D, 纹理) = 0.381$
$G a n i (D, 脐部) = 0.289$
$G a n i (D, 触感) = 0.006$

import numpy as np
import pandas as pd
import math

datasets = pd.read_csv('./xigua.csv', sep=' ')
total_nums = datasets.shape[0]
print(datasets.shape)

#cal entropy
def cal_entropy(good_melon_nums, bad_melon_nums):
    total_nums = good_melon_nums + bad_melon_nums
    prob_good = good_melon_nums / total_nums
    prob_bad = bad_melon_nums / total_nums
    log_prob_good = (math.log(prob_good, 2) if prob_good != 0 else 0)
    log_prob_bad = (math.log(prob_bad, 2) if prob_bad != 0 else 0)
    entropy = round(-(prob_good * log_prob_good + prob_bad * log_prob_bad), 3)
    print('entropy = %0.3f' %(entropy))
    return entropy

#cal condition entropy
def cal_condition_entropy(datasets):
    good_melon_nums = datasets.loc[datasets.好瓜 == '是'].shape[0]
    bad_melon_nums = datasets.loc[datasets.好瓜 == '否'].shape[0]
    print('good melon nums %d, bad melon nums %d.' %(good_melon_nums, bad_melon_nums))

    entropy = cal_entropy(good_melon_nums, bad_melon_nums)

    training_datas = datasets.iloc[:, 1:-1]
    column_names = training_datas.columns
    gain_feature_dict = {}
    for column in training_datas:
        feature_datas = datasets[[column, '好瓜']]
        #print(feature_datas)
        feature_dict = {}
        for p_value in feature_datas.values:
            feature_value = p_value[0]
            label_value = p_value[1]
            if feature_value not in feature_dict:
                feature_dict[feature_value] = {label_value:1}
            else:
                feature_value_dict = feature_dict[feature_value]
                if label_value not in feature_value_dict:
                    feature_value_dict[label_value] = 1
                else:
                    feature_value_dict[label_value] = feature_value_dict.get(label_value) + 1
        feature_ent = 0.0
        #print(feature_dict)
        for value in feature_dict.values():
            feature_sum = sum(value.values())
            prob_good = value.get('是', 0) / feature_sum
            prob_bad = value.get('否', 0) / feature_sum
            log_prob_good = (math.log(prob_good, 2) if prob_good != 0 else 0)
            log_prob_bad = (math.log(prob_bad, 2) if prob_bad != 0 else 0)
            ent_dv = -(prob_good * log_prob_good + prob_bad * log_prob_bad)
            feature_ent += (feature_sum / total_nums) * ent_dv
        gain_DV = round(entropy - feature_ent, 3)
        print('Gain(%s,D) = %0.3f' %(column, gain_DV))
        gain_feature_dict[gain_DV] = column

    max_gain = max(gain_feature_dict.keys())
    gain_feature = gain_feature_dict.get(max_gain)
    print('max gain feature = %s' %(gain_feature))

cal_condition_entropy(datasets)

(17, 8)
good melon nums 8, bad melon nums 9.
entropy = 0.998
Gain(色泽,D) = 0.109
Gain(根蒂,D) = 0.143
Gain(敲声,D) = 0.141
Gain(纹理,D) = 0.381
Gain(脐部,D) = 0.290
Gain(触感,D) = 0.007
max gain feature = 纹理

根据上面计算的所有属性的信息增益相比，其中“纹理”信息增益最大，所以被选为划分属性：
然后再对每个分支节点做进一步划分，计算方式跟上面一样，最终得到整个决策树。不过信息增益有一个问题，对于可取值数目较多的属性有所偏好，例如：考虑将“编号”作为一个属性。为了解决这个问题，引出另外一个算法C4.5；
疑问：为什么针对信息增益，会偏向特征取值数目多的属性？
因为根据公式，当特征取值数目越多时，对应的分支节点权重*分支信息熵求和（ $\displaystyle\sum_{k=1}^V\frac{|D^v|}{|D|}*Ent(D^v)$ ）就会越小，相应的整个信息增益就越大，所以特征取值数目越多，信息增益越大。

【实战案例】

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter
import math
from math import log

def create_data():
    datasets = [['青年', '否', '否', '一般', '否'],
               ['青年', '否', '否', '好', '否'],
               ['青年', '是', '否', '好', '是'],
               ['青年', '是', '是', '一般', '是'],
               ['青年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '好', '否'],
               ['中年', '是', '是', '好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '好', '是'],
               ['老年', '是', '否', '好', '是'],
               ['老年', '是', '否', '非常好', '是'],
               ['老年', '否', '否', '一般', '否'],
               ]
    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']
    # 返回数据集和每个维度的名称
    return datasets, labels

class Node:
    def __init__(self, root=True, label=None, feature_name=None, feature=None):
        '''
            1.叶子节点：label
            2.中间节点：条件（特征）[条件1]子节点；[条件2]子节点
            是否为叶子节点
        '''
        self.root = root # 是否为叶子节点
        self.label = label # 叶子节点所有样本的标签
        self.feature_name = feature_name # 切分条件
        self.feature = feature # 切分条件
        self.tree = {} # [条件1]子节点 node_son
        self.result = {
            'label:': self.label,
            'feature': self.feature,
            'tree': self.tree
        }

    def __repr__(self):
        return '{}'.format(self.result)

    def add_node(self, val, node):
        '''训练过程使用'''
        self.tree[val] = node

    def predict(self, features):
        '''
            features->预测数据的特征
            预测过程
        '''
        if self.root is True:
            return self.label
        return self.tree[features[self.feature]].predict(features)

# 树的根节点 Node

class DTree:
    '''
        建树过程
    '''
    def __init__(self, epsilon=0.1):
        self.epsilon = epsilon # 超参数
        self._tree = {}

    # 熵
    @staticmethod
    def calc_ent(datasets):
        data_length = len(datasets)
        label_count = {}
        for i in range(data_length):
            label = datasets[i][-1]
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        ent = -sum([(p / data_length) * log(p / data_length, 2)
                    for p in label_count.values()])
        return ent

    # 经验条件熵
    def cond_ent(self, datasets, axis=0):
        data_length = len(datasets)
        feature_sets = {}
        for i in range(data_length):
            feature = datasets[i][axis]
            if feature not in feature_sets:
                feature_sets[feature] = []
            feature_sets[feature].append(datasets[i])
        cond_ent = sum([(len(p) / data_length) * self.calc_ent(p)
                        for p in feature_sets.values()])
        return cond_ent

    # 信息增益
    @staticmethod
    def info_gain(ent, cond_ent):
        return ent - cond_ent

    def info_gain_train(self, datasets):
        count = len(datasets[0]) - 1
        ent = self.calc_ent(datasets)
        best_feature = []
        # 遍历特征
        for c in range(count):
            c_info_gain = self.info_gain(ent, self.cond_ent(datasets, axis=c))
            best_feature.append((c, c_info_gain))
        # 比较大小
        best_ = max(best_feature, key=lambda x: x[-1])
        return best_

    def train(self, train_data):
        """
        input:数据集D(DataFrame格式)，特征集A，阈值epc
        output:决策树T
        """
        """
            不断返回子树node，上级调用可以直接将子树node填在自己的.tree的dict里
            递归过程结束：返回叶子节点
            每次递归调用的train_data，都是上一级tree的节点下发下来的子数据集
        """
        _, y_train, features = train_data.iloc[:, :-1], train_data.iloc[:, -1], train_data.columns[:-1]
        # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T
        if len(y_train.value_counts()) == 1:
            return Node(root=True, label=y_train.iloc[0])

        # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T
        if len(features) == 0:
            return Node(
                root=True,
                label=y_train.value_counts().sort_values(
                    ascending=False).index[0])

        # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征
        max_feature, max_info_gain = self.info_gain_train(np.array(train_data))
        max_feature_name = features[max_feature]

        # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T
        if max_info_gain < self.epsilon:
            return Node(
                root=True,
                label=y_train.value_counts().sort_values(
                    ascending=False).index[0])

        # 5,构建Ag子集
        node_tree = Node(
            root=False, feature_name=max_feature_name, feature=max_feature)

        feature_list = train_data[max_feature_name].value_counts().index
        for f in feature_list:
            sub_train_df = train_data.loc[train_data[max_feature_name] == f].drop([max_feature_name], axis=1)

            # 6, 递归生成树
            sub_tree = self.train(sub_train_df)
            node_tree.add_node(f, sub_tree)

        return node_tree

    def fit(self, train_data):
        self._tree = self.train(train_data)
        return self._tree

    def predict(self, X_test):
        return self._tree.predict(X_test)

datasets, labels = create_data()
data_df = pd.DataFrame(datasets, columns=labels)
dt = DTree()
tree = dt.fit(data_df)
print(true)
predict_label = dt.predict(['老年', '否', '否', '一般'])
print(predict_label)

{‘label:’: None, ‘feature’: 2, ‘tree’: {‘否’: {‘label:’: None, ‘feature’: 1, ‘tree’: {‘否’: {‘label:’: ‘否’, ‘feature’: None, ‘tree’: {}}, ‘是’: {‘label:’: ‘是’, ‘feature’: None, ‘tree’: {}}}}, ‘是’: {‘label:’: ‘是’, ‘feature’: None, ‘tree’: {}}}}
‘否’

【C4.5算法】

为了解决信息增益问题，引出信息增益率，计算公式如下：
$Ganiratio(D,a)=\frac{Gani(D,a)}{IV(a)}$
( $a$ 代表某个属性，可以理解为 $D^v$ ，只是 $D^v$ 是被拆分的属性对应的特征值种类)
其中：
$Gani(D,a)=Ent(D)-\displaystyle\sum_{v=1}^V\frac{|D^v|}{|D|}*Ent(D^v)$
$IV(a)=-\displaystyle\sum_{v=1}^V\frac{|D^v|}{|D|}*log\frac{|D^v|}{|D|}$
( $D$ 代表所有集合， $D^v$ 代表某个属性， $v$ 代表这个属性的不同特征值，比如“色泽”属性分为3个特征类型值青绿、乌黑、浅白)
属性 $a$ 的取值可能越多（即V越大），则 $I V (a)$ 的值通常就越大。信息增益率本质：是在信息增益的基础上乘上一个惩罚参数，当特征个数较多（即 $a$ 的取值较多），那么 $I V (a)$ 越大，对应的惩罚参数就越小（根据公式惩罚参数为 $I V (a)$ 的倒数）；相反，当特征个数较少，惩罚参数就越大。基于此点还有一个缺点：信息增益率偏向取值较少的特征。
疑问：为什么信息增益率偏向取值较少的特征？
是因为特征取值较少时，惩罚参数越大，根据公式对应的信息增益取值就会越大，在选择划分属性时，同样也是选择信息增益率最高的特征，此时自然也就偏向取值少的特征了。
基于以上所说的缺点，在使用信息增益率时，并不是直接选择信息增益率最大的特征，而是在现在候选特征中找出信息增益高于平均水平的特征，然后再在这些特征中选择信息增益率最高的特征。

【CART算法】

另一个表示纯度的方法，叫做基尼指数：
$Gini(D)=1-\displaystyle\sum_{k=1}^{|y|}p_k^2$

表示在样本集合中，一个随机选中的样本被分错的概率。例如：在一个袋子里面有3种不同颜色的求若干，伸手进去掏出2个球，颜色不一样的概率。基尼指数能够反应复杂度，一个袋子掏出两个颜色不一样的球，那么概率就为 $p * (1 - p)$ ；
基尼指数的目的是降低复杂度，需要使基尼指数越小，让数据集的纯度越高；
熵和基尼指数都是越小，纯度就越高。与熵相比，没有log，计算量会比较小，对数计算慢；
如果使用基尼指数取替代熵，做一个近似化的修正，也不会有太大的精度上的损失，同时也比较快；
基尼指数是为了修正前面ID3/C4.5算法的缺点而诞生的（CART分类和回归树）；
不过基尼指数只能度量分类问题，回归是使用均方误差进行度量；
CART用于只有2个子树，是一个二叉树。

举例：假设有特征“学历”属性，有三个特征取值：本科、硕士、博士，当使用学历这个特征对样本集合D进行划分时，划分值分别有3个，因而有3种划分的可能集合，划分后的子集如下：

划分点：本科，划分后子集：{本科} {硕士，博士}
划分点：硕士，划分后子集：{硕士} {本科，博士}
划分点：博士，划分后子集：{博士} {本科，硕士}

对于上面的每一种划分，都可以计算出基于划分特征=某个特征值将将样本集合D划分为两个子集的纯度：
$Gini(D,a)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度 $Gini(D,a_i)$ （ $a_i表示特征a的可能取值$ ），然后从所有划分的 $Gini(D,a_i)$ 中找出基尼指数最小的划分，那么这个划分的划分点，就是使用特征a对样本集合D进行划分的最佳划分点。依次类推，就可以长成一颗大树。

【3种不同决策树对比】

ID3：特征取值越多的属性，更容易使数据更纯，其信息增益越大，所以训练的是一颗庞大且深度浅的树，不太合理；
C4.5：采用信息增益率替代信息增益；
CART：以基尼系数替代熵，最小化不纯度，而不是最大化信息增益；

当前ID3/C4.5已淘汰，CART是核心被使用的比较多（梯度提升树以及随机森林就是使用CART决策树）。

本文地址：https://blog.csdn.net/LWY_Xing/article/details/110550057

相关标签：自然语言处理机器学习决策树算法 python

上一篇： opencv-python图像预处理后处理记录

下一篇： L1-027 出租（20 分)

04.决策树介绍

【数学基础】

【ID3算法】

【信息增益示例】

【实战案例】

【C4.5算法】

【CART算法】

【3种不同决策树对比】

Mysql中Identity 详细介绍

Velocity基本语法介绍

MyBatis入门介绍(超简单)

详解Mybatis通用Mapper介绍与使用

Java编程中避免equals方法的隐藏陷阱介绍

iOS 配置.gitignore文件详细介绍

IOS Bundle详细介绍及使用方法

Java中的同步与异步详细介绍

天猫超市优惠券怎么免费领取？天猫超市10元优惠券领取方法介绍

IOS 打包静态库详细介绍