基于数据立方体的维内关联规则挖掘算法

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

·84 北京科技大学学报 2003年第1期 点，这个点称为方格.每个方格内存贮了与其对 itemset的候选集C,及l-itemset频繁集L,k=k+l. 应的各属性的值同时出现的次数，用count表示. 步骤3，重复利用频繁Lk-,生成中k-itemset候选集 三维数据立方体如图1所示. Ck,再利用C.生成k-itemsets频繁集Lk,直至L=O. (I)利用L产生候选集C的子过程. 输人：Lk Any 62 35 97 输出：C Carry Bag 30 20 50 步骤1，先置C=O.步骤2，利用Apriori性质， Any Tents 32 15 47 West 重复对L-,中的长度为k-2且有k-3个项目相同 ation Clood Poor Any South 的频繁集进行两两连接，连接结果加入Ck. Profit (2)利用候选集C产生频繁集L的子过程. 图1数据立方体示意图 输入：kC Fig.1 Sketch map of the data cube 输出：L. 2算法描述 步骤1，先置L=O.步骤2，重复对候选集C 中的每个候选，通过OLAP引擎取得其对应的计 维内关联规则是指在一个维内存在的关联 数值，检查其是否满足最小支持度.若满足，则加 规则，这个维称为项目维周.项目维内的项目通过 人L 另外一个维来分组，形成一个个的事务，这另外 (3)算法分析. 的一个维称为事务维.因此，维内关联规则涉及 算法的第一部分通过利用Apriori性质，即对 到两个维.于是可以通过OLAP引擎创建一个两 每两个(k-1)-itemset频繁项目集，若其有(k-2)个 维的数据立方体作为工作数据立方体，以便用来 共同项目，则可对这两个项目集进行连接作为一 进行数据挖掘.下面以一个例子来说明. 个k-itemset,再通过判断此k-itemset的每个子集是 例：用Sales数据库中Location作为事务维， 否均为频繁项目集以确定其候选身份.如果任一 Product作为项目维，则相应的二维数据立方体如 子集不为频繁项目集，则此k-itemset就不能作为 图2所示.根据立方体的定义，每一个格子保存 候选项目集.测试子集的次数可由 了从原始关系中产生的计数(count)值 2-6Ls-×k-2》 (1) Any 70 ■185 175 70 500■ 来计算，其中n是可能的最多候选项目集数量， Alert devices 20 20 40 Lk-,eLt-,是指由(k-l)-itemset产生的k-itemset的数 Carry-bags 10 100 110 220 量.因为相连接的两个(k-l)-itemset本身是频繁 Sport wea 20 60 40 的，因此在检查时，只需对除此两个之外的其他 Tents 45 (k-2)个(k-1)子集检查即可. Water purifiers 20 25 30 75 算法的第二部分主要是扫描数据立方体，扫 Tokyo Seattle Mexic Hong Kong Any 描的循环次数取决于计算每个候选的支持度时 Location 所涉及到的方格数量，具体可通过 图2一个用于挖掘维内关联规则的数据立方体 Fig.2 An example of the 2-dimensional data cube (Ck-transactions) (2) 1 来计算，其中C是候选集C中候选的个数， 基于这一立方体的维内关联规则挖掘的算 世ransactions是数据立方体中事务的数量 法过程与Apriori算法十分相似，所不同的是对每 根据式(1)和(2)，此算法的时间复杂度可大 一候选项目集的支持度计算是通过对数据立方 略地分为两个部分：检查子集是否频繁和扫描数 体的一部分进行扫描，而不是对事务数据库中的 据立方体.对于一个固定的最小支持度，上面两 事务表.下面给出这一算法的描述 个公式中的可变部分只有三个，即忆k-日L,C 2.1由Apriori改进的维内频繁集生成算法（算法1） 和n,而影响这几个值的主要因素取决于数据立 输入：一个二维数据立方体Cube[transactios, 方体的事务维和项目维的大小，两者越大，耗时 items].最小支持度min_supp 越多 输出：维内频繁项目L 另一个基于数据立方体的维内关联规则挖 步骤1，初始化，置k=1,L=O.步骤2，生成1-

北 京 科 技 大 学 学 报 年 第 期 点 ， 这 个 点称 为方 格 每个方格 内存贮 了与其对 应 的各属 性 的值 同时 出现 的次数 ， 用 。 表示 三 维 数据立 方体如 图 所示 屡 ” “ 蒙翼翼 翼薰霎 刀 矍 介 瓦不七磊一骂犷 图 数据立 方体示意图 · 算法 描述 维 内关联规 则 是 指 在 一 个维 内存 在 的关联 规则 ， 这个维称为项 目维‘川 项 目维 内的项 目通 过 另外一 个维来分组 ， 形 成一 个个 的事务 ， 这另外 的一 个 维称 为事务维 因此 ， 维 内关联 规则 涉及 到两 个维 于 是 可 以通 过 引擎创 建一 个 两 维 的数据立方体作为工作数据立方体 ， 以便用 来 进 行数据挖掘 下 面 以 一 个例子来说 明 例 用 数据库 中 作为事务 维 ， 作为项 目维 ， 则 相 应 的二维数据立方体如 图 所示 根 据立 方体的定 义 ， 每一 个格子保存 了从原始关系 中产生 的计数 值 的候选 集 及 卜讹 频繁集乙 ， 步骤 ， 重 复利用 频繁几 一 生 成 中 候选 集 ，再利 用 生 成 频 繁集 ，直 至 户必 利 用及 一 ，产生 候选 集 的子过程 输人 一 ， · 输 出 步骤 ， 先置 步骤 ， 利用 州 性质 ， 重 复对 一 ， 中 的长 度 为 一 且 有 一 个项 目相 同 的频 繁集进行 两 两 连 接 ， 连 接结果 加人 利用 候选 集 产生 频繁集 的子 过程 输入 ， 输 出 步骤 ， 先置 产 步骤 ， 重 复对候选集 中的每个候选 ， 通 过 引擎 取得其对应 的计 数值 ， 检查其是否满 足最小支持度 若满足 ， 则加 入 ‘ 算法 分析 算法 的第一 部分通 过利用 性 质 ， 即对 每 两个 一 频 繁项 目集 ， 若其有 一 个 共 同项 目 ， 则 可 对这两个项 目集进行连接作为一 个 ， 再通 过判 断此 的每个子集是 否均为频繁项 目集以确定其候选 身份 如果任一 子集不 为频 繁项 目集 ， 则 此不 就不 能作 为 候选 项 目集 测试 子集 的次数 可 由 艺 卜 卜 卜 一 一 图 一 个用 于挖掘维 内关联规则 的数据立 方体 一 加 基 于 这 一 立 方 体 的维 内关联 规 则 挖 掘 的算 法 过程 与 算 法 十分相 似 ， 所不 同的是对每 一 候 选 项 目集 的支 持度 计算是通 过 对数据立 方 体 的一 部分进 行扫描 ， 而不是对事务数据库 中的 事务表 下 面 给 出这 一算法 的描 述 由 改进的维 内频繁集生成算法 算法 输人 一 个二 维 数据立 方体 ， 最 小 支持度 林 输 出 维 内频 繁项 目 步骤 ， 初 始化 ， 置 ， 步骤 ， 生 成 来 计算 ， 其 中 是可 能 的最 多候 选 项 目集 数量 ， 及 一 及 一 ，是 指 由 一 卜 产 生 的 的数 量 因为相连 接 的两 个 一 一 本身是频繁 的 ， 因此 在 检查 时 ， 只需 对 除此 两 个 之外 的其他 一 个 一 子 集检查 即可 算法 的第二部分 主要 是 扫描数据立 方体 ， 扫 描 的循 环 次数取决 于计算每个候选 的 支持度 时 所涉及到 的方格 数量 ， 具体可 通 过 卜 艺 】 卜 ’ 来计算 ， 其 中 是候选 集 中候选 的个数 ， 是数据立 方体 中事 务 的数量 根 据式 和 ， 此算法 的时 间复杂度可 大 略地分为两个部分 检查 子集是 否频繁和扫描数 据立 方体 对于一个 固定 的最小 支持度 ， 上 面两 个公式 中的可 变部分 只有 三 个 ， 即 陈一 及一 ， 和 而影 响这 几个值 的主要 因素取 决于数据 立 方体 的事务维 和项 目维 的大小 ， 两 者 越 大 ， 耗时 越 多 另 一 个 基 于 数 据立 方 体 的维 内关联 规则 挖

Vol.25 No.1 杨学兵等：基于数据立方体的维内关联规则挖掘算法 ·85· 掘算法是通过对文献[10]中提出的算法进行改进 集，它不同于算法1.算法1每次扫描时只处理一 得来的，算法仅需两次扫描数据立方体 种长度的项目集，而算法2在一次扫描时需处理 2.2新的维内频繁集生成算法（算法2） 多种长度的项目集，算法2在处理每个事务时， 输人：数据立方体C(transactions,items),C中事 也用到了Apriori性质，这样就避免了对所有长度 务维中事务已按顺序编号，ISC=☑ 的项目进行处理，而只处理那些最有可能成为频 输出：频繁项目集ISC 繁集的项目.很显然，单次扫描，其耗时是多于算 步骤1，执行PHASE I;步骤2，执行PHASEⅡ； 法1，但由于算法1需扫描二维立方体以处理多 步骤3，输出SC 种长度的项目集，其总耗时会随着扫描次数的增 其中子过程如下： 加而迅速增加.算法2的第二次扫描仅仅是求精 (I)PHASE I(第一次扫描). 频繁集，因此第二次扫描耗时比第一次扫描耗时 输人：数据立方体C(transactions,items),C中 要少 事务维各事务依次编号，总事务数为n.Min sup pot为用户给定的最低支持度， 实验 输出：可能频繁集1SC 步骤1，初始化.ISC-),curr trans-0;步骤2， 实验在P2机器上进行，操作系统是Windows 对二维立方体中count>0(通过OLAP引擎得到)的 98,数据库采用SQL Server7.0数据库，算法用C+ 每个事务T进行以下操作 +Builder5.0来实现，被测数据是合肥市农河超市 ①增加计数.对所有属于SC的T的子集，其 的实际营业数据，以购买的商品名称作为项目 在ISC中的对应count+-. 维，购买序号作为事务维，具体见表1. ②插人新结点.对所有不属于ISC的T的子 算法1和2对Sales挖掘结果的比较如图3所 集1，若t的所有子集t均在ISC中，则将t加人ISC 示.表2为两算法执行的具体结果数据 中，并置 表1实验用测试数据 max missed () Table 1 Test data min {(curr_trans-1).min_support,max_missed Sales数据/个 总事务数/个 记录个数/个 (t )+count (f)fCt) 2000 2000 7418 5000 node.itemset=t,node.count=1,node.firstposition= 5000 16645 10000 10000 28971 curr trans. ③修剪.对ISC中的所有项目集，计算其最大 可能支持度，若不满足支持度条件，则将其从SC 2500 2000 中删除.最大可能支持度通过下式得到： max prop_support()-max missed()count() 算法1 curr trans 1000 (2)PHASEⅡ（第二次扫描） 800 输入：数据立方体C,可能频繁集ISC. 600 算法2 400 输出：频繁项目集SC. 200 步骤：对于二维立方体C中的每个count>0的 0.5 0.2 0.1 0.05 事务T,进行如下操作 最小支持度% 对于所有属于SC的T的子集：，若当前事务 图3算法1和2对Sales挖掘执行性能的比较 号小于ISC中对应的firstposition,则其ISC中相应 Fig.3 Comparison of mining efficiency between the two algorithms 的counti+,max_missed--;若当前事务号等于 ISC中对应的firstposition,则置ISC中相应的max 从图3中可以看出，在最小支持度较大时，两 missed--O,此时计算其支持度，若小于最小支持 算法执行时间较为接近，相比之下，算法1执行 度，则从ISC中删除t及所有以1为子集的项目集. 时间比算法2要短.这主要是由于在最小支持度 (3)算法分析 较大时，产生的频繁集数目较少，k-itemset中的k 算法2在第一次扫描时，产生估计频繁项目 值很小，甚至≤2.在这种情形下，它对立方体的

公 杨 学 兵 等 基 于 数 据 立 方 体 的维 内关 联 规 则挖 掘 算 法 掘算 法 是通 过对 文献 【 中提 出的算 法 进行 改进 得 来 的 ， 算 法 仅需 两 次 扫描 数据 立 方体 新 的维 内频 繁 集 生 成 算 法 算法 输入 数据立 方体 ， ， 中事 务 维 中事 务 已 按 顺 序 编 号 ， 输 出 频 繁项 目集 步骤 ，执 行 步 骤 ，执行 步骤 ， 输 出 其 中子 过程 如 下 以 第 一 次 扫描 输 人 数据 立 方 体 ， ， 中 事 务维 各事 务依 次 编号 ， 总 事 务数 为 为用 户 给定 的最 低 支持度 输 出 可 能频 繁集 步骤 ， 初 始化 ， ’ 步骤 ， 对二维 立 方体 中。 通 过 引擎得 到 的 每个 事 务 丁进 行 以 下操作 ①增 加 计数 对 所 有 属 于 的 的子 集 ， 其 在 中的对应 ②插 入新结 点 对所有 不 属 于 的 的子 集 ， 若 的所 有 子 集 均 在 中 ， 则将 加 人 中 ， 并置 一 ’ 一 · ， ’ ‘ ， ， 仃 ③修剪 ， 对 中的所 有项 目集 ， 计算其最 大 可 能支持度 ， 若不 满 足支持度 条件 ， 则将其从 中删 除 最 大可 能支 持 度 通 过 下 式 得 到 集 ， 它不 同于 算法 算 法 每次 扫 描 时 只 处 理 一 种长 度 的项 目集 ， 而算 法 在 一 次扫 描 时 需 处 理 多种 长度 的项 目集 算法 在 处 理 每个 事 务 时 ， 也用 到 了 性 质 ， 这 样就避 免 了对所有 长 度 的项 目进 行处 理 ， 而 只处 理那 些 最 有 可 能 成 为频 繁集的项 目 很显 然 ， 单次 扫描 ， 其耗 时是 多 于算 法 ， 但 由于 算法 需 扫 描 二 维 立 方体 以 处 理 多 种 长度 的项 目集 ， 其总 耗 时会 随着 扫描 次数 的增 加 而 迅 速增 加 算法 的第二次 扫描 仅仅是求精 频 繁集 ， 因此第 二 次 扫描 耗 时 比第 一 次 扫描耗 时 要 少 实 验 实 验在 机 器上 进 行 ， 操作 系统 是 ， 数据 库采 用 数据 库 ， 算法 用 十 来 实现 ， 被测 数据是合肥 市农 河 超 市 的实 际 营业 数 据 ， 以 购 买 的 商 品 名 称 作 为项 目 维 ， 购 买 序号作为 事 务维 ， 具体见 表 算 法 和 对 挖掘 结果 的 比较 如 图 所 示 表 为 两算法 执行 的具体结 果 数据 表 实验用测 试数据 尸 介 ’ 数据 个 总 事 务数 个 记 录个数 个 一 算法 夕 汀 第二 次 扫描 输人 数据 立 方体 ， 可 能频 繁集 输 出 频 繁项 目集 步骤 对 于二 维 立 方 体 中的每个 。 的 事 务 ， 进行 如 下操 作 对 于所 有 属 于 的 的子 集 ， 若 当前 事 务 号 小 于 中对 应 的 ， 则 其 中相 应 的 。 ， 一 一 若 当前事 务号 等于 中对应 的 ， 则 置 中相 应 的 企 ， 此 时计算其 支 持 度 ， 若小 于最 小 支 持 度 ， 则 从 中删 除 及 所 有 以 为子 集 的项 目集 算法 分析 算法 在第一 次 扫描 时 ， 产 生 估计频 繁项 目 ， 最小支持度 图 算 法 和 对 挖掘执行性能 的 比较 · 从 图 中可 以 看 出 ， 在最 小支持度较大 时 ， 两 算 法 执 行 时 间较 为 接近 ， 相 比之 下 ， 算 法 执行 时 间 比算 法 要 短 这 主 要 是 由于在 最小 支 持度 较 大 时 ， 产 生 的频 繁集数 目较 少 ， 今 中的 值很 小 ， 甚 至 ‘ 在 这 种 情形 下 ， 它对 立 方 体 的

·86· 北京科技大学学报 2003年第1期 表2实验中两算法执行情况对比表 Table 2 Mining results of the two algorithms 最小支 ARMLD Aprior 产生规 持度%第一次估计集数目/个第二次精确集数目/个执行时间s扫描次数/次频繁集数目/个执行时间s则数 0.50 893 117 276 117 193 0 0.20 2266 406 370 2 406 205 0 0.10 4717 893 508 4 893 453 18 0.08 5788 I155 563 5 1155 637 108 0.05 9064 2065 807 8 2065 2619 1483 注：事务数为10000，记录数为28971 扫描次数≤2，且每次扫描立方体只检查相应的k tures,2001.369 -itemset,所以这种情况下，其执行时间必少于算 3欧阳为民，蔡庆生，发现广义序贯模式的增量式更新 法2.但随着最小支持度的减小，频繁项目集数量 技术.软件学报，1998,910：777 4 Gray J,Chaudhuri S,Bosworth A,et al.Data cube:a rela- 变大，k-itemset中的k值也不断变大，从而导致算 tional aggregation operator generalizing group-by,cross- 法1对立方体的扫描次数>2次，且随着k的增 tab,and sub-totals [J].Data Mining and Knowledge Dis- 大，事务的k子集数目也变得很大，因而算法执行 covery,1997,1(1:29 时间也迅速增加，这从图3中可以看出，其曲线 5 Agrawal R,Imielinski T,Swami A.Mining association 上扬的角度变大，而算法2无论最小支持度多 rules between sets of items in large databases [A].Proc 1993 ACM-SIGMOD Int Conf Management of Data [C]. 大，均需扫描数据库2次，且对每个事务需检查 Washington DC,1993.207 其所有子集，因此时间消耗较大.但随着最小支 6 Agrawal R,Srikant R.Fast algorithms for mining associ- 持度的减小，由于算法2并未因此增加对立方体 ation rules [A].Proc 1994 Int Conf very Large Data Bases 的扫描次数，仅仅是由于最小支持度减小而导致 [C].Santiago 1994.487 了频繁项目集的增加，从而增加了对每个事务的 7裴健，柴玮，唐世谓，等.联机分析处理数据立方体代 数[J1.软件学报，1999,10(6：561 处理时间，而这种变化虽然影响到算法的执行时 8 Dong GZ,Han J W,Joyce M W,et al.Mining Multi-di- 间，但远不如算法1增加的迅速，因而从图形上 Mensional Constrained Gradients in Data Cubes [M].Very 看，其走势相对平缓，这正是算法2的特点所在. Large Data Base,2001:321 9 Lu H J,Feng L,Han J W.Beyond intratransaction associ- 参考文献 ation analysis:mining multidimensional intertransaction I Bischoff Joyce,.Alexander Ted著.成栋，魏立原译.数 association rules [J].Association for Computing Machin- 据仓库技术M北京：电子工业出版社，1998 ery Transactions on Office Information System,2000,18 2 Li W M.Han J W.Pei J.CMAR:Accurrate and Efficient (4):423 Classification Based on Multiple Class-association Rules I0杨学兵，高俊波，蔡庆生，可增量更新的关联规则挖 [M].The International Confederation of Drum Manufac- 掘算法[J.小型微型计算机，2000(6)：611 Algorithms for Data Cube-Based Intra-dimensional Association Rules Mining YANG Xuebing",CAl Oingsheng 1)Computer Science Department,Anhui University of Technology,Ma'an shan 243002,China 2)Computer Science Department,University of Science and Technology of China,Hefei 230027,China ABSTRACT Two algrithms for data cube-based intra-dimensional association rules mining are proposed by lu- cubrating into the structure of data cube and integrating with the technology of online analytical processing.Experi- ment results show that the two algorithms are respectively suitable for different support-constrained association ru- les mining. KEY WORDS knowledge discovery;data mining;association rule;data warehouse;data cube;multi-dimen- sional analysis

北 京 科 技 大 学 学 报 年 第 期 表 实验 中两算法执行情况对 比表 俪 最小 支 产生 规 持度 第一次估计集数 目 个第二 次精确集数 目 个 执行时间 扫描次数 次 频繁集数 目 个执行时 间 则数 ﹃川 ︸ 内‘内︸一、︶、︸、 ，同﹄ 谷内，一洲声 ，‘山、︸口 注 事务数为 ， 记录数为 扫描次数 ‘ ， 且 每次 扫描立 方体只检查 相 应 的 一 ， 所 以这种 情况 下 ， 其执行 时 间必 少 于算 法 但随着最小 支持度 的减小 ， 频繁项 目集数量 变大 ， 中的 值也 不 断变 大 ， 从 而 导致算 法 对 立 方 体的扫描 次数 次 ， 且 随着 的增 大 ， 事 务的 子 集数 目也变得很 大 ， 因而算法执行 时 间也迅 速 增 加 ， 这 从 图 中可 以看 出 ， 其 曲线 上 扬 的 角度 变 大 而算 法 无 论最小 支持度 多 大 ， 均 需 扫描数据库 次 ， 且对 每个事 务需 检查 其所有子 集 ， 因此 时 间消耗 较大 但 随着最小 支 持度 的减小 ， 由于算法 并未 因此增 加对立 方体 的扫描 次数 ， 仅仅是 由于最小 支持度减 小而 导致 了频 繁项 目集 的增加 ， 从而增加 了对 每个事务 的 处理 时 间 ， 而这种 变化虽 然影 响到算法 的执行 时 间 ， 但远 不 如算法 增 加 的迅 速 ， 因而从 图形 上 看 ， 其走 势相对 平缓 ， 这正 是算法 的特点所 在 参 考 文 献 作 ， 著 成栋 ， 魏立 原译 数 据仓库技术 」北京 电子工业 出版社 ， ， ， 一 ， 欧 阳为 民 ， 蔡庆 生 发现广义序贯模式的增量式更新 技术 软件学报 ， ， 盯 ， ， ， 一， ， 一 助 ， ， 凡 ， 一 认恤 ， ， 肠 「 裴健 ， 柴玮 ， 唐世渭 ， 等 联机分析处 理数据立方体代 数 软件学报 ， ， ， ， ， 一 ， ， ， 一 ， ， 杨学兵 ， 高俊波 ， 蔡庆生 可增量更新 的关联规则挖 掘算法 小型 微型计算机 ， 一 一 雌 ，， 岁 心 ， 别 ， ， ， ， ， ， ， 加 一 · 吃 一 一