Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2407074
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类: 项目管理

2010-10-06 14:19:14

排序采用下面的算法:

score(q,d) = sum( tf(t in d) * idf(t) * getBoost(t.field in d) * lengthNorm(t.field in d) ) * coord(q,d) * queryNorm(q) 

q 是查询 d 是一篇文章, score 表示 q d 中的评分。

t 表示 q 的一个部分,一个词汇: 比如,中国人民 可能会分割成 “中国” “人民”,q = “中国人民”,t= {“中国” ,“人民”}

tf 表示 term frequency  词频,就是这个词汇在一篇文章中出现的次数。所以有个d参数。

idf ,是另外一个参数,它表述的是:inverse document frequency。逆向文件频率,这个参数说的是:一个词语普遍重要性的度量。比如“的” 这个词,几乎每篇文章都有,所以,不能代表什么实际的意义和信息,所以,要降低“的”这个词重要性。

下面一个重要的概念是:boost 的概念,不是每个字段的权重都是一样的,比如标题,匹配到了,要比正文匹配到了优先。实际上,它的作用是协调字段之间的权重的。原来的索引中,没有对标题进行优先处理,现在进行了优先的处理。

lengthNorm 也是一个比较重要的参数,这个也是表现为文档的长度问题。一般来说,一篇文章很长,你匹配到了一个关键字 一篇文章很短,你匹配到了关键字,要做点差别。

Coord 一般来说,如果 几个关键词都在一篇文章中匹配到了,应该给个更高的权重,如果10个关键词,才匹配到了一个,那么应该降低权重。排序算法其实一直是文本搜索里面的重点,其中有两类比较常用的算法:向量空间模型 统计模型,lucunece 使用的是向量空间模型。
向量空间模型可以说贯穿整个索引系统的始终,是索引系统的核心内容。其他的内容,如,存储问题可能会影响性能,但是不影响搜索的质量。

1.       基本的思想:

向量空间模型将文档和用户查询形式转化为向量形式,对于所有文档和用户查询都映射到文本向量空间. 用户查询和被检索文档两者的相似程度可用向量之间的夹角来度量,从而将信息检索转化为向量空间的向量匹配问题. 这种表示模型考虑到了文档的内容特征,而且文档之间的相似程度的度量比较简单,并且可以根据向量之间的相似程度对所有返回结果进行排。说道向量空间,就应该有它的基,也就是坐标系。这个向量空间的基就是 所有的关键字。而一篇文章就是里面的点。一个查询也是里面的一个点。那么如何很好的把一篇文字表示为关键字的一个向量集呢,关键是要计算,每个关键字的系数。有了文章的表示方法了以后,我们就知道如何评分了。

2.       计算文本向量:

关键字的数目可能会非常的多,所以整个系统是一个维数非常高的向量空间。当然,对于一篇文章来说,关键字最多几千个,不会很多,所以这个文章的向量大部分都是为0,一般为0的就省略了,否则无法表示,就计算有关键字的值。

最简单的方法,或许就是更具关键字出现的次数,可是,这有些不公平,应为文章的长度可能会不一样,这样对长的文章可能更加有利,于是,有人觉得用 tf 比较好,也技术词频。也就是 次数/总字数。但是,这样还是不对,因为,有些词汇 很常用,比如:我,你,它,的,是。基本每篇文章中都有,但是,他没有包含什么信息量。如果,这部分字的权重太大的话,就无法区分不同的文章之间的差别了。最后,我们或许终于想明白了,应该用某个词的信息量 * 词频 一个词的信息量这个问题貌似还是很难的一个问题。这个以前是一个世界级的难题,其实某个词的信息量的概念就是一个特定条件下、关键词的概率分布的交叉熵(Kullback-Leibler Divergence)。当然,这个计算公式提出很早,只是大家都无法解释。最后,用公式表示 就是 tf * idf , tf 就是词频,idf 就是词在文章中的信息量。但是,如果要比较相似度的话,必须要做归一化处理,这个在线性代数里面都学过。

Wij = tfij ×log(N / dfi )/sqrt(ΣTkD i[ tfij ×log(N / dfi ) ]2)

不必理解上面的公式,如果需要进一步了解可以查询论文库。

相似度的计算就比较简单了。就是计算量向量的 夹角。

3.       Lucunece 中的评分算法:

Lucunece 中的评分算法是向量空间模型的一种扩展

首先要从一个简单的例子说起:

A1 =a1b1c1);

A2 = a2b2c2);

A1 A2 是归一化的向量,那么 相关度 A1 * A2 = a1*a2 + b1*b2 + c1 * c2。从这个公式可以看出,实际上,如果一个查询字符串 一个文章相似度,只和查询字符串 文章中都存在的关键字相关。否则,两个里面一个为0的话,相乘还是为0,没有意义。在lucunce 里面没有保存 wij ,为了更加灵活的处理,而是保存了下面的值:

freq 就是 tf

docFreq  文档的数目

numDocs 有这个关键字的文档的数目

利用这些值就可以计算相关度了。


要注意,前面的公式的 idf  实际上 idf * idf (query 中的idf 和 document中的idf 是一样的),而query 中的 tf 都默认为1(这样做就要通过搜索的关键字的数目来修正score

当然,其中还有好多个对算法的修正,从理论上解释这些问题以及为什么要修正的问题,可以参考更加进一步的资料。

 

公式为:

score_d = sum_t(tf_q * idf_t / norm_q * tf_d * idf_t / norm_dt_t)

score_d: Document(d) 的得分
sum_t: Term(t) 的总和
tf_q: 查询中 t 的频度的平方根
tf_q: d 中 t 的频度的平方根
idf_t: log(numDocs/docFreq_t + 1) + 1.0
numDocs: 索引中Document的数量
docFreq_t: 包含t的Document的数量
norm_q: sqrt(sum_t((tf_q*idf_t)^2))
norm_d_t: 在与 t 相同域的 d 中 tokens 数量的平方根

基础排序算法的不足

要点:
    查询词在一个 Document 中的位置并不重要。
    如果一个 Document 中含有该查询词的次数越多,该得分越高。
    一个命中document中,如果除了该查询词之外,其他的词越多,该得分越少。

不足:
    查询精确度不好。
    没有体现网页的重要性。
    Lucene的得分算法, 不适合网页搜索。
    google的pagerank算法主要是根据link

改进的算法:
    Score_d = k1 * OldScore + k2 * PrScore + k3 * ReScore + k4 * homePageScore

    Score_d: 记录d的得分。
    OldScore: 由基础排序算法计算出的记录d的得分。
    PrScore: 记录d的PageRank的得分。
    ReScore: 记录d的二次检索的加分, ReScore = rescore + (hitNum - 1) * increment
    homePageScore: 主页的加分
    K1, K2, K3, K4为权重系数

    PR(A) = (1 - d) + d(PR(1) / C(1) + ... + PR(n)/C(n))

    PageRank, 二次检索, 以及主页加分的调整确实优化了查询精确度


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/redez/archive/2005/11/17/531963.aspx

 

转载补充:

传统排序算法可以参看 BM25。Xapian中即使用BM25进行scoring。

其实BM25在相关文档信息未知(讲相关参数设置成0)时,即退化成类似于tf*idf的形式,跟本文的排序算法类似

 
 
阅读(1356) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~