海量数据挖掘技术研究刘君强
【摘要】： 随着信息技术特别是网络技术飞速发展，人们收集、存贮、传输数据能力小断提高。数据出现了爆炸性增长，与此形成鲜明对比的是，对决策有价值的知识却非常匮乏。知识发现与数据挖掘技术正是在这一背景下诞生的一门新学科。数据挖掘要在实际应用中发挥作用，高性能挖掘算法和数据挖掘软件平台是重要的技术基础。本文以数据挖掘最基本问题，频繁模式与关联规则挖掘为切入点，研究高时间效率、高空间可伸缩性的挖掘算法和分布、异质、海量数据的协同挖掘软件模型。 本文首先发现了基于树表示形式的虚拟投影方法，用于按深度优先挖掘密集型数据集；提出了稀疏型数据集表示形式及非过滤投影方法；进一步提出了基于伺机投影的思想，设计并实现了基于伺机投影的全新算法OpportuneProject，对比实验表明该算法挖掘各种规模与特性数据库的效率与可伸缩性都是最佳的。 由于其内在的计算复杂性，挖掘密集型数据的频繁模式完全集非常困难，解决办法是挖掘频繁模式的闭合集或最大集。本文提出了一种组织闭合模式集的复合型频繁模式树，支持搜索空间的高效剪裁，有效地平衡了树生成与树剪裁的代价，实现了闭合模式集挖掘算法CROP，其效率与可伸缩性大大优于CHARM等算法。在此基础上，本文提出了闭合性剪裁和一般性剪裁相结合，并能适时前窥的最大模式挖掘算法MOP，大大优于MaxMiner和MAFIA等算法。 本文进一步提出了根据信息熵自动生成与人机交互相结合来确定数值型与类别型属性概念层次的新方法，不仅支持逐层挖掘而且能进行跨层挖掘，并实现了多支持率剪裁，将所提出的挖掘频繁模式完全集、闭合集的新算法推广到无冗余关联规则、多维多层多数据类型关联规则、多支持率分类规则的挖掘问题。 本文在所取得的数据挖掘算法研究成果基础上，对数据挖掘软件模型作了深入研究。首先提出了数据挖掘作业描述语言MDL和挖掘任务模型脚本语言，设计并实现了一个集成数据仓库管理功能、挖掘引擎具有一定智能、体系结构可扩展的数据挖掘工具，并已经集成到一个大型商业连锁企业的经营决策系统中。 本文在研究分布式问题求解技术和分析移动型智能代理技术的基础上，提出了从网络海量数据中发现有用知识的协同挖掘模型。首先定义了黑板和知识源的描述语言以及知识交换格式，设计和实现了支持互联网上分布式问题求解的黑饭系统，提出了分布式网络海量数据挖掘系统DistributedMiner。接着在分析移动式 摘要 智能代理技术的基础上，设计了一种移动式智能代理服务器，通
过重构基础结构 提出了移动式网络海量数据挖掘系统模型MobifeMiner。
【关键词】：知识发现 数据挖掘 关联规则 分类规则 多维多层多数据类型关联规则 频繁模式 闭合频繁模式 最大频繁模式 黑板系统 分布式问题求解 智能代理 移动型智能代理 协同数据挖掘 分布式数据挖掘 移动式数据挖掘 智能型数据挖掘工具 算法 软件 海量数据库
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2003
【分类号】：TP311.13
【DOI】：CNKI:CDMD:1.2003.114001
【目录】： 前言4-6摘要6-8ABSTRACT8-14第1章 概论14-201.1 数据挖掘技术的兴起14-151.2 数据挖掘的主要问题15-171.2.1 数据挖掘任务与知识类型15-161.2.2 数据挖掘的过程161.2.3 数据挖掘的对象161.2.4 数据挖掘的应用16-171.2.5 面临的挑战171.3 本文的工作17-181.4 本文的结构18-20第2章 数据挖掘技术综述20-342.1 频繁模式与关联规则挖掘20-242.1.1 单层单维布尔型关联规则挖掘与Apriori算法20-222.1.2 对Apriori算法的改进22-232.1.3 频繁模式与关联规则挖掘研究的新发展23-242.2 闭合模式挖掘与A-Close算法24-272.2.1 闭合模式挖掘与A-Close算法24-262.2.2 其它闭合模式挖掘算法26-272.3 最大模式挖掘与Pincer-Search算法27-302.3.1 最大模式挖掘与Pincer-Search算法27-282.3.2 其它最大模式挖掘算法28-302.4 多层多维关联规则挖掘30-312.5 对关联规则挖掘的其它扩展31-322.6 数据挖掘软件的发展32-34第3章 伺机投影策略的挖掘算法34-503.1 引言34-353.2 问题的描述35-373.3 频繁模式树的构造37-383.4 模式支持集的表示与投影38-423.4.1 稀疏型PTS的基于数组表示及其投影38-403.4.2 密集型PTS的基于树表示及虚拟投影40-423.5 伺机投影策略与OpportuneProject算法42-453.5.1 伺机投影的启发式原则42-433.5.2 OpportuneProject算法43-453.6 性能评价45-493.6.1 数据集及其特性45-463.6.2 基本实验结果46-483.6.3 可伸缩性试验48-493.7 小结49-50第4章 闭合模式与最大模式挖掘50-664.1 引言50-514.2 问题的描述51-524.3 复合型频繁模式树及其生成52-544.3.1 复合型频繁模式树CFIST52-534.3.2 CFIST结点的合并53-544.3.3 CFIST的生成算法544.4 CFIST的剪裁与包含关系的检查54-564.4.1 高效的CFIST局部剪裁54-554.4.2 分枝包容关系的快速检查554.4.3 快速杂凑法55-564.5 CROP:挖掘闭合模式的高性能算法56-584.5.1 平衡CFIST生成与剪裁效率56-574.5.2 CROP算法57-584.6 CROP性能测评58-624.6.1 CROP与CHARM效率对比58-604.6.2 CROP与CLOSET效率对比604.6.3 CROP与MAFIA效率对比。60-614.6.4 可伸缩性实验61-624.7 挖掘最大频繁模式的新算法MOP62-644.7.1 最大频繁模式集及其剪裁624.7.2 MOP算法62-634.7.3 MOP的性能评价63-644.8 小结64-66第5章 多维多层关联规则与分类规则66-785.1 关联规则与无冗余
关联规则66-685.2 多维多层多数据类型关联规则挖掘68-725.2.1 多维多层多数据类型关联规则挖掘问题69-705.2.2 MDML-PP算法70-715.2.3 性能测评71-725.3 挖掘多支持率分类规则72-765.3.1 分类规则挖掘与TTF扩展72-735.3.2 多支持率剪裁73-745.3.3 分类规则及其单阶段挖掘算法74-755.3.4 对比实验75-765.4 小结76-78第6章 智能型数据挖掘工具设计与实现78-926.1 引言78-796.2 数据仓库及其管理79-816.2.1 数据仓库模型与OLAP79-806.2.2 数据仓库的框架描述806.2.3 数据仓库管理器80-816.3 数据挖掘任务的描述、管理及执行机制81-846.3.1 数据挖掘作业Job的描述81-826.3.2 挖掘任务模型Scenario的定义82-836.3.3 挖掘任务模型的管理与执行83-846.4 智能型数据挖掘引擎84-876.4.1 算法描述库与算法模块84-866.4.2 知识库与引擎管理器86-876.5 SmartMiner体系结构87-886.6 关键技术与SmartMiner原型实现88-916.7 小结91-92第7章 网络海量数据协同挖掘92-1127.1 引言92-937.2 分布式黑板控制93-947.2.1 问题求解的黑板系统937.2.2 分布式问题求解与黑板控制93-947.3 形式化描述语言94-967.3.1 黑板的描述947.3.2 知识源的描述94-957.3.3 知识交换格式95-967.4 实现分布式黑板控制的一般智能代理96-987.4.1 一般智能代理GA的结构设计96-977.4.2 智能代理软件DBC-MA的实现97-987.5 分布式数据挖掘系统DistributedMiner98-1017.5.1 分布式知识发现功能997.5.2 DistributedMiner的黑板设计997.5.3 挖掘平台体系结构99-1007.5.4 DistributedMiner的实现与应用100-1017.6 从分布计算到移动计算101-1077.6.1 什么是智能代理1027.6.2 智能代理的特征102-1037.6.3 移动型智能代理103-1047.6.4 典型mobile agent系统104-1077.7 移动式数据挖掘系统模型107-1097.7.1 移动型智能代理服务器107-1087.7.2 DBC-MA变型108-1097.7.3 MobileMiner工作流程1097.8 小结109-112第8章 结论和展望112-114参考文献114-130公开发表的论文、主持和参加的科研项目130-132致谢132-133