尹士闪，马增强，毛晚堆

（1.石家庄铁道大学 教务处，河北 石家庄050043；2.石家庄铁道大学 电气与电子工程学院，河北 石家庄050043；3.石家庄铁道大学 工程训练中心，河北 石家庄050043）

0 引 言

数据挖掘 （data mining）是一门交叉学科，是从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有兴趣知识的过程。关联规则挖掘则是数据挖掘中最活跃的研究方法之一［1－3］。Agrawal等于1993年首先提出了关联规则问题，随后他们建立了项目集格空间理论，提出了著名的Apriori算法［4－14］。Apriori其核心算法就是根据频集理论的一种逐层迭代搜索方法，通过项目集元素数目不断增长来逐步完成频繁项目集的发现。算法过程中需要多次扫描事务数据库，并产生庞大的候选集来完成频繁项目集的发现，如此大的候选集对时间和存储空间都是一种挑战。针对Apriori算法的这些缺点，近年来，许多学者对此提出了许多不同的算法。比较典型算法有DHP，Partition，Sampling，FP－tree。在这些研究基础之上，本文提出了一个有效生成频繁项目集的算法，它是采用一种链式存储结构用来存储频繁项目集，并生成最大频繁项目集，通过改变事务的存储方式和增加链式存储方式能够高效的生成最大频繁项目集，避免了多次扫描事务数据库，减少了庞大的候选集的生成，从而提高了效率。

1 关联规则基本概念及理论

定义1（项目） 关联规则挖掘的数据集记作D（D为事务数据库），D＝ ｛t1，t2，…，tn｝，tk＝ ｛i1，i2，…，ij｝（k＝1，2，…，n）为一条事务；tk中的元素ij（j＝1，2，…，p）称为项目 （Item）。

定义2（项目集） 设I＝ ｛i1，i2，…，im｝是事务数据库D中全体项目组成的集合，I的任何子集X称为D的项目集 （Itemset），｜X｜＝k称集合X为k项目集。设tk和X分别为D中的事务和项目集，如果X tk，称事务tk包含项目集X。

定义3（规则的支持度） 事务数据库D中包含项目集X的事务数称为项目集X的支持数，记为δx。项目集X的支持率，记作：Support（X），即概率P（X），support（X）＝δx/｜D｜×100%。

定义4（规则的可信度） 规则A→B具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P（B/A）。

定义5（频繁项目集） 如果一个k－项目集，它的支持度≥minsup（最小支持度），则称该k－项目集为频繁k－项目集。

定义6（最大频繁项目集） 如果一项目集X是频繁的，并且不存在任意项目集Y（XY），使得Y是事务集D的频繁项目集，则称项目集X为事务集D的最大频繁项目集。

由以上的定义可以看出，任何频繁项目集都是某一最大频繁项目集的子集，最大频繁项目集包含所有频繁项目集，且项目集的规模要小几个数量级，所以可以把发现频繁项目集的问题转化为发现最大频繁项目集的问题。

理论1 如果X是频繁项目集，那么X的任何非空子集都是频繁项目集。

理论2 如果X是非频繁项目集，那么X的任何超集都是非频繁项目集。

2 关联规则算法的基本思想

为了便于本文关联规则算法的论述，把基于频繁项目集链式存储方法的关联规则算法简称为CSSFI算法。

2.1 Apriori的基本思想

Apriori算法所采用的是逐层迭代搜索方法，通过项目集元素数目不断增长来逐步完成频繁项目集发现的。首先产生1－频繁项目集L1，然后是2－频繁项目集L2，直到频繁项目集为空时算法停止。在第k次循环中，过程先产生k－1－候选项目集的集合Ck－1，然后通过扫描数据库生成支持度并测试产生k－频繁项目集Lk。每次找出一个Lk，就需要扫描数据库一次。

在第一遍扫描中，计算单个项目的支持度，确定哪些项目是频繁项目，即它们需具有最小支持度。在后来的扫描中，均将前一次扫描得到的频繁项目作为基础项目，利用这个基础项目产生出新的频繁项目集，这样的频繁项目集称作候选项目集，并且在扫描数据的过程中计算这些候选项目集的实际支持度计数。扫描结束后，确定哪些候选项目集才是真正的频繁项目，然后将是频繁项目的这些候选项目集作为下一次扫描用的基础项目。重复此过程直到没有新的频繁项目集产生为止。

2.2 CSSFI算法的基本思想

CSSFI算法主要针对Apriori算法中的两点不足进行改进，这两点不足如下：

（1）多次扫描事务数据库，需要很大的I/O负载：对每次k循环，候选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如一个频繁大项目集包含10个项，那么就至少需要扫描事务数据库10遍。

（2）产生庞大的过渡候选项目集：由Lk－1产生k－候选集Ck是指数增长的，例如104个1－频繁项目集就有可能产生接近107个元素的2－候选项目集。如此大的候选集对时间和主存空间都是一种挑战。

CSSFI算法通过改变事务数据库中事务的存储方式，采用链式存储结构来存储频繁项目集，并生成最大频繁项目集，通过这种方法能够减小扫描事物数据库的次数和生成候选集的数量，克服了Apriori算法的瓶颈，从而减少了生成最大频繁项目集的时间，提高了算法的效率。

3 CSSFI算法的实现过程

生成最大频繁项目集算法共分3步，分别为：①变更事务数据库存储和表达方式，初始化存储链表，生成项目集和频繁1－项目集；②构造频繁项目集链表；③根据频繁项目集的定义及性质，对候选项目集链表进行处理，生成最大频繁项目集。

3.1 初始化阶段

把事务数据库中的事务转化成比特向量表达方式。即，在一个事物中出现第i个项目，则把对应项目的比特向量置为1，否则置为0。例如，项目集I＝ ｛A，B，C，D，E，F｝，事务数据库 T＝ ｛（ADE）， （BCD）， （ABCD），（BEF）｝，转化为比特向量表达式为 T＝ ｛（100110），（011100），（11110）， （010011）｝，同时，生成有序1―项目集，计算各个项目的支持度，按支持度从大到小进行排序，假设最小支持度为2，则生成频繁1―项目集为I1＝｛（B，3），（D，3），（A，2），（C，2），（E，2），（F，1）｝，把最小主持度小于2的都去掉，实际上，频繁1―项目集为I1＝ ｛（B，3），（D，3），（A，2），（C，2），（E，2）｝，如表1为事务数据库，表2为频繁1―项目集。

表1 事务数据库

表2 频繁1―项目集

3.2 构造频繁项目集链表

经过初始化阶段之后，进入构造频繁项目集链表阶段。具体方法为：扫描一遍事务数据库T，选取频繁项目集中支持度最小的频繁项目，如果事务中包含此频繁项目，则将此事务作为链表信息加入到该频繁项目对应的链表中，否则检查是否包含支持度较小的频繁项目，如果包含，将此事务加入到此频繁项目对应的链表中，以此类推，直到遍历整个事务数据库结束。在把事务加入到该频繁项目对应的链表的同时，把该事务中包含其他频繁项目出现次数加1。如图1是频繁项目集初始链表结构。

图1 频繁项目集初始链表结构

3.3 生成最大频繁项目集

设最大频繁项目集M为空，从支持度最小的频繁项目链表出发，检查除此频繁项目以外其它频繁项目出现的次数，如果他们出现的次数都大于或等于此频繁项目的支持数，则把这些频繁项目 （包含此支持度最小的频繁项目）进行组合，生成所有频繁项目集并加入到最大频繁项目集M中，程序结束；否则将那些出现次数大于或等于最小支持度的频繁项目 （包含此支持度最小的频繁项目）组合生成频繁项目集，同时加入频繁项目集M中，然后，对支持度最小的频繁项目链表进行处理，即把项目集链表中所有事务对应此频繁项目的比特向量置为0，对处理后的事务，按照构造频繁项目集链表的方法分别插入到其它的频繁项目集链表中；以此类推进行循环，直到程序结束，生成最大频繁项目集M。

例如，从事务数据库T中生成所有最小支持度为2的最大频繁项目集，首先从支持度最小的频繁项目E开始，频繁项目集E的链表中包含两个事务 （100110）和（010011），而其他频繁项目C、A、D、B出现的次数为0，1，1，1，没有频繁项目出现的次数和E的支持度相同，支持度也小于minsup（最小支持度），不能生成频繁项目集。接着从事务 （100110）和 （010011）中去掉E项目，变为（100100）和 （010001），然后按照生成频繁项目集链表的方法，将他们插入到频繁项目C、A、D、B链表中，这样包含较小支持度C的事务为 （01100）和 （111100），频繁项目A、D、B出现的次数为1，2，2，D和B与C出现的次数相同，但另外一个项目的支持度小于minsup，因此生成频繁项目集 ｛（C、D），（C、B），（D、B），（C、D、B）｝，按同样的方法生成频繁项目集 ｛（A、D）｝，最后合并生成最大频繁项目集 ｛（A、D），（C、D），（C、B），（D、B），（C、D、B）｝，具体过程如下：

（1）处理支持度最小的频繁项目E（见图2）。

图2 处理频繁项目E链表

（2）处理支持度较小的频繁项目C（见图3）。

图3 处理频繁项目C链表

生成频繁项目集 ｛（C、D）， （C、B）， （D、B）， （C、D、B）｝。

（3）处理的频繁项目A （见图4）。

图4 处理频繁项目A 链表

生成频繁项目集 ｛（A、D）｝，程序结束。

最后生成最大频繁项目集 ｛（A、D）， （C、D）， （C、B），（D、B），（C、D、B）｝。

3.4 算法的程序实现

本算法采用类语言的方式进行了描述，具体程序如下：

/＊变量说明部分＊/

N：事务数据库中事务总数；

M：项目数；

minsup：最小支持度；

I［M］：存储项目集；

L［］：频繁项目集链表；

max＿fi［］［］：存储最大频繁项目集

L［］struct

｛

item ［］ char［］//频繁项目名称

item＿sup ［］ int［］//对应item在此链表事务中出现的次数

tran［］ char［］//存储包含此频繁项目的事务，链表

L＿leng［］ int //链表长度

｝//L ［0］为频繁1－项目集

T ［］：事务数据库

/＊初始化阶段：把事务用比特向量方式存储＊/

For（j＝1；j＜＝N；j＋＋）do

begin

Begin

While i＜＝M do

begin

i＋＋；

if I ［i］∈T ［j］then b ［i］＝1；I ［i］.

count＋＋；//count为项目I［i］的支持度

else b ［i］＝0

end

T ［j］＝b；/＊b以比特向量方式存储T ［j］＊/

end

/＊生成频繁1－项目集＊/

for all I ［i］do begin

if I［i］.count＞＝minsup then

L ［0］.item ［j］［1］＝I［i］；

L ［0］.item＿sup ［j］［1］＝I［i］.count；j＋＋；

else i＋＋

end

L ［0］＝sort（L ［0］）/＊把频繁1－项目集进行排序，按支持度的大小从小到大进行排序，支持度相同时按字典顺序进行排序＊/

/＊构造频繁项目集链表＊/

L ［1］＝L ［0］

For（i＝1；i＜＝N；i＋＋）do

begin

for j＝1to｜L ［1］.item ［］［1］｜j＋＋do

begin

if L ［1］.item ［j］［1］∈T ［i］then begin

/＊把包含此频繁项目的事务加入到对应的链表中＊/

L［1］.tran ［j］［］＝ L［1］.tran ［j］［］∪T ［i］；

L［1］.L＿sup ［j］［1］＋＋；//把对应的item＿sup ［j］＋1

Insert（L ［1］.item ［j］，T ［i］）/＊把 T［i］中其他项目加入到L ［1］.item ［j］中，同时把对应的item＿sup ［j］［2，3，4，…］＋1＊/

end

end

end

/＊生成最大频繁项目集＊/

C［］：临时存储频繁项目集

While（遍历L1，k＝1，k＜＝｜L ［1］｜）

Begin

temp＿i＝L ［1］.item＿sup ［k］［1］

c ［1］＝L ［1］.item ［k］［1］

/＊选出此频繁项目链表中其他项目出现次数大于等于此频繁项目支持度的项目＊/

For i＝2to i＜＝｜L ［1］.item｜do

begin

if L ［1］.item＿sup ［k］［i］＞＝temp＿i then

Begin

c＝c∪L ［1］.Item ［k］［i］

end

end

delete （L ［1］.tan ［k］，c ［1］）//删除此链表事务中此频繁项目

max＿fi［k］＝Combination （c）//把c中项目进行任意组合，结果加入最大频繁项目集max＿fi中；

if temp＿i＞＝｜c｜ then begin break；//程序结束

else insert（L ［1］，L ［1］.tan ［k］）//把删除此频繁项目的事务加入到其他频繁项目链表中，再进行最大频繁项目集的搜寻

end end

4 实验结果及分析

本文使用Intel（R）Core（TM）2duo CPU 2.93GHz，2.0GB内存的微机，对Apriori算法和DHP算法及CSSFI算法在产生候选集数量和运行时间上进行了对比实验，所用数据集来源于UCI机器学习数据库［15］，共10个数据集，如表3所示。

表3 数据集

当最小支持度为0.5时，表4，表5表示产生的候选集数量和运行时间对比表。

表4 3种算法产生的候选集数

实验结果表明，在10个测试数据集中，CSSFI算法在集中的7个数据集上产生的候选集数量少于其它两种算法，在其中的7个数据集上运行时间地狱其它两种算法，这是由于CSSFI算法产生的候选集有大幅度的减少的结果。当最大频繁项目集的项目数越大时，CSSFI算法的效率显得越突出。

表5 3种算法的运行时间

5 结束语

本文提出了一种基于频繁项目集链式存储方法的关联规则算法 （CSSFI），该算法采用比特向量方式存储事务和建立频繁项目集链表，通过处理频繁项目集链表生成最大频繁项目集，并用类语言对算法进行了程序实现。从和Apriori算法和DHP算法的比较结果来看，CSSFI算法的效率得到了很大的提高，从而证明了CSSFI算法是可行的、有效的。在对CSSFI算法的仔细分析和研究基础上，发现该算法在数据库容量扩容时，性能有所下降，这是在以后的研究中需要继续探讨的问题。

［1］CHEN Wenwei.The data warehouse and data mining ［M］.Beijing：Tsinghua University Press，2006：143－155 （in Chinese）.［陈文伟.数据仓库与数据挖掘教程 ［M］.北京：清华大学出版社，2006：143－155.］

［2］MAO Guojun.Data mining：Principle and algorithm ［M］.Beijing：Tsinghua University Press，2005：5－6 （in Chinese）.［毛国君.数据挖掘原理与算法 ［M］.北京：清华大学出版社，2005：5－6.］

［3］ZHANG Ke，ZHANG Xiaogang.Data mining algorithm and engineering application ［M］.Beijing：Mechanical Industry Press，2006：50－61 （in Chinese）.［章兢，张小刚.数据挖掘算法及其工程应用 ［M］.北京：机械工业出版社，2006：50－61.］

［4］DUAN Yang－guang，WEI Yu－ke.Algorithm for mining frequent patterns based on circular orthogonal linked list ［J］.Computer Technology and Development，2009，19 （10）：73－77（in Chinese）.［段仰广，伟玉科.基于循环十字链表的频繁模式挖掘算法 ［J］.计算机技术与发展，2009，19 （10）：73－77.］

［5］ZHANG Guanglu，LEI Jingsheng.An improved Apriori algorithm for mining association rules ［J］.Computer Technology and Development，2010，20 （6）：84－92 （in Chinese）.［张广路，雷景生.一种改进的Apriori关联规则挖掘算法 ［J］.计算机技术与发展，2010，20 （6）：84－92.］

［6］WANG Hua，HU Xuegang.Mining algorithm of maximal frequent itemsets suitable to specific database ［J］.Computer Engineering，2008，34 （14）：63－65 （in Chinese）.［王华，胡学钢.特定数据最大频繁集挖掘算法 ［J］.计算机工程，2008，34 （14）：63－65.］

［7］PAN Yi－ting，HANG Hong－juan.An improved maximal frequent itemsets mining algorithm ［J］.Computer Engineering and Science，2009，31 （8）：63－65 （in Chinese）. ［潘益婷，张红娟.一种改进的最大频繁项目集挖掘算法 ［J］.计算机工程与科学，2009，31 （8）：63－65.］

［8］YANG Yu，WANG Yong.Optimized method for mining maximum frequent itemsets ［J］.Computer Engineering and Applications，2006，42 （31）：171－173 （in Chinese）. ［唐瑜，王勇.挖掘最大频繁项集的优化方法 ［J］.计算机工程与应用，2006，42 （31）：171－173.］

［9］SHANG Zhigang，YIN Shaohong.Research of mining maximum frequent itemsets based on dynamic programming ［J］.Computer ＆ Digital Engineering，2009，37 （10）：51－54 （in Chinese）.［尚志刚，尹绍宏.基于动态规划的最大频繁项目集挖掘研 究 ［J］.计算机 与 数 字 工 程，2009，37 （10）：51－54.］

［10］ZHU Ye，YE Gaoying.Improvement of Apriori algorithm in association rule mining ［J］.Modern Electronic Technique，2008，31 （18）：78－80 （in Chinese）. ［朱烨，叶高英.关联规则挖掘Apriori算法的改进 ［J］.现代电子技术，2008，31（18）：78－80.］

［11］QIU Chang－chun.On the association rules of 1wining algorithm containing item constraint ［J］.Journal of Hubei Institute of Education，2006，23 （8）：21－23 （in Chinese）. ［邱长春.基于项目约束的关联规则挖掘方法的研究 ［J］.湖北教育学院学报，2006，23 （8）：21－23.］

［12］ MA Li－sheng.Fast algorithm for mining frequent itemsets［J］.Computer Engineering and Design，2009，30 （8）：1903－1906（in Chinese）.［马丽生.快速挖掘频繁项目集算法［J］.计算机工程与设计，2009，30 （8）：1903－1906.］

［13］LI Yun，LI Qing－shan.Algorithm for mining constrained maximal frequent itemsets ［J］.Computer Engineering and Applications，2007，43 （17）：160－163 （in Chinese）. ［李芸，李青山.基于约束的最大频繁项集挖掘算法 ［J］.计算机工程与应用，2007，43 （17）：160－163.］

［14］FENG Feng.A Fast Updating Alogrithm for mining maximum frequent itemsets［J］.Journal of Hefei University，2007，17（4）：46－49 （in Chinese）.［冯凤.快速更新挖掘最大频繁项集 ［J］.合肥学院学报，2007，17 （4）：46－49.］

［15］David Aha.UCI Machine learning repository：Center for machine learning and intelligent systems ［DB］.http：//archive.ics.uci.edu/ml/datasets.html，2010.