어떤 키워드를 검색할 때, 키워드에 맞는 추천을 해주는 알고리즘에는 어떤 것이 있을까? 대표적으로 TF-IDF가 있다. TF-IDF는 검색한 키워드가 각 문서에서 갖는 가중치 스코어를 토대로 문서를 추천해주는 알고리즘이다.
오늘은 TF-IDF 알고리즘에 대해서 정리하고, 이에 대한 예제 코드를 함께 작성하려고 한다.
TF-IDF는 엘라스틱 서치에서도 스코어 알고리즘 BM25의 기반이 되는 알고리즘이기도 하다. TF-IDF를 이해하기 위해서는 TF와 DF에 대해서 이해를 해야한다. 아래에서 하나하나씩 이해를 해보도록 하자.
TF란 무엇일까?
TF 개념의 탄생은 꽤 재밌는 부분이다. 이 TF의 개념은 한스 피터 룬 (Luhn, H. P., 1957)이 이론에 창시자인데, 한스 피터 룬은 1959년대에 정보 검색 프로세스를 연구하고 있었다. 그러던 중에 한가지 중요한 사실을 깨달았는데, 바로 중요한 단어는 특정 문서에서 등장하는 빈도가 높다는 것이다..!!
TF (Term Frequency), 즉 단어 빈도는 이렇게 만들어 졌다. 하지만 여기에는 문제가 있었다. 바로 의미는 없지만 자주 반복되는 불용어! 불청객들이 있었기 때문이다. 여기서 불용어란, 문장에서 내용을 나타내는데 큰 역할을 하지 않는 기능어들을 말한다. 우리 말에서 예를 들자면, ‘그것’, ‘그’, ‘때’ 등등이 있다. 이러한 불용어들 때문에 TF는 키워드 검색에서 부족한 알고리즘이 되버리고 말았다. 왜냐하면, 불용어가 더 중요한 것처럼 보일 수 있었기 때문이다. 이러한 불용어를 배제하고 중요한 키워드를 찾아내기 위해서 DF가 등장하게 되었다.
TF의 단점을 보완하자! DF 등장!
이러한 TF 알고리즘을 보완하기 위해서 추가된 개념이 DF다. DF는 Document Frequency라고 하는데, ‘어떤 특정한 단어가 다른 문서에서도 자주 나오는지에 대한 수치’이다. 불용어의 경우 여러 문서들에서 여러번 나올 수 있다. 그만큼 자주 쓰이고 흔하기 때문이다. 이러한 DF는 어떤 식으로 구할 수 있을까? 아래 그림을 보자.
위에서 전체 문서가 3개라고 하고 찾고자 하는 ‘네모’ 키워드에 대해서 DF 의 값을 구한다면, DF의 값은 2/3이다. 여기서 주의할 점은 DF는 특정 문서에서 찾고자하는 키워드가 여러번 나온다고 하더라도 “있다”,“없다”와 같이 이분법적으로 계산되어야 한다. 있으면 1, 없으면 0으로 카운트를 해주어야 한다. 즉, ‘키워드가 다른 문서에 나온 수/전체 문서 갯수’ 이다.
TF-IDF
자 이제 TF와 DF의 개념을 어느정도 이해했다면, TF-IDF가 무엇인지 이해할 수 있다. IDF는 DF의 역수를 의미하는데, TF 값에 이 IDF를 곱해주면 우리가 원하는 키워드의 가중치를 알 수 있다. 그렇다면, 왜 역수를 곱해줄까? 특정 문서에서
[해당 키워드가 나온 갯수] x [1/다른 문서에서 해당 키워드가 나온 갯수]
위의 공식을 보면 쉽게 이해할 수 있다. 우리는 “다른 문서에서 해당 키워드가 많이” 나올 수록, 해당 키워드의 중요도는 내려가야 한다. 그렇기 때문에 역수를 곱해주는 것이다. 분모가 커질 수록 값은 줄어들기 때문이다.
예제 코드를 보며 직접 수행해보자.
아래와 같은 문서들이 있다고 가정하자.
| 문서1 | 제목: 중국집에서 짬뽕을! | 내용: 오늘 나는 짬뽕을 먹었다. 짬뽕은 맛있다. |
| 문서2 | 제목: 여행가고 싶다. | 내용: 여행을 하면 힐링이 된다. |
| 문서3 | 제목: 집에서 휴가. | 내용: 날씨가 더울 때는 역시 방콕이 최고! |
위의 3가지 문서를 통해서 TF-IDF의 가중치가 어떻게 계산되는지 확인해보도록 하자.
STEP 1) TF 함수를 구현하자
먼저 TF 함수를 구현해보자. Term Frequency는 위에서 말한것 처럼 특정 문서에서 특정 단어의 등장 횟수를 의미한다.
위의 코드를 살펴보면, 문서 안에 keyword가 있다면 count를 해주는 것을 알 수 있다. 이러한 방법을 TF 정규화 3가지 방법중 하나인 ‘불린 빈도’라고 하는데, 어떤 단어가 문서안에 있다면, 1, 없다면 0으로 하는 방법이다. 이러한 정규화를 하는 이유는 만약 TF가 너무 많아지면 한없이 발산할 수 있으므로, 이를 줄이기 위한 방법이다. 3가지 방법 중 불린빈도는 가장 간단한 방법이다. 이 방법의 단점은 당연히 특정 단어가 1번 나타나던 99번 나타나던 같은 가중치로 본다는 점이다. 불린 빈도 말고도 ‘로그 스케일 빈도’와 ‘증가 빈도’ 등의 정규화 방식이 있다.
위의 함수를 유닛 테스트 해보자. 각각 문서들을 살펴보면, ‘문서1’만 TF 불린빈도가 1임을 알 수 있다.
STEP 2) DF 함수를 구현하자.
다음으로는 Document Frequency (DF)를 구해보자. 이 DF를 구하면 특정 키워드가 다른 문서들에서 어느정도 나오는지 알 수 있는 수치를 알 수 있다.
scala로 예제를 구현하였는데, 여기서 @tailrec 은 꼬리 재귀를 의미한다. 스칼라에서는 자기 자신으로 코드가 끝날 경우, 컴파일 최적화때 해당 재귀함수는 반복문으로 바꿔준다.
코드를 살펴보면, allDocs는 문서1, 문서2, 문서3를 의미한다. 각 문서를 순회하면서 해당 문서 안에
키워드가 한번이라도 등장하면 1을 아니라면 0을 누적시켜서 DF값을 구한다.
모든 문서에서 “짬뽕” 키워드를 찾으면 현재 문서1에만 있기 때문에 1이 나온다.
STEP 3) IDF 함수를 구현하자
IDF는 DF의 역수 로 ‘모든 문서의 수 / DF + 1’을 해주면 된다. 여기서 분모에 +1을 해주는 이유는 DF 값이 0일 경우 분모가 0이 되어버리기 때문에, 이를 방지하기 위한 값이다. 또한 Math.log를 이용하여 로그 값을 취해줌으로써 IDF 값이 너무 커지지 않도록 정규화 해준다.
STEP 4) TF * IDF 로 가중치를 구하자.
이제 위에서 정의한 함수들을 이용해서 TF-IDF 값을 구해보자. 코드는 간단하다 앞에서 구한 TF와 IDF 함수를 호출하여 곱하기만 하면 끝이다.
“짬뽕” 이라는 키워드를 문서1, 문서2, 문서3에서 TF-IDF 값을 구해보면, 문서1이 가장 높은 가중치 값을 갖는 것을 알 수 있다. 왜냐하면 문서1은 제목에도 짬뽕이라는 키워드가 있기 때문에, TF-IDF를 통해 계산할 경우, 해당 키워드 가중치가 좀 더 높게 나오는 것이다.
결론
TF-IDF 알고리즘은 간단하게 구현하기에도 어렵지 않은 알고리즘이다. 물론 정규화를 어떻게 하느냐에 차이는 있겠지만, 검색 키워드에 대해 검색 추천을 하거나 할 때, 써보면 좋을 것 같다는 생각이 든다. 다음번에는 엘라스틱 서치에서 사용되고 있는 TF-IDF 기반한 BM25 알고리즘을 분석해보려고 한다.