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

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

2、是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。签名： 日期：年 月 日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段

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

4、挖掘算法面向保存在持久存储介质中的数据并且在算法运行过程中需要多 次访问数据，它们无法被直接应用到数据流领域。本文详细讨论了基于数据流的频繁集挖掘，提出了一系列高性能、低空间需 求和高准确度的单遍扫描算法：结合频繁项挖掘算法，提出了两个基于数据流中观察到的所有数据的频繁 集挖掘算法SinScanFISM算法和MulScanFISM算法。SinScanFISM算法逐个处理 新产生的事务，而MulScanFISM算法则批量处理新产生的事务。频繁集挖掘算法往往会产生大量的频繁模式，这不仅会影响算法的性能， 也会影响对算法结果的理解，解决方法之一就是利用频繁集的无损简化表达方式。结合频繁集的无损简化表

5、达方式提出了两个代表性的算法，其中BorIFISM算法基于边界集表达方式，CloIFISM算法基于闭合集表达方式。通过实验也表明这些算法在挖掘各种规模与特性的数据集时具有较高的效率 与可伸缩性。关键词：数据挖掘，SinScanFISM算法，MulScanFISM 算法，BorIFISM算法,CloIFISM 算法 # iiABSTRACTABSTRACTFrequent itemset mining is one of the important subjects of data mining, which has bee n studied exte nsively in the last

6、decade. It is used by many data mining applicati ons, such as the discovery of associati on rules, correlati ons, seque ntial rules and episodes.Recently, there has been much interest in data arriving in the form of continuous streams, which is often referred to data streams. Data streams arise in s

7、everal application domains like high-speed networking, transaction logs, finance and sensor n etworks. Data streams possessdisti net computati onal characteristics, such as unknown or unboun ded len gth, possibly very fast arrival rate, in ability to backtrack over previously arrived items (only one

8、 seque ntial pass over the data is permitted), and a lack of system con trol over the order in which the data arrive. Among the researches toward data streams, exte nding mining tech niq ues to data streams has attracted much atte nti on. However, most algorithms for frequent itemset mining have typ

9、ically been developed for datasets stored in persiste nt storage and invo Ive multiple passes over the dataset, so they cannot be directly applied to data streams.This thesis discusses the problem of freque nt itemset mi ning over data streams in detail and proposes a series of on e-pass algorithms

10、with fast update speed, low space requireme nts and accurate results.Inspired by algorithms for frequent items mining, two algorithms for frequent itemset mining over the en tire history of data streams are proposed. Sin Sca nF ISM algorithm processes new transactions one by one, and MulScanFISM alg

11、orithm processes a con siderable nu mber of tran sact ions together.The algorithms for freque nt itemset mining may gen erate a great nu mber of frequent itemsets, which may affect both the efficiency and effectiveness. One ofABTRACT iiiABTRACT #alter natives is to use con cise represe ntati on sof

12、freque nt itemsets.The paper proposes two representative algorithms, which BorlFISM 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 efficie ncy on bot

13、h sparse and dense datasets at all levels of support threshold.Key words: association rule,SinScanFISM algorithm, MulScanFISM algorithm , BorIFISM algorithm , CloIFISM algorithm目录 目录 TOC o 1-5 h z HYPERLINK l bookmark16 o Current Document 第一章绪论 1 HYPERLINK l bookmark18 o Current Document 1.1数据挖掘概述 1

14、 HYPERLINK l bookmark20 o Current Document 1.1.1数据挖掘的定义1 HYPERLINK l bookmark22 o Current Document 1.1.2数据挖掘的分类21.2数据流概述 31.2.1基于数据流的频繁集算法 41.3本文的工作 51.4本文的结构 5第二章频繁集挖掘算法概述 72.1频繁集挖掘的应用 7 HYPERLINK l bookmark24 o Current Document 2.2频繁集挖掘算法 8 HYPERLINK l bookmark26 o Current Document 2.2.1完整频繁集挖掘算法9

15、 HYPERLINK l bookmark28 o Current Document 2.2.2频繁集简化表达方式的挖掘算法 14 HYPERLINK l bookmark30 o Current Document 2.2.3增量频繁集挖掘算法 18 HYPERLINK l bookmark32 o Current Document 2.3小结 20第三章完整频繁集挖掘算法 21 HYPERLINK l bookmark34 o Current Document 3.1频繁项算法概述 22 HYPERLINK l bookmark36 o Current Document Lossy Coun

16、 ti ng 算法23 HYPERLINK l bookmark38 o Current Document SinScanFISM 算法24 HYPERLINK l bookmark40 o Current Document MulScanFISM 算法273.2 CP-tree 3.3实验3.3.1实验数据3.3.2实验环境3.3.3实验内容与结果30323233333.4小结第四章频繁集简化表达方式挖掘算法 3739BorlFISM 算法理论依据404.1.2算法描述414.1.3算法的正确性45394.2 CloIFISM 算法4.2.1 算法描述 464.2.2算法的正确性53464.

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

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

19、步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式上升过程。数据挖掘是对数据进行更深层次处理的过程， 而不仅仅对数据进行加减求和等简单运算或查询，因此说它是一个高级 的过程。1.1.2数据挖掘的分类数据挖掘通过关联分析、分类分析、聚类分析、异常性分析、趋势分析等知 识发现活动，寻找频繁模式、关联规则、分类规则、聚类模式、异常模式、周期 性规律等类型的知识。关联分析关联规则反映了数据中对象之间依赖或关联的知识。关联规则挖掘的一个典 型应用是零售业，比如超市的销售管理。关联规则可辨别商品之间是否存在某种 关联关系。例如， 购买了商品A和B的顾客中有90%的人又购买了商品C和D就是 一条关

20、联规则。关联规则提供的信息可以用作设计商品销售目录、商场布置、市 场营销的参考。关联规则是基于数据项目的同时出现特征，不是基于数据自身的固有属性（例如函数依赖关系），不能通过数据库的逻辑操作（如表的联接）或统计的方法得出。分类分析和估值分析分类从数据中发现对象的共性，并将对象分成不同种类。在分类中，一个其 中元组的种类都已知的样本数据集被当作训练集。分类的目标首先是对训练数据 进行分析，使用数据的某些特征属性，给出每个类的准确描述，然后使用这些描 述，对其它数据进行分类。估值与分类类似，不同之处在于分类描述离散型变 量，估值会产生连续值的输出。常用的方法有决策树归纳、贝叶斯分类、神经网 络、K

21、-最临近分类、粗糙集、关联分类和遗传算法等。聚类分析聚类是指将对象分成若干类对象，在每类对象内部，对象之间具有较高的相 似性，而在不同类的对象之间，相似性则比较低。它与分类不同，聚类事先不知 道对象所属的类。在数据挖掘中，聚类也是一个活跃的研究领域。聚类算法可以 分为基于划分的方法、层次方法、基于密度的方法、基于网格的方法和基于模型 的方法。4数据概括数据概括是把数据集从较低概念层次抽象到较高概念层次的过程。通常数据 集中的数据是比较具体和详细的。但在某些应用中，用户需要在更高的抽象级别 上分析数据，这就要进行一定的抽象化即数据概括。12数据流概述伴随着计算机技术的日新月异，数据管理技术发展迅

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

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

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

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

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

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

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

29、式。与它们相对 应，提出了 BorlFISM算法和CloIFISM算法。最后一章回顾了本文的主要工作，阐述了本文的创新之处，指出了进一步研 究的方向。第二章频繁集挖掘算法概述 电子科技大学工程硕士学位论文 第二章频繁集挖掘算法概述定义2-1给定项目集l=ii, i2,，im，其中ik(1求命)是一个项目。I的非 空子集被称为模式。一个模式所包含的项目数被称为该模式的长度。长度为k的模式可简写为k-模式。定义2-2事务是I的非空子集，每个事务都有唯一的标志符。数据集 D是一 组事务的集合，即 D=Ti, T2,，Tn , Tkl(1來夺)。数据集的大小即为数据集 中包含的事务的数量，记为|D|。

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

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

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

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

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

35、一项不同的两个长度为k-1的频繁模式连接来产生的。然后检测Ck中的每个候选模式的长度为k-1的子集是否都属于Lk-1，如存在子集不 属于Lk-1，则该模式必为非频繁的，从Ck中删除该模式。Ck中的剩余模式需要扫描数据集求得它们的支持度来决定它们是否是频繁模式。最后的频繁集Lk必定是Ck的一个子集。算法2-1 Apriori算法In put: and DOutput: FL1=freque nt 1-itemsetsFor (k=2; L k-1; k+)Ck=Apriori-Gen( Lk-1)/新的候选集For each TDFor each PCkIf PT Then /检查事务中是否包含

36、候选模式f(P)=f(P)+1Lk= P|PCkf(P)|D|F=kLkApriori-Ge n= Ck=P1P2P1, P2Lk-1P1.item1= P2.item1P1.itemic2 P2.itemk-2P1.itemk-1 P2.itemk-1For each PCkFor each (k-1)-subset S of PIf SLk-1 thendelete P from Ck例2-1以表2-1中数据集为例，挖掘=0.3时的频繁模式，即频繁模式的计数 必须不小于2。因为f的计数为1,项目f不是频繁模式。L1=a(4), b,c(4), d(5), e(3)。C2=ab, ac, a

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

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

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

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

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

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

43、1 , b: 5, a： 1, e： 1。则包 含 e 的条件路径为：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。注意 包

44、含a的节点无需再考虑了，因为已经得到了包含 ea的频繁模式。则包含d的条件 路径为：b： 2 , ed对应的条件子树如图2-1。利用该子树得到频繁模式edb：2。最后使用e的条件子树还可以得到频繁模式eb： 3。（4）接着利用FP-tree挖 掘c的条件子树。注意此时无需考虑FP-tree中包含e的节点。随后利用FP-tree依次挖掘a , d , b的子树。其具体的过程可参考步骤3roof;IMrecO血创b b:2OtfWt图2-1FP-Growth算法的运算过程2.2.2频繁集简化表达方式的挖掘算法因为数据集中模式的数目和项目的数量成指数关系，算法可能产生大量的频 繁模式，这不仅严重影响

45、算法的效率，也会影响对结果的理解。人们提出了多种 简化表达方式来取代频繁集。在介绍的几种无损简化表达方式中，关于闭合集表 达方式和最大集表达方式的挖掘算法的研究最为充分。2.2.2.1频繁集简化表达方式概述无损简化表达方式将是介绍的重点。所谓无损简化表达方式，是指可以重新 生成整个频繁集并给出每个频繁模式的准确支持度的简化表达方式。它们主要有 闭合集表达方式12,13、产生集表达方式14和无析取集表达方式15等。闭合集表达方式定义2-4如果模式P的任何真超集的支持度都小于 P的支持度，则称P是闭 合模式。P的闭包，c(P)，定义为包含P的长度最小的闭合模式。实际上c(P)就是数据集中包含P的所

46、有事务的交集。如果P=c(P)，那么P是闭合模式。如果一 个模式既是闭合的也是频繁的，则它被称为频繁闭合模式。所有频繁闭合模式的 集合被称为频繁闭合集，记为FC。定义2-5闭合集表达方式包含频繁闭合集及每个频繁闭合模式的支持度。可 以通过下面的方法来决定任意频繁模式的支持度。定理 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，be(3)，cd(4)，abe(2)，acd(3)，bcd(3)，bde(2)， ab

47、cd(2)。产生集表达方式定义2-6如果模式P的任意真子集的支持度都大于 P的支持度，则称P是 产生模式(Generator或Free Itemset)。所有产生模式的集合被称为产生集，记为 G。如果一个模式既是频繁模式又是产生模式，则它被称为频繁产生模式。所有 频繁产生模式的集合被称为频繁产生集，记为FG。所有真子集均为频繁产生模式的非频繁产生模式的集合称为负产生边界集，记为GB-，即卩GB-=X|XGXF(YX,YFG)。产生模式同频繁模式一样，也具有反单调性。产生模式和频繁模式结合 在一起，可以有效地减少候选集的数量。定理2-3产生模式的任意子集都是产生模式；非产生模式的任意超集都是非

48、产生模式。证明：先用反证法证明定理的第一部分。假定 P是产生模式，X是P的子集 但X不是产生模式。则根据产生模式的定义存在 X的一个子集丫，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及其中每 一个模式的支持度；(

49、b) GB-=XG|XF(YX，YFG)。定理2-4模式P，如果ZGB-并且ZX，那么PF ;否则，PF并且 s(P)=min(s(丫)|YFGYX)。例2-4以表2-1中的数据集为例，给出 =0.3的产生集表达方式。FG=a(4)，b(5)，c(4)，d(5)，e(3)，ab(3)，ac(3)，ad(3)，ae(2)，bc(3)，bd，de(2), abc(2)，abd(2)，GB-=(ade，ce。无析取集表达方式定义2-8对于模式P,如果有项印、a2和模式X，并且XP和P-X=a1，a2，则规则Xaia2被称为基于P的二元析取规则。其中 X可以为空或者ai等于 a2。该规则的支持度被定义

50、为包含X和ai或者X和a2的事务的数量，s(Xaia2)=s(Xai)+s(Xa2)-s(Xaia2)，它的可信度定义为conf(Xaia2)=s(Xaia2)/s(X)。如果规则的可信度等于1,则该规则被称为确定的。Xaia2是确定规则意味着包含 X的事务必然或者包含ai或者包含a2。定义2-9对于模式P，如果可以找到基于它的确定的二元析取规则，则它被 称为二元析取模式，否则被称为非二元析取模式 (Disju nctio n-free Itemset)。非二元 析取模式也具有反单调性：非二元析取模式的任意子集都是非二元析取模式，二 元析取模式的任意超集都是二元析取模式。所有非二元析取模式的集

51、合被称为非 二元析取集，记为BDFree。频繁非二元析取集被记为 FBDFree。产生模式是无析取模式的特例。如果模式P是非产生模式，则存在项目a，aP，s(P-a)= s(P)，那么规则P-aa必然是确定的，P不是无析取模式。同样， 如果P是无析取模式，那么P必然是产生模式。定义2-10二元无析取集表达方式BDFR的定义如下：FBDFree及其中模式的支持度；+ - FBDFreeB =XXFXBDFree(YX, YFBDFree)及其中模式的支持度；FBDFreeB-=XXF(YX, YFBDFree)。例2-5以表2-1中的数据集为例，给出=0.3的无析取集表达方式。FBDFree=a

52、(4)，b(5)，c(4)，d(5)，e(3)，ab(3)，ac(3)，ae(2)，+FBDFreeB =ad(3)，bc(3)，bd(4), be(3)，cd(4)，de(2)，FBDFreeB-= ce。例2-6二元无析取集表达方式也是一种频繁集的无损表达方式，通过举例来说明计算频繁模式及其支持度的方法。判断模式ace和abc是否频繁并求出其中频繁模式的支持度。因为ace是ce的超集，故ace不是频繁模式。因为abc是bc的超集，故abc是二元析取模式。因为规则be是确定的，则 规则 abc也是确定的，s(a)=s(a bc)。由 s(abc)=s(ab)+s(ac)-s(abc)可以得到

53、 s(a bc)= s(ab)+s(ac)-s(abc)，贝U s(abc)=s(ab)+s(ac)-s(a bc)= s(ab)+s(ac)-s(a)=(3+3- 4)/6=1/3。83将无析取集表达方式和产生集表达方式相结合，提出了无析取产生 集表达方式。引入产生集表达方式的作用在于减少边界集中模式的数量。2.222闭合集挖掘算法在本节介绍的算法中，Close算法源于Apriori算法，CLOSET算法源于FP- growth 算法。Close 算法基于闭合模式的思想，Pasquier提出了基于Apriori算法的Close算法12。Close算法借鉴了 Apriori算法的设计思想，采用

54、自底向上广度优先的搜索策略。 长度为k+l的频繁产生模式是从长度为 k的频繁产生模式进行连接得到的长度为 k+1的候选集中得到的。Close算法在生成长度为k的频繁产生集之后就扫描数据 集求得它们的闭包，从而得到对应的闭合模式。Close算法扫描数据集的次数和候选集中模式的个数一般要少于Apriori算法。CLOSET 算法Pei等人提出了挖掘频繁闭合集CLOSET算法13。CLOSET算法基于FP-Growth算法，但它对条件子树的生成做了针对性的修改，通过额外检查步骤去掉 了那些不是闭合模式的频繁模式。另外，它提出了分割FP-tree的方法来处理大型数据集。它和FP-Growth算法有同样

55、的缺点，可能需要构造大量的条件子 树。CHARM 算法CHARM算法16是Zaki等提出基于垂直数据表达方式的深度优先算法。CHARM使用了一种新颖的树结构一IT(ltemset-Tidset)树。结点表示成Xt(X),X代 表模式，t(X)是包含模式X的事务标识符的集合。节点 X的子节点为Xht(Xh)，Xl2t(Xl2),，Xlnt(Xln),其中Ik为某一项目。实际上 CHARM 算法就是对IT树 的深度优先遍历。在遍历过程中，算法利用下面的性质裁减IT树。对于两个不同的模式X、丫，如果t(X)=t(Y),那么c(X)=c(Y)=c(XY)，用XY代替X,删除代表丫的节点及子 树；如果t

56、(X)t(Y)，那么c(X)c(Y)并且c(X)=c(XY)，可用XY替代X,但不删除代表 丫的节点；如果t(Y)t(X)，那么c(X)c(Y)并且c(Y)=c(XY)，删除代表丫的节点及子树；如果t(X)t(Y),那么c(X)c(Y)并且c(X)=c(XY)，既不能裁剪分枝，也不能减少 子树的高度。CHARM算法在执行过程中按支持度的升序来重新排列候选模式，以求尽早 删除非频繁模式。2.2.3增量频繁集挖掘算法在现实生活中恒定不变的数据是很少存在的，数据总是处在不断的变化过程 中。当数据发生变化时，以前的计算结果便会失效，如果想再次得到频繁集，可 以重新运行频繁集挖掘算法来得到结果，但这样做

57、没有充分利用已有的结果，因 为数据的更新往往只会导致小部分频繁模式发生变化。因而人们提出了增量频繁 集挖掘，可以利用已有的计算结果来生成新的频繁集。为简化表述，假定D为原有的数据集，d+是新增事务的集合，d-是删除的事务的集合，N是更新后的数据 集，即N=D+d+-d-。对于修改的数据可以视为删除原有事务后再增加一个新事务。FUP算法Cheung等人首先引入了增量关联规则挖掘，提出了处理新增数据4+的FUP算法17。FUP算法遵循Apriori算法的设计思想，按照自顶向下广度优先的策 略计算频繁集。每一次循环都需要扫描整个数据集一次，扫描数据集的次数和最大的频繁模式的长度相同。在每次循环中，F

58、UP算法与Apriori算法的主要不同体现在以下三个方面：扫描数据集d+，计算原有数据集D中长度为k的频繁集(LJd中的各模式在数据集d冲的支持度，结合已有的支持度，计算在N中(LJd中模式的支持度。如果其中模式的支持度大于，就将它加入 N上的频繁集(LQn。在完成以上步骤的同时，计算集合(Ck)N-(L0D中模式在d+中的支持度。(CQn是使用和Apriori算法中Apriori_Gen方法相同的方法从(L中得到的。)如 果其中模式的支持度不大于，则将其从集合中删除；扫描数据集D，计算(Ck)N-(L0D中剩余模式在D中的支持度，结合(b)的结 果，求得在N上的支持度，将频繁模式加入(LQn

59、。保证FUP算法正确性的依据是如果在 N中模式是频繁的，那么它或者在D中是频繁的或者在d+中它是频繁的。2边界集算法Thomas等人提出了基于边界集的增量挖掘算法18，算法不仅维护频繁集， 而且也维护边界集。边界集包含所有子集为频繁模式的非频繁模式。这两个算法 大体可以分为两个步骤：(1)检测阶段。扫描d+，确定原来的频繁集Ld中的模式在N上是否仍然是频 繁的；检测边界集中是否包含在N上的频繁模式。如果边界集中不包含频繁模式，说明新增数据不会引入任何频繁集。这是因为任何新引入的频繁模式或者属 于边界集或者它的某个真子集属于边界集。更新阶段。删除Ld中的非频繁模式，利用边界集中的频繁模式生成频繁

60、 模式的候选集，在遍历数据集后将其中的频繁模式加入N的频繁集Ln。2.3小结本章系统介绍了频繁集挖掘的理论和主要算法，着重阐述了三类算法： 完整频繁集挖掘算法。主要介绍了Apriori算法和FP-growth算法以及它 们的改进算法。频繁集简化表达方式的挖掘算法。着重介绍了闭合集表达方式挖掘算法。增量频繁集挖掘算法。概括介绍了 FUP等算法。第三章完整频繁集挖掘算法 电子科技大学工程硕士学位论文 第三章完整频繁集挖掘算法随着数据流中新数据的不断产生，一个当前的非频繁模式可能在将来变成频 繁模式，因此如果想得到一个准确的频繁集，任何在数据流中出现的模式以及它 的支持度都应该被记录下来。但是模式的