摘  要： 提出了一種高效的挖掘數(shù)據(jù)倉(cāng)庫(kù)中多維關(guān)聯(lián)規(guī)則的MDP算法,。MDP算法通過構(gòu)造一種擴(kuò)展的前綴樹MDP-tree，將數(shù)據(jù)倉(cāng)庫(kù)中的有效信息壓縮存儲(chǔ),，再使用基于MDP-tree的MDP-mining方法快速發(fā)現(xiàn)有趣的關(guān)聯(lián)規(guī)則,。MDP算法僅需要掃描一次數(shù)據(jù)倉(cāng)庫(kù)，就可以構(gòu)造出MDP-tree,，進(jìn)而得到所有的關(guān)聯(lián)規(guī)則,。該算法還具有頻繁模式查找簡(jiǎn)捷、二次查找迅速等優(yōu)點(diǎn),。通過實(shí)驗(yàn)驗(yàn)證了MDP算法的高效性和穩(wěn)定性,，與傳統(tǒng)的多維關(guān)聯(lián)規(guī)則算法相比有更好的性能。
關(guān)鍵詞： 數(shù)據(jù)挖掘,；多維關(guān)聯(lián)規(guī)則,；FP-growth算法；MDP算法,；頻繁模式

　關(guān)聯(lián)規(guī)則挖掘[1]是數(shù)據(jù)挖掘的一個(gè)重要組成部分,，最早由AGRAWAL R在1993年提出關(guān)聯(lián)規(guī)則的問題，經(jīng)過多年的發(fā)展,，形成了很多有效關(guān)聯(lián)規(guī)則挖掘算法,，如Apriori算法、FP-growth算法等,。范明[1]等人提出用改進(jìn)的Apriori算法來挖掘數(shù)據(jù)立方體的關(guān)聯(lián)規(guī)則,，高學(xué)東[2]等人提出的Apriori_Cube算法也是通過改造Apriori算法進(jìn)而在數(shù)據(jù)立方體中挖掘多維關(guān)聯(lián)規(guī)則,。但傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法依然存在一些問題：（1）主要集中在事務(wù)數(shù)據(jù)庫(kù)的應(yīng)用上，而目前廣泛用于數(shù)據(jù)分析的是關(guān)系數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù),，與事務(wù)數(shù)據(jù)庫(kù)在結(jié)構(gòu)和處理方法上有很大的差異,；（2）集中在布爾型的事務(wù)項(xiàng)集的基礎(chǔ)上，對(duì)關(guān)系數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的多維數(shù)據(jù),，其處理方式不適合,；（3）目前基于關(guān)系數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的多維關(guān)聯(lián)規(guī)則挖掘算法雖然大多都是有效的，但當(dāng)數(shù)據(jù)量比較大時(shí),，這些算法的性能不太好,。針對(duì)以上問題，本文在分析了關(guān)聯(lián)規(guī)則的性能瓶頸和多維關(guān)聯(lián)規(guī)則的基本特征后,，提出了一種高效的多維關(guān)聯(lián)規(guī)則算法。
1 算法描述
1.1 MDP算法的基本思想
　多維關(guān)聯(lián)規(guī)則是指從關(guān)系數(shù)據(jù)庫(kù)或者數(shù)據(jù)倉(cāng)庫(kù)中的有趣關(guān)聯(lián)規(guī)則,。多維關(guān)聯(lián)規(guī)則的基本概念最早是由KAMBER M.等人在1997年提出的,，關(guān)聯(lián)規(guī)則的支持度和置信度通過數(shù)據(jù)立方體的COUNT值來計(jì)算。同時(shí)他們還提出了基于元規(guī)則的多維關(guān)聯(lián)規(guī)則算法multi-D-slicing算法和n-D cube search算法,。隨后不少學(xué)者在多維關(guān)聯(lián)規(guī)則研究做出了不少努力,，提出的多維關(guān)聯(lián)規(guī)則算法大多是基于Apriori算法的改進(jìn)算法[3-5]。
經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn),，當(dāng)數(shù)據(jù)立方體很大或者支持度較小時(shí),，multi-D-slicing算法和n-D cube search算法的運(yùn)行時(shí)間會(huì)急劇增加。主要是因?yàn)檫@些算法需要多次數(shù)據(jù)立方體的掃描,，并且還要通過模式匹配遍歷掃描得到的數(shù)據(jù)集,。如果能將數(shù)據(jù)立方體的掃描減少到最低，則算法性能一定會(huì)有大幅的提升,?；谶@樣的思想，本文提出了一種只需要一次數(shù)據(jù)立方體掃描的MDP（Multi-Dimensional Pattern）算法,。
　MDP算法首先引入一種新的數(shù)據(jù)結(jié)構(gòu)MDP-tree,。它是一種擴(kuò)展的前綴樹結(jié)構(gòu)，用于壓縮存儲(chǔ)數(shù)據(jù)立方體中的數(shù)據(jù),。MDP-tree的結(jié)點(diǎn)的排序方式使越頻繁的謂詞對(duì)應(yīng)的樹中結(jié)點(diǎn)越容易被共享,。同時(shí)，對(duì)數(shù)據(jù)立方體的每一維建立了一個(gè)謂詞索引表Header Table,，用來鏈接MDP-tree中該維謂詞對(duì)應(yīng)的相同的結(jié)點(diǎn),，從而很容易求得數(shù)據(jù)立方體的任一切片。本文還提出了一種基于MDP-tree的關(guān)聯(lián)規(guī)則挖掘方法MDP-mining,，可以直接從MDP-tree中迅速得到所有的強(qiáng)關(guān)聯(lián)規(guī)則,。
MDP算法步驟主要由MDP-tree的構(gòu)建和基于MDP-tree的頻繁模式挖掘兩步組成,。
1.2 MDP-tree的設(shè)計(jì)和構(gòu)造
　MDP-tree的設(shè)計(jì)原則是一次數(shù)據(jù)立方體掃描和壓縮存儲(chǔ)數(shù)據(jù)立方體信息的內(nèi)存空間：
　（1）如果僅掃描一次數(shù)據(jù)立方體,，則MDP-tree必須存儲(chǔ)完整的數(shù)據(jù)立方體信息,，而不是頻繁的最大謂詞集。因?yàn)橛?jì)算頻繁謂詞集的置信度時(shí),，需要關(guān)聯(lián)規(guī)則對(duì)應(yīng)的數(shù)據(jù)立方體切塊,。如果只是存儲(chǔ)頻繁謂詞集，則會(huì)過濾掉一些本身不頻繁,，但子集是頻繁的謂詞集,。
　（2）如果存儲(chǔ)所有的信息,，則需要一種能壓縮數(shù)據(jù)并維持原謂詞關(guān)系的數(shù)據(jù)結(jié)構(gòu),，前綴樹是一種很好的選擇。這就需要對(duì)謂詞集進(jìn)行排序,，根據(jù)數(shù)據(jù)立方體的性質(zhì),，很容易得到各個(gè)維的SUM值，以SUM值來對(duì)謂詞集排序：SUM值最小的維中謂詞重復(fù)出現(xiàn)最經(jīng)常,，對(duì)應(yīng)的謂詞位于前綴樹的第一層,；SUM值最大的維中謂詞重復(fù)出現(xiàn)最不經(jīng)常，可以作為前綴樹的葉子結(jié)點(diǎn),；其他維按照SUM值由小到大的順序在樹中分層排列,。
　（3）求頻繁謂詞集的置信度時(shí),，需要關(guān)聯(lián)規(guī)則對(duì)應(yīng)的數(shù)據(jù)立方體切塊,。如果為此每次都要遍歷整棵樹，則時(shí)間消耗較大,。因此引入了謂詞索引表,，謂詞索引表依據(jù)數(shù)據(jù)立方體的維分別建立。每個(gè)謂詞索引表存放該維的所有謂詞,，并建立樹中對(duì)應(yīng)結(jié)點(diǎn)的鏈接,。通過謂詞索引表直接得到相關(guān)謂詞的切塊，有效降低了時(shí)間消耗,。
　基于以上的設(shè)計(jì)原則構(gòu)造成的MDP-tree如下：
?。?）MDP-tree組成
　MDP-tree包含一個(gè)標(biāo)記為”root”的根結(jié)點(diǎn)，以根結(jié)點(diǎn)的孩子結(jié)點(diǎn)為根的前綴子樹集合和數(shù)據(jù)立方體每個(gè)維對(duì)應(yīng)的謂詞索引表Header Table,。
?。?）Header Table結(jié)構(gòu)及構(gòu)建過程
結(jié)點(diǎn)結(jié)構(gòu)：Header Table的結(jié)點(diǎn)包含謂詞標(biāo)識(shí)符、指向下一個(gè)結(jié)點(diǎn)的*next指針和指向樹中同名結(jié)點(diǎn)的*link指針三個(gè)屬性。
　構(gòu)建過程：根據(jù)掃描數(shù)據(jù)立方體得到的維數(shù)和謂詞,，每個(gè)維單獨(dú)建立一個(gè)謂詞索引表,，包含該維內(nèi)掃描得到的不重復(fù)謂詞。
?。?）MDP-tree結(jié)構(gòu)及構(gòu)建過程
　結(jié)點(diǎn)結(jié)構(gòu)：MDP-tree的結(jié)點(diǎn)包含謂詞標(biāo)識(shí)符,、計(jì)數(shù)Count、指向父親結(jié)點(diǎn)的指針*parent,、指向孩子結(jié)點(diǎn)的指針*child和指向同名謂詞的鏈接*link,。
　構(gòu)建過程：根據(jù)各維SUM值由大到小的順序?qū)Ω骶S排序，SUM值最小的維為MDP-tree的第一層結(jié)點(diǎn),；SUM值最大的為葉子結(jié)點(diǎn),。然后遍歷數(shù)據(jù)立方體的數(shù)據(jù)集，在MDP-tree中查找對(duì)應(yīng)結(jié)點(diǎn),，如果存在該結(jié)點(diǎn),，則將其Count數(shù)相加；如果不存在,，則按照剛才的分層順序建立結(jié)點(diǎn),。檢查頭鏈表中相應(yīng)結(jié)點(diǎn)，若其鏈接為空,，則將其鏈接到該結(jié)點(diǎn)上；否則,，找到該鏈接的最后一個(gè)結(jié)點(diǎn),，將其鏈接到該結(jié)點(diǎn)上。
1.3 MDP-tree的性質(zhì)

　由MDP-tree的構(gòu)建過程可以得到幾條重要的性質(zhì)：
　性質(zhì)1 MDP-tree的完備性：給定一個(gè)數(shù)據(jù)立方體C,，它對(duì)應(yīng)的MDP-tree包含該數(shù)據(jù)立方體的完備信息,。
　證明：由MDP-tree的構(gòu)建過程可知，任一數(shù)據(jù)立方體中記錄都映射到MDP-tree中的一條路徑,，并且對(duì)應(yīng)的Count值也完整地保存到了樹的結(jié)點(diǎn)中,，各維信息也通過謂詞索引表Header Table記錄。因此對(duì)關(guān)聯(lián)規(guī)則挖掘來說,，MDP-tree的信息是完備的,。
　性質(zhì)2 MDP-tree中葉子結(jié)點(diǎn)等高，并且MDP-tree的高度由數(shù)據(jù)立方體的維數(shù)決定,。
　證明：由MDP-tree的構(gòu)建過程可知,，任一數(shù)據(jù)立方體中記錄都映射到MDP-tree中的一條路徑。數(shù)據(jù)立方體中的記錄都是等長(zhǎng)的,，所以MDP-tree中葉子結(jié)點(diǎn)是等高的,。如果不考慮樹的根結(jié)點(diǎn)，則樹的深度和數(shù)據(jù)立方體的維數(shù)是一致的,。
　引理 葉子結(jié)點(diǎn)的計(jì)數(shù)最?。篗DP-tree的葉子結(jié)點(diǎn)Count值是該結(jié)點(diǎn)到根結(jié)點(diǎn)路徑中最小的,。
　證明：設(shè)數(shù)據(jù)立方體C，（a1,，a2,，…an）是MDP-tree中的一條根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的完整路徑，且（a1,，a2,，…an）?奐C。若謂詞a1,，a2,，…an在C的記錄中只出現(xiàn)一次，則MDP-tree中Count（a1）=Count（a2）=…=Count（an）,；若前綴路徑a1,，a2，…an-1在其他記錄中出現(xiàn),，則Count（a1）= Count（a2）=…=Count（an-1）>Count（an）,；若前綴路徑中部分謂詞在其他記錄中出現(xiàn)，如b1,，a2,，…an，則（b1,，a2,，…an）和（a1，a2,，…an）在MDP-tree中屬于不同的路徑,，路徑（a1，a2,，…an）中Count（a1）=Count（a2）=…=Count（an）,。所以葉子結(jié)點(diǎn)具有該路徑上所有結(jié)點(diǎn)的最小計(jì)數(shù)。
　定理 葉子結(jié)點(diǎn)決定整條路徑的頻繁性：如果MDP-tree的葉子結(jié)點(diǎn)是頻繁謂詞,，則該葉子結(jié)點(diǎn)到根結(jié)點(diǎn)之間路徑對(duì)應(yīng)的謂詞集是頻繁的,；反之，如果葉子結(jié)點(diǎn)是不頻繁的,，則該謂詞集是不頻繁的,。
證明：由引理可知，MDP-tree的葉子結(jié)點(diǎn)具有最小的支持?jǐn)?shù),。所以葉子結(jié)點(diǎn)是頻繁謂詞,，該謂詞集就是頻繁謂詞集，反之亦然。
2 算法驗(yàn)證
　參考文獻(xiàn)[7]中已經(jīng)驗(yàn)證了多維關(guān)聯(lián)規(guī)則算法中n-D cube search算法優(yōu)于multi-D-slicing算法,，因此,，將對(duì)本文提出的MDP算法和性能較好的n-D cube search算法進(jìn)行比較，通過實(shí)驗(yàn)來驗(yàn)證MDP算法的性能,。
2.1 實(shí)驗(yàn)環(huán)境及工具
　為了準(zhǔn)確地評(píng)價(jià)算法性能,，本文實(shí)現(xiàn)了MDP算法和n-D cube search算法。實(shí)驗(yàn)平臺(tái)的配置如表1所示,。
2.2 實(shí)驗(yàn)數(shù)據(jù)
　本實(shí)驗(yàn)的數(shù)據(jù)來自Microsoft SQL Server 2000 Analysis Service附帶的FoodMart2000數(shù)據(jù)庫(kù),。FoodMart公司是一家在美國(guó)、加拿大和墨西哥等地銷售食品和其他商品的零售連鎖店,，銷售記錄數(shù)據(jù)庫(kù)FoodMart2000中存有該公司1997年和1998年的銷售記錄,，包括商品、客戶和銷售時(shí)間等信息,。本實(shí)驗(yàn)數(shù)據(jù)取自該公司1998年的銷售記錄,，共有1 560件商品，10 280個(gè)客戶和164 558個(gè)銷售記錄,。依據(jù)該數(shù)據(jù),，分商品、客戶和時(shí)間三個(gè)維度來建立數(shù)據(jù)立方體,。
2.3 實(shí)驗(yàn)結(jié)果分析
　實(shí)驗(yàn)從數(shù)據(jù)立方體的大小,、關(guān)聯(lián)規(guī)則的最小支持度和最小置信度等方面來考察各個(gè)算法的時(shí)間消耗。
?。?）數(shù)據(jù)立方體大小變化對(duì)算法性能的影響
　圖1是數(shù)據(jù)立方體大小改變時(shí)對(duì)各算法的運(yùn)行時(shí)間的影響,。從圖中可以看出，兩種算法的運(yùn)行時(shí)間都隨著數(shù)據(jù)立方體的增大而變大,，其中n-D cube search算法受數(shù)據(jù)立方體的大小影響較大。在數(shù)據(jù)立方體比較小的時(shí)候,，n-D cube search算法的性能甚至優(yōu)于MDP算法,，因?yàn)殡m然n-D cube search算法會(huì)多次遍歷數(shù)據(jù)立方體，而MDP算法構(gòu)造MDP-tree需要一定的時(shí)間,。隨著數(shù)據(jù)立方體的增大,，需要多次掃描數(shù)據(jù)立方體的n-D cube search算法的運(yùn)行時(shí)間也會(huì)大增，而MDP-tree算法運(yùn)行時(shí)間增長(zhǎng)緩慢,，因?yàn)镸DP-tree只需要掃描一次數(shù)據(jù)立方體,，性能受數(shù)據(jù)立方體的大小影響不大。從圖1還可以看出,，MDP算法的運(yùn)行時(shí)間增長(zhǎng)十分平穩(wěn),，說明MDP算法有較好的可伸縮性。

　圖2是數(shù)據(jù)立方體大小改變時(shí)對(duì)算法內(nèi)存消耗的影響。從圖中可以看出,，隨著數(shù)據(jù)立方體的增大,，n-D cube search算法和MDP算法消耗的內(nèi)存都在增加。當(dāng)數(shù)據(jù)立方體較小時(shí),， MDP算法消耗的內(nèi)存較小,。但隨著數(shù)據(jù)立方體的增大，需要更多的內(nèi)存空間來構(gòu)造MDP-tree,，因此MDP算法的內(nèi)存消耗增加更快,，逐漸大于n-D cube search算法的內(nèi)存消耗。
?。?）最小支持度變化對(duì)算法性能的影響
　圖3是支持度變化時(shí),，n-D cube search算法和MDP算法運(yùn)行時(shí)間結(jié)果。從圖中可以看出,，隨著支持度的增大,，兩種算法的運(yùn)行時(shí)間都在減少，因?yàn)殡S著支持度的增大,，得到的頻繁謂詞集也會(huì)減少,，使求出強(qiáng)關(guān)聯(lián)規(guī)則的時(shí)間也更少。但由于n-D cube search算法初始頻繁謂詞集比較多時(shí),，n-D cube search算法需要很多的運(yùn)行時(shí)間,，因此n-D cube search算法的運(yùn)行時(shí)間減少得更快。而MDP算法在建立MDP-tree時(shí)是不考慮最小支持度的,，所以支持度的變化對(duì)MDP算法的運(yùn)行時(shí)間影響不大,。

　（3）MDP算法的二次查詢優(yōu)化
　由于MDP算法的MDP-tree與關(guān)聯(lián)規(guī)則的最小支持度和最小置信度無關(guān),，因此,，當(dāng)最小支持度或最小置信度改變時(shí)，不需要重新構(gòu)建新的MDP-tree,。圖4是最小支持度變化時(shí)不用構(gòu)建新的MDP-tree的MDP算法的運(yùn)行時(shí)間結(jié)果,。從圖中可以看出，第一次輸入最小支持度時(shí)需要構(gòu)建MDP-tree,，運(yùn)行時(shí)間比較長(zhǎng),；當(dāng)改變最小支持度時(shí)，不再需要重新構(gòu)建MDP-tree,，MDP算法的運(yùn)行時(shí)間就會(huì)大幅度降低,，而且隨著最小支持度的變化緩慢改變。
　本文針對(duì)傳統(tǒng)的多維關(guān)聯(lián)規(guī)則算法在處理數(shù)據(jù)量大或者頻繁模式長(zhǎng)時(shí)存在時(shí)間消耗較大的問題,，提出了一種高效的多維關(guān)聯(lián)規(guī)則的MDP算法,。該算法通過構(gòu)造一種擴(kuò)展的前綴樹MDP-tree,，將數(shù)據(jù)倉(cāng)庫(kù)中的有效信息壓縮存儲(chǔ)，再使用基于MDP-tree的MDP-mining方法來發(fā)現(xiàn)有趣的關(guān)聯(lián)規(guī)則,，通過實(shí)驗(yàn)驗(yàn)證了該算法的工作過程以及其優(yōu)越性,。
參考文獻(xiàn)
[1] 范明，牛常勇,，朱琰.一種挖掘多維關(guān)聯(lián)規(guī)則的有效算法[J].計(jì)算機(jī)科學(xué),，2001，28（11）.
[2] 高學(xué)東,，王文賢,，武森.基于數(shù)據(jù)立方體的多維關(guān)聯(lián)規(guī)則的挖掘方法[J].計(jì)算機(jī)工程，2003,，29（14）.
[3] DONG G,， HAN J. Mining constrained gradients in large databases[J]. IEEE Transactions on Knowledge and Data Engineering， 2004,， 16（8）：922-938.
[4] TJIOE H,， TANIAR D. Mining association rules in data warehouses[J]. International Journal of Data Warehousing and Mining， 2005,， 1（3）：28–62.
[5] TJIOE H,， TANIAR D. A framework for mining association rules in data ware houses[M]. Springer-Verlag Berlin Heidelberg， 2004： 159-165.