Apriori算法的研究与实现

2016-05-18皖南医学院教务处安徽芜湖241002

赤峰学院学报·自然科学版 2016年8期

关键词：Apriori算法不足性质

牛　猛（皖南医学院　教务处，安徽　芜湖　241002）

Apriori算法的研究与实现

牛猛
（皖南医学院教务处，安徽芜湖241002）

摘要：Apriori算法是关联规则中最常见的一种算法.本文简要介绍了Apriori算法的概念、基本思想与实现过程，阐述了Apriori算法的性质与步骤，并用实例演示了算法的详细过程，最后总结了Apriori算法的特点与不足之处.

关键词：Apriori算法；性质；步骤；特点；不足

基金资助：安徽省高校人文社会科学研究项目(SK2016A0953）名称：大数据视阈下基于社交网络的大学生心理健康预测与信息系统构建

0　Apriori算法的概念

Apriori算法是最有影响力的关联规则算法，是使用逐层搜索的迭代方法，找到频繁项集，挖掘关联规则的单维、单层的宽度优先算法.

1　Apriori算法的基本思想

是在生成候选项集的基础上，通过逐层扫描数据库并进行计数，从候选项集中找到频繁项集的过程[1].

2　Apriori算法的实现过程

Apriori算法的具体实现过程是：首先对数据库中所有的事务进行扫描，根据事务中每项的出现次数计算出1项的候选集C1，然后按照事先确定的最小支持度min_sup，从候选集C1中确定频繁1-项集的集合L1；然后在L1的基础上，通过进行L1^L1连接运算生成2项的候选集C2,再次对数据库中所有的事务进行扫描，通过计算得到候选集C2中每项的出现次数，再按照之前的最小支持度min_sup，从候选集C2中确定频繁2-项集的集合L2；然后在L2的基础上，通过进行L2^L2连接运算生成3项的候选集C3,再扫描数据库中的所有事务，计算候选集C3中每项的出现次数，再根据最小支持度min_sup，从候选集C3中确定频繁3-项集的集合L3；以此循环，生成出L4、L5、L6……直到仍能够生成频繁k-项集的集合Lk，但却不能够再生成满足min_sup的k+1项目集.对于j项候选集Cj(j=3,4,5,……,k)，若其中某元素的(j-1)子集不是(j-1)频繁集，将被删除掉.

3　Apriori算法的性质

3.1频繁项集的所有的非空子集均为频繁项集

频繁项集是向下封闭的，即若一个项集满足最小支持度的要求，则此项集的所有非空子集也都满足最小支持度的要求.

3.2非频繁项集的所有超集均为非频繁项集

Apriori性质满足反单调性，即若项集K是不频繁的，即P(K)＜min_sup，则将项A添加到项集K后形成的结果项集(A∪K)也一定是不频繁的，即P(A∪K)＜min_sup.

4　Apriori算法的步骤

4.1 Apriori算法的步骤

①扫描所有事务，产生候选1-项集的集合C1；②根据min_sup，由C1产生频繁1-项集的集合L1；③设k=1；④对Lk执行连接步和剪枝步，产生候选(k+1)-项集的集合Ck+1；⑤根据最小支持度min_sup，由Ck+1产生频繁(k+1)-项集的集合Lk+1；⑥若Lk+1≠Ø，则k=k+1，然后进入步骤④，否则进入步骤⑦；⑦根据min_conf，由频繁项集产生强关联规则.

4.2 Apriori算法的步骤说明

Apriori算法最重要的两个步骤是通过候选项集确定频繁项集以及通过频繁项集产生关联规则.

4.2.1通过候选项集确定频繁项集

在通过候选项集确定频繁项集的过程中，如何通过频繁k-项集Lk确定频繁(k+1)-项集Lk+1是Apriori算法的核心.使用Apriori算法的性质能够压缩搜索空间，提高生成频繁项集的效率[2].由频繁k-项集确定频繁(k+1)-项集，分为连接步和剪枝步：

连接步：在Lk-1的基础上，采用递推的方法，通过Lk-1与自己进行连接从而产生候选k-项集[3]的集合Ck.

剪枝步：Ck是Lk的超集，即Ck中包含频繁项集和非频繁项集.若Ck中包含大量的项集，则所需的计算量就会非常大.

使用Apriori算法的性质来删除非频繁的候选项集，从而减少扫描事物数据库的次数，进而大大提高算法的效率.

4.2.2通过频繁项集产生关联规则

在所有的频繁项集确定之后，就可以根据min_sup和min_conf确定强关联规则.即当Support(X⇒Y)≥min_sup成立，同时Confidence(X⇒Y)≥min_conf成立，那么称X⇒Y为强关联规则；否则称X⇒Y称为弱关联规则.

5　Apriori算法的示例

设有事务数据库D，如表1所示的，其中，D中有9个事务（E1，E2，…E9），并且事务中的项（A，B，C，D，E）均已根据字典次序存放.本例通过运用Apriori算法，探索从事务数据库中挖掘频繁项集的过程.

表1　事物数据库D

5.1算法的第一次迭代：通过第一次扫描D，得到如表2所示的1-项候选项集的集合C1.

表2　1-项候选项集的集合C1

5.2假设最小事务支持计数为2，即min_sup=2/9=0.22，可在C1的基础上确定支持度大于或等于min_sup的频繁1-项集的集合L1，如表3所示.

表3　1-项频繁项集的集合L1

5.3算法的第二次迭代：为探索2-项频繁项集L2，算法采用L1X L1（L1自身连接）产生如表4所示的2-项候选项集C2.

5.4第二次扫描D，计算出C2中每个候选项集的支持计数，再根据min_sup确定L2，如表5所示.

表4　2-项候选项集的集合C2

表5　2-项频繁项集的集合L2

5.5算法的第三次迭代：为探索L3，算法采用L2X L2（L2自身连接）产生C3，C3={{A,B,C},{A,B,E},{A,C,E},{B,C,D},{B,C, E},{B,D,E}}.根据Apriori算法的性质，确定{A,C,E}、{B,C,D}、{B,C,E}、{B,D,E}这4个候选项集不是频繁的，故从C3中删除将这4个非频繁候选项集（剪枝），然在通过扫描D来确定L3时，就无需再计算他们的计数值，因此就得到删除非频繁项集的C3，如表6所示.

表6　3-项候选项集的集合C3

5.6第三次扫描D，计算出C3中每个候选项集的支持计数，再根据min_sup确定L3，如表7所示.

表7　3-项频繁项集的集合L3

5.7算法的第四次迭代：为探索L4，算法采用L3X L3（L3自身连接）产生C4，C4={A,B,C,E}.根据Apriori算法的性质，因其子集{B,C,E}不是频繁的，确定{A,B,C,E}不是频繁的，故将其从C4中删除（剪枝），则C4=Ø，此时所有的频繁项集均被找到，同时算法结束.

5.8根据频繁项集，生成关联规则

在挖掘出所有的频繁项集后，可生成关联规则，其步骤如下：

①对任何一个频繁项集L，确定L的所有非空子集.

②对L的任何一个非空子集s，若满足support_count(L) /support_count(s)≥min_conf，则输出形如“s⇒(L-s)”的关联规则，其中min_conf为最小置信度阀值.

在本例中，设频繁项集L={A,B,E}，则L的非空子集为{A,B}、{A,E}、{B,E}、{A}、{B}和{E}，则可得到如下关联规则：

①A∧B⇒E,confidence=2/4=0.5

②A∧E⇒B,confidence=2/2=1

③B∧E⇒A,confidence=2/2=1

④A⇒B∧E,confidence=2/6=0.33

⑤B⇒A∧E,confidence=2/7=0.29

⑥E⇒A∧B,confidence=2/2=1

若设min_conf为0.5，则可得到如下强关联规则：

①A∧B⇒E,confidence=2/4=0.5

②A∧E⇒B,confidence=2/2=1

③B∧E⇒A,confidence=2/2=1

④E⇒A∧B,confidence=2/2=1

若设min_conf为0.6，则可得到如下强关联规则：

①A∧E⇒B,confidence=2/2=1

②B∧E⇒A,confidence=2/2=1

③E⇒A∧B,confidence=2/2=1

6　Apriori算法的特点

6.1 Apriori算法具有非常好的可伸缩性，尤其在处理离散数据时效果非常好，由于采用逐层搜索的迭代算法，无需复杂的理论证明，简单且易于实现[4].

6.2 Apriori算法是一个逐层搜索的迭代算法：该算法通过循环扫描事物数据库，直到仍能够生成频繁k-项集的集合Lk，但却不能够再生成满足min_sup的k+1项目集.Apriori算法最终会生成大于或等于最小支持度的所有频繁项集.

6.3 Apriori算法是适合处理事务数据库的关联规则挖掘算法，通常采用形如{事务编号(TID),项目集(I)}的水平方式组织数据[5].

6.4利用Apriori的性质对算法进行了优化，删除了非频繁项集，提高了算法的效率.

6.5 Apriori算法通常只适合于频繁项集的长度稍小的稀疏数据集.

7　Apriori算法的不足之处

7.1 Apriori算法对事物数据库的扫描次数过多[6].在Apriori算法中，每生成一个候选项集Ck，都要对事物数据库进行一次全面的扫描；并且在每个循环中，在需要对数据存取确认时（如从Ck到Ct时）也都需要扫描事物数据库.当事务数据非常大时，系统的I/O负载就会非常大，导致扫描数据库的时间会很长，这样大大降低了算法的效率.

7.2 Apriori算法通常在计算过程中会产生大量的侯选项集[7].在apriori_gen(Lk-1,min_sup)函数中，当Lk-1中的项集通过连接步操作生成候选k-项集时，生成的候选项集数量会呈几何级数增加.

7.3当频繁项集的长度增加的时候，运算的时间就会明显增加[8].Apriori算法是在事务数据库中来计算频繁项集的支持度，因为频繁项集的长度增加，即频繁项集所包含项目的数目增加，因此在确定每个事务是否包含每个频繁项集的时间也会增大，在相同的事务数据库中，频繁项集长度增加时，所需的运算时间会明显增加.

7.4 Apriori算法采用统一的最小支持度.Apriori算法没有考虑不同事物以及事物不同属性的不同的实际情况，没有针对不同事物及事物的不同属性分别给出不同的加权值来确定最小支持度.

7.5 Apriori算法是属于单维、单层、布尔关联规则的挖掘算法.其适应范围较窄，只能进行单维、单层、布尔关联规则的挖掘.对现实中大量存在的多维、多层、量化型数据的挖掘问题，该算法就不再适用，需对其进行改进或者采用别的算法.

参考文献：

〔1〕王媛媛,胡学钢.关联规则挖掘研究[C].全国第16届计算机科学与技术应用(CACIS)学术会议论文集,2004.808-812.

〔2〕蔡伟杰,张晓辉,朱建秋,等.关联规则挖掘综述[J].计算机工程,2001,27(5):31-33.

〔3〕续蕾.关联规则Apriori算法实际应用解析[J].电脑知识与技术,2008,3(5):862-864.

〔4〕钱冬云.数据挖掘中关联规则算法的研究[D].天津大学，2006.

〔5〕周文秀.关联规则挖掘算法的研究与改进[D].武汉理工大学,2008.

〔6〕李杰.数据挖掘技术在学生成绩分析中的应用研究[D].西安石油大学,2010.

〔7〕兰天.关联规则数据挖掘方法的研究与实现[D].西安科技大学,2008.

〔8〕刘芝怡.关联规则挖掘算法的分析、优化及应用[D].苏州大学,2007.

收稿日期：2015-12-25