大數(shù)據(jù)經(jīng)典算法Apriori講解

1、nApriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法nApriori算法利用頻繁項集性質(zhì)的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。n先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。APRIORI算法nApriori算法利用的是Apriori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。n模式不可能比A更頻繁的出現(xiàn)nApriori算法是反單調(diào)的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。nA

2、priori性質(zhì)通過減少搜索空間，來提高頻繁項集逐層產(chǎn)生的效率算法應(yīng)用n經(jīng)典的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法Apriori 算法廣泛應(yīng)用于各種領(lǐng)域，通過對數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行了分析和挖掘，挖掘出的這些信息在決策制定過程中具有重要的參考價值。nApriori算法廣泛應(yīng)用于商業(yè)中，應(yīng)用于消費(fèi)市場價格分析中，它能夠很快的求出各種產(chǎn)品之間的價格關(guān)系和它們之間的影響。通過數(shù)據(jù)挖掘，市場商人可以瞄準(zhǔn)目標(biāo)客戶，采用個人股票行市、最新信息、特殊的市場推廣活動或其他一些特殊的信息手段，從而極大地減少廣告預(yù)算和增加收入。百貨商場、超市和一些老字型大小的零售店也在進(jìn)行數(shù)據(jù)挖掘，以便猜測這些年來顧客的消費(fèi)習(xí)慣。nApriori算法

3、應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，比如時候入侵檢測技術(shù)中。早期中大型的電腦系統(tǒng)中都收集審計信息來建立跟蹤檔，這些審計跟蹤的目的多是為了性能測試或計費(fèi)，因此對攻擊檢測提供的有用信息比較少。它通過模式的學(xué)習(xí)和訓(xùn)練可以發(fā)現(xiàn)網(wǎng)絡(luò)用戶的異常行為模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘結(jié)果規(guī)則，是網(wǎng)絡(luò)入侵檢測系統(tǒng)可以快速的發(fā)現(xiàn)用戶的行為模式，能夠快速的鎖定攻擊者，提高了基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)的檢測性。nApriori算法應(yīng)用于高校管理中。隨著高校貧困生人數(shù)的不斷增加，學(xué)校管理部門資助工作難度也越加增大。針對這一現(xiàn)象，提出一種基于數(shù)據(jù)挖掘算法的解決方法。將關(guān)聯(lián)規(guī)則的Apriori算法應(yīng)用到貧

4、困助學(xué)體系中，并且針對經(jīng)典Apriori挖掘算法存在的不足進(jìn)行改進(jìn)，先將事務(wù)數(shù)據(jù)庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態(tài)的分配內(nèi)存進(jìn)行存儲，再利用向量求與運(yùn)算，尋找頻繁項集。實驗結(jié)果表明，改進(jìn)后的Apriori算法在運(yùn)行效率上有了很大的提升，挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作。算法思想n該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)

5、則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞歸的方法。 算法實現(xiàn)Apriori算法利用頻繁項集性質(zhì)的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。nApriori算法由連接和剪枝兩個步驟組成。n連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選k項集記為Ck。nLk-1中的兩個元素L1和

6、L2可以執(zhí)行連接操作 的條件是nCk是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度來得到Lk 。n為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll n算法：Apriori。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項集。n輸入：nD:實物數(shù)據(jù)庫；nMin_sup:最小支持度計數(shù)閾值。n輸出：L：D中的頻繁項集。n方法：nL1=fin

7、d_frequent_1-itemsets(D);nfor(k=2;Lk-1 !=；k+)nCk=apriori_gen(Lk-1);nFor each 事務(wù) tD/掃描D用于計數(shù)nCt=subset(Ck,t);/得到t的子集，它們是候選nfor each候選cC;nC.count+;nnLk=cC|c.count=min_stpnnreturn L=UkLk；Apriori偽代碼nProcedure apriori_gen(Lk-1:frequent(k-1)-itemsets)nfor each項集l1Lk-1nfor each項集l2Lk-1nIf (l11=l21) (l12=l22

8、) (l1k-2=l2k-2) (l1k-1=l2k-1) thennc=l1l2/連接步：產(chǎn)生候選nif has_infrequent_subset(c,Lk-1)thenndelete c;/剪枝部；刪除非頻繁的候選nelse add c to Ck；nnreturn Ck；nprocedure has_infrequent_subset (c:candidate k-itemset;nLk-1：frequent (k-1)-itemset)/使用先驗知識nfor each(k-1)-subset s of cnIf s Lk-1thennreturn TRUE;nreturn FALSE

9、;Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetA,B,CB, C, EItemsetsupB, C, E2n1 . 連接：nC3=L2 L2= A,C,B,C,B,

10、EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,En2使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：nA,B,C的2項子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個選項；nA,C,E的2項子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以刪除這個選項；nB,C,E的2項子集是B,C,B,E,C,E，它的所有2項子集都是L2的元素，因此保留這個選項。n3這樣，剪枝后得到C3=B,C,E從以上的算法執(zhí)行過程可以看到Apriori算法的缺點:第一:在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)

11、生的組合過多， 沒有排除不應(yīng)該參與組合的元素;第二:每次計算項集的支持度時，都對數(shù)據(jù)庫D中的全部 記錄進(jìn)行了一遍掃描比較，如果是一個大型的數(shù)據(jù) 庫的話，這種掃描比較會大大增加計算機(jī)系統(tǒng)的 I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加 呈現(xiàn)出幾何級數(shù)的增加。 因此人們開始尋求一種能減少這種系統(tǒng)1/O開銷的更為快捷的算法。Apriori算法的缺點改進(jìn)Apriori算法的方法n方法1：基于hash表的項集計數(shù)n將每個項集通過相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過將桶中的項集技術(shù)跟最小支持計數(shù)相比較先淘汰一部分項集。n方法2：事務(wù)壓縮（壓縮進(jìn)一步迭代的事務(wù)數(shù)）n不包含任何k-

12、項集的事務(wù)不可能包含任何(k+1)-項集，這種事務(wù)在下一步的計算中可以加上標(biāo)記或刪除。n方法3：劃分n挖掘頻繁項集只需要兩次數(shù)據(jù)掃描nD中的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。n第一次掃描：將數(shù)據(jù)劃分為多個部分并找到局部頻繁項集n第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集。n方法4：選樣（在給定數(shù)據(jù)的一個子集挖掘）n基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式n通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式n可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式

13、n可以通過第二此全局掃描來找到遺漏的模式n方法5：動態(tài)項集計數(shù)n在掃描的不同點添加候選項集，這樣，如果一個候選項集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算方法4：選樣（在給定數(shù)據(jù)的一個子集挖掘）基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式可以通過第二此全局掃描來找到遺漏的模式方法5：動態(tài)項集計數(shù)在掃描的不同點添加候選項集，這樣，如果一個候選項集已經(jīng)滿足

14、最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算一種Apriori的改進(jìn)算法實現(xiàn)在Apriori算法中，尋找最大項目集的基本思路是:第一步:簡單統(tǒng)計所有含一個元素的項目出現(xiàn)的頻率，并找出那些大于或等于最小支持度的項目集，產(chǎn)生一維頻繁項目集Lt。第二步:循環(huán)處理直到未能再產(chǎn)生維數(shù)更高的頻繁項目集。 循環(huán)過程是:在第k步中，根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集，由于在產(chǎn)生k-1維頻繁項目集時，我們可以實現(xiàn)對該集中出現(xiàn)元素的個數(shù)進(jìn)行計數(shù)處理，因此對某元素而言，若它的計數(shù)個數(shù)不到k-1的話，可以事先刪除該元素，從而排除由該元素將引起的大規(guī)格所有組合。第三步：按Apriori算法再檢驗新的K 維頻繁項目集的所有k-1維項目集是否已經(jīng)包含在已經(jīng)求出的K-1維頻繁項目集。若其中有一個沒有包含，則也可刪去該組合，這樣得到一個真正有用的K維頻繁項目集選項目集。第四步：得到了這個候選項目集后，可以對數(shù)據(jù)庫D的每一個事務(wù)tid進(jìn)行掃描，若該事務(wù)中至少含有候選項目集CK中的一員，則保留該項事務(wù)，否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標(biāo)記的事務(wù)記錄對換，并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標(biāo)一記，整個數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫D 中。一種Aprio