基于遗传算法的主题爬虫搜索策略研究

湖北工业大学硕士学位论文基于遗传算法的主题爬虫搜索策略研究姓名：梁云静申请学位级别：硕士专业：计算机应用技术指导教师：邵雄凯20100301湖北工业大学硕士学位论文I摘要传统的搜索引擎需要对互联网上的信息进行广泛的收集和分析处理，随着互联网的急剧膨胀，传统的搜索引擎需要处理的网络信息也越来越多，同时也就不可避免的为用户提供了或多或少的无关信息。在专业化需求日益增长的今天，主题搜索引擎以其分类细致精确、数据全面准确的特点迅速流行起来，而主题搜索引擎的关键技术——主题爬虫的搜索策略就成为了近几年的研究热点。本文将遗传算法应用在主题爬虫的搜索中，引入遗传算法来改进爬虫的搜索策略，利用遗传算法高效、并行、全局寻优的特点，提高爬虫的搜索效率。本文的研究内容主要有以下两个方面：根据网络特点改进传统的遗传算法；通过实验验证改进后的效果。基于遗传算法的主题爬虫搜索策略，是将待检索的问题提交给通用搜索引擎，对其返回的结果集进行处理，选择一定数目的URL作为初始群体；通过交叉操作，提取初始群体中URL对应页面包含的所有超链，产生出大量新的个体，再对所有超链进行相似度预测，选出相关度高的种子作为交叉结果；通过变异操作，引入目录型网页，扩大搜索范围；通过选择操作，对遗传之后的结果进行处理，选出相关度高的个体作为新一代的种子进入新一轮的遗传；通过爬虫终止搜索条件，来结束爬虫的搜索。本文在构造初始群时，将待检索的问题提交给通用搜索引擎Google，对其返回的结果集选择前n个URL，再扩展、去重、计算Authority和Hub值，重点是引入了Alexa排名，然后依据综合排名值选择初始种子集合。在交叉过程，根据超链的锚文本有效地预测对应的页面与主题的相似度。在变异阶段，根据目录型网页包含的大量链接和详细的分类来寻找相关网页。本文设计了一个实验，来验证遗传算法在爬虫搜索中应用的可行性以及改进后的遗传算法的效果。在实验中，本文采用GA、HITS、Best-First三种算法分别对给定主题进行搜索，将搜索到的网页根据向量空间模型算法计算其与主题的相关度，再分别统计三种算法搜索到的相关的网页数。实验结果表明，本文的基于遗传算法的爬虫搜索策略在某种程度上具有一定的优势。关键词：主题爬虫，遗传算法，Best-First，HITS湖北工业大学硕士学位论文IIAbstractTraditionalsearchengineontheInternetrequiresextensiveinformationcollectionandanalysisandprocessing,withtherapidexpansionoftheInternet,traditionalsearchengineneedtohandlemoreandmorenetworkinformation,whilealsoinevitablethatprovidestheuserwithmoreorlessirrelevantinformation.TheGeneticAlgorithmisusedinourtopiccrawlersearch,theintroductionofitimprovesthesearchstrategyofthereptile,usingtheefficient,parallel,globaloptimizationgeneticalgorithmtoimprovethesearchefficiencyofthereptile.Thisstudymainlyincludesthefollowingtwoaspects:ImprovethetraditionalGeneticAlgorithmaccordingtothenetworkfeatures;Testtheimprovedresultsbyexperiments.Thetopicofinformationsearchstrategy,whichbasedonGeneticAlgorithmsearchstrategy,firstofall,submitthequestionwillberetrievedtothegeneralsearchengine，processresultsetreturned，andselectacertainnumberofURLasinitialgroup;thenitextractallthehyperlinksincludedinthepagecorrespondingtotheURLininitialgroup,producealargenumberofnewindividuals,predictsimilarityamongallthehyperlinks,andelectahighcorrelationofseedsascross-cuttingresults,next,itintroducedirectory-typepagetoexpandthesearchrangethroughthemutationoperation,andelecttheresultscomefromthegenetictreatmenttogettheindividualswithhighsuitabilitydegreewhichasanewgenerationofseedsgoonintoanewroundofinheritance.Atlast,itendthesearchconditionsbyreptiles.Inthispaper,whenconstructtheinitialcluster,itsubmitthequestionswillberetrievedtothegeneralsearchengineGoogle.Withthepreviousn-URLintheresultsetreturned,thereisaseriesofprocesslikereexpand、de-emphasis、andcalculatetheAuthorityandHubvalues。ThepaperfocusontheAlexaranking,thennextselecttheinitialseedsgroupaccordingtointegratedrankvalues.Inthecross-process,iteffectivelypredicttherelevancebetweenthecorrespondingpagewiththetopicaccordingtotheanchortextofhyperlinks.Inthevariationphase,itfindrelatedpagesaccordingtothelargenumberoflinksandadetailedclassificationincludedinthedirectory-typepage.ThispaperdesignedanexperimenttotestandverifythefeasibilityofGeneticAlgorithminreptilesearchaswellastheeffectofimprovedGeneticAlgorithm.Intheexperiment,ourpaperusedthreekindsofalgorithmssearchingthegiventopics,calculatingthesimilarityofsearchedwebpagestothetopicaccordingtothevectorspacemodelalgorithm,thencountrelatedwebpageswhicharesearchedoutbythisthreealgorithms.Theresultsshowthat:theefficiencyofGAalgorithmisalsohigherthanBFandHITSalgorithms.Keywords:TopicCrawler,GeneticAlgorithm,Best-First,HITS学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。学位论文作者签名：指导教师签名：日期：年月日日期：年月日湖北工业大学硕士学位论文1第1章引言1.1背景随着互联网的快速发展，网络对人们的影响越来越大，而发展迅猛的万维网(WorldWideWeb)技术，以其简单的使用方法和丰富的数据资源，成为了互联网上重要的信息发布和信息共享的平台。万维网作为一个全球性信息服务中心，丰富的数据资源和包罗万象的网络服务为人们的日常生活提供了很多便利。但是万维网庞大的数据量和迷宫般错综复杂的链接关系也给人们的使用带来了很多不便，试想，面对如此复杂而庞大的万维网，如何才能从海量的信息中找到自己的答案，这一问题困扰了越来越多的用户，也阻碍了互联网的发展。针对这个状况，人们开始研究一个新的技术——搜索引擎，搜索引擎就是根据用户提供的关键词在万维网上查找用户需要的信息并返回结果，这一技术的出现快速地打破了万维网复杂的局面，也解决了阻碍万维网发展的瓶颈问题。搜索引擎成为了指引人们走出“迷宫”的灯塔，它帮助全世界的网民方便快捷地找到了自己需要的信息，从而更好地展示着万维网独特的魅力。传统搜索引擎，即通用搜索引擎，首先需要尽可能多、尽可能全面地采集互联网上的信息和页面，有时甚至是整个Web上的资源，然后把搜集到的页面下载并存储到本地，再为数据库中的页面信息建立索引，根据用户提供的关键词跟索引数据库进行匹配，从而查找相关页面并返回给用户。但是随着Web上信息的急速增长，全部采集万维网上的信息并且保持与万维网上信息变化同步已经越来越困难，而且信息采集的速度也越来越不能满足人们实际应用的需要[1]。为了解决这些问题，传统搜索引擎采用了并行机制，但并行技术带来的效果仍不能满足广大网民的需要。此时，新一代的搜索引擎——主题搜索引擎应运而生，主题搜索引擎则是为了满足某些特定用户的需要，专门查询某一学科或某一主题的信息的查询工具，它可以在某个特定的范围内或者某个特定的主题上取得比传统搜索引擎更令人满意的结果。1.2搜索引擎分类搜索引擎(searchengine)是指根据一定的搜索策略、运用特定的计算机程序搜集互联网上的信息，再对信息进行组织和处理，将处理后的信息显示给用户，湖北工业大学硕士学位论文2从而为用户提供检索服务的系统。在1990年以前，没有人能搜索万维网。所有搜索引擎的祖先，是1990年由Montreal的加拿大麦吉尔大学(UniversityofMcGill)的三名学生(AlanEmtage、PeterDeutsch和BillWheelan)发明的Archie(ArchieFAQ)，而在当时尚未出现。虽然Archie搜集的信息资源不是网页（HTML文件），但和搜索引擎的基本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。所以，Archie被公认为搜索引擎的鼻祖。时止今日，搜索引擎经历了二十年的时间，在这短短的二十年里，搜索引擎技术的发展一日千里，人们对搜索引擎的认识也越来越全面，目前，搜索引擎主要分为以下四类：1.目录式搜索引擎目录式搜索引擎虽然有搜索功能，但严格意义上不能称之为真正的搜