基于立方体的复杂查询聚集方法研究

论文摘要

I数据挖掘（Data Mining）是二十世纪九十年代新兴发展起来的一门交叉学科,它是指从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有趣知识的过程,因此又称为数据库中的知识发现（KDD: Knowledge Discovery in Database）。数据挖掘的一个主要特点就是其数据对象是大型数据集或信息库,如数据仓库或大型交易数据库等。数据（仓）库的基本特点是数据的多维特性,即用多个维属性描述数据对象的多个特征。根据数据挖掘任务对数据分析的复杂程度,可以分为单维数据分析技术和多维数据分析技术。单维数据分析是只取数据库中某个属性进行分析,如传统的关联规则就是只对交易数据库中的商品ID进行分析,得出购买商品之间的关联特性。而多维数据分析是对数据库中的多个维属性同时进行分析,得出潜在有趣的知识和规则。由于多维属性潜藏着比单维属性更丰富的信息,因此多维数据分析已成为数据挖掘技术的一个重要研究课题,许多重要的数据分析工具和决策支持系统都建立在多维数据之上,如联机分析处理（OLAP: On-Line Analytic Processing）和联机分析挖掘（OLAM:On-Line Analytic Mining）,多维数据挖掘（MDDM:Multi-dimensional Data Mining）。而且,越来越多的数据挖掘任务也从最初的单维数据分析发展到了多维数据分析,如多维关联规则,多维聚类,多维数据的孤立点分析等。众多的多维分析技术中,建立在多维数据模型——立方体之上的多粒度聚集方法研究从一开始就受到了广泛的关注。立方体是多维数据的有效模型,用于对多维数据建模和数据聚集（汇总）。基于立方体的查询实现是决策支持系统的核心功能,其主要通过对多维数据不同角度不同层次的数据分析为实现快速信息获取提供支持。立方体查询技术中的核心部分就是多粒度上的有效聚集。因此,目前国际国内都对立方体上多粒度聚集的查询实现进行了相关的研究,产生了许多基于立方体的聚集计算的有效实现算法。但是,较多的研究只是集中于仅含简单查询任务（如1个查询）的立方体（称简单立方体）聚集技术实现;而含复杂查询任务（如多个查询）的立方体（又称复杂立方体或多特征方）聚集的实现技术则研究得较少。信息是竞争取胜的武器,基于立方体的复杂查询能够给用户同时提供更详尽更全面的信息,因此将成为用户查询需求的趋势,基于立方体的复杂查询的聚集技术也将是立方体技术发展的方向所在。目前,仅有少量的研究文献涉及复杂立方体查询的实现。文献[1]提出了复杂立方体查询的扩展SQL语言实现,[2]中提出分布和代数型复杂立方体查询的计算算法,算法基于相应的分布型（代数型）简单立方体查询算法。涉及复杂立方体查询的其他少量文献,同样只涉及分布型。国内外的研究中尚没有整体型复杂立方体查询的有效算法,同时也没有能充分利用复杂立方体查询的内在特点提出更有效的复杂立方体查询聚集方法。目前,立方体技术中涉及部分粒度的聚集计算的也还是集中在简单立方体查询,但还没有复杂立方体查询中的部分粒度研究。完全粒度计算优点是对数据能全方位多角度地观察和分析,缺点是计算代价太大,没有给用户选择的余地。相对于完全粒度计算,部分粒度上的聚集计算和查询实现是适应用户个性化查询的要求,符合信息查询的多样化趋势。新的多数据库挖掘思想保持了数据的分布式存储特性,局部挖掘,综合分析,已经成为数据挖掘技术发展的一个新热点。基于这个趋势,为多数据库挖掘服务的多立方体联合聚集的思想应运而生,这也是数据挖掘技术和数据库技术发展的要求。基于以上所述,本文以基于立方体的复杂查询的聚集计算方法为研究重点,具体工作包含以下几点:第一,提出一种整体型复杂立方体查询的计算方法,以部分分布聚集特性为主,结合冰山查询（Iceberg Query）技术和Cache重用技术,并综合此三策略生成PDIC算法。该算法能有效实现整体型复杂立方体查询的聚集计算,与朴素方法相比,效率提高显著。实验在模拟数据和真实数据集上进行,实验结果显示了提出方法的可行性和高效性。第二,提出了基于Cache重用的有依赖聚集的复杂立方体查询实现方法。对复杂查询中存在的三种依赖聚集,相应提出以Cache重用技术为主的三种解决方法,提出的方法与传统计算方法相比,能有效节省内存空间,有效提高聚集速度。而且,提出的方法对分布、代数和整体型三类复杂立方体查询均适用。第三,提出两种复杂立方体查询进一步发展的研究内容,包含部分（可选）粒度的复杂立方体查询聚集方法研究框架和为多数据库挖掘服务的多立方体联合聚集的研究框架。部分粒度的聚集计算方法以用户的不同需求为前提,提出研究方案。多立方体联合聚集根据多数据集分布式存储的特点,使用并行聚集技术对多个数据集联合聚集,为多数据库挖掘中的模式发现和链接发现提供有利数据。

论文目录

• 中文摘要
• Abstract
• 第一章 前言
• 1.1 本研究的目的、意义和研究背景
• 1.2 基于立方体的复杂分析技术的主要内容
• 1.2.1 数据立方体及其相关概念
• 1.2.2 数据立方体的预计算
• 1.2.3 立方体查询
• 1.3 立方体查询与数据库查询的区别
• 1.4 立方体技术的国内外研究现状
• 1.5 立方体查询技术的难点
• 1.5.1 需要同时计算多个粒度上的复杂聚集函数值
• 1.5.2 用户提出的复杂查询对决策支持系统提出的挑战
• 1.5.3 启动个性化复杂查询服务机制提高查询质量和效率
• 1.5.4 多立方体聚集计算在多数据库挖掘中的应用
• 1.6 本文的研究重点、主要贡献和论文的组织
• 1.6.1 本文的研究内容
• 1.6.2 本论文各部分的研究内容
• 第二章 整体型复杂立方体查询的聚集优化策略
• 2.1 引言
• 2.2 相关研究工作
• 2.3 相关概念
• 2.3.1 多特征方（Multi-Feature Cubes）
• 2.3.2 分布型复杂查询及其计算特点、实现算法
• 2.3.3 代数型复杂查询及其计算特点、实现算法
• 2.3.4 整体型复杂查询及其计算特点、实现算法
• 2.4 整体型复杂立方体聚集优化策略
• 2.5 实验和分析
• 2.5.1 数据集
• 2.5.2 传统算法
• 2.5.3 优化算法
• 2.5.4 PDIC 算法描述
• 2.5.5 实验结果
• 2.6 本章小结
• 第三章 基于 Cache 重用的复杂立方体查询聚集方法
• 3.1 引言
• 3.2 复杂查询中的三种聚集依赖
• 3.2.1 完全重叠（Entire-overlapping）
• 3.2.2 部分重叠（Partly-overlapping）
• 3.2.3 互斥重叠（anti-overlapping）
• 3.3 基于Cache 重用的聚集优化方法
• 3.3.1 Cache 重用技术
• 3.3.2 三种基于Cache 重用的依赖聚集技术
• 3.4 实验和分析
• 3.4.1 数据集
• 3.4.2 基本算法
• 3.4.3 优化算法
• 3.4.4 实验结果
• 3.5 本章小结
• 第四章 复杂立方体查询技术的进一步发展
• 4.1 引言
• 4.2 基于用户个性化复杂查询的不完全粒度聚集方法
• 4.2.1 个性化复杂查询
• 4.2.2 可选路经的部分粒度聚集方法
• 4.3 多立方体联合聚集在多数据库挖掘中的应用研究
• 4.3.1 多数据库挖掘
• 4.3.2 多立方体联合聚集
• 4.3.3 多立方体联合聚集在多数据库挖掘中的应用研究
• 4.4 本章小结
• 第五章 总结
• 5.1 本论文工作总结
• 5.2 本论文的缺陷和不足
• 5.3 后续工作探讨
• 参考文献
• 附录：论文中用到的表格和实验结果图
• 读研期间发表的论文目录
• 致谢