1. 首页
  2. 文章中心
  3. Other

机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配

87 阅读 0 评论
我是靠谱客的博主 朴素爆米花，最近开发中收集的这篇文章主要介绍机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言：决策树是一种基本的分类与回归的方法，按照统计学习方法的三个基本要素——模型，策略，算法的方式，我们来进行学习。

1. 决策树模型

  • 决策树定义：分类决策树是一种描述对象分类的树形结构。树中的节点为了两类：内部节点和叶节点，内部节点表示了一个特征，叶节点表示了最后输出的类标志。有趣的是，与其他分类模型算法不同的是，决策树既不是寻找超平面对其进行逼近，也不是使用先验后验概率对其进行预测，决策树在分类的过程中所使用的是最大化样本子集特征纯度的策略进行分类，这样就不需要任何领域知识/参数设定。当然决策树模型也会有欠拟合或过拟合的担忧，那么我们其实在决策树模型中就将关注点放在了以下几点：

    1. 策略：最优化目标函数/目标值是什么？
    2. 策略：如何避免过拟合？
    3. 算法：我们依据最优化目标采取的算法是什么？
    4. 算法：我们如何生成一个决策树，并防止其过拟合？

  • 形象化理解决策树：
    举一个例子我们来看一下到底什么是决策树生成过程（摘自其他博客）：

母亲：给你介绍个对象。
女儿：年纪多大了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

这就是一个女生在决定去或者不去的一个2分类决策树的生成过程，我们将其可视化为一个树结构，可以看到：

在其中我们可以清晰的看到，绿色的节点是内部节点，代表了一个决策依据。橙色的节点是叶节点，代表了决策结果。箭头表示了决策依据的判断路径。那么这个模型就可以在加入具体量化的判断依据之后就可以为一个决策树了。

  • 决策树的学习：
    依据决策树定义中我们的关注点，我们确认了决策树的学习算法应该包括了内部节点的特征选择，决策树的生成，防止过拟合的剪枝过程。如此，我们就有了一个决策树的基本算法
输入：训练集D={(x1,y1),(x2,y2),...,(xm,ym)}
属性集A={a1,a2,...,ad}
过程：函数GenerateTree(D,A)
1: 生成节点node；
2: if D中样本全是一个类别C then
3:
将node节点标记为C类叶节点；return；
4: end if
5:if A = null or D中样本在A上取值相同 then
6:
将node标记为叶节点，按照少数服从多数原则标记为D类中样本数最多的类 ；return
7: end if
8: 从A中按照策略选择最优的划分属性a*;
9：for a* 的每一个可能取值a*v then
10:
为node生成一个分支；令Dv表示D中在属性a*上取值为a*v的样本子集；
11:
if Dv为空集 then
12:
将node的分支节点标记为叶节点，其类别标记为D中样本最多的类；return
13：
else
14:
以GenerateTree（Dv，A{a*}）为分支节点
15： end if
16：end for
输出 以node为根节点的一颗决策树

有上面的基本算法过程，我们可以发现：
1. 决策树生成过程是一个递归的过程
2. 在递归过程中会导致递归返回的情形有三种：
- 2.1 当前节点包含的样本子集都是同一类，无需划分，直接以当前类作为叶节点的决策结果
- 2.2 当前节点属性级为空集，或所有样本在所有属性上都取值相同，无法划分，直接按照少数服从多数来作为当前叶节点的决策结果，这是利用当前节点的后验分布
- 2.3 当前节点的样本子集为空集，无法划分，只能以其父节点中的样本子集中的样本最多类来表示。把父节点的样本分布当作当前节点的先验分布
3.伪代码第8行就是我们关注点1和3的解答过程，详见下：

2. 特征选择：

特征选择问题，希望在对一个节点选取最有属性来最为这个节点的标志，这样的过程其实质就是一个条件选取的过程，在属性ai的条件下，再选取aj，使得特征选择最优目标可以最大，但是有一点值得确定：特征有离散和连续两种特性，针对这两种不同特征，我们采取什么样的选择呢？这个是我们后面需要确定的，现在我们还是回到特征选择的最有函数/值上来
（不好意思，这个是我的逻辑思路，有了这样的疑问，将其当作次要任务先记录后解决，先关注当前重点）

2.1 熵(entropy)

  1. 定义：度量样本集合纯度
  2. 公式：
    Ent(D)=−∑i=1|y|pklog2pk E n t ( D ) = − ∑ i = 1 | y | p k l o g 2 p k

    Ent（D）的值越小，则D的纯度越高，同时在 p1=p2=p3=...=pd=1d p 1 = p 2 = p 3 = . . . = p d = 1 d 时，取到熵最小值

2.2 信息增益（information gain）：

  1. 定义：信息增益表示得知特征信息而使得类的信息不确定性减少的程度，那么根据这个描述，我们如果使用信息增益作为决策树最优选择的依据，那么就要选取使得类信息不确定性减少最多的，也就是信息增益最大的特征。
  2. 公式：
    假定离散属性a有V个可能取值 a1,a2,...,aV a 1 , a 2 , . . . , a V ，如果使用a对样本集来进行划分，则会产生V个分支，每一个分支i都对应了样本集在属性a上取 ai a i 值的样本集 Di D i 我们就可以根据信息熵的公式来计算信息增益了，但是同时因为不同样本集数量不一样，我们就需要进行加权，权值为 |Di||D| | D i | | D | ，所以有
    Gain(D,a)=Ent(D)−∑i=1V|Di||D|Ent(Di) G a i n ( D , a ) = E n t ( D ) − ∑ i = 1 V | D i | | D | E n t ( D i )

    表示父节点的信息熵和以a属性进行分支之后各分支信息熵加权和之间的差值，数值上，父节点信息熵为负数，个分支节点的加权和表明了分支之后的信息纯度效果，是肯定比父节点信息熵更小的负数，那么相减就可以得到分支之后的纯度提升效果，结果越大则纯度提升效果越大。所以：
    • 信息增益越大，该属性分类越好
    • 决策树中最常用的算法ID3就是使用信息增益来最为特征最优选择依据的决策树生成算法

2.3 信息增益比（information gain ratio,又称增益率）：

在对信息增益分析我们发现， Gain(D,a) G a i n ( D , a ) 的计算不仅仅受每一个父节点，分支节点的信息熵影响，同时也会受到分支个数V的影响。或者我们可以这样理解，如果我们将属性a的取值分的足够细，那么它的信息增益就会很大，这样就会形成一个所谓的：
**信息增益准则对可取值数目较多的属性有所偏好。
取一个极端的例子，当我们如果把样本集中的编号也作为一个属性的时候，那么决策树生成的只会是一个深度为2，一个根节点，m个叶节点的树结构，但是这样的结构具有非常大的过拟合特性，根本不是我们想要。所以我们为了避免这种偏好，定义了 信息率
- 定义：

Gainration(D,a)=Gain(D,a)IV(a) G a i n r a t i o n ( D , a ) = G a i n ( D , a ) I V ( a )
其中
IV(a)=−∑v=1V|Dv||D|log2|Dv||D| I V ( a ) = − ∑ v = 1 V | D v | | D | l o g 2 | D v | | D |

称为属性a的固有值，属性a的可能值数目越多，则IV(a)的值通常会越大。
需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此， C4.5算法并不是直接选择增益率最大的候选划分属性，而是用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率高的

2.4 基尼指数

基尼值反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此基尼值越小，则表明样本集D的纯度越高。
- 公式：

Gini(D)=∑k=1|y|∑k′!=kpkpk′=1−∑k=1|y|p2k G i n i ( D ) = ∑ k = 1 | y | ∑ k ′ ! = k p k p k ′ = 1 − ∑ k = 1 | y | p k 2

采用和信息增益的先沟通的符号表示，属性a的基尼指数定义为
Gini_index(D,a)=∑k=1|y||Dv||D|Gini(Dv) G i n i _ i n d e x ( D , a ) = ∑ k = 1 | y | | D v | | D | G i n i ( D v )

则 CART决策树算法就是在决策树基本算法第8行中使用基尼系数最为最优判据，寻找最小基尼系数的属性或者切分点作为节点属性。

3. 剪枝

剪枝操作主要有两种操作：预剪枝，后剪枝

3.1 预剪枝：

  1. 定义：在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点
  2. 优点：预剪枝可以时决策树很多分支都没有展开，这可以有效降低过拟合的风险，而且显著减少了决策树的训练时间开销和测试时间开销。
  3. 缺点：有些分支的当前划分虽不能提高泛化性能，甚至降低性能，但是在其基础上的下一次划分却有可能导致性能显著提高；但是因为预剪枝本质是禁止展开，所以带来了欠拟合的风险

3.2 后剪枝：

  1. 定义：先从训练集生成一个完整决策树，然后自底向上对非叶节点考察，若将该节点对应子树替换为叶节点带来决策树泛化性能的提升，则将该节点替换为叶节点

3.2.1 REP 方法

  • 过程：
    • 自底向上，对于树T的每一个子树S，使它成为叶子节点，生成一颗新树，如果在测试集上，新树可以得到一个较小或者相等的分类错误，而且子树S中不包含具有相同性质的子树，则S删除，用叶子节点替代，重复此过程，知道任意树都不可替代为止
  • REP优点：可以有效的删除因为训练集中的巧合规律而生成的结点；可以生成最高精度最小节点的决策树
  • REP缺点：偏向于过度修剪，但是对于训练集中稀少的训练数据对应的分支，则会在剪枝过程中被删除，这样会出现欠拟合的问题。所以在训练集数据较少的情况下不建议使用REP剪枝

3.2.2 PEP方法（悲观剪枝）

前沿：主要是为了克服REP剪枝需要独立剪枝数据集的缺点二提出的
- 过程：
- 使用二项分布来取代正太分布，因为在伯努利分布中，当数量极大的时候，根据中心极限定理，事件A出现的次数渐进于正态分布的问题，但是只是渐进而不是相等
-
如上图所示，我们虽然可以拿正态分布近似，但是还有一部分在外面，所以我们有

P(Y<=a)=P(Z<a+12−E[Y]σ)=P(Z<a+12−npnpq−−−√) P ( Y <= a ) = P ( Z < a + 1 2 − E [ Y ] σ ) = P ( Z < a + 1 2 − n p n p q )

- 设n(t)为原始决策树T某一叶子节点的实例个数，其中错误个数为e(t)，则有了错误率为r(t) = e(t)/n(t)。但是有一点我们需要注意，这个错误率是我们用训练数据来进行的测试，那么是有偏倚的，不能精确的用来表示泛化性能，所以我们需要对其进行误差校正，在这里我们有一个基本假设， 对所有叶子节点产生的所有误差都认为是二项分布的，那么我们根据之前公式，我们将单个子节点的错误个数为：
e′(t)=e(t)+12 e ′ ( t ) = e ( t ) + 1 2

则设S为树T的子树Tt。其叶子节点个数为L(s)，则Tt的分类误差率为：
r′(Tt)=∑s[e(s)+12]∑sn(s)=∑se(s)+L(s)2∑n(s) r ′ ( T t ) = ∑ s [ e ( s ) + 1 2 ] ∑ s n ( s ) = ∑ s e ( s ) + L ( s ) 2 ∑ n ( s )

如果将S替换为一个叶子节点，那么其错误个数为：
e′(Tt)=∑s[e(s)+12]=∑se(s)+L(s)2 e ′ ( T t ) = ∑ s [ e ( s ) + 1 2 ] = ∑ s e ( s ) + L ( s ) 2

因为其是近似服从正太分布的，所以我们可以给这个比较加一个标准差，允许其有一定的误差范围，则有
SE[e′(Tt)]=npq−−−√=n(t)e′(Tt)n(t)n(t)−e′(Tt)n(t)−−−−−−−−−−−−−−−−−−−√ S E [ e ′ ( T t ) ] = n p q = n ( t ) e ′ ( T t ) n ( t ) n ( t ) − e ′ ( T t ) n ( t )

所以我们就有了如下结论：
e′(t)<=e′(T(t))+SE[e′(Tt)] e ′ ( t ) <= e ′ ( T ( t ) ) + S E [ e ′ ( T t ) ]

如果在将子树假设为一个叶子节点时的错误个数 e′(t) e ′ ( t ) 小于子树总的错误个数和标准差之和，那么我们认为这个树Tt是可以被替换的，可以修建掉
- PEP优点：精度较高；不需要测试集，对于样本数据较少是非常有利的；自顶向下的效率更高，速度更快。
- PEP缺点：是一个采用自顶向下的后剪枝方法，这种策略带来的就是贪心的问题，有可能删除这个虽然会降低，但是保留这个，删除其子树可能精度更高，但是已经删除，无法再添加了

3.2.3 CCP剪枝(Cost-Complexity Pruning)方法——CART剪枝法

  • 过程：
    • 自底向上，通过原始决策树中的修剪得到一系列的树{T0,T1,T2,…,Tk}，其中Ti+1是由Ti中的一个或者多个子树被替换所得到的，T0为未经任何修剪的原始树，Tk为只有一个节点的树
    • 评价这些树，根据真是误差率来选择一个最优秀的树最为最后剪枝的树
  • 核心 ：我们应该如何得到一系列的树
    • 设e为分类错误的实例个数，L(S)为树中叶子节点的个数，N为训练集实例个数，则定义树T的CC为：
      eN+αL(T) e N + α L ( T )

      若某一子树S被叶子节点替换掉，得到一颗新树，用 ΔE Δ E 来表示错误个数的插值，而此时树T的叶子节点树就比原来少了L(s)-1个，未来保持CC不变，则必须有：
      α=ΔEN(L(s)−1) α = Δ E N ( L ( s ) − 1 )

      这样，我们针对每一个树T的子树进行计算CC，找到 α α 最小的值对应的子树，将其用叶子节点替换生成下一个树，采用递归的思想，我们就可以生成上述的一系列生成树了
  • 核心：我们应该如何选择：肯定是采用误差率的比较了，可以采用基于交叉验证的的方式来生成和检测树，最后取平均就好。或者也可以采用留出法，留出一定比例的测试集。而测试集的替代准则，我们可以采用PEP中的不等式的，来进行评判
  • CCP特点：只能从那一系列树中选择，而且每一个树T的生成都是在前面的条件下的，这样的话也会存在贪心的问题

4 连续值属性：

前沿：我们在之前的所有讨论中，为了方便我们都潜在的将属性的取值认为了离散值，但是对于连续属性该如何处理。
可以预见的是虽然属性取值范围是连续的，但是我们实际得到的数据集个数是有限的，那么这个属性的值也就是有限的，我们可以根据这一点来将连续和离散相互联系
1. 首先将连续属性所有值顺序排列，
2. 取相邻两点之间的中间值作为一次划分的标准，然后进行二分法，将数据集D分为D-和D+
3. 信息增益表达式改为只有两个取值的：

Gain(D,a)=maxt∈TaGain(D,a)=maxt∈TaEnt(D)−∑λ∈−,+|Dλt||D|Ent(Dλt) G a i n ( D , a ) = max t ∈ T a G a i n ( D , a ) = max t ∈ T a E n t ( D ) − ∑ λ ∈ − , + | D t λ | | D | E n t ( D t λ )

5 缺失值处理：

对于缺失值，我们如果将其直接舍去不用未免太过浪费了，而且对于数据集本身比较小的集合来讲，就更不能舍弃了否则会有极大的欠拟合情况发生，所以我们希望将缺失的值也放进去，但是放进去又不能直接放，它所含信息量要小与这个属性上没有缺失的。那么我们就要解决一下两个问题：
1. 如何在属性值缺失的情况下，进行属性划分？
2. 在属性划分之后，在该属性缺失的值应该放在那个分支里？

5.1 属性划分

针对第一个问题：
设 D^ D ^ 为数据集D中在属性a上没有缺失的样本子集，嘉兴属性a有V个可取值 {a1,a2,...aV} { a 1 , a 2 , . . . a V } ,其中 Dk^ D k ^ 表示无缺失样本第k类的样本子集， Dv^ D v ^ 表示属性a取值为v的无缺失样本子集，同时我们赋予D中每一个样本一个权重 wx w x ，并有如下定义：

θ=∑x∈D^wx∑x∈Dwxpk^=∑x∈Dk^wx∑x∈D^wxrv^=∑x∈Dv^wx∑x∈D^wx θ = ∑ x ∈ D ^ w x ∑ x ∈ D w x p k ^ = ∑ x ∈ D k ^ w x ∑ x ∈ D ^ w x r v ^ = ∑ x ∈ D v ^ w x ∑ x ∈ D ^ w x

由此我们可以直观的从上述定义中得到其具体含义：
θ θ ：在属性a上，无缺失值样本所占的比例
pk^ p k ^ ：在属性a上，无缺失值中第k类样本所占无缺失值的比例
rv^ r v ^ ：在属性a上，属性a取值为v的无缺失值占无缺失值的比例
有了上述的定义，我们就可以将其带入到我们的信息增益的定义中：
Gain(D,a)=θ∗Gain(D^,a)=θ∗(Ent(D^)−∑v=1VEnt(Dv^)) G a i n ( D , a ) = θ ∗ G a i n ( D ^ , a ) = θ ∗ ( E n t ( D ^ ) − ∑ v = 1 V E n t ( D v ^ ) )

其中
Ent(D^)=−∑k=1|y|pk^log2pk^ E n t ( D ^ ) = − ∑ k = 1 | y | p k ^ l o g 2 p k ^

5.2 属性缺失值的分配

对于问题2有一个原则：属性值没有缺失的，保持样本对应的权重不变；属性值缺失的则按照比例划为各个分支，样本权值的划分的时候，样本权值调整为 rv^∗wx r v ^ ∗ w x

最后

以上就是朴素爆米花为你收集整理的机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配的全部内容，希望文章能够帮你解决机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(58)

相关文章

回归树与基于规则的模型(part1)--if-then语句
回归树与基于规则的模型(part1)--if-then语句
分类器评价指标
分类器评价指标
scikit-learn决策树算法类库使用小结
scikit-learn决策树算法类库使用小结
[python机器学习及实践(4)]Sklearn实现决策树并用Graphviz可视化决策树
[python机器学习及实践(4)]Sklearn实现决策树并用Graphviz可视化决策树
机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配
机器学习笔记（二）——决策树基本原理1. 决策树模型2. 特征选择：3. 剪枝4 连续值属性：5 缺失值处理：5.2 属性缺失值的分配
机器学习中---分类模型--决策树模型
机器学习中---分类模型--决策树模型
JVM之垃圾回收机制JVM之垃圾回收机制
JVM之垃圾回收机制JVM之垃圾回收机制
JVM的4种垃圾回收算法、垃圾回收机制
JVM的4种垃圾回收算法、垃圾回收机制

评论列表共有 0 条评论

立即
投稿
返回
顶部