Python教程

「机器学习算法的数学解析与Python实现」决策树分类算法

本文主要是介绍「机器学习算法的数学解析与Python实现」决策树分类算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

决策树分类:用if-else进行选择

目前数据竞赛中排名靠前的算法除了深度学习系列之外,机器学习算法基本上都是选用XGBoostLightgbm算法,而这两者的基石都是决策树分类算法

决策树的简单来说就是if-else层层相套的判断结构,同时也是数据结构中典型的树形结构。决策树这一类算法,基本原理都是用一长串的if-else完成样本分类,区别主要在纯度度量等细节上选择了不同的方案。

决策树算法的核心要点就是如何选择判断条件来生成判断分支,也就是生成if-else分支,称为节点划分节点分裂

决策树有以下重点概念:

  • 决策树的分类方法
  • 分支节点划分
  • 纯度度量

程序员的选择观:if-else

假定待分类的数据集有A、B、C三个特征维度,同时每个特征维度只有“是”和“否”两种赋值,要进行二元分类。如下所示:

album_temp_1612598084

经过简单分析发现,只有在A、B、C三个特征维度值都是“是”的情况下,样本才为正类,只要出现一个“否”,样本就被归为负类。

if-else进行判别的伪代码大概如下:

把上面的伪代码画成流程图,就能够看到一颗典型的二叉树。

如何构建一棵树

在编程中,if-else的判断条件是由程序员写的,而在机器学习中,判断条件只能算法自己生成。

如何选择决策条件

从目标来看,我们希望分类后的结果杂质越少越好,也就是越纯越好,所以引入了“纯度”的概念。集合中归属同一类别的样本越多,我们就说这个集合的纯度越高。

度量纯度方法的不同,就产生了不同的决策树算法,最著名的有三种:

  • ID3:信息增益
  • C4.5:增益率
  • CART:基尼指数

纯度有三点要求:

  • 当一个分支下的所有样本都属于同一个类时,纯度最高;
  • 当一个分支下样本所有的类别一半正类一半负类时,纯度最低;
  • 纯度考察的是同一个类的占比,并不在乎该类为正负类,即无论是正类占70%,还是负类占70%,纯度的值应该是一样的。

把上面三点汇总,可以得到一个函数图像:

纯度函数的函数图像

而由于在机器学习中更习惯使用“损失值”,而纯度越大则损失越小,所以函数图像应该是相反的:

决策树的剪枝问题

决策树分类容易出现过拟合,而“剪枝”正是为了解决这个问题。剪枝根据触发时间不同,可分为:

  • 预剪枝:在分支划分之前就判断是否需要剪枝;
  • 后剪枝:决策树划分完成之后再进行剪枝操作。

是否剪枝遵循一个原则:如果剪枝后模型在验证集上效果更好,则进行剪枝,否则不剪枝。

决策树分类的算法原理

基本思路

决策树进行分类的主要流程:首先选取一个特征维度作为“根结点”,然后不断进行分裂,直到达到停止分裂条件。

停止分裂的三种条件:

  • 到达终点:当前集合的样本都属于同一类时;
  • 自然停止:决策树依赖特征维度作为判别条件,如果特征维度用完了,自然也就无法继续分裂。如果此时分类还没完成,那就就以占比最大的类别作为当前节点的归属类别。
  • 选不出来:极端情况下是不同特征维度的提纯效果完全一样。

以上三种是算法自带的停止条件,实际使用中也可以通过设置外部阈值,比如决策树的深度,叶子节点的个数等作为停止条件。

数学解析

1.信息熵(Information Entropy)

"熵"是热力学概念,用于表示无序程度。信息熵用于衡量不确定性的程度,不确定性(通过概率来理解)越大,则信息熵越大。

信息熵的数学表达式:

\[H(X) = - \sum_{k=1}^N p_k \log_2(p_k) \]

\(p\) 表示概率,\(X\) 表示进行信息熵计算的集合。

以信息熵计算两种极端情况。在二元分类中,如果当前样本都属于同一类别a,即 \(p_a=1, p_b=0\),则信息熵为:

\[H(X) =-(1 \times \log_21 + 0 \times \log_20) = 0 \]

由于只有一种类别,所以不确定性达到最小,信息熵也就取得最小值0。

如果两种类别各占一半,即 \(p_a=p_b=50\%\),这时信息熵为:

\[H(X) = -(0.5 \times \log_2 0.5 + 0.5 \times \log_2 0.5) = -(-0.5-0.5) = 1 \]

两种类别各占一半,也就是不确定性最大,信息熵也就取得最大值1。

信息熵的函数图像:

信息熵是以整个集合作为计算对象的,ID3算法使用了信息增益。信息增益通过比较节点划分前后集合的信息熵来判断:

\[G(D,a) = H(x) - \sum_{v=1}^V \frac{|D^v|}{|D|} H(D^v) \]

  • \(G(D,a)\) 表示集合 \(D\) 选择特征属性 \(a\) 划分子集时的信息增益。

  • \(V\) 表示按照特征维度 \(a\) 划分后的子集个数。

  • \(|D|\) 表示集合 \(D\) 的元素个数。

信息增益越大,说明提纯效果越好。

由于特征维度的值越多,子集被切分的越细,信息增益越大,所以ID3算法倾向于选择值比较多的特征维度作为判定条件,但是这种情况下的纯度提升与目标不符,所以提出了改进版的算法——C4.5

C4.5用信息增益比来代替信息增益,用信息增益除以特征维度的固有值(Intrinsic Value)进行表示:

\[G_r = \frac{G(D,a)}{IV(a)} \]

特征维度越多,固有值越大,因此消除了特征维度所产生的影响。

固有值的数学表达式如下:

\[IV(a) = \frac{|D^v|}{|D|} \log_2\frac{|D^v|}{|D|} \]

2.基尼系数(Information Entropy)

CART算法采用了基尼系数作为决策条件的选择,数学表达式如下:

\[Gini(D)=1-\sum_{k=1}^Np_k^2 \]

\(D\) 表示进行基尼系数计算的集合。

以基尼系数计算两种极端情况。在二元分类中,如果当前样本都属于同一类别a,即 \(p_a=1, p_b=0\),则基尼系数为:

\[Gini(D) = 1-(1^2 + 0^2) = 0 \]

由于只有一种类别,所以不确定性达到最小,基尼系数也就取得最小值0。

如果两种类别各占一半,即 \(p_a=p_b=50\%\),这时基尼系数为:

\[Gini(D) = 1-(0.5^2 + 0.5^2)=0.5 \]

两种类别各占一半,也就是不确定性最大,基尼系数也就取得最大值0.5。

基尼系数的函数图像:

注意:基尼系数最大值为0.5,和信息熵不同。

使用基尼系数选择特征和前面一样,公式如下:

\[Gini_a = \sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v) \]

具体步骤

决策树分类算法信息表

album_temp_1612861600

决策树算法四个步骤:

  1. 确定纯度度量指标。
  2. 利用纯度度量指标,依次计算每个特征维度分类后子集的纯度,选取纯度能够达到最大的特征作为该次的分类条件。
  3. 利用该特征切分数据集,同时剔除该特征。
  4. 重复二三步,直至达到结束条件。

在Python中使用决策树分类算法

基于决策树这一大类的算法模型的相关类库都在sklearn.tree包中,包含了4个决策树算法类:

  • DecisionTreeClassifier类:经典的决策树分类算法。
  • DecisionTreeRegressor类:用决策树算法解决回归问题。
  • ExtraTreeClassifier类:这也是一款决策树分类算法,跟前面不同的是在决策条件选择环节加入了随机性。先随机抽取n个特征维度构成子集,然后再从该子集中选取决策条件。n的值通过参数“max_features”设置,当max_features设置为1时,相当于决策条件完全通过随机抽取得到。
  • ExtraTreeRegressor类:与ExtraTreeClassifier类似,同样在决策条件选择环境加入随机性,用于解决回归问题。

决策树分类算法,其中有一个名为“criterion”的参数,给这个参数传入字符串“gini”,将使用基尼指数;传入字符串“entropy”,则使用信息增益。默认使用的是基尼指数。

使用方法如下:

from sklearn.datasets import load_iris
# 导入决策树模型中的决策树分类算法
from sklearn.tree import DecisionTreeClassifier

# 鸢尾花数据集
X, y = load_iris(return_X_y=True)

# 训练模型:默认使用基尼系数
clf = DecisionTreeClassifier().fit(X, y)

# 预测结果
clf.predict(X)

预测结果如下:

array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])

默认的性能评估器评分:

clf.score(X, y)

评分结果:

1.0

全部分类正确!!!

改用信息熵:

# 训练模型:使用信息熵
clf_entropy = DecisionTreeClassifier(criterion='entropy').fit(X, y)

# 性能评估
clf_entropy.score(X, y)

评分结果:

1.0

依然全部分类正确!!!

绘制决策树如下:

import matplotlib.pyplot as plt
from sklearn.tree import plot_tree

fig = plt.figure(figsize=(10,10))
plot_tree(clf)

截屏2021-02-09 下午5.03.11

决策树分类算法的使用场景

决策树分类算法最大问题是容易过拟合,同时默认各特征指标之间相互独立。

决策树分类算法的特点

album_temp_1612861591

这篇关于「机器学习算法的数学解析与Python实现」决策树分类算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!