NLP

나이브 베이지안 분류기(Naive Bayesian Classifier) - 구현과정

작성일 작성자 난다로~

나이브 베이지안 분류기는 기본적으로 아래와 과정으로 구현된다. 


train set T(i) : train data for c(i)

c(i) : i's class

f(j) : j's feature in feature vector, size V

d(i,k) : k's document in T(i)


1. 학습데이터의 준비 T(i)

   스팸필터링을 위한 나이브 베이지안 분류기를 구현할 경우라면

   스팸이라고 태깅된 문서집합, 정상이라고 태깅된 문서집합을 구해야한다. 

   스팸문서가 어디엔가 누적되고 있는 상태라고 한다면, 스팸문서는 현재 상태로 보고

   정상문서 집합을 어느정도 규모로 수집할 지 결정해야한다. 

   사실 많으면 많을 수록 좋다. 그러나, 너무 많아지면 학습에 걸리는 시간과 비용도 커지게 되므로  

   적절하게 조절해야한다. 


2. feature vector 생성기

   문서에는 많은 정보가 담겨져 있다. 이 모든 정보를 전부 사용하면 좋겠지만, 다룰 수 있는 정도로

   치환해서 문제에 접근하려면 문서를 정형화 시켜서 표현해야한다. 

   f_generator(d)가 이런 역할을 수행한다. 

   이것의 입력은 문서이며

   출력은 아래와 같은 형태의 feature vector이다. 


   f(1)  f(2)  f(3) ..... f(j)

   -------------------------

   0     1     1     ..... 0


   여기서 1,0은 해당 feature f(j)가 문서에 존재하는가(1), 아닌가(0)를 표시한다. 


   feature는 문서를 처리하는 경우이므로 대부분 문서에 등장하는 단어일 것이다. 

   한국어의 경우 형태소분석해서 명사,용언 정도만 추출해서 사용할 수 있다. 

   또한, 특정 패턴이나 URL의 포함 여부등도 feature로 추가할 수 있다. 

   문제를 해결하기 위해 도움이 되는 사전 정보가 있는 경우, 그 정보에 맞춰서 

   feature를 생성하면 된다. 

   naive bayesian은 기본적으로 feature간 독립적이라는 가정으로 적용하는데, 

   '검색엔진'을 형태소분석하면 '검색','엔진'으로 분리되어 각각 feature가 되어 

   연속적인 정보가 중요한 문제에서는 정확률이 떨어지는 요인이 될 수 있다. 

   이런 경우 복합명사 bigram 등을 새로운 feature로 추가해볼수도 있다. 

   물론, feature space가 커지면 계산량이 많아지는 문제를 감수해야한다. 

   개체명인식의 경우라면 '이름'의 주변 문맥에서 태그, 조사, 복합명사 포함유무, 거리정보 등이 

   새로운 feature가 될 수 있겠다. 


   전체 학습데이터에 속하는 모든 문서 D에 대해서 feature vocabulary 혹은  

   feature set을 먼저 만들어야한다. (size = V)

   이것은 검색엔진에 검색문서집합을 넣고 색인하면 나오는 lexicon과 같은 개념이다. 

   

3. 학습데이터를 feature vector set으로 변환

   f_generator(d)가 만들어 졌다면, 이를 train set T(i)에 적용한다. 

   그러면 각각의 문서에 대해서 생성된 feature vector가 쌓여진 형태의 매트릭스가 만들어진다. 


             f(1)  f(2)  f(3)   ....   f(j) ....

   ----------------------------------------

   d(1,1)  1     0     1              1

   d(1,2)  0     1     0              1

   ...

   d(1,k)  1     1      1              0

   ...

   d(2,1)  0     0      1              0

   d(2,2)  1     0      0              0

   ...

   d(2,k)  0     0       0              1

   ...

    

   사실 feature가 keyword로 표현된다면 굳이 이렇게 만들 필요없이, keyword 자체를 써도 상관없다. 

 

   d(1,1)  w1   w3 ... wj ...

   d(1,2)  w2   wj  ...

   ...

   d(1,k)  w1   w2   w3 ...

   ...

   d(2,1)  w3 ....

   d(2,2)  w1 ....

   ...

   d(2,k)  wj ...

   ...

 

  feature vector set을 시스템 내부 자료구조로 표현하는 방법은 여러가지가 있다. 

  간단한 구조체를 써서 메모리에 올리거나, 검색엔진으로 색인하거나 아니면 하둡에 있는 그대로 저장하거나 

  하는 방법 등이다. 

  심플하게 테스트해볼때는 python, perl같은 언어로 만든 스크립트로 처리해도 되지만

  학습데이터의 양이 늘어나면 메모리에 전체 feature vector set이 올라가지 않는다. 

  feature vector set을 그냥 파일로 쓰고 이것을 읽어들이면서 필요한 확률정보를 계산하는 방법도 있다. 


4. feature vector set에서 class probability p(c), feature probability p(f|c) 계산

  1) 각각의 class c(i)에 대해서 p(c(i))를 계산

      이것은 심플한다. feature vector set에서 class c(i)의 비율을 계산하면된다. 

      전체 문서의 수가 |D|라고 하자. 

      |D| = sum { |d(i)| }  for all i, |d(i)| is the number of document in class c(i)

      p(c(i)) = d(i) / |D|


      feature vector set을 파일에 썼다면 한번 읽는 과정으로 계산이 가능하다. 


  2) 각각의 f(j)에 대해서 p( f(j) | c(i) )를 계산


      이 계산이 전체 학습 과정의 대부분을 차지한다. 


      p( f(j) | c(i) ) = n( f(j), c(i) ) / S

      S = sum {  n( f(j), c(i) ) } for all j


      즉, class c(i)로 태깅된 문서집합에 나타나는 feature f(j)의 빈도수를 

      모든 f에 대해서 구한 다음, 그 비율을 계산하면 된다. 


      class c(i)에 있는 feature f(j)의 빈도수를 어떻게 계산하면 될까? 


      이것은 전통적인 inverted index 방식으로 계산이 가능하다. 

      f(j)를 색인텀으로 보고, f(j)를 가지고 있는 문서를 아래와 같이 표현한다고 하자. 

    

      f(j) : doc1(10, 0), doc2(3, 1), doc3(1, 0), ...., docn(100, 1)


      * docn(x,y)의 괄호 안 숫자는  

          x = 해당 문서 내부에 있는 f(j)의 빈도수이다.   

          y = 해당 문서의 class 번호


      이러한 상태에서 n( f(j), c(1) )은 class 번호가 1번인 문서의 term frequency를 모두 

      합해서 계산할 수 있다. 

      만약, 하나의 문서 내부에 있는 term frequency가 큰 의미가 없다면

      전부 1로 만들수도 있는데, 이렇게 되면 결국 

      n( f(j), c(1) )은 f(j)로 검색한 검색 건수 중에서 class가 1인 문서의 갯수가 된다. 

      (document frequency)


      따라서, 모든 f(j)에 대해서 위 과정을 반복해서 n( f(j), c(i) )를 계산하고 그 비율을 

      구하면 feature probability를 계산할 수 있다. 

      계산 과정이 끝나면 n( f(j), c(i) ) 확률값이 정확히 (feature의 갯수) * (class의 갯수)만큼

      나온다. 

      (feature의 갯수는 검색엔진을 이용할 경우 lexicon의 사이즈라고 할 수 있다) 


      모든 feature에 대해서 반복하기 때문에 실제 걸리는 시간은 대략 아래와 같다. 

   

      (inverted index를 만드는 시간) + (feature의 갯수)*(class의 갯수)*(검색시간) 


5. 계산된 확률 사전을 저장 

   위에서 계산된 확률 사전 class probability p(c), feature probability p(f|c)를 어딘가에 저장한다. 

   데이터베이스도 좋고 다른 자료구조도 상관없다. 


   위에서 확률 계산할 때, 분자가 0인 경우 확률이 0이 되버리는 문제가 생기는데, 


   p( f(j) | c(i) ) = n( f(j), c(i) ) / S

   S = sum {  n( f(j), c(i) ) } for all j


   이를 보정하기 위해서 보통 Laplace smoothing 기법을 사용한다. (Laplacian smoothing과는 다르다)
   방법은 간단하게 1을 더하는 방법으로 additive smoothing 기법중의 하나이다. 

   p( f(j) | c(i) ) = { n( f(j), c(i) ) + 1 } / S

   S = sum {  n( f(j), c(i) ) + 1 } for all j


   각각의 class c(i)에 대해서 사실 f(j)는 듬성듬성 sparse하게 0인 경우가 많을 것이다. 

   Laplace smoothing 기법을 사용하면 0이 아니라 매우 작은 확률값들로 채워지게 되는데

   이 확률값들을 미리 계산해두고 사용하는 방법과

   0이면 확률값을 저장해두지 않고, 차후 새로운 문서에 대한 확률 계산을 할 때, 

   p( f(j) | c(i) )에 대한 확률값이 없으면 매우 작은 값을 일괄적으로 할당해버리는 트릭도 있다. 

   메모리 사이즈를 줄이는 방법중의 하나다. 


   또한, feature vector의 크기는 학습데이터가 많으면 많을수록 커지게 되서 메모리를 크게 
   잡아먹게된다. 분류 성능을 어느정도 포기하고 메모리 사이즈를 줄이기 위해서 
   feature selection 기법을 사용 할 수 있다. 
   (노이즈가 섞여진 부분을 제거하는 방법이기도 해서 분류 성능은 오히려 오를 수도 있다)

   [기법 참고] http://2010.telfor.rs/files/radovi/TELFOR2010_10_13.pdf
   * threshold 0.1 이상의 feature들만 사용하였다. 
   * Information Gain, Gain Ratio, Symmetrical Uncertainty, Chi-Squared, one-R, Relief-F 등을 사용

6. 학습 데이터에 없는 새로운 문서가 들어왔을 때 class 판단

   어떤 새로운 문서 d가 들어왔을 때, 이 문서가 어떤 class에 속할 가능성이 높은지 판단하는 수식은

   아래와 같다. 


   1) 일단 feature vector 생성기에 넣어서 feature vector를 만든다

   

       F = f_generator(d)


   2) 각각의 class c(i)에 대해서 아래 확률을 계산


       p(c(i) | F) = p( c(i) ) * product{ p( f(j) | c(i) ) } for all j

      

       확률값은 0과 1 사이의 값이므로 곱하게 되면 계속 작아진다. 따라서, log값을 취해서

       덧셈으로 바꾸자. 

 

       p(c(i) | F) = log(p( c(i) )) + sum{ log(p( f(j) | c(i) )) } for all j


   3) 위에서 계산한 확률 p(c(i) | F) 들 중에서 가장 큰 값을 갖는 c(i)를 선택한다. 


   학습된 확률사전이 너무 커서 메모리에 올라가지 않는 경우도 생긴다. 

   이때는 조금 느리더라도 BTREE로 저장해서 탐색하거나 아니면 확률사전 자체를 

   여러조각으로 나누는 방법도 있다. 

   feature vector의 크기가 V라면,  


   1부터 100번까지에 해당하는 확률사전을 1

   101부터 200번까지에 해당하는 확률사전을 2

   ...

   V-99부터 V까지 해당하는 확률사전을 m

    

   이렇게 두고, 어떤 새로운 문서 d가 들어 왔을 때


    F = f_generator(d)


    이것도 역시 m조각해서 각각의 p(c(i) | F(m))을 구한다. 

    각각의 F(m)에 대해서 c(i)들은 다르게 나올 수 있는데

    이것들에 대해서 voting해서 가장 많은 수가 나온 c(i)를 선택하는 방식이다. 


7. 하둡을 이용한 feature probability p( f(j) | c(i) ) 계산

    앞에서 inverted index를 구해서 아래와 같은 결과를 얻는 다고 언급했었는데, 

    

    f(j) : doc1(10, 0), doc2(3, 1), doc3(1, 0), ...., docn(100, 1)

      

    이 과정을 하둡의 map&reduce를 이용해서 구현해볼수도 있다. 


    일단 HDFS에는 feature vector set이 저장되어 있다고 하자. 

    또한, lexicon에 해당하는 feature set도 있다고 하자. 

    ( lexicon은 HDFS를 한번 스캔하면 구할 수 있다)

    

    1) map

       key를 f(j)로 하고 value를 docn(tf, class(i))로 하는 출력을 생성 

     

       doc1에 대해서 


       f(1) : doc1(10, 0)

       f(2) : doc1(1, 0)

       ...

       f(j)  : doc1(1, 0)

       ...


       docn에 대해서 


       f(1) : docn(1, 1)

       f(2) : docn(1, 1)

       ...

       f(j)  : docn(4, 1)

       ...

    

    2) reduce

       key값이 f(j)를 기준으로 docn(tf, class(i)) 리스트가 출력됨


    이제 4의 2)번에 언급한 과정을 그대로 진행하면 p( f(j) | c(i) )를 계산할 수 있다. 


8.  속성 가중치가 부여된 Naive Bayesian 

    베이지안 분류기는 기본적으로 모든 속성들이 독립적이라고 가정하고 계산한다.

    앞에서 bigram을 사용하거나 기타 dependency가 있는 부분을 묶어서 새로운 속성으로

    추가하는 방법에 대해서 언급했었는데, 이러한 방법 말고 속성별로 다른 가중치를 부여하는 

    방식도 있다. 

    

    예를 들어서, 일반적인 형태소분석 결과에서 나온 feature보다는 문서 자체가 가지고 있는

    이미지나 특정 URL 정보 혹은 구조적 정보가 더 스팸문서를 판단하는데 도움이 될 수도 있다. 

    그런데, 이런 feature들을 일괄적으로 같은 가중치로 처리한다면 문제의 소지가 있다. 


    물론, 아주 확실한 feature라고 판단되면 굳이 베이지안 분류기까지 올것도 없이 

    규칙으로 처리해버리면 된다. 

    하지만, 규칙으로 처리하기에는 조금 애매해고, 다른 일반적인 feature들과 동일한 가중치를 

    부여하기에는 아까운 feature들이 있을 경우도 있기 때문에 

    가중치 부여 방식은 유용하다고 할 수 있다. 


    가중치 부여 방법은 아래와 같이 두가지가 있다. 


    1) 학습 단계에서 feature probability p( f(j) | c(i) ) 자체에 가중치를 추가하는 방법


       각각의 f(j)에 대해서 별도로 관리하는(이미 결정된) 가중치 weight(j)가 있다고 하자. 


       여기서 weight(j)는 1보다 같거나 큰 양의 실수값(대부분 1이다)


       p( f(j) | c(i) ) = { n( f(j), c(i) ) + 1 } / S

       S = sum {  n( f(j), c(i) ) + 1 } for all j


       그러면, 이 수식은 가중치를 부여해서 아래와 같이 바뀐다. 


       p( f(j) | c(i) ) = { { n( f(j), c(i) ) + 1} / S } * weight(j)

       S = sum {  n( f(j), c(i) ) + 1 } for all j


       이렇게 계산된 확률값 p( f(j) | c(i) ) 값은 그 자체로 가중치를 포함하고 있으므로


       분류 단계에서는 그냥 사용하면 된다. 

       시스템 구현 및 관리 측면에서 보면, 분류 단계에서 가지고 있어야할 확률사전은  

       class probability p( c(i) )와 feature probability p( f(j) | c(i) ) 뿐이어서

       조금 더 심플하다. 


    2) 분류 단계에서 p( c(i) | F )를 계산 할 때, 가중치를 부여하는 방법

       학습단계에서는 기존과 똑같은 방식으로 학습하고, 

       분류 단계에서는  아래와 같이 계산한다. 

       

       p(c(i) | F) = p( c(i) ) * product{ p( f(j) | c(i) )^weight(j) } for all j


       p(c(i) | F) = log(p( c(i) )) + sum{ weight(j) * log(p( f(j) | c(i) )) } for all j


       여기서 weight(j)는 1보다 같거나 큰 양의 실수값(대부분 1이다)


       기존의 학습 시스템을 바꾸지 않고, 분류 단계에서만 weight(j) vector를 추가적으로 

       활용해서 사용하는 방식이다. 


    가중치 weight(j)를 어떻게 계산하는 것이 좋을지는 앞에서 feature selection을 언급했었는데

    여기서 나오는 measure를 그대로 사용하는 방법도 있다. 

    예를 들어서, mutual information을 사용할 경우, 해당하는 MI값 자체를 해당 feature의 

    가중치로 보는 방식이다. 


9. 기타 

   스팸 필터링을 할 경우, 한 문서에서 여러번 나오는 단어에 대해서 어떻게 고려할 것인가

   의문의 들 때가 있다. 

   feature probability를 계산할 때는 기본적으로 term frequency를 사용하게 되는데, 

   이 term frequency는 문서별이 아니라 전체 class에서의 term frequency라서 그 의미가 다르다. 

   

   아래 확률값을 계산할 때, f(j)가 반복적으로 나오는 경우라고 생각하면 된다. 


   p(c(i) | F) = log(p( c(i) )) + sum{ weight(j) * log(p( f(j) | c(i) )) } for all j


   f(j)가 반복적으로 나온다고 해서 수식에서 반복 계산하는 것이 과연 합당한가? 


   학습 자체를 그런 고려를 하지 않고 계산했기 때문에 반복 계산하면 안된다. 


   다만, 학습할 때나 분류할 때, f(j)가 반복적으로 나오는 경우에 대해서

   또 하나의  f(j+1) feature를 만드는 경우라면 어떨까? 


   이것은 마치 베이지안의 독립가정의 약점을 보완하기 위해서 bigram을 사용하는 것과

   비슷하게 반복적으로 나타나는 경우 자체를 feature로 설정해주는 것과 같다. 


   이런식으로 특정 반복 패턴을 feature의 하나로 설정해서 베이지안을 이용할수도 있을 것 같다. 





맨위로
통합 검색어 입력폼