淺談Apriori算法

【摘要】隨著大量數(shù)據(jù)不斷收集和存儲，許多業(yè)界人士對于從他們的數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則越來越感興趣。Apriori算法就是經(jīng)典的關(guān)聯(lián)挖掘算法，文章分析了Apriori的算法思想、算法具體方法及其不足。

【關(guān)鍵詞】數(shù)據(jù)；關(guān)聯(lián)規(guī)則；Apriori算法

一、Apriori算法概述

Apriori算法是一種最有影響力的挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項集的算法，它是由Rakesh Agrawal和Ramakrishnan Skrikant提出的。它使用一種稱作逐層搜索的迭代方法，k-項集用于探索（k+1）-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L2，如此下去，直到不能找到k-項集。每找一個Lk需要一次數(shù)據(jù)庫掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。其運行定理在于一是頻繁項集的所有非空子集都必須也是頻繁的，二是非頻繁項集的所有父集都是非頻繁的。

二、Apriori算法思想

Apriori中提出了一個基于兩階段頻集思想的方法，其核心思想如下：（1）連接步：為找Lk，通過Lk-ι與自己連接產(chǎn)生候選k-項集的集合。該候選項集的集合記作Ck。設I1和I2是Lk-1中的項集。記號Li[j]表示Li的第j項。為方便計，假定事物或項集中的項按字典次序排序。如果它們前（k-2）個項相同，則它們是可連接的。如果：（L■1）=L■1∧（2）=L■2∧…（L■K-2=（L■K-2）∧（L■K-1＜L■k-1），條件L■K-1＜L■k-1是保證不產(chǎn)生重復，則Lk-1中的元素I1和I2是可連接的，結(jié)果項集是I11I12…I1k-1I2k-1。（2）剪枝步：Ck是Lk的超集；即，Ck的成員可能是或可能不是大項集，但所有k-大項集都包含在Ck中。掃描數(shù)據(jù)庫，確定每個侯選集的計數(shù)，計數(shù)值不小于最小支持度的所有侯選集為大項集，從而確定Lk。然而Ck，可能很大，因此要確定侯選計數(shù)的量可能很大。為壓縮Ck，可由性質(zhì)：任何非頻繁（k-1）項集都不可能是k-項集的子集。因此，如果一個侯選k-項集的（k-1）項子集不在Lk-1中，則該侯選項集也不是頻繁的，從而可從Ck中刪除。

三、Apriori算法具體方法

Apriori算法在于Apriori使用根據(jù)候選生成的逐層迭代找出頻繁項集。輸入事物數(shù)據(jù)庫D，最小支持度閡值min_supp；輸出D中的頻繁項集L。方法如下：={large1-itemsets}；for（k=2；Lk-1≠￠；k++）{ Ck=Apriori_gen（Lk-1，min_supp）；//產(chǎn)生侯選集for each transaction t∈D { Ct=subset（Ck，t）；//交易t中包含的侯選集for each candidate c∈Ct c.count++；}//end for t Lk={c∈Ck|c.count≥min_supp}}//end for k ReturnL=∪kLk；Procedure Apriori_gen（Lk-1；frequent（k-1）-itemsets；min_supp）{ for each itemset L1∈Lk-1 for each itemset L2∈Lk-1 if（L■1）=L■1∧（2）=L■2∧…（L■K-2=（L■K-2）∧（L■K-1＜L■k-1）{ c=L1×L2；//連接步 產(chǎn)生侯選集 if has_infrequent_subset（c，） Delete c；//剪枝步 刪除不頻繁侯選else add c to Ck；} RenturenCk } Procedure has_infrequent_subset（c：candidate;k-itemset；Lk-1） { for each（k-1）-sebset s of c if s∈Lk-1 Return True；else Return False；}

四、Apriori算法的不足之處

Apriori首先產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個r值使得Lr為空，這時算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于Lk-1的頻集做連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個子集。Ck中的每個元素需在交易數(shù)據(jù)庫中進行驗證來決定其是否加入Lk，這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個項，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負載，因而挖掘效率很低。其次，該算法使用起來不方便，因為它只讓用戶提供最小支持度和最小可信度，然后將所有滿足條件的關(guān)聯(lián)規(guī)則都挖掘出來，導致結(jié)果集很大，用戶難以理解，需要進行大量的篩選才能抽取有用的規(guī)則。由此可見，關(guān)聯(lián)規(guī)則所采用的算法應注重用戶的參與性，因為不可能簡單的通過把許多數(shù)據(jù)輸入一個“黑匣子”以期望得到有用的知識。同時用戶必須了解所屬領(lǐng)域的背景知識，然后才可選擇感興趣的數(shù)據(jù)集合和模式。因此，關(guān)聯(lián)規(guī)則的任務應該是一個交互式工具而非僅僅是自動分析。

參 考 文獻

[1]朱其祥，徐勇，張林．基于改進Apriori算法的關(guān)聯(lián)規(guī)則挖掘研究[J]．計算機技術(shù)與發(fā)展．2006（7）

[2]李曉虹，尚晉．一種改進的新Apriori算法[J]．計算機科學．2007（4）

[3]文蓉，李仁發(fā)．一種優(yōu)化的Apriori算法[J]．計算機系統(tǒng)應用．2008（1）

[4]頓毅杰．關(guān)聯(lián)規(guī)則挖掘中的Apriori算法淺析[J]．中國科技信息．2009（22）

[5]況莉莉．Apriori算法與FP-tree算法的探討[J]．淮北煤炭師范學院學報（自然科學版）．2010（2）