摘要：本文首先回顧了關(guān)聯(lián)規(guī)則" title="關(guān)聯(lián)規(guī)則">關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展情況,，然后對(duì)關(guān)聯(lián)規(guī)則問題進(jìn)行了形式化描述,，最后討論了關(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ī)則挖掘研究進(jìn)展

數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中挖掘出隱含的,、先前未知的,、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則的高級(jí)處理過程[1,2]。通過數(shù)據(jù)挖掘,，有價(jià)值的知識(shí),、規(guī)則或高層次的信息就能從數(shù)據(jù)庫的相關(guān)數(shù)據(jù)集合中抽取出來，并從不同角度展現(xiàn),，從而使大型數(shù)據(jù)庫作為一個(gè)豐富,、可靠的資源為知識(shí)的提取服務(wù)。?

R. Agrawal等人在1993年首先提出在交易數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則[3],，典型的例子是“多數(shù)顧客在購買面包和黃油的同時(shí)也會(huì)購買牛奶”,，找出所有這類規(guī)則，對(duì)于確定市場(chǎng)策略是很有價(jià)值的，例如可用于追加銷售,、倉儲(chǔ)規(guī)劃,，并可根據(jù)購買模式對(duì)顧客進(jìn)行劃分。?

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

AIS算法要對(duì)整個(gè)數(shù)據(jù)庫進(jìn)行多次分析。每次分析都要掃描全部事務(wù),。第一次分析計(jì)算數(shù)據(jù)庫中單個(gè)項(xiàng)目的支持度,，并確定哪個(gè)是大或頻繁項(xiàng)目集。對(duì)每次分析的大項(xiàng)目集進(jìn)行擴(kuò)展以生成候選項(xiàng)目集,。掃描一個(gè)事務(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ù),，它采用了一種評(píng)估工具和剪枝技術(shù),。該評(píng)估和剪枝技術(shù)通過刪除候選集合中不必要的項(xiàng)目集來確定最終的候選集合。然后計(jì)算每個(gè)候選集合的支持度,。支持度大于等于最小支持度閾值的候選集合被選出作為大項(xiàng)目集,。這些大項(xiàng)目集繼續(xù)被擴(kuò)展以生成下一次分析的候選集合。直到不能發(fā)現(xiàn)更多大項(xiàng)目集時(shí)該處理過程結(jié)束,。?

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

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

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

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

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

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

J. S. Park等人指出,，Apriori算法的計(jì)算開銷主要在頻繁2項(xiàng)目集的計(jì)算上，因此提出了基于Hash技術(shù)對(duì)生成的候選2項(xiàng)目集進(jìn)行裁剪的DHP算法[10]。Apriori算法和DHP算法掃描數(shù)據(jù)庫的次數(shù)是和最大" title="最大">最大頻繁項(xiàng)目集的長(zhǎng)度一致的,，但是對(duì)大型數(shù)據(jù)庫系統(tǒng)一次數(shù)據(jù)庫掃描的代價(jià)是非常昂貴的,，所以數(shù)據(jù)庫掃描的次數(shù)成為關(guān)聯(lián)規(guī)則挖掘算法的一個(gè)主要的瓶頸問題。?

A. Savasere等人提出了分區(qū)（Partition）算法[11],，該算法將數(shù)據(jù)庫掃描的次數(shù)降為兩次,。Partition算法邏輯上將數(shù)據(jù)庫劃分為互不相交的若干個(gè)區(qū)，算法首先找出每個(gè)分區(qū)中的局部頻繁項(xiàng)目集,，然后根據(jù)“頻繁項(xiàng)目集至少在一個(gè)分區(qū)中是頻繁的”這一性質(zhì),，合并所有的局部頻繁項(xiàng)目集，最后對(duì)合并后所有的局部頻繁項(xiàng)目集進(jìn)行全局計(jì)數(shù),，得到全局頻繁項(xiàng)目集,。?

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

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

J. Han等人提出了一種無需生成候選頻繁項(xiàng)目集的算法FP-Growth（頻繁模式增長(zhǎng)算法）[14],，該算法首先將數(shù)據(jù)庫壓縮成一個(gè)高度濃縮的數(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算法的效率有一個(gè)量級(jí)的提高,。?

Ei-Hajj等人提出了一種基于反轉(zhuǎn)矩陣（Inverted Matrix）的算法[15]，它類似于FP-Growth算法,，該算法首先將數(shù)據(jù)庫映射為一個(gè)基于磁盤的反轉(zhuǎn)矩陣,，然后針對(duì)該反轉(zhuǎn)矩陣在內(nèi)存中建立COFI（Co-Ocurrence Frequent Item）樹,，利用COFI樹發(fā)現(xiàn)頻繁項(xiàng)目集。實(shí)驗(yàn)結(jié)果表明,，該算法優(yōu)于Apriori和FP-Growth,，對(duì)于超大規(guī)模數(shù)據(jù)庫和較小支持度的情況，優(yōu)勢(shì)更加明顯,。另外,，反轉(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ī)則,、時(shí)態(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ī)則挖掘利用概念分層的背景知識(shí)在更高的抽象層次上挖掘關(guān)聯(lián)規(guī)則，從而解決了稀疏數(shù)據(jù)中關(guān)聯(lián)規(guī)則的支持度閾值過低而難以挖掘的問題,。?

Srikant等人通過將數(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 = {I₁, I₂, … , I_m}是由m個(gè)不同項(xiàng)目（Items）組成的集合,，D是由事務(wù)T組成的集合（數(shù)據(jù)庫）,，這里事務(wù)T是項(xiàng)目的集合，并且T í I,。其中,，每個(gè)事務(wù)T有一個(gè)唯一標(biāo)識(shí)，記為TID,。關(guān)聯(lián)規(guī)則是形如XTY的蘊(yùn)涵式,，其中X í ?I，Y í ?I,，而且X ?Y = f,。這里，X 稱為前提,，Y 稱為結(jié)論,。?

下面定義關(guān)聯(lián)規(guī)則的兩個(gè)重要測(cè)度：支持度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ù),。?

給定一個(gè)事務(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ù)庫中項(xiàng)目集之間關(guān)聯(lián)規(guī)則的問題,，這是一種基于頻繁集合理論的遞推方法,，它將關(guān)聯(lián)規(guī)則挖掘算法分解為兩個(gè)步驟：?

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

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

如給定了一個(gè)頻繁集合Y=I₁I₂...I_k，k32,，I_j∈I,，產(chǎn)生只包含集合{I₁，I₂,，...,，I_k}中項(xiàng)目的所有規(guī)則（最多k個(gè)），其中每一個(gè)規(guī)則的右部只有一項(xiàng),，(即形如[Y-I_i]TI_i,，'1￡i￡k)，這里采用的是[13]中規(guī)則的定義,。一旦生成了這些規(guī)則,，只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。對(duì)于規(guī)則右部含兩個(gè)以上項(xiàng)目的規(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-項(xiàng)目集L₁,，然后是頻繁2-項(xiàng)目集L₂，直到有某個(gè)r值使得L_r為空,，這時(shí)算法停止,。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項(xiàng)目集的集合C_k,，C_k中的每一個(gè)項(xiàng)目集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于L_k-1的頻繁集合做一個(gè)(k-2)-連接來產(chǎn)生的,。C_k中的項(xiàng)目集是用來產(chǎn)生頻繁集合的候選集，最后的頻繁集合L_k必須是C_k的一個(gè)子集,。C_k中的每個(gè)元素需在事務(wù)數(shù)據(jù)庫中進(jìn)行驗(yàn)證來決定其是否加入L_k,，這里的驗(yàn)證過程是算法性能的一個(gè)瓶頸,。這個(gè)方法要求多次掃描可能很大的事務(wù)數(shù)據(jù)庫，即如果頻繁集合最多包含10個(gè)項(xiàng)目,，那么就需要掃描事務(wù)數(shù)據(jù)庫10遍,，這需要很大的I/O" title="I/O">I/O開銷。?

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

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

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

1.??劃分方法

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

2. Hash方法

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

3. 采樣方法

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

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

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

其它頻繁集合挖掘方法?

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

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

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

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

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

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

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

基本的方法有兩類：?

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

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

結(jié)束語

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

參考文獻(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 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.?