流数据的决策树分类
VIP免费
摘 要
决策树分类是数据挖掘研究领域中最重要的分枝之一。该算法有以下的一些
主要优点：构造简单，可理解性强，易于转化为应用规则，并且比同类分类算法
的分类精度（包括神经网络、遗传算法、贝叶斯估计等等）更高。今天，它已经
被广泛应用于金融、保险、政府、教育以及国防等相关领域。但是，已有的一些
决策树算法挖掘流数据的效果却不能令人满意，尤其是当流数据存在概念漂移现
象时，原有的算法要么内存开销过大，要么分类准确率偏低。
针对决策树在上述问题上出现的严重缺陷，本文做了相对深入的研究，以
VFDT算法作为基础，加以改进，并设计出新决策树算法D-DT。这种新算法可以
大大增强决策树对存在概念漂移流数据的适应能力，提高分类准确率，减少内存
消耗。
首先构造两个可伸缩窗结构截留数据，依据Hoeffding不等式，利用窗结构的
分裂机制，构造流数据概念漂移探测器D-1。该探测器是设计新决策树算法的基础。
它不仅仅能够有效的探测概念漂移的发生，还能够精确确定概念漂移发生的具体
位置和时间。可以发挥双窗结构的优势，识别虚漂移。然后利用探测器D-1来设计
新的决策树算法D-DT。D-DT是将两个D-1加装在VFDT每一个枝上，分别探测原
数据的分布以及在线错误率的分布，使决策树算法对数据的概念漂移具有高度敏
感性。一旦探测器报告概念漂移发生后，就会自我修复。同时利用窗结构里的样
本生成新的备用决策树，然后计算出的相关指标会标明两个决策树优劣，取出其
中的优者，为正式的决策树。这样，新树可以大大提高决策树处理存在概念漂移
流数据的分类准确率。
重要的是，文章还对探测器D-1和决策树D-DT中的相关理论进行了推导。这
些推导，为新决策树的设计打下了良好的理论基础。
经过实证研究，证实了探测器新算法D-1在应用于存在概念漂移人工数据和实
际数据中的准确性和探出率方面都达到了预想的效果，高于同类其他算法。还证
实了决策树D-DT的内存开销可以有效降低，分类精度达到了较高水平，相关指标
均高于VFDT算法。
关键词：数据挖掘 决策树 流数据 D-DT
ABSTRACT
Decision-tree, as we all known, is one of the most important algorithms in the
data-mining field. This algorithm has some advantages: easily understood, constructed
simply, easily converted into rules. This algorithm is used widely in banking finance,
insurance, government, education, transportation and national defense etc.
Unfortunately, most of algorithms are not adapt to the new data—stream data. And also,
the existed algorithms cannot work effectively to the data with concept drift.
In this paper, we propose a new efficient algorithm for mining decision trees from
continuously-changing Data-streams, based on the VFDT decision tree leaner. The work
we do in this paper mainly as follows:
Firstly, this paper introduces the basic theory of Data mining and Classification
technology macroscopically，and analysis and comparison of decision tree algorithms
were especially emphasized on.
Secondly, we design the concept drift detector D-1, which is the base of the new
decision-tree model. This detector not only can efficiently detect weather concept drift
exist but also can confirm the time when concept drift starts.
Thirdly, we design the new decision-tree algorithm D-DT. The principle is simple:
adding two D-1 on the all branches to detect the data distribution and the D-DT error
rate. Then, this model could be sensitive to concept drift. The classified correct rate
would grow up. Furthermore, this paper proposes the theory of the D-DT.
Finally, we take the empirical study in synthetic and real data. The results point
that the new models are efficient. All the indexes are better than that of the existed
algorithm VFDT.
Key Words: Data mining, Decision tree, data-stream, D-DT
目 录
目录
摘要
ABSTRACT
第一章 绪论 ..........................................................1
1.1 背景和现实意义 ..................................................1
1.2 国内外研究的现状和最新进展 ......................................3
1.3 本研究方向的发展趋势 ............................................4
1.4 本文的主要工作 ..................................................5
1.5 本文的结构安排 ..................................................5
第二章 决策树基本原理和基本结构 ......................................7
2.1 决策树算法基本原理 ..............................................7
2.2 决策树算法的相关技术 ............................................8
2.2.1 数据预处理 ....................................................8
2.2.2 属性选取标准 ..................................................9
2.2.3 修剪技术 .....................................................10
2.2.4 性能评价 .....................................................11
2.3 属性选取判据 ...................................................12
2.3.1 信息增益 .....................................................12
2.3.2 GINI 索引标准 ................................................ 14
2.4 典型算法简介 ...................................................15
2.4.1 ID3 ......................................................... 15
2.4.2 C4.5 ........................................................ 15
2.5 规则提取 .......................................................15
第三章 流数据决策树原理和典型算法 ...................................17
3.1 流数据及其特点 .................................................17
3.2 概念漂移及其特点 ...............................................18
3.3 VFDT .......................................................... 18
3.3 CVFDT ......................................................... 20
3.4 本章小结 .......................................................21
第四章 流数据决策树新算法 D-DT ...................................... 23
4.1 概念漂移探测器 .................................................23
4.1.1 漂移探测算法 D-0 ............................................. 23
4.1.2 相关参数确定方法及理论 .......................................24
4.1.3 算法 D-0 的效果 ...............................................27
4.1.4 虚漂移（VIRTUAL）及其探测器 D-1 ............................... 28
4.2 新的决策树算法 D-DT ............................................ 30
4.2.1 VFDT 在 D-1 上的改进 ..........................................30
4.2.2 算法分析 .....................................................31
4.3 相关参数理论证明 ...............................................32
4.4 本章小结 .......................................................33
第五章 仿真研究 .....................................................35
5.1 人工数据 .......................................................35
5.1.1SEA CONCEPT 数据 ............................................... 35
5.1.2HYPERPLANE 超平面 .............................................. 37
5.2 真实数据 .......................................................39
5.3 内存消耗和时间效率 .............................................39
5.3.1 实验 .........................................................39
5.3.2 结论 .........................................................40
5.4 本章小结 .......................................................40
第六章 总结和展望 ................................................... 43
6.1 总结 ...........................................................43
6.2 对未来研究的展望 ...............................................44
参考文献 ............................................................ 45
在读期间公开发表的论文和承担科研项目及取得成果 ......................49
致 谢 ............................................................... 51
第一章 绪论
1
第一章 绪论
1.1 背景和现实意义
随着经济社会的快速发展以及科学技术的飞速进步，人们获取和存储的数据
量快速增加。上个世纪八十年代，全球数据量每隔二十个月就增加一倍。进入九
十年代增长速度更快，1993年全球数据存贮容量约为二千TB，而到了2000年增加
到了三百万TB[1]。面对这极度膨胀的数据量，人们惊讶地发现，“信息爆炸”、“混
沌信息空间”和“数据过剩”带来的巨大压力已经显现。
但是，这些激增的海量数据中隐藏着许多有价值的信息和知识。如果能把信
息和知识从这些数据中提取出来，就能为人类服务并能创造很高的应用价值。因
此，对大量历史数据进行分析处理，挖掘有用的信息和知识，就显得极为迫切。
传统的查询技术无法解决目前面临的“信息爆炸”问题。如何有效地管理数据和利用
数据，怎样快速发现数据中潜在的信息和知识？这些问题需要有更有效的手段去
发现新的信息和知识，进而发挥这些数据的潜能。正是由于这样时代背景和巨大
的需求，迅速产生并发展起来一门新兴技术——数据挖掘。
数据挖掘(Data Mining)，又称为数据库中的知识发现(Knowledge Discovery in
Database, KDD)，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理
解的模式的非平凡过程[2]。通俗的说，数据挖掘是从大量数据中寻找有用的东西。
当代的数据挖掘，是一个融合了数据库、机器学习、数理统计、可视化和信
息科学技术为一体的新兴交叉学科。它的发展不仅可以为商务管理、科学研究、
查询优化、过程控制等领域提供决策支持，还能为相关的计算机学科注入新的活
力。数据挖掘技术，发展出了众多的挖掘理论及其方法，包括关联规则(Association
Rule)、分类(Classification)、聚类(Clustering)、趋势(Trend)、偏差(Deviation)和模式
(Pattern)分析等。其中，对分类的研究是目前数据挖掘研究领域中最为广泛，最有
价值和前景的课题之一。
分类的目的是提出一个分类函数或分类模型(分类器)，该模型能把数据库中的
数据映射到给定类别中的某一个类别。分类技术能够为各个行业提供良好的决策
支持，这些不同的行业有着多种不同领域方法的分类算法，例如决策树方法、神
经网络方法、统计学方法等。这些算法中，决策树方法最容易理解，应用领域也
特别广泛。
摘要：
展开>>
收起<<
摘要决策树分类是数据挖掘研究领域中最重要的分枝之一。该算法有以下的一些主要优点：构造简单，可理解性强，易于转化为应用规则，并且比同类分类算法的分类精度（包括神经网络、遗传算法、贝叶斯估计等等）更高。今天，它已经被广泛应用于金融、保险、政府、教育以及国防等相关领域。但是，已有的一些决策树算法挖掘流数据的效果却不能令人满意，尤其是当流数据存在概念漂移现象时，原有的算法要么内存开销过大，要么分类准确率偏低。针对决策树在上述问题上出现的严重缺陷，本文做了相对深入的研究，以VFDT算法作为基础，加以改进，并设计出新决策树算法D-DT。这种新算法可以大大增强决策树对存在概念漂移流数据的适应能力，提高分类准...
相关推荐
作者：高德中
分类：高等教育资料
价格：15积分
属性：50 页
大小：1.05MB
格式：PDF
时间：2024-11-19
