并行关联规则挖掘综述

1 关联规则的基本概念
关联规则的形式化描述如下：
令I
=
{i
,
1
i
,...,
2
i
m}
为项目集，D为事物数据库，其中每
个事物T是一个项目子集( T ⊆ I )，并另有一个唯一的事物标
识符TID。如果 X ⊆T ，则事物T 包含项目集X。
一个关联规则是形如 X ⇒Y 的蕴涵式,这里 X ⊂ I,Y ⊂ I ,并
balancing strategy used, and the integration with databases. The goal of this paper is to serve as a re源自文库erence for both researchers and practitioners
interested in the state-of-the-art in parallel association rule mining. 【 Key words】 Data mining；Association rules；Parallel algorithms
关联规则挖掘具有计算量大，I/O 负载集中的特点。而 且许多关联规则的实际应用涉及到海量数据。在这种情况 下，即使对算法进行了优化，在单处理机上使用串行算法进 行挖掘所需要的时间可能也是无法接受的。其主要原因在于 单处理器本身受到内存和I/O 带宽的限制。因此，必须依靠 高性能并行计算来有效地完成挖掘任务。
Survey of Parallel Association Rule Mining
SHANG Xuequn，SHEN Junyi
(Software Institute,School of Telecom Engineering, Xi'an Jiaotong University, Xi'an 710049) 【Abstract 】Due to the huge size of data and amount of computation involved in data mining, high-performance computing is an essential
Zaki等在论文中提出了基于数据的垂直分布的关 联规则发现算法。其中最简单的是Eclat算法，性能最 好的是MaxClique算法。当前多数关联规则挖掘算法采 用的是水平数据分布方式，即数据由一系列事物构 成。使用这种格式，计算负载主要集中在支持计数 上。而且，数据的水平分布迫使每次循环均需遍历整 个数据库或每个局部划分。数据的垂直分布是指数据 集由一系列项目构成。数据垂直分布的优点在于可以 通 过 简 单 地 链 接 任 意 两 个 (k-1)- 子 集 生 成 候 选 k- 项 目 集，不需要复杂的hash数据结构，无须对数据库进行遍历。
第 30卷 第 14期 Vol.30 № 14
计 算 机 工 程 Computer Engineering
2004年 7月 July 2004
·发展趋势 /热 点 技 术 · 文章编号： 1000— 3428(2004)14 — 0001— 03
文献标识码：A
中图分类号： TP182
并行关联规则挖掘综述
多 处 理 器 体 系 结 构 有 3 种 形 式 ： 共 享 内 存 系 统 (sharememory system)，共享磁盘系统(share-disk system)和不共享 系统(share-nothing system)。在共享内存系统中，所有处理 器共享一个通用的，非常大的内存。这样任何一个处理器都 可以访问所有的数据，具有动态负载平衡。在这种系统中， 想要获得好的并行性能，关键在于处理好数据的同步问题。 在共享磁盘和不共享系统中，数据分布在各个处理器节点 上，它们之间的通信和I/O 是通过消息传递来实现的。因此 获得好的并行性能的关键就在于合理分布数据，以取得好的 负载平衡，减小通信代价。
尚学群，沈均毅 (西安交通大学电信工程学院软件研究所，西安 710049 ) 摘 要 ：关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算， 高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析 和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。 关 键 词 ： 数据挖掘；关联规则；并行算法
component for any successful large-scale data mining application. This paper provides a survey of the study in parallel association rule generation,
reviews and analyses some typical algorithms, views the trend of parallel association rule mining based on the kind of parallelism exploited, the load
2 串行关联规则挖掘算法
目前所有并行关联规则算法都是在相应的串行算法的基 础上提出的。本文首先对这些串行算法进行介绍和分析。 2.1 Apriori-like 算 法
在各种关联规则挖掘算法中，最经典、最广泛使用的就 是Agrawal等[2]设计的Apriori算法，其核心思想是基于频集理 论的递推方法。首先产生频繁1-项集，然后是频繁2-项集， 直到有某个r值使频繁r-项集为空，算法停止。这里在第k次 循环中，过程先通过对两个只有一个项不同的属于k-1的 频 集做(k-2)-连接产生候选k-项集的集合。然后验证候选k-项集 中的每个元素来决定是否将其加入k-频集，这里的验证过程 是算法性能的一个瓶颈。这个方法要求多次扫描数据库，这 就需要很大的I/O负载。
作 者 简 介 ：尚学群(1973－)，女，博士生，研究方向：数据挖掘和 并行数据库查询处理；沈均毅，博导 收 稿 日 期 ：2003-04-17 E-mail：xq_shang@sina.com
—1—
修剪，任何物理上的修剪意味着在每次循环中要改写数据 库，这是不切实际的。
Savasere等提出了一种基于划分(partition)的算法。这种 算法把数据库从逻辑上分成几个互不相交的块，每次单独考 虑一个分块并对它生成所有的频集。然后把产生的频集合 并，用以生成所有可能的频集，最后计算这些频集的支持 度。Partition算法很大程度上减小了I/O负载。然而在处理高 项集时存在一些问题，而且它还有频集的错误处理的缺陷。 Brin等提出的Dynamic Itemset Counting(DIC)，也是基于划分 的一种算法。它通过在一个循环中生成不同长度的候选集以 减少数据库扫描的次数，有效地改进了算法在低层的效率。 然而该算法在同构数据的情况下具有较好的性能。例如，多 数分块有相似的频集分布。否则，DIC可能需要比Apriori更 多的对数据库的扫描。
Muellel在 他 的 硕 士 论 文 中 提 出 了 4种 基 于 Apriori 和 Partition的算法：SEAR算法， 基于TID划分的SPTID算法， 基于划分的SPEAR算法和SPINC算法。SEAR算法与Apriori 算法相似，只是该算法用一个前缀数(prefix tree)取代杂凑数 (hash tree)来存储候选项集，而且引入了一个循环绑定 (pass bunding)的优化策略，即只要内存允许在一个循 环中可生成不同长度的候选集，这样在对数据库的一 次扫描中就可以计算所有当前候选集的支持度。实验 表明，SEAR算法优于其他算法，具有较好的性能。
3 并行关联规则挖掘算法
尽管关联规则的描述很简单，但是它却是一个计算 和 I/O集中的任务。假设给定m个项目集，那么存在2m个 子集可能是频集。处理如此指数级的数据需要大量的磁盘I/ O。实验证明，在限定交易长度的情况下，关联规则的挖掘 和数据库的大小呈线性递增的关系。而且，随着项目集的数 量和维度的增加，以及交易数据库大小的增加，串行算法显
N：数据项集的数目 P：处理器的数目 M：候选集的大小 图 1 CD算法
Agrawal 等[1]提出了 3种基于Apriori的并行关联规则挖掘 算 法 ： Count Distribution(CD) ， Date Distribution(DD) 和 Candidate Distribution算法。它们是在不共享的IBM POWER 并行 SP2系统上实现的。Apriori算法的主要计算代价是候选 集的生成及其支持度的计算。因此高度并行地完成此过程必 然可以大大地降低算法执行的时间，提高算法的性能。一种 并行的方法是复制候选集(CD算法)(见图1)，另一种方法是 划分候选集(DD算法)(见图2)，再就是将两种方法合成，即 部分划分候选集的方法(Candidate Distribution)。CD算法将生 成候选集的过程复制到所有处理器上。每个处理器生成一个 完整的候选杂凑树，根据本地数据库分块独立地计算出候选 项的局部支持计数，然后通过在所有处理器之间交换局部支 持计数来得到全局支持计数。因为在处理器间只需交换支持 数而不是合并不同的杂凑树，这种算法具有较小的通信负 载。然而它并没有实现杂凑树构成过程的并行化，在处理器 数量增加的情况下，将成为算法执行的瓶颈，而且它也没有 有效地利用内存。DD算法用一种循环的方式将候选集划分 到每个处理器中，然后由每个处理器负责计算本地存储的候 选子项集的支持计数。这个过程需要每个处理器既要扫描分 配给该处理器的数据库，还要扫描其他处理器上的数据库， 从而导致了很高的通信负载，降低了该算法的性能。为了交
关联规则是R.Agrawal等人首先提出的KDD的一个重要 研究内容，近年来受到了数据库界的广泛关注。
关联规则是寻找在同一个事件中出现的不同项的相关 性，即找出事件中频繁发生的项或属性的所有子集，以及它 们之间应用相互关联性。关联规则最早用于发现顾客交易数 据库中不同商品间的联系，后来诸多的研究人员对关联规则 的挖掘问题进行了大量的拓展和研究。他们的工作包括对原 有算法的优化，如引入并行的思想，以提高算法的效率，对 关联规则的应用进行扩展。
confidence( X ⇒Y )，即
confidence( X ⇒Y )= {T : X ∪ Y ⊆ T , T ∈ D} / {T : X ⊆ T ,T ∈ D} 给定一个交易集D，关联规则的挖掘问题就是产生支持 度和可信度分别大于用户给定的最小支持度(minsupp)和最 小可信度(minconf)的关联规则。 关联规则的发掘分为两个步骤：(1)找出所有支持度大 于最小支持度的频集；(2)从频集中产生期望的规则。
且 X ∩Y =ф。规则 X ⇒Y 在交易数据库D中的支持度( support)是交易数据库中X和Y的交易数与所有交易数之比， 记为support( X ⇒Y )，即
support( X ⇒Y )= {T : X ∪ Y ⊆ T , T ∈ D } / D
规则 X ⇒Y 在交易数据库D中的可信度(confidence)指包 含X和Y的交易数与包含X的交易数之比，记为
Park等提出了一个高效地产生频繁集的基于杂凑(hash) 的算法：Dynamic Hashing and Pruning(DHP)算法。通过实验 可以发现寻找频集的主要计算是在生成频繁2-项集上。DHP 利用一个杂凑表在计算频繁1-项集时先大概计算出2-项集的 支持度，从而减少了候选2-项集的数量。DHP还采用了数据 库修剪技术，通过修剪掉那些不包含频集的事物集以减小下 一次循环中数据库的大小。然而，这种修剪技术的优化并不 显著。其主要原因在于只能通过过滤对数据库执行逻辑上的
—2—
然不具有良好的性能。因此必须依靠高性能并行计算来有效 地完成挖掘任务。然而利用多处理器系统进行关联规则发 现，要想获得好的性能并非易事。其中涉及到的问题包括： 减小同步和通信，负载平衡，数据放置和减小磁盘I/O。下 面从并行度、负载平衡、以及实现平台等方面对当前主要的 并行关联规则发现算法进行介绍和分析。 3.1 基 于Apriori的并行关联规则挖掘算法
以上介绍的都是基于Apriori的关联规则挖掘算法。即使 已经进行了一定的优化，但是Apriori方法仍存在一些固有的 无法克服的缺陷：(1)可能产生大量的候选集；(2)对数据库 进行多次扫描。 2.2 FP-growth算 法
Han等提出了一种富有创新性的方法，即FP-growth方 法。这种算法采用了分而治之的策略，经过第1次扫描之 后，把数据库中的频集压缩到一棵频繁模式树(FP-tree)中， 同时依然保留其中的关联信息。随后再将FP-tree划分为一些 条件库，每个库和一个长度为1的频集相关。然后再对这些 条件库分别进行挖掘。FP-growth只需对数据库进行二次扫 描，而且避免了产生大量候选集的问题。实验表明， FPgrowth对不同长度的规则具有很好的适应性，同时在效率上 较之Apriori算法有很大的提高。