数据流上频繁项挖掘方法研究毕业论文.doc

《数据流上频繁项挖掘方法研究毕业论文.doc》由会员分享，可在线阅读，更多相关《数据流上频繁项挖掘方法研究毕业论文.doc（40页珍藏版）》请在三一办公上搜索。

1、毕 业 设 计（论 文）题 目： 数据流上频繁项挖掘方法研究 专 业： 信息安全 学生姓名： 班级学号： 指导教师： 指导单位： 信息安全系 日期： 2008年 3 月 21 日至 2008 年 6 月10日摘 要发现数据流中的频繁项是数据流挖掘中最基本的问题之一。数据流的无限性和流动性使得传统的频繁模式挖掘算法难以适应。针对数据流的特点，论文对数据流处理技术和数据流挖掘中的关键问题进行了研究和总结，并对一些经典的频繁项挖掘算法进行了介绍。在借鉴FP-growth算法的基础上，采用了一种较新的数据流频繁模式挖掘的算法：FP-stream算法。算法受能够进行有效频繁项挖掘的数据结构FP-tree

2、的启发，创造了一个可以在数据流上进行有效挖掘的数据结构FP-stream。一个FP-stream结构包含(a)一个可捕捉频繁项和次频繁项的内存中的频繁树，(b)每一个频繁项都有的倾斜时间窗口表。构建、更新和维护该结构实现了在数据流上的挖掘。分析和实验证明了其性能。最后对未来的研究方向进行了展望。关键词: 数据流； 频繁项； 流数据挖掘； FP-stream算法； 倾斜时间窗口；ABSTRACTFinding frequent items is one of the most basic problems in the data stream. The limitless and mobilit

3、y of data streams make the traditional frequent-pattern algorithm difficult to extend to data streams. According to the character of data streams, a new FP-stream algorithm for mining frequent items for data streams is proposed. Inspired by the fact that the FP-tree provides an effective data struct

4、ure for frequent pattern mining, we develop FP-stream, an effective FP-tree-based model for mining frequent patterns from data streams. In addition, An FP-stream structure consists of (a) an in-memory frequent pattern-tree to capture the frequent itemset information, and (b) a tilted-time window tab

5、le for each frequent pattern. Efficient algorithms for constructing, maintaining and updating an FP-stream structure over data streams are explored. The analysis and experiments show the performance of this algorithm. Finally, future directions in research are discussed.Key words data streams; frequ

6、ent items; stream data mining; FP-stream algorithm; tilted-time window目 录第一章 绪论11.1课题背景和研究现状11.2 课题内容3第二章 数据流和数据流挖掘42.1 数据流42.2 数据流挖掘算法和特点52.3 数据流挖掘的关键问题62.4 本章小结8第三章 频繁项挖掘及相关算法93.1 频繁模式概念93.2 挖掘方法103.3 有关算法123.4 本章小结13第四章 数据流上频繁项挖掘算法144.1 改进的FP-stream算法关键点144.1.1头表fList的设计144.1.2 倾斜时间窗口维护策略154.2 改进

7、的FP-stream算法设计184.2.1 FP-stream的模式树结构184.2.2 FP-stream结构204.3 对FP-stream的更新和维护22第五章 改进的FP-STREAM算法实现235.1 FP-tree的构建235.2 FP-tree的更新255.3 分析和评价295.4.1 数据处理295.4.2 结果分析和性能分析295.4.3 应用展望31结束语32致 谢33参考文献34第一章 绪论随着信息技术的高速发展，海量数据的积累成指数级增长，人类面临数据海洋、知识匾乏的难题。数据挖掘技术旨在从大量数据中提取有用的知识，帮助人们进行科学分析和决策。经过近十几年的发展，很多有

8、用的挖掘算法和模型相继被提出，数据挖掘技术已经被应用到多个相关领域。然而，近年来，产生了一种新的数据形式，如传感器网络、电子商务记录、网络监控日记。这些数据源源不断的到来，并且是快速的、无限的。这种数据流挖掘算法只能对数据进行一次顺序扫描，有限的内存也无法处理高速大量的数据。传统的数据挖掘算法不能适用于这种数据流模型，这促使人们设计新的算法来适应数据流挖掘。1.1课题背景和研究现状数据挖掘技术出现于20世纪80年代后期，90年代有了突飞猛进的发展。数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对

9、数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。现在数据挖掘技术在商业应用中己经可以马上投入使用，因为对这种技术进行支持的三种基础技术已经发展成熟，分别是:海量数据搜集；强大的多处理器计算机；数据挖掘算法。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的人们事先不知道的、但又是潜在有用的信息和知识的过程1。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包含好几层含义:数据源必须是真实的、大量的、含噪声的;发现的是用户感兴趣的知识;发现的知识要

10、可接受、可理解、可运用;知识从广义上理解为数据和信息。但人们更把概念、规则、模式、规律和约束等看作知识。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现的知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行

11、计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 尽管传统数据库获得了巨大的成功，但是在20世纪末，一种新的应用模型却对它提出了有力的挑战。这种名为数据流(data stream)的应用模型广泛出现在众多领域,其中也包括安全领域。数据流的处理技术最早就是出现在网络监控方面，人们用它来做网络质量分析，流量统计等。数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息从数据库中抽取出来，将为公司创造很多潜在的利润，数据挖掘概念就是从这样的商业角度提出来的。数据挖掘(Data Minin

12、g)是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应用价值的领域，最近十几年出现了大量的数据挖掘方法，比如聚类，分类，关联分析等。随着数据流管理系统和数据流处理技术研究和发展，人们开始考虑能像以前的数据库一样，从数据流中发现知识，于是数据流挖掘算法随之出现。数据流挖掘类似数据挖掘，都是从大量的数据中获取有用的知识，不过挖掘对象是数据流。数据流管理系统、数据流处理技术和传统的数据挖掘，为数据流挖掘的研究提供了一系列方法。传统的数据挖掘问题也被引入到数据流挖掘领域，比如聚类，分类，频繁模式挖掘等。数据流还是一门较新的领域，对于数据流

13、的查询和分析以及数据流挖掘有许多的发展空间和研究方向。目前研究比较多的是:数据流处理的模型和语言；处理类似于普通数据库查询的流查询；数据流的采样和近似技术；数据流处理时对内存的管理；数据流处理与数据库的结合；对高速数据流的挖掘算法；新型的数据流处理的应用。这些都是一些重要的和活跃的研究领域，国外许多大学和研究机构都在对数据流做进一步的探讨。国内的数据流的研究还不是很多，但己有一些大学、研究院开始了数据流的相关研究，并己有一些相关的论文出现于国内刊物上。最近几 年，数据流上的频繁模式挖掘被广泛的进行研究。Manku提出的Lossy counting算法2，通过对当前整个数据流的事务进行近似计数挖

14、掘频繁项。Charikar 提出了一次扫描数据流的算法返回当前最频繁项。Chang提出了estDec算法，通过定义按时间指数进行衰减的策略挖掘最近的频繁项集。Giannella和Jiawei Han 等提出了在任意时间间隔上挖掘频繁项集的近似算法3.4，该算法采用在内存中保存频繁项的FP-stream数据结构，通过把数据流分成等长的数据段，对数据流进行批量处理，然后把历史数据保存在对数倾斜时间窗口中，能够实现对任意时间段的数据进行查询。由于是对数据流进行分段处理，不能实时的对数据流进行处理，处理时间粒度较粗。Huafu Li等提出DSM-MFI算法，用于挖掘最近的最大频繁项集，通过SFI-fo

15、rest数据结构存储当前的概要频繁项集。频繁模式挖掘算法能够发现所有的频繁项集，但会产生大量的冗余信息，最大频繁项集挖掘虽然减少内存空间的占用，却丢失大量有用的信息。相对于有限的内存空间，频繁闭项集挖掘能更好的满足用户的需求。Yun Chi提出基于滑动窗口的频繁闭项集挖掘算法，采用CET数据结构存储数据流中的所有项集，根据滑动窗口数据的变化实时更新CET中四种不同的项集，但项集的历史信息没有保存。国内研究数据流频繁模式挖掘主要有中国人民大学、哈尔滨工业大学和复旦大学等。哈尔滨工业大学提出了基于字典树5的频繁模式挖掘算法，复旦大学的周傲英等提出了数据流频繁模式历史计数的有效保存方法6。1.2 课

16、题内容基于数据流模型的挖掘算法，必须在有限的内存空间内完成，数据流高速到达的特性要求挖掘算法尽量采用增量更新的方法。本课题研究了一种有效的数据结构存储数据流的概要信息，基于滑动窗口实现挖掘算法的增量更新，主要研究内容包括以下几个方面。第一: 分析数据流的特点，对比传统数据挖掘与数据流挖掘的不同，理解数据流模型。第二: 研究存储数据流的概要信息的数据结构，FP-tree是目前比较有效的存储结构，在此基础上提出的FP-stream结构，类似于前缀树，并且通过时间窗口保存历史频繁计数。第三: 在用FP-stream结构存储数据流概要信息的基础上，研究数据流上频繁项挖掘算法FP-stream算法，以指

17、数直方图形式处理高速、大量的数据流，更好地适应数据流挖掘的特点。第四: 通过进行大量的实验，结合理论定理的说明，在时间复杂度和空间复杂度上证明算法的有效性。第二章 数据流和数据流挖掘2.1 数据流传统的数据库存储的是静态的关系型数据记录的集合，它们具有限定的大小、可控制的操作、详细定义的结构，同时这些数据具有持久性。传统数据库中的计算具有较高时间复杂度和空间复杂度，其查询处理为单次查询，查询计划为静态的，且最终生成确定的查询结果。另外，传统数据基本没有时间的概念。但许多当前的及今后的应用，要求能对不断快速变化的数据流提供在线分析支持。当网络控制器、电信数据管理、网络个性化、生产、传感器网络等应

18、用出现之后，数据大都是连续的数据流，并且与过去的那种单次查询相反，用户需要长期的、连续的查询，这就对数据库系统以及数据的处理算法等提出了新的挑战。数据流是连续的、无限的、快速的、随时间变化的数据元素的流。与传统的数据相比，流式数据具有许多特点:它是大量的、连续的、无限的数据；变化很快，并且要求快速的即时响应；数据流管理中随机存取采用的是一种代价昂贵的单一线性的扫描算法；仅仅存储到目前为止的现有数据。2.1.1 数据流的特点数据流不同于传统的数据仓库，数据流的到来往往是高速的，并且数据量是无穷的，通过对比传统关系型数据，数据流具有以下几个特点。(1) 数据记录是动态的，即数据不是静态的，需要动态

19、的进行更新并存储在管理系统中以备使用。(2) 数据流管理系统DSMS无法知道下个到达的数据是什么，甚至在同一个数据流中，DSMS也无法控制待处理的数据记录的顺序。(3) 本质上，数据流的长度是无限的，查询处理的数据流是高速的、连续的、随时间变化的。(4) 数据流中的记录一旦被处理，可能抛弃，也可能归档；无论是哪一种处理方式，很难重新查询。(5) 在数据流处理中，可能会结合DBMS。例如，某一次数据查询中，可能需要用到关系数据库中的数据，或者，连接操作，可能把数据流与关系表连接，以获得所需的数据流。2.1.2 数据流模型的特点数据流的这些特点要求一个完整、优秀的数据流处理系统必须具有以下特点:1

20、. 实时接受到达的数据，在不作存储的情况下立即处理，处理速度满足输入数据的速度要求。2. 由于数据流无边界，所以其处理结果的反馈也必须是实时的:结果即时更新、即时可查。3. 其处理算法必须满足一次扫描的要求，即不再对数据做重复扫描和计算。用户数据库或数据仓库DML结果数据用户概要数据结构数据处理算法DML结果实时更新数据流(a) 传统数据处理(b) 数据流处理 图 2-12.2 数据流挖掘算法和特点数据流具有以下几种性质:数据快速持续地到达、数据海量、数据到达有序。在传统的数据挖掘过程中一个重要的问题在于数据获取困难，从而导致在小样本上出现过配；而如今大量数据迅速到达样本获取不再困难，但处理时

21、的资源消耗成为主要的瓶颈；而且对数据流进行分析时不能忽略它的另一个重要性质:数据经过处理后，除非有其特殊价值，否则不进行保存，这主要是因为内存有限而使用外存增加处理时间。为了和数据流模型相适应，对应的数据挖掘算法需要能够只需要单遍扫描样本子集就能有效地快速地进行学习。另外和现实数据相关的数据流还有一些不可以忽略的性质，例如数据分布可能随时间变化而改变等，这就需要对一定时间内子样本进行学习的结果进行更新，这样的算法才能自适应数据分布的变化。相对于普通的数据挖掘算法，数据流的算法时空复杂度小，但是大多得到的是相对于普通算法的次优解，于是对数据流挖掘算法和普通算法差异的界的讨论也是必要的。数据流挖掘

22、算法和传统挖掘算法相对比有其特殊的地方。无论是分类、聚类还是频繁模式挖掘，数据流上的算法注重的都是一遍扫描数据集，并尽可能对结果集压缩存储。所有的分类和聚类算法注重模型的定义及再建立，以取得更好的匹配效果，使得分类或聚类的效果更好，而时间效率并不太关心；在数据流上进行分类或聚类算法则注意动态的适应数据的变化，尽可能及时地调整模型，算法的执行速度要达到一定要求，而建模的精确程度没有过多研究。原有的频繁模式挖掘算法因为最终结果是固定的，所以算法重点在于减少扫描数据集的次数， 以获得更好的时间效果；在数据流上挖掘频繁模式，算法一方面要保证只扫描一遍数据，另一方面要使结果集与统计的结果相比尽可能准确，

23、挑战是可想而知的。有的算法通过哈希或抽样等方法，在保证一定误差下降低处理的数据量，加快响应时间:有的算法以低支持度阐值的方法，来保证在一遍扫描的前提下，及时记录可能频繁的模式，使挖掘结果的误差尽量低。数据历史信息的压缩存储也是数据流挖掘算法共同关心的问题。一般来说，算法只保存数据的概要信息，如统计值；或分时间段保存数据，将大量信息存储为几个代表点。另外，随着数据的流动，部分信息可能过时，算法通常以一定策略进行删除，以释放存储空间。2.3 数据流挖掘的关键问题频繁项集挖掘是找出支持度大于给定支持度的所有项集。这些项集被称为频繁项集。由于数据流的连续性、无限性、商速性及数据分布随时间不断改变这些特

24、性，传统的频繁项集挖掘方法不再完全适用。这就使得我们在进行数据流中频繁项集的挖掘时需要考虑比传统的数据库中频繁项集挖掘更多的问题。由于数据流的特点，在对数据流进行频繁项挖掘时我们需要考虑以下问题：数据处理模型建立进行挖掘的数据流中数据的处理模型；压缩数据结构建立压缩的数据结构存储无限的数据中的有用数据；计算高效的一追扫描算法高速处理数据流；概念漂移适应数据分布的变化；自适应性根据资源和数据流自己进行调整。2.3.1 数据处理模型在进行数据流挖掘算法设计时，首先要考虑的问题是要对数据流中哪些数据进行哪些挖掘。数据处理模型便是对数据流中数据进行处理、挖掘的模型。当前的数据流挖掘算法中主要存在三中数

25、据模型：Landmark Windows、Damped Windows、Slinding Windows。Landmark Windows模型挖掘从某一叫做landmark的时间点到现在的所有历史数据中的频繁项集。无限的窗口是这一模型的特殊情况。它挖掘从数据流开始到当前所有的数据中的频繁项集。但是，这一模型不适合于人们只对数据流中最近的信息感兴趣的应用。Damped Windows模型也叫做时间衰退(Time-fading)模型。在这种模型中，数据流中每一个项集都有一个权重。该权重随时间逐渐减小，即新出现的项集对该项集的频度影响大于原来的项集。这种模型考虑对新的和旧的数据赋予不同的权重。这适合

26、于旧的数据对挖掘结果产生影响但是会随着时间减弱的应用.Slinding Window模型挖掘和维护当前窗口中的频繁项集.窗口的大小根据应用和资源来确定。在金融和股票交易中，使用滑动窗口模型更合适。一个Landmark模型可以转变成其它两种模型。在其上加上时间衰退函数就能使其转变为Damped模型。在其上跟踪、处理一个滑动的窗口中的数据就能使该模型变为一个Slinding Windows模型.不同的数据模型适用于不同的具体应用。在进行数据流挖掘算法设计时，具体使用哪种模型根据具体的应用对象而定。2.3.2 压缩的数据结构静态数据上的频繁项集挖掘是在多追扫描数据库之后，收集所有项集的计数信息并且丢

27、弃非频萦项集和它们的计数信息。但是在数据流上进行频繁项集挖掘时这种方法是不可行的。第一，当巨大的数据流连续不断的到来时，不可能在内存中存储所有的项集和它们的计数。第二，项集计数随新到来的数据而改变。一种算法是存储最频繁的项集和它们的计数。这种算法存储了最重要的信息，但是丢弃了非频繁项集的计数和将来有可能成为频繁项集的项集。可以看到，为了收集更多的资源来获得更精确的结果就会使用更多的内存空间和需要更多的处理时间。这就 需 要 一个有效的压缩的数据结构来存储更新和检索收集的信息。由于有限的内存空间和巨大的数据流连续不断的到来。不能建立这样一种数据结构将会很大程度的降低挖掘算法。因为即使我们在磁盘上

28、存储了这些信息，附加的I/O操作将会增加处理时间。由于巨大的数据量不可能重新扫描整个输入数据来满足在线查询高度响应的要求，因此数据结构必须增量维护。能否建立一个好的压缩数据结构是一个数据流挖掘算法性能好坏甚至是否可行的重要基础。现存的一些算法使用的压缩数据结构有FP-树、前缀树。树形结构压缩程度较高，是常用的数据结构。略图是进行频繁项集统计的一种有效的压缩数据结构。它将计数映射到一个Sketch数据结构中进行压缩统计。在设计算法时，选择适合的项集压缩数据结构和项集计数的统计压缩数据结构。此外，还有一些其它的概要数据结构。2.3.3 概念漂移数据流中的数据分布随着时间不断的改变。这些变化经常使在

29、旧的数据上建立的模型和新的数据产生不一致，而且需要频繁的更新模型。在某一时间段内出现的频繁项集可能在下一个时间段内变成非频繁的项集。同样在某一时间段非频繁的项集在下一时间段可能变成频繁的项集。如果我们只在数据结构中存储频繁项集的计数，当我们需要一些潜在的、稍后变为频繁项集的非频繁项集的计数时，我们得不到这些信息。因此需要考虑处理概念漂移的技术。滑动窗口技术能够针对窗口大小的数据流进行挖掘，不会受到以前挖掘结果的影响。FP-stream算法中在频繁模式树中嵌入时间窗口，可以挖掘不同时间粒度的频繁项集。 Slinding Window方法挖掘滑动窗口中的频繁项集。在设计针对数据分布不断变化的挖掘算

30、法时，可以考虑使用滑动窗口技术挖掘不同范围和不同时间粒度的数据。2.3.4 自适应性在数据挖掘中，内存和CPU等资源十分珍贵。如何有效利用这些资源是设计数据流挖掘算法时需要考虑的又一问题。当可用资源较少时，流数据高速到来很快就会耗尽资源。如果在算法中不考虑资源的使用情况，则很可能导致大量数据的丢失甚至挖掘产生错误和失败。当可用资源较多时，算法能够根据可用资源来进行调整则可以提高挖掘的精度和速度。另外，当前各种手持设备和传感器网络的普及也要求算法能够根据不同的设备和资源来自行调整。所以，根据资源来自行调整挖掘参数进行有效的挖掘是算法设计时要考虑的问题之一。降载技术在一定程度上可以解决数据流爆发或

31、者数据流输入超过系统处理能力的情况。但是降载技术丢弃了一些比较重要的数据。因此，在使用降载技术解决数据流挖掘算法的自适应性问题时，要慎重考虑。此外，数据流挖掘算法还可以考虑在处理能力有限的情况下，使用一些概要的数据结构代表数据进行粗粒度的数据处理。2.4 本章小结本章主要介绍了数据流这一新型数据类型的特点，管理数据流应该采用的数据流管理系统模型。对比传统的数据挖掘，由于数据流本身所具有的特点，在数据流上执行挖掘要面临许多新的困难。介绍了数据流的特点、数据流挖掘的关键问题和数据流处理技术。数据流是一个随时间到来的数据序列。它具有连续性、无限性、高速性、分布随时间改变的特点。由于数据流的这些特点，

32、我们在进行数据流挖掘时必须考虑更多的问题。在对数据流进行挖掘时我们要考虑到数据处理模型、压缩的数据结构、计算高效的一遍扫描算法、概念漂移、自适应性等关键的问题。数据流的处理技术主要有基于数据的和基于任务的两种。其中基于数据的技术主要有概要数据结构(Synopsis data structures)和聚集(Aggregation)、采样(sampling)、降载(Load shedding)、略图(Skeching)等技术。基于任务的技术主要有近似算法(Approximation algorithm)、窗口(window)和算法输出粒度(Algorithm output granularity)

33、等技术。还介绍了数据流上数据挖掘的思路，说明了数据流挖掘在侧重点上有哪些变化。第三章 频繁项挖掘及相关算法频繁项挖掘作为关联规则挖掘的基础，一直是数据挖掘领域的重点。其中FP-growth算法是较为有效的一种挖掘算法3.1 频繁模式概念给定项目集I = i1,i2,.,im。其中，ik(1km)是一个项目(item)，I的非空子集称为模式。一个模式所包含的项目的数量称为该模式的长度。数据集D是一组事务的集合，事务是I的非空子集，数据集D包含的事务的总数记为|D|。数据集D中包含模式P的事务的数量称为P的计数，记为f(P)。P的计数与数据集中事务的总数的比值称为P的支持度(support)，记为

34、s(P)。假定是事先设定的最小支持度，如果s(P)，则称P是频繁的。所有频繁模式的集合称为频繁集，记为F。频繁模式挖掘通常用于进一步产生关联规则，或直接作为决策支持的辅助信息，主要应用于分类设计、交叉购物和贱卖分析等等。典型的例子是购物篮分析，通过了解哪些商品频繁地被顾客同时购买，可以帮助零售商制订营销策略。然而，现在大多数公司组织都采用电子方式记录他们涉及的每一件事务，当这个组织变大，记录的结果每天也就相应的迅速增加，无论是支持商业决策而挖掘的销售数据，还是Web挖掘所用的日志数据，其增长速率都在飞速提高，例如Google网站每天处理1亿500万条搜索记录。并且，例如决策支持、传感器数据分析

35、和个性化推荐等，这些频繁模式挖掘的应用领域对动态反馈的要求都比较高，简单提高传统算法的时间效率并不能完全满足数据流上这些要求。必须以数据流的方式处理这些数据，研究数据流中频繁模式挖掘的方法。数据流频繁模式挖掘应用广泛，近年来网络安全是应用数据流挖掘技术比较多的一个领域，但传统的网络入侵检测系统多采用预先设置好规则，然后进行规则对比发现威胁，网络流的高速要求实时对数据进行处理，挖掘网络流的频繁模式就能进一步为网络入侵系统提供有用信息。除此之外数据流中的频繁模式挖掘还广泛应用于传感器网络等。3.1.1 频繁模式分类定义3.1：设所有项的集合=I1，I2.Im，Ii为第i个项。事务数据库DT1,T2

36、.Tn，Ti是第i个事务，Ti是的子集，例如:TI=I1，I3，I7，|D|为事务数据库的长度。项Ii在事务数据库中出现的次数记为Si,用户定义最小支持度(01)，如果Si大于|D|，项Ii就是频繁项。项集F是E的子集，如果项集F在事务数据库中出现的次数大于|D|，那么项集F就是频繁项集。依据Apriori性质得到，频繁项集的子集也是频繁的，只要得到最大频繁项集或频繁闭项集就能得到大部分频繁项集。定义3.2：最大频繁项集(M)是指频繁项集的任何超集都不是频繁的。挖掘最大频繁项集的结果集数量远远小于频繁项集的数量，从最大频繁项集的子集得到的频繁项集丢失了频繁计数信息。所以，只挖掘最大频繁项集会丢

37、失大量有用信息。定义3.3：频繁闭项集(C)是指频繁项集的频繁计数大于任何超集的频繁数。挖掘频繁闭项集的结果数量远远小于频繁项集的数量，从频繁项集的子集得到的频繁项集，它的支持度一定等于频繁闭项集的支持度。所以频繁项集的信息得到了保存。3.2 挖掘方法数据流中频繁模式挖掘算法按挖掘方式的不同，可以分为批处理算法与启发式算法两种。批处理方法的处理速度较快，但需要积攒足够数据，无法满足实时性要求，并且查询粒度通常较粗。启发式方法能够随流数据的到达直接进行处理，在一定程度上可以实时反映频繁模式的变化，但对于高速到达的数据流，其处理速度仍然有限，且现有算法的模式统计计数不包含详细历史信息，使得模式估计

38、与查询精度仍然较低。3.2.1 批处理方法批处理方法主要思想是对数据流分片，通过分片上的局部频繁模式来求解全局频繁模式。批处理方法中有代表性的是Manku提出的Lossy counting算法Gialmela等提出的FP-stream 算法。Lossy counting算法中，数据流被分为均匀分片，每片包含1/个事务，初始分片编号为1，之后依次递增。其中是事先指定的允许误差，远远小于通常使用的频繁度阐值。频繁模式集以三元组(set,f,)存储模式，set标识唯一模式，f为模式计数，为计数误差。算法每次处理个分片，若分片中的模式包含于频繁模式集，则按在分片中的出现次数更新那些被包含模式的f值；若

39、不包含于频繁模式集，则判断模式在分片中的出现次数是否大于民若是则将该模式加入频繁模式集，新加入模式的值为当前分片编号减1。算法定期扫描频繁模式集，若模式的(f+)值小于当前编号，则将模式从频繁模式集中删除。Lossy Counting算法的频繁模式集中包含所有真实计数大于。N的模式，N是当前数据流中的事务数。如果一个模式包含于频繁模式集，其真实计数一定在f与(f+)之间。如果用户以阐值5查询频繁模式，算法输出频繁模式集中f值大于(s-)N的所有模式。FP-stream算法基本思想与Lossy Counting算法一致。FP-Stream算法在将数据流均匀分片后，依照模式在第一分片中的计数排序，

40、构造字典树来存储频繁模式集。算法在当前分片中，以不指定阀值的FP一Growth算法挖掘模式。如果模式存在于字典树中，则更新其计数;若不存在，则判断其计数是否大于指定误差与分片包含事务数B的乘积，如果大于则将其插入字典树。FP-stream算法利用时间窗口记录模式的历史信息来回答用户对各个时间段的查询。基于人们对越新的事物关心程度越高的事实，算法使用一种“倾斜”的时间窗以不同粒度压缩不同时间段的数据，给出在这种时间窗下保证模式查询精度的断言与证明。并对该算法进行了改进，提出全局时间窗方法，以衰减的策略发现最近频繁的模式。批处理方法时间效率较好，但不能实时处理流数据和响应用户对当前数据的查询，并且

41、算法查询精度较低，即使使用时间窗口，其窗口粒度仍然较粗(等于每分片包含的事务数)。3.2.2 启发式方法启发式方法的主要思想是随着流数据的不断到达，由己知频繁模式逐步生成新的频繁模式，基本过程是当新事务到达后，判断其中新模式蕴含的所有父模式，只有当新模式的所有父模式都己经存在于频繁模式集，才将其加入模式集。由于在启发式挖掘频繁模式过程中，长度为k的模式只有在其所有长度为k-1的父模式都被发现的前提下，才能被考虑，因而存在模式计数偏小的问题。Hidber提出Carma算法对这个问题进行了改进，提出以父模式中的最小频数估计新产生模式的频数，算法中频繁模式集也以三元组存储:计数count，首次发生时

42、间firstTrans，最大误差maxMissed。Carma算法中通过第二次扫描数据来保证最大误差，从而使其在数据流挖掘中的应用受到限制。Chang等的estDec算法采用了字母序的字典树存储模式，应用了类似Carma算法的估计频数思想，也是以新模式的父模式中的最小计数来近似估计新模式的实际计数，并由阐值s与模式长度k约束频数上限。算法通过按时间指数进行衰减的策略，保证只挖掘最近发生的频繁模式。同批处理方法相比，启发式方法不需要积累数据，具有较好的实时性和更高的查询精度。但算法均以字典树的结构保存挖掘结果，而挖掘得到的模式较多，使得结构较宽，无论是在其中对是否增加节点进行判断，还是更新节点的

43、计数信息，都需要在结构中横向查找，其时间代价较大。对于高速到达的数据流，启发式算法的处理速度仍然有限，且现有算法的模式计数不包含详细历史信息，使得模式估计与查询精度仍然较低。3.2.3 增量更新方法批处理的方法分片处理数据流，在每个分片上可以使用现有的各种快速挖掘算法，从而整体处理速度快。但数据流频繁模式挖掘为防止可能频繁的模式不能被及时发现，通常使用较低的支持度阈值，这样一来，数据流的分片宽度也随之变大。在大的分片宽度下，算法要等待积攒足够的数据才能执行，从而使得对当前数据的处理不够及时，也就不能尽快的反映频繁模式的变化情况。并且由于分片宽度关系到窗口粒度，进而与查询精度相关，所以批处理方法

44、的查询粒度也较粗。启发式方法以事务为单位处理数据流，可以及时响应对当前数据的查询，具有较好的实时性。由于挖掘任务通常在具有较多的项的数据集上进行，如多种类的商品(购物篮分析)，大量的网页(Web挖掘、个性化推荐)等等。由大量的项所组成的事务也就包含了大量的模式，并且在数据流频繁模式挖掘所使用的低阐值下，相当数量的模式被认为是频繁或者可能频繁而被记录。这样在被大多算法使用的树型模式存储结构中，表现出的后果就是树的宽度极大，并进一步导致在树中查找模式的代价很大。启发式算法在处理每个事务时，无论是对己有模式进行更新，还是在增加新模式时对相应父模式进行判断，都需要在树中进行查找操作，这使得算法整体时间

45、效率较低。数据流挖掘中人们往往关注最近的数据。本文以启发式算法为基础，采用定量更新滑动窗口技术来实现对当前数据流的挖掘。3.3 有关算法3.3.1 Apriori算法1994年Agrawal等在先前工作的基础上，完善了一个称为Apriori的关联规则挖掘算法。该算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，是用先验知识，通过项目集元素数目不断增长来逐步完成频繁项目集的发现。首先找出频繁1-项集的集合，记做L1。L1用于找频繁2-项集合L2。L2而又用于找L3。如此下去，直到不能找到频繁k-项集。该算法基于这样一个性质：频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。是通过

46、项目集元素数目不断增长来逐步完成频繁项目集发现的。首先产生1-频繁项集L1，然后是2-频繁项集L2，直到不再能扩展频繁项集的元素数目而算法停止。在第k次循环中，过程先产生k-候选项集的集合Ck然后通过扫描数据库生成支持度并侧试产生k-频繁项集Lk。Apriori算法有两个致命的性能瓶颈：它可能产生很大的候选项集。例如，如果有104个频繁1-项集，则Apriori算法可能产生接近107个元素的2-侯选集。这样的庞大的候选项集在时间和空间上都是很难接受的。它可能重复扫描数据库，需要很大的I/O负载。每产生一次候选项集都要扫描一次数据库。如果频繁项集包含的项很多的话就需要多次扫描数据库。这样I/O开

47、销十分庞大。3.3.2 Close算法1999年Pasquier等人提出关闭项目集挖掘理论，并给出了基于这种理论的Close算法。他们给出了关闭项目集的概念，并讨论了这个关闭项目集格空间上的基本操作算子。Close 算法是基于这样原理的:一个频繁关闭项目集的所有关闭子集一定是频繁的，一个非频繁关闭项目集的所有关闭超集一定是非频繁的。因此，可以在关闭项目集空间格上讨论频策问题。实验证明，它对特殊数据是可以减少数据库扫描次数的。Close算法仍然沿用Apriori算法递增测试项目集的方法来寻找频繁项目集的，但是它是在关闭项目集格空间上侧试，提高了生成频繁项目集的效率，并且可能减少扫描数据库的次数。Close算法存在的主要问题是：(1)当最小支持度较小时，每个层次上的关闭频繁项目集的数目仍很大，因此不可能大幅度提高效率；(2)事先很难确定具体的数据库扫描次数；(3)为形成关闭项目集需要额外的代价。.3.3.3 FP-growth算法2000年Han等提出了一种FP-growth算法。该算法挖掘全部的频繁项集