[主题爬行策略与算法研究综述] 贪心算法经典例题

　　[摘要]主题爬行是专业搜索引擎的基础，爬行策略与爬行算法是主题爬行技术的核心，通过分析主题爬行的基本原理，对爬行策略与爬行算法进行分类比较，展示爬行策略与爬行算法的研究进展及当前研究热点，为主题爬行技术的进一步研究提供参考。
　　[关键词]搜索引擎　主题爬行　爬行策略　爬行算法
　　[分类号]TP391
　　
　　搜索引擎技术自诞生之日起就成为互联网中最吸引人的技术之一，各种商业化的搜索引擎已经成了人们使用互联网时不可缺少的工具。传统搜索引擎的工作原理是服务提供商利用网络爬虫(Web crawler，也被称作网络蜘蛛(Web spider)或网络机器人(robot)，通过一些种子站点按照深度优先或者广度优先的搜索策略对可以爬行到的资源进行扫描、下载，并将下载的信息以快照或全文方式存储在数据库中，建立相关索引，当用户在搜索引擎的用户界面中输入搜索关键字后，搜索引擎访问数据库，返回数据库中与搜索关键字匹配的纪录。随着互联网中网页资源的快速增长，传统的搜索引擎在某些方面的缺陷也越来越明显：①搜索结果不够全面。传统搜索引擎希望镜像整个Web世界，搜索引擎追求的是尽量多的处理及存储网络爬虫爬回的网页，但不同的搜索引擎由于受到服务器位置、网络带宽、爬行算法、服务器容量等因素的影响，服务器中存储的资源是有限的，任何一个搜索引擎不可能存储并索引网络上所有的网页信息。即使是全球最大的搜索引擎Google，其索引的页面数量也仅占Web总量的40％左右。②搜索周期增加，影响信息的实效性。随着Web资源的快速增长，传统搜索引擎网络爬虫的爬行周期不断增加，数据库更新时间越来越长。每一个网页都有自己的生命周期，网页的更新速度可能会快于搜索引擎数据库的更新速度，当搜索引擎把数据库中已经过期的信息反馈给用户时，用户可能根本无法打开相关链接或者打开的是过期的网页。③搜索结果的针对性不强。用户输入一个关键字后返回很多结果，但存在大量重复，很多结果并不是用户需要的。通过对欧洲和美国9个主要的搜索引擎日志的统计分析，认为用户对于搜索结果的查看呈减少趋势。普通用户仅仅会察看搜索引擎返回的前若干条数据，对于其他搜索结果，很多用户没有耐性全部看完。不同专业背景的人，对于同一个关键词的理解可能大相径庭，同样的“苹果”一词，有人可能理解成为食品，有人可能理解成为苹果公司或者其IT产品。
　　鉴于传统搜索引擎的这些缺陷，一些学者提出了垂直式搜索引擎的概念，即该搜索引擎不以爬行所有的Web页面为目标，仅仅在互联网中快速爬行某一部分Web页面并存储，这样的搜索引擎既可以节约网络带宽资源，又可以缩短搜索引擎数据库的更新周期，使搜索引擎得到实时性更好的网页。De Bra等最先提出的主题爬行(topic crawling)搜索引擎通过限定爬行主题，提高了搜索精度，成为垂直式搜索引擎的代表。主题爬行技术的核心是爬行策略与算法，本文从主题爬行技术的基本原理出发，对其策略进行分类，沿着爬行策略及算法的改进，分析了主题爬行策略与算法的研究热点，为主题爬行技术的进一步研究提供参考。
　　
　　1　主题爬行原理
　　
　　主题爬行是在传统网络爬行技术基础上，加入文本分类、聚类以及Web挖掘等相关技术用于捕获特定主题的Web信息。主题爬行技术的应用可以提高搜索精度，降低搜索引擎对网络资源的占用，缩短搜索引擎数据库的更新周期。基于主题爬行技术的搜索引擎与传统搜索引擎最大的区别在于：该搜索引擎的网络爬虫是面向主题的。传统搜索引擎的网络爬虫在爬行过程中采用的是“通吃”策略，不分类别、不分内容全部爬行并下载；基于主题的网络爬虫在爬行前或者爬行过程中根据已经爬行的结果有选择性的进行预测下一步爬行并下载。
　　主题爬行过程通常由三部分构成：①分类器(clas―sifter)，主要对已抓取网页的元素进行计算，判断其主题相关度，确定是否对该网页中所包含的超级链接进一步抓取；②提取器(distilIer)，该模块存储待下载队列，并确定待下载队列的优先级；③爬行器(crawler)，该模块在分类器和提取器的指导下，执行网页抓取工作。主题爬虫的爬行过程为爬行器根据不同的爬行策略执行爬行操作，抓取网页送人分类器中，分类器对已经抓取的网页进行处理，根据设定主题及其域值判断该网页的主题相关性，结合其他参数，确定是否对该网页包含的超级链接进一步爬行。如果爬行，则送入提取器中的队列，由提取器根据队列规则确定其爬行优先极。Chakrabarti等人 1999年正式提出了个性化主题搜索引擎的概念，该搜索引擎不以传统的关键词作为搜索内容，而是在某一限定范围内，通过计算Web页面内容与主题的相关性，决定主题爬虫是否值得进一步搜索。其中，主题是由一些范例文档来确定的，该主题爬虫实时查找与文档词典有相关性的网页，保证了搜索页面的时效性与针对性。
　　
　　2　主题爬行基本爬行策略与算法
　　
　　主题爬行技术的核心是爬行的策略与算法，由于主题爬虫与传统网络爬虫在爬行目标上有很大差别，因此，除了采用传统网络爬虫的爬行策略之外，主题爬虫在爬行过程中还要采用有效爬行策略与算法尽快爬到并抓取与主题相关的网页。Sotiris Batsakis等人将主题爬行策略分成三类：经典主题爬行策略、改进的主题爬行策略、基于语义的主题爬行策略。经典爬行策略主要指主题爬行的“鱼群搜索策略”(fish search)，改进的主题爬行策略主要指“鲨鱼搜索策略”(sharksearch)、“最优最先(best first)搜索策略”等。
　　鱼群搜索策略是以“鱼群搜索算法”(fish algo―rithm)为基础的主题爬行策略，鱼群搜索算法是一种基于群体动物行为的智能优化算法，该算法模仿鱼群在觅食和繁殖时的表现，动态调整种群的个数。在鱼群搜索策略中，每个网页相当于一条鱼，如果遇到满足给定条件的相关网页，则该鱼繁殖小鱼，并对该网页发出的链接进一步探索；否则食物减少，如果一条鱼的食物减为零，则该鱼将停止寻食并放弃对该链接的爬行。鱼群搜索策略中某一超级链接是否放人提取器中待下载，取决于该链接的父链接与主题的相关性。关于待下载链接与主题的相关性，De Bra L”提出了通过比较已下载网页内容与主题关键字是否匹配，引入二元分类方法(1代表相关，O代表不相关)来计量相关性。
　　改进的主题爬行策略是基于鱼群搜索策略基础的改进，Hersoviei M”。提出采用向量空间模型(vectorspace model)来计量相关性，向量空间模型不以整数0、1来计量相关性，而是通过多个参数比较，采用O一1之间的实数来计量。该方法除了用已下载网页内容和主题关键词是否简单匹配来判断相关性，还通过计算 锚文本(anchor)等其他参数与主题的相关性来计量。这种改进的搜索策略比鱼群搜索策略在爬行的准确率(precision rate)和召回率(recall rate)上有很大的进步，该搜索策略被称之为“鲨鱼搜索策略”(shark search)。在“鲨鱼搜索策略”中，已下载网页中页面内容、锚文本内容、链接内容(URL)及父页(指向包含链接页面的Web页)的相关性等都作为主要参数用来计量待下载网页与主题的相关性，通过计算确定待下载网页是否进人提取器队列中。关于参数向量的选择，Cho J等提出了重要度向量，该重要度向量由几个部分构成：①已下载页面逆文献频率法(inverse document frequency，IDF)的关键词相关度；②已下载Web页的重要链接指向个数(backlink count)；③已下载页面指向链接的重要度值(pagerank)；⑧URL位置矩阵(10cation metrics)等四个参数作为衡量相关性的向量。
　　随着研究的不断深入，“鲨鱼搜索策略”也不断完善，该方法中向量空间模型的参数越多，相关性计量越准确，但参数增加使计算量也随之增加，因此，过多的参数对爬行速度有一定影响。但Zhumin Chen等”。对各种主题爬虫的运行时间进行了实验分析比较，该学者认为，相对于网络中的下载等待时间来说，相关性计算的时间很少，有时甚至不到下载时间的十分之一，因此页面相关性的计算对爬行速度的影响是可以忽略的。在“鲨鱼搜索策略”的基础上，Menczer F等提出了“最优最先”(best first)搜索策略，这一策略通过计算向量空间的相关性，把相关性“最好”的页面放入最优先下载的队列，另外，“最优最先”搜索策略采用了术语频度(TF)值计算文本相似度，减少了部分计算量。根据文献，由于只选择与主题相关性很大的链接，而忽略某些当前相关性不高但下级链接中包含很高相关性链接的网页，最优最先算法具有很大的贪婪性，该算法只能找到局部范围内的最优解，难以得到全局范围内的最优解。因此，该搜索策略只适用于小范围内的主题爬行，对于大范围的主题爬行，容易过早地陷入Web空间中局部最优子空间的陷阱。
　　作为一种有效表现概念层次结构和语义的模型，本体论(ontology)被广泛地应用到计算机科学的众多领域。美国斯坦福大学的知识系统实验室学者TomGruber提出了本体是概念化的显式表示，Studer在Gruber的基础上扩展了本体的概念，提出本体是共享概念模型的明确形式化规范说明。本体具有良好的概念层次结构和对逻辑推理的支持，可以解决信息源之间结构和语义的异构，W3C在2004年提出了Web本体语言(Web ontology language，OWL)的标准。基于本体的网络爬虫认为概念上使用相似术语的页面应具有一定的相关性。M.Ehrig等学者将本体应用于主题爬虫的分离器中，首先通过定义术语的相关性，建立本体术语集合，通过对已下载网页处理并对本体库的比较分析，计算其相关性，确定是否将待下载链接放入分离器，提高了主题爬行的准确度与召回率。Jason J.Jung提出基于语义主题爬行的开放式决策支持系统，该开放系统主要包括基于上下文语义的主题爬虫通过域内链接进行区域内知识发现及知识的处理，为开放式决策支持系统迅速提供知识。基于语义的主题爬行技术中，本体库的构建及完善是一项复杂的工作，因此应用范围有限。
　　
　　3　爬行策略与爬行算法的改进
　　
　　虽然鱼群搜索策略、鲨鱼搜索策略、最优最先搜索策略是主题爬虫常用的搜索策略，但由于互联网中网站结构的多样性及复杂性，很多学者在主题爬行算法中尝试采用其他的搜索算法实现较高准确率与召回率。相继提出了采用模糊算法、人工神经网络、遗传算法、粗集理论等方法指导主题爬虫的爬行过程。
　　作为最优最先搜索策略的改进，李学勇等采用模拟退火算法作为爬行的启发式搜索算法，与爬行中的“隧道技术”结合改进主题爬虫。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。该算法在选择优化解方面具有非贪婪性，在爬虫搜索过程中，每次除了选择评价值最优的链接，还以一定概率有限度地接收评价值次优的链接，确保有一定价值的链接有机会被选中。“隧道技术”使爬虫有机会穿过相关性低的区域进入相关性高的区域，当页面内容的相关度低于设定的阈值时，通过扩大主题范围，使更多的相关链接加入到链接优先级队列，提高相关网页的召回率。模拟退火算法是一种随机算法，虽然可以比较快地找到问题的近似最优解，但不一定能找到全局的最优解。因此，将模拟退火算法应用于最优最先搜索策略并不能完全保证主题爬行的鲁棒性。
　　遗传算法(genetic algorithm)是模拟生物进化论与遗传学结合的计算模型，在最优解搜索领域具有一定优势，自从密西根大学的Holland教授提出该算法后，由于其鲁棒性、自组织性强等优点，在很多方面有广泛的应用。Jialun Qin等学者采用遗传算法实现主题爬虫在特定域内的爬行，通过初始化、内容分析选择、链接分析杂交、变异等几个步骤实现主题爬虫在特定域内的爬行。根据文献，该算法的应用在某些Web页的主题爬行中具有较好的准确率与召回率。遗传算法应用于主题爬行技术中存在编码方式的确定、适应性函数的确定等问题，由于网站结构、网页类型的不同需要采取不同的标准。遗传算法也存在局部最优陷阱问题，单纯使用遗传算法进行主题爬行时也会存在无法穿越隧道的问题。
　　隐马尔柯夫模型(HMM)作为一种统计分析模型，在信号识别等领域有广泛的应用，隐马尔柯夫链在相关性评估应用中具有一定优势。Hongyu Liu等提出基于隐马尔柯夫模型的算法来评估待下载页面与主题之间的相关性。该系统包括三个步骤：①进行数据收集；②依据相关性模式建模；③根据模型对待下载页面评估并进行主题爬行。该算法的应用可以提高主题爬虫在分离器中的处理精度，但由于计算量的增加，会降低处理效率。
　　人工神经网络近来日益受到人们的关注，因为它特有的非线性、自适应性、自学习性为解决复杂问题提供了一种相对比较有效的简单方法。Hai-Tao Zhengr提出采用基于本体的人工神经网络(ANN)实现自学习爬行，系统框架分为三个步骤：①进行数据准备；②通过现有的数据集对人工神经网络进行训l练；③将训练过的主题爬虫应用于实际爬行，取得较高的准确率与召回率。人工神经网络存在训练时间长、学习算法的通用性低等缺点，所以，将人工神经网络应用于主题爬行中，也存在样本学习时间长，学习算法不具有通用性等缺点。因此，人工神经网络仅仅适用于小范围的主题爬行。
　　除以上算法的改进，很多学者还尝试采用其他计 算方法改善主题爬虫的搜索性能，Suman Saha等。应用粗集理论对未下载的Web页面进行预测，判断其与主题相关性，该方法提高了爬行页面的准确率，降低了噪声。Huaxiang Zhang等提出利用Q学习及在线半监督学习理论在待访问的URL列表中选择与主题最相关的URL，相关值的计算基于模糊理论及Q值理论。
　　虽然很多学者尝试通过不同的软计算方法改进主题爬虫，但由于互联网中网站结构与网站内容多样复杂，这些算法往往应用于某些网站时具有较高的准确率与召回率，但是应用于另一些网站时准确率与召回率会下降。主题爬虫的准确率与召回率除了受网站结构、主题爬虫的爬行策略与算法等因素的影响，还受爬行入口位置、Web服务器性能等其他相关因素影响。
　　
　　4　主题爬行策略与算法的研究热点
　　
　　鉴于主题爬行技术的不断发展，主题爬行策略及算法也在不断完善。目前关于主题爬行策略与算法的研究主要集中于以下几个方面：①爬行策略与爬行算法的通用性研究。互联网中不同类型网站的网页间组织形式相差很大，如何从已经下载的网页中高效、准确地判断待下载页面与主题的相关性，并根据相关性修改下载队列，是主题爬行技术能否成功的关键。目前主要通过修改爬行策略及利用各种软计算方法来实现，但很多时候对于某些网站具有很高的召回率和准确率的方法，对于另一些网站可能并不适用。主题爬行的准确率与召回率有时候与种子URL的起始位置等其他相关因素有很大关系。②“隧道技术”的研究。很多时候主题爬虫需要穿过若干个与爬行主题相关性很低的页面后才会发现一组与主题相关性很高的页面群，穿越中间相关性很低的页面需要隧道技术，如何实现隧道穿越、提高主题爬行准确度是目前很多学者研究的内容。③对于深度Web(deep Web)资源爬行策略的研究。许多深度Web资源存放在数据库中，这些数据库的访问需要用户名、密码等信息，目前常采用半人工辅助方法使主题爬虫访问数据库，如何快速、自动地发现这些数据库并访问这些深度Web资源，也是当前主题爬行技术的研究热点。
　　
　　5　结语、
　　
　　随着人们对个性化信息服务需求的增长，专业搜索引擎的发展将成为搜索引擎发展的趋势之一，主题爬行技术是专业搜索引擎的研究重点，也是数字图书馆、智能商业信息检索的技术基础。主题爬行技术的关键是如何让网络爬虫迅速找到并抓取与主题相关的页面，解决这一问题需要爬行策略与爬行算法的不断改进。本文在分析主题爬行技术基本原理的基础上，对现有的主题爬行策略及算法做了分类，系统分析、比较了不同爬行策略及算法的特点及优缺点，对主题爬行技术的进一步研究进行了展望，以期为主题爬行技术的研究和主题搜索引擎的不断完善提供一定参考。

相关热词搜索：爬行 算法 综述 主题爬行策略与算法研究综述 酒店营销策略研究综述 促销策略研究文献综述