一種新的MDP算法的研究*

高集榮，田 艷，楊永紅，黨運峰

（中山大學 信息科學與技術學院，廣東 廣州 510006）

關聯(lián)規(guī)則挖掘[1]是數(shù)據(jù)挖掘的一個重要組成部分，最早由AGRAWAL R在1993年提出關聯(lián)規(guī)則的問題，經(jīng)過多年的發(fā)展，形成了很多有效關聯(lián)規(guī)則挖掘算法，如Apriori算法、FP-growth算法等。范明[1]等人提出用改進的Apriori算法來挖掘數(shù)據(jù)立方體的關聯(lián)規(guī)則，高學東[2]等人提出的Apriori_Cube算法也是通過改造Apriori算法進而在數(shù)據(jù)立方體中挖掘多維關聯(lián)規(guī)則。但傳統(tǒng)的關聯(lián)規(guī)則挖掘算法依然存在一些問題：（1）主要集中在事務數(shù)據(jù)庫的應用上，而目前廣泛用于數(shù)據(jù)分析的是關系數(shù)據(jù)庫和數(shù)據(jù)倉庫，與事務數(shù)據(jù)庫在結(jié)構(gòu)和處理方法上有很大的差異；（2）集中在布爾型的事務項集的基礎上，對關系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維數(shù)據(jù)，其處理方式不適合；（3）目前基于關系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關聯(lián)規(guī)則挖掘算法雖然大多都是有效的，但當數(shù)據(jù)量比較大時，這些算法的性能不太好。針對以上問題，本文在分析了關聯(lián)規(guī)則的性能瓶頸和多維關聯(lián)規(guī)則的基本特征后，提出了一種高效的多維關聯(lián)規(guī)則算法。

1 算法描述

1.1 MDP算法的基本思想

多維關聯(lián)規(guī)則是指從關系數(shù)據(jù)庫或者數(shù)據(jù)倉庫中的有趣關聯(lián)規(guī)則。多維關聯(lián)規(guī)則的基本概念最早是由KAMBER M.等人在1997年提出的，關聯(lián)規(guī)則的支持度和置信度通過數(shù)據(jù)立方體的COUNT值來計算。同時他們還提出了基于元規(guī)則的多維關聯(lián)規(guī)則算法multi-D-slicing算法和n-D cube search算法。隨后不少學者在多維關聯(lián)規(guī)則研究做出了不少努力，提出的多維關聯(lián)規(guī)則算法大多是基于Apriori算法的改進算法[3-5]。

經(jīng)過實驗發(fā)現(xiàn)，當數(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é)點的排序方式使越頻繁的謂詞對應的樹中結(jié)點越容易被共享。同時，對數(shù)據(jù)立方體的每一維建立了一個謂詞索引表Header Table，用來鏈接MDP-tree中該維謂詞對應的相同的結(jié)點，從而很容易求得數(shù)據(jù)立方體的任一切片。本文還提出了一種基于MDP-tree的關聯(lián)規(guī)則挖掘方法MDP-mining，可以直接從MDP-tree中迅速得到所有的強關聯(lián)規(guī)則。

MDP算法步驟主要由MDP-tree的構(gòu)建和基于MDP-tree的頻繁模式挖掘兩步組成。

1.2 MDP-tree的設計和構(gòu)造

MDP-tree的設計原則是一次數(shù)據(jù)立方體掃描和壓縮存儲數(shù)據(jù)立方體信息的內(nèi)存空間：

（1）如果僅掃描一次數(shù)據(jù)立方體，則 MDP-tree必須存儲完整的數(shù)據(jù)立方體信息，而不是頻繁的最大謂詞集。因為計算頻繁謂詞集的置信度時，需要關聯(lián)規(guī)則對應的數(shù)據(jù)立方體切塊。如果只是存儲頻繁謂詞集，則會過濾掉一些本身不頻繁，但子集是頻繁的謂詞集。

（2）如果存儲所有的信息，則需要一種能壓縮數(shù)據(jù)并維持原謂詞關系的數(shù)據(jù)結(jié)構(gòu)，前綴樹是一種很好的選擇。這就需要對謂詞集進行排序，根據(jù)數(shù)據(jù)立方體的性質(zhì)，很容易得到各個維的SUM值，以SUM值來對謂詞集排序：SUM值最小的維中謂詞重復出現(xiàn)最經(jīng)常，對應的謂詞位于前綴樹的第一層；SUM值最大的維中謂詞重復出現(xiàn)最不經(jīng)常，可以作為前綴樹的葉子結(jié)點；其他維按照SUM值由小到大的順序在樹中分層排列。

（3）求頻繁謂詞集的置信度時，需要關聯(lián)規(guī)則對應的數(shù)據(jù)立方體切塊。如果為此每次都要遍歷整棵樹，則時間消耗較大。因此引入了謂詞索引表，謂詞索引表依據(jù)數(shù)據(jù)立方體的維分別建立。每個謂詞索引表存放該維的所有謂詞，并建立樹中對應結(jié)點的鏈接。通過謂詞索引表直接得到相關謂詞的切塊，有效降低了時間消耗。

基于以上的設計原則構(gòu)造成的MDP-tree如下：

（1）MDP-tree組成

MDP-tree包含一個標記為”root”的根結(jié)點，以根結(jié)點的孩子結(jié)點為根的前綴子樹集合和數(shù)據(jù)立方體每個維對應的謂詞索引表Header Table。

（2）Header Table結(jié)構(gòu)及構(gòu)建過程

結(jié)點結(jié)構(gòu)：Header Table的結(jié)點包含謂詞標識符、指向下一個結(jié)點的*next指針和指向樹中同名結(jié)點的*link指針三個屬性。

構(gòu)建過程：根據(jù)掃描數(shù)據(jù)立方體得到的維數(shù)和謂詞，每個維單獨建立一個謂詞索引表，包含該維內(nèi)掃描得到的不重復謂詞。

（3）MDP-tree結(jié)構(gòu)及構(gòu)建過程

結(jié)點結(jié)構(gòu)：MDP-tree的結(jié)點包含謂詞標識符、計數(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中查找對應結(jié)點，如果存在該結(jié)點，則將其Count數(shù)相加；如果不存在，則按照剛才的分層順序建立結(jié)點。檢查頭鏈表中相應結(jié)點，若其鏈接為空，則將其鏈接到該結(jié)點上；否則，找到該鏈接的最后一個結(jié)點，將其鏈接到該結(jié)點上。

1.3 MDP-tree的性質(zhì)

由MDP-tree的構(gòu)建過程可以得到幾條重要的性質(zhì)：

性質(zhì)1 MDP-tree的完備性：給定一個數(shù)據(jù)立方體C，它對應的MDP-tree包含該數(shù)據(jù)立方體的完備信息。

證明：由MDP-tree的構(gòu)建過程可知，任一數(shù)據(jù)立方體中記錄都映射到MDP-tree中的一條路徑，并且對應的Count值也完整地保存到了樹的結(jié)點中，各維信息也通過謂詞索引表Header Table記錄。因此對關聯(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ù)據(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é)點之間路徑對應的謂詞集是頻繁的；反之，如果葉子結(jié)點是不頻繁的，則該謂詞集是不頻繁的。

證明：由引理可知，MDP-tree的葉子結(jié)點具有最小的支持數(shù)。所以葉子結(jié)點是頻繁謂詞，該謂詞集就是頻繁謂詞集，反之亦然。

2 算法驗證

[7]中已經(jīng)驗證了多維關聯(lián)規(guī)則算法中n-D cube search算法優(yōu)于multi-D-slicing算法，因此，將對本文提出的MDP算法和性能較好的n-D cube search算法進行比較，通過實驗來驗證MDP算法的性能。

2.1 實驗環(huán)境及工具

為了準確地評價算法性能，本文實現(xiàn)了MDP算法和n-D cube search算法。實驗平臺的配置如表1所示。

表1 實驗平臺配置

2.2 實驗數(shù)據(jù)

本實驗的數(shù)據(jù)來自MicrosoftSQLServer2000 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ù)立方體的大小、關聯(lián)規(guī)則的最小支持度和最小置信度等方面來考察各個算法的時間消耗。

（1）數(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)存都在增加。當數(shù)據(jù)立方體較小時，MDP算法消耗的內(nèi)存較小。但隨著數(shù)據(jù)立方體的增大，需要更多的內(nèi)存空間來構(gòu)造MDP-tree，因此MDP算法的內(nèi)存消耗增加更快，逐漸大于n-D cube search算法的內(nèi)存消耗。

圖1 數(shù)據(jù)立方體大小變化對各算法運行時間的影響

圖2 數(shù)據(jù)立方體的大小變化對算法內(nèi)存消耗的影響

（2）最小支持度變化對算法性能的影響

圖3是支持度變化時，n-D cubesearch算法和MDP算法運行時間結(jié)果。從圖中可以看出，隨著支持度的增大，兩種算法的運行時間都在減少，因為隨著支持度的增大，得到的頻繁謂詞集也會減少，使求出強關聯(lián)規(guī)則的時間也更少。但由于n-D cube search算法初始頻繁謂詞集比較多時，n-D cube search算法需要很多的運行時間，因此n-D cube search算法的運行時間減少得更快。而MDP算法在建立MDP-tree時是不考慮最小支持度的，所以支持度的變化對MDP算法的運行時間影響不大。

（3）MDP算法的二次查詢優(yōu)化

由于MDP算法的MDP-tree與關聯(lián)規(guī)則的最小支持度和最小置信度無關，因此，當最小支持度或最小置信度改變時，不需要重新構(gòu)建新的MDP-tree。圖4是最小支持度變化時不用構(gòu)建新的MDP-tree的MDP算法的運行時間結(jié)果。從圖中可以看出，第一次輸入最小支持度時需要構(gòu)建MDP-tree，運行時間比較長；當改變最小支持度時，不再需要重新構(gòu)建MDP-tree，MDP算法的運行時間就會大幅度降低，而且隨著最小支持度的變化緩慢改變。

圖3 支持度變化對各算法運行時間的影響

圖4 MDP算法的二次查找優(yōu)化

本文針對傳統(tǒng)的多維關聯(lián)規(guī)則算法在處理數(shù)據(jù)量大或者頻繁模式長時存在時間消耗較大的問題，提出了一種高效的多維關聯(lián)規(guī)則的MDP算法。該算法通過構(gòu)造一種擴展的前綴樹MDP-tree，將數(shù)據(jù)倉庫中的有效信息壓縮存儲，再使用基于MDP-tree的MDP-mining方法來發(fā)現(xiàn)有趣的關聯(lián)規(guī)則，通過實驗驗證了該算法的工作過程以及其優(yōu)越性。

參考文獻

[1]范明，牛常勇，朱琰.一種挖掘多維關聯(lián)規(guī)則的有效算法[J].計算機科學，2001，28（11）.

[2]高學東，王文賢，武森.基于數(shù)據(jù)立方體的多維關聯(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 rulesin data ware houses[M].Springer-Verlag Berlin Heidelberg， 2004： 159-165.