基于决策树的数据流挖掘算法的研究
- 格式：pdf
- 大小：262.77 KB
- 文档页数：5
通过分析 比较 ， 总结 了各种算 法的主要特 征， 国 为
内研究者提供借鉴 。
前的数据挖掘技术提 出了新 的要求 ， 中之一就是 其
对数据流 的数 据挖掘。数据流 是一系列连续 且有
１ 基 于决策树 的数据流分类算法
１ １ 传统的增量式的决策树分类算法 ．
对于已有 的 Ｉ３ｌ Ｃ ． 算法 ， Ｄ 和 ４ ５２ Ｌ Ｌ 由于这些算
掘算法是很 困难的事。近几年来， 对数据流进行数据挖掘的算法相继被提 出。本文主要 阐述分类算法中基于决策树的各种数据流挖掘算法， 包括传统的增量式的决策树分类、 基
于 Ｈ ｅｄ ｇｔｅ的 Ｖ Ｄ 、 ｏｆ ｉ ｅ ｎ ｒ Ｆ Ｔ 可调整的 Ｖ Ｄ （ Ｃ Ｆ Ｔ 以及使用整合技术的决策树 分类 ＦＴ 即 ＶＤ ）
算法 ， 通过分析比较， 总结 了各种算法的主要特征 ， 国内研 究者提供借鉴。 为
关键词 ： 决策树 ；ＬＱ Ｓ ＲＮ ； Ｆ Ｔ Ｃ Ｆ Ｔ Ｓ Ｉ ；Ｐ ＩＴ Ｖ Ｄ ； Ｖ Ｄ
中图分 类号 ：Ｐ ０． Ｔ ３ １６ 文 献标识 码 ： Ａ
‘
目 ， 前 数据挖掘技术在许多领域得到 了广泛的 应用 ， 而多样的数据形 式和 日益增 加的数据量 给 目
文章编 号 ：６３— ０７ ２０ ）４— ２ ８— ４ １７ ２５ （０ ６ ０ ０ ６ ０
基 于决策树 的数据流挖 掘算法 的研 究
孙超利
（ 太原科技大学计算机科 学与技 术学院， 太原 ０ ０２ ） ３０４ 摘 要： 由于数据流的快速流动性 以及计算机 内存的限制 ， 因此要设计好 的数据流挖
ｌ ｒｅ） ｅ ｎ ｒ算法。 ａ
划分 ， 所以必须长驻 内存。每个属性都有一张属性
表， 可以驻 留磁盘。类 直方图附属在 叶节 点上 ， 用
来描述节点上某个 属性 的类别分布 。描述连续属 性分布时 ， 由一组 二元组 ＜类别 ， 它 该类别 的样本 数＞ 组成 ； 描述离散 属性分布时 ， 由一组三元组 它 ＜ 属性值 ， 类别 ， 该类别 中取该属 性值 的样本数 ＞ 组成。随着算法 的执 行 ， 类直 方 图中 的值 不断更
的分类法将由每个子集得 到的分类法组合在一起 。 尽管该方法可以用 于大数据集的分类 ， 其分类的准
确性不如一次使用所有的数据的方法高。 最近， 已经 提 出了一些判定 树算法 ， 它们强 调
可伸缩性 。由非常 大的训 练集进行 判定树归纳 的
算法包括 Ｓ Ｉ 和 Ｓ ＲＮ Ｌ ， ＬＱ Ｐ ＩＴ４ 两种算法都定义使
（ Ｃ Ｆ Ｔ 以及使用整合技术的决策树分类算法 ， 即 ＶＤ ）
收 稿 日期 ０ ６ ３２ ２０ － －７ ０
作者简介 ： 孙超利 （９８ ， ， １７ 一）女 硕士研究生 ， 研究方向 ： 数据挖掘 、 数据库理论 与应用 。
维普资讯
第 ２ 卷第 ４ ７ 期
大的数据集中挖掘有用信息 ， 这样设计出来 的学习
器要求每个样本最多只能读取一次 ， 并且 只有很短 的时间来进行处 理。这就使它能够 直接挖掘 在线
属性值和样本号 。类表也含有两个字段 ： 样本类别 和样本所属节点 。类表的第 ｋ 跳记录对应于训练集 中第 ｋ个样本 （ 样本号为 ｋ ， ） 所以属性表和类表之
维普资讯
第２ 卷 ７
第 ４期 太原源自科技大 学
学
报
Ｖ １ ７ Ｎ ・ ｏ ２ ｏ４ ．
Ａ ｇ２ ０ ｕ ．０ ６
２０ ０ ６年 ８月
Ｊ Ｕ Ｎ ＬＯ Ａ Ｙ Ａ Ｎ Ｖ Ｒ ＩＹ Ｏ Ｃ Ｅ Ｃ Ｎ Ｅ ＨＮ Ｌ Ｇ Ｏ Ｒ Ａ ＦＴ Ｉ Ｕ Ｎ Ｕ Ｉ Ｅ ＳＴ ＦＳ ＩＮ Ｅ Ａ Ｄ Ｔ Ｃ Ｏ Ｏ Ｙ
序的点的组成序列 Ｘ ” 置 ， ， ， …， 它的特点是数
据快速持续 地到达 、 据海量并且数 据到达有序 。 数
比如传感器 网络 、 大型商业 网站 、 电信公 司每时每 刻都产生大量 的数据 ， 这些数据 形式都是数据 流。 对于数据流挖掘 ， 主要有两个 限制 ： １ 内存 限制 ； （） （） ２ 数据流的快速流动性。后者要求处理数据 、 进 行分析的速度不能低于数 据流动 的速度 ， 这在算法 的执行效率上要求 很高。而 又 由于 内存 的本 身限 制， 因此设计好 的数据流挖掘算法是很 困难的事。 近几年来 ， 对数据 流进行数 据挖掘的算法相继 被提出。本文 主要 阐述分类算 法 中基于决策 树 的 各种数据流挖掘算法 ， 包括传统的增量式 的决策树 分类 、 基于 Ｈ ｅｄ ｇｔｅ的 Ｖ Ｄ 、 ｏｆｉ ｅ’ Ｆ Ｔ 可调整 的 Ｖ Ｄ ｎ ｒ ＦＴ
孙超利 ： 基于决策树的数据流挖掘算法的研究
２９ ６
用新的数据结构 ， 以利于树的构造 。
变的非常昂贵 ， 并且 当数据集大小不适合可用磁盘 空间时就会失败 。而数据 流挖掘 的 目标是在 非常
ＳＩ ＬＱ算法利用 ３ 种数据结构来构造树 ， 分别是
属性表 、 类表 和类 直方 图。属性 表含有两个字 段：
法要求训练样本驻 留内存 ， 因此对于相对小 的数据 集是很有效 的， 但是 当碰到大 规模数据时 ， 由于训 练样本需在主存和高速缓存 中换进 换出， 因此判定 树 的构造 变 的效率 低下 。一种 替 代的方 法是 ： 首 先， 将样本划 分成子集 ， 得每个子 集可 以放在 内 使 存； 然后 ， 由每个子集构造 一棵 判定树 ； 最后 ， 出 输
间可以建立关联。类 表可 以随时指示样本 所属 的
的数据资源 ， 并且在可接受的计算资源耗费下建立 潜在 的复杂树。为此 Ｄ ｍｎｏ Ｐ 等人提 出了基 ｏｉ ｓ ． ｇ 于 Ｈ ｅｄ ｇ树 的 Ｖ Ｄ Ｖ ｒ Ｆｓ Ｄ ｃ ｉ ｒ ｏｆ ｉ ｎ Ｆ Ｔ（ ｅ ａ ｅｉｏ Ｔｅ ｙ ｔ ｓｎ ｅ
