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