发布时间 : 星期四 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读f82c9d1e10a6f524ccbf85c8
山东师范大学硕士学位论文
算法的效率,要提高效率关键是减少数据库遍历的次数和数据库的规模(即交易数)。 (2)可能产生大量的候选项集,不利于规则的产生。为克服Apriori算法存在的问题、提高算法效率,人们提出了许多Apriori算法的变形[2,3]来优化Apriori算法,如基于散列技术(散列项集计数)、事务压缩(压所进一步选代扫描的交易数)、划分(为找候项集划分数据)、选样(在给定数据的一个子集挖掘)、动态项集记数(在扫描的不同点添加候选项集)等,这些算法从不同方面改善了Apriori算法的性能,提高了效率。
3.5关联规则挖掘的基本算法及其改进 3.5.1基本算法
现有的各种关联规则挖掘算法大致可分为以下几种: 1.搜索算法
搜索算法在读入数据集中的每条事务时，对该事务中包含的所有项目集进行处理，因此搜索算法需计算数据集D中的所有项目集的支持度。AIS算法、SETM算法以及以建格算法为主体的关联规则挖掘算法都是这种搜索算法[1z] 2. 层次算法
以Aprior i算法为代表的层次算法是按项目数从小到大的顺序寻找频繁项目集。以Apriori算法为代表的层次算法可以产生相对较小的候选项目集，扫描数据库的次数由最大频繁项目集的项目数决定。因此，这类算法适合于最大频繁项目集相对较小的数据集中的关联规则的挖掘[19] 3. 数据集合划分算法
数据集划分算法包括Partition算法、DIC算法等，这些算法将整个数据集划分为可以存放在内存中进行处理的数据块，以节省访问外存的I/O开销。Partition算法只需要对整个数据集进行两次扫描，DIC算法在数据块划分恰当时可以通过两次扫描数据集找出所有的频繁项目集。 4. 抽样算法
抽样算法通过对数据集D抽样产生抽样数据集D'，找出抽样数据集D’中的频繁项目集作为候选项目集，然后扫描数据集D确定其中的频繁项目集。如何计算负边界以找回部分遗漏的频繁项目集是抽样算法的关键。抽样算法适合于要求挖掘效率较高，而挖掘准
33
山东师范大学硕士学位论文
确性不太高的环境下的关联规则挖掘。另外 ，目前也提出一些新的算法[21.25]。特别是文献（21)提出的基于COFI-tree的挖掘算法，这种算法通过四种方法来提高它的效率:①使用一种基于小型存储器的数据结构;②对每一个频繁项目集，都有一个相对较小的独立的树结构描述事务数据集;③独特的删除策略降低了搜索的空间;④简单的和非循环的挖掘处理能降低最小的事务数据集的存储空间。与以往算法相比，挖掘效率得到了很大的提高，而且对内存依赖性较小。
选样的基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔细地组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点[MTV94]，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想[Toi96]，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。
Apriori算法是一种最有影响力的挖掘布尔关联规则频繁项集的算法，采用了一种称作逐层搜索的迭代方法，K-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合，记为L1。L1 用于找频繁2-项集的集合L2，而L2 用于找L3，如此下去，直到不能找到频繁K-项集，找到每个Lk需要一次数据库扫描，其生成频集所使用了递推的方法核心思想描述如下：
(1) L1 ={large1-itemsets}; (2) for (k=2;Lk-1≠￠;k++) do begin (3) Ck =Apriori-gen(Lk-1);//新的候选集 (4) for all tansactions t∈D do begin
(5) Ct=subset(Ck,t);//事务t中包含的候选集 (6) for all candidates c∈Ct do (7) c.count++; (8) end
(9) Lk={c∈Ck |c.count≥minsup} (10) end
34
山东师范大学硕士学位论文
(11) Answer=UkLk;
上面算法中调用了apriori-gen(Lk)，是为了通过k-1-频繁项目集产生k候选集。下面的算法描述了apriori-gen过程。 apriori_gen(Lk-1，是频繁(k-1)-项目集) (1) For each itemset l1∈Lk-1 (2) For each itemset l2∈Lk-1
(3）If(l1[1]=12[1]) (l1,[2]=l2[2])A?A(l1[k一1]＜l2[k一1])then{ (4) c=l1? 12 ;// 连接步:把q的第k-1个元素连到p后 (5) If has_infrequent_subset (c,Lk-1)then
(6) delete c ; // 剪枝步:删除含有非频繁项目子集的候选元素 (7) Else add c to Ck; (8) } (9) Return Ck;
上一个算法中调用了has_infrequent_subset(c,Lk-1)，是为了判断c是否需要 加入到k-候选集中。按着Agrawal的项目集格空间理论，含有非频繁项目子 集的元素不可能是频繁项目集，因此应该裁减掉，以提高效率。下面的算法描 述了has_in frequent_subset过程。
算法3-3 has_infrequent_subset(c,Lk-1)--判断候选集的元素 (1) For each(k-1)-subsets of c (2) If s?Lk-1,then (3) Return TURE; (4) Return FALSE;
3.5.2对Apriori算法的改进算法
为了提高Apriori算法的效率,近年来,一些专家已经提出该算法的一些变形[33] 1. 基于散列的技术
由JSparkｋ等人提出,用于压缩候选Ｋ项集Ck(Ｋ>1),特点是当扫描数据库中每个事务,由Ck-1中的候选(Ｋ-1)项集产生频繁(Ｋ-1) 项集ＬＫ-1时,可以对每个事务产生所有的
35
山东师范大学硕士学位论文
Ｋ项集,将它们通过散列函数映射到散列表结构的不同桶中 并增加对应的桶计数 在散列表中对应的桶计数低于最小支持度的Ｋ 项集不可能是频繁项集,因而应从CK中删除 这种基于散列的技术可以大大压缩要考察的Ｋ 项集(特别是Ｋ=2时)
由R. Aprioril,J.han和JSpark等多人提出,用于压缩事务数据库中的扫描事务数 由于不包含任何Ｋ项集的事务不可能包含任何(Ｋ+1) 项集,这样,这种事务在其后的考察时,可以加上标记或删除,在产生i-项集(ｉ>Ｋ)扫描数据库时,不需要它们. 2. 基于划分的方法
由A Savasere等人提出,基本思想是首先将D中的事务划分成几个非重叠的部分,使得每个部分能够放入内存,其次找出局部于每一部分的频繁项集,每个部分的最小支持度计数为minsupx(该部分中事务数),最后把局部频繁项集并成候选项集,在候选项集中找出全局频繁项集(D的任何频繁项集,一定作为局部频繁项集至少出现在一个部分中) 3.基于选样的方法
由H Toivonen 提出,选样方法的基本思想是:选取给定数据库D的随机样本S,使得S可以放入内存,然后在S而不是D中搜索频繁项集 用这种方法会使精度降低,如可能会丢失一些全局频繁项集, 为减少这种可能性,可使用比最小支持度低的支持度来找出局部于S的频繁项集 4.动态项集
计数由S Brin等人提出,该技术动态地评估已被计数的所有项集的支持度,如果1个项集的所有子集已被确定为频繁的,则添加它作为新的候选,需要的数据库扫描比Apriori少
5.减少事物的个数
这种方法的基本原理就是当一个事务不包含长度为k的项目集时，则必然不包含长度为(k十1)的频繁项目集.从而我们就可以将这些事务删除，这样在下一遍的扫描中就可以使用较少个数的事务集，使得挖掘效率得到提高。 6. 尽量减少数据库的扫描遮数
1997, Brin等提出了一个减少数据库的扫描遍数的算法[35]。具体的考虑是，在计算k-项目集时，一旦我们认为某个(k +1)一项目集可能是频繁项目集时，就并行地计算这个(k + 1)-项目集的支持度，算法需要的总的扫描次数通常少于最大的频繁项目集的项数。实验表明，它比却Apriori算法使用较少的扫描遍数，同时比基于抽样的方法使用更少的
36