《分布式数据环境下关联规则挖掘算法研究》由会员分享，可在线阅读，更多相关《分布式数据环境下关联规则挖掘算法研究（66页珍藏版）》请在金锄头文库上搜索。
1、西北师范大学 硕士学位论文 分布式数据环境下关联规则挖掘算法研究 姓名：景永霞 申请学位级别：硕士 专业：计算机应用技术 指导教师：王治和 2008-06 摘 要 摘 要 近些年来，人们收集数据、存储数据的能力得到了空前的提高，我们可以轻 而易举地获得海量数据，在这些海量数据背后隐藏着许多重要的信息，理解它们 已经远远超出了人的能力，这就需要一种强有力的数据库分析工具。数据库知识 发现(KDD)就是为顺应这种需要而发展起来的一门学科， 它用来进行数据分析， 发 现重要的数据模式，并且已经成为一个重要而活跃的研究领域。 数据挖掘被视为数据库知识发现过程的一个基本步骤，它已引起了信息产业 界的极大
2、关注，其主要原因是“数据丰富，但信息贫乏”，为了有效利用这些海 量数据，如何将它们转换为有用的信息和知识就成为当务之急。随着计算机和网 络技术的发展，我们可以方便地获取 Internet 上的各种信息资源，传统的集中式数 据挖掘已经不能满足需要。企业的数据资源往往规模大、动态增长并且存在于地 理上分布的各个数据库中，把所有数据集中在一起进行处理既不可取，也不可行， 这使得数据挖掘系统必须具有分布式挖掘的能力。基于分布式信息资源的数据挖 掘日益受到人们的关注，成为信息科学研究领域中一个新的课题。 关联规则挖掘是近些年来研究较多、应用也最为广泛的数据挖掘方法。关联 规则挖掘于 1993 年由 Ag
3、rawal 等人提出，它最初是以分析事务数据库中项与项之 间的联系为目标，后来的研究者们对问题原型进行了多方面的改进和扩充。关联 规则挖掘问题的关键是频繁项集的产生，Apriori 算法是一种经典的挖掘布尔关联 规则的算法，本文将用它在局部站点来产生频繁项集。 分布式数据环境下的关联规则挖掘算法中，时间开销主要体现在两方面：(1) 频繁项集的确定；(2) 网络的通讯量。本文提出了一种基于 Web Services 框架的 改进算法 DARM(Distributed Association Rules Mining)，成功地克服了 FDM 算法 中可能造成频繁项集丢失的缺点，保证了数据挖掘结果的
4、完整性和正确性，同时 也减少了站点间的通讯量。 关键词：关键词：分布式数据环境；数据挖掘；关联规则；知识发现；Web Services II Abstract In the last decade, we have seen an explosive growth in our capabilities to both of collecting and storing data, and generate massive data by further computer processing. Interpretation and understand for massive data ar
5、e beyond our ability. As a result, a powerful analysis tool is needed to be developed. Consequently, the discipline of knowledge discovery in databases(KDD), which used for analyzing data and discovering important data model, has evolved into an important and active research area. Data mining is a s
6、tep in the knowledge discovery process. The major reason that data mining has attracted a great deal of attention in the information industry in recent years is due to “We are drowning in data, but starving for knowledge”. It is urgent matter to convert such data into useful information and knowledg
7、e. With the increasing developments of computer and network technology, we can easily access the Internet information resources, but the traditional centralized data mining can not meet the needs. Data repositories are large in size, dynamic, and physically distributed. Consequently, it is neither d
8、esirable nor feasible to gather all of the data in a centralized location for analysis. Hence, there is a need for algorithms to support knowledge acquisition and decision making from distributed databases. How to discover knowledge from distributed databases has been a new topic of information indu
9、stry. Association rule mining is active data mining research area and applies more widely than other methods, which is put forward by Agrawal et al in 1993. The initial purpose is analyzing the relation of items in transaction database. Later, many investigators improved and extended the prototype o
10、f question. Association rule mining has been an active research area of data mining. The most important step of association rule mining is the frequent itemsets generation. Apriori is a classic one of algorithms for mining frequent itemsets for Boolean association rules. Frequent itemsets in the loc
11、al sites will be achieved with it in this thesis. The time complexity of association rules mining in distributed databases mainly reflects in the two aspects: (1) the generation of the frequent itemsets; (2) the network communication traffic. Aimming at the shortage of FDM algorithm that may lost th
12、e III frequent itemsets, an improved algorithm DRAM(Distributed Association Rules Mining) based on Web Services was presented in this thesis. It not only guarantees the integrity and accuracy of the data mining results, but also cuts down the communication overhead among sites. Keywords: Distributed
13、 Environment; Data Mining; Association Rules; KDD; Web Services IV 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包括其他人已经发表或撰写过的研究成果，也不包含为获得 西北师范大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 签名： 日期： 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，
14、允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 （保密的论文在解密后应遵守此规定） 签名： 导师签名： 日期： I 第一章 绪 论 第一章 绪 论 在信息化时代里，人们可以轻而易举地获得海量数据，在这些海量数据背后 隐藏着许多重要的信息，因此人们希望能够对其进行更高层次的分析，以便更好 地利用这些数据。但是，要利用这些快速增长的、存放在大型和大量数据库中的 海量数据，没有强有力的工具，是非常困难的。 1.1 数据挖掘概述 数据挖掘概述 数据挖掘本身并不是新技术，它融合了来自于统计学、数据库和机器学习等 多学科已经成熟的内容，组成数据挖掘的
15、这三门支柱学科都已经发展了多年，也 已经得到了广泛的应用，数据挖掘的出现和发展有其自身的必然性。无论是商业、 企业、科研机构或者政府部门，在过去的若干年里都积累了海量的、以不同形式 存储的数据资料，在这些海量数据背后隐藏着许多重要的信息，要从中发现有价 值的信息和模式已经超出了人的能力，特别是随着数据仓库的出现，原有的数据 库工具已无法满足用户的需求，这就需要一种强有力的数据库分析工具，以达到 预测发展和决策支持。 对于数据挖掘，目前一种比较公认的定义是W.J.Frawley，G.P.Shapiro等人提出 的：数据挖掘(DataMining，DM)就是从大型数据库的数据中提取人们感兴趣的知
16、识，这些知识是隐含的、事先未知的、潜在有用的信息。提取的知识表示为概念 (concepts)、规则(rules)、规律(regulations)、模式(patterns)等形式 1 。这种定义把数 据挖掘的对象定义为数据库，而更广义的说法是：数据挖掘意味着在一些事实或 观察数据的集合中寻找模式的决策支持过程 2 。所以，数据挖掘的对象可以是结构 化的，如关系数据库中的数据；也可以是半结构化的，如文本，图形和图像数据； 甚至是分布在网络上的异构型数据。这里所说的知识发现，不是要求发现放之四 海而皆准的真理，实际上，所有发现的知识都是相对的，是有特定前提和约束条 件的，是面向特定领域的，同时还要能够易于被用户理解的结果 3 。 许多学者认为数据挖掘和KDD(Knowledge Discovery in Databases)是等价的概 念，人工智能领域习惯称为KDD，而数据库领域习惯称为数据挖掘；也有学者把 KDD看作是发现知识的完整过程，而将数据挖掘视为其中的一个基本步骤。这里 1 西北师范大学硕士学
