NMF 알고리즘을 이용한 유사한 문서 검색과 구현(1/2)

NMF 알고리즘을 이용한 유사한 문서 검색과 구현(1/2)

조대협 (http://bcho.tistory.com)

앞의 글들에서, 데이타의 특징을 뽑아내는 방법으로 차원 감소 (Dimension reduction) 기법에 대해서 설명하였다. 구체적인 알고리즘으로는  PCA와 t-SNE 알고리즘을 소개하였는데, 오늘은 차원 감소 기법중의 하나인 행렬 인수분해 (Matrix Factorization)에 대해서 알아보고자 한다.

문서 유사도 검색

행렬 인수 분해를 설명하기 위해서 유사한 문서를 찾는 시나리오를 예를 들어서 설명하겠다.

문서 유사도 검색의 원리는 다음과 같다

1. 문서에 나온 각 단어들을 숫자(벡터)로 변환하여 행렬화 한다.

2. 행렬화된 문서에서 차원 감소 기법을 이용하여, 문서의 특징을 추출한다.

3. 추출된 특징을 기반으로, 해당 문서와 특징이 유사한 문서를 찾아서 유사값을 기반으로 소팅하여, 유사 문서를 찾아낸다.

각 과정에서 사용할 알고리즘을 보면 다음과 같다.

1. 문서의 단어들을 숫자화 하여, 행렬로 변환하는 과정에서는 여러가지 word2Vec (요즘 대세) 알고리즘이 있지만, 간단하게 tfidf 라는 알고리즘을 사용하겠다.

2. 다음 문서의 행렬을 값을 가지고 특징을 추천하기 위해서는 앞에서 언급한 행렬 인수 분해 (Matrix Factorization) 알고리즘을 이용하여, 행렬의 차원을 줄일것이고

3. 해당 문서와 특징 값이 유사한 문서를 찾기 위한 방법으로는 벡터간의 거리를 측정하는 방법을 사용하여 유사도를 측정하는데, Consine distance (코싸인 거리) 알고리즘을 사용하도록 한다.

각 알고리즘에 대한 간략한 개념을 설명하고 구현은 파이썬의 sklearn의 라이브러리를 사용해서 구현하도록 하겠다.그러면 각 알고리즘에 대한 설명을 보자

TF-IDF (Term Frequency Inverse Document Frequency)

TF-IDF를 이해하기 위해서는 먼저 TF(Term Frequency)와 DF(Document Frequency)에 대한 개념을 먼저 이해해야 한다

• TF(Term Frequency) : TF랑, 하나의 문서에서 그 단어(Term) 가 얼마나 자주 나타나는가(Frequency)를 정의한 값이다.
  예를 들어, 한문서에서 “조대협" 이라는 단어가 10번 등장했다면 조대협에 대한 TF값은 10이 된다.

• DF(Document Frequency) : DF란, 전체 문서(Document)에서 그 단어(Term)가 등장한 문서의 수를 나타낸다.  “조대협" 이라는 단어가 20개의 문서에 나타났다고 하면 DF 값은 20이 된다.

그러면 TF-IDF란 무엇인가 TF값을 DF값으로 나눈 값을 TFIDF라고 하는데, 위의 설명에서 “조대협" 이라는 단어에 대한 TFIDF값은 10/20=0.5 가 된다. (정확하게는 IDF는 log 를 포함한 다른 수식을 사용하지만 의미상으로 DF를 나눈것과 같이 문서에 등장하는 단어의 밀도를 나타낸다고 이해하면 된다.)

TF-IDF값의 의미는 무엇일까?

10년치 뉴스 문서가 있다고 가정하자.

그리고 우리가 뉴스에  많이 사용하는 단어로 “예를 들어" 라는 단어가 있다고 가정하자. (원래는 단어별로 잘라서 생각해야 하지만 설명을 쉽게 하기 위해서 두 단어를 하나의 단어로 생각하자). “예를 들어" 라는 단어는 어떤 문서의 특징을 나타내기는 사실 어렵다. 너무 일반적으로 사용되는 말이기 때문인데, 이런 단어의 경우에는 거의 모든 문서에 나타날 수 있기 때문에 DF 값이 매우 커진다. 그래서 “예를 들어"의 TF-IDF 값은 거의 0으로 수렴하게 되고, “세월호"와 같은 단어는 세월호를 언급한 뉴스 기사에만 있기 때문에, DF 값은 낮아질것이고, 결과적으로 TF-IDF 값은 커질 수 있는데, 세월호 라는 단어가 많이 언급된 문서일 수 록 TF-IDF 값이 커지게 된다.

눈치가 빠른 사람은 벌써 이해했겠지만, TFIDF의 기본 원리는 전체 문서에 널리 사용되는 일반적인 단어는 특징에서 배제하고, 문서에 특정 단어가 많이 언급될 수 록 그 단어의 TF-IDF값을 크게 하여, 문서의 특징을 나타내는데 사용할 수 있다.

NMF (Non-negative Matrix Factorization)

NMF (비음수 행렬 인수 분해)는 차원 감소 기법으로, 컴퓨터 시각 처리나, 우리가 하려는 문서 분류 그리고 음파 분석등에 널리 사용된다. 앞의 글들에서 소개했던 PCA나 t-SNE와 같은 차원 감소 기법에 대비한 차이를 보면, NMF에 의해 추출된 특징의 경우에는 해석이 가능하다는 장점을 가지고 있다.

PCA나 t-SNE는 원본 데이타의 특징을 추출하여 새로운 특징 셋으로 표현을 하지만 새로운 특징셋이 원본 특징과 어떤 연관 관계를 가지는지는 해석이 불가능하다. NMF의 경우 새로운 특징셋이 어떻게 원본 데이타 들과 관계를 가지는지 확인이 가능한데 이 부분은 NMF 알고리즘을 먼저 이해하고 하도록 하자

NMF는 행렬 인수 분해 알고리즘 중 하나로, 행렬 인수 분해란 다음과 같다.

우리가 원본 행렬 V가 있다고 했을때, 행렬 인수 분해는 이 V 행렬을 두개의 행렬로 분리 하는 것이다.

아래 그림은 원본 행렬 V 를 V=W*H 로 분리한 예이다.

예를 들어 TF-IDF를 이용하여 책 제목과 단어로 이루어진 행렬 V의 모양이 다음과 같다고 하자

책제목	협상	스타트업	투자	비지니스	데이타	...	...
협상의법칙	0.9	0	0.3	0.8	0
린스타트업	0	0.8	0.7	0.9	0.3
빅데이타	0	0	0.5	0	0.8

< 그림. 책 제목과, 그 책에 나온 단어의 TFIDF 값으로 이루어진 행렬 V >

이를 행렬 분해를 통하면

행렬 W는 다음과 같은 모양을 가지게 되고

책제목	특징1	특징2	특징3	특징4
협상의법칙	0.9	0	0.1	0.2
린스타트업	0	0.8	0	0
빅데이타	0.2	0.1	0.8	0.1

행렬 H는 다음과 같은 모양을 가지게 된다.

	협상	스타트업	투자	비지니스	데이타	...	...
특징1	0.92	0	0.1	0.2	0
특징2	0	0.85	0.5	0.3	0.3
특징3	0	0	0.3	0	0.8
특징4	0	0	0	0	0	...

여기서 W를 가중치 행렬 (Weight Matrix), H를 특성 행렬 (Feature Matrix)라고 한다.

W는 카테고리 (책제목) 에 특성과의 관계를 나타내며, H는 원래 특성(협상,스타트업,...)에 대비한 새로운 특성(특징 1,2,3…)에 대한 관계를 나타낸다.

W 값을 보면 특징 1은 “협상의 법칙"에 자주 나오는 단어들 빈도와 관련이 높은 특성임을 알 수 있고, 특징 2는 “린스타트업", 특징3은 “빅데이타"에 자주 나오는 단어들의 빈도와 관련이 높은 특성임을 예측할 수 있다.

또한 특성 행렬 H를 보면 특징 1은 “협상" 이라는 단어와 관련이 많고, 특징 2는 “스타트업" 이라는 단어와 관련이 많은 것을 알 수 있다.

아래는 그림은  특징을 NMF를 이용하여 추출한 특성 행렬 H를 나타내는데, 해당 특징이 어떤 단어들에 의해서 반응 하는지를 알 수 있다.

그래서 NMF를 PCA나 t-SNE와 같은 다른 알고리즘과 비교했을때 특성을 해석 가능하다고 이야기 하는 것이다.

이 데이타셋에 만약에 이 데이타에 “스타트업 데이타 분석" 이라는 책이 들어왔고, 이 책은 빅데이타와 스타트업에 대해 다루고 있다면, 아마도 가중치 행렬 W에서 “스타트업 데이타 분석"은 다음과 같이 특징2와 3과 관련이 높은 형태를 나타낼 것이다.

책제목	특징1	특징2	특징3	특징4
협상의법칙	0.9	0	0.1	0.2
린스타트업	0	0.8	0	0
빅데이타	0.2	0.1	0.8	0.1
스타트업 데이타 분석	0	0.9	0.7	0

여기서 중요한 것은 차원을 줄일때 몇개의 특징으로 기존의 특성을 압축(줄일가)인데, 여기서는 4개의 특징으로 전체 특성을 줄이는 것으로 하였다. (특징을 몇개로 표현할 것인가가 매우 중요한 튜닝 패러미터가 된다.)

지금까지 설명한 행렬 인수 분해 방식은 행렬의 값이 양수일때 사용하는 행렬 분해 방식으로 “비음수 행렬 인수 분해 (Non negative Matrix Factorization)이라고 한다. NMF 방식에도 여러가지 다양한 발전된 알고리즘들이 있으며, 알고리즘 리스트는 https://en.wikipedia.org/wiki/Non-negative_matrix_factorization 를 참고하기 바란다.

코싸인 거리기반의 유사도 측정

NMF등을 이용하여 압축되어 있는 특성을 기반으로 하여 유사한 문서를 찾는 방법에 대해서 알아보자. 특성을 기반으로 유사도를 측정하는 방법은 여러가지가 있다. 주로 특성값을 벡터 공간에 맵핑 한후, 벡터간의 거리를 기반으로 계산하는 방법이 많이 사용되는데, 유클리디안 거리, 코사인 거리, 자카드 거리, 피어슨 상관 계수, 맨해튼 거리등이 있다. 여기서는 코사인 거리를 사용하여 문서간의 유사도를 측정한다.

코사인 거리의 기본 원리는 다음과 같다.

특성 값을 나타내는 벡터 A와 B가 있을때, 이 벡터 A와 B사이의 각도가 가까울 수록, 두 개의 특성이 유사하다고 판단하기로 한다. 즉 A와 B의 각도 θ 가 최소일 수 록 값이 유사하다고 판단하면 된다. 그러면 벡터 A 와 B만을 가지고, 어떻게 각도 θ를 구할 수 있는가?

벡터의 내적을 사용하면 이 θ 가 크고 작음을 알아낼 수 있는데 기본 원리는 다음과 같다.

벡터 a와 b 가 있을 때 이 두 벡터의 내적 a•b = |a|*|b|*cos(θ) 가 된다.

cos(θ)를 좌변으로 옮기면

cos(θ) = a•b / |a|*|b

가 되고, 이를 계산하는 공식은 a•b 은 벡터 a 행렬의 각 항의 값 Ai 과  b행렬의 각 항의 값 Bi를 순차적으로 곱하여 더하면 된다. (A1*B1+A2*B2 …. + An*Bn)

|a|는 a 벡터의 길이로, sqrt(A1^2 + A2^2 + …. An^2)로 계산을 하고, |b|역시 sqrt(B1^2 + B2^2 + …  Bn^2로 계산한다.)

이를 수식으로 풀어보면 다음과 같다.

이렇게 계산하여, cos(θ) 의 값이 1에 가까우면 유사도가 높고, 0에 가까우면 유사도가 낮은 것으로 판단할 수 있다.

정리해보면  유사도를 파악하고자 하는 문서를 정한 후에, NMF를 이용하여 각 문서의 특성을 추출한후에 NMF에 의해 추출된 가중치 행렬을 가지고, 유사도를 파악하고자 하는 문서와 다른 문서들간의 코싸인 거리를 구하여, 이 거리 값이 가장 큰 문서가 가장 유사한 문서가 된다.

여기까지 간단한게 TF-IDF,NMF 그리고 코사인 유사도를 이용하여 유사한 문서를 찾는 방법을 설명하였다.코싸인 유사도를 적용하지 않고 NMF로 찾아낸 특성값을 기반으로 문서를 군집화 하는 클러스터링에도 활용이 가능하다.

다음글에서는 이 알고리즘을 실제로 sklearn을 이용해서 구현해보도록 한다.