Apriori算法實(shí)驗(yàn)報(bào)告

Apriori算法實(shí)驗(yàn)報(bào)告1背景關(guān)聯(lián)規(guī)則挖掘的研究工作主要包括：Apriori算法的擴(kuò)展、數(shù)量關(guān)聯(lián)規(guī)則挖掘、關(guān)聯(lián)規(guī)則增量式更新、無須生成候選項(xiàng)目集的關(guān)聯(lián)規(guī)則挖掘、最大頻繁項(xiàng)目集挖掘、約束性關(guān)聯(lián)規(guī)則挖掘以及并行及分布關(guān)聯(lián)規(guī)則挖掘算法等，其中快速挖掘與更新頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘研究的重點(diǎn)，也是多種數(shù)據(jù)挖掘應(yīng)用中的技術(shù)關(guān)鍵，已用于分類規(guī)則挖掘和網(wǎng)絡(luò)入侵檢測等方面的研究。研究者還對數(shù)據(jù)挖掘的理論進(jìn)行了有益的探索，將概念格和粗糙集應(yīng)用于關(guān)聯(lián)規(guī)則挖掘中，獲得了顯著的效果。到目前為止，關(guān)聯(lián)規(guī)則的挖掘已經(jīng)取得了令人矚目的成績，包括：單機(jī)環(huán)境下的關(guān)聯(lián)規(guī)則挖掘算法；多值屬性關(guān)聯(lián)規(guī)則挖掘；關(guān)聯(lián)規(guī)則更新算法；基于約束條件的關(guān)聯(lián)規(guī)則挖掘；關(guān)聯(lián)規(guī)則并行及分布挖掘算法等。2算法描述Apriori算法是一種找頻繁項(xiàng)目集的基本算法。其基本原理是逐層搜索的迭代：頻繁 K項(xiàng)Lk集用于搜索頻繁(K+1)項(xiàng)集Lk+1，如此下去，直到不能找到維度更高的頻繁項(xiàng)集為止。這種方法依賴連接和剪枝這兩步來實(shí)現(xiàn)。算法的第一次遍歷僅僅計(jì)算每個(gè)項(xiàng)目的具體值的數(shù)量，以確定大型l項(xiàng)集。隨后的遍歷，第k次遍歷，包括兩個(gè)階段。首先，使用在第(k-1)次遍歷中找到的大項(xiàng)集Lk-1和用Aprioir-gen函數(shù)產(chǎn)生候選項(xiàng)集Ck。接著掃描數(shù)據(jù)庫，計(jì)算Ck中候選的支持度。用Hash樹可以有效地確定Ck中包含在一個(gè)給定的事務(wù)t中的候選。算法如下：L1={大項(xiàng)目集1項(xiàng)目集};for(k=2;Lk1!=空；k++)dobeginCk=apriori-gen(Lk-1); 〃新的候選集for所有事務(wù)t￡DdobeginCt=subset(Ck，t); //t中所包含的候選for所有候選c￡Ctdoc.count++;endLk={c￡Ck|c.count^minsupp}endkey=ULk；Apriori-gen函數(shù)：Apriori候選產(chǎn)生函數(shù)Apriori-gen的參數(shù)Lk-1，即所有大型(k-1)項(xiàng)目集的集合。它返回所有大型k項(xiàng)目集的集合的一個(gè)超集(Superset)。首先，在Jion(連接)步驟，我們把Lk-1和Lk-1相連接以獲得候選的最終集合的一個(gè)超集C:kinsertintoCkselectp[1],p[2], , p[k-1],q[k-1]⑶fromLk-1p,Lk-1q(4)wherep[1]=q[1], , p[k-2]=q[k-2],p[k-1]<q[k-1]接著，在Prune(修剪)步驟，我們將刪除所有的項(xiàng)目集c^Ck，如果c的一些k-1子集不在Lk-1中，為了說明這個(gè)產(chǎn)生過程為什么能保持完全性，要注意對于Lk中的任何有最小支持度的項(xiàng)目集，任何大小為k-1的子集也必須有最小支持度。因此，如果我們用所有可能的項(xiàng)目擴(kuò)充Lk-1中的每個(gè)項(xiàng)目集，然后刪除所有k-1子集不在Lk-1中的項(xiàng)目集，那么我們就能得到Lk中項(xiàng)目集的一個(gè)超集。上面的合并運(yùn)算相當(dāng)于用數(shù)據(jù)庫中所有項(xiàng)目來擴(kuò)展Lk-1；如果刪除擴(kuò)展項(xiàng)目集的第k-1個(gè)項(xiàng)目后得到的k-1項(xiàng)目集不在Lk-1中，則刪除該擴(kuò)展項(xiàng)目集。條件p[k-1]<q[k-1]保證不會(huì)出現(xiàn)相同的擴(kuò)展項(xiàng)。因此，經(jīng)過合并運(yùn)算，Ck>Lk。類似原因在刪除運(yùn)算中，刪除Ck中其k-1子項(xiàng)目集不在Lk-1中的項(xiàng)目集，同樣沒有刪除包含在Lk中的項(xiàng)目集。for所有項(xiàng)目集c￡Ckdofor所有c的(k-1)子集sdoif(s0Lk-1)then從Ck中刪除c例如：L3為｛｛123｝，｛124｝，｛134｝，｛135｝，｛234｝｝。Jion步驟之后，C4為｛｛1234｝，(1345｝｝。Prune步驟將刪除項(xiàng)集｛1345｝，因?yàn)轫?xiàng)集｛145｝不在L3中。Subset函數(shù)：候選項(xiàng)目集Ck存儲(chǔ)在一棵Hash樹中。Hash樹的一個(gè)節(jié)點(diǎn)包含了項(xiàng)集的一個(gè)鏈表(一個(gè)葉節(jié)點(diǎn))或包含了一個(gè)Hash表(一個(gè)內(nèi)節(jié)點(diǎn))。在內(nèi)節(jié)點(diǎn)中，Hash表的每個(gè)Bucket都指向另一個(gè)節(jié)點(diǎn)。Hash樹的根的深度定義為1。在深度d的一個(gè)內(nèi)節(jié)點(diǎn)指向深度d+1的節(jié)點(diǎn)。項(xiàng)目集存儲(chǔ)在葉子中。要加載一個(gè)項(xiàng)目集c時(shí)，從根開始向下直到一個(gè)葉子。在深度為d的一個(gè)內(nèi)節(jié)點(diǎn)上，要決定選取哪個(gè)分枝，可以對此項(xiàng)目集的第d個(gè)項(xiàng)目使用一個(gè)Hash函數(shù)，然后跟隨相應(yīng)Bucket中的指針。所有的節(jié)點(diǎn)最初都創(chuàng)建成葉節(jié)點(diǎn)。當(dāng)一個(gè)葉節(jié)點(diǎn)中項(xiàng)集數(shù)量超過某個(gè)指定的閾值時(shí)，此葉節(jié)點(diǎn)就轉(zhuǎn)為一個(gè)內(nèi)節(jié)點(diǎn)。從根節(jié)點(diǎn)開始，Subset函數(shù)尋找所有包含在某個(gè)事務(wù)t中的候選，方法如下：若處于一個(gè)葉子，就尋找此葉子中的哪些項(xiàng)目集是包括在t中的，并對它們附加引用指向答案集合。若處于一個(gè)內(nèi)節(jié)點(diǎn)，而且是通過Hash項(xiàng)目i從而到達(dá)此節(jié)點(diǎn)的，那么就對t中i之后的每個(gè)項(xiàng)目進(jìn)行Hash，并對相應(yīng)Bucket中的節(jié)點(diǎn)遞歸地應(yīng)用這個(gè)過程。對于根節(jié)點(diǎn)，就對t中的每個(gè)項(xiàng)目進(jìn)行Hash。盡管Apriori算法已經(jīng)可以壓縮候選數(shù)據(jù)項(xiàng)集Ck，但是對于頻繁項(xiàng)集尤其是2維的候選數(shù)據(jù)項(xiàng)集產(chǎn)生仍然需要大量的存儲(chǔ)空間。也就是說對于2維的候選數(shù)據(jù)項(xiàng)集，Apriori算法的剪枝操作幾乎不起任何作用。例如：1維高頻數(shù)據(jù)項(xiàng)集L1的規(guī)模是O(n)，則2維候選數(shù)據(jù)項(xiàng)集的規(guī)模將達(dá)到O(n2)。如果我們考慮一般情況，即在沒有支持度的情況下1維高頻數(shù)據(jù)項(xiàng)集L1的規(guī)模是103，則2維候選數(shù)據(jù)項(xiàng)集的規(guī)模C2將達(dá)到C1000篤X105.這種空間復(fù)雜度以指數(shù)形式的增長，使得這個(gè)經(jīng)

典的算法的執(zhí)行效率很難讓人滿意.Apriori算法的兩大缺點(diǎn)就是產(chǎn)生大量的候選集，以及需重復(fù)掃描數(shù)據(jù)庫。3實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)測試用機(jī)為P41.49GHZ，內(nèi)存256M。實(shí)驗(yàn)采用蘑菇數(shù)據(jù)庫，項(xiàng)目數(shù)=15，共進(jìn)行了6組實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)如下:表1、表2為時(shí)間性能表；表3為對于不同的記錄數(shù)和最小支持度所測試到的頻繁項(xiàng)目集的個(gè)數(shù)。記錄數(shù)time(s)2001記錄數(shù)time(s)2001500410005200014400049800090表1：最小支持度=0.7記錄數(shù)time(s)200150021000420009400027800059表2:最小支持度=0.9表3：'頻繁項(xiàng)目集記錄數(shù)、Min_supL1L2L3L4L5L62000.791930251120.9910105105000.792030251120.9910930010000.7915102000.971000020000.78202718610.9710930040000.78222613200.985200080000.7918209100.9831000下圖為對表1、表2中數(shù)據(jù)的繪制:

emirOOOOOOOOOOO09876543211—emirOOOOOOOOOOO09876543211—sup=0.7—sup=0.9從上圖可以看出當(dāng)增大數(shù)據(jù)庫或者減少最小支持度時(shí)，都會(huì)增加計(jì)算的時(shí)間而且是成指數(shù)增加。因?yàn)樗惴ㄔ诿看窝h(huán)時(shí)都要重新掃描數(shù)據(jù)庫來計(jì)算支持度，而增大數(shù)