BM25 알고리즘을 이용한 문서 관련도 점수 계산 방법
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- 소프트웨어 개발자, 검색 엔지니어, 정보 검색 시스템 설계자
- 난이도: 중간(알고리즘 이해 및 C# 코드 구현 기초 필요)
핵심 요약
- BM25 알고리즘은 문서와 쿼리 간 관련도를 계산하기 위해
Term Frequency (TF)와Inverse Document Frequency (IDF)를 결합한 비선형 점수 계산 방식을 사용 - TF 계산 시 토큰 빈도에 따라 점수 감소(diminishing returns)를 적용하여 과도한 빈도에 대한 편향 제거
- IDF 계산은 토큰의 전체 문서 집합에서의 희소성(rarity)을 반영하여 관련도 높은 토큰에 가중치 부여
- C# 예제 코드로 BM25 알고리즘 구현
섹션별 세부 요약
1. 문제 정의: 관련도 점수 계산의 필요성
- 문서 풀에서 특정 키워드로 검색 시, 해당 키워드가 포함된 문서의 관련도에 따라 순위 결정 필요
- 단순한 토큰 빈도 기반 점수 계산은 과도한 빈도에 대한 편향 및 다중 토큰 매칭 시 관련도 평가 불가 문제 발생
2. 기초 개념 정의: 토큰과 역색인 인덱스
- 문서 및 쿼리 토큰 정의: "단어" = "토큰" (예:
“A”, “panda”, “is”, “black”) - 역색인 인덱스: 토큰별로 포함된 문서 목록을 사전 형태로 저장 (예:
"black"토큰 → 문서 1, 3, 6) Document및SearchResult클래스 정의 (문서 ID, 토큰 목록, 점수 등 포함)
3. 기초 점수 계산: 토큰 빈도 기반
- 단순 빈도 기반 점수 계산:
GetScore(string token, Document doc)함수로 토큰 빈도를 1:1로 계산 - 문제점: 문서 6의
"black"토큰이 11번 반복되어 과도한 점수 부여 - 해결 방안: 점수 상한선(예: 5) 적용 및 다중 토큰 매칭 시 보너스 점수 부여
4. BM25 알고리즘 적용: 비선형 점수 계산
- TF 계산: 토큰 빈도에 따라 점수 감소(예: 1회 → 1점, 2회 → 0.95점, 3회 → 0.92점)
- IDF 계산: 전체 문서 집합에서 토큰의 희소성 반영 (예:
"the"토큰은 모든 문서에 존재 → 낮은 가중치,"animal"토큰은 문서 1에만 존재 → 높은 가중치) - C# 구현 예제:
```csharp
public double GetScore(List
{
double totalScore = 0;
int matchToken = 0;
foreach (var token in queryTokens)
{
int frequency = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
if (frequency > 0) matchToken++;
double freqScore = (1 - Math.Pow(decay, frequency)) / (1 - decay);
totalScore += freqScore;
}
if (matchToken == queryTokens.Count) matchToken *= 2;
totalScore += matchToken * 10;
return totalScore;
}
```
- 결과: 문서 3(“cat” + “black” 포함) → 22점, 문서 6(“black” 11번) → 15점
5. 알고리즘 한계점 및 개선 방향
- 문제점:
"the"와"animal"모두 단일 빈도로 점수 동일 (예: 문서 2, 3, 5, 6 → 각각 1점) - 개선 방안: 역색인 인덱스를 통해 전체 문서 집합의 토큰 희소성 반영 (IDF 계산)
결론
- BM25 알고리즘은 단순 빈도 기반 점수 계산의 한계를 극복하며, 비선형 TF 계산과 IDF 가중치를 결합하여 관련도를 정확히 평가
- C# 구현 시
Math.Pow와decay파라미터를 활용하여 점수 감소 효과 적용 - 역색인 인덱스를 통해 전체 문서 집합의 토큰 분포를 분석하여 IDI 계산 시 토큰 희소성 반영 필수