垂直搜XX擎中主题爬行技术的研究

垂直搜XX擎中主题爬行技术的研究 重庆大学硕士学位论文英文摘要adverti sementsi nWebpages；surroundi ngtextof ananchor l i nki sal sohard todefi ne，and anchortext contai ns l i mi ted i nformati onThus，i n thi sthesi s，page segmentationbased ondepthfi rsttraversals wasfirstl yintroduced tofi lterpartof noise nodesinWebpagesAndthepri ori tyof acandi datelink wasmeasured asanaggregatevaluebytaki ngthecontent ofWebpage containi ngit，i tsblock textand anchortexti ntoconsiderati onPage segmentation hasbeen vali datedto enhancethe performanceoffocusedcrawl ing effectivel yby experiments (3)Two adaptivestrategi esbasedOi li nformati on gain(IG)and ratio ofsum ofinformation(RSI)respecti velywere introducedThei niti aldescri pti onoftopi cgenerated byconcept hierarchy in categorytree tendsto beunreal andi naurateToi mprovetopic descripti on，at everyi ntervalduri ngcrawl ing，the contributi onof eachconceptintopi cvectorspacetotopicdescriptionwoul dbel earnedautomatical ly fromal lcrawl edpagesaordi ngtothe twoadaptive strategies andfed backto modif ythewei ghtofeach conceptbythecrawlerExperi mentsdemonstratethat thetwoadapti vestrategies bothserveto enhancethecrawl ing ability ofthefocused crawler；Webpagescrawl edwi thIG aremore related totopic thanthose with RSI，whereas RSIbeats IGi noverallstabi lityIn theend，a focusedcrawl ing prototypesystem wasdesi gnedandi mplementedon which aseri esofexperi mentswerecarri edoutto vali dateandanal yzemethodsproposed inthisthesisKeywordsFocusedCrawl ing，Wi kipedi a，Topi cDescri ption，Page Segmentati on，Adapti veStrategy重庆大学硕士学位论文目录目录中文摘要?I英文摘要?III1绪论?111主题爬行技术的研究背景及意义?11】1垂直搜索引擎的提出?1112垂直搜索引擎与通用搜索引擎的区别?1113主题爬行技术的提出?2114主题爬行技术的研究意义?212主题爬行技术的研究现状?313本文的研究内容及组织结构?51-31本文的研究内容?5132本文的组织结构?62主题爬行相关技术?821引言?822主题描述相关技术?8221主题表示模型?8222确定主题向量空间?9223主题特征加权?1023搜索策略?一1124网页预处理相关技术?12241网页规范化?一12242网页解析?一12243网页分块?12244分词、去停用词?1325主题相关性计算中的相关技术?14251主题相关性的度量方法?14252基于HowNet的语义分析技术?14253基于WordNet的语义分析技术?15254基于ODP的语义分析技术?16255基于本体的语义分析技术?一1726小结?18V重庆大学硕士学位论文目录3基于维基百科的主题描述?1931引言?1932主题描述的主要方法及存在问题?1933维基百科简介?2034基于维基百科的主题描述方法?22341扩充维基百科的分类树?一22342构建主题向量?22343词语映射到概念过程中的消歧?一2435小结?254基于网页分块的候选链接优先级的预测方法?2641引言?2642候选链接优先级预测的主要方法及存在问题?2643基于网页分块的候选链接优先级的预测方法?29431基于深度优先遍历的网页分块?一29432候选链接的优先级预测?一3144小结?345自适应的主题爬行策略?3551引言?3552自适应主题爬行策略的相关研究及存在问题?3553基于维基百科和网页分块的自适应的主题爬行器?3754基于信息增益的自适应方法?38541信息增益简介?一3854_2基于信息增益的自适应方法?一3855基于信息量总和比率的自适应方法?3956小结?406实验与分析?4161引言?4162主题爬行原型系统的实现?4163实验数据和参数设置?42631实验数据?一42632参数设置?4364评价指标?4365实验方案?44651主题爬行策略的功能演进过程?一44VI重庆大学硕士学位论文目录652主题描述方法的对比实验?45653主题描述详略程度对主题爬行性能的影响对比实验?46654引入网页分块前后的对比实验?48655不同的自适应方法之间的对比实验?一4866小结?507总结与展望?5171本文总结?5172进一步的工作?52致谢?54参考文献?55附录?59A作者在攻读硕士学位期间发表的论文目录?59B作者在攻读硕士学位期间参与的科研项目?59VII重庆大学硕士学位论文1绪论1绪论11主题爬行技术的研究背景及意义111垂直搜索引擎的提出随着Inter的飞速发展，Web的信息量越来越大，并且每天都在以极快的速度动态更新着，互联网已经成为一个高度开放、异构、分布式的巨大信息空间。 因此如何快速、准确的从这个海量信息空间中获取用户真正感兴趣的内容，变得至关重要。 搜索引擎便在这个背景下应运而生了，用户只需在搜索框中输入关键词，就可在数以万亿计的海量信息中获得与之相关的内容。 近些年来，搜索引擎作为一种必不可少的工具，在人们的工作生活中得到了广泛的应用。 xx年7月19日，中国互联网络信息中心(NIC)在京发布了第28次中国互联网络发展状况统计报告1】，报告显示，截至xx年6月底，中国的搜索引擎用户规模达到386亿，并以796的使用率位居用户网络应用和信息获取方式的榜首。 传统的通用搜索引擎(如Googl e、Al taVista、百度等)，虽然能够在很大程度上帮助人们在互联网上查找信息，但是它面向的是所有用户，返回结果也总要做到面面俱到，因此在使用中逐渐暴露出了一些问题，像覆盖率低、时效性差、易导致迷航、结果不准确、过于死板【2J等。 面对这些挑战，并且伴随着信息技术的日渐成熟，搜索引擎技术正在以专业化、智能化、个性化为目标而发展。 在这种情况下，垂直搜索引擎(Verti calSearchEngi ne，VSE)诞生了，并引起了学术界和产业界的广泛重视。 垂直搜索引擎【2】3】是面向特定领域(主题)的专业搜索引擎，是相对通用搜索引擎的覆盖率过低、查询不准确、更新不及时等缺点提出来的新的搜索引擎服务模式，它利用主题爬行技术对Web中某个主题的相关信息进行爬行、索引并进行整合，定向分字段抽取出需要的数据进行处理后再以某种满足用户个性化需求的形式返回给用户，其特点是“专、精、深”，且具有行业色彩。 垂直搜索引擎已经成为信息检索的发展趋势。 112垂直搜索引擎与通用搜索引擎的区别垂直搜索引擎是搜索引擎的细分和延伸。 它与通用搜索引擎的区别主要体现在数据资源与服务上。 具体可分为以下四点【4J通用搜索引擎面向的是全网信息，采集范围广、数量大，采集深度比较浅，采集的动态网页的优先级比较低；而垂直搜索引擎只对Web进行局部采集，所采网页都是面向某一特定领域，服务于某一特定人群或需求的，数量适中，采集层次更深，采集的动态网页的优先级相对较高。 重庆大学硕士学位论文1绪论通用搜索引擎通常只能解析和提取网页的标题和正文；而垂直搜索引擎常常还能根据用户的需求解析时间、作者以及其他元数据，根据行业特色提取网页中的特殊内容。 通用搜索引擎追求响应速度，仅对部分网页中特定位置的文本进行索引，检索结果不完全，只能给出预估的数量和排在前面部分的结果信息；而垂直搜索引擎更注重信息的专业性和使用价值，支持全文检索和精确检索，按需提供多种结果排序方式，支持结构和非结构化数据联合检索。 通用搜索引擎以网页为搜索的最小单位，而垂直搜索引擎对网页信息进行了结构化的信息抽取加工，以结构化数据为搜索的最小单位。 总之，垂直搜索引擎，就是专业和深入的分析和挖掘特定领域的信息，经过精细分类和过滤筛选使其定位更准确的搜索引擎。 113主题爬行技术的提出从上述比较可以得到，垂直搜索引擎亟待解决的问题就是如何从Web的海量信息中获取与特定领域相关的信息，即以何种策略访问Web从而高效的获取有用资源，最终提高垂直搜索的性能。 这已经成为近年来垂直搜索引擎研究的主要问题之一。 而这个任务则是由垂直搜索引擎的核心部分主题爬行器来完成的。 主题爬行的概念【6最早是由Soumen Chakrabarti等人在1999年提出来的，它是在预定主题的指导下，在Web上有选择的爬行与主题相关的网页，并避免爬行不相关的网页。 不同于通用搜索引擎中的通用爬行器不加选择的对所有链接进行爬行，主题爬行器对每个网页中的链接都会进行分析并且预测它们所指向的网页与预定主题是否相关，对那些被判断为与主题相关的链接进行优先爬行，并舍弃那些与主题无关的链接。 主题爬行器基于这样一个重要的假设Web上具有相同或相关主题的页面趋向于相互链接，被称为Web的主题局部性(Topi calLocal ity)_71。 主题爬行技术是构建垂直搜索引擎的核心技术，它的性能直接影响着垂直搜索引擎的性能。 114主题爬行技术的研究意义首先，根据Web的主题局部性，从一个好的种子链接出发，可以检索到Web上所有与主题相关的网页。 这就从理论上为主题爬行器的创建提供了依据，而Web的主题局部性越好，相同主题的网页之问就会链接得越紧密，最终主题爬行器的性能也就会越好。 主题爬行器比通用爬行器更进一步，它能快速爬行Web中特定主题的相关部分，因此，对于这种不是对整个Web，而是对某个预定主题感兴趣的搜索来说，它占有很大的优势。 另一方面，与通用爬行器不同，主题爬行器只对Web的局部进行搜索，并有选择的爬行和预定主题相关的网页，从而在很大程度上节省了硬件和网络资源。 重庆大学硕士学位论文1绪论因此，研究主题爬行技术，可以高效的搜集高质量的网页，进而提高垂直搜索引擎的性能。 同时主题爬行技术还可以在很多领域得到应用，如数字图书馆、专业数据集的获取以及个性化信息检索等方面。 12主题爬行技术的研究现状为了在w曲上有更广的覆盖面，通用爬行器通常会采用广度优先或深度优先爬行策略来遍历Web；而主题爬行器只对那些与特定主题相关的页面感兴趣，所以在爬行过程中它会有选择的从局部而非从整体上对Web进行遍历和访问。 因此，主题爬行器采用什么样的爬行策略，才能尽可能多的下载与主题相关的网页，避免与主题无关的网页，从而提高主题爬行的性能，就成为当前研究的热点。 目前，对主题爬行策略8】9】的研究，主要集中在三个方向一是基于网页内容的爬行策略，二是基于网络拓扑结构的爬行策略，三是基于网页内容与网络拓扑结构相结合的爬行策略。 (1)基于网页内容的爬行策略，就是对表现网页主题内容的文本信息进行分析，从而预测候选链接(Candi dateLi nk)所指向的网页的主题相关度。 Fi shSearch【joJ是最先被提出来的基于网页内容的爬行策略，它将包含主题关键词或短语的页面视为与主题相关，并将整个爬行过程比喻成鱼的觅食过程，将在Web这个“大池塘”中遍历的搜索代理比喻成一群鱼，当它们寻找到食物(相关网页)时，就会繁殖更多的孩子(相关网页的出链)，否则就会饿死。 为了避免形成环路，对孩子网页的深度要预先设定一个值。 当这个深度值减为零时，这个方向的搜索就停止。 但这种算法对页面和候选链接的相关性判断是一个二元值(0或1)，不能评价它们与主题相关程度的高低。 SharkSearch算法?J对Fi shSearch进行了改进，不但使用了一个取值在0到1之间的连续函数来判断网页的相关度，而且在计算候选链接的优先级时，还同时考虑了网页内容、锚文本和锚文本上下文。 BestFi rst算法【5】【123和NBestFi rst算法12】，则使用向量来表示主题和计算页面内容与主题之间的相关度。 基于网页内容的爬行策略也包括利用分类器来判断网页内容是否与主题相关的爬行策略。 文献131中的爬行过程包括训练和搜索两个阶段，训练阶段用增强学习算法(Rei nforcementLearni ng)计算训练集中每个链接的Q值，根据Q值将这些链接划分为几组，每组的Q值为该组中所有链接Q值的平均，利用每个组内所有链接的相邻文本信息训练一个相应的Nai veBayes分类器；在搜索时，用这些Nai veBayes分类器对候选链接的相邻文本信息进行分析，计算候选链接落在各个分组内的概率，并将其作为权值来计算链接的综合Q值，以此来衡量这个链接的重庆大学硕士学位论文1绪论优先级。 文献141和15都利用了两个分类器，前者用基准分类器来遍历W曲为学徒分类器来收集更高质量的训练集，再用训练好的学徒分类器根据候选链接的锚文本预测其优先级，学徒分类器会通过自适应的方法在爬行过程中不断的得到更新。 而后者则首先计算根集(正例集)文档的质心向量，将其作为前端分类器来指导主题爬行，并在下载网页后用后端分类器判断页面内容的主题相关性；然后利用前、后端分类器分别给锚文本打分求和来选择优先访问的候选链接；而在整个爬行过程中，会将后端分类器判断为主题相关的那些网页用来不断的更新质心向量，从而实现扩充主题，提高爬行效率的目的。 基于网页内容的爬行策略还包括基于语义的爬行策略316-211和通过分析网页内容在爬行过程中自适应地动态改变搜索方向的爬行策略【3】14】15】【201等。 (2)基于网络拓扑结构的爬行策略，是考虑到网页是一种半结构化的文档，可以利用网页之间的结构信息来预测候选链接的重要性，指导主题爬行。 PageRank算法圈和HITS(Hyperl ink InducedTopi cSearch)算法吲是基于网络拓扑结构的爬行策略中比较经典的两个。 PageRank算法是由Googl e搜索引擎的创始人SergeyBri n和LawrencePage于1998年提出的。 它基于一个重要的假设，即网页的重要性可以通过链接它的其他网页的重要性和数量来衡量。 根据这个假设，PageRank算法通过分析网页的链入和链出数来给每个页面赋予一个PageRank值，这个值的迭代计算公式如下PR(矽)尘望+dy广PRl(r)(11)，氦)Iout(r)I其中，为Web上所有网页的数量，in(p)表示页面P的入链的集合，out(r)表示页面r的出链的集合，d是一个衰减因子。 最先爬行的页面的PageRank值人为的给出，作为迭代的初始值。 HITS算法通过两个权值Authori ty值和Hub值来对网页的优先级进行评估。 它的基本思想是被越多网页所引用的网页，其质量就越高，相应的Authori ty值也就越高；引用越多高质量页面的网页，其Hub值就越高。 这两个值随着爬行过程通过迭代计算逐渐趋于稳定。 计算公式如下彳(p)=日(g)(12)qel(p)=彳(g)(13)qeO其中，为所有指向页面P的页面集合，O为被页面P中的链接所指向的页面集合。 (3)基于网页内容与网络拓扑结构相结合的爬行策略，就是将页面的文本信息和页面之间的结构信息相结合来预测候选链接的优先级，从而指导主题爬行。 比较直观的如文献24，它在HITS算法的基础之上，还考虑了页面的主题权重4重庆大学硕士学位论文1绪论形(p)，即页面内容与主题的相关分数值，在计算页面的Authori ty值时，用(p)半日(p)代替H(p)，这样做就使得页面对它所指向页面的推荐程度数值化了，从而减小了不相关页面对其邻近页面的影响，有效的避免了“主题漂移”。 文献25禾1J用搜索引擎的反向链接查询功能从一个与主题相关的链接(目标页面)集出发反向回溯一定深度，构建了一个树状的W曲语境图用来估计当前页面距离目标页面的远近。 它同样分为训练和搜索两个阶段。 训练阶段从目标页面出发，利用某一通用搜索引擎查询出所有指向目标页面的网页，将它们作为距离目标页面为1的第一层级，并用这些页面的页面文本训练一个分类器C，以同样的方法从第一层级的页面出发，得到距离目标页面为2的第二层级的分类器C，以此类推，就能获得目标页面与邻近页面之间层次结构的语境图。 搜索阶段，用各个层级的分类器判断刚刚下载的页面属于哪个层级，就可得到该页面与目标页面的距离，离目标页面越近的页面获得的优先级就越高，页面中的链接也就会被最先访问。 这种方法通过训练页面内容来预测页面之间的结构信息，以页面之间的层次关系来衡量页面的重要性。 它对预测链接的远期回报和解决主题爬行中的“隧道”问题具有一定优势。 为了对距离目标网页相同的不同网页的优先级做出预测，文献26对文献25进行了改进，利用隐马尔科夫模型(Hi ddenMarkov Model，HMM)来学习用户的浏览模式，从而指导主题爬行。 它通过用户浏览网页标注出主题相关网页(目标网页)，并记录用户浏览网页的序列，构成一个Web图，这样就获得了从不同的网页到目标网页的距离，距离目标网页越近的网页优先级越高；再对Web图中的所有网页文档用潜在语义标引(Latent Semantic Indexing，LSI)处理后提取关键词问的语义关系，并对网页文档应用Xmeans算法进行聚类，再将网页用类来标记，从而把Web图转化为概念图，其中所有的目标网页被标记为同一类，从而获得了从不同的网页到目标网页之间的语义关系；将不同网页到目标网页的距离作为隐藏状态，将不同网页所属的类作为观察状态，并结合Web图和概念图通过最大似然估计获得迁移矩阵和混合状态矩阵，用隐马尔科夫模型来预测在两个网页距离目标网页相同的状况下，向目标网页迁移的概率，概率越大的网页优先级越高。 作为垂直搜索引擎的核心部分，主题爬行是一种有效的面向特定主题的信息获取技术，已经得到了国内外学者越来越多的关注。 13本文的研究内容及组织结构131本文的研究内容通用的主题爬行过程如下选取若干种子链接，初始化待爬行的URLs优先级队列；重庆大学硕士学位论文1绪论根据不同的爬行策略设置主题；取出待爬行URLs队列中优先级最高的候选链接，下载对应的网页，经分析后从网页中提取出URLs作为候选链接并计算其主题相关分数，将这些候选链接按优先级降序插入队列中，其中，相关分数越高的候选链接，优先级也越高；重复，直到已下载的网页达到预设的最大网页数或达到预设的最大时问。 由上述过程可知，一个高效的主题爬行策略需要解决以下几个问题如何描述主题，这也是主题爬行中首要解决的问题。 主题描述的形式和精度直接决定了主题相关性的计算，最终影响着主题爬行的整体性能。 链接优先级预测，即提取有价值链接。 链接的锚文本很短，并且多数使用简略表达，所含信息量有限，所以不能很好的区分噪音链接和相关链接。 主题的初始描述往往不够客观、不够精确，如何在爬行过程中不断优化主题描述，实现增量爬行，也是一个需要解决的问题。 为解决上述问题，本文提出了一种基于维基百科(Wi kipedi a)和网页分块的自适应主题爬行策略首先利用维基百科的分类树(Category Tree)和主题描述文档来构建主题向量，从而在计算主题相关度时引入语义分析，而在将文本映射到主题向量空间的过程中，则引入了消歧参照表将不确定归类的或多义的词语进行词频均分后再映射，避免了通过判断词语上下文消歧的繁杂和词语映射不准确造成的主题爬行性能的下降；同时，通过网页分块来过滤噪音链接，并在计算候选链接的优先级时引入块相关性来提高链接预测的准确度；另外，在爬行过程中分别基于信息增益和基于信息量总和比率两种策略，对爬行到的网页进行自动学习，反馈更新主题向量空问中每个概念的权重，使得在主题爬行中对命中主题作用更突出的概念获得较高的权重，作用小的概念则分配较低的权重，从而优化主题描述，使主题爬行具备增量爬行的能力。 最后，基于Net Framework平台，用C语言实现了一个主题爬行的原型系统，并用逐渐累加功能的方法通过多组实验将本文中提出的主题爬行策略与其他算法进行比较。 利用常用的主题爬行性能评价指标对实验结果进行评估和分析。 132本文的组织结构第一章为绪论，介绍了主题爬行技术的相关背景知识，包括垂直搜索引擎和主题爬行技术的提出，主题爬行的概念、研究意义和研究现状，以及本文的主要工作。 第二章介绍了主题爬行的相关技术，包括通用的主题爬行器框架及其各个关键部分的相关技术，重点介绍了主题描述相关技术和主题相关性计算中的语义分6重庆大学硕士学位论文1绪论析技术。 第三章介绍了基于维基百科的主题描述方法，采用向量空间模型VSM，并通过引入维基百科知识库，来构造主题向量，对主题进行描述，从而向主题相关性的计算中引入了语义分析，同时还给出了利用参照表在词语映射到概念过程中消歧的方法。 第四章介绍了基于网页分块的候选链接优先级的预测方法，首先引入了基于深度优先遍历的网页分块算法，并以此为基础定义了块文本和网页内容文本，最后通过引入块相关性来提取候选链接，并综合考虑网页内容文本、块文本和锚文本来预测候选链接的优先级。 第五章分别介绍了基于信息增益和基于信息量总和比率的两种白适应方法，通过对已经爬行到的网页进行分析，自动学习并更新主题向量空问中每个概念的权重，从而完善主题描述，实现增量的主题爬行。 第六章首先介绍主题爬行原型系统的实现过程，然后介绍实验数据、参数设置和实验方案，最后利用查准率和信息量总和两种评价指标对实验结果进行分析，验证了本文提出的各种方法的有效性。 第七章对本文的工作进行总结，并提出了下一步的研究方向。 重庆大学硕士学位论文2主题爬行相关技术2主题爬行相关技术21引言主题爬行器是一个完整而复杂的系统。 主题爬行就是在预定主题的指导下在网络上搜索、抓取网页的过程。 因此，如何描述主题就是主题爬行中首要解决的问题。 同时，由于网页是一种半结构化的文档，所以在下载网页后还要对其进行预处理，提取网页的核心内容，才能利用主题相关性计算方法判断网页是否与主题相关。 根据通用的主题爬行器框架(见图21)，本章分别从主题描述、搜索策略、网页预处理和主题相关性计算几个方面来介绍主题爬行中的关键技术，重点介绍主题描述相关技术和主题相关性计算中的语义分析技术。 禽、-导、请求响压旺待爬行结慝束爬行、_。 关分聱的页面_爬网解_爵罢一炳鬻姚I行一页+析_-一R二二二j uRLs优先级队列一去-If-1uRLs优先级计算图21通用的主题爬行器框架Fi g21Framework ofGeneral FocusedCrawl er22主题描述相关技术221主题表示模型由于主题描述是主题爬行的前提条件，所以主题的表示方式、描述详略以及描述精度都直接决定了主题相关性的计算，最终影响着主题爬行的整体性能。 目前，主题表示模型主要包括主题查询字符串和向量空间模型两种。 重庆大学硕士学位论文一!圭壑墨堑塑菱垫查主题查询字符串是由相互间隔的一个或多个可以描述主题的关键词组成的查询字符串，主要出现在早期的主题爬行研究中。 向量空间模型VSM(Vector SpaceModel)271是由Sal ton等人提出的应用于信息过滤，信息提取，索引以及评估相关性的代数模型。 它通常用于表示文档，将一篇文档视为一个多元向量，向量中的每一项由一个词和它的权重组成，其中，词在文档中至少出现过一次，而权重代表了这个词对区分这篇文档所发挥的作用；从广义上讲，如果表示文档的向量空间已经确定了，而其中某一项的词从未在当前处理文档中出现过，则表示该文档的向量中，这个词的权重为0。 当在主题爬行中把向量空间模型用于表示主题时，向量中的每一项则由可以刻画、描述主题的关键词f及其权重W组成，此处权重的大小反映了这个关键词对主题描述贡献的多少；主题向量的数学表示形式为主题f=r(t1，W，；f2，W2；?；f。 ，w，)。 用向量空问模型VSM表示主题是目前主题爬行研究中普遍使用的方法。 另外，在一些主题爬行模型中，虽然没有明确的用某种方式表示主题，但却通过对训练集进行学习将主题融合在了判断主题相关性的分类器中，例如文献13、14、15；也有一些研究中，则是把人为标注过的主题相关网页作为目标网页，依据当前网页与目标网页的距离来判断相关性，此时的目标网页就代表了主题，这也是结合网络拓扑结构的主题爬行策略中所特有的，例如文献25、26】。 222确定主题向量空间在使用向量空间模型VSM时，由于文档是自然语言格式的文本，它可以基于自身通过特征选择提取特征词来构成向量，而主题却是一个特定的概念，它无法依靠自身来构成一个向量，所以在构建主题向量之前，通常要先通过一些方法确定主题的向量空间。 确定主题向量空间，也就是获取能够描述主题的特征集或关键词集合，此时向量空间的每一维对应一个特征词，而特征词的权重默认为1。 主题特征集的大小决定了主题描述的详略。 现有的获取主题特征集的方法主要有基于特征选择的方法，就是收集与主题相关的网页集作为训练集，将训练集中的网页预处理后，利用文本分类中的特征选择方法来提取特征集，如文献15。 常用的特征选择方法有特征频度、信息增益、互信息、z2统计、期望交叉熵等。 这种确定主题向量空问的方法存在一定的缺点，一方面是由于训练集中的网页只是Web的一个局部，所以从中提取的特征集也只是真实主题特征集的一部分，不能完整的描述主题；另一方面，被提取的特征词之间并不是完全正交的，通常存在着上下位关系，而它们却稀疏的分布在主题向量空间中，从而降低了对主题的描述性。 基于知识库的方法，即从已有知识库的概念层次体系(通常为树状)或者是知识网络中提取主题相关的特征集。 由于知识库中的概念层次体系所含的概念重庆大学硕士学位论奎一!圭望墨堑塑菱垫查-_-一。 和知识网络中所描述的知识都更加全面、更加细化，并且概念之间或知识之问还根据它们在现实中的语义关系被组织成了一个体系结构，这样就可以在主题爬行时根据概念或知识的层次体系引入语义分析，而不单单局限于词语之间的机械式匹配。 常用的知识库有HowNet16】、WordNet 171、ODPl3】【18、本g本【,911201等。 223主题特征加权在向量空间模型VSM中存在两个影响主题描述准确度的因素一个是向量空间的大小，即特征词t的选择粒度，另一个是特征词的权重w。 特征词的权重的计算方法直接决定了特征词对主题描述的精确度。 主题特征的权重计算方法取决于确定主题向量空间的方法。 对基于特征选择的方法来讲，主题特征词的权重计算与文本分类中的特征加权方法类似，主要有以下三种TF权重(Term Frequency)，也称为词频权重。 如果特征词f在训练集中的主题相关网页中经常出现，即TF值越大，则说明它对主题描述的重要程度越高。 TF权重的核心思想是特征词在主题相关网页中的出现频率正比于它对主题描述的作用，出现频率越高则该特征词对主题描述越重要。 TF权重体现了信息论中频度的思想，它的计算公式如下彬=坑=特征词f，在训练集网页中出现的次数(21)在具体的应用中，通常会用够死。 对TF权重做归一化处理，其中死。 是主题网页训练集中特征词出现次数的最大值。 IDF权重(Inverse DocumentFrequency)，也称为逆文档频率权重。 IDF权重的核心思想是那些只在少部分主题相关网页中出现的特征词反而比在大多数相关网页中都出现的特征词更重要。 逆文档频率是一个词语普遍重要性的度量，是对特征词在训练网页集中分布集中度的量化，体现了信息论中集中度的思想。 公式如下W=l092(赤)(22)或表示主题网页训练集中包含特征词f，的网页总数，表示主题网页训练集中包含的网页总数，p是调节因子，特征词t，出现在越少的相关网页中，其IDF值就越大，代表其在主题网页训练集中的分布越集中，说明它的类别区分能力越强，即对主题的刻画描述就越深刻。 TFIDF权重是TF权重和IDF权重的组合，公式如下嘭=羔logz(赤)(23)在主题爬行过程中，为了计算网页的主题相关性，通常要先把网页内容文本映射到主题向量空间中，获得代表网页内容的向量。 在对网页内容向量中的特征重庆大学硕士学位论文2主题爬行相关技术词权重进行计算时，所分析的并不是主题网页训练集，而是已经爬行到的网页集，因此，如果此时考虑IDF权重的话，就会存在一些问题。 因为它不仅意味着每爬行一张网页，就要更新优先级队列中所有候选链接的优先级(候选链接的优先级依赖于它所在网页内容的主题相关性)和己爬行到的网页的主题相关分数；而且在爬行初期，IDF值会因为己爬行的网页个数太小而高度的不精确【28】。 所以在主题爬行中，基于特征选择的方法来确定主题向量空间时，特征词的权重计算通常采用TF权重。 而对于基于知识库的方法来讲，主题特征表示的权重计算则具体依赖于所用知识库对概念的描述方法和概念层次体系或知识网络的组织方式。 具体的介绍见下文。 23搜索策略目前，互联网上的资源在数量和种类上都是非常巨大的。 现有的爬行器没有能力也没有必要将互联网上的资源全部抓取。 它们通常都采用一定的遍历抓取策略来进行抓取。 爬行器通常的遍历抓取方式包括深度优先策略、广度优先策略和最优优先策略等。 (1)深度优先策略是爬行器从入口网页的一个URL开始，沿着一条URL链一直爬取，层层深入，一直到达最底层没有URL可爬取为止，再返回入口网页从另一个URL开始按照相同的方式继续进行下去。 深度优先策略虽然可以挖掘到深层次的资源，但却容易忽略爬行的广度，有时会陷入循环链接。 (2)广度优先策略是爬行器从入口网页开始进行逐层的遍历抓取，只有在遍历完本层网页后才进入下一层继续遍历。 广度优先策略更符合通用爬行器的特点，即尽可能广和全面的覆盖到互联网上的资源，但容易忽略深层次一些有用的资源。 (3)最优优先策略是爬行器在爬行过程中要一直维护一个待爬行URL优先级队列，每次爬行时都会从这个队列中挑选优先级最高的URL进行爬取，下载对应网页并分析和计算网页中链接的优先级，最后更新优先级队列。 如此循环重复直到达到终止条件才停止。 如果将链接的优先级高低用其与主题的相关程度来衡量，那么爬行器就会一直优先爬行抓取与主题相关度高的网页，这与主题爬行器最大程度的爬取与主题相关的网页，最小程度的爬取与主题不相关的网页的特点是相符合的，所以主题爬行中通常都采用最优优先策略爬取网页。 BestFi rst策略陋儿12J就是一种最简单的最优优先策略。 它的复杂性和有效性取决于它对候选链接的预测标准和预测方法。 Best。 Fi rst策略因为其简洁性和高效性被认为是最成功的爬行策略之一，也是技术评价中常用的一个基准策略。 重庆大学硕士学位论文2主题爬行相关技术24网页预处理相关技术241网页规范化由通用的主题爬行器框架(见图21)可知，从网上抓取到网页后要先对其进行解析，从而提取网页内容文本和候选链接，为后续的主题相关性计算做准备。 目前互联网上的网页绝大多数是由HTML语言编写的。 HTML语言用一组符号来标记要显示的网页中的各个部分，它是一种规范，也是一种标准。 但互联网上的HTML网页大都是通过服务器端代码自动生成的，因此偶尔会出现一些语法错误或其他不符合W3C发布标准的地方，例如只有开始标记，没有结束标记等错误，虽然这些错误不会影响HTML网页的显示，但常常会使网页解析程序崩溃。 所以为了能够在解析HTML网页时不发生错误，要先对其进行规范化处理，最常用的是Dave Raggett的HTML TIDY29】。 它是一个的HTML检查工具，可以检查并指出一段HTML代码或者一个HTML文件中没有完全符合W3C发布标准的地方，并自动进行必需的修改。 242网页解析在将HTML网页代码规范化后，最重要的就是要从中获取网页内容和候选链接。 但HTML网页是是一种半结构化的文档，怎样从一个单纯的字符串流中区分标记和内容，去掉网页中格式控制元素和无意义的标签信息并提取出有用信息，是很重要的一个环节。 HTML Parser301是目前比较流行的一款功能强大、处理速度快的HTML文档解析和分析工具，是一个纯的J ava写的HTML解析的库。 它将HTML文档中的每个标记都视为一个节点，如果标记之间有文字，则将这段文字也视为一个节点，而整个HTML文档也用一个节点表示。 由于HTML文档中标记之间会相互嵌套，这样整个HTML文档就被表示成一棵节点树。 HTML Parser通过定义一些接口来访问节点，使用者也可以根据自己的需要定义一些方法。 HTML Parser可以实现文本信息抽取、链接提取、资源提取和XML格式转换等信息提取和信息转换功能。 另外，MSHTML31J是微软公司的一个组件，它封装了HTML语言中的所有元素及其属性。 利用MSHTMLdl l提供的IHTMLDocument2类可以从HTML文件的文本流中直接获取一个与该网页对应的DOM对象，通过这个DOM对象提供的标准接口，可以访问对应网页中的所有元素。 243网页分块用网页解析工具虽然可以区分HTML网页中的标记和有实际意义的内容，从而抽取有用信息，但网页通常是由导航、正文内容、广告、相关链接、版本声明等多种信息组成的。 多种信息分布在网页的不同区域，包含着不同