关于单数据流和分布式数据流挖掘分类算法的研究毕业论文

1、关于单数据流和分布式数据流挖掘分类算法的研究摘 要随着科学技术的发展，社会经济不断进步，在社会生产的各个领域中都产生了大量的数据，这些数据中蕴含着大量的丰富的信息。但是，如何处理这些数据并从中得到有用的信息，是对当今计算机科学研究的一项重大的挑战。数据挖掘技术成为了当前研究的一项重要的课题。近年来，单数据流的挖掘得到了广泛的研究，提出了许多有价值的模型和算法。但是，随着网络环境应用的普及，单一数据流的应用必然向着多节点的分布式数据流方向转移，并有着广泛的应用前景。本课题阐述了当前国际上关于单数据流和分布式数据流挖掘分类算法的研究现状，按照算法学习模式的方法，对各种分类算法进行比较、归纳，同时，

2、对分类技术当前所面临的问题和发展趋势进行了总结和展望。在单数据流环境里，增量式学习和集成学习是两种典型的学习方法；在分布式数据流环境里，集中式挖掘和分布式挖掘是两种典型的架构，各具优势。关键字：数据挖掘，单数据流，分布式数据流，weka abstract with the development of science and technology, as well as the progress of the economics, there are a lot of data in different areas, which contain large amount of informat

3、ion. however, how to handle these data and derive useful information today is such a major challenge of computer science. data mining technology is becoming an important topic in current research. in recent years, the mining of single data stream has been studied extensively and many valuable models

4、 and algorithms emerged. but, with the popularity of internet applications, the application of a single data stream towards the inevitable multi-node transfer of distributed data flow direction and has a wide range of applications. this topic describes the current international and distributed on a

5、single data stream of data stream mining research classification algorithm, in accordance with the method of learning algorithms, to compare and to summarized the various classification algorithm, at the same time classification and current problems faced by a summary of trends and prospects. in a s

6、ingle data stream environment, incremental learning and integrated learning are two typical learning. in a distributed environment where data flow, centralized mining and mining are two typical distributed architecture, they have different advantage.keywords: data mining ,single data stream, distrib

7、uted data streams, weka 目 录摘 要1abstract2第1章 绪论41.1本文工作的来源41.2目的和意义51.3国内外进展51.4本文工作的主要内容5第二章 数据流的概述72.1数据流管理系统的研究82.2数据流在不同领域的应用92.2.1在电信数据处理方面92.2.2在军事作战环境中92.2.3在科学计算领域方面102.3数据流的特点102.4数据流挖掘框架112.5本章总结12第三章 单数据流分类方法研究133.1传统的分类方法133.2数据流分类技术153.2.1增量式(incremental)算法。153.2.2集合分类器173.3本章总结19第四章 分布式

8、数据流分类方法研究204.1分布式数据流的定义204.2分布式数据流挖掘面临的挑战214.3分布式数据流相关系数计算224.4基于sprint的vhdds分类方法234.4.1 sprint算法简介234.4.2 vhdds分类算法234.4.3算法过程244.5本章总结28第五章 分析数据挖掘工具295.1weka背景295.2weka功能295.3weka的输入305.4weka的输出315.5weka的可视化325.6本章总结32参考文献33致 谢35外文科技资料翻译36英文原文36中文译文41第1章 绪论1.1本文工作的来源本课题来源于教学，在教学中让我们理解数据流和分布式数据流，并且

9、对数据流和分布式数据的分类进行研究1.2目的和意义通过该课题，使我们能够明确的建立数据挖掘的概念，对该领域的相关算法有一个大概的认识，学会使用数据挖掘软件weka进行相关分析；同时培养我们的科学研究能力，使我们能够初步掌握进行科学研究的基本程序和方法，通过自己的研究和学习，能够在其中提出问题、分析问题和解决问题，将来走向社会，既有较扎实的基础知识和专业知识，又能发挥无限的创造力，不断解决实际工作中出现的新问题。1.3国内外进展最近几年，数据流技术发展很快，针对数据流的研究主要包括以下三方面：(1)数据流管理系统(data stream management system，简称dsms)的研究，

10、包括斯坦福大学的stream项目、施乐公司的tapestry项目、加州大学伯克力分校的telegraph项目、布朗大学和麻省理工学院合作的aurora项目等等，这些系统针对具体行业背景，给出较全面的数据管理解决方案；(2)数据流挖掘算法的研究，包括数据流的聚类、决策树分类、关联规则挖掘等等；(3)数据流应用领域的研究。1.4本文工作的主要内容 研究数据流的有关概念，单数据流和分布式数据流的分类方法，以及分析数据挖掘工具。数据流（data stream）最初是通信领域使用的概念，代表传输中所使用的信息的数字编码信号序列。然而，我们所提到的数据流概念与此不同。这个概念最初在1998年由henzin

11、ger提出，他将数据流定义为“只能以事先规定好的顺序被读取一次的数据的一个序列”。分布式数据流（distributed data stream）是指相互联系的多个数据流。随着技术的发展，分布式数据流的环境越来越普遍，人们可以收集不同结点的大量数据，如股票市场、传感器网络、网络点击流等。为了从这些技术中真正受益，很明显，必须使用数据挖掘这样的半自动化交互式技术来处理和分析这些数据。数据挖掘(data mining)，就是从存放在数据库，数据仓库或其他信息库中的大量的数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。数据挖掘利用了来自如下一些领域的思想：(1) 来自统计学的抽样、

12、估计和假设检验，(2) 人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。一些其他领域也起到重要的支撑作用。特别地，需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能（并行）计算的技术在处理海量数据集方面常常是重要的。分布式技术也能帮助处理海量数据，并且当数据不能集中到一起处理时更是至关重要。数据挖掘可以概括分为两类，一类是直接数据挖掘，另一类是间接数据挖掘。直接数据挖掘目标是利用可用的数据建立一个模型，这个模型对剩余的数据，对一个特定的变量（可以理解成数据库中表的属

13、性，即列）进行描述。间接数据挖掘目标中没有选出某一具体的变量，用模型进行描述；而是在所有的变量中建立起某种关系 。weka的全名是怀卡托智能分析环境（waikato environment for knowledge analysis）， weka是基于java，用于数据挖掘和知识分析一个平台。weka作为一个公开的数据挖掘工作平台，集合了大量能承担数据挖掘任务的机器学习算法，包括对数据进行预处理，分类，回归、聚类、关联规则以及在新的交互式界面上的可视化。 第二章 数据流的概述近十几年，随着科学技术飞速的发展，社会经济取得了巨大的进步，与此同时，在社会生产的各个领域中都产生了大量的数据，如人类

14、在对太空的探索中所产生的数据，银行每天的巨额交易数据等。显然，在这些数据中蕴涵着丰富的信息，但是，如何处理这些数据并从中得到有用的信息，是对当今计算机科学研究的一项重大挑战。虽然当前计算机技术的迅速发展使得处理数据成为可能，但是面对不断增加的海量数据，人们已经不再仅仅满足于简单的数据库查询功能，而是希望可以从数据中提取信息或者知识为进一步的决策服务。就数据库技术而言已经显得无能为力了，同样，传统的统计技术也面临着极大的挑战。这就急需有新的方法来处理这些海量数据。于是，数据挖掘技术就成为当前研究的一项重要的课题。对于传统的数据挖掘算法来说，样本容量已经成为制约其效率和准确度的一项主要限制。过小的

15、样本数据会导致学习模型的过度拟合（overfitting），而过大的样本又导致学习时间迅速增加到不可容忍的地步。但是对于当前的很多组织和公司来说，他们每天都会产生大量的数据，如大型的零售超市、电子商务网站、电信领域的服务商或者科研机构，每天数十gbytes的数据量是十分常见的。因此，将传统的数据挖掘模型加以扩展，使其可以处理数据流就有着十分重要的意义和应用价值。处理数据流的挑战性在于怎样用一种及时有效的方式处理如此庞大的数据。目前大多数文献所说的数据流（data stream）或称流数据（streaming data）是指单数据流。近年来，（单）数据流的挖掘得到了广泛的研究，提出了许多有价值的

16、模型和算法。随着网络环境应用的普及，单一数据流的应用必然向着多节点的分布式数据流方向转移。所谓分布式数据流（distributed data stream）是指相互联系的多个数据流。本课题主要对单数据流的分类方法及分布式数据流的分类方法进行研究，从宏观方面对单数据流的分类方法及分布式数据流的分类方法进行概述，以便为进一步的研究工作打下基础。随着网络技术的发展、计算速度的提升与存储容量的提高，引发了数据流处理的广泛需求。首先，搜集到的数据量大到无法完整的存储下来；或者即使存储下来了，处理第二遍的可能性也很小。其次，传统的数据处理方法要求多次扫描整个数据集，而在数据流应用模型中，大多要求单遍处理。

17、再次，数据流挖掘需要快速。实时处理以保证与高速的数据到达率同步。这些需求在面向全球范围内的网络监控、通话日志分析。web点击流分析等数据流应用中显得尤为突出。2.1数据流管理系统的研究目前国际、国内很多研究机构都在进行数据流方面的研究，但均处于实验原型阶段，还没有产品原型出现，下面简要介绍几个主要的数据流项目：(1) stanford的stream项目stream项目是一个处理在多重连续数据流和关系型数据上的通用的数据流管理系统，强调内存管理和近似查询解答。stream项目可按照用户的查询需求针对数据流进行实时的连续查询。(2) uc berkeley的telegraph cq数据流项目tel

18、egraph cq是目前发展时间最长，最成熟的一个数据流管理系统。它是一个连续查询处理系统，着重于共享查询评价和适应性查询处理。(3) aurora项目aurora项目是一个面向数据流量检测应用的数据流管理系统。采用了工作流系统模型中常用的box(功能盒操作符)&arrow(数据流向符)模型。用户根据查询需要，将查询表示为由arrow流向符连接起来的若干box操作符组合而成的网络模块，这个模式就是初步查询计划。用户注册一个查询，就是要生成一个相应的查询计划。查询计划被简单换成调度器中的不同查询处理队列。(4) niagara cq项目niagara cq基于一个xml的解析引擎，将信息从web

19、站点中抽取并保存，它可扩展性好，根据数据流的特点优化查询，并考虑了数据达到速度。(5) fiords项目fjords是california大学开发的传感器数据采集系统，主要应用于公路交通状况监测，通过计算传感器数据获取机车的行驶速度。(6) psoup项目psoup项目是berkeley的california大学研制的dsms，它是为支持cq (continuous query)系统而建立的。它的核心是允许数据元和查询是流，更重要的是支持双重流的存在。(7) 北京大学argus项目argus是北京大学计算机系开发的一个流系统，最初它是根据stream的原型和代码做初步研究，现已有了自己的代码。

20、该系统的主要应用就是用sqldba工具实现了流上的实时监控；另外argus还与372l进行合作，开发了一个对天网日志进行查询的监控服务器。2.2数据流在不同领域的应用许多应用领域产生的数据属于数据流(data stream)类型，如金融市场、网络监控、电信数据管理、传感器网络等。数据流高速、连续无限和动态的特性使得传统的数据管理和分析技术无效或需要改进，数据流的管理和挖掘成了一个研究热点。数据流管理的主要目标是建立具有类似于传统数据库系统功能的dsms(data stream management system)。数据流挖掘致力于从潜在无限的数据流中挖掘有价值的知识，典型的数据流挖掘问题有频繁

21、模式、聚类、分类、异常检测等。2.2.1在电信数据处理方面美国电话与电报公司(american telephone and telegraph corporation，简称at&t)对其骨干ip通讯网络部署了gigascope系统进行对网络流量分析与监视。监控的范围从固定网络的链路利用率(link utilization)、流量矩阵(traffic matrices)计算到自组织网络的入侵检测(intrusion detection)、性能故障(performance problem)等均有涉及。在gigascope部署的环境中，数据流应用要求对千兆位或更高链路速率的大容量数据进行处理并且要求

22、实时报告要求。at&t以此来发现用户使用通信网络的规律，对定价策略、网络维护、基础设施投资规划产生指导作用。gigascope目前运行在at&t实验室的ip主干网上，在网络监控数据处理方面取得了较好的效果。2.2.2在军事作战环境中美军联合监控目标打击雷达系统(joint surveillance target attack radar system，简称joint star)的设计作战规程中指出，陆军师一级、空军联队一级的单位需要对系统所产生的数据流信息具有完全的访问权限并进行处理。该系统的数据流处理结果将对战场移动目标指示物(moving target indicator)、固定目标指示物

23、(fixed target indicator)、合成孔径雷达(synthetic aperture radar)等设备提供的信息具有实时掌握能力，对指挥控制(command and control)提供有效支撑。2.2.3在科学计算领域方面费米实验室(fermilab)与欧洲核子研究中心(cern)对于高能物理粒子的研究实验每秒产生的数据量达40tb，即使经过硬件预处理后的压缩数据流流速也高达800gbs。若采用持久存储再进行分析的方法处理这些数据，则存储代价过高、计算量太大。采用数据流应用模型来处理该类数据可以加快处理速度、提高吞吐量。2.3数据流的特点从目前的应用场景来看，数据流处理技术

24、呈现的特点包括有：(1)数据流的动态性。由于数据流是在线实时产生的，根据具体应用不同、环境不同，数据产生的速率不一定，到达处理端的数据序列不一致。这就要求数据流处理技术能够灵活地处理各种速率的数据，消除突发数据流对系统可用性的影响。(2)响应的准时性。包括互联网流量监控、传感器网络监控、金融经济分析在内的数据流应用场景，对系统响应的实时性较高。(3)多数据流来源。在网络监控、数字化作战战场实时信息处理分析等数据流应用中，通过需要处理由多个来源发送的数据流。因此研究多数据流处理技术极为的重要。(4)单遍扫描需求。数据流是无限到达的，即不能确定其终止位置。因此不能将其全部存储后按照传统静态数据处理

25、方法反复扫描，而大多只能进行单遍扫描。一个数据流是实时、连续、有序、时变(time-changing)、无限的元组序列。与传统的数据集相比，数据流具有以下一些鲜明的特点：a)有序性。数据流中的元组按时间有序生成，序号隐含于到来的时刻或直接以时间戳记录。b)不可再现性。数据流中的数据一旦流过处理节点就不会再次出现，除非进行特殊的保存。c)高速性。数据流数据高速地生成，即产生元组的速率较高。d)无限性。数据流数据一直连续不断地产生，往往是无限量的。e)高维性。数据流往往包含大量的属性，即描述数据流的维数较高。f)动态性。产生数据流的概率分布模型是时变的，且变化的速率无法控制。2.4数据流挖掘框架

26、数据流挖掘是数据流管理技术的一个重要研究方向。数据流挖掘就是在流式数据上发现提取隐含在其中的、人们事先不知道的、但是又潜在有用的信息和知识的过程。由于数据流本身的特点，许多传统的数据挖掘技术不适合于数据流挖掘。因为数据是以流动方式出现，并不像传统的数据是静态存储在磁盘中，许多数据如果没有被保存将无法重新访问。所以，要求数据流挖掘技术不能多次重复扫描数据，只能对数据进行一次或几次扫描就完成挖掘。而且，数据流中的数据规模宏大，内存无法存储全部数据，也使得数据挖掘技术只能利用有限的内存提取数据流的概要特征信息作为挖掘算法输入数据，所以挖掘的结果通常是近似的。由于数据不断被更新，挖掘的结果也随时间不断

27、变化，因此，数据流挖掘技术应当支持增量计算，并不断将挖掘结果返回给用户。基于数据流的快速流入和数据流中的数据量极大的特点，要求算法的事件复杂度必须较低，必须能够在内存中实现，不能进行内外存数据交换，因为内外存数据交换会浪费大量的时间。内存资源的有限性也要求算法占用的内存不能太大。以下是数据流挖掘框架，在这个架构中，数据流算法需要在内存中维护一个概要数据结构，当新“元组到来时，更新概要数据结构，当需要查询挖掘算法处理结果时，也同样要从概要数据结构中获取信息。数据流挖掘算法输入数据内存中的概要数据结构挖掘结果输出 图2-1数据流挖掘框架2.5本章总结 本章介绍了数据流的概念和在不同领域的研究热点，

28、对数据流的特点进行研究，简单的介绍了数据流挖掘框架，数据流挖掘致力于从潜在无限的数据流中挖掘有价值的知识，很多领域都运用到了数据流技术，数据流的出现对传统数据挖掘技术提出了新的挑战。第三章 单数据流分类方法研究分类是最常用的数据分析方法之一，长期以来得到了不同学科的广泛研究，主要包括统计学、模式识别、机器学习、数据挖掘等。根据数据复杂度和数鼍的大小，本文将分类的研究工作分成两大类，即基于有限数据量和关于无限数据量。有限数据量主要是指数据可以驻留内存或磁盘的传统分类方法；无限数据量是指本文要研究的数据流分类问题。虽然传统的分类方法不能有效地解决数据流分类中的一些关键问题，但它们是新方法的基础，对

29、研究新方法具有启示作用。本章首先概述传统的分类方法，然后综述数据流分类的研究现状。没有特殊说明，以下所有的分类技术都是指自动分类，有关手工分类方法不作介绍。3.1传统的分类方法1)决策树决策树是一种类似树状结构的分类器。典型的决策树算法有：a)1984年，breiman等人基于统计科学提出了有名的cart(classification and regression tree)算法，用于构建二叉决策树，不但可以用于分类，而且能解决回归问题。b)1986年，quinlan基于机器学习方法提出了经典的id3(iterative dichotomiser)分类算法，1993年给出了它的改进版c45算法

30、，c50是它的后继商业版本。后来，c45成了其他监督学习算法比较的基准。id3、c45和cart仅仅适用于少量数据集，当数据集大于内存容最时会变得无效或效率极低。为此，一系列基于磁盘级的可伸缩性(scalability)决策树算法相继被提出和应用。c)1996年，mehta等人提出了sliq；同年，shafer等人给出了sliq的扩展版sprint。两者均采用特殊的数据结构来暂存必要的统计信息，它们可用于磁盘级数据量的训练集。不同的是，sliq中使用的类列表数据结构需要存放在内存中，而sprint的数据结构存放于磁盘中，不依赖于内存的大小。因此，当sliq的类列表大于可以使用的内存时，其性能低

31、于sprint。但sprint使用的哈希树(hash tree)的大小与训练集的大小成正比，当训练集较大时具有较高的计算开销。d)为了进一步提高算法的可伸缩性，gehrke等人在1998年提出了rainforest决策树分类算法。它使用的数据结构能适应可用内存的大小，性能优于其他基于磁盘级的决策树算法，包括sliq和sprint。类似的决策树算法还有public、clouds、boat等。文献对决策树算法作了一个多方位的综述。2)贝叶斯分类贝叶斯分类是一种统计学的分类方法，通过贝叶斯公式可以由先验概率(prior probability)计算出后验概率(posterior probabilit

32、y)。后验概率比先验概率提供更多的信息，从而可以作为分类的标准。贝叶斯分类方法主要有朴素贝叶斯分类和贝叶斯信念网络两种。朴素的(naive)贝叶斯分类假定不同属性对分类结果的影响是独立的，这样主要是为了简化计算。理论上当独立的假设成立时，朴素贝叶斯分类具有最小的分类误差，但是实际应用中会有误差。如果考虑属性之间的相互影响，就要用到贝叶斯信念网络。它通过定义属性之间的依赖网络来表示联合分布，从而提高分类的精确度。3)尽最近邻尽最近邻方法用一个度量来表示两个实例之间的距离。给定未知样本后，在已知的样本中挑选k个和它最接近的样本，然后找出这k个标记样本中最公共的标记来作为对未知样本的预测。它是一种懒

33、惰学习方法，先存放样本，直到需要时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销。4)神经网络的bp算法神经网络是对人脑神经运作方式的模拟，是一组相连的输入输出单元，用单元之间的相互连接权值的调整来达到学习的目的。后向传播算法在多层前馈(multilayer feed-forward)神经网络上学习。神经网络的训练过程需要很长时间，对于时间充裕的应用比较合适。其主要优点是容忍噪声数据以及其泛化能力；缺点主要是结果可解释性差，以及算法时间复杂度比较高。5)支持向量机svm是由vapnik等人于1995年提出。具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法，其主要

34、的思想是通过学习算法自动寻找出那些对分类有较好区分能力的支持向量确定一个超平面。svm有线性和非线性两种。线性svm对训练向量作线性变换，非线性svm通过非线性变换将向量映射到高维特征空间中进行计算。由于向量之间仅有点积运算，可以应用核函数(kernel function)技巧，避免复杂的运算；由于svm可以寻找全局最优解，有其他方法难以比拟的优势。其缺点是计算开销较大。6)集成学习集成学习建立一系列的分类器，然后采用多个分类器之间的(加权)投票结果作为数据的预测结果。现有的方法包括贝叶斯平均、包装(bagging)、推进(boosting)等算法。集成学习由于采用了投票平均的方法，有可能减少

35、单个分类器的误差，获得对问题空间模型更加准确的表示，从而提高分类器的分类精度。这些传统的分类方法一般采用批处理方式学习算法，具有较好的性能，已得到广泛应用。但它们主要基于以下假设：a)数据量有限，可以驻留内存或磁盘等，因此，一般采用批处理方式，整个数据可以多次存取b)从统计意义上说，训练集是数据总体的一个随机样本，总体分布是一个稳定的随机过程，因而，构建在充足训练集上的初始模型可以适用于整个数据。数据流数据不满足这些假设，传统的分类方法对它无效，需要扩展传统的技术和提出新的分类方法。3.2数据流分类技术3.2.1增量式(incremental)算法。增量(在线)学习算法是从连续无限数据流中抽取

36、模式的主要方法增量归纳的基本思想是，每当接收到一个实例时，更新一个已存在的模式比创建一个新模式的代价低许多。增量算法通过不断地处理来自数据流的新数据而修改模型,同时又不断将老样本的影响以一定的速率删除而加以改进,从而解决概念漂移问题。如domingos等人提出的增量式(incremental)、随时可用(any-time)的vfdt(very fast decision tree learner)算。它利用固定大小的内存、实时地处理数据、高效地构建了一个有效的决策树分类器。不同于传统的批处理方法，vfdt处理每一个决策树的节点时仅依赖于整个数据的部分子样本，对整个流数据仅作一次扫描，得到一个近

37、似的解。与传统算法相比，vfdt具有较高的时空效率，分类器的性能可以渐近于传统算法生成的分类器，vfdt不能处理含有数值型属性的数据。在传统的批处理学习方法中，处理数值型属性采用直接或所谓的精确方法。通过对数据集进行预处理，在内存或磁盘中分别保存按各个属性排序的数据集，统计每一个属性、每一个分裂点的信息，用于计算它们的分裂函数值，确定最佳的分裂属性和分裂点。这种精确方法需要对整个数据集多次存取；需要的存储空间与数据集的规模成正比；计算时间与属性及其分裂点的数目成正比。因此，它不能用于潜在无限、具有较多数值型属性的数据流。为了提高精确算法的可伸缩性，一些学者提出了采样(sampling)的方法。

38、对整个数据集采样，对样本数据采用精确的方法。这样虽然可以处理更大规模的数据集，但精确方法中的多次存取数据集和预处理等运算使得算法的效率较低。为了提高处理数值型属性的效率，有些文献中采用了离散化(discretization)的方法处理数值型属性。将连续的数值型属性转变成少数有序的离散值，避免了数据集的预处理运算，降低了时间、空间复杂度，但是离散化容易导致偏差太大，不能训练出有效的分类模型。由domingos和hulten研发出来的这种由决策树方法解决数据流分类的算法快速决策树算法(vfdt)。这是一种基于hoeffding数的决策树系统。决策树的建立是基于对最佳分裂属性的选择，而最佳分类属性的

39、选择是以使用的样本数超过了hoeffding界限为标准的。使用此技术后，能使其结果极为近似传统的分类方法。vfdt算法是基于这种技术的，此算法能够解决数据流分类研究中所面对的一些问题。这些问题包括：(1)分类属性的竞争：这种竞争发生在当两个或多个属性拥有详尽的分类指标值的时候，这种指标值可能是信息增益值或gini指标值。在决策树生长的过程中，当仅有获得这些数据的时候，必须在两个或多个属性问做出选择。虽然不能确定在数据量不足时是否该做出决定，但在到达了一定的误差范围后做出决定还是必须的。(2)内存限制：决策树能在内存耗尽后继续增长。解决这个问题的办法是尽量高效地维护决策树。(3)效率和准确率：这

40、是所有数据流分类算法所拥有的问题。上述问题在基于hoeffding数的vfdt算法中是采用如下技术解决的：(1)建立决策树的主要问题就是对属性中的分裂点的选择。属性问的竞争是使用一个用户指定的误差范围阈值来决定属性的选择的。在使用了这种方法后，当属性发生竞争的时候能够很快地使用一个基于一定误差范围的划分线来确定属性的选择。决定竞争属性所需的误差范围是由hoeffding不等式所提供的。设定一个极小值q。hoeffding不等式能确定所选择的分裂属性的正确率为1-q，当获得了一个足够多的训练样本，而这个足够多的样本是由log(1q)所决定的，是一个可以接受的数字。这种对分列节点准确率的范围确定能

41、够推广到整个树的构造。(2)对有限的内存空间问题的解决是分解那些最差的叶节点和属性节点。而最差的节点的选取是通过计算在这个节点中最高的分类界限和最低的分类界限的差别所确定的，差别大的为最差节点，而被定义为最差节点后就会被内存释放。(3)整个vfdt系统是受io限制的，换句话说就是处理样本的时间比读取样本的时间短。这是因为使用hoeffding树而产生的效果。这个系统可以在不需要重复读取数据的情况下快速地决定构造分类树中的属性点。而且，分类界限的计算是采用批处理方法而不是在线方法，这大量节省了为每一个属性点计算分类界限的时间。在低速数据流的情况下也可采用多次读取数据来提高结果的准确率。以上所提到

42、的这些技术在一组人工数据的测试下显示是有效的。vfdt分类方法假设数据是平稳分布的，没有考虑概念漂移的处理方法，忽略潜在概念中可能的改变(也即概念漂移)将会降低分类模型的预测性能。hulten等人在vfdt的基础上提出了解决概念漂移问题的算法cvfdt,cvfdt是vfdt的扩展，保持了vfdt的速度和精度，增加了检测概念漂移的能力。它拥有一个模型，该模型与滑动窗口中的样本一致，当某结点发生概念漂移时，cvfdt用新的最好的属性生长一颗可替代子树，当这颗可替代子树在新数据上比原先的子树预测更精确的，用这颗新的子树替代原先的子树。从而解决了概念漂移所导致的预测性能下降的问题。3.2.2集合分类器

43、增量学习建造单一的模型代表整个数据流，当新数据到来时，不断地重新定义这个模型。它们不能捕获数据流中的新趋势，当新的数据到来时，原来旧的数据被抛弃，因此可能排除旧的但有价值的信息，最近几年，用集成分类器挖掘数据流受到越来越多的关注。集成分类器算法是一个由多个基础分类器通过某种评价机制对数据流中的样本进行综合评价的集成算法。集成分类器算法已经被实验证明在处理存在概念漂移的数据流数据时比简单的分类算法具有更好的适应性和精确性。集成分类器算法是一个由多个基础分类器通过某种评价机制对数据流中的样本进行综合评价的集成算法。集成分类器算法已经被实验证明在处理存在概念漂移的数据流数据时比简单的分类算法具有更好

44、的适应性和精确性。理论上, 1988年, kearns提出了弱学习算法与强学习算法的等价性问题,即是否可以将弱学习算法提升成为强学习算法问题。1990年, schap ire证明了这样的假设是成立的,并给出了著名的boosting方法。这个理论也同时证明了集成分类器比一般单一分类器所具有的优势,即通过集成分类器进行综合评价的效果要好于单个分类器的分类结果。haixun wang等人提出了一种解决数据流上的概念漂移的一般框架。经过观察发现很多数据流分类问题都没有解决在进化数据流上的数据漂移问题，而这个框架就是基于解决概念漂移问题的。这个框架是基于使用一组分类模型，对分类结果进行投票表决，从而提高

45、分类精度的。这个分类模型是基于3个数据流挖掘中的主要问题而设计的：(1)概念漂移：分类器的精度对进化数据流上的概念漂移问题是很敏感的。在数据流分类过程中，如果一段数据流没有发生概念漂移，则不希望这段数据流被忽略掉。所以，需要一种方法能决定那一段数据流用来构造分类器。(2)效率：建立分类器的过程就是一个复杂的过程，而由于概念漂移，分类器的更新也是非常复杂的。在处理高速数据流的时候，效率问题越发显得重要。(3)鲁棒性：传统的集合分类器的设计就是为了提升算法的鲁棒性。集合分类器就是为了避免单个分类器中存在的过度拟合问题。然而，由于数据流所具有的高速性，很难高效地使用集合分类器。这个框架的设计动力很大

46、一部分来自于应对那些失效了的过往数据。在大多数程序中，如果只使用最近的数据流来构建分类器的话可能并不可行。虽然过往的数据流对分类器模型只有一些消极和负面的影响，但依然对现存的模型产生一些影响。而本框架使用带权值的集合分类器来减小过往数据对分类器精度的影响。本框架使用的分类器的权值是根据分类器当前的分类精度而确定的。每个分类器的权值是随数据流的进化而改变的。实验表明，此框架比单个分类器有明显的性能优势。这个结果部分是由于集合分类器天生所具有的鲁棒性所产生的，部分是由于其对潜在的数据流的变化能够更为敏感所产生的。3.3本章总结本章对单数据流的分类进行研究，首先介绍的传统的分类方法，主要介绍决策树和

47、贝叶斯分类。然后研究数据流的分类技术，主要由两个方面进行研究，一个是集合分类器，另一个是增量式的算法。并对一些问题进行研究与解决，并对其优缺点进行了总结。第四章 分布式数据流分类方法研究4.1分布式数据流的定义分布式数据流(distributed data stream)是指相互联系的多个数据流，其数据来自地理上分布的数据源，且各数据源观测不同的属性集。分布式数据流面临着许多挑战性的问题。首先，把多个节点的数据流传送到中心节点进行数据挖掘可以是一种解决问题的方法，目前的研究尝试这样的思路，从研究的角度能够更加深入的了解分布式数据流的挖掘特点，并且这是很有意义的。其次，从技术的角度上这种集中式的

48、数据传输是不可行的，数据流的集中式挖掘缺点是显而易见的：由于传输的数据量过大，可能会导致通讯问题、由于中心节点要处理不同分支传输来的数据，所以会导致中心节点的处理数据量大而导致计算机瓶颈等。目前，分布式数据流的应用越来越广泛（如传感网络，进程控制等）。我们从分布式数据流中提取知识的能力已经变得相当重要了。然而分布式数据流的分类研究工作才刚刚起步，有很多的知识和技术还有待我们去进一步的发现和学习，当前分类的方法主要采用的是集中式的处理框架，这种方法有很多的弊端，比如由于集中式处理容易造成通信负载过大，中心节点的计算量过大的原因，在许多情况下，将大量的分布在不同地方的数据汇总在一起进行分析是不可行

49、的；分布式数据流挖掘是数据挖掘技术和分布式计算的有机结合，集中式的挖掘方式没有充分的运用这其中的特点，将原本可以并行处理的数据的工作变成了串行来处理，这样增加了系统的传输负载和计算量，可能会导致一些重要的传输路径的瓶颈问题。分布式数据流挖掘是数据流挖掘技术与分布式计算的有机结合，主要用于分布式环境下的数据模式发现。分布式数据流挖掘是一个快速发展领域，受到国内外的广泛关注。它考虑两种分布式数据同构和异构。在同构的分布式环境下，每个站点观测相同的属性集，即一个实体(或事件)的全部信息集中在一个局部节点上，每个局部节点上收集整个系统的一个数据子集，所有局部节点上数据的并集构成整个系统的完整数据集。在

50、异构的分布式环境下，每个站点观测不同的属性集。即一个实体(或事件)的完整信息分布在不同的局部节点上。每个局部节点上观测的数据是相关实体(或事件)的部分信息。同构和异构有时也被称为水平和垂直划分。在同构站点的情况，每行定义了一个特有的实体，然而在异构的情况下，同一个实体的观测属性被分布在不同的位置。因此异构的情况下必须预先定义一些方法来关联同一实体的不同属性，行索引和关键字可用于识别不同站点上不同行之间的对应关系，在数据流环境下，可以时间戳来关联。4.2分布式数据流挖掘面临的挑战在网络环境下，不仅数据流的产生源分布在不同的网络节点，而且数据的传输路由以及目标地址也具有分布性。很多时间关键的应用像

51、传感器网络、网络入侵检测和欺诈性交易检测产生像“流一样的数据。它要求基于观测的新数据立刻做出决策。一般来说，这样的流数据在更多的新数据到达之前的短时间内有效。，因此，从异构的分布式数据流中进行知识挖掘是一个重要的研究课题，面临着许多挑战性的问题。(1)作为分布式数据流挖掘的基础，(单)数据流提出的问题对分布式数据流来说也同样需要面对。数据流的潜在无限性和达到速率的不可预测性等，使得传统的数据挖掘理论与算法不可能被直接利用。因为传统的处理大数据样本的多遍扫描或者非在线的处理方式显然不能来处理随时间变化的动态数据流。目前研究表明，数据流挖掘采用增量式算法是必须的，即随着流数据的到达不断更新模式。当

52、然，分布式数据流挖掘的增量式模式更新问题，面临着新的挑战：同一时间或者时间段，多个节点都可能有数据到达，而且速率可能差异很大。因此，如何准确而高效的对全局模式进行增量式更新需要有新的构架和模型来支撑。(2)集中式解决分布式数据流的模式挖掘问题是不现实的。由于分布式数据流的每个节点的局部数据流的数据达到速率都是不可控的，假如设想将所有节点的到达数据都及时送到一个中心节点来统一处理，那么网络传输时间和对中心节点的存储需求都是无法克服的问题。因此，研究分布式的模式更新策略是必需的，需要从可用的模型和应用构架到关键的问题(如局部模式与全局模式的融合)的解决算法等方面进行深入研究。另外，对于大规模的分布

53、式数据流来说，为了在线实时跟踪数据的变化，采用“准精确挖掘手段也是必需的，于是提高挖掘精度成了一个不可回避的问题。(3)为了提高数据流的挖掘精度，近年来人们开始关注数据流的集成学习(ensemble learning)模型和方法研究。集成学习需要同时维护多个模式，这样可以有效避免高速流动的数据带来的概念颠簸(即由于只保留最新的一个，可能使最近几个常出现的模式频繁切换)，也可以改善传统的非集成学习对样本数据的过分拟合的情况。对于分布式数据流而言，这样的问题存在而且更复杂。虽然，目前有些文献提到了相关问题，但是研究还是策略性的。因此，利用集成学习方法来解决分布式数据流的模式挖掘问题有很好的研究价值

54、。4.3分布式数据流相关系数计算设数据流x=x,x,.x,x,.x,.和y=y,y,.y,.y,.y,.，考察从第i项开始宽度为w的窗口中数据流之间的相关系数可以用下式计算： r= （1）为了适合基于基窗口的聚集，将式（1）作如下变形： （2）将，代入式（2）整理得： （3）将式（1）分母进行如下整理： （4）将式（3）和式（4）作为分子和分母代入式（1），得到4.4基于sprint的vhdds分类方法一般而言，同构的分布式数据流是指各节点的局部数据流的数据结构是相同的，即他们的属性个数、类别以及定义域都是相同的，局部数据流可以看作是全局模式的数据子集。相比同构的分布式数据流，异构的分布式数据

55、流的情况就复杂的多了，下面就来介绍一下基于sprint的vhdds分类方法。4.4.1 sprint算法简介sprint(scalable parallelizable induction of classification tree)，即可扩展的可并行的归纳决策树，是john sharer和rakesh agrawal于1996年提出的针对大型数据库的一种高速可伸缩的数据挖掘分类算法。该算法有效解决了内存大小对于数据规模的限制问题，并且在系统运行时间、规模可扩展性、应用可扩展性等方面优于其它的分类树算法。同时，在设计中兼顾了并行处理，允许多个处理器相互合作以生成一致的模型，这进一步增强了可伸缩性。算法最初的目的是要解决内存大小对