사례연구: TF-IDF 기반 문서 검색 (내용기반 Content-Based 검색)

💬 인트로

문서검색이란, 사용자가 검색엔진에 질의(Query) 또는 문장을 입력해 검색엔진은 질의와 관련이 되는 문서들-검색결과를 찾아내어 사용자에게 제공하는 과정이다. 문서검색은 정보검색의 대표적인 사례로, 검색엔진에서의 검색어들이 질의가 된다.

 

🅰 Boolean Search

• 정보검색 분야에서 널리 사용되는 단순한 검색방법
• Boolean Logic을 사용하여 질의문장을 만든다 (AND, OR, NOT 등)
• ex. (흥부 OR 놀부) AND NOT 제비
• (장점) 검색 시스템이 단순히 각 문서가 질의 문장의 조건을 만족하는지를 테스트하면 되므로 구현이 쉽고 빠르며 많은 데이터를 쉽게 다룰 수 있다.
• (단점) 동음이의어, 다의어 검색에 취약하며 많은 양의 문서들을 검색 시 정확하고 복잡한 질의가 요구되어 일반인에게 다루기 어렵다. 또한 검색 결과에 대한 우선순위를 부여할 수 없고, 너무 많거나(OR) 적은(AND) 검색 결과가 발생하기 쉽다.

🅱 순위 검색 모델 Ranked Retrieval Models

검색된 결과를 질의와 관련된 순서에 따라 문서들을 나열하는 개선된 방법

검색엔진이 각 문서와 질의와의 관련도를 계산해 우선순위를 결정함, 사람이 사용하는 일반적 문장의 형식으로 자유롭게 구성할 수 있다. 이 글의 남은 부분에서는 모두 순위 검색 모델를 구하는 방법에 대해 얘기해본다.

• 질의-문서 관련도 : 문서의 순위는 대상집합에 포함된 각 문서 간 유사도 점수를 부여해 계산
• 질의에 포함된 각 용어들이 출현하는 빈도수가 높은 문서일수록 관련도가 높다 (여러 번 포함될 수록 높은 점수 부여)

• 용어벡터
  1. 용어출현벡터 term incidence vector : 용어의 출현 여부 → 이진벡터(자카드 계수 사용)
  2. 용어빈도벡터 term frequency vector : 용어의 빈도수 → 코사인유사도 사용

 

0️⃣ 자카드 계수

두 항목집합 A와 B의 중복(match)의 정도를 측정하기 위해 사용하는 방법

집합 A와 B는 동일 크기일 필요가 없으며 계수의 범위는 [0, 1] 이다.

 

ex. 하나의 질의와 각 문서와의 유사도를 자카드 계수로 계산한다.

질의 : 흥부와 놀부

문서1 : 흥부와 놀부는 형제다

문저2 : 흥부는 착하다

1. 용어사전 정의 (term dictionary) 조사, 어미 등을 제외하고 중요 용어들고 사전 구성 (2단어 이상으로 구성된 복합어도 용어로 정의 가능)	용어사전 = (흥부, 놀부, 형제, 착하다)
2. 질의와 문서를 용어 집합으로 변환 → 이진 용어 벡터로 변환 가능	질의 : {흥부, 놀부} 문서1 : {흥부, 놀부, 형제} 문서2 : {흥부, 착하다}
3. 질의와 각 문서와의 자카드 계수를 계산	질의-문서1 : | {흥부, 놀부} | / | {흥부, 놀부, 형제} | = 2/3 = 0.67 질의-문서2 : | {흥부} | / | {흥부, 놀부, 착하다} | = 1/3 = 0.33 → 질의는 문서1과 더 유사하다

자카드 계수의 한계

• 용어가 문서에 포함되는 지 여부만 고려하고 빈도수(출현하는 횟수)는 고려하지 않는다
• "드물게 출현하는 용어가 자주 출현하는 용어보다 많은 정보를 가진다"
• 문서의 길이를 정규화(normalizing)하는 고급의 방법이 필요하다 (아래의 수식 사용 가능)

  

 

1️⃣ 용어빈도수 tf; term frequency

tf_t,d : 문서 d에서 용어 t의 출현 빈도수

• 절대 빈도수를 그대로 사용하는 것에 문제가 있다
• 즉, 관련도와 용어빈도수는 비례관계가 아니므로 빈도수의 효과를 누그러뜨리기 위해 절대빈도수의 로그값을 사용한다
• 용어 t의 로그 빈도수 가중치를 아래와 같이 정의
  

  

  0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc
• 질의-문서쌍의 유사도 점수 계산
  질의 q와 문서 d에 공통적으로 포함된 용어에 대해 가중치를 합산
  

  

 

2️⃣ 문서빈도수 document frequency - 용어의 중요도에 더 많은 영향을 미침

임의의 용어가 대상 집합의 문서들 중 몇 개의 문서에서 출현했는지의 빈도수

(용어의 수를 세는 것이 아님)

• 희귀하게 사용되는(=문서빈도수가 낮은) 용어는 흔하게 사용되는(=문서빈도수가 높은) 용어보다는 정보가 많다. 희귀한 용어는 특별한 용어로 이러한 용어를 포함하는 문서가 이 용어와 관련성이 높은 문서임을 알려주는 단서가 된다. 예를 들어, "초현실주의적"이라는 용어는 희귀하게 사용되는 전문적인 미술 용어리므로 이 용어가 포함된 문서가 미술 분야 문서일 가능성이 높다.
• 따라서 희귀한 용어(rare term)에 대해 높은 가중치를 두는 것이 합리적이다.

cf. 집합적 빈도수 collection frequency : 임의의 용어가 검색이 되는 문서 집합 전체에서 몇 번에 걸쳐 출현했는지의 빈도수

 

역문서 빈도

• df_t : 용어 t의 문서 빈도수. 용어 t에 대한 문서빈도수 df가 작을수록 (문서가 희귀할수록) t의 중요도 즉, 정보효용도는 커진다.
• 문서빈도수와 정보효용도가 역의 관계이므로 헷갈려 등장한 것이 역문서빈도 idf이다.
• idf_t = log10(N/(df_t+1)), N은 대상 문서 집합의 크기-문서의 수
• idf 식에서 1을 더한 이유는 분수의 분모가 0이 되는 것을 방지하기 위함이며, log의 밑은 10이든 2든 상관없이 일관되게만 사용하면 된다. log를 사용하는 이유는 역문서 빈도수의 효과를 누그러뜨리기 위해서다.

 

3️⃣ 문서-역문서 빈도가중치 : tf와 idf의 합성

용어 t의 tf 가중치와, idf 가중치의 곱으로 정의. 정보검색 분야에서 많이 사용되는 가중치 방법

• tf-idf 가중치가 증가하는 경우
  • 해당되는 문서에서 용어의 빈도수가 높아질수록
  • 문서집합에서 용어의 희귀성 - rarity가 높아질수록

4️⃣ 질의 q에 대한 문서 d의 관련도 점수

• 문서집합의 각 문서에 대하여 그 문서와 질의에 공통적으로 포함되어 있는 용어에 대해 tf-idf 가중치를 합산하여 관련도를 계산
  

  

• 변형방법 : tf 계산 시 log의 사용유무, 질의에서 각 용어에 대해 다른 가중치 적용
• 긴 문서에는 용어가 많이 포함되어 있으므로 tf, idf가 클 가능성이 높으므로 긴 문서들이 검색 결과의 앞 순위에 들어가는 경향이 있음

5️⃣ tf-idf와 코사인유사도에 기반한 문서 관련도 점수

• 질의와 문서에 공통된 용어의 tf-idf 값의 합산은 긴 문서가 높은 점수를 얻게되는 단점이 있음
• 우리가 원하는 것은,
  문서의 내용, 특성을 기반으로 관련도 점수를 계산하자
  문서의 길이가 점수에 영향을 주지 않도록 하자
• 개선된 방법
  질의와 문서의 관련도 = 질의 벡터와 문서벡터간의 코사인 유사도
  질의도 용어들의 tf-idf 값의 벡터로 변환하여 각 질의와 문서의 문서공간을 만든다
• BUT
  → 문서 공간은 매우 고차원의 벡터공간이지만 희소벡터이다. 웹 검색 엔진에 이 방법을 응용할 경우 초고차원 공간이 되어 효율적인 벡터 저장 및 처리 방법이 필요하다.

• 문서의 유사도로 유클리디언 거리를 사용한다면?
  → 좋은 방법이 아니다. 용어벡터는 용어의 빈도수가 클수록 원점에서 멀어져서 유클리디언 거리도 커져 문서의 길이가 유사도에 영향을 줄 수 있다.
  
  ex. 문서 d2 가 문서 d1, d3 보다 길이가 길다고 가정하고, 질의 q가 문서 d2와 유사한 문서이며 용어들의 분포가 비슷하다고 가정하자. q와 d2의 길이 차이가 커서 유클리디언 거리는 커지게 되며, 오히려 질의 q는 다른문서인 d1과 d3와 거리가 더 가까운 것으로 나타난다.

 

코사인 유사도

이에 따라 거리 대신 각도를 고려한다. 임의의 문서 d를 N번 반복해 이어붙인 새로운 문서 d'이 있다고 가정하자. 원래 문서 d와 d'의 유클리디언 거리는 N이 커짐에 따라 커지나 의미적으로는 d와 d'이 동일하다.

문서의 내용(의미)을 결정하는 것은 각각의 용어의 절대적 빈도수가 아닌, 용어들의 빈도수 분포(비율)이다. 이에 따라 벡터의 각도를 활용한다. 앞에서 나온 두 문서 d, d'의 용어 벡터간의 각도는 0이므로 거리는 최소, 유사도는 최대이며 동일한 문서임을 의미한다.

엄밀히 말해, 각도의 범위는 0 ~ 360도로 각도가 클수록 유사도는 작아진다. 그러나 단위의 차이로 각도를 문서의 유사도로 사용하기에는 불편함이 있어 각도의 코사인 값을 활용한다. 코사인 함수는 입력 [0,180] 범위에서 출력 [1, -1] 범위이며 단조 감소 함수이다. 코사인은 사이 각이 작아질수록 커지므로 유사도로 사용하기에 적합하다.

 

각 질의나 문서의 용어 벡터는 단위벡터로 정규화되며 문서간의 유사도는 용어 벡터의 사이 각의 코사인으로 계산된다. 두 문서에 나타난 용어들의 정규화된 분포가 유사할수록 문서가 유사한 것으로 계산된다. 문서의 길이는 문서의 코사인 유사도와 무관하다.

코사인함수