Jaccard系数(Jaccard Coefficient)和tf-idf方法

这个方法在信息检索或者搜索引擎中经常用到,用于衡量两个词库的交集。这里面的两个词库可能来源于文档或者请求的语句。虽然简单,但是很实用。

比如A和B是由文档(Document)或者请求语句(Query)得到的两个词库 (term sets)。




所以,我们有 JACCARD(A, A) = 1; 当A∩B=0 JACCARD(A, B) = 0; 0=<JACCARD(A, B)<=1。

注意,两个词库A和B大小不一定相同。


举个简单的例子,请求语句(Query):“ides of March”,

                               文档(Document):"Caesar died in March"

我们有JACCARD(q, d) = 1/6。(A与B的并集中March出现了两次,并作一次) 


但是这个方法有个非常突出且严重的缺陷,就是没有考虑到term出现的频率(term frequency),仅仅统计了次数。同时,我们需要一个使文档长度归一化的方法。


我们不考虑term出现的顺序,所以这种模型为bag of words model。比如说“John is quicker than Mary”和“Mary is quicker than John”,我们认为是一样的。之所以不考虑term出现的顺序,是考虑到算法复杂度(complexity),也就是运行速度(speed)问题。

那么如何加进去term frequency这个维度呢?

这里介绍一种非常实用且现在搜索引擎中也用到的tf-idf方法。之前也看了网上的一些算法介绍,但总感觉比较模糊。这次修了Information Retrieval这门课,对算法中一些不理解的地方豁然开朗了。下面我就介绍一下这个算法。

我们用tf(t,d)来表示term t在document d中出现的次数。但是,这样生成的term frequency并不是我们希望的,一个term在某个文档中的tf=10,而在另一个文档中tf=1,但这并不意味着tf大的文档与term的相关性是另一个文档的10倍;也就是说,相关性(relevance)并不会随着这种term frequency成正比增加。所以,用log frequency weight来代替之前“粗暴”的表示。

Term t在文档d中的log frequency term定义为:




所以,对于一对document-query,这个document的score为  由document和query得来的两个词汇集合交集的词(term)的log frequency weight之和。


如果query的term库中没有出现在document中,那么这个score便是0。


看起来这样貌似就可以表示term frequency了,但是,我们还需要考虑到这样一种情况:通常很少出现的词反而比出现频率高的词信息量更大。比如:“the”、"a"等词在文档中出现的频率相当高,而类似于“Arachnocentric” (蜘蛛学)这样的词出现次数比较少,而正是这种很少出现的词能表现出相关性。所以,我们需要提高这些很少出现的term的权重(height)。这里,用document frequency这个因素来作为权重。Document frequency为所有documents中出现这个term的documents的数目。

因为document frequency越高,越说明这个词不重要,所以我们采用其倒数来表示,term t 的权重idf定义为:


idf 可以用来衡量某个term的信息丰富程度, 其中,N为所有documents的数目。之所以采用log,是为了"抑制" idf 的影响。

从上可以看出,我们对term frequency和document frequency都取了log。

比方说,我们用下面的公式来计算idf(t) :


注意,idf 是用于含至少两个term的query的情况下,决定文档的排序。如果query只有一个term,那么 idf 的影响就很小。


某个term的 tf-idf weight 定义为 该term的 tf-weight 和 idf-weight 之间的乘积:


这就是信息检索(information retrieval)领域非常出名的加权方案(weighting scheme)。也可记为 tf.idx,tf x idf。

相关文章
相关标签/搜索