• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

机器学习导论(10)-决策树

ml admin 3年前 (2016-11-19) 1206次浏览 0个评论 扫描二维码

 决策树概念

决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

可以看到,决策树的决策过程非常直观,容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法,下面介绍决策树的构造算法。

qhiqhqjcmkp105s

上图以一个西瓜的决策树为例,决策树的判定顺序就是一个树的搜索过程,首先判定西瓜的色泽,若西瓜的颜色是青绿色,则继续判定当前西瓜的根蒂情况,要是蜷缩的话继续听敲声,若敲声浑浊,则可以判定当前的西瓜是个好瓜,如此完成决策树决策的过程。

决策树的构造

不同于贝叶斯算法,决策树的构造过程不依赖领域知识,它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支,其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况:

1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支。

3、属性是连续值。此时确定一个值作为分裂点 split_point,按照>split_point 和<=split_point 生成两个分支。

如何选择最优划分属性的方法是决策树的关键所在,常用的有 ID3 算法(信息增益算法),C45 算法(增益率)和 CART 算法

ID3 算法

信息论知识中我们直到,期望信息越小,信息增益越大,从而纯度越高。所以 ID3 算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。

设 D 为用类别对训练元组进行的划分,则 D 的(entropy)表示为:

其中 pi 表示第 i 个类别在整个训练元组中出现的概率,可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是 D 中元组的类标号所需要的平均信息量。

现在我们假设将训练元组 D 按属性 A 进行划分,则 A 对 D 划分的期望信息为:

而信息增益即为两者的差值:

ID3 算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。下面我们继续用 SNS 社区中不真实账号检测的例子说明如何使用 ID3 算法构造决策树。为了简单起见,我们假设训练集合包含 10 个元素:

其中 s、m 和 l 分别表示小、中和大。

设 L、F、H 和 R 表示日志密度、好友密度、是否使用真实头像和账号是否真实,下面计算各属性的信息增益。

因此日志密度的信息增益是 0.276。

用同样方法得到 H 和 F 的信息增益分别为 0.033 和 0.553。

因为 F 具有最大的信息增益,所以第一次分裂选择 F 为分裂属性,分裂后的结果如下图表示:

在上图的基础上,再递归使用这个方法计算子节点的分裂属性,最终就可以得到整个决策树。

上面为了简便,将特征属性离散化了,其实日志密度和好友密度都是连续的属性。对于特征属性为连续值,可以如此使用 ID3 算法:

先将 D 中元素按照特征属性排序,则每两个相邻元素的中间点可以看做潜在分裂点,从第一个潜在分裂点开始,分裂 D 并计算两个集合的期望信息,具有最小期望信息的点称为这个属性的最佳分裂点,其信息期望作为此属性的信息期望。

C4.5 算法

ID3 算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性 ID,则 ID3 会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3 的后继算法 C4.5 使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。

C4.5 算法首先定义了“分裂信息”,其定义可以表示成:

其中各符号意义与 ID3 算法相同,然后,增益率被定义为:

C4.5 选择具有最大增益率的属性作为分裂属性,其具体应用与 ID3 类似,不再赘述。

ID3 算法和 C45 对比

ID3 对于可取值数量较多的属性具有较好的偏好,C45 则对可取值数量较少的属性具有较好的偏好

CART

代表单个样本的个属性,表示所属类别。CART 算法通过递归的方式将维的空间划分为不重

叠的矩形。划分步骤大致如下

(1)选一个自变量,再选取的一个值维空间划分为两部分,一部分的所有点都满足

另一部分的所有点都满足,对非连续变量来说属性值的取值只有两个,即等于该值或不等于该值。

(2)递归处理,将上面得到的两部分按步骤(1)重新选取一个属性继续划分,直到把整个维空间都划分完。

 

在划分时候有一个问题,它是按照什么标准来划分的 ? 对于一个变量属性来说,它的划分点是一对连续变量属

性值的中点。假设个样本的集合一个属性有个连续的值,那么则会有个分裂点,每个分裂点为相邻

两个连续值的均值。每个属性的划分按照能减少的杂质的量来进行排序,而杂质的减少量定义为划分前的杂质减

去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用Gini 指标,假设一个样本共有类,那么

一个节点的 Gini 不纯度可定义为

其中表示属于类的概率,当 Gini(A)=0 时,所有样本属于同类,所有类在节点中以等概率出现时,Gini(A)

最大化,此时

有了上述理论基础,实际的递归划分过程是这样的:如果当前节点的所有样本都不属于同一类或者只剩下一个样

本,那么此节点为非叶子节点,所以会尝试样本的每个属性以及每个属性对应的分裂点,尝试找到杂质变量最大

的一个划分,该属性划分的子树即为最优分支。

下面举个简单的例子,如下图

上述图中,属性有 3 个,分别是有房情况,婚姻状况和年收入,其中有房情况和婚姻状况是离散的取值,而年

收入是连续的取值。拖欠贷款者属于分类的结果。

假设现在来看有房情况这个属性,那么按照它划分后的 Gini 指数计算如下

而对于婚姻状况属性来说,它的取值有 3 种,按照每种属性值分裂后 Gini 指标计算如下

 

最后还有一个取值连续的属性,年收入,它的取值是连续的,那么连续的取值采用分裂点进行分裂。如下

 

根据这样的分裂规则 CART 算法就能完成建树过程.

 

部分参考:

http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html

http://blog.csdn.net/acdreamers/article/details/44664481


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明机器学习导论(10)-决策树
喜欢 (1)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!