论文部分内容阅读
摘要：如何在海量的数据中，挖掘其中隐藏的、人们感兴趣的知识，已经成为了一个研究的热点。Apriori算法是目前使用最为广泛的关联规则挖掘算法，本文就其算法实现的流程以及具体的实现进行研究。
关键词：数据挖掘；关联规则挖掘；Apriori算法
中图分类号：TP309 文献标识码：A 文章编号：1007-9599 (2011) 23-0000-02
Apriori Association Rule Mining Algorithm
Nan Zhihai,Sun Yong
(School of Computer Science&Technology,Soochow University,Suzhou 215006,China)
Abstract:How to vast amounts of data,mining the hidden,people are interested in knowledge,has become a research hotspot.Apriori algorithm is the most widely used association rule mining algorithm,this algorithm on the implementation process and the specific study.
Keywords:Data mining;Association rule mining;Apriori algorithm
一、数据挖掘技术概述
随着信息技术的发展，信息量呈爆炸式增长。在大量的数据面前，“无用”的信息量远远超过了“有用”信息量，使用手工的方式在海量的数据里面寻找所需要的信息已经不再现实。在这种“数据爆炸，知识贫乏”的背景下，数据量的不断增长，大大降低了数据检索的效率。因此，数据挖掘作为在海量的数据中发现有价值知识的工具，得到了广泛的关注和应用。例如“尿布与啤酒”的例子就是数据挖掘应用的经典案例。目前，数据挖掘以其优越性，已经在各行各业中得到了广泛的应用，同时也进一步促进了数据挖掘技术的发展。
数据挖掘的目的就是从大量数据中发现有用的模式。模式表示数据之间的关联关系，是预测数据变化、进行数据分类的标准。各种模式为用户提供了各种各样的数据挖掘途径，用户可以根据不同的具体情况来使用不同的模式挖掘数据中有用的知识。在现实应用中，模式常被划分成如下几种类型：
（一）关联模式
关联模式通过对数据出现的频率进行统计，从而分析数据中各元素的关联程度，即关联模式表示了数据之间潜在的联系，从而挖掘其中隐含的关系。
（二）分类模式
分类模式是将海量的数据进行分类，将数据库中的数据映射到一个分类中，从而对这个数据进行标记。例如判定树、神经网络以及数学公式等都是比较常见的分类模型。
（三）聚类模式
聚类模式即识别数据的内资规则，将具有同类关联内在规则的数据划分到同一个簇中。使得聚类中粗之间的区别尽可能大，而簇内元素的差别尽可能小。聚类模式与分类模式相似，其区别在于：聚类模式在划分过程中，来确定簇的数量和半径；而在分类模式中，在数据映射之间就确定了分类的定义。
（四）时序模式
时序模式指将原有的数据在时间轴上进行排序，并且根据这些数据基于时间的变化，来预测未来的发展趋势。
二、Apriori算法流程分析
Agrawal等在1994年提出使用Apriori算法对顾客交易的数据库项之间的关联规则进行挖掘的方法。基于这种方法分成以下两部分来完成：
（1）首先，找出数据库中所有出现频率比最小支持度大或者相等的频繁项集；
（2）然后，根据所得到的频繁项集来制定强关联规则，同时这些强关联规则必须要满足最小可信度以及最小支持度这两个基本的条件。
从上面方法实现的两个部分可以看出，Apriori算法的实现分成以下两个步骤：
（1）首先使用迭代方法对数据集中的所有项集进行扫描，并且设定一个支持度阈值，筛选出数据集中的所有频繁项集，即将支持度低于阈值的项集全部淘汰掉，而将支持度高于这个阈值的项集认为是频繁项集。
（2）对上一步迭代所得到的频繁项集的置信度进行计算，从而获取真正的规则。
具体实现的方法如下：
首先，将数据集中所有的1阶项集全部找出来，并且根据一个预先设定的支持度阈值来找出这些1阶项集中的频繁项集，并且将频繁项集记为L1；
然后，根据上一步所计算出来的1阶频繁项集计算出2阶候选集C2，同样通过与最小支持度的比较，得到2阶频繁项集，记为L2；
不断的重复，直到根据Lk-1所生成的候选Ck中的所有项集支持度都小于阈值位置，即不再有更长的频繁项集出现为止。
在这个不断重复的过程中，经历了“连接”和“剪枝”两个部分。
（一）连接
连接指的是不断的由Li频繁项集生成Ci+1候选集的过程。由于Ci+1候选集是通过Li频繁项两两不断连接所形成的，因此，Ci+1候选集中元素的个数会呈指数倍增长，为了将其中一些无用的数据去除掉，就需要对Ci+1候选集进行剪枝。
（二）剪枝
剪枝简单的说就是判断Ci+1候选集中项集的可信度，即出现的频率，一旦这个频率高于某个阈值，则认为该项集是频繁项集，应该计入到频繁项集Li+1中。
下面以一个简单的例子来对Apriori算法的具体实现进行介绍。
在商场中有进行了如表1所示的四笔交易：
表1 事务实例表
编号 1 2 3 4
购买商品 a,b,d,g,i a,b,c,d,e,h,j a,b,c,e,f a,b,d,k
通过这四笔交易，并且设定置信度为60%来查找其中的关联规则。
（1）首先，求出1阶的候选项集为:a,b,c,d,e,f,g,h,I,j,k这11个候选项集在这四笔交易中出现的频率如表2所示：
表2 1阶候选项集及其频繁度
项集 a b c d e f g h i j k
频繁度 100% 100% 50% 75% 50% 25% 25% 25% 25% 25% 25%
（2）根据60%的置信度，得到1阶频繁项集为a,b,d其频繁度分别为100%，100%和75%；
（3）根据1阶频繁项集计算2阶候选项集，并且计算2阶候选项集中所有项的频繁度，如表3所示：
表3 2阶候选项集及其频繁度
项集 a,b a,d b,d
频繁度 100% 75% 75%
（4）根据60%的置信度可知2阶候选项集中的所有项都是频繁项集，为此，在得到2阶频繁项集之后计算3阶候选项集，3阶候选项集中的项及其频繁度如表4所示：
表4 3阶频繁项集及其置信度
项集 a,b,d
频繁度 75%
（5）最终得到的频繁项集为（a,b,d），其频繁度为75%，为此，根据最后得到的频繁项集分析其中的规则，并且找出规则的可信度，如表5所示：
表5 规则及其置信度
规则 置信度 描述
a→b∩d 75% 买了a商品之后，再买b和d商品的置信度为75%
b→a∩d 75% 买了b商品之后，再买a和d商品的置信度为75%
d→a∩b 100% 买了d商品之后，再买a和b商品的置信度为100%
a∩b →d 75% 买了a和b商品之后，再买d商品的置信度为75%
a∩d →b 100% 买了a和d商品之后，再买b商品的置信度为100%
b∩d →a 100% 买了b和d商品之后，再买a商品的置信度为100%
三、Apriori算法设计与实现
Apriori数据挖掘算法实现的流程如图1所示：
图1 Apriori算法实现流程
第一步：找出事务数据库中的频繁项集
即在对所有已经确认的攻击数据包进行分析，根据如表4-1所示的标准数据包中的属性来确定频繁项集，频繁项集的确定如下所示：
/**其中Lk表示频繁k-项集，Ck表示具有K个数据项的候选项集，D表示整个事务集**/
输入：事务集D，最小支持度阈值min_sup。
输出：事务集D中的频繁项集L。
方法：
L1={large 1-itemsets};//初始产生频繁1-项集的集合
for(k=2,Lk-1不为空;k++)//由频繁k-1项集产生频繁k项集
do
begin
Ck=apriori_get(Lk-1);//调用apriori_gen，算法，由Lk-1产生Ck
for D事务集中所有的事务t
do
begin
Ct=subset(ck,t);//t中所包含的候选
for( Ct中的所有候选c) do c.count++;
end;
Lk={c|c.count>=min_sup};
L=LULk;
end;
return L;
在apriori_gen函数中，主要完成项集的连接和剪枝这两个操作，从而从项集Lk+1中得到Ck。apriori_gen函数的算法描述如下所示：
select p.item1,p.item2,…,p.itemk-1,q.itemk-1//连接
from Lk-1p,Lk-1q
where p.item1= q.item1, p.itemk-2= q.itemk-2, p.itemk-1< q.itemk-2;
for all Ck中的元素c
do //剪枝
for(all (k-1)-subsets s of c
do
if(s不属于Lk-1)
delete c from Ck;
end;
end;
第二步：产生关联规则
在获取了攻击数据包的频繁项集之后，在分析最终频繁项集中的关联规则，并且将获取的关联规则加入到规则数据库中。
根据第一步所获取得到的由频繁项集，再来进行强关联规则的产生则相对的简单。其中强关联规则中的置信度计算公式如公式1所示：
其中，表示为包含了的事务数量，而表示为包含了的事务数量。
关联规则所产生的步骤表示为：
（1）首先对每一个计算所得到的频繁数据集I，得到I所有的非空子集S。
（2）对频繁数据子集I的所有非空子集S进行判断，如果S满足公式2（其中的min_conf为设置的最小信度阈值），则将确定关联规则。
四、总结
关系数据库技术的发展使得数据的存储管理得到了很大的发展，在海量的数据面前，人们意识到其中肯定包含了许多隐藏的知识。而关联规则的挖掘，就是在数据库中发现商品之间隐藏联系的一种方法。通过对大量交易的研究，发现顾客在购买时，一种商品对另外商品的影响，从而可以改善超市的货架设计，以及存储安排。Apriori算法是一种使用最为广泛的关联规则算法，在本文将针对Apriori算法的设计和实现进行了深入的研究。
参考文献：
[1]范明.数据挖掘概念与技术[M].北京:机械工业出版社,2005
[2]陈文伟,黄金才.数据仓库与数据挖掘[M].北京人民邮电出版社,2004
[3]Zaki M J,Parthasarathy S,Li W,et al.Evaluation of sampling for data mining of association rules[A].Proceedings of the 7thInternational Workshop on Research Issues
关键词：数据挖掘；关联规则挖掘；Apriori算法
中图分类号：TP309 文献标识码：A 文章编号：1007-9599 (2011) 23-0000-02
Apriori Association Rule Mining Algorithm
Nan Zhihai,Sun Yong
(School of Computer Science&Technology,Soochow University,Suzhou 215006,China)
Abstract:How to vast amounts of data,mining the hidden,people are interested in knowledge,has become a research hotspot.Apriori algorithm is the most widely used association rule mining algorithm,this algorithm on the implementation process and the specific study.
Keywords:Data mining;Association rule mining;Apriori algorithm
一、数据挖掘技术概述
随着信息技术的发展，信息量呈爆炸式增长。在大量的数据面前，“无用”的信息量远远超过了“有用”信息量，使用手工的方式在海量的数据里面寻找所需要的信息已经不再现实。在这种“数据爆炸，知识贫乏”的背景下，数据量的不断增长，大大降低了数据检索的效率。因此，数据挖掘作为在海量的数据中发现有价值知识的工具，得到了广泛的关注和应用。例如“尿布与啤酒”的例子就是数据挖掘应用的经典案例。目前，数据挖掘以其优越性，已经在各行各业中得到了广泛的应用，同时也进一步促进了数据挖掘技术的发展。
数据挖掘的目的就是从大量数据中发现有用的模式。模式表示数据之间的关联关系，是预测数据变化、进行数据分类的标准。各种模式为用户提供了各种各样的数据挖掘途径，用户可以根据不同的具体情况来使用不同的模式挖掘数据中有用的知识。在现实应用中，模式常被划分成如下几种类型：
（一）关联模式
关联模式通过对数据出现的频率进行统计，从而分析数据中各元素的关联程度，即关联模式表示了数据之间潜在的联系，从而挖掘其中隐含的关系。
（二）分类模式
分类模式是将海量的数据进行分类，将数据库中的数据映射到一个分类中，从而对这个数据进行标记。例如判定树、神经网络以及数学公式等都是比较常见的分类模型。
（三）聚类模式
聚类模式即识别数据的内资规则，将具有同类关联内在规则的数据划分到同一个簇中。使得聚类中粗之间的区别尽可能大，而簇内元素的差别尽可能小。聚类模式与分类模式相似，其区别在于：聚类模式在划分过程中，来确定簇的数量和半径；而在分类模式中，在数据映射之间就确定了分类的定义。
（四）时序模式
时序模式指将原有的数据在时间轴上进行排序，并且根据这些数据基于时间的变化，来预测未来的发展趋势。
二、Apriori算法流程分析
Agrawal等在1994年提出使用Apriori算法对顾客交易的数据库项之间的关联规则进行挖掘的方法。基于这种方法分成以下两部分来完成：
（1）首先，找出数据库中所有出现频率比最小支持度大或者相等的频繁项集；
（2）然后，根据所得到的频繁项集来制定强关联规则，同时这些强关联规则必须要满足最小可信度以及最小支持度这两个基本的条件。
从上面方法实现的两个部分可以看出，Apriori算法的实现分成以下两个步骤：
（1）首先使用迭代方法对数据集中的所有项集进行扫描，并且设定一个支持度阈值，筛选出数据集中的所有频繁项集，即将支持度低于阈值的项集全部淘汰掉，而将支持度高于这个阈值的项集认为是频繁项集。
（2）对上一步迭代所得到的频繁项集的置信度进行计算，从而获取真正的规则。
具体实现的方法如下：
首先，将数据集中所有的1阶项集全部找出来，并且根据一个预先设定的支持度阈值来找出这些1阶项集中的频繁项集，并且将频繁项集记为L1；
然后，根据上一步所计算出来的1阶频繁项集计算出2阶候选集C2，同样通过与最小支持度的比较，得到2阶频繁项集，记为L2；
不断的重复，直到根据Lk-1所生成的候选Ck中的所有项集支持度都小于阈值位置，即不再有更长的频繁项集出现为止。
在这个不断重复的过程中，经历了“连接”和“剪枝”两个部分。
（一）连接
连接指的是不断的由Li频繁项集生成Ci+1候选集的过程。由于Ci+1候选集是通过Li频繁项两两不断连接所形成的，因此，Ci+1候选集中元素的个数会呈指数倍增长，为了将其中一些无用的数据去除掉，就需要对Ci+1候选集进行剪枝。
（二）剪枝
剪枝简单的说就是判断Ci+1候选集中项集的可信度，即出现的频率，一旦这个频率高于某个阈值，则认为该项集是频繁项集，应该计入到频繁项集Li+1中。
下面以一个简单的例子来对Apriori算法的具体实现进行介绍。
在商场中有进行了如表1所示的四笔交易：
表1 事务实例表
编号 1 2 3 4
购买商品 a,b,d,g,i a,b,c,d,e,h,j a,b,c,e,f a,b,d,k
通过这四笔交易，并且设定置信度为60%来查找其中的关联规则。
（1）首先，求出1阶的候选项集为:a,b,c,d,e,f,g,h,I,j,k这11个候选项集在这四笔交易中出现的频率如表2所示：
表2 1阶候选项集及其频繁度
项集 a b c d e f g h i j k
频繁度 100% 100% 50% 75% 50% 25% 25% 25% 25% 25% 25%
（2）根据60%的置信度，得到1阶频繁项集为a,b,d其频繁度分别为100%，100%和75%；
（3）根据1阶频繁项集计算2阶候选项集，并且计算2阶候选项集中所有项的频繁度，如表3所示：
表3 2阶候选项集及其频繁度
项集 a,b a,d b,d
频繁度 100% 75% 75%
（4）根据60%的置信度可知2阶候选项集中的所有项都是频繁项集，为此，在得到2阶频繁项集之后计算3阶候选项集，3阶候选项集中的项及其频繁度如表4所示：
表4 3阶频繁项集及其置信度
项集 a,b,d
频繁度 75%
（5）最终得到的频繁项集为（a,b,d），其频繁度为75%，为此，根据最后得到的频繁项集分析其中的规则，并且找出规则的可信度，如表5所示：
表5 规则及其置信度
规则 置信度 描述
a→b∩d 75% 买了a商品之后，再买b和d商品的置信度为75%
b→a∩d 75% 买了b商品之后，再买a和d商品的置信度为75%
d→a∩b 100% 买了d商品之后，再买a和b商品的置信度为100%
a∩b →d 75% 买了a和b商品之后，再买d商品的置信度为75%
a∩d →b 100% 买了a和d商品之后，再买b商品的置信度为100%
b∩d →a 100% 买了b和d商品之后，再买a商品的置信度为100%
三、Apriori算法设计与实现
Apriori数据挖掘算法实现的流程如图1所示：
图1 Apriori算法实现流程
第一步：找出事务数据库中的频繁项集
即在对所有已经确认的攻击数据包进行分析，根据如表4-1所示的标准数据包中的属性来确定频繁项集，频繁项集的确定如下所示：
/**其中Lk表示频繁k-项集，Ck表示具有K个数据项的候选项集，D表示整个事务集**/
输入：事务集D，最小支持度阈值min_sup。
输出：事务集D中的频繁项集L。
方法：
L1={large 1-itemsets};//初始产生频繁1-项集的集合
for(k=2,Lk-1不为空;k++)//由频繁k-1项集产生频繁k项集
do
begin
Ck=apriori_get(Lk-1);//调用apriori_gen，算法，由Lk-1产生Ck
for D事务集中所有的事务t
do
begin
Ct=subset(ck,t);//t中所包含的候选
for( Ct中的所有候选c) do c.count++;
end;
Lk={c|c.count>=min_sup};
L=LULk;
end;
return L;
在apriori_gen函数中，主要完成项集的连接和剪枝这两个操作，从而从项集Lk+1中得到Ck。apriori_gen函数的算法描述如下所示：
select p.item1,p.item2,…,p.itemk-1,q.itemk-1//连接
from Lk-1p,Lk-1q
where p.item1= q.item1, p.itemk-2= q.itemk-2, p.itemk-1< q.itemk-2;
for all Ck中的元素c
do //剪枝
for(all (k-1)-subsets s of c
do
if(s不属于Lk-1)
delete c from Ck;
end;
end;
第二步：产生关联规则
在获取了攻击数据包的频繁项集之后，在分析最终频繁项集中的关联规则，并且将获取的关联规则加入到规则数据库中。
根据第一步所获取得到的由频繁项集，再来进行强关联规则的产生则相对的简单。其中强关联规则中的置信度计算公式如公式1所示：
其中，表示为包含了的事务数量，而表示为包含了的事务数量。
关联规则所产生的步骤表示为：
（1）首先对每一个计算所得到的频繁数据集I，得到I所有的非空子集S。
（2）对频繁数据子集I的所有非空子集S进行判断，如果S满足公式2（其中的min_conf为设置的最小信度阈值），则将确定关联规则。
四、总结
关系数据库技术的发展使得数据的存储管理得到了很大的发展，在海量的数据面前，人们意识到其中肯定包含了许多隐藏的知识。而关联规则的挖掘，就是在数据库中发现商品之间隐藏联系的一种方法。通过对大量交易的研究，发现顾客在购买时，一种商品对另外商品的影响，从而可以改善超市的货架设计，以及存储安排。Apriori算法是一种使用最为广泛的关联规则算法，在本文将针对Apriori算法的设计和实现进行了深入的研究。
参考文献：
[1]范明.数据挖掘概念与技术[M].北京:机械工业出版社,2005
[2]陈文伟,黄金才.数据仓库与数据挖掘[M].北京人民邮电出版社,2004
[3]Zaki M J,Parthasarathy S,Li W,et al.Evaluation of sampling for data mining of association rules[A].Proceedings of the 7thInternational Workshop on Research Issues