机器学习入门|决策树(二)

  1. 云栖社区>
  2. 博客>
  3. 正文

机器学习入门|决策树(二)

kissjz 2018-02-03 23:45:02 浏览6352
展开阅读全文

说来真是惭愧,今天上午看了一个阿里云大学的课,中午吃完饭就信心十足点击 “考试” 了,结果.....

WeChat_Image_20180203165350_2_

OK ,里面考了很多决策树的知识,想想也对,课程中唯一提到的机器学习算法就是决策树,你说考不考(ノへ ̄、)

总之,单单靠之前学习的一点知识机器学习入门|决策树(一)是远远不够对付这场考试的,以考促学,OK!

下面让我们再深入的了解一下决策树吧!

注:再看这一篇之前,最好先回顾一下上一篇机器学习入门|决策树(一),之前提过的概念,这篇就不再啰嗦啦(/▽\)

信息增益与ID3算法

ID3算法(Iterative Dichotomiser 3,迭代二叉树3代),是Ross Quinlan发明的一种决策树算法。

这个算法是建立在奥卡姆剃刀的基础上:越是小型的决策树越优于大的决策树(简单理论)。尽管如此,该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念:

$$ Ent(D)=-\sum_{k=1}^{|\gamma|}p_{k}log_{2}p_{k}. $$

进而引入信息增益:

$$ Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v}). $$

这个ID3算法可以归纳为以下几点:

  1. 分别计算各个属性的信息增益
  2. 选取其中信息增益最大的属性最为划分属性
  3. 生成包含该属性的结点

ID3算法的核心思想就是以信息增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

ID3算法的一些优缺点:

  1. ID3算法在构造决策树的结构时从不回溯,是一种典型的贪婪搜索算法
  2. 用信息增益选择属性时偏向于选择分枝比较多的属性值,即取值多的属性(这个在上一篇中提到了)
  3. 不能处理连续值的属性
  4. 不做剪枝,容易过拟合

增益比率与C4.5算法

信息增益是一种选择特征的有效办法,但是它偏向于选择取值较多的哪些特征。比如,按编号进行划分,会产生庞大的分支,而每一支分支只包含一个样例。这种情况下为“纯”划分,此时信息增益为最大,但是这种划分对于分类并无意义。因此需要对具有不同特征值数目的特征进行校准。于是C4.5算法就在ID3的基础上引入了增益比率

$$ Gain-ratio(D,a)=\frac{Gain(D,a)}{IV(a)}, $$

其中

$$ IV(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|} $$

C4.5算法改进了ID3算法,ID3算法只能处理离散型特征,而C4.5算法能够处理连续型特征。C4.5算法对数据进行预处理将连续型特征离散化。

那么,问题来了。

怎么将连续型的特征离散化呢?

最简单的策略是采取二分法(bi-partition)对连续属性进行处理,这正是C4.5决策树算法中采用的机制。

给定样本集$D$和连续属性$a$,假定$a$在$D$上出现了$n$个不同的取值,将这些值从小到大进行排序,记为$\left\{a^{1},a^{2},...,a^{n}\right\}.$基于划分点$t$可将$D$分为子集$D_{t}^{-}$和$D_{t}^{+}$,其中$D_{t}^{-}$包含那些属性$a$上取值不大于$t$的样本,$D_{t}^{+}$相反。显然,对于相邻的属性取值$a^{i}$与$a^{i+1}$来说,$t$在区间$[a^{i},a^{i+1})$中取任意值所产生的划分结果相同。因此,对连续属性$a$,我们可考察包含$n-1$个元素的候选划分点集合

$$ T_{a}=\left \{ \frac{a^i+a^{i+1}}{2}|1\leqslant i\leqslant n-1 \right \}, $$

即把区间$[a^i,a^{i+1})$的中位点作为候选划分点。然后,我们就可以像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分

$$ Gain(D,a)=\underset{t\in T_a}{max}\;Gain(D,a) $$

$$ =\underset{t\in T_a}{max}Ent(D)-\underset{\lambda \in \left\{-,+ \right \}}{\sum}\frac{|D^{\lambda }_{t}|}{|D|}Ent(D^{\lambda }_{t}) $$

其中$Gain(D,a,t)$是样本集$D$基于划分点$t$二分后的信息增益。于是,我们就可选择使$Gain(D,a,t)$最大化的划分点

这里可能有难理解,举个例子。就比如说判别一个西瓜好坏的属性中有一个叫做“纹理”,它就是可以用ID3算法来处理的离散值,取值有1.清晰,2.稍糊,3.模糊.很容易根据ID3中信息增益的公式求出其信息增益。好了,现在回到我们要处理的连续值,这可麻烦大了!连续值该怎么求!因为不是说取固定一个值来作为划分点,我们这里是要找到连续值属性比如密度的信息增益,求法如上,比如可以得到密度$\leqslant $0.318的为好瓜,反之为坏瓜,当然如果划分出来的“纯度”还是不高,那还可以再分,也可以再次用密度这个属性(注意!!这跟离散值不同了,离散值属性划分完就不可以再用了)。OK,对比一下,仔细思考,希望能理解,不理解可以留言噢( ̄︶ ̄)↗

再次强调,与离散属性不同,若当前结点划分属性为连续属性,该属性还可以作为其后代结点的划分属性

和ID3相比的改进:

  1. 用信息增益率代替信息增益
  2. 能对连续属性进行离散化,对不完整数据进行处理
  3. 进行剪枝

补充:在阿里云大学课堂中还介绍了C50算法,其相对于C4.5的改进:

  1. 使用了boosting
  2. 预剪枝,后剪枝

Gini指数与CART算法

CART(classification and regression tree)算法,即分类回归树,顾名思义,是一个既能用于分类(如ID3算法,C4.5算法),又能用于回归的算法。

至于基尼指数计算都在机器学习入门|决策树(一)中了。

根据视频中的,CART总结:

  1. 核心是基尼系数(Gini)
  2. 分类是二叉树
  3. 支持连续值和离散值
  4. 后剪枝进行修剪
  5. 支持回归,可以预测连续值

总结

WeChat_Image_20180203231840_1_

OK !写完这篇博客,再战!
WeChat_Image_20180203232108_1_

啥?只是飘过,有啥得意的╰( ̄ω ̄o)

但我觉得,OK就行!

参考:

wiki
于 剑 《机器学习:从公理到算法》
周志华 《机器学习》

网友评论

登录后评论
0/500
评论
kissjz
+ 关注