关联规则挖掘中改进型Ｄｉｆｆｓｅｔｓ算法

　　摘 要：频繁项集挖掘是关联规则挖掘中至关重要的一步。对于稠密数据集的频繁项集挖掘，传统的挖掘算法往往产生大量无用的中间结果，造成内存利用率的极大浪费，尤其是在支持度较低的情况下。Diffsets算法通过引入“差集”的概念，在一定程度上解决了挖掘过程中产生的大量中间结果与内存容量之间的矛盾。改进型Diffsets算法是在原算法的基础上，在差集运算过程中根据差集中所包含的事务标识个数进行递减排序，进一步减少了挖掘过程中产生的中间结果数量。分析与实例表明，改进后的算法在执行过程中将占用更少的内存空间，加快了算法的收敛速度。
　　关键词：数据挖掘；关联规则挖掘；频繁项集挖掘；Diffsets
　　中图分类号：TP311文献标识码：B
　　文章编号：1004-373X(2008)22-080-04
　　
　　Improved Diffsets Algorithm in Association Rules Mining
　　SUN Zhichang,FENG Zuhong
　　(Institute of Computer Science and Engineering,North Nationality University,Yinchuan,750021,China)
　　Abstract：Mining frequent items is a key step in association rules mining.As to the mining frequent items of dense datasets,the traditional mining algorithm always turn out a great deal of useless intermediate results which occupies a large proportion of the memory,especially in a low values of support.Diffsets algorithm introduces the conception of differences,and to some extent,it provides a solution of dealing with the contradiction between those multi-intermediate results and the memory capacity.This improved Diffsets algorithm on the basis of original algorithm ranks the number of tids in a degressive way during the the calculation course,in this way,the amount of intermidiate results can be decreased.The analysis and examples show that this imporved algorithm takes less memory space in the operation process and accelerates the convergence pace of the algorithm.
　　Keywords：data mining;association rules mining;mining frequent items;Diffsets
　　
　　1 引 言
　　
　　在过去的数十年中，人们收集数据的能力迅速提高。许多商务、科学和行政事务的计算机化，特别是万维网的流行，已经将人们淹没在数据和信息的海洋中。存贮数据的爆炸性增长已激发对新技术和自动工具的需求，以便帮助人们将海量数据转换成信息和知识。关联规则挖掘就是按企业既定的业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的商业规律，且进一步将其模式化的数据处理方法。它的最大特点是能够建立预测模型，预测未来的情况。目前，关联规则挖掘技术在各种类型的风险分析、资信评估、医疗诊断决策和市场开发等诸多领域得到了应用。以关联规则挖掘技术为基础的信用卡分析市场规模已超过2 000亿美元。
　　关联规则挖掘通常分解为2个主要的子任务：一是频繁项集的产生，其目标是发现满足最小支持度阈值的所有项集；二是规则的产生，其目标是从上一步发现的频繁项集中提取所有高置信度的规则^［1］。通常，频繁项集产生所需要的计算开销远远大于规则产生所需的计算开销。
　　传统的频繁项集挖掘算法大多采用水平数据格式来存储项集与事务集，如经典的Apriori^［2］算法。DepthProject ^［3］和MaxMiner^［4］算法也利用这种格式来进行最大频繁项集的挖掘。后来人们又提出许多性能优异的垂直挖掘算法。对于稠密数据集，如中国移动的通话记录，Diffsets^［5］算法表现出良好的性能。Diffsets算法较好地解决了交集计算产生的中间结果与内存容量之间的矛盾。它只保留了候选项之间不同的事务标识号，这种方法极大地减少了中间结果对内存的需求量。本文通过对Diffsets算法的改进，进一步减少了中间计算结果，进而提高了算法的整体性能。
　　
　　2 Diffsets算法介绍
　　
　　2.1 关联规则挖掘介绍
　　关联规则反映的是一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么其中一个事物就能够通过对其他事物的预测而得到。典型的关联规则问题是对超市中的购物篮数据进行分析，通过发现顾客所购不同商品之间的关系来分析顾客的购买习惯。
　　关联规则定义如下：设I={i1,i2,…,im}为所有项目的集合，D为事务数据库，T={t1,t2,…tn}是所有事务的集合。每个事务ti包含的项集都是I的子集。每一个事务都具有惟一的事务标识TID。包含0个或多个项的集合被称为项集，如果一个项集包含k个项，则称它为k-项集。项集A在事务数据库D中出现的次数占D中总事务数的百分比叫作项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集。关联规则是形如XY的逻辑蕴含式，其中XI，YI，且X∩Y=。如果事务数据库D中有s%的事务包含X∪Y，则称关联规则XY的支持度为s%。实际上，支持度是一个联合概率值。若项集X的支持度记为support(X)，规则的置信度为support(X∪Y)/support(X)。这是一个条件概率P(Y|X)。也就是：support(XY)=P(X∪Y)，confidence(XY)=P(Y| X)。关联规则挖掘就是找出支持度和置信度分别满足用户给定阈值的规则。例如数据库中有5个不同的项，I={A,C,D,T,W}，6个事务T={1,2,3,4,5,6}，如图1所示。表的右侧列出了在最小支持度为50%时，产生的19个频繁项集。关联规则挖掘过程主要分为频繁项集的产生和规则的产生，其中频繁项集产生所需的计算开销远远大于规则产生所需的开销。
　　
　　图1 频繁项集挖掘
　　图2列举了关联规则挖掘中事务数据库常用的数据表示格式。在传统的水平数据表示格式中，每个事务对应的项集都存在惟一的事务标识。而垂直数据标出的是各项在事务中出现的位置，Eclat^［6］、Charm^［7］和Partion^［8］等算法都是利用此种格式进行数据挖掘。
　　图2 常用数据表示格式
　　垂直挖掘向对于以前水平挖掘有很多优势，其中最大的优势在于它可以只用交集操作就能得到潜在可能的频繁项集。而传统的基于水平数据格式的挖掘算法需要建立复杂的数据结构。还有一些算法(如Viper^［9］)利用压缩的二进制格式来代替事务标识。
　　2.2 垂直数据挖掘与Diffsets算法
　　定义1 等价关系：I为项集，定义函数p，P(I)×N→P(I)，其中p(X,k)=X(1∶K)，k是前缀X的长度。在子集树上定义等价关系θk：X,Y∈P(I)，X≡θkYp(X,k)=p(Y,k)。也就是说，如果两个项集享有共同的k长度前缀，它们就是同一个类。θk被称为基于前缀的等价关系^［10］。
　　等价关系的优势在于它将传统的搜索空间划分为一些独立的子问题，每个带有前缀的分类都可以作为一个新问题来对待。如果确定了某个前缀类是频繁的，就可以递归地扩展出下面所有的频繁项集。如对于给定的以P为前缀的类，［P］={X1,X2,…,Xn}是频繁的，将PXi与所有的Xj进行组合，这样就可以得到下面所有频繁的子集。
　　传统的垂直挖掘算法(如Viper^［9］)是在两个频繁项的事务标识间做交集运算来产生潜在可能的频繁项集。图3展示了一个典型的垂直挖掘过程。事务集A(t(A)={1,3,4,5})，D(t(D)={2,4,5,6})，这时将A和D进行交集运算，得到AD(t(AD)={4,5})。通过支持度计算可知，项集AD不是频繁项集。在对稠密数据集进行挖掘过程中，会产生大量的中间结果，大量的交集操作将需要许多时间。而当结果达到一定数量时，又不得不对这些中间结果进行压缩，把它存储到硬盘上。如果遇到这样的情况，垂直挖掘算法将失去原有的优势。
　　Diffsets的做法是避免存储候选项所在的每个事务标识，它只保留了两个候选项之间的差集。在根部，差集是每个候选项所在的事务标识与整个数据集所包含的事务标识的差集。如项A(t(A)={1,3,4,5})，整个事务的标识T为{1,2,3,4,5,6}，这时Diffsets只存储t(A)与T的差异之处，即{2,6}。通过根部的每个候选项的集合，可以通过计算每两个项之间的差集来得到所有的子节点。
　　图3 典型垂直挖掘过程
　　下面是Diffsets形式化的表示方法：
　　给定一个带有前缀P的类，令t(X)代表项X所在的事务标识，d(X)代表X的差集，定义d(PX)=t(P)-t(X)，也就是用集合P减去集合P与集合X的交集。同样的方法，也可以得到d(PY)。这里首先要注意的是项集的支持度已经不是差集中所包含的项集个数与整个事务数的比值，而是由如下公式来计算：σ(PX)=σ(P)-|d(PX)|，其中σ代表了项集的支持度计数，|d(PX)|代表差集PX所包含事务标识的个数。为了得到σ(PXY)，需递归的进行计算。σ(PXY)=σ(PX)-|d(PXY)|，所以需要计算d(PXY)。
　　根据定义：
　　d(PXY)=t(PX)-t(PY)=t(PX)-t(PY)+
　　t(P)-t(P)
　　=t(P)-t(PY)-(t(P)-t(PX))
　　=d(PY)-d(PX)
　　由上式可知，可以不用t(PX)-t(PY)来计算d(PXY)，而是用d(PY)-d(PX)来计算。
　　下面举例说明在在差集的计算过程。从根部开始，如图4所示，如计算项集AD的支持度。根据定义可以得到：
　　d(AD)=t(A)-t(D)={1,3}，σ(AD)
　　=σ(A)-|d(AD)|=4-2=2
　　由于用户定义的最小支持度为50%，而σ(AD)/6=2/6，小于50%，所以得到AD不是频繁项集。如果以差集计算项集AD的支持度，可以得到d(AD)=d(D)-d(A)={1,3}-{2,6}={1,3}，将和前面得到同样的计算结果。惟一不同的是对于稠密数据集，如果初始就用差集表示将会占用更少的内存空间。再用差集来计算AC的支持度。d(AC)=d(C)-d(A)=-{2,6}=，σ(AC)=σ(A)-|d(AC)|=4-0=4，σ(AC)/6=4/6，大于50%，所以项集AC是频繁的。
　　图4 Diffsets挖掘过程
　　在图3中整个数据集需要23个事务标识来表示，而在图4中差集只需要7个事务标识。基于交集运算的垂直挖掘过程共产生76个事务标识，而基于差集的运算只产生22个事务标识。由此可以看出，对于稠密数据集，Diffsets算法在一定程度上减少了挖掘过程中产生的中间结果。
　　
　　3 Diffsets算法进一步改进
　　
　　3.1 Diffsets算法改进的思想
　　在稠密数据集中，差集表示法在一定程度上减少了内存中需要存储的事务标识的个数。但是可以通过对算法的改进，使挖掘过程中产生的结果更少。
　　改进算法描述如下：
　　(1) 计算原始各项差集；
　　(2) 对于输入集数据，根据差集中所包含的事务标识个数按降序进行排列；
　　(3) 进行正常的差集运算；
　　(4) 当下一层潜在的频繁项集全部产生后，在内存中删除当前层；
　　(5) 返回步骤2，直到产生所有的频繁项集。
　　差集的定义是d(PX)=d(X)-d(P)，假如用短的事务标识集减去长的事务标识集，就可能得到较短的差集。上例中，d(CD)=d(D)-d(C)={1,3}-={1,3}，而d(DC)=d(C)-d(D)=-{1,3}=，从而在内存中需存储的事务标识将更少。所以这里的做法是对每次的输入集根据它们所包含的事务数长短进行递减排序，这样通过差集计算得到的下一层的差集将包含更少的事务标识。证明如下：
　　令：|D(A)|=Am,|D(B)|=Bn
　　 Am　　 |D(A)∩D(B)|=t≤min{Am,Bn}
　　有：
　　|D(A)-D(B)|=|D(A)-D(A)∩D(B)|
　　=Am-t
　　|D(B)-D(A)|=|D(B)-D(A)∩D(B)|
　　=Bn-t
　　∵ Am　　∴ Am-t　　∴ |D(A)-D(B)|<|D(B)-D(A)|
　　证毕
　　3.2 算法改进的伪码及其应用举例
　　程序的输入集是可以产生子节点的一组类成员P。首先对这组类成员P按它们所包含的事务数长短进行递减排序，然后通过计算所有项集对之间的差集和检查这些差集的支持度，就可以得到所有的频繁项集。这个过程递归的进行调用，就可以得到当前层可能产生的所有频繁项集。在内存中，只需要保存2层事务标识集就可以了，一旦下一层所有潜在的频繁项集都已产生，就可以删除当前层的数据集^［4］。改进算法描述如下：
　　Input P，smin_support；
　　Sort P descending according to Tids′ length；//按它们所包含事务数的长短递减排序
　　
　　for all Xi∈［P］do
　　 for all Xj∈［P］ with j>i do
　　 R={Xi,Xj}；//R为项集Xi和Xj组成的集合
　　 d(R)=d(Xj)-d(Xi)；
　　if σ(R)≥min_support then
　　 Ti=Ti∪{R}；//Ti初始为空集
　　 New P=Ti；
　　Delete P；//删除当前层的数据集
　　Return New P；
　　根据上面的例子来说明算法改进后的优势，如图5所示。原来的Diffsets在频繁项集的挖掘过程中共产生22个事务标识，而改进后的算法在挖掘过程中只产生了14个事务标识。可以看出算法在改进后，在挖掘过程中产生的事务标识数减少了1/3左右。上例中，如果事先没有对项集的事务标识列表进行排序，那么d(T)将在d(C)之后，d(T)-d(C)将得到包含2个项的事务标识列表，而排序后得到的结果为空集。这表明算法改进后不但节省了更多的存储空间，还加快了算法的收敛速度。
　　图5 改进后的Diffsets挖掘过程
　　
　　4 结 语
　　
　　传统的垂直挖掘算法是通过对两个项所包含的事务标识进行交集操作来发现潜在的频繁项集。对于稠密数据集，其致命的弱点是交集操作可能产生大量的非频繁项集。这不但需要花费大量的计算时间，而且当中间结果达到一定数量时，不得不对它们进行压缩，然后存储到硬盘上。这将失去垂直挖掘算法原有的优势。Diffsets算法通过利用差集，极大地减少了中间结果的数量。本文提出一种改进型Diffsets算法，又进一步减少了挖掘过程中产生的事务标识数量。通过数学证明和与原文例子的比较，展示了算法改进后的优势。
　　
　　参考文献
　　［1］PangNing Tan,Michael Steinbach,Vipin Kumar.数据挖掘导论［M］.北京:人民邮电出版社,2006.
　　［2］Agrawal R,Mannila H,Srikant R,et al.Fast Discovery of Association Rules［J］.Advances in Knowledge Discovery and Data Mining,AAAI Press,Menlo Park,CA,1996:307-328.
　　［3］Rakesh C Agrawal,Charu C Aggarwal,Prasad V V V.Depth First Generation of Long Patterns［J］.In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000),2000:108-118.
　　［4］Bayardo R J.Efficiently Mining Long Patterns from Databases Proc［C］.1998 ACM-SIGMOD Int′l Conf.Management of Data (SIGMOD ′98),1998:85-93.
　　［5］Zaki M J,Gouda K.Fast Vertical Mining Using Diffsets［Z］.In Proc.of ACM SIGKDD′03.Washington,DC:2003.
　　［6］Zaki M J.Scalable Algorithms for Association Mining［J］.IEEE Transactions on Knowledge and Data Engineering,2000,12(3):372-390.
　　［7］Zaki M J.Generating Non-redundant Association Rules［C］.In 6th ACM SIGKDD Int′l Conf.Knowledge Discovery and Data Mining,2000.
　　［8］Omiecinsky E,Sarasere A,Navathe S.An Efficient Algorithm for Mining Association Rules in Large Databases［J］.In Proc.of the 21st VLDB Conference,Zurich,Switzerland,1995:432-444.
　　［9］Shenoy P,Haritsa J R,Sudarshan S,et al.Turbo-charging Vertical Mining of Large Databases［C］.In ACM SIGMOD Intl.Conf.Management of Data,2000.
　　［10］Zaki M J.Scalable Algorithms for Association Mining［J］.IEEE Transactions on Knowledge and Data Engineering,2000,12(3):372-390.
　　［11］陈莉平,屈百达.基于关联规则的数据挖掘算法的研究与应用.现代电子技术,2007,30(20):71-74.
　　
　　作者简介
　　孙志长 男，1982年出生，辽宁人，硕士研究生。主要研究方向为数据挖掘和分布式计算。
　　冯祖洪 男，1956年出生，江苏人，教授，硕士生导师。
　　
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文