机器学习中的那些树——决策树(一)

从零基础开始参加了几场数据挖掘方面的比赛,每次比赛都会学到不少东西,自从上次在elo的kernel中看见很多人都使用LightGBM、XGBoost,那之后我也开始用起了这些,但是却从未花时间去了解过这是究竟是什么,其内部工作原理是怎么样的,正好这段时间在参加df平台的消费者人群画像—信用智能评分这一比赛,做起了调参,但因为对其内部并不是很收悉,便准备好好学习有关树模型方面的内容,并写下这系列的博...

从零基础开始参加了几场数据挖掘方面的比赛,每次比赛都会学到不少东西,自从上次在 elo 的 kernel 中看见很多人都使用 LightGBM、XGBoost,那之后我也开始用起了这些,但是却从未花时间去了解过这是究竟是什么,其内部工作原理是怎么样的,正好这段时间在参加df平台消费者人群画像—信用智能评分这一比赛,做起了调参,但因为对其内部并不是很收悉,便准备好好学习有关树模型方面的内容,并写下这系列的博客。这里将从最基础的决策树开始讲起。

概述

决策树(decision tree)是一类常见的机器学习方法。类似于流程图,一颗决策树包含一个根节点、若干个内部节点和叶子节点,每一个树节点表示对一个特征或属性的测试,每一个分支代表一个属性的输出,每一个叶子节点对应一种决策结果。从根节点到每个叶节点的路径对应了一个判定测试序列。其学习的基本流程遵循分治(divide-and-conquer)策略。

算法

输入:训练集\(D=\{(x_1,y_1),(x_2,y_2),... ,(x_n,y_n)\}\)
属性集\(A=\{a_1,a_2,...,a_n\}\\\)
过程:函数\(TreeGenerate(D,A)\)

\(1:生成节点 node;\)

\(2:if\) $ D $ $ 中样本全属于同一类别$ $ C$ $ then$

\(3:\quad将\) $ node$ \(标 记为\) $ C$ $ 类叶节点;$ $ return$

\(4:end\) $ if$

\(5:if\) $ A=\emptyset $ $ OR$ $ D$ $ 中样本在A上取值相同$ $ then $

\(6:\quad 将node标记为叶节点,其类别标记为D中样本数最多的类;then\)

\(7:end\) \(if\)

\(8:从A中选择最优划分属性\)

$9:for $ $ a_* $ \(的每一个值\) $ a_{*}^{v}$ $ do$

\(10:\quad 为node生成一个分支;令D_v表示D中在a_*上取值为a_{*}^{v} 的样本子集:\)

$11:\quad if $ \(D_v\) \(为空\) \(then\)

\(12:\quad\quad将分支节点标记为叶节点,其类别标记为D中样本最多的类;return\)

\(13:\quad else\)

\(14:\quad\quad以TreeGenerate(D_v,A\)\(\{a_*\})为分支节点\)

\(15:\quad end\) \(if\)

\(16:end\) \(for\)

输出:\(node\)为节点的一颗决策树

划分选择

从上面的算法中可以看出,最重要的一步就是第8行选取最优划分,但我们该如何选取最优划分呢?这里就涉及到了信息增益的概念。在讲解信息增益前,先来了解了解信息熵和条件熵。

信息熵(information entropy)是度量样本集合纯度最常用的一种指标,它可以衡量一个随机变量出现的期望值。如果信息的不确定性越大,熵的值也就越大,出现的各种情况也就越多。

假设当前样本集合\(D\)中第\(k\)类样本所占比例为\(p_k(k=1,2,\cdots,|n|)\),则\(D\)的信息熵为:
\[Ent(D)=-\sum_{k=1}^{|n|}p_k\log_2p_k \tag{1}\]
定义:\(0log0 = 0\)

条件熵(conditional entropy)表示在已知随机变量X的条件下随机变量Y的不确定性。定义随机变量X给定的条件下随机变量Y的概率分布的熵:
\[Ent(Y|X)=\sum_{k=1}^{n}p_kH(Y|X=x_k) \tag{2}\]
假定离散属性(特征)a有V个可能取值\(\{a^1,a^2,\cdots,a^V\}\),若使用a来对样本集D进行划分,则会产生V个分支节点,其中第\(v\)个分支节点包含了\(D\)中所有在属性(特征)a上取值为\(a^v\)的样本,记作\(D^v\)。那么,特征\(a^v\)的条件概率分布为 \(\frac{|D^v|}{|D|}\),我们可得信息增益(information gain):
\[Gain(D,a)=Ent(D)-Ent(D|a) \tag{3} \\=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{D}Ent(D^v)\]
由上式可知,信息增益是相对于特征而言的,定义为集合\(D\)的信息熵与特征\(a\)\(D\)的条件熵之差。

这里回到一开始的问题,如何选择最优划分?方法是对训练数据集\(D\),计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

然而,有时存在这么一个问题,以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题。对这一问题的解决方法是使用信息增益比(information gain ratio):

​ 特征A对训练数据集D的信息增益比\(g_R(D,A)\)定义为其信息增益\(g(D,A)\)与训练数据集D关于A的值的熵\(H_A(D)\)之比,即
\[g_R(D,A)=\frac{g(D,A)}{H_A(D)} \tag{4}\]
其中,\(H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}\),n是特征A取值的个数。

结语

这篇文章中介绍了决策树的一些基本理论,对于决策树的优化以及ID3、C4.5、CART的代码实现将在后面的文章中给出。

源文地址:https://www.guoxiongfei.cn/cntech/12770.html