1系统结构
本文提出基于链接回溯的地理信息更新主题爬虫方法，以广度优先通用爬虫方法为基础，针对现有主题爬虫算法在实际应用中的缺陷，引入回溯的思想，根据新闻网站的结构特点，计算出最有可能包含主题相关信息的链接方向，从而大幅提高爬取效率，获取更多与主题相关的信息。系统整体流程分为两个阶段，如图1所示：第一阶段以初始种子链接为基础，使用基于SVM分类的加权爬取算法，先指定某一层的链接为父链接组，然后以广度优先的方式进行网页爬取，在这个过程中使用SVM分类模型，逐条验证链接信息，找出分类准确的链接在之前指定层数的父链接，令该父链接权值增加，整个过程完成后，统计权值较高的父链接作为优化种子链接；第二阶段以优化种子链接为基础，利用基于知识库判别的爬取算法以广度优先的方式进行网页爬取，使用知识库逐条验证链接信息，判断并确定地理信息更新内容的主题，最后将优化种子链接和主题相关网页文档存入数据库，作为今后爬取的经验参考。
2算法介绍
2.1基于SVM分类的加权爬取算法
2.1.1SVM分类模型
支持向量机(SupportVectorMachine,SVM)是目前分类性能最好的模型之一，本文采用支持向量机进行事件类型判断。从地理信息变化要素知识库(详见3.2.1节)中选择几种最常见的特征词汇作为类型关键词，以这些特征词汇及其对应的典型要素为基础收集样本文档，使用支持向量机方法进行样本机器学习，以特征词汇和典型要素作为触发词，在不影响分类精度的情况下提高分类效率，最终通过机器学习得到一个分类模型。当判断一条链接包含的消息是否属于主题相关的范畴时，由于标题往往是一个文档包含信息最好的总结，故先判断这条标题中是否含有之前选择的特征词汇之一，如果包含，则对这条链接的正文部分使用SVM分类模型进行分类，如果分类得出的结果与标题中包含的特征词汇一致，则证明了这条链接中确实包含该特征词汇所代表的主题相关内容。这种基于机器学习和触发词的分类方法相比于单纯的字符匹配，可以避免字符一致但语意出现歧义的现象，并且有较高的准确率，是一种快速有效的主题相关度判别方法。系统第一阶段是对网站所包含主题信息位置的一种试探，由于SVM分类性能有限，只能判断一篇文本是否属于某一特征词汇所代表地理信息范畴，无法最终确定以特征词汇和对应典型要素作为主题的内容，所以只选择几种最常见的特征词汇作为分类关键词，作为是否对父链接加权的依据。
2.1.2算法描述
爬取过程采用广度优先的爬取策略，处理中的链接分为两个队列：待爬取队列(Uncrawled)和已爬取队列(Crawled)；首先将种子链接集(Seed)加入待爬取队列，然后解析待爬取队列中链接的源代码，获得下一层超链接组，对下一层超链接组进行去重并去除已爬取过的链接，接着将待爬取队列加入已爬取队列中，下一层超链接组加入待爬取队列中，最后再次解析待爬取队列，重复上述过程，直至达到指定条件。广度优先爬虫从种子链接出发，以层数为单位进行爬取。加权算法思想是将第S层链接指定为父链接组，其中每条链接初始权值为0，F为最大爬取层数；在网页爬取的过程中，对第S+1层至第F层的链接调用3.1.1节中提到的SVM分类模型进行验证，如果分类结果正确，则证明这条链接包含一定程度的主题相关信息，那么其父链接所指向的方向，就有可能包含更多与主题相关的信息，所以找到这条链接在S层的父链接，令其权值加1；爬取过程结束后，统计第S层所有父链接的权值，选择权值最大的K条链接作为优化种子链接。这些链接相比于初始种子链接，指向主题相关内容的可能性更大，从而提高了整体爬取效率和准确性。S、F、K的取值可以根据实际网站规模和结构进行调整。本算法的伪代码如算法1所示。
2.2基于知识库判别的爬取算法
2.2.1知识库判别方法
本文的应用方向是针对地理信息变化的检测，在参考《GBT13923-2006基础地理信息要素分类与代码》中分类标准的基础上，对各类别的特征词汇和典型要素进行了总结，形成一个特征词汇对应多个典型要素的地理信息变化要素知识库；表达形式以特征词汇和典型要素两个关键词的组合来表示，例如：路+拓宽，路+通车，河+截流等，以此判断一个文本的内容是否属于地理信息范畴，并确定该文本的主题。具体步骤如下：(1)将待处理的网络文本进行分句并编号；(2)利用ICTCLAS分词软件对所有句子进行分词；(3)从第一句开始，检查被标记为动词的词汇是否属于特征词汇集，如果匹配，则以该动词为中心，以词汇距离从近到远的顺序遍历所有被标记为名词的词汇，参照知识库中的特征词汇和典型要素匹配关系，如果配对成功，将该名词和动词作为组合抽取并记录；(4)遍历所有句子，找出所有满足条件的组合。其中，步骤(3)中的提到的关键词匹配方法，过程例如图2所示。需要处理的语句是“郑州彩虹桥隧道5月通车将成北区新交通枢纽”，后缀为“/n”代表名词，“/v”代表动词，首先找到动词“通车/v”并与知识库中的典型要素进行匹配，成功后以“通车/v”为中心，以词汇距离从近到远的原则分别向左右两个方向寻找名词，向右找到名词“区/n”后，将“区+通车”与知识库进行匹配后失败，向左找到名词“隧道/n”后，将“隧道+通车”与知识库进行匹配后成功，因此停止寻找并抽取出“隧道+通车”的关键词组合作为这一句话的主题内容。
2.2.2算法描述
爬取算法依然采用广度优先的爬取策略，对爬取到的每条链接使用3.2.1节中的知识库判别方法，确定相关信息的主题内容，保存网页文档。
3实验测试与性能分析
利用前文介绍的方法，使用适合网络编程的Java语言实现了基础地理信息更新检测原型系统，以新浪、网易和腾讯等主流新闻网站作为初始种子链接进行测试。分词工具使用中科院设计开发的ICTCLAS分词软件，机器学习使用目前最广泛应用的LIBSVM工具，由于实验设备和网络条件有限，回溯过程中设置初始层S=1，爬取最大层数F=4，回溯后取权值最大的K=2条链接作为优化种子链接。图3展示了两种爬虫在爬取相同数量(10000条)链接的情况下的整体效率，因为回溯之后再爬取是一个重复的过程，也就是为了计算出优化种子链接而付出的代价，所以比较两种爬虫的整体效率是为了检测这个重复过程对于整体效率的影响。从图3可以看出由于回溯过程，系统整体效率确实受到了一定的影响，但依旧好于通用的方法，并且在找出一个网站的优化种子链接后，今后对于该网站的爬取就可以直接使用优化种子链接，不再需要进行回溯的过程，所以从总体上来看，回溯方法造成的效率影响是可以接受的。同样在爬取相同数量(10000条)链接的情况下，正如之前所说的，如果不是第一次对某网站进行爬取，那么可以直接使用通过回溯后得到的优化种子链接为基础，如图4所示，这样找到的主题相关信息明显多于通用方法；结合图3和图4的实验结果可以证明通过本文提出的回溯方法，确实可以分析出一个网站中最有可能包含主题相关信息的链接方向，从而大大提高爬取效率，减少低效率的爬取过程，从实验结果可以看出该方法在各类新闻网站中都具有广泛的可用性，在其他主题方向也具有一定的推广性。
4结束语
主题网络爬虫能够针对用户需求，有效地进行特定主题的信息检索。本文在现有爬取策略和主题相关度算法的基础上，提出一种基于链接回溯的地理信息更新主题爬虫方法，通过实验证明了本方法确实可以提高爬取效率，设计并实现了基础地理信息更新检测原型系统，该系统适合于在新闻类网站中寻找地理信息更新的消息，后续研究可以考虑在其他主题方向的应用，以及减少回溯过程的代价来提升效率的方法。
作者：吴家皋 余浩 张雪英 单位：南京邮电大学 江苏省无线传感网高技术研究重点实验室 南京师范大学
