一种新的关联规则挖掘算法

摘要：对关联规则算法进行了研究和分析，基于候选集的Apriori-like算法需要反复扫描数据库，并产生大量的候选集，在挖掘低支持度、长模式的规则时效率低下。针对算法的缺陷，该文提出了一种PS算法，优化了关联规则的挖掘。实验结果证明了该算法的有效性。

关键词： 数据挖掘；关联规则

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)17-20ppp-0c

A New Association Rules Mining Algorithm

LIU Zhi-yi, CHANG Rui

(Changzhou Institute of Technology,Changzhou 213002,china)

Abstract:After analyzing and studying data mining algorithms, there are great flaws in Apriori-like algorithm based on candidate sets, the algorithm needs multiple scanning, produces lots of candidate sets, and has low efficiency when mining low support threshold, long rules. This paper introduces a new algorithm PS which optimizes association rules mining. Experimental results show the algorithm is effective.

Key words:data mining;association rules

Apriori算法[1-3]是关联规则中最常被使用的方法，但其有些缺点：1)寻找频繁项目集时，会产生大量侯选项目集2)需要多次扫描数据库3)当最小支持度改变时，需要重新挖掘。以后虽有许多研究针对此点做改进，但大都没有跳出Apriori算法的整体框架，包括前面提出的AprioriMend算法。在此提出一个新的挖掘算法PS（Power Set），它将完全脱离Apriori算法的框架结构。

PS算法是一个执行效率快而且平稳的关联规则挖掘算法，它含有以下特性：只需要扫描数据库一次，从而可以大大降低I/O存取的时间；算法结构简单清晰；可以实现先发现各个项目集合，然后用户在输入最小支持度，增加挖掘的弹性，即用户可以任意改变最小支持度，而无须重新扫描整个数据库；执行效率平稳，不会随着支持度的变动，而影响其执行效率；可以运用在增量式挖掘；不需要进行数据库的前期处理。

1 几个相关概念

定义1：幂集合PS（A）：对于任意一个非空集合A，它的幂集合PS（A）就是由A的全部子集组成的集合。例如非空集合A={a,b,c}，则它的幂集合PS（A）={{φ}，{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。

定义2：对任意事务数据库D，I={i1,i2……im}，liuzy01.tif ，则D中包含X的事务数量称为X在D中的频度，简称为X的频度。

定义3：对于任意集合A={u1,u2,u3,……，ui}，其中所含元素的个数称之为该集合的长度，记作Length(A)。

2 PS算法描述

PS算法主要的运作规则相当快速简单，主要步骤：在读取事务数据库D中的每一条交易记录时，直接以该笔记录的商品项目本身拆解，也就是直接求出该交易记录所对应的集合的所有子集（除空集外），例如，ABC为此笔交易记录，可以拆解出ABC、AB、AC、BC、A、B、C七个子集，接着将这些子集依据集合长度存放在不同的结果表中并做计数动作，如果此集合已经存在于对应的结果表中，则将该集合的计数值加1；如果不存在，则将该集合加入其中，并设置初始值为1。完成以上动作后，此笔交易记录的拆解才算结束。所以当扫描事务数据库D一次以后，即表示所有的交易记录都拆解完成。最后，只需等待使用者输入最小支持度和最小置信度，就可以产生频繁项目集和关联规则，算法伪代码如下：

PS算法

输入：事务数据库D

输出：所有项目集

（1） scan D;

（2） Result_Table RT; //RT的个数由D中的所有项目总数确定

（3） Forall transaction t contains D do begin

（4） AnalysisElements(transcaton t);//求出一条交易记录的所有子集

（5） Forall item i do// i代表某交易记录的某个子集

（6） m =length(i)

（7） If ( i contains RTm)

（8） i.count++;

（9） Else

（10） Add i to RTm;

（11） i.count=1;

（12） End

（13） End

3 PS算法中交易记录拆解过程

为了便于后面分析，在此先描述一下相关概念。

定义4：事务数据库中所有项目组成的集合称为数据库的项目集，记为大写字母I，则I={i1,i2……,im}，│I│=m,其中m为事务数据库中所含项目的总数。

定义5：事务数据库D：所有事务的集合，相当于事务数据库中的记录集合，每个事务T由I中的若干项组成，是I的子集，用唯一的TID来标识。

规定1：对于集合I={i1,i2……im}，规定一个m位的二进制串L（p1,p2,……,pn）与之对应，该位串第一位p1 对应i1, 该位串第二位p2 对应i2，依次类推。

规定2：m位的二进制串l（p1,p2,……,pn）是集合X在I中的对应二进制串，X I，如果pk=1,则ik∈I是其集合X中的元素，反之，如果pk=0,则ik不是集合X中的元素。

定理1：对于任意一个非空集合A={a1，a2，……，an}，则由其可产生的所有子集（空集除外）个数为2n-1。例如非空集合A={a,b,c}，则它的所有子集个数为23-1=7。它们分别为{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。

下面说明PS算法中交易记录的拆解过程。设有如下一条交易记录t={A，B，C}，它所生成的子集为{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。根据规定1和规定2来重新描述t和它所生成的子集，见表1。

表1 t和它所生成的子集对应二进制和十进制描述表

从上述表格中,可以看到一个由三个元素组成的集合，它的所有子集共有7个（23-1=7）这些子集如果用二进制串所对应的十进制数表示的话，依次为1、2、3、4、5、6、7，即分别为1到7之间的整数值。依据上述发现，可以使用如下方法快速生成一个集合的所有子集。假如有一条交易记录t={B，C}，依次读入t中的每一个元素，并将其存入临时一维数组M中，等到t读入完毕之后，就可以得到t的长度和数组M（其中M[1]=B，M[2]=C），从而进一步得知t所产生的所有子集个数为3（22-1=3），这些子集如果用二进制串所对应的十进制数表示的话，依次为1，2，3。然后将1、2、3分别转换为两位二进制（因为t的长度为2），分别为01、10、11。先取出某一子集所对应的二进制串“01”，找出“1”在“01”所处的位置，结果发现只有2号位，于是用从数组M中取出相应的数组元素M[2]中的值代表该子集，即C。接下来取出“10”，找出“1”在“10”所处的位置，结果发现只有1号位，于是用从数组M中取出相应的数组元素M[1]中的值代表该子集，即B。最后取出“11”，找出“1”在“11”所处的位置，结果发现有1号位和2号位，于是用从数组M中取出相应的数组元素M[1]和M[2]中的值代表该子集，即BC。

4 PS算法完整实例说明

第一步：载入数据库中的交易记录，如表2，其中TID是顾客交易编号，Itemset为顾客购买商品项目的交易记录代码明细，D中所含项目总数为4，交易记录总数为5，最长交易记录长度为3。

表2 交易数据库D

第二步：读入第一条交易记录，内容为B和C，此笔交易记录长度为2，申请一个大小为2的临时数组M，将记录中的B、C依次存储在一维数组M中。随即根据3中的方法产生{B}、{C}、{B，C}项目集组合，将{B}、{C}、{B，C}依据长度不同存储于不同的RT（Result Table）中,见图1，此时第一条交易记录处理完毕，此刻释放临时数组M所占用的内存空间。

图1 T1拆解结果图

第三步：判断出数据库D中尚有记录，读取下一条记录，内容为 A、B和C，此条交易记录长度为3，随即产生{A}、{B}、{C}，{A，B}、{A，C}、{B，C}、{A，B，C}。同理将它们存入不同的RT表，结果见图2。

图2 T2拆解结果图

第四步：判断出数据库D中尚有记录，读取下一条记录，内容为 A和C，此条交易记录长度为2，随即产生{A}、{C}和{A，C}。同理将它们存入不同的RT表。

第五步：判断出数据库D中尚有记录，读取下一条记录，内容为D，此条交易记录长度为1，随即产生{D}，同理将它存入RT1表中。

第六步：判断出数据库D中尚有记录，读取下一条记录，内容为A和D，此条交易记录长度为2，随即产生{A}、{D}、{A，D}，同理将它们依次存入RT表中。

图3 所有记录拆解完成后的结果示意图

第七步：判断没有任何交易记录，此时最终的RT表形成，见图3，等待用户输入最小支持度。

第八步：假如此刻用户输入最小支持度为40%（5*40%=2）和最小置信度为80%，然后根据使用者所设定的最小支持度产生频繁项目集，见表3。

表3 生成的频繁项集统计表

第九步：利用频繁项目集以及使用者设定的最小置信度80%，来产生符合使用者需求的关联规则，见表4。

表4 生成的关联规则表

5 PS算法与Apriori算法比较

PS算法与Apriori算法最主要的不同点如下：对于交易记录的处理，是直接由数据库中的第一条记录开始依次往下处理到最后一条记录，将交易数据的出现次数直接求和，支持度和置信度的计算由整个数据库记录数和项目集个别计算，不需要反复扫描数据库以求得各个阶层项目集的相关信息。

对于新增的记录而言，也不需要重新扫描整个数据库，仅需要对新增的记录加以处理，然后连接之前处理过的记录资料，即可对所有的项集进行计算支持度。假设数据库中的交易有N条记录，而所有交易的记录中全部有L个项目，新增的交易有m条记录，N远大于m；一般以Apriori算法为主的算法必须在每次新增记录的时候，重新扫描包含新增记录的全部数据库记录，而PS算法则仅仅只对新增记录做处理，再连接原来的资料即可。假如计算一般算法的时间复杂度的公式表示为Ω（L2（N+m）），则对PS算法的时间复杂度而言，就可以表示为θ（N+m）。从这两个公式可看出，类似Apriori的各个算法在数据库中记录数量越多时，其花费的时间复杂度会随着数据量L的大小做指数的增加，而由于PS算法处理记录的方式为单条记录处理，所以时间复杂度不会随着整体记录量的变化而有所变动，且PS算法的处理时间在记录增加时即时处理，也无须花费一段额外的数据预处理时间，图4为Apriori算法和PS算法对于每次新增记录时的处理所耗费时间的比较示意图，虚线部分为节省扫描数据库的时间成本，从中可明显看出PS算法在新增记录时比Apriori算法节省许多重复搜索记录的时间，但是PS算法在存储的空间上，却会花费比Apriori算法大上数倍的存储空间，所以PS算法是一种以存储空间换取挖掘时间的方式。

图4 Apriori和PS新增记录时处理所耗费时间比较示意图

6 算法的实现与比较

为了验证PS算法的可行性和执行效率，进行了一系列对比实验。实验环境为windows Server 2003，硬件为Intel Pentium Processor 1.70GHz和256MB内存，PS算法用Microsoft VB6.0实现，用来实验的数据库是由IBM generator产生。

表5PS算法与Apriori算法在不同支持度下的效率比较（单位：秒）

由表5可看出当最小支持度越高，商品出现在交易中的次数需要越大，所以找出的频繁项目集就相对的减少；而当支持度变低时，商品出现在交易中的次数则需要越少，故挖掘出的频繁项目集就会增多，当然需要花费的时间也增加。Apriori算法在支持度递增的情况下，对于测试数据库所花费的运行时间就相应变少。PS算法是在先不输入最小支持度的前提下进行挖掘，等到挖掘结束后再根据使用者确定的最小支持度找出频繁项目集，所以PS算法不会随着支持度大小的改变，影响整体执行效率。因此PS算法在各种支持度下，整体执行效率优于Apriori算法。

7 PS算法的限制

PS算法的主要操作是拆解每条交易记录以生成对应的项目集组合，故随着交易记录长度的增加，拆解时间会急剧增加，所以PS算法适用于挖掘那些最长记录长度较小，记录数适量的中小规模数据库。

参考文献

[1]Jiawei Han,Micheline Kamber.Data Mining Concepts and Techniques[M].Morgan Kaufmann Publishers,2000.

[2]David J Hand,Heikki Mannila,Padhraic Smyth.Principles of Data Mining (Adaptive Computation and Machine Learning)[M].MIT Press,2001.

[3]T Hastie,R Tibshirani,J H Friedma.The Elements of Statistical Learning[M].Springer Verlag,2001.

[4]Ian H Eibe Frank.Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[M].Morgan Kaufmann,1999.

[5][Eb/OL].

收稿日期：2008-03-26

作者简介：刘芝怡（1977-），女，讲师，硕士，研究方向：数据挖掘、数据仓库技术、网络开发。