블로그 이미지
평범하게 살고 싶은 월급쟁이 기술적인 토론 환영합니다.같이 이야기 하고 싶으시면 부담 말고 연락주세요:이메일-bwcho75골뱅이지메일 닷컴. 조대협


Archive»


 
 

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

sklearn을 이용한 구현


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


http://bcho.tistory.com/1216 를 통하여 tf-idf를 이용하여 문서를 벡터화 하고, nmf를 이용하여 문서의 특성을 추출한 다음, 코싸인 유사도를 이용하여 유사 문서를 검색하는 알고리즘에 대해서 알아보았다. 이번글에서는 이 알고리즘을 직접 sklearn을 이용해서 구현해보도록 하자. sklearn은 이용하면 분산 학습을 이용한 대규모 데이타 처리는 불가능하지만, 작은 수의 문서나 모델에는 사용이 가능하다. 무엇보다 sklearn의 경우 대부분의 모델을 라이브러리화 해놓았기 때문에, 복잡한 구현이 없이 쉽게 사용이 가능하다.


전체 소스 코드는 https://github.com/bwcho75/dataanalyticsandML/blob/master/NMF%20based%20document%20recommendation/NMF%20based%20similar%20document%20recommendation.ipynb 에 공유되어 있다.


샘플 데이타

여기서 사용할 데이타 셋은 sklearn 테스트 데이타셋에 있는 20개의 뉴스 그룹의 이메일 데이타를 사용한다. 총 20개의 토픽으로 약 18000개의 포스팅으로 구성되어 있다.


이메일 텍스트 형식으로, 제목과, 날짜등의 헤더 정보와 이메일 내용으로 구성되어 있다. 첫번째 코드에서는 이 데이타를 읽어서 제목과 본문만을 추출하여, Pandas data frame에 저장하도록 한다.


from sklearn.datasets import fetch_20newsgroups
import StringIO
import pandas as pd

newsgroups_train = fetch_20newsgroups(subset='train')

def parseDocument(data):
   buf = StringIO.StringIO(data)
   line=buf.readline()
   data=[]
   subject=''
   while line:
       if(line.startswith('Subject:')):
           subject = line[8:].strip()
       elif (line.startswith('Lines:')):
              lines = line[6:]
              while line :
                   line = buf.readline()
                   data.append(line)
       line=buf.readline()
   text = ''.join(data)
   
   return subject,text


textlist = []
df = pd.DataFrame(columns=['text'])
for data in newsgroups_train.data[0:1000]:
   subject,text = parseDocument(data)
   df.loc[subject]=text
df.head()


제목은 ‘Subject:’로 시작하는 줄에 들어 있고, 본문은 ‘Lines:’로 시작하는 줄에 있다. 이 내용들만을 추출하여 pandas data frame에 저장하였다. 본문은 data frame 상에 ‘text’라는 이름으로된 컬럼에 저장하였다.

Tfidf 를 이용한 단어의 벡터화 구현

단어를 벡터로 변환하기 위해서 앞에서 설명한 tfidf 모델을 이용한다. sklearn에 이미 구현이 되어 있기 때문에 어렵지 않게 구현이 가능하다.


from sklearn.feature_extraction.text import TfidfVectorizer

vectorizer = TfidfVectorizer()
vectors = vectorizer.fit_transform(df['text'].tolist())
print(vectors.shape)


간단하게, TfidfVectorizer를 로딩한다음에, fit_transform을 이용하여, 문장의 본문이 있는 데이타 프레임의 ‘text’ 컬럼을 배열 형태로 변환하여 리턴해주면 된다.


NMF를 이용하여 본문에서 특성 추출

문서가 tf-idf를 이용하여 벡터화가 되었으면, NMF를 이용하여, 각 문서별로 특성을 추출한다.

NMF역시 sklearn에 NMF라는 모듈로 미리 정의되어 있다. 단지, 몇개의 특징으로 압축을 해낼것인지만 지정하면 되는데, 여기서는 n_components 인자를 이용하여 총 40개의 특징으로 특성을 압축하여 추출하도록 하였다.


from sklearn.decomposition import NMF

vector_array = vectors.toarray()
nmf = NMF(n_components=40)
nmf.fit(vector_array)
features = nmf.transform(vector_array)


추출된 피쳐는 features 변수에 저장하였다.

피쳐 정규화

추출된 피쳐가 피쳐마다 또는 문서마다 변화의 폭이 클 수 있기 때문에, Normalizer를 이용하여 0~1사이로 스케일링을 한다. 이 정규화 역시 간단하게 아래와 같이 Normalizer 모듈을 이용하면 된다.


from sklearn.preprocessing import Normalizer

normalizer = Normalizer()
norm_features=normalizer.fit_transform(features)

print(norm_features[0:2])


정규화된 피쳐가 배열 형태이기 때문에, 사용 편의상 데이타 프레임에 로딩한다.


df_features = pd.DataFrame(norm_features,index=df.index.tolist())


df_features 변수에 문서별 특징과 문서 제목을 가지고 데이타 프레임을 만들어서 생성하였다.

인덱스는 문서의 이름이 될것이고 0~39 컬럼은 각문서별 특징이 된다. 출력해보면 대략 다음과 같은 모양이 된다.


문서 유사도 계산

문서별로 특징을 계산이 끝났으면 특정 문서와 유사한 문서를 찾도록 해보자.

앞의 글에서도 설명했지만, 문서의 유사도는 코싸인 유사도를 사용한다.

공식을 다시 기억해보면


여기서 A는 문서 A의 특성 행렬, B는 B 의 특성 행렬이 된다. |A|와 |B|는 각 문서 특성 행렬의 벡터의 길이인데, 앞에서 정규화 Normalization 을 하면서 각 문서의 행렬의 크기가 1이 되었기 때문에, 여기서 코싸인 유사도는 A*B / |A|*|B| = A*B / 1*1 = A*B 가된다.

즉 두 문서의 특성 행렬을 곱한 값이 코싸인 유사도가 된다.


데이타 프레임을 이용하면, 하나의 문서 특성 행렬을 전체 문서에 대해서 곱할 수 있다. .dot 함수를 이용하면 되는데,


article = df_features.loc['WHAT car is this!?']


“WHAT car is this!?” 라는 문서의 유사한 문서를 찾아보도록 하자. df_features에서 “WHAT car is this!?” 의 특성 행렬을 찾아내서 article 변수에 저장하고


similarities=df_features.dot(article)


전체 문서의 특성행렬에서 각 문서의 특성 행렬과 article 문서의 특성행렬을 곱한다. 그러면 article 문서에 대해서 각문서에 대한 유사도가 계산이된다.


top=similarities.nlargest()


이 값을 큰 순서대로 소팅해서 top 이라는 변수에 저장해놓고, 유사도가 높은 문서데로 문서의 제목과 유사도를 출력해본다.


texts = df.loc[top.index]['text'].tolist()
i = 0
for text in texts:
   print('TITLE :'+top.index[i]+" Similarities:"+ str(top[i]))
   #print(text+'\n')
   i = i+1



다음은 실행 결과이다.

TITLE :WHAT car is this!? Similarities:1.0
TITLE :Re: WHAT car is this!? Similarities:0.999080385281
TITLE :Re: New break pads & exhausts after 96K km (60K mi) on '90 Maxima? Similarities:0.980421814633
TITLE :Insurance Rates on Performance Cars SUMMARY Similarities:0.945184088039
TITLE :Re: What is " Volvo " ? Similarities:0.935911211878


간단하게 tf-idf와 NMF를 이용한 문서 유사도 측정을 구현해봤다. 조금 더 높은 정확도와 대규모 학습을 위해서는 이보다는 Word2Vector를 이용한 문서의 벡터화와, 딥러닝을 이용한 문서의 유사도 분석을 하면 훨씬 정확도를 높일 수 있다. 전체 기본 개념은 유사하다고 보면 된다.


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 가 있을 때 이 두 벡터의 내적 ab = |a|*|b|*cos(θ) 가 된다.

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


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


가 되고, 이를 계산하는 공식은 ab 은 벡터 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을 이용해서 구현해보도록 한다.