机器学习算法理论与实践——决策树_csdn机器学习决策树算法头歌

一、基本思想

  决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。决策树是一个预测模型，代表的是对象属性与对象值之间的一种映射关系。

  决策树的基本流程如下

即按属性不断的对样本进行划分，直到每个叶结点都只包含同一类的样本

二、规则及数学推导

1.划分选择

  关键是如何选择最优划分属性，随着划分过程不断进行，希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度(purity)越来越高。

（1）信息增益

1）信息熵：
  假定当前样本集合$D$中第$k$类样本所占比例为$p_k(k=1,2,\dots ,|Y|)$，则$D$的 信息熵(information entropy) 定义为
$$Ent(D)=-\sum _{k=1}^{|Y|}{p}_k{\log }_2{p}_k$$
$Ent(D)$的值越小，则$D$的纯度越高。
  假定离散属性a有V个可能的取值 { a 1 , a 2 , … , a V } \{a^1,a^2,\dots,a^V\} {a1,a2,…,aV}，其对样本集D进行划分会产生V个分支结点，$D^v$表示第v个分支结点的样本（D中在属性a上取值为$a^v$的样本），每个分支包含的样本数不同，给分支结点赋予权重$\frac{|D^v|}{|D|}$，即样本数越多的分支结点影响越大，则 信息增益(information gain) 定义为
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
  信息增益越大，意味着用属性a来进行划分获得的"纯度提升"越大。ID3决策树学习算法以信息增益为准则来选择划分属性。

（2）增益率

  如果一个属性划分的每个分支只包含1个样本，即这些分支结点的纯度已达最大，则该属性的信息增益显然是最大的，但这样的决策树显然不具有泛化能力。
  信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好带来的影响，产生了 增益率(gain ratio)
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},\text{其中}IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$
称为属性a的"固有值"(intrinsic value)，属性a的取值越多，则IV(a)值通常越大。
  C4.5算法采用信息增益率来选择划分属性，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

（3）基尼指数

1）基尼值
  数据集D的纯度可用基尼值来度量
$$Gini(D)=\sum _{i=1}^{|Y|}\sum _{k^{\prime }̸=k}{p}_k{p}_{k^{\prime }}=1-\sum _{i=1}^{|Y|}{p}_k^2$$
公式推导：
$$\begin{gathered} \sum _{i=1}^{|Y|}\sum _{k^{\prime }̸=k}{p}_k{p}_{k^{\prime }}=\sum _{i=1}^{|Y|}{p}_k\sum _{k^{\prime }̸=k}{p}_{k^{\prime }} \\ =\sum _{i=1}^{|Y|}{p}_k(1-p_k) \\ =1-\sum _{i=1}^{|Y|}{p}_k^2 \end{gathered}$$
$Gini(D)$反映了从数据集D中随机抽取两个样本，其类别不一致的概率，$Gini(D)$越小，数据集D的纯度越高。
2）基尼指数
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$
CART决策树(Classification and Regression Tree) 使用基尼指数来选择划分属性，即在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性
$$a_{\ast }=\arg \underset{a\in A}{\min }Gini\_index(D,a)$$

2.剪枝处理

  因为决策树的学习过程中，经常会产生过多的分支，导致过拟合，所以剪枝(pruning)是决策树算法对付过拟合的手段。
  决策树剪枝的基本策略有"预剪枝"和"后剪枝"。

1. 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。因为预剪枝直接停止了后续的划分，但更后续的划分可能会显著提高泛化能力，所以预剪枝可能导致欠拟合。
2. 后剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。后剪枝通常比预剪枝保留更多的分支，欠拟合风险小，但时间开销要大得多。

对泛化性能的评估可以用"验证集"

3.连续与缺失值

（1）连续值处理

  C4.5决策树算法中采用的二分法。
  给定样本集D和连续属性a，a在D上有n个不同的取值，将这n个取值从小到大排序，记为 { a 1 , a 2 , … , a n } \{a^1,a^2,\dots,a^n\} {a1,a2,…,an}，基于划分点t可将D分为子集$D_t^{-}$（在属性a上取值<=t的样本）和$D_t^{+}$（在属性a上取值>t的样本）。可得包含n-1个元素的候选划分点集合
T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } T_a=\{\dfrac{a^i+a^{i+1}}{2}|1\leq i\leq n-1\} Ta​={2ai+ai+1​∣1≤i≤n−1}
对该集合可以像离散属性值一样来考察。例如对于最优的信息增益
G a i n ( D , a ) ∗ = m a x t ∈ T a &ThickSpace; G a i n ( D , a , t ) = m a x t ∈ T a &ThickSpace; E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) Gain(D,a)_*=max_{t\in T_a}\;Gain(D,a,t)\\ =max_{t\in T_a}\;Ent(D)-\sum_{\lambda\in\{-,+\}}{\dfrac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda)} Gain(D,a)∗​=maxt∈Ta​​Gain(D,a,t)=maxt∈Ta​​Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)

（2）缺失值处理

  给定数据集D和属性a，令$\tilde{D}$表示D中在属性a上没有缺失值的样本子集。假定属性a有V个可取值 { a 1 , a 2 , … , a V } \{a^1,a^2,\dots,a^V\} {a1,a2,…,aV}，令${\tilde{D}}^v$表示$\tilde{D}$中在属性a上取值为$a^v$的样本子集，令${\tilde{D}}_k$表示$\tilde{D}$中属于第k类$(k=1,2,\dots ,|Y|)$的样本子集，显然有$\tilde{D}={\bigcup }_{k=1}^{|Y|}{\tilde{D}}_k={\bigcup }_{v=1}^V{\tilde{D}}^v$，为每个样本x赋予一个权重$w_x$，并定义
$$\begin{gathered} \rho =\frac{{\sum }_{x\in \tilde{D}}{w}_x}{{\sum }_{x\in D}{w}_x}, \\ {\tilde{p}}_k=\frac{{\sum }_{x\in {\tilde{D}}_k}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x}(1\le k\le |Y|), \\ {\tilde{r}}_v=\frac{{\sum }_{x\in {\tilde{D}}^v}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x}(1\le v\le V) \end{gathered}$$
$\rho$表示无缺失值样本所占的比例，${\tilde{p}}_k$表示无缺失值样本中第k类所占的比例，${\tilde{r}}_v$表示无缺失值样本中在属性a上取值$a^v$的样本所占的比例。显然${\sum }_{k=1}^{|Y|}{\tilde{p}}_k=1,{\sum }_{v=1}^V{\tilde{r}}_v=1$。

  信息增益可推广为
$$\begin{gathered} Gain(D,a)=\rho \times Gain(\tilde{D},a) \\ =\rho \times (Ent(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v)) \end{gathered}$$
其中
$$Ent(\tilde{D})=-\sum _{k=1}^{|Y|}{\tilde{p}}_k{\log }_2{\tilde{p}}_k$$
在决策树学习开始阶段，根结点中各样本的权重初始化为1。在划分过程中，若样本x在属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为$w_x$；若样本x在属性a上的取值未知（即为缺失值），则将x同时划入所有子结点，且样本权值在与属性值$a^v$对应的子结点中调整为${\tilde{r}}_v\cdot w_x$。直观的看，就是将属性值缺失的样本以不同的概率划入到不同的子结点中去。

4.多变量决策树

  把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本对应了d维空间中的一个数据点，对样本分类即为在坐标空间中寻找不同类样本之间的分类边界，这些分类边界由若干个与坐标轴平行的分段组成。

  平行分段划分时间开销大，若使用斜的划分边界可以大大简化。

此时非叶结点不再仅对某个属性，而是对属性的线性组合进行测试。如下图

三、sklearn包中的DecisionTreeClassifier

  sklearn中关于实现决策树的类是sklearn.tree.DecisionTreeClassifier，官方文档：https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier
  下面是该类各参数、属性和方法的介绍，基本翻译自官方文档：

sklearn.tree.DecisionTreeClassifier(criterion=‘gini’, splitter=‘best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=0.0000001, class_weight=None, presort=False)

1.参数解释：

1. criterion：字符串，可选参数。指定选择划分属性的方法。可选方法有
   (1) ‘gini’(默认)：使用基尼指数。
   (2) ‘entropy’：使用信息增益。
2. splitter：字符串，可选参数。指定划分点的策略。
   (1) ‘best’(默认)：在特征的所有划分点中找出最优的划分点。适合样本量小的情况。
   (2) ‘random’：随机的在部分划分点中找出局部最优的划分点。适合样本量大的情况。
3. max_depth：整数或None，可选参数，默认值为None。指定决策树的最大深度。如果为None，则决策树会完全生长至每个叶结点完全纯净(只包含同类样本)或者所有叶结点的样本数均小于参数min_samples_split。本参数旨在避免过拟合，在样本量大，特征数多的情况下可以使用。
4. min_samples_split：整数或浮点数，可选参数，默认值为2。对内部结点进行划分时，指定内部结点所包含的最小样本数。
   (1) 整数：表示最小的样本数量
   (2) 浮点数：表示一个比例，且 向上取整(比例*样本数) 表示最小的样本数量
5. min_samples_leaf：整数或浮点数，可选参数，默认值为1。叶结点包含的最小样本数量。该参数表示如果一个结点划分后其左右分支包含的样本数不小于min_sample_leaf时，才考虑对其进行划分。
   (1) 整数：表示最小的样本数量
   (2) 浮点数：表示一个比例，且 向上取整(比例*样本数) 表示最小的样本数量
6. min_weight_fraction_leaf：浮点数，可选参数，默认为0.。指定叶子结点所有样本权重和的最小值，小于该值则其被剪枝，即其父结点不进行划分，默认值为0表示不考虑权重问题。当样本缺失值较多或样本类别分布偏差很大时，会引入样本权重，此时需要考虑本参数值。
7. max_features：整数、浮点数、字符串或None，可选参数。指定寻找最优划分属性时允许考虑的最大特征数量。
   (1) 整数：max_features表示考虑的最大特征数量
   (2) 浮点数：表示一个比例，向下取整(比例*特征数) 为考虑的最大特征数量
   (3) ‘auto’：max_features = sqrt(特征数)
   (4) ‘sqrt’：max_features = sqrt(特征数)
   (5) ‘log2’：max_features = log2(特征数)
   (6) None(默认)：max_features = 特征数
     注意，在至少有一个有效划分结点样本找到之前，对最优划分属性的搜寻不会停止，即使设置了本参数，仍然会超过限制特征数量去搜寻。
8. random_state：可选参数。设定随机种子。
   (1) 整数：random_state是随机数生成器使用的种子
   (2) RandomState实例：random_state是随机数生成器
   (3) None(默认)：随机数生成器是np.random使用的RandomState实例
9. max_leaf_nodes：整数或None，可选参数，默认值为None。指定最大叶结点数量，旨在限制复杂度避免过拟合。None表示不限制叶结点数量。
10. min_impurity_decrease：浮点数，可选参数，默认值为0.。当一个结点划分后的纯度增长大于等于该参数值时，才将该结点进行划分。纯度增长公式为$\frac{N_t}{N\ast (\text{impurity}-N_{t_R}/N_t\ast \text{right\_impurity}-N_{t_L}/N_t\ast \text{left\_impurity})}$，其中$N$表示样本数量，$N_t$表示当前结点样本数量，$N_{t_L}$表示划分后的左分支的样本数量，$N_{t_R}$表示划分后的右分支的样本数量（如果权重参数传入了，则所有数量均加权）。
11. min_impurity_split：浮点数，默认值为1e-7。纯度阈值，如果一个结点的纯度大于该值则划分，否则该结点即为叶结点。
12. class_weight：指定各类别的权重。
    (1) 字典：形如{class_label: weight}
    (2) 字典列表：对于多结果分类问题，需要为每个类别单独设置权重，比如4分类问题，权重应设置为[{0: 1, 1: 1}, {0: 1, 1: 5}, {0: 1, 1: 1}, {0: 1, 1: 1}]而不是[{1:1}, {2:5}, {3:1}, {4:1}]
    (3) ‘balanced’：每个类别的权重与实际样本中的比例成反比，权重计算公式为$\frac{\text{n\_samples}}{(\text{n\_classes * np.bincount(y))}}\text{np.bincount表示每个类别计数}$
    (4) None(默认)：每个类别的权重都一样
    如果fit方法中sample_weight指定了，则类别权重会跟样本权重(sample_weight)相乘。
13. presort：布尔值，可选参数，默认值为False。指定是否预先对数据进行排序。数据集较大时，预先排序可能会降低训练速度；数据集较小或者限制了数的深度时，则会提升训练速度。

注意：由于在划分的时候特征是随机排列的，因此尽管数据集相同，每次得到的最优划分属性也不一定相同，为了避免这种情况，random_state必须固定。

2.属性解释：

1. classes_：数组，shape[分类数]。分类类别的列表。
2. feature_importances_：数组，shape[分类树]。各特征的重要程度列表。
3. max_features_：整数。同参数当中的max_features。
4. n_classes_：整数或列表。类别数量。
5. n_features_：整数。特征数量。
6. n_outputs_：整数。叶结点包含的结果类型。
7. tree_：Tree对象。

3.方法解释：

1. apply(self,X[, check_input])：
   根据训练出来的决策树，返回输入样本预测进入的叶结点编号。
   参数：
   $\bullet$ X: shape[样本数, 特征数]。要预测的样本矩阵。
   $\bullet$ check_input：布尔值，默认为True。是否检查输入值。
   返回值：
   $\bullet$ 数组，shape[样本数,]。每个样本返回其预测进入的叶结点编号，叶结点会按[0:叶节点数]进行编号。
2. decision_path(self, X, check_input=True)：
   根据训练出来的决策树，返回输入样本预测进入的叶结点的路径。
   参数：
   $\bullet$ X: shape[样本数, 特征数]。要预测的样本矩阵。
   $\bullet$ check_input：布尔值，默认为True。是否检查输入值。
   返回值：
   $\bullet$ 稀疏矩阵，shape(样本编号, 叶结点编号)。表示了样本进入叶结点的路径。
3. fit(self, X, y, sample_weight=None, check_input=True, X_idx_sorted=None)：
   训练模型构建决策树。
   参数：
   $\bullet$ X：shape(样本数, 特征数)，自变量
   $\bullet$ y：shape(样本数,)，因变量，整数或字符串
   $\bullet$ sample_weight：shape(样本数, )，可选参数。每个样本的权重，如果不设置，则每个样本权重一样。选择结点进行拆分时，若该结点是零权重或负权重则会被忽略，如果拆分后的子结点会变为负权重，则该结点也会被忽略。
   $\bullet$ check_input：布尔值，默认为True。是否检查输入值。
   $\bullet$ X_idx_sorted：数组，shape[样本数, 特征数]，可选参数。训练样本的排序编号。如果多棵树建立在同一数据集上，该参数允许在树之间缓存顺序编号。如果不设置该参数，则不缓存。
   返回值：
   $\bullet$ 实例对象
4. get_depth(self)：
   返回树的深度。(树深度是根节点到所有叶结点的距离中的最大值)
5. get_n_leaves(self)：
   返回叶结点的数量。
6. get_params(self, deep=True)：
   以字典返回模型的参数值。参数deep默认为True，还会返回包含的子模型的参数值。
7. predict(self, X, check_input=True)：
   根据模型的训练，返回预测值。
   参数：
   $\bullet$ X: shape[样本数, 特征数]
   $\bullet$ check_input：布尔值，默认为True。是否检查输入值。
   返回值：
   $\bullet$ 数组，shape [样本数] or shape[样本数, 包含结果数]
8. predict_log_proba(self, X)：
   返回X中每一个样本预测为各个分类的对数概率
   参数：
   $\bullet$ X: shape[样本数, 特征数]
   返回值：
   $\bullet$ 数组，shape[样本数, 分类数]
9. predict_proba(self, X, check_input=True)：
   返回X中每一个样本预测为各个分类的概率
   参数：
   $\bullet$ X: shape[样本数, 特征数]
   返回值：
   $\bullet$ 数组，shape[样本数, 分类数]
10. score(self, X, y, sample_weight=None)：
    根据给定的测试数据X和分类标签y返回预测正确的平均准确率。可以用于性能度量，返回模型的准确率，参数为x_test，y_test。
    $\bullet$ 参数：X,y,sample_weight
    $\bullet$ 返回值：浮点数
11. set_params(self, **params)：
    设定参数。

四、实例

1.数据来源

  本例所用数据集为sklearn自带的iris(鸢尾花卉)数据集。

2.数据概况

  该数据集共150个样本，包含4个特征分别为Sepal Length（花萼长度）、Sepal Width（花萼宽度）、Petal Length（花瓣长度）、Petal Width（花瓣宽度），共分为3类分别为Setosa（山鸢尾）、Versicolour（变色鸢尾）、Virginica（维吉尼亚鸢尾）。数据样例如下

3.代码实现

  sklearn 的 DecisionTreeClassifier 仅提供了预剪枝，所以本例采取了网格搜索法确定最佳的参数（max_depth、min_samples_split、min_samples_leaf）。决策树生成后，还使用了Graphviz绘制了决策树。Graphviz的安装及使用详见 https://www.cnblogs.com/shuodehaoa/p/8667045.html

from sklearn.datasets import load_iris
from sklearn import tree
from sklearn import model_selection
from sklearn.model_selection import GridSearchCV
import graphviz

# 加载iris数据集
iris = load_iris()
# 拆分为训练集和测试集
x_train, x_test, y_train, y_test = model_selection.train_test_split(iris.data, iris.target, test_size=0.25,
                                                                    random_state=1234)

# 使用网格搜索法，尝试不同组合（最大深度、分支最小样本量、叶节点最小样本量）
# 根据经验，数据量较小时树的最大深度可设置10以内，较大时则需设置比较大的树深度，如20左右
max_depth = [2, 3, 4, 5, 6]
min_samples_split = [2, 4, 6, 8]
min_samples_leaf = [2, 4, 8, 10, 12]
parameters = {'max_depth': max_depth, 'min_samples_split': min_samples_split, 'min_samples_leaf': min_samples_leaf}
# 网格搜索法，测试不同的参数值
grid_dtcateg = GridSearchCV(estimator=tree.DecisionTreeClassifier(), param_grid=parameters, cv=10)
# 模型拟合
grid_dtcateg.fit(x_train, y_train)
# 返回最佳参数组合
print('最佳参数组合为：', grid_dtcateg.best_params_)

# 构建分类决策树
dt = tree.DecisionTreeClassifier(max_depth=grid_dtcateg.best_params_['max_depth'],
                                 min_samples_leaf=grid_dtcateg.best_params_['min_samples_leaf'],
                                 min_samples_split=grid_dtcateg.best_params_['min_samples_split'], random_state=1234)
# 模型训练
dt.fit(x_train, y_train)
# 模型评估
print('模型准确率为：', dt.score(x_test, y_test))

# 绘制决策树
dot_data = tree.export_graphviz(dt, out_file=None, feature_names=iris.feature_names, class_names=iris.target_names,
                                filled=True, rounded=True, special_characters=True)
graph = graphviz.Source(dot_data)
graph.render('iris')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

运行可得最终结果如下

绘制的决策树如下

4.决策树详解

  在网上搜寻了很久，发现很少有讲到最后绘制的这个决策树，各个部分的具体意思是什么。于是博主决定在这里详细的讲解一下。

  以根结点为例

• 第一行表明该结点划分属性是petal length，petal length<=2.6的样本划分到左分支，反之的划分到右分支；
• 第二行表明该结点的纯度gini=0.666，由于本例使用默认的’gini’，因此此处是基尼指数，如果使用’entropy’，则此处为信息增益；
• 第三行表明该结点包含的样本量samples=112；
• 第四行表明该结点所包含的样本在3个分类上的数量value = [37, 35, 40]，即这112个样本，属于3个类别的数量分别为37、35、40；
• 第五行表明样本流入该结点应判断为哪个类别，可以看到这个类别由该结点包含的样本决定，即哪个类别的样本量多，就判断为哪个类别。根结点第3类的样本数最多，为40，所以类别判断为virginica。

  下面我们以一个具体的样本来看一下决策树是如何判断其所属类别的。

  从根结点开始，划分属性为Petal Length，样本的Petal Length为2.7>2.6，因此流入右分支；第二层划分属性为Petal Width，样本的Petal Width为1.5<1.65，因此流入左分支；第三层划分属性为Petal Length，样本的Petal Length为2.7<4.95，因此流入左分支；第四层就是叶结点了，刚才流入的左分支，因此最终的分类就是Versicolour。

参考文献：
[1]周志华.《机器学习》.清华大学出版社,2016-1
[2]https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier