[高效的动态脚本网页关联性挖掘算法研究]关联性思维
时间：2019-04-20 03:16:02 来源：柠檬阅读网 本文已影响 人 
摘要：由于动态脚本网页更多地采用脚本方式与用户交互，缺乏足够的链接信息，传统的公共搜索引擎仅通过基于链接分析的算法很难实现对此类网页关联性的一个高效挖掘，因为Web上的网页链接无法到达其内部内容。对这些网页的信息挖掘仍处在起步阶段，提出了一个此类文档关联信息的搜索方案，将动态脚本网页每一次加载产生的页面作为一个状态，以状态为信息挖掘的基本单位，就此描述了基于状态关联度匹配的动态脚本网页的分析算法。此外，具体给出了算法并行实现的步骤流程并通过实验证明了算法的效率。
关键词：动态脚本；状态关联度匹配；状态转换；排序；关联信息
中图分类号：TP271文献标识码：A文章编号：1009-3044(2012)13-3002-04
An Algorithm Study of Information Mining on Web Pages with Dynamic Scripts
TAN Tao
(School of Computer, China West Normal University, Nanchong 637002, China)
Abstract: The current search engines can not rank well when searching for web pages with dynamic scripts, because there is not enough hyperlink information. Traditional public search engines are implemented by the hyperlink analysis algorithms. It is hard to realize the efficient searching for these related pages. This paper proposes a new searching approach based on traditional search engines and presents its framework of this approach. When loading a new page, a state is considered as a basic unit of ranking. Then, the paper presents a ranking algorithm based on state-interrelated similarity of these pages. Finally, the paper describes implementing process of the algorithm, and demonstrates the efficiency of the algorithm by experimental results.
Key words: dynamic scripts; state-interrelated similarity; state transition; ranking; related information searching
随着互联网的不断发展，人们越来越多地在互联网上发布和获取信息。Web已经成为信息制造、发布、加工和处理的主要平台。目前主流的搜索引擎普遍提供的服务是通过提交查询词来搜索与某主题相关的网页，在这些搜索引擎中，利用了以PageRank、HITS为代表的链接分析算法，通过网页间建立的超链接拓扑结构信息来计算网页的排序。它的基本出发点是通过对大规模网页的链接信息的统计，给网页赋予一个量化的价值度，然后按照得到高价值度的网页进行排序，将结果返回给查询用户。
然而，随着Web2.0应用的推广，越来越多的网站采用了动态脚本方式与用户交互，其中就包括了AJAX技术，使用这种技术的网页文档就没有足够的链接信息，URL不再是页面的唯一标识，对AJAX应用而言，多页面可以共享一个URL。内部的重要内容则是通过执行客户端脚本（如JAVASCRIPT）从web服务器加载，每执行一次加载，这时的页面内容就会发生改变。由此看来，动态脚本网页的页面跳转不仅是由链接来控制，很大程度上，可以由任意的页面元素上触发的各种事件来引起页面的跳转。那么传统的基于链接拓扑结构的链接分析算法则不再适用于对动态脚本网页的分析排序。在搜索动态脚本网页的关联信息时，目前的搜索引擎不能对其内部信息进行较好的发现。
1相关工作
动态脚本网页的关联性挖掘是一个比较新的领域。文献[1]就目前链接结构分析的最新研究进展和应用情况作出了介绍，并对其在Web信息搜索，潜在信息发现等方面的实际应用作出了综述；文献[2]提出了一种动态脚本网站页面内容的获取方法，提出了对动态脚本网站建立状态转换图模型来描述，通过规约出需触发事件的页面元素按XPATH特征及需触发的事件类型，利用该结果抓取信息的方法。文献中提到的状态转换图，强调了转换的过程，但未对状态进行详尽描述；文献[3]介绍了对类似动态脚本网页链接信息较少文档的爬取，阐述了基于网页搜索结果聚类的文档排序算法。将聚类技术应用于此类文档的排序算法中,对AJAX应用的爬取来说，需要一个高性能的爬虫,如何利用聚类技术从爬取日志中挖掘规则以提高爬取效率是值得思考的。该文在动态脚本网页关联信息挖掘上所做的工作有：1.由于在动态脚本网页中，URL不是唯一标识，于是为网页的每一次加载建立状态信息表，每一个不同状态作为分析的基本单位。2.提出了一个基于动态脚本网页关联信息的搜索方案，并重点描述了一个基于状态关联度匹配的动态脚本网页的分析挖掘算法StaS。
2基本原理
由于动态脚本网页缺乏足够的链接信息，很多的页面转换是通过脚本的函数触发的，因此对此类网页关联性的挖掘仅通过基于链接分析的算法很难实现一个高效的分析挖掘，因为Web上的网页无法链接到其内部内容。该文给出了一个此类文档关联信息的搜索方案，重点描述了一个基于状态关联度匹配的动态脚本网页的分析算法。在AJAX应用中,每执行一次动态客户端脚本，在URL保持不变的情况下，用户获得了新的页面内容，如同这些应用为用户展示了一个新的状态，因而，使用一个URL区分链接目标来表示一个文档的方式不再适合，更为恰当的方式是将动态脚本网页文档表示为多个状态，不同的状态也对应于不同的页面内容。在这里，为了便于讨论，我们把状态定义为用户操作后向用户呈现的内容。为了能够实现对动态脚本网页的高效挖掘，新的搜索方案必须以文档状态为最小的检索单位。同时，根据对用户的搜索习惯分析，网页搜索结果与动态脚本网页的主题分布一般能保持较好的一致性，因此本文采取这样的策略来解决问题：首先，给定查询，进行基于公共搜索引擎搜索结果的信息查找，然后再根据动态脚本网页的页面状态信息关联度进行计算，其计算得到的值再进行排序。下面是对新的搜索方案的描述，其框架图如图1所示。和传统搜索引擎类似，也分为在线和离线两部分的实现。离线部分包括对动态脚本网页的抓取和排序，在线部分则包括文档检索和排序部分。
2.1公共搜索引擎搜索
现在以GOOGLE为代表的搜索引擎能够很好对静态网页进行搜索。给定一个查询，一个网页越重要或受欢迎，其价值度就越高，排名就越靠前。排名靠前的网页主题阐述了该查询在互联网上的主题。因此，利用高质量的网页搜索结果来改善动态脚本网页的关联网页的排序是可行的，一个直接的办法就是利用公共搜索引擎进行最初的文档筛选，后面的工作则在此基础上进行。
图1搜索方案框架图
2.2爬取文档
在AJAX应用中，必须通过内部链接或者客户端脚本来请求内容。给定初始的URL地址，爬虫模拟用户行为，触发每一个用户可能触发的事件来不断地爬取动态应用中的全部内容。在这里，每触发一个事件，爬虫就获得应用的一个新状态。在此过程中，爬虫最困难的任务是如何检查一个重复的状态。在爬取AJAX应用的过程中，客户端向服务器发出的请求是动态生成和执行的。这就使得要识别重复状态就必须能理解应用的脚本逻辑。在此，我们使用一个专门的AJAX爬虫，该爬虫通过对AJAX的脚本分析，获得AJAX脚本的调用关系图，然后对发生网络连接的HOT函数节点的参数进行监控和缓存，成功实现了对重复状态的检测，大大提高了爬虫的爬取效率[4-5]。
2.3建立索引
由于文档状态是搜索的基本单位，在建立索引文件时需要对传统的倒排索引文件（Inverted File List）进行扩展，以状态为基本单位建立索引。主要的三个数据结构如下：文档表存储了文档编号（DocID）、文档的URL和该URL所包含的不同状态数（SNum）；状态表则记录了状态的基本信息，包括状态编号（StateID）、长度(length)、内部链接地址(Inner-URL)和在文档中的内部权值(Inner-Score);倒排索引文件则包括了词项、状态编号、权重和位置。同时，页面的变化意味着状态的转换，我们通过一个有向图来描述这个动态的转换过程。一个二元组G=,V表示状态，E表示触发页面元素上的事件实现的页面改变（即状态变化）。V表示状态集合，V={v1,v2,..vn}；E表示状态间变化的集合，Ei->j表示状态vi到vj间的一个变化。
2.4查询输出
给定的用户提交的查询，首先是将查询提交到公共网页搜索引擎中，同时，对AJAX应用的文档进行爬取，并就状态进行索引，然后从状态索引文件中读取相关主题的状态，最后，将状态信息与之前的搜索结果按照关联度匹配算法对网页文档进行排序输出。
3关键算法
基于以上思想，该文提出了基于状态关联度匹配的动态脚本网页的分析算法StaS。为便于描述挖掘关联网页算法的流程，首先介绍以下定义：
定义1在状态转换有向图G中，页面状态变化定义为如下几种：
a)In(vi):状态vi的入度集合，即指向vi的状态{ vj|Ej->i∈E}；
b)Out(vi):状态vi的出度集合，即vi指向的状态{vj|Ei->j∈E}；
c)Co-In(vi):状态vi的联合引用集合，{vj|vi≠vj∧Ek->i∈E∧Ek->j∈E}；
d)Co-Out(vi):状态vi的联合引用集合，{vj|vi≠vj∧Ei->k∈E∧Ej->k∈E}。
定义2任意的两个状态vi和vj被状态v联合引用，当且仅当它们都被状态v所指向或都指向状态v(即定义1中的c,d描述项)。v表示v上一个联合引用对,sim()表示v间的关联度。如果vi,vj不是v上的一个联合引用对，则令sim()=0。
由上述定义，不难看出sim()实际记录了两个状态共同被其他状态所指向的数目和两个状态共同指向其他状态的数目。对于每个联合引用对，我们将结合状态的关联位置信息来计算它们的关联度，其他的一些有用信息（如状态的相关属性等）也将被记录。状态转换图G将一个状态与其他状态联系在一起，形成结构化特征的状态链，状态链是两个或两个以上的状态结点通过转换边顺次相连构成的一条路径，记作P={v0e0v1e1…vn-1en-1vn}从状态链来看，状态vi与vj之间的关联强度与vi、vj的相对位置关系有密切联系。一个状态vi的最邻近的几个状态，往往与其的主题的相似程度较高。基于这一理论，v的位置关联度由如下公式计算:
公式中i,j表示vi与vj在P中的位置序号，近邻阈值是位置关系的分界点。
定义3对于任意两个状态vi和vj，定义从vi到vj的路径内关联度PSimv(vi->vj)，类似的，从vj到vi的路径内关联度为PSimv(vj->vi)。
PSimv(vi->vj)的值是通过累加所有在POSV()中的联合引用对的关联度得到的，但在累加过程中有如下的限制:为避免某些恶意页面为两个状态贡献过高的关联度，使得本不相关的两个状态具有较高的关联度。PSimv(vi->vj)的最大值也需要限制，使其最大不超过N，即关联度的最大阈值。
PSimv(vi->vj)=min(N,∑
POSV())（2）
算法流程：Input:查询q,一个公共搜索引擎E Output:一个已排序的动态脚本网页序列J（q）
(1)将查询q提交到搜索引擎E，返回的前n个网页记为D(q)={d1,d2,…,dn}；(2)在(1)的结果中，将查询提交到WS获得包含所有包含q的状态页面构成的集合记为S(q)={s1,s2,…,sn}；(3)就(2)获得的关联隐含状态si，根据StaS算法，对状态si∈S(q)计算其关联度值；(4)根据关联度值进行降序排序J(q)，将结果返回。
4算法实现及结果分析
由于整个算法包含了较多的启发性经验公式，为了给公式的各参数阈值作出一个合理的取值，我们综合了具体统计数据的分析和经验估计的结果。近邻阈值l，通过对部分动态脚本网站的事件模拟测试分析，发现多数网站的状态变化数都小于5，因此在本实验中，l的取值为4。路径关联度阈值N，经过对路径内进行取样，发现仅有6%的路径内关联度会大于8,因此在本实验中，N的取值为8。总关联度阈值T,为避免过低总关联度的状态页面也会进行排序输出，在实验中，T的取值是2.0，低于该阈值的关联状态将被丢弃。为验证StaS算法的对动态脚本网页信息的挖掘能力，我们在单机上进行了模拟实验，使用JAVA程序实现了该算法，选择了20个查询，实验与直接使用公共搜索引擎的实验结果进行了比较。20个查询分属于10个不同的主题，包括了文学、科技、企业等，对于每一次查询，两种实现生成的前30个排名由5名测评人员一起对其产生的结果进行判断。判断策略：排名中关联动态网页数量的比较,即分别对30个排名中属于同一动态脚本网站的结果进行累加。
图2新算法与传统引擎实现的对比结果
图2所示为两种实现的比较结果。可以看到，在关联精度上前3个结果比较接近，但引入更多的结果进行测评后，精度差逐渐扩大；而在关联动态网页数量的比较上，引入StaS算法后的搜索明显比传统搜索引擎的数量要多，说明对动态脚本网页的信息挖掘要优于公共搜索引擎。
5总结及进一步的研究
本文在动态脚本网页关联信息挖掘上，为动态脚本网页中同一URL范畴下的页面变化建立了对应状态信息表，就其状态转换过程建立了状态链，将每一个不同状态作为信息分析的基本单位，并就此提出了一个基于动态脚本网页关联信息的搜索方案，重点描述了一个基于状态关联度匹配的动态脚本网页的分析挖掘算法StaS。实验证明，与传统公共搜索引擎对动态脚本网页的信息挖掘相比，该文给出的解决方案具有明显的优势，大幅提高了对此类网页关联信息的网页的搜索数量。
参考文献:
[1]夏冰,高军,王腾蛟,杨冬青.一种高效的动态脚本网站有效页面获取方法[J].软件学报,2009(20):176-183.
[2]王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].软件学报,2003(14):1768-1780.
[3]周翀.搜索引擎中文聚类方法研究[D].武汉:华中科技大学,2009.
[4] Duda C,Frey G,Kossmann D,Matter R,Zhou C, AJAX Crawl:Making AJAX Applications Searchable[C],上海, IEEE Computer Society第25届国际数据工程会议,2009: 78-89.
[5] Duda C,Frey G,Kossmann D,etal. AJAX Search:crawling,indexing and searching web 2.0 applications[C], Endow,Proc.VLDB.2008: 1440-1443.
[6] Lin,Z,King I,Lyu MR.PageSim:A novel link-based measure of web pages similarity[C].香港,IEEE Computer Society第15届万维网国际会议,2006:1019-1020.
[7] Sadi,M S,Rahman M M H,Horiguchi S.A new algorithm to measure relevance among web pages[C].Prague, WIT Press第7届国际数据挖掘和信息工程会议,2006:243-251.
[8]方启明,杨广文.基于P2P的Web搜索技术[J].软件学报,2008(19):2706-2719.
