决策树

最编程 2024-10-02 14:38:18

...

决策树（decision tree）

决策树特点

决策树是一个 if - else 规则集合，从根节点到叶子节点的一条路径，构成一条规则。
所有规则具备一个重要性质：互斥并且完备。
节点：内部节点和叶子节点。内部节点表示一个特征。叶子节点对应一个决策结果。

解决的问题

分类
回归

优点

易于理解，模型可读性强
分类速度快，决策待见： $O(log_2m)$ ,m 为样本特征数。
既可以处理离散值也可以处理连续值。很多算法只是专注离散值或者连续值。
相比其他算法需要更少的特征工程（比如：不需要特征标准化，可以很好处理字段缺失值，不用关心特征间是否相互依赖，自动组合多个特征）
可以处理多维度输出的分类问题。
对于异常点的容错能力好，健壮性高。
可以交叉验证的剪枝来选择模型，从而提高泛化能力。

缺点：

非常容易过拟合，导致泛化能力不强。
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

比较幸运的是，防止过拟合的方法很多：

限制树的最大深度
限制叶子节点的最少样本数量。
限制节点分裂时的最小样本数量。
吸收 bagging 的思想对训练样本采样（subsample），使用部分训练样本进行训练单棵树。
借鉴随机森林的思想在学习单棵树时，只采用一部分特征。
在目标函数中添加正则项，惩罚复杂的树结构。

决策树学习步骤

特征选择
决策树的生成
决策树的修剪

常见的决策树算法

ID3 算法：使用信息增益，寻找最优特征
C4.5 算法：使用信息增益比，寻找最优特征
CART（classification and regression tree）算法：使用基尼系数，寻找最优特征。

生成决策树

决策树的生成是一个递归过程，递归选择最优特征，并根据该特征对训练数据进行划分，使每个子数集有一个最好的分类。

递归过程中，有三种情况会导致递归结束。

当前节点包含的样本全属于一个类别，无需再划分。
当前属性集为空，或者所有样本在所有属性上取值相同，无法划分。
当前节点包含的样本集合为空，不能划分。

输入：训练集 $D = [\,(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\,]$

属性集 $ = [, a_1,a_2,…,a_d ,] $

TreeGenerate( D , A )

生成节点 node

if D 中样本全属于同一类别 C:

将 node 标记为 C 类的叶子节点

return

if len(A) == 0 or D 中样本在 A 上取中相同：

将 node 标记为叶子节点，其类别标记为 D 中样本最多的类。

return

从 A 中选择出最优划分属性： $a_*$

for $a_*$ in $a_*^v$ ：

为 node 生成一个分支，令 $D_v = $ D 中在 $a_*$ 上取中为 $a_*^v$ 的样本子集。

if len( $D_v$ ) == 0:

将分支节点标记为叶子节点，其类别标记为 D 中样本最多的类。

return

else:

TreeGenerate( $D_v, A / {a_*}$ )

return node

决策树代码

# 决策树
import math

class DecisionTree():
    def create_tree(self, data_set, labels):
        class_list = [example[0] for example in data_set]
        # data_set 中的样本，类别完全相同，停止划分
        if class_list.count(class_list[0]) == len(class_list):
            return class_list[0]
        # 只有一个特征
        if len(labels) == 0 or len(data_set[0]) == 1:
            return self.majority_count(class_list)

        # 选择最优特征划分
        best_feat = self.choose_best_feature(data_set)
        best_feat_label = labels[best_feat]
        my_tree = {best_feat_label: {}}
        del (labels[best_feat])

        feat_value_set = set([example[best_feat] for example in data_set])
        for value in feat_value_set:
            sub_labels = labels[:]
            sub_list = self.split_data_set(data_set, best_feat, value)
            if len(sub_list) == 0:
                my_tree[best_feat_label][value] = self.majority_count(class_list)
            else:
                my_tree[best_feat_label][value] = self.create_tree(sub_list, sub_labels)

        return my_tree

    # 样本中类别最多
    @staticmethod
    def majority_count(class_list):
        class_count = {}
        for vote in class_list:
            class_count[vote] += class_count.get(vote, 0) + 1
        return sorted(class_count.items(), key=lambda x: x[1], reverse=True)[0][0]

    # 使用增益率进行特征选择
    def choose_best_feature(self, data_set):
        num_features = len(data_set[0]) - 1
        base_ent = self.calc_shannon_ent(data_set)
        best_info_gain_ratio = 0.0
        best_feature = -1

        for i in range(num_features):
            feat_set = set(example[i] for example in data_set)
            new_ent = 0.0
            split_info = 0.0
            for value in feat_set:
                sub_data_set = self.split_data_set(data_set, i, value)
                prod = len(sub_data_set) / float(len(data_set))
                new_ent += prod * self.calc_shannon_ent(sub_data_set)
                split_info += -prod * math.log2(prod)
            info_gain = base_ent - new_ent
            if info_gain == 0: continue

            info_gain_ratio = info_gain / split_info
            if info_gain_ratio > best_info_gain_ratio:
                best_info_gain_ratio = info_gain_ratio
                best_feature = i

        return best_feature

    # 计算熵：
    @staticmethod
    def calc_shannon_ent(data_set):

        label_count = {}
        for feat_vec in data_set:
            label = feat_vec[0]
            label_count[label] = label_count.get(label, 0) + 1

        shannon_ent = 0.0
        n = len(data_set)
        for label, count in label_count.items():
            prob = float(count) / n
            shannon_ent -= prob * math.log(prob, 2)
        return shannon_ent

    # 离散型特征，分隔数据集
    @staticmethod
    def split_data_set(data_set, axis, value):
        result = []
        for feat_vec in data_set:
            if feat_vec[axis] != value: continue
            result.append(feat_vec[:axis] + feat_vec[axis + 1:])
        return result

特征选择

决策树生成过程，一个关键步骤，选择最优特征进行划分。

我们希望决策树的分支节点包含的样本属于同一类别，即节点的“纯度”（purity）越来越高。

信息增益

信息熵（information enthropy）

熵度量事物的不确定性，越不确定的事物，它的熵越大。

$-\sum_{i=1}^{n}{p_i log_2 p_i}$

n：X 的 n 种不同的离散值
$p_i$ ：X 取值为 i 的概率

$Ent(D) $ 的值越小，D 的纯度越高。

例子：假设 X 有两个取值A，B。P(A) =0.5，P(B) =0.5。

那么 X 具有的不确定性： $Ent(X)=-(0.5*log_2{0.5}+0.5*log_2{0.5})=log_2{2}=1$

假设 X 有两个取值A，B。P(A) =1/3，P(B) =2/3。

那么 X 具有的不确定性： $Ent(X)=-(\frac{1}{3}*log_2{\frac{1}{3}}+\frac{2}{3}*log_2{\frac{2}{3}})$

$=\frac{1}{3}log_23-\frac{2}{3}log_2\frac{2}{3}$

$=log_23-\frac{2}{3}log_23-\frac{2}{3}log_2{\frac{2}{3}}$

$=log_23-\frac{2}{3}(log_23+log_2{\frac{2}{3}})$

$=log_23-\frac{2}{3}log_22$

$=log_23-\frac{2}{3}<log_22=1$

P(A) =1/3，P(B) =2/3 比 P(A) =1/2，P(B) =1/2 确定性大。

熵只与 X 的分布有关，与 X 取值无关

    def calc_shannon_ent(data_set):
        label_count = {}
        for feat_vec in data_set:
            label = feat_vec[0]
            label_count[label] = label_count.get(label, 0) + 1

        shannon_ent = 0.0
        n = len(data_set)
        for label, count in label_count.items():
            prob = float(count) / n
            shannon_ent -= prob * math.log(prob, 2)
        return shannon_ent

联合熵

多个变量的联合熵

$-\sum_{x_i \in X}\sum_{y_i \in Y}{p(x_i,y_i)log_2{p(x_i,y_i)}}$

条件熵

条件熵类似条件概率，它度量了已知 X 后，剩下 Y 的不确定性。

$-\sum_{x_i \in X}\sum_{y_i \in Y}{p(x_i,y_i)log_2{p(x_i|y_i)}}=\sum_{j=1}^np(y_i)H(X|y_i)$

信息增益

H(X) 度量了 X 的不确定性。

H(X|Y) 度量了，已知 Y 后 X 剩下的不确定性

H(X) - H(X|Y) 什么能度量什么？

韦恩图

H(X)：左边的椭圆
H(Y)：左边的椭圆
I (X ,Y)互信息或者信息增益：两个椭圆交集
H( X , Y)：两个椭圆并集
H(X|Y)
H(Y|X)

$G ain (X, Y) = H (X) - H (X ∣ Y)$

$\frac{|D^v|}{|D|}$ 加权：每个分支数量不一样。

信息增益特点：对可取值数目较多的属性有偏好。

决策树中信息增益等价于训练数据集中类与特征的互信息。

增益率

为了克服信息增益：对可取值数目较多的属性有偏好。使用增益率。

Gain_ratio(D,a) = $\frac{Gain(D,a)}{IV(a)}$

$-\sum_{i=1}^{n}{\frac{|D_i|}{|D|}log{\frac{|D_i|}{|D|}}}$ 模仿信息熵。

n 是特征 A 取值的个数。

增益率特点：对可取值数目较少的属性有偏好。

    def choose_best_feature(self, data_set):
        num_features = len(data_set[0]) - 1
        base_ent = self.calc_shannon_ent(data_set)
        best_info_gain_ratio = 0.0
        best_feature = -1

        for i in range(num_features):
            feat_set = set(example[i] for example in data_set)
            new_ent = 0.0
            split_info = 0.0
            for value in feat_set:
                sub_data_set = self.split_data_set(data_set, i, value)
                prod = len(sub_data_set) / float(len(data_set))
                new_ent += prod * self.calc_shannon_ent(sub_data_set)
                split_info += -prod * math.log2(prod)
            info_gain = base_ent - new_ent
            if info_gain == 0: continue

            info_gain_ratio = info_gain / split_info
            if info_gain_ratio > best_info_gain_ratio:
                best_info_gain_ratio = info_gain_ratio
                best_feature = i

        return best_feature

基尼指数

基尼值

$=\sum_{k=1}^K{p_k*（1-p_k)}=1-\sum_{k=1}^Kp_k^2$

Gini(D) 越小，则数据集 D 的纯度越高。

基尼指数：

$Gini\_index(D,a) = \sum_{i=1}^n{\frac{|D_i|}{|D|}Gini(D_i)}$

在属性集合 A 中，选择那个使得划分后基尼指数最小的特征，作为最优化划分特征。

预测

    def classify(self, input_tree, feat_lables, text_vec):
        first_str = list(input_tree.keys())[0]
        second_dict = input_tree[first_str]
        feat_index = feat_lables.index(first_str)
        for key in second_dict.keys():
            if text_vec[feat_index] == key:
                if type(second_dict[key]).__name__ == "dict":
                    class_label = self.classify(second_dict[key], feat_lables, text_vec)
                else:
                    class_label = second_dict[key]
        return class_label

上一篇： Android studio 配置 AVD 虚拟机

下一篇： [Python] 2.变量和数据类型 - 3.数据类型

决策树

生成决策树

特征选择

信息增益

增益率

基尼指数

预测

决策树

决策树损失函数公式的详细说明和示例图解

探索决策树模型-2. 揭秘决策树的训练过程

【阿旭教你玩转机器学习实战12课】：决策树基础原理、构建与实际应用详解

决策树（ID3、C4.5、C5.0、CART 算法）和条件推理决策树 R 语言实现

ENVI 扩展工具：基于 CART 算法-安装方法的自动决策树分类：

IV.分类算法--决策树

使用决策树法进行投标决策

分析模型案例研究：决策树分析--决策制定的常用分析工具

Spark 上的决策树（Decision Tree On Spark）