基于筛选压缩的类Apriori算法的研究

摘要：该文根据用户的Web访问路径应用关联规则和类Apriori算法挖掘出该用户的频繁访问路径，通过对Apriori算法和目前针对提高该算法效率的各种优化技术的详细分析和研究，对类Apriori算法进行了改进，提出了基于筛选压缩的类Apriori挖掘算法，并进行了模拟实验，比较结果显示基于筛选压缩的类Apriori挖掘算法挖掘用户频繁遍历路径的效率高于类Apriori算法，最终可获取用户的频繁遍历路径。

关键词：Web日志挖掘；频繁遍历路径；类Apriori算法；筛选压缩

中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)34-2038-04

The Research Based on the Homo-Apriori of Riddling Compression Algorithm

ZHANG Li, SHENG Yun-yao

(Computer Sicence and Engineering Department, Changzhou Institute of Mechatronic Technology, Changzhou 213164, China)

Abstract: Basing on the user's Web access path frequent access sequences were mined by using the association rules and homo-Apriori algorithm. The Apriori algorithms of association rules and all kinds of optimized techniques which were designed to promote the algorithms efficiency were studied and discussed in detail here. Based on the basic, the homo-Apriori algorithm was improved and the homo-Apriori algorithm of riddling compression was proposed. And hasing carried on the simulation, the result demonstrats that the frequent access sequences mined by homo-Apriori algorithm of riddling compression is quickly than it mined by homo-Apriori. Eventually, the algorithm of users frequent access sequences is found.

Key words: Web log mining; Frequent access sequences; Homo-Apriori algorithm; Riddling Compression

1 引言

WWW的迅速发展，在给人们带来丰富信息和极大便利的同时，也随之产生了一些觅待解决的问题，个性化的信息服务和构建智能化Web站点便是其中之一。一方面，不同层次、不同爱好和使用目的的浏览者需要个性化的信息服务；另一方面，Web站点的经营和管理者为提高网站的声誉和效益，需要了解客户需要什么和想做什么。其中包括根据大多数客户的共同兴趣，开展有针对性的信息服务，以及对特定的用户开展个性化的信息服务和电子商务活动。直接或间接地解决这个问题的途径之一就是将数据挖掘技术应用于Web服务器日志的挖掘。从用户在Web上浏览行为数据中获取用户的频繁访问路径，根据用户的频繁访问路径改进站点的设计和服务。开展个性化信息服务和有针对性的电子商务活动和构建智能化Web站点。

2 类Apriori算法

Web日志挖掘经过了数据预处理、事务识别后，已经生成了事务数据库，事务中包含了用户的浏览路径,也就是最大向前引用路径MFP。找出MFP中所有频繁遍历路径的过程与挖掘关联规则时从事务数据库中找出所有的频繁项集比较类似。因此，可以利用Apriori算法的思想来实现频繁遍历路径的发现过程。

为方便以后的论述，现约定如下：

定义1 事务的长度为其包含的页面数,一个有k个页面引用的事务称为一个k引用。

定义2 引用s1,s2,…,sn包含k引用r1,r2,…,rk，如果存在i，使得1≤j

定义3 如果一个k引用序列r1,r2,…,rk满足以下条件：

（包含r1,r2,……,rk序列的MFP数）/（所有的MFP数）×100%>minsupport

则称为频繁k引用。其中，minsupport是预先定义好的最小支持度（在有些场合用minsupport乘以所有的MFP数作为最小支持度）。有了频繁k引用的定义，就可以定义它们的集合Lk是所有频繁k引用的集合，Lk中每个成员有两个项（k引用，支持度S）。Ck是候选频繁k引用的集合，候选频繁k引用也就是潜在的频繁k引用，该集合中每个成员也有两个项（k引用，支持度S）。

类Apriori算法描述：使用逐层迭代方法基于候选产生找出频繁遍历路径

输入：

D：事务数据库

Minsupport：最小支持度计数阈值

输出：

R：D中的频繁项集

方法：

1) C1={所有的页面引用};

2) L1={c∈C1|c.count≥minsupport};

3) For(k=2;Lk-l≠Φ;k++)

{

4) Ck=adv_gen(Lk-1);

5) For each 事务t∈D

{

6) Ct=subset(Ck,t);

7) for each 候选c∈Ct

8) c.count++;

}

9) Lk={c∈Ck|c.count≥minsupport};

}

10) return R=R∪Lk;

说明：c.count表示引用c在事务数据库D中被包含的次数。假设项集用item表示，c.count相当于如下SQL语句：

select item from D group by item having count(*)≥minsupport

算法的前两步（步骤1)2)）是统计所有含一个页面的引用出现的次数，然后决定频繁1引用集L1。在步骤3)～9)，Lk-1用于产生候选Ck，以找出Lk，其中k>=2。adv_gen()产生候选，该过程在下面描述。一旦产生了所有的候选就扫描数据库（步骤5)）。对于每个事务，使用subset函数找出该事务中是候选的所有子集（步骤6)），并对每个这样的候选累加计数（步骤7)8)）。最后，所有满足最小支持度的候选（步骤9)）形成频繁项集的集合R（步骤10)）。

该过程和挖掘关联规则时的Apriori算法类似，但是在Apriori算法中，只要两个k-1维最大项集有k-2个元素相同就可以合并成一个k维候选项。而在挖掘频繁遍历路径时，引用中的页面是有序的，因此不能简单地只要k-2个元素相同就行了，需要作如下的处理：Lk-1中任意两个不同的(k-1)引用s1,s2,…,sk-1和r1,r2,…,rk-1，如果r1,r2,…,rk-1包含s1,s2,…,sk-2或者s1,s2,…,sk-1包含r1,r2,…,rk-2（包含的定义参见前面定义2），也就是说这两个(k-1)引用中一个去掉第一个元素，另一个去掉最后一个元素后完全相等，则这两个(k-1)引用可以合并成一个k引用。

这样通过Lk-1求Ck的过程，adv_gen()可以用如下的SQL语句说明：

insert into Ck

select P.item1,P.item2,…,P.itemk-1,Q.itemk-1 from Lk-1 P,Lk-1 Q

Where P.item1=Q.item2,P.item2=Q.item3,…,P.itemk-2=Q.itemk-1

在Apriori算法中，从Lk-1中求出所有的候选k维项目集后，函数adv_gen()还要进行修剪,修剪的原则是：如果一个k项目集的某一个(k-1)维子集不在Lk-1中,则该k维项目集需从Ck中删除。例如，Lk-1={AB,BC}，则根据求候选项目集的算法，Ck={ABC}，然后进行修剪，发现ABC的一个2维子集AC不在Lk-1中，将ABC从Ck中删除。但是，在挖掘频繁k引用时，一个k引用r1,r2,…,rk只有两个(k-1)子引用r1,r2,…,rk-1和r2,…,rk,只有当这两个(k-1)子引用都在Lk-1内时，r1,r2,…,rk才可能从Lk-1选出来，因此在这里进行修剪是没有意义的。

Subset()函数的参数是候选引用集Ck和某一事务t，结果返回这一事务t中包含的候选引用集，即

subset(Ck,t) = {c|c∈Ck∩c?哿t}

下面用此算法对某用户的浏览路径进行分析，找出频繁遍历路径。

该数据库中有6个事务，集|D|=6。这里设定最小支持度minsupport＝2。

操作步骤：

1) 扫描D，对每个候选计数，统计每个页面的支持度产生候选1引用集C1，C1:{{{C},6},{{G},2},{{GG},1},{{L},2},{{W},2},{{WC},2}}；

2)比较候选支持度计数与最小支持度计数，找到满足最小支持度的页面加入到L1中，L1:{{{C},6}，{{G},2},{{L},2},{{W},2},{{WC},2}}；

3) 为发现频繁引用2的集合L2，使用L1连接L1产生候选2引用集C2，由于页面引用具有顺序性，所以这里不是Apriori算法中的组合，而是排列，C2:{{ {C G},2},{{C L},2},{{C W},2},{{C WC},0},{{G C},0},{{G L},0},{{G W},0},{{G WC},0},{{L C},0},{{L G},0},{{L W},0},{{L WC},0},{{W C},0},{{W G},0},{{W L},0}，{{W WC}，2}，{{WC C}，0}，{{WC G}，0}，{{WC L}，0}，{{WC W}，0}}；

4) 比较候选支持度计数与最小支持度计数，找到满足最小支持度的页面加入到L2中，L2:{{{C G},2},{{C L},2},{{C W},2},{{W WC},2}}；

5) 依次类推，直到某一次发现Lk=Φ循环结束。

6) 最后得到此用户频繁引用页面C-W-WC。

3 Apriori算法的瓶颈

传统Apriori算法有两个致命的性能瓶颈：

多次扫描事务数据库需要很大的I/O负载，对每次k循环侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk；假如有一个频繁大项集包含10个项的话那么就至少需要扫描事务数据库10遍。

可能产生庞大的侯选集由Lk-1产生k侯选集Ck是指数增长的例如104的1频繁项集就有可能产生接近107个元素的2侯选集。如此大的候选集对时间和主存空间都是一种挑战。

4 对类Apriori挖算法的改进

Apriori是一种宽度优先算法，通过对数据库D的多趟扫描来发现所有的频繁项目集。由于数据库D一般是海量存储，所以对数据库D多趟扫描将耗费大量时间和内存空间，随着数据库海量增大，这也就成为Apriori算法的瓶颈。针对这一点，研究产生了多种改进方法，如基于哈希(hash)表技术、划分数据、采样技术、动态项集计数等方法，这些方法为改善己有算法提供许多可以借鉴的思想。日志数据库中数据也是海量的，而且随着时间的推移，日志数据库中数据越来越多，Apriori算法的瓶颈同样也制约着类Apriori算法的挖掘效率，因此这里引入了数据删除技术及压缩来提高类Apriori挖掘算法对日志数据库挖掘的效率和适应能力，得到的基于筛选压缩的类Apriori挖掘算法。

4.1 算法描述

基于筛选压缩的类Apriori挖掘算法利用了以下两个事实：

1) 对于己生成的事务数据库D，任意一个项集I的出现支持度与规模小于I的事务无关。所以可以删除规模小于I的事务记录。

2) 由于不包含任何k项集的事务不可能包含任何一个(k+l)频繁项集。因此在生成(k+l)频繁项集之前对这样的事务记录进行删除操作，以便来减少下次扫描事务数据库的次数。

利用在关联规则中的连接操作运算，对于由k项集生成(k+1)项集，则仅对最后一位进行表记录添加和表记录删除操作，产生新的候选频繁项，并及时对表中项进行支持度判断。

可以用临时表的添加删除来完成频繁项的生成，在频繁数据项产生时，对于不能满足的项马上删除，而不是在生成数据项后进行统计、删除，从而减少了空间耗费。用D表示数据库，用|T|表示数据库中事务T的规模，即T中引用的个数。用|k|表示引用集k的长度。其算法过程描述如下：

第一步：生成事务数据库（经过数据预处理和事务识别后，就生成了事务数据库）。

第二步：扫描事务数据库，从中找出所有的引用长度为|k|=1的项的支持度，形成原始的频繁引用集，生成临时表table_1。

第三步：删除操作，删除事务数据库中所有的引用长度小于|k|的事务。以及删除事务数据库中所有的不包含任何k项频繁引用的事务。

第四步：对k频繁关联引用进行连接操作，以生成(k+l)项频繁关联引用。以k项频繁关联引用为基础，k引用的其它引用集的最后一引用依次添加进table_2和删除。进行判断，产生(k+l)项频繁关联引用。(该过程有两重嵌套循环)

1) 取生成的候选引用集中(长度为|k|)第i=1个引用。

2) 取第j=i+1引用且最后一引用与第i个引用集最后一引用不同的引用合并成k+l引用添加进临时表table_2中，生成了(k+1)引用集，并计算其支持度。若支持度大于最小支持度minsupport，则生成了第一个频繁关联引用，保存该频繁关联引用。

3) j=j+1，若j为k引用集最后一个记录则转到4)，否则转2)。

4) i=i+l，若i为k引用集最后一个记录则转到5)，否则转2)。

5) 所有符合条件的k+1引用集生成，则table_2 为k+l相关联引用，根据需要可对其进行保存。

第五步：k=k+l，把table_2 赋给bable_1，依次重复执行第三步，直到k引用集为Φ时终结。

4.2 算法模拟分析比较

利用表1(某用户中的事务数据)将筛选压缩的类Apriori挖掘算法与类Apriori算法进行比较，可得到类Apriori算法与基于临时表的算法的扫描规模与空间耗费分析。

算法执行过程：

1) 扫描一遍数据库D，对每个候选计数，统计每个页面的支持度得到引用长度为1的引用及其支持度（S），生成表table_1。筛选出S>=minsupport的引用生成表table_2。这里假设最小支持度为0.2，这样就可以确定table_2，table_2:{ {{C},1},{{G},0.33},{{L},0.33},{{W},0.33},{{WC},0.33}}；

2) 删除数据库中引用不大于1的TID，表table_2的内容赋给table_1。这里所有TID都大于1，所以数据库中记录没有变化；

3) 为发现频繁引用2的集合L2，使用L1连接L1产生候选2引用集C2，并获得其支持度。由于页面引用具有顺序性，所以这里是排列；

4) 比较候选支持度计数与最小支持度计数，找到满足最小支持度的页面加入到L2中，L2:{{ {C G},0.33},{{C L},0.33},{{C W},0.33},{{W WC},0.33}}；

5) 删除数据库中引用长度不大于2的TID。此时数据库记录为T100，T300，T600。把table_2的内容赋值给table_1；

6) 重复步骤3，为发现L3，L2连接L2，根据Apriori性质“一个频繁项集的所有子集也是频繁的”，由此获得L3，得到引用：{C W WC }，支持度：0.67；

7) 删除数据库中引用长度不大于3的TID。此时数据库中记录全部删除完，算法结束；

8) 最后得到此用户频繁引用页面C-W-WC。

5 结束论

由比较可见，删除操作是基于筛选压缩挖掘算法提高效率的关键，当挖掘到k频繁引用时，在完成k-1频繁引用挖掘后就着手删除一次事务项不超过k-1个项事务，显而易见，这将删除数据库中大量的记录，生成k频繁引用时扫描数据库的工作量大大减少，这就是基于筛选压缩挖掘算法提高效率的关键所在而类Apriori算法每次扫描都要彻底扫描整个原始数据库D，这要耗费大量的时间。

■

图1 时空耗费分析

6 模拟实验

用开发的简单Web日志挖掘系统SZS，对本算法进行了验证：SZS系统的数据处理流程可简要归纳为：将日志文件合并到数据库中，数据清洗，用户会话识别，事务识别和频繁遍历路径识别。首先，用本文提出的算法替代该系统的挖掘频繁遍历路径的部分，然后使用常州机电职业技术学院的Web服务器上的4月份的日志文件进行挖掘，并对原始数据文件进行初始化处理以后，获得了大约2000条引用。令最小支持度为2%，即引用次数达到40次的页面序列为频繁遍历路径。挖掘找到频繁遍历路径的结果如图2所示，实验结果表明本算法能够有效地识别出频繁遍历路径。

参考文献：

[1] Han J,Kamber M.数据挖掘概念与技术[M].范明,孟小峰,译.北京:机械工业出版社,2007.

[2] 杨怡玲.一个简单的Web日志挖掘系统[J].上海交通大学学报,2000,34(7):932-935.

[3] 吕橙,易艳红.一种挖掘Web用户访问模式的新方法MFP[J].小型微型计算机系统,2006,27(5):919-923.

[4] 吕橙,魏楚元.基于MFP方法的Web用户访问模式的模式发现[J].计算机应用 2007,27(3):555-569.

[5] HENM S,PARK J S,YU P S.Data mining for path traversal patterns in a Web environment[C].The 16th International Conference on Distributed Computing Systems.HongKong,1996:385-392.

[6] 唐北平,肖建华.通用Web日志挖掘系统设计实现[J].电脑知识技术,2006(11):310-311.