基于基集和概念格的数据挖掘方法研究

摘要

从大量的数据中提取或者“挖掘”隐含的知识是数据挖掘的主要任务，因此又称数据挖掘为数据库中的知识发现过程。数据挖掘涉及了多个新兴学科领域的知识，其发展和这些学科的发展相辅相成。关联分析是数据挖掘诸多功能中最为重要和应用最广泛的一种技术。关联分析用于发现数据间蕴涵的关联规则，关联规则描述了给定数据集的数据项之间的某些有趣联系。
　　 概念是人类进行知识表达的一种手段。数据库知识发现的过程就是将数据库中蕴含的知识形式化成有用概念的过程。概念格是知识的一种表现模型，依据知识体在内涵和外延上的依赖或因果关系，建立概念层次结构。概念格是一种基于概念和概念层次的数学化的表达，是应用数学的一个分支。目前，概念格被广泛应用于多个研究领域。在数据挖掘领域，概念格是提取关联规则的重要方法之一。
　　 本文首先介绍了数据挖掘的基本概念、应用范围、功能、分类、常用技术和存在问题及发展方向。其次介绍了关联分析的基本概念及一些关联规则的主要应用场合和挖掘方法。其中着重介绍了挖掘关联规则的一些常用算法（如Apriori算法）的基本思想，并讨论了这些算法的共性和为提高效率所采用的一些技术和方法。这些算法普遍面临着因为项集生成瓶颈而造成的效率低下问题，同时存在着挖掘出的规则包含大量冗余规则的问题。本文针对这些问题，做了一些相关的研究工作，主要内容包括：
　　 提出了一个基于基集的关联规则挖掘算法。基集是用采样的原理从原始数据集中提取出的一个子集，本文提出了一个称为“动态系统扩散”的方法来获得这个集合。该方法以一些用户感兴趣的种子项为基础，使用一种动态扩散的方法，通过扫描数据库得到与种子项存在较大关系的一个子集。这个子集相对于原始数据库来说具有较小的规模，因而在传统算法生成频繁项集容易遇到的频繁项集急剧增多而造成效率严重下降的问题上，有了明显的改善。同时，该算法产生的关联规则避免了大量冗余无效的规则，使之更容易形成被用户接受的知识。
　　 提出了一种约简概念格的构造算法，并把该算法应用于关联规则的挖掘中。该算法在频繁1项集的基础上，利用项集可以用事务标识号表示的特点，同时在建格过程中引入支持度比较的方法，提高建格的速度，并使得最后得到的概念格具有高度的约简性。在建好的约简概念格上，本文提出了两种方法可以快速提取出频繁项集，从而进一步挖掘出关联规则。
　　 提出了一种综合利用基集和约简概念格技术的关联规则提取算法。该算法以基集作为建格的基础节点，利用约简概念格的建格和提取算法快速地搜索出所有的频繁项集。
　　 本文最后尝试了把基于基集和约简概念格的关联规则提取算法应用于GIS中空间数据的关联规则挖掘领域中。通过空间连接索引(SJI)技术将空间数据进行适当的格式转换，可以把空间数据库转换成适宜于关联规则挖掘的数据形式。本文针对空间数据挖掘容易产生大量无用强规则的特点，应用了两种剔除冗余规则和无意义规则的方法，让最后产生的结果更加精简并符合用户的期望。

目录

文摘

英文文摘

引言

第一章 数据挖掘

1.1 数据挖掘的历史

1.2 数据挖掘的基础讨论

1.2.1 数据挖掘的基本概念

1.2.2 数据挖掘的应用范围

1.2.3 数据挖掘的功能

1.2.4 数据挖掘的分类

1.2.5 数据挖掘存在的问题和发展方向

1.3 数据挖掘常用技术概述

1.3.1 神经网络

1.3.2 决策树

1.3.3 粗糙集

1.3.4 概念格

1.3.5 统计分析方法

1.3.6 遗传算法

第二章 基于基集的关联规则挖掘

2.1 关联规则的一般性描述

2.1.1 基本概念

2.1.2 购物篮分析——一个典型挖掘关联规则的例子

2.1.3 关联规则的分类

2.1.4 挖掘关联规则的基本步骤

2.2 挖掘关联规则的常用算法

2.2.1 Apriori算法

2.2.2 Apriori算法的变形及改进

2.3 基于基集的关联规则挖掘算法

2.3.1 算法基础

2.3.2 基集生成算法

2.3.3 设计支持度函数和权值函数

2.3.4 算法流程

2.3.5 算法示例

2.3.6 性能测试

2.3.7 结论

第三章 基于基集和约简概念格的关联规则挖掘算法

3.1 概念格的基本概念

3.2 概念格的建造和简化

3.2.1 批处理算法

3.2.2 增量式算法

3.2.3 概念格的简化

3.3 一个约简的增量式建格算法

3.3.1 在频繁1项集基础上构建约简概念格

3.3.2 基于约简概念格生成频繁项集

3.4 基于基集和约简概念格的关联规则挖掘

3.4.1 算法伪代码

3.4.2 应用示例

3.4.3 性能测试

3.4.4 结论

第四章 关联规则挖掘在GIS中的应用

4.1 GIS与数据挖掘

4.2 空间关联规则挖掘的补充定义

4.3 空间数据格式转换

4.4 关联规则挖掘算法在GIS上的应用

4.5 剔除空间关联规则中的冗余规则和无意义规则

结束语

本文工作总结

进一步的研究工作

致谢

参考文献

攻博期间取得的研究成果