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