淘先锋技术网

首页 1 2 3 4 5 6 7

算法概述

决策树 是一种基本的分类与回归方法。这里我们主要讨论用于分类的决策树。在分类过程中,根据各个特征对实例进行分类,它可以认为是 if - then 规则的集合,最大的优点是可读性强,分类速度快。 决策树 的学习通常包含三个步骤:特征选择、决策树的生成和决策树的剪枝。

首先我们通过一个日常例子来直观了解一下 什么是决策树

生活中父母在为孩子介绍对象时候,发生的经典对话

女儿:年龄多大了?
母亲:27
女儿:长得帅吗?有照片吗?
母亲:有,你瞅瞅?
女儿:还不错,什么学历啊?
母亲:研究生毕业
女儿:可以的,现在做什么工作的?待遇怎么样啊?
母亲:公务员,待遇不算很高6000,但是各项福利很好!
女儿:有房吗?
。。。。。。

女儿:那我去见见面再说吧

这里的女孩的决策过程,就是根据各个条件一步一步筛选下来的,我们换成图标来看一下:

这里写图片描述 (图片来源见水印)
上图中的绿色节点表示判断条件,橙色节点表示决策结果,箭头表示在一个判断条件下的不同决策路径。

通过这个例子可以看出决策树 的中心思想,如果我们将各个判断条件量化,则变成真正的决策树
下面我们正式定义决策树:
分类决策树模型是一种描述对实例进行分类的树形结构,决策树有节点和有向边组成。节点有两种类型:内部节点和叶节点,内部节点表示一个特征或者属性,叶节点表示一个类

特征选择

因为决策树的中心思想是根据特征来进行分类,那么采用哪些特征就显得尤为重要,只有对结果的分类效果比较明显的特征才适合作为模型的特征。

这里为了量化分类效果,我们引入熵,是信息论中的概念,表示随机变量不确定性的度量。

H(x) = -∑p(xi)log(p(xi)) (i=1,2,..n)
其中,x 是不同的离散随机变量,p 是对应的概率

也就是说熵越大,则不确定性越大(即分类效果差,和随机抽取的结果一样)

条件熵 H(Y|X) :表示在已知随机变量X 的条件下 随机变量Y 的不确定性。 定义为X给定条件下Y 的条件概率分布 的熵对X 的数学期望。

H(Y|X) = ∑pi * H(Y|X=xi) (i=1,2,..n)
(更多可参考 https://blog.csdn.net/yizhen_nlp/article/details/70765037

接下来介绍信息增益,信息增益表示得知特征X的信息而使得类Y 的信息的不确定性减少的程度。
“特征A 对训练数据集D 的信息增益 g(D,A) ,定义为集合D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件熵 H (D|A) 之差, 即
g(D,A) = H(D) - H(D|A) ”

ID3 算法

ID3 的核心是在决策树各个节点上应用信息增益准则选择特征,递归的构建决策树,具体方法是:从根节点开始,对节点计算所有可能的特征的信息增益,选择信息增益最大的特征作为节点的特征,由该特征的不同取值建立子节点;在对子节点递归的调用以上方法,直到所有特征的信息增益均很小或者没有特征可以选择为止。
选择依据 g(D,A) = H(D) - H(D|A)
(信息增益越大越好)

C 4.5 算法

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

信息增益率 gR (D,A) = g(D,A) / H(D) 即 信息增益除以开始的信息熵。

(信息增益率越大越好)

CART 算法

CART 假设决策树是二叉树,内部节点特征的取值为 是 和 否。
采用特征选择依据为 基尼指数
基尼指数定义:
这里写图片描述

如果训练数据集D根据特征A是否取某一可能值a被分割为D1和D2两部分,则在特征A的条件下,集合D的基尼指数定义为这里写图片描述

(基尼指数越小越好)

最后,决策树模型建立完成后,为防止过拟合,需要进行剪枝,不再赘述