摘要:互联网上的数据规模大、种类多、变化快,而且越来越复杂。通过数据挖掘和分析,可以获取有潜在价值的信息。但是,传统的数据挖掘系统在数据存储和计算性能上存在瓶颈。通过使用云计算技术,设计了一个基于Hadoop架构的网页日志数据挖掘和分析平台来解决这个问题。同时,为了提高挖掘效率,为大规模网页日志挖掘实现了Apriori算法的并行化,并使用该平台验证了该行算法的效率。
关键词:数据挖掘;网页日志挖掘;Apriori算法;云计算;Hadoop
中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2014)28-6603-04
随着互联网技术的飞速发展,因特网上的数据成指数级增长。如何在这样的一个环境中发现并挖掘出有价值的信息成了研究的热点[1]。网页日志挖掘是数据挖掘技术在网页上的应用,它需要大量的网页数据[2]。这方面的研究一直集中在改进挖掘算法上,而对于大规模数据的数据挖掘系统的处理能力尚未得到很大改善。在大规模数据挖掘方面,单个节点的计算能力遇到了瓶颈。解决这个问题的一个有效的方法就是利用云计算、分布式计算和虚拟化技术的优势,将复杂的计算通过网络分配给多个节点。文章结合网页日志文件的特性,设计了一个基于Hadoop集群架构的数据挖掘平台,改进了Apriori算法,并通过实验验证了该算法的高效性。
1 云计算和数据挖掘技术
1.1 MapReduce编程模型
MapReduce是一种用于大规模数据集并行运算的编程模型[3]。该模型处理集群上的大规模数据集时主要分两步:“映射(Map)”和“归约(Reduce)”。首先,通过映射处理输入的键-值对数据,获得键-值对形式的中间结果。然后,将获得的中间结果整理并排序。最后,结合处理得到的结果进行合并得到最终结果。整个过程如图1所示。
1.2 网页日志挖掘的概念
网页日志是由网页服务器在用户浏览网页时产生的数据文件。它记录了用户的交互操作。这样做的目的是为了分析并找出有用的信息,比如用户浏览网页的方式,用户的爱好等等。
1.3 网页日志挖掘的过程
网页日志挖掘主要分为三个步骤:
1) 预处理:网页日志里的大多是些板结构化或者非结构化的数据。这使得数据挖掘的算法不能直接应用于原始的日志数据。如果不进行预处理,很难找出有价值的信息[4]。
2) 模式识别:通过此步为经过预处理产生的数据文件选择合适的数据挖掘技术和算法,找出能反映用户特定行为、资源、会话以及简明数据的隐式信息模式。
3) 模式分析:解析并分析上一步挖掘出的模式信息,找出感兴趣的模式,然后以可视化的方式输出结果。
2 基于云计算的网页日志挖掘系统的设计
2.1单节点数据挖掘系统
传统的集中式数据挖掘系统基于单节点,它使用一个服务器来完成包括数据采集、数据存储、数据预处理以及数据挖掘等所有的工作。当数据挖掘工作的复杂度不高,数据量不大的时候,单节点系统的工作效率很高。然而,随着互联网网页日志数据的不断增长,数据挖掘工作越来越复杂,集中式数据挖掘系统已经不能满足大规模网页日志处理的要求。
2.2 基于云的大规模网页日志挖掘系统
由分析可知,传统的数据挖掘系统在处理海量数据时有很多瓶颈,使用云计算技术可以有效地解决这个问题[5,6]。
云计算平台包括一个主节点,一个名称节点,一个算法存储节点和一些数据节点。主节点负责各计算节点的计算流程的协调和调度,处理节点异常,负载均衡等事项。名称节点存储元数据信息。主节点也可以用作为名称节点。为了减少由于数据传输占用的大量资源,每个数据节点也是计算节点。
通过上面的分析,通过使用Hadoop集群架构,构建一个基于云计算的大规模网页日志挖掘系统[7]。该系统分为三层:分布式数据存储层,功能层和可视化层。系统的整体结构如图2所示。
1) 分布式数据存储层
分布式数据存储层是本系统的硬件资源,由成本低的计算机和网络设施组成。这些资源就是云计算平台的数据节点。这些节点不仅提供了数据存储功能,还提供了计算功能。系统采集的原始网页日志数据文件经过预处理后转换为半结构化的XML格式的文件,存储到数据节点上。同一份数据文件会被复制存储到不同的存储节点上,这样就可以避免由系统崩溃带来的数据丢失的问题。
2) 功能层
功能层为系统提供了核心功能。数据预处理组件和数据挖掘算法就部署在该层。网页日志数据挖掘由主节点负责。主节点将复杂的数据挖掘任务合理地分配给各计算节点。这样数据挖掘任务可以同时执行,达到了在分布式数据库上并行挖掘的目的。
在每个周期中,主节点发送一个信号给数据节点,确定数据节点的状态是工作中还是闲置。收到信号后,各数据节点将自己的状态信息发送给主节点。主节点将根据收到的信息将闲置的节点列入到闲置节点列表中。当主节点收到来自客户端的任务请求时,就将任务分配给各数据节点。当计算任务完成后,处理得到的数据文件块会被返回给主节点。
3) 可视化层
可视化层为用户提供交互界面和结果的可视化显示功能。
3 网页日志挖掘算法和并行化改进
3.1 网页日志挖掘算法
当前,网页日志挖掘算法包括最大正向引用序列法,关联规则算法等。关联规则算法是在一个事务中描述各个事件之间的联系规律的一个知识模型。通过分析和处理网页服务器的日志,关联规则可以用来分析用户访问网页的习惯和爱好,进而为其提供个性化的信息。
关联规则挖掘分两步:首先是找出所有的频繁项集。然后找出频繁项集中各项目之间的紧密关系。
Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集[8]。算法已经被广泛的应用到商业、网络安全等各个领域。Apriori采用逐层搜索迭代的方法产生频繁项集,比如,K-1项目集用来搜索产生K项目集。其步骤如下:
1) 首先,扫描数据库找出满足最小支持度的项目,构成一个集合——“1项集”,记作L1。
2) 利用L1产生“2项集”的集合L2。
3) 重复上面的步骤,直到找不到“K项集”——LK。
3.2 基于MapReduce的并行化改进
冲Apriori的工作步骤可以看出,在扫描数据库的时候会产生大量的候选项目集。特别是在处理像网站的网页这样的WAN数据源的时候尤其如此。这是一个严重的缺陷,它会影响到挖掘的效率和准确性。基于云计算平台的并行Apriori算法可以将上述各项工作分配给各个数据节点,由这些节点来进行并发处理并产生各自的频繁项集。主节点将所有节点产生的频繁项集集中起来,产生全局的频繁项集。这样可以大大提高Apriori算法的效率。主要步骤如下:
1) 首先读取配置参数、最小支持度和最小可信度,设置MapReduce参数。
2) 映射:将读取到的数据映射为键值对。
3) 归约:每次读取到一个输入时,同一个项集会被映射到相同的归约器。归约器会计算出项集的频繁度并识别出满足最低支持度的频繁项集。
4) 将K项集记录在本地。如果K项集为空,停止并跳到第6步。
5) 从本地读取K项集并产生K+1项集。如果没有新的候选项集,进入第6步。否则,返回第2步。
6) 根据产生的频繁项集和最小可信度,产生关联规则。
4 实验结果
实验用了7个安装了Linux和Hadoop的服务器,其中一个为主节点,其他的为数据存储兼计算节点。实验主要是挖掘网页日志的频繁项集。首先使用传统的Apriori算法,用单个节点进行挖掘,然后用改进的Apriori算法进行并行挖掘。通过对两组结果进行对比分析,可以看出并行的网页日志挖掘系统和改进的Apriori算法比传统的方法的效率高很多。
4.1 实验1
将同一个网页日志数据分别用单节点系统和Hadoop集群系统进行挖掘。然后用比较数据集的大小。可以看到,单节点系统和Hadoop集群系统产生的频繁项集的一致性波动很小,如图3所示。
4.2 实验2
实验采用较大规模的数据作为输入,比较处理相同规模的数据时单节点系统和Hadoop集群系统的效率。然后持续增加输入数据的规模并记录两个系统的处理时间。从实验中可以得出一个结论:当输入的数据低于一定的规模时,两个系统并没有太大区别。随着处理的数据规模增大,Hadoop集群系统处理数据的时间比单节点系统少得多,如图4所示。
5 结论
介绍了数据挖掘的概念和云计算的相关技术,分析了传统单节点数据挖掘系统存在的不足。设计了一个基于云计算和Hadoop集群架构的网页日志挖掘系统,并将Apriori算法和MapReduce结合起来,实现了并行Apriori算法。通过实验验证了在进行大规模网页日志挖掘时,并行系统比单节点系统的效率高很多。并行挖掘系统不仅解决了传统系统的瓶颈问题,还提高了数据处理和分析的效率。
参考文献:
[1] 马妮娜.数据库新的应用技术——数据挖掘技术[J].中国电子商务,2003(7).
.山东轻工业学院学报(自然科学版),2009(3).
[3] 吴宝贵,丁振国.基于Map/Reduce的分布式搜索引擎研究[J].现代图书情报技术,2007(8).
.电脑知识与技术,2013,9(5).
.计算机与信息技术,2009(4).
.杭州:浙江理工大学,2012.
.大连:大连理工大学,2011.
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。 返回通信学论文列表