摘 要： 提出了一种高效的挖掘数据仓库中多维关联规则的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）求频繁谓词集的置信度时，需要关联规则对应的数据立方体切块。如果为此每次都要遍历整棵树，则时间消耗较大。因此引入了谓词索引表，谓词索引表依据数据立方体的维分别建立。每个谓词索引表存放该维的所有谓词，并建立树中对应结点的链接。通过谓词索引表直接得到相关谓词的切块，有效降低了时间消耗。
