数据流频繁集挖掘算法研究.doc

《数据流频繁集挖掘算法研究.doc》由会员分享，可在线阅读，更多相关《数据流频繁集挖掘算法研究.doc（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、电 子 科 技 大 学UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA工程硕士学位论文ENGINEERING MASTER DISSERTATION论 文 题 目： 数据流频繁集挖掘算法研究 工 程 领 域： 软件工程 指 导 教 师： 卢国明 教授 作 者 姓 名： 赵传冰 班 学 号： 200892303008 分类号 密级UDC 学 位 论 文数据流频繁集挖掘算法研究赵传冰指导教师姓名 卢国明 教授 （职务、职称、学位、单位名称及地址）申请学位级别 工程硕士 专业名称 软件工程 论文提交日期 论文答辩日期 学位授予单位和日期

2、 答辩委员会主席 评阅人 年 月 日注1注明国际十进分类法UDC的类独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名： 日期： 年 月 日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科

3、技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）签名： 导师签名： 日期： 年 月 日 摘 要摘 要频繁集挖掘是数据挖掘领域的一个重要的研究方向，它的研究成果已被广泛应用到关联规则挖掘、关联分类和序列模式挖掘等许多应用中。在过去的十几年间研究人员对频繁集挖掘进行了深入广泛的研究，取得了一系列研究成果。近年来在高速网络、事务日志、金融和传感器网络等领域出现了一种称为数据流的新的数据类型。它具有与普通数据集截然不同的特点，如持续不断产生数据、数据产生速度快、数据太多以致只能顺序访问一遍数据、无法

4、控制数据产生的次序等。针对数据流的数据挖掘已经成为研究的热点。但因为现存的绝大多数频繁集挖掘算法面向保存在持久存储介质中的数据并且在算法运行过程中需要多次访问数据，它们无法被直接应用到数据流领域。本文详细讨论了基于数据流的频繁集挖掘，提出了一系列高性能、低空间需求和高准确度的单遍扫描算法：(a)结合频繁项挖掘算法，提出了两个基于数据流中观察到的所有数据的频繁集挖掘算法SinScanFISM算法和MulScanFISM 算法。SinScanFISM算法逐个处理新产生的事务,而MulScanFISM算法则批量处理新产生的事务。(b)频繁集挖掘算法往往会产生大量的频繁模式，这不仅会影响算法的性能，也

5、会影响对算法结果的理解，解决方法之一就是利用频繁集的无损简化表达方式。结合频繁集的无损简化表达方式提出了两个代表性的算法，其中 BorIFISM算法基于边界集表达方式，CloIFISM 算法基于闭合集表达方式。通过实验也表明这些算法在挖掘各种规模与特性的数据集时具有较高的效率与可伸缩性。关键词：数据挖掘，SinScanFISM算法，MulScanFISM 算法，BorIFISM算法，CloIFISM 算法IABTRACTABSTRACTFrequent itemset mining is one of the important subjects of data mining, which h

6、as been studied extensively in the last decade. It is used by many data mining applications, such as the discovery of association rules, correlations, sequential rules and episodes. Recently, there has been much interest in data arriving in the form of continuous streams, which is often referred to

7、data streams. Data streams arise in several application domains like high-speed networking, transaction logs, finance and sensor networks. Data streams possessdistinct computational characteristics, such as unknown or unbounded length, possibly very fast arrival rate, inability to backtrack over pre

8、viously arrived items (only one sequential pass over the data is permitted), and a lack of system control over the order in which the data arrive. Among the researches toward data streams, extending mining techniques to data streams has attracted much attention. However, most algorithms for frequent

9、 itemset mining have typically been developed for datasets stored in persistent storage and involve multiple passes over the dataset, so they cannot be directly applied to data streams.This thesis discusses the problem of frequent itemset mining over data streams in detail and proposes a series of o

10、ne-pass algorithms with fast update speed, low space requirements and accurate results.(a)Inspired by algorithms for frequent items mining, two algorithms for frequent itemset mining over the entire history of data streams are proposed. SinScanFISM algorithm processes new transactions one by one, an

11、d MulScanFISM algorithm processes a considerable number of transactions together.(b)The algorithms for frequent itemset mining may generate a great number of frequent itemsets, which may affect both the efficiency and effectiveness. One of alternatives is to use concise representations of frequent i

12、temsets.The paper proposes two representative algorithms, which BorIFISM algorithm is based on the generator representation and CloIFISM algorithm is based on the closed itemset representation.Extensive experimental results highlight significant gains in scalability and efficiency on both sparse and

13、 dense datasets at all levels of support threshold.Key words：association rule, SinScanFISM algorithm，MulScanFISM algorithm，BorIFISM algorithm，CloIFISM algorithmV目 录目 录第一章 绪论11.1 数据挖掘概述11.1.1 数据挖掘的定义11.1.2 数据挖掘的分类21.2 数据流概述31.2.1 基于数据流的频繁集算法41.3 本文的工作51.4 本文的结构5第二章 频繁集挖掘算法概述72.1频繁集挖掘的应用72.2频繁集挖掘算法82.

14、2.1 完整频繁集挖掘算法92.2.2 频繁集简化表达方式的挖掘算法142.2.3 增量频繁集挖掘算法182.3小结20第三章 完整频繁集挖掘算法213.1 频繁项算法概述223.1.1 Lossy Counting算法233.1.2 SinScanFISM 算法243.1.3 MulScanFISM 算法273.2 CP-tree303.3 实验323.3.1 实验数据323.3.2 实验环境333.3.3 实验内容与结果333.4 小结37第四章 频繁集简化表达方式挖掘算法394.1 BorIFISM算法394.1.1 理论依据404.1.2 算法描述414.1.3 算法的正确性454.2

15、 CloIFISM 算法464.2.1 算法描述464.2.2 算法的正确性534.3 实验534.4 小结56第五章 总结和展望57参考文献59第一章 绪论第一章 绪论1.1 数据挖掘概述最近几十年，随着科学技术的迅猛发展和信息技术的广泛应用，人类产生数据和获取数据的能力迅速提高，从制造业到服务业，从生物研究到空间探索，无时无刻不在产生着大量数据。与这种现象相对应的是，人类处理和分析数据的能力却相当有限。互联网的兴起更加加剧了“数据爆炸，知识匮乏”这一趋势。数据挖掘作为新一代的、智能辅助人类从海量数据中发现有用知识的技术正是在这种背景下产生并迅速发展起来，成为了知识发现的一个重要的研究领域。

16、数据挖掘是统计分析、数据可视化、人工智能、机器学习、高性能计算和数据库技术等众多领域交叉形成的新兴学科，在市场营销、金融预测和决策支持等领域具有广泛的应用前景。1.1.1 数据挖掘的定义数据挖掘，又称为数据库中知识发现(Knowledge Discovery in Database，简称KDD)，是指一个从大量的数据中提取出未知的、潜在有用的、可理解的模式的高级过程。其中：l 数据：是用来描述事物的信息，是进一步发现知识的基础。l 未知：经过数据挖掘提取出的模式必须是新颖的。l 潜在有用：提取出的模式应该是有意义的，可以用某些标准来衡量。可被人理解：数据集中隐含的模式要以容易被人理解的形式表现

17、出来，从而帮助人们更好地理解数据中所包含的信息。l 高级过程：一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式上升过程。数据挖掘是对数据进行更深层次处理的过程，而不仅仅对数据进行加减求和等简单运算或查询，因此说它是一个高级的过程。1.1.2 数据挖掘的分类数据挖掘通过关联分析、分类分析、聚类分析、异常性分析、趋势分析等知识发现活动，寻找频繁模式、关联规则、分类规则、聚类模式、异常模式、周期性规律等类型的知识。1.关联分析关联规则反映了数据中对象之间依赖或关联的知识。关联规则挖掘的一个典型应用是零售业，比如超市的销售管理。关联规则可辨别商品之间是否存在某种关联关系。例如，“购买

18、了商品A和B的顾客中有90%的人又购买了商品C和D就是一条关联规则。关联规则提供的信息可以用作设计商品销售目录、商场布置、市场营销的参考。关联规则是基于数据项目的同时出现特征，不是基于数据自身的固有属性(例如函数依赖关系)，不能通过数据库的逻辑操作(如表的联接)或统计的方法得出。2.分类分析和估值分析分类从数据中发现对象的共性，并将对象分成不同种类。在分类中，一个其中元组的种类都已知的样本数据集被当作训练集。分类的目标首先是对训练数据进行分析，使用数据的某些特征属性，给出每个类的准确描述，然后使用这些描述，对其它数据进行分类。估值与分类类似，不同之处在于分类描述离散型变量，估值会产生连续值的输

19、出。常用的方法有决策树归纳、贝叶斯分类、神经网络、K-最临近分类、粗糙集、关联分类和遗传算法等。3.聚类分析聚类是指将对象分成若干类对象，在每类对象内部，对象之间具有较高的相似性，而在不同类的对象之间，相似性则比较低。它与分类不同，聚类事先不知道对象所属的类。在数据挖掘中，聚类也是一个活跃的研究领域。聚类算法可以分为基于划分的方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。4.数据概括数据概括是把数据集从较低概念层次抽象到较高概念层次的过程。通常数据集中的数据是比较具体和详细的。但在某些应用中，用户需要在更高的抽象级别上分析数据，这就要进行一定的抽象化即数据概括。1.2 数据流

20、概述伴随着计算机技术的日新月异，数据管理技术发展迅速并且得到了广泛应用。一方面，出现了多种数据管理模型，从层次数据库、网状数据库、关系数据库、对象数据库，直到关系对象数据库等；另一方面，数据量也越来越大，很多大型数据库的容量已经达到甚至超出了TB级。这些数据管理技术的一个共同点是：据存储在辅助存储介质中，可以多次访问。在上世纪末，一种新的数据类型的出现却对已有的数据管理模型提出了有力的挑战。在网络通信、金融、科学观察、电信等领域中，如网络监听和流量控制、股票的价格预测、传感器网络、电话通信等应用，数据以流的形式产生，实时的、连续的、有序的数据不断到达，没有终点。这种一系列连续且有序的数据组成的

21、序列被称为数据流。区别于传统数据类型，数据流具有以下特点：(a)数据流中的数据可能随时到达，无法预测数据到达的时间；(b)无法控制数据项到达的次序，其次序是随机的；(c)不限制数据量的大小，可以认为其是无限的；(d)数据一经处理，通常不能被再次访问，再次提取数据代价昂贵。大多数数据挖掘算法的设计都基于两个基本假设。其一，在数据挖掘过程中，数据集是静态的。无论是否有新数据产生或者部分数据失效，数据挖掘使用的是挖掘过程开始时的数据集的一个快照。其二，执行环境总是能为算法运行提供足够的资源。算法可以不受限制多次访问数据，随时可以得到足够的内存和执行能力。但对于数据流，这两个假设都不成立，因而绝大多数

22、数据挖掘算法都无法直接应用到数据流领域。虽然不可能将数据流产生的数据全部保存在内存中，但是可以通过建立保存在内存中的数据摘要提供给数据流算法访问已处理数据的能力。尽管数据摘要通常无法保证处理的准确性，但可以保证结果的实时性。设计单遍扫描数据的算法，建立有效的数据摘要，实时地给出近似结果就成为数据流模型下数据挖掘的目标5-9。1.2.1 基于数据流的频繁集算法频繁集挖掘首先由10提出，它是很多其它挖掘问题的基础。随着产生数据流的应用不断增多，基于数据流的频繁集挖掘也得到越来越多的关注。区别于传统的静态数据，数据流具有连续性、无序性、无界性及实时性的特点，通常要求算法能够及时地反映数据变化。已有的

23、基于数据流的频繁集挖掘算法可分为两类：批处理方法和启发式方法。批处理方法的主要思想是将数据流中的数据按照产生的次序分成不同的部分，通过不同部分上的局部频繁模式来计算全局频繁模式。批处理方法虽然处理速度较快，但需要积攒足够数据，在一定程度上损害了结果的实时性。启发式方法的主要思想是随着数据的不断到达，由已知频繁模式逐步生成新的频繁模式。启发式方法能够随数据的到达直接进行处理，可以实时地反映频繁模式的变化，但由于其处理速度有限，在处理限高速到达的数据流时存在困难，而且模式计数通常不包含历史信息使得模式估计与查询精度较低。基于普通数据集的频繁集挖掘已经是一个相对成熟的研究领域，而基于数据流的频繁集挖

24、掘仍然存在许多尚待解决之处。目前该研究方向存在的主要问题有：(a)数据流挖掘算法通常返回近似结果，因而需要一个衡量算法准确性的标准。目前尚不存在这样一个标准，致使无从比较算法之间的优劣。(b)虽然普通数据集挖掘算法和数据流挖掘算法存在很多不同之处，但是普通数据集挖掘算法的很多研究成果仍然可以应用到数据流领域，在该方面的所做工作远远不够。(c)提出的算法往往有一定的限制条件，没有提出完整的解决方案。本文系统地研究了基于数据流的频繁集挖掘问题，提出了一系列高时间效率、低空间需求的算法。1.3 本文的工作本文中论述的内容大体可以分为两部分：(a)挖掘完整频繁集的算法，包括逐个处理事务的SinScan

25、FISM 算法和批量处理事务的MulScanFISM算法。SinScanFISM算法使用了延迟加入显著模式的方法，有效地减少了显著模式的数量；而MulScanFISM算法则随着批量处理的事务数量的增多，新加入的显著模式在随后的更新过程中被删除的概率则会变小。(b)挖掘频繁集简化表达方式的算法，包括挖掘带有边界集的简化表达方式的BorIFISM算法和挖掘闭合集表达方式的CloIFISM算法。BorIFISM算法首次将边界集和产生集表达方式结合在一起，避免在更新过程中产生过多的候选模式；CloIFISM算法则提出使用模式的支持度来寻找闭合模式的方法，支持搜索空间的有效剪裁。第四章的研究成果是基于频

26、繁集简化表达方式的增量挖掘算法的系统总结，其成果不仅仅是适用于数据流，也适用于普通数据集。1.4 本文的结构在第二章全面地介绍了频繁集的理论和主要算法。着重介绍了三类算法：完整频繁集的挖掘算法、频繁集简化表达方式的挖掘算法和增量频繁集挖掘算法。在第三章中讨论了挖掘基于数据流已处理过的所有数据的完整频繁集的算法。该章引入了显著模式和显著集的概念，使得有了一个量化的标准去衡量算法的准确性；其次提出了逐条处理新产生事务的SinScanFISM算法和批量处理新产生事务的MulScanFISM算法。在第四章中介绍了频繁集的简化表达方式在数据流中的应用。频繁集的简化表达方式可分为两类：带有边界集的表达方式

27、和闭合集表达方式。与它们相对应，提出了BorIFISM算法和CloIFISM算法。最后一章回顾了本文的主要工作，阐述了本文的创新之处，指出了进一步研究的方向。61第二章 频繁集挖掘算法概述第二章 频繁集挖掘算法概述定义2-1 给定项目集I=i1，i2，im，其中ik(1km)是一个项目。I 的非空子集被称为模式。一个模式所包含的项目数被称为该模式的长度。长度为k的模式可简写为k-模式。定义2-2 事务是I的非空子集，每个事务都有唯一的标志符。数据集D是一组事务的集合，即D=T1，T2，Tn，TkI(1kn)。数据集的大小即为数据集中包含的事务的数量，记为|D|。定义2-3 数据集D中包含模式P

28、的事务的数量称为在D中P的计数，记为发fD(P)或简写为f(P)。数据集D中包含模式P的事务在所有事务中所占的比例称为在D中P的支持度，记为sD(P)或简写为s(P)。显然s(P)=f(P)/|D|。假定q(01)是事先设定的支持度阈值，如果s(P)，则称P是频繁模式。所有频繁模式的集合称为频繁集，记为F。定理2-1 频繁模式具有反单调性，即频繁模式的子集是频繁的；非频繁模式的超集是非频繁的。证明：结论是显而易见的。2.1频繁集挖掘的应用频繁集挖掘是数据挖掘的一个重要研究领域，频繁集可以用来解决其它数据挖掘问题。1.关联规则关联规则是如下形式的逻辑蕴涵：XY，其中XI，YI并且XY=。通常采用

29、两个标准来衡量关联规则：(1)支持度，即s(XY)，表明在数据集中事务同时包含模式X和Y的概率；(2)置信度，即s(XY)/s(X)，表明在包含模式X的事务包含模式Y的概率。同时满足支持度阈值和最小置信度的规则称为强规则。关联规则挖掘问题实际上就是产生强规则的问题。关联规则挖掘问题一般可以分为两个步骤：(1)找出数据集中所有的频繁模式的集合；(2)根据频繁模式，产生所有强关联规则。由于关联规则挖掘算法的性能主要由第一步的性能决定，所以目前对关联规则算法的研究主要集中在频繁集挖掘算法上。2.关联分类关联分类实际上是关联规则的一个特殊应用。对于关联规则XY，如果Y是类标识，该规则可以用于数据分类。

30、3.序列模式给定一个序列数据集，它记录了多个数据序列，每个序列由若干按时间排序的事务组成，每个事务由若干项目组成。序列模式是在序列数据集中出现次数超过预先设定值的模式序列，其组成的基本元素就是频繁模式。2.2频繁集挖掘算法从1994年Agrawal等人10提出第一个频繁集挖掘算法到现在，关于频繁集挖掘算法的研究已经有了突飞猛进的发展。从时间复杂度和空间复杂度来考虑，提高频繁集挖掘算法的性能的手段主要有两种：(a)减少I/O操作。被挖掘的数据集通常包含大量的数据，频繁的I/O操作必将增加算法的运行时间。减少I/O操作主要是减少扫描数据集的次数和扫描数据集时需要访问的数据。(b)减少候选模式的数量

31、。候选模式数量的减少可以节省处理候选模式所需的计算时间和存储空间。一般来说，减少I/O操作和减少候选项目集的数量是一对矛盾，如何处理这一对矛盾，寻找最佳的平衡点是提高频繁集挖掘算法效率的关键。关于频繁集挖掘的算法很多，随后章节中将着重介绍三类算法：(a)完整频繁集挖掘算法。这类算法返回完整的频繁集。(b)频繁集简化表达方式的挖掘算法。这类算法的结果是频繁集的子集，但可以在不重新访问数据集的情况下生成完整的频繁集。(c)增量频繁集挖掘算法。这类算法假定数据集是变化的，它在运行过程中不仅要访问现在的数据集，也会利用以前生成的频繁集。2.2.1 完整频繁集挖掘算法本节概括介绍了一系列完整频繁集挖掘算

32、法，其中最具代表性的算法是Apriori算法和FP-growth算法。1.Apriori 算法Apriori 算法是 Agrawal 等人于 1994 年提出的关联规则挖掘算法5，是关联规则挖掘的经典算法。Apriori算法中产生频繁集的伪代码见算法2-1。其中Li代表长度为i的频繁模式，Ci代表长度为i的候选模式的集合。Apriori算法的基础是频繁模式的反单调性属性，遵循自底向上广度优先的搜索策略。它首先产生长度为1的频繁集 L1，然后是长度为2的频繁集L2，直到有某个 k 值使得Lk为空，此时算法终止。在每次循环中，首先产生长度为k的候选集 Ck，Ck 中的每一个模式是由只有最后一项不同

33、的两个长度为k-1的频繁模式连接来产生的。然后检测Ck 中的每个候选模式的长度为k-1的子集是否都属于 Lk-1，如存在子集不属于Lk-1，则该模式必为非频繁的，从Ck中删除该模式。Ck中的剩余模式需要扫描数据集求得它们的支持度来决定它们是否是频繁模式。最后的频繁集 Lk必定是 Ck的一个子集。算法2-1 Apriori算法Input: and DOutput: F1.L1=frequent 1-itemsets2.For (k=2; Lk-1; k+) 3. Ck=Apriori-Gen(Lk-1)/新的候选集4. For each TD5. For each PCk6. If PT The

34、n /检查事务中是否包含候选模式7. f(P)=f(P)+18. Lk=P|PCk f(P)|D|9.F=kLkApriori-Gen10.Ck=P1P2|P1, P2Lk-1P1.item1= P2.item1P1.itemk-2=P2.itemk-2P1.itemk-1P2.itemk-111.For each PCk12. For each (k-1)-subset S of P13. If SLk-1 then14. delete P from Ck例2-1以表2-1中数据集为例，挖掘=0.3时的频繁模式，即频繁模式的计数必须不小于2。(1)因为f的计数为1，项目f不是频繁模式。L1=

35、a(4)，b(5)，c(4)，d(5)，e(3)。(2)C2=ab，ac，ad，ae，bc，bd，be，cd，ce，de。因为f(ce)=1，ce被从C2中删除。L2=ab(3)，ac(3)，ad(3)，ae(2)，bc(3)，bd(4)，be(3)，cd(4)，de(2)。(3)C3=abc，abd，abe，acd，bcd，bde。C3中的所有模式都是频繁的。L3=abc(2)，abd(2)，abe(2)，acd(3)，bcd(3)，bde(2)。(4)C4=abcd，abde。因为f(abde)=1，abde被从C4中删除。L4=abcd(2)。(5)C5=，算法终止。(6)F=L1L2L

36、3L4=a(4)，b(5)，c(4)，d(5)，e(3)，ab(3)，ac(3)，ad(3)，ae(2)，bc(3)，bd(4)，be(3)，cd(4)，de(2)，abc(2)，abd(2)，abe(2)，acd(3)，bcd(3)，bde(2)，abcd(2)。表2-1 示例数据集ID事务1abcde2bdef3acd4bcd5abe6abcdApriori算法有两个显著的特点，一是扫描数据集的次数等于频繁模式的最大长度；二是需要产生候选集。当支持度阈值取值较小时，频繁集中可能包含长度很大的频繁模式，并且算法可能需要检测大量的候选模式，此时Apriori算法的性能会显著降低。在Aprior

37、i算法公布之后，很多人在该算法的基础上作了进一步的研究。2.FP-Growth算法Han等人提出了一种全新的频繁集挖掘算法FP-Growth11，克服了Apriori算法必须产生候选集的缺点，提出了一种基于FP-tree的无候选集的新方法。FP-Growth 算法的特点体现在两个方面：(a)它利用了一种紧凑的数据结构FP-tree，存储了模式的计数信息。FP-tree结构包括一个由频繁项组成的表与一个根节点标识为“null”和其它节点为频繁项的树。表中的每条记录包含两个域：项和指针。指针指向树中第一个同项目同名的节点。树中的每个节点包括三个域：项目名、计数和节点链接。其中项目名记录了节点所代表

38、的项目；计数记录了树中到达这个节点的路径所代表的事务的数目；节点链接指向树中下一个同名节点，如果没有同名节点则指向空。支持度高的节点靠近数的根节点，从而支持度高的模式比支持度低的模式更可能共享同一个节点。注意 FP-tree 中只保存了满足支持度阈值的项目。所以，首先需要对数据集进行第一次扫描得出满足支持度阈值的项并将它们按降序排列在 FP-tree 结构的表中，然后对数据集进行第二次扫描，对每个事务处理中包含的频繁项按照其在表中的先后顺序插入到树中。(b)它使用了基于FP-tree的模式片断成长算法，首先处理叶节点，从长度为 1的频繁模式开始，从包含它的分枝生成条件子树，并且在子树中递归挖掘

39、，模式的成长通过结合条件子树中产生的后缀模式来实现。挖掘过程中采用了分而治之(Divide and Conquer)的方法，而不是 Apriori 算法中自底向上的方法，它将发现长频繁模式的问题转化为寻找短模式再进行连接，避免了产生长候选模式。FP-Growth算法的主要问题是：在挖掘频繁模式时，它需要递归地生成条件FP 树，并且每产生一个频繁模式就可能生成一个条件 FP 树。在支持度阈值较小或处理密集数据集时，即使对于很小的数据集，也会产生大量的频繁模式，这时FP-Growth算法可能需要动态生成和释放大量的条件子树，将耗费大量时间和空间。例2-2以表2-1中数据集为例，使用FP-growt

40、h算法挖掘q=0.3时的频繁模式。(1)除f外所有的项目都是频繁的。按照计数的降序排序，其次序如下：b(5)，d(5)，a(4)，c(4)，e(3)。去掉非频繁项并且排序后的示例数据集见表2-2。表2-2 排序后的示例数据集ID事务排序后频繁项目1abcdebdace2bdefbde3acddac4bcdbdc5abebae6abcdbdac(2)将每个事务中排序后的频繁项插入到FP-tree，形成的结果如图2-1所示：(3)首先挖掘e的条件子树。可以得到频繁模式e：3和三个包含e的路径：b：5，d：4，a：2，c：2，e：1，b：5，d：4，e：1，b：5，a：1，e：1。则包含 e 的条件

41、路径为：b：1，d：1，a：1，c：1，b：1，d：1，b：1，a：1，e 对应的条件子树如图2-1(因为c的计数为1，故它不在条件子树中出现)。使用e的条件子树可以得到频繁模式ea：2和两个包含 a 的路径：b：3，d：2，a：1和b：3，a：1。则包含a的条件路径为：b：1，d：1和b：1，ea对应的条件子树如图2-1。使用ea的条件子树可以得到频繁模式eab：2。再次使用e的条件子树可以得到频繁模式ed：2和一个包含d的路径：b：3，d：2。注意包含a的节点无需再考虑了，因为已经得到了包含ea的频繁模式。则包含d的条件路径为：b：2，ed对应的条件子树如图2-1。利用该子树得到频繁模式e

42、db：2。最后使用 e 的条件子树还可以得到频繁模式eb：3。(4)接着利用FP-tree挖掘c的条件子树。注意此时无需考虑FP-tree中包含e的节点。随后利用FP-tree依次挖掘a，d，b的子树。其具体的过程可参考步骤3。图2-1 FP-Growth算法的运算过程2.2.2 频繁集简化表达方式的挖掘算法因为数据集中模式的数目和项目的数量成指数关系，算法可能产生大量的频繁模式，这不仅严重影响算法的效率，也会影响对结果的理解。人们提出了多种简化表达方式来取代频繁集。在介绍的几种无损简化表达方式中，关于闭合集表达方式和最大集表达方式的挖掘算法的研究最为充分。2.2.2.1 频繁集简化表达方式概

43、述无损简化表达方式将是介绍的重点。所谓无损简化表达方式，是指可以重新生成整个频繁集并给出每个频繁模式的准确支持度的简化表达方式。它们主要有闭合集表达方式12,13、产生集表达方式14和无析取集表达方式15等。1.闭合集表达方式定义2-4 如果模式P的任何真超集的支持度都小于P的支持度，则称P是闭合模式。P 的闭包，c(P)，定义为包含P的长度最小的闭合模式。实际上c(P)就是数据集中包含P的所有事务的交集。如果P=c(P)，那么P是闭合模式。如果一个模式既是闭合的也是频繁的，则它被称为频繁闭合模式。所有频繁闭合模式的集合被称为频繁闭合集，记为FC。定义2-5 闭合集表达方式包含频繁闭合集及每个

44、频繁闭合模式的支持度。可以通过下面的方法来决定任意频繁模式的支持度。定理2-2 模式P，如果ZFC，ZP，那么PF并且s(P)= max(s(Y)|YFCYP)，否则PF。例2-3以表2-1中的数据集为例，给出=0.3的闭合集表达方式。FC=a(4)，b(5)，d(5)，ab(3)，bd(4)，be(3)，cd(4)，abe(2)，acd(3)，bcd(3)，bde(2)，abcd(2)。2.产生集表达方式定义2-6 如果模式 P 的任意真子集的支持度都大于P的支持度，则称 P 是产生模式(Generator或Free Itemset)。所有产生模式的集合被称为产生集，记为 G。如果一个模式既

45、是频繁模式又是产生模式，则它被称为频繁产生模式。所有频繁产生模式的集合被称为频繁产生集，记为FG。所有真子集均为频繁产生模式的非频繁产生模式的集合称为负产生边界集，记为GB-，即GB-=X|XGXF(YX，YFG)。产生模式同频繁模式一样，也具有反单调性。产生模式和频繁模式结合在一起，可以有效地减少候选集的数量。定理2-3 产生模式的任意子集都是产生模式；非产生模式的任意超集都是非产生模式。证明：先用反证法证明定理的第一部分。假定P是产生模式，X是P的子集但X不是产生模式。则根据产生模式的定义存在 X 的一个子集 Y，s(Y)=s(X)，即包含Y的事务都包含X。记Z=(P-X)Y，Z是P的子集。因为包含Y的事务都包含X，所以s(Z)s(P-X)Y)=s(P-X)X)=s(P)。这显然与P是产生模式的假设相矛盾，故X 必须是产生模式。类似的方法可以证明定理的第二部分。仅通过频繁产生集本身，无法决定一个模式是否频繁，需要把它和边界集结合起来，才可以确定频繁模式及其支持度。定义2-7 产生集表达方式的组成包含两部分：(a)频繁产生集 FG 及其中每一个模式的支持度；