利用改进的Apriori算法挖掘用户浏览网页模式

梁少刚

（宝鸡职业技术学院 陕西 宝鸡 721000）

0 引言

随着计算机网络、电子商务的发展，很多商业性网站中对于用户的关注越来越多，因为了解用户的需求才能增高网站的收益，因此了解用户浏览模式是一项重要的工作。如何从这些海量的访问信息中发现潜在的有用的信息，确定用户浏览网页的顺序、频繁访问哪些网页，从而为用户推荐网页、推荐商品成为了一个新的研究课题。Web数据挖掘应运而生，Web数据挖掘就是从与WWW相关的资源和用户浏览行为中抽取感兴趣的、有用的模式和隐含的信息。Web上各种形式的文档和用户访问信息就构成了Web数据挖掘的对象。

挖掘用户访问模式常用算法有Web数据挖掘特有的用户访问路径模式挖掘算法(路径分析技术)和数据挖掘传统算法,如关联规则挖掘算法、序列模式挖掘算法等。而本文主要介绍如何利用Apriori算法来挖掘用户的浏览模式。

1 Apriori算法概述

Apriori算法是由R.Agrawal等人提出的一种快速挖掘算法，是大多数关联规则算法的基础，它是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法采用逐层搜索的迭代方法来找出所有的频繁项目集，在第k次迭代过程中找出所有的频繁k-项集Lk。该算法使用如下的Apriori性质：一个项目集是频繁项目集，则此项目集的所有子集构成的项目集也一定是频繁项目集；一个项目集是非频繁项目集，则此项目集的所有超集(即包含此项目集的项目集)一定是非频繁项目集。

Apriori算法的基本思想如下：C1=I，I为事务所包含的项目，扫描数据库，得到频繁1-项集L1，将L1中的项目集两两合并，产生C2，扫描数据库，得到L2，此后在第k遍扫描中，则是首先利用Lk-1来生成Ck，若Ck=Φ，则算法结束，否则扫描数据库得到Lk。在第k遍扫描中，第一步：连接步，通过Lk-1与自己连接来产生Ck（即侯选k-项集的集合）；第二步：剪枝步，Ck是Lk的超集，扫描数据库，确定Ck中每个候选的计数，计数值大于等于最小支持度计数的所有候选项是频繁的，从而属于Lk，删除不满足条件的其候选项。

综上所述，经典的Apriori算法描述如算法1.1所示。算法1.1挖掘关联规则的Apriori算法

输入：事务数据库D；最小支持度阈值min_sup输出：D中的频繁项集L Apriori算法自身虽然进行了一定的优化，但在实际应用中还是存在一些问题：

（1）需多次扫描事务数据库，通过模式匹配检查一个很大的侯选集合。由于挖掘的对象都是大型数据库或数据仓库，这样势必影响算法的效率，要提高效率关键是减少数据库遍历的次数和数据库的规模。

（2）可能产生大量的候选项集，不利于规则的产生。

为克服Apriori算法存在的问题、提高算法效率，人们提出了许多Apriori算法的变形来优化Apriori算法，如基于散列技术(散列项集计数)、事务压缩(压所进一步选代扫描的事务数)、划分(为找候项集划分数据)、选样(在给定数据的一个子集挖掘)、动态项集技数 (在扫描的不同点添加候选项集)等，这些算法从不同方面改善了Apriori算法的性能，提高了效率。

2 改进的Apriori算法

通过分析经典的Apriori算法还有一些改进算法的分析，可以看出，存在以下两个问题：

（1）更新支持度的时候，需要扫描数据库，而此时，数据库中有些项目已经被证明是非频繁的，可以不必扫描；有些事务根本不包括要寻找的项目，可以删除。所以，减少事务的数目和修剪每次交易里的项目数也是提高算法性能的关键。

（2）Aprior算法在从k-项目集生成候选k+1-项目集时，采用的是连接操作，该操作要判断是否前k-1项相同而第k项不同。这个操作占用了比较多的程序运行时间，如果能减少比较次数，也可以提高算法的性能。

2.1 连接步的改进

本文提出的连接步改进算法：设l1和l2是Lk-1中的项集，项集中的项按它在整个数据库中出现的频率按升序排序，执行连接 Lk-1×Lk-1时，若 l1[k-2]≠l2[k-2]，则停止对 l1和 l2的连接操作，因为此时产生的k-项集一定是冗余项集，以此来减少计算量。

证明：将Lk-1中的项按它在整个数据库中出现的频率按升序排序后，其中l1[k-2]出现的个数应该小于等于k-2，若l1[k-2]≠l2[k-2]，则 l1[k-2]出现的最大个数是 k-2。 而 Apriori算法的性质有：如果(k-1)-频繁项目集Lk-1中包含的单个项目I的个数小于k-1，则I不可能包含在频繁k-项目集中。因此在 Lk-1×Lk-1时，若 l1[k-2]≠l2[k-2]，则 l1[k-2]不可能包含在频繁k-项目集中，因此此时停止对l1和l2的连接操作。

因此对于算法1.1（输入输出均相同）我们可进行如下的改变：

算法1.2对于连接步的改进算法

2.2 剪枝步的改进

由算法1.1中我们可以看出剪枝步的思想是，Ck是Lk的超集，扫描数据库，确定Ck中每个候选的计数，计数值大于等于最小支持度计数的所有候选项是频繁的，从而属于Lk，删除不满足条件的其候选项。修剪步的改进思想：先计算|Lk-1(i)|，其中，i∈I。即计算Lk-1中所有项目的频度，再找出那些频度小于k-1的项目，记为I/={i||Lk-1(i)|＜k-1}，再在Lk-1中去掉所有包含I/中元素的频繁项目集而得到一个新的更小的 (k-1)-项频繁项目集的集合L/k-1，再由L/k-1与自身相连接而直接生成候选k-项集的集合Ck。

证明：由Apriori算法的性质可知，若k-项数据项目集I={i1,i2,…,ik}中，存在一个 i∈I使得|Lk-1(i)|＜k-1 则 I不是频繁项目集，其中|Lk-1(i)|表示(k-1)-项频繁项目集的集合Lk-1中包含i的个数。假设I是k-项频繁项目集，则它的k个(k-1)-项子集均在Lk-1中。则在由I生成的k个 (k-1)-项子集中每一个项目i∈I共出现k-1次，而 |Lk-1(i)|＜k-1这与条件矛盾，故I不是频繁项目集。

因此对于算法1.1（输入输出均相同）我们可进行如下的改变：

算法1.3对于剪枝步的改进算法

3 小结

本文详细介绍了Apriori算法，并对Apriori算法的思想进行了分析，在总结其不足后，提出了改进的Apriori算法，从连接步和剪枝步两部分提出了如何进行改进比给出了具体的设计思路。

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

[2]周祥,郑应平,王令群.基于 Web的数据挖掘技术研究及其在电子商务中的应用[J].电脑知识与技术:学术交流,2005（11）.

[3]陈炼,孙金华,饶泓,廖远,林渝.基于 Apriori改进算法的 Web 日志挖掘支撑工具的实现[J].南昌大学学报：工科版,2007，29（2）.