探究基于云计算的Web结构挖掘算法
2015-12-07薛娟
薛娟
摘要：云计算是基于互联网的一种超级计算模式，能够为将Web中的所有数据信息集中在一起，为其提供各种服务。数据挖掘是获取Web网页中的有用的信息，随着互联网的快速发展，Web网页中的数据信息量显著增加，传统挖掘算法已经无法满足用户的实际需求，基于云计算的Web结构挖掘算法，能够打破传统挖掘算法的桎梏，对于Web网页信息和知识的发现提供了很大的便利。文章分析了云计算的特点以及服务模式，探析了一种基于云计算的Web结构挖掘算法，即基于MapReduce的PageRank算法，以供参考。
关键词：云计算；Web；结构挖掘算法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）06-0010-02
数据挖掘指的是对大量、复杂的数据信息进行分析，然后从中获取有用的数据信息。现如今，重要的数据信息都储存在Web网页上，由此可见研究Web数据挖掘的重要性。但是，随着互联网技术的快速发展，Web网页上的数据信息量不断地增加，网络环境也越来越复杂，想要从Web网页中挖掘出有用的信息，传统的节点计算、储存算法已经远远不能满足需求，基于云计算的Web结构挖掘算法，能够有效地解决传统算法存在的问题，例如，基于MapReduce的PageRank算法，以其强大的网络数据信息获取能力、计算能力、储存能力，能够更加快速、高效的挖掘、计算和储存Web网页的信息和知识。因此，文章针对基于云计算的Web结构挖掘算法的研究具有非常重要的现实意义。
1 云计算的特点以及服务模式分析
1.1 云计算的特点
云计算是一种基于用户需求，为用户提供主动服务的超级计算模式。云计算能够为用户提供共享的服务模式，并且能够支持多个用户的不同需求。云计算能够满足不同规模的计算需求，由信息和资源处理中心对需求进行快速的分析和调节，并进行云计算。云计算采用按量计费的方式，用户不需要对没有消费的服务买单，这样既能够降低成本，又能够避免造成浪费。
1.2 云计算的服务模式分析
云计算的服务模式主要包括以下几个方面：
1）IaaS，Infraslruelure as a Service——基础设施即服务，根据用户权限，可以直接方位云计算提供的网络宽带、分布式储存、并行运算等基础设置，同时可以根据自己的需求，搭建负荷自己需求的平台；
2）PaaS，Platform as a Service——平台即服务，云计算能够为用户提供一个平台，包括工具集与软件开发语言，其能够为用户组建一个虚拟的操作系统，用户根据自己的需求在该平台上开发以及部署相应的平台与应用；
3）SaaS，Software as a service——软件即服务，用户根据自己的需求，使用基于云计算架构的应用程序为自己服务，例如网络储存、在线表格、在线文档、电子邮件等。
2 基于MapReduce的PageRank算法分析
2.1 基于MapReduce的PageRank算法的实现
2.1.1 算法数据准备
按照链接结构文件格式将文件转换成针对每一个节点的出链接结构文件，其中预处理数据包由网页上的海量数据信息组成，在map执行的过程中，按照map方法，生成所有起始节点的目标点的
2.1.2 算法的实现
PageRank算法输出的每个节点，按照Map方法对输入每一行记录的目标节点顺序，按照每个key归类MapReduce框架采集map方法对应的value。按照reduce方法，将每一个key：页面y，对的所有项进行加和，然后带入公式：Pk+1= dATPk+（1-d）（公式1）计算，其中，PK表示第k次迭代后的PageRank向量，AT表示矩阵的转置矩阵，然后输出所有页面全新的PageRank，即获得所有key初始化的PageRank值，在HDFS中储存所有的计算结果，进行下一次迭代计算。在迭代计算过程中，Mapper对所有起点的目标点生成一个与之对应的partial，然后把所有的partial传送至Mapreduce中。
2.2 基于MapReduce的PageRank算法的改进分析
2.2.1 迭代并行PageRank改进算法分析
按照PageRank算法的传统计算公式，推算PageRank算法的向量公式，即公式1，因此按照初始向量P0进行向量Pk的递推，过程表现为：
P1= dATP0+（1-d）e （公式2）
P2= d2（AT）2P0+d（1-d）ATe+（1-d）e （公式3）
Pk=+dk（AT）kP0+ dk-1（1-d）（AT）k-1e+…d（1-d）ATe+（1-d）e （公式4）
通过上述递推过程，以跨度为2计算公式为：P2= d2（AT）2P0+d（1-d）ATe+（1-d）e
迭代并行PageRank改进算法的过程表现为以下几个方面：1）在计算之前，应该先生成和跨度相关的邻接矩阵，以k=2为例，采用MapReduce计算AT，根据MapReduce过程获得（AT）2，MapReduce在迭代的过程中，以初始PageRank向量、AT以及（AT）2为输入文件，最后生成相应的PageRank向量，按照上述步骤进行反复迭代，如图1所示。按照“移动计算比移动数据更经济”的思想，应该尽可能将被计算的数据储存在原来的位置，避免出现数据大量移动的现象，这样既能够提高系统吞吐量，又不至于造成网络的堵塞。因此，HDFS中储存的AT以及（AT）2不会随着迭代的改变而改变。当k=2时，可将算法分为三个阶段：1）输入上述阶段生成的链接构成文件G，并用G代替邻接矩阵的AT，将首列作为目标节点，第i行，第j列节点用ATi，j表示；2）使用第一阶段获得的AT，生成相应的链接结构文件，然后获得相应的矩阵，通过计算获得（AT）2；3）k=2，因此每次的迭代跨度都为2，采用迭代并行PageRank算法计算向量，输入第一阶段获得的AT，计算d（1-d）ATe+（1-d）e，输入第二阶段获得的（AT）2，计算d2（AT）2P0，获得新的PageRank向量，并保存在HDPS中，再进行下一次迭代计算。
2.2.2 矩阵分块并行PageRank改进算法分析
矩阵分块并行PageRank改进算法，用矩阵如图2所示，Reduce阶段的额外性能消耗，通常来自于排序阶段与混合阶段，如果在排序阶段中存在众多key关键词，将会消耗了大量的时间，如果将块大小设定为b，通过MapReduce处理之后的向量块、数量块等将会减少为1/b。采用矩阵分块并行PageRank算法进行改进之后，一个向量块能够表示b条向量块，而且改进之后向量块之间并不存在外链接的节点，因此不会生成相应的记录，这样能够有效的节省大量邻接矩阵空间，从而降低储存空间的消耗。同时，由于不需要记录之前b条向量，记录的总条数明显降低，占用的内存量显著降低，进而境地I/O消耗，由此可见其优势。
3 结束语
总而言之，Web网页上的信息量显著增加，并且日增长量呈指数级发展，面对如此多的数据信息和庞大的Web信息资源库，想要从中获得用户所需要的信息和知识，其难度可想而知。文章探析的一种基于云计算的Web结构挖掘算法，即基于MapReduce的PageRank算法，能够更加快速、准确地从Web网页中提取用户所需要的信息和知识。同时，基于云计算的Web结构挖掘算法的研究和应用尚处在初级阶段，还需要从以下几个方面进行研究：
1）研究能够在高压力、高并发以及大容量的Web环境中运行的K-span算法。
2）加强对Hadoop调度机制的深入研究，使Hadoop算法变得更加准确、高效。
3）实现算法从单机平台向云计算平台的转移，充分利用云计算高效、准确的优势。
虽然上述几个方面还需要我们深入的研究，但是，基于云计算的Web结构挖局算法，以其强大的计算与储存能力，受到社会各界的广泛关注。
参考文献：
[1] 倪靖. 一种基于云计算的Web结构挖掘算法[J]. 电脑知识与技术， 2011，7（24）：5933-5935.
[2] 蓝昊慧. 云计算在Web结构挖掘算法中的运用研究[J]. 计算机时代， 2012（10）：30-32.
[3] 李远方. 基于云计算的Web结构挖掘算法研究[D]. 云南： 云南大学， 2011.
[4] 胡或， 封俊. HadooP下的分布式搜索引擎[J]. 计算机系统应用， 2010， 19（7）： 24-26.
[5] 王鹏. 云计算的关键技术与应用实例[M]. 北京： 人民邮电出版社， 2010.
[6] 陈修宽. 数据挖掘综述[J]. 山东轻工业学院学报， 2009， 23（3）：8-23.
