论文研究-安全协议的规范化设计.pdf

所需积分/C币:5 2019-09-08 12:00:34 572KB .PDF
收藏 收藏
举报

针对现有自顶向下挖掘算法的不足,即在非频繁项目产生子集时和修剪重复产生的子集时存在冗余计算,提出一种基于定位子集的自顶向下挖掘算法,其适合于挖掘较长频繁项目集;算法按自顶向下策略用定位子集的方法产生非频繁项的子集,并有效地修剪冗余子集和减少重复计算,提高了算法的效率。实验证明,与现有的自顶向下挖掘算法相比,该算法是快速而有效的。
1442011,47(18) Computer Engineering and Applications计算机工程与应用 Step I-Frequentlll Step l-CandidatelI Step2-NFrequent[L Step2-CandidatellL value value length SumsubsetNo 0 SumsubsetNo o Sumsubsetnoo subset〖0 itemNo[o410,1,2,.3.4 itemNo[0-4■1,2,3,4 imNO0聊2,4 Step 2-Candidate [21 itemnol0-21.3.4 产生子集 第一次产生子集 第二次产生子集 Step 2-Candidate [3]- 形成候选项 ums litemNo0-21124 Step1-Candidate[21 生子集 Order值 Step2-Candidate[41 value 14 length 频繁项 ④口enth 产生的子集个数 SumsubsetNo3 itemNo0-30.2.3. 4 LitemNo[-2LL1 2.3 reque FRequent[]. SumsubsetNo Step l-Candidate[31 Step2-NFrequent(] 1 Step 2-Candidate[51 value Sumsubsetno■2 SumsubsetNo Sumsubsetno■2 需要删除的位 temNo0=3■0,1,3,41 itemNo[0-3■0,1,3,4 itemNo0-21■0,1,4 FRequent[i]. SumsuhsetNo (Order-1) Step l-Candidate[41 Step2-Candidate[61 11 频繁项 SumsubsetNo SumsubsetNo 喊 itemNo[0-3]10,1,2,4 titemNo0-21 10 1.3 Step l-Candidate 51 Step2 FRequent 3■ ■15 15 length 产生0个子集 SumsubsetNo Sumsubsctno itemNo0-30,1,2,31 itemNo-3]0,1,2、3 图1产生子集及修剪重复子集的过程图 中值分别为D21, DT.length-m, DT. SumsubsetNo,3算法性能分析及实验比较 DTitem No[0]=0,…, itemNo[1,…, itemNolm-1]l=m-1。 31性能分析 举例:F={1,2,3,4,5},从最大项目集的数字事务31开始 ATDMBOS算法除了自身特有的定位子集方法以外,还 若其不为频繁项,则宀生子集及修剪重复子集的过程如图所用基于二进制挖掘算法的特性,即用二进制的逻辑操仵快速 示。由算法可得到6个子集为{28,26,22,14,19,11},用性质2计算支持数和产生频繁候选项。首先为了比较该算法在挖 修剪频繁项{29,23}的子集{8,22,19},其余子集{26,14,l}掘较长频繁项目集时的优势,将其与基于二进制的算法 将作为候选项计算支持数,若全部为频繁项,将终止算法,否B_ apriori进行比较;其次,为了体现该算法在同类长频繁项 则重复执行。 挖掘算法中的优势,将其与现有的自顶向下挖掘算法 DMFIA 24算法的挖掘步骤 和 Top-Down-Miner2进行比较。根据 B Apriori中的相关理 设项目属性有m个,数据库中事务总数为N个,不重复事论按DMFA和 Top-Down-Miner算法思想,实现 B DMFIA和 务数为n。定义符号如下。 B_ TopDownMiner算法。 B Apriori和 ATDMBOS算法的特性 D:存放数字事务n个,包含√e和coum;,:存放挖掘得将在实验中比较,在此主要介绍 B DMFIA B Top DownMiner 到的所有频繁数字事务。 和 ATDMBOS算法在实现“一个k项非频繁项目集生成(k-1) S(i=1,2):存放自顶向下得到的同长度的数字事务 项频繁候选项”时的不同之处。 B DMFIA算法计算主要有三部分:(1)在修剪非频繁项包 步骤1将数据库的事务转换成数字事务存入D中, value 含的项目时,每次要构造 FP-tree,对包含在非频繁项中的每个 存数值和 count存重复事务数。 项目进行刖除,最后计算生成子集;(2)当多个k项非频繁项 步骤2用DT表示事务{,b,…,1,若其为频繁数字事目集有交集在时将会有重复(k-1项子集生成此时要用 务,则将D7存入F中结束算法;否则根据23节产生D的所生成的子集比较,判别是否为重复子集,避免生成重复候选 有长度为k(k=m-1)的子集,并将其放入S中。 项。(3)在子集变成频繁候选项时,先用性质2修剪频繁项的子 步骒3对S中的每个k项子集 subset,若其不是F中的子集,其余子集才作为频繁候选项,计算其支持数。 集,则计算其支持数;若是频繁数字事务,则将其存入F中,否 B Top DownMiner算法与 B DMFIA有相似之处,利用约 则存入S2中。 简项作为启发和约束信息,压缩频繁项搜索空间,没有组合的 步骤4对S中非频繁数字事务的所有长度为k的数字事过程,克服了类 FP-tree构造,减少了复杂计算。计算包括:(1)k 务,按2.3节方法产生其长度为(k-1)的子集,存入S中。 项-非频繁项目集生成(k-1)项-子集的计算,包括判粞要删除 步骤5重复执行步骤2-4,直到没有子集产生或子集的长项目的计算(2)生成一次约简项的计算。(3)同 B DMFIA部分。 度为2,算法结束。 ATDMBOS算法针对这三个方面的计算情况为:(1)在修 方刚,涂承胜,熊江:一种定位子集的自顶向下挖掘算法研究 2011,47(8)145 剪非频繁项包含的项目时,直接用定位子集方法屮的子集序可知 ATDMBOS算法在挖掘过程屮比 B DMFIA和B_Top 号特性计算生成子集,而无需判断操作,计算方法简单方便, Downminer更有效,这也证眀了前面的算法复杂度分析。 减少了冗余计算;(2)当多个k项-非频繁项日集有交集存在 30000 时,根据定位子集的序号特性修剪,一个子集只会生成一次, 25000+B Apriori +-ADSMBtC 不会有重复了集广生。(3)同前两者 200 可见三个算法的第三部分计算是类似的,这也是自顶向 下算法的共性。对于前两部分,进行如下时间复杂度的分析 起15000 设事务数据库的总记录数为N,对每个记录中的项目集进 110000 行一次频繁项挖掘计算,总计算次数为N;设项目集的平均计 5000 算长度为M,平均约简项的计算长度为S(1≤S≤M),每次生成S 个长度为M-1的候选项目集 B DMFIA算法:如文献[1]所述,计算M,M-1,…,2,1 项目集的支持度/(%)(长度/个) 等不同长度的候选项目集,要计算12M次,每次计算至多为 图3 B Apriori和 ATDMBOS算法的执行时间比较 O(2"),合计计算量为(12M2×O(2“);加上每次构造 FP-tree 的计算量。 B_ Top DownMiner算法:如文献[2J所述,计算M,M-1, 2,1等不同长度的候选项目集,要计算1/2M2次,每次计算至 虹”物 多为O(2),合计计算量为(1/2)M2×((2);再加上生成一次约 简项的计算量MxO(N×N),算法此过程的总共计算量约为 M×O(NxN)×(12)M2×0(2)xN=(1/2)MNxO(2XN2),N是 数据厍生成的元组数。 图4三种算法的实验结果 ATDMBOS算法:只有计算M,M-1,…,2,1等不同长度 的候选项目集,要计算1/2M次,每次计算至多为O(M),总共 1200 的计算量为(1/2)M2×xO(M) .B DMFIA 32实验比较 800 +B TopDuwnMiner s ADSMBtC 为了比较算法的性能,用一组数据进行实验测试,数据库 士600 的情况为:不重复事务数为8178个,转换成数字事务后为3到 400 8191,其中不包含表示数字项目的数字事务,即2(k为非负整 200 数),项目属性为m=13。实验环境为: Intel Celeron M CPu 420@1.60GHz,512MB的内存,操作系统为 Windows Xp 守6<守首 Professional,在 Visual c#2005NET开发平台上实现算法 项日集支持度/(%)(长度/个) B Apriori, B DMFIA B TopDown Miner和 ATDMBOS。 图5三种算法的执行时间比较 (1)算法 ATDMBOS与基于二进制形式的自底向上算法 B Apriori比较 4结束语 两种算法的实验结果如图2所示,图中的支持数为绝对 本文提出的 ATDMBOS算法,适合于挖掘较长频繁项目 数;执行时间随项日集的支持度和长度变化情况如图3所示。集,其按自顶向下簧略用定位子集的方法产生非频繁项的子 从实验结果可知,当长度大于3时, ATDMBOS算法是非常高集和修剪重复了集,减少了冗余计算,提高了算法效率。算法 效的,充分体现了算法在挖掘较长频繁项目集的优势。 适合于基于事务的空间数据挖掘,将其用在海量空间数据中 进行单层布尔型关联规则挖掘是非常高效的。 ”” 参考文献: ]宋余庆,朱玉全,孙志挥,等基于 FP-treeF最大频繁项H集挖掘及 更新算法[软件学报,2003,14(9):1586-1592 [2]王晓峰,王天然,赵越.一种自顶向下挖掘长频繁项的有效方法J 计算机研究与发展,2004,41(1):148-155 图2 B Apriori和 ATDMBOS算法实验结果 [3]陈耿,朱玉仝,杨鹤标,等关联规则挖掘中若干关键技术的研究[ 计算机研究与发展,2005,42(10):1785-1789 (2)算法 ATDMBOS与现有的自顶向下算法 B DMFIA和4孙圣力,黄震华,李金玖,等数据流上高效计算子空间 Skyline的 B_ TopDownMiner比较 算法[计算机学报,2007,30(8):1418-1428 实验结果如图4所示,图中的支持数为绝对数;执行时间5吉根林,杨明,余庆,等最大频繁项日集的快速更新门计算机 随项目集的支持度和长度变化情况如图5所示。从实验结果 学报,2005,28(1):128-135

...展开详情
试读 4P 论文研究-安全协议的规范化设计.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744375 你的留言是对我莫大的支持
    2019-09-08
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-安全协议的规范化设计.pdf 5积分/C币 立即下载
    1/4
    论文研究-安全协议的规范化设计.pdf第1页
    论文研究-安全协议的规范化设计.pdf第2页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >