摘要：本文首先回顧了關(guān)聯(lián)規(guī)則" title="關(guān)聯(lián)規(guī)則">關(guān)聯(lián)規(guī)則挖掘研究進展情況，然后對關(guān)聯(lián)規(guī)則問題進行了形式化描述，最后討論了關(guān)聯(lián)規(guī)則挖掘" title="關(guān)聯(lián)規(guī)則挖掘">關(guān)聯(lián)規(guī)則挖掘的處理流程和主要算法。?

關(guān)鍵詞：數(shù)據(jù)挖掘" title="數(shù)據(jù)挖掘">數(shù)據(jù)挖掘? 關(guān)聯(lián)規(guī)則? 支持度? 可信度?

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

數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中挖掘出隱含的、先前未知的、對決策有潛在價值的知識和規(guī)則的高級處理過程[1,2]。通過數(shù)據(jù)挖掘，有價值的知識、規(guī)則或高層次的信息就能從數(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ù)購買模式對顧客進行劃分。?

AIS算法是第一個發(fā)表的生成事務(wù)數(shù)據(jù)庫中所有大項目集的算法[3]。它集中在增強數(shù)據(jù)庫必要的功能以支持決策支持查詢。該算法的目標(biāo)是發(fā)現(xiàn)定性規(guī)則。該技術(shù)的局限性是結(jié)論中只有一個項目。即關(guān)聯(lián)規(guī)則是形如XTI_j | a的規(guī)則，其中X是一個項目集合，I_j是值域I中的單個項目，a是規(guī)則的置信度。?

AIS算法要對整個數(shù)據(jù)庫進行多次分析。每次分析都要掃描全部事務(wù)。第一次分析計算數(shù)據(jù)庫中單個項目的支持度，并確定哪個是大或頻繁項目集。對每次分析的大項目集進行擴展以生成候選項目集。掃描一個事務(wù)之后，可確定上一次分析的大項目集和該事務(wù)項目的公共項目集。這些公共項目集被該事務(wù)中的其它項目擴展，生成新的候選項目集。大項目集l只能由在當(dāng)前事務(wù)中的大項目并且按照詞典順序位于l中所有項目之后的項目。為了高效地完成該任務(wù)，它采用了一種評估工具和剪枝技術(shù)。該評估和剪枝技術(shù)通過刪除候選集合中不必要的項目集來確定最終的候選集合。然后計算每個候選集合的支持度。支持度大于等于最小支持度閾值的候選集合被選出作為大項目集。這些大項目集繼續(xù)被擴展以生成下一次分析的候選集合。直到不能發(fā)現(xiàn)更多大項目集時該處理過程結(jié)束。?

STEM算法在[4]中提出，其目的是用SQL來處理候選大項目集[5]。在該算法中，大項目集組成的集合的每個成員形如，其中TID是事務(wù)的唯一標(biāo)識符。類似地，候選項目集組成的集合的每個成員形如。與AIS算法類似，SETM算法也要多次分析數(shù)據(jù)庫。?

Apriori是對AIS和SETM算法的改進，并且是第一個可擴展的關(guān)聯(lián)規(guī)則挖掘算法[2,6]。當(dāng)進行初始數(shù)據(jù)庫掃描時Apriori算法搜索大項目集合，然后用該搜索結(jié)果作為后續(xù)掃描并發(fā)現(xiàn)其它達數(shù)據(jù)集合的種子。支持度大于給定最小值的規(guī)則稱為大項目集（large itemsets）頻繁項目集（frequent itemsets），支持度小于給定最小值規(guī)則稱為小項目集（small itemsets）[7]。?

簡而言之，給定一個數(shù)據(jù)集合，Apriori算法需要通過初始掃描整個數(shù)據(jù)集合產(chǎn)生一個支持度不小于指定最小值的項目集合。生成該項目集合（稱為1-候選集合）之后，再形成下一個候選集合（稱為2-候選集合）。再次掃描數(shù)據(jù)庫來計算2-候選集合的支持度。所有支持度小于最小值的集合將被剪裁掉。當(dāng)不再生成新的候選集合時算法終止，得到k-候選集合。?

該算法基于頻繁項目集合的性質(zhì)，即一個頻繁集合的任何子集都是頻繁集合；如果一個項目集合不是頻繁集合，其所有超集均不是頻繁集合[8]。?

有一些Apriori算法的變型，如AprioriTID和AprioriHybrid。AprioriTID的工作原來與Apriori類似，所不同的是它用生成的項目集合計算支持度，取代了通過數(shù)據(jù)庫掃描計算支持度的方法。據(jù)報道，只有當(dāng)AprioriTID生成的項目集合能夠放在內(nèi)存時，AprioriTID才比Apriori效率更高。AprioriHybrid是Apriori和AprioriTID的混合體。該算法用Apriori進行初始掃描，一旦認為生成的集合能夠與內(nèi)存匹配則切換到AprioriTID算法。在大多數(shù)情況下AprioriHybrid算法比Apriori算法效率高，但是當(dāng)進行到最后一次掃描時是個例外。這是因為它花費了過高的代價獲取無意義的項目。Apriori算法比其它一些算法（如SETM和AIS）更有效[6,9]。?

此后，研究人員對關(guān)聯(lián)規(guī)則挖掘問題進行了深入的研究，通過引入隨機采樣和并行挖掘等思想，對原有算法進行了優(yōu)化，以提高挖掘算法的執(zhí)行效率。?

J. S. Park等人指出，Apriori算法的計算開銷主要在頻繁2項目集的計算上，因此提出了基于Hash技術(shù)對生成的候選2項目集進行裁剪的DHP算法[10]。Apriori算法和DHP算法掃描數(shù)據(jù)庫的次數(shù)是和最大" title="最大">最大頻繁項目集的長度一致的，但是對大型數(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ū)中的局部頻繁項目集，然后根據(jù)“頻繁項目集至少在一個分區(qū)中是頻繁的”這一性質(zhì)，合并所有的局部頻繁項目集，最后對合并后所有的局部頻繁項目集進行全局計數(shù)，得到全局頻繁項目集。?

H. Toivonen等人提出了基于采樣的關(guān)聯(lián)規(guī)則挖掘算法[12]，該算法通過數(shù)據(jù)庫的一個隨機采樣數(shù)據(jù)生成候選頻繁項目集，然后掃描整個數(shù)據(jù)庫對其進行驗證?；诓蓸拥乃惴ǘ鄶?shù)情況下只需掃描一次數(shù)據(jù)庫，最壞的情況下也只需兩次掃描，但該算法所獲得的高效率是以犧牲挖掘精度來換取的，有可能丟失一些全局頻繁項目集。?

為了進一步提高算法的有效性，S. Brin等人提出了動態(tài)項目集計數(shù)（DIC）算法[13]，該算法將數(shù)據(jù)庫劃分為若干分區(qū)并且對每個分區(qū)的開始做標(biāo)記，不同于Apriori算法的是，在數(shù)據(jù)庫掃描過程中，DIC算法可以在各個分區(qū)的標(biāo)記點添加候選項目集，而不是像Apriori那樣只能在每次完成整個數(shù)據(jù)庫掃描之后添加候選項目集，這樣便極大地減少了數(shù)據(jù)庫掃描次數(shù)。?

J. Han等人提出了一種無需生成候選頻繁項目集的算法FP-Growth（頻繁模式增長算法）[14]，該算法首先將數(shù)據(jù)庫壓縮成一個高度濃縮的數(shù)據(jù)結(jié)構(gòu)——FP樹，隨后發(fā)現(xiàn)頻繁項目集的工作都在該FP樹上完成，這樣就避免了多次數(shù)據(jù)庫掃描。另外，F(xiàn)P-Growth算法直接在FP樹上發(fā)現(xiàn)頻繁項目集，避免了產(chǎn)生數(shù)目龐大的候選頻繁項目集，因此FP-Growth算法較Apriori算法的效率有一個量級的提高。?

Ei-Hajj等人提出了一種基于反轉(zhuǎn)矩陣（Inverted Matrix）的算法[15]，它類似于FP-Growth算法，該算法首先將數(shù)據(jù)庫映射為一個基于磁盤的反轉(zhuǎn)矩陣，然后針對該反轉(zhuǎn)矩陣在內(nèi)存中建立COFI（Co-Ocurrence Frequent Item）樹，利用COFI樹發(fā)現(xiàn)頻繁項目集。實驗結(jié)果表明，該算法優(yōu)于Apriori和FP-Growth，對于超大規(guī)模數(shù)據(jù)庫和較小支持度的情況，優(yōu)勢更加明顯。另外，反轉(zhuǎn)矩陣的結(jié)構(gòu)特點決定了它便于實現(xiàn)并行挖掘算法。?

除了上述基本關(guān)聯(lián)規(guī)則挖掘算法研究，人們還進行了諸如多層關(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ī)則的支持度閾值過低而難以挖掘的問題。?

Srikant等人通過將數(shù)值型數(shù)據(jù)劃分為不同區(qū)間的方法，在這些區(qū)間之上進行定量關(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 = {I₁, I₂, … , I_m}是由m個不同項目（Items）組成的集合，D是由事務(wù)T組成的集合（數(shù)據(jù)庫），這里事務(wù)T是項目的集合，并且T í I。其中，每個事務(wù)T有一個唯一標(biāo)識，記為TID。關(guān)聯(lián)規(guī)則是形如XTY的蘊涵式，其中X í ?I，Y í ?I，而且X ?Y = f。這里，X 稱為前提，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: XíT，T?D}|是包含X的事務(wù)數(shù)。?

給定一個事務(wù)集合（數(shù)據(jù)庫）D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度S_min和最小可信度C_min的關(guān)聯(lián)規(guī)則。?

關(guān)聯(lián)規(guī)則挖掘算法

經(jīng)典頻繁集合方法?

Agrawal等人1993年[3]首先提出挖掘顧客交易數(shù)據(jù)庫中項目集之間關(guān)聯(lián)規(guī)則的問題，這是一種基于頻繁集合理論的遞推方法，它將關(guān)聯(lián)規(guī)則挖掘算法分解為兩個步驟：?

1. 找到所有支持度大于最小支持度S_min的項目集合（Itemsets），這些項集稱為頻繁集合（Frequent Itemsets)；?

2. 使用第1步找到的頻繁集合產(chǎn)生期望的規(guī)則。?

如給定了一個頻繁集合Y=I₁I₂...I_k，k32，I_j∈I，產(chǎn)生只包含集合{I₁，I₂，...，I_k}中項目的所有規(guī)則（最多k個），其中每一個規(guī)則的右部只有一項，(即形如[Y-I_i]TI_i，'1￡i￡k)，這里采用的是[13]中規(guī)則的定義。一旦生成了這些規(guī)則，只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。對于規(guī)則右部含兩個以上項目的規(guī)則，我們將在后面討論。?

為了生成所有頻繁集合，使用了遞推的方法。其核心算法如下：?

(1)???? L₁ = {large 1-itemsets};?

(2)???? for (k=2; L_k-11F; k++) do begin?

(3)?????? ? C_k=apriori-gen(L_k-1);?? //新的候選集?

(4)?????? ? for all transactions t?D do begin?

(5)??????? ?????? ???C_t=subset(C_k, t);??? //事務(wù)t中包含的候選集?

(6)?????????? for all candidates c? C_t do?

(7)?????????? c.count++;?

(8)?????? ? end?

(9)??????? L_k={c? C_k |c.count 3 S_min}?

(10)??? end?

(11)??? Answer = è_kL_k;?

首先產(chǎn)生頻繁1-項目集L₁，然后是頻繁2-項目集L₂，直到有某個r值使得L_r為空，這時算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項目集的集合C_k，C_k中的每一個項目集是對兩個只有一個項不同的屬于L_k-1的頻繁集合做一個(k-2)-連接來產(chǎn)生的。C_k中的項目集是用來產(chǎn)生頻繁集合的候選集，最后的頻繁集合L_k必須是C_k的一個子集。C_k中的每個元素需在事務(wù)數(shù)據(jù)庫中進行驗證來決定其是否加入L_k，這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的事務(wù)數(shù)據(jù)庫，即如果頻繁集合最多包含10個項目，那么就需要掃描事務(wù)數(shù)據(jù)庫10遍，這需要很大的I/O" title="I/O">I/O開銷。?

在文獻[25]中，Agrawal等人用剪枝技術(shù)（Pruning）來減小候選集C_k的大小，由此可以顯著地改進生成所有頻繁集合算法的性能。算法中引入的剪枝策略基于這樣一個性質(zhì)：一個項目集是頻繁集合當(dāng)且僅當(dāng)它的所有子集都是頻繁集合。那么，如果C_k中某個候選項目集合有一個(k-1)-子集不屬于L_k-1，則這個項目集可以被剪掉不再被考慮，這個剪枝過程可以降低計算所有的候選集合的支持度的代價。文獻[25]中還引入了雜湊樹（Hash Tree）方法來有效地計算每個項目集的支持度。?

頻繁集合算法的幾種優(yōu)化方法?

雖然Apriori算法自身已經(jīng)進行了一定的優(yōu)化，但是在實際應(yīng)用中還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化方法。?

1.??劃分方法

Savasere等[11]設(shè)計了一個基于劃分（partition）的算法，該算法先把數(shù)據(jù)庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻繁集合，然后把產(chǎn)生的頻繁集合合并，用來生成所有可能的頻繁集合，最后計算這些項目集的支持度。這里，分塊的大小要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻繁集合至少在某一個分塊中是頻繁集合保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個處理器生成頻繁集合。產(chǎn)生頻繁集合的每一個循環(huán)結(jié)束后，處理器之間進行通信來產(chǎn)生全局的候選k-項目集。通常這里的通信過程是算法執(zhí)行時間的主要瓶頸；而另一方面，每個獨立的處理器生成頻繁集合的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來產(chǎn)生頻繁集合。其它關(guān)于生成頻繁集合的并行方法詳見[10,26]。?

2. Hash方法

Park等[10]提出了一種基于雜湊（Hash）方法的算法，可以高效產(chǎn)生頻繁集合。通過實驗我們可以發(fā)現(xiàn)尋找頻繁集合主要的計算是在生成頻繁2-項目集L_k上，Park等就是利用了這個性質(zhì)引入雜湊技術(shù)來改進產(chǎn)生頻繁2-項目集的方法。?

3. 采樣方法

基于前一遍掃描得到的信息，對此仔細地進行組合分析，可以得到一個改進的算法，Mannila等[27]首先考慮到這一點，認為采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑。隨后又由Toivonen[12]進一步發(fā)展了這個思想，先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個數(shù)據(jù)庫中可能成立的規(guī)則，然后對數(shù)據(jù)庫的剩余部分驗證這個結(jié)果。Toivonen的算法相當(dāng)簡單并顯著地降低了I/O開銷，但該算法最大的缺點是產(chǎn)生的結(jié)果不精確，存在所謂的數(shù)據(jù)扭曲(Data Skew)。分布在同一頁面上的數(shù)據(jù)通常是高度相關(guān)的，可能不能表示整個數(shù)據(jù)庫中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費的代價可能同掃描一遍數(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)頻繁集合，同時比基于采樣的方法使用更少的候選集，這些改進了算法在低層的效率。具體的考慮是，在計算k-項目集時，一旦認為某個(k+1)-項目集可能是頻繁集合，就并行地計算該(k+1)-項目集的支持度，算法所需的總的掃描次數(shù)通常少于最大頻繁集合的項目數(shù)。?

4.??減少事務(wù)個數(shù)

減少用于未來掃描的事務(wù)集合的大小。一個基本的原理就是當(dāng)一個事務(wù)不包含長度為k的大項目集，則必然不包含長度為k+1的大項目集。從而我們就可以將這些事務(wù)刪掉，這樣在下一遍的掃描中就可以減少事務(wù)的個數(shù)。?

其它頻繁集合挖掘方法?

前面介紹的都是基于Apriori的頻繁集合方法。即使進行了優(yōu)化， Apriori方法固有的缺陷仍然無法克服。?

（1）Apriori可能產(chǎn)生大量的候選集。當(dāng)長度為1的頻繁集合有10000個時，長度為2的候選集個數(shù)將會超過10M。另外，如果要生成一個很長的規(guī)則，產(chǎn)生的中間元素的數(shù)量也是巨大的。?

（2）Apriori無法對稀有信息進行分析。由于頻繁集合使用了參數(shù)S_min（最小支持度），所以就無法對小于S_min的事件進行分析；而如果將S_min設(shè)成一個很低的值，那么算法的效率就會很低。?

下面介紹兩種方法，分別用來解決上述兩個問題。?

文獻[14]提到了一種解決問題（1）的FP-growth方法。該方法采用分而治之的策略：在經(jīng)過第一次掃描之后，把數(shù)據(jù)庫中的頻繁集合壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關(guān)聯(lián)信息。隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻繁集合相關(guān)。然后再對這些條件庫分別進行挖掘。當(dāng)原始數(shù)據(jù)量很大的時候，也可以結(jié)合劃分的方法，使得一個FP-tree可以放入主存中。實驗表明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時在效率上較之Apriori算法有巨大的提高。?

文獻[29]中介紹了一種解決問題（2）的方法。該方法基于這樣的思想：Apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但在實際應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在Apriori算法中，起決定作用的是支持度，而我們現(xiàn)在把可信度放在第一位，挖掘一些具有高可信度的規(guī)則。?

整個算法大致分成計算特征、生成候選集、過濾候選集三個步驟。在這三個步驟中，關(guān)鍵是在計算特征時Hash方法的使用。在考慮算法的時候，有幾個衡量好壞的指標(biāo)：時空效率、錯誤率和遺漏率。?

基本的方法有兩類：?

（1）Min_Hashing的基本思想是，將一條記錄中的頭k個為1的字段的位置作為一個Hash函數(shù)。該方法的遺漏率為零，錯誤率可以由k嚴格控制，但是時空效率相對較差。?

（2）Locality_Sentitive_Hashing的基本思想是，將整個數(shù)據(jù)庫用一種基于概率的方法進行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。該算法的遺漏率和錯誤率是無法同時降低的，但它的時空效率卻比較高。?

結(jié)束語

本文回顧了關(guān)聯(lián)規(guī)則挖掘研究的進展情況，對關(guān)聯(lián)規(guī)則問題進行了形式化描述，最后總結(jié)了關(guān)聯(lián)規(guī)則挖掘的處理流程和主要算法。?

參考文獻

[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 Knowledge Discovery and Data Mining. AAAI/MIT Press，1996.?

[3] R. 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 207–216, May 1993.?

[4] M. Houtsma and A. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Proceedings 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 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 866–883, December 1996.?

[8] J. W. Han，Y. Cai and 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 Discovery and Data Mining, pages 58–64, 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. An 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，September 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 ACM-SIGMOD Int.Conf.Management of Data(SIGMOD’00)，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. SIGKDD’03 Washington DC, USA, 2003.?

[16] R. Srikant，and R. Agrawal. Mining generalized 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, 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 432–444, September 1995.?

[19] Y. Yin, J. Pei, and J. Han. Mining Frequent Patterns Without Candidate Generation. In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), Dallas, Texas, pages 1–12, May 2000.?

[20] M. J. Zaki, S. Parthasarathy, M. Ogihara andW. Li. New Algorithms for Fast Discovery of Association Rules. In Proc. 3rd Int’l Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, California, pages 283–286, 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 544–555, 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, pages 80–86, 1998.?

[23] J. S. Park，M. S. Chen，and P. S. Yu. Efficient parallel data mining of association rules. 4th International Conference on Information and Knowledge Management，Baltimore，Maryland，Novermber 1995.?

[24] A. Savasere，E. Omiecinski，and S. Navathe. Mining for strong negative associations in a large database of costomer transactions. Proceedings of the International Conference on Data Engineering，F(xiàn)ebruary 1998.?

[25] R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. In Proc. of the International Conference of Very Large Databases, Santiago, Chile, pages 487–499, September 1994.?

[26] M. J. Zaki，S. Parthasarathy，and W. Li. A localized algorithm for parallel association mining. 9th Annual ACM Symposium on Parallel Algorithms and Architectures，Newport，Rhode Island，June 1997.?

[27] H. Mannila，H. Toivonen，and A. Verkamo. Efficient algorithm for discovering association? rules. AAAI Workshop on Knowledge Discovery in Databases，1994，pp. 181-192.?

[28] J. L. Lin，and M. H. Dunham. Mining association rules: Anti-skew algorithms. Proceedings of the International Conference on Data Engingeering，Orlando，F(xiàn)lorida，F(xiàn)ebruary 1998.?

[29] Edith Cohen，Mayur Datar，Shinji Fujiwara，Aristides Gionis，Piotr Indyk，Rajeev Motwani，Jeffrey D.Ullman，Cheng Yang. Finding Interesting Associations without Support Pruning.?