数据挖掘与模式识别

数据流频繁模式挖掘算法的研究与实现


太原理工大学硕士研究生学位论文Filter)算法。

该算法釆用滑动窗口模型挖掘最近一段时期内的频繁模式,并利用一个比特序列移位简化了滑动窗口的操作,提高了事务处理效率同时通过驻留在内存中的一个集合结构对数据流中非频繁模式进行过滤,减少了保存的信息量,使算法的内存使用率保持在一个较低的范围内,而频繁模式只需在此集合上即可生成。

实验表明,算法的空间复杂度与数据流取值范围无关,而且不会随着滑动窗口长度的增大而显著增加,特别适用于周期较长、数据取值范围广的数据流频繁模式挖掘。

关键词:数据流,数据挖掘,频繁模式,滑动窗口太原理工大学硕士研究生学位论文RESEARCH AND IMPLEMENTATION OFFREQUENT PATTERNS MINING ALGORITHMSOVER DATA STREAMABSTRACTWith ten years'research, data mining technology has been maturatingBenefitting from the development of puter network technology and datagathering technology, data stream as a new data model has more and moreappeared in many applications, such as sensor networks, stock analysis, networkmonitoring and so on. Because of the following characteristics: potentiallyunbounded volume of data, rapid and continuous arriving of data and changingdistribution with time, data streams bring new request of technologyFrequent patterns mining is the fundamental and critical subject of the datamining in data streams, which is has been widely used in solving problems ofassociation rule discovering, iceberg query, classification, cluster and so on. Thecharacteristics of data streams require that algorithms of mining data streamsmustmeet the following requirements: the speed of data processing should be asfast as possible, and must be faster than the data ing rate. So theputational plexity of the algorithm should be low. Furthermore, thepotentially unbounded volumes of data request the low space plexity and太原理工大学硕士研究生学位论文limit memory usage not obviously increasing with the amount of data. Inaddition, because the data ing rate and the distribution are changing withtime, the algorithms should be dynamically adjusting the parameters to adapt tosuch changes. Traditional data mining algorithms are developed to work onstatic data and, thus, can not be applied directly to cope with stream dataThis paper first studied the traditional theory and classical data mininalgorithms, then analyzed the characteristics and related processing technologyThe characteristics and implementation of classification and cluster was alsodiscussedThis paper aimed at frequent items and frequent patterns mining over datastream. Based on systematically analyzing the three models of frequent patternsmining over data stream and exist algorithms, we proposed a algorithm namedBSW-Filter( Bit-sequence Sliding Window with Filter) for high-speed datastream to mining the recent frequent patterns with sliding window. It applies theshift of a bit-sequence to simply the operation of sliding window so that theefficiency of dealing with transactions is improved. Due to filtering outinfrequent items by a special set retaining memory, the memory usage of ouralgorithm can remain at a low level. Frequent patterns can be generated based onthe set. The experiments show that the space plexity is independent to thevalue range of elements and does not grow dramatically with the increase of thesliding window size. So the method is especially applicable to data mining witha wide range of data values in a long period太原理工大学硕士研究生学位论文KEY WORDS: data stream, data mining, frequent pattern, sliding window太原理工大学硕士研究生学位论文第一章绪论随着科学技术的高速发展和信息技术的广泛应用,人类产生数据和获取数据的能力迅速提高,海量数据的积累成指数级增长。

与这种现象相对应的是,人类处理和分析数据的能力却相当冇限,面临着拥有数据海洋却知识匾乏的尴尬处境;互联网的兴起更加剧了“数据爆炸,知识匾乏”这一趋势。

数据挖掘技术旨在从大量数据中提取有用的知识,帮助人们进行科学分析和决策。

经过近十几年的发展,很多有用的挖掘算法和模型相继被提岀,并已经被应用到多个相关领域。

然而,近年来,越来越多的应用产生的数据以流的形式出现。

这些数据数量大、速度快,而且随着时间连续不断的产生。

这种新的数据形式被称为数据流( Data stream)。

传统的数据挖掘算法是针对静态数据的不适用于数据流模型,这促使人们设计新的算法来处理数据流挖掘1.1课题的背景和意义数据流是一种由连续、实时、有序的数据组成的序列,作为一种新的数据处理模型最早是由 Henzinger等人于1998年在文献[2]中提出的。

早期的数据流模型主要应用于网络监控方面,后来出现在一些传感器网络系统上。

这些系统的数据都是连续不断地生成的,使用数据流处理技术主要用来生成摘要信息,减小数据存储和传输带宽。

如今,数据流已成为新一代计算理论与应用的硏究热点之一,并广泛应用于众多领域中,例如:在股票交易系统中,每天使用该系统的用户有上万人,每个客户每天都要进行若干次交易,每次交易还要涉及金额、数量、股票名称等多项属性。

所有这些都需要如实完整的记录下来以备分析处理。

这些记录按照时间顺序排列,在时间维度上形成“流”的形式,源源不断的交由分析系统处理在电信行业中,通信公司每时每刻都会采集到用户的通话或者短信记录,这些记录也包括若干属性,如主叫号码,被叫号码,通话时间,收费金额等等。

大量的通话记录以时间顺序排列,汇集到通信公司的数据中心,也可以被抽象为是一种“流”。

在互联网中,一个Web网站服务器的日志文件要对每天访问客户点击进行记录每个客户访问页面的时间、内容都不同。

这些记录也是按照时间顺序生成的,如果要对客户的行为进行分析,提供个性化服务,只要将这些记录按顺序输入处理中心进行处理太原理工大学硕士研究生学位论文即可此外还有大型超市的销售记录、科学研究收集的数据(如天文观测、大气分析)等,这些都是数据流的例子。

它们产生的领域虽然不同,但是都有一些共同的特征:首先数据量非常巨大,并且会随着时间增长持续上升,如一个沃尔玛超市的日交易次数就可达数十万;其次,这些数据均按照时间顺序连续收集,从数据抽象的角度看,就像是随时间运动的“流”;另外,数据产生的速率很高,例如,除夕当天中国移动的短信发送量为46亿条,相当于每秒上万条;最后,这些数据产生的周期一般比较长,甚至是无限的,取值范围很广泛或者不确定,而且数据到达的速度和次序无法控制,分布也会随时间发生改变难以预测4数据流的这些特点决定了在对其进行处理的时候不能像传统技术那样,将其全部转存到存储介质中后,再通过数据操纵语言( Data Manipulation Language,简称DML)命令访问存储介质来获取査询结果。

因此,一方面,由于数据流规模很大且到达速度非常快,人们希望能够构造一个类似传统关系型数据库的数据管理系统,方便对这些数据流进行査询和管理;另一方面,这些快速产生的数据背后同样隐藏着许多重要的信息,如果能把这些信息从数据流中抽取岀来,将极大丰富人们的认识或者创造很多潜在的价值,所以人们也希望能够像对数据库一样对数据流进行数据挖掘。

因而数据流研究目前主要集中数据流管理系统( Data Stream Management System,简称DSMS)和数据流挖掘两个方面。

对数据流的研究除了具有重要的理论价值,还具有很重要的现实意义,很多现实中的问题都能够通过数据流处理技术和数据流挖掘解决。

目前已经有很成功的系统和方法在实际中得到应用,随着计算机网络技术和数据集技术的发人们对相关领域的需求会越来越迫切。

1.2研究现状数据流作为一个较新的领域,有许多的发展空间和研究方向。

目前研究比较多的是数据流处理的模型和语言;处理类似于普通数据库査询的流査询;数据流的采样和近似技术;数据流处理时对内存的管理;对高速数据流的挖掘算法;新型的数据流处理的应用。

这些都是重要的和活跃的研究领域,国外许多大学和研究机构都进行了广泛深入的研究,并取得了一些相关的成果。

太原理工大学硕士研究生学位论文1.2.1数据流管理系统数据流管理系统是一种新的数据管理模型,它是內存数据库、时态数据库、主动数据库、实时数据库、分布式数据库等一系列现代数据库技术的融合。

数据流管理系统是专门为处理数据流而设计,它和传统的数据库管理系统的主要区别如表1-1所示。

数据流管理系统设计中的一个重要问题是如何有效地处理连续查询,即长时间连续执行一个査询。

对数据流进行的査询为连续查询,它在一段时间内连续执行,随着新数据的到达将不断地产生新的查询结果。

例如在网络通信量管理中,连续查询用于在线监控网络行为,以便及时发现异常(如连接异常)和产生异常的原因(如硬件失败、服务器受到攻击等);连续査询还用于支持负载平衡或其他网络性能调整。

在许多金融管理系统中连续査询用于监控趋势变化并且识别一些短暂易逝的机会。

表1-1DBMS和DSMS的对比Table 1-1 Comparion of DBMS and DSMSDBMSDSMS数据对象持久静态的数据源瞬时连续动态的数据源实时数据,按时间顺序访问,数据处理后数据存储存储在磁盘中,可被随机访问被丢弃或归档,一般无法再次访问数据相对较低的更新率数据更新率高空间需求极大的磁盘存储有限的内存空间响应时间非实时性服务存在实时性处理的需求访问方式随机访问顺序访问处理结果在保证准确性的前提下,更快地得到结果强调结果的实时性,可以接受近似结果在薮据流管理系统中,薮据到来之后,并不是存储到磁盘上,而是直接进入流查询处理器:用户的査询则交由流査询处理器,査询处理器保证了用户的査询一直保持有效,直到用户注销或査询到达结束时间,实现连续査询;概要数据保存当前数据的概要信息,为数据流的实时处理做准备,并随着数据流的变化动态更新;最后生成的结果也以数据流的形式显示给用户对数据流的硏究国外开展的比较早,在数据流管理方面就有 STREAM、 Telegram等多个原型系统。

目前,与数据流管理系统相关的研究主要集中在连续査询语言、系统资太原理工大学硕士研究生学位论文源管理(主要是内存)、近似査询操作、流系统的调度等几个方面STREAM是 Stanford大学 R Motwani教授领导研究的一个项目,其目标是实现个通用的数据流管理系统。

在 STREAM系统中,查询首先被注册,随着新数据的到来,查询不停地被执行。

CQL( Continuous Query Language)是 STREAM的标准查询语言是扩展了的SQL语言,主要表现在From子句,From子句包含一个可选的滑动窗口和个取样子句。

它既支持传统的关系操作,又支持流操作。

加州大学伯克利分校的Telegraph,是一个自适应的数据流连续查询处理系统。

主要是基于主动查询处理引擎来处理査询,其元组路由和分组过滤技术可以实现多查询操作算子的共享,有效地降低了查询处理的内存开销。

在 Telegraph中,査询首先要被注册,注册后返回给用户一个句柄,然后不停地执行査询请求。

查询语句的一般模式是: SELECt Select- list fromfrom-list Where conjoined boolean factors BeGin begin time END end time。

目前的数据流管理系统多数是集中式系统,而且专注于某一方面的应用而缺乏通用性,限制较多使得应用范围狭窄,因此,开发通用的、面向对象的、分布式数据流管理系统将是今后数据流管理系统的发展方向在国内,哈尔滨工业大学、复旦大学、东南大学、北京大学和东北大学等都在数据流管理,特别是数据流连续査询等方面开展了大量的研究工作,并取得了一定的阶段性成果71,但是总的来说,还处于起步阶段。

1.2.2数据流挖掘w 数据流挖掘是数据流硏究的另一个重要硏究方面,是在流式数据上发现提取隐含在其中的、人们事先不知道的、但是又潜在有用的信息和知识的过程。

目前数据流挖掘的研究工作主要集中在薮据流的聚类、分类、频繁模式挖掘和薮据流变化及离群点检测等方面。

数据流聚类算法方面,Guha在2000年提出了基于k中心点的 small-space算法l2,该算法使用一个迭代过程实现了在数据流环境下的k-中心点聚类。

他还在文献[1l3]中扩展了k-均值算法来处理数据流。

他们提出的算法仅仅使用单遍扫描,并且需要存储空间相对较少。

算法的时间复杂度和空间复杂度分别为O(nk)和O(ne),其中n是数据元素的个数、k是簇中心点的个数,c<1。

Babcock等在文献[14]中使用一种称为指数直方图( Exponential Histogram,简称EH)的数据结构来改进Guha等人的算法。

算法思想没太原理工大学硕士研究生学位论文有改变,仅仅用EH结构来实现簇的合并。

2003年, O'Callaghan在 small-space2的基础上发展了著名的 STREAM算法1,采用分级聚类的方法,使用质心和权值(类中数据个数)表示聚类。

C Aggarwal和Han等人提出的流数据聚类算法 CluStream1把数据流看成一个随时间变化的过程,而不是一个整体进行聚类分析,该算法有很好的可扩展性,可产生高质量的聚类结果,尤其是在数据流随时间变化较大时比其它算法产生更高质量的聚类。

数据流分类算法是数据流挖掘重要组成部分,典型的有ⅤFDT( Very Fast DecisionTre)、 CVFDT( Concept-adapting Very Fast Decision Tree)s等。

国内王鹏等提出了种数据流上的基于频繁模式的分类算法CAPE9,CAPE通过数据流中的频繁模式进行分类,在压缩数据的同时保存了数据中的分类信息。

在频繁模式挖掘方面, Manku提出的 Lossy Counting算法20,通过近似计算对当前整个数据流中的频繁项进行挖掘。

Charikar提出了一次扫描数据流的算法返回当前K个频繁项21。

Chang的 estEe算法2,通过一种按时间指数进行衰减的策略挖掘最近的频繁项集。

Giannella和Han等3提出了在任意时间粒度上挖掘频繁项集的近似算法Yun Chi提出基于滑动窗口的频繁闭项集挖掘算法碑,采用CET( Closed EnumerationTree)数据结构存储数据流中的所有项集,根据滑动窗口数据的变化实时更新CET中四种不同类型的项集,但是对于项集进入CET以前的信息,算法并没有提供相应的处理手段。

张昕等在文献[25中提出一种改进的字典树结构 IL-TREE,并在其基础上提出种新的启发式算法FPL- Stream。

徐利军等提出的 MGRDS算法利用频繁集的产生集表达方式来挖掘基于整个数据流的频繁集。

该算法结合了倾斜窗口策略,在及时处理数据流的前提下,降低了数据的平均处理时间,提供了更细粒度的査询,在更新模式和生成新模式的过程中,可以快速定位历史模式。

Li Hua-Fu等提出 DSM-MFI算法1,用于挖掘最近的最大频繁项集数据流变化检测是数据流环境下所特有,文献[28]综述了在线挖掘数据流变化的重要意义。

Ben- David等不仅总结了数据流变化检测的应用领域和现实意义,而且提出了一种新的距离度量方法相对差异度量方法,并在此基础上,提出了一种非参数变化检测方法。

基于薮据挖掘概念的离群点检测对于网络监控、异常检测具有重要意义,目前已经取得了许多重要的成果,出现了一些有效的检测算法,例如:Yu等人提出的面向高维太原理工大学硕士研究生学位论文数据离群点检测算法 Findout30, Breunig等人提出的离群点检测算法LOF等。

然而上述算法在处理大规模数据集时均存在空间和时间复杂度较大的不足,特别是不能够处理只能进行一遍扫描的数据流数据。

Muthukrishnan等32首次提出了针对大规模数据流的异常检测算法, Palpanas时等针对分布式数据流中的离群点检测问题提出了一个分布环境下信号网络中异常检测的框架,杨宜东等提出了基于核密度估计的分布式薮据流离群点检测算法 FindOut strean34。

1.3本文结构第一章介绍了数据流挖掘的硏究背景和意义,并从数据流管理系统和数据流挖掘两个方面介绍了国内外相关研究的现状和已有的研究成果第二章对数据挖掘的基本理论和概念进行了介绍,探讨了常见的数据挖掘方法,并结合每种方法的代表性算法描述了其不同的技术思想和技术特点。

第三章数据流挖掘讨论了数据流挖掘的特点和技术要求,对比静态数据挖掘介绍了数据流上分类和聚类方法的不同特点和实现。

第四章数据流频繁模式挖掘详细讲述数据流频繁项和频繁模式挖掘的基本理论和对应的处理技术,对不同处理模型进行了介绍和总结第五章提出了基于滑动窗口模型的BSW- Filter算法,并用实验验证了算法的运行效第六章对本文的内容进行总结并对今后的研究进行了展望。

太原理工大学硕士研究生学位论文第二章数据挖掘从上个世纪70年代起,数据库应用技术迅速发展且得到了广泛应用。

从各种商业数据开始存储在计算机的数据库中,然后发展到可对数据库进行查询和访问,进而发展到对薮据库的即时遍历;薮据建模形式也由层次数据库、网状数据库、关系数据库,直到对象数据库。

人们在享受数据库技术的方便快捷的同时,也遇到了一系列问题:第是数据库规模越来越大,信息过量,难以消化;二是信息真假难以辨识;第三是信息安全难以保证;第四是信息形式不致,难以统一处理。

数据库中存储的数据量急剧增大,在大量的数据背后隐藏着许多重要的信息,如果能把这些信息从数据库中抽取出来,将会创造很多潜在的价值,极大丰富人们的认识,数据挖掘概念就是从这样的商业角度提出来的。

21数据挖掘简介C(n2.1.1数据挖掘概念数据挖掘技术是人们对数据库技术进行长期研究和开发的结果。

数据挖掘,又称为数据库中知识发现( Knowledge Discovery in Data Base,简称KDD),它是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的人们事先不知道的、但又是潜在有用的信息和知识的过程。

随着以 Apriori算法和 FP-Growth算法为代表的一系列算法的提出,针对静态薮据库的数据挖掘技术逐步发展成熟起来数据挖掘是对数据进行更深层次的处理,是一个多步骤处理的过程,而不仅仅是对数据进行加减求和等简单运算或査询。

它能够提高信息利用率,帮助人们从海量数据中发现未知而且有价值的信息,找出数据之间的潜在联系,从而促进信息的传递。

其中数据是用来描述事物的信息,应该是真实的、大量的、含噪声的,可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形和图像数据;信息和知识(包括概念、规则、模式、规律和约朿等)应该是用户感兴趣的、可接受、可理解、可运用的:潜在、未知是指数据挖掘出的内容应该是新颖的隐含的;发现的知识的方法可以是数学的,也可以是非数学的,可以是演绎的,也可以是归纳的;发现的知识可以被用于7太原理工大学硕士研究生学位论文信息管理,査询优化,决策支持和过程控制等,还可以用于数据自身的维护数据挖掘是统计分析、数据可视化、人工智能、机器学习、高性能计算和数据库技术等众多领域交叉形成的新兴学科,在市场营销、金融预测和决策支持等领域具有广泛的应用前景。

2.1.2数据挖掘流程数据挖掘通常由以下几个步骤组成37(1)数据清理:消除噪声、不一致或冗余数据。

(2)数据集成:多种数据源可以组合在一起。

(3)数据选择:从数据集中选择出与分析任务相关的数据(4)数据变换:将数据变换成适合挖掘的形式,如可对薮据执行汇总或聚集操作。

在有些情况下,数据变换在数据选择过程之前进行,如数据存储在数据仓库时(5)模式抽取:使用智能方法提取数据模式(6)模式评估:评价发现的模式是否是用户感兴趣的知识(7)知识表示:使用可视化等知识表示技术,以直观的方式告诉用户通常把前面四个阶段合起来称为数据准备阶段,主要对数据进行预处理,为模式抽取做好准备。

模式抽取是数据挖掘中的核心步骤,也是数据挖掘硏究的主要方向。

模式抽取首先要确定任务或者目的,然后决定使用的挖掘算法。

不同的仼务需要使用不同的算法,即使是同一任务,也可能有多种选择。

在选择算法时,除了目的之外,还需要考虑多种因素,如数据的特点、对结果准确度或者可理解程度的要求等。

模式评估主要是根据用户的兴趣度以及支持度和误差度等标准,对模式抽取的结果进行筛选,删除冗余或无关的模式,保留有用的模式。

如果发现结果不满足用户要求,这时则需要将薮据挖掘退回到模式抽取阶段之前,如重新选取数据,重新设定算法的参数值,甚至换一种挖掘算法。

知识表示是对最终发现的模式进行可视化等处理,把结果转换为用户容易理解的表现形式。

2.2数据挖掘分类利用数据挖掘可以获得决策所需的多种知识,其主要技术有关联分析、分类分析聚类分析、异常性分析、趋势分析等。

8太原理工大学硕士研究生学位论文22.1数据特征化数据特征化是把数据集从较低概念层次抽象到较髙概念层次的过程。

通常数据集中的数据是比较具体和详细的。

但在某些应用中,用户需要在更高的抽象级别上分析数据,这就要进行一定的抽象化即数据特征化。

目前,主要有两类方法进行:1)数据立方体,它是数据仓厍中的一个常用概念。

它的基本思想是通过计算某些常用的聚集函数,诸如计数、求和、平均、最大值等,并将这些结果储存在数据立方体中。

在多维数据立方体中存放预先计算好的结果将能保证快速响应,并可灵活地提供不同角度和不同抽象层次上的数据视图2)面向属性归约,它是一种交替的、增量的、基于概括的数据分析方法,其核心是增量数据概括。

它利用一种特殊的背景知识,如概念层次或者格,按照背景知识把数据集中的原始数据转换为更高级的概念222分类分析分类是这样的过程,它找出描述并区分数据类或概念的模型,以便能使用模型预测类标记未知的对象类。

分类从数据中发现对象的共性,并将对象分成不同种类。

执行分类需要提供训练数据集,通常按一定比例将数据集划分为训练集和测试集,训练集用于分类、建立模型,测试集用于对模型进行测试和修正。

一个元组的种类都已知的样本数据集通常被当作训练集。

分类的目标首先是对训练数据进行分析,使用数据的某些特征属性,给出每个类的准确描述,继而用测试集对分类进行测试,以便为每个类找到更合理的描述,获取更合理的分类规则,再运用这些分类规则对新的记录分类常用的方法有决策树归纳、贝叶斯分类、神经网络、K-最临近分类、粗糙集、模糊集、关联分类和遗传算法等,其中决策树方法优点突出,应用较多。

决策树是一种树结构,其中每个非叶节点代表一个条件属性,其下的每个分枝代表该条件属性的一个取值,而每个叶节点代表一个类或类分布,树的最顶层节点为根节点。

当决策树创建时,由于数据中的噪声和孤立点,许多分枝反映的是训练数据的异常,因此在决策树方法中般采用剪枝方法处理这种过分适应数据问题,剪去不可靠的分枝,提高决策树独立于测试数据的正确分类能力。

决策树的代表算法有ID338和C4.59。

ID3算法的具体方法是:从树的根节点处的所有训练样本开始检验所有的属性,选择信息增益最大的属性产生决策树节点,由该属性的不同取值产生一个分支,再对各分太原理工大学硕士研究生学位论文枝的子集递归调用该方法建立决策树节点和分枝,直到某一子集中的所有记录属于同类ˉ4.5算法在决策树各级节点上选择属性时,也采用信息増益作为属性的选择标准C45算法采用“窗口”的概念,首先从所有记录中选取一部分用来构造决策树,再利用剩余的记录测试决策树并对其进行调整,边生成,边测试边调整。

因此,错误率低,结果可靠。

223聚类分析聚类是搜索簇的无监督学习过程。

与分类不同,无监督学习不依赖预先定义的类或带类标记的训练实例,需要由聚类学习算法自动确定标记,在分析数据时不考虑已知的类标记,按照最大化类内相似性,最小化类间相似性的原则,将数据对象划分为不同的簇。

因为事先不知道对象所属的类,聚类是观察式学习,而不是示例式学习。

聚类能够作为一个独立的工具获得数据的分布状况,还可以作为其他数据挖掘任务(如分类、关联规则)的预处理步骤。

聚类算法可以分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法"。

划分方法( Partitioning Method,简称PM):首先对一个给定m个对象的数据集创建k(k≤m)个划分,k为要创建的划分个数。

然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量,并且要求:(1)每个划分至少包含一个对象:(2)每个对象属于且只属于一个划分。

典型的划分方法包括:K-均值算法4和K中心点算法0。

层次方法( Hierarchical method):创建一个层次以分解给定的数据集。

该方法可以分为自上而下(分解)和自下而上(合并)两种操作方式。

合并方法是将每个对象视为一个簇,相继合并相近的簇构成更大的新簇,直至达到一个终止条件;分解方法是将所有的对象视为一个簇,然后相继分裂不相近的簇为若干个更小的新簇,直至满足终止条件。

为弥补分解与合并的不足,层次方法经常要与其它聚类方法相结合。

典型的这类方法包括:1)BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies)7j法4,它首先利用树的结构对对象集进行划分,然后再利用其它聚类方法对这些聚类进行优化太原理工大学硕士研究生学位论文2)CURE( Clustering Using Reprisentatives)方法42,它利用固定数目代表对象来表示相应聚类,然后对各聚类按照指定量向聚类中心进行收缩;3) CHEMALOEN4则是在层次聚类时构造动态模型●基于密度的方法( Density- based Method):这类方法根据每个簇的密度阈值,而不是簇的数目阈值控制聚类的过程,即:只要周围簇的密度超过某个阈值就不断聚类,聚类终止的条件是满足密度要求。

典型的基于密度方法包括1)DBSCAN(Densit-based Spatial Clustering of Application with Noise)(441该算法通过不断生长足够高密度区域来进行聚类,它能从含有噪声的空间数据库中发现任意形状的聚类,此方法将一个聚类定义为一组“密度连接”的点集;2) OPTICS( Ordering Points to Identify the Clustering Structure),该算法并不明确产生一个聚类,而是为自动交互的聚类计算出一个增强聚类顺序,通过对象识别排序识别聚类结构。

●基于网格的方法(Grid- based method):首先将对象空间划分为有限数目单元以构成网格结构,所有的聚类操作均在此网格结构上进行。

这类方法的处理时间不受数据对象数目影响,仅依赖于量化空间中每一维上的单元数目,因此处理速度很快。

STING( Statistical Information grid)46就是一个利用网格单元保存的统计信息进行基于网格聚类的方法。

基于模型的方法 Model-based Method):为每个簇假定一个模型,寻找数据对给定模型的最佳拟合。

典型的基于模型方法包括1) COBWEB47,这是一个常用的且简单的增量式聚类方法,它的输入对象是采用符号量(属性-值)对来加以描述的,采用分类树的形式来创建一个层次聚类2) CLASSIT4是 COBWEB的另一个版本,它可以对连续取值属性进行增量式聚类。

它为每个结点中的每个属性保存相应的连续正态分布(均值与方差);不像 COBWEB那样计算离散属性和,而是利用一个改进的分类能力描述方法对连续属性求积分。

但是 CLASSIT与 COBWEB都不适合对大数据库进行聚类处理。

太原理工大学硕士研究生学位论文224孤立点分析孤立点分析也称孤立点检测,用于挖掘数据库中那些与数据的一般行为或模型不致的数据对象。

它通过发现异常和极端特例,揭示事物偏离常规的异常现象,而大多数数据挖掘方法则将异常数据当作噪声或例外情况予以删除。

事实上在不少情况下,异常数据含有重要信息,比如可应用于发现金融欺诈行为。

可以按照一定的统计分布假设或使用基于距离的度量来检测异常数据,还可以使用基于偏差统计的检测方法。

22.5趋势分析数据趋势分析描述行为随时间变化的对象的规律或趋势,并对其建模。

如对股票交易数据的演变分析可以识別整个股票市场和特定公司的股票演变规律。

这种规律可以帮助预测股票市场价格的未来走向,帮助投资者对投资作出决策23关联分析关联分析即关联规则挖掘,展示了“属性-值”频繁的在给定数据集中一起出现的条件,揭示了数据中对象之间相互依赖或关联的知识,是基于数据项同时出现的特征而不是基于数据自身的固有属性(例如函数依赖关系),不能通过数据库的逻辑操作(如表的联接)或统计的方法得出。

一个典型应用就是市场购物篮分析中,关联规则可辨别商品之间是否存在某种关系,例如:可以通过对数据的分析得出“购买了电脑的人中有90%的又购买了打印机”的关联规则。

关联规则提供的信息可以用作设计商品销售目录、商场布置、市场营销的参考,可以帮助许多商务决策的制定。

23.1关联规则基本概念定义2-1给定全集/={x1,x2,…,xm}是数据项的集合,与任务相关的数据集合D是数据库事务集合,其中事务7={t,x,x2,…,xn},其中x∈l,1≤-n,n表示事务的长度,l是事务的唯一标识。

T中的数据项属于l,即{x,x2,…,xn}1。

数据集的大小即为数据集中包含的事务的数量,记为D。

X是一个项集,事务T包含X当且仅当XT。

一个关联规则是形如XY的蕴涵式,其中XI,Y,并且∩Y=d。

定义2-2规则XY在事务数据库D成立,具有支持度s( support),其中s是事务太原理工大学硕士研究生学位论文集中包含X和Y的事务数与所有事务数之比,记为sppo(X1),即 support(XY=P(XY。

规则支持度越高,说明出现的次数越多定义2-3规则XY在事务数据库D中具有置信度c( confidence是指包含X和Y的事务数与包含X的事务数之比,记为 confidenc(XY)=P(Ⅺ1Y)。

置信度越高,说明这条规则越可靠。

给定一个事务集D,挖掘关联规则问题就是寻找支持度和可信度分别大于用户给定的最小支持度(mis)和最小可信度( minion)的关联规则,同时满足最小支持度和最小置信度的规则称为强规则定义2-4Ⅰ的非空子集被称为模式(也叫项集,以下不区分这两个概念)。

一个模式所包含的项目数被称为该模式的长度。

长度为k的模式可简写为K-项集。

定义2-5数据集D中包含模式P的事务数量称为在D中P的计数,记f(P)或简写为fP)。

数据集D中包含模式P的事务在所有事务中所占的比例称为P在D中的支持度,记为 supportD(P)或简写为spor(P)。

显然spor(P)=(PD。

对于事先给定的阙值s(0<≤1),如果有spor(P)>s,则称P是频繁模式。

定义26最大模式是频繁模式P,使得P的任何真超模式(Q是P的超模式,如果P是Q的子模式,即Ω包含P)都不是频繁的;频繁闭项集是一个频繁的、闭的项集,其中项集P是闭的,如果不存在P的真超集P,使得每个包含P的事务也包含P使用最大模式和频繁闭项集可以显著地压缩挖掘所产生的频繁项集数定理2-1频繁模式具有反单调性,即频繁模式的子集是频繁的,非频繁模式的超集是非频繁的证明:结论是显而易见的23.2关联规则挖掘过程关联规则挖掘分为两个过程,第一步根据最小支持度,在大量事务中找出所有的频繁模式,第二步根据最小置信度,由频繁项集产生强关联规则。

第一步比较容易,一般经过第一步的筛选后,频繁项集都不会很多,通过子集产生法就可以产生关联规则,步骤如下1)对于每个频繁模式P,产生的所有非空子集;2)对于P的每个非空子集Q,若sP)s(Q) minconf,则输出规则Q(PQ太原理工大学硕士研究生学位论文其关联规则方法的硏究集中于频繁模式发现。

因为数据集中的数据量巨大,该问题的主要难点在于频繁模式挖掘。

如何以对数据集较少的扫描次数、对每个事务较少的项集比较次数来完成这一过程,即如何用最快的速度获得频繁项集,是各种算法所研究的关键问题。

23.3频繁模式挖掘算法频繁模式挖掘是数据挖掘的一个重要硏究领域,在关联规则挖掘、冰山査询( sebergy)两、 ceberg-Cube问题等方面有着广泛应用,因此引起了广泛的关注和研究,也提出了不少有效的方法R. Agrawal等1994年提出了著名的关联规则挖掘算法 apriori3是迄今为止一种最有影响的挖掘布尔型关联规则的算法,该算法正是基于定理2-1设计的。

它首先产生长度为1的频繁模式L1,然后是长度为2的频繁模式L2,直到有某个k值使得Lk为空,算法终止。

在每次循环中,首先产生长度为k的候选集Ck,Ck中的每一个模式是由只有最后一项不同的两个长度为k-1的频繁模式连接来产生的。

然后检测Ck中的每个候选模式的长度为k-1的子集是否都属于L,如果存在子集不属于Lk,根据定理2-1该模式必为非频繁的,从C中删除该模式。

对Ck中的剩余模式需要扫描数据集求得它们的支持度来决定它们是否是频繁模式。

最后的频繁集Lk必定是Ck的一个子集。

韩家炜等人设计了一种不产生候选集的 FP-Growth挖掘算法。

算法在第一遍扫描数据库时根据第一遍访问数据库得到的按降序排列频繁1-项集生成压缩存储的F-树然后由长度为1的频繁模式(初始后缀模式)开始,构造它的条件模式基(一个“子数据库”,由FP-树中与后缀模式一起出现的前缀路径集组成)。

然后构造它的条件FP-树,并递归地在该树上进行挖掘。

模式增长通过后缀模式与条件FP-树产生的频繁模式连接实现。

由于算法将频繁模式挖掘从数据库上转化到了FP-树上,将对数据集的一次次扫描变成了对FP-树的遍历及重构操作,因而大大降低了搜索开销,提高了挖掘效率,R. Karp等人提出的算法基于支持度大于给定阙值s的频繁项不超过s的事实,只使用了O(s)的存储空间通过两次扫描数据库,就能得到精确的结果5。

综合来看,提高频繁模式挖掘算法的性能主要从时间复杂度和空间复杂度来考虑Ⅰ)减少IO操作。

被挖掘的数据集通常包含大量的数据,频繁的ⅠO操作必将增加算法的运行时间。

减少IO操作主要是减少扫描数据集的次数和扫描数据集太原理工大学硕士研究生学位论文时需要访问的数据2)减少候选模式的薮量。

候选模式数量的减少可以节省处理候选模式所需的计算时间和存储空间。

24本章小结本章简要介绍了数据挖掘的基本概念和相关理论,按照挖掘的主要方法以及目的不同从分类、聚类以及关联规则等几个方面概要地描述相关技术特点,以说明不同挖掘方法的侧重点和技术思想。

重点介绍了关联规则挖掘技术的相关概念和处理流程,并通过几个代表性的算法,介绍了传统静态数据上频繁模式挖掘的实现技术,最后指岀了频繁模式挖掘提高性能的途径。

太原理工大学硕士研究生学位论文第三章数据流挖掘传统的数据库管理系统用于那些需要永久性存储数据以及对这些数据进行复杂查询的应用。

通常情况下,一个数据库包含若干无序的记录,这些记录是相对静态的,插入、更新、删除的频率大大低于对这些数据的查询频率。

当用户提交一个查询时,数据库管理系统处理这些査询,得到的结果反映了数据库当前的状态,但是数据流中记录到来的顺序是无法控制的,并且由于有限的硬盘等资源限制,无法将到来的记录存储在永久介质中,只能访问一次,这对传统的挖掘方法提岀了新的挑战:在数据不断到达的情况下,挖掘系统应该具有高速的、连续不断的处理能力,及时地反映数据的变化情况。

3.1数据流概述3.1.1数据流定义数据流是一个以一定速度连续到达的数据项序列x1,x2,…,xn…,其序列的下标是不断递增的。

数据流可以分为在线和离线两种类型52。

在线数据流的数据是随时间一个个实时更新的,如对互联冈上P分组频率的估计、股票交易动态跟踪、传感器网络监测信号,这些数据产生的速率高,却需要连续不断的跟踪并及时处理。

而离线型数据流的数据虽然不是实时的,但要么是海量数据,执行传统分析与挖掘代价过大;要么是数据增长速度过快,传统方法对新增数据的处理速度远远落后于数据増长速度,无论哪种情况都不允许用户对数据进行回溯,也只能以数据流的方式进行处理,如数据仓库和些系统的备份数据。

一般情况下所讨论的数据流通常是指在线数据流,而离线型数据流大都可以看作在相当长的时间内近似的在线数据流。

3.1.2数据流的特点数据流的数据是以高速的、连续不断的、随时间变化、不可预测和无限的方式到达并且数据量可能是无穷的,按照时间顺序,这些数据只能被读取一次。

其特点主要有1)连续性:数据流中数据是随时间不间断、连续的到达,而且可能是从多个通道太原理工大学硕士研究生学位论文同时到达;2)动态性:数据流中的数据不是静态的,而是随时间不断变化的,需要动态的进行更新并存储以备使用3)无限性:数据流中的数据是不断到来的,理论上长度是无限的或近似无限的4)未知性:数据流的数据值是不断改变的,数据的分布不是固定的而是随时间不断改变,利用预测方法也不能准确地预测下一时刻到来的数据,具有不可知性;5)不可再现性:数据流上的数据,一旦经过处理节点就不会再次出现在输入端6)高速性:数据流中的数据产生速率相对比较高7)无序性:用户不能控制数据流中数据的顺序与传统的静态数据模型相比,数据流的这些特点使得它的处理方式有许多不同,主要表现在以下几个方面1)在数据流中,处理的数据不再是从磁盘和内存中读取的数据,而是一个或儿个连续的、无穷的数据项组成的时间序列2)数据流中的数据是实时接收的,而数据库中的数据是存储在磁盘中3)由于数据流中的数据是按时间顺序产生的,不受应用系统所控制,所以一般只能对数据进行顺序访问,而磁盘中的数据可以随机访问;4)数据流中的数据是无限的,而数据库中的数据是有限的5)由于在有限的储存空间内无法存储数据流的全部数据,因此数据流中大部分的数据处理后被丢弃,除非特意保存,否则不能被再次取出处理,或者再次提取数据代价昂贵。

所以数据流上的査询多数只能得到近似的査询结果,而数据库上的査询则可以得到精确的査询结果6)对于数据流只能保存其全部薮据的一个有限子集或统计数据,并随着数据流上新数据的到来而进行更新,这种更新的频度取决于数据流数据到达的速度。

显然,数据流的更新频率要远远高于数据库中数据更新的频率。

32数据流的应用3.2.1传感器网络传感器网络被用在地理监控(地表的温度、湿度等)、公路交通状况监控、移动追太原理工大学硕士研究生学位论文踪、医疗设备监控、制造流程监控等方面。

这些应用包含复杂的过滤,要求能够及时的发现记录中不正常的模式。

同时对多个数据流处理时,要求能够进行聚集和多个数据流的连接操作。

典型的应用如当某个区域的多个传感器产生的数据同时超过给定阈值时,处理器能够激发一个触发器报告异常。

网络流量分析互联网流量实时分析系统,要求能够对多个数据源的数据进行连接操作、数据包监控、数据包过滤和检测非正常模式(网络拥挤或拒绝服务);能够支持历史査询和在线査询,例如比较现在的流量状况和对应于某种已知的事件的模式。

其他査询包括监控对流行的URL的访问情况和发现占据大量带宽的用户。

323事务日志分析事务日志分析主要用于在线网络日志分析、电话呼叫记录和ATM记录等,其主要的是发现有价值的用户行为模式、识别欺诈行为和预测未来。

如同其他类型的数据流应用一样,这类型査询包括多个数据流的连接、复杂的过滤机制和统计分析。

例如找出所有某网站中过去一小时内访问次数超过日平均访问次数40%的网页检查网络使用日志,如果主服务器负荷过量,将部分用户重定向到备份服务器3.3数据流处理技术docIn. 数据流的特点使得对其的处理必须采用一些的特殊的手段,以降低处理的复杂度现在己经有一些通过计算和统计理论来解决数据流挖掘过程中产生的问题和挑战的技术,但还没有通用的解决方案,在特定的环境会采用特定的策略。

这些处理技术主要分为两类:基于数据的处理技术和基于任务的处理技术。

在基于数据的处理技术中,主要思想是通过检测整个数据集的一个子集或者将数据变换成一个合适大小的代表性的数据集;在基于任务的处理技术中,主要采用计算理论来得到时间和空间的有效解决方案。

331基于数据的处理技术概要数据结构( Synopsis Data Structure)18太原理工大学硕士研究生学位论文通常,接收的数据流中的原始数据属于层次结构中比较底层的对象。

根据后继分析的需要,可以有选择地采用高层次的抽象对象对其分类总结,供将来的分析使用。

这种方法结合数据流按时间分段技术,可以统计每个时间段里面数据种类或某个属性及其出现次数,不必记录全部数据,从而减少了需要保存的数据元素的种类或属性,降低了内存的消耗,同时也可以减少CPU的时间消耗概要数据结构与非摘要数据结构区别有:a)概要数据结构可驻留在主存中,査询响应和数据结构更新均可避免磁盘访问b)数据能以很小的开销传播以便异地处理査询存储开销对系统存储开销影响甚微,因而留有存储空间供其它处理使用υ)概要数据能作为当前访问代价昂贵或不可能访问的数据集的代替;e)由于概要数据结构不能代表数据集的所有特性,所以当使用概要数据结枃时査询的回答一般是近似的和非精确的;常见的概要数据结构技术有直方图,小波变换,Hash和分位数等:I)直方图( Histogram)直方图是数据库研究者最早提出的一种概要数据结构,用来估计一个数据流中元组取值的频数分布,是一种简单描述总体分布的方法能直观的描述岀数据的分布情况,同时可获得统计分位数和中位数( Means)等信息3。

一般一个直方图将元组的值域分成若干个存储桶,每个桶用一个点W表示一系列的点。

最多用B个桶来表示整个值域[,n的数据,也即用O(B)存储空间代替原来需要的n个大小的存储空间。

几种重要的直方图有:等宽直方图(Equi- Width histogram)、压缩直方图( Compressed Histogram)和V优化直方图(V- Optimal Histogram)等等等宽直方图:这是最简单的一种方法,它把整个值域分成等宽长度的桶等,可以用来获得数据集合的分位数。

文献[54]提出了一种单遍扫描算法。

该算法对桶的构造过程由对桶的合并和划分操作组成。

合并过程由桶所包含的属性值的个数的下限阈值决定,属性值的个数低于下限阈值则把该桶与相邻的桶合并。

划分过程由桶所包含的属性值的个数的上限阈值决定,属性值的个数高于上限阈值则把该桶等分为两个小桶。

但是该算法并没有误差保证。

iV优化直方图:V优化直方图⑤的目标是使得各桶的方差之和最小。

设19太原理工大学硕士研究生学位论文个数据流可以用一个长度为d的数组A[0,…,d-1表示。

A(i)表示A[引所在桶的值,则其要求∑(4-(4G)2最小2)小波变换这是一种通用的数字信号处理技术。

类似于傅立叶变换,小波变换把输入的信号变换成一系列的小波参数,少数几个最大的小波参数拥有原来信号所含的大部分能量。

根据这个特性,只需保留最大的几个小波系数,从而减少内存使用和计算的开销。

在査询时,通过系数反演变换提供对数据流查询的近似回答。

小波变换计算速度快,可用于计算无限数据流的近似值组合。

另外小波变换可以提高随机采样和直方图的效率3)Hash定义一组哈希函数,将数据从一个较大范围映射到另一个较小范围中去是计算机领域的一个常用手段。

常用的利用哈希函数生成概要数据结构的方法是 bloom filters,梗概( Sketch)等。

Bloom filter:原始的 Bloom filter是一种用来快速判定一个元素是否属于个集合的数据结构,其最大特点是仅使用一小块远小于数据集数据范围的内存空间表示数据集,并且各个数据仍然能够被区分开米。

Bloom filter是个M大小的数组,地址从0到M1,初始值为0。

对Y中的每个元素y用d个独立的hash函数,将y映射到地址y,y2,…,y(0≤y≤Ml,1≤i≤d将这些地址的值设为1。

对于X中的每个元素x,我们也用如上的d个hash函数得到d个hash值,以这d个hash值为地址检查数组中相对应的d个值是否为1,如果存在某个地址值为0,那么我们可以断定xY,如果全部为1,我们将以非常接近1的概率判断x∈Y。

ⅱ i Sketch:即对到达的数据项在一组随机向量上做映射(该过程也可称为哈希),这些映射出来的值被称为梗概。

为了降低误差,Alon等5利用多组相互独立的投影(或哈希函数),对所有估计值取中值作为最终估计值,从而在理论上保证估计值误差不超过用户预先定义的允许误差。

随机向量通过对随机变量进行某种空间节省的计算来产生。

它的主要缺点是精度比较抽样( Sampling)抽样是一种采用统计方法来选择一部分输入数据作为分析数据。

这主要是由于数据流的数据到达速率超过了系统的处理能力。

对数据流进行抽样是指以一定的概率决定是20太原理工大学硕士研究生学位论文否处理当前到达的数据项,抽样算法的误差上界通常为抽样频率的函数。

根据各数据项被选中进行处理的概率是否相同,抽样可以分为均匀抽样( Uniform Sampling)和偏倚抽样( Biased Sampling)。

均匀抽样对于每个元素的入选几率是一样的,如水库抽样( Reservoir Sampling)和精确抽样( Concise Sampling)。

偏倚抽样则相反,各数据项被选中的概率各不相同,例如计数抽样( Counting Sampling)1。

抽样大小往往确定了算法的错误极限。

使用采样技术来进行数据流分析的一个问题是数据集的大小是未知的,因此数据流的处理必须遵循特殊的分析才能够得到错误的范围。

此外,采样技术不能解决数据分布变化的情况,而且在对数据流进行不规则或者监督分析时,使用采样技术将会出现问题。

采样技术中数据速率、采样率和错误范围三个参数之间关系是需要重点关注的地方。

聚合( Aggregation)聚合是用一些统计方法对数据集进行统计,例如利用中位数和方差来总结到来的数据流。

挖掘算法通过使用这些聚集的数据来进行挖掘。

聚合所产生的一个问题是,它不能很好的反映数据的分布或者变化特征。

一些算法已经对合并在线的聚集进行离线挖掘进行了研究,如文献[59]●降载( Load Shedding)由于数据流中数据特征可能随时变化而且数据也可能岀现爆发性的井喷,因此要求数据流挖掘算法具有良好适应性。

例如,在某些外部条件下,数据流速率可能会急剧增长,超出数据流系统的负载能力,系统产生过载而导致性能下降,从而不能实时处理所有数据。

这时,如果仍旧按照原方法进行处理,查询延迟可能很大,在某些场合,这是不被允许的。

为了解决这一问题,就需要使用降载技术,暂时放弃当前的一些数据,直到上—批数据处理完。

降载技术是丢弃数据流中的一系列数据的处理过程,系统仅仅处理部分输入数据,舍弃其氽部分,从而保证能够实时输岀数据。

当然,在这种情况下,只能够得到近似答案,査询质量将会降低。

降载技术丢弃了一些将来可能用于构建模型或者是代表一个感兴趣的模式的数据。

因此,它很难被应用到数据流挖掘中。

3.32基于任务的处理技术基于任务的处理技术是指对现有方法进行修改或者发明一种新的方法,以满足处理数据流的需要。

近似算法( Approximation Algorithm)、算法输出粒度( Algorithm OutφputGranularity,简称AOG)和窗口技术都属于这类方法21太原理工大学硕士研究生学位论文●近似算法近似算法源于算法设计,是算法研究领域的一个重要分支。

它用于解决复杂的计算问题,能够保证在一定的错误范围内给岀近似的答案。

由于数据流的连续性和无限性,使得计算数据流査询的一个精确答案所需的存储空间和时间可能会无限增长。

这在现实中是不可行的,我们只能用有限的空间来计算査询值。

在计算和存储资源相对受限的情况下,近似算法是研究者常用的解决方法之一。

用近似值来代替精确值可以使处理的复杂度和时空代价都大为降低。

只要这些近似的答案有确定的误差界限,或者是算法计算出来的近似答案与精确答案之间误差很小,那么这种方法就是可以被接受的。

由于数据流产生速率高、只能单遍扫描,因此以往的近似算法并不能直接用于数据流挖掘,必须根据数据流挖掘的特点进行改进。

如 Manku等人在文献[20]提出的 Lossy Counting算法,该算法虽具有相对较大的空间复杂度,但在实验中往往比那些空间复杂度较低的方法具有更好的性能●AOGAOG技术能在一定的时间范围内利用有限的内存和处理速度来处理波动的高速数据。

AOG在有限资源的机器上接收数据流进行数据分析,主要有三个阶段。

前两个阶段是根据资源和数据流的速率进行调整,最后一个阶段是当内存溢出时合并产生的知识结构。

文献[23,60都采用了该方法。

窗口技术窗口技术是基于用户对最近产生的数据更感兴趣而产生的。

它详细分析了最近的数据项集并且总结了以前的数据项集。

在窗口技术下,数据流的查询分析是对窗口内的数据进行操作,也就是仅对最近流入的数据进行计算,而不是对全部已流过的数据的进行计算。

这是很自然的一种方法,因为现实中新的数据一般比旧的数据更重要,更有价值窗口的类型可以有很多种,比较常见的有以下几种:1)滑动窗口其大小是固定的,大小可以根据时间或其中的元组数目来定,然后通过向下滑动元组来移动窗口。

这种窗口用于执行滚动计算,如计算最近时的股票平均价格;2)固定窗口顾名思义其大小也是固定的。

它与滑动窗口不同的是在向下移动窗口时是整个窗口的移动,相邻的窗口间没有公共元组。

这种窗口把数据流分为些不相交的元组集,可用于计算每日股票价格等22太原理工大学硕士研究生学位论文3)标记窗口使用时需要对数据流进行标记,当前的标记窗口就是从当前点向后到最近的那个标记点,比如计算今天到目前为止的股票平均价格,那么每天零点整就给数据流加一个标记;4)无限窗口其在数据流生命周期内一直存在,相当于没有窗口,对窗口内数据进行计算时一直维持其内部状态34数据流挖掘算法34.1数据流挖掘算法的特点通过上述对比易知,和传统数据模型相比,数据流具有截然不同的特性,这决定了我们不能将传统的数据挖掘算法简单的移植到数据流上,必须针对数据流的特点,进行相应的调整满足数据流处理的需要。

典型的数据流处理模式如图3-1K用户查询A1o缓存K数据流挖掘处理器近似结果数据流内存中的概Www.do要数据图3-1数据流处理模型omigure 3-1 Processing Model of Data Stream归纳起来,数据流挖掘算法通常需要满足以下几点要求:1)一次扫描:算法只能对数据扫描一次,这不仅是因为数据流具有不可再现性,更是由数据流高速、无限、动态、连续等特性所决定的。

它在处理的过程中既没有足够的空间存储历史数据,更没有时间访问历史数据,因此也就不可能像传统频繁项集挖掘那样多次扫描数据数据来进行计算2)实时性:这主要体现在三个方面,第一,数据是实时处理的,即算法的处理速度不应该低于数据产生的速度;第二,算法应该能够实时响应用户的查询请求,能够在处理的任何阶段输岀可用的结果,而不是等到处理完所有的数据才输出结果,因为数据流可能是无穷的;第三,由于数据流是动态的,算法应该能够及时反应出数据流的变化23太原理工大学硕士研究生学位论文3)低空间复杂度:数据流从理论上是无限、高速的,在处理过程中会产生海量的数据。

为保证算法持续稳定运行,算法的空间复杂度要非常小,一般要求在o(pohv(log八)以内(N表示当前时刻数据流的事务数),才能保证数据流算法的空间占用量的增长速度就远远小于数据流自身规模的增长速度。

因此相关算法通常都有一个有效的压缩的数据结构来存储更新和检索收集的必要信息,如FP树,前缀树等4)适应性:在很多情况下,数据流的变化很大。

这个变化不仅可以是数据产生速率的变化,还可以是数据分布的变化。

算法应该能够根据数据流的变化而及时进行相应的调整,以满是性能上的要求)准确性:由于限定了内存空间上限,目前很多数据流挖掘的结果通常都是近似的,但是也需要满足一定的误差要求,否则挖掘的结果便没有使用的价值了。

为了满足高质量的近似回答的要求,数据流挖掘通常都会采取一些约减技术数据流挖掘算法硏究主要集中在分类算法、聚类算法和频繁模式挖掘算法三个方面,下面简要介绍一下分类算法和聚类算法,频繁模式挖掘算法将在下一章详细介绍34.2数据流分类算法P Domingos等人提出的ⅤFDT算法是一个决策树学习系统,将传统的决策树应用部球分料并具了计两的个界。

Hoeffding约東用来解决在进行分支的时候究竟应选取多少样本来得到测试属性的问题,保证高精度地处理高速数据流。

Hoeffding约束即:对于可信度1-δ,随机变量r的真实值至少是r-E,其中EAR2n(8),R是r的取值范围,n为样本数,r是样本平均值。

算法采用信息增益作为属性选择规则,对属性熵的计算做了一定优化,并保证在一定概率下分类规则的有效性,既可连续处理数据,也可通过二次抽样,重新扫描数据集,因此可以处理非常庞大的数据集。

具体做法是:VFDT将无价值的叶子节点及时删除,但保留部分信息,每隔一段固定的时间将扫描所有活跃的和不活跃的(已删除的)叶子,若发现上述情况,则做叶子的替换,一旦某个属性表现较差,系统也会及时释放其相应的存储空间;另外,如果数据流的到达速度不是很快,系统还可以二次扫描数据。

24太原理工大学硕士研究生学位论文VFDT的另一个特点是增量式学习及随时可用性,它是一个实时算法,在学习了最初的些样本之后,就提供了一个随时可用、不断优化的决策树VFDT和其它大多数机器学习方法一样,假设数据是从静态分布中随机获取的,不能反映数据随时间变化的趋势。

因此,P: Domingos和 G Hulten引入了滑动窗口技术,对ⅤFDT算法进行了改进,提出了 CVFDT算法,除了保留ⅤFDT算法在速度和精度方面的优点外,增加了对数据产生过程中变化趋势的检测和响应,使得算法更好地适应对高速时变数据流的分类。

CⅤFDT利用样本窗口来有效维护决策树的更新和模式的一致性,然而它并不需要在每个新样本到来的时候都学习新的模式,而是通过增加相应新样本的总数来更新充分统计量,相应地减少滑动窗口中旧的节点数量。

如果基本概念是静态的,将不会产生影响;然而,如果概念是动态变化的,因为一个可替换的属性有更高的增益,使得某些先前通过 Hoeffding测试的分支不再起作用。

在这种情况下,CⅤFDT开始在根节点用新的更好属性生成一棵用于替换的子树,当这棵替换的子树在新的薮据上比旧的子树更精确时,就用新的子树代替旧的子树。

由于算法在保持当前决策树的同时生成可选子树,必要时用子树替代当前决策树,大大提高了效率,且保证了准确度多数的分类方法基于数据来自一个静态的分布的假设,现实中的数据来自很长的时间范围,忽视潜在的概念的变化,很可能导致分类模型的性能下降。

Ha- Xun wang等(2针对传统的数据流分类算法是对数据流上的所有数据增量维护一个决策树模型、不能解决概念漂移( Concept Drifting)的问题,提出了个带有权重的多分类器算法,对单分类器进行了改进。

根据分类器对数据适应情况的变化,即根据每个分类器在新到来实例上的错误率来动态调整各个分类器的权重,这种带有权重的多分类器的分类算法能够解决概念漂移问题。

最后,算法通过使用基于实例的修剪方法防止分类器对最近的数据过分适应。

该算法用聚类后的结果做分类,采用统计的方法分析类在各个聚类中的分布3.4.3数据流聚类算法数据流聚类是对元素集进行分组,使得组内元素尽量相似,组间元素尽量相异。

不同于静态数据挖掘,由于无法完整地存储历史数据,算法只能由新数据来追踪聚类变化,这就要求算法必须是增量式的,对聚类表示要简洁,对新数据的处理要快,对噪音和异常数据要稳。

此外由于数据流可以看成是随时间不断变化的无限过程,其隐含的聚类可25太原理工大学硕士研究生学位论文能随时间动态地变化而导致聚类质量降低,这又要求聚类结果能够不断调整,算法要有很好的可扩展性。

最早进行相关讨论的是文献[12,13],算法将数据流分批处理,对每一批数据,算法将其聚为几个具有代表性的点,当数据流到达一定量时,算法进一步将已知的代表点聚类到更高的一层。

每一层点的个数与该层中每个点的下一层点的个数相等,由此达到对数据的“分而治之”。

当需要输出聚类结果时,将已有的代表点聚为所需的若干个类。

o'Callaghan的 STREAM算法3聚焦于解决k中心点问题,即把度量空间中的n个数据点聚类成k个簇,使得数据点与其簇之间的误差平方和最小。

STREAM算法把每个桶的数据点分成k个簇,并且仅仅保留k个簇中心点(而丢弃其余的数据)来汇总桶中的所有数据。

每个中心点的权为该簇中数据点的个数。

随着数据流的流入,这个过程不断地被重复,每次处理的数据个数为m。

此外, STREAM算法使用 LSEARCH算法改进了k-平均算法,使“k”更灵活:在算法的中间步骤中,簇的个数不再是一个固定的值,而是一个更合理的值,仅仅在算法结束时趋向于k。

STREAM算法实现了单次扫描,时间复杂度为O(kmn)。

与传统数据的聚类算法相比, STREAM算法有更好的性能,并能产生更高质量的聚类结果。

但是, STREAM算法没有考虑数据流的演变,即算法没有给予最近的数据较大的权重。

这样,聚类的结果可能受控于过期的数据点。

此外,STREAM算法更趋近与一个批处理的过程,无法给出一个随意时间的回应,即算法无法在任意时刻给出当前数据流的聚类结果以上算法都属于划分方法, Aggarwal提出的 CluStream则是一种层次方法,它其实是一个数据流的聚类框架。

Clustream算法解决了 STREAM算法1存在的两个问题。

它是增量式( Incremental)的聚类算法,在每个数据项到来时进行处理,能给出任意时刻的回应;并且它使用一种渐进对数倾斜时间框架模型( Pyramidal Time frame),能给出不同时间粒度的聚类结果。

数据快照按照不同的时间粒度被存储在不同的时间粒度层上,距离当前越近的时间戳,快照存储的密度就越高。

这对于希望分别考察诸如上周上月以及去年的聚类分析结果的用户意义重大。

CluStream算法的开创性贡献是提出了将聚类分析的过程分为联机和脱机两个部分的处理框架。

联机部分使用微簇( Microcluster)计算和存储数据流的汇总统计信息,实现增量的联机聚类査询;脱机部分则进行宏聚类( Mcroclustering),利用渐进对数倾斜时间框架提供用户感兴趣的不同时间粒度上的聚类结果。

这个两阶段处理框架被许许多多后来的数据流聚类算法所效仿26太原理工大学硕士研究生学位论文和采纳。

随后^ agarwal等针对高维数据流,改进了 Clustream算法,提出了 HPStream算法1,通过引入投影技术( Project Clustering)和衰减簇结构( Fading Cluster Structure来更好地支持高维数据流的聚类分析35本章小结木章首先介绍了数据流的特点和相关应用领域,然后根据数据流的特点和相关技术要求,描述了对其进行数据挖掘时常见的技术手段,并对比静态数据挖掘领域,结合具体的典型算法,分析了数据流上分类和聚类算法的技术特征。

太原理工大学硕士研究生学位论文第四章数据流频繁模式挖掘研究4.1数据流频繁模式概念定义4-1数据流频繁模式是指对于给定全集上{x,x2,…,xm},如果在数据流DS={T1,T2,…,T,…}中,数据项集P={x1,x2,…,x}出现的频率f(P)超过一定阈值(s-ω)M,则称该数据项集为频繁模式,记为FP。

其中N表示数据流中当前考査范围内事务的总数,k表示频繁模式的长度,s∈(O,1)是给定支持度,ε是给定的误差度,且有0≤ε<
当k-1时,频繁模式就成为频繁项事务T={t,x1,x2,…,xn},这里x∈I,1≤ism,n表示事务的长度,ta是事务的唯一标示定义4-2数据流中,数据项集P如果有fP≥M,则称P为Ds中临界的频繁模式;如果八P)εM,则称P为DS中的非频繁模式4,2频繁模式挖掘相关问题m数据流频繁项挖掘算法除了和其他算法一样需要满足一遍扫描数据、低空间复杂度以及良好的适应性要求以外,还要注意以下问题1)概念漂移6概念漂移是指由于数据流的动态性,数据分布不受系统控制的随时间改变,从而导致频繁模式和非频繁模式之间相互转化的现象。

因此在频繁项挖掘过程中,如果只是简单的将非频繁项舍弃,当其由于数据流的变化而转变为频繁项时,算法就会因缺失相关信息而捕捉不到该变化或者因丢弃的信息导致结果不准确;同样,对于频繁模式如果没有相关措施在其变成非频繁的时候进行相关处理,也会影响挖掘的结果2)假正假负由于数据流挖掘结果通常都是近似的,对于频繁模式挖掘,其结果集就会出现两种情况:一种是为了保证完整性,所有的频繁模式都被发现,部分非频繁模式也被误认为是频繁的而出现在结果集中,即假正;另一种是为了保证准确性,非频繁的都不会出现在结果集中,从而导致结果集中会缺失部分事实上频繁的模式,即假负28太原理工大学硕士研究生学位论文3)项集计算在进行数据流中频繁项集挖掘时,如何计算需要进行统计的项集是需要考虑的重要问题之一。

数据流中的数据量巨大,不能对数据流中的事务列举其子集进行统计。

首先,事务的子集可能很大。

一个长度为10的事务的子集有210个子集;其次,事务子集的计算操作比较复杂和消耗资源。

此外,现实中也没有必要对事务的所有子集都进行统计。

现在就有一些算法只针对最大频繁项集4和闭合项集2·6进行挖掘,从而有效的减少了项集的有关计算4.3数据流频繁项挖掘算法数据流频繁模式挖掘的任务就是在有限的存储空间下,通过近似算法对模式的频率进行估计,并尽可能减少误差,从而获得满足最小攴持度要求的频繁模式。

数据流频繁模式挖掘硏究最初是从频繁1-项集即频繁项挖掘开始的,大多采取的是近似算法。

设0<ε<
在任意时刻,用户发出频繁项査询,如果算法保证其输出结果满足:l)所有真实频率超过sN的数据项均被输出2)所有真实频率低于(s-e)N数据项均不输出3)算法估计的频率值与真实频率的误差小于εN;则称算法输出结果满足ε-近似要求;如果算法以概率1保证结果满足ε-近似要求,则称该算法为确定( Deterministic)的ε-近似算法;如果算法以概率1-6*保证查询结果满足e近似的要求(0<6<1),则称该算法为(,5随机( Randomized)近似算法。

现有的技术基本分为两类:l)第一种是 Sketch- based Technique。

每个数据项都有一族计数器与之相对应,每个计数器又可能被多个数据项所共享。

当新数据项到来时,其对应一族计数器都要执行更新操作。

为降低Hash冲突对频率估计值得影响,提高准确度,一般要在这一族记数器选择最合适的值最为最终的估计值,典型的算法有以下几种Charikar等人提出的 Count sketch2算法用于解决 FindApproxTop(S,k,)问题,即査找数据流S中前κ个频繁项。

算法以1-δ的概率输出k个频率至少是数据流中第k个频繁项(1-ε)倍的数据项,算法的空间复杂度会随着数据分布的倾斜度的增加而减少。

如果只希望得到出现次数超过n(k+1)的数据项,需要的存储空间为OE2logNδ)。

29太原理工大学硕士研究生学位论文Cormode等人的 Group:算法6同样以1-6的概率输出频率超过1(k+1)的数据项,但是空间复杂度降为OK(logk+log1/δ)logM。

其基本思想来源于在若干正常硬币中找岀一枚超重硬币的问题。

数据流中大量非频繁项相当于正常的硬币, Group Test算法将数据流分成2 klogk/δ个分组,每组找出一个频繁项,通过比较所有分组就可以得到所求的频繁项。

由于任意两个数据项在同一个分组的概率小于1/2k,算法将每个数据项散列logkδ次来降低由于将两个频繁项分在一组而导致的遗漏,但并不能保证不发生这种情况,而且如果恰好分组中有一些数据项的频率超过阈值也会导致正确的频繁项被“屏蔽”。

算法能够得到的是数据流中的p-k频繁项,结果虽然比较准确,但是不能提供数据项的频率信息和次序Jin等人提出的 hCount算法6使用k个相互独立的hash函数,每个hash函数均将数据流的值域[0,M-1]映射到一个二维哈希表中,降低数据项存储的空间开销,并通过引入不可能在数据流中出现的数据项来提高准确性。

算法使用O(Elog(- Mllogd)的空间以1-6的概率保证查询结果误差在e之内Sketch- basedτ echnicμues需要监控所有的数据项,受数据项在数据流中的顺序干扰小,大多数需要知道数据项的取值范围,对每个数据项或查询时都需要计算一系列的计数器,对数据项取值范围不确定或范围较广的情况具有一定的局限性,而且对数据项频率估计值也不能提供误差保证,频繁项的查询结果也只能是以1-6的概率予以给出2)第二种是 Counter- based Technique。

这些方法都需要维持若干个计数器,每个计数器对应一个数据项。

当数据项出现时其相应的计数其计数增加,在某些特定的情况下,计数器计数会减少或者重新分配给其他数据项Manku和 Motwan提出了一种确定的e近似算法 Lossy Counting20。

算法采用批处理的方式,把数据流逻辑上等分成若干个数据块,数据块的编号从1开始,每块包含1/ε个数据项。

对于每个新到的数据项如果在一个类似栅格的概要数据结构DD的大小为l)中则其计数器加1,否则估计出该数据项的计数上限加入到D中。

当一个数据块数据处理完时扫描D,删除其中所有估计频率小于当前处理的数据块编号数的数据项。

算法的空间复杂度最多为O(l/elogεN。

同时他们还提出了一种 Sticky Sampling算法,该算法在O( 1/Clogs S)的空间内以1-6的概率太原理工大学硕士研究生学位论文满足査询结果ε-近似的要求Metal等人提出的 Space- saving算法设计了一种双向链表作为计数器,将具有相同频数的数据项通过hash表或者链表放入同一个计数器中,在每一个数据项加入链表时为其记录一个最大误差估计值。

该算法能够同时处理数据流频繁项査询和Tp-k査询,具有一定的通用性。

同时文献证明了对于采用Counter- based技术的确定的ε-近似算法,其需要的计数器个数 Count应该满足以下条件:minM,12a)≤ Count smin(M,1),M为数据项的取值个数王伟平等人提出的EC( Efficient Count)算法,空间复杂度仍为O(ε),但是将数据项的估计频率和真实频率之间的误差降为e(1-s+e)N,每个数据项的处理时间复杂度为O(1)。

表4-1数据流频繁项挖掘算法(R= Randomized d= Deterministic)able 4-1 Algorithms of Mining Frequent Items in Data Stream(R=Randomized DDeterministicAlgorithmType Time Per ItemSpaceReferenceLossy CountiDO(logan)O(E logen)Count sketchRO(kle log n)O(/E logn)ECO(l/)Group TestRO(logk)O(kdlogh+log1/d)logM)RO(log(-M/logo))D(a log(-Mnlogo))Space SavingDO(logk)O(Min(M, 1/e)般来讲, Counter- based Techniques县有较快的单位元素处理效率和确定的误差上限,而且由于算法只保存部分数据项信息,其空间复杂度一般较低,但是查询的误差精度较低。

表4-1列出了各算法的时空特性。

4.4数据流频繁模式挖掘算法频繁项挖掘算法相对灵活简单,但由于其特殊性,无法直接扩展到仼意长度频繁模式的挖掘,而且频繁项也无法产生关联规则,应用范围较窄。

因此随后人们又提出了系列频繁模式挖掘算法。

在进行挖掘算法设计时,首先要考虑的问题是要对薮据流中哪些数据进行哪些挖掘,即数据处理模型。

数据处理模型便是对数据流中数据进行处理挖掘的模型。

当前的数据流挖掘算法中主要存在三中数据模型:界标模型( LandmarkModel)、衰减模型( Damped Model)和滑动窗口模型( Sliding Windows Model,简称31太原理工大学硕士研究生学位论文SW)。

4.4.1界标模型界标模型算法发现的是从特定的标记点开始直到当前时刻为止所有数据中的频繁模式,这个标记点就被称为界标( Landmark),如文献[20,71,72]。

但是,这一模型中新旧数据具有相同权值,不适合于人们只对数据流中最近信息感兴趣的应用。

刘学军等2借鉴FP- growth算法提出的FPDS算法采用批处理的方式对数据流分段处理,任意一段N所包含事务的数量相同,且有N=「1/E或1/61的整数倍。

fit是个集合用于保存扫描N段数据后,数据流的中全局临界频繁项,并按数据项的计数降序排列,其初始为空。

在处理过程中,用FP-DS树保存有关信息如图4-1所示,FP-DS树由树根(记做nu)、临界频繁项集构成的前缀子树和临界频繁项头表组成。

除根结点之外的每一个结点由7个域组成( data,f, reval, pnode,par,leftchild, rightchila),dama为该结点代表的数据项,∫表示包含从根结点(不含根结点)开始到该结点所构成的项集计数, reval是重构FP-DS树时为避免项集的重复插入而设的一个计数值,Pde为指向具有相同数据项的下一个结点的指针,pa是指向父结点的指针,le∫ child是指向第一个孩子结点的指针, rightchild是指向兄弟结点的指针;头表中的每个元组由两部分组成:数据项和指向树中相同数据项的第一个结点的指针。

FDS树类似FPre,.它的每个结点与FPte相比多了一个revl域,在生成FPDs树时,每个结点的 reval值等于∫的值;临界频繁项头表中数据项的排列顺序与 f-list中相同算法的具体过程如下:1)生成N段的初始FPDS树,包括头表和一个根结点,头表根据M段的ft生2)if(讠>1)then调用 Insertconstruct函数;俫*将第i-l段的FP-DS树保存的临界频繁项集插入到第i段的FPDS树中*删除第i1段的FPDS树;}5)然后以ε为支持度,调用改进的FP- growth算法生成N段的临界频繁闭合模式并且将每个模式中的数据都按 f-list中的顺序排列,然后将出现在 f-list中的数据太原理工大学硕士研究生学位论文项插入N的FPDS树;其中 Insertconstruct函数描述如下l)按M1段FPDS树头表的逆序取项目e;2)for each ei3)取得FP-DS树中的e模式集,分别为et,ea,erfor each ei fif(eir. reval0) then if(e∈N段fist)the按M段的fist排序c模式中的数据项,去除不包含在fit中的数据项,插入到M段的FPDS树中b8818,18丁>8,18图4-1FP-DS树结构Figure 4-1 FP-DS Tree Structure任意时刻只需根据FPDS树就可得到频繁模式,即FPDS树中项集的频繁次数大于sN的就是所査询的频繁模式。

算法由于对频繁1-项集进行了裁剪,降低了空间复杂度,适合长频繁模式的挖掘。

44.2衰减模型衰减模型给每个频繁模式赋予一个权值,最新的频繁模式拥有更高的权值,该权值会随着时间的推移逐渐衰减,即新出现的项集对该项集的频度影响大于原来的项集,以此来突出人们对最近获得信息的兴趣度,如图4-2,其中的数值表示该阶段出现的频繁太原理工大学硕士研究生学位论文项集的对结果的影响因子。

这种模型考虑对新的和旧的数据赋予不同的权重,适合于旧的数据对挖掘结果产生影响但是会随着时间减弱的应用,如文献[22,23,25]。

Data streamCurrent l0.10.160.240.340.450.71Current 20.10.160.240.340450.451Current 3010.160.240.340450.71System Start图42衰减模型Figure 4-2 Damped ModelGiannella根据 FP-Growth提出的 FP-stream算法1是这一类中具有代表性的,它能够挖掘多种时间粒度的频繁项集。

算法首先引入了倾斜时间窗( Tilted- time window)的概念,根据现实中人们对旧知识兴趣度较低、对新知识兴趣度高的假设,以不同粒度压缩存储历史数据,这样既保留了历史细节,又节省了空间。

图4-3给出了一个倾斜时间窗的例子,例子中最近的时间粒度为“刻”,稍大的是“小时”,最大的时间粒度为“天这里采用的是自然时间窗:当累计4“刻钟”之后,就压缩存储为1“小时”,累计24“小时”之后,则成为1“天”。

人们可以査询最近一个小时里每刻钟内有哪些频繁模式,以及模式的频繁计数。

如果查询最近一天里的频繁模式,则回答粒度只能是小时以此类推。

而实际算法中使用的是对数的倾斜粒度,在此不加以详细讨论31天24小时4刻图43倾斜时间窗Figure 4-3 Tilted-time window该算法通过在内存中构建一个频繁模式树来保存数据流的相关信息并进行频繁模式的挖掘。

频繁模式树代表频繁模式的集合,树中的每一个结点代表一个模式(从根到这个结点)。

如图44所示,这棵树和 FP-tree有着相似的结构同时由于通常频繁模式不会随着时间有大幅度的改变,不同时间范围内频繁模式树重叠较大。

如果把时间倾斜的窗口嵌入到锊一个结点就能够节省很大空间。

因此,算法将时间倾斜的窗口嵌入到频繁模式树的每个节点并维护这个时间倾斜的窗口。

图4-5给出了一个频繁模式树中嵌入时间倾斜窗口的例子。

太原理工大学硕士研究生学位论文只要模式是频繁或临界频繁的就被加入频繁模式集。

随着数据流的到达,模式的计数逐渐压缩到更粗的粒度存储,原来频繁或临界频繁的模式逐渐成为某粒度下的不频繁模式,此时算法将其不频繁的窗口段剪掉。

如果某个模式倾斜窗口内计数为O,则该模式将被删除Frattern○b:92C:80b:7863Frequent patternPattern Tree图44频繁模式树Figure 4-4 Pattern Treedogtilt window support丁t9WWVlaem livocin-图45嵌入倾斜时间窗的频繁模式树Figure 4-5 Pattern Tree with Tilted-Time Windows Embedded另外,文献[22]中的 estEe方法是在 Lossy Counting的基础上采用启发式的方法来获得最近的频繁模式。

为了保证结果的准确性,算法对所有的频繁1-项集都以其真实频率保存在一个集合ML( Monitoring lattice,监控栅格)中,而且一旦保存就不再删除。

对于新接收事务中的模式,如果已经在ML存在,则更新其相关频率,否则就以当前改模式的最大可能频率作为其估计频率加入ML,同时根据一个频繁模式的频率最大不超过其子模式频率最小值的原理,在对该模式的估计频率加以修正。

算法还采用延迟插入和剪裁技术提高挖掘性能。

太原理工大学硕士研究生学位论文44.3滑动窗口模型滑动窗口模型只在当前滑动窗内挖掘和维护频繁模式,超岀窗口范围的信息将不被关注。

因此在金融和股票交易中,使用滑动窗口模型更为合适个滑动窗口对应的是一组连续的单位窗口( Unit window,简称UW)序列{UW,UW2,…,UW},k是滑动窗口所包含的单位窗口的个数,表示窗口的长度。

随着新数据的到来,滑动窗口以单位窗口为基础不断更新。

每接收一个或几个新单位窗口的数据相应的就要从滑动窗口中删除相同数量的历史最久的单位窗口,即最早接收的那些单位窗口数据,这样滑动窗口就完成一次滑动更新操作。

其处理过程一般分为三个阶段:窗口初始化:该过程从系统开始一直持续到系统接收的数据流事务等于用户预定义窗口长度为止的。

由于过程只接收数据而不需要删除过期数据,其处理过程相对简单:窗口滑动:当滑动窗口接收的数据达到用户规定的窗口长度时就进入窗口滑动时期。

在这一阶段首先要将新接收的UW中的频繁模式信息加以保存,同时还要将滑动窗口中过期的UW数据清理掉,从而实现窗口的滑动。

这两个操作的顺序可以根据需要在算法中自行决定,但是新添加进滑动窗口的UW数量和删除的UW数量应该相等,一般是一个UW。

这个过程是滑动窗口模型设计的关键,直接影响算法的效率频繁模式生成:木阶段主要是针对用户的查询请求对滑动窗口内的数据进行挖掘处理得到满足要求的频繁模式集。

Data Stream图4-6滑动窗口模型Figure 4-6 Sliding Windows Model该处理模型如图4-6所示:从系统开始到S兩1是窗口初始化阶段,而SW2、SW3则是窗口进行第一次和第二次滑动以后的状态。

窗口的大小一般应根据应用需求和系统资源太原理工大学硕士研究生学位论文来确定,已有的算法有[24,73-77]文献[73]中的滑动窗口是由若干个长度相等的时间段组成的,即一个时间段就是个UW。

每个滑动窗口被分为w个时间段,每次窗口滑动时只移动一个时间段。

算法在内存维护一个前缀树来保存获得数据流频繁模式信息,每个节点包含以下三个信息:数据项值、数据项被加入前缀树的时间段编号、数据项的支持度。

对每个吋间段内的数据采用FP- Growth算法挖掘其中的频繁模式,挖掘岀来的频繁模式如果不存在于前缀树中则将其添加入前缀树中;如果存在,则增加其支持度,如果新的支持度小于阈值,则从前缀树中删除该模式。

考虑到一个模式在前缀树中存在的时间越久,它的支持度就应该越高,因此频繁模式被加入前缀树的基本时间单元不同,其阈值也不同,具体计算公式如下mIn sup(k)=「mxn1其中m=sNk,rk=(-)(k-1)+r。

k是数据项被加入前缀树的基本时间单元编号,最新的为1,最久的为w;s是用户定义的最小支持度;|M是从第k时间单元到现在为止的事务总数;0≤≤1,是系统自定义的参数表示与s的相关率。

由于算法对频繁模式被加入前缀树之前的攴持度信息并不保存,即假设该值为0,因此这就使得算法挖掘的频繁模式支持度小于等于其真实值,这可能使一些事实上频繁的项集没有岀现在最后的结果中,所以这种算法存在假负的情况文献[74将滑动窗口也分为若干个相等的时间块,同时为了保证窗口正确滑动,算法需要记录每个频繁模式在每个基本时间块中出现的次数,以及每个吋间块中的事务总数。

对每个时间块则采用FP- Growth算法挖掘其中的频繁模式,并且无论其是否在整个窗口中频繁都要进行保存。

如果已经保存有该模式信息,则只需更新其计数即可,否则还要计算该模式之前最大可能出现的次数并予以保存。

该值与之后记录的确切值之和就是其频率估计值。

当内存有限时,文献还提供了一种调节机制,通过合并相邻时间块中频繁模式信息来降低内存的使用444处理模型的关系目前这三种处理模式在数据流频繁挖掘硏究中都有应用,但是具体使用哪种模式主要是根据实际应用的需要,考察系统关注的数据主要是在哪个时间范围再进行确定。

但是一般来说界标模型是最基本的模型,在其上加入时间衰退函数就能使其转变为衰减模太原理工大学硕士研究生学位论文型;在其上増加一个限定挖掘范围的滑动窗口就可以将其转化滑动窗口模型4.5本章小结本章主要介绍了数据流频繁模式挖掘的相关理论和技术要求,然后分别从频繁项挖掘和频繁模式挖掘两个方面介绍己冇的数据流挖掘算法。

对频繁模式挖掘,按照处理模式的不同,介绍了界标模型、衰减模型和滑动窗口模型的算法特点,并选取几个代表性算法描述了不同模型的基本思路,最后对不同模型的关系进行了总结38太原理工大学硕士研究生学位论文第五章滑动窗口下频繁模式挖掘滑动窗口模型只关注最近一个时期内的数据,更符合人们的实际需要因此受到了更多的关注与研究。

本章采用一种比特序列作为滑动窗口,简化了窗口操作,提高了事务处理能力,适合高速数据流的挖掘。

5.1问题提出在数据流应用的很多场合,人们往往只关注最近获得的信息,或者希望根据获得的信息对未来发展做出预测,如网络监控、无线传感器网络、web点击流等,在这种情况下,人们并不需要知道历史非常久远的信息,这些信息对系统没有实际意义,也没有保存的价值。

这时如果采用界标模型或者衰减模型,不但増加了系统的负担而且还会影响算法及时对数据流的变化做出响应。

同时,人们在进行数据流挖掘时,接收到的原始数据往往包含了多方面的信息,但是在实际生活中,不同部门或领域的人们一般只对其中的部分信息感兴趣。

因此如果照搬现有算法,对所有的数据不加区别都进行处理,不但增加数据处理量,降低了数据处理效率,浪费了系统资源,而且挖掘的结果也可能和用户的需求相差甚远。

52比特序列滑动窗口52.1时间型滑动窗口与事务型滑动窗口时间型滑动窗口( Time-sensitive Sliding window)是指在滑动窗口范围内每隔相等的时间段划分为一个UW,每个UW的时间长度是确定,但是由于数据流的数据产生率会动态变化,所以每个UW所包含的事务数不一定相等,也无法提前确定,如文献([73,74]事务型滑动窗口( Transation-sensitive Sliding Window)是指根据事务个数对滑动窗口进行划分,每个UW中所含的事务个数相等且固定,文献[24,75,76]都属于此类。

时间型滑动窗口由于其每个UW中事务的个数不确定,需要记录每个UW中事务数以便窗口滑动时更新相应的值,这在一定程度上增加了系统的负担,而且当系统出现突39太原理工大学硕士研究生学位论文发性事务激增或者数据流速率变化比较大时,如果没有相应的措施会导致系统处理能力的下降,因此这类算法处理过程相对来讲比较复杂。

事务型滑动窗口模型由于每个UW中事务数量是固定,便于统一处理,而且算法是以事务为单位进行处理,因此能够对新接收的事务及时做出响应,效率相对较高,并且具有较好的适应性,受数据流速率的影响较弱。

但是算法应注意UW大小的选择,对于一些实时性要求较高的场合,如果过大会造成处理时延。

因此,为了适应高速数据流的需要,提高算法的实时性能,我们的算法采用了事务型滑动窗口,并且使每个UW中只包含一个事务,即UW1=1。

设滑动窗口长度为N,则滑动窗口中最多监控N个事务。

此外,根据滑动窗口模型处理流程的特点,在窗口滑动阶段,挖掘算法既要接收新数据又要删除过期信息,因此会对内存中保存的数据流信息频繁的进行插入和删除操作。

如果不能提供有效的处理手段和与之相适应的的数据结构,那么窗口的更新就会成为算法的瓶颈,不能及时的对新接收的数据进行处理522比特序列滑动窗口的实现文献6]引入了一个比特序列滑动窗口(Bit- sequence Sliding Window,简称BSW)来实现窗口滑动操作,这是一种事务型滑动窗口。

算法中任意一个数据项x都有一个与之相关的比特序列,记为BSW(x)。

如图5-1所示:每个方框表示一个比特位,代表滑动窗口中的一个UW,也即一个事务。

因为滑动窗口的长度为N,所以一共有N位。

其中T1表示当前滑动窗口中最早接收到的事务,Ⅳ则是最新接收的事务。

一个数据项x如果在当前滑动窗口中的事务Tk(1≤k
设当前已经接收了N个事务,7A个事务到来时,由于窗口已满就需要执行滑动操作。

此时对BSWαx)执行左移位,即令B(Tk=Bi(Tk+1)(1≤k
执行完以后,BSW(x)保存的就是数据项x在新滑动窗口下的状态。

太原理工大学硕士研究生学位论文文献[76]引入BSW虽然简化了窗口的滑动操作,但是它将滑动窗口内的所有数据信息都加以保存,而事实上其中大部分薮据项都是非频繁的,在频繁模式生成阶段都是需要删除的。

这些无用信息的存储和处理使得系统的空间需求增大,处理的负担增加。

因此,在此基础上我们提出了 BSW-Filter(Bit- sequence Sliding Window with Filter)算法,通过对非频繁项的过滤,降低了空间复杂度,有效提升了算法的时间效率53BSW- Filter算法53.1数据预处理对于原始的数据流,其中的信息一般会涉及事务的多个方面,然而实际应用中只有几个方面是人们在进行挖掘分析所关注的。

因此,本算法增加了一个数据预处理过程对数据流中的事务进行过滤,筛选出用户感兴趣的数据,将挖掘对象限定在用户感兴趣的数据上,从而减轻了系统的额外负担。

设用户关注的事务属性个数为L。

易知L是算法运行前用户预定义的定值。

数据预处理的过程相对简单,只需要根据用户的预定义删除事务中不相关的信息即可。

经过数据预处理后,每个事务中只包含用户关注的属性信息,因此此时每个事务的长度是相等的,都等于L,即每个待处理事务都只含有L个数据项表示该事务的L个属性值532相关说明w docIn. 算法中给定的支持度为s,给定的误差度是e,且有0≤8<<<1,F( Frequent Items)是算法在内存中维护的一个集合结构,其长度为L「1/G],用来保存当前滑动窗口中的临界频繁项。

F中的每个元素是一个是四元组

其中x表示数据项的值,q和del是两个计数器用于确定数据项的频率,BSW(x)则主要用于记录x在每个UW中状态并实现滑动窗口操作。

533频繁1-项集的生成BsW- Filter算法也采用BsW结构实现窗口滑动。

由于数据流中大量的数据项是非频繁的,而这些非频繁项的信息对挖掘结果并没有影响,如果所有的数据都保存,反而41太原理工大学硕士研究生学位论文影响了挖掘算法的性能。

因此我们并不监控滑动窗口中的所有数据,而是通过算法Item-Scan提取岀滑动窗口中的临界频繁1-项集加以保存,对于大量的非频繁数据项则并不关注。

但是当非频繁项转化成临界频繁项时,算法能够及时捕捉到相应的变化,并将其保存,同时对于衰变成非频繁项的数据,算法也能够及时发现并删除。

当用户发出频繁模式挖掘请求的时候,只需通过频繁μ-项集就可实现对频繁模式的挖掘算法Item- -Scan用于从数据流中发现临界频繁模式,具体描述如下算法1Item-Scan输入:数据流DS的一个预处理过的事务T输出:当前滑动窗口下的F1.F中所有BSW(x)的Bi(T1)=1的项xfq2.F中所有项BSW(x)<1;3.删除xfq=0的项;4. for each{xx∈n}{ifx in Fl thenxfy+;BSW(x)的Bi(T)=1n7.while fl is full% minocin. 删除所有xy=0的项;13加入F/;当用户需要査询数据流中频繁模式时,只需要根据Item-Scan算法得到当前滑动窗口下的F,接着提取其中频率计数大于(s-ε)N的项就可得到频繁1-项集,然后据此通过相应的挖掘算法即可得到频繁K项集。

定理5-1算法Item-Scan从数据流中删除的数据项一定是非频繁的,FⅠ是一个临太原理工大学硕士研究生学位论文界频繁项的集合。

数据流中没有出现在集合FⅠ中的数据项x,其真实频率∫εN,N是当前滑动窗口内的事务数。

证明:xF,x每次在滑动窗口中出现时,若当时x∈F,则算法将x的fq计数器加1;若当时xF,则算法将x加入到F中,并将其fq设为1。

因此,x在当前滑动窗中出现了f次,则算法对xq执行了∫次加1操作。

在当前时刻,xF/则说明算法对xq计数器至少执行了∫次减1操作(否则,x∈F1。

由于算法只有在F满的情况下才会对q执行减1操作,因此在x执行减1操作的同时,H中其他数据项的fq也执行了减1操作。

故算法至少执行了fF次减1操作,而减1操作的总数不应大于当前滑动窗口中总的数据项个数。

因此有/F*[1L*N,则有N「11
由定理2-1易知,频繁模式是由频繁项枃成,如果一个数据项是非频繁的,其父模式肯定是非频繁的。

再根据定理5-1可知,算法Item-Scan删除的是数据流中的非频繁项,因此不会导致频繁模式的缺失。

在任意时刻,数据项的两个计数器之和,即(fq+de)就是该数据项在当前滑动窗口下出现次数的估计值定理5-2对于F中的任意数据项,在当前滑动窗口内估计值(q+del与其真实频率F之间的误差小于eN。

证明:任意一个数据项x∈F,则km=Mm团BSW(x)中B(T)=1,1sKN}。

根据算法 Item-Scan可知, frqtdel是x在T到TN之间的真实频率,同时也是滑动窗口内的估计频率。

另外,易知在T至T期间xF,所以根据定理5-1可知x在这一段时期内出现次数小于εN。

所以x当前滑动窗口真实频率和估计值之间的误差小于N。

定理5-3Item-Scan算法保证所有真实频率超过sN的数据项均输出,所有真实频率低于(s-ε)N的数据项均不输出证明:定理5-1可知:所有真实频率超过aN的数据项均在FI中,则所有真实频率超过sN的数据项一定也在F中。

对于每个真实频率F超过sN的数据项x,F>sN,则FεN(s=ε)N,同时根据定理5-2有( frg+del)>F-eN,所以(rq+de)(s=ε)N。

在进行频繁模式挖掘时,Item-Scan算法只输出(fg+adel)>(sτε)N的数据项,因此真实频率超过sN的数据项均被输岀,而真实频率小于(s-ε)N的数据项肯定不会输出,也必然不会用于后续太原理工大学硕士研究生学位论文的频繁模式挖掘过程。

534窗口初始化过程当接收到的事务数不多于用户预定义的滑动窗口长度N时,算法就处于窗口初始化阶段。

在这一时期,只需要将新事务中的数据项加入F中,同时根据更新相关数据项的BSW(x)即可。

这主要是通过算法tem-Scan实现的,它保证了所有频繁1-项集都得以保存。

如表5-1所示,设滑动窗口长度SW=3,SW1包含三个事务:Ti(abc)、T2(ce)、race当T3到来时,滑动窗口中的事务数不大于窗口长度,因此算法还处于初始化阶段。

这时,由于数据项a在T、T3中出现,所以BSW(a)=101。

同理BSW(b)=100,BSW(c)=1,BSW(e)=011表5-1数据项BSW的初始化和滑动Table 5-1 Initialization and Sliding of Items BSW滑动窗口编号事务BSWShBSW(a)=101T(ace)BSW(c=lllBSW(e=ollBSW(allBSW(c=lllTacd)BSW(d)=001BSW(e)=110535窗口滑动在这一阶段,由于窗口的滑动,算法主要执行两个操作,一个是当新数据项加入时通过算法Item-Scan对数据流扫描,将临界频繁模式保存在FI中,同时过滤掉非频繁项另一个就是进行窗口滑动操作。

当事务TM+1到来时,窗口已经有N个事务,这时首先对F中所有数据项的BSW(x)执行Bi(Tk)=Bi(Tk+1)(1
具体如下:如果T1中的数据项x存在于F中,则将BSW(x)的Bi(TN)设为“1”,否则仍令Bi(TN)=1,但其他比特位都为“0”,再加入F。

对于FI没有中没有出现在TM1的数据项,其Bi(TN)都置为“0”。

如表5-1所示,当T4(acd到来时,由于滑动窗口已满,需要先将Ti“滑出”窗口再加入T4。

此时T2、73、74构成SW2。

因为b既没有出现在74中,也不在T2、T3中所以b不在S中,因此b从FⅠ中删除,而d只在74中出现所以BSWd)=001,以此类太原理工大学硕士研究生学位论文推便可得到其他数据项的BSW(x)。

通过对比SW1与SW2可以发现,只需对每个数据项的BSW(x)执行简单的移位操作就可以轻松的实现窗口的滑动。

53.6频繁模式的生成当用户发出请求,査询当前滑动窗口内的频繁模式时,算法就进入频繁模式生成阶段。

这一过程主要是通过类似 Apriori算法递增产生。

首先从Fl中找出所有jφ godel)>(s-eN的数据项作为频繁l-项集。

然后通过频繁1-项集得到候选的频繁K-项集CPk( Candidate pattern,k表示项集的长度),再通过对相关数据项BSW(x)的“与”操作在候选集中确定频繁K-项集,如此递归下去,直到不再产生候选项集为止5.3.7算法描述根据以上介绍,算法完整描述如下:算法2BSW- Filter输入:数据流DS.C(n输出:频繁项集FP.while no query of Fpirepeat算法ltem-Scan;docIn. 4. FP1=ixfr+del(s-aN;5. for(k-2; FPk-I* NULL; k++i由FPk得到CPkFPkckCk E CPk and f(ck>sNS9. FP=UkFP54实验结果及分析54.1实验环境Intel酷睿2双核1.8GHz处理器,lGB内存, WindowsXP操作系统,VC6.0编译太原理工大学硕士研究生学位论文实验中支持度s=0.001,误差度ε=0.ls。

数据集中每个事务有30个属性,我们每次随机抽取10个属性作为用户关注的属性个数,即L=10。

54.2算法性能分析图5-2是设每个属性取值范围 Range=2K,滑动窗口大小N分别为N20K和N=30K的实验结果。

我们可以看到当滑动窗口大小从20K增大30K时,算法的内存使用峰值并没有随之成倍的增长,依然维持在一个很低的范围内。

根据我们的算法可以知道,内存之所以会增加,是由于F中每个数据项x的BSW(x)长度增大导致的。

◆ Window size=20K— Window size=30K1025KIning Transactions(1K-1000)图52不同滑动窗口大小下的内存使用对比Figure 5-2 Comparion of Memory Usage betweenDifferent Sliding Window's SizesomRange=3K ---Range-2K1020KIning Transaction(IK=1000)图5-3不同取值范围的内存使用对比( Range是属性取值范围)Figure 5-3 Comparion of Memory Usage between Different ValuesRanges(range indicates the range of a attribute's value)图5-3是滑动窗口大小N=30K,属性取值范围分别为 Range=2K、 Range=3K的实验太原理工大学硕士研究生学位论文结果。

从中可见,虽然 Range=3K时最小内存使用值比 Ranges=2K时的要大,但是算法的最大内存使用值基本保持不变,也即薮数据项取值范围的变化并不会影响算法的最大内存使用量。

通过以上两组实验易知,算法的内存使用量有一个限值,由算法描述可知,该值主要受用户选取的关注属性个薮L和误差度ε影响,并不会随滑动窗口长度的增加而显著变化。

由于内存的使用率和数据的取值范围无关,因此对于取值范围较广或者未知的数据,算法具有较好的适应性。

算法的内存使用量呈现周期震荡,这正是由于我们采用FⅠ对数据流进行过滤、删除非频繁项的结果。

当算法的内存使用量到达限值时,就是FⅠ已满的时候,这时通过算法Item-Scan就会删除F中的非频繁项,从而降低内存占有量,然后再接收新的数据直到内存再次达到峰值。

543对比分析图5-4是滑动窗口大小N=30K,属性取值范围为 Range=2K时,BSw- Filter算法与MFI- Transsw算法在窗口初始化和滑动阶段内存使用情况的对比。

图5-5是滑动窗口大N=30K,属性取值范围为 Range=2K时,BSW- Filter算法与MFI- TransSw算法在窗口初始化和滑动阶段阶段运行时间的对比。

通过对比易知,BSW- Filter算法不仅空间性能优于MFI- Transsw算法,而且拥有较好的时间效率。

这主要是由于F结构的存在,使得 BSW-Filter算法需要保存的数据项大为减少,从而降低了内存使用量;同时数据项的减少,使得每次窗冂滑动时,需要进行的移位操作的数据项也随之减少,从而提高了处理效率-MFI-Trans Sw - W-Filter111425KIning Transactions(1K=1000)图54内存使用情况对比Figure 5-4 Comparion of Memory Usage47太原理工大学硕士研究生学位论文C-MFI-Trans Sw -BitSw-Filter目1002K7K1217K22K27KIning Transaction(IK-1000)图5-5运行时间对比Figure 5-5 Comparion of Processing Time55本章小结本章在薮据流频繁挖掘的技术要求下,结合实际应用的需求,针对高速薮据流提出了一种滑动窗口模型的BSW- Filter算法。

算法利用比特序列的移位操作,能够髙效的处理数据流的事务信息。

同时利用对非频繁项的过滤,极大的减少了需要保存的信息量,降低了内存使用率。

最后通过实验对算法进行了验证,并与MFI- TransSW算法进行了比较。

48太原理工大学硕士研究生学位论文第六章总结与展望6.1本文总结随着网络技术与计算机硬件的发展,数据流作为一种新型的数据模型一定会在越来越多的领域得到更广泛的应用,人们对数据流挖掘分析的需求也会越来越迫切。

本文重点介绍了数据流上频繁模式的挖掘算法,并针对髙速数据流的特点结合用户需求,提出了一种滑动窗口下频繁模式挖掘算法。

本文的主要内容与贡献如下:1)本文对传统的数据挖掘和数据流挖掘进行了一些概括和总结,简要的叙述了这个领域中的一些主要思想和方法,并结合现有一些挖掘算法对比阐述了数据流挖掘的技术特点和要求,详细介绍了滑动窗口模型下,薮据流频繁模式挖掘算法2)在已有频繁模式挖掘方法的基础上,针对滑动窗口模型的要求,提出了BSW- Filter算法,采用Bit- sequence Sliding Window结构,提高了滑动窗口操作效率,同时降低了内存使用率。

算法能够在单遍扫描下,生成数据流的频繁模式,并且算法最大内存使用率与数据的取值范围无关,而且不会随滑动窗口大小的增大而显著变化,适合于高速且取值不确定的数据流频繁模式挖掘62未来工作展望本文在数据流频繁模式挖掘方面做了一些硏究工作,并取得了一些成果,但这方面的研究开展的时间很短,还存在许多有待解决的问题,今后的工作主要放在以下几方面1)F中大部分数据项出现频率都小于sN,因此数据项的BSW(x)中存在大量的0”,所以可以考虑用编码技术对BSW进行压缩,进一步降低算法的空间复杂度2)频繁闭项集和最大频繁模式可以显著压缩挖掘所产生的频繁模式数,降低算法空间需求,因此我们将针对数据流展开这方面的研究3)要把数据流挖掘应用到实际环境中,为具体的应用提供丰富有用的信息和解太原理工大学硕士研究生学位论文决方案。

太原理工大学硕士研究生学位论文参考文献[1]J. Han, Micheline Kamber. Data Mining: Concepts and Techniques[M]. Higher Education PressMorgan Kaufmann Publishers. 2001.52] Henzinger M, Raghavan P, Rajagopalan S Computing on data streams[M]. Technical Report, ReportNo 1998-011, Palo Alto: HP Digital Systems Research Center, 1998. Henzinger M R, Raghavan PRajagopalan S Computing on data streams. SRC Technical Note 19982011. Digital systems researchcenter: Palo Alto, California, 1998[3] Sudipto Guha, Nick Koudas, Kyuseok Shim Data Streams and Histograms[C]. ACM Symposium onheory of Computing. Heraklion: ACM Press, 2001: 47-475[4] B Babcock, S Babu, MDatar, etc. Widom. Models and issues in data stream systems[C]. In: ProcPODS,2002:1-16[5] Motlwani R, Widom J, Arasu A, etc. Query Processing, Approximation, and Resource Managementin a Data Stream Management System[A]. In Proceedings of the CIDR Conf. on Innovative Datasystems Research[C]. Asilomar, California, USA: Morgan Kaufman Publishers, 2003: 245-256[6] Chandrasekaran S, Cooper O, Deshpande A, etc. Telegraph CQ: Continuous Dataflow Processing foran Uncertain World[A]. In Proceedings of the CIDR Conf on Innovative Data Systems Research[C]Asilomar, Califomia, USA: Morgan Kaufman Publishers 2003: 269-280[]李建中,张冬冬.滑动窗口规模的动态调整算法J.软件学报,2004,15(1):1800-1814.[8]高军,杨冬青,王腾蛟等.一种ⅹML数据流之上连续査询执行器的増量维护方法门].计算机硏究与发展,2005,42(5):23-25[9]武姗姗,宋宝燕.一种支持多目标的数据流操作语言[J小型微机系统,2005,26(5):22-25.1〕0]闰鸴,金澈清,曹锋等.多薮据流上共享窗口连接査询降载策略[.计算机硏究与发展,2005,42(10):1836-184[1门]钱江波,徐宏炳,王永利等.多数据流滑动窗口并发连接方[J计算机研究与发展,2005,(10:1771-1778[12 Guha S, Mishra N, Motwani R. Clustering data streams [A]. IEEE Symposium on Foundations ofCompute r Science[C], 2000: 359-366[13 Guha S, Meyerson A, Mishra N, etc. Clustering Data Streams: Theory and Practice[C]. IEEE51太原理工大学硕士研究生学位论文Transactionson Knowledge and Data Engineering, 2003. 15(3): 515-528[14 Babcock B, Datar M, Motwani R, etc. Maintaining Variance and k-Medians over Data StreamsWindows[C]. Proceedings of the 22nd Symposium on Principles of Database Systems, 2003: 234-243[15]O'Callaghan L, Mishra N, Meyerson A, etc. Streaming-data algorithms for high-quality clustering[A]International Conference of Data EngeeringIC] 2002: 685-694[16 Aggarwal C, Han J, Wang J, etc. A Framework for Clustering Evolving Data Streams[cIProceedings of the 29th VLDB Conference, Berlin, Germany, 2003: 81-92[17 P Domingos, GHulten Mining high-speed data streams[A]. In proceedings of the 6th ACM SIGKDDintenl ational conference Knowledge discovery and data mining(KDD2000), August20-23, Boston,USA,2000:71-80[18 GHulten, L. Spencer, P Domingos. Mining time-changing data streams C]. In proceedings of the 7thACM SIGKDD intenational conference on Knowledge discovery and data mining(KDD2001)August26-29, San Francisco, USA, 2001: 97-106[1]王鹏,吴晓晨,王晨等.CAPE数据流上的基于频繁模式的分类算法[门.计算机研究与发展2004,41(10)1677-168[20] Manku GS, Motwani R. Approximate frequency counts over data streams[C]. In: Bernstein P,loannidis Y, Ramakrishnan R, eds. Proc. of the 28th Int'I Conf on Very Large Data Bases. Hong KongMorgan Kaufmann Publishers, 2002: 346-357[21] Charikar M, Chen K, Farach-Colton M. Finding frequent items in data streams[C]. In: Widmayer P,Ruiz ft, Bueno RM, Hennessy M, Eidenbenz S, Conejo R, eds. Proc. of the Int'I Colloquium onAutomata, languages and Programming. Malaga: Springer-Verlag, 2002: 693-703[22] Joong Hyuk Chang, Won Suk Lee, Aoying Zhou. Finding Recent Frequent Itemsets Adaptively overOnline Data Streams[C]. ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining, 2003487-492[23 Chris Giannella, Jiawei Han, Jian Pei, etc. Mining Frequent Patterns in Data Streams at MultipleTime Granularities[M]. Data Mining: Next Generation Challenges and Future Directions, AAAI/MITH. Kargupta, A Joshi, K Sivakumar, and Y. Yesha(eds ) 2003: 191-21[24 Yun Chi, Haixun Wang, Philip SYu, etc. Moment: Maintaining Closed Frequent Itemsets over aStream Sliding Window[C]. In Proceedings of the 4th IEee international conference on data mining,November 2004: 59-66太原理工大学硕士研究生学位论文[25]张听,李晓光,王大玲等.数据流中一种快速启发式频繁模式挖掘方法.软件学报,2005,16(12):2099-2105[26]徐利军,谢康林,徐虹.基于数据流的频繁集挖掘J.上海交通大学学报,200640(③-502-506[27] Hua-Fu Li, Suh-Yin Lee, Man-Kwan Shan. Online mining(recently) maximal frequent itemsets overdata streams[C]. Proc. of the 15th IEEE International Workshop on Research Issues on DataEngineering(RIDE2005), Tokyo, Japan, April, 2005: 3-4[28]GDong, J. Han, L.V.S. Lakshmanan, etc. Online mining of changes from data streams Researchproblems and preliminary results[C]. In Proceedings of the 2003 ACM SIGMOD Workshop onManagement and Processing of Data Streams. San, Diego, CA, USA, 2003: 225-236[29]Ben-David S, Gehrke J, Kifer D. Detecting change in data streams[C]. In: Proceedings of the 30thInternational Conference on Very Large Data Bases. Toronto, Canada: Morgan Kaufmann,2004.180-191[30] D. Yu, G Sheikholeslami, A. Zhang Findout: Finding outliers in very large datasets[J]. Knowledgeand Information Systems, 2002, 4(4): 387-412[31M.M. Breunig, H Kriegel, R.T. Ng, etc. LOF: identifying density-based local outliers[C]. In: Proc. the2000 ACM SIGMOD Int'l Conf. Management of Data. New york ACM Press. 2000: 93-132]S Muthukrishnan, RShah, J. Vitter. Mining deviants in time series data streams[C]. In: Proc. the 1 6thInt'I Conf. Scientific and Statistical Database Management. Los Alamitos, CA: IEEE ComputerSociety Press, 2004. 41-50[33] T Palpanas, D Papadopoulos, V.Kalogeraki, etc. Distributed deviation detection in sensor networks[J]SIGMOD Record, 2003, 32(4): 77-82[34]杨宜东,孙志挥,张净.基于核密度估计的分布数据流离群点检测[J计算机研究与发展,200542(9):1498-150435 Agrawal R, Srikant R. Fast algorithms for mining association rules[C]. In: Bocca JB, Jarke M, ZanioloC, eds. Proc. of the 20th Int'l Conf. on Very Large Data Bases. Santiago: Morgan Kaufmannblisters.1994:487-499136J. Han, J. Pei, Y. Yin Mining frequent patterns without candidate generation[C]. In Proc. of 2000ACM SIGMOD. 2000: 1-12[3刀]徐利军.基于数据流的频繁集挖掘研究[D]上海:上海交通大学,200638 Quinlan JR Induction of decision trees]. Machine learning, 1986, 1(1): 81-106太原理工大学硕士研究生学位论文[39] Quinlan JR C4.5 Programs for Machine learning[M]. Morgan Kaufmann Publishers, Inc. 1993[40]李雄飞,李军.数据挖掘与知识发现(第一版)[M].高等教育出版社,2003,1192-111[41] TZhang, R Ramakrishnan, MLivny. BIRCH: An efficient data clustering method for very largedatabase[C]. In proc. 1996 ACM SIGMOD, Montreal, Canada, June 1996: 103-113[42S. Guha, RRastogi, K Sim. CURE: An effiecient clustering algorithm for large databases[C]. InProc. SIGMOD, Seattle. WA.1998: 73-84[43]GKarypis, E.H. Han, VKumar. Chameleon: A hierarchical clustering algorithm using dynamicmodeling]. Computer, 1999, 32: 68-75[44] M. Ester, H.P. Kriegel, J.Sander, etc, a density-based algorithm for discovering clusters in large spatialdatabases with noise[C]. Proc. 2 Int Conf on Knowledge Discovery and Data Mining. Portland, OR1996:226-231[45]M. Ankerst, M. Breunig, H P. Kriegel, etc. OPTICS: Ordering points to identify the clusterinstructure[ C]. In Proc of SIGMOD99, Philadelphia: ACM Press, 1999: 49-60[46 WWan, J. Yang, R Muntz. STING: A statistical information grid approach to spatial data miningMIn proc. VLdB,97. Athens, Greece. 1997: 1886-1995[47]D Fisher. Improving inference through conceptual clustering[C]. In Proc. AAAI Conf, Seattle, WA,yl987:461-465[48]JH Gennari, P. Langley, D Fisher. Models of incremental concept formation[M]. Artificial Intelligent,1989:11-61[49]Fang M, Shivakumar N, Garcia-Molina H, etc. Computing iceberg queries efficiently[C]. In: Gupta AShmueli O, widom J, eds. Proc. of the 24th Int'I Conf on Very Large Data Bases. New York: MorganKaufmann publishers, 1998: 299-310[50]J. Han, J. Pei, G Dong, etc. Efficient putation of iceberg cubes with plex measures[M]. In Procof 2001 ACM SIGMOD. 2001: 1-12[51] Richard M.Karp, Scott Shenker. A simple algorithm for finding frequent elements in sets and bags[M]ACM Transactions on Database Systems, 2003, 28(1): 51-5552 Nan Jiang, Le Gruenwald. Research issues in data stream association rule mining[C]. SIGMODRecord2006,35(1):14-19[53] Alon N, Matias Y, Szegedy m. The Space Complexity of Approximating the Frequency Moments]Journal of Computer and System Sciences, 1999, 58(1): 137-147太原理工大学硕士研究生学位论文[54]Gibbons P B, Matias Y, Poosala V. Fast incremental maintenance of approximate histograms [A]. Inproc. of the 23rd In't Conf on Very Large Data Bases[C]. Athens: Morgan Kaufmann, 1997: 466-475[55]金澈清.薮据流上若干査询处理算法的研究[D].上海:上海交通大学,2005[56]B Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors[C]. Communication of theACM,1970,13(7)422-426[57 Vitter J.S. Random sampling with a reservoir[C]. ACM Trans. on Mathematical Software, 198511(1):37-57.58 Gibbons P B, Matias Y New sampling-based summary statistics for improving approximate queryanswers[A]. Proceedings of the ACM SIGMOD Int'l Conf on Management of Data[ C]. Seattle: ACMPress,1998:331-34259 Aggarwal C, Han J, Wang J, etc. A Framework for Projected Clustering of High Dimensional DataStreams[M]. Proceedings of the 30th VLDB Conference, Toronto, Canada. 2004: 852-863[60] Gaber, M.M., Krishnaswamy S, Zaslavsky A. Adaptive Mining Techniques for Data Stream UsingAlgorithm Output Granularity[M]. In Australasian Data Mining Workshop 2003[C]. 2003: 105-115[61 Hoeffding W. Probability inequalities for sums of bounded random variables[J]. Journal of theAmerican Statistical Association, 1963, 58(301): 13-30[62]HWang, WFan, Yu P, etc. Mining Concept-Drifting Data Streams using Ensemble Classifiers[C]. Inproceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and datamining(KDD2003), August24-27, Washington, USA, 2003: 226-235[63 Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, etc. False Positive or False Negative: Mining FrequentItemsets from High Speed Transactional Data Streams[M]. Int'l Conf on Very Large Databases, 2004204-215[64 Guojun Mao, Xindong Wu, Chunnian Liu, etc Online Mining of Maximal Frequent Item Sequencesfrom Data Streams[M]. University of Vermont, Computer Science Technical Report CS-05-07, June[65]刘学军,徐宏炳,董逸生等.基于滑动窗口的数据流闭合频繁模式的挖掘[门计算机研究与发展,2006,43(10:1738-1743[66]王伟平,李建中,张冬冬等,一种有效的挖掘数据流近似频繁项算法[J.微电子学与计算机,2007,18(4):.884-892[67 Graham Cormode, S Muthukrishnan. What's hot and what's not: Tracking most frequent items55太原理工大学硕士研究生学位论文dynamically[M]. The ACM Symposium on Principles of Database System(PODS)2003, San DiegoCA,USA,2003:296-306[68]Jin C, Qian W, Sha C, etc. Dynamically maintaining frequent items over a data stream[M]. InCarbonell J. ed. Proc. of the 2003 ACM CIKM Int'l Conf. on Information and KnowledgeManagement. New Orleans: ACM Press, 2003: 287-294[69 Metwally A, Agrawal D, Abbadi AE. Efficient putation of frequent and top-k elements in datastreams[C]. In: Eiter T, Libkin L, eds. Proc. of the Int'l Conf. on Data Theory. EdinburghSpringer-Verlag, 2005: 398-412.[70 Yunyue Zhu, Dennis Shasha. StatStream: Statistical Monitoring of Thousands of Data Streams in RealTime[M. In: Bressan S, Chaudhri AB, eds. Proc. of the 28th Int'l Conf on Very Large Data BasesNew York: Springer-Verlag, 2003: 358-369[71] Hua-Fu Li, Suh-Yin Lee, Man-Kwan Shan. An Efficient Algorithm for Mining Frequent Itemsets overhe Entire History of Data Streams[C]. Int'l Workshop on Knowledge Discovery in Data Streams, Sept2004[72]刘学军,徐宏炳,董逸生等.挖掘数据流中的频繁模式[.计算机研究与发展,200542(12):2192-2198[73James Cheng, Yiping Ke, Wilfred Ng. Maintaining Frequent Itemsets over High-Speed DataStreams[ Cl PAKDD 2006: 462-467[74] Chih-Hsiang Lin, Ding- Ying Chui, Yi-Hung Wu, etc. Mining Frequent Itemsets from Data Streamswith a Time-Sensitive Sliding Window[C]. SIAM Int'l Conf on Data Mining, April 2005[75]Joong Hyuk Chang, Won Suk Lee. A Sliding Window Method for Finding Recently Frequent Itemsetsover Online Data Streams[M]. In Proceedings of the 9th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining, Washington, DC, USA, August 2003: 753-762[76Hua-Fu Li, Suh-Yin Lee. Mining frequent itemsets over data streams using efficient window slidingtechniques[EB/OL]. Expert Systems with Applications(2008), doi: 10. 1016/j eswa. 2007. 11.061。