挖掘关联规则的并行算法

精品文档 1欢迎下载 挖掘关联规则的并行算法 SC02011028 苏媛媛 摘要 挖掘关联规则是数据挖掘领域的一个重要问题 文中对挖掘关联规则问题进行了 简单的回顾 对已提出的挖掘关联规则的并行算法进行了较全面的总结 对他们的性能进 行了分析 并提出了三种新的挖掘关联规则的并行算法 对他们的性能作了简要分析 给 出了优化策略 第一种 设计了一个效率较高的并行挖掘关联规则的算法 PMAR 并与其它 相应算法进行了比较 实验证明 算法 PMAR 是有效的 第二种 提出一种新的并行算法 NA 不管大项集的最大长度是多少 他只需 2 次同步就能得到结果 当大项集的最大长度 比较大时 NA 会显示出更好的性能 第三种 介绍了一种改进的基于 Apriori 算法的挖 掘关联规则的并行算法 并和以前提出的 DD 算法进行了比较 这种改进的算法 IDD 克服了 以前提出的 DD 算法的缺点 消除了 DD 算法中的工作冗余 关键字 并行算法 关联规则 大项集 集群 格 1 引言 数据挖掘 Data Mining 就是从大量的日常业务数据中发掘出有用的信息 关联规则 的挖掘 ARM 是数据挖掘的一项重要的任务 其目的就是从事务数据库 关系数据库中发 现项目集或属性之间的相关性 关联关系 因果关系 关联规则可描述如下 D 是一个事 务数据库 其中每一个事务 T 由一些项目 Item 构成 并且都有一个唯一的标识 TID 项目的集合简称项目集 item set 含有 k 个项目的项目集称为 k 项目集 项目集 X 的支持度 support 是指在事务数据库 D 中包含项目集 X 的事务占整个事务的比例 记为 sup X 可信度 confidence 是指在事务数据库 D 中 同时含项目集 X 和 Y 的事务与含 项目集 X 的事务的比 即 sup X Y sup X 项目集中长度为 k 的子集称为 k 子项目 集 如果一个项目集不是任何其它项目集的子集则称此项目集为极大项目集 如果项目 集的支持度大于用户指定的最小支持度 min sup 则称此项目集为频繁项目集 frequent item set 或大项集 large itemset 关联规则可形式化表示为 X Y 它的含义是 X Y 的支持度 sup X Y 大于用户指定的最小支持度 min sup 且可信度 conf 大于用户指 定的最小可信度 min conf 关联规则挖掘就是在事务数据库 D 中找出满足用户指定的最 小支持度 min sup 和最小可信度 min conf 的所有关联规则 挖掘任务可分为两个子问 题 1 找出事务数据库中所有的大项集 精品文档 2欢迎下载 2 从大项集中产生所有大于最小可信度的关联规则 相对来说 第二个子问题比较容易 目 前大多数研究主要集中于第一个子问题 关联规则描述虽然简单 但它的计算量是很大的 假设数据库含 m 个项目 就有 2m 个子集可能是频繁子集 可以证明要找出某一大项集是一个 NP 问题 当 m 较大时 要穷 尽搜索每一个子集几乎是不可能的 另一方面 处理数据库中存储的大量记录要求繁重的 磁盘 I O 操作 因此 随着数据库规模的不断增大 数据属性向高维发展 传统的顺序 挖掘算法很难适应大规模 可扩展 scalability 的挖掘需要 发展高性能的并行算法是 解决这一问题的关键 2 相关工作 2 1 Apriori 算法及其并行化 Apriori 算法是由 Agrawal 等人 1 提出的 算法思想主要依据支持度有 向下封闭 的特性 即 如果一个项目集是大项集 那么它的子集也是大项集 所以 k 大项集的 候选项目集可通过合并 k 1 大项集构成 算法首先对数据库进行搜索 找出所有的频繁项目 即 1 大项集 接着从 1 大项 集中产生 2 大项集的候选集 然后进行第二次数据库搜索得出候选项目集的支持度 保 留那些支持度大于 min sup 的项目集 搜索结束时 得出 2 大项集 这个过程重复进 行 每一次迭代 保留大项集用于生成下一次 迭代的候选集 直到找出所有的大项集 基于 Apriori Agrawal 和 Shafer 在 2 中 提出了三种并行算法 Count Distribution 算法 Data Distribution 算法和 Candidate Distribute 算法 这些算法的前提是处理器有专用内存和磁盘 而结构上没有任何共享 处理器用通信网络连接 靠消息传递进行通信 数据平均分配到每个处理器的专用磁盘 精品文档 3欢迎下载 上 这些算法需要用到的符号意义如表 1 Count Distribution 算法 Count Distribution 是 Apriori 的一个简单并行化算法 算法是通过分割数据库来 完成并行化的 如果有 N 个处理器节点 则各节点获得数据库的 1 N 然后分别在各数据 库子集上完成类似于 Apriori 的算法 k 1 1 Pi 根据本地数据集 Di 产生本地 Ci1 2 Pi 将各自的 Ci1 与其它处理器交换 3 各处理器合并所有的 Ci1 得出完整的 C1 k 1 1 Pi 根据完整的大项集 Lk 1 产生完整 Ck 2 Pi 对 Di 进行搜索 计算 Ck 中候选项目集在本地的支持数 3 各 Pi 与其它所有处理器交换本地对 Cik 中候选项目集集支持数之后 算 出 Ck 中完整的候选项目集支持数 在这一步 处理器被强制同步 4 Pi 用 Ck 来计算 Lk 5 各 Pi 独立的决定是否终止或继续进行下一次搜索 由于所有的 Pi 都有 同样的 Lk 所以每个 Pi 的决定是一致 Data Distribution 算法 Data Distribution 是在各节点之间分割大项集的候选集 各节点分别计算各自所得 候选项目集的支持度 k 1 与 Count Distribution 算法相同 k 1 1 Pi 从 Lk 1 中产生 Ck 根据 Pi 个数把项目集分割成 N 份 Pi 仅保留 1 份 来构成 Cik 处理器可根据其 ID 号来决定保留哪一部分而不需要与其它处 理器通信 其中 Ni 1Cik Ni 1Cik Ck 2 利用本地数据和其它处理器传来的数据 Pi 计算在 Cik 中项目集的支持数 3 在一次数据搜索结束时 各 Pi 用本地的 Cik 来计算 Lik Ni 1Lik Ni 1Lik Lk 4 处理器之间相互通信获取其它 Lik 之后每个 Pi 得到完整的 Lk 用以下一 趟产生 Ck 1 这一步要求处理器同步 获得完整的 Lk 后 每个 Pi 能 独立的决定是否终止或继续下一次搜索 精品文档 4欢迎下载 Candidate Distribute 算法 Candidate Distribute 算法综合了 Data Distribution 和 Count Distribution 算法 以 弥补它们各自的不足 在前 l 步采用 Data Distribution 算法或 Count Distribution 算法 到第 l 步 其中 l 由启发而定 为了减少各处理器之间的数据依赖 算法对大项 集 Ll 1 进行分配 同时 也对数据进行重新分配 使 Pi 能独立于其它处理器生成 Cim m l Cim Cjm i j 为了减少处理器对候选集的依赖 Candidate Distribute 算法不等待从其它处理器传来完整的剪枝信息 它尽可能快的剪枝 而滞后到达的剪枝信 息在下一次剪枝时使用 kl 时 1 Pi 收集所有从其它处理器发送来的频繁项目集 用于对候选集剪枝 2 Pi 用本地的 Lik 生成 Cik 如果 Pi 没有收到其它处理器传来的 Ljk 1 则 Pi 剪枝时要作相应的处理 3 Pi 搜索 DRi 对 Cik 中的项目计数 然后根据 Cik 计算出 Lik 并把 它传到其它处理器 从以上三个算法可以看出 Count Distribution 算法目标是减少通信量获得较好的任 务分布性 使各处理器只对本地数据并行地进行处理 但算法的 I O 量较重 数据结构 重复 没有有效利用整个内存 Data Distribution 算法目标是尽量减小计算冗余 充分 利用各节点之间的带宽 它在节点间分割当前最大频繁项目集的候选集 然而要获得全局 支持度 各处理器必须搜索整个数据库 通信量较大 上述两种算法每次搜索结束时 都 要求所有处理器必须同步 与 Data Distribution 算法相似 Candidate Distributuon 算法也是在各节点间分配候选集 但它有选择地对数据库进行分割 使每个节点可以根据 本地的数据来处理它的候选集 减少处理器之间对数据和各候选集的依赖 从而减少同步 减 少通信量 2 2 DHP 算法及其并行化 在生成大项集的过程中 候选项目集集合越大 生成大项集的开销越多 特别是最初 精品文档 5欢迎下载 几次迭代要占整个过程的大部分开销 针对于这一问题 Park 等人提出了 DHP Direct Hash ing and Pruning 算法 与 Apriori 算法相同 DHP 也是从 k 1 大项集 Lk 1 中 产生 k 大项集的候选集 Ck 但是 DHP 算法利用哈希技术来检查 k 项目集是否满足要 求 DIH 算法只对哈希表中项目数大于 min sup 的单元进行处理 将这些单元中的 k 项目集加入 Ck 这对减少候选 2 大项集的数目尤为有效 另一方面 算法通过缩减事务 本身的大小和对数据库中事务剪枝 来缩减数据库规模 DHP 算法能有效地生成大项集 显著地减少事务数据库规模 但 DHP 对数据库进行的 是物理剪枝 而不是逻辑剪枝 每次迭代对数据库的剪枝将涉及对数据库的重写 增加了 I O 负担 基于 DHP 的思想 Park 等人提出了 PDM 算法 大体上说 PDM 算法是由并行生成候 选项目集和并行确定大项集两部分构成 PDM 算法描述如下 首先 每个节点分别计算分 数据库中 1 项目集的支持度 并利用哈希表计算 2 项目集的支持数 各节点通过广播 all to all broadcast 交换本地的 1 大项集 计算产生全局 1 大项集 而对于 2 项目集 其哈希表一般很大 直接通过广播交换 通信量很大 PDM 利用优化的方法 仅 交换哈希表中那些大于 min sup 的单元 各节点利用了全局 2 项目集的哈希表 生成 本地的候选 2 项目集 然后 生成候选 k 项目集 k 2 时 就直接利用前一次生成的 大项集了 候选集都是并行生成的 各节点产生自己本地的候选集 通过广播 进行交 换 以此生成大项集 PDM 算法有一些局限性 首先 为构成完整的候选项目集各节点都要进行广播通信 通信的开销可能会抵消掉并行生成候选项目集的优势 其次 和 DHP 一样 PDM 对非大项 集的项目和事务的物理剪枝要涉及大量磁盘 I O 操作 2 3 DIC 算法及其并行化 DIC Dynamic Itemset Counting 算法是由 Brin 等人提出的 算法的主要思想是在同 一次数据库搜索中 对 k 值不同的候选 k 项目集计数 DIC 将数据库分成 N 个大小相 等的几段 Di 进行搜索 首先搜索 D1 计算 1 项目集的支持度 所得本地 1 大项集用 来产生 2 项目集的候选集 然后搜索 D2 获取 1 项目集和候选 2 项目集 即当前所 有的候选项目集 计算它们的支持度 所得 2 大项集用于产生 3 大项集的候选集 重 复这一过程 直到 Dn 完成 在对数据库的第一次搜索中 当搜索到 Dk 时 DIC 就开始 计算候选 k 项目集的支持数 所有分块都处理完之后 开始第二次搜索 当算法回到 数据库第 k 段 Dk 进行搜索时 就能得出 k 项目集的全局支持度 每一次搜索完成后 精品文档 6欢迎下载 开始新的一次 直到当前 Dk 没有新的候选集产生 且所有的候选集都已经计算完成 DIC 终止 如果大部分的 Dk 是匀质的 homogeneous 即大项目集在 Dk 中有相似的分布 DIC 算法减少对数据库搜索非常有效 而如果数据是非匀质的 DIC 可能会在某些 Dk 中得出 一些局部而非全局的大项集 反而增加了搜索次数 基于 DIC 思想 Cheung 等人提出了 APM Asyn chronous Parallel Mining 算法 算法的前提是多处理器共享内存 APM 采用了一种全局剪枝技术 Global Pruning 来约 减候选 2 项目集的规模 当在各分数据库中数据分布不均时 这种剪枝很有效 而要 在各节点上利用 DIC 算法 则要求数据库各个分块数据均匀分布 为了解决这一矛盾 ARM 进行一次预处理 APM 从逻辑上把数据库分割成大小相等的一些分块 假设分成 n 块 n 与处理器个数 无关 但通常 n 大于处理器个数 APM 计算 m 个项目在各分块的支持度 构成一个 n m 的数据表 表示在 m 维空间的 n 个项目支持度的矢量 将这 n 个矢量聚成 k 个不同的类 使 类与类之间的差别尽量大 而类中各项目之间差别尽量小 这 k 个聚类构成了 k 个子数 据库 这使得它们之间的数据分布尽可能的不均匀 用它们可产生较小的候选 2 项目 集的集合 经过以上预处理 数据库按处理器个数化分为匀质的子数据库 APM 开始并行实施 DIC 算法 即每一个处理器独立地对本地的子数据库使用 DIC 算法 由于所有处理器共享 一个 trie 树来存储候选项目集的支持度 而 trie 树是异步构造的 所以只有当处理完 所有的侯选项目集 没有新的候选集产生 APM 才结束 虽然 数据分布不均匀有利于 APM 算法的全局剪枝 但它却加重了负载不平衡 2 4 Eclat Max Eclat Clique Max Clique 算法及其并行化 Zaki 等人在 8 中提出了 Eclat Max Eclat Clique Max Clique 四种算法 这 些算法主要采用了三种技术 算法首先用等价类或最大完全子图集 maximal hypergraph clique 方法对项目集聚类 然后用从底至上遍历或混合遍历 从顶至底与从底至上结合 的 方法从每个聚集中生成大项集 算法还利用了纵向数据库格式 vertical database layout 对事务聚类 这四种算法的基本思想相同 只是所使用的搜索策略和划分等价类 技术不同而已 这些算法对项目聚类 产生一些项目集 这些项目集可能是极大项目集 每一个聚集 包含一个子格 sublattice 对其用从底至上的搜索遍历找到所有的大项集 或用混合遍 精品文档 7欢迎下载 历法仅找出极大项集 由于用数据库的纵向格式来对事务聚类 所以仅对数据库搜索一遍 因 此大大减少了 I O 操作量 算法使用简单的事务 TID 表交集来求大项集 不需要构造和 检索复杂的数据结构 此外 由于在任何时候一个聚类中仅 k 大项集保留在内存中 所 以算法对内存要求较低 基于以上四种算法 Z aki 等人提出了 Par Eclat Par Max Eclat Par Clique Par Max Clique 四种并行算法 算法前提条件是系统有 n 个主机 每个主机有 p 个处理器 这些算法采用纵向数据库格式 在各主机间以一定的方式分配数据库 使 得每个主机能获得的所有事务的 TID 表长度总和大致相当 且每个 TID 表都是一事务完整 的 TID 表 各主机进一步根据本地的 ID 表将数据库分成 p 个纵向分数据库 这样 系 统中的每一个处理器都仅处理自己的纵向分数据库 同顺序算法一样 这四种算法只是所 使用的搜索策略和划分等价类技术不同 算法分三个阶段 在初始化阶段 主要完成数据分割 分三个子步骤 首先 读入 预处理阶段得到的 2 项目集的支持数 把大项集加入 L2 其次 应用等价类或最大完 全子图集的方法聚类 产生可能是极大频繁项目集的项目集 然后 所有处理器之间将这 些项目集在按一定策略进行分配 使各处理器尽量负载平衡 对数据库进行重新分配 使 得所有和聚类相连系的 1 项目集的 TID 表 都能在聚类所在处理器的本地磁盘获得 随后进入异步处理阶段 在这个阶段 由于每个处理器都能在本地获得分配给它的等 价类和所有项目的 TID 表 所以能独立地产生大项集 不要求通信和同步 最后的约简 阶段 主要将最终的结果进行整理 3 3 挖掘关联规则的几种新并行算法 3 1 采掘关联规则的并行算法 PMRA 在介绍算法 PMRA 之前先引入与之有密切关系的几个定义与定理 定义 1 项集 X 在数据库 DBi i 1 2 n 中的支持数 support count 即 在 DBi 中包含 X 的事务的条数 称为 X 的局部支持数 用 X supi 表示 定义 2 项集 X 在数据库 DB 中的支持数称为 X 的全局支持数 用 X sup 表示 定义 3 对于项集 X 若 X supi min sup DBi i 1 2 n 则称 X 是相 对于 Pi 的局部大项集 若 X 中的元素为 k 个 则称 X 为局部大 k 项集 定义 4 对于项集 X 若 X sup min sup D 则称 X 是全局大项集 简称大项集 若 X 中的元素为 k 个 则称 X 为大 k 项集 精品文档 8欢迎下载 定义 5 若项集 X 在 Pi i 1 2 n 是局部大项集 且它还是大项集 即 X supi min sup Di 且 X sup min sup D 则称 X 在 Pi i 1 2 n 是稠 密的 用 H L 表示 如 H Lik 表示 Pi i 1 2 n 的 k 稠密集 其中元素为 k 个 的 全体 定理 1 若项集 X 是大 k 项集 X Lk 则必存在一个计算机 Pi i 1 2 n 使 任意 Y X 的项集 Y 在 Pi 是稠密的 定理 2 对任意 k 1 大 k 项集 Lk 是所有计算机产生的局部候选大 k 项集 CHik 的 并集的子集 即 Lk CHk ni 1CHik ni 1Apriori gen H Lik 1 k 函数 Apriori gen 见文献 5 定理 1 与定理 2 的证明见文献 18 定理 3 设 CAk Apriori gen Lk 1 k CHk ni 1Apriori gen H Lik 1 k 则 CHk CAk 证明 设函数 Apriori gen 的第 1 步对 Lk 1 H Lik 1 作用的结果分别为 ALk AH Lik 对 X AH Lik 根据定义 4 与定义 5 有 Lk 1 ni 1H Lik 1 于是 H Lik 1 Lk 1 由函数 Apriori gen 的第 1 步作用过程我们可得 X ALk 于是有 AH Lik ALk 所以 ALk AH Lk ni 1AH Lik 函数 Apriori gen 的第 2 步作用于 ALk AH Lik 删 除它们中的不符合条件的元素 使它们分别变为 CAk CHk 对 X ALk 若它被删除 则 必存在 X 的元素为 k 1 个的子集 Y 有 Y Lk 1 由于 Lk 1 ni 1H Lik 1 则 Y 必 不属于任意一个 H Lik 1 i 1 2 n 所以若 X AH Lk 则也必被函数 Apriori gen 的第 2 步所删除 于是有 CHk CAk 证毕 算法 PMRA 需要每个计算机 Pi i 1 2 n 对其本地事务数据库 DBi 或本地候选 事务数据库 CBi 进行多遍扫描 在第 k k 1 2 趟扫描中 计算机 Pi i 1 2 n 都进行生成候选大项集 支持数计算 交换支持数 生成稠密集等步骤 具体情况可描 述如下 见算法 1 1 生成候选大 k 项集 CHik 根据计算机 Pi i 1 2 n 在 k 1 次循环所生 成的稠密集 H Lik 1 生成循环 k 所需用的候选大 k 项集 CHik 据定理 2 有 CHik ni 1Apriori gen H Lik 1 k 设 X CHik p 为生成 X 的两个 K 1 稠密 集中的支持数较小的那一个 令 X ocount p supi 2 支持数计算 扫描本地事务数据库 DBi 计算候选大 k 项集 CHik 中的每个元素 X 的局部支持数 X supi 我们可以对 CHik 做如下剪枝 当扫描到 DBi 的某一条记录时 记 X 的支持数为 X count 若 X count X ocount 则 X 的支持数将不会再增加 对数据库 精品文档 9欢迎下载 的以后的扫描中不必考虑其中的事务是否包含 X 若 X 是局部大 k 项集 则置 CHik L L 1 3 交换支持数 计算机 Pi i 1 2 n 广播候选大 k 项集 CHik 然后收集由 计算机 Pj i j 传来的 CHjk 计算项集 X 的全局支持数 X sup 若 X sup min sup D 则置 CHik GL 1 4 生成稠密集 H Lik 对计算机 Pi i 1 2 n 若项集 X CHjk 且有 CHjk L L 1 和 CHik GL 1 则 X 是 H Lik 的元素 并行采掘关联规则的算法高效的关键在于如何能生成较小的候选大项集和如何有效地 剪枝候选大项集 根据定理 2 与定理 3 我们可以知道算法 PMAR 所产生的候选大项集要 小于算法 CD 所产生的候选大项集 算法 PMAR 在第 2 步引入特殊的剪枝技术 提高了 算法的效率 3 2挖掘关联规则的并行算法 NA 并行计算的关键性能是负载平衡与同步 在前面介绍并行算法中 如果大项集的最大 精品文档 10欢迎下载 长度为 k 至少需要 k 次同步才能得到结果 影响了响应时间 在这部分里 我们提出一 种新的并行算法 NA 不管大项集的最大长度是多少 他只需 2 次同步就能得到结果 当大 项集的最大长度比较大时 NA 会显示出更好的性能 3 2 1 设计思想 定理 1 设 N 个事务平均分布到 P 个处理器上 每个处理器上有 N P 个事务 在这 N P 个事务上直接计算最小支持度为 sup 的大项集 称他为局部大项集 把所有处理器 上的局部大项集合并到集合 S 他一定包含了 S 中所有的项目集合 即 S 是 S 的超集 证明 考察 S 中任意一个项集 s 因为 s 是大项集 所以至少有 N sup 个事务中 包含 s 这 N sup 个事务被分布到 P 个处理器上 根据鸽巢原理 至少 1 个处理器有 N sup 1 P 1 个包含项集 s 的事务 根据大项集的定义 只要在某个处理器上有 N sup P 个事务包含 s s 就成为该处理机上的局部大项集 所以 s 一定会包含在某个处 理器的局部项集中 s S 中 由此可得 S 一定是 S 的一个超集 注意 集合 S 中的项集的计数是不完全的 试想在处理器 P0 上 AB 是局部大项 集有 5 个事务支持他 由于数据分布不均造成了 P1 只有 1 个事务支持 AB 并且他因 为没有达到最小支持度而被删除 当汇总之后得到只有 5 个事务支持 AB 漏掉了一个 计 数 这可能导致漏掉一些大项集 所以必须要对这点作弥补 局部大项集得到之后用广播 的方式使得每个处理器上都得到了 S 的超集 S 然后各处理器在本地数据上对 S 中的 项集重新计数 最终再把 S 中的项集的计数汇总 得到全局计数 于是 最终得到了完 整的大项集 S 本算法让各处理器在不知道其他处理器的任何信息的情况下独立地计算局部大项集 直到所有的处理器都计算出了局部大项集后 才开始交换数据 增加或删除项集 得到最 终结果 3 2 2 算法描述 NA 算法可以简单地描述如下 1 每个处理器 Pi 在本地 N P 个数据上各自独立地计算支持度为 sup 的局部大项集 S i 2 各处理器与其他处理器交换计算所得的大项集局部集 S i 使得每个处理器都拥 有 S 的超集 S 精品文档 11欢迎下载 3 每个处理器在本地数据上对 S 中的项集进行重新计数 得到局部计数 4 各处理器把 S 上的计数与其他处理器交换 每处都得到了全局计数 5 检查是否达到最小支持度 得到最终的大项集 S 3 2 3 实现策略 NA 算法思想简单 实现起来很容易 在 1 中可以启用任何一种好的串行算法 Apriori DIC 或是抽样算法 因为计算局部大项集的过程是独立完成的 不需要同步和交 换数据 只要响应时间快 用什么方法都可以 DIC 算法在最小支持度较小时比 Apriori 有更好的性能 所以支持度小时可以考虑使 用 DIC 方法计算局部大项集 会得到较好的响应时间 而且他使用的数据结构也比较适合 该算法 抽样算法对样本的依赖性较强 若每个处理器抽样的质量不同 就有可能造成负载不 均衡 所以建议不要使用 Apriori 算法仍然算得上是个好的选择 因为在支持度不变 数据量减少的情况下 他的响应时间是呈线性减少 这一点对 NA 算法很重要 我们可以对 Apriori 算法改进之后应用于 NA 中 考虑 C2 是一个特殊的集合 由 L1 L2 所得 而且在计算候选集时的删除一步中不会有任何项集被删除 第 2 步计算的 时间会突然增加 所以把前 2 步优化会得到更好的性能 既然 C2 的项集中仅包含两个项目 索性用 1 个二维阵列存储 C2 而不用再去维护 1 个 hash tree 让行和列上都是不同的项目 二维阵列上的每个点代表 1 个项集 大大减 少对内存的需求 由于事先约定事务中的项目是有序的 实际上 C2 的存储只是 1 个上三 角阵 可以用 1 个二维数组 a 来存储这个阵列 他的下标恰好是项目的标识 当 i j 时 a i j 中是项集 ij 的计数 当 i j 时 a i j 中是单个项目 i 的计数 当从数 据库中读出 1 个事务时 可以很方便地同时为单个项目和 2itemsets 项集计数 所有的数 据都处理一遍之后 开始检查最小支持度 满足条件的保留原有的计数 取出项集和计数 在检测最小支持度的同时还可以得到 C3 并把他存储到 hashtree 中 为后面的计算作好 准备 由于要检测的计数全部存储在二维数组中 可以通过下标很快地找到想要的数据 只须花很少的时间就可以完成计算 由于 NA 算法可以不管其他处理器而独立运行 他恰 好可以使用上面介绍的优化方法 但在其他并行算法中却不能使用 原因是他们在第 1 步 与第 2 步之间必须做一次同步 交换数据之后才能得到 C2 继续后面的计算 所以 L1 和 L2 不可能在同一步中被得到 精品文档 12欢迎下载 在 NA 算法中计算局部大项集的工作完全可以异步执行 只是在最后结束时才进行一 次同步 另外 2 和 4 中 需要一些数据通信 这里可以借用其他并行算法中的好的通 信机制 降低通信开销 而且在 4 中 由于各处理器上拥有相同的候选集 S 所以与 CD 算法一样 只需交换计数即可 在第 3 步上存在冗余的工作 因为 Pi 在上已经对 S 中的一些项集进行计数了 而这步又要全部重新计算 这无疑是冗余计算 对此作一下改进 在 2 中为处理器记录 原来本地没有而新增加的项集 这样在 3 中只须要为新增加的项集计数 避免不必要的 重复计算 在 4 中只须交换各自的新增加候选项集的计数 就能得到全局计数 3 3 一种改进的基于 Apriori 算法的挖掘关联规则的并行算法 IDD IDD 算法弥补了 DD 算法的不足 在 IDD 算法中 局部存储数据库通过一种基于环的多 对多广播方式传送给其它所有处理器 这项操作不会产生像算法那样的竞争问题 同时它 的时间复杂度为 O N 这项数据移动的伪码如下 在该算法中 处理器形成一个局域的环 每一个处理器决定它左右相邻的处理器 每 一个处理器都有一个发送缓冲区 Sbuf 和一个接收缓冲区 Rbuf 开始时 SBuf 中充满数 据 接着每一个处理器在 SBuf 中初始化一个异步发送操作为它右边的处理器 在 RBuf 中 精品文档 13欢迎下载 初始化一个异步接收操作 为它左边的处理器 当这些异步操作执行时 每一个处理器处 理 SBuf 中的事务并收集分配给这个处理器的候选的个数 然后 每一个处理器等待这些异 步操作的完成 这时把 SBuf 和 RBuf 互相交换 然后执行以上操作 直到循环 p 1 次为止 和 DD 算法相比 在所有的处理器发送数据给其它所有的处理器时 该算法在相邻处理器间 执行的是点到点的通信 这样就减少了通信竞争 更进一步 如果处理一个缓冲区的时间 变化不大的话 该算法中处理器的空转时间将很少 为了消除分割候选项目集的工作冗余 算法运用了一个快速检查给出的事务是否是潜 在的存储在每一个处理器中的候选的方法 算法在处理器中用这种方法分割 Ck 这样每一 个处理器可以得到从所有可能项目的子集开始的项目集 如果哈希树包含了从这些项目开 始的候选 就检查一个事务的项目是否与该子集相符 当事务中的项目属于这个子集时 遍历哈希树 这样通过这种智能的分割 就解决了 DD 算法中的工作冗余问题 图是算法的示例 在这个示例中 处理器 0 中是从项目 1 和 7 开始的所有候选 处理 器 1 中是从项目 2 和 5 开始的所有候选 以此类推 每一个处理器把候选的第一个项目放 在一个位图中 在 Apriori 算法中 在哈希树的根部 每一个处理器通过检查这个位图来 确定处理器是否包含从这个项目开始的候选以此来过滤事务的所有项目 如果处理器没有 包含 从这个项目开始的候选则从这个项目开始的候选的处理步 骤将会跳过 这样就减少 了计算量 如假设 1 2 3 4 5 6 7 8 是一个事务集合 在哈希树的顶部 处理器 0 将从 项目 1 和 7 开始执行 当包含这个事务的页转移到处理器 1 时 处理器 1 将只从项目 2 和 5 开始执行 图所示的就是这样的一个方案的执行过程 这样对于数据库中的每一个事务 算法把工作在处理器间分割 消除了 DD 算法的大部分工作冗余 从以上可知 分割哈希树 精品文档 14欢迎下载 和过滤都是消除处理器间的工作冗余所必需的 在 IDD 算法中智能的分割候选集合能够在处理器上达到负载平衡 也就是说 在所有 的处理器上的候选的数目是相等的 为了达到候选项目集的相等分布 该算法运用了一种 基于 bin packing 的分割算法 对于每一个项目 首先计算从这个项目开始的候选项目集 的数目 接着运用 bin packing 算法把这些项目分割到个桶中 这样就可以使从这些项目 开始的候选项目集的数目在各个桶中是相等的 一旦候选项目集的位置确定了 每一个处 理器都可以存储自己的候选项目集 在 IDD 算法中的每一步中都用了 bin packing 算法 并且花在 bin packing 算法上的时间跟整个运行时间相比是较少的 图中显示了候选哈希 树的分割和在每一个处理器上相应的位图 4 结束语 本文对采掘关联规则问题进行了简单地回顾 给出了一种提高顺序采掘关联规则算法 效率方法 对在分布式事务数据库中采掘关联规则问题进行了研究 提出了一个效率较高 的并行算法 PMAR 实验证明 算法 PMAR 是有效的 算法 PMRA 也可以对设计并行地采掘 一般关联规则 序列模式及关联规则的增量式更新等问题提供借鉴 NA 算法的思想有些 像抽样算法 先通过某种方法得到一个候选集 只不过抽样算法利用样本得到一个候选集 而 该方法是利用多个处理器的并行计算得到候选集 S 但不同的是后者得到了大项集的超 集 所以再扫描一遍数据库即可得到最终的大项集 而前者得到的候选集无法保证是超集 有 可能报告失效 这时还须扫描数据一遍或多遍 直到不再报告失效为止 NA 在计算局部大 项集是利用前面介绍的优化方法 而且只需 2 次同步 在计算方法和同步次数都要优于 CD 算法 NA 算法的设计思想虽然简单 但却有很好的性能 IDD 算法在创建哈希树的过 程中有很高的效率 而且随着候选集合规模的增长它是可扩展的 该算法在 DD 算法的基础 上进行了改进 利用智能分割候选集合和位图减少了不必要的计算 减少了处理器间的通 信量和工作冗余 该算法的另一个特点是对于只有一个数据源的数据库有很好的适应性 精品文档 15欢迎下载 参考文献 1 A grawal R Srikant R Fas