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

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

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

?。?）MDP算法的二次查詢優(yōu)化
　由于MDP算法的MDP-tree與關(guān)聯(lián)規(guī)則的最小支持度和最小置信度無關(guān)，因此，當(dāng)最小支持度或最小置信度改變時，不需要重新構(gòu)建新的MDP-tree。圖4是最小支持度變化時不用構(gòu)建新的MDP-tree的MDP算法的運行時間結(jié)果。從圖中可以看出，第一次輸入最小支持度時需要構(gòu)建MDP-tree，運行時間比較長；當(dāng)改變最小支持度時，不再需要重新構(gòu)建MDP-tree，MDP算法的運行時間就會大幅度降低，而且隨著最小支持度的變化緩慢改變。
　本文針對傳統(tǒng)的多維關(guān)聯(lián)規(guī)則算法在處理數(shù)據(jù)量大或者頻繁模式長時存在時間消耗較大的問題，提出了一種高效的多維關(guān)聯(lián)規(guī)則的MDP算法。該算法通過構(gòu)造一種擴展的前綴樹MDP-tree，將數(shù)據(jù)倉庫中的有效信息壓縮存儲，再使用基于MDP-tree的MDP-mining方法來發(fā)現(xiàn)有趣的關(guān)聯(lián)規(guī)則，通過實驗驗證了該算法的工作過程以及其優(yōu)越性。
參考文獻(xiàn)
[1] 范明，牛常勇，朱琰.一種挖掘多維關(guān)聯(lián)規(guī)則的有效算法[J].計算機科學(xué)，2001，28（11）.
[2] 高學(xué)東，王文賢，武森.基于數(shù)據(jù)立方體的多維關(guān)聯(lián)規(guī)則的挖掘方法[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.