基于WEB的数据挖掘的研究与应用

 2021-12-10 10:12

论文总字数：26391字

摘 要

近几年来，随着移动设备的增加，全球移动设备的数量几近人口总和，移动设备人均普及率超过94%，随之而来的是，数据量的爆炸式增长和WEB2.0时代的到来，为了适应设备的多变性，WEB项目成为了多数互联网公司的开发首选或者必须兼容的项目，将从WEB抓取的信息转化为实时有效商业信息，可以提高公司的竞争能力从而创造商业价值。

本文以信息抓取和数据挖掘为主要的研究方向，论述了如何与WEB进行交互从而进行数据抓取的并且使用合适算法对抓取的信息进行数据挖掘。本文采用模拟用户操作结合传统抓取方法来达到数据抓取的目的。另外对数据挖掘的关联式规则算法以及决策树算法进行了分析，使用两种算法对抓取的信息进行分析。根据决策树算法中随机森林算法的特性，对随机森林算法进行了分布式处理，提高其在面对大规模数据时的运算能力。

关键词：信息抓取、数据挖掘、分布式

Research and application of data mining based on WEB

Abstract

In recent years, with the increase of mobile devices, the number of mobile devices almost equal the total population, followed by, the arrival of data amount explosively growth and WEB 2.0 era. in order to adapt to the device's variability, web projects become the majority of the company's development. the information from the web crawl transformation for effective real-time business information can improve the competitive ability of the company to create business value.

In this paper, the main research direction are information capturing and data mining, discusses how to interact with WEB and capture data, and the use of a suitable algorithm for data mining. The purpose of information extraction is achieved by using the method of simulating user’s operation and combining traditional extraction method. In addition, the association rule algorithm and decision tree algorithm of data mining are analyzed in this paper, and two kinds of algorithms are used to analyze the information. According to the characteristic of the random forest algorithm, random forest algorithm can be used in distributed computing , and the operation ability of the random forest algorithm will be improved in the face of large-scale data.

Keywords: information extraction, data mining, distributed

目录

摘 要 II

Abstract III

第一章 绪 论 2

1.1 研究的背景和目的 2

1.2 国内外研究现状 2

1.3 主要工作及贡献 3

1.4 论文结构 4

第二章 基于动态页面的数据抓取 5

2.1 动态生成页面元素的DOM树 5

2.2 Selenium和WebDriver 5

2.3 基于DOM树的数据抓取 6

2.4 本章小结 10

第三章 关联式规则及相关算法 11

3.1 关联式规则 11

3.2 关联式规则算法 11

3.3 关联规则算法性能分析 15

（1） 关联规则算法性能实验 15

（2） 实验结果及分析 16

3.4 FP-Growth算法的应用 18

3.5 本章小结 20

第四章 分类式规则算法 21

4.1 分类式规则 21

4.2 决策树算法 21

4.3 随机森林算法 23

4.5 本章小结 26

第五章 基于MapReduce的随机森林算法 27

5.1 Hadoop分布式架构 27

5.2 随机森林算法的并行化 30

5.3 并行化随机森林算法性能实验 30

5.4 本章小结 32

第七章 总结和展望 33

7.1总结 33

6.2展望 34

第一章 绪 论

1.1 研究的背景和目的

根据来自iGR最新的调查报告显示，2014年的全球移动设备的数量已经到达了69亿，移动设备的普及率已经达到了94.5%。因为移动设备的快速增长，也直接的导致数据量呈现出快速上升的趋势。与此同时，出于兼容更多地设备和减少开发成本的目的，WEB技术近年来也快速成长并且迅速进入了广泛应用的时期，更多地新特性出现在了各种WEB中，为传统爬虫获取信息的方式造成了新的阻碍。如果仅是为了各类应用的正常运行，其实多数数据是冗余的，各类企业和团体之所以花费巨资用于贮存数据，还有着从数据中提取具有商业价值信息的想法。如何将海量数据运用于实际生产生活中，迅速且又精准地获得潜藏在数据中有价值的信息，如何理解历史数据并合理地运用于预测未来商品行情。从数据中挖掘潜在的知识的想法，催生了数据挖掘技术。

数据抓取和数据挖掘在信息社会都有着丰富的意义，不过随着技术变化，对于数据抓取和数据挖掘又提出了更多的要求。现今的动态网页不同于以往的动态网页，以往动态页面只要可以根据不同用户反馈不同的数据即可，随着前端技术的发展，客户端担负了更多的责任，甚至连DOM的生成都是依赖于前端技术。而数据挖掘技术在面对海量数据时，需要应对更多的属性和不同的属性特征，而对数据挖掘计算的要求却越发提高。了解各类算法特性，提高数据挖掘算法的效率，也有了更迫切的需要。

1.2 国内外研究现状

本文工作主要涉及以下几个方向的研究问题：

（1）WEB信息抓取：依靠WEB2.0的特性对抓取网页上的文本信息。

（2）数据挖掘算法：通过对数据挖掘算法的概念、属性分析并且通过实验来进行算法的评价。

1.2.1 WEB信息抓取

WEB信息抓取是长久以来业内都在讨论和研究的问题，传统的WEB信息抓取主要分为以下几类方式：

  1. 基于正则表达式的抓取：正则表达式是一种特定的字符串匹配模式，通过字符串处理可以从原串中找出符合正则表达式的子串。WEB页面内容是可以视作一个字符串流的，通过正则表达式对信息进行抓取，但是这种方式一个是难于复用，另外维护难度很高。
  2. 基于DOM树的抓取：HTML本身就是一棵DOM树，在信息抓取之前，需要预先将HTML解析成为DOM树，再根据DOM树的结构对信息进行抓取。
  3. 基于自然语言的提取：当WEB信息中包含大量文本信息时，可以对文本进行语法分析、句法分析、实体识别等，从而可以从中抓取信息。
  4. 基于 Web 查询的信息抓取: 该方式是将WEB看成是一个巨大的数据库,以搜索引擎做为数据库入口,不断地发送查询请求,然后对搜索引擎返回的结果进行过滤, 从而实现信息抓取。

在应对WEB信息的复杂多变性上，传统的数据挖掘方法做出了很多研究和贡献。但是前端技术的出现带来了以下几个优势：1）减少被竞争网站抓取的可能；2）减少服务器的计算压力；3）新型WEB技术有着更加丰富的显示效果；这三个优势使得越来越多的网站开始应用新的WEB技术,但是正如之前所说却为传统的数据抓取方法带来了新的问题。

1.2.2 数据挖掘算法

本文对经典的关联式规则以及分类式规则中的决策树算法进行了原理解析以及实验对比。其中关联式规则算法一般用于挖掘项目之间的关联性，比较经典的案例是“啤酒与尿布”，但是由于需要对大量的数据集中进行统计，关联式规则算法会占用大量的资源用于计算。决策树算法一般用于分类和预测，但是普通的决策树算法一般存在对训练集过度拟合的问题，随机森林算法是决策树的一种，其特有的构造决策树的方式在很大程度上避免了过度拟合，且一般决策树存在剪枝操作，处理不当容易对算法准确度造成影响，随机森林算法通过构造大量决策树来避开剪枝操作，且由于树的生长相对独立，随机森林算法更有便于并行化的特性。

1.3 主要工作及贡献

本文主要对数据抓取技术和数据挖掘技术的应用进行了研究，主要工作如下：

（1）提出了一种模拟用户行为进行数据抓取的方法：WEB技术一直是作为承载信息的载体，其发展的过程和他的开放性和便于检索的特性密不可分，但是新的前端技术为数据抓取带来了新的阻碍。为了突破前端技术带来问题，本文采用JavaScript模拟用户的系列操作，与WEB进行交互，得到指定的DOM之后结合传统的数据抓取技术，对目标信息进行抓取。

（2）对经典的关联式规则算法进行了研究：关联式规则算法大量的使用在从历史交易记录中提取关联商品，比较经典的案例是“啤酒和尿布”。本文对关联式规则算法的几种经典算法进行了论述和分析，选取了Apriori算法和FP-Growth算法作为分析的对象，对算法的核心计算方法进行论述分析，并进行试验分析以上算法那在应对各种规模数据量时的表现。通过处理使用网页抓取技术得到的真实的商品数据，将抓取转换成目标格式的数据集，并使用FP-Growth算法对其进行分析。

（3）对决策树算法进行了研究及并行化处理：决策树算法属于分类规则算法中的一支。其广泛地被使用在分类和回归的运算中，本文选取随机森林算法作为分析的样本。本文使用随机森林算法对商品销售的情况进行预测。随机森林算法相比于其余决策树算法，具有更容易处理成分布式计算的优点，本文对分布式的随机森林算法进行了试验，分析其在分布式集群下进行计算的特性和优势。

1.4 论文结构

第一章介绍了数据抓取和数据挖掘的基本背景和国内外研究状况。

第二章阐述了如何对交互式网站进行数据抓取以及过程中遇到的问题及处理方案

第三章阐述了关联式规则的原理，对经典的关联时规则算法进行了实验分析算法性能，并使用FP-Growth算法对从WEB上抓取的商品信息进行了计算以及分析。

第四章阐述了决策树算法的原理以及决策树算法中的随机森林算法做了详细介绍

第五章对Hadoop平台进行了介绍，并对并行处理后的随机森林与原始随机森林算法进行了对比。

第二章 基于动态页面的数据抓取

数据的积累一般会经历漫长的过程，但是互联网最大的特性就是其开放性。通过数据抓取，可以快速度过数据积累的阶段。本章主要阐述模拟用户操作与WEB交互的方法和基于DOM树抓取相关文本的方法。

2.1 动态生成页面元素的DOM树

与静态页面和普通动态页面不同，静态页面本身是静态的文件，如后缀是html的文件，浏览器发送请求之后直接反馈给请求方即可。更多的是动态页面，服务器需要进行运算反馈给浏览器HTML流。浏览器请求HTML流［1］的过程如下：

（1）浏览器向服务器发出请求，等待服务器返回HTML流；

（2）浏览器接受HTML并载入，遍历lt;headgt;中的lt;linkgt;链接请求CSS；

（3）浏览器继续载入HTML中的代码，根据CSS开始渲染页面；

一般的请求到渲染的流程到这里就结束了。不过WEB技术的发展给了JavaScript更多的施展空间。在传统的WEB中，输出的HTML包含了所有的元素以及数据，随着前端技术的发展，尤其本文中针对的动态生成页面元素的WEB，在其处理流程中，服务器仅用来做少量的计算，反馈给用户基础的HTML，其中包含了页面中所有的数据、渲染页面的CSS文件以及生成DOM元素的JavaScript文件的链接。得到链接后浏览器向CDN服务器请求各类JS及CSS文件，然后JavaScript生成对应的DOM节点并插入到基础的HTML DOM节点树中，此时浏览器再根据CSS文件渲染HTML，用户才得以见到请求的页面。

这样的做法给数据抓取带来的难度就是，必须要完整运行JavaScript代码，才可以得到期望的DOM树。基于这个原因，催生了Selenium这一类似的WEB自动化测试工具的产生。

2.2 Selenium和WebDriver

Selenium［2］是有ThoughtWorks公司开发的WEB自动化测试工具。Selenium通过WebDriver原生的测试接口实现自动化测试。Selenium的底层是使用JavaScript来实现的，对所有的浏览器都使用的是同一个接口，其最大的特点是支持在不同的浏览器上运行同一份测试代码，同样也可以使用多种主流语言进行编码。

WebDriver［3］是一个有语言中立的接口和相关的协议的浏览器，WebDriver设计的目的是提供一个更简便的编程接口，允许使用程序或者脚本控制一个浏览器的行为。 Selenium和WebDriver结合可以实现WEB APP的自动化测试。Selenium整合了WebDriver的API，实现在使用时可以使用一份代码对不同的浏览器进行兼容性测试。

Selenium-WebDriver开发的目的是更好的支持动态网页，其轻量级和易于移植的特性，使其得以被广泛的使用于动态网页的数据抓取。

2.3 基于DOM树的数据抓取

本文采用的方法Selenium触发对应事件获得目标DOM节点，然后采用基于DOM树的抓取，抽取DOM节点中的信息。

DOM树的数据抓取主要由两种方式：

XPath［4］：XPath是一门在XML文档中查找信息的语言，HTML文本的实质是XML文档，XPath作为功能强大的查找语言，十分适合用来进行信息抽取；

JavaScript选择器［5］： JavaScript有原生的DOM节点选择功能，而Selenium对JavaScript有良好的支持，通过Selenium执行JavaScript选择器，可以将JavaScript的DOM对象转换为Selenium中的对象，从而进行文本抽取的操作。

XPath和Javascript原生的选择器已经很强大，但是实际应用中选择器都还稍有不足，我们通过Selenium可以执行JavaScript的特点，对JavaScript的选择器进行拓展和优化。

（1）选择器的优化

本文除了XPath和JavaScript的选择器外，还采用了JQuery的选择器。JQuery是JavaScript应用最为广泛的库之一，其选择器有着极其强大的功能，JQuery的选择器一向遵从“更少的代码，做更多的事”的原则。在WEB中可以通过JavaScript动态的创建节点并插入DOM树，达到引用JQuery的效果，以下的JavaScript代码可以达到以上叙述的效果：

var body= document.getElementsByTagName('head')[0];  
var jquery = document.createElement('script');  
jquery.type= 'text/javascript';  
jquery.onload = script.onreadystatechange = function() {  
    if (!this.readyState || this.readyState === "loaded" ||    this.readyState === "complete" ) { 
        callback();
           jquery.onload = script.onreadystatechange = null;  
    } };  
jquery.src= ' http://lib.sinaapp.com/js/jquery/1.7.2/jquery.min.js ';  
body.appendChild(jquery);

以上的代码创建了一个lt;scriptgt;标签，并且等待该标签加载完毕然后回调callback()函数，函数中可以执行JQuery的函数。该方法通过lt;scriptgt;标签载入，可以避过跨域访问的问题。通过该方法实质上可以引入其他JS文件从而对功能实现进一步扩展功能，所以该方法的意义不仅局限于选择器的优化。

（2）事件模拟

对于电商网站而言，网站与用户的交互大多都是通过鼠标完成。而用户通过鼠标的操作可以大致分为三类：

  1. 单击：Selenium自身带有模拟单击的函数click(),但是Selenium自带的click函数在不同浏览器之间存在兼容性问题，这一点在下文有阐述。
  2. 鼠标移动：在大型的WEB应用上，出于成本和性能开销的考虑，图片几乎都是采用异步加载的方式，一部分的网站为了防止用户大量开启网页，检测当前鼠标位置是否有变化来决定是否载入页面，面对类似的问题可以使用Selenium的功能ActionChain。ActionChain可以触发包括鼠标移动在内的一系列事件，当然ActionChain的事件同样也需要指定目标元素。在带有鼠标移动检测的页面，一般是对lt;bodygt;标签传入鼠标移动事件。
  3. 滚动页面：页面的滚动可以通过调节当前页面的高度距顶部的距离来实现，通过简单地JavaScript代码即可。采用JavaScript来滚动页面，必须要考虑到页面滚动的幅度，而且必须检测目标节点是否加载完成。不过滚动页面一般是在页面有宽高的情况下，屏幕无法完整显示整个页面，我们采用了更加粗暴的方式。在开发过程中，我们使用的WebDriver是ChromeDriver，而生产环境是在服务器。由于服务器没有图像界面（该类浏览器称为Headless浏览器），我们使用的是Headless的浏览器PhantomJS，可以通过我们自己的需求来定义页面宽高，可以将页面高设置为一个无限大的值，可以完全不用顾忌页面中的节点是否加载完成。

（3）事件模拟过程中的难点及解决方案

由于浏览器之间的兼容性差异，我们开发时必须使用有图形界面的浏览器ChromeDriver，而造成了生产环境下代码不能正常运行，其问题主要表现在如下两方面：

  1. 无法触发lt;agt;标签的事件：lt;agt;标签并不是一个兼容性良好的标签，各级浏览器对lt;agt;标签的支持本身并不一致。再加上多数WEB页面的编写并不规范，lt;agt;标签被随意的应用，常常造成一些兼容性的问题。而且这样的问题不止存在于Headless浏览器中，在Android的WebView浏览器中也会造成无法触发对应事件的问题。对于lt;agt;标签一般出现问题是由于lt;agt;的互相嵌套，导致无法触发期望事件。

对于使用链接的lt;agt;标签，可以获取lt;agt;标签的href中的链接，然后加载该链接。对于带有其他事件的lt;agt;标签，在Selenium的Click函数和JQuery的Click函数均失效的情况下，可以利用JavaScript事件冒泡的特征。JavaScript事件冒泡特性的特征是，当一个事件触发之后，如果该节点上没有可以响应的事件，该事件会一直向父节点传播，直到有节点响应为止。利用事件冒泡特性，遍历图形界面中可点击区域的叶子节点，对所有叶子节点发送Click事件，直到目标事件响应。

  1. 事件触发的结果判断：随着前端技术发展，WEB应用的复杂程度也越发复杂，对同一个DOM元素进行事件触发也可能出现不同结果。使用Selenium进行抓取时使用者必须对目标元素有预期，并且需要提取出目标元素的特征。由于DOM元素是动态生成的，计算和输出是需要时间的，甚至某些数据需要异步请求。因此判断一次事件触发是否符合预期其实需要至少两个条件：1）目标元素的特征；2）设置等待的时间上限。如果在等待事件内有目标元素出现，则判定事件触发成功。设置时间上限的原因是防止出现不在预计内的情况时程序陷入死循环。之所以将结果判断列入难点是因为在异步请求中太多不能预计的情况，因为出现了不在程序记录内的条件，程序只有记录程序异常的日志和当时的数据，包括出错时显示的DOM树和引起出错事件之前的DOM树结构。目前已经出现的情况如：异步请求数据时网络错误;访问频率过高遭到服务器屏蔽，目标节点不予显示。

（4）数据格式

剩余内容已隐藏，请支付后下载全文，论文总字数：26391字

您需要先支付 80元 才能查看全部内容！立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;

您可能感兴趣的文章