基于FP树的极大频繁项集的挖掘方法

石芹芹

（四川大学计算机学院，成都　610065）

基于FP树的极大频繁项集的挖掘方法

石芹芹

（四川大学计算机学院，成都610065）

0　引言

数据挖掘是20世纪90年代兴起的一项新技术，是知识发现的关键步骤。数据挖掘是多门学科和多门技术相结合的产物，是指从数据库中抽取隐含的、潜在的、先前未知的、有用的信息（如知识、规则、约束和规律等）的一个非平凡过程［1］。其中挖掘关联规则是一个非常重要的研究内容，而挖掘频繁项集是研究关联规则的基本和关键步骤。频繁项集导致发现大型事务或关系数据集中项之间有趣的关联或相关性，发现的这些相关联系，可以为分类设计、交叉销售和顾客购买习惯分析等许多商务决策过程提供帮助，故受到业界人士的青睐。然而从大型数据集中挖掘频繁项集是具有很大的挑战性的，因为对每一个k维的频繁项集个频繁1项集个频繁2项集因此频繁项集总共为个，项集个数太大。而极大频繁项集隐含了频繁项集的信息，因此近些年对极大频繁项集的研究也越来越多。

目前，极大频繁项集挖掘算法主要是基于Apriori 和FP-tree的改良和衍生算法。基于Apriori的有maxminer、pincer-search、Mafia、GenMax等，基于FP-tree的有Fpmax、IDMFIA、FPMFI等2。由于访问内存中的数据比访问外存磁盘中相同大小的数据快五六个数量级，上述这些算法至少需要两次外存数据库扫描，其数据结构表达形式也主要是枚举树、字典树和频繁模式树（FP-tree）等树形结构，结构较单一。

1　相关定义

定义1设τ=｛I1，I2，…，Im｝是项的集合，设任务相关的数据D是数据库事务的集合，其中每个事务T是一个非空项集（项的集合称为项集），使得T⊆τ。每一个事务T都有一个标识符，成为TID。设A是一个项集，当A⊆T时，则称事务T包含A。

定义2形如A⇒B（其中A⊂τ，B⊂τ，A≠Ø，B≠Ø，且A∩B≠Ø）的蕴含式叫关联规则。

定义3在事务D中规则A⇒B成立，则把D中事务包含A∪B的百分比叫做支持度（有时也称为相对支持度），记为s，即support（A⇒B）=P（A∪B）。

定义4在事务D中规则A⇒B成立，则把D中事务包含A∩B（包含A的事务也同时包含B）的百分比叫做置信度，记为c，即confidence（A⇒B）=P（B|A）。

定义5同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）的规则成为强规则。

定义6包含项集的事务数称为项集的出现频度，简称为项集的频度、支持度计数或计数，该支持度是绝对支持度。

定义7如果项集I的相对支持度满足预定义的最小支持度阈值 （即I的绝对支持度满足对应的最小支持度计数阈值），则I是频繁项集。频繁k项集的集合记为Lk。

定义8项集X是事务D中的频繁项集，且不存在超项集Y使得X⊂Y且Y在D中也是频繁的，则称X是极大频繁项集。

2　频繁项集挖掘的两大经典算法

Apriori算法是在1994年由Agrawal和R.Srikant提出的一种为布尔关联规则挖掘频繁项集原创性算法。它使用逐层搜索的迭代方法，其中k项集用于探索（k+1）项集，其算法思想是：第一遍扫描数据库，累计每个项的计数，并收集满足最小支持度的项，得到频繁1项集的集合，记为L1，第二遍扫描数据库，通过L1找出频繁2项集的集合L2，然后每一遍扫描数据库，都通过Lk-1找出LK，直到不能找到频繁K项集。在通过Lk-1找出LK时，根据先验性质进行剪枝。

频繁模式增长（Frequent-Pattern Growth），称为FP算法，该算法采用分治策略，发现频繁模式而不产生候选。其算法思想是：先将代表频繁项集的数据库压缩到一颗频繁模式树（FP-tree）中，该树能保留项集的关联信息。再把压缩后的数据库划分成一组条件数据库，使每一个数据库关联一个频繁项或者“模式段”，并分别挖掘每个条件数据库。该算法分两部分，第一部分是构造FP树，先创建树的根节点，第二遍扫描数据库D，对每个事务中的项按递减支持度计数排序，为其创建一个分枝，如果当前分枝与树的已有分枝有共同路径，则共享路径前缀；第二部分是挖掘FP树，由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基，然后构造它的条件FP树，并递归地在该树上进行挖掘。

两大算法中Apriori算法的候选产生-检查方法显著压缩了候选项集的规模，能产生很好的性能，却仍可能需要产生大量的候选项集，过程中需要重复地扫描整个数据库，因此挖掘出全部的频繁项集需要花费较昂贵的代价。FP-growth算法将发现长频繁模式的问题转换成在较小的条件数据库中递归地搜索一些较短模式，显著地降低了搜索开销，但当数据库很大时，构造基于主存的FP树有时是不现实的。

3　基于FP树的极大频繁项集的挖掘方法

我们看到，频繁模式挖掘可能产生大量的频繁项集，特别是当最小支持度阈值设置较小或者数据集中存在长模式时尤其如此。而实际中，有的时候只需要挖掘出极大频繁模式的集合，而不是所有频繁模式的集合。

在一个新的频繁项集导出之后，要对其进行超集检查和子集检查，检查新发现的项集是否是某个已经发现的、极大项集的子集。这些检查可以在构建FP树时完成。

算法思路：（1）先扫描一遍数据库，导出频繁1项集的集合，并按照它们的支持度计数降序排列；（2）构建极大频繁项集候选集列表，第二遍扫描数据库，构造FP-tree，在对每个事务创建分支时，若当前事务的分支与已存在的事务分支完全重合，则说明该事务是已发现的极大频繁项集的子集，不应被导出，否则存入候选集列表中。

算法：基于FP树的挖掘极大频繁项集的算法输入：DB：事务数据库；msup：最小支持度阈值输出：极大频繁项集的完全集M步骤构造极大频繁项集的FP树

①扫描事务数据库DB一次，导出满足msup的频繁项集合，保存它们的支持度计数，并按支持度计数降序排列，得到频繁项列表L，L中每项包括item-name、count；

②创建FP树tree的根节点 “null”。每个节点有parent，child，item-name，count属性；

③创建极大频繁项候选列表M，初始为空；

④CreatTree（）｛

排序Ti中的项，得到Ti的频繁项列表为［p|P］；//如果Ti在M表中没有共享前缀，按照L的次序排列，反之按M中的顺序排列；p是第一个项元素，P是剩余项元素

If each p in Ti is in Mi；//如果当前事务T所有项集已在M中出现，那么此不是极大频繁项集候选，删除该事务集中的所有项

4　算法应用结果

假设某商店的事务数据如下表，最小支持度阈值msup=2。

表1　某商店的事务数据

全局频繁1项集组成的集合是L1=｛A，B，C，D，E｝，排序之后得到的L为｛B：8，A:7，C:6，D:2，E:2｝，M=｛｝。根据L构建的频繁树如图1所示，该树并没有将非频繁的项集剪枝，极大项集完全集M构建过程如表2所示。

图1　频繁模式树FP-tree

表2　极大频繁项集候选每趟读取事务之后的结果

5　结语

该算法基于FP树，通过增加极大频繁项集候选列表M，能够准确地从事务数据库中挖掘出所有的最大频繁项集，在每趟读取事务项时，如果已被候选表中的项集包含，则不需要再记录该频繁项集，从而节省了时间，而最后得到的候选表M就是极大频繁项集的集合。因候选表M是存在于内存中，故计算机内存大小对该算法有一定限制，在事务数据量不大时效果较好，但在事务数据量庞大时该算法不太理想。

［1］张德干，王晓晔.规则挖掘技术［M］.北京：科学出版社，2008：2.

［2］王黎明，赵辉.基于FP树的全局最大频繁项集挖掘算法［J］.计算机研究与发展，2007：445-451.

［3］何波.基于FP-tree的快速挖掘全局最大频繁项集算法［J］.计算机集成制造系统，2011-07：1547-1552.

［4］任永功，张亮，付玉.一种基于频繁模式树的最大频繁项目集挖掘算法［J］.小型微型计算机系统，2010：317-321.

［5］Jiangwen Han，Micheline Kamber，Jian Pei.Data Mining Concepts and Techniques Third Edition［M］.北京：机械工业出版社，2012.7.

［6］阮幼林，李庆华，杨世达.一种基于事务树的快速频繁项集挖掘与更新算法［J］.计算机科学，2005：2-5.

［7］崔海莉，袁兆山.一种快速发现最大频繁项集的挖掘算法［J］.合肥工业大学学报（自然科学版），2006：11-16.

［8］张忠平，郑为夷.基于事务树的最大频繁项集挖掘算法［J］.计算机工程，2009：97-100.

［9］宋晶晶，姜保庆，关丽霞.在单向FP-tree上挖掘最大频繁项集［J］.现代计算机，2010：19-25.

Maximal Frequent Itemsets；FP-tree；Association Rules

Maximum Frequent Itemsets Mining Method Based on FP-tree SHI Qin-qin

（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2015）36-0007-04

10.3969/j.issn.1007-1423.2015.36.002

石芹芹（1990-），女，四川蓬溪人，硕士，硕士研究生，研究方向为图像处理与合成、数据挖掘

2015-11-17

2015-12-10

提出一种基于FP树的极大频繁项集的挖掘算法，该算法在构建FP树的过程中，通过子项集剪枝的方法，将挖掘到的极大频繁项集存储起来，从而节省再次挖掘FP树的时间，较已有的算法在挖掘极大频繁项集时简化挖掘过程。该算法的提出，为关联规则的精简提供新的解决办法。

极大频繁项集；FP树；关联规则

Proposes an algorithm for mining maximum frequent itemsets based on frequent pattern tree.The algorithm is an algorithm in the process of building FP-tree by pruning children-set and storing maximum frequent itemsets，thereby saves time mining again FP-tree than existing algorithms during mining Maximum frequent itemsets.It is a new algorithm to search association rules.