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

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

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

3、法應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，比如時(shí)候入侵檢測技術(shù)中。早期中大型的電腦系統(tǒng)中都收集審計(jì)信息來建立跟蹤檔，這些審計(jì)跟蹤的目的多是為了性能測試或計(jì)費(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)的檢測性。 Apriori算法應(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ù)庫映射為一個(gè)布爾矩陣，用一種逐層遞增的思想來動(dòng)態(tài)的分配內(nèi)存進(jìn)行存儲(chǔ)，再利用向量求與運(yùn)算，尋找頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的Apriori算法在運(yùn)行效率上有了很大的提升，挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作。,算法思想,該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則，其中每一條規(guī)則的右部只有一項(xiàng)，這里采用的是

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

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

7、；k+) Ck=apriori_gen(Lk-1); For each 事務(wù) tD/掃描D用于計(jì)數(shù) Ct=subset(Ck,t);/得到t的子集，它們是候選 for each候選cC; C.count+; Lk=cC|c.count=min_stp return L=UkLk；,Apriori偽代碼,Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets) for each項(xiàng)集l1Lk-1 for each項(xiàng)集l2Lk-1 If (l11=l21) (l12=l22) (l1k-2=l2k-2) (l1k-1=l2k-1) then c=l1l2/

8、連接步：產(chǎn)生候選 if has_infrequent_subset(c,Lk-1)then delete c;/剪枝部；刪除非頻繁的候選 else add c to Ck； return Ck； procedure has_infrequent_subset (c:candidate k-itemset; Lk-1：frequent (k-1)-itemset)/使用先驗(yàn)知識 for each(k-1)-subset s of c If s Lk-1then return TRUE; return FALSE;,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd

9、scan,C3,L3,3rd scan,1 . 連接： C3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E 2使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)： A,B,C的2項(xiàng)子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個(gè)選項(xiàng)； A,C,E的2項(xiàng)子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以刪除這個(gè)選項(xiàng)； B,C,E的2項(xiàng)子集是B,C,B,E,C,E，它的所有2項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。 3這樣，剪枝后得到C3=B,

10、C,E,從以上的算法執(zhí)行過程可以看到Apriori算法的缺點(diǎn): 第一:在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過多， 沒有排除不應(yīng)該參與組合的元素; 第二:每次計(jì)算項(xiàng)集的支持度時(shí)，都對數(shù)據(jù)庫D中的全部 記錄進(jìn)行了一遍掃描比較，如果是一個(gè)大型的數(shù)據(jù) 庫的話，這種掃描比較會(huì)大大增加計(jì)算機(jī)系統(tǒng)的 I/O開銷。而這種代價(jià)是隨著數(shù)據(jù)庫的記錄的增加 呈現(xiàn)出幾何級數(shù)的增加。 因此人們開始尋求一種能減少這種系統(tǒng)1/O開銷的更為快捷的算法。,Apriori算法的缺點(diǎn),改進(jìn)Apriori算法的方法,方法1：基于hash表的項(xiàng)集計(jì)數(shù) 將每個(gè)項(xiàng)集通過相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過將桶中的

11、項(xiàng)集技術(shù)跟最小支持計(jì)數(shù)相比較先淘汰一部分項(xiàng)集。 方法2：事務(wù)壓縮（壓縮進(jìn)一步迭代的事務(wù)數(shù)） 不包含任何k-項(xiàng)集的事務(wù)不可能包含任何(k+1)-項(xiàng)集，這種事務(wù)在下一步的計(jì)算中可以加上標(biāo)記或刪除。,方法3：劃分 挖掘頻繁項(xiàng)集只需要兩次數(shù)據(jù)掃描 D中的任何頻繁項(xiàng)集必須作為局部頻繁項(xiàng)集至少出現(xiàn)在一個(gè)部分中。 第一次掃描：將數(shù)據(jù)劃分為多個(gè)部分并找到局部頻繁項(xiàng)集 第二次掃描：評估每個(gè)候選項(xiàng)集的實(shí)際支持度，以確定全局頻繁項(xiàng)集。 方法4：選樣（在給定數(shù)據(jù)的一個(gè)子集挖掘） 基本思想：選擇原始數(shù)據(jù)的一個(gè)樣本，在這個(gè)樣本上用Apriori算法挖掘頻繁模式 通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可

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

13、可以通過第二此全局掃描來找到遺漏的模式 方法5：動(dòng)態(tài)項(xiàng)集計(jì)數(shù) 在掃描的不同點(diǎn)添加候選項(xiàng)集，這樣，如果一個(gè)候選項(xiàng)集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項(xiàng)集，而不必在這次掃描的以后對比中繼續(xù)計(jì)算,一種Apriori的改進(jìn)算法實(shí)現(xiàn),在Apriori算法中，尋找最大項(xiàng)目集的基本思路是: 第一步:簡單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)目出現(xiàn)的頻率，并找出那些大于或等于最小支持度的項(xiàng)目集，產(chǎn)生一維頻繁項(xiàng)目集Lt。 第二步:循環(huán)處理直到未能再產(chǎn)生維數(shù)更高的頻繁項(xiàng)目集。 循環(huán)過程是:在第k步中，根據(jù)k-1步生成的k-1維頻繁項(xiàng)目集來產(chǎn)生k維候選項(xiàng)目集，由于在產(chǎn)生k-1維頻繁項(xiàng)目集時(shí)，我們可以實(shí)現(xiàn)對該集中出現(xiàn)元素

14、的個(gè)數(shù)進(jìn)行計(jì)數(shù)處理，因此對某元素而言，若它的計(jì)數(shù)個(gè)數(shù)不到k-1的話，可以事先刪除該元素，從而排除由該元素將引起的大規(guī)格所有組合。,第三步：按Apriori算法再檢驗(yàn)新的K 維頻繁項(xiàng)目集的所有k-1維項(xiàng)目集是否已經(jīng)包含在已經(jīng)求出的K-1維頻繁項(xiàng)目集。 若其中有一個(gè)沒有包含，則也可刪去該組合，這樣得到一個(gè)真正有用的K維頻繁項(xiàng)目集選項(xiàng)目集。 第四步：得到了這個(gè)候選項(xiàng)目集后，可以對數(shù)據(jù)庫D的每一個(gè)事務(wù)tid進(jìn)行掃描，若該事務(wù)中至少含有候選項(xiàng)目集CK中的一員，則保留該項(xiàng)事務(wù)，否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標(biāo)記的事務(wù)記錄對換，并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標(biāo)一記，整個(gè)數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫D 中。,一種Apriori的改進(jìn)算法實(shí)現(xiàn),算法的圖例