增量决策树算法及复杂度分析

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

Vol.26 No.2 尹阿东等：增量决策树算法及复杂度分析 ·203· 下面讨论如何利用增量算法解决增量数据 有d个属性，所以增加一条记录而确定d个属性的 集构造决策树的问题.在决策树的某一节点上， 正负实例数量的计算复杂度为d.然后确定一级 分类属性与候选属性熵值的差决定了增加记录 决策树上(d-l)个属性上的正负实例数量的费用 的最大数量aw, 是(d-1).最不理想的情况下，一条记录修改决策 (p+n+1)E2-E) (2) 树所需要的实例费用为： 1bb,+2+lbe 式中，b,=p+%是属性j值段上记录的数量. i=d(d-D)-ad) 2 (3) 根据式(2)，给出如下策略构造增量决策树： 第二部分考虑在决策树根节点上分类属性 当新增记录asamsx时，新增记录后的分类属 变化所带来的费用.设Pa(d为最不理想的情况 性信息熵值小于候选属性的信息熵值，仍然选择 下，决策树节点上分类属性发生变化时引起的费 原先的分类属性作为节点属性， 用.当决策树只有一个属性时，不能更新决策树， 当新增记录a>amm时，新增记录后的分类属 Pa(1)=0.当决策树有两个属性时，由于决策树根 性信息熵值大于候选属性的信息熵值，选择候选 节点上新增实例费用己经在第一步计算出来，并 属性作为节点属性， 且第一层上只能有一个属性，没有候选属性，所 以Pa(2)=0.随着d值的增加，实例费用来源于叶 2增量决策树算法的复杂度分析 子上升为节点的过程，当决策树有三个属性时， 对于一个给定的数据集，分析在最不理想的 在决策树的第一层上有一个候选属性，每个候选 属性有b个可能的取值种类，每个值段上都需要 情况下，构造一棵决策树的复杂度，这种最不理 计算正例集和负例集的数量，正例集和负例集数 想的情况特指利用全部的候选属性构造了一个 量的计算是将每个候选属性值段下的b棵子树中 层次最多的决策树的情况，在本文中，从两个方 包含的正例集和负例集数量求和得到的，所以单 面考虑决策树的复杂度. 独计算正例集的费用为，负例集的费用也是 第一个方面是测量当有新增记录加入时，计 b×b=b.由于候选属性的个数为(d-2)个，故整个 算正例集和负例集数量所需要的计算费用，新增 的实例费用为2b2×(d-2). 一条记录带来的这种计算费用叫做实例费用(n- 最不理想的情况是从决策树的最低层将分 stance-Count Addition). 类属性提升到根节点上，此时需要的实例费用最 第二个方面是根据信息熵原理测量选择分 类属性时需要的计算费用叫做信息熵费用(E 大，上述已经推出决策树最高两级的费用为2b× (d-2),当决策树的属性d增多时，每个属性所对 Score Calculations).这种测量方法需要计算每个 应的b棵子决策树的费用为b×Pa(d-1),其中b为 属性的信息熵，选择信息量最大的属性作为分类 属性的值段数量.所以可得如下的费用公式： 属性，所以这种测量方法的计算复杂度是极为昂 Pa(d0=∑b-2×2b2×(d-i)=Ob (4) 贵的， 现作如下假设：给定一个训练数据集，包含n 第三部分考虑递归地重构子决策树，重新选 个记录，d个候选属性，其中属性最多有b个值段， 择子决策树根节点上最好的分类属性所引起的 分析增量决策树算法的计算复杂度 费用.提升一个属性来替换旧分类属性的过程将 2.1增量决策树算法实例费用 导致实例费用的产生，这个费用是由每个子决策 增量决策树算法修改决策树时包含三部分 树下一级的候选属性的费用总和决定的 费用：第一部分是当有新记录加入时，计算正负 假设一个分类属性重构b棵新子树，设Ra(d) 实例集数量的费用：第二部分是在根节点选择分 是最不理想情况下，在决策树第(d-1)层构造b棵 类属性，重构决策树的费用：第三部分是为了确 决策树的费用. 定每个子树根节点上的分类属性而递归地构造 当d=1时，决策树除根节点外没有其他属 决策树的费用， 性，故Ra(1)=0. 第一部分，考虑新增一条记录，在对决策树 当d=2时，只有一个候选属性，在决策树的 的形态没有影响的情况下，所带来的计算费用. 第一层上，意味着在该属性下没有子决策树，故 假设一个已经拓展开的决策树，在根节点上因为 Ra(2)=0

、 勺L Z` N 0 . 2 尹 阿东 等 : 增量 决 策树算 法 及复杂 度 分析 . 2 03 . 下 面 讨 论 如 何 利 用 增 量 算法 解 决增 量 数 据 集 构 造 决策 树 的 问题 . 在 决 策树 的某一 节 点上 , 分类 属 性 与 候选 属 性 嫡 值 的 差决 定 了增加 记 录 的最 大 数量 a ~ , _ 扮 n + 1)(zE 一 E , ) l b bj + 2+ l b e ( 2 ) 有 d个 属性 , 所 以增 加 一条记 录 而确 定d 个属性 的 正负 实例 数 量 的计 算 复杂 度 为d . 然 后确 定一 级 决策树 上 d( 一 l) 个 属性 上 的正 负实 例 数量 的 费用 是 d( 一 1) . 最 不理 想 的情 况下 , 一条 记 录修 改 决策 树 所 需要 的实例 费 用 为 : 式 中 , 九= jP + nj 是 属 』 由值 段 上记 录 的 数量 , 根 据 式(2 ) , 给 出如 下策 略构 造 增量 决 策树 : 当 新增 记 录a ` am ax 时 , 新增 记 录后 的 分类 属 性信息 嫡值 小 于候选 属性 的信 息墒 值 , 仍 然选 择 原 先 的分 类属 性 作 为节 点 属性 . 当 新增 记 录 >a am ax 时 , 新 增记 录 后 的分 类 属 性信 息 嫡值 大于 候选 属性 的信 息 墒值 , 选 择候 选 属 性作 为节 点属 性 . i = 亘(进 塑= 2 O (了) (3 ) d 曰Z 2 增 量 决 策树 算法 的 复杂 度 分 析 对 于一 个给 定 的数 据集 , 分析 在最 不理 想 的 情 况下 , 构造 一 棵 决策 树 的 复杂度 , 这种 最 不 理 想 的情 况特 指 利 用全 部 的候 选 属 性构 造 了一 个 层 次最 多 的决 策树 的情 况 . 在 本文 中 , 从两 个 方 面 考虑 决 策树 的复 杂度 . 第 一个方 面 是测 量 当有 新 增记 录加 入 时 , 计 算 正例 集和 负例 集数 量所 需要 的计算 费用 . 新 增 一 条记 录带 来 的这 种计 算 费用 叫做 实例 费用 ( nI - s ant c e 一 C o u n t A d d iti o n ) . 第 二 个 方 面 是 根 据 信 息 嫡 原 理 测 量 选 择 分 类 属 性 时 需 要 的计 算 费 用 叫 做 信 息 嫡 费用 ( E - cs o er C al cu alt in ns ) . 这 种测 量 方 法需 要计 算 每 个 属性 的信 息嫡 , 选 择 信 息量最 大 的属性 作 为分类 属性 , 所 以这种 测量 方法 的计 算 复杂度 是 极为 昂 贵 的 . 现作 如下 假 设 : 给 定一个 训 练数 据集 , 包 含 n 个记 录 , d个候 选属 性 , 其 中属性 最 多有 b个 值段 , 分 析增 量 决策 树 算 法 的计算 复 杂度 . .2 1 增 量 决策 树 算 法实 例 费用 增 量 决策 树 算 法 修 改决 策 树 时 包 含 三 部 分 费用 : 第 一 部分 是 当有 新 记录 加入 时 , 计 算 正 负 实例 集 数量 的 费用 ; 第 二 部 分是在 根节 点选 择 分 类 属性 , 重 构决 策树 的费用 ; 第 三部 分 是为 了确 定 每 个 子树 根 节 点 上 的分 类 属 性 而递 归 地 构 造 决 策树 的费用 , 第 一部 分 , 考 虑 新增 一条 记 录 , 在 对决 策 树 的形 态 没有 影 响 的情 况 下 , 所 带 来 的计算 费用 . 假设 一个 己经 拓展 开 的决 策树 , 在 根节 点上 因为 第 二 部 分 考 虑 在 决 策树 根 节 点上 分 类 属 性 变 化所 带来 的费用 . 设 aP (刃为最 不 理想 的情 况 下 , 决 策树 节 点上分 类属 性 发生变 化 时 引起 的费 用 . 当决策树只 有一 个属 性时 , 不 能更 新决 策树 , P a( l ) = 0 . 当 决策 树有 两个 属 性 时 , 由于 决 策树 根 节 点上 新增 实例 费用 已经 在第 一 步计 算 出来 , 并 且 第一 层 上只 能 有 一个 属性 , 没 有候 选 属性 , 所 以P a( 2) = 0 . 随着 d 值 的增 加 , 实例 费用 来 源于 叶 子 上升 为节 点 的过程 , 当决策 树 有三 个 属性 时 , 在 决策 树 的第一 层上 有 一个候 选 属性 , 每 个候 选 属性 有 b 个可 能 的取 值 种类 , 每 个值 段 上都 需 要 计算 正例 集和 负例 集 的数 量 . 正例 集和 负 例集 数 量 的计算 是将 每个 候 选属 性值 段下 的b棵 子树 中 包含 的 正例集 和 负例 集数 量求 和得 到 的 , 所 以单 独 计 算 正 例 集 的 费 用 为 , 负 例 集 的 费 用 也 是 b ` b = 夕 . 由于候 选 属性 的个 数 为 d( 一 2) 个 , 故整 个 的实例 费 用 为2 夕 “ d( 一 2) . 最 不 理想 的情 况是 从决 策 树 的最 低 层 将 分 类属 性 提升 到根 节 点上 , 此 时需要 的实例 费用 最 大 . 上 述 己 经 推 出决 策 树最 高 两级 的 费用 为 2 b 2` d( 一 2 ) , 当决策 树 的属 性 d增 多时 , 每 个属 性 所对 应 的 b棵 子决 策 树 的费 用 为 bx P a( d 一 l) , 其 中b 为 属性 的值段 数 量 . 所 以可得 如 下 的费用 公式 : aP (刃= 艺b ` 一 , x Zb , x (d 一 ’l) = O (b今 ( 4 ) 第三 部分 考 虑递 归地 重 构 子决 策树 , 重新 选 择 子 决 策树 根 节 点 上最 好 的分 类 属性 所 引起 的 费用 . 提升 一个 属性 来替 换 旧 分类 属 性 的过程 将 导致 实例 费用 的产 生 , 这 个 费用是 由每 个 子决 策 树下 一 级 的候 选属 性 的 费用 总和 决 定 的 . 假 设 一个 分 类 属性 重 构 b棵 新 子树 , 设 aR (的 是最 不 理想 情况 下 , 在 决 策树 第 d( 一 l) 层 构造 b棵 决策 树 的费用 . 当 d = 1 时 , 决策 树 除 根 节 点 外 没有 其 他 属 性 , 故 R a ( l ) = 0 . 当 d = 2 时 , 只 有一 个 候选 属 性 , 在 决 策树 的 第 一层 上 , 意味 着在 该 属 性下 没 有子 决 策树 , 故 R a ( 2) = 0

204· 北京科技大学学报 2004年第2期 当d=3时，在决策树的第一层节点下有b个子 假设b棵子决策树的分类属性都需要重新选 树，每个子树都可能有一个候选属性作为子决策 择.通常情况下，决策树的第一级上需要计算的 树的根节点.通常有： 信息熵的复杂度为b×(d-1):同时决策树的第一 Ra(d0=b×[Pa(d-1)+Ra(d-l)】 级上有b个节点属性，每个属性下对应一棵深度 d-1 =Σb-txPa(t)-O(dxb (5) 为(d-I)的子决策树，该子决策树在重新选择分 =3 将上述三部分更新决策树的费用加起来得 类属性时，需要计算的信息熵费用为Re(d-I),共 到最不理想的情况下，新增一条记录所引起的实 有b棵子决策树，所以计算深度为d的决策树重选 例费用为： 子决策树分类属性时，计算信息熵所需要的计算 2[i+Pa(0+Ra(0]-+2Pa(+2Ra() 费用为： (6) -t Re(d)=bx[(d-1)+Re(d-1)] (9) 为了简化计算，设Pa(d=b,Ra(d=dxb,则 将两部分新增一个实例给决策树构造时带 得新增一条记录总的实例费用为： 2[+Pa(iHRa(0】= 来的信息熵计算费用综合起来得 d(d+1)dxb-(n+D)xb"tb-Oldxb) ∑[i+Re(]=∑i计∑Re() (10) 2 (b-1Y (7) 设Re(d=b,则有 所以，当有n个新增实例时所引起的实例费 2+Re(0】=克+2b=4c41,二b=0b(1) 用为On×db).上述分析表明，在最不理想的情 t t-1 2b-1 况下，利用增量决策树算法构造决策树的复杂度 所以当n个实例全部加入到决策树时，最不 理想的情况引起的信息熵计算复杂度为O(×b). 与训练数据集中包含的记录数n线性相关， 2.2增量决策树算法信息熵费用 上述分析显示，增量决策树算法信息熵计算的复 杂度与训练数据集的数量n成线性关系， 在最不理想的情况下，修改决策树时，信息 熵复杂度由两个部分组成.第一部分是当有新的 3增量决策树算法的实例分析 实例加入到决策树时，增加的信息熵的费用.第 二部分费用是递归地修改每个子树根节点上的 以表1中的数据集为例，其中候选属性分别 分类属性所引起的， 为“身高”，“头发颜色”和“眼睛颜色”，各候选属 第一部分，考虑最不理想情况下，新增一个 性以及类主属性的取值情况见表1， 实例对决策树形状没有影响时所引起的信息熵 下面以上述的8条记录作为训练数据集说明 费用.假设一个已经拓展的决策树，选择根节点 增量决策树算法的工作原理.· 上的分类属性时，需要计算全部d个属性的信息 (1)当训练数据集中只有第1条记录时，决策 熵，然后在第一级上选择分类属性时，需要计算 树只有一个叶节点. 其余(d-1)个属性的信息熵.因此，当新增一个实 (2)当训练数据集新增第2条记录时，随机选 例时，更新决策树所需要的费用为： 择候选属性“身高”作为根节点，生成的决策树包 i=dx(d+1)-O(d) (8) 含两个叶节点.由于此时在叶节点上都只有一个 2 下面考虑决策树修改时带来的信息熵费用， 表1增量决策树算法的训练数据集 设Re(d)为重新选择一个深度为d(属性个数) Table 1 Training data sets for the incremental induction of 的决策树的分类属性所带来的计算费用. decision trees 当决策树的深度d=1时，没有下一级子决策 序号 身高头发颜色眼睛颜色类别 树，因此Re(1)=0. 矮 金黄 棕色 本 当决策树的深度d=2时，在决策树的第一级 停 黑色 棕色 莎 3 上只有一个属性，不需要重新计算该属性的信息 高 金黄 蓝色 是 4 高 黑色 蓝色 香 熵，故Re(2)=0. 5 矮 黑色 蓝色 名 当决策树的深度d=3时，在决策树的第一级 6 高 红色 蓝色 上有b个子树，每个子树需要计算(d-1)个候选属 7 高 金黄 棕色 否 性的信息熵，因此Re(3)=bx(d-1). 矮 金黄 蓝色 是

北 京 科 技 大 学 学 报 2 0 4年 第 2 期 当 d = 3时 , 在决策 树 的第一层 节 点下有 b个子 树 , 每 个子树 都 可能有 一个 候选属 性作 为 子决策 树的根 节 点 . 通 常有 : R a (刃= b x 「P a ( d 一 l ) + aR (d 一 l )〕 d一 1 = Z b d 一` x P a (i) = O( d x b今 ( 5) 将 上述 三 部 分 更 新 决策 树 的费 用 加起 来 得 到最不 理想 的情况 下 , 新增 一条记 录所 引起 的实 例 费用 为 : (6)则 d d d d 艺 [+i P a ( i ) + aR ( i )」= 艺+i 艺P a ( i ) + X R试i) : , 1 孟写 1 召= l 为 了简化 计算 , 设 P a( 的= 夕 , aR (动= d ` 夕 , 得 新增 一条 记 录总 的实 例费 用 为: 、产、、. nU ` .1 `且1. 了 二. 砚 `、了 艺 [+i P a (i) + R a (i) ] = 假 设 b棵子 决策 树 的分类 属性 都 需要重 新选 择 . 通 常情 况 下 , 决策树 的第一 级 上需 要计 算 的 信 息嫡 的复杂 度 为 b ` d( 一 l) ; 同时 决策 树 的第 一 级 上 有 b个节 点属 性 , 每个 属性 下对 应 一棵 深度 为 d( 一 l) 的子 决策 树 , 该子 决策 树在 重 新选 择分 类 属性 时 , 需要 计算 的信息嫡 费用 为eR d( 一 l) , 共 有 b棵 子决策 树 , 所 以计算深 度 为d 的决策树 重选 子 决策树 分类 属性 时 , 计算 信息 嫡所 需要 的计算 费用 为 : R e (刃= b x 【(d 一 l ) + eR (d 一 l )」 ( 9 ) 将 两部 分 新 增 一 个 实例 给 决 策 树 构造 时带 来 的信 息嫡 计算 费用 综 合起 来得 d( +d l) d x b祝 一 ( n + l ) x b 肚 `+ b d d 艺+i Z R e (i) (b 一 l ) 2 = 0 (d x b今 ( 7 ) d X [+i R e (i) ] = i= l 设 R e( 刃= 少 , 则 有 所 以 , 当有 n 个新 增 实例 时所 引起 的实例 费 用 为口( n ` d ` b今 . 上 述分 析表 明 , 在 最不 理想 的情 况下 , 利用 增量 决策 树算 法构造 决 策树 的复杂 度 与 训练数 据集 中包含 的记 录 数 n 线性 相 关 . .2 2 增 量决 策树 算法 信 息嫡 费用 在 最 不理想 的情 况 下 , 修 改决 策树 时 , 信 息 嫡复 杂度 由两个 部分组 成 . 第一 部分 是 当有新 的 实例 加入 到 决策树 时 , 增 加 的信 息嫡 的费用 . 第 二 部 分 费用 是 递 归地 修 改每 个 子 树根 节 点 上 的 分类 属性所 引起 的 . 第 一部 分 , 考虑 最 不理 想情 况 下 , 新增 一 个 实例 对 决策 树 形状 没 有 影 响 时所 引起 的信 息嫡 费用 . 假 设一 个 已 经 拓展 的 决策 树 , 选择 根 节 点 上 的分类属 性 时 , 需 要计 算全 部 d个 属性 的信 息 嫡 , 然后 在第 一 级上选 择 分类 属性 时 , 需要 计算 其 余 d( 一 l) 个属 性 的信 息嫡 . 因此 , 当新 增一 个实 例 时 , 更新 决策 树所 需 要 的费用 为 : 凰+i[ eR i()] 一 急礁 ,粤护碟举 一 。 所 以当 n 个实 例 全部 加入 到 决策 树 时 , 最 不 理想 的情 况 引起 的信 息嫡 计算复杂度 为以xn b今 . 上述 分析 显示 , 增量 决策 树算法 信 息嫡计 算的复 杂度 与训 练数 据 集 的数 量 n 成线 性 关系 . 矛 _ d x (+d l ) 2 = O (护) ( 8 ) 下 面考 虑决 策树 修 改时带 来 的信 息嫡 费用 . 设 R e( 的为 重新选 择 一 个深 度 为d( 属性 个 数 ) 的决策树 的 分类 属性所 带来 的计 算 费用 . 当决策 树 的深度 d = 1时 , 没有 下一 级子 决 策 树 , 因此 R e ( l ) = 0 . 当决策树 的深 度 d = 2 时 , 在决 策树 的第 一 级 上只有 一个 属性 , 不需 要重 新计 算该 属性 的信 息 嫡 , 故 eR (2 ) = 0 . 当决策树 的深 度 d = 3 时 , 在决 策树 的第 一 级 上 有 b个子 树 , 每个 子树 需要 计算 d( 一 1) 个候 选属 性 的信 息嫡 , 因此 eR ( 3) = bx d( 一 1) . 3 增 量 决策树 算法 的实例 分 析 以表 1 中的数 据集 为 例 , 其 中候选 属性 分 别 为 “ 身高 ” , “ 头 发颜 色 ” 和 “ 眼 睛颜 色 ” , 各候 选属 性 以及类 主属 性 的取 值情 况 见表 1 . 下面 以上述 的 8 条记 录作 为训练 数据集 说 明 增 量 决策 树算法 的工 作原 理 . ’ ( l) 当训练 数据 集 中只有 第 1 条 记录 时 , 决策 树 只 有一 个 叶节 点 . (2 )当 训练数 据 集新 增第 2 条记 录时 , 随 机选 择候 选属 性 “ 身高 ” 作 为根节 点 , 生成 的决策树 包 含两 个 叶节 点 . 由于 此 时在叶 节 点上都只 有 一个 表 1 增量 决策树 算法 的训 练数据 集 aT b l e l 竹a i n in g d a t a s e t s fo r t h e in e er 口e n t a l i n d u e it o n o f d e e is i o n t er e s 序 号 身高 头发颜 色 眼睛颜色 类 别 1 矮 金黄 棕 色 否 2 高 黑 色 棕 色 否 3 高 金黄 蓝 色 是 4 高 黑色 蓝 色 否 5 矮 黑 色 蓝 色 否 6 高 红色 蓝 色 是 7 高 金黄 棕 色 否 8 矮 金黄 蓝 色 是

Vol.26 No.2 尹阿东等：增量决策树算法及复杂度分析 ·205· 记录，所以停止决策树的拓展 集，由增量决策树算法生成的决策树的形态与传 (3)当训练数据集新增第3条记录时，由于节 统的D3算法生成的决策树的形态完全一致，说 点分类属性“身高”与候选属性“眼睛颜色”有相 明两种算法具有相同的准确率， 同的信息熵值0，根据公式a-经E可 Ibb,+2+lbe 知，am=0,所以当新增一条记录后，将导致候选 4结论 属性“眼睛颜色”替代原先的分类属性“身高”，此 增量决策树算法利用两个辅助定理，处理增 时的决策树的形态如图1所示. 量数据集的决策树构造问题，解决了传统D3算 (4)依次类推，当训练数据集新增第48条记 法无法处理增量数据集的缺点，通过对增量决策 录的过程中，根据增量决策树算法可以得到相应 树算法复杂度的分析可以发现，虽然增量算法在 的增量决策树.最终根据训练数据集中的8条记 构造决策树时，需要较大的计算费用，但是利用 录，利用增量决策树算法生成的决策树的形态如 增量算法可以一次完成决策树的构造，避免了对 图2所示. 数据集的重复扫描，而且可以构造出与D3算法 经过对比分析发现，利用表1中的训练数据 准确率基本相同的决策树， 眼睛颜色 参考文献 蓝色0，] 棕色[0,2] 1 Schlimmer J C,Fisher D.A case study of incremental con- 是 身高 cept induction [A].Proceedings of AAAI-86 [C].Philad- elphia,1986 矮0,1] 高[0,1] 2 Utgoff P E.Incremental Induction of Decision Trees [J]. Mach Learn,1989(4):161 否 否 3 Utgoff P E.An improved algorithm for incremental induc- 图1三条记录时决策树的形态 tion of decision trees [A].Proceedings of the Eleventh Int. Fig.1 Decision trees of three training instances Conference on Machine Learning [C].New Jersey,1994. 318 头发颜色 4 Kalles D,Morris T.Efficient incremental induction of de- 金色[2,2 红色[1,0] cision trees [J].Mach Learn,1996(1):1 黑色0,3 眼晴颜色 5 Kalles D,Papagelis A.Stable decision trees:Using local 是 蓝色2,01 棕色[0,2] anarchy for efficient incremental learning [J].Int J Artif 眼睛颜色 Intell Tools,2000,9(1):79 身高 身高 蓝色[0,2]/ 棕色[0,1】 6 Piater JH,Riseman E M.Interactively training pixel clas- \高0,1] sifiers []Int J Patter Recognit Artif Intell,1999,13(2): 矮0,1y 高[1,0] 171 否 7 Elomaa T,Kaariainen M.An analysis of reduced error pru- 是 否 否 ning[J].J Artif Intell Res,2001,15:163 图2增量算法生成决策树的最终形态 8 Wang X Z,Chen B,Qian G L,et al.On the optimization Fig.2 Final decision trees of eight training instances offuzzy decision trees [J].Fuzzy Sets Syst,000,112:117 An Incremental Alogrithm for Inducing Decision Trees and Its Complexity YIN Adong,GONG Yu,WU Shengli,WU Sen,GAO Xuedong,LI Yongjun Management School,University of Science and Technology Beijing,Beijing 100083,China ABSTRACT An incremental algorithm for inducing decision trees is presented based on ID3 algorithm.The com- plexity of the incremental algorithm is analyzed in terms of instance-count additions and e-score calculations.The same training instance shows that the incremental algorithm can induce decision trees equivalent to those forms by ID3 algorithm. KEY WORDS decision trees;incremental algorithm;complexity

V心1 . 2 6 N 0 . 2 尹 阿东等 : 增 量决策 树算 法及 复杂 度分 析 一 2 0 5 . 记录 , 所 以停 止决 策树 的拓 展 , (3 ) 当训 练数 据集 新 增第 3 条记 录 时 , 由于节 点分 类属 性 “ 身 高 ” 与 候选 属 性 “ 眼睛 颜色 ” 有 相 集 , 由增量 决 策树算 法 生成 的决 策树 的形 态与 传 统 的 ID 3 算 法 生成 的 决策 树 的形 态完 全 一 致 , 说 明两种 算 法 具有 相 同 的准确 率 . 同 的信 息 嫡值 。 , 根据 公式 am 。 一 史拱实兽任军卫可 I U竹 丁 ` 不 i U` 知 , am ax = O , 所 以 当新增 一 条 记录 后 , 将 导致 候 选 属 性 “ 眼睛 颜色 ” 替代 原 先 的分类属 性 “ 身高 ” . 此 时 的决策 树 的形 态如 图 1 所示 . (4 )依 次类 推 , 当训练 数 据 集新 增 第 4一 8 条记 录 的过 程 中 , 根 据增 量 决策树 算 法可 以得 到相应 的增量 决 策树 . 最 终 根据 训 练数 据集 中的 8 条记 录 , 利用 增 量决 策树 算法 生成 的 决策树 的形 态如 图 2 所 示 . 经过 对 比分 析 发现 , 利 用表 1 中的 训练 数据 眼睛颜色 蓝罗/ 映 , 2 ’ 身高 一 / 准 【。 , 1」 否 否 图 1 三条 记录 时决 策树 的形 态 F ig . l D e c is i o n t r e e s o f t h r e e t r a in i n g in s t a n c e s 头发颜色 眼睛颜色 蓝色 l州冷 【0 , 2 , 否 否 图 2 增 量算 法生 成决 策树 的最终 形 态 F ig . 2 F i n a l d e c is i o n t r e e s o f e i g h t t r a i n i n g i n s t a n e e s 4 结论 增量 决策 树 算法 利 用两 个辅 助 定理 , 处 理 增 量 数据 集 的决 策树 构 造 问题 , 解 决 了传统 ID 3 算 法无 法 处理增 量数 据 集 的缺 点 . 通 过对 增量 决 策 树算法 复杂度 的分 析 可 以发现 , 虽 然增 量算 法在 构造 决 策树 时 , 需要 较大 的计 算费用 , 但 是 利用 增量算 法 可 以一次 完成 决策 树 的构 造 , 避免 了对 数据 集 的重 复 扫描 , 而且 可 以构 造 出 与 ID 3 算法 准 确 率 基本 相 同 的决策 树 . 参 考 文 献 1 S e h l im m e r J C , F i s h e r D . A c a s e s ut 勿 o f i n e er m e n t a l e o n · e e Pt i n d u e t i o n [ A ] . Pr o e e e d ing s o f A A A I 一 8 6 [C」 . P h i l a d - e lP h i a , 19 8 6 2 U tg o任 P E . In e r e m e n t a 1 In du e t i o n o f D e e i s i o n rT e e s [J」 . M a c h L e am , 19 89 ( 4 ) : 1 6 1 3 U tg o f P E . A n 而P r o v e d a l g o r i thm fo r i n c r e m e in a l i n d u c - ti o n o f d e e i s i o n etr e s [A ] . Por c e e di n g s o f ht e E l e v e n t h l n t . C o n fe r e n e e o n M a e h i n e L e anr i n g [C ] . N e w J e r s e y, 1 9 9 4 . 3 1 8 4 K a ll e s D , M o r i s .T E if c i e in in e er m e n t a 1 i n d u e ti o n o f d e - c i s i o n etr e s [J] . M ac h L e anr , 1 9 9 6 ( l ) : l 5 K a ll e s D , P ap ag e l i s A . S at bl e d e e i s i o n tr e e s : U s i n g l o c a l a n ar c hy fo r e if c i e n t i n c r e m e nt a l l e anr i n g [ J] . I in J A rt if I nt e l l oT o l s , 2 0 0 0 , 9 ( l ) : 7 9 6 P iat e r J H , Ri s e m an E M . I nt e r a c t i v e ly tr a i n i n g Pi x e l e l a s - s i if e r s [J] . I n t J P a t em eR e o gn i t A rt if lin e l l , 19 9 9 , 13 ( 2 ) : 1 7 1 7 E l o m a T, K ar i a i n e n M . nA an a ly s i s o f er du e e d e r o r Pur - n i n g [J ] . J A rt l f lin e ll R e s , 2 0 0 1 , 1 5 : 1 6 3 8 从a/ n g X Z , C he n B , Q i a n G L , e t a l . O n ht e o Pt im iatZ i o n o f fu Z yZ d e c i s i o n tr e e s [J I . F u Z y s e t s s y s t , 2 0 0 0 , 1 1 2 : 1 1 7 A n I n e r e m e n t a l A l o g r it h m fo r I n d u c i n g D e c i s i o n rT e e s a n d I t s C o m P l e x iyt 1了N A do ng, G O N G ,uY 附 U hS e喇砚砰 U eS n , G月口 Xu e ` lo ng, IL oY ” 乡 un M an ag e m e n t S e h o o l , U n i v c r s ity o f s c i e n e e an d eT e hn o l o gy B e ij i n g , B e ij in g 10 0 0 8 3 , C h in a A B S T R A C T A n i n e r e m e n t a l a lg o ir t h n l of r i n du e i n g d e e i s i o n tr e e s 1 5 P re s e in e d b a s e d o n ID 3 a l g o ir t hj m . hT e e o m - P l e x ity o f ht e i n e r e m e in a l a l g o ir t 加rn 1 5 an ly z e d in t e rm s o f in s t an e e 一 c o u n t a d dit i o n s an d e 一 s e o re e a l c u l at i o n s . hT e s am e atr l n i n g l n s t an e e s h o w s ht at ht e i cn re m e in a l a lg o ir t 加rn e an in du e e d e e i s i o n tre e s e qu i v a l ent t o ht o s e of rm s 勿 ID 3 a l g o ir t知rn . K E Y W O R D S d e e i s i o n tr e e s ; i n e r e m e nt a l a lg o ir t h m ; e o m Pl e x i ty