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