Apriori算法研究

《Apriori算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、Apriori算法研究Apriori算法是一個(gè)挖掘關(guān)聯(lián)規(guī)則的算法，是Agrawal等設(shè)計(jì)的一個(gè)基本算法。它采用兩階段挖掘的思想，并且基于多次掃描事務(wù)數(shù)據(jù)庫(kù)來(lái)執(zhí)行。1.關(guān)聯(lián)規(guī)則1.1.基本概念關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)涵式，表示通過(guò)X可以推導(dǎo)“得到”Y，其中X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)(antecedent或left-hand-side,LHS)和后繼(consequent或right-hand-side,RHS)。關(guān)聯(lián)規(guī)則A->B的支持度support=P(AB)，指的是事件A和事件B同時(shí)發(fā)生的概率。置信度confidence=P(B

2、A)=P(AB)

3、/P(A),指的是發(fā)生事件A的基礎(chǔ)上發(fā)生事件B的概率。同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則。如果事件A中包含k個(gè)元素，那么稱這個(gè)事件A為k項(xiàng)集，并且事件A滿足最小支持度閾值的事件稱為頻繁k項(xiàng)集。1.2.挖掘過(guò)程第一，找出所有的頻繁項(xiàng)集；其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集。第二，由頻繁項(xiàng)集產(chǎn)生強(qiáng)規(guī)則。其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱為強(qiáng)規(guī)則。通常，頻繁項(xiàng)集產(chǎn)生的計(jì)算開(kāi)銷遠(yuǎn)大于產(chǎn)生規(guī)則所需的計(jì)算開(kāi)銷。2.Apriori算法思想Apriori算法使用頻繁項(xiàng)集的先驗(yàn)知識(shí)，使用一種

4、稱作逐層搜索的迭代方法，k項(xiàng)集用于探索(k+1)項(xiàng)集。首先，通過(guò)掃描事務(wù)（交易）記錄，找出所有的頻繁1項(xiàng)集，該集合記做L1，然后利用L1找頻繁2項(xiàng)集的集合L2，L2找L3，如此下去，直到不能再找到任何頻繁k項(xiàng)集。最后再在所有的頻繁集中找出強(qiáng)規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。其中，Apriori算法具有這樣一條性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。因?yàn)榧偃鏟(I)<最小支持度閾值，當(dāng)有元素A添加到I中時(shí)，結(jié)果項(xiàng)集（A∩I）不可能比I出現(xiàn)次數(shù)更多。因此A∩I也不是頻繁的。該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的

5、最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則，其中每一條規(guī)則的右部只有一項(xiàng)，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來(lái)。為了生成所有頻集，使用了遞歸的方法。1.Apriori算法步驟Apriori算法的設(shè)計(jì)可以分解為兩步驟來(lái)執(zhí)行挖掘：1.2.3.3.1.挖掘所有頻繁項(xiàng)集從事務(wù)數(shù)據(jù)庫(kù)（D）中挖掘出所有頻繁項(xiàng)集。支持度大于最小支持度minSup的項(xiàng)集（Itemset）稱為頻集（FrequentI

6、temset)。首先需要挖掘出頻繁1-項(xiàng)集；然后，繼續(xù)采用遞推的方式來(lái)挖掘頻繁k-項(xiàng)集（k>1），具體做法是：在挖掘出候選頻繁k-項(xiàng)集（Ck）之后，根據(jù)最小置信度minSup來(lái)篩選，得到頻繁k-項(xiàng)集。最后合并全部的頻繁k-項(xiàng)集（k>0）。挖掘頻繁項(xiàng)集的算法描述如下：算法Apriori算法的頻繁集產(chǎn)生1:L1=find_frequent_1-itemsets(D);//挖掘頻繁1-項(xiàng)集，比較容易2:for(k=2;Lk-1≠Φ;k++){3:Ck=apriori_gen(Lk-1,min_sup);//調(diào)用apriori_gen方法生成候選頻繁k-項(xiàng)集

7、4:foreachtransactiont∈D{//掃描事務(wù)數(shù)據(jù)庫(kù)D5:Ct=subset(Ck,t);6:foreachcandidatec∈Ct7:c.count++;//統(tǒng)計(jì)候選頻繁k-項(xiàng)集的計(jì)數(shù)8:}9:Lk={c∈Ck

8、c.count≥min_sup}//滿足最小支持度的k-項(xiàng)集即為頻繁k-項(xiàng)集10:}11:returnL=∪kLk;//合并頻繁k-項(xiàng)集（k>0）Apriori算法的頻繁項(xiàng)集產(chǎn)生的部分有兩個(gè)重要的特點(diǎn)：第一，它是一個(gè)逐層算法，即從頻繁1-項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍歷項(xiàng)集格中的一層；第二，它使用產(chǎn)生-測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集

9、。在每次迭代之后，新的候選項(xiàng)集都由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對(duì)每個(gè)候選的支持度進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次數(shù)是kmax+1，其中kmax是頻繁項(xiàng)集的最大長(zhǎng)度。3.2.挖掘頻繁關(guān)聯(lián)規(guī)則基于第1步挖掘到的頻繁項(xiàng)集，繼續(xù)挖掘出全部的頻繁關(guān)聯(lián)規(guī)則。置信度大于給定最小置信度minConf的關(guān)聯(lián)規(guī)則稱為頻繁關(guān)聯(lián)規(guī)則（FrequentAssociationRule）。在這一步，首先需要從頻繁項(xiàng)集入手，首先挖掘出全部的關(guān)聯(lián)規(guī)則（或者稱候選關(guān)聯(lián)規(guī)則），然后根據(jù)minConf來(lái)得到頻繁關(guān)聯(lián)規(guī)則。挖掘頻繁關(guān)聯(lián)規(guī)則的算法描述如下：算法挖

10、掘頻繁關(guān)聯(lián)規(guī)則1:初始狀態(tài)：L=∪kLk;AR=Φ;//L是頻繁項(xiàng)集集合，AR是頻繁關(guān)聯(lián)規(guī)則集合2:fora