摘  要： 提出了一種高效的挖掘數(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算法來(lái)挖掘數(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值來(lái)計(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，用來(lái)鏈接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值來(lái)對(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如下：
　（1）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ī)則挖掘來(lái)說，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ù)最小：MDP-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)來(lái)驗(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ù)來(lái)自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è)維度來(lái)建立數(shù)據(jù)立方體。
2.3 實(shí)驗(yàn)結(jié)果分析
　實(shí)驗(yàn)從數(shù)據(jù)立方體的大小、關(guān)聯(lián)規(guī)則的最小支持度和最小置信度等方面來(lái)考察各個(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)存空間來(lá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í)間影響不大。

?。?）MDP算法的二次查詢優(yōu)化
　由于MDP算法的MDP-tree與關(guān)聯(lián)規(guī)則的最小支持度和最小置信度無(wú)關(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方法來(lái)發(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.