论文研究-基于最近共享邻居节点的K-means聚类算法.pdf

所需积分/C币:6 2019-09-12 08:26:40 597KB .PDF
收藏 收藏
举报

提出了一种新的多维序列模式挖掘算法,首先在序列信息中挖掘序列模式,然后针对每个序列模式,在包含此模式的所有元组中的多维信息中挖掘频繁1-项集,由得到的频繁1-项集开始,循环的由频繁(k-1)-项集(k>1)连接生成频繁k项集,从而得到所有的多维模式。该算法通过扫描不断缩小的频繁(k-1)-项集来生成频繁k项集,减少了扫描投影数据库的次数,因而减少了时间开销,实验表明该算法有较高的挖掘效率。
肖仁财,薛安荣:一种挖掘多维序列模式的有效方法 2008,44(6)189 表2频繁1-项集L1 输出:所有的多维模式 标号项列表(iist)元组标识集( rlist)属性列表( alist) 方法 business cust-grp (1)L=fnd-freqμuent1- -itemset(D);∥扫描数据库得到所有的频繁 cust-grp 1-项集 Chicago 1,2,3 city (2)for(k=2;k≤M&&Lk1≠φ;k++)∥M为属性个数,即维度 p4 age-grp (3)L= Pattern gen(Lk4, minsup);/由频繁(k-1)-项集生成频 P retired age-grp 繁k-项集 其中子过程 Pattern gen是由频繁(k-1)-项集(k>1)连接生成频繁 频繁项p1,由于共3个属性,而 business属于第一个属性cust-k-项集,方法描述如下 gTp,所以可以得到1-维模式( business,*,*),其支持数就是元 Pattern_gen(Lk-1) 组标识集中的元素个数,即为2,频繁1-项集中的其他频繁项 (1) for each p∈Lk 同样可以得到1-维模式。 (2) for each q∈Lk 得到频繁1-项集后,通过循环对频繁(k-1)-项集(k>1)做 (3)pq=join(p,q);/p,q作连接生成新的频繁项p 连接得到频繁k-项集,其中k的初始值为2。 (4) pq≠9 当k=2时,是对频繁1-项集中的频繁项作连接,只要两个 (5) L=L∪pg;} 频繁项的项列表中的项属于不同的属性且两个频繁项的元组 (6) return LK 标识集的交集中元素数目大于最小支持数就可以做连接生成 做连接的子过程join描述如下 新的频繁项。得到的新频繁项的项列表和所属属性列表分别是 oin(p,q)设pit=item,…,item},q,ilst={tem,…,iem-} 原两个频繁项项列表和所属属性列表的并集,而新频繁项的元 (1)i(k=2)Mk=2时,L1中是频繁1-项集 组标识集是原两个频繁项元组标识集的交集。例如表2中的p1 (2) if((p alist*galist )and (lp. rlistn q rlistl2min_sup ) 和p,由于 Pianist≠pait并且p, rlist np3s=1(1,3川=2≥2, 对属于不同属性的频繁1-项集作连接 满足作连接的条件,生成的新的频繁项p的各项值为:p.ilit= pq ilist=p ilist U gilist (4) (business, Chicago), P alist=(cust-grp, age-grpl, P alist=(1, 3)o Xf pq alist=p alist U gilist; (5) 表1所示的L做连接后得到的频繁2-项集L2如表3所示。其 pq rlist=p rlist ngilist; (6) else it(k>2M/设p. alist={att,…,attl,q,list=at,…,attl 中L2中每个频繁项都可以得到一个2-维模式,如q2,由表3可 ir((pilisl. itel2=q ilist. itell )and(p ilisl. itel3 =y ilisl itel 2 以看出,q2中的频繁项集的属性列表中两个值分别是cust- gp and-…and 和age-grp,属于不同的属性,所以可以得到2-维模式(busi (p ilist. item-=q ilist. itemk-2)and (lp rlist n g. rlistl> ness,*, middle)。 当k>2时,对于两个频繁(k-1)-项集p和q,如果p去掉 lpg ilist=p ilist. iteml, .. p.ilist. itemk-I, q.ilist. itemk-l1 项列表中的第一个项之后与q去掉项列表中最后一个项后两 pq alist=p. alist attr, ". Palist. attrk-1, g alist. attrk-11; 者剩余部分相同且两者的元组标识集交集的个数大于最小支 (10) pq rlist=p rlist ng rlist: J 持数,则两者可以做连接,生成的新的频繁项的值计算与k=2 (11) return pq; 时相同。例如对表3所示的频繁2-项集中的频繁项q和q3,q1 中的频繁项集去掉项列表中第个项后的剩余部分与q3去掉4算法分析与实验结果 最后一个项后的剩余部分相同,都只剩余 Chicago,且 qrlist∩ 从上面的描述可以看出,对每个序列模式,Seq-mdp算法 q3rl2,所以两者可以做连接,生成的新的各项值见表4扫只扫描此序列模式的投影数据库得到频繁1-项集后,对不断 描表3后得到的所有的频繁3-项集L3如表4所示,同样L3中缩小的频繁(k-1)-项集进行连接得到频繁k顶集,进而得到所 的每个频繁项都可以生成一个3-维模式。 有的多维模式。而Seq-Dim算法对多维模式的挖掘是采用类 表3频繁2-项集L2 BUC算法,要多次扫描每个序列的投影数据库,因而在维度较 标号频繁项列表( ilist)元组标识集( rlist)属性列表( alist 高时与本文提出的方法相比时间性能有所下降 usIness Chi 1,3 cust-grp, city 本文采用ve+6.0实现了Seq-mdp算法,并与Seq-Dim算 g2 business, middle 1,3 cust-grp, age-grp 法作了比较。实验环境为 Intel(R)2.8GHz/.00GB/ Windows Xp, Chicago, middle 1,3 city, age-grp 实验数据是采用IBM的数据生成工具合成的数据,然后从 表4频繁3-项集L3 htt:/ vww.ics. uci. edu/- mlearn下载的蘑菇数据库中选取的属 频繁项列表(ist)元组标识集( rlist)属性列表( alist) 性作为维信息。有关数据集参数为:D表示原事务数据记录的 business, Chicago, middle 1,3 cust-grp, city, age-grp 数目;m表示事务数据记录的平均长度;表示事务项的个 数。实验中采用了4组数据集,分别用C1,C2,C3,C4表示,其 由于共有3个属性,所以生成所有的频繁3-项集后就可中数据集C1中D=2000,1ml=5,|H=30,数据集C2中D|= 以停止操作,因为3维属性不可能再生成高于3维的模式。同4000,C3中D=6000,C4中D=8000,其它参数不变。采用C 样如果有M个属性,则生成频繁M-项集后就可以得到所有的数据集分别测试了在支持度不变(20%),维度变化以及维度不 多维模式。 变(5维),支持度不断变化的情况,分别如图2,图3所示。图4 322算法描述 是在支持度取20%,维度取5,不同数据集下两种算法的运行 Seq-mdp算法中多维模式挖掘伪代码描述如下: 情况。 输入:投影数据库D,最小支持数 ensue 从图2可以看出,当维度不变,支持度不断增大时,两种算 1902008,44(6) Computer Engineering and Applications计算机工程与应用 算法运行吋间都在增加,但是Seq-mp算法增加的要缓慢,因 eq-mdp算法 而在时间性能上要优于Seq-Dim算法,尤其在维度比较高时 图4显示了不同数据集下两种算法的运行情况,可以看出在数 据集不断增大时,Seq-Dim算法花費的时间要比Seq-mp算 法多。 5结束语 00.20.30.40.50.60.7 本文提出了一种有效的多维序列模式挖掘方法Seq-mdp 支持度/% 图2不同支持度时的运行情况 算法,首先挖掘序列模式,然后对每个序列模式构造投影数据 库,扫描投影数据库得到频繁1-项集后,不断对频繁(k-1)-项 Seq-mdp算法 集作连接生成频繁k-项集,进而得到多维模式。该方法减少了 100 扫描投影数据库的次数,只对不断减小的频繁(k-1)-项集扫 描,因而节约了时间开销,实验表明了算法有较好的性能。 多维序列模式挖掘有着广阔的应用前景,如何进一步提高 算法的挖掘性能,以及如何加入一些时间和分类等约束,是有 待于进一步研究的问题 0 78 维度 参考文献 图3不同维度时的运行情况 [1] Agrawal R, Srikant RMining sequential patterns(CyiProc of the llth 120 Int Conf on Data Engineering, Taipei, Taiwan, 1995: 3-14 100 算法 [2 Pinto H, Han J, Pei J, et al. Multi-dimensional sequential pattern mining [CV/Proc of the 1Oth Int Conf on Information and Knowl edge Management, Atlanta, Georgia, 2001: 81-88 3 Pei Jian, Han Jia-wei Mining sequential patterns by patter-growth the PrefixSpan approach[J]. IEEE Transactions on Knowledge and Data engineering,2004,16(11):1424-1440. [4 Beyer K, Ramakrishnan R Bottom -up computation of sparse and 数据集 图4不同数据集时的运行情况 iceberg cubes[C]//Proc 1999 ACM-SIGMOD Int Conf Manage ment of Data(SIGMOD99 ), Philadelphia, PA, 1999: 359-370 法的执行时间都在减小,但是Seq-mdp算法的时间性能要明5] Ayres J, Gehrke j.Seqμ uential pattern mining using a bitmap repre 显优于seq-Dim算法。图3是在给定支持度不变的情况下,维 sentation(CV/proc of the 8th ACM SIGKDD Int Conf on Knowled 度不断变化时的情况,从图中可以看出,随着维度的升高,两种 Discovery and Data Mining, Edmonton, Alberta, Canada, 2002: 429-435 (上接141页) 并且不会带来使接入时延增加的问题,因此,提出的算法是 法比UGS算法和rPS算法具有更高的吞吐量,而且提岀的算IEEE802.16系统中一种有效可行的VoIP服务调度算法。 法可以使系统具有更高的上行链路容量,支持更多的VoIP用 户。从图中可以看出,在仿真环境下,UGS算法、rPS算法和提参考文献: 出的算法支持的最大用户数分别为40、61和72,与UG算法1IEE802.16-200 eee standard for local and metropolitan area 和rPS算法相比,提出的算法使系统的吞吐量和上行链路容 networks-part 16: air interface for fixed broadband wireless access 量分别提高为原来的1.8倍和1.2倍。另外,可以证明,在其它 systems[S2002-04-08 仿真环境下,提岀的算法在吞吐量和上行链路容量方面依然具[2] Brady P T. A model for generating ON- OFF speech patterns i 有最优的性能,因此可以说提出的算法是IEE802.16系统中 two way conversations[J]. Bell Syst Technology Journal, 1969, 48(7): 种较好的VoP服务调度算法。 2445-2472. [3 Ozer S Z, liou S P Performance analysis of CDMA systems with 5结束语 integrated service[J]. Vehicular Technology, 2003, 52(4): 828-836 [4 Lee H, Kwon T, Cho D H, et al. Performance analysis of scheduling 本文提出了应用于IEE802.16系统中的一种基于语音 algorithms for VolP services in IEEE 802. 16e systems[C]/Vehicu 活动检测的Ⅴo服务调度算法,它利用MAC通用报头中的一 lar Technology Conference, VTC 2006, 2006,3: 1231-1235 个预留比特将语音状态的转换告知BS,BS根据SS的语音状51IE802.l68-200 EEE standard for local and metropolitan 态转换来分配上行链路资源。文章就吞吐量和接入时延两方面 area networks-part 16: air interface for fixed and mobile broad 将此算法与传统的UGS和rPS算法作了较。结果表明,提出 band wireless access systems-Amendment for physical and medi 的算法不但解决了传统算法的缺点,而且具有更高的吞吐量, um access control layers for fixed and mobile operation in li- 能够使系统具有更高的上行链路容量,支持更多的VoIP用户 censed bands[S].2005-05-20

...展开详情
试读 4P 论文研究-基于最近共享邻居节点的K-means聚类算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743968 欢迎大家使用并留下宝贵意见
2019-09-12
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于最近共享邻居节点的K-means聚类算法.pdf 6积分/C币 立即下载
1/4
论文研究-基于最近共享邻居节点的K-means聚类算法.pdf第1页

试读结束, 可继续读1页

6积分/C币 立即下载 >