摘 要： 提出了一種高效的挖掘數據倉庫中多維關聯規則的MDP算法。MDP算法通過構造一種擴展的前綴樹MDP-tree，將數據倉庫中的有效信息壓縮存儲，再使用基于MDP-tree的MDP-mining方法快速發現有趣的關聯規則。MDP算法僅需要掃描一次數據倉庫，就可以構造出MDP-tree，進而得到所有的關聯規則。該算法還具有頻繁模式查找簡捷、二次查找迅速等優點。通過實驗驗證了MDP算法的高效性和穩定性，與傳統的多維關聯規則算法相比有更好的性能。
關鍵詞： 數據挖掘；多維關聯規則；FP-growth算法；MDP算法；頻繁模式
關聯規則挖掘[1]是數據挖掘的一個重要組成部分，最早由AGRAWAL R在1993年提出關聯規則的問題，經過多年的發展，形成了很多有效關聯規則挖掘算法，如Apriori算法、FP-growth算法等。范明[1]等人提出用改進的Apriori算法來挖掘數據立方體的關聯規則，高學東[2]等人提出的Apriori_Cube算法也是通過改造Apriori算法進而在數據立方體中挖掘多維關聯規則。但傳統的關聯規則挖掘算法依然存在一些問題：（1）主要集中在事務數據庫的應用上，而目前廣泛用于數據分析的是關系數據庫和數據倉庫，與事務數據庫在結構和處理方法上有很大的差異；（2）集中在布爾型的事務項集的基礎上，對關系數據庫和數據倉庫的多維數據，其處理方式不適合；（3）目前基于關系數據庫和數據倉庫的多維關聯規則挖掘算法雖然大多都是有效的，但當數據量比較大時，這些算法的性能不太好。針對以上問題，本文在分析了關聯規則的性能瓶頸和多維關聯規則的基本特征后，提出了一種高效的多維關聯規則算法。
1 算法描述
1.1 MDP算法的基本思想
多維關聯規則是指從關系數據庫或者數據倉庫中的有趣關聯規則。多維關聯規則的基本概念最早是由KAMBER M.等人在1997年提出的，關聯規則的支持度和置信度通過數據立方體的COUNT值來計算。同時他們還提出了基于元規則的多維關聯規則算法multi-D-slicing算法和n-D cube search算法。隨后不少學者在多維關聯規則研究做出了不少努力，提出的多維關聯規則算法大多是基于Apriori算法的改進算法[3-5]。
經過實驗發現，當數據立方體很大或者支持度較小時，multi-D-slicing算法和n-D cube search算法的運行時間會急劇增加。主要是因為這些算法需要多次數據立方體的掃描，并且還要通過模式匹配遍歷掃描得到的數據集。如果能將數據立方體的掃描減少到最低，則算法性能一定會有大幅的提升。基于這樣的思想，本文提出了一種只需要一次數據立方體掃描的MDP（Multi-Dimensional Pattern）算法。
MDP算法首先引入一種新的數據結構MDP-tree。它是一種擴展的前綴樹結構，用于壓縮存儲數據立方體中的數據。MDP-tree的結點的排序方式使越頻繁的謂詞對應的樹中結點越容易被共享。同時，對數據立方體的每一維建立了一個謂詞索引表Header Table，用來鏈接MDP-tree中該維謂詞對應的相同的結點，從而很容易求得數據立方體的任一切片。本文還提出了一種基于MDP-tree的關聯規則挖掘方法MDP-mining，可以直接從MDP-tree中迅速得到所有的強關聯規則。
MDP算法步驟主要由MDP-tree的構建和基于MDP-tree的頻繁模式挖掘兩步組成。
1.2 MDP-tree的設計和構造
MDP-tree的設計原則是一次數據立方體掃描和壓縮存儲數據立方體信息的內存空間：
（1）如果僅掃描一次數據立方體，則MDP-tree必須存儲完整的數據立方體信息，而不是頻繁的最大謂詞集。因為計算頻繁謂詞集的置信度時，需要關聯規則對應的數據立方體切塊。如果只是存儲頻繁謂詞集，則會過濾掉一些本身不頻繁，但子集是頻繁的謂詞集。
（2）如果存儲所有的信息，則需要一種能壓縮數據并維持原謂詞關系的數據結構，前綴樹是一種很好的選擇。這就需要對謂詞集進行排序，根據數據立方體的性質，很容易得到各個維的SUM值，以SUM值來對謂詞集排序：SUM值最小的維中謂詞重復出現最經常，對應的謂詞位于前綴樹的第一層；SUM值最大的維中謂詞重復出現最不經常，可以作為前綴樹的葉子結點；其他維按照SUM值由小到大的順序在樹中分層排列。
（3）求頻繁謂詞集的置信度時，需要關聯規則對應的數據立方體切塊。如果為此每次都要遍歷整棵樹，則時間消耗較大。因此引入了謂詞索引表，謂詞索引表依據數據立方體的維分別建立。每個謂詞索引表存放該維的所有謂詞，并建立樹中對應結點的鏈接。通過謂詞索引表直接得到相關謂詞的切塊，有效降低了時間消耗。
基于以上的設計原則構造成的MDP-tree如下：
（1）MDP-tree組成
MDP-tree包含一個標記為”root”的根結點，以根結點的孩子結點為根的前綴子樹集合和數據立方體每個維對應的謂詞索引表Header Table。
（2）Header Table結構及構建過程
結點結構：Header Table的結點包含謂詞標識符、指向下一個結點的*next指針和指向樹中同名結點的*link指針三個屬性。
構建過程：根據掃描數據立方體得到的維數和謂詞，每個維單獨建立一個謂詞索引表，包含該維內掃描得到的不重復謂詞。
（3）MDP-tree結構及構建過程
結點結構：MDP-tree的結點包含謂詞標識符、計數Count、指向父親結點的指針*parent、指向孩子結點的指針*child和指向同名謂詞的鏈接*link。
構建過程：根據各維SUM值由大到小的順序對各維排序，SUM值最小的維為MDP-tree的第一層結點；SUM值最大的為葉子結點。然后遍歷數據立方體的數據集，在MDP-tree中查找對應結點，如果存在該結點，則將其Count數相加；如果不存在，則按照剛才的分層順序建立結點。檢查頭鏈表中相應結點，若其鏈接為空，則將其鏈接到該結點上；否則，找到該鏈接的最后一個結點，將其鏈接到該結點上。
1.3 MDP-tree的性質
由MDP-tree的構建過程可以得到幾條重要的性質：
性質1 MDP-tree的完備性：給定一個數據立方體C，它對應的MDP-tree包含該數據立方體的完備信息。
證明：由MDP-tree的構建過程可知，任一數據立方體中記錄都映射到MDP-tree中的一條路徑，并且對應的Count值也完整地保存到了樹的結點中，各維信息也通過謂詞索引表Header Table記錄。因此對關聯規則挖掘來說，MDP-tree的信息是完備的。
性質2 MDP-tree中葉子結點等高，并且MDP-tree的高度由數據立方體的維數決定。
證明：由MDP-tree的構建過程可知，任一數據立方體中記錄都映射到MDP-tree中的一條路徑。數據立方體中的記錄都是等長的，所以MDP-tree中葉子結點是等高的。如果不考慮樹的根結點，則樹的深度和數據立方體的維數是一致的。
引理 葉子結點的計數最小：MDP-tree的葉子結點Count值是該結點到根結點路徑中最小的。
證明：設數據立方體C，（a1，a2，…an）是MDP-tree中的一條根結點到葉子結點的完整路徑，且（a1，a2，…an）?奐C。若謂詞a1，a2，…an在C的記錄中只出現一次，則MDP-tree中Count（a1）=Count（a2）=…=Count（an）；若前綴路徑a1，a2，…an-1在其他記錄中出現，則Count（a1）= Count（a2）=…=Count（an-1）>Count（an）；若前綴路徑中部分謂詞在其他記錄中出現，如b1，a2，…an，則（b1，a2，…an）和（a1，a2，…an）在MDP-tree中屬于不同的路徑，路徑（a1，a2，…an）中Count（a1）=Count（a2）=…=Count（an）。所以葉子結點具有該路徑上所有結點的最小計數。
定理 葉子結點決定整條路徑的頻繁性：如果MDP-tree的葉子結點是頻繁謂詞，則該葉子結點到根結點之間路徑對應的謂詞集是頻繁的；反之，如果葉子結點是不頻繁的，則該謂詞集是不頻繁的。
證明：由引理可知，MDP-tree的葉子結點具有最小的支持數。所以葉子結點是頻繁謂詞，該謂詞集就是頻繁謂詞集，反之亦然。
2 算法驗證
參考文獻[7]中已經驗證了多維關聯規則算法中n-D cube search算法優于multi-D-slicing算法，因此，將對本文提出的MDP算法和性能較好的n-D cube search算法進行比較，通過實驗來驗證MDP算法的性能。
2.1 實驗環境及工具
為了準確地評價算法性能，本文實現了MDP算法和n-D cube search算法。實驗平臺的配置如表1所示。
2.2 實驗數據
本實驗的數據來自Microsoft SQL Server 2000 Analysis Service附帶的FoodMart2000數據庫。FoodMart公司是一家在美國、加拿大和墨西哥等地銷售食品和其他商品的零售連鎖店，銷售記錄數據庫FoodMart2000中存有該公司1997年和1998年的銷售記錄，包括商品、客戶和銷售時間等信息。本實驗數據取自該公司1998年的銷售記錄，共有1 560件商品，10 280個客戶和164 558個銷售記錄。依據該數據，分商品、客戶和時間三個維度來建立數據立方體。
2.3 實驗結果分析
實驗從數據立方體的大小、關聯規則的最小支持度和最小置信度等方面來考察各個算法的時間消耗。
（1）數據立方體大小變化對算法性能的影響
圖1是數據立方體大小改變時對各算法的運行時間的影響。從圖中可以看出，兩種算法的運行時間都隨著數據立方體的增大而變大，其中n-D cube search算法受數據立方體的大小影響較大。在數據立方體比較小的時候，n-D cube search算法的性能甚至優于MDP算法，因為雖然n-D cube search算法會多次遍歷數據立方體，而MDP算法構造MDP-tree需要一定的時間。隨著數據立方體的增大，需要多次掃描數據立方體的n-D cube search算法的運行時間也會大增，而MDP-tree算法運行時間增長緩慢，因為MDP-tree只需要掃描一次數據立方體，性能受數據立方體的大小影響不大。從圖1還可以看出，MDP算法的運行時間增長十分平穩，說明MDP算法有較好的可伸縮性。
圖2是數據立方體大小改變時對算法內存消耗的影響。從圖中可以看出，隨著數據立方體的增大，n-D cube search算法和MDP算法消耗的內存都在增加。當數據立方體較小時， MDP算法消耗的內存較小。但隨著數據立方體的增大，需要更多的內存空間來構造MDP-tree，因此MDP算法的內存消耗增加更快，逐漸大于n-D cube search算法的內存消耗。
（2）最小支持度變化對算法性能的影響
圖3是支持度變化時，n-D cube search算法和MDP算法運行時間結果。從圖中可以看出，隨著支持度的增大，兩種算法的運行時間都在減少，因為隨著支持度的增大，得到的頻繁謂詞集也會減少，使求出強關聯規則的時間也更少。但由于n-D cube search算法初始頻繁謂詞集比較多時，n-D cube search算法需要很多的運行時間，因此n-D cube search算法的運行時間減少得更快。而MDP算法在建立MDP-tree時是不考慮最小支持度的，所以支持度的變化對MDP算法的運行時間影響不大。
（3）MDP算法的二次查詢優化
由于MDP算法的MDP-tree與關聯規則的最小支持度和最小置信度無關，因此，當最小支持度或最小置信度改變時，不需要重新構建新的MDP-tree。圖4是最小支持度變化時不用構建新的MDP-tree的MDP算法的運行時間結果。從圖中可以看出，第一次輸入最小支持度時需要構建MDP-tree，運行時間比較長；當改變最小支持度時，不再需要重新構建MDP-tree，MDP算法的運行時間就會大幅度降低，而且隨著最小支持度的變化緩慢改變。
本文針對傳統的多維關聯規則算法在處理數據量大或者頻繁模式長時存在時間消耗較大的問題，提出了一種高效的多維關聯規則的MDP算法。該算法通過構造一種擴展的前綴樹MDP-tree，將數據倉庫中的有效信息壓縮存儲，再使用基于MDP-tree的MDP-mining方法來發現有趣的關聯規則，通過實驗驗證了該算法的工作過程以及其優越性。
參考文獻
[1] 范明，牛常勇，朱琰.一種挖掘多維關聯規則的有效算法[J].計算機科學，2001，28（11）.
[2] 高學東，王文賢，武森.基于數據立方體的多維關聯規則的挖掘方法[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.