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 矮 金黄 蓝 色 是