基于Apriori改进算法的频繁路径挖掘——以实现图书移动路径挖掘为例

王宇一

（江苏信息职业技术学院信息化建设与管理中心，江苏无锡 214153）

1 Apriori算法

Apriori算法首先利用递归的方法对数据进行逐层挖掘找出所有的频集，然后从这些频集中产生关联规则，最后除去那些小于用户预设的最小可信度和最小支持度的规则，留下的便是需要的强关联规则。Apriori算法的主要描述如下［1］：

事务数据库F；最小支持度min_s。

输出：F的频繁项集L。

（1）L1={frequent_1-itemsets}；//初始产生的频繁1-项集的集合；

（2）for（x=2；Lx-1≠；x++）{//由频繁x-1-项集产生频繁x-项集；

（3）Cx=ap_hxx（Lx-1）；//调用函数 ap_hxx，由 Lx-1 产生新的候选项集 Cx；

（4）for all affairs t∈D do{//对于事务数据库F中的每一个事务t；

（5）Ct=subset（Cx，t）；//t中所包含的候选项集Cx；

（6）return L=∪xLx；//频繁项集L为输出结果。

函数ap_hxx通过连接产生新的候选项集，并根据“频繁路径+Apriori性质”的定义对Ck内的候选项集进行删选，删除那些不包含频繁路径子集的候选项集。

只要检查候选项集的子集是否为频繁路径集，就可判断该候选项集是否为频繁路径集。这里用函数has_apriori_s完成非频繁路径子集的测试，描述如下［1］：

funtion has_apriori_s（C，Lx-1）{//C 为候选 x项集，Lx-1为频繁 x-1项集。

（1）for each（x-1）-subset s ofC//对每个 k-1 项子集 s；

（2）ifs Lk-1 then//如果s不在Lk-1中则返回true，即从Ck中删除。

2 Apriori算法的不足

Apriori算法通过递归搜索的方法［2］来产生强关联规则。该算法虽然简单易懂，容易实现，但在实际应用中仍有许多不足之处。

2.1 重复扫描数据库

在Apriori算法中扫描数据库的次数是根据频繁项集的长度而定的，这就是说每产生一次频繁项集都要扫描一次数据库，直到产生出最大频繁项集为止。

2.2 候选项集太多

用Apriori算法生成关联规则的过程中会产生大量的候选项集，这些候选项集又会带来大量的中间数据［2］。

2.3 执行时间较长

在频繁项集的长度较大而事务并没有减少的情况下，Apriori算法需要消耗较长的时间才能完成对非频繁项集的删选工作。

2.4 挖掘效率较低

Apriori算法只是单纯依靠设定的支持度来产生强关联规则［3］，并没有考虑到项目的重要性［4］，如此导致了大量无用规则的产生，大大降低了挖掘的效率。

2.5 分析数据不全面

因为算法设定了最小支持度，所以无法对小于这个支持度的事务进行分析。同时算法的效率还会随着支持度的变小而降低。

3 改进的Apriori算法

3.1 改进算法的描述

用Apriori算法进行数据挖掘时扫描数据库的次数与频繁项集的长度有关，如频繁项集的长度为N时就需扫描数据库N次，这样不仅给网络的传输造成了一定的负担，还明显降低了Apriori算法的挖掘效率。因此本文在设计Apriori改进算法时，考虑改变原有数据库的存储结构，建立临时二进制数据库，并采用二进制位的方法来表示项目在事务集中出现的情况，如项目在某事务中出现就用“1”来表示，反之用“0”来表示，然后通过设定的最小支持度(min_sup)对候选项集进行删选，直到产生出最大频繁项集为止。如此较好地减少了扫描数据库的次数和产生候选项集的个数，大大提高了算法的效率。

3.2 改进算法在频繁路径挖掘中的具体步骤

3.2.1 创建临时二进制数据库

抽取RFID数据库中图书的路径数据组成事务数据库，并把图书的属性值嵌入路径记录来作为事务数据库中的事务P；同时用单个形如（location，times）的路径段或属性值来表示事务中的每个项目（path）；之后通过对事务数据库的扫描来创建临时二进制数据库，该数据库以项目为主键，另用二进制位来表示项目的事务集，也就是每个项目依次在所有事务中出现的情况，如它在某事务中出现就用“1”表示，未出现则用“0”表示；最后统计“1”的个数作为各项目的支持数（countp），countp=supportp*|DB|，所以min_countp=min_supportp*|DB|，其中|DB|为事务P的总数。

3.2.2 生成频繁1-路径集

用统计好的项目支持数依次与指定的最小支持数进行比较，如其支持数大于等于最小支持数，那么该项就是频繁路径，如小于则为非频繁路径；最后根据比较结果，删除非频繁路径，得到长度为1的频繁1-路径集。

3.2.3生成频繁2-路径集

先将频繁1-路径集中所有的项目两两相交，也就是进行二进制位的与运算，并统计运算结果中“1”的个数来作为项目的新支持数，得到包含2个路径段和属性值的候选2-路径集；接着同样把新支持数与最小支持数进行比较，最后删除候选集中的非频繁路径，得到长度为2的频繁2-路径集。

3.2.4 生成频繁k-路径集

从频繁3-路径集开始，只需求前k-2项相同的两个项目的交集，不同的则不需再重复运算，就可生成符合的所有频繁路径集。当再没有新的频繁路径产生时，最终的频繁路径集就是最大频繁路径集。

3.3 改进算法在频繁路径挖掘中的应用举例

设事务数据库为D，其事务P的总数为4，即|DB|=4，指定最小支持度（min_sup）为0.5，据上所述，可得到最小支持数（min_cup）为2。路径数据中各地点的含义为：c，仓库；j，书架；r，阅览室。停留以“小时”为时间单位，如表1所示。

表1 事务数据库D

首先把表1中的项数N与最小支持数2进行比较，然后通过对事务数据库D的一次扫描来创建临时二进制数据库，它以项目（path）为主键，并用二进制位来表示项目的事务集，也就是代表 （c，1）、（j，2）、（r，7）、（r，5）、（c，30）、（小说）、（散文）、（随笔）这8个项分别在每条事务（路径）中出现的情况，如有出现则用“1”表示，未出现则用“0”表示；最后统计“1”的个数作为各项目的支持数（countp），如表2所示。

表2 临时二进制数据库

由于最小支持数为 2，而表 2 中（r，7）、（c，30）、（散文）、（随笔）的支持数为 1，其支持数≤最小支持数，所以（r，7）、（c，30）、（散文）、（随笔）是非频繁路径，它们更不属于最大频繁路径集，因此将其删除，得到长度为1的频繁1-路径集，如表3所示。

表3 频繁1-路径集表

根据表 3，把（小说）、（c，1）、（j，2）、（r，5）这 4 个路径两两相交，也就是进行二进制位的与运算，并同样对运算结果中“1”的个数进行统计作为路径的支持数［1］，得到包含2个路径段和属性值的候选2-路径集，如表4所示。

表4 候选2-路径集

由于最小支持数为 2，而表 4 中（小说）（r，5）、（j，2）（r，5）的支持数为 1，其支持数≤最小支持数，所以（小说）（r，5）、（j，2）（r，5）是非频繁路径，（小说）（r，5）、（j，2）（r，5）更不属于最大频繁路径集，因此将其从候选2-路径集中删除，得到长度为2的频繁2-路径集，如表5所示。

表5 频繁2-路径集

在将表5中长度为2的路径进行两两相交时，先判断其第1项是否相同，然后只求第1项相同路径的交集，也就是进行二进制位的与运算，并统计运算结果中“1”的个数获取新的支持数，最后得到包含3个路径段和属性值的候选3-路径集，如表6所示。

由于最小支持数为 2，而表 6 中（c，1）（j，2）（r，5）的支持数是 1，其支持数≤最小支持数，所以（c，1）（j，2）（r，5）是非频繁路径，它更不属于最大频繁路径集，因此将其删除，得到长度为3的频繁3-路径集，如表7所示。

表6 候选3-路径集

表7 频繁3-路径集

由于事务数据库D中事务P的总数为4，而频繁3-路径集的数目为1，所以事务数据库的最大频繁路径集为{（小说）（c，1）（j，2）}。

3.4 改进算法的分析

改进算法用二进制位来表示项目的事务集，并通过二进制的运算来获得各项目的支持数，然后将支持数与最小支持数进行比较，找出候选项集中的非频繁项，最后从候选项集中删除这些非频繁项来得到频繁项集。改进算法与经典算法相比具有以下优势。

3.4.1 降低访问数据量

改进算法只扫描原始数据库一次，当求候选项集Ck的支持数时只需访问二进制数据库的频繁k-1项集即可，并且随着k的增大，频繁k-1项集却在减小，因此大大降低了访问的数据量［3］。

3.4.2 快速求得交集

改进算法只需对项目的事务集进行二进制位的与运算就可完成两项集的交集。

3.4.3 节省存储空间

因为改进算法采用的是二进制数据库，所以大大节省了事务的存储空间，而且对二进制数进行运算远比对字符串来得快［4］。

3.4.5 实验结果

通过数据库WebDocs的测试来比较经典算法与改进算法的性能，同时考虑到基于Apriori的改进算法目前已有很多，为了体现出本文改进算法的优越性，在此加入了基于矩阵的Apriori改进算法和基于深度优先的Apriori改进算法来进行共同比较。另外，为了比较出几个算法的实际效率，我们采用相同的最小支持数和最小可信度，且在Pentium双核E5 300，内存1 024 M的环境下运行。实验结果如表8所示。

表8 不同算法的性能比较（min_cup=10 min_conf=0.5）

由表8可知，在事务数较少的情况下改进算法的性能与经典算法差不多，但随着事务数的增加，改进算法的效率明显优于经典算法。因其在任何情况下都只扫描原始数据库一次，而经典算法则需根据最大频繁项集的长度来确定扫描数据库的次数［5］。另外从本文的改进算法与另外两种改进算法的比较来看，本文的改进算法在性能上也略有提高，虽然不是很多，但在事务数不断增加的情况下仍具有一定的优越性。