机器学习之决策树

一、什么是决策树

相关名词

• 信息熵
• 信息增益和信息增益率
• 剪枝、预剪枝和后剪枝
• 过拟合
• 根节点和叶节点
  （关于这些名词涉及的具体算法本文不会多谈，详情请参阅周志华先生的《机器学习》）

1.1 决策树简介

决策树（decision tree）是一类常见的机器学习方法，一个简单的决策树如下图：

简单的决策树

一般的，一棵决策树包含一个根节点，若干个内部结点和若干个叶节点；叶节点对应决策结果，其他节点则对应一个属性测试；每个结点包含样本集合根据属性测试的结果被划分到子结点中；根节点包含样本全集。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单而直观的“分而治之”的策略。（摘自周志华的《机器学习》）

决策树可分为分类决策树和回归决策树，分类决策树有ID3决策树和C4.5决策树，回归决策树有CART决策树，其中C4.5和CART属于十大数据挖掘算法之二。

1.2 优缺点

• 优点：计算复杂度不高，分类规则易于理解，准确度较高；
• 缺点：在构造树的过程中需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效，另外可能会产生过拟合的问题。

二、如何构造一个决策树

在谈如何构造决策树之前，我们需要先简单了解一下信息熵、信息增益和信息增益率。

信息熵指的是信息混乱程度，熵越大，信息混乱程度越高，纯度越低。比如A = [1, 2, 3, 4, 5]，B = [1, 1, 1, 1, 2]，A的熵就比较高，B的熵就比较低。信息熵的计算公式如下图：

信息熵

对A进行计算，假设每个值的取值概率为0.2，则A的信息熵为5（0.2log2(0.2)）=2.3219，而B的信息熵是1.49446。

信息增益指的是经过一个决策结点信息熵的变化量，信息增益越大，纯度提升越大。

不同于ID3使用信息增益，C4.5使用信息增益率，避免了用信息增益选择属性时偏向取值多的属性的问题。信息增益率的公式如下，其中D为信息熵。

信息增益率

构造决策树的一个要点就是如何选择结点，我们需要使用信息增益最大的结点。

使用决策树的基本想法是随着树深度的增加，节点的熵迅速的降低。熵降低速度越快越好，这样我们有望得到一个高度最矮的决策树。

三、剪枝

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这是就可能因训练样本学得太好了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，我们需要主动去掉一些分支来降低过拟合的风险，而剪枝是决策树学习算法对付过拟合的主要手段。

剪枝分为“预剪枝”和“后剪枝”。预剪枝是指在构造决策树的过程中边构造边剪枝，在决策每个结点之前先估计其对决策树性能的效果，若不能就停止决策该节点并划为叶节点。后剪枝指的是先生成一个决策树，然后从上而下的考察非叶节点并剪枝。

四、Talk is cheap, show me code.

• from sklearn.tree import DecisionTreeClassifier

# 运行于Jupyter Notebook
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn import datasets
sns.set()

#加载鸢尾花的数据
iris = datasets.load_iris()
data = pd.DataFrame(iris.data,columns=iris.feature_names)
data['target'] = iris.target

tmp = pd.DataFrame({"target":[0,1,2],
                   "target_name":iris.target_names})

data = pd.merge(data,tmp,on='target')
data = data.drop(['target'],axis=1)

sns.pairplot(data.dropna(),hue='target_name')

irisPairplot

# 训练数据和分类
train_data = data.drop(['target_name'],axis=1)
train_class = data['target_name']

#调用sklearn的决策树方法
from sklearn.tree import DecisionTreeClassifier
# 创建决策树模型
decision_tree_classifier = DecisionTreeClassifier()
# 训练决策树
decision_tree_classifier.fit(train_data,train_class)
# 查看决策树的准确率
decision_tree_classifier.score(train_data,train_class)

详解DecisionTreeClassifier

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=None,
    class_weight=None,
    presort=False,
)

主要参数

• criterion : 'gini'或者'entropy', 前者是基尼系数，后者是信息熵。两种算法差异不大对准确率无影响，信息墒运算效率低一点，因为它有对数运算.一般说使用默认的基尼系数”gini”就可以了，即CART算法。除非你更喜欢类似ID3, C4.5的最优特征选择方法。
• splitter : 'best' or 'random', 前者是在所有特征中找最好的切分点 后者是在部分特征中，默认的”best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐”random” .
• max_depth : int or None, optional (default=None) 一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。常用来解决过拟合。
• min_samples_split : 如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分，如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
• min_samples_leaf : 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝，如果样本量不大，不需要管这个值，大些如10W可是尝试下5。
• max_features : None（所有），在划分数据集时考虑的最多的特征值数量。
• min_weight_fraction_leaf : 这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
• max_leaf_nodes : 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制具体的值可以通过交叉验证得到。
• min_impurity_decrease : 节点划分最小不纯度。默认值为‘0’；用来限制决策树的增长，如果某节点的不纯度（基尼系数，信息增益，均方差，绝对差）小于这个阈值，则该节点不再生成子节点。
• min_impurity_split : 这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值则该节点不再生成子节点。即为叶子节点 。
• class_weight : 指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重，如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。
• presort : bool，默认是False，表示在进行拟合之前，是否预分数据来加快树的构建。对于数据集非常庞大的分类，presort=true将导致整个分类变得缓慢；当数据集较小，且树的深度有限制，presort=true才会加速分类。

主要属性

• n_classes_ : 列出类数目
• classes_ : 列出类标签
• feature_importances_ : 列出每一维特征的重要性
• n_features_ : 特征数目

主要方法

• fit() : 训练模型
• get_params() : 获取参数表的参数
• predict() : 返回预测的结果
• score() : 返回准确率

五、回归

决策树也可以执行回归任务

from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X,y)

参数max_depth越大，拟合效果越好，但其值过大时会造成过拟合。

六、其他

通过组合多个决策树可以创建随机森林，随机森林可以获得更好的分类结果。sklearn中的相关方法为：

• from sklearn.ensemble import BaggingClassifier
• from sklearn.ensemble import RandomForestRegressor
  （第二个是随机森林回归器）