决策树算法概论及python实现

发布于 2021-08-30  1681 次阅读


决策树算法概述

决策树(decision tree)是一种常用的有监督算法,之所以名字中带有“树”,因为其算法的实现过程类似于一棵树的生长过程,它从根部(根节点)出发,住不到进行分支(内部节点),最终到一片片末端的树叶(叶结点)。在决策树里,所有的训练样本构成了根节点,每个内部节点对应一个特征(属性)测试,用来区分不同标签的样本,经过特征测试后,这个节点包含的所有样本根据特征测试的结果划分到下一层的子结点中,层层细化,最终形成若干个叶子节点,即最终的分类结果。

一旦构造的决策树,对新样本进行分类就相当容易了,具体做法是,从树的根节点开始,测试新样本中相应的特征,根据结果选择恰当的分支路线,沿着该路线到达最终的叶节点后,就得到了该样本的分类结果。

决策树在贷款申请的信用风险评估、医疗诊断等领域应用十分广泛,主要原因在于决策树的每一步划分都能产生一系列的规则,很容易被建模人员和业务人员理解,而这些规则经过稍加整理后就能很容易形成业务策略。另外,决策树可以处理高维的数据,对极端值和缺失值有很强的稳健性。

决策树算法有很多类型,其中最大的差别就是最优特征选择的方法不同。最优特征指的是,在每个结点处,如何选择最好的特征(属性)对样本进行分类,这里最佳的意义即经过这步划分,能使分类精度最好,知道这棵树能准确分类所有训练样本。通常特征选择的方法有信息增益、信息增益比、基尼指数等,对应3种最常用的决策树实现算法,分别是ID3算法、C4.5算法和CART算法。

CART算法和基尼指数

分类回归树算法

CART(classification and regression tree)分类回归树由L.Breiman,J.Friedmin,R.Olshen和C.Stone于1984年提出,它可以用于分类任务,也可以应用于回归任务。
CART算法形成的决策树是一颗二叉树,在每次进行划分时,它都会把当前样本集划分为两个子样本集,生成两个分支,因此每一步的划分决策只能是“是”或“否”,及使用来划分的特征有多个取值,也是处理后二分。在划分时,CART每次都是针对单个变量进行划分,并且这个变量可能重复使用,在划分后,CART还会采用交叉验证法进行剪枝。
因此,决策树的关键在于从所有样本特征中选择出每个节点上的最佳特征,使得决策树的分类精度可以最高,而决策树的生长过程实际就是不断把样本集进行分割的过程,每次分割都要求被分到一个分支(或叶子)上的样本间的差异最小,而不同分枝(或叶子)之间的差异最大。这个差异的指标被称为“不纯性”。CART使用的不纯性度量指标是基尼指数。

基尼指数

基尼指数(Gini index)是一种不等性度量,通常用来度量收入不平衡,也可以用来度量任何不均匀分布,是一个介于0~1的实数。基尼指数代表了不纯度,基尼指数越小,则样本的不纯度越低,特征越好。
在分类问题中,假设有K个类别,第k个类别的概率为 P_k ,则基尼指数的表达式为:

Gini(P) = \sum_{k=1}^{K}P_k(1-P_k) = 1-\sum_{k=1}^{K}p_k^2


若是二分类问题,计算就更简单了,如果属于第一个样本输出的概率是 p ,则基尼指数的表达式为:

Gini(p) = 2p(1-p)


对于给定样本D,假设有K个类别,第k个类别的数量为 C_k ,则样本D的基尼指数的表达式为:

Gini(D) = 1 - \sum_{k=1}^K (\frac{|C_k|}{|D|})^2


特别地,对于样本D,如果根据特征A的某个值a,把D分为 D_1D_2 两部分,则在特征A的条件下,D的基尼指数表达式为:

Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) +\frac{|D_2|}{|D|}Gini(D_2)


如此,CART算法基于最小化基尼指数的原则,得出当前样本集上最优的划分,生成两个子节点,将当前训练样本集分配到这两个节点中,完成一次划分。整个决策树构建的过程即不断递归这一步骤,直到满足一定条件为止。

算法过程

  1. 设节点处的训练数据集为D,计算现有特征对该数据集的基尼指数。此时对每一个特征A,对其可能取的每个值a,根据样本点对 A=a 的测试为“是”或“否”,将D分割成 D_1D_2 两部分,利用基尼指数计算公式计算。
  2. 在所有可能的特征A及它们所有可能的切分点a中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依据最优特征和最有切分点,从当前节点生成两个子节点,将训练数据集依特征分配到两个子结点中去。
  3. 对两个子节点递归地调用(1)~(2),直到满足停止条件。
  4. 生成CART决策树。

算法停止计算的条件是节点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值,亦或没有更多特征。

优缺点

优点

  1. 产生的决策树模型非常直观,能直接生成判断规则,方便业务角度的理解。
  2. 数据不需要预处理和标准化。
  3. 对于数据的分布没有严格规定。
  4. 对于缺失值和异常值较健壮、受影响较小。
  5. 可以帮助其他算法挑选重要的特征变量,发现那些特征对分类最有价值。
  6. 可以轻松处理多分类问题。

缺点

  1. 很容模在训练数据中生成复杂的树结构,从而造成过拟合,模型泛化能力不强。
  2. 会因为样本发生一点点的改动,导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

python实现

from sklearn import tree
from sklearn.datasets import load_iris
from IPython.display import Image
import pydotplus

# 载入数据集
iris = load_iris()

'''建立决策树模型。criterion表示最优特征的选择方法,这里是Gini指数,其他可调的参数:书的最大深度,叶节点允许的最少样本数,内部节点允许的最少样本数。'''
clf = tree.DecisionTreeClassifier(criterion = 'gini')
clf = clf.fit(iris.data, iris.target)

# 将模型结构保存下来
dot_data = tree.export_graphviz(clf, out_file=None)

# 显示模型结构
graph = pydotplus.graphviz.graph_from_dot_data(dot_data)
Image(graph.create_png())

可以看到,在最上方(即根节点),我们一共有150个样本(sample=150),3个类别各有50个样本(value=[50,50,50])。在根节点处的最优特征是X[2],即第三个特征,最有切分点是否<=2.45。根据这给判断规则,所有样本被分为两个子类别,左侧类别的基尼指数为0.0,表示这个类别的不纯度已经为0,即说明这个节点中所有样本都已经属于同一个类别,所以可以直接当作叶节点。右侧类别的基尼指数为0.5,还可以继续划分,我们看到CART树不断分支,直到分类后每个结点的基尼指数为0为止。

扩展:

剪枝

剪枝可以分为前剪枝和后剪枝,前剪枝即在决策树生成之前就人为定义好树的层数,以及每个节点允许的最少样本数,而且在给定的节点不再分裂。后剪枝指的是先让决策树充分生长,然后剪掉部分子树,用树叶替换删掉的节点。
CART算法采用的后剪枝方法,他先生成一颗完整的树,然后产生所有可能的剪枝过的CART树,在使用交叉验证来检验剪枝后的预测能力,选择泛化预测能力最好的剪枝后的树作为最终的CART树。

K层交叉验证

首先计算出整体的决策树T,叶结点个数记作N,设i属于[1, N]。对每个i,使用k层交叉验证方法衡量决策树,并裁剪到i个节点,计算错误率,最后求出平均错误率。这样可以用具有最小错误率对应的i作为最终决策树的大小,对原始决策树进行裁剪,得出最优决策树。

随机森林

随机森林使用训练数据随机计算出许多决策树,形成一个由多个决策树构成的“森林”,然后用这个森林对未知数据进行预测,选取投票最多的分类作为分类结果。实践证明,此算法的错误率会比一般的决策树低。一棵树预测正确的概率可能不高,但是集体中大多数预测正确的概率却很高。