项集的集 合。仿真 实验结果表 明 ， 随着节点数 目的增多 ， 改进算法 比原算法执行时间要短 ， 并且这种优势随着
节点数 目的增 加而扩大 ， 说 明在异构集群环境下 ， Ｍａ ｐ Ｒ ｅ ｄ ｕ ｃ ｅ模型 的 Ａ ｐ ｉ ｆ ｏ ｉ算法能够 提高关联规则挖 掘的执 ｆ
行效率 。将改进的分布式关 联规则算 法在 分布式教育决 策支持系统 中应用 ， 通过对实 际数 据的挖掘 ， 证明 了
Ｖ０ １ ． ３ ５ Ｎｏ ．１ Ｆ ｅ ｂ． ２ ０１ ３
文章编号 ： ２ ０ ９ ５—３ ８ ５ ２ （ ２ ０ １ ３ ） ０ １ — ０ ０ ４ ０一 ｏ ４
文 献标 志 码 ： Ａ
基 于 分布 式 数 据 挖 掘 方 法 的研 究 与 应 用
汪 丽 ，张 露
（ １ ．武汉理工大学 统战部 ， 湖北 武汉 ４ ３ ０ ０ ７ ０ ； ２ ． 武汉理工大学 计算机科学与技术学 院， 湖北 武汉 ４ ３ ０ ０ ７ ０ ）
联规则挖掘算法 ， 但Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法仍是许多新算法
收稿 １ ５ ｔ 期： ２ ０ １ ２— ０ ９—１ ０ ．
作者简 介： 汪
丽（ １ ９ ７ ７ 一） ， 女， 湖北武汉人 ， 武汉理工大学统战部 助理研究员
基金项 目： 湖北省教育厅教学研究基金资助项 目（ ２ ０ ０ ９ ２ ４ ０ ） ．
将运行 于大规模集群上复杂的并行计算过程高度 地抽象成两个函数 ： Ｍ ａ ｐ和 Ｒ ｅ ｄ ｕ ｃ ｅ Ｊ 。在实现上 将并行化 、 容错 、 数据分布和负载均衡等细节隐藏 起来 ， 然后把整个分布式过程看作 由 Ｍ ａ ｐ ／ Ｒ ｅ ｄ ｕ ｃ ｅ 来表达 的一个类 函数过程。Ｍ ａ ｐ阶段 ， Ｍ ａ ｐ ／ Ｒ ｅ ．
１ 关联规则挖掘算法及其分布式改进
１ ． １ 关联规 则挖 掘算 法
从广义上讲 ， 数据挖掘 的本质 即关 联分析。
数据挖 掘 的 目的是挖 掘 出潜 藏在 大量 数据 背后 的 有用 知识 ， 这种 知识 所 反 映 的 必 然是 不 同对 象不 同属 性之 间 的关 联 。
掘也不再适用 Ｊ 。针对 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法进行改进 ， 提
出了一 种 分 布式 的关 联 数据 挖 掘 算 法 ， 利 用 Ｍａ ．
没有复杂的推导 。但同时该算法也存在两个主要 缺点 ： ① 多次重 复 扫描 数 据 库 和产 生 大 量 候选 频 繁项集。在实际应用 中， 多次重复扫描数据库在 需要挖掘很长的模式时将带来 巨大开销 ； ②在迭 代过程中要在 内存 中产生 、 处理和保存候选频繁
该方法对教育决策 的有效性 。
关键词 ： 分布式数 据挖 掘 ； Ｍａ ｐ Ｒ ｅ ｄ ｕ ｃ ｅ 模型； 关联规则 ； 分布式教育决策支持系统
中 图分 类 号 ： Ｔ Ｐ ３ １ １ ． １ ３ Ｄ Ｏ Ｉ ： １ ０ ． ３ ９ ６ ３ ／ ｊ ． ｉ ｓ ｓ ｎ ． ２ ０ ９ ５— ３ ８ ５ ２ ． ２ ０ １ ３ ． ０ １ ． ０ １ １
摘Hale Waihona Puke 要： 针对关联 规则 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算 法多次重复 扫描数 据库 和产生 大量候选 频繁 项集 的缺点 ， 对 其进行 改
进， 并在 Ｍａ ｐ Ｒ ｅ ｄ ｕ ｃ ｅ 模 型上得以实现。改进 的 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法 只需要对 整个数据库扫描一次 ， 即可得到所有频 繁
Ｍａ ｐ Ｒ ｅ ｄ ｕ ｃ ｅ模 型 是 Ｇ ｏ ｏ ｇ ｌ ｅ开 发 的一 个 针 对 大规模 群组 海量 数 据 处 理 的分 布 式 编程 模 型 ， 它
在众多的关联规则算法中， 最著名的是 １ ９ ９ ３ 年Ａ Ｇ Ｒ Ａ ＷＡ Ｌ等提出 的 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法及其改进算 法 。 ｊ 。尽管后来又有科研工作者提出了许多关
项集 ， 这 个数量 有 时候是 非常 大 的 ， 会导致 算法 在
广 度和 深度 上 的适 应性 很差 。 １ ． ２ 分布式 Ａｐ ｒ ｉ ｏ ｒ ｉ 算法 设计
ｐ Ｒ ｅ ｄ ｕ ｃ ｅ 模型对算法 进行实现， 并将改进 的关 联
规则 算法 应用 于分 布式 教育决 策支 持系统 中。
步骤 为 ： ① 根据 原事 务集 产生频 繁 １项 集 Ｌ ； ②根据频繁 ｋ 项集产生第 ｋ ＋１ 层候选集； ③
扫描事务集 ， 找出第 ｋ ＋ｌ 层频繁集； ④循环步骤
②和步骤③ ， 直到第 ｋ ＋ １ 层频繁集为空。
Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算 法 的优 点 是 结 构 简 单 ， 易 于理解 ，
随着网络和计算机技术 的快速发展 ， 信息也
在爆 炸 式地 增 长 并呈 现 出 海量 、 多样 、 异构、 动态
的原 型 ， 很 多算法 都是 基于 Ａ ｐ ｒ ｉ ｏ ｒ ｉ 算法 的改进 。 可将 Ａ ｐ ｉ ｆ ｏ ｒ ｉ 算法 描述 如下 ： 输人 为事务 数据 库 Ｄ； 最 小支持 度 阈值 Ｊ ｓ 输 出为 Ｄ 中 的频 繁项 集 Ｌ 。
第３ ５ 卷 第１ 期
２ ０ １ ３ 年２ 月
武 汉理工大学学报 （ 信息与管理工 程版 ）
Ｊ Ｏ Ｕ Ｒ Ｎ Ａ Ｌ Ｏ Ｆ ＷＵ Ｔ （ Ｉ Ｎ Ｆ Ｏ Ｒ Ｍ Ａ Ｔ Ｉ Ｏ Ｎ＆Ｍ Ａ Ｎ Ａ Ｇ Ｅ Ｍ Ｅ Ｎ Ｔ Ｅ Ｎ Ｇ Ｉ Ｎ Ｅ Ｅ Ｒ Ｉ Ｎ Ｇ ）
变化 等特 性 Ｊ 。分 布 式 计 算 平 台 的 出现 解 决 了
海量数据 的存储和计算 的瓶颈问题 ， 使海量数据 的数据挖掘成为可能。将分布式与现有数据挖掘 算法相结合 ， 已成为研究 的热点 Ｊ 。 而随着信息化建设 的深入发展 ， 高校都拥有
大量 的教育 信息 ， 其 分 布 范 围在地 理 上 越来 越 广 泛， 数 据结 构呈 现多样 化 的趋势 ， 使传 统 的数 据挖