学习笔记： 机器学习经典算法-决策树（Decision Tress）

决策树是一种用于分类和回归任务的 非参数监督学习算法。该算法在于基于训练数据生成一个树形的决策结构。树形的决策结构的执行逻辑由根节点、分支、内部节点和叶节点组成。其中每个节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后的每个叶节点代表一种判别结果。基于树形判别结构，决策树天然地用于解决多分类问题（分类决策树）。决策树同时也能够解决回归问题，回归数值最后由样例所进入的叶子节点内的训练样本取均值可得（回归决策树）。决策树基于属性判断的特点，也使得决策树的输出结果具有非常好的可解释性。

在处理数值特征的分类问题的时候，决策树算法会为每个节点上选择某一个特征和特征阈值建立判断条件和判断输出建立决策树。【生成一棵决策树的关键在于 如何为每个判断节点选取合适的特征和特征阈值 作为数据的划分依据。】

1、信息熵建树的策略

1.1 信息熵简介

在信息论中，信息熵（information entropy，香农熵）提出用来量化度量一个系统的混乱程度(不确定程度)。熵越大，有数据的不确定性越高；熵越小，有数据的不确定性越低。

$$ H = -\sum_{i=1}^{k} p_i(\log(p_i))$$

$p_i$描述了一个系统内某类事件发生的概率，简单理解为系统内一类群体的比例。

关于信息熵所度量的系统混乱程度的直观理解
对于包含3个类群($a,b,c$)系统，

• 系统A内个类群的占比均匀，$A\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\}$；
• 系统B内个主要是包含类群$c$，$B\{\frac{1}{10},\frac{2}{10},\frac{7}{10}\}$；
• 系统C内全部都是类群$a$，$C\{1,0,0\}$；

在A系统里由于3个类群($a,b,c$)的比例都是均匀的，从A系统里任抽出一个样本其实很难判断它的类别。在B系统里由于主要包含了类群$c$，所以从B系统里任抽出一个样本就有很大的概率可以确定它是$c$类。在C系统里由于只有类群$a$，所以从C系统里任抽出一个样本就知道它一定是$a$类。从而计算三个系统各自的信息熵可得 $H(A) = 1.1,H(B) = 0.8,H(C) = 0; H(A) > H(B)> H(C)$。

1.2 基于 信息熵 搜索决策节点

将数据集视作一个系统，分类任务实则是根据规则将系统内的所有样本根据类群进行归类，归类后形成的子系统相比原始系统具有最高的确定性，所以 分类过程本质是使得原系统的信息熵变低的过程 。据此，在生成决策树的决策条件的时候，就可以通过被当前决策条件划分出来的子系统的总信息熵来判断一个决策条件的好坏。搜索数据集里每个可能的划分组合（特征和对应特征阈值），划分结果具有最小系统信息熵的划分组合即当前系统的一个最优划分条件。

1.2 信息熵数据划分策略的 python 实现

def split(X,y,d,value): ### 用于返回基于给定特征和特征阈值的数据集划分结果
    return X[X[:,d] <= value],X[X[:,d] > value],y[X[:,d] <= value],y[X[:,d] > value]


def entropy(y): ### 返回一个系统的信息熵
    from collections import Counter
    from math import log
    counters = Counter(y)  ### 对系统内各类别的样本进行计数
    res = 0.0
    for num in counters.values(): 
        p = num / len(y) ### 计算系统内各类样本的占比
        res += -p * log(p)
    return res

def search_DecisionCondition(X,y):
    import numpy as np
    best_entropy = float('inf') ### 初始一个用于比较迭代的熵值
    best_d,best_value = -1,-1   ### 初始化一个用于迭代的决策特征和特征value
    for d in range(X.shape[1]): ### 对数据集的所有特征进行遍历
        sorted_idx = np.argsort(X[:,d]) #### 对当前遍历的样本特征，按照特征value大小顺序排序
        for i in range(1,len(X)): #
            if X[sorted_idx[i-1],d] != X[sorted_idx[i],d]:
                v = np.mean([X[sorted_idx[i-1],d],X[sorted_idx[i],d]])  #### 当前被搜索样本特征的决策阈值的可选择范围为顺序排列后两两样本的均值进行搜索
                X_A,X_B,y_A,y_B = split(X,y,d,v) ### 基于当前的 d和value 组合划分数据集
                e = entropy(y_A) + entropy(y_B)  ### 基于当前的 d和value 组合划分后数据集的信息熵
                if e < best_entropy: 
                    best_entropy,best_d,best_value = e,d,v
    return best_entropy,best_d,best_value


from sklearn import datasets
X = datasets.load_iris().data[:,2:]
y = datasets.load_iris().target

search_DecisionCondition(X,y)

决策树的建立基于二叉树的构建方式，具体设计方案依赖数据算法与结构的学习，有待学习更新。。。。

1.3 在sklearn中训练基于信息熵的决策树模型

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(max_depth=2,criterion="entropy",random_state = 666) ### sklearn 中生成决策树有一定的随机因素，建议固定随机种子保证结果的可重复性
dt_clf.fit(X,y)

2、基尼系数 建树的策略

基尼系数 与 信息熵的作用一致，本质是用来量化度量一个系统的混乱程度。基尼系数 对系统混乱程度的描述方式是对于在系统内任意抽出的两个不同类别样本的概率，这个概率（基尼系数）越低意味着系统的确定性越高。
$$ G = 1- \sum_{i=1}^{k}{p_i^2}$$

基尼系数与信息熵的差异 主要在于，前者 的平方运算 相比后者的log运算要快。这也是 scikit-learn中默认使用基尼系数 生成决策树的原因。除此之外二者对模型的性能贡献几乎没有优略之分。

基尼系数的python实现

def gini(y): ### 基尼系数
    from collections import Counter
    from math import log
    counters = Counter(y)  ### 对系统内各类别的样本进行计数
    res = 1.0
    for num in counters.values(): 
        p = num / len(y) ### 计算系统内各类样本的占比
        res -= p**2
    return res

应用基尼系数(G)搜索决策条件的实习测量同以上信息熵搜索策略。

2.2 在sklearn中训练基于基尼系数的决策树模型

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(max_depth=2,criterion="gini")
dt_clf.fit(X,y)

3、决策树的过拟合问题

在训练决策树模型建树的过程中，如果不对建树过程进行限制，建树时就会根据系统混乱程度最小化原则持续创建数据集划分节点，直到最后所有叶节点的信息熵(或基尼系数)为零，生成一棵复杂度超高的决策树模型。

3.2 防止决策树过拟合- 常用剪枝策略

① 限制建树深度
建树深度限制的指的是当最多为添加几层判断条件，注意建树深度过浅容易发生欠拟合。

对应sklearn 决策树模型超参数 max_depth

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(max_depth=2)
dt_clf.fit(X,y)

② 限制节点大小
该方法指的是只有当前节点内包含样本数满足一定数量才能被进一步划分。

对应sklearn 决策树模型超参数 min_samples_split

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(min_samples_split =  10)
dt_clf.fit(X,y)

③ 限制叶子节点包含的样本量
该方法主要是限制了最后叶子节点里应包含的最少样本数目，这个数目太少容易发生过拟合。
对应sklearn 决策树模型超参数 min_samples_leaf

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(min_samples_leaf =  6)
dt_clf.fit(X,y)

④ 限制叶子节点的数量
对应sklearn 决策树模型超参数 max_leaf_nodes

from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(max_leaf_nodes=  6)
dt_clf.fit(X,y)

4、决策树的回归处理方案

在分类问题中，新样例的预测标签由新样例所进入的决策树叶子节点内的样本投票产生。同理用决策树处理问题中，新样例的预测标签也由新样例所进入的决策树叶子节点内所有样本的标记值取均值得出：

回归决策树同样基于对数据集的持续划分进行建树，与分类树的熵最小化划分策略不同，回归决策树寻找的划分特征和划分阈值在于使得划分后的两个集合的 方差和最小，其实是 MSE的变相理解（具体可参考博客 Regression Trees），所以 回归决策树的建树过程在于使得使得划分后各子集内的方差之和最小化。

5、决策树的局限性

① 可能无法真实反映数据分布
决策树做决策的时候由于每次只是在一个特征轴和特征阈值上对数据集进行判别归类，表现在决策边界上就是每个决策节点对于的决策边界都是垂直与一条特征轴的，这样的决策边界存在无法真实反映数据分布的可能。

② 决策树算法可能对于个别样本点极度敏感
具体体现在，如果训练集内样本数量发生改变，决策树的决策边界将发生巨大变化。

在机器学习领域，决策树的主要应用是使用集成学习创建随机森林。