基于矩阵的频繁项集挖掘算法

摘要: 在所有频繁项集挖掘算法中,Apriori算法一直是一个经典的算法，但是该算法存在的最大缺陷是要进行多次的数据库扫描并且在挖掘过程中产生大量的候选频繁项集，因此效率很低.提出了利用基于矩阵的方法挖掘频繁项集，很好地避免了这个缺陷.

关键词: 数据挖掘；矩阵；关联规则；Apriori算法；频繁项集

中图分类号:TP18

文献标识码:A文章编号:1672-8513(2010)05-0334-03

A New Algorithm Based on Matrix to Mine Frequent Item Sets

YANG Jing, ZHENG Zhongzhi,SONG Jinge，DUAN Peng

(School of Mathematic and Computer Science, Yunnan University of Nationalities, Kunming 650031, China)

Abstract: Apriori algorithm has been considered as a classic algorithm to mine frequent item sets. But its major defect is that the database has to be scanned many times, and there are a large number of candidate item sets in the result. So this algorithm is inefficient. This research proposes a new algorithm based on matrix to mine frequent item sets and it can help overcome such defect.

Key words: data mining; matrix; association rule; Apriori algorithm; frequent item set

关联规则挖掘是数据挖掘的一种［1-2］，是描述在一个事件中不同的项之间同时出现的规律的知识模式，具体地针对一个事务数据库来说，关联规则就是通过量化的数据描述某种物品的出现对另一种物品的出现有多大的影响.

挖掘关联规则主要包含以下2个步骤.

步骤1:发现所有的频繁项集，根据定义，这些项集的频率至少应该等于（预先设置的）最小支持度；

步骤2:根据所获得的频繁项集，产生相应的强关联规则.根据定义这些规则必须满足最小信任度阈值.

此外还可利用有趣性度量标准来帮助挖掘有价值的关联规则知识.由于步骤2中的相应操作极为简单，因此挖掘关联规则的整个性能就是由步骤1中的操作处理所决定.因此，基本上所有关于挖掘关联规则的研究都围绕步骤1展开.

传统的挖掘频繁项集的经典算法是Apriori算法.但是随着研究的深入，它的缺点也暴露出来.Apriori算法有2个致命的性能瓶颈.

1)多次扫描事务数据库，需要很大的I/O负载.对每次k循环，候选集Ck中的每个元素都必须通过扫描数据库1次来验证其是否加入频繁项目集Lk.

2)可能产生庞大的候选集.由Lk－1产生k-候选集Ck是指数增长的.如此大的候选集对时间和主存空间都是一种挑战.

1 基于矩阵的频繁项集挖掘算法

随着研究的不断深入，各种挖掘频繁项目集的算法相继被提出，在文献［3］中作者的主要思想是将矩阵和向量内积结合使用，从而产生频繁项目集，进而挖掘出关联规则；在文献［4］中作者主要思想是在矩阵的基础上，分别统计各个商品的频数，然后计算其他商品相对于该商品的信任度，从而挖掘出事务数据库内的关联规则；而在文献［5］中作者利用矩阵对Apriori算法进行改进，从而避免多次扫描原始事务数据库.除此之外，还有许多其他的关于关联规则的方法被提出［6-8］，在这就不一一介绍了.

本文提出了一种基于矩阵的频繁项集挖掘算法.与文献［3］中的方法相比，本文提出的方法更加简洁方便，求解过程中只用到矩阵中行之间的加法，实现程序也非常简单.

该算法的主要思想如下：

首先根据所要分析的事务数据定义1个矩阵，矩阵的每一行表示事务数据库中的每一条购买记录的购买情况，矩阵的每一列表示各种事物的被购买情况.矩阵中的元素只用0和1两个数表示，当矩阵中第i行，第j列的元素为0时，元素0表示第i条购物记录所对应的购物者没有购买j列所对应的商品；相反当矩阵中第i行，第j列的元素为1时，元素1表示第i条购物记录所对应的购物者购买了j列所对应的商品.

其次，由题设的最小支持度要求及数据库的大小计算出相应的最小支持计数，设该最小支持计数为n.

最后，根据以下提出的定理完成频繁项目集的挖掘.

定理 设由题设计算出的最小支持计数为n，则某一频繁项集中包含某一组商品的充要条件是由任意选取已知矩阵中的n个行相加而得到的所有一维数组集中必存在1个一维数组使得该组商品对应该一维数组的分量都为n.

证明 充分性的证明：若任选n个行相加得到的所有的一维数组集中存在1个一维数组使得某组商品对应分量都为n，由于矩阵只由0和1构成，则在原矩阵中必存在n个行使得这n个行对应这组商品的分量的值都为1，即这n条记录所对应的购买者都买了这组商品，那么这组商品也就满足了最小支持计数要求，则频繁项集中必包含这组商品.

必要性的证明：若某一频繁项集中包含某一组商品，也就是说这组商品同时被购买的次数大于或等于要求的最小支持计数n，即在原矩阵中存在m(m>n)个行，使得这些行对应该组商品的分量的值都为1，在这m行里选取n个行相加得到1个一维数组，该一维数组所对应这组商品的分量也就都为n.定理证明完毕.

本文算法的具体描述：

输入：事务数据；

输出：该事务数据的频繁项集；

步骤1:用布尔矩阵A表示事务数据库中的数据；

步骤2:根据数据库大小及最小支持度要求计算出相应的最小支持计数n；

步骤3:计算出由任意选取已知矩阵中的n个行相加而得到的所有的一维数组集；

步骤4:扫描由步骤3得到的所有一维数组，并由这些数组得出所有的频繁项集.

2 本文算法的运用

本例题基于某商场的日常销售事务数据库，数据库中有9条数据记录.这9条记录分别是T1=［A B E］，T2=［B D］，T3=［B C］，T4=［A B D］，T5=［A C］，T6=［B C］，T7=［A C］，T8=［A B C E］，T9=［A B C］.上面9条数据中中括号内的大写字母A,B,C,D,E分别表示5种商品，放在同一个中括号内的字母表示被某顾客同时购买的物品.假定最小支持计数为2.要求：求出该数据库的频繁项目集.

这里先把这9条数据转化为一个9×5的矩阵，矩阵的行分别表示9个事务，矩阵的列依次表示A,B,C,D,E这5种商品被购买情况，根据上面介绍的算法思想，该事务数据库中的数据就可以用如下的一个9×5的矩阵表示:

基于上述理论,我们可以把该矩阵中9个行两两相加，这里有36种可能结果，也就是有36个一维数组构成结果，然后对这36个一维数组进行逐个检查以确定符合要求的频繁项集.例如把原矩阵的第1行和第2行相加便得到如下s矩阵的第1行，根据此行便得知［B］为频繁1-项集；把原矩阵的第1行和第3行相加便得到如下s矩阵的第2行，根据此行也可得知［B］为频繁1-项集；把原矩阵的第1行和第4行相加便得到如下s矩阵的第3行，根据此行就可得知［A B］为频繁2-项集，［A］，［B］均为频繁1-项集.把原矩阵中9个行两两相加，得到的结果矩阵s如下所示：

由于矩阵s的各列均含有元素为2，所以［A］，［B］，［C］，［D］，［E］均为频繁1-项集，而所有行都没有出现4个或4个以上的2，说明该数据库没有频繁4-项集，也没有频繁5-项集.第7行和第36行出现了3个2，说明该数据库有2个频繁3-项集，分别为［A B C］和［A B E］.由Apriori性质［1］可知，［A B C］和［A B E］的2-项子集都是频繁2-项集，所以［A B］,［B C］,［A C］,［A E］,［B E］均为频繁2-项集，除此之外，扫描矩阵s发现第10行有两个2，即［B D］也为频繁2-项集.

由分析可知，此事务数据库的

频繁1-项集为：［A］,［B］,［C］,［D］,［E］;

频繁2-项集为：［A B］,［B C］,［A C］,［A E］,［B E］,［B D］;

频繁3-项集为：［A B C］,［A B E］.

以上便是基于矩阵的频繁项集挖掘算法具体思想及应用.

如果对这个例题用Apriori算法求解，由于结果中存在13个频繁项集，因此至少需要扫描事务数据库13次，并且在求解过程中需要用大量的连接操作去产生候选频繁项集，产生的候选频繁项集会占用大量的内存空间，在产生候选频繁项集后还需多次使用Apriori性质对这些候选频繁项集进行判断.相比而言，运用本文提出的算法求解就会简单得多，只需扫描事务数据库1次，不需产生候选频繁项集，节省了内存空间，也就避免了反复使用Apriori性质对候选频繁项集进行判断.

3 结语

此方法与Apriori算法相比较，其优点是：首先，算法在执行过程中只需扫描事务数据库1次，扫描的过程中将事务数据库的内容转换为布尔矩阵，减少了频繁扫描原始的事务数据库所需消耗的大量时间，因而有效地解决了Apriori算法迭代产生频繁项集的瓶颈问题；其次，该算法不用产生大量的候选频繁项集，节省了大量的内存空间，更无需反复使用Apriori性质对候选频繁项集进行判断.因此，该算法具有较高的效率.与其他的基于矩阵的方法相比，该算法更简洁明了，方便易懂.其缺点是对于海量数据库，当要求的最小支持计数特别大时，算法所需用的循环将很多并且非常复杂，如何克服这个困难将是下一步着重的研究方向.

参考文献:

［1］HAN Jiawei, KAMBER M. 数据挖掘概念与技术［M］. 北京: 机械工业出版社,2006.

［2］佘玉梅, 段鹏. 人工智能及其应用［M］.上海:上海交通大学出版社,2007.

［3］方炜炜,杨炳儒,宋威,等.基于布尔矩阵的关联规则算法研究［J］.计算机应用研究,2005,25(7):1964-1966.

［4］高正红,邵良杉,沈学利.基于布尔矩阵的关联挖掘算法［J］.科技资讯,2007(4):59-60.

［5］李娟,张明义,汪维清.基于矩阵的关联规则增量式更新算法［J］.云南民族大学学报:自然科学版,2007,16(2):148-151.

［6］王新, 赵强.不完全数据库中的关联规则挖掘［J］.云南民族大学学报:自然科学版,2005，14(3): 252-258.

［7］冯玉才,冯剑琳.关联规则的增量式更新算法［J］.软件学报, 1998,9(4):301-306.

［8］朱绍文,王泉德,黄治,等.关联规则挖掘技术及发展动向［J］.计算机工程,2000,26(9):4-6.