论文部分内容阅读
摘要：今年是辛亥革命100周年，该文在普通爬虫的技术基础上以主题相关性为核心构建辛亥革命史主题爬虫，从而保证该主题爬虫所搜集网页与辛亥革命主题相关，返回用户所需，做构建辛亥革命主题搜索引擎的前期工作。
关键词：主题搜索引擎；主题爬虫；主题相关性；主题字典
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)13-3009-02
近年来，随着Internet的飞速发展，Web信息以爆炸的方式增长着，人们的身边围绕着各种各样的信息资源，但是这同时也给人们带来了难题，因为从大量类似的信息中获取自己想要的信息不是一件简单的事。搜索引擎技术的出现在很大程度上解决了这个问题，但如何满足用户对快速、准确的获取信息资源的要求，尤其是获取专业领域的信息，这是目前主流搜索引擎的尚未解决的问题。
在这种情况下，针对特定的专业领域提供搜索服务的主题搜索引擎逐步受到人们的青睐。相比传统的搜索引擎，主题搜索引擎只覆盖与特定主题相关的Web区域，这样它搜索的内容可以更深，搜索的周期可以更短。主题搜索引擎的针对性强和专业化的特点使它成为计算机科学界和信息产业界争相研究、开发的对象，国内外专家学者们纷纷对主题搜索引擎的关键技术和实现方案进行了广泛的探索和研究。彭涛在他的博士学位论文中提出了基于链接上下文关系的自适应性主题爬行方法，利用改进的原始微粒群优化算法对网页分类器进行优化组合提高网页分类的精确度，并提出来了增量式索引结构[1]。张岭在他的博士论文里提出了智能WEB信息评价，资源价值标定、分布式图结构索引等WEB数据挖掘的模型，将智能挖掘算法有机的结合到主题搜索引擎中[2]。同时在国外，Rui Chen，Bipin C.Desai，Cong Zhou提出了基于多层检测模型的CINDI聚焦爬虫，最大限度的考虑了WEB页面特征来发现相关主题网页[3]。P.Srinivasan，F.Menczer，G.Pant提出了主题爬虫的主题相关度综合评价框架[4]。
本文的研究问题是在传统爬虫基础上，构造辛亥革命主题词典，利用基于链接内容分析的主题相关度预测方法的爬取策略，构造辛亥革命主题搜索引擎的爬虫模块，为广大历史学家和历史爱好者提供精准的信息服务。
1 研究基础
1.1 构建基于动态主题库的主题词典
1) URL信息
有过网页制作经历的人都知道，在URL中加入提示页面的文字都或多或少是相关主题的信息，来区别其他主题的页面。如历史：history；体育：sports、pingpong、basketball；因此在URL地址中有可能含有與页面主题相关的信息。比如：http：//www.ccnu.edu.cn则表示这是一个教育的链接,反应了主题。
2) 锚文本信息
锚文本实际上就是链接文本，是对页面中的超链接的文字解释。锚文本对该URL所指向的页面起到了概括描述的作用。比如页面中有超链接历史"历史"就是该超链接的锚文本，该子页面包含的内容就很有可能与“历史”有关;辛亥革命百年纪念电影，该锚文本则与主题相关。锚文本是对URL主题相关度预测时一个重要的指标。
3) 父页面与子页面的信息
一个网页中，总会有许多个链接，那么我们就称该页面为父页面，它里边的链接所指向的页面叫做该页面的子页面，如index.html有如下链接指向的页面：information.html，organizatioon.html，news.html，about.html，则这些页面被称为index.html的子页面。根据主题页面的分布规律，index.html与某一主题相关，那么这些子页面与主题相关度也可能很高。
4) 主题字典
动态主题库是由静态主题库和动态主题库而构成，静态主题库在初始过程中由历史领域专家建立，并在抓取过程中保持不变[5]。动态主题库是在网页爬取过程中，根据提取出来的锚文本中和URL中的未知字段构建。
锚文本中未出现在主题库的字段可能是与主题相关的概念的另一种表述，这些信息是主题相关的潜在信息。本文利用Google的blog搜索方法，对未知字段进行查询，提交给Google，在返回的结果列表中，提取前n个结果对应的URL，将这n个URL对应的网页抓取回来，构成一个未知字段ut相关的网页集合X。通过对网页集合X中的网页进行字段统计，得出一个（字段，频率）的列表，根据频率降序排列，从中选取前S个字段，构成未知字段的反馈字段集合T。对T中的每个字段ti,利用同义词进行替换，替换成静态主题库中的词语，构成新的语义层次的相关反馈字段集合ST。为了进一步判断未知字段的主题相关性，利用其对应的相关反馈字段集合ST和动态主题库DTB进行匹配，利用概率计算方法，得出ST和动态主题库DTB的匹配度M(ST,DTKB)，其表达式如式（1）所示。
（1）
利用匹配度M和给定的的阈值δ进行比较，若M＞δ,则ut是与主题相关的，添加到动态主题知识集中；反之，则ut与主题不相关。将动态主题集的字段加入到动态主题库中，更新主题字典。
上述过程不断反复，动态主题库不断增加，动态主题库和静态主题库中的词语一同构成主题字典，主题字典的主题字段越来越丰富。
1.2 基于内容和链接分析的主题相关度预测
下面我们提出了关于计算URL内容相关度的公式：
Wi=β*URL(i)+(1-β)*sim(αi,T) （2）
（3）
（4）
其中Wi是链接i的URL内容相关度度量值，由公式（2）计算可得。URL(i)是链接i的字符串主题相关度得分，由公式（3）计算可得。sim(αi,T)事锚文本与主题的相关度度量值，对锚文本和相关主题建立向量空间模型，由公式（4）计算可得。β为权重因子，取值为0.2，表明URL字符串和锚文本内容这两个因素在公式（1）中所占的比重。
父页面因素体现了对网页的链接分析和锚文本内容分析。因为主题相关度是内容分析的结果，继承父页面的相似度则是链接分析的结果。据此提出了从种子URL到当前URL的链接得分公式：
（5）
其中Li是从当前种子URL到当前URL的链接得分，Wi是链接i的URL内容相关度，有公式（2）计算可得，W(dj)是页面ｉ的父页面dj的ＵＲＬ内容相关度。我们通过设置Li的阈值ε来判定是否将该链接抛弃，用来解决信息孤岛问题。即：
(6)
2 主题爬虫算法设计与实现
本文提出采用的构建基于动态主题库的主题字典和基于内容和链接分析的URL搜索策略是结合从种子URL到当前URL的链接得分来选择辛亥革命历史主题相关页面，使网络爬虫可以穿越隧道找到主题孤岛跳出局部最优点，爬取更多与辛亥革命史主题相关的页面。
算法描述如下：
1）将初始URL文件中的URL集合读入内存放入URL优先级队列，其内容相关度初始值设为1.0；
2）如果还未下载指定个数的页面且URL优先级队列和主题无关队列不为空则转入3），否则转入9）；
3）从优先级队列中取出第一个URL，利用传统爬虫爬取并下载该页面，并把该URL放入已爬行队列中；
4）对上一步爬取的页面进行解析，计算页面文本内容与主题字典中字段的相关度，如果文本内容与主题相关，则索引该页面；提取其中的所有链接（包括URL和锚文本），利用链接中的锚文本，构建动态主题库，判断锚文本中未知字段是否主题相关，从而更新主题字典，然后将链接放入一个新建的临时队列；
5）对临时队列中每一个链接判断该链接是否爬行过，若爬行过转8）；
6）计算Li，如果Li＜ε，转8）；
7）计算Wi，如果Wi＞ε，按其Wi插入URL优先级队列，否则按其Wi插入主题无关队列；
8）转2）；
9）退出。
此算法的主要思想是：利用URL初始集合抓取网页内容，然后解析网页内的URL和链接，根据网页URL和锚文本与主题的相似度，确定下一步将要被抓取的URL，过滤与主题不相关的URL。每抓取一个页面，便分析其中的链接锚文本动态更新主题字典。通过初始的URL尽可多的抓取与主题相关的网页集合进行索引。
3 实验分析
在本機环境下，初始URL为大型历史网站，百度，谷歌，分别分析了1000个URL，2000个URL，10000个URL，实际爬行的网页数目分别为58,102,300个，URL数目越多，被过滤掉的网页数目越多，而真正的主题相关URL并不是太多。
4 结束语
本文在主题爬虫基础上，结合动态主题库技术和基于内容和链接分析的URL搜索策略，构造辛亥革命史的主题爬虫。接下来准备将改进开源搜索引擎Nutch爬行策略，实现本主题搜索引擎全部功能。
参考文献：
[1] 彭涛.面向专业搜索引擎的主题爬行技术研究[D].吉林:吉林大学,2007.
[2] 张岭.智能信息检索中的Web挖掘研究[D].上海:上海交通大学,2002.
[3] RuiChen,BIPinC.Desai,CongZhou.CINDIRobot：an Intelligent Web Crawler Based on Multi-level InsPeetion[C].Database Engineering and APPlications SymPosium,2007.IDEAS 2007.11th International 6-8 SePt,2007:93-101.
[4] Srinivasan P,Menczer F,Gpant.A General Evaluation Framework for ToPical Crawlers[J].ACM SIGIR Conference on Research and DeveloPment in Information Retrieval,2005,8(3):417-447.
[5] 金明珠,丁岳伟.基于动态主题库的主题爬虫[J].计算机应用,2009(12).
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
关键词：主题搜索引擎；主题爬虫；主题相关性；主题字典
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)13-3009-02
近年来，随着Internet的飞速发展，Web信息以爆炸的方式增长着，人们的身边围绕着各种各样的信息资源，但是这同时也给人们带来了难题，因为从大量类似的信息中获取自己想要的信息不是一件简单的事。搜索引擎技术的出现在很大程度上解决了这个问题，但如何满足用户对快速、准确的获取信息资源的要求，尤其是获取专业领域的信息，这是目前主流搜索引擎的尚未解决的问题。
在这种情况下，针对特定的专业领域提供搜索服务的主题搜索引擎逐步受到人们的青睐。相比传统的搜索引擎，主题搜索引擎只覆盖与特定主题相关的Web区域，这样它搜索的内容可以更深，搜索的周期可以更短。主题搜索引擎的针对性强和专业化的特点使它成为计算机科学界和信息产业界争相研究、开发的对象，国内外专家学者们纷纷对主题搜索引擎的关键技术和实现方案进行了广泛的探索和研究。彭涛在他的博士学位论文中提出了基于链接上下文关系的自适应性主题爬行方法，利用改进的原始微粒群优化算法对网页分类器进行优化组合提高网页分类的精确度，并提出来了增量式索引结构[1]。张岭在他的博士论文里提出了智能WEB信息评价，资源价值标定、分布式图结构索引等WEB数据挖掘的模型，将智能挖掘算法有机的结合到主题搜索引擎中[2]。同时在国外，Rui Chen，Bipin C.Desai，Cong Zhou提出了基于多层检测模型的CINDI聚焦爬虫，最大限度的考虑了WEB页面特征来发现相关主题网页[3]。P.Srinivasan，F.Menczer，G.Pant提出了主题爬虫的主题相关度综合评价框架[4]。
本文的研究问题是在传统爬虫基础上，构造辛亥革命主题词典，利用基于链接内容分析的主题相关度预测方法的爬取策略，构造辛亥革命主题搜索引擎的爬虫模块，为广大历史学家和历史爱好者提供精准的信息服务。
1 研究基础
1.1 构建基于动态主题库的主题词典
1) URL信息
有过网页制作经历的人都知道，在URL中加入提示页面的文字都或多或少是相关主题的信息，来区别其他主题的页面。如历史：history；体育：sports、pingpong、basketball；因此在URL地址中有可能含有與页面主题相关的信息。比如：http：//www.ccnu.edu.cn则表示这是一个教育的链接,反应了主题。
2) 锚文本信息
锚文本实际上就是链接文本，是对页面中的超链接的文字解释。锚文本对该URL所指向的页面起到了概括描述的作用。比如页面中有超链接历史"历史"就是该超链接的锚文本，该子页面包含的内容就很有可能与“历史”有关;辛亥革命百年纪念电影，该锚文本则与主题相关。锚文本是对URL主题相关度预测时一个重要的指标。
3) 父页面与子页面的信息
一个网页中，总会有许多个链接，那么我们就称该页面为父页面，它里边的链接所指向的页面叫做该页面的子页面，如index.html有如下链接指向的页面：information.html，organizatioon.html，news.html，about.html，则这些页面被称为index.html的子页面。根据主题页面的分布规律，index.html与某一主题相关，那么这些子页面与主题相关度也可能很高。
4) 主题字典
动态主题库是由静态主题库和动态主题库而构成，静态主题库在初始过程中由历史领域专家建立，并在抓取过程中保持不变[5]。动态主题库是在网页爬取过程中，根据提取出来的锚文本中和URL中的未知字段构建。
锚文本中未出现在主题库的字段可能是与主题相关的概念的另一种表述，这些信息是主题相关的潜在信息。本文利用Google的blog搜索方法，对未知字段进行查询，提交给Google，在返回的结果列表中，提取前n个结果对应的URL，将这n个URL对应的网页抓取回来，构成一个未知字段ut相关的网页集合X。通过对网页集合X中的网页进行字段统计，得出一个（字段，频率）的列表，根据频率降序排列，从中选取前S个字段，构成未知字段的反馈字段集合T。对T中的每个字段ti,利用同义词进行替换，替换成静态主题库中的词语，构成新的语义层次的相关反馈字段集合ST。为了进一步判断未知字段的主题相关性，利用其对应的相关反馈字段集合ST和动态主题库DTB进行匹配，利用概率计算方法，得出ST和动态主题库DTB的匹配度M(ST,DTKB)，其表达式如式（1）所示。
（1）
利用匹配度M和给定的的阈值δ进行比较，若M＞δ,则ut是与主题相关的，添加到动态主题知识集中；反之，则ut与主题不相关。将动态主题集的字段加入到动态主题库中，更新主题字典。
上述过程不断反复，动态主题库不断增加，动态主题库和静态主题库中的词语一同构成主题字典，主题字典的主题字段越来越丰富。
1.2 基于内容和链接分析的主题相关度预测
下面我们提出了关于计算URL内容相关度的公式：
Wi=β*URL(i)+(1-β)*sim(αi,T) （2）
（3）
（4）
其中Wi是链接i的URL内容相关度度量值，由公式（2）计算可得。URL(i)是链接i的字符串主题相关度得分，由公式（3）计算可得。sim(αi,T)事锚文本与主题的相关度度量值，对锚文本和相关主题建立向量空间模型，由公式（4）计算可得。β为权重因子，取值为0.2，表明URL字符串和锚文本内容这两个因素在公式（1）中所占的比重。
父页面因素体现了对网页的链接分析和锚文本内容分析。因为主题相关度是内容分析的结果，继承父页面的相似度则是链接分析的结果。据此提出了从种子URL到当前URL的链接得分公式：
（5）
其中Li是从当前种子URL到当前URL的链接得分，Wi是链接i的URL内容相关度，有公式（2）计算可得，W(dj)是页面ｉ的父页面dj的ＵＲＬ内容相关度。我们通过设置Li的阈值ε来判定是否将该链接抛弃，用来解决信息孤岛问题。即：
(6)
2 主题爬虫算法设计与实现
本文提出采用的构建基于动态主题库的主题字典和基于内容和链接分析的URL搜索策略是结合从种子URL到当前URL的链接得分来选择辛亥革命历史主题相关页面，使网络爬虫可以穿越隧道找到主题孤岛跳出局部最优点，爬取更多与辛亥革命史主题相关的页面。
算法描述如下：
1）将初始URL文件中的URL集合读入内存放入URL优先级队列，其内容相关度初始值设为1.0；
2）如果还未下载指定个数的页面且URL优先级队列和主题无关队列不为空则转入3），否则转入9）；
3）从优先级队列中取出第一个URL，利用传统爬虫爬取并下载该页面，并把该URL放入已爬行队列中；
4）对上一步爬取的页面进行解析，计算页面文本内容与主题字典中字段的相关度，如果文本内容与主题相关，则索引该页面；提取其中的所有链接（包括URL和锚文本），利用链接中的锚文本，构建动态主题库，判断锚文本中未知字段是否主题相关，从而更新主题字典，然后将链接放入一个新建的临时队列；
5）对临时队列中每一个链接判断该链接是否爬行过，若爬行过转8）；
6）计算Li，如果Li＜ε，转8）；
7）计算Wi，如果Wi＞ε，按其Wi插入URL优先级队列，否则按其Wi插入主题无关队列；
8）转2）；
9）退出。
此算法的主要思想是：利用URL初始集合抓取网页内容，然后解析网页内的URL和链接，根据网页URL和锚文本与主题的相似度，确定下一步将要被抓取的URL，过滤与主题不相关的URL。每抓取一个页面，便分析其中的链接锚文本动态更新主题字典。通过初始的URL尽可多的抓取与主题相关的网页集合进行索引。
3 实验分析
在本機环境下，初始URL为大型历史网站，百度，谷歌，分别分析了1000个URL，2000个URL，10000个URL，实际爬行的网页数目分别为58,102,300个，URL数目越多，被过滤掉的网页数目越多，而真正的主题相关URL并不是太多。
4 结束语
本文在主题爬虫基础上，结合动态主题库技术和基于内容和链接分析的URL搜索策略，构造辛亥革命史的主题爬虫。接下来准备将改进开源搜索引擎Nutch爬行策略，实现本主题搜索引擎全部功能。
参考文献：
[1] 彭涛.面向专业搜索引擎的主题爬行技术研究[D].吉林:吉林大学,2007.
[2] 张岭.智能信息检索中的Web挖掘研究[D].上海:上海交通大学,2002.
[3] RuiChen,BIPinC.Desai,CongZhou.CINDIRobot：an Intelligent Web Crawler Based on Multi-level InsPeetion[C].Database Engineering and APPlications SymPosium,2007.IDEAS 2007.11th International 6-8 SePt,2007:93-101.
[4] Srinivasan P,Menczer F,Gpant.A General Evaluation Framework for ToPical Crawlers[J].ACM SIGIR Conference on Research and DeveloPment in Information Retrieval,2005,8(3):417-447.
[5] 金明珠,丁岳伟.基于动态主题库的主题爬虫[J].计算机应用,2009(12).
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文