数据挖掘关联分析.pdf

数据挖掘关联分析1 引言在大型数据库中，关联规则挖掘是最常见的数据挖掘任务之一关联规则挖掘就是从大量数据中发现项集之间的相关联系Apriori 算法，前者采用逐层搜索的迭代策略，先产生候选集，再对候选集进行筛选，然后产生该层的频繁集。2 Apriori 算法Apriori 算法是关联规则挖掘中最基本也是最常见的算法它是由Agrawal 等人于 1993 年提出的一种最有影响的挖掘布尔关联规则频繁项集的算法，主要用来在大型数据库上进行快速挖掘关联规则。2.1 算法基本思想Apriori 算法采用逐层迭代搜索方法，使用候选项集来找频繁项集。其基本思想是:首先找出所有频繁1项集的集合Ll，L1用于找频繁2项集的集合L2，而 L2用于找L3，如此下去，直到不能找到频繁k项集。并利用事先设定好的最小支持度阈值进行筛选，将小于最小支持度的候选项集删除，再进行下一次的合并生成该层的频繁项集。经过筛选可减少候选项集数，从而加快关联规则挖掘的速度。2.2 算法的挖掘如果一个项集是频繁的，那么它的所有子集都是频繁的先验原理成立的原因:)()()(:,YsXsYXYX一个项集的支持度不会超过其任何子集的支持度该性质称作支持度的反单调性质2.2.1 候选项集的生成Apriori 算法使用了Apriori 性质来产生候选项集任何非频繁的(k1)项集都不可能是频繁k项集的子集因此，如果一个候选k项集的(k 1)子集不在Lk1 中，则该候选项集也不可能是频繁的，从而可以从Ck中删除2.2.2 由 Lk-1 生成 Lk设定 k=1 扫描事务数据库一次，生成频繁的1-项集如果存在两个或以上频繁k-项集，重复下面过程：候选产生 由长度为 k 的频繁项集生成长度为k+1 的候选项集候选前剪枝 对每个候选项集，若其具有非频繁的长度为k 的子集，则删除该候选项集支持度计算 扫描事务数据库一次，统计每个余下的候选项集的支持度候选后剪枝 删除非频繁的候选项集，仅保留频繁的(k+1)-项集，设定k=k+1 Apriori 流程图2.2.3 候选项集的支持度计算1)扫描事务数据库，决定每个候选项集的支持度。2)为了减少比较次数，将候选项集保存在散列（hash）结构中，将每个事务与保存在散列结构的候选项集作匹配2.3 基于 Apriori 算法的数据挖掘应用实例2.3.1 数据库样本当前是列出我们实验中用到的一个候选项集：1 4 5,1 2 4,4 5 7,1 2 5,4 5 8,1 5 9,1 3 6,2 3 4,5 6 7,3 4 5,3 5 6,3 5 7,6 8 9,3 6 7,3 6 8。2.3.2Apriori 算法的实现过程首先设置散列函数，和叶子大小限制。根据以上限制，先根据首项形成初步的散列树，见下图：图：生成候选的散列树（原始版本）接着根据第二项形成优化后的散列树，结果见下图：图：生成候选的散列树（中间过程）按照以上过程，按照项的顺序，我们可以将树的分裂做到最后一项，最终结果见下图：图：生成候选的散列树（最终版本）2.4 Apriori 算法的优缺点1)产生大量的频繁集2)重复扫描事务数据库2.5 Apriori 算法的优化思考我们从复杂度方面考虑：1)最小支持度阈值的选择低支持度阈值导致更多频繁项集将会增加候选项集的个数和频繁项集的最大长度2)数据库的维度，即项的个数需要更多空间保存每个项的支持度计数如果频繁项集的个数增加，则计算量和I/O 开销也增加3)数据库的大小由于 Apriori 多次访问数据库，算法的运行时间将随事务个数的增加而增加平均事务长度4)事务长度随数据库密度的增加而增加可能会增加频繁项集的最大长度和散列树的遍历时间（因为事务的子集个数随着其长度的增加而增加）