基于前缀路径图的频繁闭项集挖掘算法∗

宋 薇 张晓民 郭东恩

（南阳理工学院软件学院 南阳 473000）

基于前缀路径图的频繁闭项集挖掘算法∗

宋 薇 张晓民 郭东恩

（南阳理工学院软件学院 南阳 473000）

关联规则是数据挖掘的重要方法之一，它主要用来揭示数据库中项或属性之间的相关性。频繁项集是产生关联的基础和核心。频繁闭项集项集数量远远小于频繁项集，而且包含了频繁项集的全部信息。为了有效压缩事务数据库信息，论文提出了前缀路径图结构，该结构可以存储挖掘所需的全部项集信息，减少扫描数据库次数。并且提出了一种基于前缀路径图的频繁闭项集挖掘算法PGraph-FCIMiner。论文的实验均采用Java语言编写，实验结果证明算法具有较好的执行效率和可扩展性。

数据挖掘；频繁闭项集；前缀路径图

1 引言

挖掘频繁项集是产生关联的核心和基础，因此目前对关联规则算法的研究上主要集中在如何高效的生成频繁项集上。为了减少扫描数据库的次数，提出了压缩结构，将挖掘频繁项集所需相关信息存储在这些结构上，然后基于这些结构挖掘出频繁项集。常见的结构有树结构、位表以及图结构。

CATS Tree［1］是一棵动态构建的前缀树，在挖掘的过程中可以动态指定最小支持度且不需要重新构建。但树构建的过程以及挖掘的过程都很复杂，为了解决这个问题提出了 SC Tree［2］。SC Tree通过提前对数据库排序实现静态构建，在挖掘过程中也没有最小支持度的限制。CanTree［3］用于增量式频繁模式挖掘，数据库更新时，树记录事务数据库的内容。CP-tree［4］是像FP-tree的压缩的支持度降序的树结构，通过扫描一次数据库构建，构建过程包含插入阶段和重建阶段。IFP-growth［5］是基于address-table和FP-tree+的算法。挖掘FP-tree+是通过自顶向下遍历头表中的每个项，所以FP-tree+可以在原始的FP-tree上构建，减少内存需要。

BitTable［6］是一些整数的集合，每一位代表一个项，用来压缩候选项集和数据库。BitTableFI在水平和垂直方向使用BitTable压缩数据库快速产生候选集和支持度，但是候选集的产生及检测影响算法的效率，为了解决这个问题提出了Index-Bit-TableFI［7］。Index-BitTableFI在水平和垂直方向使用BitTable，在水平方向上运用索引数组以及相应的计算方法，通过深度优先策略快速得到频繁模式。BTFIM［8］是基于BitTable的频繁模式挖掘算法，算法中首先将数据库信息压缩到BitTable中，而且算法中使用垂直方向BitTable用来快速计算支持度。

PrefixDigraph［9］由结点和有向边集合构成，用来存储每个结点的前缀路径集，用来压缩事务数据库信息。PDG-FIMiner算法［9］和PDG-FCIMiner算法［10］是基于该结构提出的频繁项集挖掘算法和闭项集频繁算法。

为了能够更加紧凑地压缩事务数据库信息，提高挖掘频繁闭项集效率，本文定义了前缀路径图（PrefixpathGraph）结构用来压缩存储事务数据库信息。挖掘时按照支持度由低到高的顺序挖掘结点，挖掘之后对该结点的前缀路径集进行分解。挖掘时，通过读取结点及其指向结点和有向边内容，读取该结点所有的前缀路径，挖掘出该结点的频繁闭项集。最后对所有结点的频繁闭项集进行闭包检查，挖掘出所有的频繁闭项集。

2 前缀路径图

2.1 问题定义

事务数据库TDB是一组事务的集合，集合中的每个事务用一个二元组＜tid，X＞表示，这个二元组包含了一组项的集合和该事务的ID号。设I=｛i1，i2，…，in｝是出现在TDB中项的全部集合，包含k个项的项集称为k-项集。在TDB中包含项集Y的事务的个数称为项集Y的支持度，表示为sup（Y）。给定一个最小支持度min_sup，如果一个项集的sup（Y）＞min_sup，那么我们就称项集Y是频繁的。

如果项集Y不存在真超项集X使得X与Y在数据集中有相同的支持度计数，则称项集Y在数据集中是闭合的。如果Y在数据集中是频繁的且闭合的，则称项集Y是数据集中的频繁闭项集。

2.2 前缀路径图定义

定义1 前缀路径图（PrefixpathGraph）是一个图形结构，用来记录事务数据库中的事务信息且记录每个结点的前缀路径集：

1）它是由结点的集合和有向边的集合组成；

2）图中每个结点代表事务数据库的一个频繁项；

3）有向边连接图中结点，始终是由事务信息中支持度最低的项指向支持度最高的项，有向边上记录着该结点的前缀路径信息，而且前缀路径信息按照支持度由高到低的顺序对项进行排序。

2.3 前缀路径图构造算法

首先扫描数据库，统计事务中出现的项及其支持度，得到频繁1-项集。再次扫描数据库，对于每个事务删除不频繁项。对删除不频繁项之后长度大于1的事务按照支持度由高到低对事务中的频繁项进行排序，当项的支持度相同时，按照词典顺序排序。在第二次扫描数据库过程中构造前缀路径图，在前缀路径图中保存每个预处理后的事务。为每个排序后事务中最后一项即当前事务支持度最低的项创建结点，排序后事务第一项即当前事务支持度最高的项为该结点的连接结点，创建有向边由当前事务中支持度最低的项指向支持度最高的项，有向边记录当前事务的其他频繁项信息，且有向边的内容也是由支持度高到低的顺序排序，当有向边只包含支持度时，内容为“：”。创建结点时，判断图中是否存在对应的结点，若无，则创建并更新nodelist。若存在，则判断当前连接结点是否存在，若无，则创建。若当前连接结点存在，则判断当前结点和连接结点是否已存在有向边，若不存在，新增有向边并记录当前事务其他频繁项信息。若存在有向边，则判断需要记录的当前事务项集信息是否存在，若不存在则在有向边上新增当前事务项集信息。若存在，更新其支持度。

算法1 前缀路径图的构造算法C-PrefixpathGraph

输入：事务数据库TDB，最小支持度ε；

输出：前缀路径图PrefixpathGraph，频繁1-项集allI-tem，node-list。

begin

扫描TDB并统计频繁项及其支持度，将频繁项按照支持度由高到低顺序排序，并记录为allItem；

for（TDB中的每个事务）｛

事务的频繁项按照支持度由高到低排序，若支持度相同，按照词典顺序排序，排序后的事务记为sortedTran

if（sortedTran长度＞1）｛

if（sortedTran长度=2）｛

name=sortedTran最后一项；

link=sortedTran第一项；

edge=”：”；

｝else｛

name=sortedTran最后一项；

link=sortedTran第一项；

edge=sortedTran其他项；

｝

if（！graph.contains（name））｛

graphNode=new Node（）；

graphNode.setName（name）；

graphNode.setLink（link）；

graphNode.setEdge（edge）；

nodeList.add（name）；

｝else｛

graphNode=graph.get（name）；

if（！graphNode.getLink（）。contains（link））｛

graphNode.addLink（link）；

graphNode.addEdge（edge）；

｝else｛

i=graphNode.getLink（）.indexOf（link）；

if（！graphNode.getEdge（i）.contains（edge））

graphNode.addEdge（edge，i）；

else

graphNode.updateEdge（edge，i）；

｝

｝

graph.put（name，graphNode）；

｝

end；

例1 表1是一个事务数据库，最小支持度为2。

表1 一个事务数据库

扫描数据库一次，事务数据库的项集为I=｛a，b，c，d，e，f，g，h，i｝，记录各项及其支持度，频繁1-项集FI=｛b：7，a：6，c：6，d：2，e：2｝。再次扫描数据库，事务信息按照支持度降序排序且删去不频繁项。读取T1：bae，创建结点e，e指向b，创建结点b，有向边eb内容为a：1；读取T2：bd，创建结点d，d 指向b，有向边db内容为1；读取T3：bc，创建结点c，有向边cb内容为1，此时前缀路径图见图1（a）；读取T4：bad，d结点以及有向边db存在，有向边内容增加a：1；读取T5：ac，创建结点a，有向边ca内容为1；读取T6：bc，c结点以及有向边cb存在，将有向边内容更新为2；读取T7：ac，c结点以及有向边cb存在，将有向边内容更新为2，此时前缀路径图见图1（b）；读取T8：bace，e结点以及有向边eb存在，有向边内容增加ac：1；读取T9：bac，c结点和有向边cb存在，有向边内容增加a：1；T10内容为空，不读取。最终前缀路径图见图1（c）。

图1 构造中的前缀路径图

2.4 前缀路径图性质

性质1 不受事务数据量的影响，前缀路径图结点数不超过事务数据库中频繁项的数目。

由定义1可知图中的每个结点代表事务数据库中的一个频繁项，因此图中的结点数最多是事务数据库中频繁项的数目，事务数据量不影响前缀路径图中结点数。

性质2 给定一个事务数据库，最小支持度，其对应的前缀路径图存储了挖掘长度大于1的频繁闭项集所需的全部信息。

根据上述构建过程可知，事务数据库中每个事务预处理后的频繁项长度大于2的事务信息都存储在该结构上。事务数据库的每条预处理事务均由某个结点和其连接结点以及有向边上记录的内容进行存储。因此该结构存储了挖掘长度大于1的频繁闭项集所需的全部信息。

3 基于前缀路径图的频繁闭项集挖掘算法

第一次扫描数据库时已经挖掘出频繁1项集，由性质2可知，前缀路径图上存储了挖掘长度大于1的频繁闭项集所需的全部信息。挖掘前缀路径图算法中频繁1-项集作为输入，且项按照支持度由低到高的顺序排序。按照这个顺序，挖掘每个结点的前缀路径，抽取出频繁闭合的前缀项集与对应结点连接产生每个结点的频繁闭项集候选集。计算这些频繁闭项集支持度最高的项并与结点项支持度进行比较判断当前结点项是否闭合。支持度最高的项没有前缀，因此将其1-项集放入频繁闭项集候选集中。最终对各结点产生的频繁闭项集采用哈希技术进行闭包检查，在当前频繁闭项集候选集中移除非频繁闭项集，挖掘出所有的频繁闭项集。

由构造图的算法可知，构造的图包含了预处理事务的所有信息。每个预处理事务由支持度最低的项指向支持度最高的项。挖掘时先挖掘支持度最低的项，当前项的连接结点和有向边的内容记录着当前项的全部前缀路径信息。挖掘完该结点频繁闭项集之后，需要对该结点记录的事务信息进行分解，分解时依旧是支持度最低的项指向支持度最高的项，因此连接结点不变，将有向边内容最后一项对应的结点即当前事务中除挖掘结点外支持度最低的结点指向连接结点，有向边内容为分解前有向边内容移除最后一项的信息，循环直到所有结点都挖掘完毕。因为最高结点没有前缀信息，因此根据按照支持度由低到高的频繁1-项集allItem循环时，判断当前结点在node-list里是否存在，当图创建结点时会更新node-list里的值。

当前挖掘结点其连接结点和有向边的内容构成当前结点的所有前缀路径信息。因为预处理事务时只保留长度大于2的事务，因此当前挖掘结点必包含前缀路径信息。如果当前挖掘结点的前缀路径只有一个，且支持度大于最小支持度将其前缀路径信息和结点连接加入频繁闭项集候选集。将当前前缀路径信息支持度与结点支持度比较，如果小于结点支持度，则将该结点对应的频繁1-项集加入频繁闭项集候选集。结点的前缀路径信息包括三种情况分别是项的个数等于2，其中有向边内容为“：”；项的个数为2，有向边内容是某个项；项的个数大于2。第一种情况表示预处理后事务只包含两项，不需要分解。第二种情况分解后结点为有向边最后一项即除挖掘结点支持度最低的结点，连接结点不变，有向边内容为“：”，并且记录其支持度。第三种情况分解后结点为有向边最后一项即除挖掘结点支持度最低的结点，连接结点不变，有向边内容为原有向边内容移除最后一项的内容，并记录其支持度。分解之后，则对图进行更新，判断结点是否存在，如果不存在，则新建结点并更新nodelist。若存在，则判断当前连接结点是否存在，若无，则创建。若当前连接结点存在，则判断当前结点和连接结点是否已存在有向边，若不存在，新增有向边并记录当前分解后有向边内容及支持度。若存在有向边，则判断需要记录的分解信息是否存在，若不存在则在有向边上新增当前分解信息。若存在，更新其支持度。最后增加新结点到图并删除挖掘结点图信息。如果当前挖掘结点的前缀路径大于一个，则需要抽取前缀路径集的频繁闭合项集信息。抽取频繁闭合的前缀路径主要是通过该结点前缀路径之间相互做交集，记录其交集并统计其支持度。统计交集支持度是通过交集之间做交集，更新其支持集。将前缀路径集的频繁闭合信息和其对应的结点进行连接，产生各结点的频繁闭项集候选集。将这些前缀路径集的频繁闭合信息中最高的支持度和其对应的结点支持度进行比较判断，如果小于结点支持度，则该结点对应的频繁1-项集是闭项集。并且对每个前缀路径进行分解，分解步骤同上。结点间的频繁闭项集候选集的闭包检查是借助哈希表进行比较判断。所有的频繁闭项集候选集都存储在哈希表中，其中支持度相等的任意两项做交集，判断交集是否等于自身，如果等于，则说明该候选集不是闭项集，而是另外项集的子集。最终在频繁闭项集候选集中移除不是闭合的候选集，得到所有的频繁闭项集。

算法2 基于前缀路径图的闭频繁项集挖掘算法PGraph-FCIMiner

输入：前缀路径图PrefixpathGraph，最小支持度ε，allI-tem，node-list；

输出：所有的频繁闭项集FCI。

begin

支持度最高的频繁项加入FCI；

for（支持度从低到高的allItem每个项）｛

if（当前项在node-list里）｛

获取该项对应的结点的前缀路径信息paths

if（paths.size（）==1）｛

if（paths的支持度大于等于最小支持度）｛

前缀路径连接结点及其支持度存入FCI；

if（paths支持度小于结点支持度）结点及其支持度存入FCI；

｝

link=paths第一项；

canNode=paths最后一项；

if（paths项个数＞2）｛

newedge=paths其他项集信息；

flag=1；

｝else｛

if（！canNode不是“：”）｛

newedge=“：”；

flag=1；

｝

｝

if（flag=1）

添加canNode，newedge，link到图、更新nodelist；

｝else｛

获得prePaths的频繁闭合信息连接结点存入FCI，并将支持度最大的项与结点支持度比较，若小于，将结点及其支持度存入FCI；

分解前缀路径即更新图，类似之前操作；

｝

｝

｝

结点间闭包检查，移除非频繁项集，得到最终FCI；

｝

end；

例2 将例1的前缀路径图作为输入，挖掘过程如下。

结点b无前缀路径集，因此将b：7加入FCI。支持度从低到高进行考察，第一个考察的是结点e，前缀路径大于1，因此通过求交集等方法得到其频繁前缀是ba：2连接结点加入FCI，与e支持度相同，因此e不是频繁闭项集，分解e结点的前缀路径ba和bac，删除e结点，更新图结果见图2（a）；考察结点d，频繁前缀是b：2连接结点加入FCI，与d支持度相同，因此d不是频繁闭项集，分解d结点前缀路径ba，删除d结点，更新图结果见图2（b）；考察结点c，频繁前缀路径ba：2，b：4，a：4连接结点加入FCI，频繁前缀项集最大支持度小于结点支持度，因此c是频繁闭项集加入FCI，分解c结点前缀路径ba，删除c结点，更新图结果见图2（c）；考察结点a，只有一个前缀路径b：4连接结点加入FCI，且支持度小于结点支持度，因此a是频繁闭项集，加入FCI。结点项之间采用哈希技术进行闭包检查，最终FCI=｛b：7，bae：2，bd：2，ac：4，bc：4，bac：2，c：6，ba：4，a：6｝。

图2 挖掘过程中分解图

4 实验

实验中算法是采用Java语言编写，机器配置为CPU 为 Intel（R）Core（TM）i5-4210H CPU@2.90 GHz 2.90 GHz，内存为4G，操作系统为Windows 8系统。实验使用的数据集是人工合成数据集T10I4D100K。 本 文将 PGraph-FCIMiner和PDG-FCIMiner算法执行效率进行比较，结果如图3所示。由图3可知，PGraph-FCIMiner挖掘时间低于PDG-FCIMiner，特别是当支持度低时，算法效率相比更高。而且由实验结果可知，当数据量不变时随着最小支持度递减，运行时间呈线性增长。

图3 在T10I4D100K上数据集上执行效率比较

为了验证变化事务量时算法的可扩展性，采用数据集T10I4D100K，将数据集分为五部分，每部分数据量为20K。每次运行各部分数据与其之前的运行数据的累计数据。数据量由20K逐步增为100K，每次增加20K。支持度固定为3.5%，4%和4.5%。实验结果见图4。显然支持度不变时随着数据量增长，运行时间呈线性增长。

图4 数据量20K到100K的运行时间

5 结语

本文定义了一种存储事务数据库信息的新结构前缀路径图，用来更加紧凑地压缩事务信息。图中的每个结点代表事务数据库中一个频繁项，有向边上记录着指向结点的前缀路径集信息而且是由支持度高的项指向支持度较低的项，这样保证更多的相同的前缀路径信息合并。每个项只占用一个结点而且信息存储的过程中如果指向结点、有向边、前缀信息均存在，只需更新前缀信息的支持度。本文提出了一种基于前缀路径图的频繁闭模式挖掘算法PGraph-FCIMiner，该算法只需将前缀路径图中每个结点连接指向该结点的结点和有向边上的前缀路径构成该结点的前缀路径集，通过挖掘前缀路径集的频繁闭合项集信息，将结点代表的项连接得到各结点的频繁闭合项集。通过对各结点的频繁闭合项集做闭包检查挖掘出频繁闭合项集。实验结果表明算法具有较好的执行效率和可扩展性。

［1］Cheung W，Zaiane O R.Incremental Mining of Frequent Patterns without Candidate Generation or Support Constraint［C］//Proceedings of the Seventh International Database Engineering and Application Symposium（IDEAS'03），Edmonton，Canada，2003：111-116.

［2］Chiou C K，Tseng J C R.Sorted Compressed Tree：an Imporve Method of Frequent Patterns Mining without Support Constraint［C］//Proceedings of 2nd International Conference on Software Engineering and Data Mining，Hsinchu，Taiwan，2010：328-333.

［3］Leung C，Khan Q，Li Z，et al.CanTree：a Canonical-order Tree for Incremental Frequent-pattern Mining［J］.Knowledge and Information Systems，2007，11（3）：287-311.

［4］Tanbeer S，Ahmed C，Jeong B，et al.CP-tree：a Tree Structure for Single-pass Frequent Pattern Mining［C］//Proceedings of the 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining（PAKDD），2008：1022-1027.

［5］Lin K C，Liao I E，Chen Z S.An Imporved Frequent Pattern Growth Method for Mining Association Rules［J］.Expert Systems with Applications，2011，38（5）：5154-5161.

［6］Dong J，Han M.BitTableFI：an Efficient Mining Frequent Itemsets Algorithm［J］.Journal of Knowledge-Based Systems，2007，20（4）：329-335.

［7］Song W，Yang B，Xu ZH.Index-BitTableFI：an Improved Algorithm for Mining Frequent Itemsets［J］.Journal of Knowledge-Based Systems，2008，21（6）：507-513.

［8］He H，Feng S，Ren J，et al.A BitTable-based Algorithm of Mining Frequent Itemsets［J］.International Journal of Advancements in Computing Technology，2011，3（8）：198-204.

［9］Wang P，Song W，Yang X，et al.PDG-FIMiner：An Efficient Frequent Itemset Mining Approach Using Prefix-PathsDigraph［J］.Advances in Information Sciences&Service Sciences，2012，4（16）：39-46.

［10］宋薇.基于二叉树和有向图的频繁闭项集挖掘算法研究［D］.秦皇岛：燕山大学，2013.SONG Wei.Research of Frequent Closed Itemset Mining Algorithms based on Binary Tree and Directed Graph［D］.Qinghuangdao：Yanshan University，2013.

An Efficient Frequent Closed Itemset Mining Approach Based on PrefixpathGraph

SONG WeiZHANG XiaominGUO Dongen
（School of Software，Nanyang Institute of Technology，Nanyang 473000）

Association rules is one of the important methods of data mining，it is mainly used to reveal the correlation between items or attributes in the database.Frequent itemsets is the basis and core of the generation of the association.The number of frequent closed itemsets is much smaller than the frequent itemsets，and it contains all the information of frequent itemsets.A novel structure termed PrefixpathGraph is defined to store the transaction database compactly，which can store all the item set information and reduce the number of scanning database.In this paper，a PrefixpathGraph-based algorithm is proposed called PGraph-FCIMiner.The experiments in this paper are written in Java language，and the experimental results show that the algorithm has a good performance and scalability.

data mining，frequent closed itemsets，PrefixpathGraph

TP301.6

10.3969/j.issn.1672-9722.2017.11.043

Class Number TP301.6

2017年5月6日，

2017年6月27日

国家自然科学基金项目“软件系统复杂网络层次化实体挖掘方法及关键技术研究”（编号：61572420）资助。

宋薇，女，硕士研究生，讲师，研究方向：数据挖掘。张晓民，男，硕士研究生，副教授，研究方向：软件工程。郭东恩，男，硕士研究生，副教授，研究方向：大数据。