摘要：本文首先回顧了關(guān)聯(lián)規(guī)則" title="關(guān)聯(lián)規(guī)則">關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展情況，然后對(duì)關(guān)聯(lián)規(guī)則問(wèn)題進(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í)處理過(guò)程[1,2]。通過(guò)數(shù)據(jù)挖掘，有價(jià)值的知識(shí)、規(guī)則或高層次的信息就能從數(shù)據(jù)庫(kù)的相關(guān)數(shù)據(jù)集合中抽取出來(lái)，并從不同角度展現(xiàn)，從而使大型數(shù)據(jù)庫(kù)作為一個(gè)豐富、可靠的資源為知識(shí)的提取服務(wù)。?

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

AIS算法是第一個(gè)發(fā)表的生成事務(wù)數(shù)據(jù)庫(kù)中所有大項(xiàng)目集的算法[3]。它集中在增強(qiáng)數(shù)據(jù)庫(kù)必要的功能以支持決策支持查詢(xún)。該算法的目標(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ù)庫(kù)進(jìn)行多次分析。每次分析都要掃描全部事務(wù)。第一次分析計(jì)算數(shù)據(jù)庫(kù)中單個(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ù)通過(guò)刪除候選集合中不必要的項(xiàng)目集來(lái)確定最終的候選集合。然后計(jì)算每個(gè)候選集合的支持度。支持度大于等于最小支持度閾值的候選集合被選出作為大項(xiàng)目集。這些大項(xiàng)目集繼續(xù)被擴(kuò)展以生成下一次分析的候選集合。直到不能發(fā)現(xiàn)更多大項(xiàng)目集時(shí)該處理過(guò)程結(jié)束。?

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

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

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

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

有一些Apriori算法的變型，如AprioriTID和AprioriHybrid。AprioriTID的工作原來(lái)與Apriori類(lèi)似，所不同的是它用生成的項(xiàng)目集合計(jì)算支持度，取代了通過(guò)數(shù)據(jù)庫(kù)掃描計(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)了過(guò)高的代價(jià)獲取無(wú)意義的項(xiàng)目。Apriori算法比其它一些算法（如SETM和AIS）更有效[6,9]。?

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

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

A. Savasere等人提出了分區(qū)（Partition）算法[11]，該算法將數(shù)據(jù)庫(kù)掃描的次數(shù)降為兩次。Partition算法邏輯上將數(shù)據(jù)庫(kù)劃分為互不相交的若干個(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]，該算法通過(guò)數(shù)據(jù)庫(kù)的一個(gè)隨機(jī)采樣數(shù)據(jù)生成候選頻繁項(xiàng)目集，然后掃描整個(gè)數(shù)據(jù)庫(kù)對(duì)其進(jìn)行驗(yàn)證?；诓蓸拥乃惴ǘ鄶?shù)情況下只需掃描一次數(shù)據(jù)庫(kù)，最壞的情況下也只需兩次掃描，但該算法所獲得的高效率是以犧牲挖掘精度來(lái)?yè)Q取的，有可能丟失一些全局頻繁項(xiàng)目集。?

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

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

Ei-Hajj等人提出了一種基于反轉(zhuǎn)矩陣（Inverted Matrix）的算法[15]，它類(lèi)似于FP-Growth算法，該算法首先將數(shù)據(jù)庫(kù)映射為一個(gè)基于磁盤(pán)的反轉(zhuǎn)矩陣，然后針對(duì)該反轉(zhuǎn)矩陣在內(nèi)存中建立COFI（Co-Ocurrence Frequent Item）樹(shù)，利用COFI樹(shù)發(fā)現(xiàn)頻繁項(xiàng)目集。實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于Apriori和FP-Growth，對(duì)于超大規(guī)模數(shù)據(jù)庫(kù)和較小支持度的情況，優(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ī)則等類(lèi)型關(guān)聯(lián)規(guī)則挖掘算法的研究。?

Srikant和Agrawal從廣義關(guān)聯(lián)規(guī)則挖掘的角度研究了多層關(guān)聯(lián)規(guī)則挖掘問(wèn)題[16]，多層關(guān)聯(lián)規(guī)則挖掘利用概念分層的背景知識(shí)在更高的抽象層次上挖掘關(guān)聯(lián)規(guī)則，從而解決了稀疏數(shù)據(jù)中關(guān)聯(lián)規(guī)則的支持度閾值過(guò)低而難以挖掘的問(wèn)題。?

Srikant等人通過(guò)將數(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ī)則問(wèn)題描述

本節(jié)給出關(guān)聯(lián)規(guī)則挖掘問(wèn)題的形式描述。?

定義2.1 令I = {I₁, I₂, … , I_m}是由m個(gè)不同項(xiàng)目（Items）組成的集合，D是由事務(wù)T組成的集合（數(shù)據(jù)庫(kù)），這里事務(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 稱(chēng)為前提，Y 稱(chēng)為結(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ù)庫(kù)）D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶(hù)給定的最小支持度S_min和最小可信度C_min的關(guān)聯(lián)規(guī)則。?

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

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

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

1. 找到所有支持度大于最小支持度S_min的項(xiàng)目集合（Itemsets），這些項(xiàng)集稱(chē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ī)則，只有那些大于用戶(hù)給定的最小可信度的規(guī)則才被留下來(lái)。對(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)中，過(guò)程先產(chǎn)生候選k-項(xiàng)目集的集合C_k，C_k中的每一個(gè)項(xiàng)目集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于L_k-1的頻繁集合做一個(gè)(k-2)-連接來(lái)產(chǎn)生的。C_k中的項(xiàng)目集是用來(lái)產(chǎn)生頻繁集合的候選集，最后的頻繁集合L_k必須是C_k的一個(gè)子集。C_k中的每個(gè)元素需在事務(wù)數(shù)據(jù)庫(kù)中進(jìn)行驗(yàn)證來(lái)決定其是否加入L_k，這里的驗(yàn)證過(guò)程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的事務(wù)數(shù)據(jù)庫(kù)，即如果頻繁集合最多包含10個(gè)項(xiàng)目，那么就需要掃描事務(wù)數(shù)據(jù)庫(kù)10遍，這需要很大的I/O" title="I/O">I/O開(kāi)銷(xiāo)。?

在文獻(xiàn)[25]中，Agrawal等人用剪枝技術(shù)（Pruning）來(lái)減小候選集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è)剪枝過(guò)程可以降低計(jì)算所有的候選集合的支持度的代價(jià)。文獻(xiàn)[25]中還引入了雜湊樹(shù)（Hash Tree）方法來(lái)有效地計(jì)算每個(gè)項(xiàng)目集的支持度。?

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

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

1.??劃分方法

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

2. Hash方法

Park等[10]提出了一種基于雜湊（Hash）方法的算法，可以高效產(chǎn)生頻繁集合。通過(guò)實(shí)驗(yàn)我們可以發(fā)現(xiàn)尋找頻繁集合主要的計(jì)算是在生成頻繁2-項(xiàng)目集L_k上，Park等就是利用了這個(gè)性質(zhì)引入雜湊技術(shù)來(lái)改進(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ù)庫(kù)中抽取出來(lái)的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地降低了I/O開(kāi)銷(xiāo)，但該算法最大的缺點(diǎn)是產(chǎn)生的結(jié)果不精確，存在所謂的數(shù)據(jù)扭曲(Data Skew)。分布在同一頁(yè)面上的數(shù)據(jù)通常是高度相關(guān)的，可能不能表示整個(gè)數(shù)據(jù)庫(kù)中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價(jià)可能同掃描一遍數(shù)據(jù)庫(kù)相近。Lin和Dunham在[28]中討論了反扭曲(Anti-skew)算法來(lái)挖掘關(guān)聯(lián)規(guī)則，在那里他們引入的技術(shù)使得掃描數(shù)據(jù)庫(kù)的次數(shù)少于2次。?

Brin等[13]提出的算法使用比傳統(tǒng)算法少的掃描遍數(shù)來(lái)發(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ù)

減少用于未來(lái)掃描的事務(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方法固有的缺陷仍然無(wú)法克服。?

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

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

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

文獻(xiàn)[14]提到了一種解決問(wèn)題（1）的FP-growth方法。該方法采用分而治之的策略：在經(jīng)過(guò)第一次掃描之后，把數(shù)據(jù)庫(kù)中的頻繁集合壓縮進(jìn)一棵頻繁模式樹(shù)（FP-tree），同時(shí)依然保留其中的關(guān)聯(lián)信息。隨后再將FP-tree分化成一些條件庫(kù)，每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻繁集合相關(guān)。然后再對(duì)這些條件庫(kù)分別進(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]中介紹了一種解決問(wèn)題（2）的方法。該方法基于這樣的思想：Apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但在實(shí)際應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在Apriori算法中，起決定作用的是支持度，而我們現(xiàn)在把可信度放在第一位，挖掘一些具有高可信度的規(guī)則。?

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

基本的方法有兩類(lèi)：?

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

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

結(jié)束語(yǔ)

本文回顧了關(guān)聯(lián)規(guī)則挖掘研究的進(jìn)展情況，對(duì)關(guān)聯(lián)規(guī)則問(wèn)題進(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.?