资源描述：
《数据挖掘关联分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据挖掘关联分析1引言在大型数据库屮，关联规则挖掘是最常见的数据挖掘任务之一.关联规则挖掘就是从大量数据中发现项集之间的相关联系.Apriori算法，前者采用逐层搜索的迭代策略，先产生候选集，再对候选集进行筛选，然后产生该层的频繁集。2Apriori算法Apriori算法是关联规则挖掘中最基本也是最常见的算法.它是山Agrawal等人于1993年提出的一种最有影响的挖掘布尔关联规则频繁项集的算法，主耍用来在大型数据库上进行快速挖掘关联规则。2.1算法基本思想Apriori算法采用逐层迭代搜索方法，使用候选项集
2、來找频繁项集。其基本思想是:首先找出所有频繁1一项集的集合Li,LJIJ于找频繁2—项集的集合L2,而L2用于找・，如此下去，肯到不能找到频繁k—项集。并利用事先设定好的最小支持度阈值进行筛选，将小于最小支持度的候选项集删除，再进行下一次的合并牛成该层的频繁项集。经过筛选可减少候选项集数，从而加快关联规则挖掘的速度。2.2算法的挖掘如果一个项集是频繁的，那么它的所有了集都是频繁的先验原理成立的原因：vx,y：（xor）^5（x）＞5（y）一个项集的支持度不会超过其任何子集的支持度该性质称作支持度的反单调性质2
3、.2.1候选项集的生成Apriori算法使丿IJ了Apriori性质来产生候选项集.任何非频繁的（k—1）项集都不可能是频繁k—项集的子集.因此，如果一个候选k—项集的（k-1）—子集不在Lk—1中，则该候选项集也不可能是频繁的，从而可以从G中删除.2.2.2由Lk.j生成Lk设定k=l扫描事务数据库一次，生成频繁的1-项集如果存在两个或以上频繁k-项集，重复下面过程：［候选产生］由长度为k的频繁项集生成长度为k+1的候选项集L候选前剪枝］対每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集［支持
4、度计算］扫描事务数据库一次，统计每个余下的候选项集的支持度［候选后剪枝］删除非频繁的候选项集，仅保留频繁的（k+1）-项集，设定k=k+lSTOPApriori流程图223候选项集的支持度计算1）扫描事务数据库，决定每个候选项集的支持度。2）为了减少比较次数，将候选项集保存在散列（hash）结构中，将每个事务与保存在散列结构的候选项集作匹配2.3基丁Apriori算法的数据挖掘应用实例2.3.1数据库样本当前是列出我们实验中用到的一个候选项集:{145},{124},{457},{125},{458},{15
5、9},{136},{234},{567},{345},{356},{357},{689},{367},{368}。2.3.2Apriori算法的实现过程首先设置散列函数,和叶子大小限制。散列函数1,4”「7,6,92,5,8叶子大小限制：3根据以上限制，先根据首项形成初步的散列树，见下图:159图：生成候选的散列树（原始版本）接着根据笫二项形成优化后的散列树，结果见卜•图:散列树图:散列树图：生成候选的散列树（最终版木）图：生成候选的散列树（中间过程）按照以上过程，按照项的顺序，我们可以将树的分裂做到最后-•
6、项，最终结果见F2.4Apriori算法的优缺点1）产生大量的频繁集2）重复扫描事务数据库.2.5Apriori算法的优化思、考我们从复杂度方面考虑：1）最小支持度阈值的选择低支持度阈值导致更多频繁项集将会增加候选项集的个数和频繁项集的最大长度2）数据库的维度，即项的个数需要更多空间保存每个项的支持度计数如果频繁项集的个数增加，则计算量和I/O开销也增加3）数据库的大小由T*Apriori多次访问数据库，算法的运行吋间将随事务个数的增加而增加平均事务长度4）事务长度随数据库密度的增加而增加可能会增加频繁项集的
7、最大长度和散列树的遍历吋间（因为事务的子集个数随着其长度的增加而增加）
