BM25(Okapi BM25)

바쁘신 분들을 위한 결론

1. BM25는 단어의 빈도수가 같을 경우 문서의 길이가 길수록 낮은 score를 가진다.
2. 다른 문서에 잘 등장하지 않는 단어 a를 포함한 문서는 a의 빈도수가 높지 않아도 높은 score를 가진다.
3. 같은 단어가 너무 많이 등장하면 낮은 score를 가진다.

 

BM25 : 키워드 기반의 랭킹 알고리즘

• BM25(a.k.a Okapi BM25)는 주어진 쿼리에 대해 문서와의 연관성을 평가하는 랭킹 알고리즘으로, TF-IDF 계열의 검색 알고리즘 중 SOTA(State-of-the-art)
• 엘라스틱서치에서도 ElasticSearch 5.0서부터 기본(default) 유사도 알고리즘으로 BM25 알고리즘을 채택

 

 

BM25 살펴보기

• BM25는 Bag-of-words 개념을 사용하여 쿼리에 있는 용어가 각각의 문서에 얼마나 자주 등장하는지를 평가한다.
• 키워드 q1,..., q_n을 포함하는 쿼리 Q가 주어질 때 문서 D에 대한 BM25 점수는 다음과 같이 구한다.

 

IDF (Inverse Document Frequency)

IDF(inverse document frequency) weight 로 전체 문서에서 query(단어)에 대한 전체 카운트를 뜻한다.

즉 tf-idf 문서를 참조하면 이해하기 쉽다.

 

 

 

 

TF (Term Frequency, 단어 빈도수)

TF는 특정문서 d에서 단어 t(검색어)가 등장한 횟수를 말한다.

해당 문서에 중요한, 핵심적인 의미를 가지는 단어일 수록 해당 단어는 문서에서 자주 등장할 확률이 높다. (물론 의도적으로 단어를 많이 노출해서 중요한 문서처럼 보이는 ‘광고’도 있을수 있다.)

수식이 복잡하지만 사실 대부분이 상수다.

f(qi, D) : qi(토큰)이 D 문서에 출현한 횟수

K1 : 같은 토큰일 경우 패널티 부여 가중치 (default 1.2 ~ 2.0 값 , 디폴트 1.2)

b : 문서의 길이에 따르는 패널티를 부여 (default 0.75 )

|D| : 해당 문서의 길이

avgdl : 모든 문서의 평균 길이

 

 

파이썬 구현

from konlpy.tag import Mecab
import pandas as pd
import math
import numpy as np
from collections import defaultdict

class BM25:
    def __init__(self, documents, k1=1.2, b=0.75):
        self.documents = documents
        self.k1 = k1
        self.b = b
        self.doc_count = len(documents) # 총 문서 갯수
        self.avgdl = 0                  # 문서 평균 길이 
        self.doc_freqs = []             # 각 문서 내 corpus 카운트 
        self.idf = {}                   # corpus당 idf 값
        self.doc_len = []               # 각 문서 길이
        
        self._calc_idf()

        
    def _calc_idf(self):
        doc_tokenized_corpus = list(map(lambda s: ' '.join(mecab.morphs(s)), self.documents ))
        doc_corpus = [token.split(" ") for token in doc_tokenized_corpus]

        # 문서별 IDF 계산
        word_freq = defaultdict(int)
        total_words = 0
        for document in doc_corpus:
            self.doc_len.append(len(document))
            total_words += len(document)
            
            frequencies = defaultdict(int)
            for word in document:
                frequencies[word] += 1
            
            self.doc_freqs.append(frequencies)
            
            for word, freq in frequencies.items():
                word_freq[word] += 1

        self.avgdl = total_words / self.doc_count
        
        for word, freq in word_freq.items():
            idf = math.log(1 + (self.doc_count - freq + 0.5) / (freq + 0.5))
            self.idf[word] = idf

            
    def get_top_n(self, query, n=5):
        query_morphs = mecab.morphs(query)
        scores = self.get_scores(query_morphs)
        top_n = np.argsort(scores)[::-1][:n]
        return [self.documents[i] for i in top_n]



    def get_scores(self, query):
        score = np.zeros(self.doc_count)
        doc_len = np.array(self.doc_len)
        for q in query:
            q_freq = np.array([(corpus[q] or 0) for corpus in self.doc_freqs])
            # TF 계산
            try:
                score += (self.idf[q] or 0) * (q_freq * (self.k1 + 1) /
                                                   (q_freq + self.k1 * (1 - self.b + self.b * doc_len / self.avgdl)))
            except Exception:
                # 알수 없는 단어일 경우 패스 
                pass
        return score

 

실행

query = "문의"
result = bm25.get_top_n(query)
result

결과

 

 

참고사항

https://heytech.tistory.com/337

https://simonezz.tistory.com/41

https://blog.naver.com/PostView.naver?blogId=goreng2&logNo=221782081265&redirect=Dlog&widgetTypeCall=true&directAccess=false

https://blog.naver.com/shino1025/222240603533

https://littlefoxdiary.tistory.com/12

https://github.com/shmsw25/GraphRetriever