论文研究-一种基于数据压缩的Apriori算法.pdf

所需积分/C币:10 2019-09-10 19:39:31 535KB .PDF
收藏 收藏
举报

随着物联网技术的飞速发展,数据采集手段迅速增加,对海量数据分析与处理的需求也愈加强烈。关联规则挖掘算法通过数据之间的关联分析,挖掘出数据之间的隐含关系,进而获得了大量应用。在众多的关联规则算法中,传统的Apriori算法虽然得到了大量应用,但是因为该算法产生大量的候选集,而且需要多次对数据库进行扫描,导致该算法的运行效率大大降低。为了克服Apriori算法的以上缺点,通过数据压缩的方法减少了数据库扫描次数的同时,对生成的候选集进行了多次验证,大大减少了无效候选集的数量。大量的数据挖掘实验证明提出的改进算法可以在正确挖掘数据集关联规则的同时,大大提高了算法的运行效率。
高海洋,沈强,张轩溢,等:一种基于数据压缩的 Apriori算法 2013,49(14)119 集,即(keyc)=Ck={,1…,1,那么 算法的执行时间。当最小支持度较小吋,产生的频繁集较 多,原有算法扫描数据库的开销较大,算法在速度方面提 sup(Ck)=2 H(key ) d(keyc)sd(key) 升幅度大,随着最小支持度的增加,满足最小支持度的频 详细的实施步骤如下所述: 繁集的数量逐渐减少,算法消耗的时间在减少,因此,在最 (1)对于候选集C=1,1……,1}.调用f(C)生成keyc 小支持度递增的条件下,时间提升的百分比呈递减趋势 如表1所示。图2所示的是改进后算法与原有算法在生成 (2)因为对于任意两个项集A,B,若A≌B,那么候选集数的量方面的比较,这里以三项候选集为例,其中 bivector≤ bivector即keyA≤ kev.o 横轴表示支持度,纵轴表示生成三项候选集的数量。不同 所以包含CA的项集所对应的key均大于或等于keyc,的支持度下,3项选集的数量减少百分比如表2所示。随 因此从冂B_Map_ Table中距离ke。最近处开始顺序向后着最小支持度的增加,产生的候选集的数量呈递减趋势, 遍历直到找到所有满足条件C的项集 当最小支持度为25%时,经过检测,所产生的侯选集的数量 (3)在步骤(2)扫描过程中,对于每一个满足条件为0,候选集的数量减少100%,算法中止 key≥keyc的键值,调用函数a(key),d(key)实现过程如下 L将ky转换为2进制向量 0 原有 Apriori算法 从/={112…}中选出第 项组成key对 改进的 应的项集l-{ 支持度(% 若(kec)cd(kep), 图1原有 Apriori算法与收进的 Apriori算法 则令sD(l)=8p()1H(key) 运行时间的比较 当到达 DB Map tablc末尾时,此过程结束 表1不同支持度下算法运行时间白分比 通过对数据库的访问优化,减小了原有数据库信息量 的规模,将数据库的扫描次数减少为一次,而使用经过排 支持度 时间提高的百分比 序处理的 DB Map Tablc,可以提高査询的速度,减少存储 空间的使用。本方法采取了以空问换取时间的策略,在压 缩的过程中,为了能将数据库的信息完整的保存,增加了 对内存空间的需求。 32候选集检测 250 当使用 Apriori算法由n-1项频繁集L,生成n项候 2()) 选集C(n>2)时,需每次从n-1项频繁集Ln1(L,-1= l50) 原有 Apriori算法 {1,2…,l})中选出没有合并过的两个元素x,l1,如果 这两个顶集的前n-2项相同,第n-1项不同,则它们符合 改进的 Apriori算法 原始算法的合并条件。本文在此基础上额外加入新的判 断条件,判断将要合并的两个频繁集l、1中不同的两项 支持度% x,l1(xcl,lcl)所组成的二项集lxy={l,l1}是否是 图2原有 A priori算法与改进的 Apriori算法 二项频繁集L,的子集,若 L CL2,则将l2Ul加入候选集 生成3顶候选集数量的比较 的集合Cn中,否则将xl丟弃 表2不同支持度下3项候选集 的数量减少百分比 4验证 支持度 侯选集数量减少百分比 为了验证改进后算法的效率,设计实验从算法运行速 度和产生候选集的数量两个方面,将改进后的算法与原有 10 的 Apriori算法进行分析比较。所有程序都基于Java SDK1.60编写。仿真环境:CPU为 Pentium dual-Core 100 3.0GH;主存为200GB;操作系统为 Windows7。数据集 是某超市最近几年的销售记录。图显示的是改进后算法5结束语 与原有算法执行时间的比较,横轴表示支持度,纵轴表示 数据库经过去重压缩处理之后,数据库的信息被无损 120 013,49(14) Computer Engineering and Applications计算机工程与应用 地保存在 DB Map Table中,这种方式可减少数据库的扌14| Parks, Chen MS, Yu P sAn effective hash- based algo 描次数,提高算法的效率。使用映射表进行存储,可提高 rithIn for Inlining associalion rules[ C]/Proceedings of ACM 存储空间的利用效率,同时借助key在 DB Map tablo中 SIGMOD Internalional Conference on Manayement of Data 递增排列的特点,在求某一个侯选集的支持度时,可以不 1995:175-186 用遍历整个 DB Map Table,仅从包含该候选集的最小单 5 Savasere A, Omiecinski e, Navathe. An efficient algorithm 元开始遍历 DB Map Table即可,这样可以降低查询操作 for mining association rules in large databases[C]/Proceed 的时间复杂度。另外,对生成的候选集进行了多次验证 ngs of the 2 i st International Conference on Very I,arge 大大减少了无效候选集的数量。本文成功地将提出的改 Database, 1995: 4 进算法应用到了防入侵应用验证平台中,通过对该平台16Bms. Motwani R, Ullman J D, et al. Dynamic Itemset count- 定位精度,漏报率,误警率,自然条件等多项属性的挖掘分 ing and implication rules for market basket dala CiACV 析,发现了影响该平台性能的诸多隐性因素,为平台中传 SIGMOD Internalional Conference on the Managenient o[ 感器的改进提出了有价值的参考。 Data,l997:255-264 [7 Mannila H, Toivonen H. Verkamo A Efficient algorithm for 参考文献: discovering association rules[C]/ AAAI Workshop on Know ledge Discovery in Databases, 1994: 181-192 l1 Shen Q, Liu Y, Zhao Z, et al.Distributed Hash table based 3 Han J, Pei J, Yin Y Mining frequent patterns without candi- II)management optimization for Internet af things[C] WCMO date generation[CProc 2000 ACM-SIGMOD Int Cont 2010:686-690 Managernent of Dala( SIGMOD 00), 2000: 1-12 [2 Agrawal R, Imielinski T, Swami A Mining association rules between sets of items in large databases[C]/Proceedings of [9] Mannila H. Toivonen H, Verkamo IEfficient algorithm for Lhe ACM SIGMOD Conference on Management of data discovering association rules[C]//AAAl Workshop on Kno 993:207-216 ledge Discovery in Databases, 1994: 181-192 [3] Agrawal R, Srikant R Tast algorithms for mining association [0] Wu Iihing, rong Ku, Hc Yanxiang ct aL.A study of improv rulcs in large databasc[C]proceedings of thc 20th International ing A priori algorithm[C]/2010 2nd International Work shop Conference on Very Large Data Bases, 1994: 487-499 on Intelligent Systems and Applications( ISA), 2010: 22-23 上接108页) [3 Wong C K, Coppersmith D A combinatorial problem related 传统的L型瓦来进行研究,文献[9采用了矩阵等T具,与 to multi-module memory organizations[J].Association for 这些文献不同的是本文通过其等价的直角坐标系下的构 Compuling Machinery, 1974. 21(3): 392-402 图来研究容错路由。根据无向双环网络的特点,将其节点4 armon. mellat, su D F Distributed loop com. 以无故障最优路由的方式等价的映射到直角坐标系屮,形 purer networks: a survey J. Parallel and Dilribuled Compul- ng,1995,24(2):2-9 成一种最优路由构图,基于这个构图,来讨论源节点和目 15 Hwang F KA complementary survey on double-loop net 的节点之问的路由。提出了故障节点封闭区和逃逸区等 works.Theoretical Computer Science, 2001, 263: 211-229 概念。当源节点和凵的节点周围出现故障节点封闭区的[6 Mukhonadhyava K, Sinha b P. Fault-tolcrant routing in dis 情况时,最优路由不能进行,通过增加等价节点形成一个 tributed loop networks[]. IETf Trans on Computers, 1995 扩展的最优路由构图,基于这个图来寻找跻由算法。最后 44(12):1452-1456 提出了两种构图的枃造算法,以及容错路由算法。算法的[7] Peha J M, Tobagi F A. Analyzing the fault tolerance of double 时间开销主要在构图上为O(m),而最优路由的构造为常数 loop networks[J].IEEE/ACM Trans on Networking, 1994, 4 级;存储空间开销为O(n)。 [8 Liu Yuling, Wang Yueli, Guan D J.An optimal fault-tolerant routing algorithm for double-loop networks[J]. IEEE Trans 参考文献: l!刘辉,方木公,杭婷婷,等直角坐标系下双环网络GM,)容9] Dharmasena H P, Yan XinAn optimal fault-tolerant routing 错路由研究[华中科技大学学报,2010,38(10):43-4 algorithm for weighted bidirectional double-loop networks[JI [2]方木云,赵保华.一种新的无向双环网络G(N;±1,±s直径求 IEEE Trans on Parallel and Distributed Systems. 2005.16 解方汏[通信学报,2007,28(2):124-129 (9):841-852

...展开详情
试读 4P 论文研究-一种基于数据压缩的Apriori算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744270 你的留言是对我莫大的支持
    2019-09-10
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种基于数据压缩的Apriori算法.pdf 10积分/C币 立即下载
    1/4
    论文研究-一种基于数据压缩的Apriori算法.pdf第1页
    论文研究-一种基于数据压缩的Apriori算法.pdf第2页

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

    10积分/C币 立即下载 >