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

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

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

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

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

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

6、規(guī)則的發(fā)現(xiàn)19，學習邏輯定義18，函數(shù)的數(shù)據(jù)擬合15以及簇9,10. 非公開性的有關機器學習文獻的作品是在20中的KID3算法. 如果應用在查找所有關聯(lián)規(guī)則問題上，這個算法在與假定關聯(lián)項的數(shù)目一樣多的數(shù)據(jù)上進行運算時，運算量非常大. 最近在數(shù)據(jù)庫上的研究工作是由數(shù)據(jù)出發(fā)來定義關聯(lián)函數(shù)16. 函數(shù)關聯(lián)規(guī)則需要十分嚴格的條件. 因此，定義一種函數(shù)規(guī)則為后,在16中描述的算法若從規(guī)則來考慮，就無法推出. 我們考慮的這些關聯(lián)規(guī)則要符合實際性質(zhì). 規(guī)則的存在并不意味著也成立，因為后者可能不具備最小支持度. 同樣的，規(guī)則和的存在也不意味著成立，因為后者可能也不具備最小置信度.曾有一個關于測定“有用性”或“

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

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

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

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

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

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

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

14、數(shù)Apriori-gen實現(xiàn)的，該函數(shù)返回的是所有頻繁-項集的超集，其計算過程如下：第一步，鏈接，把與自己鏈接：insert into select ,from , Where =, =, ;第二步，剪枝，如果項集但中的(-1)-項子集不屬于，則: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. 通過鏈接步， =1 2 3 4，1 3 4 5，剪枝步會刪除1 3 4 5，因為1 4 5不屬于，所以最后=1 2 3 4.把這里產(chǎn)生候選集的

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

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

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

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

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

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

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

22、記錄，因為他們不包含中的任何項集. 于是中的候選項集2 3 5就證明是最大的，且是唯一的元素. 當用生成時，結果為空，那么計算結束.數(shù)據(jù)結構我們給每個候選項集分配一個唯一的號碼，稱為. 每個候選項集都按隊列保存，則指針可通過來查找項集. 中的每個元素都以形式存在且每個都存儲在連續(xù)的結構中.通過鏈接兩個頻繁(-1)-項集并運用Apriori-gen函數(shù)來產(chǎn)生一個候選-項集，我們?yōu)槊總€候選項集設定兩個附加域：i)初始域；ii)擴展域. 初始域存儲著產(chǎn)生的兩個頻繁(-1)-項集的，而擴展域存儲著所有由的擴展而成的(+1)-項候選集的. 因此，如果候選集是由和產(chǎn)生的，那么初始域中存儲著和的，同時，把的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45、挖掘是數(shù)據(jù)庫上的一塊新的重要的應用領域，可以激起人們的好奇心結合商業(yè)利益來研究問題.致謝：我們十分感謝Mike Carey具有洞察力的評論與建議.參考文獻：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,