文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 一种基于极大完全子图的最大频繁项集并行挖掘算法
侵权投诉

一种基于极大完全子图的最大频繁项集并行挖掘算法

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};

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email