海量数据关键分类挖掘算法

论文摘要

随着Internet的出现,人类已经进入了新的信息时代,信息的获取已经不像过去那样途径单一,内容有限,人们可以通过网络获得各种信息,并且每时每刻都有更多新的信息在产生。然而在给人们带来便捷的同时,不断膨胀的信息也给人们带来了一系列问题,信息的海量规模使得一些真正有价值的信息被淹没在大量无用的噪声信息中间,而一般人缺乏有效的方法或工具进行辨别,使其获取有价值的信息变得更加困难。数据挖掘技术的出现,正是为了帮助人们更有效地从海量的数据中发现有用的知识,帮助人们获得有价值的信息,辅助人们进行决策。同时,由于Internet的发展,海量的Web数据逐渐成为了一个重要的数据源,从静态的HTML页面,数据库中存储的交互信息,用户访问网站留下的日志信息,多元化的数据构成了Web。而在这些数据中,也不乏存在许多有价值的信息,越来越多的研究人员和公司企业都在将数据挖掘技术运用到Web数据挖掘中,以发现潜在的知识以及商业规律。我们发现Web数据中存在大量的分类数据,并且在一些具体应用中,存在挖掘分类数据的需求,以更好地提供决策支持,为此,本文结合实际应用需求提出了关键分类查询,主要工作有以下4个方面：1.对决策支持应用中普遍用到的查询算法Top-K查询、KNN查询、Skyline查询及相关工作进行了讨论,并根据他们的共同特征总结出查找关键的对象是决策支持应用中需求较多的查询任务。2.对Web数据中普遍存在的分类数据及其挖掘价值进行了探讨,并结合决策支持应用中对数据挖掘的需求提出了新问题,关键分类查询。同时我们对新问题进行了详细地分析,给出了两种定义和相应的基本处理算法。3.分析了基本处理算法的复杂度,并针对关键分类查询第二种定义的处理算法,提出了一系列启发式剪枝规则,设计了改进的算法,并通过大量实验验证了改进后算法的有效性和高效性。4.讨论了关键分类查询应用在海量数据环境下可能遇到的性能问题,并应用了Map-Reduce算法框架对处理算法进行分布式改造,使其能够有效处理海量数据,同时,我们也通过实验验证了分布式算法的有效性和高效性。

论文目录

• 中文摘要
• 英文摘要
• 图目录
• 表目录
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 决策支持
• 1.1.2 数据挖掘
• 1.1.3 分类数据挖掘
• 1.1.4 海量数据管理
• 1.2 研究意义
• 1.3 研究内容
• 1.4 本文工作
• 1.5 本文结构
• 第二章 基本概念和相关知识
• 2.1 数据挖掘概述
• 2.1.1 数据挖掘定义
• 2.1.2 数据挖掘过程
• 2.2 数据挖掘算法与应用
• 2.2.1 特征（Characteristic）规则
• 2.2.2 区分（Discrimination）规则
• 2.2.3 预测（Prediction）
• 2.2.4 关联规则（Association Rules）
• 2.2.5 分类（Classification）
• 2.2.6 聚类（Clustering）
• 2.3 决策支持应用中常见的查询问题
• 2.3.1 Top-K查询
• 2.3.2 KNN查询
• 2.3.3 Skyline查询
• 2.3.4 决策支持应用的查询需求
• 2.4 本章小结
• 第三章 关键分类查找算法
• 3.1 Web中的分类数据
• 3.1.1 电子商务应用中的分类数据挖掘
• 3.2 基于均值的关键分类查询
• 3.3 基于概率的关键分类查询
• 3.3.1 不确定数据管理
• 3.3.2 基于概率的关键分类查询定义
• 3.4 关键分类查询处理算法
• 3.4.1 基于均值的关键分类查询处理算法
• 3.4.2 基于概率的关键分类查询处理算法
• 3.5 基于启发式规则的处理算法
• 3.5.1 预处理剪枝规则
• 3.5.2 扩展过程剪枝规则
• 3.5.3 基于剪枝规则的改进算法
• 3.6 实验设计及分析
• 3.6.1 实验准备
• 3.6.2 AKCQ的性能分析
• 3.6.3 PKCQ与PKCQ+的性能对比分析
• 3.7 本章小结
• 第四章 海量数据环境下的改进算法
• 4.1 海量数据管理概述
• 4.1.1 海量数据的存储与访问
• 4.1.2 Map-Reduce算法框架介绍
• 4.2 基于均值的查询处理算法改进
• 4.3 基于概率的查询处理算法改进
• 4.3.1 预处理的改进
• 4.3.2 计算过程的改进
• 4.4 实验设计及分析
• 4.4.1 实验准备
• 4.4.2 Map-reduce算法性能分析
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 内容总结
• 5.2 未来展望
• 参考文献
• 攻读硕士期间发表论文
• 致谢