数据处理---之---网页排序算法

一. 网页排序算法

二. 网页排序算法分类

1 基于访问量的排序算法

2 基于词频统计和词语位置加权的排序算法

3 基于链接分析的排序算法

4 基于智能化的排序算法

三. TD-IDF 算法

1 词频(Term Frequency, TF)

2 逆文档频率(Inverse Document Frequency, IDF)

四. BM25算法

五. PageRank 算法

一. 网页排序算法

在能将“包含某关键字的网页迅速查找出来”之后，另一个问题出现在我们面前:应该如何对查找结果内的每一张网页进行 “打分”和“排序”，以保证排在前面的文档是“最重要的”“最符合搜索意图的”文档?这个问题看起来似乎很容易，但是解决的方法却没有我们想象的那么简单。

二. 网页排序算法分类

网页排序算法大致可分为4种：基于访问量的排序算法、基于词频统计和词语位置加权的排序算法、基于链接分析的排序算法、基于智能化的排序算法。

1. 基于访问量的排序算法

这种算法的主要思想如下:越是重要的网页，访问量就会越大。访问量越大的网页，排名越靠前。但是这种排名算法有两个很显著的问题:一是它 只能够抽样统计，统计数据不一定准确，并且访问量的波动较大，想要得到准确的统计，需要大量的时间和人力，统计结果有效期很短;二是访问量并不一定能体现 个网页的 “重要 程度”

2. 基于词频统计和词语位置加权的排序算法

利用查询关键词在文档中出现的频率和出现位置对文档进行排序是搜索引排序的一种主要思想。这种技术发展最为成熟，应用非常广泛，是许多搜索引擎的核心排序技术。查询关键词在文档中出现的频率越高，出现的位置越重要，则认为此文档越符合搜索意图、此文档越“重要”。这种技术有两个关键步骤：词频统计和词位置加权。

(1)词频统计

查询关键词在文档中出现的频率(词频)越高，则认为此文档和查询关键词的相关度越大。但当查询关键词为常用词(例如，“的”“这个”)时，其对相关性判断的意义非常小。在基于词频的统计算法中，著名的算法有TF-IDF算法、BM25算法等。

(2)词位置加权

由于网页文件是带有版面格式信息(HTML标签等)的，这些信息对于搜索关键词的加权起着十分重要的作用。例如，如果搜索关键词出现在了标题中，或搜索关键词在正文中被加粗，那么，可以对此关键词的这次出现分配更大的权值。

一. 回到文首

3. 基于链接分析的排序算法

在文献索引机制中，一篇论文被其他论文引用次数越多，或被越权威的论文引用，则这篇论文的重要性越大。在链接分析中，一个网页被其他网页引用次数越多，说明这个网页的内容越受欢迎，被越权威的网页所引用，说明这个网页的质量越高，其价值越大。链接分析排序算法大致可以分为如下几类：

(1)基于随机漫游模型的链接分析算法，例如PageRank和Reputation算法。

(2)基于概率模型的链接分析算法，如SALSA、PHITS等。

(3)基于Hub和Authority相互加强模型的链接分析算法，如HITS及其变种。

(4)基于贝叶斯模型的链接分析算法，如贝叶斯算法及其简化版本。

所有的算法在实际应用中都结合传统的内容分析技术进行了优化。

一. 回到文首

4. 基于智能化的排序算法

目前，主流搜索引擎都在研究新的排序方法，来提升用户的满意度。但是上述几类算法都或多或少存在相关性差问题和搜索结果单一化的问题(241。

(1)搜索结果相关性差的问题

相关性是指检索关键词和网页的相关程度，相关性分析越精准，用户的搜索效果就会越好。由于语言是一个很复杂的系统，仅仅通过网页的表面特征及链接分析来判断检索词与页面的相关性得到的结论往往是片面的。例如，我们检索关键词为A,有些网页整篇都在介绍A的相关知识，但全篇都没有出现A这个关键词，这个网页根本无法被搜索引擎检索到。提升搜索相关性的方法是使用语意理解来分析检索关键词与网页的相关程度，同时剔除那些相关性低的网页。

(2)搜索结果单一化问题

一般情况下， 在搜索引擎中，不同的人搜索同一个关键词，得到的搜索结果是完全相同的，但是这并不能满足我们的需求。例如，普通人搜索“感冒”，一般是想得到感冒的预防知识和如何治疗感冒，但医学工作者可能更想得到关于感冒的论文。解决搜索结果单的方法是通过 Web数据挖掘， 建立用户模型(如用户职业、 兴趣、行为、 风格),提供个性化服务。

一. 回到文首

三. TD-IDF 算法

TF-IDF (Term Frequency Inverse Document Frequency)是一种统计方法，不仅可以用于评估一个词语对于语料库中某份文档的重要 程度，还可以对搜索结果进行排序，使“重要的”和“贴合搜索关键词的"网页排在前面。基于TF-IDF的网页评分系统在搜索引擎中被广泛使用。它不仅可以自动过滤掉那些无意义的词(例如，“的”“是”“这个”等)，还可以自动提取出文章的关键词，用以对文章进行自动分类。它的总体思想是:一个词语的重要性随着它在单个文档中出现次数的增加而增加，但同时会随着它在语料库中出现频率的增加而下降。

1. 词频(Term Frequency, TF)

TF是某个词在某个文档中出现的次数或者频率。这是一个很容易想到的思路:某个词语A在某篇文档B中出现的次数很多，但在其他文档中出现的次数很少，那么对于文档B来说，词语A可能更能反映文档B的特性，词语A就很“重要”。TF的计算公式很多，最简单的形式为

TF =某个词语A在文档B出现的次数 / 文档B的长度

2. 逆文档频率(Inverse Document Frequency, IDF)

只使用词频进行统计显然是不够的:通常情况下，文档中会大量出现“的”“是”“这个”“this”“a”“the"这样的对搜索结果毫无帮助的词语(也称为“常用词”或“停止词(Stop Words)”)。 于是我们给每个词语增加这样一个权重：如果这个词在语料库中的每个文档中均频繁出现，那么这个词的权重就很小甚至为0；相反，如果某个词只在语料库中的某几篇文档中大量出现，那么这个词的权重就很大。这里的“权重”就是“逆文档频率”，它计算公式也有许多，最简单的形式如下：

IDF = log[语料库中文档总数 / 在语料中有多少个文档包含词语A]

除了最简单的形式外，下面这种形式的计算公式也经常被使用:

IDF=log[(N- n+0.5) / (n+0.5)]

其中，N为语料库中的文档数目，n为语料库中包含词语A的文档数目。不难发现，使用上述公式计算出来的IDF值符合我们的预期。

一. 回到文首

四. BM25算法

与TF-IDF类似，BM25 (BM是Best Matching的缩写)也是一种基 于统计方法的排序算法，是二元独立模型的扩展，或者看作是TF-IDF算法的变形。此算法也是一种有效的相关性评分手段，被搜索引擎广泛使用。BM25 算法只关心“词语在查询中和在文档中的出现频率”，而不关心词语之间的内在联系(例如，先后顺序)。由于Okapi最早实现了此算法，故此算法也经常被称为“Okapi BM25”。

给出查询关键词A,则语料库中某篇文档B的BM25分数定义如下:

Score(A,B)= IDF(A) x [fx(k.+1)] / [f +k1x(1-b+bxk2)]

在这里，IDF是逆文档频率，f是“词语A在文章B中出现的频率”，k和b是两个调节参数，其中参数b用来调节文档长度对相关性影响的大小，通常使用的经验值为k=2, b=0.75，k2是文档的平均长度。

在实际使用中，可以对此公式做一些修改以适应不同场景的需要。

(1)如需完全忽略常用词，只需将它们的IDF值人为设为0即可。

(2)为了避免常用词被完全忽视，IDF项可以设定一个最小值ε。

(3) IDF 项可以用其他非线性函数代替。

(4)当词语A在于粮库中超过50%的文档中均有出现时，IDF值为负数。此时需要对IDF值做特殊处理。

一. 回到文首

五. PageRank 算法

在Google 诞生之前，流行的网页排名大多基于流量统计：某个网页被访问得越多，这个网页就越重要，它就会被排在检索结果的前面。1998 年，Larry Page 发表了一篇论文，论文中提出了一种叫作PageRank的算法，这种算法的主要思想如下：越重要的网页，页面上的链接质量也越高，同时越容易被其他重要的网页链接。该算法完全利用网页之间互相链接的关系来计算网页的重要程度，摆脱了利用访问量加权的方法，将网页排序问题变成一个数学问题。与其他网页排序算法相比，PageRank 算法将整个互联网视为一体，充分利用了网页之间的联系，而不是仅仅关注于某一张网页。

PageRank算法的核心思想是让页面之间通过超链接来进行"投票”:页面A上有一个指向页面H的超链接，就相当于页面A给页面H“投了一票”；一个网页被越多网页链接到，那么这个网页就越受大家信赖，此网页越重要，PageRank值越高：一个很重要、PageRank值很高的网页(如网页B)链接到了其他网页，那么这些网页的PageRank值也会因此提高。

PageRank算法的背后是马尔可夫链(Markov Chain)：PageRank 算法假设一个在网络上浏览网页的人，每看过一个网页之后都会随机点击网页上的某个链接以访问新的网页。如果当前这个人正在浏览网页x,那么此网页上每个链接被点击的概率(可以用向量Nx表示)也是确定的。

一. 回到文首