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

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

2007年第24卷第10期微电子学与计算机

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

杨仕博,贺彦琨。马志新

(兰州大学信息科学与工程学院,甘肃兰州730000)

摘要:提出一种基于极大完垒子图的最大频繁项集并行挖掘算法PMFIM.通过遍历由频繁2一项羹构成的用邻接矩阵表示的圈.寻找田的极大完全子田.从而由极大完全子田顶点序列实现对项集的划分.即挖掘子任务竹划分。在同类算法中.特找到的最大频繁项划分为局部最大频繁项集LMFI、可能最大籁繁项集PMFI和邻接项集的最大频繁项集的超集SMFl,减少了该类算法合并最大额繁项集的开销.井对算法进行了实现和优化。关键词:数据挖掘;关联规则;极大完垒子圉;籁繁项集:井行算法

中圈分类号:TP3386

文献标识码:A

立章编号:1000-7180(2007)10-0029-03

ANewParallelAlgorithmfor

MiningMaximumFrequent

ItemsetsBased

on

MaximumCompleteSubgraph

YANGShi—bo,HEYan-kun,MAZhi-xin

(Schoolof/击om,atioaScienceand

Erlgin秭“g,I丑nd矾 Unlverslty,Lanzh加730660,Chi越)

Abstract:"Fnispaperp∞esents

8

蚰b酣.TheparalletalgorithmformlmingmaxiIlIumfrequentitemsetsbased

on

mⅡ面mcomplete

ggorithm由跏e硌衄画mⅧcomplete驰bgr讪姆tra-versingthe缸删2-1ten性ets

mapp。esentedb

呐acent

嘣mm

matrices,anddividesitemsetswith

m自‘lmm

completesubgraphvertex

sequence.Theinnovationisdividing

frequentitemsetsintoLMFI,PMFI

andSMFI

This

methodreducesthe

cost

0fmer舀“gmaximttmh8quent

itemset&Meanwhile

thealgorithmhasbeenimp]ementodandoptimized,

Keywords:detamining;associationroles;lnaxhllmcompletesubgraph;h2quentitemsets;parallelalgorlthm

l引言

一个项集。并且如果盖满足用户给定的最小支持频繁项集挖掘是关联规则挖掘中一个活跃而度,那么称x是频繁的。如果IXl=k,则工称为频繁重要的子领域.所有频繁项集挖掘、最大频繁项集女一项集。如果不存在一个项集互’,使得.:fc工,成立。挖掘和封闭频繁项集挖掘¨】。按照执行的顺序.算法且X’是频繁项集.那么称盖是,上的一个最大频繁分为串行算法和并行算法.典型的串行算法有项集。

Apriori,MaxMiner。MAFIA日,CHARM和LcM。典型定义2事务r是一个二元组:T=(tld.x).其的并行算法有CD。DD,IDD.CandiateDistribution算中£试称为事务号.是该事务的惟一标识.石是一个法。由于数据挖掘常常处理的是海量级数据.而单

项集。J£,。事务数据库D是T上事务的集合。D=处理器处理能力有限∞,因此研究并行挖掘算法十

(t,,£:,…,fJ,其中n为全部事务的个数,当JE(1,2,分必要。而挖掘最大频繁项集并行算法的难点在于…。nl,£.表示一个事务。

对挖掘任务的划分。文中提出一种基于极大完全子定义3(邻接矩阵)设G=(P,E)是具有n个图的最大频繁项集并行挖掘算法PMFIM.通过遍历顶点的图,其中y=(n,V2,…,yJ,E={印。砖>11≤i≤由频繁2一项集构成的用邻接矩阵表示的图.寻找图B,1-<j≤n),则G的邻接矩阵是n阶方阵JIIf=(8Ⅱ),

的极大完全子图,从而由极大完全子图顶点序列实若<巩,p隹E,e产O;若q,垆∈E,%=l。

现对项集的划分,即挖掘子任务的划分。定义4(极大完全子图和极大项集)对于图C=(矿,E),如果存在图G’=(V7,E’),l,’∈V,E’∈E,2基本定义和定理

且G’是完全图,那么G7是G的完全子图。如果不存定义1项目集合I=11,,屯,…,iA,其中当J

E

在C的另一个完全子图G”--(V“.F).那么G’是G{1,2,…,n】,ij表示一个项目。如果xC;.那么X是

的一个极大完全于图。设数据库D有n个项目.项

收藕H弱二2007-06—02

目集合仁‰i2,…,村,其频繁l一项集为只,频繁2一

第1页

你可能喜欢

热门文档

相关文档

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