挖掘關(guān)聯(lián)規(guī)則的快速算法(apriori算法-外文翻譯)

1、精選優(yōu)質(zhì)文檔傾情為你奉上精選優(yōu)質(zhì)文檔傾情為你奉上專心專注專業(yè)專心專注專業(yè)精選優(yōu)質(zhì)文檔傾情為你奉上專心專注專業(yè)挖掘關(guān)聯(lián)規(guī)則的快速算法 （英）Rakesh Agrawal Ramakrishnan Srikant威斯康辛大學(xué)，計(jì)算機(jī)系，麥迪遜全部或部分材料允許被免費(fèi)拷貝，這些拷貝不是為直接的商業(yè)優(yōu)勢(shì)而制作的，VLDB的拷貝權(quán)是由VLDBE授予的. 另外，拷貝或重新出版還需要金額和VLDBE的允許.第20屆極大數(shù)據(jù)庫(kù)程序會(huì)議 智利 圣地亞哥 ，1994IBM阿爾馬丁研究中心圣塔克萊拉市650亨利道 95120證摘要：針對(duì)找出銷售交易中大量數(shù)據(jù)庫(kù)里項(xiàng)目之間的關(guān)聯(lián)規(guī)則問(wèn)題，我們提出兩種與已知算法完全不同

2、的新的算法來(lái)解決此問(wèn)題. 觀察數(shù)據(jù)表明：這兩種算法在從小問(wèn)題的三個(gè)到大問(wèn)題的多個(gè)度量的因子上都優(yōu)于先前的算法. 根據(jù)這兩種算法的特點(diǎn)，我們還指出如何將它們合并才是一個(gè)最佳的混合算法，稱為AprioriHybrid算法. 按比例增大實(shí)驗(yàn)證明AprioriHybrid算法是隨著交易數(shù)量按線性比例遞增的，且它在交易大小和數(shù)據(jù)庫(kù)中的項(xiàng)目上也有良好的遞推性.引言條形碼技術(shù)的廣泛應(yīng)用使得零售商在收集和存儲(chǔ)大量商品的價(jià)格數(shù)據(jù)時(shí)十分方便，簡(jiǎn)稱為貨籃數(shù)據(jù). 一條這樣的數(shù)據(jù)記錄通常都包括某個(gè)顧客的交易日期，交易中所購(gòu)的物品項(xiàng)目. 成功的組織者視這種數(shù)據(jù)庫(kù)為貿(mào)易市場(chǎng)基礎(chǔ)結(jié)構(gòu)的重要組成部分. 他們專注于研究用數(shù)據(jù)庫(kù)技

3、術(shù)來(lái)推動(dòng)市場(chǎng)信息化過(guò)程，這樣市場(chǎng)經(jīng)營(yíng)者就可以有能力發(fā)展及實(shí)施為顧客制定購(gòu)買產(chǎn)品的方案和策略6.有關(guān)在貨籃數(shù)據(jù)上挖掘關(guān)聯(lián)規(guī)則的問(wèn)題在4中已作介紹. 舉個(gè)例子：可能有98%的顧客在購(gòu)買輪胎和汽車配件的同時(shí)接受了有關(guān)汽車的服務(wù). 找出所有這樣的規(guī)則對(duì)于促進(jìn)市場(chǎng)營(yíng)銷和提高顧客購(gòu)買力是非常有價(jià)值的. 另外還有價(jià)目表設(shè)計(jì)，商品上架設(shè)計(jì)，進(jìn)貨安排，根據(jù)購(gòu)買行為模式對(duì)顧客進(jìn)行分類. 但這些應(yīng)用中的數(shù)據(jù)庫(kù)都是極其龐大的，因此，尋找一種快速的算法來(lái)完成此項(xiàng)任務(wù)是我們的當(dāng)務(wù)之急.以下是關(guān)于這個(gè)問(wèn)題4的一個(gè)表述：令=是個(gè)不同項(xiàng)目的集合，給定一個(gè)事務(wù)數(shù)據(jù)庫(kù),其中每一個(gè)事務(wù)是中一些項(xiàng)目的集合，且都與一個(gè)唯一的標(biāo)識(shí)符相聯(lián).

4、 如果對(duì)于中的一個(gè)子集,有,我們就說(shuō)事務(wù)包含. 關(guān)聯(lián)規(guī)則是形如的蘊(yùn)含式，其中,且=. 如果事務(wù)數(shù)據(jù)庫(kù)中有%的事務(wù)包含的同時(shí)也包含，則稱關(guān)聯(lián)規(guī)則的置信度為%. 如果事務(wù)數(shù)據(jù)庫(kù)中，有%的事務(wù)包含了，則稱關(guān)聯(lián)規(guī)則具有支持度%. 這個(gè)規(guī)則在我們討論多項(xiàng)集的問(wèn)題時(shí)比4中的闡述要簡(jiǎn)單很多.給定一個(gè)事務(wù)集，挖掘關(guān)聯(lián)規(guī)則的問(wèn)題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則. 我們對(duì)事務(wù)集的內(nèi)容屬性方面不加以討論，比如說(shuō)，可以是一份數(shù)據(jù)文件，也可以是一張關(guān)系表，或者是一個(gè)關(guān)聯(lián)表達(dá)式的結(jié)果.找出所有關(guān)聯(lián)規(guī)則中的算法，我們稱文章4提出的為AIS算法，文章13提出的為SETM算法. 在本文中

5、，我們介紹兩種新的算法：Apriori和AprioriTid算法，基本上與先前的算法不同. 我們將用實(shí)驗(yàn)結(jié)果證明這兩種算法優(yōu)于先前算法. 它們之間的差距主要體現(xiàn)在問(wèn)題大小的增大及問(wèn)題范圍從小問(wèn)題的三個(gè)到大問(wèn)題的多個(gè)度量的因子上變化. 接著我們討論由Apriori和AprioriTid算法合并而成的混合算法（AprioriHybrid算法）是如何的優(yōu)異. 實(shí)驗(yàn)證明AprioriHybrid算法具有良好的遞推性能，開(kāi)啟了挖掘關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫(kù)中應(yīng)用的可行性.找出關(guān)聯(lián)規(guī)則屬于數(shù)據(jù)庫(kù)挖掘范疇3,12，也稱為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)21. 類似地，但不直接可應(yīng)用的工作還包括分類規(guī)則的介紹8,11,22，因果關(guān)聯(lián)

6、規(guī)則的發(fā)現(xiàn)19，學(xué)習(xí)邏輯定義18，函數(shù)的數(shù)據(jù)擬合15以及簇9,10. 非公開(kāi)性的有關(guān)機(jī)器學(xué)習(xí)文獻(xiàn)的作品是在20中的KID3算法. 如果應(yīng)用在查找所有關(guān)聯(lián)規(guī)則問(wèn)題上，這個(gè)算法在與假定關(guān)聯(lián)項(xiàng)的數(shù)目一樣多的數(shù)據(jù)上進(jìn)行運(yùn)算時(shí)，運(yùn)算量非常大. 最近在數(shù)據(jù)庫(kù)上的研究工作是由數(shù)據(jù)出發(fā)來(lái)定義關(guān)聯(lián)函數(shù)16. 函數(shù)關(guān)聯(lián)規(guī)則需要十分嚴(yán)格的條件. 因此，定義一種函數(shù)規(guī)則為后,在16中描述的算法若從規(guī)則來(lái)考慮，就無(wú)法推出. 我們考慮的這些關(guān)聯(lián)規(guī)則要符合實(shí)際性質(zhì). 規(guī)則的存在并不意味著也成立，因?yàn)楹笳呖赡懿痪邆渥钚≈С侄? 同樣的，規(guī)則和的存在也不意味著成立，因?yàn)楹笳呖赡芤膊痪邆渥钚≈眯哦?曾有一個(gè)關(guān)于測(cè)定“有用性”或“

7、有趣性”規(guī)則的實(shí)驗(yàn)20. 無(wú)論是有用的還是有趣的，通常都是依賴于運(yùn)用的. 它需要圈內(nèi)人員去提供材料，讓所有人知道規(guī)則的發(fā)現(xiàn)過(guò)程以及讓規(guī)則清晰明了，如7,14. 在本文中，對(duì)這些觀點(diǎn)我們不加以討論，除了指出它們?cè)谝?guī)則發(fā)現(xiàn)體系中的必要特征，可以利用我們的算法作為發(fā)現(xiàn)過(guò)程中的引擎.問(wèn)題剖析和論文概要找出所有關(guān)聯(lián)規(guī)則的問(wèn)題可分解為以下兩個(gè)小問(wèn)題：找出事務(wù)中所有滿足用戶指定最小支持度的項(xiàng)集，每個(gè)項(xiàng)集的支持度就是包含項(xiàng)集的事務(wù)數(shù). 具有最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，否則稱為非頻繁項(xiàng)集. 在第二章，我們給出新的算法:Apriori和AprioriTid算法來(lái)解決這個(gè)問(wèn)題.利用頻繁項(xiàng)集來(lái)產(chǎn)生所需要的規(guī)則，這里

8、有一種直接的算法. 對(duì)于每個(gè)頻繁項(xiàng)集，找出中所有非空子集，如果就生成關(guān)聯(lián)規(guī)則(-). 我們需要考慮所有的子集產(chǎn)生的多種規(guī)則的結(jié)果. 由于篇幅關(guān)系，這里對(duì)此問(wèn)題不做深入探討，但讀者可通過(guò)閱讀5來(lái)獲取一種快速算法.第三章，我們就提出的Apriori和AprioriTid算法與AIS算法4和SETM算法13作出比較. 為了使論文更完善，在這個(gè)章節(jié)中還對(duì)AIS和SETM算法做了簡(jiǎn)要介紹. 同時(shí)我們還闡述了Apriori和AprioriTid算法如何合并形成AprioriHybrid算法，并且演示了這種算法的遞推性. 在第四章，我們總結(jié)指出許多相關(guān)聯(lián)的開(kāi)放性問(wèn)題.產(chǎn)生頻繁項(xiàng)集產(chǎn)生頻繁項(xiàng)集需要在數(shù)據(jù)上作多

9、步運(yùn)算. 第一步，需要計(jì)算出每個(gè)項(xiàng)目的支持度，從而確定哪些是頻繁的，換言之，就是具有最小支持度. 在后續(xù)的步驟中，都以前一步生成的頻繁項(xiàng)集為基礎(chǔ)，產(chǎn)生新的候選項(xiàng)集，即潛在的頻繁項(xiàng)集，再掃描數(shù)據(jù)庫(kù)計(jì)算候選項(xiàng)集的支持度，最后確定哪個(gè)些候選項(xiàng)集能真正成為頻繁項(xiàng)集. 重復(fù)上述過(guò)程，直到?jīng)]有新的頻繁項(xiàng)集產(chǎn)生為止.Apriori和AprioriTid算法與AIS算法4和SETM算法13完全不同之處就在于候選項(xiàng)集的產(chǎn)生方面，前者一步到位而后者在數(shù)據(jù)掃描時(shí)臨時(shí)產(chǎn)生. 在AIS和SETM算法中，掃描一個(gè)數(shù)據(jù)時(shí)候選項(xiàng)集呈飛過(guò)式產(chǎn)生. 特別地，瀏覽一個(gè)事務(wù)之后，事務(wù)中哪一個(gè)是前一步生成的頻繁項(xiàng)集是確定的. 新的候選

10、項(xiàng)集是將事務(wù)中原有的項(xiàng)擴(kuò)展到這些頻繁項(xiàng)集中產(chǎn)生的. 然而，就我們看來(lái)，明顯的缺陷就是這個(gè)結(jié)果不一定會(huì)產(chǎn)生，而且對(duì)候選項(xiàng)集計(jì)算的次數(shù)太多導(dǎo)致效率低下.而Apriori和AprioriTid算法只需通過(guò)先前事務(wù)中前一步找出的頻繁項(xiàng)集來(lái)產(chǎn)生候選項(xiàng)集，而無(wú)需考慮數(shù)據(jù)庫(kù)中所有事務(wù). 其基本的思想是任何頻繁項(xiàng)集的子集也一定是頻繁項(xiàng)集. 因此，就可以通過(guò)鏈接頻繁(-1)-項(xiàng)集，刪除其中含有非頻繁子集的項(xiàng)集來(lái)產(chǎn)生候選-項(xiàng)集. 這個(gè)過(guò)程使得更少的候選項(xiàng)集產(chǎn)生.此外，AprioriTid算法還有自己的特點(diǎn)，數(shù)據(jù)庫(kù)僅在第一次統(tǒng)計(jì)候選項(xiàng)集的支持度時(shí)被掃描一次. 更確切地說(shuō)，把前一步中得到的候選項(xiàng)集的代碼用到這個(gè)項(xiàng)目中

11、，在接下來(lái)的步驟中，代碼的大小會(huì)變得比數(shù)據(jù)庫(kù)小，因此，節(jié)省了很多掃描過(guò)程. 在描述此算法時(shí)我們會(huì)對(duì)細(xì)節(jié)的關(guān)鍵點(diǎn)作出具體解釋.符號(hào)表示 假設(shè)每個(gè)事務(wù)中項(xiàng)目都按字典序排列，那么就可以直接采用這些算法來(lái)保持?jǐn)?shù)據(jù)庫(kù)中的運(yùn)算正常化，且數(shù)據(jù)庫(kù)中每條記錄顯示為，其中是事務(wù)的標(biāo)志符.我們把一個(gè)項(xiàng)集中所含項(xiàng)的個(gè)數(shù)稱為項(xiàng)集的長(zhǎng)度，長(zhǎng)度為的項(xiàng)集稱為-項(xiàng)集. 項(xiàng)集中各項(xiàng)按字典序排列，我們用符號(hào)12表示一個(gè)-項(xiàng)集，其中包含項(xiàng)目1,2,，且12. 如果，且為-項(xiàng)集，則為的-項(xiàng)擴(kuò)展集. 關(guān)聯(lián)每個(gè)項(xiàng)集的是一個(gè)用來(lái)儲(chǔ)存這個(gè)項(xiàng)集支持度的計(jì)算領(lǐng)域，其初始值為0.對(duì)算法中使用的符號(hào)，我們?cè)诒?中作了總結(jié). 集合在AprioriTid

12、算法中會(huì)應(yīng)用到，我們?cè)诿枋鲞@個(gè)算法時(shí)再對(duì)它作進(jìn)一步的探討.表1：符號(hào)-項(xiàng)集含有個(gè)項(xiàng)的項(xiàng)集頻繁-項(xiàng)集（具有最小支持度）集合中的每個(gè)元素含有兩個(gè)計(jì)算域：i)項(xiàng)集的計(jì)算；ii)支持度的計(jì)算候選-項(xiàng)集（潛在的頻繁項(xiàng)集）集合中的每個(gè)元素含有兩個(gè)計(jì)算域：i)項(xiàng)集的計(jì)算；ii)支持度的計(jì)算當(dāng)生成的事務(wù)與候選集保持關(guān)聯(lián)時(shí)的候選-項(xiàng)集Apriori算法圖1給出了Apriori算法的詳細(xì)過(guò)程. 算法的第一步就是簡(jiǎn)單地計(jì)算出決定生成頻繁1-項(xiàng)集的項(xiàng)目. 接下來(lái)直到第步，可分成兩個(gè)階段：首先，在第-1步中產(chǎn)生頻繁項(xiàng)集，通過(guò)調(diào)用Apriori-gen函數(shù)產(chǎn)生候選項(xiàng)集；其次，對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描并計(jì)算候選項(xiàng)集的支持度. 為了

13、使計(jì)算更快速，我們需要確定候選項(xiàng)集包含于給定的事務(wù)中. 2.1.2章節(jié)描述的Subset函數(shù)就運(yùn)用于這個(gè)目的. 參考5中討論的緩沖管理.1）large 1-itemsets;2) for (2; ;) do begin3) apriori-gen();/新的候選項(xiàng)集4） forall transactions do begin 5) subset(,);/所有包含的候選項(xiàng)集6） forall candidates do7) .count;8) end9) .countminsup10) end11)Answer圖1：Apriori算法Apriori候選集的產(chǎn)生求得所有頻繁(-1)-項(xiàng)集是通過(guò)函

14、數(shù)Apriori-gen實(shí)現(xiàn)的，該函數(shù)返回的是所有頻繁-項(xiàng)集的超集，其計(jì)算過(guò)程如下：第一步，鏈接，把與自己鏈接：insert into select ,from , Where =, =, ;第二步，剪枝，如果項(xiàng)集但中的(-1)-項(xiàng)子集不屬于，則:forall itemsets do forall (-1)-subsets of do if () then delete from ;舉例：令=1 2 3，1 2 4，1 3 4，1 3 5，2 3 4. 通過(guò)鏈接步， =1 2 3 4，1 3 4 5，剪枝步會(huì)刪除1 3 4 5，因?yàn)? 4 5不屬于，所以最后=1 2 3 4.把這里產(chǎn)生候選集的

15、方法與AIS和SETM算法的相比較,方法的第步都是掃描數(shù)據(jù)庫(kù)，從而確定中的哪個(gè)頻繁項(xiàng)集當(dāng)前屬于. 這里的每個(gè)頻繁項(xiàng)集是由中原有頻繁的項(xiàng)一起擴(kuò)展而成的，且這些項(xiàng)目在按字典序排列后會(huì)排在中原有的項(xiàng)目之后. 繼續(xù)上面的例子，考慮事務(wù)1 2 3 4 5，第四步，AIS和SETM算法會(huì)通過(guò)擴(kuò)展頻繁項(xiàng)集1 2 3來(lái)產(chǎn)生兩個(gè)候選集1 2 3 4，1 2 3 5. 類似地，另外的三個(gè)候選項(xiàng)集會(huì)通過(guò)擴(kuò)展中的其他頻繁項(xiàng)集來(lái)生成，導(dǎo)致第四步需要考慮5個(gè)候選項(xiàng)集. 另一方面，Apriori算法只產(chǎn)生并計(jì)算一個(gè)項(xiàng)集1 3 4 5，因?yàn)樗ㄒ粋€(gè)Apriori，其余合并的項(xiàng)集不可能具有最小支持度.驗(yàn)證：我們需要證明. 顯

16、然，任意頻繁項(xiàng)集的子集都具有最小支持度，因此，如果把所有可能的項(xiàng)目擴(kuò)展到中的每個(gè)項(xiàng)集內(nèi)，刪除其中(-1)-子集不屬于的項(xiàng)集，就得到中項(xiàng)集的超集.鏈接等同于用數(shù)據(jù)庫(kù)中的每個(gè)項(xiàng)擴(kuò)展，再刪除那些第(-1)項(xiàng)不屬于的項(xiàng)集，得到(-1)-項(xiàng)集. 條件明確不產(chǎn)生重復(fù)項(xiàng). 因此，在鏈接步后就有.同理，雖然刪除所有(-1)-項(xiàng)子集不屬于的項(xiàng)集，但不會(huì)刪除內(nèi)的任何項(xiàng)集.變形：在同一步中計(jì)算多種長(zhǎng)度的候選集 在第步不僅能計(jì)算長(zhǎng)度為的候選集，還能計(jì)算由產(chǎn)生的候選集等，這里由產(chǎn)生且. 當(dāng)計(jì)算和保存額外的候選集到存儲(chǔ)器上所花的時(shí)間比掃描數(shù)據(jù)庫(kù)少時(shí)，這個(gè)變形就可在后續(xù)步驟中得到應(yīng)用.Subset 函數(shù)候選項(xiàng)集存儲(chǔ)于has

17、h-樹(shù)中，hash-樹(shù)的一個(gè)結(jié)點(diǎn)包含的不是一列項(xiàng)集（葉子結(jié)點(diǎn)）就是一個(gè)hash-表（內(nèi)部結(jié)點(diǎn)）. 在內(nèi)部結(jié)點(diǎn)中，hash-表的每個(gè)桶指向另一個(gè)結(jié)點(diǎn). 規(guī)定hash-樹(shù)樹(shù)根的深度為1，深度為的內(nèi)部結(jié)點(diǎn)指向深度為的結(jié)點(diǎn)，項(xiàng)集都存儲(chǔ)在葉子結(jié)點(diǎn)中，當(dāng)存儲(chǔ)一個(gè)項(xiàng)集時(shí)，我們從樹(shù)根出發(fā)，沿著樹(shù)直到葉子. 在深度為的內(nèi)部結(jié)點(diǎn)處確定沿著哪條樹(shù)枝以運(yùn)用hash-函數(shù)到達(dá)項(xiàng)集的第項(xiàng). 所有的結(jié)點(diǎn)最初都是由葉子結(jié)點(diǎn)生成的，當(dāng)葉子結(jié)點(diǎn)上項(xiàng)集的數(shù)目超出一個(gè)特定的范圍時(shí)，葉子結(jié)點(diǎn)就轉(zhuǎn)化為內(nèi)部結(jié)點(diǎn).從根結(jié)點(diǎn)出發(fā)，運(yùn)用Subset函數(shù)找出事務(wù)中所有的候選集. 如果在一個(gè)葉子結(jié)點(diǎn)中找到屬于的項(xiàng)集，那么對(duì)他們?cè)趩?wèn)題集中添加附注；如

18、果通過(guò)對(duì)項(xiàng)進(jìn)行hash后到達(dá)一個(gè)內(nèi)部結(jié)點(diǎn)，那么對(duì)中之后的所有項(xiàng)進(jìn)行hash，并用這個(gè)程序?qū)ν皟?nèi)相對(duì)應(yīng)的結(jié)點(diǎn)進(jìn)行遞歸；此外，對(duì)于根結(jié)點(diǎn)中每個(gè)屬于的項(xiàng)都要進(jìn)行hash.究竟為什么Subset函數(shù)會(huì)返回附注的所需集合呢，這里就要考慮根結(jié)點(diǎn)發(fā)生了什么變化. 對(duì)于事務(wù)中的任意項(xiàng)集，中的第一個(gè)項(xiàng)目肯定屬于，在根部，通過(guò)對(duì)中的每個(gè)項(xiàng)目進(jìn)行hash后，確定不是以中的項(xiàng)目為開(kāi)始的項(xiàng)集. 同樣對(duì)深度較低的結(jié)點(diǎn)運(yùn)用這個(gè)結(jié)論，唯一附加的因素是，只要每個(gè)項(xiàng)集中的項(xiàng)目都按字典序排列著，如果僅對(duì)項(xiàng)進(jìn)行hash后就到達(dá)當(dāng)前的結(jié)點(diǎn)，那么只需考慮中排在之后的項(xiàng).AprioriTid 算法AprioriTid算法的過(guò)程如圖2所示，

19、同樣在計(jì)算過(guò)程之前運(yùn)用apriori-gen函數(shù)（2.1.1章節(jié)已給出）確定候選項(xiàng)集. 這個(gè)算法有意思的地方就是數(shù)據(jù)在第一步被掃描之后就不必再去計(jì)算它的支持度，而是被集合所取代. 集合中的每個(gè)元素都以形式存在，代表事務(wù)中潛在的頻繁-項(xiàng)集，用表示整個(gè)集合. 當(dāng)=1時(shí)，對(duì)應(yīng)數(shù)據(jù)庫(kù)，雖然概念上是每個(gè)項(xiàng)目被項(xiàng)集所取代；當(dāng)1時(shí)，由算法（第10步）產(chǎn)生，其中的元素與事務(wù)相對(duì)應(yīng)，表示為. 如果一個(gè)事務(wù)不包含候選-項(xiàng)集，則不會(huì)含有這個(gè)事務(wù)的入口記錄. 因此，中入口記錄的數(shù)目可能會(huì)少于數(shù)據(jù)庫(kù)中事務(wù)的數(shù)目，尤其對(duì)于數(shù)值較大的. 另外，對(duì)于數(shù)值較大的，每條入口記錄可能會(huì)比相對(duì)應(yīng)的事務(wù)要小，因?yàn)榭赡苤挥猩贁?shù)候選集屬于

20、事務(wù). 然而對(duì)于數(shù)值較小的，每條入口記錄可能會(huì)比相對(duì)應(yīng)的事務(wù)要大，因?yàn)橹械囊粭l入口記錄包括事務(wù)中所有的候選-項(xiàng)集.在2.2.1章節(jié)，我們給出了數(shù)據(jù)結(jié)構(gòu)用來(lái)運(yùn)行這個(gè)算法. 參考5可得這個(gè)驗(yàn)證的證明過(guò)程以及對(duì)商業(yè)中緩沖管理的討論.1) large 1-itemsets;2) database ;3) for (2; +) do begin4) apriori-gen();/新的候選項(xiàng)集5) ;6) forall entries do begin7) /確定中的候選項(xiàng)集 /在事務(wù)中定義 set-of-itemsetsset-of-itemsets;8) forall candidates do9)

21、.coumt;10) if then 11) end12) countminsup13) end14) Answer圖2：AprioriTid算法舉例：考慮圖3所示的數(shù)據(jù)庫(kù)，假設(shè)事務(wù)的最小支持度為2，在第4步時(shí)對(duì)運(yùn)用apriori-gen函數(shù)得到候選項(xiàng)集，從第6步到第10步，通過(guò)掃描的入口記錄來(lái)計(jì)算中候選集的支持度并產(chǎn)生. 中的第一條入口記錄是134，與事務(wù)100相對(duì)應(yīng). 第7步中對(duì)應(yīng)中的入口記錄為1 3，因?yàn)? 3是的一個(gè)元素，且1 3-1與1 3-3都是set_of_itemsets中的元素.對(duì)運(yùn)用apriori-gen函數(shù)得到，對(duì)與作進(jìn)一步計(jì)算得到，發(fā)現(xiàn)中缺少事務(wù)100和400的兩條入口

22、記錄，因?yàn)樗麄儾话械娜魏雾?xiàng)集. 于是中的候選項(xiàng)集2 3 5就證明是最大的，且是唯一的元素. 當(dāng)用生成時(shí)，結(jié)果為空，那么計(jì)算結(jié)束.數(shù)據(jù)結(jié)構(gòu)我們給每個(gè)候選項(xiàng)集分配一個(gè)唯一的號(hào)碼，稱為. 每個(gè)候選項(xiàng)集都按隊(duì)列保存，則指針可通過(guò)來(lái)查找項(xiàng)集. 中的每個(gè)元素都以形式存在且每個(gè)都存儲(chǔ)在連續(xù)的結(jié)構(gòu)中.通過(guò)鏈接兩個(gè)頻繁(-1)-項(xiàng)集并運(yùn)用Apriori-gen函數(shù)來(lái)產(chǎn)生一個(gè)候選-項(xiàng)集，我們?yōu)槊總€(gè)候選項(xiàng)集設(shè)定兩個(gè)附加域：i)初始域；ii)擴(kuò)展域. 初始域存儲(chǔ)著產(chǎn)生的兩個(gè)頻繁(-1)-項(xiàng)集的，而擴(kuò)展域存儲(chǔ)著所有由的擴(kuò)展而成的(+1)-項(xiàng)候選集的. 因此，如果候選集是由和產(chǎn)生的，那么初始域中存儲(chǔ)著和的，同時(shí)，把的

23、添加到的擴(kuò)展域中.圖3：舉例現(xiàn)在我們來(lái)描述圖2中的第7步在上述數(shù)據(jù)結(jié)構(gòu)中是如何運(yùn)用的. 調(diào)回中入口記錄對(duì)應(yīng)的set_of_itemsets域，給所有屬于事務(wù)的(-1)-候選集，記這種候選集的擴(kuò)展域?yàn)?，所有候選-項(xiàng)集的集合構(gòu)成擴(kuò)展集,對(duì)每個(gè)中的，初始域給出產(chǎn)生的兩個(gè)項(xiàng)集的. 如果這些項(xiàng)集目前有set_of_itemsets的入口記錄，那么可以總結(jié)出在事務(wù)中，且把加入中.運(yùn)行為了評(píng)估這個(gè)方法在產(chǎn)生頻繁項(xiàng)集時(shí)的有關(guān)運(yùn)行情況，我們?cè)贗BM RS/6000 530H工作站作了幾個(gè)關(guān)于測(cè)試CPU在33MHZ，64MB的存儲(chǔ)器和AIX3.2的操作系統(tǒng)下運(yùn)行效率的實(shí)驗(yàn). 數(shù)據(jù)存于AIX文檔程序中，并保存在“2

24、GB SCSI3.5”的驅(qū)動(dòng)器上，計(jì)算測(cè)得連續(xù)流量的速度大約為2MB/s.我們首先給出AIS和SETM算法的概要，再針對(duì)其算法，把Apriori和AprioriTid算法的運(yùn)行過(guò)程與之相比較. 接著闡述如何對(duì)虛擬數(shù)據(jù)庫(kù)進(jìn)行求值，并且給出運(yùn)算結(jié)果. 最后來(lái)總結(jié)把Apriori和AprioriTid算法合并形成AprioriHybrid算法在運(yùn)行上的優(yōu)點(diǎn)所在，并證明它的遞推性.AIS算法當(dāng)掃描數(shù)據(jù)庫(kù)時(shí)，生成候選項(xiàng)集且被快速統(tǒng)計(jì)；瀏覽一個(gè)事務(wù)后，確定前一步找出的哪個(gè)頻繁項(xiàng)集包含于此事務(wù)中，新的候選項(xiàng)集可通過(guò)把事務(wù)中的項(xiàng)擴(kuò)展到這些頻繁項(xiàng)集中生成. 頻繁項(xiàng)集僅由頻繁的項(xiàng)目擴(kuò)展而成，且這些項(xiàng)目在按字典序排

25、列后會(huì)排在中原有的項(xiàng)目之后. 候選集由事務(wù)生成并加入到候選項(xiàng)集中繼續(xù)下一步的運(yùn)行，否則對(duì)應(yīng)入口記錄的條數(shù)將會(huì)增大，如果他們是之前的事務(wù)產(chǎn)生的話. 參考4可對(duì)AIS算法的細(xì)節(jié)有更深入的了解.SETM算法SETM算法是在使用SQL時(shí)需要計(jì)算頻繁項(xiàng)集的背景驅(qū)動(dòng)下研究出來(lái)的. 與AIS算法一樣，SETM算法也是快速掃描數(shù)據(jù)庫(kù)中的事務(wù)產(chǎn)生候選項(xiàng)集，計(jì)算每個(gè)候選項(xiàng)集時(shí)也一致. 但是，使用標(biāo)準(zhǔn)的SQL語(yǔ)句運(yùn)行此算法產(chǎn)生候選集時(shí)，把產(chǎn)生候選集與計(jì)算分離開(kāi)來(lái)了. 它保存候選項(xiàng)集的復(fù)本并與連續(xù)結(jié)構(gòu)中的事務(wù)相連接. 過(guò)程的最后一步，候選項(xiàng)集的支持度被確定下來(lái)并保存和收集在這個(gè)連續(xù)結(jié)構(gòu)中.SETM算法記錄事務(wù)及其候選

26、項(xiàng)集，為了避免需要運(yùn)行子集，就利用這個(gè)信息確定事務(wù)中的頻繁項(xiàng)集，是刪除不具有最小支持度的候選集后得到的. 假設(shè)數(shù)據(jù)庫(kù)保存在列表中，SETM算法在通過(guò)把存儲(chǔ)在上，就能很容易找出事務(wù)中的頻繁項(xiàng)集. 實(shí)際上，只需要在列表上對(duì)進(jìn)行掃描一次就夠了，產(chǎn)生候選集可通過(guò)有關(guān)合并-鏈接操作來(lái)完成.這個(gè)方法的主要缺點(diǎn)是候選集的長(zhǎng)度問(wèn)題. 對(duì)于每個(gè)候選項(xiàng)集，候選集的入口記錄與包含候選項(xiàng)集的事務(wù)數(shù)目一樣多. 此外，當(dāng)我們?cè)谧詈笠徊經(jīng)Q定計(jì)算候選項(xiàng)集的支持度時(shí)，處在錯(cuò)誤的位置，且需要保存在項(xiàng)集上. 在計(jì)算與刪除不具有最小支持度的非頻繁候選項(xiàng)集后，在下一步被用于產(chǎn)生候選集之前需要在上作另外保存.構(gòu)造虛擬數(shù)據(jù)我們構(gòu)造虛擬事務(wù)

27、去評(píng)價(jià)算法在大量數(shù)據(jù)中的運(yùn)行情況. 這些事務(wù)都是模仿零售商情況，模型即顧客趨向于購(gòu)買的商品的集合. 每個(gè)集合都包含有潛在的頻繁項(xiàng)集，比如一個(gè)集合包括床單、枕套、羊毛圍巾和花邊，有些人可能會(huì)購(gòu)買其中的某幾項(xiàng)如床單和枕套，有些人會(huì)只購(gòu)買一項(xiàng)如床單. 一個(gè)事務(wù)也可包含一個(gè)或多個(gè)頻繁項(xiàng)集，比如一個(gè)顧客在寫(xiě)下一件裙子和一件夾克衫訂單的同時(shí)，又預(yù)訂了床單和枕套. 這里裙子和夾克衫的組合構(gòu)成另一個(gè)頻繁項(xiàng)集. 事務(wù)的大小通常會(huì)蘊(yùn)含著某種意義，且只有少數(shù)事務(wù)含有許多項(xiàng)；頻繁項(xiàng)集的大小通常也會(huì)蘊(yùn)含著某種含義，且只有少數(shù)頻繁項(xiàng)集含有許多項(xiàng).建立一個(gè)數(shù)據(jù)集，構(gòu)造數(shù)據(jù)過(guò)程中使用的參數(shù)如表2所示：表2：參數(shù)事務(wù)的數(shù)目事務(wù)

28、的平均大小最大的潛在頻繁項(xiàng)集的平均大小最大的潛在頻繁項(xiàng)集的數(shù)目項(xiàng)目的個(gè)數(shù)首先確定下一事務(wù)的大小，可通過(guò)Poisson分布，令平均數(shù)=獲得. 如果每個(gè)項(xiàng)目被提取的可能性都為，且共有項(xiàng)，那么事務(wù)中項(xiàng)目的期望值可通過(guò)二項(xiàng)分布求得，設(shè)參數(shù)為，則結(jié)果與Possion分布近似，為.接著給事務(wù)分配項(xiàng)目，每個(gè)事務(wù)會(huì)分配到一個(gè)連續(xù)的潛在頻繁項(xiàng)集. 如果當(dāng)前的頻繁項(xiàng)集不能放入事務(wù)中，就先置于一旁，當(dāng)分配結(jié)束時(shí)再移入下一事務(wù)中.頻繁項(xiàng)集中的項(xiàng)是從中提取出來(lái)的，中項(xiàng)集的數(shù)目記為，它與潛在頻繁項(xiàng)集的平均支持度的關(guān)系相反. 中的項(xiàng)集由Poisson分布令平均數(shù)=計(jì)算項(xiàng)集的長(zhǎng)度生成. 第一個(gè)項(xiàng)集內(nèi)的項(xiàng)是隨機(jī)提取產(chǎn)生的，為了

29、模仿各頻繁項(xiàng)集間常含有相同項(xiàng)目的現(xiàn)象，項(xiàng)集內(nèi)的部分項(xiàng)取自連續(xù)著的前一項(xiàng)集. 我們用指數(shù)分布隨機(jī)抽取平均數(shù)等于關(guān)聯(lián)度的項(xiàng)，從而確定每個(gè)項(xiàng)集的重復(fù)部分，其余部分的項(xiàng)隨機(jī)提取. 實(shí)驗(yàn)中的數(shù)據(jù)集，關(guān)聯(lián)度為0.5；當(dāng)在現(xiàn)實(shí)生活中運(yùn)行多種實(shí)驗(yàn)，把關(guān)聯(lián)度設(shè)為0.25或0.75時(shí)，對(duì)結(jié)果都不會(huì)造成影響.中的每一個(gè)項(xiàng)都有自己的權(quán)值，與這個(gè)項(xiàng)集被選取的可能性相對(duì)應(yīng). 這個(gè)重量由指數(shù)分布通過(guò)單位計(jì)算所得并使之標(biāo)準(zhǔn)化，所以中所有項(xiàng)集的權(quán)值之和為1. 隨后加入事務(wù)的項(xiàng)集是通過(guò)投一枚帶權(quán)值的面硬幣，權(quán)值偏向的一邊就有可能被提取相關(guān)項(xiàng)集.為了模仿頻繁項(xiàng)集中的所有項(xiàng)不總是被一起購(gòu)買現(xiàn)象，我們給中的每個(gè)項(xiàng)集一個(gè)誤差度. 當(dāng)事務(wù)

30、中加入一個(gè)項(xiàng)集時(shí)，只要同樣分布的任意數(shù)字（010）比小，就從項(xiàng)集中去掉一個(gè)項(xiàng). 所以對(duì)一個(gè)長(zhǎng)度為的項(xiàng)集，在事務(wù)中加入項(xiàng)需要次，-1項(xiàng)需要次，-2項(xiàng)需要次等. 一個(gè)項(xiàng)集的誤差度是固定的，且由平均數(shù)為0.5，方差為0.1的正態(tài)分布取得.我們構(gòu)造數(shù)據(jù)集時(shí)，令=1000，=2000；給取3個(gè)數(shù)值分別為5，10，20；給取3個(gè)數(shù)值分別為2，4，6；事務(wù)的大小設(shè)為100,000，因?yàn)樵?.4章節(jié)中，將證明STEM算法不能運(yùn)行較大的數(shù)值. 但是對(duì)于按比例增大實(shí)驗(yàn)，我們可以構(gòu)造大小為10,000,000的事務(wù)（838MB,T20）的數(shù)據(jù)集. 表3對(duì)數(shù)據(jù)集合中的參數(shù)設(shè)置作了概括，并給出和的數(shù)值，對(duì)于不同數(shù)值的，

31、數(shù)據(jù)集合的長(zhǎng)度都以Mb為單位且大致相等.表3：參數(shù)設(shè)置對(duì)比運(yùn)行情況表3給出的6個(gè)虛擬數(shù)據(jù)集的運(yùn)行時(shí)間如圖4所示. 當(dāng)最小支持度降低時(shí)，候選項(xiàng)集和頻繁項(xiàng)集的數(shù)目都增多，因此所有算法的運(yùn)行時(shí)間都延長(zhǎng).觀察圖4可發(fā)現(xiàn)，對(duì)于SETM算法，我們只描繪出他對(duì)數(shù)據(jù)集T15.I2.D100K的運(yùn)行時(shí)間曲線圖，而對(duì)兩個(gè)平均大小為10的事務(wù)的運(yùn)行時(shí)間如表4所示. 不能描繪出與表4相對(duì)應(yīng)的曲線圖是因?yàn)樗倪\(yùn)行時(shí)間跟其他算法的相比太長(zhǎng)了；而對(duì)于另外3個(gè)大小為20的事務(wù)的數(shù)據(jù)集，它的運(yùn)行時(shí)間太長(zhǎng)而不得不對(duì)此運(yùn)行宣告失敗，雖然它的算法是正確的. 很明顯，Apriori算法在大小確定的大數(shù)據(jù)集上運(yùn)行比SETM算法優(yōu)異.圖4

32、：運(yùn)行時(shí)間表4：SETM算法的運(yùn)行時(shí)間（s）Apriori算法在不確定大小的問(wèn)題上運(yùn)行比AIS算法也優(yōu)異，因素范圍可從以2為最大的最小支持度到為低水平的支持度規(guī)定的大小要大的最小支持度. 但AIS算法比SETM算法相對(duì)來(lái)說(shuō)要好. 在數(shù)據(jù)較小的問(wèn)題上，AprioriTid算法與Apriori算法相當(dāng)，可在數(shù)據(jù)較大的問(wèn)題上，前者的運(yùn)行速度要降低一半.分析對(duì)比運(yùn)行情況為了分析這些算法的運(yùn)行過(guò)程，在數(shù)據(jù)集T10.I4.D100K中，令最小支持度為0.75%，在不同算法中，頻繁及候選項(xiàng)集的數(shù)目在運(yùn)算過(guò)程中的變化情況如圖5所示，注意圖中y軸的刻度標(biāo)記.圖5：頻繁及候選集的大小(T10.I4.D100K)S

33、ETM算法的根本性問(wèn)題就在于集合的長(zhǎng)度問(wèn)題，回顧的長(zhǎng)度，它是由計(jì)算得到的. 因此，如果是候選項(xiàng)集支持度的平均數(shù)，則集合大約比對(duì)應(yīng)集合大倍，除非問(wèn)題的大小非常小，否則不得不被寫(xiě)入磁盤，且被存儲(chǔ)兩次，從而導(dǎo)致STEM算法運(yùn)行緩慢，這也就解釋了為什么表4中當(dāng)大小為10的事務(wù)中數(shù)據(jù)集的最小支持度從1.5%變到1.0%時(shí)，SETM算法運(yùn)行時(shí)間就劇增. 在13中為SETM算法設(shè)計(jì)的最大數(shù)據(jù)集遞推性實(shí)驗(yàn)，數(shù)據(jù)仍然太小以致可以放入內(nèi)存中，在運(yùn)行時(shí)間上沒(méi)有發(fā)生這種劇增情況. 值得注意的是，對(duì)于相同大小的最小支持度，候選項(xiàng)集的支持度根據(jù)事務(wù)的數(shù)目呈線性增長(zhǎng). 因此，當(dāng)事務(wù)的數(shù)目增大時(shí)和的數(shù)值也在增大，即使的長(zhǎng)度沒(méi)

34、有改變，的長(zhǎng)度也呈線性增長(zhǎng). 故對(duì)于多個(gè)事務(wù)的數(shù)據(jù)集，SETM算法與其他算法的運(yùn)行效率相比差距會(huì)更大.AIS算法的問(wèn)題在于它在過(guò)程中生成太多的候選集，但計(jì)算結(jié)果的數(shù)目卻很小，導(dǎo)致計(jì)算效率低下. 雖然Apriori算法在第二步也計(jì)算出很多小集合（是的中間產(chǎn)物），但這些中間產(chǎn)物從第三步開(kāi)始就明顯減少了（如圖5所示），之后計(jì)算得到的候選項(xiàng)集幾乎都是頻繁的.AprioriTid算法與SETM算法具有相同的問(wèn)題就是不能太大. 但最后AprioriTid得出的中的項(xiàng)目要比SETM算法的少很多；且它能利用單獨(dú)的存儲(chǔ)一個(gè)候選集，而無(wú)需與候選集中項(xiàng)的數(shù)目相等的來(lái)存儲(chǔ). 另外，與SETM算法不同的是，它不需要存儲(chǔ)

35、，因此就不會(huì)遭受SETM算法保存后的麻煩.AprioriTid算法還有個(gè)很好的特點(diǎn)就是它利用來(lái)代替原始數(shù)據(jù)集，故在的大小變得比數(shù)據(jù)集小之后，運(yùn)行效率非常高. 當(dāng)可以放入內(nèi)存中但頻繁項(xiàng)集的分布隊(duì)列很長(zhǎng)時(shí)，我們會(huì)發(fā)現(xiàn)AprioriTid算法比Apriori算法的性能好；但當(dāng)不能放入內(nèi)存時(shí)，AprioriTid算法在運(yùn)行時(shí)間就會(huì)劇增，像表4中大小為10的事務(wù)中數(shù)據(jù)庫(kù)的最小支持度從0.75%到0.5%的時(shí)間變化，這時(shí)，它就不如Apriori算法了.AprioriHybrid算法不一定在所有的數(shù)據(jù)上只能用同一種方法來(lái)計(jì)算，圖6描繪的是在數(shù)據(jù)集T10.I4.D100K上，過(guò)程中使用AprioriTid和A

36、priori算法的運(yùn)行時(shí)間情況. 在最初掃描時(shí)，Apriori算法比AprioriTid好，而后期掃描時(shí)，情況相反. 我們?cè)谄渌麛?shù)據(jù)庫(kù)中也觀察到類似情形，其主要原因如下：二者的候選集產(chǎn)生過(guò)程和要計(jì)算的項(xiàng)集是相同的；而后期過(guò)程中，候選項(xiàng)集的數(shù)目在減少（觀察圖5中兩種算法的的大?。獳priori算法始終要掃描整個(gè)數(shù)據(jù)庫(kù)，而AprioriTid只需通過(guò)掃描來(lái)獲得支持度數(shù)據(jù)，并且的大小會(huì)變得比數(shù)據(jù)庫(kù)小. 當(dāng)可以放入內(nèi)存時(shí)，我們就不會(huì)遭遇它被寫(xiě)入磁盤的窘境.圖6：Apriori和AprioriTid算法每一步的運(yùn)行時(shí)間（T10.I4.D100K,最小支持度=0.75%）基于這些觀察，我們提出一種混合

37、算法：在最初的數(shù)據(jù)讀取中使用Apriori算法，當(dāng)可以放入內(nèi)存中時(shí)，就切換成AprioriTid，稱這種算法為AprioriHybrid算法. 這里需要估計(jì)的大小. 在一次數(shù)據(jù)庫(kù)掃描結(jié)束時(shí)，就可以得到中候選項(xiàng)集的數(shù)值. 當(dāng)已經(jīng)產(chǎn)生，則可以根據(jù)這來(lái)估計(jì)它的大小，為. 如果在本次掃描中小的可以放入內(nèi)存，且頻繁項(xiàng)集的數(shù)目比前期少，就轉(zhuǎn)向?yàn)锳prioriTid. 增加后面的條件是為了避免本次掃描的可以放入內(nèi)存而下一次掃描的不能.從Apriori到AprioriTid算法的轉(zhuǎn)換也會(huì)有代價(jià). 假設(shè)在第步結(jié)束時(shí)決定轉(zhuǎn)換算法，那么在第（+1）步找到事務(wù)中的候選項(xiàng)集后，還要將它們的加入中（參考2.2章節(jié)描述的A

38、prioriTid算法），因此在這步中與僅調(diào)用Apriori相比就多了一個(gè)額外的步驟，只有在第（+2）步才真正調(diào)用AprioriTid. 假如不存在頻繁(+1)-項(xiàng)集或(+2)-候選集的話，將會(huì)花費(fèi)了時(shí)間去轉(zhuǎn)換卻沒(méi)有得到調(diào)用AprioriTid的任何好處.圖7所描繪的是對(duì)三個(gè)數(shù)據(jù)集合采用AprioriHybrid算法的運(yùn)行情況. 幾乎所有的例子都顯示出AprioriHybrid優(yōu)于Apriori算法，只有對(duì)于支持度為1.5%的數(shù)據(jù)集T10.I2.D100K，AprioriHybrid稍微遜色一些，由于算法的轉(zhuǎn)換過(guò)程發(fā)生在最后一步，沒(méi)有顯出它的優(yōu)勢(shì)所致. 通常AprioriHybrid是否優(yōu)于A

39、priori算法，主要依靠后期過(guò)程中的大小來(lái)決定. 若一直保持增大，直到快結(jié)束時(shí)才變小，則算法轉(zhuǎn)換后僅在短時(shí)間內(nèi)調(diào)用AprioriTid，速度還是會(huì)突然下降，所以AprioriHybrid算法就不能顯示出它的優(yōu)勢(shì). 這也是數(shù)據(jù)集T20.I6.D100K發(fā)生那種情況的原因. 但如果的大小在逐漸減小，AprioriTid算法在轉(zhuǎn)換后還能運(yùn)行一段時(shí)間的話，運(yùn)行效率就會(huì)獲得顯著提高.圖7：AprioriHybrid的運(yùn)行時(shí)間按比例增大實(shí)驗(yàn)圖8描繪的是隨著事務(wù)大小從100,000增大到10,000,000時(shí)，AprioriHybrid算法的運(yùn)行時(shí)間變化情況，聯(lián)立(T5.I2)，(T10.I4)和(T20

40、.I6)，分別取事務(wù)及項(xiàng)集大小的平均數(shù)，所有其他參數(shù)值同表3，大小為10,000,000的事務(wù)中數(shù)據(jù)集大小分別為239MB，439MB和838MB，設(shè)最小支持度為0.75%. 運(yùn)行時(shí)間的規(guī)格主要體現(xiàn)在以下兩個(gè)方面：第一幅圖中大小為100,000的事務(wù)中數(shù)據(jù)集的運(yùn)行時(shí)間和第二副圖中大小為1,000,000的事務(wù)中數(shù)據(jù)集的運(yùn)行時(shí)間. 如圖所示，運(yùn)行時(shí)間近似于線性增長(zhǎng).圖8：增大事務(wù)數(shù)目接下來(lái)，我們來(lái)探究AprioriHybrid是如何隨著項(xiàng)目的數(shù)量增多而按比例增長(zhǎng)的. 把三個(gè)參數(shù)設(shè)置為T5.I2.D100K，T10.I4.D100K和T20.I6.D100K的數(shù)據(jù)集中項(xiàng)目的數(shù)量從1000增到10,

41、000，其余參數(shù)值同表3，設(shè)最小支持度為0.75%. 運(yùn)行實(shí)驗(yàn)后，得到的結(jié)果如圖9所示，當(dāng)項(xiàng)目的數(shù)量增多，項(xiàng)目的平均支持度下降，從而運(yùn)行時(shí)間也減少. 把這個(gè)結(jié)果運(yùn)用到稍微大點(diǎn)的項(xiàng)集時(shí)，運(yùn)行的效率更高了.最后，我們來(lái)研究當(dāng)增大事務(wù)的平均大小時(shí)的按比例遞增情況. 實(shí)驗(yàn)的目的是為了觀察數(shù)據(jù)結(jié)構(gòu)是如何隨著事務(wù)大小改變的，不依賴于其他任何因素，如數(shù)據(jù)庫(kù)本身大小，頻繁項(xiàng)集的數(shù)目. 通過(guò)保持事務(wù)的平均大小及數(shù)目的結(jié)果不變從而保持?jǐn)?shù)據(jù)庫(kù)的本身大小基本不變，事務(wù)的數(shù)目范圍而從平均大小為5的事務(wù)中含200,000個(gè)數(shù)據(jù)庫(kù)到平均大小為50的事務(wù)中含20,000個(gè)數(shù)據(jù)庫(kù)，固定最小支持度不變，隨著事務(wù)大小的擴(kuò)大，頻繁項(xiàng)

42、集的數(shù)目也按比例增長(zhǎng)，只要事務(wù)中的項(xiàng)集存在的概率與事務(wù)大小大致成比例. 為此，以事務(wù)的數(shù)目固定項(xiàng)的最小支持度水平，結(jié)果如圖10所示，圖中的數(shù)字（如500）代表最小支持度. 由圖可得，運(yùn)行時(shí)間隨著事務(wù)大小的增大而逐步地延長(zhǎng). 延長(zhǎng)的主要原因是頻繁項(xiàng)集的數(shù)目在隨著事務(wù)大小增大而增大，盡管以事務(wù)的數(shù)目設(shè)定了項(xiàng)的最小支持度. 另外，在當(dāng)前事務(wù)中找出候選集需要花一定的時(shí)間.圖9：增大項(xiàng)的數(shù)目 圖10：增大事務(wù)大小總結(jié)與工作前景在本文中我們提出了兩種新的算法：Apriori和AprioriTid算法，用于在事務(wù)中大量數(shù)據(jù)庫(kù)的項(xiàng)目?jī)?nèi)找出所有有意義的關(guān)聯(lián)規(guī)則；并且把這兩種算法與先前已知的AIS和STEM算法進(jìn)

43、行比較，用實(shí)驗(yàn)結(jié)果證明這兩種算法總是優(yōu)于AIS和STEM算法. 它們之間的差距還會(huì)隨著問(wèn)題范圍大小的增大而增大.同時(shí)我們還展現(xiàn)了把這兩種算法合并形成一種混合算法AprioriHybrid算法的優(yōu)點(diǎn)，在以后將會(huì)成為求解問(wèn)題的精選算法. 按比例增大證明了AprioriHybrid隨著事務(wù)數(shù)目的增長(zhǎng)呈線性增長(zhǎng)，另外，運(yùn)行時(shí)間也會(huì)隨著數(shù)據(jù)庫(kù)中項(xiàng)目數(shù)量的增多而縮短. 如果事務(wù)大小的平均數(shù)在增大（保持?jǐn)?shù)據(jù)庫(kù)大小不變），運(yùn)行時(shí)間也逐步地延長(zhǎng). 這些實(shí)驗(yàn)還證明了在實(shí)際應(yīng)用程序中，對(duì)引入的大數(shù)據(jù)庫(kù)采用AprioriHybrid算法的可行性.本文中提到的算法已經(jīng)在多個(gè)數(shù)據(jù)倉(cāng)庫(kù)中得到實(shí)行，包括AIX文本系統(tǒng)，DB2

44、/MVS，及DB2/6000. 我們還把測(cè)試算法的結(jié)果與真實(shí)的顧客數(shù)據(jù)相比較. 具體過(guò)程可參考5. 以后，我們計(jì)劃在以下范圍內(nèi)擴(kuò)展對(duì)此算法的運(yùn)用：項(xiàng)目的多重分類（組合）. 如洗碗機(jī)是一種廚房器具，又是一種電子設(shè)備等. 我們就可以根據(jù)這樣的組合來(lái)找出關(guān)聯(lián)規(guī)則.我們從未考慮進(jìn)入事務(wù)的項(xiàng)目數(shù)量，而這個(gè)在很多應(yīng)用程序上是十分有用的. 找出這樣的規(guī)則就需要我們以后的工作發(fā)展.本文中所得出的成果已經(jīng)成為IBM Almaden Research Center的研究課題，主要探索數(shù)據(jù)庫(kù)挖掘的多方面問(wèn)題. 除了找出關(guān)聯(lián)規(guī)則問(wèn)題之外，還要調(diào)查在時(shí)間順序上根據(jù)不同疑問(wèn)和類似疑問(wèn)來(lái)提高數(shù)據(jù)庫(kù)的容量等. 我們相信數(shù)據(jù)庫(kù)

45、挖掘是數(shù)據(jù)庫(kù)上的一塊新的重要的應(yīng)用領(lǐng)域，可以激起人們的好奇心結(jié)合商業(yè)利益來(lái)研究問(wèn)題.致謝：我們十分感謝Mike Carey具有洞察力的評(píng)論與建議.參考文獻(xiàn)：R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In Proc. of the Fourth International Conference on Foundations of Data Organization and Algorithms, Chicago, October 1993.R. Agrawa

46、l, S. Ghosh, T. Imielinski, B. Iyer, and A. Swami. An interval classier for database mining applications. InProc. of the VLDB Conference, pages 560-573, Vancouver, British Columbia Canada, 1992.R. Agrawal, T. Imielinski, and A. Swami. Database mining: A performance perspective. IEEE Transactions on

47、Knowledge and Data Engineering, 56:914-925, December 1993. Special Issue on Learning and Discovery in Knowledge-Based Databases.R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proc. of the ACM SIGMOD Conference on Management of Data, Wan

48、shington, D.C., May 1993.R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. Research Report RJ 9839, IBM Almaden Research Center, San Jose, California, June 1994.D. S. Associates. The new direct marketing. Business One Irwin, Illinois, 1990.R. Brachman et al.

49、 Integrated support for data archeology. In AAAI-93 Workshop on Knowledge Discovery in Databases, July 1993.L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, 1984.P. Cheeseman et al. Autoclass: A Bayesian classification system. In 5th Intl Conf. on Machine Learning. Morgan Kaufman, June 1988.D. H. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning,