大數(shù)據(jù)經(jīng)典算法Apriori講解_第1頁(yè)
大數(shù)據(jù)經(jīng)典算法Apriori講解_第2頁(yè)
大數(shù)據(jù)經(jīng)典算法Apriori講解_第3頁(yè)
大數(shù)據(jù)經(jīng)典算法Apriori講解_第4頁(yè)
大數(shù)據(jù)經(jīng)典算法Apriori講解_第5頁(yè)
已閱讀5頁(yè),還剩15頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

4、困助學(xué)體系中,并且針對(duì)經(jīng)典Apriori挖掘算法存在的不足進(jìn)行改進(jìn),先將事務(wù)數(shù)據(jù)庫(kù)映射為一個(gè)布爾矩陣,用一種逐層遞增的思想來(lái)動(dòng)態(tài)的分配內(nèi)存進(jìn)行存儲(chǔ),再利用向量求與運(yùn)算,尋找頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的Apriori算法在運(yùn)行效率上有了很大的提升,挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對(duì)性的開(kāi)展貧困助學(xué)工作。算法思想n該算法的基本思想是:首先找出所有的頻集,這些項(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),這里采用的是中規(guī)

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

6、L2可以執(zhí)行連接操作 的條件是nCk是Lk的超集,即它的成員可能不是頻繁的,但是所有頻繁的k-項(xiàng)集都在Ck中(為什么?)。因此可以通過(guò)掃描數(shù)據(jù)庫(kù),通過(guò)計(jì)算每個(gè)k-項(xiàng)集的支持度來(lái)得到Lk 。n為了減少計(jì)算量,可以使用Apriori性質(zhì),即如果一個(gè)k-項(xiàng)集的(k-1)-子集不在Lk-1中,則該候選不可能是頻繁的,可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll n算法:Apriori。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項(xiàng)集。n輸入:nD:實(shí)物數(shù)據(jù)庫(kù);nMin_sup:最小支持度計(jì)數(shù)閾值。n輸出:L:D中的頻繁項(xiàng)集。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用于計(jì)數(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項(xiàng)集l1Lk-1nfor each項(xiàng)集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)/使用先驗(yàn)知識(shí)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ì)剪枝:頻繁項(xiàng)集的所有子集必須是頻繁的,對(duì)候選項(xiàng)C3,我們可以刪除其子集為非頻繁的選項(xiàng):nA,B,C的2項(xiàng)子集是A,B,A,C,B,C,其中A,B不是L2的元素,所以刪除這個(gè)選項(xiàng);nA,C,E的2項(xiàng)子集是A,C,A,E,C,E,其中A,E 不是L2的元素,所以刪除這個(gè)選項(xiàng);nB,C,E的2項(xiàng)子集是B,C,B,E,C,E,它的所有2項(xiàng)子集都是L2的元素,因此保留這個(gè)選項(xiàng)。n3這樣,剪枝后得到C3=B,C,E從以上的算法執(zhí)行過(guò)程可以看到Apriori算法的缺點(diǎn):第一:在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論