快速开采最大频繁项目集.pdf

2 0 0 l j o u r n a l o f S o f t wa r e软 件 学 报 Vo 1 ． 1 2 ．N o ． 2 快 速 开 采 最 大频 繁 项 目集 路松 嶂，F正鼎 华 中 理工 大学 计 算 机学 院 ， 湖 北 武 汉4 3 0 0 7 4 E ma i l s o n g fl u p u b l i c ． wh ． h b ． c n h t t p ／ i s o n g f e n g l u h o mo e h i n a r n ． c o rn 摘 要 发 现 最 太频 繁 项 目集是 多种数 据 开采 应 用 中的 关键 问题． 提 出一 种快 速 开采 最 太频繁 项 目集 的 算 法 DM F I d i s c o v e r yma x ] n ] u if r e q u e n t i t e ms e t s ． 该 算 法把 自底 向上 和 自顶 向下 的搜 索策略进 行 了合 并． 通过 其 独 特 的 排 序 方 法和 有 效 的剪 枝策 略 ， 太太减 少 了慢 选 项 目集 的 生成 ， 从 而显著 地 降低 了 CP U 时间 美 键 词 数 据 开采 ； 知识 发现 ； 关联 规 刑 ； 最 太频繁 项 目集 { 最 小 支持 度 中图 法分 类 号 T P3 1 1 文 献标 识 码 A 发 现 频 繁项 目集 是 关 联 规 则 开 采 和 顺 序 模 式 开 采 等 数 据 开 采 应 用 中的 关 键 技 术 和 步 骤 ． 典 型 的 发 现 频 繁 项 目集 的 算 法 多 为 Ap r i o r i _ l 算 法 或 者 其 变 种 ， 这 些 算 法 采 用 自底 向 上 的 搜 索 方 法 ， 穷 举 每 一 个 频 繁 项 目集 ． 对 一 个 维 数 为 ， J 的 频 繁 项 目集 F， 由 于 F 的 每 个 子 集 都 是 频 繁 项 目 集 ， 这 就 意 味 着 算 法 必 须 产 生 F 所有 的 2 1个 子 集 ， 当 L 很 大 时 ， 这 将是 一 个 NP难 度 问 题 ． 计 算 项 目集 的 支 持 度 是 发 现 频 繁 项 目集 中最 耗 时 的工 作 ， 降 低 候 选 项 目 集 的 数 量 是 降 低 开 销 的 最 好 的 手 段 ， 由 于最 大 频 繁 项 目集 见 第 1 ． 1节 已经 隐 含 了所 有 频 繁 项 目集 ， 所 以 可 把 发 现 频 繁 项 目集 的 问 题 转 化 为 发 现 最 大 频 繁 项 目集 的 问 题 ． 另 外 ． 某 些 数 据 开 采应 用 例 如 发 现 最 小 主 键 等 仅 需 发 现 最 大 频 繁 项 目集 ， 而 不 必 发 现 所 有 的频 繁项 目集 ． 因 而发 现 最 大 频 繁 项 目集 对 数 据 开 采 具 有重 大 意 义 本 文 提 出一 种 快 速 发 现 最 大 频 繁 项 目集 的 算 法 DM F I d i s c o v e r y ma x i mu m f r e q u e n t i t e ms e t s ． 1相 关} 既念 ‘ l l 1关联 规则和最大 频繁 项 目集 关 联 规 则 ‘ 的 开 采 就 是 发 现 支 持 度 和 置 信 度 分 别 大 于 用 户 指 定 的 最 小 支 持 度 mi n s u p mi n i mu m s u p p o r t 和 最 小 置 信 度 mi n i mu m c o n f i d e n c e 的 规 则 ． 支 持 度 不 小 于 mi n s u p的 项 目集 叫频 繁 项 目集 f r e q u e n t i t e ms e t s ， 反 之 ， 称 为 非 频 繁 项 目集 i n f r e q u e n t i t e ms e t s ． 项 目集 中项 目的 数 量 叫 做 项 目集维 数 或 长度 ， 项 目集 x 的 支 持 度 记 作 s u p x ． 有 关项 目集 具有 如 下 性 质 性 质 1 ．如 果 x 是 频 繁 项 目集 ， 那 么 x 的 任 何 子 集 都 是 频 繁 项 目集 ． 性 质 2 ．如 果 x 是 非 频 繁 项 目集 ， 那 么 x 的 任 何 超 集都 是 非 频 繁 项 目集 ． 如 果 频 繁 项 目集 F 的所 有 超 集 都 是 非 频 繁 项 目集 ， 那 么 称 F 为 最 大频 繁 项 目集 ， 所 有 F 的 集 台 称 为最 大 频 繁 项 目集 台 ， 记 作 MF S ma x i mu m f r e q u e n t s e t s ． 显 然 ， 任 何 频 繁 项 目集 都 是 最 大 频 繁 项 目集 的 子 集 ， 所 以 ． 发 现 所 有 频 繁 项 目集 的 问 题 可 以转 化 为 发 现 所有 最 大 频 繁 项 目集 的 问 题 ． 收 稿 日期 1 9 9 9 0 7 3 0 {修 改 日 期 1 9 9 9 1 2 - 0 8 基 金 疆 目 国家 “ 九 五 ” 国 防 顶研 基 盘 资 助 项 目 作者 简介 路拴 ■ 1 9 6 8 一 ， 男 一 河 南巩 义 ． 博 士生 一 师， 主要 研 究钡域 为数 据 开采 ； 卢正 鼎 1 9 4 5 一 男 ， 湖北 武 汉 ， 教 授 ， 博 士生导 师 ． 主要 研究 领域 为数据 库 ， 软件 复用 维普资讯 2 9 4 d o u r n a t o fSo j l z a r e软 件 学报2 0 0 1 ， 1 2 [ 2 1 ． 2集合枚 举树 用 如 图 1所 示 的 集 台 枚 举 树来 描 述 项 目集 ． 可 方 便 地 枚 举 所 有 可 能 的 项 目组 台 ， 从 而 数 据 开 采过程 可 转 化为 集合 枚举树 的搜索 过程． 图 1表示 D { ， 6 ， r ， d} 的完全项 目集台 枚 举树． 树 的 每 个 结 点 由两 个 项 目集 来 表 示 ． 第 1个 项 目集 叫 首 h e a d ． 记 作 h ， 由树 当前 结 点 的 枚 举 项 目 集表 示 第 2个 项 目集 叫尾 t a i l ， 记 作 t ， 由 当 前 结 点 的 子 结 点 的 所 有 项 目 除去 当 前 结 点 所 包 含 的项 目后 排序 组 成 ． 例 如 ． 对 结 点 口， h a 一 { dl ， t 口 一 { b ． f ． d} ． 把 结 点 的父 结 点 记 作 ， 子 结 点 记 作 ． 的 生成 方 法是 h n j 一 U{ i ， i ∈t n ； 1 J l J ∈t ． j i ． 例 如 一 结 点 d有 3个 子结 点 a b ． 4 c和 a d， 对 结 点 a L “ 有 h Ⅱ c 一h U { f ⋯ ， f ， a c 一 { d ． f } 一 一 一一 一一一 一 一 l } a c ,d e ． d { } 、 c } { ． ，、 ～ 、、 、＼ 、 ‘ 吐 、 ’0 b ’ d ’ 固 辞 最 、 ～ 、 l a, 6 ， } { ， 6 ， { ， f ， ， ， { n ， 6， f 一 F i g , 1 Co mp l e t e 廿】 u r r H a t i o n t r e e f o r 4 d i me n s i o n i t e ms e t D一 ‘ d 一 ， f ， 图1 4 维项 目集 台 D一{ R ， 完全 枚举 树 另 外 ， 我 们 约 定 在 进 行 第 次 搜 索 时 ， 所 生 成 的 『王一 候 选 项 目集 日可 以表 示 为 U以 ， 其 中 A 为 A 的前 矗个元 素 ， A 为 A 的后 L～ 个元 素 ， 为 且 的维数． 2 发 现 最 大 频 繁 项 目集 的 算 法 DMF 1 2 ． 1 剪枝 策略 为 了减 少 生 成 不 必 要 的 项 目集 ， 发 现 频 繁 项 目集 的算 法 都 利 用 性 质 1或 性 质 2来 减 少 候 选 项 目集 的 数 量 ． 自底 向上 的搜 索 方 法 只 能 利 用 性 质 2 ， 自顶 向下 的搜 索 方 法 只 能 利 用 性 质 1 ． 为 了加 速 搜索进程 ． DMF I 算 法采用 自底 向上 和 自顶 向下相结台 的搜索策 略 ， 利 用每 个搜 索 方 向搜索 到 的信 息 对 集 台 枚 举 树 进 行 剪 枝 ． 在 DM F I算 法 中 ， 我 们 设 置 了两 个 数组 MF C S ma x i mu m { r e q u e n t c a n d i d a t e s e t s 和 C c a n d i d a t e S e t s ， 分 别用 以 保存 自顶 向下方 向和 自底 向上方 向上 生成 的候 选 项 目集． 在进行 第 矗遍搜 索 时 ， C 中每个项 目集的维数 为 矗 ．而 MF C S包含枚 举树 第 矗层 中所有结点 首项 目集 的最长 的超 集 ， 例 如 在 图 1中 ， 当 丘 2 l时 ． 4个 结 点 ， b ， C和 的 首 项 目集 所 对 应 的最 长 超 集 分 别 为 f 口． 6 ， c ． d} ． { 6， c． d ． { f， d 和 dj ， 此 时 ． MFCS一 a， b， f， d} ， { b ， C， d} ， { “d} ， { d} } ． 如 果 在 自顶 向 下 的 方 向 上发 现 某 个 频 繁 项 目集 F， 由 于 F 的 所 有 子 集 都 是 频 繁 项 目集 ， 且 都 不 可 能 是 最 大 频 繁 项 目集 ， 从 而可 把 C 中是 F 子 集 的 元 素 剪 掉 ． 反 之 ， 如 果 在 自底 向 上 的 方 向 上 发 现 某 个 非 频 繁 项 目集 ， 由性 质 2可 知 它 所 有 的 超 集 都 是 非 频 繁 项 目集 ， 从 而 可 以 对 MF C S进 行 剪 枝 ． 由 于第 一 1次 的 MF CS是 由第 次 的 MF C S所 生 成 见 第 2 ． 2节 ， 所 以 对 MF C S剪 枝 时 不 能 简 单 地利 用 性 质 2 ． 例 如 ， 如 果 } ∈C 是 非 频 繁 项 目集 ， 若 MF C S一 1 J ， b ． f ， d} ． 虽 然 ＆ ， 6 ．d』 是 非 频 繁 项 目集 ． 但 它 的 子 集 不 一 定 是 非 频 繁 项 目集 ， 因 而 不 可 简 单 地 把 { ． ， ， d} 剪 掉 ． C 对 MF C S 的剪 枝 方 法 如 下 如 果 在 第 遍 搜 索 时 ． 项 目集 A∈ 为 非 频 繁 项 目集 ， A 1 n ． d ⋯ ． ， a } A U ； 对 于任 一 m∈MF C S， m m Um 1 L ， m 2 ⋯ ． ， l U { m j U ， 由 C 的 生 成方法 见第 2 ， 2节 可 知 ， 一 定存在某些 m∈MF C S， 使得 ． m ⋯ ． ， m一 ， 并且 { m } U 维普资讯 路 松 峰 等 快速 开 采最 太 蝴繁 项 目集 2 9 j m ] { a } ． 把 n 从 m U 中 去 掉 即 可 ． 2 ． 2候 选 项 目集 的 生 成 可 由 M F C S中 的非 频 繁 项 目集 生 成 ， 一 { 卅 U { i 1 f 卅∈M F C S． i ∈卅 ， s u p 卅 i ． 2 ． 3排 序 第 略 项 目集 的支持 度越高 ， 就越 有 可能是 最 大频 繁项 目集 的一部 分 ， 所 以在生成 新 的 MF C S之前 ， 要 对 原 有 的 MF C S 中元 素 m 的 尾 部 m 重 新 排 序 ， 以 便 使 支 持 度 较 高 的 子 项 目集 出 现 在 更 多 的 新 项 目集 中 ， 这 对尽 早 发 现 最 大频 繁 项 目集 有 重 要 意 义 ． 对 每 一 个 m∈M F C S， m 应 按 照 s u p m U { i J 的 大 小 来 排 序 ， 其 中 i ∈卅 ． 例 如 ， 卅一 { a ， b ， c ， d， ∈MF C S， 一 2 ， 卅 一 { Ⅱ ， 6 ， 卅 一 i c ， d， P } ， 如 果 s u p Ⅱ， 6 ． c } s u p { 日， ， d s u p { 口， 6 ， P } ， 则 1 口， 6 ， c } 更 可 能 是 最 大 频 繁 项 目集 的 一 部 分 ， 所 以应 当使 { 日 ， 6 ， c 尽 可 能 多 地 出现 在 新 的 M F CS中 ， 对 卅 重 新 排 序 后 卅 一 { e ， d， c } ， 从 而 卅 变 为 { Ⅱ， 6 ， ， d， c ． 则 新 生 成 的 项 目集 为 { a ， 6 ， e ， d， c } ， { a ， 6 ， d， c f 和 1 n， b ， t - ． 另 外 ， 应 当对 M F C S的 元 素按 项 目集 的维 数 进 行 排 序 ， 其 原 因是 ， 根 据 性 质 1 ， 按 我 们 的排 序 策 略 ， 任 何 项 目集 的子 集 一 定 在 该 项 目集 之 后 出 现 ， 这 样 ， 当 发 现 某 个 项 目集 为 频 繁 项 目集 时 ， 由 于 其 子 集 不 可 能 是 最 大 频 繁 项 目集 ， 因 而 不 必 计 算 其 子 集 的 支 持 度 ， 直 接从 M F CS 中把 其 子 集 删 除 即 可 ， 这 样 可 以 降 低 I ／ 0 和 C P U 时 间 ． 2 ． 4 DMF 1算 法 D M F I算 法 按 宽 度 优 先 的 方 法 对 集 台 枚 举 树 进 行 双 向 搜 索 ． MF S用 来 保 存 最 大 频 繁 项 目 集 ， 算 法 描 述 如 下 1 k 0 ， C 。 一 { } ， MF CS { 1 ． 2 ⋯ 圳} ， MF S { } ／ ／ 假设 项 目交易 集合 f 1 ， 2 ⋯ ． ， 2 d o 3 d e l e t e i f r o m wh e r e m Um a n d ∈MF CS a n d s u p m U ， 这 与 已知 条 件 矛 盾 ， 所 以最 多 只 需 搜 索 遍 ． 维普资讯 J o u r n a l S o f t wa r e软 件 学报2 0 0 1 ， 1 2 2 其 他计算最 大频 繁项 目集 的算 法有 Ma x Mi n e r 和 P i n c e r S e a r c h 。 ． Ma x Mi n e r突 破 了传 统 的 自底 向上 的搜 索策略 ， 尽可能早 地对项 目集 进行 了剪 枝． 其缺 陷是 ① 未利用 自顶 向下 的信息进 行剪枝 ； ② 未对 MF CS进 行适 当 的排序 ， 产生 了多余 的候选项 目集 ； ③ 在第 k次搜 索时 ， 由 DMF I 可知 ， 维数不大 于 的项 E 1 集 一定是频 繁项 目集 ， 不必计 算它们 ， 但 Ma x Mi n e r将计 算这些 项 目集 的 支 持 度 ． P i n c e r S e a r c h采 用 了 自底 向 上 和 自顶 向 下 的 双 向搜 索 策 略 ， 但 其 第 k次 的 MF C S是 由 k ～ 1 次 的 MF C S 中的 非 频 繁 项 目集 去 掉 一 个 元 素 来 生 成 ， 产 生 了过 多 的 无 用 候 选 项 目集 ， 其 G 的 生 成 采 用 类 似 于 Ap r i o r i 生 成 候 选 项 目集 的方 法 ， 对海 量 数 据 库 来 讲 ， 将 陷 人 NP难 度 的 陷 阱 ． 我 们 用 P o we r b u i l d e r在 6 4 M 内存 、 CP U 为 P e n t i u m t l [ 4 5 0 M 的联 想 奔 月 2 0 0 0机 器 上 实 现 了 D M F I ， Ma x ． 一 M i n e r和 P i n c e r S e a r c h算 法 ． 我 们 利 用 h t t p ／ i www． i c s ． u c i ． e d u ／ ～m| e a r n ／ M L S u m ma r y ． h t ml 上 所 提 供 的 蘑 菇 数 据 库 mu s h r o o m d a t a b a s e 来 进 行 实 验 ， 该 数 据 库 有 8 1 2 4条 记 录 ， 记 录 了蘑 菇 的 2 3种 属 性 ， 每 种属 性 有 2 ～ 1 2个 枚 举 值 ． 图 2 a 显 示 了不 同 的 最 小 支 持 度 分 为 5 档 2 0 ， 1 0 ， 5 ， 2 ， 1 下 算法 的性 能 变 化 ， 实验 结 果 表 明 ， 最 小 支 持 度 越 低 候 选 项 目集 将 越 多 ， CP U 耗 费 时 间越 多 ； 同 时我 们 看 到 ， DMF I 算 法 的 执 行 时 间 比其 他 两 种算 法 要 少 ． 图 2 b 显 示 了在 不 同 的最 小 支 持度 分 为 5挡 4 0 ． 2 0 ， 】 0 ． 5 ， 2 下 算 法 要 计 算 的 项 目 集 的 数 量 ， 可 以 看 出 ， DM F I 算 法 计 算 的 项 目集 将 更 少 ． 为 了 显 示 在 不 同数 据 量 下 算 法 的 扩 展 性 ， 我 们 随 机 从 范 例 数 据 库 中抽 取 了 4个 不 同 的记 录 数 1 0 0 0 ， 2 0 0 0 ， 4 0 0 0和 8 0 0 0 j 进 行 测 试 ， 固 定 最 小 支 持 度 为 2 ， 结 果 如 图 2 c 所 示 ， 因 为 DMF I算 法 计 算 较 少 的项 目集 ， 因 而 具 有 更 好 的 扩 展 性 ， E x e c u t i 6 n t l me【 s Nu mb e r o f i t e ms s f K1 ∞ 5 0 4 0 3 0 2 O 1 0 0 2 0 1 0 5 2 1 f 盯 n u 仃 I s u P P o 誊 ％， a EX e C u E L 0 n t i me o f al g or i l hms f a 算 法 的 抽 行 时 间 4小结 0 5 2 1 0 5 0 2 0 4 0 2 0 1 0 5 2 Mi l l imu m s u p p o r t f ％ bN u m b e r Of L ⋯ c L s of a [ g or kh ms b J算 法计 算 的项 目集触 【 cSc a [ a b i [ i l y o f a l go r i t hm s c 算 法 的 扩 展 性 一曰 一 P i n c e r - S e a r c h 1自 M a x - M i n e r 日 一DM FI 执行 时间 秒 ， 圆最 小 支持 度 ． ③ 项 目集 数 千 t 记录 数 千 ． Fi g．2 图 2 本 文 提 出 了一 种 有 效 的 快 速 发 现 最 大 频 繁 项 目集 的算 法 DMFI ， 有 效 地 把 自底 向上 和 自顶 向 下 的 搜 索 策 略 进 行 了 合 并 ． 理 论 和 实 验 结 果 表 明 ． 相 对 于其 他 发 现 频 繁 项 目集 的 算 法 ， D M F I具 有 更 优越 的性 能 ． DMF I为 海 量 数 据 库 发 现 频 繁 项 目集 和 仅 需 发 现 最 大 频 繁项 目集 的数 据 开 采 应 用 提 供 了一 种 有 效 而 快 速 的算 法 ． Re f e r e nc e s 1 ]Ag r a wa 1 ．R．，S r t k a n t ，R．F a s t a l g o r i t h msf o r mi n i n g a s s o c ia t i o n r u l e s I nB o c c a， J ． B ． ．J a r k e ．M．Za n i o l o．c ．e d s 维普资讯 路拙 峰 等 快速 开 采 最太频 繁 项 目桌 2 9 7 [ 2 [ 3 ] 4 Pr o c d Es。 f t he 2 0t h I nt e r n a t lon a ]Con f e r e n c e o n Ver y La r ge Da * a b a s e s S a n Fr a n c i s c oM o r g a n Ka u f m a nn Pub l i s he r s一 1 9 9 4 48 7～ d 99 Ag r a w a l ，R．．Sr l k a nt ，R． M i ni n g s e q ue nt i a l p a t t e r ns ． i nY uP S．．Che n，A． L． P．，e d s Pr o c e e d i n gs。ft h e ll t h I n t e r n at i o na l Co n f e r e n c e o n Da t a En gi a e e r l n g Lo s A a m i t os ，CA I EEE Co m p u t e r So c i e t y一1 9 9 5 3 ～ 1 4 Ba y a r d o．R EI f l c ie nt l y r u i ni n g l o ng p a t t e r n s f r om d a t a b a s e s ． i nHa a sI ． M，T iwa r y，A．e ds Pr o c e e d i ng s o 1“t h e ACM S1 GM OD I nt e r n a t i o n a 】Con [ e r e n c e o n M an a ge me n t of Da t a Ne w Yo r kACN I Pr e s s，I 9 9 8 8 j ～ 9 3 Li n．Da o I，Ke d e t u，Z M ． Pi n c e r Se a r c h w a l g or i t hm [ o r d i s c o v e r i ng t he ma x i mu m r e q u e nt s e t ． I n Sc h e k，H．J ， Sa ] t or ．F．．Ra mos．I ．，e t a l ，e d s Pr oc e e di n gs o ft h e 6 t h Eur o p e a n Con f e r e n c e o n Ext e n d i n g Da t a b a s eTe c h no l og y He l d e l b e r gSp r ing e r Ve r ] a g，1 99 8 1 05 ～ 1 1 9 Fa s t M i ni ng M a x i m um Fr e que nt I t e m s e t s’ LU S o n g f e n g，LU Zh e n g d i ng Co e g e o fC o mp u r s ⋯ d Te c h n o l o g yt l -t z a o r e gUm s i t y S c u c e d 7 “e c h n Jo g y-l P u h n 4 3 0 0 7 4 t C A i n ． E ma i l s o n g f l u p u b l i c wh h b c n ht t pi ．／ ,, s o n gf en g l u ． ho m e c hl n a r e n e om Ab s t r a c t Di s c ov e r i n g ma xi m u m f r e q ue n t i t e m s e t s i s a ke y p r o bl e m i n m a ny d a t a m i n i n g a p p l i c a t i on s ． I n t hi s p a p e r ．t h e DM FI d i s c o v e r y m a xi mum f r e q ue n t i t c h ] s e t s a [ g o r [ t hm whi c h c o m b i n e s t h e b o t t o m u p a n d t o p d o w n s e a r c h e s i s p r o p o s e d t o s o l v e t h L s p r o bt e m． U s i n g t h e u n i q ue o r d e r i n g me t h o d a n d e f f i c i e n t p r u n i n g s t r a t e g y，t he nu m b e r o f c a n d i d a t e i t e ms e t s i s g r e a t l y d e c r e a s e d，t h e r e f o r e CPU t i m e i s r e d u c e d r e m a r k a b l y ． Ke y wo r d sd a t a m i n i ng；k n o wl e d g e d i s c o v e r y；a s s o c i a t i o n r u l e；m t x i m u n ]f r e q u e n t i t e m s e t ；mi n i m u m s u p p o r t Re c e i ve d J u l y 3 O，1 9 9 9a c c e p t e d De c e mb e r 8，1 9 99 Su pp o r t e d b y t he De e nc e Pr e Re s e a r c h P r o j t。 f t h e Na t i o na l 维普资讯