Ranked Retrieval 검색 알고리즘

Boolean Retrieval은 검색 결과가 너무 적거나, 너무 많거나 할 수 있다.
Boolean Retrieval 질의 방법은 일반사용자가 사용하기 불편하다.
이러한 단점을 보완한 것이 Ranked Retrieval

 

 

🔍 Query-document matching scores

• 쿼리와 문서의 매칭 정도를 점수로 매김
• 질의하는 term이 여러번 등장할수록 점수가 더 높음
• "term document incidence matrix(binary incidence matrix)"를 확장하여 term 등장 횟수를 기록했다.
• count matrix라고 부름

 

 

• Bag of words model : term의 위치는 고려하지 않고 등장 횟수만 고려한 모델

🔍 tf - term frequency

 

• 계산식
  

 

• 질의에 여러 단어가 등장할 때
  각각의 결과를 더한다.
  

🔍 idf

• stop word(검색에 영향을 주지않는)를 고려하여 계산하는 법
• 전체 collection에서 tf가 높으면 흔한 단어이다.
• 그러므로 df (term이 등장하는 문서 개수)를 구한다.
  

ex) 100개의 문서에서 df가 100이면 매우 흔하기 때문에 idf는 0이다.

🔍 tf-idf weights (logarithm)

• 결론은 둘이 합쳐진 이 계산식을 사용해 점수를 준다.
  

  

결국 ranking에 영향을 미치는 것을 tf이다. 하지만 term이 많아졌을 때, idf가 중요도를 판단해주는 역할을 한다.

 

🔍 tf-idf ➡ vector로 표현

• 하나의 단어는 x,y 등의 하나의 축을 담당한다.
• document는 점이나 벡터로 표현될 수 있다.

• 질의어도 벡터로 변형할 수 있다.
• 질의어 g와 document 사이의 거리가 짧을수록 ranking이 높아진다. 유사도가 높다.

🔍 질의와 유사한 문서를 구하는 계산법 (질의와 문서의 유사도 구하기)

• 유클리디안 거리 구하는 공식은 정보검색에서 적합하지 않다.
  • 해당 단어가 많이 나올 수록 vector의 위치가 멀어지기 때문에
• 두 벡터 간의 각도가 작을수록 유사하다고 할 수 있다.
  (원점에서 각도를 보면된다)
  
  (이 그림은 d의 내용이 두번 반복된 d'문서를 만들어 실험한 것)

 

• 즉, cosθ가 클수록 유사도가 높다.



• length normalization
• document와 query이 최종 weight를 같은 term끼리 각각 곱하고 전부 더해 유사도를 구한다.