張 晶， 張 斌， 胡學(xué)鋼

(合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽合肥 230009)

關(guān)聯(lián)規(guī)則挖掘技術(shù)目的在于發(fā)現(xiàn)新穎的、有用的、感興趣的、隱藏在項目集合中的關(guān)聯(lián)規(guī)則[1]。關(guān)聯(lián)規(guī)則挖掘算法應(yīng)該發(fā)現(xiàn)隱藏的、新穎的關(guān)聯(lián)性。然而，大部分經(jīng)典算法僅考慮數(shù)據(jù)本身[2，3]，而與數(shù)據(jù)相關(guān)的極為豐富的相關(guān)領(lǐng)域知識資源并沒有作為先驗知識來消除已知模式，導(dǎo)致挖掘的知識往往包含大量冗余的規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法把很多在領(lǐng)域中作為常識的已知關(guān)聯(lián)知識提取了出來，造成知識大量的冗余。在關(guān)聯(lián)發(fā)現(xiàn)中大部分研究集中在采取降低閾值的方法來降低規(guī)則數(shù)目從而達(dá)到消除冗余的效果。

所謂的領(lǐng)域知識[4]DK(dom ain know ledge，簡稱DK)，是指一個專門領(lǐng)域中的重要問題或概念以及這些問題或概念之間的相互關(guān)系。

在知識發(fā)現(xiàn)系統(tǒng)中，把加入的那些有關(guān)指導(dǎo)和限制搜索感興趣的知識稱為背景知識或領(lǐng)域知識，且一般不把兩者進(jìn)行區(qū)分。知識發(fā)現(xiàn)算法應(yīng)該合理使用領(lǐng)域知識，以達(dá)到縮短搜尋時間的目的。領(lǐng)域知識是指有助于進(jìn)行知識發(fā)現(xiàn)的信息，它不僅僅是一些應(yīng)用領(lǐng)域內(nèi)的業(yè)務(wù)知識，還包括知識發(fā)現(xiàn)相關(guān)知識以及其它相關(guān)背景知識等。知識發(fā)現(xiàn)應(yīng)以領(lǐng)域知識為基礎(chǔ)，利用領(lǐng)域知識有目標(biāo)地進(jìn)行知識發(fā)現(xiàn)，一方面可以縮小目標(biāo)搜索范圍，提高效率;另一方面可以提高發(fā)現(xiàn)模式或結(jié)果的興趣度、可信度，同時興趣度和可信度本身也與領(lǐng)域知識有關(guān)。

本文提出一種基于領(lǐng)域知識的關(guān)聯(lián)規(guī)則算法DKARM，既考慮了數(shù)據(jù)本身具有的領(lǐng)域知識關(guān)系，又針對經(jīng)典的關(guān)聯(lián)規(guī)則算法進(jìn)行了改進(jìn)，同時對算法進(jìn)行了理論分析和實驗驗證。

1 引入領(lǐng)域知識挖掘關(guān)聯(lián)規(guī)則

由于某些事務(wù)項之間在領(lǐng)域知識的指導(dǎo)或約束下體現(xiàn)了眾所周知的強(qiáng)依賴性，關(guān)聯(lián)挖掘所得到的規(guī)則往往包含大量冗余的規(guī)則。如超市銷售數(shù)據(jù)中，{釘子，錘子}之間具有強(qiáng)關(guān)聯(lián)性，是一個可信度很高的規(guī)則。但這類規(guī)則對用戶來說，可能并不感興趣。用戶感興趣的是類似于{尿布，啤酒}這類無法在領(lǐng)域知識指導(dǎo)下得到的真正有趣的知識。在傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘中，大部分已挖掘出的規(guī)則可能與已知的領(lǐng)域知識存在強(qiáng)烈的聯(lián)系，但是發(fā)現(xiàn)有用新穎的知識卻不能借助這些規(guī)則。這樣就造成了一種結(jié)果，那就是用戶感興趣和不感興趣的關(guān)聯(lián)規(guī)則交錯在一起，這樣用戶為了發(fā)現(xiàn)感興趣的模式不得不逐一區(qū)分和解釋這類規(guī)則。

顯然，在領(lǐng)域知識指導(dǎo)下能明顯呈現(xiàn)出的關(guān)聯(lián)規(guī)則被剔除在關(guān)聯(lián)規(guī)則挖掘當(dāng)中，則可以避免這類規(guī)則被用戶所提取和看到。為了達(dá)到減少在關(guān)聯(lián)規(guī)則挖掘中的已知模式的數(shù)目，本文提出了DKARM算法，使用領(lǐng)域知識作為先驗知識，來消除冗余的關(guān)聯(lián)規(guī)則及其派生規(guī)則。

1.1 關(guān)聯(lián)規(guī)則基本模型

關(guān)聯(lián)規(guī)則是支持度和置信度分別滿足用戶給定閾值的規(guī)則，所有支持度大于最小支持度的項集(Itemset)，稱為頻繁項集(Frequent Itemset)，簡稱頻集。

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則主要分2個步驟:找出所有頻繁項集;由頻繁項集生成滿足最小信任度的規(guī)則。

文獻(xiàn)[2]首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻集理論的遞推方法。這是一種有效的關(guān)聯(lián)規(guī)則挖掘算法，但它可能產(chǎn)生大量候選項集，且需要多次重復(fù)掃描數(shù)據(jù)庫，大量的時間消耗在內(nèi)存與數(shù)據(jù)庫中數(shù)據(jù)的交換上。

文獻(xiàn)[2]證明關(guān)聯(lián)規(guī)則具有如下性質(zhì):

性質(zhì)1 頻繁項集的子集必定是頻繁項集。

性質(zhì)2 非頻繁項集的超集一定是非頻繁的。

針對Apriori算法的固有缺陷，文獻(xiàn)[3]提出了不產(chǎn)生候選挖掘頻繁項集的方法——FP-樹頻集算法。采用分而治之的策略，建立了基于FP-tree頻繁項模式的無候選項集的結(jié)構(gòu)思想，將原始數(shù)據(jù)庫中的每一項事務(wù)都壓縮到一棵FP-tree中，從而大大降低了FP-G row th算法的挖掘耗時，提高了挖掘效率。但FP算法仍存在一定的局限性，它通過遞歸創(chuàng)建條件模式來挖掘頻繁項，如果樹中分枝較長時，這個遞歸過程仍很費時。

1.2 實例分析

通過實例分析沒有消除明確的領(lǐng)域知識指導(dǎo)下的強(qiáng)關(guān)聯(lián)性規(guī)則挖掘問題。考慮元素集合 Γ= {A，B，C，D，E}，這些元素所有可能的組合集為: {AB}、{AC}、{AD}、{AE}、{BC}、{BD}、{BE}、{CD}、{CE}、{DE}、{ABC}、{ABD}、{ABE}、{ACD}、{ACE}、{ADE}、{BCD}、{BCE}、{BDE}、{CDE}、{ABCD}、{ABCE}、{ABDE}、{ACDE}、{BCDE}、{ABCDE}。不考慮任何閾值，可能的子集數(shù)目是26，這些子集產(chǎn)生的最大規(guī)則數(shù)是180。

下面考慮元素C和D在領(lǐng)域知識指導(dǎo)下有強(qiáng)關(guān)聯(lián)關(guān)系。值得注意的是，C和D同時出現(xiàn)的有8個集合({CD}、{ACD}、{BCD}、{CDE}、{ABCD}、{ACDE}、{BCDE}、{ABCDE})。這8個集合將產(chǎn)生92個規(guī)則，在每個規(guī)則中，C、D都同時出現(xiàn)，結(jié)果是整個規(guī)則的51.11%將由C和D之間的關(guān)聯(lián)性而產(chǎn)生。

非常重要的一點是，不能在預(yù)處理工作中直接從Γ中刪掉C和D，因為C或者D都可能和A、B或者E有關(guān)聯(lián)。然而，在同一集合中，應(yīng)該能避免C和D的組合，這就消除了產(chǎn)生的規(guī)則同時包括C和D的可能性。

1.3 基于領(lǐng)域知識的關(guān)聯(lián)規(guī)則挖掘算法

為了便于展開研究，冗余規(guī)則限定為只包含2個事務(wù)項(ITEM)，這2個事務(wù)項稱為冗余項對。超市商品交易數(shù)據(jù)庫見表1所列。

表1 超市事務(wù)數(shù)據(jù)庫

1.3.1 算法DKARM描述

輸入:事務(wù)數(shù)據(jù)庫D，最小支持度計數(shù)m insup，領(lǐng)域知識指導(dǎo)下的冗余項對Ω。

輸出:消除了冗余項對的頻繁模式集合P。

(1)掃描一遍數(shù)據(jù)庫D獲得1-候選集，刪除頻率小于最小支持度計數(shù)min_sup的項，獲取所有頻繁項，得到1-頻集，并將1-頻集中各項按支持?jǐn)?shù)遞減排列。由表1得到的支持度計數(shù)結(jié)果按降序排列，見表2所列，并將數(shù)據(jù)庫中每一項事務(wù)根據(jù)1-頻集中的次序重新排序后得到L，見表3所列，這是有效合并重復(fù)路徑的前提。

(2)第2次掃描數(shù)據(jù)庫L，構(gòu)建帶有分支編號的FP-tree。

表2 計數(shù)結(jié)果(1-項集)

表3 重排列的數(shù)據(jù)庫L

首先創(chuàng)建樹的根節(jié)點，以“NULL”標(biāo)記它;接著，第2次掃描數(shù)據(jù)庫，按照L中的次序，將數(shù)據(jù)庫中的事務(wù)依次插入到根節(jié)點下。根據(jù)表3得到的帶分支編號的FP樹，如圖1所示。如結(jié)點I3:2(12)表示在I3結(jié)點的支持度計數(shù)是2，分支編號用括號中的字符串表示，“12”表示結(jié)點I2在從根開始的第1分支的第2子分支中。

(3)依次從各分枝開始從根往下挖掘與該分枝中的第1項組合的2-項集，并依次統(tǒng)計各分枝中該項的支持?jǐn)?shù)，結(jié)合min_sup，得到2-頻集。如圖1中從“NULL”結(jié)點開始，I2結(jié)點得到的2-項集{I2 I1:4(11)，I2 I3:2(12)+2(112)，I2 I4: 1(13)+1(113)，I2 I5:1(111)+1(1221)}，I1結(jié)點得到的2-項集為{I1I3:2(112)+2(21)，I1 I5:1(111)+1(1221)}。依次按表2中結(jié)點的順序再如此計算I3、I4、I5結(jié)點。假設(shè)最小支持度計數(shù)為2，則可得{I2I1:4(11)，I2I3:2(12)+ 2(112)，I2 I4:1(13)+1(113)，I2 I5:1(111)+ 1(1221)，I1 I3:2(112)+2(21)，I1 I5:1(111)+ 1(1221)}均為2-頻繁項集。

(4)在所有的2-頻集中刪除領(lǐng)域知識指導(dǎo)下得到的冗余項對集合 Ω。

(5)根據(jù)Apriori性質(zhì)，由K-1階的項集可構(gòu)造K階的候選項集，直到某一階的項集為空，得到所有消除了冗余項對的頻繁模式集合P，算法停止。

由于2-項集中保留了每項事務(wù)在每個分支中的支持?jǐn)?shù)，因此在2-項集的基礎(chǔ)上可直接得到3-候選集的支持?jǐn)?shù)，而不必再次掃描原數(shù)據(jù)庫或者遞歸訪問 FP樹。如{I2I1:4(11)，I2I3: 2(12)+2(112)，I1I3:2(112)+2(21)}是2-頻繁項集，所以3-項集{I2 I1 I3}也是頻繁的，根據(jù)其分支編號共享的前綴，可得其支持?jǐn)?shù)為2，即得{I2I1I3:2(112)}。

圖1 帶分支編號的FP樹

1.3.2 算法說明

第1步和第 2步基本和FP樹算法保持一致，但是在形成FP樹時增加了分支編號，以便后續(xù)步驟中更高階項集的信息獲取。

第3步在2-項集的搜索中沒有沿用FP樹常用的自底向上方法，而是自頂向下進(jìn)行項的組合。

第4步中，當(dāng)產(chǎn)生2個元素的候選集后，所有Ω中冗余的元素對都從2-頻集中刪除。由于這一步驟中消除了 Ω中的每個來源于領(lǐng)域知識的冗余項對(如{C，D})，不僅避免產(chǎn)生規(guī)則C→D，而且也避免產(chǎn)生所有派生規(guī)則(如{D→C，C→AD})，這些規(guī)則也包含已知強(qiáng)關(guān)聯(lián)性。根據(jù)性質(zhì)1和性質(zhì)2，保證了 Ω中冗余項對不會在后續(xù)頻繁項集合中同時出現(xiàn)，也將不會在關(guān)聯(lián)規(guī)則中出現(xiàn)，使得此方法很有效，而且獨立于任何最小支持度、最小置信度等閾值的限制。這種方法消除所有的包含冗余項對的候選集合，而獨立于任何概念層次，這是本算法不同于其它消除冗余規(guī)則算法的特點[5，6]。

在前2個步驟中，利用FP算法將原始數(shù)據(jù)庫中的每一項事務(wù)都壓縮到一棵FP-tree中，避免了多次掃描數(shù)據(jù)庫;第5步利用了Ap riori算法的核心思想。根據(jù)Apriori性質(zhì)，在2-項集的基礎(chǔ)上通過鏈接與剪枝可得到更高階的項集;通過FP樹中增分支編號，在獲取2-項集時保留了每項事務(wù)在每個分枝中的支持?jǐn)?shù)，因此，在2-項集的基礎(chǔ)上可以直接得到3-候選集的支持?jǐn)?shù)，而不必再次遞歸訪問FP樹。因此，DKARM算法既可避免Apriori算法中多次掃描數(shù)據(jù)庫不斷產(chǎn)生候選項的缺點，又克服了FP-Grow th算法中的遞歸挖掘方式。

值得說明的是，在DKARM算法中，領(lǐng)域知識指導(dǎo)下的冗余對是作為已知輸入直接獲取的。針對領(lǐng)域知識獲取與數(shù)據(jù)挖掘的融合工作，很多學(xué)者展開了一系列研究，參見文獻(xiàn)[7-9]。

2 評 估

不考慮最小支持度和最小可信度的閾值，圖2所示給出了消除不同數(shù)目的冗余項對后得到的規(guī)則數(shù)的理論計算結(jié)果，理論分析中事務(wù)項個數(shù)為2～12的事務(wù)數(shù)據(jù)庫。其中，分別討論了0對、1對、2對冗余項對從集合中消除，0對即為不消除冗余規(guī)則得到的結(jié)果。

圖2 消除不同數(shù)目的冗余對的規(guī)則數(shù)分布圖

從這3種情況可以看出，不消除冗余的規(guī)則數(shù)目隨著集合中的元素數(shù)目的增加呈指數(shù)形式增長，而消除冗余后能夠大大減少產(chǎn)生規(guī)則的數(shù)目。

顯然，如果冗余項對的數(shù)目越多，這種方法的作用也就越明顯。

圖3所示給出了當(dāng)被消除的冗余項對的數(shù)目為0、1、2時，減少規(guī)則占總的規(guī)則的百分比。如當(dāng)消除1個冗余項對時，產(chǎn)生的規(guī)則僅占總規(guī)則數(shù)目的55%，而被消除的已知規(guī)則占45%;當(dāng)消除的依賴對的數(shù)目為2時，僅有30%的規(guī)則產(chǎn)生，而被消除的規(guī)則增加到70%。

不難看出，隨著事務(wù)項數(shù)目的增加，曲線趨向于飽和值。

圖3 規(guī)則數(shù)變化百分比分布圖

同時，在 W indow s XP、CPU Intel T2050 1.60 GH z、內(nèi)存1.00GB環(huán)境下，使用Java語言實現(xiàn)了DKARM算法。采用來源于文獻(xiàn)[1]中的A llElectronics某分店的事務(wù)數(shù)據(jù)(包括9個事務(wù)數(shù)和5個項數(shù))、Weka生成的RDG1(100個事務(wù)數(shù)和10個項數(shù))和contact-lenses(包括24個事務(wù)數(shù)和12個項數(shù))進(jìn)行實驗，實驗中設(shè)置支持度為20%，置信度為60%，得到的實驗結(jié)果見表4所列。

從實際數(shù)據(jù)的驗證結(jié)果可知，規(guī)則數(shù)和時間明顯降低了。對于數(shù)據(jù)挖掘的用戶來說，消除領(lǐng)域知識指導(dǎo)下的已知規(guī)則比降低產(chǎn)生關(guān)聯(lián)規(guī)則的計算時間更為重要，充分考慮數(shù)據(jù)相關(guān)的領(lǐng)域知識對挖掘過程的指導(dǎo)意義，這是本文的主要目的。然而，隨著具有關(guān)聯(lián)的依賴對集合的消除，較少的候選集將會產(chǎn)生，因此產(chǎn)生規(guī)則的計算時間也隨著減少，這也是必然的結(jié)果。

表4 DKARM算法實驗結(jié)果m s

3 結(jié)束語

本文以領(lǐng)域知識作為指導(dǎo)，提出可消減冗余關(guān)聯(lián)規(guī)則數(shù)目的挖掘方法，可以在某種程度上保證產(chǎn)生的規(guī)則對用戶來說更感興趣，這種消減并不受最小支持等閾值的影響。在有關(guān)領(lǐng)域知識指導(dǎo)下，如何獲取更復(fù)雜的項之間關(guān)系作為先驗知識指導(dǎo)后續(xù)的挖掘工作，如何更有效地評估挖掘后規(guī)則的興趣度，都是進(jìn)一步的研究工作。

本文初稿首次刊登于《計算機(jī)技術(shù)與應(yīng)用進(jìn)展?2010》

[1] Han Jiaw ei，Kamber M.Data m ining-concepts and techniques[M].M organ Kaufman Publishers，2001:1-30.

[2] Agrawal R，Imielinski T，Swami A.M ining association ru les betw een setsof item s in large databases[C]//Proc of the ACM SIGMOD Conference on M anagem ent of Data，1993: 207-216.

[3] Han Jiaw ei，Pei Jian，Yin Y.M ining frequent patterns withou t candidate generation[C]//Proc of the ACM SIGMOD Conference on Management of Data，2000:1-12.

[4] Fayyad U，Piatetsky-Shapiro G，Smyth P.From datam ining to know ledge discovery:an overview[C]//Advances in Know ledge Discovery and Data M ining.M enlo Park，California:AAA IPress，1996:1-35.

[5] ZakiM.Generating non-redundan t association rules[C]// Proc of the 6th ACM-SIGKDD International Conference on Know ledge Discovery and Data M ining，Boston，M assachusetts，USA，2000:34-43.

[6] Liu B，H su W，Ma Y.Pruning and summarizing the discovered associations[C]//Proc of the 5th ACM-SIGKDD International Conference on Know ledge Discovery and Data M ining，San Diego，California，1999:125-134.

[7] 邢平平，施鵬飛，趙 奕.基于本體論的數(shù)據(jù)挖掘方法[J].計算機(jī)工程，2001，27(5):15-17.

[8] 鐘佩思，徐文勝，曾慶良，等.領(lǐng)域知識獲取與有效性檢查過程集成研究[J].機(jī)械科學(xué)與技術(shù)，2001，20(5):798-800.

[9] 謝 亮，張 晶，胡學(xué)鋼.主從關(guān)系數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則挖掘算法研究[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2009，32 (5):663-666.