【摘要】隨著大量數(shù)據(jù)不斷收集和存儲(chǔ)，許多業(yè)界人士對(duì)于從他們的數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則越來(lái)越感興趣。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ī)則的頻繁項(xiàng)集的算法，它是由Rakesh Agrawal和Ramakrishnan Skrikant提出的。它使用一種稱(chēng)作逐層搜索的迭代方法，k-項(xiàng)集用于探索（k+1）-項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合。該集合記作L1。L1用于找頻繁2-項(xiàng)集的集合L2，而L2用于找L2，如此下去，直到不能找到k-項(xiàng)集。每找一個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。為提高頻繁項(xiàng)集逐層產(chǎn)生的效率，一種稱(chēng)作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。其運(yùn)行定理在于一是頻繁項(xiàng)集的所有非空子集都必須也是頻繁的，二是非頻繁項(xiàng)集的所有父集都是非頻繁的。

二、Apriori算法思想

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

三、Apriori算法具體方法

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

參 考 文獻(xiàn)

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

[2]李曉虹，尚晉．一種改進(jìn)的新Apriori算法[J]．計(jì)算機(jī)科學(xué)．2007（4）

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

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

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