页面群的能力。我们在评价基于主题的Web信息采集系统URL预测方法时，也提出了另一个衡量指标——重要度。 4.5.3.1.2 重要度的概念
在信息检索中，重要度定义为：检索结果中，某文本的相对重要程度[杨志峰 2001]。我们在此处对重要度进行扩展：在一个文本集合中，某文本的相对重要程度。重要度刻画的是一篇文本实际的质量和有用性，相关度则刻画一篇文本和一个主题或者查询在语义方面的相联程度。尽管从统计概念的角度说，它们之间有较强的相关性(也就是说，统计上页面表现出来的规律是：重要度高的页面很可能相关度也高，反之，相关度高的页面很可能重要度也高)，但从实际意义上看它们并无太大联系，只是从两个不同的角度对本页面的评价。一个不太恰当的比喻是马克思对商品的看法：商品是价值和使用价值的统一体。在这里，我把相关度比作价值，重要度比作使用价值，二者相关，但也有很大的不同。
计算页面相关性的方法丝毫不能评估页面的重要性，那么我们如何得到对页面重要性的评估呢？链接分析给我们指明了道路。事实上，整个Web上的指向页面的链接数恰恰反映了页面的可用程度和质量，也就是页面的重要度。如果一个页面质量好或可用程度高，那么就会有很多页面指向它，如果一个页面不好或可用程度低，就只有很少的页面指向它。这说明链接关系不仅仅反映了页面的重要度，还因为排除了个别用户或临时行为的干扰而使得这种重要度有较强的可信度。 因此人们用链接分析算法来评估页面的重要度，流行的算法有PageRank和Authorities/Hubs算法，在后文我们设计的基于主题的IPageRank算法，就利用了重要度的概念。
4.5.3.2 PageRank算法
PageRank是著名搜索引擎Google的一个重要检索算法，它有效的帮助搜索引擎识别那些重要的页面并且将它们排在检索结果的前列。Google是美国斯坦福大学计算机科学系研究开发的一个大型搜索引擎。它的设计目标，是提供千万页面级的搜索引擎，每天可以应付数以百万计的查询请求，并且，最重要的是提供了相对令人满意的检索结果。
4.5.3.2.1 PageRank函数定义
WORLD WIDE WEB上的无数页面互相链接，构成了一个巨大的链接有向图。也许是受论文引用排名的启发，Google的设计者们发现这个有向图中包含了非常有用的引用信息，而这种资源以前从未被人注意过。
设计者的思路是：被别人大量引用(也就是被链接)的网页，一定是好网页。从这个观点出发，他们构造了以下的基本公式：
给定一个网页A，假设指向它的网页有T1，T2，…，Tn。令C(A)为从A出发指向其它网页的链接数目，PR(A)为A的PageRank，d为衰减因子(通常设成0.85)，则有 公式4.7
设计者声称，PR(A)可以用简单的迭代算法进行计算；在一台中等规模的工作站上，2600万个网页的PR函数值可以在几小时内完成。
4.5.3.2.2 PageRank的直观解释
假设WEB上有一个随机的浏览者，从一个任意给定的页面出发，从来不执行“BACK”操作，按照页面上的链接前进，我们假设浏览者选择本页中任意一个链接前进的概率是相等的。在每一个页面，浏览者都有可能不再对本页面的链接感兴趣，从而随机选择一个新的页面开始新的浏览。这个离开的可能性设为d。这样，PageRank(即函数PR(A))就是它访问到本页面A的概率。因为用户是趋向于浏览重要页面的，所以这个概率就反映了此页面的重要程度。从直观上看，如果有很多页面指向一个页面，那么这个页面的PageRank就会比较高；如果有PageRank很高的页面指向它，这个页面的PageRank也会很高。这样，从“随机浏览者”模型出发的PageRank函数就在直观上同WEB上的实际情形相对应了。
4.5.3.2.3 对PageRank公式的修正
从随机浏览者解释思路看，公式8.7的形式是不准确的。有人认为应该修正为以下形式[杨志峰 2001]： 公式4.8
公式中，(1-d)(PR(Ti)/C(Ti))代表随机浏览者从页面Ti进入页面A的概率，所有概率值相加得到随机浏览者从某个链接进入页面A的概率；d/(Ctotal-1)代表随机浏览者离开当前页面，随机开始一个新页面，从而选中页面A的概率。这两个概率相加，即得到进入页面A的总概率。 因为d/(CTotal-1)约等于0，所以我们认为公式4.7中的d并不表示随机浏览者离开当前页面的选择一个新页的概率，而只是起到调高PR(A)值以便计算的作用，实际公式中的d/(CTotal-1)由于为0已被省略了。
4.5.3.3 权威中心页面算法(Authorities/Hubs)
4.5.3.3.1背景
该算法主要在IBM的Almaden研究开发中心研制的CLEVER系统中实践和应用。他们认为，WEB页面的数量正呈指数形增长，但人们可以接受的信息数量几乎保持不变。因此，没有必要把所有的页面都进行索引、分类以供检索。他们的目标是主题提取(Topic Distillation)：给定一个覆盖面比较广的主题，筛选出这个主题下面质量最高的一小部分WEB页面。
CLEVER系统把链接分析的深度又提高了一层。在这个系统中，首次提出了两个重要的概念：Hubs和Authorities。从这两个概念的名称可以推想到，Authorities是重要的页面，Hubs就是指向众多重要页面的中心点。
Hubs和Authorities之间是相互加强的关系。一个好的Hub必然指向许多好的Authorities，一个好的Authorities必然被许多好的Hub链接。当然，一个页面可以同时是Hub和Authorities。
4.5.3.3.2 权威中心页面算法(Authorities/Hubs)
下面是CLEVER算法的示意性算法描述。
1. 用户给定一个查询以后，CLEVER把它提交给一个通用的基于关键字查询技术的搜索引擎，例如AltaVista。从这个搜索引擎返回的结果称为基本集(Initial Set)。基本集不超过200页。
2. 向基本集中增加页面。被增加的页面必须或者是基本集中的页面所链接的页面，或者是它们链接到基本集中的页面。扩展后的页面集合称为根集(Root Set)。
3. 对根集中的每个页面p，赋给两个权值：a(p)，代表Authority权值；h(p)，代表hub权值。它们初始值设为1。 4. 迭代计算每个页面的权值。
a) 对于页面p，令 ，其中qi为页面p链接的页面。 b) 对于页面p，令 ，其中ri是链接到页面p的页面。 5. 重复执行若干次迭代，每次迭代后进行规格化。
最终，取a(p)最高的页面为最好的Authorities页面，取h(p)最高的页面为最好的Hubs页面，每个页面的Authority值就是这个页面的重要度。从算法中我们可以得知：根据Authorities/Hubs算法得到的权威页面是基于主题的，也就是说得到的权威页面是这个主题的权威页面。但由于根集中扩展进了许多主题相关性较低的页面和算法初始化各个页面的Authorities值相同(都为1)，这个算法一般只适用于较广泛的主题。
4.5.4 根据页面语义信息的判定
最好的判断URL和页面与主题的相关性方法还是要基于语义的理解，尽管这样做往往要花费更高的时空代价。目前，判断文本和主题相关性的方法仍然是基于关键词的，主要有以下几种方法：
全文本扫描，布尔模型，扩展布尔模型，向量空间模型，概率模型。它们都是IR领域里经典方法。
4.5.4.1 全文本扫描
对于检索来说，要检查某个检索串的位置，最简单有效的办法恐怕是全文检索，也就是从头到尾扫描手中掌握的文本，检查这些串是否存在于其中。相应地，要判定是否页面与主题相关，最简单的方法也是全文扫描，在进行分词、去除停用词、词根还原（stemming）等简单的预处理之后，看看主题中的关键词是否都在本页面中出现，如果出现则相关，否则不相关，出现的频率越高，则相关度越大。
如果系统支持带正则表达式的查询，那么情况会复杂一些，需要判断文本中的字符串是否符合指定的模式。一般来说，可以构造一个和正则表达式对应的有限自动机，用它检测字符串是否满足要求。
全文本扫描的优点，在于这种方法非常简单，不需要预先对文本进行处理，不需要耗费空间存储索引，自然也不需要花代价维护索引。它的缺点在于，这是一种非常低效的方法，任何字符串的查找都要遍历所有的文本。不仅响应时间太长，而且极其耗费CPU时间和磁盘IO时间。所以不适合大规模应用。但是，如果数据量不大，全文本扫描不失为一种有效的简便方法。
4.5.4.2 布尔逻辑模型
该模型构成了几乎所有信息检索和数据库系统的基础，直到今天仍然如此。采用这种模型的检索系统，用户查询词用布尔操作符“与”（AND）、“或”（OR）、“非”（NOT）进行连接，系统则返回满足上述词项组合的文档[Cooper 1988]。对于判定页面与主题的相关性来说，将主题表示成若干个关键词并用布尔操作符相连，然后与页面进行相关性判定，一般可采用全文扫描的方法。
4.5.4.3 扩展布尔模型
图4.3 P-norm模型
经典的布尔逻辑模型的最大缺点是只有0和1，没有ranking。也就是说只要整个布尔表达式中只要有一处不符合，则不相关；都符合，则相关。这种判定方式显然十分僵化：在OR方式中，包含很多主题词的页面和包含少数词的页面在与主题的相关度上是等同的；在AND方式中，即使缺少一个词，结果也是FALSE，等于一个词也没有。为此建立了扩展布尔模型，在各种扩展中，p-norm模型的运行结果是最符合实际的。
如图4.3所示，当P=infinity时，p-norm模型等同于classical boolean模型，当P较低时（如在[2,5]内），and方式中一个权值低的词会使总体值大大降低，or方式中一个权值高的值会使总体值大大提高。当P=1时，变成向量空间模型(vector space model)，and和or方式实际上相同，公式变为cosine similarity。当P-norm可以得到更大的灵活性。用户可以指定某个子表达式的P值，例如一个较大的值表示对它要求比较严格。
4.5.4.4 向量空间模型
进行主题词和页面内容相关性的计算过程，实际上也是一个对页面进行分类和聚类的过程。Salton 等人于60年代末提出了向量空间模型 VSM (Vector Space Model) 的概念，即使用向量表示文本或页面。
向量空间模型的基本概念可以描述如下：1).文档：泛指一般的文本或文本的片段（段落、句群或句子），一般指一篇文章。尽管文档可以是多媒体对象，但在我们的讨论中假设为文本对象，并且对文本和文档不加以区别。
2).项（特征项）：文本的内容由一些特征项来表达，一般由文本所含有的基本语言单位（字、词、词组或短语等）来表示，即文本可以表示为 ，其中， 表示各个项。换句话说，由这些项张开了一个向量空间，每个项表示一个维度。
3).项的权重：在一个文本中，每个特征项都被赋予一个权重 W，以表示这个特征项在该文本中的重要程度。权重一般都是以特征项的频率为基础进行计算的，比如采用 TF-IDF 公式表示等等。这样文本就表示为： ，简记为 ，这时我们说项 的权重为 ，其中 。
4).向量空间模型（VSM）：给定一自然语言文本 ，由于 在文本中既可以重复出现又应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析，可以暂不考虑 在文本中的先后次序并要求 互异（即没有重复）。这时可以把 看成一个 n 维的坐标系，而 为相应的坐标值，因此一个文本就表示为 n 维空间的一个向量，我们称 为文本 D 的向量表示或向量空间模型。 5).相似度度量：两个文本 和 之间的相关程度常常用它们的相似度 来度量。在向量空间模型下，我们可以借助向量之间的某种距离来表示文本间的相似度。相似度常用向量之间的内积来计算：
公式4.9 或用夹角余弦表示： 公式4.10