基于多维谓词索引树的关联规则挖掘算法的研究与应用

论文摘要

关联规则挖掘作为数据挖掘中的一个重要问题,已经广泛地应用于各大商业领域,成为数据挖掘中最主要的研究内容之一。多维关联规则作为关联规则的一种重要形式,在近年来也得到了迅速的发展,成为近几年来一个研究热点。首先,本文分析了目前研究多维关联规则挖掘的两种主要途径,一种是扩展维内关联挖掘算法直接应用于多维事务数据库产生多维关联规则,此方法具有很好的灵活性,但处理维谓词的I/O开销较大,从整体上来说效率较低。另一种是利用数据立方体技术进行多维关联规则挖掘,此方法具有较好的I/O性能,特别当数据立方体较小时,可以用多维数组有效实现,然而针对维数较多的大型数据库,构造及维护相应的数据立方体是极其昂贵的。然后,针对两类方法的优缺点,提出了一种高效的多维关联规则算法,通过引入一种新的数据结构——MDPI-tree （Multi-dimensional Predicate Index Tree）结构,有效地将数据立方体技术和频繁项集挖掘技术结合起来,其中MDPI-tree由维信息部分的DP-tree （Dimensioal Predicate Tree）和项信息部分事务构造的FP-tree （Frequent Pattern Tree）及其连接构造而成。算法采取分而治之的思想,首先对维信息部分构建数据立方体,并采用致密的前缀树结构DP-tree压缩存储,最大限度的压缩存储空间；然后对项信息部分,采用FP-Growth算法挖掘频繁维谓词约束下的频繁项集,从而大大减少了项信息的处理量。该算法既利用了数据立方体能够有效处理多维数值度量的优点,又高效地处理了事务的项信息,不仅能够挖掘维间关联规则,而且能够挖掘混合维关联规则。最后,本文以vc++ 6.0, sql server 2000为实验平台,通过实验验证了MDPI算法的性能,实验结果表明MDPI算法不仅具有良好的I/O性能,还具有很好的伸缩性与稳定性。并将基于MDPI的多维关联规则算法应用于某移动通信公司交叉销售中,结果显示所挖掘出的多维关联规则具有一定的商业价值,能为决策分析人员提供决策依据。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 问题的提出
• 1.2 研究背景
• 1.3 多维关联规则的研究现状
• 1.4 研究内容和意义
• 1.4.1 研究内容
• 1.4.2 研究思路与研究意义
• 1.5 文章的组织结构
• 第2章 关联规则的基本理论与算法分析
• 2.1 关联规则的基本概念
• 2.2 关联规则的分类
• 2.3 关联规则算法在不同环境中的应用
• 2.3.1 事务数据库
• 2.3.2 关系数据库
• 2.3.3 OLAP环境
• 2.4 关联规则的算法性能评价
• 2.5 单维关联规则
• 2.5.1 FP-growth算法的基本思想
• 2.5.2 FP-growth算法的步骤
• 2.5.3 FP算法性能分析
• 2.6 多维关联规则
• 2.6.1 多维关联规则基本描述
• 2.6.2 多维关联规则挖掘方法
• 2.6.3 多维关联规则算法研究
• 2.7 小结
• 第3章 OLAP技术在多维关联规则算法中的研究
• 3.1 OLAP基本概念
• 3.2 OLAP技术与数据挖掘
• 3.2.1 OLAP技术与数据挖掘的区别与联系
• 3.2.2 OLAP关联规则挖掘思想
• 3.2.3 OLAP关联规则挖掘方法
• 3.2.4 数据立方体技术在多维关联规则中的优化
• 3.3 基于数据立方体的多维关联规则算法研究
• cube算法'>3.3.1 Apriori_cube算法
• Cube算法'>3.3.2 FP-Growth_Cube算法
• 3.4 小结
• 第4章 基于MDPI多维关联规则算法
• 4.1 数据立方体技术与FP算法的结合点
• 4.2 MDPI算法的基本描述
• 4.2.1 构建DP-tree
• 4.2.2 计算频繁谓词集
• 4.2.3 构建MDPI-tree
• 4.2.4 优化寻找多维频繁项集的算法
• 4.3 算法实验结果以及性能分析
• 4.3.1 实验环境与工具介绍
• 4.3.2 实验数据与测试方案
• 4.3.3 实验结果分析
• 4.3.4 算法性能分析
• 4.4 小结
• 第5章 多维关联规则算法在交叉销售中的应用
• 5.1 移动通信交叉销售模型简介
• 5.2 交叉销售模型的研究与技术支持
• 5.3 交叉销售模型总体设计
• 5.4 多维关联规则算法在交叉销售中的实现
• 5.4.1 数据预处理
• 5.4.2 构建多维数据模型
• 5.4.3 关联规则挖掘结果分析
• 5.5 小结
• 结论
• 参考文献
• 致谢
• 附录A （攻读学位期间发表的学术论文）