D0I:10.13374/i.issm1001053x.2003.01.023 第25卷第1期 北京科技大学学报 Vol.25 No.1 2003年2月 Journal of University of Science and Technology Beijing Feb.2003 基于数据立方体的维内关联规则挖掘算法 杨学兵”蔡庆生” 1)安徽工业大学计算机科学系，马鞍山2430022)中国科技大学计算机科学系，合肥230027 摘要针对数据立方体的结构特点，结合联机分析处理技术，提出了两种基于数据立方体 的维内关联规则挖掘算法.以合肥农河超市实际数据作为测试数据，给出了两种算法的实验 结果，结果表明，两种算法在不同支持度情况下执行效率存在明显差异，分别适合在高支持 度和低支持度情况下进行关联规则挖掘. 关键词知识发现；数据挖掘：关联规则：数据仓库；数据立方体；多维分析 分类号TP311;TP132.3 数据库中知识发现(Knowledge Discovery in 形如：A八A2N…AA,一BAB2A…AB(4%,70%)意味 Databases,简称KDD)是目前人工智能和数据库相 着目标数据中客体B,B,,B,倾向于同客体 交叉的一个热门研究领域，已经受到越来越多的 A,A,…,A,一起出现.其中4%为关联规则的支持 关注I.数据挖掘(Data Mining,简称DM)是KDD 度，70%为关联规则的信任度 的一个十分重要的步骤，其内容涉及各种知识模 1.2 Apriori性质 式的提取算法.关联规则是数据库中存在的一 Apriori算法"采用的是迭代方法，需要多遍 种知识模式，其挖掘算法已得到了广泛的重视， 扫描事务数据库，为了提高频繁项目集的产生效 并取得了较大的进展.数据仓库技术(Data Ware- 率，可利用一个重要的Apriori性质来减少项目搜 house Techniques)、联机分析处理(Online Analy- 索空间. tical Processing,简称OLAP)和多维数据立方体 定理l(Apriori性质)一个频繁项目集的所 (Muti-Dimensional Data Cube)等也是近年来涌现 有非空子集必需也是频繁项目集®.这一性质是 出的一些更有效地对数据进行组织、存贮：、分析 由Agrawal和Srikant提出并得以证明的. 和处理的新方法川.维内关联规则是指在数据立 根据这一性质，进行第k次扫描之前，可先 方体中同一属性维内各项目之间存在的关联规 产生候选集C.C可以分两步来产生，设前一次 则，通过对传统关联规则挖掘算法进行改进，给 (第k-1次)已生成k频繁集L,则首先可以通过 出基于数据立方体的多维关联规则挖掘算法.由 对L,中的成员进行联接来产生候选，L-中的两 于现有的OLAP技术已容许构建数据立方体，且 个成员必需满足在两个成员的项目中有k一2个 数据立方体内已有各项目出现次数的统计，因 项目是相同的这个条件方可联接，即： 此可通过读取其统计数据来确定频繁项目集，使 .L-eL-1=(40B4,BCL-1,AOBI=k-2) 挖掘过程效率大大提高. 接着再从C中删除所有包含不是频繁的 (k一1)子集的成员项目集即可 1相关概念 13数据立方体 1.1关联规则 数据立方体是指含有多维属性的统计实体， 关联规则概念首先由Agrawal等提出s.所谓 设为n维，每维共有d,+1个值，其中d是指第i维 关联规则，是指客体之间的相互关系.关联规则 中互不相同的属性值，每维中再加上一个"Ay" 值，共d+1个不同值 收稿日期20010104杨学兵男.35岁，副数授 假设存在一个n维空间，则由每一维中各取 *国家自然科学基金项目资助(N0.60075015)和安徽省教育 一个具体的属性值，则可对应一个n维空间中的 厅科研经费资助(No.2002KJ046)第 卷 第 期 年 月 北 京 科 技 大 学 学 报 饱 。 基于数据立方体的维 内关联规则挖掘算法 杨 学兵 ” 蔡庆 生 ， 安徽 工业 大学 计算机科学 系 ， 马 鞍 山 中国科技大学计算机科学 系 ， 合肥 摘 要 针 对 数据立 方体的结构特点 ， 结合联 机分析处 理技术 ， 提 出 了两 种 基于 数 据立 方体 的维 内关联 规则挖掘算法 以 合肥农 河超 市 实 际数据作为测试数据 ， 给出 了两种 算法 的实验 结果 结果 表 明 ， 两种算法在不 同支持度 情况 下 执 行 效率存在 明显 差 异 ， 分别适 合在高支持 度 和 低 支 持度 情况下 进行关联 规则挖掘 关键词 知识发现 数据 挖 掘 关联 规则 数据 仓库 数 据 立 方体 多维分析 分 类号 数据 库 中知 识 发 现 叮 ， 简称 是 目前人 工 智能和数据库相 交叉 的一 个热 门研究 领域 ， 已 经 受 到越来 越 多 的 关 注 ‘， 数据挖 掘 ， 简 称 是 的一 个 十分重 要 的步骤 ， 其 内容 涉及各种 知识模 式 的提 取算法 ’ 、 关联 规 则 是 数 据库 中存 在 的一 种 知识模 式 ， 其挖掘算 法 已 得 到 了广 泛 的重 视 ， 并取 得 了较 大 的进 展 数据仓库技 术 认 叫 、 联 机 分析处理 · ， 简称 和 多维 数据 立 方 体 一 等也 是 近 年来 涌 现 出的一 些 更 有 效地 对数据 进 行 组 织 、 存贮 、 分析 和 处 理 的新 方 法 ’ 维 内关联 规 则 是 指 在 数据 立 方 体 中同一 属 性 维 内各 项 目之 间存 在 的关 联 规 则 ， 通 过 对传统 关联 规则 挖 掘算法 进 行 改 进 ， 给 出基 于数据 立 方体 的 多维关联规则挖 掘算法 由 于 现 有 的 技 术 已 容许构 建 数 据 立 方体 ， 且 数据 立 方 体 内 已 有 各项 目出现 次 数 的统 计 “ ，， 因 此 可通 过 读取其统计数据来确 定 频 繁项 目集 ， 使 挖 掘 过 程 效 率 大大提 高 相 关 概 念 关 联 规 则 关联 规则 概 念 首 先 由 等提 出 下 所 谓 关联 规 则 ， 是 指 客 体之 间 的相 互 关 系 关联 规 则 收稿 日期 一 刁 杨学兵 男 ， 岁 ， 副教授 国家 自然科学基金项 目资助 和安徽 省教育 厅 科研经 费资助 形 如 八 二 法一 八 … ， ， 意 味 着 目 标 数 据 中 客 体，刀，’ ， 倾 向 于 同 客 体 】 ， 瓜 ， … ，法一 起 出现 其 中 为关联 规则 的支持 度 ， 为关联 规则 的信 任度 性 质 算法 ’ 采 用 的是 迭 代方 法 ， 需 要 多 遍 扫描事务 数据库 为 了提 高频 繁项 目集 的产 生 效 率 ， 可利 用 一 个 重 要 的 。 汁胜质来 减 少 项 目搜 索 空 间 定 理 性 质 一 个频 繁项 目集 的所 有非 空 子 集 必需 也 是 频 繁项 目集 〔 ， 这 一 性 质 是 由 和 提 出并得 以 证 明 的 根 据 这 一 性 质 ， 进 行第 次 扫 描 之 前 ， 可 先 产 生 候选 集 可 以 分 两 步 来 产 生 ， 设 前 一 次 第 一 次 已 生 成 频 繁集 ， 则 首先可 以 通 过 对 一 、 中的成 员 进 行 联 接 来 产 生候选 ，及 一 ，中的两 个 成 员 必 需 满 足 在 两 个 成 员 的 项 目 中有 一 个 项 目是 相 同 的这 个 条件方 可 联 接 ， 即 · 一 及一 阵方 及 一 ，，冈 川 一 ‘ 接 着 再 从 中 删 除 所 有 包 含 不 是 频 繁 的 一 子集 的成员 项 目集 即可 数 据 立 方体 数据 立 方 体是 指 含 有 多维 属 性 的统计 实 体 ， 设 为 维 ， 每维共 有 圆 个值 ， 其 中圆是指第 维 中互 不 相 同 的属 性 值 ， 每维 中再加 上 一 个 ” ” 值 ， 共 个不 同值， 假设存在 一 个 维 空 间 ， 则 由每一 维 中各取 一 个具体 的 属性值 ， 则可 对 应 一 个 维 空 间 中的 DOI ：10．13374／j ．issn1001－053x．2003．01．023