关联规则的增量式更新算法.pdf

关联删 更新 1 、 冯 玉 才 冯 割 琳 1 r 5 l l 、0 华中理工大学计算 饥系武 汉4 3 0 0 7 4 摘要关联规 则的开 采是 一个 重要 的数据 开采 问题．目前 已经提 出 了许 多耳法用 于高鼓地发现 大规模 数 据库 中的关联 规 则， 而对关联规 则维护 问题的研 完工作却艰 少． 在 用户开采 关联规 则的交互 过程 中 ， 为 了 找到真正令 其感兴趣的规 则 ， 用户将需 要不断调整两个描述 用户兴趣程度的闽值 最小主持度和最 小可信 度． 本 文提 出了两 种增量 式更蘸 导 法 I UA i n c r e me n t a l u p d a t i n g a l g o r i t h m 和 P I UA p a r a l l e l i n c r e me n t a l u p d a t i n g a l g o r i t h m ， 用来解决这一关联 规且 - I 高鼓 维护 问题． 1 ， ． 差 ． ，．掣 ， 塑， 型 查 兰 翩晾。 瓠龋 中 圈 法 分 类 3 3 书 『 【 数据开采 Da t a Mi n i n g 又称数据 库 中的知识发 现 KD D k n o wl e d g e d i s c o v e r y i n d a t a b a s e s ， 已经被 认为是数 据 库研 究中的 一十极 富应 用前景 的新领域． 这一领域 可 以定义为在大 规模 数据库 中高效地发 现潜 在可 用的模式 P a t t e r n s 或规则 R u l e s ． 推 动数据开采迅猛发展的是 大型零售组织所面临的决策 支持 问题 ． 条型码技 术的发展 已经 使得 超级市场能够收集和存储数量巨大的销售数据． 一条这样的数据记录通常都包括与某个客户相关的交易 Tr a n s a c t i o n s 日期 、 交 易中所购物品项 目 i t e m s 等等． 通 过对 往 的大量交 易数据进 行分析就能昭 获得有关客 户购 买模式 的 有用信息， 从而提高商业决策的质量． _ I 在交易数据项 目之 间开采关 联规则的 问题 Mi n i n g As s o c i a t i o n Ru l e s 是 R． Ag r a wa l 等人 在文献 [ 1 中首先 引入 的． 有一十关联规 则的例子就是 “ 9 0 的客户在购买面包和黄 油的同 时也 会购买牛 奶” ， 其直观 的意 义是 ， 客户在购 买 某些东西的时候有多大的倾向也会购买另外一些东西． 找出所有类似这佯的规则， 对于确定市场策略是很有价值的． 关联规则的其他应用还包括附加邮递、 目录设计、 追加销售、 仓储规划以及基于购买模式对客户进行划分等等． 这些应 用 中的数据 库都是极 其庞 大的 ， 因此 ． 不 仅需要设计高效 的算 法来开 采关联规则 ， 而且也迫 切需要设计 高敷 的算 法来 更新、 维护和管理已开采出来的关联规则． 目前大量的研究工作主要集中在开采算法方面口 ． 而对更新算法方面的 研究工作却很少． 口 本文主要考虑当最小支持度 mi n s u p mi n i mu m s u p p o r t 和最小可信度 mi n c o n f m[ n l mu m c o n f i d e n c e 发生变化时 当前交易数据库 中关联规则 的更新 问题 ， 提 出了两 种高 技的增量式更新算法 1 UA i n c r e me n t a l u D d a t i n g a l g o r i t h m 和 P I UA p a r a l l e l i n c r e me n t a l u p d a t i n g a l g o r i t h m ． 详细的问题描述在第 1节给出． 第 2节描述 1 UA算法和 P I UA算法． 性 能分析则在第 3 节 讨论 ． 第 4节作 出总结． 1 问题描述 1 ． 1 关联规则的开采 关联规则开采 问题 的形式 化描述如 下 l l _ ] 假设 一{ i ⋯i⋯ ⋯i 是 卅十不 同项 目的一个 集合． 给 定一十交 易数 据库 D， 其 中每一个交易 是 中一组 项目 的集合 ． 即 ． 每一十交 易都 与一十唯一 的标识 符 T I D相联． 如果 对于 J中的一个子集 x． 有 x ． 我 们就说 一个 交 易 包 含 x． 一条关联规则 A s s o c i a t i o n R u l e 就是一 个形如 x y 的蕴涵式 ， 其 中 x亡J ， y亡J ． 而且 xny一 ． 如果 D 中 c ％的包含 x 的交易同时也包 含 y． 则 关联 规则 x y在 D 中以可信度 C o n fi d e n c e 成立 如果 D 中 ％的 交 易包含 xUy， 则 关联规则 x y在 D 中具有支持 度 S u p p o r t ． 关联规 则 的开 采 问题 就是 生成所有具 有用 户指定 本文研究得到国家 8 6 3高科技项目基金资助． 作者冯玉才， 1 9 4 5 年生． 教授， 博士导师， 主要研究领域为数据库， 多媒体， G I S 冯刳琳 ， 1 9 7 0年生 ， 博士 生， 主要研究领域为数据开采 本文通讯联系人 冯玉才， 武汉 4 3 0 0 7A， 华中理工大学计算机系 本文 1 9 9 7 0 4 - 2 2 收 到原稿， 1 9 9 7 0 7 1 8 收到修 改稿 维普资讯 软件学报 9 卷 的最 小支持度和最小可信度 的关 联规 则 ， 即 这些 关联 规则 的支持度和可信度分别 不小于最 小支持 度和最小可信度 ． 关联规则 的开 采问题可 以分解 成 下两个子 同题 ①找 出交 易数 据库 D 中所有 具有 用户指定最 小支持 度的项 目集 i t e mt ， ，的一 个非空子集 ． 具有最 小支持度 的 项 目集称 为频繁项 目集 F r e q u e n t I t e ms e t s ， 反之就称为非频繁项 目集． ②利 用频 繁项 目集生 成所需要 的关 联规 则． 对 于每 一个频繁项 目集 A， 找 出 A的所有 非空子集 n ， 如果 比率 s u P p o r t A ／ s u p p o r t a ≥mi n c o n f ， 就生成关联规则 口 似 --a ． 由于第 2个子 同题较 为容 易和直观 ， 目前大量的研 究工 作主要都集 中在第 1 个子 同题上． ． 1 ． 2 相 关工 作 在 已经提 出的许多 算法 中， R． Ag r a wa l 等人在文 献[ 2 ] 中提 出的 Ap r i o r i 算法是最 有影响的． 除 了最 初提 出的 性能较 Ap r l o r i 差 的 AI S算法及其面 向 S Q L 的变体 S E T M_ ] ～， 目前 已知 的大多数算法都 是以 Ap r i o r i 为核心 ， 或是 其变体 ， 或是 其扩 展． 口 Ap r i o r i 是 一种宽度优先算 法 ， 通过 对数据库 D的多趟 P a s s 扫 描来发现 所有的频繁 项 目集 ， 在 每一趟 k中只考 虑具 有同一长度 k 即项 目集 中所含项 目的个数 的所有项 目集． 在第 1 趟 扫描 中， A p r i o r i 算法计算 中所有单 个项 目 的支持度 ， 生 成所 有长 度为 1 的频繁项 目集 ． 在后续 的每一 趟 k中 ， 首先以前一趟 中所发 现的所有频繁项 目集为基础 ， 生成所有 新的候选项 目集 C a n d i d a t eI t e ms e t s ， 即潜在的频繁项 目集 ， 然后 扫描数据库 D， 计 算这些候选 项 目集 的支 持 度 ， 最 后确定候选项 目集 中哪一 些真 正成为频 繁项 目集． 重复上述过程 直到再也发 现不 了新的频 繁项 目集． 算法 高 效的关键 在于 生成较 小的候选 项 目集 ， 也 就是尽 可能 不生 成和计算那些 不可能 成为频 繁项 目集 的候选 项 目集． _ 2 ． 为了实现这一点， 所有已知的算法都利用了这样一个基本性质， 即一个频繁项 目集的任一子集必定也是频繁项 目集． 1 ． 3 关联规刚的更新 D． W． C h e u n g等人首先考虑 了关联规则的高效更新同题． 他们考虑的同题是给定交易数据库 D B， 候定最小支持 度不变， 当一个新的交易数据集 d b添加到 DB中去时， 如何生成 DBU 中的关联规则． 他们提出了增量式更新算法 F UP， F UP的基本框架和 Ap r i o r i 是一致的． [ ] 本文的目的在于， 考虑当交易数据库 D保持不变， 而最小支持度和最小可信度发生变化时， 关联规则的高效更新 同题． 事实上， 为了发现事先未知的关联规则 ， 用户必然需要通过对最小支持度和最小可信度这两个闽值的不断调整 来逐步聚 焦到那些真正 令其感兴 趣的关 联规 则上 去 ， 这将是一个动态 的交互过程 ， 因此 ， 迫切 需要 高技的更 新算法来 满足用户对较快 的响应时间的需求 ． 显然 ， 对 于最 小可信度发生变化 时的关联 规则 的更 新 同题就 如同 1 ． 1 节 的第 2个 子同题一样直观， 因此， 我们主要考虑最小支持度发生变化时关联规则的高效更新问题， 并且这一问题也归结为发现 在 新的最 小支持度下 的所有频繁 项 目集． 对 于这 一更 新同题 ， 一 种可能 的方法就是将 关联 规则的 开采算法 如 Ap r i 3 i 以新的最小支持度重新运行一遍． 这种方法虽然简单明了． 却有着明显的不足． 因为最初用来发现旧的频繁项 目集的 计算都将被浪费， 所有的频繁项 目集都必须从头开始计算． 本文提出的增量式更新算法 1 UA和 P 1 UA将利用从旧的 频繁项目集所获得的信息来高效发现所有新的频繁项 目集． 2 增量式更新算法 I L I A和 P I U A 给定交易数据库 D， 一十项 目集的支持度可以就认为是所有包含该项 目集的交易的数 目． 设旧的最小支持度为 ， 厶 为这时所 有频繁 k项 目集 f r e q u e n t k - i t e ms e t s ， 即长度为 k的频繁项 目集 的集合 ， 1 ． 2 ⋯ ． ， m1 ， 这里 为所 有 频 繁项 目集 长度中的最大者 ． 同样地 ， 对 于新的最 小支持度 ， 设 厶 为所 有频 繁 k项 目集的 集合 ， k 1 ， 2 ⋯ ． ， 辨 对 于每一个项 目集都有一个域 c o u n t 用来保存它的支持度 计数． 当最小支持度发生改变时 ， 可以分 为如下两种情况 ； ， 原 有的一些 频繁项 目集可 能失去最小支持度 I ② 1 f o r l } ． 所 以原来所 有 的频繁 项 目集 厶 在新 的最小支持度 下仍然是频 繁 项 目集 ， 因此在 每一趟 中扫 描交 易数据库 D计算候选 项 目 集的支持度计数时 ． 我 们就 没有必要再考虑 一遍 厶 对应的候选 项 目集． 如果更进 一步希望避免 叉重新生成一遍 厶 对应的候选 项 目集 ， 我 们可以考虑采取 以空 间换 时 间的策略 ， 只要 在 Ap r i o r i 算法中 的每一趟 k ． 保 存相应 的 c 。 一 L D即可． 在第 1 趟 扫描 中 ， I UA 算法只 对原来 不在 L_ 中的单个 项 目进行支 持度 计算 ， 井确 定 出所 有新 的频 繁 1 项 目集 L 1 ， 然后通过 ￡ - U L1 得到 ￡ - ． 在后续的每一趟 中 ． 包 括两个阶段． 首先 生成计算 厶 所需的候选 项 目集 c a n d i d a t e i t e ms e t s ， 即长度为 的 候选 项 目集 ． 设 c 为所 有候 选 项 目集 的集台 一种质朴的增量 式方法就 是我们利 用 Ap r i o r [ 算法 中的 a p r i o r i g e n 函数0 按如下方式来生成 C t C a p r i o r i g e n L k l ’ 一Lj ． 为了更好地利用从 旧的频繁项 目集所获得 的信息来高教地 发现所有新 的频繁项 目集 ， 我们提出了一种新 的生成 所有候选 项 目集 C 的方 法 ， 这 一新 方法的关键就 在于我 们发掘 的如下一个重要 事实． 在第 1 趟 中， 所有 的频 繁 1项 目集 已经被分成两个 不相 交 的集合 L 1 和 L 又因为一 个频繁项 目集的任一 子集 必定也是频繁项 目集 ， 所 以频繁 项 目集 c中的每一单个项 目i 所 对应 的频 繁 1项 目集 { 或者从 L 1 中取 ． 或者从 L_ 中取． 根据这一点 ． 我 就 可以将具有新 的最 小支 持度 S 的所有频繁 项 目集分 成 3类 ① 对于 其中的每一个频繁 项 目集 一{ ， i ． i 1 ， V J 1 ≤J ≤ ， 必有 ∈L - ； 对于其中的每一个频繁 项 目集 f 一 ， i z _ ． 川i ， V J 1 ≤J ≤ ， 必有 { ∈L． ； ⑧对于其 中的每 一个频繁 项 目集 f 一 { i - i ． ． - ． r ．i} ， 必有 两个非 空子集 r 和 ％ 使得 r ． Uc 。 一c 岫 n c 一 ， 而 且 c l cLI ， CLl ” ． 因此我们就得到 厶 的一个分划， 厶 由 3 个互不相交的子集构成． 我们将所有第①类频繁 项 目集构成的集台记 为 ， 第②类记 为 雎 ， 第③类记为 ． 同时与之相 对应的候选 项 目集构成的集合分别记 为 C i ， c j ， c { ． 其中 C { 之 中可 以去掉原有频繁 k 项 目集 厶 ． 这样生成 的第① 类频 繁 项 目集构 成的集合记为 础 ， 即有 一 U厶 ． 于是 ． 我们有 厶 ’ 一 U U ． 而且 nL i 一 ， Ll n 一 ， L { n 一 ． 对 于 C i 和 C l ， 我们直接 利用 A p r i o r i 算法 中的 a p r i o r i g e n函数按 如下方式生成 C i a p r [ o r i g e n L i I 一厶 ； C i a p r i o r i g e n 雎一 1 ． 我们提 出一个 新的候选 项 目集生成函数 i u a g e n L 来生成 c i ． 事实上 ， 中的每一个候选 项 目集只需将 一 个第①类频繁 J 项 目集 1 ≤ ≤ 一1 和一个第 ②类频繁 一J 项 目集进行 简单 的拼接 即可． 这里 假定这一对 项 目集 都不 为空 ． i u a g e n 函数分为两步 1 拼接 i n s e r t i n t o cj s e l e c t声． i t e mi ， 户 i t e m2 ， ． ． ．， 声 i t e mj ， g ． i t e ml ， ／ t e rn2 ⋯． q ． 啪 j ho rn ， 雕 2 修剪 f or a i l i t e ms e t s c ∈C d o f o r a i l 一 1 一 s u b s e t s o f d o 】 f“在 i 一 】 t h e n d e l e t e f r o m ci l 将所有的第④类频繁 J 项 目集与相对应的第②类频繁 一J 项 目集通过 [ u a g e n 函数进行拼接 ， 就 得到 c { 现在 ， 我们来说 明候 选 项 目集生成 函数 i u a g e n 的正确性 ， 也就 是 成 立． 正 如前 面所 定义的 ， 中 的每一个频繁 项 目集都是 由两 个不相交 的非 空子集 和 c 组 成． 又 由于 一个频繁项 目集的任一子集必定 也是频繁 项 目集 ． 因此 和 f z 必然都是频繁项 目集． 而 i u a g e n L 中的拼 接步就相当于 将每一个第① 类频繁 J 项 目集分 别和 每一个第②类频繁 幢--j 项 目集进 行集台的“ 并” 操作 ， 从而生成 所有潜在 的频 繁 项 目集． 为 了避免重复生 成相 同的 候选 项 目集 ， 我 们只需 将第①类频繁 J项 目集从 1到 幢一1 迭代． 通过迭代 ． 我们就考虑 了将频繁 k项 目集划分 为 维普资讯 软件学报 9卷 两 个不相交非 空子集的所有 组合情况 ． 因此 ， Ci 必然是 的一 十超集 ， 亦即 c 。3 “a ． 其次 ， 在 修剪步 ． j u a g e n L 删 除的只是那些 根本不可能 出现在 中的项 目集． 在这里 ， 我们也是 利用了“ 一十频 繁项 目集 的任一子集必定也 是频繁 项 目集 这一基本性 质． 综上 ， 我们就有 c i 成立 ． 同理可知 ， c U厶 L ． 也是成立 的． c J 生成之 后 ， 紧接着就 扫描 数据库 D， 最终 生成 L ． 上述过程 一直重复到不再有新 的频繁项目集生成为止． 我 们可 以根据 L 一1 ， 2 ， 3 是否 为空独立地决 定是 否还 需 进入 一1 趟计算 厶 ． 显然 ， 对 的计算总是最 后一十结 束的． 在下面 的算法描述 中 ， 我们 只简 单地以判 断 厶 是否为 空来决 定 I UA 算法 是否还需进八 曲1 趟． I uA算法的基本框架描述 如下所示． 算法 2 ．I UA算法 1 L 1 一{ n e w I r e q u e n t I - i t e ms e t s I L 1 一L 1 UL】 l 2 f o r 一2 l 厶1 ≠ | d o b e g i n 3 C a p r ] o r i g e ． L j L L | 4 c l a p r ] o r [ 一 g e n L ] 一L ； 5 翻 一 ‘ 6 f o r J 1 I 一 1 F J d o 7 翻一c j Ui u a g e n L } l ／ * 生成所有第③娄候选 项目集 * ／ 8 e a d 9 f o r a 1 1 t r a ns a c t io n s t ED do b e g i n 1 0 C , 1 s u b s e t c 1 ． f | ／ 中包古于交易 l 的候选 项目集构成 0】 ／ I 1 f o r a 1 1 c a n d i da t e s c ∈o 】 d o 1 2 ． c o u n t - F| ／ C rl 中候选 项目集的支持度计数加 1* ／ 1 3 C s b s a C t ， f l 1 4 f o r a l l c a n d i da t e s c ∈C d o 1 5 ． o u m- F- F j 1 6 0 s b s e t C ] ， f 1 7 f o r a l t c a nd i d a t e s ∈C d o 1 8 ． C O u n t l 1 9e n d 2 0 朋 c ∈e l ． 删埘f ≥一 l 一朋 Un F 2 1 I 3 c ∈c j ． C o u n t ≥ } F 2 2 I 3一 { ∈c j ． C O unt ≥一 } 2 3 工 l U U 2 4e n d 2 5 An s we r U 厶 ． 2 ． 2 P I UA算法 在 1 UA算法中， 我们已经将所有的频繁 项目集分成了互不相交的 3类， 这使得 1 UA算法能够很容易实现基于 共 享 内存 S h a r e d me mo r y 多处理 机结 构的 并行化 ， 即 P 1 UA 算法 ． 事实 上 ， 象 P 1 UA这样 的基于共享 内存 多处理机 结构的并行算法特别有 利于在限 时应 用中用来加快单个大顺 序算法的计算 ． 设有处理机P ， P⋯P ， 它们有一个共享 内存 ， 都能同样地运行 I UA算法 ， 但只有处理机 P。 能够访问外存中的交 易数据库 D． 让处理机P。 I ， 2 ， 3 负责计算对应的 c 和 对， 处理机P 同时还负责扫描交易数据库 D． P I UA算 法 的基本框架可 以简单地描述如下 算法 3 ． P 1 UA算法 s的情况 下 ， I UA 算法 显然将 大大优 于 Ap r i o r i 算法 厂 ]_T] 现在来考虑时s s 的 情况． 模拟安验 是在奔腾1 2 0 上Win d o w s I ， 1 ． I ． 1 N T 4 ． o 下进 行的， 使用了与文献[ 2 ] 同样的 生成程序来合成所需 1 i ＼ 1＼ l 的 测 试 数 据 ” 圉 1 显 示 丁 测 试 数 据 库 包 含 1 0 0 o o 6 个 数 据 记 录 磬 4 ～ 时 的 实验结果． 4 r 1 f ■ 卜 图1 中3 条折线分别对应旧的最小支持度 取值2 ． o o ％． 同 l } j 印 1 ． 5 0 ％和0 ． 7 5 ％ ． 测试数据库的有关参数使用文献[ 2 ] 中同样的 l l 1 l ＼ 记号来表示 l DI 表示交易数据记录的数目} l Tl 表示交易数据记 { 1 { { l 录的平均长度； J f 表示最大的潜在频繁项目集的平均长度； j Lf 1 L _ T _ _ _ L 1 1 表示 最大的 潜在额繁项 目集的 数 目j N 表示 交 易项 目的个数 ． 而 L J J 一 十强 l 试数据库实例则记为T z ． 如． D m K， 也就是1 D1 m K． I T1 l 5 o ％1 0 o 堑 0 ． 0 5 0 o 2 5 ％ 一 以 及 I1 1兰 ． 在 我 们 的 实 验 中 Ⅳ 一 l 。 0 o ， IJ已 I 一 2 0 0 o ． 实 验 结 最 小 支 譬 度 果表 明在 1 O 0 0 0 0 个交 易敷据记录时 ， I UA算 法 比 Ap r i o r i 算法快 岢_ s 。 。 ％ Bs L 。 ％ ● _ s ；。 ， 5 2 ～6倍 ， 而当交易披据记 录增 加到 l 0 0 0 0 0 0个时 ， 性能 加速 比为 图l 性骺加速 比 1 1 O - I 4 D l O O K 2 ～1 4倍． 因此 ， I L I A算 法在增 量式 更新关 联规 则 的意义上 优 于 Ap r i o r i 算法． 现在， 我们来对实验结果作出分析说明． 事实上， 算法高效的关键在于如何高效地生成较小的候选项目集． 在第 1 趟 中 A p r i o r i 算法需 要对全集 ，中的所 有单十项 目进 行支持度 计数 以生成频 繁 1 项 目集 ． 而 I UA 算 法只需要 考虑 I --L 中的单个项 且． 在后续 的 第 趟中 ． 在 A p r i o r l 算法中 ， 所有的 候选 项 臣集为 a p r i o r i g e n 【 L ． I 而在 I UA算法中． 厶 将从c j中去掉， c 。 肯定小于 a． 显然厶 愈大， 则 I UA算法的意义血大． 实验结果表明， 当频繁项 目集 的分布在新旧最小支持度两种情况下相差不大时可以获得较高的性能加速比； 其次 ． 对于生成 对应的那部分候选 项 目集， I U A算法也优于Ap r i o r i 算法． 在 Ap r i o r i 算法中是使用 a p r l o r i g e n函数将两十鞭繁“一1 项 目集扩展成 为候选量项 目集， 它需要 一1 个连接 J o i n 条件来实现复杂的连接口 ] ． 而在 I UA算法中只需使用 i u a 一 n函数对两 个子项 目集进行 简单 的拼接 即可 - 第 3 ， 在修剪步 ． I UA 算法在生成 c f l ’ 2 ， 3 时 ， 只需对 一 单独进行检查就能实 现有效的修剪， 而对应地在 Ap r i o r i 算法中必须检查整个L 才舱确定有效的修剪， 因此， A p r i o r i 算法中修剪步的检 查范围要比I L I A算法多两倍的f 厶一 L 1 ． 即 3*l 厶一 ． I 一 1 工 L I l 一 I f 雎 I ． 当上 2 一 ． 一 和 L i 一 在单独的情 况下分别都可以装进内存， 而 厶一 ． 却不能装进内存野 ， 这一点尤其具有明显的意义． 事实上， 这时在 A p r i o r i 算法中已 经不能再做有效的修剪， 因为不能在内存中得到整个 L一 ． 在模拟实验中， 当交易数据记录增加到 1 0 0 0 0 0 0 十 ， 并 且出现 上情况时． 就得到了较高的性能加速 比． I UA算法的另外一大优点就是很容易 实现基 于共 享 内存 多处理 机结构 的并行化． 由于 目前 主要 的并行关联规则 开采算法都是基 于无共享 S h a r e d n o t h i n g 多处理机结构的 A p r i o r i 算法的井行 化_ ‘ - ． 因此 ， 对于 并行增 量式 更新算法 P l eA的性 能评价 ． 我们就留特以后进一步的工作． 4 结语 当用户交互式开采 令其真 正摩 趣 的关 联规则 时 ， 需要频繁调整最小支持度． 针 对这一问题 ， 本文提 出 了两种高 效的关联规贝 【『 更新算法 l UA和 P I UA． I l i a算法的基本思想也可用 于 D． W． C h e u n g等人所考虑 的关 联规则更新 问题． 而且对于增量式开采一般化的关联规则 G e n e r a l i z e d A s s o c i a t i o n R u l e s 或者其他类型的规则如序列模式 t S e q u e n t i a l P a t t e r n s 也是可 提供借鉴的． 目前， 我们正在将Ap r i o r i 算法、 I UA算法以及 F L I p算法集成为一个完整 的关联规则开采杀统， 并将在自行研制的数据库管理系统D M2 上实麓． 维普资讯 3 0 6 软件学报 9 卷 参考文献 1 Ag r a wa L R 4 f M i nin g a s s o c iatio n r u l e s he t we e n s e t s o f i t e ms in l a r ge da t a b a s e s ．I nP r o c e e d i ng s o f ACM S I GM OD Co nf e r e n c e o n M a a ng e m e n t o f Da t a，W a s h i n gt o n，DC t M a y 19 93 ． 2 0 7～ 2 1 6 9 Ag r a wa l R ，S r i ka nt R．Fa s t a l g o rit h ms f o r mi ni ng a s s o c i a t i o n r u l e s ．I nPr oc e e d i n gs o f t h e 2 0 t h I n t e r r mt i oa ul Co a f e r e n c e o n Ve r y La r ge Da t a ha s e s，S a n t i a g ot Chi l et S e p t e mb e r 1 9 94 4 8 7～ 4 99’ 3 Ag r a w且 I R，S r l k a n t R．F _衄t a L g o r i t hms f o r mi ni n g a s s oc i a t i o n r u l e s ．I BM Re s e a r c h Re p o r t RJ 9 8 3 9t 1 9 9 4 4 Ag r a wni R，S h a f e r J C．P a r a l l e l mi n i n g o f a s s o c i a t i o n r u l e sd e s i g n，i mp l e me n t a t i o nt a n d e xp e r i e n c e I BM Re s e ar c hRe p o r t RJ 1 0 00 4，1 9 9 9 5 Sfik a n t R，Ag r a wa l R．Mi n i n g g e ne r a l i z ed a s s o c iat i o n r u l e s．I nPr oc e e d i n g s o f t h e Zl s t I n t e r na t i o n a l Co n f e r e n c e O n Ve r y La r ge Da t a lms e s t Z ur i c hSwi t z e r l a n dSe p t e mbe r 1 9 9 4 ． 4 0 7 ～ 4 1 9 6 P a r k J S e t a 1 ．An e f f e c t i v e h * s h b a s ed a ] g o r l t h m f ormi n i ng o f a s s o c i a t i o n r ul e s ．I nP r oce e d i ng s o fACM S I GMODCo n f e r e nc e o n Ma n a g e me n t o f Da t a ， S a n J o s e ，C a l i f o r nia ， M a y 1 9 9 5 ．1 7 5 ～ 1 8 6 7 Se v a s e r e A． An e f fi c i e n t a l g o r i t h ms f or m i n i ng a s s o c i a t i o n r u l e s i n l a r g e d a t ab a s e s ．I nP r o c e e d i n gs o t h e 2 1 s t I n t e r t mt i o r ml Co n f e r e n c e o n Ve r y La r ge Da t a h a s e s，Z0 r ie h，S wl t z e r ] d．Se p t e mbe r 1 9 9 5 ． 4 3 2 ～ 4 4 4 8 Ho ut s ma M ，S wa m i A．Set o r i e n t e d mi n i n g a s s o c iat i o n r u l e s ．I nPr o c e e di ng s o f t h e 1 1 s t I n t e r r mt J o r m[ Con f e r e n c e o n Da ta En g l n e e r ingTa i pa i ，M a r c h 1 9 9 5 ． 2 5 ～ 3 3 9 Tniv o n e n H． Se mp ] i n g l a r g e d a t a b a s e sf o r a s s oc i a t i o n r ul e s ．I n}Pr oc e e d i n g s oft h e 2 2 t hIn t e r n a t i o r m] Co nf e r e n c e o nVe ry La rg e Da t a h a s e s ，B omh a y，I n d i at 1 9 99 ． 1 ～ 1 9 1 0 Ch e u n g D W e t a 1 ．Ma i n t e r m n c e o f d i s c o v e r ed s s oci a t l o n rul e s i n l a r g e d a t a lm s e s ； a n i n c r e me n tal u p d a t i ng t ech n i q u e I n P ro c e e d J n g s o f t he 1 Z t h I n t e r r mt i o n l Co t de ren c e o n Da t a Eng i ne e r i n g，Ne w Or l e a ns t Lo nis a r a t ，1 9 9 9 ．1 06 1 14 1 1 h t t p ／ ／ www． a l ma d e n ． i b m． c o mi c s ／ q u e s t ／ data／ a s s o c ． g e n ． t a r ． Z 1 9 Ag r a wa l R ，Sr i k a n tR．M i n i n g s e q ue n t ia l p a t t e r n s ．I aPr o c e e d i ng s o ft h e l i s tIn t e r n a t lon a [ Co n f e r e n c e o p t Da t aEn g d n e e r i n g， Ta i p e i ，M a r c h 1 9 9 5 ．3 ～ 1 4 I nc r e me nt a l Up da t i ng Al g or i t hms f o r M i ni ng As s o c i a t i o n Ru l e s FENG Yu c a i FENG J i a n 1 i n De p a r t me n t o Y C o m p u t e r S c i enc e Hu a z h o n g Un i * r ff t y o Y S c i e n c e a n d Te c h n o l o g y Wu h a n 4 3 0 0 7 4 Ab s t