分布式存储结构的频繁闭合模式挖掘并行算法

1、( 1 桂林电子科技大学 计算机科学技术系, 广西 桂林 541004;2 中国科学技术大学 电子工程与信息科学系, 安徽 合肥 230026)摘 要 : 研究分布式存储结构下频繁闭合模式挖掘的并行化问题, 针对频繁闭合模式的特点, 提出了两阶段并行判断频繁模式闭合性的方法, 基于串行算法 fpclose 和两种 fp- tree 的并行构造方式, 分别给出了两个频繁闭合模 式挖掘并行算法 dp- fp 和 dl- fp, 性能分析表明, 这两个算法具有较大的并行化, 较小的 i/o 开销与良好的负载 平衡。关 键 词 : 关联规则; 频繁模式; 频繁闭合模式; fp- tree;并行算法中

2、图 分 类 号 : tp391文 献 标 识 码 : a文 章 编 号 : 1000- 7180( 2007) 10- 0161- 03par allel algor ithm for mining fr equent closed patter ns ondistr ibuted memor y multi- pr ocessor smiao yu-qing1, yin dong21 department of computer science and technology, guilin university of electronic technology, guilin 541004,

3、 china;2 department of electronic engineering and information science, ustc, hefei 230026, china)abstr act: in this paper, we addressed the problem of parallel mining for frequent closed patterns on distributed memorymulti - processors. the two phases strategy was proposed to parallel check if a fre

4、quent pattern was closed. based on fpclose algorithm and two methods for parallel constructing fp- tree, two parallel algorithms, dp- fp and dl- fp were presented for frequent closed patterns mining. our performance study shows the two algorithms achieved parallelism maximization, disk i/o minimizat

5、ion and good workload balancing.key wor ds: association rules; frequent patterns; frequent closed patterns; fp- tree; parallel algorithm1引言频繁模式挖掘是关联规则挖掘、序列模式挖础上, 针对频繁闭合模式的特点, 提出了两阶段并行挖掘频繁闭合模式策略, 并基于这种策略和分布掘、空间和多媒体模式挖掘等许多数据挖掘任务的基础, 在市场营销、股票分析、灾害预测、医疗诊断、 生物信息学等领域有着广泛的应用。用频繁闭合模 式挖掘代替频繁模式挖掘是近些年提出的新策略, 频

6、繁闭合模式集合包含了频繁模式集合的完整信 息, 由所有频繁闭合模式可直接产生所有频繁模式 及其支持度, 但数量上通常前者比后者要少许多, 从而可大大减少计算代价。另外, 由频繁闭合模式 集合可直接产生非冗余的关联规则。式存储结构下两种并行构造 fp- tree 的方式,设计了两个基于 fp- tree 的频繁闭合模式挖掘并行算法dp- fp 和 dl- fp, 性能分析表明, 这两个算法具有 较大的并行化, 较小的 i/o 开销与良好的负载平衡, 特别是 dp- fp 算法, 可更好地实现处理器之间较少 的同步和更小的通信开销。相关概念频繁模式22.1示。y 的支持数在 d 中所占的比例称为项

7、目集 y 在d 中的支持度( support) , 用 sup( y) 表示, 即:各处理器之间不需要任何通信。但是, 算法多次扫描数据集产生投影数据集会带来高昂的 i/o 开销, 并且处理器之间严重的负载不平衡也会影响 pmine 算法的性能。鉴于频繁闭合模式挖掘串行算法 fpclose 的性sup(y)=!(y) / |d|式中, |d|为 d 中的事务总数。( 1)定义 1给定数据集 d 和一个用户指定的最小支持度阈值 minsup ( minimum support threshold) , 若 项目集 x 的支持 度 sup ( x) minsup, 则 称 x 是 频能特点,提出了

8、分布式存储结构下 fpclose 算法的并行化版本, 基于两种并行构造 fp- tree 的方式, 分别给出了两个频繁闭合模式挖掘并行算法 dp- fp和 dl- fp。繁 项 目 集pattern) 。或 频 繁 模 式 ( frequent( frequent itemset)频繁闭合模式dp- fp 算法( 1) 投影 fp- tree 的并行构造 在分布式存储结构下, 有两种并行构造 fp- tree的方式: 投影 fp- tree 与局部 fp- tree4。投影 fp- tree( project fp- tree, pfp- tree) 的并行 构造方法: 首先将频繁项目集合划分

9、为不相交的子 集均匀分配给各处理器, 然后根据频繁项目的分配 将数据集物理投影给各处理器, 各处理器再由投影 数据集构造投影 fp- tree。2.24.2定义 2设 x 是项目集, 如果不存在任何真超集 y, yx, 使 得 sup ( y) =sup ( x) , 则 称 x 是 闭 合的。如果 x 既是频繁的又是闭合的, 则 x 称为频繁 闭合项目集( frequent closed itemset) 或频繁闭合模 式( frequent closed pattern) 。引理 1在数据集 d 中, 包含频繁模式 x 且与x 有相同支持度的频繁闭合模式有且仅有一个2。引理 2设 x, y

10、 都是频繁模式, 假如 x#y 且sup( x) =sup( y) , 则 x 不是频繁闭合模式。 频繁闭合模式挖掘问题可描述为:给定数据集 d 和最小支持度阈值 minsup, 在 d 中找出所有频繁闭合模式 x, 其中, sup ( x) min- sup, 且不存在 任 何 真 超 集 y, yx, 使 得 sup ( y) = sup( x) 。算法设计( 2)基于 pfp- tree 构造方式提出的频繁闭合模式挖掘并行算法 dp- fp, 其算法描述如下:算法 1: dp- fp 算法algorithm dp- fp( d, minsup)输入: 数据集 d 和最小支持度阈值 min

11、sup;输出: 频繁闭合模式集;步骤: 统计频繁项目。首先水平划分数据集平均分配给各 处理器, 各处理器在局部数据集上并行统计所有项目的局部 支持数。然后再将所有项目平均划分给各处理器, 各处理器 按照项目的划分将每个项目的局部支持数传送给相应的处 理器。各处理器统计所分配项目的全局支持数, 删除非频繁 项目, 将余下的频繁项目按支持度非递增排序, 得到一个局 部频繁项目表。最后, 各处理器将局部频繁项目表传递给其 它处理器, 并且归并排序所得到的局部频繁项目表得到有序 的全局频繁项目表。 并行构造 pfp- tree。 并行挖掘局部频繁闭合模式。各处理器在各自 pfp- tree 上使用 f

12、pclose 串行算法并行挖掘以所分配频繁项目为 后缀的局部频繁闭合模式。 并行挖掘全局频繁闭合模式。各处理器都将本地的 局部频繁闭合模式发送给其他处理器, 各处理器都将所收到 的局部频繁闭合模式保存到一棵 cfi- tree 中, 然后依据这棵 cfi- tree 判断本地每个局部频繁闭合模式的全局闭合性。将 非全局闭合的删除, 保留下来的就是全局频繁闭合模式。4.3dl- fp 算法( 1) 局部 fp- tree 的并行构造3串行算法 fpclose文中提出的分布式存储结构下的频繁闭合模 式 挖 掘 并 行 算 法 是 grahne 等 人 提 出 的 串 行 算 法 fpclose1的

13、并行化。fpclose 算法是基于 fp- tree 结 构的频繁闭合模式挖掘算法, 采取的是分而治之的 策略, 即按照 fp- tree 头指针表自下而上的次序, 依 次 挖 掘 以 每 个 频 繁 项 目 为 后 缀 的 频 繁 闭 合 模 式 。 fpclose 除了利用 fp- tree 自身的特点外, 还针对稀 疏数据集使用数组技术减少一次扫描条件 fp- tree 的次数, 并且为了能够快速判断频繁模式的闭合 性, 使用了条件 cfi- tree 来压缩保存已找到的频繁 闭合模式, 从而获得了较高的性能。并行算法相关工作当前已提出的基于分布式存储结构的频繁闭44.1合模式挖掘并行算

14、法较少, tang 等人提出了机群环境下的 pmine 算法3。pmine 算法的最大特点是各处 理器能独立地挖掘频繁闭合模式, 在挖掘过程中,棵 fp- tree。( 2)算法设计5结束语文中研究了分布式存储结构下频繁闭合模式基于以上的 lfp- tree 构造方式, 提出频繁闭合模式挖掘并行算法 dl- fp。dl- fp 算法与 dp- fp 算 法 的 不 同 之 处 在 于 算 法 的 步 骤 ( 并 行 构 造 lfp- tree) 和步骤( 并行挖掘局部频繁闭合模式) 。 dl- fp 算法在并行构造 lfp- tree 基础上, 首先划分 频繁项目均匀分配给各处理器, 然后各处

15、理器按照 频繁项目的划分, 将 lfp- tree 中含有其他处理器所 需的前缀路径信息发送给相应的处理器。各处理器 收 到 其 他 处 理 器 发 来 的 前 缀 路 径 信 息 后 插 入 到lfp- tree 中, 最后使用 fpclose 串行算法并行挖掘 局部频繁闭合模式。限于篇幅, 在这里省略了 dl- fp 算法的描述。挖掘的并行化问题。在已有基于 fp- tree 的串行算法 fpclose 的基础上, 针对频繁闭合模式的特点, 提 出了并行挖掘局部频繁闭合模式和并行挖掘全局 频繁闭合模式的两阶段闭合性判断策略, 并基于这 种策略和分布式存储结构下两种并行构造 fp- tree

16、 的方式, 设计了两个基于 fp- tree 的频繁闭合模式 挖掘并行算法 dp- fp 和 dl- fp, 性能分析表明, 这 两个算法具有较大的并行化、较小的 i/o 开销与良 好的负载平衡, 特别是 dp- fp 算法, 可更好地实现 处理器之间较少的同步和更小的通信开销。性能分析正如前面所言, 模式闭合性的判断具有很强的 串行性。在 dp- fp 和 dl- fp 算法中, 模式闭合性的 判断采取的是两阶段并行化方法: 第一阶段并行判 断频繁模式的局部闭合性( 见算法步骤) , 第二阶参考文献:4.41grahne g, zhu j. efficiently using prefix-

17、 trees in miningfrequent itemsets c. proceedings of the fimi03 work- shop on frequent itemsets mining implementations, 2003:13缪裕青. 频繁闭合项目集的并行挖掘算法研究 j. 计算 机科学, 2004, 31: 166167tang p, ning l, wu n. domain and data partitioning for parallel mining of frequent closed itemsetsc. proceedings of the 43th

18、annual southeast regional conference, ken- nesaw, ga,usa: acm press, 2005: 250252javed a, khokhar a. frequent pattern mining on message passing multiprocessor systemsj. distributed and paralleldatabases, 2004, 16: 3213222段并行判断频繁模式的全局闭合性( 见算法步骤) 。这种方法既解决了模式闭合性的判断问题又提高了并行化程度。另外, 在统计频繁项目、并行挖掘局部频繁闭 合 模 式 和 全 局 频 繁 闭 合 模 式 时 , dp - fp 和 dl- fp 算法所采取的在处理器之间有选择的传递方式, 既 考虑了尽可能减少通信量, 又提高了