关联规则中Apriori算法的研究与改进

朱惠

摘要：随着科学技术的发展，人们可以更快、更方便地获取数据、保存数据，数据的量和复杂程度都是前所未见。该文对数据挖掘技术中的关联规则挖掘进行了系统的分析和研究，并在经典的Apriori算法的基础上改进了一个算法。该算法是一种基于矩阵的关联规则挖掘算法，通过扫描将数据库映射为0-1矩阵，直接在矩阵上进行运算，避免了反复扫描的过程，还对Apriori性质进行了引申和利用，对矩阵进行彻底的压缩。理论分析和实验证明了改进算法在效率上的提高。

关键词：关联规则；0-1矩阵

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）12-2697-05

Research and Improvement of Apriori Algorithm in Association Rules

ZHU Hui

（Dept. of Computer Science and Technology， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： With the rapid development of information technologies， people can get data and store data quickly and conveniently， which results in the unprecedented rising of the quantity and complexity of the data. This thesis presents the systematic analysis and research on the data mining and association rule mining. The algorithm is an algorithm of mining association rules based on matrix.The new algorithm maps the database into a 0-1matrix， computing directly on the matrix and avoiding scanning the database repeatedly. And also extended and utilization the properties of the Apriori， the matrix will be compressed more thoroughly. At the end of the paper， a theoretical analysis and experiment will been given.

Key words： association rules； 0-1 matrix

数据挖掘的一种比较常见的理解是：从大量的、不完整的、操作的大型数据库中，查找潜在的、有价值的、有趣的知识发现（ KDD，Knowledge Discovery in Database ）过程。数据挖掘过程如图1所示。关联规则是数据挖掘中，应用最广泛、研究最深入的一个方法。它最早是由 Agrawal 等人提出的（ 1993 ）。最初的提出是针对购物篮分析问题（ Market Basket Analysi ）提出的，其最初目的是为了发现交易数据库中售出的不同商品之间的联系规则。这些联系规则反应了顾客的购买行为模式，为销售者提供销售知识，指导商家科学地安排进货、人性化地设计货架以及科学地设计库存等。关联规则的挖掘应用领域非常广泛，比如电信业、医药业、制造业、政府数据库、公安破案、安全交易、交通数据处理、保险业等等。可以发现，关联规则挖掘对于诸多领域都有很好的应用，所以对于它的研究意义重大。

1 Apriori算法概述

Apriori算法是所有算法中最有代表性的，它的应用也是最为的广泛。该算法的主要思路是首先，找出频繁 1-项集的集合。该集合记作 L1。然后用 L2 找候选 2-项集的集合 C2，再根据支持度删除不满足条件的项，找到频繁2-项集。而 L2 用于找 C3，C3 用于找 L3，以此类推，直到没有频繁 k-项集为止。然后用找出的频繁集通过公式计算得到最后的强关联规则。从这个算法的大致思路就可以看出，每计算一个候选项集的支持度的时候，都要对整个数据库进行一次扫描，当候选项集比较大的时候，扫描次数将变得非常的多，这样就会验证影响算法的效率。

Apriori 性质[1]：频繁项集的所有非空子集也都是频繁的。

证明：假设一个项集 M，不是频繁项集，那么久说明他的支持度是小雨最小支持度的。当将任意一个项 m 加入到项集 M 中，项集 M 就变成了 M∪m，长度为 |M|+1，而长度为 |M|+1 的项集出现的次数不可能比长度为 |M| 的出现次数要多，既然 M 不是频繁集，那么 M∪m 就更不可能是频繁项集了。所以 M 的任意超级都不可能是频繁项集。这样也即能得出，频繁项集的所有子集都肯定是频繁项集。

这一性质还有另外一个名词，叫做反单调性，即如果一个项不是频繁的，那么它的所有超集都不可能是频繁的。

2 算法改进的概述

本改进算法主要是针对 Apriori 算法的几个性质进行的。首先对 Apriori 的几个算法的性质进行简单介绍：

1）如果设 Lk-1 是频繁 （k-1）-项集项集，Ik 是频繁 k-项集。那么 Ik-1 中包含的 Ik 的 （k-1）-项子集的个数一定不大于或等于 k。如果不大于，那么 Ik 就肯定不是频繁项集。

2）当要挖掘频繁 （k+1）-项集时，就可以将数据库中长度小于等于 k 的项进行删除。endprint

3）如果当频繁 k-项集的长度不大于 k+1 时，那么源数据库中最大频繁项集的长度为 k。

改进的Apriori具体的算法

1）扫描数据库 D，建立矩阵 R

首先给出数据库的几个集合：

事务数据库 D={T1，T2，...，Tm}，这里，数据库中事务的个数有 m 个；

项目集 I={I1，I2，...，In}，这里，项目集中项目的个数有 n 个。

首先，根据事物数据库建立布尔矩阵 R。由布尔矩阵定义可知，该矩阵中的元素只有“0”和“1”。这里的“0”和“1”设置方法如下：

将行向量设为事务 T，将列向量设为项i。当一个项出现在某一事务 T 中，那么就将该项所在的行与改事务所在的列所指向的位置设为1，若不出现，则设为0。然后再在建立的矩阵后面分别在加一行一列，行来写入每个乡的支持度，而列用来写入每个项的编码。

生成布尔矩阵R（m+2）·（n+1）具体算法如下：

for（j=1；j

{

R[0][j]=j； //填充项编号行

R[m+1][j] =0； //填充 sum_c 行，初值为 0

}

for（i=1；i<=m；i++）

{ sum_r=0； //项支持度初值为 0

for（j=1；j<=n；j++） //将 j 从1到 n 进行循环

if （ij in Ti） //若 ij 在事务 Ti 中

{ R[i][j]=1； // 将矩阵中的元素设为“1”

sum_r++； //统计支持度

R[m+1][j]++； //统计行的项数

}

else R[i][j]=0； // 若ij不在事务Ti中

R[i][0]=sum_r； //则将布尔矩阵中元素设为“0”

}

2）用函数 min_supsh=ceiling（min_sup*m）（ ceilong 的作用是计算大于或等于 min_sup*m 的整数）来计算项的支持数。删除 sum_c 中比最小支持数 min_supsh 小的项，经删除后的项目集就是频繁项集。此时得出 sum_r 的结果，然后再对表中元素等于 0 的项进行筛选。

3）k=2；

4）应用 Apriori 算法的性质，对上面所得到的表进行压缩。压缩方式如下：扫描列 sum_r，找出其中小于 k 的元素，因为它不可能成为频繁项集，所以可以将其删除；再扫描行sum_c，找出其中小于最小支持数 min_supsh 的元素，因为它也不可能成为频繁项集，所以可以及将其进行删除；然后再先扫描列 sum_r，再扫描行 sum_c，再进行删除操作，这样反复的操作，一直删除，知道不能再删除为止。

5）求频繁k-项集。将频繁 （k-1）-项集经过自连接，生成 [P=Ck-1c_num-1]个候选项集，然后再将这些候选项集中的每个元素的列向量进行与运算，得出的向量中“1”的个数，就是该项集的支持度。最后删除支持度小与于小支持度的项集，剩余的就是频繁项集。

求频繁 k-项集的主要代码如下：

// R 为压缩后的事物矩

// r_num 为 R 的行数，c-num 为 R 的列数

// L：频繁k-项集

// W 数组存放 p 个 k 维项组合对

for （a=0；a

{ sup_n=0； // k-项集支持度初值为 0

for（i=1；i

{

cj=1；

for（m=1；m<=k；m++）

{ cm=cm*R[i][W[p][j]]； //“与”运算

if（cm==o） break；

}

Sup_n=suo_n+cj； //统计 k-项集支持度

}

if sup_n>=min_supsh //为频繁集

{ for（m=0；m

L[m]=R[0][W[p][m]]； //求 k维数组合的项数

Lk=Lk∪L；

}}

6）计算出|Kk|，若|Lk|>=k+1，k=k+1，跳转到 4）；否则停止算法。

3 改进的Apriori算法在用户行为分析中的应用

用户行为分析是网络信息检索技术得以前进的重要基石，也是能够在商用搜索引擎中发挥重要作用的各种算法的基本出发点之一。为了更好的理解用户的点击行为，该文对亚马逊某一段时间内的70万多条访问记录进行了分析。该数据主要包含了在一段特定的时间内，不同的用户所访问的网站代码以及访问的时间等。原始的部分数据如图2所示。

系统的硬件要求环境并不是很高，需要1台性能一般的电脑便可以了。本系统的开发环境如下：

操作系统： window7；处理器：pentium r dualcore cpu T4200 ；主频、内存：2.00GHz，2G；数据源：亚马逊访问记录；开发语言：c＼Java；开发平台：Eclipse。

根据上一章节的算法设计，将使用新的关联规则改进算法对用户网站访问记录进行分析。首先是要对源数据进行预处理，将没有用的信息删除，提取出要处理的有用信息，然后对提取出来的信息进行规整，为下一步数据挖掘做好准备。

亚马逊用户行为分析日志数据为 716064 条，经过清理后的数据为 4254 条。

扫描数据库 D，建立矩阵 R：

首先，根据事物数据库建立布尔矩阵R。由布尔矩阵定义可知，该矩阵中的元素只有“0”和“1”。这里的“0”和“1”设置方法为：将行向量设为事务 T，将列向量设为项 i。当一个项出现在某一事务 T 中，那么就将该项所在的行与改事务所在的列所指向的位置设为1，若不出现，则设为0。然后再在建立的矩阵后面分别在加一行一列，行来写入每个乡的支持度，而列用来写入每个项的编码。

然后，计算出每个项集的支持度。计算最小支持度是通过用函数 ceiling 来进行。该函数是通过计算每个列中“1”的个数来进行对支持度的计算的。

最后应用 Apriori 算法的性质，对上面所得到的表进行压缩。压缩方式如下：扫描列 sum_r，找出其中小于 k 的元素，因为它不可能成为频繁项集，所以可以将其删除；再扫描行 sum_c，找出其中小于最小支持数 min_supsh 的元素，因为它也不可能成为频繁项集，所以可以及将其进行删除；然后再先扫描列sum_r，再扫描行 sum_c，再进行删除操作，这样反复的操作，一直删除，知道不能再删除为止。最后计算出|Lk|，若|Lk|>=k+1，K=K+1，继续扫描；否则停止算法。

经挖掘后的规则如表 1 与表 2 所示。其中表 5.1中，第一列为序号，第二列为页面代码，这张表所表示的是每个页面代码所对应的序号，即页面“11044”所对应的序号为 1。

表 2 中，第一列为强规则，第二列为强规则所对应的权值。在这里，设定当权值大于 1 时，所对应的规则为强规则。

当支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）时，强关联规则输出有向图如图 3 所示。

从图 3 可以看出，随着设定的最小支持度的不断变大，得到的规则越来越少。而不管最小支持度怎么变化，得出的总体趋势不变，都是以固定几个主要的点向外出发。从实际情况出发，就可以知道，这几个网址之间的点击就是用户点击行为做频繁的。在调整页面设置时，就可以将这些网址链接放在一起，这样就能够很好地提高用户的点击率。

4 性能分析

对时间复杂度的分析：本改进算法通过扫描一次数据库，将数据库中信息映射到布尔型数据表中，以后的所有操作都不在需要扫描数据库，只要对布尔输几把进行分析，极大地降低了扫描数据库时所需的时间。而且在需找频繁集时，只要对表中的“0”和“1”进行操作，而不产生 Apriori 算法中所必须产生的候选项集，这样就避免了 Apriori 算法中的最大瓶颈，降低了时间复杂度。

对空间复杂度的分析：由于本算法在一开始就将数据映射到布尔数据表中，所以，往后的操作都是对“0”和“1”进行的，所以的源数据库中的数据都是有“0”和“1”表示的，而存储“0”和“1”所需要的空间远比原始数据要来的少，这样就减少了空间的占有量。

5 结束语

虽然改进的基于用户行为分析的兴趣数据挖掘系统在工作效率上有所提高，但是还是存在一些问题需要解决：

1） 通过改进系统算法，提升了基于用户行为分析的兴趣数据挖掘系统的工作效率，但是提升幅度有限，算法和系统性能仍有进一步优化和改进的空间。

2） 改进的基于用户行为分析的兴趣数据挖掘系统处理所得到结果只可以为 Boolean 型（即真假），不能为用户产生量化的结果，也就是说无法在“真”的基础上给出程度的表示。

3） 系统相关的初始数据需要更新与丰富。系统中用来得到用户兴趣信息的用户训练数据和用户兴趣表都需要进一步的丰富和完善，从而使得训练完成后，系统能给出更加准确的处理结果。

参考文献：

[1] 陆楠.关联规则的挖掘及其算法的研究[D].长春：吉林大学， 2007.

[2] 伊卫国.基于关联规则与决策树的预测方法研究及其应用[D].大连：大连海事大学， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改进及其在教育决策系统中的应用[D].长春：吉林大学，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩阵的 Apriori 算法改进[J].计算机工程，2006，32（23）：68-69.

[8] 曾万聃，周绪波，戴勃，等.关联规则挖掘的矩阵算法[J].计算机工程，2006，32（2）：45-47.endprint

亚马逊用户行为分析日志数据为 716064 条，经过清理后的数据为 4254 条。

扫描数据库 D，建立矩阵 R：

首先，根据事物数据库建立布尔矩阵R。由布尔矩阵定义可知，该矩阵中的元素只有“0”和“1”。这里的“0”和“1”设置方法为：将行向量设为事务 T，将列向量设为项 i。当一个项出现在某一事务 T 中，那么就将该项所在的行与改事务所在的列所指向的位置设为1，若不出现，则设为0。然后再在建立的矩阵后面分别在加一行一列，行来写入每个乡的支持度，而列用来写入每个项的编码。

然后，计算出每个项集的支持度。计算最小支持度是通过用函数 ceiling 来进行。该函数是通过计算每个列中“1”的个数来进行对支持度的计算的。

最后应用 Apriori 算法的性质，对上面所得到的表进行压缩。压缩方式如下：扫描列 sum_r，找出其中小于 k 的元素，因为它不可能成为频繁项集，所以可以将其删除；再扫描行 sum_c，找出其中小于最小支持数 min_supsh 的元素，因为它也不可能成为频繁项集，所以可以及将其进行删除；然后再先扫描列sum_r，再扫描行 sum_c，再进行删除操作，这样反复的操作，一直删除，知道不能再删除为止。最后计算出|Lk|，若|Lk|>=k+1，K=K+1，继续扫描；否则停止算法。

经挖掘后的规则如表 1 与表 2 所示。其中表 5.1中，第一列为序号，第二列为页面代码，这张表所表示的是每个页面代码所对应的序号，即页面“11044”所对应的序号为 1。

表 2 中，第一列为强规则，第二列为强规则所对应的权值。在这里，设定当权值大于 1 时，所对应的规则为强规则。

当支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）时，强关联规则输出有向图如图 3 所示。

从图 3 可以看出，随着设定的最小支持度的不断变大，得到的规则越来越少。而不管最小支持度怎么变化，得出的总体趋势不变，都是以固定几个主要的点向外出发。从实际情况出发，就可以知道，这几个网址之间的点击就是用户点击行为做频繁的。在调整页面设置时，就可以将这些网址链接放在一起，这样就能够很好地提高用户的点击率。

4 性能分析

对时间复杂度的分析：本改进算法通过扫描一次数据库，将数据库中信息映射到布尔型数据表中，以后的所有操作都不在需要扫描数据库，只要对布尔输几把进行分析，极大地降低了扫描数据库时所需的时间。而且在需找频繁集时，只要对表中的“0”和“1”进行操作，而不产生 Apriori 算法中所必须产生的候选项集，这样就避免了 Apriori 算法中的最大瓶颈，降低了时间复杂度。

对空间复杂度的分析：由于本算法在一开始就将数据映射到布尔数据表中，所以，往后的操作都是对“0”和“1”进行的，所以的源数据库中的数据都是有“0”和“1”表示的，而存储“0”和“1”所需要的空间远比原始数据要来的少，这样就减少了空间的占有量。

5 结束语

虽然改进的基于用户行为分析的兴趣数据挖掘系统在工作效率上有所提高，但是还是存在一些问题需要解决：

1） 通过改进系统算法，提升了基于用户行为分析的兴趣数据挖掘系统的工作效率，但是提升幅度有限，算法和系统性能仍有进一步优化和改进的空间。

2） 改进的基于用户行为分析的兴趣数据挖掘系统处理所得到结果只可以为 Boolean 型（即真假），不能为用户产生量化的结果，也就是说无法在“真”的基础上给出程度的表示。

3） 系统相关的初始数据需要更新与丰富。系统中用来得到用户兴趣信息的用户训练数据和用户兴趣表都需要进一步的丰富和完善，从而使得训练完成后，系统能给出更加准确的处理结果。

参考文献：

[1] 陆楠.关联规则的挖掘及其算法的研究[D].长春：吉林大学， 2007.

[2] 伊卫国.基于关联规则与决策树的预测方法研究及其应用[D].大连：大连海事大学， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改进及其在教育决策系统中的应用[D].长春：吉林大学，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩阵的 Apriori 算法改进[J].计算机工程，2006，32（23）：68-69.

[8] 曾万聃，周绪波，戴勃，等.关联规则挖掘的矩阵算法[J].计算机工程，2006，32（2）：45-47.endprint

亚马逊用户行为分析日志数据为 716064 条，经过清理后的数据为 4254 条。

扫描数据库 D，建立矩阵 R：

首先，根据事物数据库建立布尔矩阵R。由布尔矩阵定义可知，该矩阵中的元素只有“0”和“1”。这里的“0”和“1”设置方法为：将行向量设为事务 T，将列向量设为项 i。当一个项出现在某一事务 T 中，那么就将该项所在的行与改事务所在的列所指向的位置设为1，若不出现，则设为0。然后再在建立的矩阵后面分别在加一行一列，行来写入每个乡的支持度，而列用来写入每个项的编码。

然后，计算出每个项集的支持度。计算最小支持度是通过用函数 ceiling 来进行。该函数是通过计算每个列中“1”的个数来进行对支持度的计算的。

最后应用 Apriori 算法的性质，对上面所得到的表进行压缩。压缩方式如下：扫描列 sum_r，找出其中小于 k 的元素，因为它不可能成为频繁项集，所以可以将其删除；再扫描行 sum_c，找出其中小于最小支持数 min_supsh 的元素，因为它也不可能成为频繁项集，所以可以及将其进行删除；然后再先扫描列sum_r，再扫描行 sum_c，再进行删除操作，这样反复的操作，一直删除，知道不能再删除为止。最后计算出|Lk|，若|Lk|>=k+1，K=K+1，继续扫描；否则停止算法。

经挖掘后的规则如表 1 与表 2 所示。其中表 5.1中，第一列为序号，第二列为页面代码，这张表所表示的是每个页面代码所对应的序号，即页面“11044”所对应的序号为 1。

表 2 中，第一列为强规则，第二列为强规则所对应的权值。在这里，设定当权值大于 1 时，所对应的规则为强规则。

当支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）时，强关联规则输出有向图如图 3 所示。

从图 3 可以看出，随着设定的最小支持度的不断变大，得到的规则越来越少。而不管最小支持度怎么变化，得出的总体趋势不变，都是以固定几个主要的点向外出发。从实际情况出发，就可以知道，这几个网址之间的点击就是用户点击行为做频繁的。在调整页面设置时，就可以将这些网址链接放在一起，这样就能够很好地提高用户的点击率。

4 性能分析

对时间复杂度的分析：本改进算法通过扫描一次数据库，将数据库中信息映射到布尔型数据表中，以后的所有操作都不在需要扫描数据库，只要对布尔输几把进行分析，极大地降低了扫描数据库时所需的时间。而且在需找频繁集时，只要对表中的“0”和“1”进行操作，而不产生 Apriori 算法中所必须产生的候选项集，这样就避免了 Apriori 算法中的最大瓶颈，降低了时间复杂度。

对空间复杂度的分析：由于本算法在一开始就将数据映射到布尔数据表中，所以，往后的操作都是对“0”和“1”进行的，所以的源数据库中的数据都是有“0”和“1”表示的，而存储“0”和“1”所需要的空间远比原始数据要来的少，这样就减少了空间的占有量。

5 结束语

虽然改进的基于用户行为分析的兴趣数据挖掘系统在工作效率上有所提高，但是还是存在一些问题需要解决：

1） 通过改进系统算法，提升了基于用户行为分析的兴趣数据挖掘系统的工作效率，但是提升幅度有限，算法和系统性能仍有进一步优化和改进的空间。

2） 改进的基于用户行为分析的兴趣数据挖掘系统处理所得到结果只可以为 Boolean 型（即真假），不能为用户产生量化的结果，也就是说无法在“真”的基础上给出程度的表示。

3） 系统相关的初始数据需要更新与丰富。系统中用来得到用户兴趣信息的用户训练数据和用户兴趣表都需要进一步的丰富和完善，从而使得训练完成后，系统能给出更加准确的处理结果。

参考文献：

[1] 陆楠.关联规则的挖掘及其算法的研究[D].长春：吉林大学， 2007.

[2] 伊卫国.基于关联规则与决策树的预测方法研究及其应用[D].大连：大连海事大学， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改进及其在教育决策系统中的应用[D].长春：吉林大学，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩阵的 Apriori 算法改进[J].计算机工程，2006，32（23）：68-69.

[8] 曾万聃，周绪波，戴勃，等.关联规则挖掘的矩阵算法[J].计算机工程，2006，32（2）：45-47.endprint