摘 要：提出了一种高效的挖掘数据仓库中多维关联规则的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.