论文研究-基于有序树的不确定数据最大频繁项挖掘算法.pdf

所需积分/C币:9 2019-09-13 07:50:05 587KB .PDF
收藏 收藏
举报

针对UF-tree中项集存在的数据和路径冗余的问题,设计了有序的压缩不确定树SCUF-tree,在节点中存储元素的不同支持度,达到压缩存储空间和方便移植已有的确定数据最大频繁项集算法的目的。结合最大频繁项集挖掘算法MMFI的设计思想,提出了一种挖掘不确定最大频繁项集算法UMMFI算法,并采取逐层逐个的NBN策略挖掘不确定最大频繁项集。实验结果表明,UMMFI算法具有较好的时空效益和适应性。
刘卫明,蒯海龙,陈志刚,等:基于有序树的不确定数据最大频繁项挖掘算法 2015,51(24)147 记为nul”的根节点(用root表示);(2)频繁项目头表 步骒2再次扫描数据库,将每条事务中的烻繁项插 屮的每一表项都包含3个域,分别是 item name,item到SCUF-tre中。这里与UF-tree略有不同,将不同攴持 count以及 head of nodelink,其中 item count表示iem度的相同元素也放到同一个节点,并加上其在祉先节点 name的期望支持度;(3)树的每个节点都有7个属性,首的支持度选择,如果支持度也相同则其个数加1。新建 先,节点p有一个name的属性用来存储节点的编号或的节点插入到树中时按照兄弟节点之间的优先关系把 者名称,其次,Dm属性用来指定其在父节点的支持它插在恰当的位置使得右侧的节点在头表中的位置 度的选择,nex属性用来存储指向相同项目节点链中定位于左侧的节点的下方,这样就可以创建 SCUF-tree 下一个节点的指针(参考MMFI算法的改进MMFI算3.3 UMMMFI算法描述 法),ng用来标记l是否是最大频繁项集,cOnt用 根据MMFI算法思想及SCUF-tree的性质,设计 来存放L的期望支持度(L,表示从根节点到节点P的UMMF算法进行最大频繁项的挖掘,其具体的流程如 路径上的所有节点对应的项目组成的项集),com在下所示: 储L的超集中包含的的期望支持度计数信息,最后, 输入不确定事务数据库DB和期望支持度的阈值 CMFS(可能的最大频繁项集,初始为空集) expect用来存放不同的支持度以及对应出现的个数 输出MFS(所有的最大频繁项集) 可以看出SCUF-tree与 UF-tree相差较大的地方就在于 只体的伪代码: 节点的结构不同。 SCUF-tree虽然将同一元素但是支持 1)根椐DB和期望支持度的國值τ构造有序的SCUF 度不同的项放在树中的一个节点上,但是在计算期rec 在计算期望支持度时能准确区分同节点不同支持度为 望支持度时,会造成无法正确区分支持度的选择。为∫ MFS=,所有的tg城设T,所有 count'域初始设 (3)p指向最底层节点链上的第一个节点(下文中将p 的选择,需标记出其祖先节点的支持度选择,这正是 指示的节点称为节点p) arent属性的作用 (4) While p≠ Null do SCUF-ree具有以下两个性质 (5){fp:ag=F∥/和它的子集都不是MFI 性质1对于SCUF-tree头表中的任意两个项目i,和 (6){沿节点链搜索本层右侧的所有ag域为r的 ,若位于的上方,则以为后级的项集可能是以;节点9,q2…,9,若1=,则将q,节点的lg域赎为F 为后缀的项集的超集,但一定不会是以i为后缀的项集 (7)将节点p的父节点的tag域赋为F 的子集 (8) P指向节点链中的下一个节点或直接上一个 证明因为scUF-trec头表中的频繁项是按照攴持项目的第一个节点:; 度降序排列的,所以性质1显然成立 (9)F1 性质2对于有序的 SCUF-trea中任意层上的任意 (10)1f(如果′是CMFS的某个项子集) 两个节点p1和p2,若P1在节点链上位于P2的左侧,则 {不用计算;} (12 ln可能是l的超集,但一定不是2的子集 Else: i 13) 计算 p, count; 证明根据 SCUF-trea6的构建可知,n和l2一定不 (14) If(p. count+p count)>t/ 会相同,如果相同应该会合在一起,所以(ncLn2) 将节点p的父节点的tg域赋为F (1nl2)一定成立:由于 SCUF-tree是有序的,mp在 沿节点链搜索本层右侧的所有tag域为 左侧,根据有序树的定义可知n1>P2,P1的祖先节点A T的节点q1q 若L∈I,则将q,节点的tg域赋为 在头表中的位置一定位于P2的社先节点B的上方,根 MFS=MFS∪ 据 SCUF-trec的构造过程,既然A位于B的上方,那么B (18 p指向下一个节点;} 的子孙节点一定不会包含A节点,同时由于A和B都 (19) Else 是q的孩子节点,所以A一定不会出现在Jn2中,所以要 (20) 计算所有的可能以p结尾的项集组合的 期望支持度(计算时从最多项开始,逐渐减少,新加入的项集 么ln和l2设有包含关系,要么ln1=l2 不能是已有的项集的子集),满足最小期望支持度的并入 32SCUF-tree的构建 CMFS,如果CMFS已经包含则不用计算。 SCUF-tre建立的主要步骤为 (21) 沿节点链搜索右侧的所有tag域为T的 步骤1遍历不确定数据库一次,根据公式(1)计算节点q,4…,9;若 ,计算 p(q)com并且 每个顼的期望支持度,并从其中筛选出所有的频繁项 (22) count=q,. count'+p(g,) 把它们按照支持度降序的顺序插入头表中ε (23) p(q)cum是指在p中包含的的期 148 015,51(24) Computer Engineering and Applications计算机工程与应用 望支持度。 后的子节点中SCUF-ree可以比UF-tree节省更多空间。 p指向下一个节点;} 从中不难看出 SCUF-tree可以有效减少空间的消耗。当 然,为了进一步减少不同的支持度选项,还可以四舍五 入,取小数点后固定位数,用来合并更多的子节点。 sCUr-tree建立完成后就可以进行频繁项集挖掘的 (28)将MFS和CMFS合并,并去掉重复的(指的 过程。首先,从最底层的E开始,计算 EDCBA的期望支 是其不是某项的子集) 下面通过表1的内容来构建 SCUF-trcc,然后用持度 count=0.3×0.6×0.7×0.7×0.9+0.5×0.3×0.7 7×0.9=0.14553≤τ,所以不是频繁的,g值变成F UMMFI算法计算它的最大频繁项集,在这个例子中本 文假设最小支持度t为0.6。 计算所有的可能组合,将频繁项放入CMF,如AE 以后,每次不是频繁项的tag值都会变成F。之后到下 表1一个简单的不确定事务数据库(例子) 个E点,出于左边的 EDCBA包含右边的BCE,所以计 事务 内容 算好左边的BCE:0.3×0.7×0.7+0.5×0.7×0.7=0.392 A:0.9,B:0.7,C:0.7,D:0.6,E:0.3,F:0,1} {A:0.4,C:0.6,D:0.4,F:0.1} 将其赋予E点的 count',计算BCE的期望支持度 B:0.6,C:0.4,E:0.4} cont=04×04×0.6=0.096,因为0.096-0.392=0488≤r 14{4:0.9,B:0.7,C:0.7,D:0.3,E:0.5,F:0.2} 所以不是。E结束后,继续计算D点,DCBA的期垫支 15 A:0.8,B:0.7,D:0.2,G:0.3 持度: count=0.6×0.7×0.7×0.9+0.3×0.7×0.7×0.9= sCUF-tree的详细构建过程。首先,遍历一次数据03969≤x,下个D点,计算所有的可能组合,将频繁项 库并计算各个项的期壟支持度,从中筛选出频繁的项, 放入CMFS,有AD,BD,CD,计算DBA:0.6×0.7×0.9+ 当然最后要按照降序排列。频繁的项有A、B、C、D、E, 0.3×0.7×0.9=0.567,赋给下个D点cont,comt=0.2 它们的期望支持度分别为:3.0、2.7、24、1.5、1.2,F和 037×0.8+0.567=0.679≥τ,满足,DBA所以是频繁项 不是频繁的。之后,第二次遍历数据库,将事务插」 入 DBA加入MFS,将其所有的祖先节点的tag值变成F SCUF-tree首先将插入得到第一个分支,在插入时因为DCA不是DB4子集,g值还是r,所以还是需 指针指向的支持度就是这个元素的默认的父节点支持要计算的,计算DCBA中的DCA期望支持度:06×0.7 度。在插入n2时A的期望支持度不同,但是不需另建 9+0.3×0.7×0.9=0.567,赋给下个D点 count', count= 节点,只需C节点指定默认支持度为04即可。73用相0.4×0.6×04+0.567=0.6032,满足,DCA所以是频繁 似的方法插入,但是由于B的期望支持度小于A,所以项。DCA加入MFS,将其所有的祖先节点的ag值变成 在A的右边(这么做可以保证其为有序的树)。14插入 再计算C节点出于CBA的 count=20.9×0.7×0.7)= 时,D和F项支持度都没有相同的,所以需加入一个支0.882≥7,CBA加入MFS,将其所有的祖先节点的tg值 持度,由于在73中D不是默认的支持度0.6,所以需在变成F。出于BA的tg为F,而B是BA的子集,所以 E节点中指明D的攴持度选择,即0.3。75用同样的方不川计算。最后可得MFS为{DBA,DCA,CBA},CMFS 法插入。最终结果如图1所示。在这个例子中SCUF-为{AF,AD,BD,CD},将它们合并去掉子集,最终可得 tree HL UF-tree第一层子节点就减少了两个分支,在之MFS为{DBA,DCA,CBA,AE}。 root 实验 实验环境为 IntcIcorc2T6400CPU、2GB内存、win 0.9:2 0.6:1 dows XP操作系统的笔记本电脑。代码由jva语言编写 B 0).4:1 0.7 A:3.0 实现。实验中所用的数据由BM的数据生成器生成,每 0.8:1 0.7,(08)A:1 C||B:2.7 个元素的出现概率为0到1之间。出于 UMMFI算法是 0.4 (:24 基于期望支持度的不确定算法,所以只将其与UH-Mine, 1.6:1 D 进行对比 072 0.2:1 D E E:1.2 实验1在同一个数据库中,改变最小期望支持度, 0.4:1 查看不同算法运行时间所受的影响,结果如图2所示。 从图中可以看出,在期望支持度小的时候,三个算法的 0.3: 时间花销都比较大,随着攴持度的增加,显著减少,最 0.3:110.5,(0.3)D 终趋于平滑。可以发现, UFP-Growth花销的时间是最 图1根据表1产生的 SCUF-tree 多的,而 UMMFI虽然在最小期望低时花的时间还是比 刘卫明,蒯海龙,陈志刚,等:基于有序树的不确定数据最大频繁项挖掘算法 2015,51(24)149 UH-Mine多点,但是在最小期望大于05以后 UMMFI算素的不同支持度,实现以比UFre更少的空间存储不 法是所有算法屮用时最少的,这正是通过寻最大频繁项确定数据的目的,实验证明SUF-tree完成了这个目标 集确定颊繁的优势体现。 之后结合确定数据中挖掘最大频繁项集的思想在伈确 1000 实数据中提出最大频繁项集的概念,并改进MMF算 800 HFUFP-Growth 法,通过在不确定数据中挖掘最大频繁项集找出所有的 6(0 +UH-Mine 频繁项。从实验可以看出 UMMFI算法比 UFP-Growth -+UMMFI 400 算法具有更好的时空效益和适应性。进一步的工作可 以在sCUF-tre的基础和确定数据颎繁挖掘的思路丨: 对不确定数据的频繁项集挖掘进行更加有效的改进 5 最小支持度 图2运行时间与最小攴持度的关系 参考文献 实验2在同一个数据库中,改变最小期望支持度 1]注金苗,张龙波,邓齐忐,等不确定数据频繁项集挖掘方 查看不同算法存储空间所受的影响,结杲如图3所示。 法综述[J计算机工程与应用,2011,47(20):121-125. 从图中不难看出 UFP-Grow th消耗的空间一直是最大的, [2]李雪,江贺.确定数据挖掘技术併究进展[JOL中国科 技论文在线2009.http://www.paper.edu.cn UH-Mine的空间相对消耗得较少,而 UMMFI与UFP Growth相比较,可以看出其消耗的空间得到了显著的面53刘立新,张晓琳,毛伊敏一种有效的不确定数据概率频繁 项集挖掘算法[计算机应用研究,2012,29(3):841-843 善,是所有算法中空间使用最少的。 [4] Aggarwal CC, Li Y, Wang J, ct al. Frequent pattern min 12 ing with uncertain data[C]!/KDD, 2009: 29-3 B, Hung Ukp-Growth UH-Mine uncertain data[C/PAKDD, 2007: 47-58 F-UMMFI [6]B er t, Kriegel H P. Renz M, et al. Probabilis quent itemset mining in uncertain databases[C]//KDD 2009:119-128. 0.4 0.5 0.6 0.7 0.8 最小攴持度 [7 Tong Y ng Y, ct al. Mining frequent itemsets over uncertain databases cl//Proc of VI DB, 2012 图3存储空间与最小攴持度的关系 Leung C K s, Mateo M a F, Brajczuk DA A tree-based 实验3给定最小期望支持度0.5后,分别对不同的 approach for frequent pattern mining from uncertain data c// 数据库进行频繁挖掘,结果如图4所示。从图屮不难看 LNAI5012: PAKDL,2008:653-661 出,随着数据库的增加,所有的算法都会成线性增长的[9]SunL, Cheng R, Cheung D w,etal. Mining uncertain 趋势。在数据事物数小于50吋,UH-Mine增长趋势最 data with probabilistic guarantees[C]/KDD, 2010: 273-282 缓慢,当数据事物数大于50时, UMMFI增长趋势最为101 Wang L, Cheng r,LesD, et al. Accelerating probabi 缓慢 listic frequent itemset mining: a model-based approach[C]: IKM,2010:429-438 500 [ll Calders T, Carboni C, Goethals B Approximation of fre UMMFI quentness probability of itemsets in uncertain data[c]/ UFP-Girow th ICDM,2010:749-754 湖 -+ UH-Mine [12 Chui C K, Kao Ba decremental approach for mining frequent itemsets from uncertain data[C]/LNAl 5012 150 200 PAKDD,2008:64-75 数据库大小KB 13]陈超泉,黄佳欢,江云辉压缩 UF-tree挖掘不确定数据频 图4数据事物数与运行时间 繁项[门计算机应用研究,2014(3) 「14]陈晨,鞠时光基于改进r-lree的最大频繁项集挖掘算 结语 法门J计算机工程与设计,2008,29(24):6236-6239 本文主要为解决 UFP-Growth的缺陷,在 UF-tree.的口15陈晨,鞠时光进的最大频繁项集挖掘算法计算机工 基础上提出 SCUF-tree。在SCUF-tree的节点上存储元 程与设计,2010,31(18):40094032

...展开详情
试读 5P 论文研究-基于有序树的不确定数据最大频繁项挖掘算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743506 如果觉得有用,不妨留言支持一下
2019-09-13
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于有序树的不确定数据最大频繁项挖掘算法.pdf 9积分/C币 立即下载
1/5
论文研究-基于有序树的不确定数据最大频繁项挖掘算法.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载 >