logo资料库

本文通过对Apriori算法分析，应用散列、事务压缩、划分、抽样等方法，最大可能的减少数据库扫描的次数，快速发现频繁项集，提高A....doc

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.21M 资料格式：doc 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    关联规则挖掘 Apriori 算法效率提高方法研究 班 级： 计算机技术班 学 号： 姓 名： 指导教师： 信息学院 2016 年月
    关联规则挖掘 Apriori 算法效率提高方法研究 摘 要 Apriori 算法是关联规则挖掘中的经典算法。在 Apriori 算法中，使用频繁项 集的先验知识，逐层搜索的迭代方法，通过扫描数据库，累积每个项的计数，并 收集满足最小支持度的项，找每个 kL 都需要扫描一次数据库。算法的效率随着 数据量的增大，频繁项集的增多，算法的效率就非常的低，本文通过对 Apriori 算法分析，应用散列、事务压缩、划分、抽样等方法，最大可能的减少数据库扫 描的次数，快速发现频繁项集，提高 Apriori 算法的效率。 关键字 关联规则；Apriori 算法；效率；提高方法 0 引言 关联规则揭示数据间的相互关系，关联规则挖掘试图从一组给定的数据项以 及事务数据库(每个事务是一个数据项的集合)中，筛选出数据项集在事务数据库 中出现的频度关系。关联规则挖掘可以发现大量数据中数据项集之间有价值的关 联或相关联系。 关联规则挖掘问题首先是由 R.Agrawal 等于 1993 年提出 ,其后许多的研 究人员对该问题进行了广泛的研究,主要集中在改进关联规则挖掘算法以提高挖 掘的效率等和推广关联规则挖掘应用两个方面。至今,最经典的关联规则挖掘算 法仍是由 R.Agrawal 等提出的 Apriori 算法 ,该算法的主要思想是首先寻找给定 大数据集中的频繁项集 ,然后通过频繁项集生成强关联规则。寻找频繁项集步骤 的核心思想是用前一次扫描数据库的结果产生本次扫描的候选项目集,从而提高 搜索的效率 。在数据挖掘中，Apriori 算法是布尔型关联规则挖掘频繁项集的原 创算法，算法使用了频繁项集的先验知识，使用一种称作逐层搜索的迭代方法， k 项集用于探索（k+1）项集。首先通过扫描数据库，累积每个项的计数，并收 集满足最小支持度的项，找出频繁 1 项集的集合。该集合记作 1L 。然后， 1L 用 于找频繁 2 项集的集合 2L ， 2L 用于找 3L ，如此下去，直到不能再找到频繁 K 项 集。找每个 kL 需要扫描一次数据库。这样，算法的效率随着数据量的增大，频
    繁项集的增多，算法的效率就非常的低。 关联规则的一个例子是“90 % 的顾客在购买面包和黄油的同时也会购买牛 奶” ,表示顾客在购买某些商品时很可能会同时购买其它的一些相关商品。发现 这样的规则有助于商品货架设计、库存安排及根据购买模式对用户进行分类。 已有的关联规则挖掘算法及其相关改进算法主要是针对压缩候选项集、减少 扫描数据库次数等方面的,而很少涉及从数据库本身的角度来考虑算法的改进。 笔者在实际研究过程中发现,在扫描数据库的某些遍中一些记录对频繁项集的产 生是无贡献的 ,也即在频繁项集产生的过程中数据库中的有些记录可以被忽略。 因此,文中在此基础上提出了一种新的关联规则挖掘改进算法。 1.关联规则的基本概念 设I={i1,i2,…,im}是项的集合，设D={T1,T2,…,Tn} 是与任务相关的数据 库事务的集合，其中每个事务是项的集合，使得 iT I 。 设 A 是一个项集，包含 k 个项的项集称为 k  项集。事务 iT 包含 A 当且仅当 A I 。事务集 D 中项集 A 的支持度 sup(A)是 D 中包含 A U B 的事务的百分比， i 即 sup(A)=P(A U B)。若 SUP(A)≥min_sup，其中 min_sup 是给定的最小支持度， 则称 A 为频繁项集。 关联规则就是形如 A B 的蕴涵式，其中 A B 在事务集 D 中的置信度 conf( A I ，并且 A B   。 I ， B B )是 D 中包含 A 的事务同时 关联规则 A 也包含 B 的事务的百分比，即 conf( A B )=P( |B A)。 因此。关联规则挖掘问题可以转为两个子问题： (1)找出所有频繁项集，这些项集满足预定义的最小支持度(min_sup)。 (2)由频繁项集产生强关联规则，这些规则必须同时满足最小支持度(min_sup) 和最小置信度(min_conf)。问题(2)实现简单容易。关联规则挖掘算法的性能主要 集中在问题(1)上，大部分算法都集中在如何高效发现频繁项集。 目前，已提出许多关联规则挖掘的算法，其中由 R.Agrawal 等首先提出的 Apdori 算法是一种较有效的频繁项集挖掘算法。该算法的基本思想是利用一个层 次顺序搜索的迭代方法来完成频繁项集的挖掘工作，即利用 k  项集来生成 ( k   项集，用候选项集 1kC  找频繁项集 kL 。首先，找出频繁1 项集的集合， 1)
    记作 1L ， 1L 用于找频繁 2  项集的集合 2L ，而 2L 用于找 3L ，如此下去，直到不 能找到频繁 k  项集。找每个 kL 需要一次数据库扫描。一旦从数据库的事务 D 中 找出频繁项集，就可以根据最小置信度直接产生强关联规则。算法的缺陷是：可 能需要产生大量的候选项集，Apriori 可能需要重复地扫描数据库，通过模式匹 配检查一个很大的候选集合。 2 算法改进 2. 1Apriori 算法思想 在已有的关联规则发现算法中，最著名的是 Agrawal 等人于 1993 年提出的 Apriori 算法。Apriori 算法是一种宽度优先算法，算法步骤如下： ①扫描事务数据库 D，对遇到的每个事务分析其中出现的数据项，如果第一 次遇到该数据项，则加入候选1 项集的集合 1C ，并将它的计数值设置为 1；如 果该数据项已加入 1C ，则将它的计数值加上 1，这样就得到了候选1 项集的集 合 1C (其中每个数据项集只包含一个数据项)。扫描 1C ，删除那些出现计数值小于 minisupport 的项集，这样就得到了1 频繁项集的集合 1L 。 ②一般地，假设 1kL  已生成，现在可用它来生成 kL ， 1kL  与自身进行连接( 1kL  中的每个项集与其他项集相互连接)，得到候选 k  项集的集合 kC 。 ③对 kC 进行剪枝，从 kC 中删除所有 ( k   子集不全包含在 1k  中的项集。 1) ④扫描数据库事务 D，对于其中的每一个事务，如果它包含 kC 中的候选项 集 c，则将 c 的计数值加 1(在扫描之前，初始值为 0)。扫描 kC ，删除那些出现计 数值小于给定支持度的项集，这样就得到了 k  频繁项集的集合 kL 。 ⑤重复②到④，直到 kL 为空。 ⑥对 1L 到 kL 取并集即为最终的频繁集 L。 2.2Apriori 算法的缺陷 根据对 Apriori 算法的分析，关联规则挖掘可以比较有效地产生关联规则，
    但是也存在算法效率不高的严重缺陷。 主要原因如下： ①数据库扫描的次数过多，寻找每个 k  频繁项集(k=1，2，⋯，k)都需要扫 描数据库一次，共需要扫描 k 次。因此当数据库或者 k 太大时，算法的耗时将太 大甚至无法完成。 ②算法的剪枝步， c C  ，判断 c 的 k 个 ( k k   子集是否都在 1kL  中，若 1) 找到一个 ( k   子集不在 1kL  中就淘汰 c。因为这个过程会多次扫描 1kL  ，特别 1) 是当生成的 kC 很大时，算法的效率并不理想。 2. 3 Apriori 算法效率提高方法 因为关联规则挖掘过程面对的是大规模数据库,导致挖掘算法效率较低的因 素一是产生的候选项目集数量庞大 ,其次是数据库中的记录数很多导致过多的 I/O 开销。所以提高关联规则挖掘算法的效率可以从以下 3 个方面考虑: （1）减小候选项集 kC 的规模。Apriori 算法及已有相关改进算法对从候选 k 项集 kC 中产生频繁项目集 kL ,是通过扫描数据库分别计算每个候选项的支持计 数来完成的。通过上文的分析,在候选项集 kC 产生后、扫描数据库计算每个候选 项的支持计数之前,可以先判断 kC 中每一元素 X 的 1k  项子集是否是 1kL  的子 集 。若是,则将 X 保留在 kC 中,继续判断 kC 中的下一个元素; 否则将 X 从 kC 中删除。实验证明,很多情况下这样先通过 1kL  对 kC 进行预先剪枝可以大大减少 kC 的规模 。 （2）在扫描数据库的过程中忽略对频繁项目集 kL 中所产生的无贡献的交易 记录,即减少扫描数据库时实际需要对其进行操作的交易数 。 在一次扫描数据 库由候选项目集 kC 确定频繁项目集 kL 的过程中,若某条交易记录 T 不包含候选 项集 kC 中的任一元素 ,则可通过将该交易记录的标识号置为空（如 0）以在下一 次扫描数据库时直接跳过该记录。因为若 T 不包含 kC 中的任一元素,也必不包
    含 1kC  的任一元素 。 （3）通过程序优化提高算法效率 。很多研究工作者在关联规则挖掘算法研 究过程中,往往只注重对算法策略的考虑,而忽视对程序进行优化 。良好的数据结 构 、编程风格及程序优化等对算法的效率是有影响的。例如 ,作者通过实验在 JAVA 语言中使用文件缓冲与未使用文件缓冲策略对 Windows 操作系统文件 Shell32. dll 进行读操作所耗时间比约为 3∶ 100。 3.算法实现 采用一个实际超市交易数据集进行实验并与 Apriori 算法进行比较,数据集 中共有交易记录 3000 条,交易商品种类( 即项目数) 为 88 。 实验环境为 Pentium Ⅳ 2. 6GMHz ,512M 内存,Win-dows XP 操作系统,编 程语言为 JAVA 。 图 1 显示了在最小可信度阈值为 0 . 6 时的不同支持度阈值下 ,分别用 Apriori 算法及改进后的算法对交易数据进行关联规则挖掘时所耗时间 。 实验表明 ,改进后的算法基本上总是优于 Apriori 算法的 ; 并且当支持度 阈值较小时,改进算法的效率有更明显的提高 。 通过实验也发现当数据库规模较小、数据库中包含的项数较小时,改进算法 的效率没有明显的提高 。这是因为改进算法主要是针对减少候选项的数量 、及 跳过对于频繁项目集产生无贡献的记录的考虑而获得性能改进的。当数据库包含 的项数较少时,通过连接操作产生的候选项数也较少 ; 当数据库规模较小时,扫 描数据库过程中忽略的记录也较少 ,所以在这种情况下,由于整个挖掘过程的所 耗费的时间较少,从而改进算法的效率提高不明显 。
    图 1 两种算法在不同支持度下的时间性能比较 4.结论 文中对关联规则挖掘的经典算法 Apriori 算法进行了讨论分析,研究了相关 的性质,提出从减少候选项数及减少实际需要考虑的交易记录数的角度改进挖掘 算法的思想,并通过实验证明了改进方法的有效性与正确性 。 关于关联规则挖掘研究的下一步研究方向可以是研究面向分布式环境下的 关联规则挖掘问题,研究结合背景知识的关联规则挖掘问题。 参考文献 [1] 区玉明，张师超，徐章艳，等．一种提高 Apriori 算法效率的方法[J]．计算 机工程与设计，2004，25(5)．846—848． [2] 周焕银，张永，蔺鹏．一种不产生候选项挖掘频繁项集的新算法[J]．计算 机工程与应用，2004，40(15),45—46． [3] 马盈仓．挖掘关联规则中 Aprion 算法的改进[J]．计算机应用与软件，2004， 21(11)：82—84． [4] Agrawal R, Imielinski T, Swami A. Mining Association Rules Between Sets of Items in LargeDatabases[ A] . In: Proceedings of 1993 ACM -SIGMOD International Conference Management of Data( SIGMOD' 93) [ C] . Washington D. C . : [ s. n. ] , 1993 . 207-216. [5] Agrawal R, Srikant R. Fast algorithms for mining association rules in large
    database[ R] . Technical Report FJ9893 , San Jose, CA: IBM Almaden Research Center, 1994. [6] Agrawal R, Srikant R. Fast algorithms for mining association rules[ A] . In: Proc of 20th Int Conf Very Large Databases ( VLDB' 94) [ C] . CA: [ s. n. ] , 1994. 487 -499 . [7] 徐瑞, 乔志萍, 李伟华. 单维关联规则快速 Apriori 算法研究[ J] . 微电子学 与计算机, 2005 , 22( 2): 43-45.
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料