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