30微电子学与计算机
2007年第24卷第lo期
项集为而。若,’中的每一个项目作为图上一个顶点,即Vl=^,E一=f(‘.‘)l{‘,i。}E最,其中1≤P≤n,1≤g≤^,P≠g】那么Gl-(V。,吕)是一个简单图。如果G2=(V2,易)是C1的一个极大完全子图,那么y。是,上的一个极大项集。
定义5(邻接极大项集)给定2个极大项集J,和,”(,’£,,,”£J).P:Inl’,如果,胛≠0.那么,’和,互为邻接极大项集。,上极大项集的集合表示为中,J’的邻接极大项集集合为妒(J’)=Irlr∈中.,nJ’
≠O,r#l’1。
频繁的.因此其频繁2一项集组成的图是完全图.那么j,,∈西,使得mfi∈LMFI(,’)UPMFI(,’)USM兀(,,);(2)算法的正确性,算法找到的mfi不是最大
频繁项集,即mfi《MH,有两种可能:①TIlfi不是频
繁项集.定理的正确性是显然的.若mfi不是频繁项集。由LMFl.PMFI和SMn的定义可知,n16tM兀;
②若t血是频繁的.但不是最大频繁项集,那么存
在一个raft的超集raft’.并且是最大频繁项集.由(1)可知:raft’EMFI,那么nail
eMFI。
定义6(局部最大频繁项LM兀)给定,上的一个极大项集,,.事务数据库口。最小支持度计数rain_sup.如果满足:
(1)j,”.,”∈,’,包含,的事务在D中出现的次数大于等于min_sup:
3最大频繁项集并行挖掘算法PMFIM
lmfi_miner算法按照深度优先方式进行遍历。遍历的过程中,使用了最大剪枝策略.并对每一结点的候选项集以支持度递减的方式进行动态排序。
算法1:lnn'i_miner(root)
输入:root.head初始为D.root.tail初始为极大项集,.
PMFI。SMFI和LMH为全局变量.初始为0。
(2)对于,∈州』’).如果,”n/'=O;那么称,”是
,’上对于r的一个局部最大频繁项集。
定义7f可能最大频繁项PMFI)给定,上的一个极大项集,’.事务数据库D.最小支持度计数min_sup。如果满足:
(1)j,”,,”C_I’。包含,”的事务在D中出现的次数大于等于min_sup:
(2)如果j,E妒(,’),使得,”c_r成立;那么称,”是,’上对于,的一个可能最大频繁项集。
定义8(邻接最大频繁项集的超集SMFI)给定J上的一个极大项集,7.事务数据库r.最小支持度计数rain_sup.如果满足:
(1)j,一。,”E,’,包含J”的事务在D中出现的次数大于等于mitt_sup:
(2),∈妒(,’),如果,”nr≠o;并且,”—,≠O;那么称J”是,’上对于r的一个最大频鬟项集的超集。
定理1给定项目集合,.,上极大项集的集合表示为中.对V,’£垂.,’的邻接极大项集集合为妒(j’)={,I/-E圣,rnl’≠O,,≠J’1,,’上的局部最大频繁项集、可能最大频繁项集和邻接最大频繁项集的超集分别记为LMFl(,’),PMl:I(,’)和SMH(I’),那么,上的所有最大频繁项集:
“
输出:PMFI.SMFI和LMH。
if(superset(root.headUroot.tai)£(LMFIUPEHULMH))retum;Noderm,maode;foreachiinroot.tailf
newnode.head=root.heMU埘i;newnode.taft=root.tail—m;
foreach,innewnode.tail
if(newaode.headU∽的支持度计数(1lIirL8up){
newnode.tail=newnode.tail—Uh对newnode.tail按照支持度降序排序:J
lmtl—miner(newnode,PMFI,SMFI,LMFl);l}
if(root.tail=D】for
each,in州r00t.head)
if(O<lrootheadf-lFl<l,n/'1)
把root.head添加到PMH’中:
elseif(I/'n/'l≤in:or.headnfl)
把rOOt.head添加到SMH‘中:
elseif(Iroot.headn/'l=O)
把root.head添加副LMFI二
算法2:最大频繁项集合并算法merge_mil
tA:邻接极大项集集台为妒,SMH.PMH,LMFI。输出:MFI
for
MFI=艺LMn(I’)UPMFI(I‘)USMFl(r)。
,et
证明:定理1是算法正确性的依据。下面分两方面来证明。(1)算法不会丢失最大频繁项集,即算法的完备性。假设存在,上的一个最大频繁项集mfi,由于m6是最大频繁项集.所以其2一项集都是
each/-in坝,’)
foreach
pmfiinPMFI"
if(supemet(pmfi)ESMFF
PMI:F=PMH'-(pmtl};
维普资讯 http://www.cqvip.com 200 7年第 2 4卷第1 O期 微 电子 学与计 算机 2 9 一 种基于极大完全子 图的最大频繁项集并 行挖掘算法 杨仕博 ...
一种有效的并行频繁子图挖掘算法 陈晓云 赵娟 陈鹏飞 邢乔金 刘国华 (兰州大学信息科学与工程学院 兰州 730000) 摘要:在分析并行频繁项集挖掘算法的基础上,提出...
目前已经提出的最大频繁项目集挖掘算法大多是基于单机环境的,在分布环境中挖掘最大频繁项目集的算法尚不多见。文章提出了一种基于分布数据库的并行挖掘最大频繁项目...
挖掘最大频繁项集的并行化策略 提出基于因子项集的并行化策略GP以发挥串行算法的剪枝功效。其基本思想是利用因子项集的完全包含关系在处理机之间贪心分配等价类....
一种基于FP-Growth的频繁项目集并行挖掘算法_互联网_IT/计算机_专业资料。... 基于FP-tree的最大频繁项... 42人阅读 4页 2.00 一种改进的FP-...
一种有效的并行频繁项集挖掘算法_专业资料。传统的挖掘频繁项集的并行算法存在各节点间负载不均衡、同步开销过大、通信量大等问题。针对这些问题,提出了一种多次...
一种基于极大完全子图的最... 4页 5财富值 一种高效的并行频繁集挖掘.....) "#) CA" 一种频繁项集并行挖掘算法李 ! 力! 翟东海! 靳 ! 蕃 ! !...
一种基于后缀项表的并行闭频繁项集挖掘算法_信息与通信_工程科技_专业资料。第3 1卷第 2期 201 4年 2月 计算机应用研究 Application Research of Comput...
一种基于频繁模式树的最大频繁项目集挖掘算法_IT/计算机_专业资料。小型微型...M A F IA 算法的概念框架是项集网格和 子集树 , 并利用纵向位图存储事务...
2012 分布式全局最大频繁项集挖掘算法杨君锐,何洪德,杨莉,李海文,薛萍 (西安科技大学 计算机科学与技术学院,陕西 西安,710054) 摘要:提出一种分布式全局最大频繁...
热门文档