北京大学硕士研究生学位论文

PAGE70北京大学硕士研究生学位论文题目：结合语义相似度的链接分析姓名：朱家稷学号：10308194院系：信息科学技术学院专业：计算机软件与理论研究方向：计算机网络与分布式系统导师：李晓明教授2006年5月

版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。

摘要链接分析技术作为文本分析和日志挖掘技术的有效补充，被广泛应用在主题提取、网页分类、资源发现等诸多Web信息处理任务和服务中。由于Web的巨大、动态变化和复杂，给链接分析技术带来了很大的挑战。链接表达了网页间复杂而隐蔽的关系。为了更有效的进行链接分析，需要细致的考察并区分对待不同的链接关系（后面如何体现？？？）。在本文中我们研究了链接网页间多种属性，包括网页的入度、出度分布，内容相似度和链接相似度等，并且引入了语义相似度的概念。语义相似度描述了网页表达的潜在主题间的相似程度。它与内容相似度和链接相似度相关却又有很大差别。它更精确的刻画了链接网页间语义上的关联程度。我们用语义相似度作为区分链接权重的标准，并将它应用在PageRank的改进中。在PageRank的基本框架下，我们提出了如下假设：浏览者在选择链接浏览下一网页时，他以更大的概率选择与当前网页主题相似的网页链接；并且网页间的语义相似度恰好刻画了网页间主题间的这种相似程度。直接计算网页间的语义相似度是困难的。为此我们计算了链接网页间的内容相似度和链接相似度，并结合当前的研究成果探索了三者间的联系。我们发现CWT100g链接网页间的内容相似度和链接相似度的PearsonCorrelation高达0.74，并且在实验中使用不同的函数来模拟语义相似度和内容相似度之间的关系。实验证明，改进后的PageRank排序在主题提取任务中优于改进前的PageRank排序。关键词：万维网，搜索引擎，链接分析，语义相似度，PageRank

Abstract TechniquesforhyperlinkanalysisarewidelyappliedtovariousWebinformationprocessingtasksrangingfromtopicdistillation,webpageclustering,toresourcediscovery.BecauseofWeb’simmensity,dynamicsandcomplexity,it’sagreatchallengetoconducteffectivehyperlinkanalysis. Hyperlinkscontaincomplexandlatentrelationshipsbetweenwebpages.Itwouldbringgreatefficiencypromotionifwetakeseriousconsiderationstotheserelationships.Inthispaper,westudyvariousfeaturesofhyperlinkedwebpagesincludingindegreeandoutdegreedistribution,contentsimilarity,linksimilarityandetc.Andweintroducetheconceptofsemanticsimilaritywhichdescribesthelikenessofthelatenttopicsbehindwebpagesinsemantics.Semanticsimilarityisrelatedtocontentsimilarityandlinksimilarity,butmorepreciselydescribesthesemanticrelationshipbetweenhyperlinkedwebpages. WeusesemanticsimilarityasthecriterionofhyperlinkweightandapplyittotheimprovementofPageRank.Ourhypothesizesarewhenasurfertraversesahyperlinkfromthecurrentwebpageheisreading,theprobabilityofthehyperlinkheischoosingisrelatedwiththesemanticsimilaritybetweentheoutlinkedwebpagesandthecurrentwebpage,andthemorehighersemanticsimilaritythehyperlinktakes,themorelikelythesurferchoosesthishyperlink. Computingsemanticsimilaritydirectlybetweenwebpagesisdifficult.Westudytherelationshipsofcontentsimilarity,linksimilarityandsemanticsimilarityrefenrecingwithcurrentresearchresults.ForthewebtestdataofCWT100g,weobservethatthePearsonCorrelationbetweencontentsimilarityandlinksimilarityis0.74,andwetriedseveraltypesoffunctionstoroughlymodeltherelationshipbetweencontentsimilarityandsemanticsimilarity. ResultsprovedthatourimprovementonPageRankbringsbettersortofwebpages’importanceintopicdistillationtasks.Keywords:WorldWideWeb,searchengine,hyperlinkanalysis,semanticsimilarity,PageRankTOC\o"1-3"\u第1章引言 71.1 研究背景 71.2本文研究内容 81．3本文贡献 81.4本文组织 9第2章 相关研究 102.1Web挖掘 102.2链接分析 112.2.1模型 112.2.2度量和算法 152.2.3链接分析的应用 192.3搜索引擎 202.3.1搜索引擎发展历史 212.3.2搜索引擎分类 222.3.3基于Robot的搜索引擎基本原理 252.4语义相似度 26第3章链接结构的特征 283.1网页的链接特征 283.1.1链接的URL属性 283.1.2网页的链入链出分布 293.1.3网页间的内容相似度 293.1.4网页的链接相似度 303.1.5网页的语义相似度 313.1.6内容相似度、链接相似度和语义相似度之间的联系 313.2CWT100g网页的链接特征 323.2.1CWT100g链接网页的URL特征 333.2.2CWT100g链接网页的入度出度分布 363.2.3CWT100g链接网页间的内容相似度 363.2.4CWT100g链接网页间的链接相似度 383.2.5CWT100g链接网页间内容相似度和链接相似度的关系 39第4章结合语义相似度的链接分析 424.1PageRank的缺陷 434.2结合语义相似度的PageRank 454.3SemanticEnhancedPageRank公式 464.4结合语义相似度的PageRank实验 494.4.1实验数据集和测试集 494.4.2实验步骤和设置 514.4.3实验结果 524.5算法总结和启示 585.1总结 605.2展望 60参考资料 62作者就读期间参加的科研项目和发表的论文 67致谢 68

第1章引言研究背景万维网（WorldWideWeb，简记为Web）是因特网上最成功的应用。随着Web上信息的飞速增长，针对Web的信息检索已成为一个最具挑战的工作。在对Web上网页进行分析处理的过程中，传统信息检索领域的技术自然的会被引用进来。但Web上网页与传统的文档相比，人们发现Web中的网页有一个极大的相异点——链接。如果我们将每个网页认为是一个节点，每一条链接认为是一条有向边，那么整个Web就构成了一个庞大的有向图。链接结构对网页分析处理提供了更多的信息和手段。链接分析技术已应用于多种目的：衡量特定主题的网页质量。目前的搜索引擎几乎都使用了链接分析技术对返回结果网页进行排序，最重要的有PageRank和HITS算法。描述Web结构特征。比如网页的入度和出度分布，Web直径，Web社区等。网页分类。结合链接信息和内容信息的网页分类的效果高于只基于内容信息分类算法，甚至只依据链接信息的分类效果与内容分类效果相当。（适当的引文willbebetter）网页搜集。依据链接信息，可以针对某个主题或特定目的，对Web进行高效的网页搜集。个性化。链接分析和用户的Web行为日志结合，可以更好预测用户意图，以提供更好的用户体验。但同时我们也应该看到目前链接分析的一些局限和缺点：正由于链接分析技术的成功，使得很多网站为了提高自身的声望，使用了各种linkspam技术使原有的链接分析算法产生误差。(算法缺点：抵抗spam的性能差？)链接有多种目的和类型，而传统的链接分析算法没有区别对待不同类型的链接，这使得链接分析的结果与人们的期望之间产生差别。链接分析技术没有和其它网页分析技术很好的结合。(what’sthis?)本文相信，如果能够改进上述的缺点和局限，链接分析的效果将会更加明显。本文的研究工作也是基于这个目标展开的。1.2本文研究内容本文的研究围绕以下几个方面进行：分析Web链接网页间的特征，主要包括链接网页的内容相似度、链接相似度和语义相似度。给出它们的定义和计算公式，并描述三者间的区别和联系。对PageRank的顺沿链接的跳转策略进行改进：选择链接的网页跳转概率不是均等的，而是与链接网页间的语义相似度相关的。通过网页间的内容相似度来模拟语义相似度，重新评估链接权重和跳转概率，改进PageRank算法。1．3本文贡献本文在链接分析中引入了链接网页间的语义相似度来作为链接权重的评判标准，区别对待链接来提高链接分析的效率。本文认为网页链接与论文引用的很大区别是链接的目的和种类更加复杂。而通过语义相似度作为链接可信度的参考，在链接分析中，区分对待不同的链接，会提高链接分析的效率。分析链接网页间的内容相似度、链接相似度和语义相似度，考查三者间的区别和联系，尝试了用几种函数来模拟内容相似度和语义相似度之间的关系，并比较了它们的效果。利用语义相似度改进PageRank算法。在PageRank的随机游走模型中，浏览者沿着链接跳向下一个网页的概率是相同的。而我们认为，浏览者跳向链接的概率取决当前网页与链接网页间的语义相似度：浏览者以更大的概率跳向相似主题网页的链接（即网页间语义相似度较高的链接）。通过内容相似度来模拟语义相似度，并重新评估网页间跳转的概率来计算PageRank。实验证明，改进后的PageRank对于主题提取任务的精度比原先提高了5％以上。1.4本文组织本文后面是这样组织的，第2章是相关领域的研究；第3章讨论网页链接的特征，给出了链接网页间各种相似度的定义和计算公式，并用CWT100g作为实验数据计算和分析这些相似度；第4章给出结合网页语义相似度的PageRank改进算法和实验结果；第5章是对本文的总结和对未来工作的展望。

相关研究2.1Web挖掘链接分析本身属于一个更大的研究领域的一部分——Web挖掘。Web挖掘是应用数据挖掘技术来从Web数据中抽取有用信息。用于Web挖掘分析的数据种类包括内容数据、结构数据和用法数据[3]。因此Web挖掘可以根据要挖掘的数据种类划分为三类[3,4]：1．Web内容挖掘：Web内容挖掘是从Web文档的内容中抽取有用信息。内容数据是网页要传达给用户的事实集合。它可以包括文字、图片、音频、视频、或者结构记录比如列表或表格等。这个领域的研究经常包括其它学科的技术，比如信息检索（InformationRetrieval，IR）和自然语言处理（NatureLanguageProcessing,NLP）。2．Web结构挖掘：典型的Web图结构是以网页为节点，以连接两个相关网页的链接为边的图。此外，网页内部也可以根据自身的HTML或XML标签组织为一个树形结构。因此，Web结构挖掘是从Web中发现结构信息的过程。这种挖掘既可在网页的层面上（intra），也可以是在链接的层面上（inter）。3．Web用法挖掘：Web用法挖掘是应用数据挖掘技术从Web数据中发现有趣的使用模式，以用来理解和更好的服务于基于Web的应用需求[3]。用法数据跟踪Web用户在访问Web站点时的浏览行为，典型的记录包括Web用户的IP地址，所访问的页面和访问时间。图1展示了Web挖掘领域研究的一个层次分类。对于Web结构挖掘，我们可以把这个领域再划分两个类别，即文档结构分析（比如DocumentObjectModel）和链接分析（连接多个文档的链接结构）。如图所示，链接分析主要专注于文档间的链接结构所提取出的信息。但是，链接分析可以与文档结构分析，Web内容挖掘或Web用法挖掘结合使用。比如，链接提供的结构信息和Web内容结合，可以更好的挖掘Web有用信息和衡量信息质量。图1.Web挖掘分类及链接分析在Web结构挖掘中的位置(摘自[2])2.2链接分析根据[2]的总结，链接分析的研究包括模型、度量标准及算法，以及应用等。以下给出这些研究的描述。2.2.1模型大多数链接分析的研究都会有一个基本的Web结构的表示模型，各种度量和算法都基于这个模型衍生而来。不同类型的模型包括图结构模型，统计模型，网络流模型等。图结构模型在这一节，我们讨论各种Web挖掘中表示某种概念和信息单元的图结构。图结构包括单节点结构，多节点结构和图中所有节点的结构。单节点结构单节点结构模型包括一个单独的节点（网页），以及链向它或从它链出的链接。Authority：一个authority网页是指被大量其它网页链向的网页。Hub：一个hub网页是指链向大量其它网页的网页。一个好的hub网页会链向很多好的authority网页；而好的authority网页会被很多好的hub网页所链向。Hub和authority的概念首先在[30]中被引出。单节点模型通常用来决定网页的质量[11,12,13]。多节点结构多节点结构包括多个节点以及它们之间的链接。一些结构和模式已经在[14]中讨论。我们下面将描述这些模型和概念：共同链入（Co-Citation）：如果节点A同时链向节点B和C，那么节点B和C被A共同链入。在Web上，共同链入直观上表明网页B和C间的某种相似。共同链出（Co-Reference）：如果节点B和C同时链向节点A，那么节点B和C共同链出A。和共同链入一样，共同链出也表明网页B和C间的某种相似。有向二分图(DirectedBipartiteGraph)：如果图G可以划分为两个节点集合F和C，每条有向边都从F中的某个节点u链向C中某个节点v，那么图G为有向二分图。完全二分图（CompleteBipartiteGraph）：如果二分图G包含所有的从F链向C的边，那么G为完全二分图。二分核（BipartiteCore）：核(i,j)是一个完全有向二分子图，并且F中至少包含i个节点，而C中至少包含j个节点。在Web图中，这包含链接的i个网页被称为“fans”，而被链向的j个网页被称为“centers”。从概念角度来说，二分核的“fans”和“centers”基本就是hub网页和authority网页。对某个主题的网页集合来说，可以寻找二分核来发现该主题的hub网页核authority网页。Hub网页和authority网页表示了这个主题的良好的信息来源。社区（Community）：社区是被hub网页共同链向的authority网页的核心[15]。它还被定义被一组网页集合，使得集合中网页在社区内的链接度（任意方向）大于社区外的链接度[16]。整体图结构领结模型（Bow-TieModel）：[7,17]提出了Web图的领结模型，详细描述了Web图的各种属性、度量和方法。领结结构包含一个强连通部分（SCC），一个链向SCC的部分（IN），一个被SCC链向的部分（OUT），还有一些不相连的部分。马尔可夫模型（MarkovModel）n阶马尔可夫链表示系统的下一状态只由当前状态和前n-1个状态决定。1阶马尔可夫模型通常用来模拟用户的浏览行为。PageRank[11]和随机HITS[18]就使用了基于马尔可夫模型的随机游走过程：用户随机选择跳向某个新网页或跟随链接到某个网页（在PageRank中是正向链接，而在随机HITS中根据不同的时间步，选择正向链接或反向链接）。其它的方法，比如SALSA[12]也引入了马尔可夫随机游走过程。[19]中使用马尔可夫链为自适应网站预测链接。Web游走模型，即基于马尔可夫模型的链接跳动，被链接分析大量使用。最大流模型（MaximalFlowModel）s-t最大流问题可以表述如下：图G=(V,E)，每条边被赋予为正数的传输能力，s和t是G的两个不同节点，问题是要找到从s到t的最大流能力。[20]提出最大流问题等价于“minimalcut”问题，即从图G去掉最小数量的边，使得s和t分割。已有一些算法被提出来解决这个问题[21,22]。[17,23]中应用这些算法来识别“Web社区”，其被定义为“社区内部链接度大于社区外部链接度的网页集合”。概率关系模型（ProbabilisticRelationalModel）概率关系模型是关系模型和贝叶斯置信网络的结合。类内部属性的关系合类间属性的关系可以通过赋予不同的概率分布来建模。[24]将网页和链接作为实体，并赋予它们间以关系。一个网页实体的属性包括：hub，category，words等；而链接实体包含属性exists，表示网页实体间的关系。通过预先给出的网页实体category属性的概率分布，可以利用贝叶斯和置信传播方法来进行文档分类。其它模型[25]提出“probabilisticfactoredmodel”来识别authority网页。[26]中定义Agora网页为被多个网页链向的网页，且根据Google的PageRank在它们的社区中排名靠前；其目的在于识别刚浮现出的社区。还有其它一些对hub、authority和PageRank的改进[18,12,27,28,29]在这里不在讨论。2.2.2度量和算法链接可以用来作为单个网页、一组网页或整个Web结构属性的度量标准。例如，链接分析已被用来作为衡量主题网页的权威性、网页知名度和网页间距离的有效工具。已有多种方法利用链接分析来衡量网页质量。一些标准基于Web图的随机游走模型，而一些基于Web结构的完全二分图和二分核，还有的基于概率和随机方法。这些度量标准还有一个区别是它们是否与查询相关。在本节，将给出利用链接信息的一些的常用的度量和算法。链接在衡量单个网页、一组网页和整个Web图的属性上非常有用。平均点击度（AverageClicks）是利用链接结构衡量网页间距离的一种方法。可以根据度量的元素是单个网页、多个网页和整个Web对这些度量标准进行分类。PageRank[11]、HITS[30]、SALSA[12]和网页知名度（WebPageReputation）[13]用来衡量单个网页的质量。PageRankPageRank是对网页质量进行排名的一个标准。[11]使用这个度量应用于Google搜索引擎。其主要思想是如果一个网页的所有链入网页的排名总和很高，那么这个网页的排名也会很高。因此一个网页的排名取决于链向它的网页的排名。排名是一个迭代的过程，直到所有网页的排名稳定。排名的公式如下：直观上看，PageRank是在Web图上的随机游走的分析方法。ε表示一个随机冲浪的用户直接跳转的概率，比如通过键入URL、从书签中或特定主页中访问某个网页。n表示总网页数。ε/n即表示随机直接跳转到网页的概率。对所有链向的网页，从沿着链接跳转到的概率是的链接出度的倒数，即假设跳向任意链接的概率是相同的。其右面的项则表示通过链接跳转到网页的概率。而整个PageRank值即表示用户停留在网页的概率。PageRank是与查询无关的全局值。[33]给出计算PageRank的高效方法。PageRank和其它排名标准的稳定性在[18,27,34]中讨论。根据[18,34]，只要PageRank值高的网页的链接结构没有改变，那么修改链接结构对排名的影响不大。其中的一个主要原因在于随机直接跳转的存在。HITS前文提到的hub和authority值可以通过HITS算法来计算。其主要过程是，首先通过查询得到一组相关的网页集合（rootset），加入rootset的链入链出网页得到扩展的baseset。构造baseset中网页的authority值和hub值可以通过如下公式迭代计算：HITS算法对主题查询的应用是成功的。但有时候会出现“主题漂移”的现象，即一个细节查询的结果可能是其概括问题的结果，或者相反。其原因是HITS趋向与给出Web图中链接密集处的主题结果。[28,29]中对HITS中的邻接矩阵进行了改进。IBM的CLEVER[31]使用了基于HITS的算法来进行Web搜集、网页分类和识别Web社区。SALSASALSA（StochasticApproachforLinkStructureAnalysis）由[12]提出。它结合了随机游走模型以及HITS中的hub和authority。和HITS一样，SALSA也是与查询相关的。其主要思想是，在由查询词构成的Web子图上随机游走，游走者会以较大的概率访问高质量信息的网页，即authority值较高的网页；同样，游走者会以较大的概率访问链向较高的authority网页的网页，即hub值较高的网页。它的查询词网页集合的构造与HITS相同，然后以此集合得到一个无向的二分图G。两种游走方式来计算网页的hub和authority值。一种是游走于G的hub子图部分而生成hub值，另一种游走于G的authority子图而生成authority值。当执行游走过程时，游走者从二分图的一个部分开始，每步跳跃两条边——第一条边将他带到图G的另一部分，而第二条边将他带回原来的部分。利用马尔可夫模型帮助即可估算出游走者访问hub子图或authority子图中某个节点的概率。其游走过程的概率矩阵H和A表示如下：通过计算H和A的主特征向量，即可得到网页的hub值和authority值。由于引入了随机游走，SALSA不会出现HITS的“主题漂移”问题。WebPageReputation在[13]中，作者提出了网页在不同主题下“声望”的概念。与SALSA相似，它也是执行两阶段随机游走过程，并计算针对某个主题的网页的authority声望和hub声望。其每步游走的原理是：以概率d>0，游走者随机直接跳向某个网页；以概率1-d，游走者从所在网页沿着正向链接或反向链接跳向另一个网页。其authority声望和hub声望的定义分别是：AuthorityReputation：针对某个主题，游走者正向游走访问网页p的概率。HubReputation：针对某个主题，游走者反向游走访问网页p的概率。其计算公式在这里就不在列出。平均点击度（AverageClicks）在[34]中提出用点击度（numberofclicks）来衡量网页间的距离不能与人们的直觉相符。因为用户以较大的概率沿着链接数较少的网页跳转，而以较小的概率沿着链接数较多的网页跳转。因此，他们提出平均点击度，它基于随机游走中点击某个链接的概率。根据这个模型，定义网页p中链接的长度为。因此网页p与q间的距离为p到q的最短路径上的链接长度之和。平均点击度可以用来过滤网站以识别一定距离内的Web社区，也可以用来衡量用户在网站内访问到需要信息的代价，以改善网站的友好性和可用性。信息气味（InformationScent）信息线索的概念是指利用网页链接周围的信息片断作为“气味”来评估它链向的网页质量和访问该网页的代价[41]。其基本思想是用户在某个网页搜寻信息时，会跟踪“气味”最浓的链接。“气味”的计算方法是比较用户信息需求与链接信息片断的相似度。其它其它一些重要的概念包括网页的共同入度和共同出度。网页p和q的共同入度表示同时链向p和q的网页数，共同出度表示p和q同时链向的网页数。[1]中讨论了这些概念。Web图的属性包括Web直径，连通性、入度和出度分布等。[6,7,17]给出了Web直径的讨论，并指出Web网页的入度和出度分布遵从“powerlaw”分布。在整个Web结构研究中，发现Web社区是一个热点。其主要方法是最大流方法[17,23]。2.2.3链接分析的应用链接分析技术被广泛应用，包括判断主题网页的质量，网页分类，网页搜集，社区发现，网站优化，个性化和网页推荐等。本节将介绍一些应用。主题提取（TopicDistillation）主题提取是从网页集合中识别与主题最相关的网页。在[50]中它被定义为“寻找指定主题的密切联系的authority网页和hub网页”。HITS算法[30]本身就是一种典型的主题提取算法。基于文档对象模型（DocumentObjectModel）的更精细的链接分析算法在[50,51]中讨论。[52]改进PageRank，提出主题相关的PageRank算法。网页分类网页分类是将网页划分到指定的类别中。[53]给出了8种网页类别和7种描述网页特性的属性。[54]给出一种基于链接和上下文的自动网页分类方法，其主要思想是如果一个网页被其它网页链向，其链接上下文会给予一定的权重，因为它表示某些人通过链接信息而阅读了该网页。[24]将网页和链接看作实体－关系模型中的实体，并用概率关系模型来进行网页分类。[55]给出了利用主题类别和自动分类器来估计整个Web上的主题分布。Web社区识别整个互联网存在着成千上万的社区。这些社区有的已经以非常清晰的形式表现出来(例如，门户网站中的层次目录式结构)。但是，在极度分散和无序的互联网环境中。有理由认为必然还存在更多潜在的未被发现和定义的互联网社区．从互联网中系统地抽取这些社区至少有以下3方面的意义：·这些社区为了解互联网用户的兴趣提供了有价值的，甚至是最及时、最可靠的信息。·这些社区展现了互联网社会学(sociologyofweb)，研究和发现这些社区可以深入了解互联网的进化过程。·门户网站通过识别和区分这些社区，可以更有效地组织它们的目录层次(因为很多潜在的社区以很快的速度在增长，而很多已经清晰出现的社区又在逐渐消失)。这同时意味着互联网的自动分类成为可能。主要的社区发现技术有最大流算法[17,23]的和基于二分有向图算法[55]。Web搜集“主题搜集”是一种针对特定主题的高效网页搜集方法[50]。在搜集中，需要识别主题中好的authority网页和hub网页，还要决定是否跟踪某个链接进行搜集[50]。2.3搜索引擎Web给人们带来了巨大的方便，使人们可以跨越时间和空间的界限共享大量的信息。但是，面对如此大量的信息，人们同时也开始感到无所适从。太多的信息使他们很难迅速定位到真正需要的信息，而跟随超链接在Web上漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在Web上进行导航。这种需求导致了搜索引擎的问世。搜索引擎迅速成为人们网上搜索的有效工具。2.3.1搜索引擎发展历史如何在包含海量信息的互联网上获得有价值的信息一直是Web用户关注的焦点问题。搜索技术的出现为用户快速定位所需信息带来了福音。1993年，Internet上出现了最早的Web浏览器Mosaic，次年Netscape推出了Navigator，浏览器的发展促使Web得到迅速推广，同时也推动着搜索引擎的发展。1994年春天出现了最早的真正意义上的搜索引擎—Lycos。当时MichaelMauldin将JohnLeavitt的spider程序接入到其索引程序中，实现网页的自动发现和索引。随后,Infoseek和Exite也相继出现。这些搜索引擎主要出于研究目的，解决的主要问题是“查全率”。它们一般都索引少于100万个网页，响应时间都在10秒以上。我们称之为第0代搜索引擎。1996年出现了第1代搜索引擎。这些搜索引擎一般每天能够接受1000万次检索，并且能够索引大约5000万网页。这一代搜索引擎的代表是AltaVista和Inktomi。它们的实现方法大不相同。AltaVista采用大型的多处理器计算机来支持它们搜索引擎的运转；而Inktomi则采用分布式方案来解决搜索引擎对计算能力的要求。大约到了1998年，出现了第2代搜索引擎。此时，搜索引擎技术得到了空前的发展。这个时期搜索引擎发展的主要特点有：1）开始出现了主题搜索和地域搜索。很多小型的垂直门户站点开始使用这些技术。2）随着大型多处理器计算机以及分布式技术的应用，搜索引擎搜集、索引网页的能力得到空前的提高。这个时期的搜索引擎都试图收集“整个Web”。“查全率”问题已不是主要矛盾。但是随着索引网页规模的扩大，检索结果的准确性成了主要问题。检索结果相关度评价或“查准率”问题成为研究的焦点。其典型代表为Google和Inktomi。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面Stanford大学的Google系统和IBM的Clever系统作出了很大的贡献；另一类是用户信息的反馈，DirectHit系统采用的就是这种方法。2.3.2搜索引擎分类尽管目前存在数量众多的搜索引擎，但根据它们所基于的技术原理，可以把它们分成三大主要类型：基于机器人（Robot）的搜索引擎、目录式（Directory，或Catalog）搜索引擎和元（Meta）搜索引擎。1）基于机器人的搜索引擎这种搜索引擎的特点是利用一个称为Robot（或Spider、WebCrawler或WebWanderer）的程序以某种策略在互联网中自动搜集和发现信息，由索引器为搜集到的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向网页的全文检索服务。基于Robot的搜索引擎一般要定期访问大多数以前搜集的网页来刷新索引，以反映出网页的更新情况。同时还要去除一些死链接和镜像网页。网页部分内容的变化情况将会反映到用户查询的结果中，这是基于Robot的搜索引擎的一个重要特征。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表国外有Google、AltaVista、NorthernLight、Excite、Infoseek、Inktomi、FAST、Lycos等；国内有天网、百度、悠游等。2）目录式搜索引擎这种搜索引擎以人工方式或半自动方式搜集信息。目录式搜索引擎的数据库是依靠专职编辑或志愿人员建立起来的。这些编辑人员在访问了某个Web站点后撰写一段对该站点的描述，并根据站点的内容和性质将其归为一个预先分好的类别，把站点的URL和描述放在这个类别中。信息大多面向网站，提供目录浏览服务和直接检索服务。很多目录也接受用户提交的网站和描述，当目录的编辑人员认可该网站及描述后，就会将之添加到合适的类别中。目录的用户界面基本上都是分级结构，首页提供了最基本的几个大类的入口，用户可以按照目录结构层层向下访问，直至找到自己感兴趣的类别。另外，用户也可以利用目录提供的搜索功能直接查找一个关键词，该类搜索引擎因为加入了人的智能，因此用户从目录搜索得到的结果往往比从基于Robot的搜索引擎得到的结果更具参考价值。缺点是需要人工介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代表有Yahoo!、AOL等。3）元搜索引擎元搜索引擎通常被称为搜索引擎之上的搜索引擎。用户只需递交一次检索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将所有查询结果集中起来以整体统一的格式呈现到用户面前。由于采用了一系列的优化运行机制，能够在尽可能短的时间内提供相对全面、准确的信息，而且即使不能完全满足用户需求，仍可以作为相对可靠的参考源进行扩展搜索，因此成为倍受推崇的检索首选入口。一个真正的元搜索引擎由三部分组成：检索请求提交机制、检索接口代理机制、检索结果显示机制。“请求提交”负责实现用户的检索设置要求，包括调用哪些搜索引擎、检索时间限制、结果数量限制等。“接口代理”负责将用户的检索请求“翻译”成满足不同搜索引擎“本地化”要求的格式。“结果显示”负责所有源搜索引擎检索结果的去重、合并、输出处理等。这类搜索引擎的代表有：ByteSearch、Mamma、MetaCrawler、Profusion等。这三类搜索引擎中，元搜索引擎是基于第1类和第2类搜索引擎的。第一类搜索引擎（基于Robot的搜索引擎）与第二类搜索引擎（目录式搜索引擎）各有如下特点：1）基于Robot的搜索引擎自动收集、分析和处理网页，因而它索引的网页数多，信息量大，并且能够定期重新收集网页，更新索引库的内容，向用户提供最新的Web网页信息。但是它只提供基于关键词的检索，用户只有确切的知道自己感兴趣的网页含有哪些关键词时，查询的效果才比较理想。否则，返回的结果很可能和用户的实际需求“风马牛不相及”。2）目录式搜索引擎支持基于分类目录的查询。目录式搜索引擎对收集的网页采用人工分类。由于这种人工方式对网页内容的理解比较准确，因此查询的准确性优于Spider式搜索引擎。当用户对某个领域感兴趣但并不熟悉这个领域的关键词时，这种查询方式能为用户提供更好的服务。由于人工分类效率低，网页更新困难，目录式搜索引擎在索引的网页的规模上受到了很大的限制。Google等Spider式搜索引擎索引的网页数量早以突破十亿级，而yahoo！还停留在千万级的水平。由于目录式搜索引擎完全采用人工进行网页的搜集和分类，其网页规模和更新速度与Internet的网页总量和网页更新速度相差太远，其涵盖的范围无法满足用户的需要，已经逐渐被基于Robot的搜索引擎代替。同时，基于Robot的搜索引擎在用户的抱怨声中不断成长，不断改进检索质量，目前已经成为Web用户发现网上信息必不可少的工具。2.3.3基于Robot的搜索引擎基本原理 因为本文中的所有实验和结论都是在“天网”搜索引擎的基础上进行，前文中提到，“天网”属于基于Robot的搜索引擎。下面简要介绍一下这类搜索引擎的基本工作原理。搜索引擎的通用结构如图2所示。图2 搜索引擎通用结构图(摘自[48]）搜索引擎的工作包括如下3个过程[49]：1）搜集Web信息：发现、搜集Web上的网页信息。需要有高性能的搜集器自动的在Web中搜索信息。Web信息搜集器是下载Web上网页的程序。它顺着网页之间的链接移动，自动下载所经过的网页。给定起始URL集合S，Web搜集器不停的从S中移除URL，下载相应的网页，解析出网页中的超链接URL，将未访问过的URL加入集合S。Web搜集器也称作Web机器人或Web蜘蛛。搜集器把所获得的信息保存下来以备建立索引库和用户检索。2）索引库的建立：对搜集到的Web信息提取和组织，建立索引库。这关系到用户能否迅速找到准确、广泛的信息。对搜集器抓来的网页信息快速建立索引，通常采用倒排表技术。如果在建立索引库的过程中对用户在检索端搜索的查询串进行跟踪，并对查询频率高的查询串建立Cache，可以在检索端请求时，加快索引库的响应速度。3）检索端的查询：根据用户输入的查询字串，在索引库中快速检索出文档。采用基于网页内容分析和基于超链分析相结合的方法进行相关度评价，对检索出的网页进行客观的排序，从而尽量保证搜索出的结果与用户的查询串相一致。然后将输出的结果返回给用户。为了加快检索端的响应速度，可以根据最近用户查询信息建立检索端Cache。2.4语义相似度语义一般是指词语的意义所指。它通常和句法相对，语义是意义所在，而句法是语义表达的外边形式。 在概念网络中，衡量本体对象和它们之间的关系时，语义相似度是其知识表示的一个关键。我们这里讨论的语义相似度是指在一个分类系统(taxonomy)中两个概念或主题间的相似程度。比如WordNet[21]和OpenDirectoryProject（ODP）[32]中网络节点间在语义上的关联程度。[35,36,37,38]给出了各种表示语义相似度的表示形式，我们下面给出一种最常见的形式。 在信息理论中[5]，一个主题t的信息内容用其出现概率的负对数表示，即-logPr[t]。而两个主题间的语义相似度是其公有的信息内容与其各自信息内容和的比率，即其中是其公有的信息主题。如何用树状结构来表示主题分类的话，那么就是其共同的祖先节点。 比如，图3是WordNet中的一个片断。每个节点旁的数字使其出现概率。那么概念Hill和Coast的语义相似度可以如下计算：其结果为0.59。图3.WordNet片断（摘自[56]）关于如何计算网络中的节点的语义相似度，[6]给出了很好的解释。

第3章链接结构的特征3.1网页的链接特征图4.网页的链接结构ACD图4.网页的链接结构ACDB我们知道，链接是为了满足人们多种需要而存在的：比如浏览导航，相关引用，推荐和广告等等。链接的最相关的属性有三个：源网页（或其一部分），链接文字（anchortext）和目的网页（或其一部分）。我们细分网页的属性，又包括网页URL，网页内容及主题，网页的链入和链出情况（或其在链接结构中的特征）。目前的研究对各个属性均有涉及：3.1.1链接的URL属性我们知道网页的URL是一种层次结构：它主要由主机名和路径构成，而主机名又是一种层次结构，由大至小可分为域（domain），域名（domainname）和主机名。对链接来说，主要是根据链接的源和目的网页的URL是否拥有相同的主机名将链接分为主机内部链接(intra-hosthyperlink)和主机外部链接(inter-hosthyperlink)。类似的定义包括站内链接（intra-sitehyperlink）和站外链接（inter-sitehyperlink）。更高的层次包括域内链接（intra-domainhyperlink）和域间链接(inter-domainhyperlink)。大量的实验研究数据表明，主机内部链接的比例占链接的绝大部分（80％以上），另外同域链接和域间链接情况也是研究的一个热点[43,44]。3.1.2网页的链入链出分布网页链入度和链出度的遵从“powerlaw”分布。其用公式可以表达如下：其中x表示网页的链入（链出）度，而y表示表示拥有该链入（链出）度的网页数量。在对数图中，“powerlaw”曲线是一条直线，因为是一个线性公式。K的取值为负实数。我们会在下一节给出各种链入链出度的分布图。从中可以看出它们符合“powerlaw”分布。3.1.3网页间的内容相似度在传统的文本处理领域中，一个文本被看作是一定特征项的一种分布（？），因此文本就被表示成一个特征项向量，其中是第i个特征项的权值，n是特征项的总数。这样，每个文本就被映射到了向量空间中的一个点，因而向量空间中的点的距离就可以用来衡量其对应的文本的相似性。在量化方法上，对权值的计算，比较常用的是TF-IDF方法[42]，其计算公式如下：其中是第i个关键词在文档D中的出现频率，N是文档集中的文档总数，是文档集中含有第i个关键词的文档数。相似性的计算有很多方法，较为常用的是计算对应向量的Euclid距离、cosine距离[39]和内积[40]。给定向量， （1） （2） （3）（1）Euclid距离，（2）cosine距离，（3）内积3.1.4网页的链接相似度网页的链接相似度可以通过两个网页间共同链入度或共同链出度计算。[8]给出了以下的链接相似度计算公式：其中网页p的链出、链入和自身的URL集合。当然我们可以参考网页内容的TF-IDF表示，将每个网页的链接URL集合中的每一项权值化。3.1.5网页的语义相似度在上一章中，我们给出了分类体系中节点的语义相似度的定义公式。在这里，我们也假设存在对所有网页的一个分类体系或其概念网络，并且每个网页属于其中的一个或多个节点。在很多实验中使用的OpenDirectoryProject(ODP)的目录结构可以看作是这个分类体系的近似。有了这个分类体系后，我们定义网页间的语义相似度，即是其所属的类别间的语义相似度。3.1.6内容相似度、链接相似度和语义相似度之间的联系为了叙述方便，内容相似度、链接相似度和语义相似度分别用，，表示。[8,45]中通过对OpenDirectoryProject（ODP）中的38亿（实验用的数据量？！）个网页对计算它们的内容相似度、链接相似度和语义相似度，并研究三者间的差别和联系。根据[8,45]的结果，－，－和－的PearsonCorrelation都很小，分别为0.10，0.11和0.08。但是考虑到数量的巨大，这也说明三者间仍存在较强的关系。图5给出了[8,45]中三者相似度间的分布。其中颜色亮度越高，表示其区域的统计数量越大。网页内容与网页链接间有两个著名的假设：网页链接内容相关假设（TheLink-ContentConjecture）和链接内容聚类假设（TheLink-ClusterConjecture）。网页链接内容相关假设指如果两个网页存在链接，那么这两个网页间内容相关的可能性很大。链接内容聚类假设是指同一主题的网页很可能在链接结构中聚成一团的。[9]就提出了主题在链接上的局部性：存在链接关系的网页间内容相似度比随机挑选的两个网页间的内容相似度明显高出。[10]给出上述两个假设的形式化定义，并通过实验验证。可以说这两个假设是目前很多链接分析算法和应用（比如主题提取，网页聚类，主题抓取等）的基础。图5.内容相似度、链接相似度和语义相似度分布图(摘自[8,45])3.2CWT100g网页的链接特征为了清晰认识链接的这些特性，我们分析了中文网页测试集CWT100g[46]的链接特征。CWT100g根据天网搜索引擎截止2004年2月1日发现的中国范围内提供Web服务的1,000,614个主机，从中采样17,683个站点，在2004年6月搜集获得5,712,710个网页，包括网页内容和Web服务器返回的信息，容量为90GB。我们通过去除jsp和asp网页，共提取网页数量4,865,066个，我们采用这4,865,066个网页来计算其链接关系。其统计结果如下表：表格1.CWT100g数据的统计结果参考变量数量（单位：个）网站个数17,760网页数量4,865,066主机内部链接总数36,753,069主机间链接总数477,173有出度的网站3,091网站平均网页数273.9每个网页平均包含链接数CWT100g链接网页的URL特征我们知道，站内链接和站外链接的作用是不同的。站内链接主要是为了方便浏览，而站外链接的作用则比较复杂。因此，我们专门考查了CWT100g的站外链接。判断一个链接是否是站外链接的方法是：首先比较链接的源网页和目的网页的URL的hostname，如果两者相同，那么该链接属于站内链接；否则比较其注册域名是否相同，如果相同，则属于站内链接，否则属于站外链接。比如从/index.htm到/~wbia/的链接属于站内链接，因为它们的hostname相同；从/index.htm到的链接同样属于站内链接，因为两者的注册域名同为pku；而/index.htm到的链接属于站外链接。通过上面方法的统计，我们得到CWT100g的站外链接共140,388个，涉及的网页数共115,754（这么少？！）。我们对域的划分遵守传统的域名分类，即com,net,edu,org,gov。考虑到国内的cn域名，我们把以，，，，结尾的主机名仍划分到上述相应的类别中；其它以cn结尾的主机名属于cn类。不属于以上分类的归结到others类。这些网页的域分布如图6：图6.站外链接的所有网页的域分布我们把这些网页分为源集（sourcepageset）和汇集(destinationpageset)。源集包括所有站外出度大于等于1的网页；而汇集包括所有站外入度大于等于1的网页。源集的网页数有109,714，而汇集的网页数为7,027；由此可知，既属于源集又属于汇集的网页有987个。我们考查了源集和汇集在不同域间的分布。源集和汇集网页的在这些域类的分布如图7。从图可知，com[.cn]类占据了最主要部分；另外观察源集和汇集分布的差异是：edu[.cn]类和gov[.cn]类的比例在汇集中显著上升，这与我们的直观体验是相符的，教育和政府网站的权威性要高于其它类别网站。图7站外链接的源集和汇集网页的域分布我们还考查了不同类别的域间的链接情况，如表2所示：表格2.站外链接的在各类域间的分布com[.cn]net[.cn]edu[.cn]org[.cn]gov[.cn]cnotherstotalcom[.cn]38.80%17.76%1.76%1.18%1.10%0.90%0.10%61.60%net[.cn]4.19%6.04%1.81%0.20%0.96%0.15%0.01%13.36%edu[.cn]0.42%0.10%0.93%0.06%0.08%0.12%0.00%1.72%org[.cn]6.95%0.22%0.17%0.05%0.18%0.03%0.00%7.59%gov[.cn]1.32%0.20%0.24%0.37%2.93%0.05%0.00%5.10%cn9.22%0.36%0.28%0.06%0.09%0.05%0.00%10.05%others0.24%0.07%0.07%0.01%0.03%0.02%0.00%0.43%total61.13%24.73%5.26%1.93%5.37%1.32%0.11%100%表格2中的每个单元格表示所在行的域类别到所在列的域类别的链接数占总链接数的百分比。比如第6行，第2列的数据表示gov[.cn]到com[.cn]的链接数占总链接数的1.32%。从中我们可以看到com[.cn]的链入和链出占据很大一部分，其次是net[.cn]。而且域的自链接性也很突出，即域内的链接占据了首要位置，这可以从com[.cn]，net[.cn]，edu[.cn]，gov[.cn]看到。3.2.2CWT100g链接网页的入度出度分布图8给出了源集和汇集网页的站外出度和入度分布情况。其中横轴表示网页的站外出度（入度），纵轴表示网页数。注意该图是对数图，从类似直线的分布可知，网页的站外出度（入度）仍遵守“powerlaw”。图8.站外链接的源集和汇集网页的入度、出度分布3.2.3CWT100g链接网页间的内容相似度我们还考查了链接网页间的内容相似度。计算链接网页间内容相似度的方法是利用前文提到的TF-IDF公式得到网页的词权重向量，然后计算向量间的余弦夹角来表示网页间的内容相似度。内容相似度其值范围是0到1，值越大表明网页间的内容相似度越高。图9给出CWT100g所有链接网页间的内容相似度分布。其横轴表示内容相似度的取值范围，纵轴表示内容相似度落在某个区间范围（区间大小为0.05）内的链接数占总链接数的百分比。蓝色曲线是根据其分布点自动拟和得到的类高斯曲线？（加入了因子和纵向间距）。从图9中可以看出，大部分网页间的内容相似度都很小，60％以上的网页间内容相似度小于0.3。我们还特意考查了其站外链接网页间内容相似度，如图10所示。可以看到，站外链接的内容相似度更聚集在取值较小的区域内。图9.链接网页间的内容相似度分布图10.站外链接网页间的内容相似度分布3.2.4CWT100g链接网页间的链接相似度根据前面给出的链接相似度计算公式，我们计算了CWT100g的链接相似度分布，如图11，可以看到大多数的链接相似度都很低。在高于0.7以后，其分布有增长的趋势，这主要是一些网站的网页间紧密环绕导致的。图11.链接网页间的链接相似度分布3.2.5CWT100g链接网页间内容相似度和链接相似度的关系在图12中我们给出了CWT100g链接相似度－内容相似度分布变化的三维曲面图。该图的含义如下，固定链接相似度,其的分布比例就是沿轴方向的一条曲线。该曲面的左前端和右后端突起最明显，分布表明当链接相似度很小或很大时，内容相似度与之相应一致的概率很高。而曲面的中间部分虽然突起却并不明显，表明当链接相似度取值中间时，其内容相似度的取值的一致性并不高。左后端的突起说明虽然有些网页间的链接相似度很低，但其内容相似度可能很高。而右前端并没有明显突起，表明链接相似度很大而内容相似度很小的概率并不很大。最后，我们对的每个小区域内求的期望与其对应的的期望，构造其－的期望的散点图，并通过线性函数拟和（what’sthis?与曲面图上看到的不一致？）。如图13所示。我们还求得CWT100g的和的PearsonCorrelation为0.74。这个值比[8]中计算出来的值要高出很多，一是因为我们只考查存在链接关系的网页对，而[8]中考查了所有网页对；另外这与CWT100g的站内链接占据了绝大部分有很大原因。图12.链接相似度－内容相似度的三维曲面图图13.链接相似度-内容相似度期望的散点分布图最后因为CWT200g没有分类树，所以我们无法直接给出其语义相似度的分布曲线。在下一章，我们利用[8,45]中的研究结果，用可以显式计算的内容相似度和链接相似度来模拟语义相似度，并用此来提高链接分析的效率。

第4章结合语义相似度的链接分析链接分析的应用决定了不同的链接分析方法。在这里我们主要关注应用在搜索引擎上的链接分析方法。搜索引擎，作为一种信息检索系统，衡量它的查询质量有两个重要的标准，“查全率”（precision）和“查准率”（recall）。查全率在信息检索领域的定义是系统在进行某一检索时，检出的相关文献量与系统文献库中相关文献总量的比率，它反映该系统文献库中实有的相关文献量在多大程度上被检索出来。对于搜索引擎，查全率是指搜索引擎返回的结果占Internet上所有相关网页的比率。查准率在信息检索领域的定义是系统在进行某一检索时，检出的相关文献量与检出文献总量的比率，它反映每次从该系统文献库中实际检出的全部文献中有多少是相关的。对于搜索引擎，因为用户通常只关注返回结果最前的几页，所以其返回结果的排序非常重要。因此衡量搜索引擎效率最常用的指标是P@10。它表示在前10个返回结果中，相关文档所占的比率。目前的搜索引擎在计算返回结果的排序上越来越复杂，考虑的因素也越来越多。但一般来说，有两项因素是需要考虑的，一是返回结果的网页内容与查询词的相关性，二是该网页在链接结构中的重要程度。网页内容与查询词的相关性的计算不属于本文的研究范围；我们主要关注网页在链接结构中的重要程度，改进链接分析的方法，最终来优化返回结果。搜索引擎最常用的链接分析算法是前面提到的HITS算法和PageRank方法。下表是对两者的一些特征的比较和总结。表格3.HITS算法和PageRank算法特征比较HITSPageRank是否与查询相关是否计算方式在线离线稳定性较差较好现实中很多搜索引擎使用了PageRanks算法及其变体。其主要原因一是PageRank只需要离线计算一次，而HITS算法对每个查询都需要重新计算，在Web网页数量和查询数量都在迅速增长的情况下，PageRank有更好的响应速度；二是HITS的计算只针对一个很小的子图，HITS算法对该子图的结构非常敏感，子图的微小改变可能就会来最终结果的很大改变，而PageRank是对整个Web的链接结构图计算，其稳定性要好一些。基于这些原因，我们下面给出的结合语义相关度的链接分析以PageRank其基础框架；然而，其主要思想仍可以应用到HITS算法中，甚至其它任务的链接分析中。4.1PageRank的缺陷PageRank作为目前最为成功的链接分析算法之一在搜索引擎中应用广泛。但PageRank也有其自身的缺陷：PageRank得到的网页重要度评分是与查询无关的。这样导致的结果是针对某个特定查询，返回结果中一些与查询相关不大的网页因为PageRank值过高而被放在返回结果的前列。这也是TopicPageRank的被提出的原因[20]。鉴于本文的研究，我们并不深入讨论这一点。PageRank无差别的对待不同链接。即在其randomsurf模型中，浏览者从一个网页跳向它链向的其中任一网页的概率是相同。而在现实中，浏览者跳向下一网页的概率直接受到其阅读兴趣和链接信息的影响，并不是等概率的。为了说明这一点，图14展示了一个典型的网页链接情况。其网页顶部的链接用于站点内部导航；两侧的链接是赞助商的广告；而中间的链接是该网页主题相关的链接。当浏览者到达该页面时，他在下一时刻会选择哪个链接呢？一般情况下，浏览者如果选择浏览了该网页，那么他会最可能选择相关链接中的一个；而以最小概率选择广告链接。因为浏览者选择浏览该网页，那么他的阅读兴趣应该是就是该网页的主题——足球，那么下一刻浏览者选择跳向的网页很有可能也是与足球相关的。在图14中，我们简单的把链接归为三种：导航链接、相关链接和广告链接。在现实中，链接的种类和目的更复杂，而且需要注意的是，即使都属于主题相关链接，它们被浏览者选择的概率也可能会有很大差别。PageRank的基本假设是链接表示作者对链向网页的评价，这点在早期是基本成立的。但也许正因为链接分析方法早期的成功，使目前的网页链接关系变得非常复杂。网页上的链接可能表示编辑者的多种目的，而且很多时候是被用作linkspamming来提高网站的排名。这也是网页的链接引用与学术论文引用的区别，学术引用的信用度较高，而且目的也很明确；但网页间的链接要复杂得多，表达的网页间关系也是非常隐蔽的，因此我们需要区别不同的链接。图14.典型的网页链接情况4.2结合语义相似度的PageRank由前一节的分析，我们对PageRank的游走模型加入如下假设：当用户浏览某一主题相关的网页时，如果下一时刻他的动作是选择链接浏览，那么他优先选择与该主题相关的网页链接。在原先的PageRank中，浏览者随机等概率的选择每一条链接；而根据我们的假设，他会优先选择主题相关度高的链接。我们可以用前面定义的链接网页间的语义相似度来表示这个选择概率。形式化的表示如下：即浏览者从网页p选择链接跳到网页q的概率正比于网页p和网页q间的语义相似度。 如果网页链向网页，那么我们在计算的PageRank值分配给时，其比例不是原先的链出度的倒数，而是和语义相似度占和其所有链出的网页间的语义相似度和的比率，即。遗憾的是，在很多时候我们因为没有网页的分类体系而无法直接给出链接网页间的语义相似度。虽然可以通过构造分类体系和网页自动分类来完成，但我们这里给出另外的一种近似方法——用网页的内容相似度或链接相似度来模拟（F()未作分析，近似有效吗？）。因为网页间的内容相似度和链接相似度都是可以根据网页数据直接计算出来的。我们把内容相似度或链接相似度看作语义相似度函数的变量，通过该函数近似表示语义相似度。即可以是内容相似度或链接相似度，甚至是两者的结合。我们的目标就是利用链接网页间这种语义相似度来差异化不同的链接权重，以此改进PageRank。4.3SemanticEnhancedPageRank公式我们先给出改进前的PageRank公式： 在该公式中，ε/n即表示随机直接跳转到网页的概率，该项我们保持不变。而只改进顺延链接到达的概率。改进后的PageRank公式为： 其中是两个网页的内容相似度或链接相似度。F是一个相似度评估函数，它用来模拟我们真正需要的语义相似度，给出该相似度下对应的链接权重，给出了链接在的所有链出链接中的相对权重。这样每条链接的权重是网页间内容相似度的一个函数，我们通过调整这个函数就得到不同链接权重算法。我们引入相似度评估函数的意义在于内容相似度、链接相似度和语义相似度间的不一致性。[8]中指出内容相似度在衡量网页间语义关系上是粗糙和误差很大的。根据我们前面的PageRank分析，在计算每个链接权值时，使用其语义相似度最符合我们的假设。但由于语义相似度无法直接计算，因此我们使用内容相似度或链接相似度来近似模拟它，而这个模拟函数即类似于我们的相似度评估函数。用内容相似度来或链接相似度来模拟语义相似度的关键是找到符合两者联系的函数。[8,45]的研究结果给了我们一些帮助，让我们重新审视前面给出的内容相似度－语义相似度分布图。我们发现，如果其分布进行纵向加权叠加，得到的内容相似度－语义相似度曲线如大致图15的白色曲线所示。这条曲线可以看作是以内容相似度为变量的语义相似度函数曲线。图15.内容相似度－语义相似度的关联曲线我们从该曲线来看：当内容相似度较小时，其语义相似度的取值却可能很大(这样的统计近似，在实际应用中带来的误差如何？？？)。这点是很好解释，因为在计算内容相似度时使用的是词向量间的余弦值，而相同的语义可以用多个不同的词汇来表示，因此计算出来的内容相似度会小于其语义相似度。而当内容相似度较高时，其语义相似度的值并没有相应的提高，而是略微下降。这说明语义相似度并不会随着内容相似度单调递增（这个结论反自觉，需要精细的量化说明）。因为有可能两个网页的词汇分布大致相同，因此其内容相似度较高，但这两个网页却并不属于同一格主题。比如，有两篇网页p和q，p讲述的是Java语言编程，而q讲述却是C++语言编程，两者的词汇分布可能非常接近，因此内容相似度很高，但语义上，两者属于不同的类别（Java和C++），因此语义相似度并不像内容相似度那样高。为了验证我们的分析假设，我们采用了如下几种常见的函数作为链接评估函数F(s)：线性函数：反比函数：正态分布函数：折线函数：F(s)＝ 我们先解释给出四种函数的目的：最常用的当然是线性函数，虽然从图中的观察还是[8]中的实验，我们知道线性函数很难真正的描述内容相似度和语义相似度的关系，但我们以之作为一个基准。反比函数的给出主要是为了说明两者是否有负相关的联系，虽然这有违我们的观察和经验，但我们仍保留这种可能性。正态分布函数和折线函数的给出是为了更好的拟和上图给出的白色曲线。在正态分布函数中，我们会加入一个截距d来纵向平移该函数曲线；在折线函数中，先单调上升，在t点（0<t<1）取得最大值，然后单调下降。我们给出折线函数的原因是取消正态函数的对称性的限制。4.4结合语义相似度的PageRank实验4.4.1实验数据集和测试集我们以CWT100g的所有网页作为试验数据，并使用其2004年的CWT100g的主题提取任务作为评测指标。主题提取目的是对于一个特定主题发现一组关键资源。它注重以站点作为资源的查询。根据评测网站[46]上的要求，在查询返回的前十个结果中寻找尽可能多的不同站点（用它们的网站首页面表示）。比如对于主题“linux”，CWT100g中的下面站点可能被认为是关键资源：表格4.“linux”主题查询的有效返回结果和描述URLDescriptionlinuxorg/os/29明辉开发者网络linux区/红旗Linux返回页面应该是一个站点的好的首页面。判断是否一个好的首页面,考查三个方面:是否大部分切合主题；提供主题的可靠的信息；不是一个更大的切合主题站点的一部分。CWT100g的2004年主题提取任务共有70个查询，最后保留了50个问题并提供答案。原因是有些问题的答案过少，没有通过评测人员第二轮的检查被去掉,或者个别评测人员没有按时提交答案。其列表参见[47]。查询的相关结果集采用PoolingPlus方法构造完成,即：将搜索引擎转换为虚拟参赛队，参与结果集合成。这样，即使参加队数量不多，也能合成质量较高的结果集，达到检验参与系统检索质量的目的。4.4.2实验步骤和设置我们的实验步骤如下：1． 计算CWT100g链接网页间的内容相似度：即用前文中网页的TF-IDF词向量来表示每个网页，并计算链接网页间词向量的余弦夹角，以此表示网页间的内容相似度。2． 根据上述的链接评估函数计算链接的推荐权值。3． 使用PageRank的迭代过程计算网页的重要度4． 对于每