决策树的经典算法_ID3与C4_5

2007 年第 5 期
这时的不确定程度比概率均为 0. 5 小 , 则对应的期望信 0. 2 0. 8 息 : I = - ( 0. 2 ・ log2 + 0. 8 ・ log2 ) = 0. 72 决策树的生成过程也就是不确定性程度不断降低的 过程 。 ( 2 ) 计算属性 A, 每个取值的信息期望 I ( A = aj ) , j = 1, 2, …, m 设 : A 为数据集的某一属性 , A 的取值为 : a1 , a2 , …,
信息增益 Ga in (A ) 越大 , 则属性 A 对于分类提供的信 息量越大 , 则选择属性 A 之后对于分类的不确定程度越 小 。因此将计算出的各个属性的信息增益对比 , 选择信息 增益最大的属性作为根节点 。 S tep2. 由根节点属性的不同取值建立分支 ; S tep3. 采用递归 ( Recursively) 的方法 , 对各分支的子 集仍然选择信息增益最大的属性作为子节点 …… 直到所有的子集包含同一类别的数据为止 。 由以上步骤就能构造一棵决策树 , 可以用它来对新的 样本进行分类 。 [2] 2. 2 C4. 5 算法 C4. 5 算法是构造决策树分类规则的一种算法 , 它是 I D 3 算法的扩展 。 I D 3 算法只能处理离散型的描述性属 性 ,而 C4. 5 算法还能够处理描述属性取值为连续型的情 况 。选取节点的标准是最大信息增益率 ,具体的算法步骤 如下 : Step1. 对数据源进行数据预处理 , 将连续型的属性变 量进行离散化处理形成决策树的训练集 (如果没有连续取 值的属性则忽略 ) ; ( 1 ) 根据原始数据 , 找到该连续型属性的最小取值 a0 、 最大取值 an + 1 ; ( 2 ) 在区间 [ a , b ]内插入 n 个数值等分为 n + 1 个小 区间 ; ( 3 ) 分 别 以 ai , i = 1, 2, …, n 为 分 段 点 , 将 区 间 a0 , an + 1 划分为两个子区间 :
此时 , 训练数据集分类的信息期望 :
I = - i∑ pi ・ log2 3 =1
pi
k
( 1)
I表示把训练数据集 D, 划分为 k 类的不确定性程度 。
设训练数据集分为两类 : D1 , D2 , 若 :训练数据集属于这两类的概率均为 0. 5, 这时的不确 定程度最大 , 则对应的期望信息 : l = - 2 × 0. 5・log2 = 1 若 :训练数据集属于这两类的概率均分别为 0. 2、 0. 8,
于第 i类 ( D i ) 的条件概率 , 记为 pij : pij =
dij dj ,
k
则 I ( A = aj ) = - i∑ pij log2 =1
m
p属性 A 信息熵 En tropy ( A ) En tropy ( A ) = j∑ pj ・ I ( A = aj ) =1 ( 3) dj d
第 17 卷第 5 期 四川文理学院学报 (自然科学 ) Vol . 17 No. 5 S ichuan Un iversity of Arts and Sc ience Journa l( Na tura l Sc ience Ed ition )
2007 年 9 月 Sep. 2007
3
决策树的经典算法 : I D 3 与 C4. 5
0. 5
[收稿日期 ]2007 —06 —14 [作者简介 ]黄 文 ( 1981 —) ,女 ,四川大竹人 ,助教 , 2006 级硕士研究生 ,主要从事金融数量分析及智能金融研究 。
对函数以 2 为底 ,其原因是信息用二进制编码 。
16
黄 文
1, 2
:决策树的经典算法 : ID 3 与 C4. 5
3 3
标准就能够克服这一问题 。 C4. 5 算法还针对属性取值为 连续数据进行了处理 ,弥补了 I D 3 算法只能处理离散的属 性数据这一缺陷 。
2 I D 3 算法与 C4. 5 算法的描述
2. 1 I D 3 算法 1986 年 Quinlan 提出的 I D 3 算法是基于决策树学习
am , dj : A = aj的观测数 , dij :当 A = aj 时 , 对应的属于子集 D j的观测数 , 实例属
[ a0 , aj ], [ ( ai + 1 , an + 1 ) ]对应该连续型的属性变量的 两类取值 , 有 n 种划分方式 ; Step2. 计算每个属性的信息增益和信息增益率 ; ( 1 ) 计算属性 A 的信息增益 Ga in ( A ) 信息增益 Ga in ( A ) 的计算和 I D 3 算法中的完全一致 ; ( 2 ) 计算属性 A 的信息增益率 Ga in - R atio ( A ) Ga in - R a tio (A ) = Ga in ( A ) I (A ) ( 5)
中最重要的一种算法 , 最具代表性 , 在国际上的影响也最 大 。有大量的学者围绕该算法作了广泛的研究 ,并提出了 多种改进算法 。下面对 I D 3 算法进行详细的叙述 。 决策树的生成过程也就是一个树的节点的选择过程 :
Step1. 计算所有属性的信息增益 , 选择信息增益最大
的属性作为根节点 ;
黄 文
1, 2
( 1. 西南石油大学 理学院 ,四川 成都 610500; 2. 西南财经大学 统计学院 ,四川 成都 610074 )
【 摘 要】 决策树各类算法 ,各有特点 ,其中 J. R. Quinlan提出的 I D 3 算法最具代表性 ,在国际上的影响 也最大 , C4. 5 算法就是在 I D 3 算法基础上进行改进得到的 。通过对两种算法详细描述 , 阐明了决策树算 法步骤及其主要思想 。 【 关键词 】 I D 3; C4. 5; 信息增益 ; 信息增益率 ; 剪枝
其中 : dj 为 A = aj 的观测数 , pj =
( 4 ) 计算属性 A 的信息增益 Ga in ( A )
属性 A 对于分类提供的信息量 , 叫做属性 A 的信息增 益 , 记为 Gain ( A ) , 则 :
Ga in ( A ) = En tropy ( A ) - I ( 4)
对于取值连续的属性而言 , 分别计算以 ai ( i = 1, 2, …, n ) 为分割点 , 对应分类的信息增益率 , 选择最大信息 增益率对应的 ai , 作为该属性分类的分割点 。 选择信息增益率最大的属性 , 作为当前的属性节点 , 得到决策树的根节点 。 Step3. 根节点属性每一个可能的取值对应一个子集 , 对样本子集递归地执行以上 Step2 过程 , 直到划分的每个 子集中的观测数据在分类属性上取值都相同 , 生成决策 树。 Step4. 根据构造的决策树提取分类规则 , 对新的数据 集进行分类 。 类似算法的主要思想都是 , 逐步找出能够为各个层次 的分类提供最大信息量的变量 , 由此可以确定决策树从根 到枝 , 再从枝到叶的结构 。决策树生成的过程也就是对训 练数据集进行分类的过程 。
17
2007 年第 5 期
黄 文
1, 2
:决策树的经典算法 : ID 3 与 C4. 5
判率 。采用训练数据集作为测试集 ,取置信区间的上限作 为对误判率的估计 。给定一个显著性水平度 α ( C4. 5 算 法中默认 α = 0. 25 ) , 显然错误的总数服从二项分布 , 则 有:
P
Step5. 在剪枝的过程中修正各个属性的隶属函数 ; Step6. 从决策树中提取分类规则 。
|p - p |
p ( 1 - p ) /N
e e
e
> u1 - α =α
( 6)
其中 : N 为被修剪的子树下的实例总数 , E 为修剪后出现 的错误实例数 ,
p= E e 是实际观测到的误判率 , p 为估计的误判率 。 N
3 决策树的简化
从前文对 I D 3 和 C4. 5 算法的描述中可以看到这种算 法使用的分类准则是以信息论的概念为基础的 ,而信息论 也正在不断的发展完善 。但许多分类规则都存在一个普 遍的问题 — 过度拟合 ,由训练集生成的决策树对训练集分 类的结果很好 ,但用它来对未参与决策树生成过程的新的 数据集进行分类得到的结果 ,可能并不理想 。因此有必要 对生成的初始决策树进行简化修正 , 也称为剪枝 , 来得到 更一般的分类规则 ,剪枝后得到的新的决策树可能会使得 它对训练集分类的误判率增大 ,但同时却能减少对新的数 据集分类的误判率 。 Quinlan提出 的 剪 枝 方 法 是 一 种 悲 观 错 误 修 剪 法 ( Pessim istic Error Pruning) ,因为用生成决策树的训练数据 集来检验误判率时 ,实际上对错误的估计过于乐观了 , 因 为决策树是由训练数据集生成的 , 所以 , 在多数情况下决 策树与训练数据集是符合的 。但把决策树用于对训练数 据以外的数据进行分类时 ,很明显这时的错误率将大大增 加 。基于以上原因 , Quinlan 借用二项分布对训练数据中 的误判率加以修正 , 以得到更为符合实际的错误率 。显 然 ,与修正前的错误率相比 ,修正后的错误率增大了不少 , 因此认为它对错误率的看法是“ 悲观 ” 的 。下面我们进一 步讨论决策树的剪枝 (简化 )过程 。 决策树的简化过程 : 对决策树上所有非叶节点 A 进行计算分析 。从树的 根节点开始 ,计算每个分枝节点被剪也即被叶替代后的误
( 1 )计算给定的训练数据集分类的信息期望 I
记 :训练数据集为 D, 分为 k 类 , 也即 k 个子集 : D1 ,
D2 , …, D k , d :数据集中观测的总数 , di : D i中的观测数 , 则一个实例属于第 i类的概率 : pi = d1 d ( i = 1, 2, …, k ) ,
[中图分类号 ]O24 [文献标识码 ]A [文章编号 ]1008 - 4886 ( 2007 ) 05 - 0016 - 03