python實現bm25演算法的簡單介紹

本文目錄一覽：

• 1、求解python語句
• 2、BM25演算法
• 3、文本相似度演算法
• 4、文本抽取式摘要
• 5、經典檢索演算法：BM25原理
• 6、【轉】相關性打分

求解python語句

format是一種格式化輸出，你可以查一下，這句話的作用就是把tmp中4個元素按順序填到前面的4個{}中，前面的 代表右對齊，後面的數字表示一個占幾個字元，:表示規定空白位置補什麼

BM25演算法

bm25 是一種用來評價搜索詞和文檔之間相關性的演算法，它是一種基於 概率檢索模型 提出的演算法，再用簡單的話來描述下bm25演算法：我們有一個query和一批文檔Ds，現在要計算query和每篇文檔D之間的相關性分數，我們的做法是，先對query進行切分，得到單詞，然後單詞的分數由3部分組成：

最後對於每個單詞的分數我們做一個求和，就得到了query和文檔之間的分數。

講bm25之前，我們要先介紹一些概念。

BIM(binary independence model)是為了對文檔和query相關性評價而提出的演算法，BIM為了計算，引入了兩個基本假設：

假設一：二元假設

所謂二元假設，類似於布爾模型的表示方法，一篇文章在由特徵表示的時候，以特徵「出現」和「不出現」兩種情況來表示，也可以理解為相關不相關。

假設二：辭彙獨立性假設

所謂獨立性假設，是指文檔里出現的單詞之間沒有任何關聯，任一個單詞在文章中的分布率不依賴於另一個單詞是否出現，這個假設明顯與事實不符，但是為了簡化計算，很多地方需要做出獨立性假設，這種假設是普遍的。

在以上兩個假設的前提下，二元獨立模型即可以對兩個因子P(D|R)和P(D|NR)進行估算（條件概率），舉個簡單的例子，文檔D中五個單詞的出現情況如下：{1,0,1,0,1} 0表示不出現，1表示出現。用Pi表示第i個單詞在相關文檔中出現的概率，在已知相關文檔集合的情況下，觀察到文檔D的概率為:

對於因子P(D|NR)，我們假設用Si表示第i個單詞在在不相關文檔集合中出現的概率，於是在已知不相關文檔集合的情況下，觀察到文檔D的概率為：

於是我們可以得到下面的估算

可以將各個因子規劃為兩個部分，一部分是在文檔D中出現的各個單詞的概率乘積，另一部分是沒在文檔D中出現的各個單詞的概率乘積，於是公式可以理解為下面的形式

對公式進行一下等價的變換，可得：

為了方便計算，對上述公式兩邊取log，得到：

那麼如何估算概率Si和Pi呢，如果給定用戶查詢，我們能確定哪些文檔集合構成了相關文檔集合，哪些文檔構成了不相關文檔集合，那麼就可以用如下的數據對概率進行估算：

根據上表可以計算出Pi和Si的概率估值，為了避免log（0），對估值公式進行平滑操作，分子+0.5，分母+1.0

代入估值公式得到：

這個公式代表的含義就是，對於同時出現在查詢Q和文檔D中的單詞，累加每個單詞的估值結果就是文檔D和查詢Q的相關性度量，在預先不知道哪些文檔相關哪些文檔不相關的情況下，可以使用固定值代替，這種情況下該公式等價於向量空間模型（VSM）中的IDF因子，實際證明該模型的實際使用結果不好，但是它是BM25模型的基礎。

後來人們發現應該講BIM中沒有考慮到的詞頻和文檔長度等因素都考慮進來，就有了後面的BM25演算法。

BIM（二元假設模型）對於 單詞特徵 ，只考慮單詞是否在 doc中出現過 ，並沒有考慮 單詞本身的相關特徵 ，BM25在BIM的基礎上引入單詞在查詢中的權值，單詞在doc中的權值，以及一些經驗參數，所以BM25在實際應用中效果要遠遠好於BIM模型。

BM25由3部分組成：

在第二部分中K因子代表了文檔長度的考慮，dl是文檔的長度，avdl是文檔的平均長度，k1和b是調整參數，b為0時即不考慮文檔長度的影響，經驗表明b=0.75左右效果比較好。但是也要根據相應的場景進行調整。b越大對文檔長度的懲罰越大，k1因子用於調整詞頻，極限情況下k1=0，則第二部分退化成1，及詞頻特徵失效，可以證明k1越大詞頻的作用越大。

在我們不知道哪些文檔相關，哪些文檔不相關的情況下，將相關文檔數R及包含查詢詞相關文檔數r設為0，那麼第一部分的BIM公式退化成：

就是IDF因子的定義，N是總文檔數，n是查詢詞的tf信息，0.5是平滑因子。

文本相似度演算法

TF是指歸一化後的詞頻，IDF是指逆文檔頻率。給定一個文檔集合D，有d1,d2,d3,……,dn∈D。文檔集合總共包含m個詞（註：一般在計算TF−IDF時會去除如「的」這一類的停用詞），有w1,w2,w3,……,wm∈W。我們現在以計算詞wi在文檔dj中的TF−IDF指為例。

TF的計算公式為：

TF=freq(i,j) / maxlen(j)

在這裡freq(i,j) 為wi在dj中出現的頻率，maxlen(j)為dj長度。

TF只能時描述詞在文檔中的頻率，但假設現在有個詞為」我們「，這個詞可能在文檔集D中每篇文檔中都會出現，並且有較高的頻率。那麼這一類詞就不具有很好的區分文檔的能力，為了降低這種通用詞的作用，引入了IDF。

IDF的表達式如下：

IDF=log(len(D) / n(i))

在這裡len(D)表示文檔集合D中文檔的總數，n(i)表示含有wi這個詞的文檔的數量。

得到TF和IDF之後，我們將這兩個值相乘得到TF−IDF的值：

TF−IDF=TF∗IDF

TF可以計算在一篇文檔中詞出現的頻率，而IDF可以降低一些通用詞的作用。因此對於一篇文檔我們可以用文檔中每個詞的TF−IDF組成的向量來表示該文檔，再根據餘弦相似度這類的方法來計算文檔之間的相關性。

BM25演算法通常用來做搜索相關性評分的，也是ES中的搜索演算法，通常用來計算query和文本集合D中每篇文本之間的相關性。我們用Q表示query，在這裡Q一般是一個句子。在這裡我們要對Q進行語素解析（一般是分詞），在這裡以分詞為例，我們對Q進行分詞，得到q1,q2,……,qt這樣一個詞序列。給定文本d∈D，現在以計算Q和d之間的分數（相關性），其表達式如下：

Score(Q,d)=∑ti=1wi∗R(qi,d)

　 上面式子中wi表示qi的權重，R(qi,d)為qi和d的相關性，Score(Q,d)就是每個語素qi和d的相關性的加權和。

wi的計算方法有很多，一般是用IDF來表示的，但這裡的IDF計算和上面的有所不同，具體的表達式如下：

wi=IDF(qi)=logN−n(qi)+0.5n(qi)+0.5

上面式子中N表示文本集合中文本的總數量，n(qi)表示包含qi這個詞的文本的數量，0.5主要是做平滑處理。

R(qi,d)的計算公式如下：

R(qi,d)=fi∗(k1+1)fi+K∗qfi∗(k2+1)qfi+k2

其中

K=k1∗(1−b+b∗dlavgdl)

上面式子中fi為qi在文本d中出現的頻率，qfi為qi在Q中出現的頻率，k1,k2,b都是可調節的參數，dl,avgdl分別為文本d的長度和文本集D中所有文本的平均長度。

一般qfi=1，取k2=0，則可以去除後一項，將上面式子改寫成：

R(qi,d)=fi∗(k1+1)fi+K

通常設置k1=2,b=0.75。參數b的作用主要是調節文本長度對相關性的影響。

文本抽取式摘要

關鍵詞：抽取式，BM25演算法，行業知識後處理。

背景

筆者所在的公司原來已經有一個自動摘要的模塊，我只是在原來的基礎上，做了些針對特定領域的優化。

首先自動文本摘要大概分為 抽取式和生成式兩類。抽取式摘要主要是直接抽取輸入文本的幾句話來概括整段的內容，這個實現相對簡單（常用演算法 TextRank、TF-IDF 等，本文使用的是 BM25 演算法）。另一種是生成式，生成式的構成比較複雜，實現難度也很大，效果在實際落地過程中也並不理想。所以下文主要是針對抽取式自動摘要來討論的。

問題的演算法抽象

首先抽取式摘要，問題可以歸結為從文章中選取和其他句子最相關的那句話。也就是將每句話當成「搜索框」里輸入的句子，然後計算其他句子和他的相關度得分，然後選取和其他句子相關性得分最高的那句話作為摘要。

BM25演算法：

首先BM25演算法在搜索引擎領域是很有用的。這裡關於BM25解析，講的很好的文章：  BM25 – ywl925 – 博客園  。這裡就不展開介紹了。

BM25演算法得分的歸一化

經過BM25演算法計算的得分，範圍相差會很大，筆者為了實現後面的靜態加分，先對BM25算的score進行了一個歸一化。歸一化一般最常見的兩種： Min-Max和Z score，是相對常見的概念。可以參考博客： 數據歸一化和兩種常用的歸一化方法 – ChaoSimple – 博客園

特定領域知識的積累

這裡明確一下，這裡所說的領域知識，主要是某些很有區分度的詞和短語。這裡涉及的底層模塊也比較多。

首先是特定領域的語料庫的積累。

以中文為例，除了一些公開的語料庫，我們還需要一些擴充一些專門領域的語料。並對他們進行標註。

然後相應的，分詞模塊也要增強。

特別是針對那些領域專有的名詞。由於現在中文分詞的技術已經比較成熟，所以這塊相對來說挑戰不是很大。而且這面即使是基於HMM或者CRF做的分詞，都已經有很可觀的實用表現，和相當的泛化。不過如果能把底層的分詞的模塊性能和準確率提升一點，也會有很大的幫助，畢竟在中文文本處理中，分詞是第一步要做的基礎操作。

行業知識靜態加分

這裡的實現目前還是比較粗糙的。首先總結每個行業有區分度的詞。這個詞的獲取會上面提到的特定的行業語料庫，以及針對這個領域的分詞。

在句子計算BM25得分，並歸一化後，這裡判斷句子裡面是否有領域關鍵詞，如果有領域關鍵詞，則靜態的給歸一化後的BM25 分數加一個靜值。 之後對各個句子，按照這個新的分數排序。抽取得分最高的那句話。

這裡還有一個問題可以深挖，就是筆者目前實現的領域知識加分，是在已經預先分好了分類的前提下，也就是說傳入的參數，除了原文還會有屬於哪個領域的具體信息。如果這個領域分類信息沒有提前獲得，那麼就需要對整段文字做一個大概的分類，這樣的難度就會大增。我們後續可以繼續討論這種情況。

經典檢索演算法：BM25原理

本文cmd地址： 經典檢索演算法：BM25原理

bm25 是一種用來評價搜索詞和文檔之間相關性的演算法，它是一種基於 概率檢索模型 提出的演算法，再用簡單的話來描述下bm25演算法：我們有一個query和一批文檔Ds，現在要計算query和每篇文檔D之間的相關性分數，我們的做法是，先對query進行切分，得到單詞$q_i$，然後單詞的分數由3部分組成：

最後對於每個單詞的分數我們做一個求和，就得到了query和文檔之間的分數。

講bm25之前，我們要先介紹一些概念。

BIM(binary independence model)是為了對文檔和query相關性評價而提出的演算法，BIM為了計算$P(R|d,q)$，引入了兩個基本假設：

假設1

一篇文章在由特徵表示的時候，只考慮詞出現或者不出現，具體來說就是文檔d在表示為向量$\vec x=(x_1,x_2,…,x_n)$，其中當詞$t$出現在文檔d時，$x_t=1$，否在$x_t=0$。

假設2

文檔中詞的出現與否是彼此獨立的，數學上描述就是$P(D)=\sum_{i=0}^n P(x_i)$

有了這兩個假設，我們來對文檔和query相關性建模：

接著因為我們最終得到的是一個排序，所以，我們通過計算文檔和query相關和不相關的比率，也可得文檔的排序，有下面的公式：

由於每個 xt 的取值要麼為 0 要麼為 1，所以，我們可得到：

我們接著做下面的等價變換：

其中N是總的文檔數，dft是包含t的文檔數。

以上就是BIM的主要思想，後來人們發現應該講BIM中沒有考慮到的詞頻和文檔長度等因素都考慮進來，就有了後面的BM25演算法，下面按照

3個部分來介紹bm25演算法。

，也就是有多少文檔包含某個單詞信息進行變換。如果在這裡使用 IDF 的話，那麼整個 BM25 就可以看作是一個某種意義下的 TF-IDF，只不過 TF 的部分是一個複雜的基於文檔和查詢關鍵字、有兩個部分的詞頻函數，還有一個就是用上面得到的ct值。

tf-idf中，這個信息直接就用「詞頻」，如果出現的次數比較多，一般就認為更相關。但是BM25洞察到：詞頻和相關性之間的關係是非線性的，具體來說，每一個詞對於文檔相關性的分數不會超過一個特定的閾值，當詞出現的次數達到一個閾值後，其影響不再線性增長，而這個閾值會跟文檔本身有關。

在具體操作上，我們對於詞頻做了」標準化處理「，具體公式如下：

其中，tftd 是詞項 t 在文檔 d 中的權重，Ld 和 Lave 分別是文檔 d 的長度及整個文檔集中文檔的平均長度。k1是一個取正值的調優參數，用於對文檔中的詞項頻率進行縮放控制。如果 k 1 取 0，則相當於不考慮詞頻，如果 k 1取較大的值，那麼對應於使用原始詞項頻率。b 是另外一個調節參數 （0≤ b≤ 1），決定文檔長度的縮放程度：b = 1 表示基於文檔長度對詞項權重進行完全的縮放，b = 0 表示歸一化時不考慮文檔長度因素。

如果查詢很長，那麼對於查詢詞項也可以採用類似的權重計算方法。

其中，tftq是詞項t在查詢q中的權重。這裡k3 是另一個取正值的調優參數，用於對查詢中的詞項tq 頻率進行縮放控制。

於是最後的公式是：

gensim在實現bm25的時候idf值是通過BIM公式計算得到的：

然後也沒有考慮單詞和query的相關性。

此處 EPSILON 是用來表示出現負值的時候怎麼獲取idf值的。

總結下本文的內容：BM25是檢索領域裡最基本的一個技術，BM25 由三個核心的概念組成，包括詞在文檔中相關度、詞在查詢關鍵字中的相關度以及詞的權重。BM25里的一些參數是經驗總結得到的，後面我會繼續介紹BM25的變種以及和其他文檔信息（非文字）結合起來的應用。

BM25 演算法淺析

搜索之 BM25 和 BM25F 模型

經典搜索核心演算法：BM25 及其變種

信息檢索導論

【轉】相關性打分

原文： ;wd=eqid=c38628d80000913b000000055f5c827a

BM25演算法是一種常見用來做相關度打分的公式，思路比較簡單，主要就是計算一個query裡面所有term和文檔的相關度，然後在把分數做累加操作,而每個詞的相關度分數主要還是受到tf/idf的影響。公式如下：

其中： 是每個詞和文檔的相關度值； 代表query中的term； 代表相關的文檔； 是詞 的權重。

可由外部設置，默認是 值，idf公式的基本思想是：詞的重要程度和其出現在總文檔集合里的頻率成反比。其公式如下:

其中： 是文檔總數； 是包含該詞的文檔數；0.5是調教係數，避免 為0的情況。取個log是為了讓idf的值受N和 的影響更加平滑。

從這個公式可以看出當 越大， 越小時 值越大，

下面是 的公式，

其中: ， ， 都是調節因子，一般 ， ， ； 是詞 在文檔中的次數， 代表詞在查詢句里的次數； 是文檔長度， 是文檔平均長度；

可以看出如果其他因素一樣 越大，相關度越低；至於除以一個 ，我想是拿本篇文檔長度和整體文檔長度水平做比較 ，以免單獨取 值時過大。

乘積的左邊因數代表詞在文檔中的次數關係，乘積的右邊因數代表詞在查詢語句中的次數關係。絕大多數情況下，查詢詞在查詢語句裡面出現一次，所以 可以看成是1，又因為 為1，所以右邊因數其實就等於1，所以公式可化簡為下面這樣:

公式化簡後可得:

影響BM25公式的因數有

1 ： 越高分數越高

2 ： 越高分數越高

3 ： 如果該文檔長度在文檔水平中越高則分數越低。

4 為分數的調節因子

一般情況下，一篇文章是分為多個部分的，如 title，content，description，anchor 等，在BM25F算分公式中，這些部分被稱為域(field)。有兩篇文章，一篇文章的title部分與query 的BM25相關性得分為 a， 另一篇文章的content部分與query 的BM25相關性得分也為 a。假設不考慮這兩篇文章其他部分與query的相關性情況，根據經驗，一般第一篇文章應該應該比第一篇文章更相關。BM25F 引入了文章d的每個域的信息，它將每個term在文章d中的每個域中的相關性進行了處理。公式如下：

BM25 被也稱為 Okapi BM25 , OkaTP是BM25與 term proximity 融合的相關性計算公式。

query中第 個term的權重定義為：

可以發現 的定義在形式上比較像BM25中 query部分與IDF 的乘積。 區別是常量參數的設置。在論文中設置 .

term proximity 定義如下

is the distance expressed in number of words between search term and .

下式體現了BM25與 term proximity 的融合， 該演算法將BM25中的tf 替換成了

的定義和BM25相同。

OkaTP 最終定義為

其中 S是 query中所有term 兩兩組合的集合。

該演算法與 OkaTP 非常相似。

其中TP即 term proximity，在該演算法中引入了proximity 信息來優化相關性計算效果。

假設一個query q中包含n個term ， 表示一篇文章，任意兩個不同term 在文章 中所處位置的距離表示為 。這兩個term的

note: query中的第 個term可能在 document 可能出現多次， 每一次出現用 表示。

原始論文見 Term proximity scoring for ad-hoc retrieval on very large text collections

可以結合文章 Selective Term Proximity Scoring Via BP-ANN 理解上面第2，3兩個公式。

文章認為OkaTP存在兩個方面的問題 1. OkaTP 算分公式的後面部分(可以看做對於prase的算分)和前面的BM25部分是有重疊的，即一個term會同時出現在前後兩個部分； 2.Linear combination of scores of unigrams and those of loose phrases may break the non-linear property of term frequency。

基於這兩點提出了 newTP演算法。 newTP中引入了 span的概念。 span 是根據query term在一個docment中的命中位置，將整個命中列表分割為多個片段，每個片段稱為一個 expanded span。 span 的確定規則如下。

其中 MAX_DIS 是認為設定的。

根據span的中 query term的密度和數量來確定一個term對於相關性的貢獻。從而取代OkaTP 中的 tpi 和 tf部分。

一個 中的term t的 對於相關性的貢獻表示為:

其中:

一個term t 在整個document 中對相關性的貢獻為:

可以看出 rc 中包含了 proximity的信息 和 tf的信息。

直接用 rc 替換 BM25 中的 tf， 得到新的相關性計算公式:

其中TOP即 term order proximity. 該演算法是在BM25TP的基礎上進行的優化。在該演算法中引入了 term oder信息， 如果兩個term在 query中出現的順序 與 其在document中的順序相反則進行懲罰， 如果順序相同則 reward。

在BM25TP演算法中 使用的 來計算proximity， 但是這個公式對於term oder是不敏感的。就會認為 John is faster than Mary 和 Mary is faster than John 兩個句子是相同的。

為了說明 BM25TOP演算法，先引入如下兩個定義。

: The position of in query Q

: The position of in document d

在BM25TOP 中使用了一個新的公式對 進行了替換。這個公式應該符合如下三個條件。

滿足前兩條是BM25TP演算法中dist 函數也能滿足的，第三條是增加考慮 term order 的一項。

滿足以上三個條件的公式挺多，論文中選擇了如下公式。

其中

的大小表示 和 在文檔 d 中 的相對距離，符號說明了這兩個term在query和document中的順序是否相同，正號(+) 表示順序相同，符號(-) 表示這兩個term在query和document中的順序相反。

隨 的函數變化圖像如下:

[圖片上傳中…(image-8d6891-1599898211594-0)]

note: proximity 是 的倒數， 值越大 proximity 越小。

從上圖可以看出，兩個term距離越遠， 越大， proximity 越小；

當對於兩對term的 的大小相等，但符號相反時，符號為負(-) 的一對 term 的proximity會更小。

下面將BM25TOP的計算公正整理如下：

其中: