關(guān)聯(lián)規(guī)則挖掘研究綜述

1、    關(guān)聯(lián)規(guī)則挖掘研究綜述        劉東波1,2 盧正鼎1 時間:2007年08月20日     字 體: 大 中 小        關(guān)鍵詞:<"cblue" " target='_blank'>關(guān)聯(lián)規(guī)則<"cblue" " target='_bla

2、nk'>關(guān)聯(lián)規(guī)則挖掘<"cblue" " target='_blank'>數(shù)據(jù)挖掘<"cblue" " target='_blank'>最大<"cblue" " target='_blank'>I/O            摘要：本文首先回顧了<"cblue" &q

3、uot; title="關(guān)聯(lián)規(guī)則">關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展情況，然后對關(guān)聯(lián)規(guī)則問題進(jìn)行了形式化描述，最后討論了<"cblue" " title="關(guān)聯(lián)規(guī)則挖掘">關(guān)聯(lián)規(guī)則挖掘的處理流程和主要算法。?關(guān)鍵詞：<"cblue" " title="數(shù)據(jù)挖掘">數(shù)據(jù)挖掘? 關(guān)聯(lián)規(guī)則? 支持度? 可信度?關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中挖掘出隱含的、先前未知的、對決策有潛在價值的知識和規(guī)則的高級處理過程1,2。通過數(shù)據(jù)挖掘，有價值的知識、規(guī)則或高

4、層次的信息就能從數(shù)據(jù)庫的相關(guān)數(shù)據(jù)集合中抽取出來，并從不同角度展現(xiàn)，從而使大型數(shù)據(jù)庫作為一個豐富、可靠的資源為知識的提取服務(wù)。?R. Agrawal等人在1993年首先提出在交易數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則3，典型的例子是“多數(shù)顧客在購買面包和黃油的同時也會購買牛奶”，找出所有這類規(guī)則，對于確定市場策略是很有價值的，例如可用于追加銷售、倉儲規(guī)劃，并可根據(jù)購買模式對顧客進(jìn)行劃分。?AIS算法是第一個發(fā)表的生成事務(wù)數(shù)據(jù)庫中所有大項(xiàng)目集的算法3。它集中在增強(qiáng)數(shù)據(jù)庫必要的功能以支持決策支持查詢。該算法的目標(biāo)是發(fā)現(xiàn)定性規(guī)則。該技術(shù)的局限性是結(jié)論中只有一個項(xiàng)目。即關(guān)聯(lián)規(guī)則是形如XTIj | a的規(guī)則，其中X是一個項(xiàng)

5、目集合，Ij是值域I中的單個項(xiàng)目，a是規(guī)則的置信度。?AIS算法要對整個數(shù)據(jù)庫進(jìn)行多次分析。每次分析都要掃描全部事務(wù)。第一次分析計(jì)算數(shù)據(jù)庫中單個項(xiàng)目的支持度，并確定哪個是大或頻繁項(xiàng)目集。對每次分析的大項(xiàng)目集進(jìn)行擴(kuò)展以生成候選項(xiàng)目集。掃描一個事務(wù)之后，可確定上一次分析的大項(xiàng)目集和該事務(wù)項(xiàng)目的公共項(xiàng)目集。這些公共項(xiàng)目集被該事務(wù)中的其它項(xiàng)目擴(kuò)展，生成新的候選項(xiàng)目集。大項(xiàng)目集l只能由在當(dāng)前事務(wù)中的大項(xiàng)目并且按照詞典順序位于l中所有項(xiàng)目之后的項(xiàng)目。為了高效地完成該任務(wù)，它采用了一種評估工具和剪枝技術(shù)。該評估和剪枝技術(shù)通過刪除候選集合中不必要的項(xiàng)目集來確定最終的候選集合。然后計(jì)算每個候選集合的支持度。支持

6、度大于等于最小支持度閾值的候選集合被選出作為大項(xiàng)目集。這些大項(xiàng)目集繼續(xù)被擴(kuò)展以生成下一次分析的候選集合。直到不能發(fā)現(xiàn)更多大項(xiàng)目集時該處理過程結(jié)束。?STEM算法在4中提出，其目的是用SQL來處理候選大項(xiàng)目集5。在該算法中，大項(xiàng)目集組成的集合的每個成員形如，其中TID是事務(wù)的唯一標(biāo)識符。類似地，候選項(xiàng)目集組成的集合的每個成員形如。與AIS算法類似，SETM算法也要多次分析數(shù)據(jù)庫。?Apriori是對AIS和SETM算法的改進(jìn)，并且是第一個可擴(kuò)展的關(guān)聯(lián)規(guī)則挖掘算法2,6。當(dāng)進(jìn)行初始數(shù)據(jù)庫掃描時Apriori算法搜索大項(xiàng)目集合，然后用該搜索結(jié)果作為后續(xù)掃描并發(fā)現(xiàn)其它達(dá)數(shù)據(jù)集合的種子。支持度大于給定最

7、小值的規(guī)則稱為大項(xiàng)目集（large itemsets）頻繁項(xiàng)目集（frequent itemsets），支持度小于給定最小值規(guī)則稱為小項(xiàng)目集（small itemsets）7。?簡而言之，給定一個數(shù)據(jù)集合，Apriori算法需要通過初始掃描整個數(shù)據(jù)集合產(chǎn)生一個支持度不小于指定最小值的項(xiàng)目集合。生成該項(xiàng)目集合（稱為1-候選集合）之后，再形成下一個候選集合（稱為2-候選集合）。再次掃描數(shù)據(jù)庫來計(jì)算2-候選集合的支持度。所有支持度小于最小值的集合將被剪裁掉。當(dāng)不再生成新的候選集合時算法終止，得到k-候選集合。?該算法基于頻繁項(xiàng)目集合的性質(zhì)，即一個頻繁集合的任何子集都是頻繁集合；如果一個項(xiàng)目集合不是頻

8、繁集合，其所有超集均不是頻繁集合8。?有一些Apriori算法的變型，如AprioriTID和AprioriHybrid。AprioriTID的工作原來與Apriori類似，所不同的是它用生成的項(xiàng)目集合計(jì)算支持度，取代了通過數(shù)據(jù)庫掃描計(jì)算支持度的方法。據(jù)報道，只有當(dāng)AprioriTID生成的項(xiàng)目集合能夠放在內(nèi)存時，AprioriTID才比Apriori效率更高。AprioriHybrid是Apriori和AprioriTID的混合體。該算法用Apriori進(jìn)行初始掃描，一旦認(rèn)為生成的集合能夠與內(nèi)存匹配則切換到AprioriTID算法。在大多數(shù)情況下AprioriHybrid算法比Apriori

9、算法效率高，但是當(dāng)進(jìn)行到最后一次掃描時是個例外。這是因?yàn)樗ㄙM(fèi)了過高的代價獲取無意義的項(xiàng)目。Apriori算法比其它一些算法（如SETM和AIS）更有效6,9。?此后，研究人員對關(guān)聯(lián)規(guī)則挖掘問題進(jìn)行了深入的研究，通過引入隨機(jī)采樣和并行挖掘等思想，對原有算法進(jìn)行了優(yōu)化，以提高挖掘算法的執(zhí)行效率。?J. S. Park等人指出，Apriori算法的計(jì)算開銷主要在頻繁2項(xiàng)目集的計(jì)算上，因此提出了基于Hash技術(shù)對生成的候選2項(xiàng)目集進(jìn)行裁剪的DHP算法10。Apriori算法和DHP算法掃描數(shù)據(jù)庫的次數(shù)是和<"cblue" " title="最大"

10、;>最大頻繁項(xiàng)目集的長度一致的，但是對大型數(shù)據(jù)庫系統(tǒng)一次數(shù)據(jù)庫掃描的代價是非常昂貴的，所以數(shù)據(jù)庫掃描的次數(shù)成為關(guān)聯(lián)規(guī)則挖掘算法的一個主要的瓶頸問題。?A. Savasere等人提出了分區(qū)（Partition）算法11，該算法將數(shù)據(jù)庫掃描的次數(shù)降為兩次。Partition算法邏輯上將數(shù)據(jù)庫劃分為互不相交的若干個區(qū)，算法首先找出每個分區(qū)中的局部頻繁項(xiàng)目集，然后根據(jù)“頻繁項(xiàng)目集至少在一個分區(qū)中是頻繁的”這一性質(zhì)，合并所有的局部頻繁項(xiàng)目集，最后對合并后所有的局部頻繁項(xiàng)目集進(jìn)行全局計(jì)數(shù)，得到全局頻繁項(xiàng)目集。?H. Toivonen等人提出了基于采樣的關(guān)聯(lián)規(guī)則挖掘算法12，該算法通過數(shù)據(jù)庫的一個隨機(jī)

11、采樣數(shù)據(jù)生成候選頻繁項(xiàng)目集，然后掃描整個數(shù)據(jù)庫對其進(jìn)行驗(yàn)證。基于采樣的算法多數(shù)情況下只需掃描一次數(shù)據(jù)庫，最壞的情況下也只需兩次掃描，但該算法所獲得的高效率是以犧牲挖掘精度來換取的，有可能丟失一些全局頻繁項(xiàng)目集。?為了進(jìn)一步提高算法的有效性，S. Brin等人提出了動態(tài)項(xiàng)目集計(jì)數(shù)（DIC）算法13，該算法將數(shù)據(jù)庫劃分為若干分區(qū)并且對每個分區(qū)的開始做標(biāo)記，不同于Apriori算法的是，在數(shù)據(jù)庫掃描過程中，DIC算法可以在各個分區(qū)的標(biāo)記點(diǎn)添加候選項(xiàng)目集，而不是像Apriori那樣只能在每次完成整個數(shù)據(jù)庫掃描之后添加候選項(xiàng)目集，這樣便極大地減少了數(shù)據(jù)庫掃描次數(shù)。?J. Han等人提出了一種無需生成候選

12、頻繁項(xiàng)目集的算法FP-Growth（頻繁模式增長算法）14，該算法首先將數(shù)據(jù)庫壓縮成一個高度濃縮的數(shù)據(jù)結(jié)構(gòu)FP樹，隨后發(fā)現(xiàn)頻繁項(xiàng)目集的工作都在該FP樹上完成，這樣就避免了多次數(shù)據(jù)庫掃描。另外，F(xiàn)P-Growth算法直接在FP樹上發(fā)現(xiàn)頻繁項(xiàng)目集，避免了產(chǎn)生數(shù)目龐大的候選頻繁項(xiàng)目集，因此FP-Growth算法較Apriori算法的效率有一個量級的提高。?Ei-Hajj等人提出了一種基于反轉(zhuǎn)矩陣（Inverted Matrix）的算法15，它類似于FP-Growth算法，該算法首先將數(shù)據(jù)庫映射為一個基于磁盤的反轉(zhuǎn)矩陣，然后針對該反轉(zhuǎn)矩陣在內(nèi)存中建立COFI（Co-Ocurrence Frequent

13、 Item）樹，利用COFI樹發(fā)現(xiàn)頻繁項(xiàng)目集。實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于Apriori和FP-Growth，對于超大規(guī)模數(shù)據(jù)庫和較小支持度的情況，優(yōu)勢更加明顯。另外，反轉(zhuǎn)矩陣的結(jié)構(gòu)特點(diǎn)決定了它便于實(shí)現(xiàn)并行挖掘算法。?除了上述基本關(guān)聯(lián)規(guī)則挖掘算法研究，人們還進(jìn)行了諸如多層關(guān)聯(lián)規(guī)則、量化關(guān)聯(lián)規(guī)則、基于約束的關(guān)聯(lián)規(guī)則、時態(tài)關(guān)聯(lián)規(guī)則、空間關(guān)聯(lián)規(guī)則等類型關(guān)聯(lián)規(guī)則挖掘算法的研究。?Srikant和Agrawal從廣義關(guān)聯(lián)規(guī)則挖掘的角度研究了多層關(guān)聯(lián)規(guī)則挖掘問題16，多層關(guān)聯(lián)規(guī)則挖掘利用概念分層的背景知識在更高的抽象層次上挖掘關(guān)聯(lián)規(guī)則，從而解決了稀疏數(shù)據(jù)中關(guān)聯(lián)規(guī)則的支持度閾值過低而難以挖掘的問題。?Srika

14、nt等人通過將數(shù)值型數(shù)據(jù)劃分為不同區(qū)間的方法，在這些區(qū)間之上進(jìn)行定量關(guān)聯(lián)規(guī)則的挖掘17。?為了克服Agrawal頻集方法的缺陷，人們還提出了一些新的關(guān)聯(lián)規(guī)則挖掘方法18,19,20,21,22,23,24。?關(guān)聯(lián)規(guī)則問題描述本節(jié)給出關(guān)聯(lián)規(guī)則挖掘問題的形式描述。?定義2.1 令I(lǐng) = I1, I2, , Im是由m個不同項(xiàng)目（Items）組成的集合，D是由事務(wù)T組成的集合（數(shù)據(jù)庫），這里事務(wù)T是項(xiàng)目的集合，并且T í I。其中，每個事務(wù)T有一個唯一標(biāo)識，記為TID。關(guān)聯(lián)規(guī)則是形如XTY的蘊(yùn)涵式，其中X í ?I，Y í ?I，而且X ?Y = f。這里，X 稱為前提

15、，Y 稱為結(jié)論。?下面定義關(guān)聯(lián)規(guī)則的兩個重要測度：支持度S（Support）和可信度C（Confidence）。?定義2.2 關(guān)聯(lián)規(guī)則XTY在事務(wù)集合D中的支持度是?S(XTY) = |T: XèYíT, T?D| / |D|?其中，|T: XèYíT, T?D|是D中包含X和Y的事務(wù)數(shù)，|D|是D中所有事務(wù)數(shù)。?定義2.3 關(guān)聯(lián)規(guī)則XTY在事務(wù)集合D中的可信度是?C(XTY) = |T: XèYíT, T?D| / |T: XíT，T?D|?其中，|T: XèYíT, T?D|是包含X和Y的事務(wù)數(shù)，|T

16、: XíT，T?D|是包含X的事務(wù)數(shù)。?給定一個事務(wù)集合（數(shù)據(jù)庫）D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度Smin和最小可信度Cmin的關(guān)聯(lián)規(guī)則。?關(guān)聯(lián)規(guī)則挖掘算法經(jīng)典頻繁集合方法?Agrawal等人1993年3首先提出挖掘顧客交易數(shù)據(jù)庫中項(xiàng)目集之間關(guān)聯(lián)規(guī)則的問題，這是一種基于頻繁集合理論的遞推方法，它將關(guān)聯(lián)規(guī)則挖掘算法分解為兩個步驟：?1. 找到所有支持度大于最小支持度Smin的項(xiàng)目集合（Itemsets），這些項(xiàng)集稱為頻繁集合（Frequent Itemsets)；?2. 使用第1步找到的頻繁集合產(chǎn)生期望的規(guī)則。?如給定了一個頻繁集合Y=I1I2.I

17、k，k32，IjI，產(chǎn)生只包含集合I1，I2，.，Ik中項(xiàng)目的所有規(guī)則（最多k個），其中每一個規(guī)則的右部只有一項(xiàng)，(即形如Y-IiTIi，'1ik)，這里采用的是13中規(guī)則的定義。一旦生成了這些規(guī)則，只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。對于規(guī)則右部含兩個以上項(xiàng)目的規(guī)則，我們將在后面討論。?為了生成所有頻繁集合，使用了遞推的方法。其核心算法如下：?(1)? L1 = large 1-itemsets;?(2)? for (k=2; Lk-11F; k+) do begin?(3)? ? Ck=apriori-gen(Lk-1);? /新的候選集?(4)? ? for all

18、 transactions t?D do begin?(5)? ? ?Ct=subset(Ck, t);? /事務(wù)t中包含的候選集?(6)? for all candidates c? Ct do?(7)? c.count+;?(8)? ? end?(9)? Lk=c? Ck |c.count 3 Smin?(10)? end?(11)? Answer = èkLk;?首先產(chǎn)生頻繁1-項(xiàng)目集L1，然后是頻繁2-項(xiàng)目集L2，直到有某個r值使得Lr為空，這時算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項(xiàng)目集的集合Ck，Ck中的每一個項(xiàng)目集是對兩個只有一個項(xiàng)不同的屬于Lk-1的頻繁集合

19、做一個(k-2)-連接來產(chǎn)生的。Ck中的項(xiàng)目集是用來產(chǎn)生頻繁集合的候選集，最后的頻繁集合Lk必須是Ck的一個子集。Ck中的每個元素需在事務(wù)數(shù)據(jù)庫中進(jìn)行驗(yàn)證來決定其是否加入Lk，這里的驗(yàn)證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的事務(wù)數(shù)據(jù)庫，即如果頻繁集合最多包含10個項(xiàng)目，那么就需要掃描事務(wù)數(shù)據(jù)庫10遍，這需要很大的<"cblue" " title="I/O">I/O開銷。?在文獻(xiàn)25中，Agrawal等人用剪枝技術(shù)（Pruning）來減小候選集Ck的大小，由此可以顯著地改進(jìn)生成所有頻繁集合算法的性能。算法中引入的剪枝

20、策略基于這樣一個性質(zhì)：一個項(xiàng)目集是頻繁集合當(dāng)且僅當(dāng)它的所有子集都是頻繁集合。那么，如果Ck中某個候選項(xiàng)目集合有一個(k-1)-子集不屬于Lk-1，則這個項(xiàng)目集可以被剪掉不再被考慮，這個剪枝過程可以降低計(jì)算所有的候選集合的支持度的代價。文獻(xiàn)25中還引入了雜湊樹（Hash Tree）方法來有效地計(jì)算每個項(xiàng)目集的支持度。?頻繁集合算法的幾種優(yōu)化方法?雖然Apriori算法自身已經(jīng)進(jìn)行了一定的優(yōu)化，但是在實(shí)際應(yīng)用中還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化方法。?1.?劃分方法Savasere等11設(shè)計(jì)了一個基于劃分（partition）的算法，該算法先把數(shù)據(jù)庫從邏輯上分成幾個互不相交的塊，

21、每次單獨(dú)考慮一個分塊并對它生成所有的頻繁集合，然后把產(chǎn)生的頻繁集合合并，用來生成所有可能的頻繁集合，最后計(jì)算這些項(xiàng)目集的支持度。這里，分塊的大小要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻繁集合至少在某一個分塊中是頻繁集合保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個處理器生成頻繁集合。產(chǎn)生頻繁集合的每一個循環(huán)結(jié)束后，處理器之間進(jìn)行通信來產(chǎn)生全局的候選k-項(xiàng)目集。通常這里的通信過程是算法執(zhí)行時間的主要瓶頸；而另一方面，每個獨(dú)立的處理器生成頻繁集合的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來產(chǎn)生頻繁集合。其它

22、關(guān)于生成頻繁集合的并行方法詳見10,26。?2. Hash方法Park等10提出了一種基于雜湊（Hash）方法的算法，可以高效產(chǎn)生頻繁集合。通過實(shí)驗(yàn)我們可以發(fā)現(xiàn)尋找頻繁集合主要的計(jì)算是在生成頻繁2-項(xiàng)目集Lk上，Park等就是利用了這個性質(zhì)引入雜湊技術(shù)來改進(jìn)產(chǎn)生頻繁2-項(xiàng)目集的方法。?3. 采樣方法基于前一遍掃描得到的信息，對此仔細(xì)地進(jìn)行組合分析，可以得到一個改進(jìn)的算法，Mannila等27首先考慮到這一點(diǎn)，認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑。隨后又由Toivonen12進(jìn)一步發(fā)展了這個思想，先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個數(shù)據(jù)庫中可能成立的規(guī)則，然后對數(shù)據(jù)庫的剩余部分驗(yàn)證這個結(jié)果。

23、Toivonen的算法相當(dāng)簡單并顯著地降低了I/O開銷，但該算法最大的缺點(diǎn)是產(chǎn)生的結(jié)果不精確，存在所謂的數(shù)據(jù)扭曲(Data Skew)。分布在同一頁面上的數(shù)據(jù)通常是高度相關(guān)的，可能不能表示整個數(shù)據(jù)庫中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價可能同掃描一遍數(shù)據(jù)庫相近。Lin和Dunham在28中討論了反扭曲(Anti-skew)算法來挖掘關(guān)聯(lián)規(guī)則，在那里他們引入的技術(shù)使得掃描數(shù)據(jù)庫的次數(shù)少于2次。?Brin等13提出的算法使用比傳統(tǒng)算法少的掃描遍數(shù)來發(fā)現(xiàn)頻繁集合，同時比基于采樣的方法使用更少的候選集，這些改進(jìn)了算法在低層的效率。具體的考慮是，在計(jì)算k-項(xiàng)目集時，一旦認(rèn)為某個(k+

24、1)-項(xiàng)目集可能是頻繁集合，就并行地計(jì)算該(k+1)-項(xiàng)目集的支持度，算法所需的總的掃描次數(shù)通常少于最大頻繁集合的項(xiàng)目數(shù)。?4.?減少事務(wù)個數(shù)減少用于未來掃描的事務(wù)集合的大小。一個基本的原理就是當(dāng)一個事務(wù)不包含長度為k的大項(xiàng)目集，則必然不包含長度為k+1的大項(xiàng)目集。從而我們就可以將這些事務(wù)刪掉，這樣在下一遍的掃描中就可以減少事務(wù)的個數(shù)。?其它頻繁集合挖掘方法?前面介紹的都是基于Apriori的頻繁集合方法。即使進(jìn)行了優(yōu)化， Apriori方法固有的缺陷仍然無法克服。?（1）Apriori可能產(chǎn)生大量的候選集。當(dāng)長度為1的頻繁集合有10000個時，長度為2的候選集個數(shù)將會超過10M。另外，如果要

25、生成一個很長的規(guī)則，產(chǎn)生的中間元素的數(shù)量也是巨大的。?（2）Apriori無法對稀有信息進(jìn)行分析。由于頻繁集合使用了參數(shù)Smin（最小支持度），所以就無法對小于Smin的事件進(jìn)行分析；而如果將Smin設(shè)成一個很低的值，那么算法的效率就會很低。?下面介紹兩種方法，分別用來解決上述兩個問題。?文獻(xiàn)14提到了一種解決問題（1）的FP-growth方法。該方法采用分而治之的策略：在經(jīng)過第一次掃描之后，把數(shù)據(jù)庫中的頻繁集合壓縮進(jìn)一棵頻繁模式樹（FP-tree），同時依然保留其中的關(guān)聯(lián)信息。隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻繁集合相關(guān)。然后再對這些條件庫分別進(jìn)行挖掘。當(dāng)原始數(shù)

26、據(jù)量很大的時候，也可以結(jié)合劃分的方法，使得一個FP-tree可以放入主存中。實(shí)驗(yàn)表明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時在效率上較之Apriori算法有巨大的提高。?文獻(xiàn)29中介紹了一種解決問題（2）的方法。該方法基于這樣的思想：Apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但在實(shí)際應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在Apriori算法中，起決定作用的是支持度，而我們現(xiàn)在把可信度放在第一位，挖掘一些具有高可信度的規(guī)則。?整個算法大致分成計(jì)算特征、生成候選集、過濾候選集三個步驟。在這三個步驟中，關(guān)鍵是在計(jì)算特征時Hash方法的使用。在考慮

27、算法的時候，有幾個衡量好壞的指標(biāo)：時空效率、錯誤率和遺漏率。?基本的方法有兩類：?（1）Min_Hashing的基本思想是，將一條記錄中的頭k個為1的字段的位置作為一個Hash函數(shù)。該方法的遺漏率為零，錯誤率可以由k嚴(yán)格控制，但是時空效率相對較差。?（2）Locality_Sentitive_Hashing的基本思想是，將整個數(shù)據(jù)庫用一種基于概率的方法進(jìn)行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。該算法的遺漏率和錯誤率是無法同時降低的，但它的時空效率卻比較高。?結(jié)束語本文回顧了關(guān)聯(lián)規(guī)則挖掘研究的進(jìn)展情況，對關(guān)聯(lián)規(guī)則問題進(jìn)行了形式化描述，最后總結(jié)了關(guān)聯(lián)規(guī)則挖掘的處理流程

28、和主要算法。?參考文獻(xiàn)1 BERRY, M.J. and LINOFF, G. Data Mining Techniques. John Wiley & Sons, New York. 1997.?2 U. M.Fayyad，G. Piatesky-Shapiro，P. Smyth，and R. Uthurusamy Eds. Advances in Know<"innerlink" " title="led">ledge Discovery and Data Mining. AAAI/MIT Press，1996.?3 R

29、. Agrawal, T. Imielinski and A. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proc. 1993 ACM-SIGMOD Int. Conf. Management of Data, Washington, D.C., pages 207216, May 1993.?4 M. Houtsma and A. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Pr

30、oceedings of the 11th IEEE International Conference on Data Engineering, pp. 25-34, Taipei, Taiwan, March 1995.?5 R. Srikant, Fast Algorithms for Mining Association Rules and Sequential Patterns, Ph.D Dissertation, 1996, University of Wisconsin, Madison.?6 R. Agrawal and R. Srikant. Fast algorithms

31、for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases，pages 487-499，Santiago，Chile，September 1994.?7 M. Chen, J. Han and P. Yu. Data mining: An overview from database perspective. IEEE Transactions on Knowledge and Data Eng., pages 866883, December 1996.?8 J. W. Han，Y. Cai and

32、N. Cercone. Knowledge Discovery in Databases: an Attribute-Oriented Approach. Proc. of 18th VLDB，1992:547-559, 1992.?9 J. Hipp, U. Guntzer, and G. Nakaeizadeh. Algorithms for Association Rule Mining - A General Survey and Comparison. In Proc. ACM SIGKDD International Conference on Knowledge Discover

33、y and Data Mining, pages 5864, July 2000.?10 J. S. Park，M. S. Chen，and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data，pages 175-186，San Jose，CA，May 1995.?11 A. Savasere，E. Omiecinski，and S. Navathe. A

34、n efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very large Database，1995.?12 H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database，Bombay，India，Se

35、ptember 1996.?13 S. Brin，R. Motwani，J. D. Ullman，and S. Tsur. Dynamic Itemset counting and implication rules for market basket data. In ACM SIGMOD International Conference On the Management of Data. 1997.?14 J. Han，J. Pei，and Y. Yin.Mining frequent patterns without candidate generation.In Proc.2000

36、ACM-SIGMOD Int.Conf.Management of Data(SIGMOD00)，Dalas，TX，May 2000.?15 Mohammad Ei-Hajj, Osmar R. Za?ane. Inverted Matrix Efficient Discovery of Frequent Items in Large Datasets in the Context of Interactive Mining. SIGKDD03 Washington DC, USA, 2003.?16 R. Srikant，and R. Agrawal. Mining generalized

37、association rules. Proceedings of the 21st International Conference on Very Large Database，1995，pp. 407-419.?17 R. Srikant，and R. Agrawal. Mining quantitative association rules in large relational tables.? Proceedings of the ACM SIGMOD Conference on Management of Data，1996. pp.1-12.?18 E. Omiecinsky

38、, A. Sarasere, and S. Navathe. An efficient Algorithm for Mining Association Rules in Large Databases. In Proc. of the 21st VLDB conference, Zurich, Switzerland, pages 432444, September 1995.?19 Y. Yin, J. Pei, and J. Han. Mining Frequent Patterns Without Candidate Generation. In Proc. 2000 ACM-SIGM

39、OD Int. Conf. Management of Data (SIGMOD00), Dallas, Texas, pages 112, May 2000.?20 M. J. Zaki, S. Parthasarathy, M. Ogihara andW. Li. New Algorithms for Fast Discovery of Association Rules. In Proc. 3rd Intl Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, California, pages 283286

40、, April 1997.?21 M. Mehta, R. Agrawal, and J. Shafer. Sprint: A scalable parallel classifier for data mining. In Proc. Of the 1996 Int. Conf. Very Large Data Bases, Bombay, India, pages 544555, September 1996.?22 W. Hsu, B. Liu, and Y. Ma. Integrating Classification and Association Rule Mining. In Proc. of the Fourth International Conference on Knowledge Discovery and Data Mining KDD-98, New York, USA, pa