基于云计算的分布式数据挖掘算法研究
来源:用户上传
作者: 王超鹏 梁正科 李强
摘 要： 数据挖掘是对海量数据进行分析和总结，得到有用信息的知识发现的过程。作为数据挖掘的一个分支，成熟的分布式数据挖掘已经应用到社会生活许多领域。对海量数据的存储和挖掘，云计算提供廉价和有效的解决方案，能解决分布式数据挖掘的瓶颈。因此，基于云计算平台的分布式数据挖掘是目前的热门研究。给出数据挖掘算法的分类，重点针对不同的数据类型，给出适用的基于云计算的分布式挖掘算法。
关键词： 云计算；数据挖掘；分布式
中图分类号：TP393.08 文献标识码：A 文章编号：1671－7597（2012）0220104－01
0 引言
信息技术的出现导致各种格式（如记录、文档、图像、声音、航空数据等）的海量数据存储在数据仓库中，如何从海量的数据中找到有价值的信息是当前的一个热点，对人类社会具有非常重要的社会价值和经济利益，数据挖掘就是实现这一功能的技术。数据挖掘从早期的单独算法对单系统、单机器进行对向量数据的挖掘，到与数据库相结合，支持多个算法的挖掘，以及和预测模型相集成，支持Web数据、半结构化的数据的网络化计算，发展到了分布式数据挖掘。分布式数据挖掘（Distributed Data Mining，DDM）作为一种成熟的挖掘技术已被广泛应用到各个领域，是数据挖掘领域的热点之一。“分布”的含义包括数据的分布和计算的分布两层含义。在分布式计算环境中，用户、数据、计算硬件、数据挖掘软件均可能在地域上分散。分布式数据挖掘旨在解决分散的同构和异构数据库的挖掘问题；同时，数据的分布性带来处理的并行性，则可能解决海量数据挖掘的可伸缩性（Scalability）瓶颈[1]。
随着科学技术的飞速发展，人类社会信息正以每18个月产生的数量等于过去几千年的总和的速度不断增加[1]。尤其是随着物联网产业的迅猛发展，越来越多的应用终端被接入网络，随之带来的庞大的数据量极大的增加了人们从海量数据中发现有用知识的难度。物联网产生的数据具有数量大，高度分散的特点，传统的分布式数据挖掘已经无法解决现有数据处理瓶颈问题[2]。作为新兴商业计算模型的云计算，为分布式数据挖掘提供了许多新的解决思路和方案。云计算是数据管理技术发展的必然趋势，能对分布在大量计算机上存储的资源池上进行操作，使基于云计算平台的应用能根据需要获取所需的存储空间，软件服务和计算能力。目前，IT巨头正在相继开发云计算平台、云计算终端和服务器。
1 数据挖掘算法分类
数据挖掘算法有很多，从不同的视角，数据挖掘技算法可以有根据发现知识的种类分类、根据挖掘的数据库的种类分类和根据采用的技术分类的几种常见分类标准[3]。
1）根据发现的知识种类，数据挖掘算法有：关联规则发现、分类或预测模型知识发现、数据总结、数据聚类、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等多种算法。
2）根据挖掘的数据库的种类，数据挖掘有基于各种数据库的挖掘算法：关系型、面向对象数据库、空间数据库、时态数据库、文本数据源、交易型、多媒体数据库、异质数据库、遗留数据库等，已经基于数据仓库、基于Web的挖掘算法等。
3）根据挖掘方法采用的技术，可分为：统计分析、机器学习方法、模式识别、面向数据库或数据仓库的技术、可视化技术和神经网络等挖掘算法。其中，常用的统计方法可细分为回归分析、判别分析、聚类分析（系统聚类、动态聚类等）、探索性分析等。机器学习方法可细分为：归纳学习方法（决策树、规则归纳等）、基于范例学习、遗传算法等。数据库方法主要是多维数据分析或OLAP方法，另外还有面向属性的归纳方法。
基于云计算分布式数据挖掘算法是在这些数据挖掘算法的基础上，采用云计算平台实现的数据挖掘算法，也可以采用这样的分类标准进行分类。然而，由于有各式各样的数据存在，每一种挖掘算法都应用到具体的数据类型上，对数据类型的要求是有限制的，一种算法不可能会适应所有数据类型的挖掘应用。因此，在考虑不同数据类型的挖掘和具体的应用时，如何选择合适的挖掘算法是非常重要的。当然，在实际应用中，往往结合多方面的因素，考虑算法的优缺点，采用多种算法实现有效的挖掘。
2 不同数据类型对应的挖掘算法
随着信息量的剧增，数据的种类也不断增多。从粗粒度来看，数据挖掘常应用到如下几种数据形式：文本型（Textual）、关系型（Relational）、
事务型（Transactional）、面向对象型（Objected-Oriented）、主动型（Active）、空间型（Spatial）、时间型（Temporal）、多媒体（Multi-Media）、异质（Heterogeneous）数据库和遗留（Legacy）系统等。从挖掘的数据特性出发，专家和相关研究人员将数据挖掘归为如下几种技术：[4，5]
1）分类。分类算法适用于以元组构成的关系型数据形式，关系型中的一个数据属性可以看作分类输出的目标属性，其他属性作为分类算法数据模式（输入）。这类算法的主要目的是对训练的数据集进行挖掘，以发现另外的数据为目标得出数据分类的原理，这个原理可以用于后加入数据的分类。如果预测的变量是离散的，这类问题成为分类；如果预测的变量是连续的，这类问题成为回归。基于云计算常用的分布式挖掘算法实现关系型数据的挖掘主要有基于K-最邻近方法的分类算法、云计算环境下朴素贝叶斯文本分类算法、基于神经网络、基于范例的推理、决策树和径向基函数等分类算法。
2）聚类分析。聚类分析和分类算法相似适用于关系型数据的挖掘。聚类是在事先不规定分组规则的情况下，将数据按照其自身特征划分成不同的群组进行挖掘，以期从潜在的数据中发现新的、有意义的数据分布模式。聚类方法主要有划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的聚类。云计算聚类算法常用的有基于云计算的并行k均值聚类算法等。
3）关联规则。关联规则适用于事务型、交易型和关系型数据，但对关系型数据要求按事务分组。最适合处理的变量类型是布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，而数值型关联规则可以和多维关联或多层关联规则结合起来。关联规则挖掘主要是发现大量数据中项集之间有趣的关联或相关联系，关联规则研究有助于发现交易数据库中不同商品（项）之间的联系以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。云计算环境下的常用关联规则分布式挖掘算法有：Apriori算法，已经出现了多种对Apriori算法改进的版本。
4）基于模式的相似性查找。该算法适用于于文本型和时间型数据，进行文本相似性搜索和时间相似性。时间序列数据是一类重要的复杂数据对象，对时间序列数据库进行挖掘能发现时间序列中所蕴涵的知识，数据挖掘技术在时间序列中的主要应用有规则发现、周期模式挖掘、相似性搜索和序列模式发现等方面。文本数据是最常见的一种数据，基于文本相似型的挖掘可以实现文本雷同度与相似性的研究。常用的算法有基于云模型的时间序列分段聚合近似方法、基于模糊聚类的文本挖掘算法、基于云计算的ARMA算法和基于离散傅立叶变换的时间序列相似性查找算法等。
5）时间序列或趋势发现和分析。该技术主要用于时间型数据，通过对不同时间点以前时间数据值的变化，发现或预测未来可能的变化和趋势，如股票的预测就是这种一个好的时间序列趋势析例子。常用的算法有神经网络算法、支持向量机算法等。
此外，除了上面提到的常用数据类型的挖掘，对空间数据的挖掘多采用空间聚类分析和空间OLAP等方法；对多媒体数据的挖掘多采用基于规则的决策树分类算法；对于应用在智能终端上的普适数据多采用机器学习和统计的挖掘算法。
3 结束语
本文首先介绍了云计算和分布式数据挖掘的相关知识，随着Internet的普及和数据的海量增加，二者相结合能解决分布式数据挖掘的瓶颈问题，是今后的一个发展方向。本文重点针对不同的数据类型采用的基于云计算的分布式挖掘算法进行了对比，为基于云平台的分布式数据挖掘系统的开发提供了支持。云计算为海量和复杂数据对象的数据挖掘提供了基础设施，为网络环境下面向大众的数据挖掘服务带来了机遇。
参考文献：
[1]张诚、郭毅，专访中国科学院计算技术研究所-何清博士，数字通信，2011，3：5-7.
[2]陈磊、王鹏、董静宜、任超，基于云计算架构的分布式数据挖掘研究，成都信息工程学院学报，2010，12：777-579.
[3]邵峰晶、于忠清著，数据挖掘原理与算法，北京：水利水电出版社，2003.08.
[4]M.S.Chen, J. Han and P.S.Yu,Data Mining:An Overview from Database Perspective,“In IEEE Trans.on Knowledge and Data Engineering,Vol.8, No.6, pp. 866-883, Dec.,1996.
[5]J.Han,“Data mining techniques,”ACM-SIGMOD'96 Conference Tutorial, June,1996.
转载注明来源:https://www.xzbu.com/8/view-1702400.htm
