D0I:10.13374/i.issn1001053x.2001.02.022 第26卷第2期 北京科技大学学报 Vol.26 No.2 2004年4月 Journal of University of Science and Technology Beijing Apr.2004 增量决策树算法及复杂度分析 尹阿东宫雨吴胜利武森高学东李拥军 北京科技大学管理学院，北京100083 摘要介绍了增量决策树算法的基本原理，并从实例费用和信息熵费用两个角度出发，对 增量决策树算法的复杂度进行分析.通过实例说明，增量决策树算法能够构造出与D3算法 形态基本相同的决策树. 关键词决策树：增量算法：复杂度 分类号TP18 增量D3算法的雏形出现在1986年，是由分类能力高的属性为准，增量算法构造决策树的 Schilimmer和Fisher首先提出的，定名为D4 这种思想保证了作为节点的分类属性始终包含 (Iterative Dichotomizer4)算法，并且Fisher在l987 有最大的信息量，能够保证构造的决策树一直沿 年利用D4算法的思想构造出一个增量学习系 着熵减最大的方向拓展. 统川.但是，D4算法在构造增量决策树的时候， 假设一个给定的决策树节点上存在两个候 不得不多次根据不同的训练集来重构决策树，需 选属性F1和F2,并且经计算可知，属性F1的信 要昂贵的计算费用才能完成增量决策树的构建， 息增益大于属性F2的，所以将属性F1作为分类 1989年，Massachuasetts大学计算机学院的Utgoff 属性.当新增一条记录时，将对属性F1和F2的 教授在D3算法思想的基础上提出一种新的增 信息增益产生影响，属性F1和F2信息增益大小 量决策树算法—ID5R(Revision)m.ID5R算法继 的变化有可能导致分类属性的变化.引起的信息 承D3算法的全部优点，并且在原有D3算法的 熵的变化如下： 基础上进行合理的改进，解决了D3算法不能处 △E=E-E=6+A A 理增量数据集的缺点.1994年Utgof任教授又提出 ptntl pinpin+1 (pin)(pinti)(1) 的ITI算法，解决了增量数据集中数值属性的分 式中，t=一p品an叫on p+n,' A=p.lb p.t p+n. 类问题，同时还可以对连续的数值属性进行离散 ab2元-e*ia prtn+T-nlb n bp+n+i其中p,和m,分 处理，然后再进行分类.2000年，Kalles和Papage- 别代表分类属性所覆盖的正例集数量和负例集 s对原有的增量决策树算法进行适当的改进，利 数量（这里只考虑二值类主属性，类主属性的取 用启发式原理解决了增量算法构造决策树稳定 值也可以是多值的，原理相同) 性的问题，提高了决策树分类的准确率. 根据改进并证明的与增量算法相关的两个 定理： 1增量决策树算法 定理1x,y∈[0，+o],有0≤A(x,y)≤lb(x+y+1)+ 当有新记录加入训练数据集时，有可能产生 lbe恒成立. 原先选定的分类属性对新记录分类能力降低，而 定理2e≤p叶n. 原先未被选中的候选属性集中的某个属性的分 将定理1,2代入式(1)中，得到熵变△E的上下 类能力增高的情况.在这种情况下，构造决策树 界：当4仁0pn时，得△S的下界A二p 时的分类属性选择就要以候选属性集中的那个 当A=lb(x+y+1)+lbe,e=0时，得△E的上界△Ew≤ 收稿日期2002-06-10 尹阿东男，28岁，博士研究生 Ib(x+y+1)+lbe p+n+l *国家自然科学基金资助项目(No.50074005)第2 6 卷 第 2 期 2 0 0 4 年 4 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n iv e rs i ty o f S c i e n e e a n d Te e b n 0 I O盯 B e ij in g V 匕1 . 2 6 N o . 2 A P r. 2 0 4 增量决策树算法及复杂度分析 尹 阿 东 宫 雨 吴 胜 利 武 森 高学 东 李拥 军 北 京科技 大学管 理学 院 , 北 京 10 0 0 8 3 摘 要 介绍 了增量 决策 树算 法的基 本原 理 , 并 从实例 费用 和信 息嫡 费用两 个角度 出发 , 对 增量 决策树 算法 的复 杂度进 行分 析 . 通过 实例 说明 , 增量 决策树 算法 能够 构造 出与 I D 3 算 法 形态基 本相 同 的决策树 . 关键词 决策树 ; 增量 算法 ; 复杂 度 分类号 T P 1 8 增量 ID 3 算法 的雏 形 出现 在 19 86 年 , 是 由 S e ih lim m e r 和 F i s h e r 首 先 提 出 的 , 定 名 为 DI 4 ( It e art i v e D i e h o t o m i z e r 4 )算 法 , 并 且 F i s h e r 在 19 8 7 年 利用 ID 4 算法 的思想 构 造 出一 个增 量 学 习 系 统 `1 . 但 是 , ID 4 算 法在 构造 增 量 决策 树 的时 候 , 不得 不 多次根 据不 同 的训练集 来重 构决 策树 , 需 要 昂贵 的计算 费用才 能完 成增 量 决策树 的构 建 . 19 89 年 , M a s s a e h au s e t s 大学 计算 机 学 院的 U t g o f 教 授在 DI 3 算 法 思想 的基 础上 提 出一 种 新 的增 量 决策树 算 法— ID S R (R e v i s i o n ) `, , . ID S R 算 法继 承 DI 3 算法 的全 部优 点 , 并且在 原 有 DI 3 算 法 的 基础 上进 行 合理 的 改进 , 解 决 了 DI 3 算 法 不 能处 理增 量数 据 集 的缺 点 . 19 94 年 Ut go f 教授 又提 出 的I T I 算法【3] , 解 决 了增 量数据 集 中数 值属 性 的分 类 问题 , 同 时还 可 以对连 续 的数 值 属性进 行 离散 处理 , 然 后 再进 行分 类 . 2 0 0 年 , aK le s 和 P ap ag e - h s 对 原有 的增量 决策 树算法 进行 适 当的 改进 , 利 用 启发 式 原理 解 决 了增 量 算 法构 造 决策 树 稳 定 性 的 问题 , 提高 了决 策 树分类 的准确 率阅 . 分类 能力高 的属性 为准 . 增 量算 法构造 决 策树 的 这 种 思想 保 证 了作 为 节 点 的分 类 属性 始 终包 含 有 最大 的信 息量 , 能够 保证 构造 的决 策树 一直沿 着嫡 减 最 大 的方 向拓展 l稠 . 假 设 一个 给 定 的 决 策树 节 点上 存 在 两个 候 选 属性 lF 和 F Z , 并且 经计 算 可知 , 属 性 lF 的信 息 增益 大 于属 性 FZ 的 , 所 以将 属性 lF 作 为分类 属 性 . 当新 增一 条记 录 时 , 将 对 属性 lF 和 F Z 的 信 息增 益产 生 影响 , 属性 lF 和 F Z 信 息 增益 大 小 的变 化 有可 能导致 分类属 性 的变化 . 引起 的信息 墒 的变 化 如下 : AE 一“ , 一“ 一 备 一 六 一 渝下两奋丽) ( , ) 式 中 , 一誉巨圈 +n ,lb除)… , ` 一 P,l 唁翰 十 n,l 喘 一 * ` )唠击 一 n,l 七常百 , 其 中卿盼 1 增 量 决策 树 算 法 当有新 记录 加入 训练 数据 集 时 , 有可 能产 生 原先选 定 的分类 属性对 新记 录分 类 能力 降低 , 而 原先 未被 选 中的候 选 属性 集 中的 某个 属 性 的 分 类 能力增 高 的情 况`6] . 在这种 情况 下 , 构造 决策树 时 的分类 属 性选 择 就 要 以候 选 属性 集 中的 那个 收稿 日期 2 0 02 刁6 一 10 尹 阿 东 男 , 28 岁 , 博 士 研究 生 * 国家 自然科 学基 金资助 项 目 ( N o 5 0 O74 0 0 5) 别代 表 分 类 属性 所 覆 盖 的正 例 集数 量 和 负例 集 数量 ( 这 里只 考虑 二 值 类 主属 性 , 类 主属 性 的取 值 也可 以是 多值 的 , 原理相 同) . 根 据 改 进 并 证 明 的与 增 量 算 法 相 关 的两 个 定理 : 定理 I V x 沙任 「0 , + 。 」 , 有 0 ` A (x , 夕)引b (+x, 汗 1) + lb曰恒成 立 . 定理 2 : 印 + .n 将 定理 l , 2 代入 式 ( l) 中 , 得到 嫡变△百的上 下 界: 当 , 一 。 , : 一 +P 。 时 , 得 二的下界 mAE , : 二共 下; 一 , ` - · - 一 ’ 一 ’ 一 P 十n 十 1 ’ 当A = lb (x 勺斤 1)+l b e , 。 = 0 时 , 得△百的上 界△百山ax ` l b ( x +) 咔 1) + l b e P + n + DOI: 10. 13374 /j . issn1001 -053x. 2004. 02. 022