关联规则最大频繁项目集的快速发现算法

刘大有1,2,刘亚波1,2,尹治东3

(1.吉林大学计算机科学与技术学院,长春130012;2.吉林大学符号计算与知识工程教育部重点实验室,长春130012;3.吉林出入境检验检疫局,长春130062)

摘要:提出一种快速发现最大频繁项目集的算法,该算法对集合枚举树进行改进,结合自底向上与自顶向下的搜索策略,利用非频繁项目集对候选最大频繁项目集进行剪枝和降维,减

少了不必要候选最大频繁项目集的数量,显著提高了发现的效率.

关键词:关联规则;集合枚举树;最大频繁项目集

中图分类号:TP311 文献标识码:A 文章编号:1671-5489(2004)02-0212-04

Fastalgorithmfordiscoveringmaximumfrequentitemsets

ofassociationrules

LIUDa-you1,2,LIUYa-bo1,2,YINZhi-dong3

(1.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China;2.KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringofMinistryofEducation,JilinUniversity,Changchun130012,China;3.JilinEntry-ExitInspectionandQuarantineBureau,Changchun130062,China)

Abstract:Thepresentpaperpresentsanefficientalgorithmthatimprovesset-enumerationtreeandfindsmaximumfrequentitemsets.Bycombiningbottom-upandtop-downsearchesinset-enumeration

treeandmakinguseoftheinfrequentitemsetstoprunecandidatesofthemaximumfrequentitemsets,

thealgorithmreducesthenumberofcandidatesofthemaximumfrequentitemsetsgeneratedbyitsothattheefficiencyisincreased.

Keywords:associationrule;set-enumerationtree;maximumfrequentitemset

收稿日期:2003-09-28.作者简介:刘大有(1942～),男,教授,博士生导师,从事人工智能、数据挖掘和计算机应用的研究,E-mail:dyliu@mail.jlu.edu.cn.联系人:刘亚波(1975～),女,博士研究生,从事关联规则挖掘和粗糙集理论的研究,E-mail:liu-yabo@263.net.基金项目:国家自然科学基金(批准号:60173006)、国家高技术研究发展计划项目(批准号:2003AA118020)、吉林省科技发展计划重大项目(批准号:吉科合字20020303-2)和吉林大学符号计算与知识工程教育部重点实验室资助基金.发现频繁项目集是关联规则等多种数据挖掘的关键问题.在关联规则挖掘中,如果一个项目集的

支持度不小于用户定义的最小支持度(以下简记为minsup),则称为频繁项目集;反之则称为非频繁项

目集.如果一个频繁项目集的所有超集都是非频繁项目集,则称为最大频繁项目集.目前,多数频繁项目集发现算法都是Apriori算法或者其变种[1].这些算法采用自底向上的方法穷举每个频繁项目集,

当最大频繁项目集很长时,这将是一个NP问题.任何频繁项目集都是最大频繁项目集的子集,该问

题可以转化为发现所有最大频繁项目集.提高发现最大频繁项目集效率的关键是减少生成不必要的候选项目集及对其支持度的计算.

文献[2]中的Max-Miner算法采用集合枚举树来描述项目集,突破了传统的自底向上的搜索策第42卷　第2期 吉林大学学报(理学版) Vol.42　No.22004年4月 JOURNALOFJILINUNIVERSITY(SCIENCEEDITION)Apr　2004

Fig.1　Set-enumerationtreeoverfouritems略,采用自底向上和自顶向下的搜索策略同时进行

搜索,提出向前看(lookahead)的剪枝策略,最大

频繁项目集发现过程转化为在集合枚举树的搜索过程.集合枚举树可以枚举一个项目集合的所有子

集.图1表示集合{a,b,c,d}的集合枚举树.但

Max-Miner算法并没有充分利用在剪枝时生成的非

频繁项目集信息,产生许多不必要的候选最大频繁项目集.本文提出的P&M算法针对Max-Miner算

法,对集合枚举树进行改进,借鉴文献[3]中Pin-

cer-Search算法的思想,利用非频繁项目集对候选最大频繁项目集进行剪枝和降维,减少了不必要候选最大频繁项目集的数量,并能及时发现最大频繁

项目集.

1　发现最大频繁项目集的算法P&M

1.1　集合枚举树的改进

P&M算法对集合枚举树节点的表示及子节点生成方法进行了改进,使第i层节点node枚举的项

目集由两个项目集表示,node的前i个元素记为h(node);除h(node)以外其余的元素记为t(node),

node=h(node)∪t(node).改进后集合枚举树根节点root满足h(root)为空集,t(root)为整个集合.从

父节点node生成其子节点的方法是:󰀁m1∈t(node),则第一个子节点subnode1为

h(subnode1)=h(node)∪m1,　t(subnode1)=t(node)-m1;　󰀁m2∈t(subnode1),

第二个子节点subnode2为

h(subnode2)=h(node)∪m2,　t(subnode2)=t(subnode1)-m2,…,　󰀁mi∈t(subnodei-1),

Fig.2　Improvedset-enumerationtreeoverfouritems第i个子节点subnodei为

h(subnodei)=h(node)∪mi,

t(subnodei)=t(subnodei-1)-mi.

图2为改进后{a,b,c,d}的集合枚举树.图2

中,带下划线的部分为h(node),不带下划线的为

t(node).图2使集合枚举树的表示与子节点生成更加清晰.因为{h(node)󰀁node为集合枚举树第k层节点}包含一个集合的所有k维子集,任一节点

node都是在某一序关系下h(node)的最长超集,所

以集合枚举树第k层节点枚举的项目集可作为候选最大频繁项目集.

1.2　剪枝与降维策略

P&M算法从树根开始双向搜索,当搜索集合枚举树的第k层时,P&M算法设置候选最大频繁项目集集合MFCSk包含集合枚举树第k层节点枚举的项目集,根据下面的策略对MFCSk中的元素进行

剪枝与降维,减少候选最大频繁项目集的数量.为方便,以下记任意项目集g的支持度为sup(g).剪枝与降维策略:

(1)󰀁g∈MFCSk,若sup(h(g))

(2)󰀁g∈MFCSk,若sup(h(g))≥minsup,并且󰀂mi∈t(g),使得sup(h(g)∪mi)

sup(g)

集,判断其是否是频繁项目集;若是,则加入最大频繁项目集集合MFS中;否则,用于生成MFC-

Sk+1.图2中,k=2时,MFCS2中若ac不是频繁项目集,则从MFCS2删除acd;若ab是频繁项目集,

并且abc不频繁,则abcd降维后生成abd,若abd是频繁项目集,则加入MFS.1.3　非频繁项目集的生成

根据降维策略(2),搜索集合枚举树第k-1层,对候选最大频繁项目集降维时,生成k维非频繁

项目集,例如g∈MFCSk-1,sup(h(g))≥minsup,如果󰀂mi∈t(g),sup(h(g)∪mi)

若MFCSk中某个项目集包含至少一个非频繁子集,则其一定是非频繁项目集,可以不必计算其支持度.

1.4　候选最大频繁项目集的生成

对MFCSk中项目集剪枝与降维后,P&M算法根据MFCSk中的非频繁项目集生成MFCSk+1,利用非频繁项目集对候选最大频繁项目集进行剪枝和降维.

设g为MFCSk中的非频繁项目集,nfs是g的一个非频繁子集,因为sup(h(g))≥minsup,并且󰀁mi∈t(g),有sup(h(g)∪mi)≥minsup,所以󰀁nfs∩t(g)󰀁≥2.因此由g生成MFCSk+1中项目集的方

法为:选取g的一个非频繁子集nfs1,并且nfs1∩t(g)={m1,m′1},则g的第一个子项目集g1,

h(g1)=h(g)∪m1, t(g1)=t(g)-m1-m′1;

再选取g的一个非频繁子集nfs2,并且nfs2∩(t(g1)∪m′1)={m2,m′2},则g的第二个子项目集g2,

h(g2)=h(g)∪m2, t(g2)=t(g1)∪m′1-m2-m′2;

再选取g的一个非频繁项目集nfs3,并且nfs3∩{t(g2)∪m′2}={m3,m′3},则g的第三个子项目集g3,

h(g3)=h(g)∪m3, t(g3)=t(g2)∪m′2-m3-m′3,

以此类推.若生成第j+1个子项目集时,g与t(gj)中没有满足条件的非频繁项目集,则按文献[2]中集合枚举树父节点生成子节点生成其余子项目集.可见在生成前j个子项目集的同时,也对其进行了

降维.

例如,对于候选最大频繁项目集g,h(g)={},t(g)=ABCDEF,若k=1时,发现CE,BD,EF是非频繁项目集,则按照先选取CE,然后选取BD,最后选取EF的顺序,分别生成ACBDF和ABEF,AED;AFD,AD,若ABCDF是频繁项目集,则加入MFS中.

1.5　P&M算法

P&M算法初始MFCS0中只有一个候选最大频繁项目集root,h(root)为空集,t(root)为所有项目

的集合.

输入:(1)关系数据库DB;(2)最小支持度minsup.输出:满足最小支持度minsup的最大频繁项目集集合MFS.

MFS={};NFS={}.h(root)={}.t(root)=DB中所有项目的集合.MFCS0={root}.k=0.

whileMFCSk≠ do{for󰀁g∈MFCSkdo　{if(nfs(g)= )//若g不包含小于等于k-1维的非频繁子集,　then{if(sup(g)≥minsup)//判断g是否是最大频繁项目集

then{MFS=MFS∪g.deleteg′fromMFCSkwhereg′!g.}//若g是最大频繁项目集,

加入MFS,并删除MFS中g的子集 elseCreate(g,MFCSk+1,NFSk+1).}//若g不是最大频繁项目集,按候选最大频繁项目集

的生成方法生成MFCSk+1.

　elseCreate(g,MFCSk+1,NFSk+1).}//若g包含小于等于k-1维的非频繁子集,按候选最大频繁项目集的生成方法生成MFCSk+1.

根据NFSk+1,计算MFCSk+1中元素的非频繁子集214 吉林大学学报(理学版)第42卷