分布式并行关联规则挖掘算法研究

收稿日期： ２ ０ １ ２－ ０ ６－ ２ ８ 。江苏省现代教育技术研究项目（ ２ ０ １ １－ Ｒ － １ ９ ４ ７ ０ ） ； 江苏省高校自然科学基金项目（ １ １ Ｋ Ｊ Ｄ ５ ２ ０ ０ ０ ６ ） 。 王智钢， 副 教授， 主研领域： 数据挖掘， 网络信息系统， 软件工程。 王池社， 副教授。 马青霞， 硕士。
Ａ ｂ ｓ ｔ ｒ ａ ｃ ｔ Ｉ ｎａ ｓ ｓ ｏ ｃ ｉ ａ ｔ ｉ ｏ ｎｒ ｕ ｌ ｅｍ ｉ ｎ ｉ ｎ ｇ ，ｔ ｈ ｏ ｕ ｇ ｈｔ ｈ ｅＦ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｉ ｓａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｅ ｌ ｙｏ ｎ ｅｏ ｒ ｄ ｅ ｒ ｏ ｆ ｍ ａ ｇ ｎ ｉ ｔ ｕ ｄ ｅｆ ａ ｓ ｔ ｅ ｒ ｔ ｈ ａ ｎｔ ｈ ｅＡ ｐ ｒ ｉ ｏ ｒ ｉ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ，ｂ ｕ ｔ ｉ ｔ ｈ ａ ｓ ｔ ｗ ｏｄ ｉ ｓ ａ ｄ ｖ ａ ｎ ｔ ａ ｇ ｅ ｓ ：ｔ ｈ ｅ ｆ ｉ ｒ ｓ ｔ ｉ ｓ ｔ ｈ ａ ｔ ｉ ｔ ｓ ｆ ｒ ｅ ｑ ｕ ｅ ｎ ｔ ｐ ａ ｔ ｔ ｅ ｒ ｎｔ ｒ ｅ ｅ ｍ ａ ｙ ｂ ｅ ｔ ｏ ｏ ｂ ｉ ｇ ｔ ｏ ｂ ｅ ｃ ｒ ｅ ａ ｔ ｅ ｄｉ ｎｔ ｈ ｅ ｍ ｅ ｍ ｏ ｒ ｙ ；ｔ ｈ ｅ ｓ ｅ ｃ ｏ ｎ ｄｉ ｓ ｉ ｔ ｓ ｓ ｅ ｒ ｉ ａ ｌ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇａ ｐ ｐ ｒ ｏ ａ ｃ ｈ ．Ｉ ｎｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ ｗ ｅｐ ｒ ｏ ｐ ｏ ｓ ｅａｋ ｉ ｎ ｄｏ ｆ ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｓ ｓ ｏ ｃ ｉ ａ ｔ ｉ ｏ ｎｒ ｕ ｌ ｅｍ ｉ ｎ ｉ ｎ ｇａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ．Ｉ ｔ ｉ ｓ ｆ ｏ ｒ ｔ ｈ ｅｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ ａ ｐ ｐ ｌ ｉ ｅ ｄｄ ａ ｔ ａｆ ｒ ａ ｍ ｅ ｗ ｏ ｒ ｋ ，ｄ ｏ ｅ ｓ ｎ ｏ ｔ ｎ ｅ ｅ ｄｔ ｏ ｃ ｒ ｅ ａ ｔ ｅ ｔ ｈ ｅ ｇ ｌ ｏ ｂ ａ ｌ Ｆ Ｐ ｔ ｒ ｅ ｅ ｓ ｏ ａ ｖ ｏ ｉ ｄ ｓ ｔ ｈ ｅ ｐ ｒ ｏ ｂ ｌ ｅ ｍｏ ｆ ｔ ｏ ｏ ｂ ｉ ｇ ｔ ｈ ｅ ｇ ｌ ｏ ｂ ａ ｌ Ｆ Ｐｔ ｒ ｅ ｅ ｔ ｈ ａ ｔ ｆ ｉ ｌ ｌ ｓ ｔ ｈ ｅ ｍ ｅ ｍ ｏ ｒ ｙ ｔ ｏ ｅ ｘ ｃ ｅ ｓ ｓ ．Ｉ ｎａ ｌ ｌ ｉ ｔ ｓ ｐ ｒ ｉ ｎ ｃ ｉ ｐ ａ ｌ ｓ ｔ ｅ ｐ ｓ ｔ ｈ ｅ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍａ ｃ ｈ ｉ ｅ ｖ ｅ ｓ ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ．Ｔ ｅ ｓ ｔ ｒ ｅ ｓ ｕ ｌ ｔ ａ ｎ ｄａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ｏ ｆ ｔ ｈ ｅ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ｈ ｏ ｗｔ ｈ ａ ｔ ｃ ｏ ｍ ｐ ａ ｒ ｅ ｄｗ ｉ ｔ ｈ ｃ ｏ ｎ ｖ ｅ ｎ ｔ ｉ ｏ ｎ ａ ｌ ａ ｓ ｓ ｏ ｃ ｉ ａ ｔ ｉ ｏ ｎｒ ｕ ｌ ｅ ｍ ｉ ｎ ｉ ｎ ｇ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍＦ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ ， ｔ ｈ ｉ ｓ ｏ ｎ ｅ ｓ ｉ ｇ ｎ ｉ ｆ ｉ ｃ ａ ｎ ｔ ｌ ｙ ｉ ｍ ｐ ｒ ｏ ｖ ｅ ｓ ｔ ｈ ｅ ｅ ｘ ｅ ｃ ｕ ｔ ｉ ｎ ｇ ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｃ ｙ ａ ｎ ｄｔ ｈ ｅ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ａ ｂ ｉ ｌ ｉ ｔ ｙ ｂ ｙ ｍ ｕ ｌ ｔ ｉ ｎ ｏ ｄ ｅｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ． Ｋ ｅ ｙ ｗ ｏ ｒ ｄ ｓ Ｄ ａ ｔ ａｍ ｉ ｎ ｉ ｎ ｇ Ａ ｓ ｓ ｏ ｃ ｉ ａ ｔ ｉ ｏ ｎｒ ｕ ｌ ｅ Ｆ ｒ ｅ ｑ ｕ ｅ ｎ ｔ ｐ ａ ｔ ｔ ｅ ｒ ｎ Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ 架构的关联规则挖掘问题， 为避免大量数据的传输和转储， 也对
， ２ ， ２ 王智钢１ 王池社１ 马青霞１
１ ２
（ 金陵科技学院信息技术学院 江苏 南京 ２ １ １ １ ６ ９ ） （ 江苏省信息分析工程实验室 江苏 南京 ２ １ １ １ ６ ９ ）
摘 要 关联规则挖掘算法 Ｆ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ 虽然效率比 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 要快一个数量级， 但存在频繁模式树可能过大而内存无法容纳和数据 挖掘过程串行处理等两大缺点。提出一种分布式并行关联规则挖掘算法， 该算法针对分布式应用数据架构， 不需要产生全局 Ｆ Ｐ ｔ ｒ ｅ ｅ ， 避免全局 Ｆ Ｐ ｔ ｒ ｅ ｅ 可能过大而内存无法容纳的问题， 算法在各个主要步骤上都实现了并行处理。算法测试结果和分析表明， 与 传统的关联规则挖掘算法 Ｆ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ 相比， 该算法通过多节点分布式并行处理显著提高了执行效率和处理能力。 关键词 数据挖掘 关联规则 频繁模式 并行算法 中图分类号 Ｔ Ｐ ３ １ １ 文献标识码 Ａ Ｄ Ｏ Ｉ ： １ ０ ． ３ ９ ６ ９ ／ ｊ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ０ ３ ８ ６ ｘ ． ２ ０ １ ３ ． １ ０ ． ０ ３ １
２ ］ 法［ ， 在Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法基础上还派生出了很多改进算法， 但Ａ ｐ ｒ ｉ ｏ ３ ）算法必须耗费大量时间处理规模
分布式的数据挖掘提出了现实需求。 为实现分布式或并行关联规则挖掘， 文献［ ５ ］ 提出了数据 划分， 文献［ ６ ， ７ ］ 采用多线程内存共享， 文献［ ８ ］ 在得到全局 Ｆ Ｐ ｔ ｒ ｅ ｅ 之后将其分解为子树进行并行处理， 文献［ ９ ］ 谈到由于 Ｆ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ 算法挖掘每个条件模式库的过程是彼此独立的， 故可将 每个条件模式库的挖掘看成一个子任务， 总的频繁模式挖掘任 务可被划分为数目与频繁项目数相等的若干个子任务， 然后将 这些子任务分配给计算机集群中的各个节点分别执行。 本文提出一种分布式并行关联规则挖掘算法， 为便于表述， 称之为 Ｐ Ｆ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ算法， 该算法针对分布式的应用数据架构， 不需要产生全局 Ｆ Ｐ ｔ ｒ ｅ ｅ ， 在算法的各个主要步骤上都实现了分 布式并行处理。
表 １中第三行表示 Ｉ ４ ５次， 将被分配到计算 ７ 共出现了 ３７ 节点 Ｃ ２ 进行频繁模式挖掘。 为 Ｌ中的项目分配计算节点的策略可以有很多种， 既可事 先静态分配， 适合于远程分布式计算， 也可在通信非常便利的情 况下， 采用动态分配。 静态分配策略可以是按照项目计数顺序依次分配。例如： 设项目按照计数降序排列后依次称为第 １ ， ２ ， …， ｎ 个， 计算节点 共有 ｐ 个， 依次名为 Ｃ ， …， Ｃ ｐ ， 则满足 ｎｍ ｏ ｄｐ ＝ ｉ 的第 ｎ 个项目 １ 分配给 Ｃ １ 。 ｉ＋ 动态分配策略可以是： 先从 Ｌ 的末端开始， 为每个计算节点 分配一个项目的频繁模式挖掘任务， 然后在某计算节点完成任 务之后再从 Ｌ 中由后往前分配一个项目挖掘任务。 算法描述中第（ ４ ） 步， 是在全局 １－项频集 Ｌ约束下， 为各 个局部数据库建立局部 Ｆ Ｐ ｔ ｒ ｅ ｅ ， 建立的方法同传统 Ｆ Ｐ Ｇ ｒ ｏ ｗ ｔ ｈ 算法， 主要就是对数据库中的事务进行三步操作： ① 过滤掉 Ｌ 中没有的项目； ② 将剩下的项目按照 Ｌ中的计数降序排列； ③ 将该事务加入本节点的 Ｆ Ｐ ｔ ｒ ｅ ｅ 。本步骤处理结束后， 可得到多 个在全局 １－ 项频集 Ｌ 约束下的局部 Ｆ Ｐ ｔ ｒ ｅ ｅ 和Ｈ ｅ ａ ｄ ｅ ｒ Ｔ ａ ｂ ｌ ｅ 。 算法描述中第（ ６ ） 步， 各计算节点按项目汇总各个项目的 条件模式库并进行频繁模式挖掘时， 如果某个项目的条件模式 库异常大， 远远大于其他项目， 可递归调用本算法， 对该项目的 频繁模式挖掘任务进一步进行分解， 然后再进行并行处理。
０ 引 言
关联规则是由 Ａ ｇ ｒ ａ ｗ ａ ｌ 等于 １ ９ ９ ３年在文献［ １ ］ 中首先提出 的一个重要的数据挖掘研究课题， Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法是 Ｒ ． Ａ ｇ ｒ ａ ｗ ａ ｌ 和 Ｒ ． Ｓ ｒ ｉ ｋ ａ ｎ ｔ 于１ ９ ９ ４年 提 出 的 布 尔 型 关 联 规 则 原 创 性 挖 掘 算
Ｒ Ｅ Ｓ Ｅ Ａ Ｒ Ｃ ＨＯ ＮＤ Ｉ Ｓ Ｔ Ｒ Ｉ Ｂ Ｕ Ｔ Ｅ ＤＰ Ａ Ｒ Ａ Ｌ Ｌ Ｅ ＬＡ Ｓ Ｓ Ｏ Ｃ Ｉ Ａ Ｔ Ｉ Ｏ ＮＲ Ｕ Ｌ ＥＭＩ Ｎ Ｉ Ｎ Ｇ
１ ， ２ １ ， ２ １ Ｗａ ｎ ｇＺ ｈ ｉ ｇ ａ ｎ ｇ Ｗａ ｎ ｇＣ ｈ ｉ ｓ ｈ ｅ Ｍ ａＱ ｉ ｎ ｇ ｘ ｉ ａ
１ ２
（ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｉ Ｔ ，Ｊ ｉ ｎ ｌ ｉ ｎ ｇＩ ｎ ｓ ｔ ｉ ｔ ｕ ｔ ｅ ｏ ｆ Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ ，Ｎ ａ ｎ ｊ ｉ ｎ ｇ ２ １ １ １ ６ ９ ，Ｊ ｉ ａ ｎ ｇ ｓ ｕ ，Ｃ ｈ ｉ ｎ ａ ）
（ Ｉ ｎ ｆ ｏ ｒ ｍ ａ ｔ ｉ ｏ ｎＡ ｎ ａ ｌ ｙ ｓ ｉ ｓ Ｅ ｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇＬ ａ ｂ ｏ ｒ ａ ｔ ｏ ｒ ｙｏ ｆ Ｊ ｉ ａ ｎ ｇ ｓ ｕＰ ｒ ｏ ｖ ｉ ｎ ｃ ｅ ，Ｎ ａ ｎ ｊ ｉ ｎ ｇ ２ １ １ １ ６ ９ ，Ｊ ｉ ａ ｎ ｇ ｓ ｕ ，Ｃ ｈ ｉ ｎ ａ ）
第３ ０卷第 １ ０期 ２ ０ １ ３年 １ ０月
计算机应用与软件 Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ Ａ ｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ ａ ｎ ｄＳ ｏ ｆ ｔ ｗ ａ ｒ ｅ
Ｖ ｏ ｌ ３ ０Ｎ ｏ ． １ ０ １ ３ Ｏ ｃ ｔ ． ２ ０
分布式并行关联规则挖掘算法研究
巨大的候选项目集； （ ２ ）算法必须多次重复扫描数据库， 对候选 项目集进行模式匹配。针对 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 类算法的不足， Ｈ ａ ｎ等人提