发布时间 : 星期日 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
候选集。 7. 并行挖掘
利用数据分布技术对数据子集进行挖掘，而且各子集间可以并行进行。另外，并行挖掘也涉及到针对并行处理开发的并行挖掘模型和算法。在这方面有许多工作可以借鉴[34-37]
以上我们介绍了关联规则挖掘中的一些优化算法的方法，这些方法为我们改善已有算法提供了许多可以借鉴的思想。
3.5.2.1 DDApriori算法
描述如下[32]：
算法：DDAprior使用根据候选生成的逐行迭代找出频繁项集。 输入：事务数据库Ｄ；最小支持记数阈值Vminsup。 输出：Ｄ中的频繁项集Ｌ。 方法：
10) L1=find_frenquent_1-itemset(D); 20) for(i=2;Li-1≠￠;i++){
30) Ck=apriori_gen(Li-1,Vmin_sup); ∥产生新的候选项集,此函数同于Apriori算法中的函数
40) for each transaction t∈Ｄ{ ∥扫描Ｄ并计数 41) if t.delete=0 then do begin
50) Ct =subset(Ci,t); ∥获取ｔ的子集作为候选 51) if Ct=￠then ｔ
52) t.delete=1 ∥打上删除标志
53) else ∥对每一个Ct进行计数并记录内容 54) if Ct=c then t.count ++,t.text=c 60) for each candidate c∈Ct 70) c.count++; 71) end 80) }
37
山东师范大学硕士学位论文
81) if 0 110)renturn L=UiLi; 下面举例说明。设最小支持记数为2。支持度计数简记为Sup。图示如下: Database C1 Itcm set {I1} {I2} {I3} {I4} {I5} TID item m T100 I1 I2 I5 T200 I1 I4 T300 I3 I5 T400 I2 I4 T500 I3 I4 T600 I2 I3 T700 I4 I5 T800 I1 I2 I3 I5 T900 I1 I2 I3 L1 Itc m sup {I1} 4 {I2} 5 {I3} 5 {I4} 4 {I5} C1 Itcm set {I1 I2} {I1 I3} {I1 I4} {I1 I5} {I2 I3} {I2 I4} {I2 I5} {I3 I4} {I3 I5 {I4 I5} Database L2 TID item m T100 I1 I2 I5 T200 I1 I4 T300 I3 I5 T400 I2 I4 T500 I3 I4 T600 I2 I3 T700 I4 I5 T800 I1 I2 I3 I5 T900 I1 I2 I3 Itc m sup {I1 I2} 3 {I1 I3 } 2 {I1 I5 } 2 {I2 I3} 3 {I2 I5} 2 {I3 I5} 2 38 山东师范大学硕士学位论文 Database C1 Ite m set {I1 I2 I3 } {I1 I2 I5} {I2 I3 I5} TID ite m T100 I1 I2 I5 T300 I3 I5 T600 I2 I3 T800 I1 I2 I3I5 T900 I1 I2 I3 L3 Itm m set sup {I1 I2 I3} 2 {I1 I2 I5} 2 从图中可以看出,在Ｃ2扫描数据库时,数据库中的事务Ｔ200,Ｔ400,Ｔ500,Ｔ700在Ｃ2中,且它的支持记数小于2,因此在Ｃ3扫描时,数据库Ｄ已经不再考虑它们,数据库已经有了很大的缩小,这对于大型数据来说是很有用处的。 3.5.2.2 MApriori算法 算法描述如下:算法: MApriori使用根据候选生成的逐行迭代找出频繁项集。输入:事务数据库D的布尔矩阵M;最小支持记数阈值Vminsup. 输出:D中的频繁项集L 方法： 10) L1=find_frenquent_1-itemsets(D); 20) for(i=2; Li-1≠￠;ｉ++){ 30) Ci=apriori_gen(Li-1,Vmin_sup); ∥产生新的候选项集 40) for each transaction c ∈Ci{ ∥扫描矩阵M并计数 50) for (j=1;j≤M_列数;ｊ++) If M_[c_1][j]=1 and M_[c_2][j]=1 and?and M_[c_i][j]=1 then 70) c.count ++; 80) } 90) Li={c∈Ci|c.count≥Vmin_sup}; ∥得到满足条件的Li 100) } 110) return L=UiLi; 作为理解,取上一例子作以简单说明。由布尔矩阵的各行和可以得出一项集的支持记 39 山东师范大学硕士学位论文 数,从而求出Ｌ1,进而得出Ｃ2。对Ｃ2中的每一项集扫描数据库的布尔矩阵,并且记数。比如对二项集{Ｉ1,Ｉ2},只需扫描第一行与第二行,每一列同为1的记数,得出它的支持记数为3。依次取遍Ｃ2,支持记数大于或者等于Vminsup的项集生成Ｌ2,由Ｌ2生成Ｃ3,在对Ｃ3中的每三项集扫描布尔矩阵,这时要扫描3行。依此类推,直到算法终止。 3.5.2.3 Aprioritid算法 Apriori和Aprioritid算法在不考虑数据库中的事务的情况下,通过使用在前边发现的频繁项集来生成候选项集。给人的基本直觉就是一个频繁项集的任何子集也是频繁的。因此,通过联接含有ｋ-1个项的频繁项集产生了具有ｋ个项的候选项集,并删除那些包含任何不频繁的项集。这个过程导致产生了许多更小的非频繁候选项集。Aprioritid算法具有额外的特征,就是在第一步之后,计算候选项集的支持度时完全不用数据库,在前边用到的候选项集的编码便用于这一目的。稍后,该编码的大小便比数据库小得多,这样就节省了很多用于读的开销。 3.5.2.4 Apriorisuper算法 Apriorisuper是对Apriori和Aprioritid算法的改进，Apriorisuper是提取两种算法的优点,即让该算法在开始时使用Apriori的算法思想,当在过程的后面预期的集ＣＫ大小可放入内存时,我们转用AprioriTid的算法思想。关键是算法在何时由一种算法转向另一个算法思想,如何确定其转向条件呢?我们通过反复测试发现,算法是否读写磁盘是影响算法执行时间的关键因素,也就是说算法的执行和读写数据均在内存中完成,将会大大缩小算法的运行时间。由此,我们将条件定为大小是否在下一步能放进内存。若能,则让算法由Apriori转用Aprioritid,否则继续使用Apriori。 经过仔细检测,我们发现从Apriori到Aprioritid的转向并不会耗费多余代价。假定在第ｋ次途径的后面,我们决定从Apriori转向Aprioritid。在第(ｋ+1)次途径中,在找到事务中的候选项集之后,我们也将必须将它们的ID增加到 ＣＫ+1中。这样,相对于刚才运行的Apriori在这次途径中就有一个额外的代价发生。仅仅在第(ｋ+2)次途径中我们才开始运行Aprioritid算法。这样,如果没有频繁的(ｋ+1)-项集,或者没有(ｋ+2)-候选,这时我们转向使用Aprioritid不会获得任何好处,这种情况下的转向将会耗费一定的资 40