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

释放双眼,带上耳机,听听看~!

从零基础开始参加了几场数据挖掘方面的比赛,每次比赛都会学到不少东西,自从上次在 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的代码实现将在后面的文章中给出。

人已赞赏
随笔日记

设计模式之欢迎来到设计模式世界(一)

2020-11-9 3:54:43

随笔日记

课后作业二(贪吃蛇)

2020-11-9 3:54:45

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索