毕业设计（论文）-基于映射和逻辑运算的Apriori算法优化.doc

本本 科科 生生 毕毕 业业 设设 计计 ( (论论 文文) ) 题目：基于映射和逻辑运算的题目：基于映射和逻辑运算的 aprioriapriori 算法优化算法优化 mapping and logic computing based on improved apriori algorithm 教学单位教学单位 ： 姓姓 名名 ： 学学 号号 ： 200631104116200631104116 年年 级级 ： 专专 业业 ： 软件工程软件工程 指导教师指导教师 ： 职职 称称 ： 讲讲 师师 20102010 年年 5 5 月月 1 1 日日 基于映射和逻辑运算的 apriori 算法的优化 i 目录目录 摘要摘要.ii abstractiii 第一章第一章 绪论绪论 1 1.1 本文研究背景.1 1.2 本文的研究目的及工作.1 第二章第二章 关联规则关联规则 传统传统 apriori 算法算法.2 2 关联规则.2 2.1 apriori算法 3 2.2 apriori算法 pad .4 2.3 apriori算法优点及问题 5 第三章第三章 改进的改进的 apriori 算法算法.6 3.0 apriori算法的强关联规则 - 以购物篮系统为例.6 3.1 改进的基于映射和逻辑运算的 apriori算法6 3.2 改进 apriori算法示例与分析9 3.3 算法分析.19 第四章第四章 总结与展望总结与展望 22 4.1 总结.22 4.2 展望.22 参考文献参考文献 23 致谢致谢 24 基于映射和逻辑运算的 apriori 算法的优化 ii 摘要摘要 摘摘 要要关联规则是数据挖掘研究的一个重要分支，其反映了海量数据间的有意义的关 联。而 apriori 算法作为最经典的算法之一备受推崇的同时也存在着如下问题：多次扫 描数据库，候选集巨大，时间和空间复杂度过高等。针对这一问题，本文在分析传统 apriori 算法后，提出了基于映射和逻辑运算改进的 apriori 算法，该改进算法大大提高 了数据挖掘的效率。 关关 键键 词词apriori 关联规则 数据挖掘 基于映射和逻辑运算的 apriori 算法的优化 iii abstract abstractassociation rules is an important branch of data mining, which reflects a meaningful association in mass data. the apriori algorithm is one of the most highly regarded classical algorithms, while there are also some questions such as: multiple scans of database, colossal candidate sets, high time and space complexity. to solve this problem, this paper presents an improved apriori algorithm that is based on mapping and logic computing after introducing and analyzing traditional apriori algorithm. the algorithm can significantly improve efficiency of apriori algorithm. keywords apriori association-rules data-mining 基于映射和逻辑运算的 apriori 算法的优化 1 第一章第一章 绪论绪论 1.11.1 本文研究背景本文研究背景 数据挖掘是一种从大量数据中提取出隐含的、未知的、潜在的和有用的信息的 过程。数据挖掘技术和数据库知识发现（knowledge discovery in database，kdd） 都是近年来随着数据库技术、人工智能技术，以及计算机科学技术的发展而出现的 一种全新信息技术。 本文以商场购物篮系统为研究背景，利用 apriori 算法挖掘出客户购买商品种类 之间的强关联规则，由此来达到了解客户购买习惯，进而使商家可以使销售策略有 章可循来达到利润的突破。 1.21.2 本文的研究目的及工作本文的研究目的及工作 本文研究工作源于上述背景，对传统的关联规则算法 apriori 进行研究分析, 在 此基础上对传统算法进行优化，同时 code 实现改进的 apriori 算法，验证其有效性。 本文主要工作： （1）介绍关联规则以及相关概念。 （2）介绍传统 apriori 算法并分析其缺陷。 （3）通过对 apriori 算法的性质研究针对其缺陷优化，并给出严格的数学论证。 （4）设计出优化的算法，并编码实现。 （5）对其性能进行算法分析。 基于映射和逻辑运算的 apriori 算法的优化 2 第二章第二章 关联规则关联规则 传统传统 apriori 算法算法 2 2 关联规则关联规则 设 d 是交易(transaction) t 的集合，d=t1,t2,t3tn，这里交易 t 是项的集合，可 以表述为：t=t1,t2,tp并且 td。t 中的元素 ij=j=1,2,p称为项。对应每一 个交易有唯一的标识交易号，记作 tid。设 i=i1,i2,im是数据集中所有项的集合， i 中的任何子集称为项目集(itemset)，记项的个数|x|=k，则称集合 x 为 k-项集。设 tk 和 x 分别为 d 中的事务和项目集，如果 xtk，称事务 tk 包含项目集 x。项目集 x 的支持度为 support(x),若 support(x)不小于用户指定的最小支持度(记作： minsupport)，则称 x 为频繁项目集，否则称 x 为非频繁项目集。设 x，y 是数据集 d 中的项目集。若 xy，则 support(x)=support(y)；若 xy，如果 x 是非频繁 项目集，则 y 也是非频繁项目集；若 xy，如果 y 是频繁项目集，则 x 也是频繁 项目集。 一个关联规则是形如 x=y 的蕴涵式，这里 x，y 都是项目集，且 x 与 y 包含 于同一个事务中，并且 x 与 y 的交集为空，x，y 分别称为关联规则 x=y 的前提 和结论。 一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的 属性。 （1）支持度 规则 x=y 在数据库 d 中的支持度(support)是交易集中同时包含 x，y 的事务 数与所有事务数之比，记为 support(x=y) = support (x u y)。支持度描述了 x,y 这 两个项集在所有事务中同时出现的概率。 （2）置信度 规则 x=y 在事务集中的置信度(confidence)是指同时包含 x，y 的事务数与包 含 x 的事务数之比，它用来衡量关联规则的可信程度。记为 confidence(x=y) = support(x u y) / support(x)。 一般情况下，只有关联规则的置信度大于期望可信度，才说明 x 的出现对 y 的 出现有促进作用，也说明了它们之间的某种程度的相关性。给定一个事务集 d，挖 掘关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和 最小置信度的关联规则。关联规则挖掘的任务就是要挖掘出 d 中所有的强规则 x=y。强规则 x=y 对应的项目集(x u y)必定是频繁项目集，频繁项目集(x u y) 导出的关联规则 x=y 的置信度可由频繁项目集 x 和（x u y）的支持度计算。 基于映射和逻辑运算的 apriori 算法的优化 3 因此，可以把关联规则挖掘划分为两个子问题：一个是找出所有的频繁项目集： 即所有支持度不低于给定的最小支持度的项目集。另一个是由频繁项目集产生强关 联规则：即从第一个子问题得到的频繁项目集中找出置信度不小于用户给定的最小 置信度的规则。其中，第一个子问题是关联规则挖掘算法的核心问题，是衡量关联 规则挖掘算法的标准。 2.12.1 apriori 算法算法 针对核心问题(获得频繁项目集), apriori 算法的描述如下。 输入： 数据库 d； 最小支持度阀值 min_sup。 输出：d 中的频繁项集。方法：l step1: l1 = large 1-itemsets/得到频繁一项目集 step2: for( k = 2 ; lk-1 ; k +) ck = apriori-gen(lk-1);/连接由频繁项目集 k-1 得到候选项目集 k forall transaction td ct = subset(ck,t)/遍历事务数据库集查看 ck 中是否在事务 t forall candidates c ct c.count+;/对遍历后且包含在某一事务 t 中的 ck 计数 /目的：计算支持度 lk = c ct | c.count min_sup 基于映射和逻辑运算的 apriori 算法的优化 4 2.22.2 apriori 算法算法 pad 算法示例图 2-2： 数据库 d min_sup 扫描数据表，生成候选项目集 c1,进而生成频繁项目集 l1 连接操作，得到频繁 2-项目集 置 k=2 连接操作，由频繁项目集 lk 生成候选项目集 ck+1 遍历完毕 ck+1 中的项集包含在 数据库中某一记录中 根据最小支持度生 成频繁 lk+1 项集， 并 k+ 遍历 ck+1 中的项集 扫描数据库 ccount+ 扫描完毕 lk 为空或 1 得到所有频繁项目集 基于映射和逻辑运算的 apriori 算法的优化 5 2.32.3 apriori 算法算法优点及问题优点及问题 apriori 算法的优点是结构简单，易于理解，没有复杂的推导。另外算法应用 apriori 性质而设计的连接后剪枝方法在许多情况下大大缩小了需要检查的候选规模， 使算法效率大幅度提高。但 apriori 算法依然存在两个主要的问题： （1）多次扫描数据库。apriori 算法需要在每进行一次迭代的时候扫描 x 次数 据库，而在实际应用中经常需要挖掘很长的模式，多次扫描数据库带来巨大开销。 （2）可能产生大量候选。apriori 算法在迭代过程中要在内存中产生、处理和保 存候选频繁项集，这个数量有时候是非常巨大的，导致算法在广度和深度上的适应 性很差。 即 apriori 算法有个严重的缺陷：因为需要多次扫描数据库和产生大量的频繁项 集，使得算法的花费在 i/0 上的时间很多，从而导致挖掘的效率非常低。因此，为了 提高 apriori 算法的有效性,需要对 apriori 算法进行改进。人们对 apriori 算法进行了 大量的改进，希望能够找出一个高效、可靠的挖掘频繁项集的算法。因此本文针对 购物篮系统对 apriori 算法进行了改进，提出一种基于映射和 0-1 编码逻辑与运算的 apriori 改进算法。 基于映射和逻辑运算的 apriori 算法的优化 6 第三章第三章 改进的改进的 apriori 算法算法 3.03.0 apriori 算法的强关联规则算法的强关联规则 - - 以购物篮系统为例以购物篮系统为例 walmart 曾将自己的全球销售网络组建一个大型的购物篮系统,通过先进的 挖掘技术将数以万计的销售信息汇集到其数据仓库中,其中一个方法就是找出其中的 强关联规则,找出顾客的购买习惯，以此调配管理物流.。其中经典的例子是：发现尿 布和啤酒同时被购买的概率很高，经调查发现在家里带孩子的男士会在买尿布的时 候购买啤酒打发无聊的时间，故将两种商品放在一起，提高了销售利润。 因此，找出潜在的强关联规则是发现购物篮系统潜在信息的行之有效的方法， 这体现了 apriori 算法的优势。然而，如果数据量大，如何来降低计算量并提高数据 分析的效率？本文针对该问题提出了下列改进： 通过数据存储方式的改变来减少数据库扫描 通过 apriori 性质分析来缩小候选集 3.13.1 改进的基于映射和逻辑运算的改进的基于映射和逻辑运算的 apriori 算法算法 改进的基于映射和逻辑运算的 apriori 是在实现强关联规则的基础上，采用映 射集和 0-1 矩阵的逻辑运算降低数据计算量并提高数据分析的效率。 3.1.13.1.1 算法简介算法简介 apriori 算法需要频繁扫描整个数据库。与 apriori 算法相比，基于映射和逻辑 运算的改进算法只需要扫描整个数据库两次。 第一遍：扫描商品项目映射表（metadata） ，将产生商品名称与商品代号对应映射。 得到所有项目，用简单的编码减小存储在内存中的存储空间，减少扫描数 据库的 i/o 负载。 第二遍：对所有项目构建逻辑 0-1 矩阵，某一条购买事务中存在该项目集则计数为 1，否则计数为 0；通过矩阵迭代进行逻辑与运算和加入连接前减枝得到所 有频繁集。 基于映射和逻辑运算的 apriori 算法的优化 7 3.1.23.1.2 算法伪码算法伪码 基于映射和逻辑运算的 apriori 改进算法的具体描述如下： 输入：数据库 d；最小支持度阀值 min_sup 输出：d 的频繁项集 l step1: got items();/第一次扫描得到所有项目 second scan();/第二次扫描构建 0-1 矩阵 gotl1();/统计得到 l1 gotc2();/逻辑与运算得到候选项目集 2 gotl2();/得到 l2 step2: for( k = 2 ; lk-1 ; k +) l_c=cutbefore(lk);/连接前剪枝 ck+1 = conitems(l_c);/由剪枝后的频繁集连接得到候选项目集 /ck+1 lk+1 = cutafter(ck+1);/连接后剪枝 基于映射和逻辑运算的 apriori 算法的优化 8 3.1.33.1.3 算法算法 pad 算法示例图 3-1-3： 数据库 d min_sup 扫描数据表，根据 0-1 编码构建数据矩阵 根据矩阵得到频繁项 1-目集，并进行逻辑与运 算得到计算 1 的个数得到频繁 2-项目集 置 k=2 连接前剪枝，缩小候选集，由 lk 生成 l_c，保留编码 连接，由 l_c 与运算生成 ck+1，保留编 码 ck+1=nul l l_c=null 连接后剪枝，缩小候选集，由 ck+1 生成 lk+1，保留编码 lk+1=null k = k+1 得到所有频繁集 根据最小置信度 得到关联规则 基于映射和逻辑运算的 apriori 算法的优化 9 3.23.2 改进改进 apriori 算法示例与分析算法示例与分析 3.2.13.2.1 数据数据 本文以购物篮系统为背景所用数据为随机输入 （数据库 d：顾客购买物品编码表，每一条为 1 个购买记录，以下共有 6 条购买记录） （数据库 d：物品映射编码表，每一条为 1 种物品映射关系，以下共有 6 种商品信息） 解释：（tid1，aegkm） 某一顾客一次购买了 aegkm（牛奶，花生酱，雪碧，啤酒， 大豆）这些商品。 基于映射和逻辑运算的 apriori 算法的优化 10 3.2.23.2.2 第一次扫描数据库映射关系表第一次扫描数据库映射关系表 关键伪码示例： /* *为构建矩阵与逻辑运算提供简单编码支持 */ for each items rs in metadata2 begin: items = new items(); items.a = rs.getstring(1).trim(); items.b =rs.getstring(2).trim(); list.add(items); end; 基于映射和逻辑运算的 apriori 算法的优化 11 3.2.33.2.3 第二次扫描数据库购买事务表第二次扫描数据库购买事务表 关键伪码示例： /* *遍历事务表 dataset2 如果该项目元素出现在某一事务中置 1 否则置 0 */ for each items rs in dataset2 begin： for each items listitem in list if listitem rs then listitem += “1”; else then listitem +=”0”; end； 表 dataset2 代码示例：扫描数据库对于商品 a 生成向量（111011）,因扫描 tid1,2,3,5,6 均包含 a，因此置 1，否则为 0。同理，建立如下图矩阵。 基于映射和逻辑运算的 apriori 算法的优化 12 3.2.43.2.4 根据最小支持数计算频繁项目集根据最小支持数计算频繁项目集 l1l1 支持数：含有某一项集的 tid 的个数。 假设最小支持数为 2（min_sup = 2） support(b ) y 事务集中包含 x 的事务数目不大于 y x 的支持度肯定不大于 y 的支持度 证毕 推论 1：xk 是数据集 d 的频繁 k 项集,则频繁 k-1 项集中包含 xk 的所有 k-1 项子集 即个数为 k。 当 p = k-1 时，= k。 c p k 推论 2：如果某个元素在 k-频繁项目集中，则该元素在 k-1 频繁项目集中出现的次数最 少为 k-1. 证明： （性质一）所有 k 频繁集的 k-1 子集一定是频繁集 设：频繁 k 项集的某一项中的任一元素 o 在频繁 k-1 子集中出现的次数为 n n=k-1 (i = k-1,g = k-2) c g i 频繁 k 项集中含有 n 项,n=1 当 k-频繁集中含有元素 o 的频繁项 x=1 时，则该元素在 k-1 频繁集中的出现次数 m= xn =x （k-1） m = k-1 证毕 推论 2 即为（连接前剪枝）：首先统计 lk-1 中所有项出现的次数，然后删除 lk-1 中 包含有出现次数小于(k-1)的项的项集，得到 l_c（连接前剪枝后待连接的项目集） 。 基于映射和逻辑运算的 apriori 算法的优化 16 关键伪码示例： /* *统计 lk 频繁项目集中元素出现次数 */ for each item lk begin: for each element item switch (element) case(a): a.count+;break; case(b): b.count+;break; case(c): c.count+;break; case(d): d.count+;break; end; 运行结果： 对频繁项目集l2进行连接前剪枝 关键伪码示例： for each element =2 的项目进行两两连接） 步骤： 连接 输入连接前剪枝后 的项目集 l_c（每 个项目含有 x 个元 素） 循环遍历使每个项目 都与其他项目比较 两个项目是否只有 x-1 个元素相同 相同不同 进行连接操作，生 成含有 x+1 个元素 的项目有 不进行连接操作 连接后剪枝：删除支持数min_sup 的项目 结果： 基于映射和逻辑运算的 apriori 算法的优化 18 共 11 个项目集 与最小支持数比较：淘汰 aek.agk.afk.ahk.fhl.fho.fkl.fko 同理，连接前剪枝 l3 生成 l_c 由于频繁项目集 l3 中所有项的出现次数均小于 3，因此均不参与连接，频繁项集搜索结束。 打印出所有候选项目集 基于映射和逻辑运算的 apriori 算法的优化 19 3.33.3 算法分析算法分析 3.3.1 本文示例分析 优化后的算法的优势有两点： 逻辑与运算的 0-1 编码矩阵理解简单，计算机实现方便。 连接前剪枝 如上例所示，由 l2 生成 l3 共 11 项目集 = 55 (p=2,k=11)c p k 因此要判断 55 次是否要 参与连接 传统 apriori 共 10 项目集 = 45 (p=2,k=10)c p k 因此要判断 45 次是否要 参与连接 改进 apriori 基于映射和逻辑运算的 apriori 算法的优化 20 如上例所示，由 l3 生成 l4 共 3 项目集 = 3 (p=2,k=3)c p k 因此要判断 3 次是否要 参与连接 传输 apriori l_c 共 0 项目 集 不需要任何的判断即可知道不用继续连接判 断。因为此时就知道已经得到了所有的频繁 项目集 改进 apriori 连接次数比较，如下表所示： 传统 apriori 55+3=58 次 改进 apriori 45+0=45 次 对于仅仅有 6 个事务的示例来说，实际优化效果比为： (58-45)/58 = 22.4% 显然优化后的算法有优秀的时间效率。 与此同时，实际应用中有上亿条的购买事务，因此利用优化后的算法显然会产生巨大的经 济效益。 基于映射和逻辑运算的 apriori 算法的优化 21 3.3.2 综合分析 随具体数据不同所达到实际效果有偏差 按上文得到的 22.4%的优化率作为分析依据 假设如下： 已经得到频繁 2 项目集，且频繁 2 项目集的个数是 106，求由 l2 生成候选项目集 3。 优化后算法对传统算法的优化率为 22.4% 实际效率表格如下： 扫描数据 库次数 连接次数效率分析 改进 apriori 算法 2 =3*1011c p k k=106*(1-22.4%)=776000 p=2 传统 apriori 算法 106 =5*1011 c p k k=106 p=2 1.连接次数 优化后的算法比传统算法在连接次 数上减少了 2*1011 次，自然节省 了这么多次的连接操作时间。 2.扫描数据库次数 传统 apriori 算法：根据项目的多 少来决定扫描多少次数据库，因此 当项目激增的时候，扫描次数也成 指数级增长 改进 apriori 算法：无论多少个项 目 都只扫描 2 次数据库，是个定值 基于映射和逻辑运算的 apriori 算法的优化 22 第四章第四章 总结与展望总结与展望 4.14.1 总结总结 本文目的：通过改进传统算法缩减候选集大小，来达到提高 apriori 算法的效率。 方法：对传统 apriori 算法对象进行流程剖析（在扫描数据库，剪枝缩小候选集 两方面入手） ，对前者采用映射数据表和 tid 表的方式进行两次次扫描，对后者采 用 0-1 编码构成矩阵采用逻辑与运算和加入一次连接前剪枝有效减少候选集。 结果：采用对照组的形式对比