一种快速挖掘生成器算法

许普乐　纪　允

(1.芜湖职业技术学院　教务处，安徽　芜湖241006；2.中国移动通信集团安徽有限公司　铜陵分公司，安徽　铜陵244000)



一种快速挖掘生成器算法

许普乐1纪允2

(1.芜湖职业技术学院教务处，安徽芜湖241006；2.中国移动通信集团安徽有限公司铜陵分公司，安徽铜陵244000)

摘要：生成器是频繁项集精简表示中的一个经典模型，但其传统挖掘算法存在重复生成候选项集，反复扫描数据库得到支持度，需要遍历所有直接子集等缺点，导致生成效率低下.基于此，一种快速挖掘生成器算法FMG，该算法采用Rymon枚举树作为搜索空间，提出的判断生成器定理对候选项集进行快速判断，以及特定的剪枝策略.通过这些方法快速的挖掘生成器.实验结果证明，该算法不仅比传统的算法要快，而且比最新提出的快速挖掘算法还要快.

关键词：数据挖掘；频繁项集；精简表示；Rymon枚举树；生成器

引言

在数据挖掘领域中，频繁项集研究一直是一个热点问题.频繁项集在解决分类，聚类，关联规则等诸多理论研究问题中有着非常重要的作用[1-2].特别随着推荐系统的兴起，抽取关联规则使得频繁项集的研究进一步得到发展.但是在实际的数据库中抽取频繁项集的数量过多，直接导致占用大量的数据空间，同时在传输和使用过程中也会增加网络带宽代价和CPU代价以及IO代价[3].这些缺点在数据密集型数据集上表现尤为明显并且限制了频繁项集的使用范围和能力.相关学者对这些海量的频繁项集进行研究后，发现可以通过某些方法例如格结构中的等价类，压缩频繁项集的数量，使得一部分的项集的支持度是可以从保留的项集中通过推算得到.为了压缩频繁项集的数量，学者们提出了频繁项集的精简表示，并且从各个方面提出多种精简方法和模型.目前频繁项集精简表示模型主要有最大频繁项集[4-5]、频繁闭合项集[6-8]、生成器模型[9]等.

由于在生成器精简表示模型中恢复频繁项集的支持度比最大频繁项集、闭合项集更加有效率[9]，因此频繁生成器成为频繁项集研究中一个热点.但是传统的抽取频繁生成器算法存在重复生成、反复遍历直接子集、反复扫描数据库等缺点，这些缺点导致生成器的生成效率底下.针对于挖掘效率低下情况，也有学者针对其进行研究，许普乐等人在文献[3]中提出基于FP树快速生成生成器算法FPASCAL.虽然在文中提出的算法比原有算法效率有所提高，但是该算法依然存在判断一个项集是否为生成器需要遍历所有直接子集的支持度的问题.

本文在分析生成器的相关的特点后，提出一种快速挖掘生成器崭新算法，该算法采用深度递归的思想，采用特定的剪枝思想和遍历策略，避免重复生成同一个候选项集.同时针对于一个生成器的支持度，可以根据先前生成器项集存储的信息计算而得到.在算法的具体运行过程中，从一个生成器直接跳到另外一个生成器，对于生成器的判断，也避免和所有直接子集的支持度进行比较.

1相关概念

1.1频繁项集和生成器

设项集IIS={k1，k2,……,kn}为n个不同的项所组成的集合.集合R⊆IIS为项集，项集中含有d个元素称该项集为d项集.在集合IIS基础上建立的交易记录数据库D,数据库D中每条记录o均有一个唯一的标识符TID.一个数据库D由三项O,I,R所组成,即D=(O,I,R)，其中R⊆O×I，(o,i)∈R表示在o这条交易记录中，包含i这个项.

设X⊆IIS，项集X的支持度supp(X)为数据库中包含X中所有项的交易记录个数或者比例.如果项集的支持度supp(X)大于或者等于设置的最小支持度minsupp，即supp(X)≥minsupp，则称该项集为频繁项集.

如果项集X和自己的所有直接子集的支持度均不相等，即supp(X)≠supp(Xi)其中i∈X，则称该项集为生成器.需要注意是，空集φ在交易数据库中也是一个生成器.如果生成器X的支持度大于或者等于最小支持度minsup，即supp(X)≥minsupp，则称该生成器为频繁生成器.可以很容易地发现，频繁生成器和频繁项集一样具有反单调性质.

1.2生成器精简表示模型

生成闭合项集的第一步是挖掘生成器，但是相关学者经过研究后发现生成器本身也可以作为频繁项集的一种精简表示方法，进而压缩频繁项集规模.在文献[9]中，Bastide Y等人提出了一种以频繁生成器为基础的一种频繁项集精简表示模型—生成器模型.频繁生成器FG (Frequent Generator)是生成器精简表示模型的基础.设项集X为频繁生成器，说明项集X不仅是频繁的，而且也是生成器，FG={X|X∈F,X∈G}.但是仅有频繁生成器FG是不能足以判断一个项集X是否为频繁项集.

因此需要加入另外一个辅助判断的集合，生成器边界.生成器边界包含最小不频繁生成器，若项集X为生成器边界，则X为生成器，且X不频繁，X的任意子集均为频繁生成器，即

GBd={X∈G|X∉F∧(∀Y⊂X,Y∈FG)}.

生成器精简表示模型由三个集合所构成，分别为：在数据库D交易记录中出现的不同项的集合I，频繁生成器集合FG，生成器边界集合GBd.需要注意的是，集合I和集合GBd只存储集合，不存储其他信息.而在集合FG中，存储的是频繁生成器集合，以及每个生成器的支持度.

生成器精简表示模型对于任意一个项集X，首先判断项集X是否是频繁项集，如果是频繁项集，再寻找其支持度.过程如下：

在文献[9]中，学者Bastide Y等人也提出一种算法PASCAL挖掘出生成器精简表示所需要的频繁生成器集合和边界集合.算法PASCAL主要步骤如下[3,9]：

1)Ck←PASCAL_GEN(Pk-1);

2)if∃(c∈Ckwhere c.key=true) then

3)forall o∈D do begin

4)Co←subset(Ck,o);

5)forall c∈Cowhere c.key=true do

6)c.sup++;

7)end

8)forall c∈Ckdo

9)if c.sup≥minsup then begin

10)if c.key and c.sup=c.pred_sup then

11)c.key←false;

12)Pk←Pk∪{c};

从该算法中，可以看出，Ck存在多次生成同一个候选项集的问题，同时针对于每一个候选项集c，需要扫描数据库得到其支持度，为了判断一个候选项集是否为生成器，需要和其所有直接子集进行比较.这些缺点使得算法的执行效率比较低下.

1.3枚举树

Rymon枚举树[10-11]的思想是在一个给定的集合元素中设定一个偏序.这种偏序可以是人为设定的也是可以任意指定的.这种偏序保证了在枚举树上的节点之间的父母/孩子关系.枚举树能够将一个集合中所有元素的各种组合很完整地没有重复的枚举出来，这点非常适合解决搜索问题.

枚举树的高效使用特点体现在搜索的过程中，如果某一个节点不满足要求，可以将该分支完整的进行剪枝.在文献[9]中,频繁生成器也具有典型的反单调性质,非常适合在Rymon枚举树上进行搜索.如果一个节点不是频繁生成器,则该分支下面所有节点都不是频繁生成器.

2算法

在本节中,提出了一种快速挖掘频繁核心项集算法FMG(Fast Mining Generators).传统的生成器算法中存在的扫描数据库得到支持度，候选项集重复生成，遍历候选项集所有的直接子集等三个严重缺点，这三个缺点会严重影响挖掘生成器的效率.算法FMG针对于这些问题进行解决.

2.1生成器判断定理

在闭合项集算法，提出了一个函数g，该函数能够返回在数据库中出现所有该项集的元素的行.该函数定义如下：

g(X)={o∈O|∀i∈X,(o,i)∈R}从函数g中可以看出，项集X的支持度等于|g(X)|.

设i为单个项，i∉X，则项集X∪i的支持度为|g(X)∩g(i)|.

生成器判断定理：设X项集为频繁生成器，i为某单个项，i∉X.如果不存在某个项y，y∈X，g(y)⊆g(i),或者g(i)⊆g(y)，则项集X∪i是生成器.如果|g(X)∩g(i)|大于等于最小支持度，则为频繁生成器.

证明：设g(y)⊆g(i)，则g(y) ∩g(i)=g(i),即g(X∪i)=g(X).因此|g(X∪i)|=|g(X)|，则项集X∪i和项集X的支持度是相等的.根据2.1节中的定义，项集X∪i不是生成器.同理，当g(y)⊆g(i)时，项集X∪i也不是生成器.

因此当不存在这样y的时候，项集X∪i是生成器，并且其支持度为|g(X)∩g(i)|，如果支持度最小支持度，则为频繁生成器.

2.2FMG算法

根据以上思想，本文提出了新的算法FMG，该算法采用2.1，将数据集中的每个项的g函数得到的结果进行存储.在集合中POST为所有项的集合，并且集合中的元素之间存在一种偏序关系.

算法FMG

输入：数据库D，最小支持度minsup

输出：生成器FG

1)FG=NULL

2)C1={1项集}

3)POST=C1

4)generator=null

5)FMG(generator,POST,FG)

6)return FG

procedureFMG(generator,POST,FG)

1)while POST≠NULL do

2)i=min(POST)

3)newgenerator= generator∪i

4)POST=POSTi

5)if(!contain(generator,i))

6)newgenerator.sup=|g(generator) ∩g(i) |

7)FG=FG∪newgenerator

8)if(newgenerator.sup) ≥minsup

9)NEWPOST=POST

10)FMG(newgenerator,NEWPOST,FG)

11)endif

12)endif

13)endwhile

procedurecontain(generator,i)

1)for all item j∈generator

2)if gen(j) ⊆gen(i) or gen(i) ⊆gen(j)

3)return true

4)endif

5)endfor

6)return false

2.3算法介绍

算法FMG的输入是数据库D和最小支持度minsup，输出是生成器集合FG.在算法的第1步到第4步都是初始化，分别将所得到的FG集合设定为空，POST集合设定为数据库D中的所有项，并且将最先的generator设定为空.在第5步正式调用算法，算法中的参数有三个，分别是上一轮生成的生成器generator，POST集合，需要返回的集合FG.需要注意的是POST集合中的元素已经设定成一种偏序关系.

算法首先在POST集合中找到偏序最小的元素i，i和上一轮生成器generator集合形成新的候选项集newgenerator，并且在POST集合中除去元素i.通过这样的步骤，形成Rymon枚举树的搜索空间.再调用contain函数判断在generator的元素和i是否有包含关系.如果没有在候选项集newgenerator是生成器，并且生成器的支持度为|g(generator)∩g(i)|，并且将newgenerator加入到FG集合中.如果newgenerator是频繁的，则此时使用一个新的NEWPOST集合保持POST集合，并且继续调用FMG算法直至POST集合为空为止.最后算法返回生成器集合FG.

contain函数主要有两个参数，生成器generator和单个项i.对于生成器generator中的所有项j，如果存在gen(j) ⊆gen(i) 或者 gen(i) ⊆gen(j)，则根据3.1节生成器判断定理，生成器generator和单个项i形成的候选项集不是生成器.

2.4算法实例

设数据库D如下图所示.

TID1abcd2abc3c4cd5ad

图1数据库D

设最小支持度为1，则g(a)={1,2,5}，g(b)={1,2},g(c)={1,2,3,4}, g(d)={1,4,5}.设枚举树的排序按照字母的顺序进行排序.FG为空，POST={a,b,c,d}.

算法从a开始,POSTa={b,c,d}.则a是生成器.a和b组合，形成ab，POSTab={c,d}.由于g(a)和g(b)存在gen(b)⊆gen(a)，不满足3.1节中定理的要求，所以ab不是生成器.a和c结合形成ac，POSTac={d}.ac满足定理的要求，ac是生成器.ac和d组合，形成acd，POSTacd={}.acd满足定理的要求，因此acd是生成器.

b，POSTb={c,d}.b是生成器，b和c组合，形成bc，POSTbc={d}.但是bc不满足条件，存在gen(b) ⊆gen(c).因此bc不是生成器.b和d组合，形成bd，POSTbd={}.bd满足要求，因此bd是生成器.

c，POSTc={d}.c是生成器，c和d组合，形成cd，POSTcd={}.cd满足要求，是生成器.

d，POSTd={}.d是生成器.

3.实验结果和分析

在本文中，提出了一种快速挖掘生成算法FMG，为了比较算法的性能，包括时间复杂度和空间复杂度，本文使用C++分别实现算法FMG和PASCAL以及在文献[3]中提出的算法FPASCAL.但是在文献[3]的实验结果中，FPASCAL的时间效率优于PASCAL，因此在本文和算法FPASCAL进行比较.

实验平台是win7环境下的PC机，i5处理器，4G内存.实验所采用的数据集均从http://fimi.cs.helsinki.fi/data/中下载的.为了全面衡量实验效果，实验中使用的数据集既包括密集型数据集：connect、chess、pumsb、pumbs_star，也包括稀疏型数据集T10I4D100K、T40I10D100K.FMG算法挖掘出来的生成器精简表示结果和文献[9]一致.实验结果如表1、表2、图1、图2、图3、图4、图5、图6、图7所示.

在表1和表2中可以看出，FMG算法得到的生成器精简表示结果和PASCAL算法所挖掘出来的结果是一样的.

在图2和图3、图4以及图5中，可以得知在数据密集型数据集上，算法FMG比FPASCAL要快3倍左右，并且随着支持度的降低，这种优势会更加明显.在图6和图7中，可以得知在数据稀疏性数据集上，算法FMG比FPASCAL要快30%，这是因为在稀疏型数据集上，需要存储的项的g函数的值比较多，从而增加检索时间，但是随着支持度的降低，这种效率优势会继续增加.

表1在connect数据集上运行结果

15%25%35%45%55%生成器负边界生成器负边界生成器负边界生成器负边界生成器负边界FMG663992064215479543060582412258512931122640PASCAL663992064215479543060582412258512931122640

表2在pumsb数据集上运行结果

70%75%80%85%90%生成器负边界生成器负边界生成器负边界生成器负边界生成器负边界FMG351848355451342672210237336106067755456111702622PASCAL351848355451342672210237336106067755456111702622

图2　connect时间效率对比图

图3　chess时间效率对比图

图4　pumsb时间效率对比图

图5　pumsb_star时间效率对比图

图6　T10I4D100K时间效率对比图

图7　T40I10D100K时间效率对比图

4结束语

本文在分析传统生成器挖掘算法后，得出导致该算法效率低下的几点原因.针对于这些问题，提出了一种快速挖掘生成器算法FMG，该算法使用Rymon枚举树作为搜索空间，采用Rymon枚举树的特定剪枝策略，利用生成器的特有性质快速判断候选项集是否为生成器，这些方法都很好地解决传统算法中的三个重大缺点，从而快速地挖掘所有的生成器.实验结果也很好地证明了FMG算法比传统的算法PASCAL和后来改进的算法FPASCAL都快很多.随着大数据时代和云计算时代的到来，如何将FMG算法应用到海量数据集中快速挖掘，如何在分布式环境下应用该算法，这些问题今后值得探讨和研究.

参考文献:

[1]Jiawei Han，Micheline Kamber．Data Mining Concepts and Techniques.数据挖掘概念与技术[M]．范明，孟小峰,译．北京：机械工业出版社，2004：1-261.

[2]纪允.析取闭合项集的快速生成和恢复算法研究[D].安徽：合肥工业大学,2013.

[3]许普乐,张勤,纪允.基于FP树的一种快速挖掘生成器算法[J].安庆师范学院学报(自然科学版),2013,19(1)：48-53.

[4]陈凯,冯全源.最大频繁项集的高效挖掘[J].微电子学与计算机,2005,22(8):22-25.

[5]Bayardo R J. Efficiently mining long patterns from databases[C]//Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM Press, 1998: 85- 93.

[6]陈俊杰,崔晓红.基于FP-Tree的频繁闭合项目集挖掘算法的研究[J].计算机工程与应用,2006,42(34):169-171.

[7]谭军,卜英勇,杨勃.一种高效的闭频繁模式挖掘算法[J].计算机工程与应用,2010,46(6):130-132.

[8] Pasquier N, Bastide Y, Taouil R, et al. Discovering frequent closed itemsets for association rules[C]//7th Intl. Conf. on Database Theory, January：1999: 398-416.

[9] Bastide Y, Taouil R. Pasquire N. Mining frequent patterns with counting inference [J]. SIGKDD Explorations,2000, 2(2): 66-75.

[10] Rymon R. Search through Systematic Set Enumeration[C]//Proc of Third Int’l Conf. on Principles of Knowledge Representation and Reasoning, 1992:539-550.

[11]田卫东，纪允.一种频繁核心项集的快速挖掘算法[J].计算机工程,2014,40(6):120-124.

(责任编辑鲁越青)

A Fast Mining Generator Algorithm

Xu PuleJi Yun

(1.Office of Educational Administration, Wuhu Vocational and Technical College, Wuhu, Anhui 241006;2.Tongling Branch, China Mobile Communication Group Anhui Co., Ltd., Tongling, Anhui 244000)

Abstract：Generators are a classical model concisely represented in frequent itemsets, whose traditional mining algorithm has such deficiencies as repeated generations of candidate itemsets and whose support obtained by repeatedly scanning database needs traversing all direct subsets. All those drawbacks result in lower generation efficiency. Motivated by this, a fast mining generator algorithm FMG is proposed. This algorithm uses the Rymon setenumeration tree as its searching space; a generator determiner lemma proposed in this paper is used to quickly determine a candidate itemset and to select particular paths for pruning. All the methods are helpful for mining generators. Experimental results show that this algorithm not only has better performance than traditional ones, but also is faster than a fast mining generator algorithm proposed recently.

Key words：data mining; frequent itemset; concise representation; Rymon setenumeration tree; generator

收稿日期：2016-01-12基金项目：安徽省高等教育振兴计划重大教学改革研究项目“职业院校信息化教学改革的研究与实践”(项目编号2014zdjy198); 安徽省高校优秀青年人才支持计划重点项目 “职业院校教育信息化发展路径研究-以安徽省为例”(项目编号：gxyqZD2016591)

作者简介：许普乐 (1980- )，男，安徽芜湖人，副教授，研究方向：数据挖掘、智能计算.

doi：10.16169/j.issn.1008-293x.k.2016.07.13

中图分类号：TP311

文献标志码：A

文章编号：1008-293X(2016)07-0063-06