西安网站,网站伪静态化,phpcms 网站,搭建网站的价格创建时间#xff1a;2024-03-02 最后编辑时间#xff1a;2024-03-02 作者#xff1a;Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏#xff0c;很高兴遇见你~ 我是 Geeker_LStar#xff0c;一名初三学生#xff0c;热爱计算机和数学#xff0c;我们一起加…创建时间2024-03-02 最后编辑时间2024-03-02 作者Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏很高兴遇见你~ 我是 Geeker_LStar一名初三学生热爱计算机和数学我们一起加油~ ⭐(●’◡’●) ⭐ 那就让我们开始吧 emmm本来打算接着之前的内容把线性回归算法的实现写一下的但是开学了在学校大部分时间都只能看理论 errrrso 花了两天啃完了决策树算法这篇启动 决策树不难至少数学原理不难不像 SVMbushi 文章目录 简介 工作流程数学原理ID3 决策树C4.5 决策树CART 决策树 剪枝操作预剪枝后剪枝 连续值与缺失值处理连续值缺失值 简介 工作流程
决策树一个并不难的经典算法属于监督学习。它仿照人类在判断一个东西的类别时的一种思维路径——先判断这个东西是否有 A 特征若有再判断是否有 B 特征以此类推直到这些特征足够判断这个东西的类别。比如西瓜书上那个经典的例子我们要把一堆西瓜分成好瓜和坏瓜此时我们的思维是有路径的我们可能会先看这个西瓜的色泽如何如果色泽是青绿色的再敲一敲它听一下声音如果色泽不是青绿色的又进行其它操作…以此类推直到我们能通过这些特征判断出这个瓜是好的还是坏的。
well先简单复习一下树这种数据结构——它有一个根节点、若干内部节点和若干叶节点每一个叶节点都对应一个分类结果不同叶节点对应的分类结果可以重复相当于不同的判断路径。决策树要干的事就是寻找一些合理的从根节点到叶节点的路径完成分类当然也可以回归不过决策树更多还是用在分类上。
那么决策树什么时候会到达叶节点呢 通常有以下三种情况 1当前节点包含的样本全部属于同一类别即这条分类路径已经很成功了不用继续分类了。此时会把该节点设为叶节点叶节点的类别就是这些样本的类别。 2所有的属性如上面 “西瓜问题” 中提到的色泽、敲声都已经用于划分了没有其它属性可以再继续划分这个节点所包含的样本了或者此时把该节点设为叶节点类别为这些样本中出现次数最多的类别即后验概率最大的类别。 3用某个属性划分后没有符合要求的样本即当前节点包含的样本集合为空。此时把该节点设为叶节点类别为它的父节点包含的样本中出现次数最多的类别即先验概率最大的类别。
知道了以上三种情况决策树的伪代码就好写了其实是个递归
# 训练集:
D ((x_1, y_1), (x_2, y_2), ..., (x_n, y_n))其中 $x_i (x_{i1}, x_{i2}, ... , x_{id})
# 属性集
A {a_1, a_2, ..., a_n}函数 TreeGenerate (D, A) 如下
# 生成父节点
生成结点 node;
# 情况 1
if D 中样本全属于同一类别 C then将 node 标记为 C 类叶节点 ; return
end if
# 情况 2
if A ∅ or D 中样本在 A 上取值相同 then将 node 标记为叶节点其类别标记为 D 中样本数最多的类 ; return
end if
# 否则递归
从 A 中选择最优划分属性 a* # 选择的具体方法在下文
for a* 中的每一个值 do为 node 生成一个分支把相应的样本放入合适的分支中用 D_v 表示在 a* 中取值为 a*_v 的样本子集 ;# 情况 3if D_v 为空 then将分支节点标记为叶节点其类别标记为 D 中样本最多的类 ; returnelse# 递归产生新的子树以 TreeGenerate(D_v, A \ a*) 为分支节点end if
end for嗯~~这样应该很清晰啦至于那个 “最优划分属性” 到底怎么选往下看
ok讲完基本流程我们把本篇要用的数据集例子放在这~yes 西瓜书嘿嘿
编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺清脆清晰平坦软粘否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否
数学原理
决策树算法有三种主要的实现方式——ID3 决策树基于信息增益、C4.5 决策树基于增益率、CART 决策树基于基尼指数每种实现方式的数学原理都不一样来看看~
ID3 决策树
ID3 决策树基于信息增益。它是最早提出的决策树算法最简单不支持剪枝操作不提供连续值和缺失值处理。不过它的基本思想被后来的两个决策树算法沿用so 先从它开始吧
要想理解信息增益我们得先来看看信息熵information entropy是什么。 “熵” 这个概念你肯定不陌生在物理/化学中它表示一个系统的混乱程度熵越大说明整个体系越无序熵越小说明整个体系越有序。 在决策树中也一样假设我们有一堆样本 D ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) ) D((x_1, y_1), (x_2, y_2), ..., (x_n, y_n)) D((x1,y1),(x2,y2),...,(xn,yn))其中 x i ( x i 1 , x i 2 , . . . , x i d ) x_i (x_{i1}, x_{i2}, ... , x_{id}) xi(xi1,xi2,...,xid) y i y_i yi 表示该样本的分类。“熵” 表示这个数据集的混乱程度直观理解就是这个数据集中的数据属于不同分类的程度。这 n 个数据属于 n 个分类肯定比这 n 个数据属于 2 个分类的混乱程度高。
ok说的简单那我们怎么精确地度量一个数据集的混乱程度呢信息熵的数学公式如下 E n t ( D ) − ∑ k 1 ∣ Y ∣ p k log 2 p k Ent(D)-\sum_{k1}^{|Y|}p_k \log_2p_k Ent(D)−k1∑∣Y∣pklog2pk其中 ∣ Y ∣ |Y| ∣Y∣ 表示标记空间或输出空间简单理解就是不同的分类结果引用西瓜书上的例子“对一堆西瓜分类” 的标记空间就是 “好瓜、坏瓜”。 p k p_k pk 表示样本被分到第 k 类的概率也就是第 k 类样本在数据集 D 中的占比。大多数情况下 p k 1 p_k1 pk1所以 log 2 p k \log_2 p_k log2pk 是个负数so 我们需要在式子最前面加一个负号把结果变成正数。
不难发现 E n t ( D ) Ent(D) Ent(D) 的值越小说明这组样本的 “混乱程度” 越低即更多的样本都是同一类数据集的 “纯度” 更高。 准确来说当 p 1 p 2 . . . p ∣ Y ∣ 1 ∣ Y ∣ p_1 p_2 ... p_{|Y|} \frac{1}{|Y|} p1p2...p∣Y∣∣Y∣1 的时候即每个类别的样本在数据集中占比相同时 E n t ( D ) Ent(D) Ent(D) 有最大值 log 2 ∣ Y ∣ \log_2|Y| log2∣Y∣对应数据集纯度最低。而当 p k ( k 1 , 2 , . . . , ∣ Y ∣ ) p_k (k 1, 2, ..., |Y|) pk(k1,2,...,∣Y∣) 中有一个为 1其它为 0即数据集中全是某一类样本的时候 E n t ( D ) Ent(D) Ent(D) 有最小值 0对应数据集的纯度最高。 至于以上两种情况的证明不在此展开简单来说就是凸优化问题让它的拉格朗日函数的一阶偏导等于 0 就 ok。
举个例子用最开始的数据集算一下信息熵共 17 个数据正例好瓜8 个反例 9 个则信息熵为 E n t ( D ) − ∑ k 1 ∣ Y ∣ p k log 2 p k − ( 8 17 log 2 8 17 9 17 log 2 9 17 ) 0.998 Ent(D)-\sum_{k1}^{|Y|}p_k \log_2p_k -(\frac{8}{17} \log_2\frac{8}{17}\frac{9}{17} \log_2\frac{9}{17})0.998 Ent(D)−k1∑∣Y∣pklog2pk−(178log2178179log2179)0.998
好~现在我们知道信息熵是什么了根据前面说的决策树的工作流程我们现在得找一个最优划分属性。即用这个属性划分原数据集之后分支数据集的纯度要尽可能高也就是分支数据集的信息熵要尽可能小。
这事好办原始数据集的信息熵是一个定值我们想让划分后每一个分支数据集的信息熵都尽可能小不妨转换个思路让 “原始信息熵减去分支信息熵的和” 的结果最大。给这个结果一个名字——信息增益。简言之信息增益越大这次划分对数据集的 “纯度提升” 就越大。 换言之最优划分属性就是信息增益最大的属性。
先把信息增益的数学表达式放在这里后面会用一个例子来过一遍完整的计算。 G a i n ( D , a ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) Ent(D)-\sum^{V}_{v1}\frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv)其实很好理解a 是我们选择的划分属性V 是这个划分属性一共有几种可能的情况减号前面的式子就是原始数据集的信息熵后面就是把划分后的每个分支数据集的信息熵加起来两个相减就是信息增益。 这里说一下为什么有 ∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣ 这一项。可以把它简单理解为权重毕竟样本数越多的分支数据集对信息增益的影响理应越大如果不加这一项那不管分支数据集有 1 个数据还是有 100 个数据对信息增益的影响程度都一样这可就不合适了。
前面说过所谓最优划分属性就是让信息增益最大的属性用最开始的那个西瓜数据集我们可以选择的特征有 { 色泽、根蒂、敲声、纹理、脐部、触感 } \{色泽、根蒂、敲声、纹理、脐部、触感\} {色泽、根蒂、敲声、纹理、脐部、触感}现在来算一下这些属性的信息增益以第一项 “色泽” 为例。
“色泽” 属性有三个可能的取值划分成三个分支数据集就是 D 1 ( 色泽 青绿 ) , D 2 ( 色泽 乌黑 ) , D 3 ( 色泽 浅白 ) D^1(色泽青绿), \ D^2(色泽乌黑), \ D^3(色泽浅白) D1(色泽青绿), D2(色泽乌黑), D3(色泽浅白). 其中 D 1 D^1 D1 包含 6 个样例属于正例好瓜的有 3 个属于反例坏瓜的也有 3 个信息熵为 E n t ( D ) − ∑ k 1 ∣ Y ∣ p k log 2 p k − ( 3 6 log 2 3 6 3 6 log 2 3 6 ) 1 Ent(D)-\sum_{k1}^{|Y|}p_k \log_2p_k -(\frac{3}{6} \log_2\frac{3}{6}\frac{3}{6} \log_2\frac{3}{6})1 Ent(D)−∑k1∣Y∣pklog2pk−(63log26363log263)1。 同理 D 2 D^2 D2 和 D 3 D^3 D3 的信息熵分别为 0.918 和 0.722。 再用信息增益的公式 ( D , 色泽 ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) E n t ( D ) − ∑ v 1 3 ∣ D v ∣ ∣ D ∣ E n t ( D v ) 0.998 − ( 6 17 × 1.000 6 17 × 0.918 5 17 × 0.722 ) 0.109 \begin{align*} (D,色泽) Ent(D)-\sum^{V}_{v1}\frac{|D^v|}{|D|}Ent(D^v) \\ Ent(D)-\sum^{3}_{v1}\frac{|D^v|}{|D|}Ent(D^v) \\ 0.998-(\frac{6}{17}×1.000\frac{6}{17}×0.918\frac{5}{17}×0.722) \\ 0.109 \end{align*} (D,色泽)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv)Ent(D)−v1∑3∣D∣∣Dv∣Ent(Dv)0.998−(176×1.000176×0.918175×0.722)0.109计算出使用属性 ”色泽“ 进行划分信息增益是 0.109。
类似地对所有属性进行计算后发现属性 “纹理” 的信息增益最大于是我们用它作为划分属性。 ok这样第一轮划分就完成了按照这个套路继续对每个分支数据集进行划分即可~ 注意对于划分好的三个分支数据集进一步划分它们的时候每个分支数据集之间是彼此独立的也就是说可以用不同的划分属性去划分它们三个。
这样一步步划分的结果如下图from 书 emmm 没错你应该也感觉到了这玩意明显过拟合了不过现在先不管这个后面会讲怎么解决。
代码会在下一篇文章里集中给出这一篇先把原理讲完~~
C4.5 决策树
嗯其实有了 ID3 决策树的各种铺垫C4.5 和 CART 理解起来会超级简单因为基本思想是一样的只不过参考指标的计算方式变了。
怎么说C4.5 是对 ID3 的改进。其中两点是 C4.5 支持剪枝、支持连续值和缺失值不过这不是这部分的重点。 先举个例子我如果在上面的划分属性中加一个 “编号”共 17 个可取值那这事可就好办了直接用编号进行划分划分之后每个分支数据集里就 1 个数据信息增益高达 0.998也就是说划分之后信息熵之和直接变成 0 了。这貌似很强可是这样的决策树没有任何泛化能力。 这是个极端的例子但是它反映了 ID 3 算法的不足之处——可取值数量多了每一个取值下的数据就少了纯度自然就提高了那划分后的信息熵之和必然就减小了信息增益肯定会提高。
也就是说ID3 算法在选择最优划分属性的时候会倾向于选择 “可取值数量多” 的属性。这会导致什么yesyes如果一个属性的可取值数量过多比如上面举例的 “编号”很容易就导致过拟合。。。so 我们得避免这种情况。
一个简单的思路是既然信息增益会在属性可取值数量多的时候偏大那就让信息增益除以另一个值并且让这个值也在属性可取值多的时候偏大即可。类似于归一化。
这个 “除以的值” 的数学表达式如下 I V ( a ) ∑ v 1 V ∣ D v ∣ ∣ D ∣ log 2 ∣ D v ∣ ∣ D ∣ IV(a) \sum^V_{v1}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|} IV(a)v1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣其中a 即划分属性这个值被称作属性 a 的固有值。 你可能会感觉诶这个式子的形式怎么如此熟悉…好像就是信息熵那个式子的形式 yesyes恭喜你感觉的很对这个式子其实就是在计算信息熵呀它计算的是某个划分属性自身的信息熵。代换一下V 是这个属性的可取值数量类似于信息熵中的标记空间 ∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣ 是样本在 a 属性上的值等于该属性某个可取值的概率类似于信息熵中的 p k p_k pk。所以其实这个公式可以理解为属性本身的信息熵即不确定性。
如果一个属性的可取值越多这个属性自身的 “混乱度”不确定性就越高它的固有值信息熵也会相应的大所以用固有值作为分母还挺不错 这么一来C4.5 算法选择最优划分属性的公式如下我们把它称作增益率。 G a i n _ r a d i o ( D , a ) G a i n ( D , a ) I V ( a ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) ∑ v 1 V ∣ D v ∣ ∣ D ∣ log 2 ∣ D v ∣ ∣ D ∣ \begin{align*} Gain\_radio(D,a) \frac{Gain(D,a)}{IV(a)} \\ \frac{Ent(D)-\sum^{V}_{v1}\frac{|D^v|}{|D|}Ent(D^v)}{\sum^V_{v1}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}} \end{align*} Gain_radio(D,a)IV(a)Gain(D,a)∑v1V∣D∣∣Dv∣log2∣D∣∣Dv∣Ent(D)−∑v1V∣D∣∣Dv∣Ent(Dv)
emmm不过 C4.5 其实也有 bug。因为从数学角度来看信息增益和增益率都不是线性变化的有 log 的参与所以不论是信息增益还是增益率其二阶导数必定不为 0或一阶导必定不为常数这说明它们的变化率一阶导不是均匀变化的即因变量会在自变量值较大的时候变化较快或在自变量值较小的时候变化较快这就决定了它们必然会偏向样本较多的属性或样本较少的属性看二阶导是正还是负了。
C4.5 和 ID3 相反它会偏向可取值数量较少的属性。所以 C4.5 算法并不是直接选择增益率最大的属性作为划分属性而是用了一个折中的方法先在所有属性中选出信息增益较大的一半再从这一半属性中选择增益率最高的属性。 这是一种相对平衡的方法。
一样代码会在下一篇给出~
CART 决策树
CART英文全称 classification and regression tree是三种决策树中性能最强的。从名字就能看出它既可以用于分类也可以用于回归。sklearn 中默认的决策树算法就是 CART。
CART 决策树使用基尼指数作为选择属性的指标。这个指标比前两个好理解一些。 直观来看我在一堆样本中随机抽取两个抽取 10 次如果这 10 次中有 8 次我抽到的两个样本都是同类那我可以大胆推测这个数据集还蛮 “整齐” 的纯度挺高的。但是如果我这 10 次每次抽到的两个样本都不同类那我肯定觉得这数据集也太混乱了。
没错基尼指数的基本逻辑就是上面那段它衡量的是从一个数据集中随机抽取两个样本它们的类别标记不一致的概率。 基尼指数越小说明数据集的纯度越高。
式子很简单“两个样本类别不一致的概率” 等于 1 减去 “两个样本类别一致的概率” G i n i ( D ) 1 − ∑ k 1 ∣ Y ∣ p k 2 Gini(D) 1-\sum^{|Y|}_{k1}p_k^2 Gini(D)1−k1∑∣Y∣pk2这就是原始数据集 D 的基尼指数。
再来计算每个属性的基尼指数形式和之前信息熵那里保持统一 G i n i _ i n d e x ( D , a ) ∑ v 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini\_index(D,a) \sum^{V}_{v1}\frac{|D^v|}{|D|}Gini(D^v) Gini_index(D,a)v1∑V∣D∣∣Dv∣Gini(Dv)我们选择基尼指数最小的属性作为最优划分属性。
但是嘛…这种方法说来简单在实际中却没办法应用因为 CART 是一棵二叉树它不像 ID3 那样可以同时生成多个分支。 不过关于 CART 的详细做法我打算放到下一篇二分类算法推广到多分类的一些方法中再说这里先说这么多~
OK以上就是三种决策树算法的数学原理~其实并不难。
放一个各项对比图 接下来我们开始解决过拟合问题…
剪枝操作
well任何一个机器学习算法都不可避免地会遇到过拟合问题决策树也一样。 对于决策树过拟合的主要原因是它的分支过多就比如我有 n 个样本我如果用 “编号” 进行分类那每个分支就一个样本这样肯定最后的信息熵最低看似是 “最优” 的划分方式可是这个决策树完全不具有泛化能力。 所以为了减少过拟合我们需要对决策树进行 “剪枝”——如果用某一个条件进行划分不能使决策树的性能提升甚至反而下降那么就不必用这个条件进行划分了这个 “树枝” 就可以被剪掉了这就是剪枝操作的基本思想。
注意“性能是否提升” 是需要验证集进行验证的所以我们把最开始的数据集分成两部分一部分作为训练集另一部分作为验证集。emm 的确这个数据集很小但是作为示例够用了
训练集
编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是10青绿硬挺清脆清晰平坦软粘否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否
验证集
编号色泽根蒂敲声纹理脐部触感好瓜4青绿蜷缩沉闷清晰凹陷硬滑是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否
先来看一下如果不进行剪枝基于训练集最终生成的决策树是什么样的 常用的剪枝操作有两种——预剪枝和后剪枝其实现过程和优劣势略有不同。 我们用上面的训练集来训练决策树选择信息增益准则。
预剪枝
顾名思义预剪枝就是在生成一棵完整的决策树之前就把没必要的树枝剪掉也就是一些树枝根本就不会被生成。
根据信息增益准则如果要划分的话对于训练集而言最优划分属性是 “脐部”。 但是是否有必要进行这个划分呢请记住决策树的剪枝准则在剪枝部分最开始也有说过如果用该属性进行划分能够提高决策树在验证集上的准确率就划分否则就不划分即 “剪枝”。
在基本流程中我们提到如果在当前节点处不进行划分那么当前节点将被标记为叶子节点类别为在当前节点的所有样本中出现最多的类别。 也就是说如果在根节点这里不用 “脐部” 属性进行划分那直接把根节点标记为叶子节点类别为在训练集中出现次数最多的类别也就是 “好瓜”。换言之这棵决策树会把验证集中所有数据都分类为好瓜。 well不进行划分的情况下验证集 7 个样本全部被判定为好瓜但实际上好瓜只有 3 个准确率为 42.9%。
再来看看进行划分的情况。我们先只用 “脐部” 属性划分一次然后不再进行第二次划分把节点类别标记为被分到节点那一类的数据中出现最多的类别。 okkk大概就是这样划分后在验证集上的准确率达到了 71.4%大于不划分的情况42.9%于是我们选择用 “脐部” 进行划分。
第一次划分完成然后呢还要继续划分吗 没错重复上述套路就 ok 了④ 节点已经没有必要继续划分了类别一致对于 ②③ 节点通过计算发现划分后决策树在验证集上的准确率都下降了于是不再划分最终的决策树如上图所示这种只有一层的决策树也被称为 “决策树桩”。
对比一下预剪枝决策树和未剪枝决策树 可以看出预剪枝决策树的很多分支都没有展开。这在一方面减少了过拟合风险降低了决策树训练的各种开销但是从另一方面看这同时增加了欠拟合的风险嗯至少我觉得预剪枝决策树明显是欠拟合的因为有些划分可能并不能直接提高决策树的准确率甚至会导致准确率下降但在其基础上的划分却能让决策树的准确率提升。但是预剪枝相当于直接否定了这种可能造成欠拟合的风险。
后剪枝
很明显后剪枝和预剪枝相对它会在一棵完整的决策树生成完毕后自底向上地计算哪些树枝是没必要的再把它们去掉。
简单来说后剪枝的过程就是从一个叶子节点出发看看如果把这个叶子节点的父节点作为叶子节点相当于剪掉叶子节点这一层的分支决策树的准确率是否提高如果提高了就剪掉这一层分支否则就不剪。 特别地如果是否剪枝对决策树的准确率没有影响那可剪可不剪。
因为流程已经在预剪枝那里讲过一遍了这里不用再展开说放一张最终决策树的图即可。 不难发现后剪枝比预剪枝保留了更多分支因此它的欠拟合风险很小泛化性能往往优于预剪枝和未剪枝决策树。但同时后剪枝需要先训练一棵完整的决策树再自底向上对每一个分支进行考察这导致后剪枝的各种开销在属性数量较多且数据量较大时都远大于预剪枝和未剪枝。
连续值与缺失值处理
well在现实情况中我们很难收集到非常完整的指没有属性缺失的数据集也很难保证一个数据集中所有的属性都是连续的 or 都是离散的。如果遇到这两种情况原始的决策树算法就不那么好用了我们需要做一些特殊处理。
连续值
显然面对连续值我们肯定不可能把每一个值单独分为一类。这就需要用到连续属性离散化技术了在决策树算法中最常用的是二分法简单来说就是选出一个临界值大于这个临界值的连续属性被分为一类小于这个临界值的被分为另一类。
比如现在我们有一个数据集 D 和一个连续属性 aa 在 D 上有 n 个不同的取值把这些取值从小到大排序即 { a 1 , a 2 , . . . , a n } \{a^1, a^2, ..., a^n\} {a1,a2,...,an}那么肯定存在一个临界值 t ( a 1 t a n ) t \ ( a^1 t a^n) t (a1tan) 能够通过属性 a 把数据集 D 划分为两部分即 “在属性 a 上的取值大于 t 的部分” 和 “在属性 a 上的取值不大于 t 的部分”记为 D t D^_t Dt 和 D t − D^-_t Dt−。
怎么找这个临界值 t 呢不难发现对于相邻的属性取值 a i a^i ai 和 a i 1 a^{i1} ai1 来说这个 t 取区间 [ a i , a i 1 ) [a^i, a^{i1}) [ai,ai1) 里任意一个值的划分效果都是一样的so 我们不妨就取中间值作为一个可能的临界值。 即二分法的核心就是对于每两个相邻的属性取值都取中间值作为一个可能的临界值这些中间值组成一个 “可能临界值” 的集合再通过一些标准选出最合适的临界值。 由这些中间值组成的集合可表示为 T a { a i a i 1 2 , 1 ≤ i ≤ n − 1 } T_a \{\frac{a^ia^{i1}}{2},1≤i≤n-1\} Ta{2aiai1,1≤i≤n−1}那么临界值怎么选呢这就和选取最优划分属性一样了。因为选临界值的目的也是分类那就用三种评价标准中的一个比如信息增益选出 “可能临界值” 集合中信息增益最大的那个值作为最终的临界划分值 t。
不过和离散值不同的是连续值可以反复作为最优划分属性只不过每次选择的临界值可能不一样。换言之比如一棵决策树已经用 “属性 7.25” 划分过一次了但也可以在此基础上再用 “属性 2.18” 继续划分。
连续值的处理比较简单这里就不再举例子了。
缺失值
well缺失值是很常见的通常指样本在某个或某几个属性上的值有空缺。 如果有缺失值的样本很少总样本量又比较大那直接丢掉这些有缺失值的样本也可以但是通常情况下事情不会这么简单所以在遇到缺失值的时候我们需要一些应对方案。
我们面临的问题主要有两个 1如何在某些属性有缺失值的情况下选择最优划分属性 2选好最优划分属性后如果某样本在这个属性上的值缺失怎么划分这个样本
先来解决第一个问题。很显然我们只能通过在该属性上没有缺失值的样本来判断这个属性是否能作为最优划分属性依然采用信息增益作为标准。
还是一样给定数据集 D D D 和属性 a a a作以下规定 D D D 中的数据共有 ∣ Y ∣ |Y| ∣Y∣ 个分类 D ~ \tilde{D} D~ 表示数据集 D D D 中在属性 a a a 上没有缺失值的样本子集属性 a a a 有 V V V 个可取值 { a 1 , a 2 , . . . , a v } \{a^1, a^2, ... , a^v\} {a1,a2,...,av} D v ~ \tilde{D^v} Dv~ 表示 D ~ \tilde{D} D~ 中在属性 a a a 上取值为 a v a^v av 的样本子集 D k ~ \tilde{D_k} Dk~ 表示 D ~ \tilde{D} D~ 中属于第 k , ( k 1 , 2 , . . . , ∣ Y ∣ ) k, (k1, 2, ..., |Y|) k,(k1,2,...,∣Y∣) 类的样本子集 D D D 中的每个样本的初始权重 w x 1 w_x1 wx1
ok有了这些我们来计算一些式子 Ⅰ. 对于属性 a a a在属性 a a a 上无缺失值的样本占总样本的比例 ρ ∑ x ∈ D ~ w x ∑ x ∈ D w x ρ \frac{\sum_{x\in\tilde{D} \ w_x}}{\sum_{x\in D \ w_x}} ρ∑x∈D wx∑x∈D~ wx
Ⅱ. 在属性 a a a 上无缺失值的样本中属于第 k k k 类样本所占比例 p k ∑ x ∈ D k ~ w x ∑ x ∈ D ~ w x , k 1 , 2 , . . . , ∣ Y ∣ p_k \frac{\sum_{x\in\tilde{D_k} w_x}}{\sum_{x\in\tilde{D} \ w_x}}, k1, 2, ..., |Y| pk∑x∈D~ wx∑x∈Dk~wx,k1,2,...,∣Y∣
Ⅲ. 在属性 a a a 上无缺失值的样本中在属性 a a a 上取值为 a v a^v av 的样本所占比例 r v ~ ∑ x ∈ D v ~ w x ∑ x ∈ D ~ w x \tilde{r_v} \frac{\sum_{x\in\tilde{D^v} \ w_x}}{\sum_{x\in \tilde{D} \ w_x}} rv~∑x∈D~ wx∑x∈Dv~ wx
计算这些是为了把信息增益的计算式推广到有缺失值的场景。 再回顾一下信息增益的原始表达式 G a i n ( D , a ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) Ent(D)-\sum^{V}_{v1}\frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv)
把新计算出的数值代换进去新的信息增益算式为 G a i n ( D , a ) ρ × G a i n ( D ~ , a ) ρ × ( E n t ( D ~ ) − ∑ v 1 V r v ~ E n t ( D v ~ ) ) Gain(D, a) ρ × Gain(\tilde{D}, a) \\ ρ × (Ent(\tilde{D})-\sum^{V}_{v1}\tilde{r_v}Ent(\tilde{D^v})) Gain(D,a)ρ×Gain(D~,a)ρ×(Ent(D~)−v1∑Vrv~Ent(Dv~))其中 E n t ( D ~ ) − ∑ k 1 ∣ Y ∣ p k log 2 p k Ent(\tilde{D}) -\sum_{k1}^{|Y|}p_k\log_2p_k Ent(D~)−k1∑∣Y∣pklog2pk
其实就相当于把 D ~ \tilde D D~ 当成了新的数据集所有的计算方式都和原算式一样。至于为什么要乘 ρ ρ ρ可以这么理解 ρ ρ ρ 类似置信度或权重因为对于一个属性肯定是缺失的值越少参考价值越高 × ρ ×ρ ×ρ 相当于同时兼顾了纯度提升和可信度参考价值。
ok 终于把公式讲完了对这是这一篇最后一个公式。
emmmm我们好像还有个问题2是吧问题2比1好解决——之前不是说给每一个样本在最初都赋予了 1 的权重嘛这个权重这时候就有用了我们不知道这个有缺失值的样本到底怎么分那就同时把它分到所有分支中它在新分支中的权重就等于这个分支的先验概率也就是被分到这个分支的样本在总样本中的占比。当然其它有明确分类的样本的权重不变还是 1。
C4.5 算法对缺失值的处理方式就如上两个问题的答案所说。
举个例子我们现在有这样一个数据集
编号色泽根蒂敲声纹理脐部触感好瓜1–蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷–是3乌黑蜷缩–清晰凹陷硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5–蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰–软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响–稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺清脆–平坦软粘否11浅白硬挺清脆模糊平坦–否12浅白蜷缩–模糊平坦软粘否13–稍蜷浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰–软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿–沉闷稍糊稍凹硬滑否
以属性 “色泽” 为例17 个样本中共有 14 个样本在该属性上没有缺失值则这 14 个样本的信息熵为 − ( 6 14 log 2 6 14 8 14 log 2 8 14 ) 0.985 -(\frac{6}{14} \log_2\frac{6}{14}\frac{8}{14} \log_2\frac{8}{14})0.985 −(146log2146148log2148)0.985 同样我们也可以计算出三个分支数据集的信息熵分别为 1.000、0.918、0。
ok样本子集 D ~ \tilde{D} D~ 上属性 “色泽” 的信息增益就是 0.998 − ( 4 14 × 1.000 6 14 × 0.918 4 14 × 0.000 ) 0.306 0.998-(\frac{4}{14}×1.000\frac{6}{14}×0.918\frac{4}{14}×0.000) 0.306 0.998−(144×1.000146×0.918144×0.000)0.306
那么样本集 D D D 上的信息增益就是 14 17 × 0.306 0.252 \frac{14}{17}×0.306 0.252 1714×0.3060.252.
类似的我们计算出属性 “纹理” 的信息增益最大为 0.424于是我们选择它作为最优划分属性。 重复上述过程直到决策树构建完成。
最终结果如下 ok以上就是决策树算法的原理学完这些大概用了几节自习课吧写这篇又写了好几个小时代码之后发~ 好嘞这篇就到这里感谢~ 这篇文章详解决策树算法写了好几个小时希望对你有所帮助⭐ 欢迎三连一起加油 ——Geeker_LStar
