나이브 베이즈 분류기 - Naive Bayes Classifier

강남의 어느 검색 솔루션 기업에서 인턴한지 어연 4주차가 지나간다. 중간 지점을 지나가면서 한 것을 정리할 겸 나이브베이즈 문서 분류기 구현과 이론에 대해서 정리해 보려고 한다. 최대한 쉽게!!

나이브 베이즈 분류기는 베이즈 정리(Bayes’ theorem)을 사용한 분류 알고리즘이다. 이것은 전통적으로 텍스트 분류를 하는 분류기로 인공지능의 기능을 기학적으로 올려준 인공 신경망 알고리즘은 아니지만 머신 러닝의 중요한 알고리즘 중 하나로 꽤 좋은 성능을 보인다. 나이브 베이즈 분류기에서 사용하는 베이즈 정리는 무엇일까?

베이즈의 정리(Bayes’ theorem)를 사용한 분류 기법

베이즈 정리는 조건부 확률을 계산하는 방법 중 하나이다. 다음과 같이 표현할 수 있다.

P(A): 사전확률(Prior). 사건 B가 발생하기 전 A가 가지고 있던 확률
P(B): 정규화 상수(normalizing constant). B가 일어날 확률
P(B | A): 가능도(likelihood). A가 발생한 경우 B가 일어날 확률
P(A | B): 사후확률(Posterior). B가 발생한 후 A가 일어날 확률

이 때 P(A | B)를 구하려면, 다음과 같은 수식을 사용한다.

$$ P(A|B) = \frac {P(B|A)P(A)} {P(B)} $$

주로 나이브 베이즈 분류기법을 설명할 때 스팸 메일 분류기를 예를 들어서 설명한다.

나이브 베이즈를 활용한 스팸 분류기

어떤 문서 D에 대하여 해당 문서가 스팸(S)클래스에 속하는지 일반(!S)클래스에 속하는지 분류할 때 나이브 베이즈 분류 알고리즘을 사용한다고 하자. 그리고 이미 각기 다른 단어들에 대해서 해당 단어가 스팸일 확률과 일반일 확률에 대한 데이터가 이미 확보되어 있다고 가정한다. 한번 기호로 살펴보자. 우리가 가지고 있는 데이터는 다음 두개와 같다. 다음은 각각 “Sale이라는 단어는 60%의 확률로 스팸메일에서 발견되고, 30%의 확률로 일반메일에 발견된다.”라는 정보를 가지고 있는 것이다.

$$ P(‘Sale’|S), P(‘Sale’|!S) $$

데이터를 수 만개의 단어들에 대한 위의 데이터를 활용해서 결국 풀고 싶은 문제는 $P(S|D)$와 $P(!S|D)$이다. 다음 두 확률을 구한 다음 확률이 더 큰 클래스에 해당 문서가 속한다고 결론을 내린다. $P(S|D)$는 문서 $D$가 주어졌다는 가정하에 해당 문서가 스팸일 조건부 확률을 나타낸다. 반대로 $P(!S|D)$는 문서 $D$가 주어졌다는 가정하에 해당 문서가 스팸이 아닐 조건부 확률을 나타낸다. 해당 문서를 어떤 클래스에 속하는지 분류하려면 먼저 문서에서 feature를 추출해야 한다. 추출된 feature들이 어떤 규칙에 의한 키워드 단어들이라고 할 때, 베이즈 정리는 특징벡터$x=(x1, x2, …, xn)$의 요소들이 모두 조건부 독립이라는 가정을 한다. 즉, 각 단어들이 서로 미치는 확률에 있어서 연관이 없다고 가정하는 것이다. (이 부분에서 ‘Naive(순진한) ‘라는 이름이 붙는다. 실제로는 모두 독립적이지 않고 동등하지 않은데 이렇게 간주해버리는 순진함을 가지고 있다.) 이때 해당 특징벡터 $x$에 대한 클래스 $S$에 속할 확률은 다음과 같다.

$$ P(S|x1,x2,…,xn)=\frac {P(x1,x2,…,xn)P(S)}{P(x1,x2,…,xn)} $$

앞에서 언급했듯이 각 feature의 요소들은 조건부 독립이기 때문에 다음과 같이 바꿔 쓸 수 있다.

$$ P(S|x1,x2,…,xn)=\frac {P(x1|S)P(x2|S)…P(xn|S)P(S)}{P(x1)P(x2)…P(xn)} $$

위와 같이 수식을 사용하면 문서를 특정 클래스들로 분류하기 위해서는 다음만 알면 된다. 1) 문서로부터 특징벡터를 추출하는 방법 2)기존에 확보된 데이터로부터 $P(S|x)$와 $P(!S|x)$를 계산하는 방법 3)각 클래스의 비율인 사전확률 $P(S),P(!S)$. 해당 문제를 해결하기 위해 주어진 문서로 부터 판단에 사용할 특징feature를 추출해야 하는데 이때 어떤 확률분포를 사용하는지에 따라 특징벡터가 달라지게 된다.

나이브 베이즈 분류기 3종류

나이브 베이즈 분류기에는 다음과 같이 3 종류가 있다. 세가지를 모두 다루지는 않고 인턴 기간동안 구현한 Bernoulli naive bayes classifier에 대해서 주로 다룰 것이다. 다만 3종류는 어떠한 것이 있고 각각의 특징과 다른점들에 대해서 간단히 설명하고 넘어가보자.

Gaussian naive bayes classifier: 설명변수가 연속형인 경우
- 연속적인 데이터에 적용 가능
Multinomial naive bayes classifier: 설명변수가 범주형인 경우
- 카운트 데이터(횟수)에 적용 가능
Bernoulli naive bayes classifier: 설명변수가 이분형인 경우
- 이진 데이터에 적용 가능.

Gaussian naive bayes는 주로 매우 고차원적인 데이터 세트를 다룰 때 사용된다. 나머지 두 베이즈 모델인 다항분포(Multinomial)과 베르누이(Bernoulli)는 보다 텍스트와 같은 데이터에 사용된다. 인턴하는 회사에서 요구한 업무는 문서에 대한 분류기이니 후자가 더 적합하다. 그 중, 내가 맡은 업무는 베르누이를 사용한 나이브 베이즈 문서 분류기이다.

Bernoulli Naive Bayes 분류기

일부 코드를 제시하면서 구현 로직 설명을 하겠지만 인턴 회사의 코드이므로 모든 공개가 어렵다. 또한 여기서 참고할 점은 구현 언어가 회사 내에서 개발한 새로운 언어라는 것이다. 머신러닝을 사용한 인공지능 회사인 만큼 자체적으로 로직을 짜고 데이터를 처리하기에 더 적합한 언어를 포팅하여 사용하고 있다. 따라서 큰 로직만 참고하는 것을 추천한다.

먼저 텍스트 분류에 크게 사용되는 베르누이 확률 분포 모형과 다항분포 모형을 비교하며 간단히 어떤 차이가 있는지 살펴보자.

먼저 다항분포는 표본벡터 $x$가 있다고 가정했을 때, 이것을 $D$면을 가진 주사위를 $y$번 던진 결과라고 본다. 즉, $x=[1, 4, 0, 5]$가 있을 때, 다음 표본벡터는 4면체 주사위를 10번 던져서 1인 면이 1번, 2인 면이 4번, 4인 면이 5번 나온 결과이다. $K$개의 class가 있다면 $D$개 면을 가진 주사위 $K$개가 있다고 보고, 주사위를 던진 결과로부터 $1, … ,K$중 어떤 주사위를 던졌는지 찾아내는 것이라고 이해한다. 문서 내에 특정 단어가 몇번 등장하는지에 대한 횟수를 모형화 할 수 있다.

베르누이분포는 $x$의 원소가 0 또는 1 값만을 가질 수 있다. 위와 다르게 독립변수는 $D$개의 독립적인 확률변수를 가지고 있는, 동전으로 구성된 동전 세트로 표현할 수 있다. 각각의 값은 0 또는 1이다. $K$개의 클래스를 가지고 있다고 할 때, 전체 $D * K$의 조합의 동전이 존재하며 같은 class에 속하는 D개의 동전이 하나의 동전 세트를 구성하고 이런 동전 세트가 $K$개 있다고 볼 수 있다. 즉 베르누이를 사용한 나이브 베이즈 모형은 동전 세트를 N번 던진 결과로부터 1, …, $K$ 중 어느 동전 세트를 던졌는지 찾아내는 것이다. 문서 내에 특정한 단어가 포함되어 있는지의 여부로 확률을 판단할 때 주로 사용한다.

feature_count: 각 class k에 대해 d번째 동전이 앞면이 나온 횟수 $N_d,_k$
feature_log_prob: 베르누이분포 모수의 로그값

$$ log\mu_k = (log\mu_1,_k,…,log\mu_D,_k) = (log\frac{N_1,_k}{N_k},…,log\frac{N_D,_k}{N_k}) $$

$N_k$는 class k에 대해서 동전을 던진 횟수이다.

다음 파이썬 코드를 잠깐 훑으며 베르누이 확률분포를 사용해 나이브베이즈 분류 확률을 구하는 과적을 살펴보자.

x = np.array([
[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 0, 1, 1],
[0, 1, 1, 0]])

y = np.array([0, 0, 0, 0, 1, 1, 1, 1, 1, 1]) //class 분류

클래스는 0과 1로 총 2개라고 본다. $x$는 확률변수를 가지고 있는 동전 세트로 볼 수 있고, $y$는 각 세트에 대한 클래스를 정의해 놓은 것이다. 처음 4개 세트는 class 0, 다음 6개 세트는 class 1이다.

각 클래스 $k$별, 독립변수 $d$별로 총 8개의 베르누이 확률변수의 모수를 구하면 다음과 같다. (각 클래스 별로 합치는 것)

array([[2, 4, 3, 1],
	   [2, 3, 5, 3]])

$[2, 4, 3, 1]$이 어떻게 나왔는지 간단하게 설명해보겠다. $x$의 첫번 째 4 세트가 class 0이므로 각각 첫번째 요소가 1인 횟수를 더하여서 2, 두번째 요소가 1인 횟수를 더하여서 4, … 이렇게 합친다.

이렇게 합쳐진 요소들에 대해서 각 클래스의 전체 개수로 나누어 주어야 한다. 위 예시의 경우 class 0의 전체 개수는 4이고 1의 전체 개수는 6이다. 결과는 다음과 같다.

array([[0.5,   1,   0.75,    0.25],
	   [0.333, 0.5, 0.83333, 0.5]])

여기서 이제 **스무딩(Smoothing)**을 해야한다. 표본 데이터의 수가 그렇지 않음에도 불구하고 0 또는 1이라는 극단적인 값이 나오게 된다. (현실에서 그런 확률은 거의 없다) 따라서 이런 현상을 방지하기 위해서 베르누이는 모수가 0.5인 가장 일반적인 경를 가정하여서 0이 나오는 경우와 1이 나오는 경우의 가장 표본 데이터를 추가하여 스무딩한다. 주로 smoothing은 가중치 $\alpha$의 값으로 스무딩을 조절한다. 이것을 ==라플라스 스무딩(Laplace smooting)== 또는 *==애드원(Add-One) 스무딩==*이라고 한다.

$$ \mu_d,_k = \frac {N_d,_k + \alpha} {N_k + 2\alpha} $$

위에서 스무딩 가중치 $\alpha$를 1.0을 주었을 때 결과 값은 다음과 같다. 확인해보면 1과 같은 극단적인 값이 없어졌음을 볼 수 있다.

array([[0.5,   0.833333, 0.66667, 0.33333],
	   [0.375, 0.5,      0.75,    0.5]])

예측을 하기 위해 $[0, 0, 1, 1]$ 을 입력하면 $array([0.0953 , 0.9046])$ 값이 나온다. 즉 3, 4번 키워드가 포함되어 있다면 class 1 일 확률이 90%라는 의미이다.

Implementation - 문서 분류기 구현

원리를 이해했다면 구현은 생각보다 간단하다. 물론 파이썬의 sklearn등의 모듈을 사용하면 나이브 베이즈와 각 확률분포에 대한 기능이 모두 구현되어 있다. 따라서 가져가 쓰기면 하면 된다. 여기서는 문서분류기에 해당 알고리즘을 모듈을 사용하지 않고 어떻게 구현해야 하는지를 다룰 것이다. 앞서 말했든 사내에서 쓰는 언어를 사용한 것이 때문에 코드구현은 플로우만 참고하는 것을 추천한다.

학습 Learn

Input: 텍스트, 분류 클래스

문서 키워드를 추출한다. 키워드 추출은 사용자마다 다른 기능이나 모듈을 가져와서 기준에 따라 추출할 수 있다.
중복 제거를 위해 추출된 키워드를 Set에 입력시킨다.
클래스 횟수가 저장되어 있는 자료구조에 해당 클래수 횟수를 1 증가시킨다.
해당 클래스의 해당 단어의 여부를 기록하기 위해 해당 자료구조에 1을 더한다.
전체 단어를 저장하는 자료구조에 단어를 추가한다.

위에서 설명한 베르누이 확률분포를 계산하기 위한 $N_d,_k$와 $N_k$를 계산하는 과정으로 이해하면된다. 다음은 해당을 특정 언어로 코딩한 일부분이다. 여기서 m_n_cls와 m_n_cls_word등의 자료구조는 hash이고 m_words는 set이다.

void BernoulliModel::learn(string text, string cls){
    list<string> tok;
    tok = extract_words(text.trim(), m_lang, m_charset;
    m_n_cls[cls] +=1;
                        
    set<string> word_set;
    string word;
    for word in tok {
        word_set.add(word);
    }                    
    
    for word in word_set {
        m_n_cls_word[cls+"_"+word] += 1;
        m_words.add(word);
    }                    
}

예측 Predict

Input: 예측할 테스트, Smoothing을 위한 $\alpha$

입력 텍스트에 대해서 키워드를 추출함
클래쓰 목록을 가져와서 각 클래스마다 다음을 반복함(해당 클래스의 Score를 구함)
분모에 총 클래스 횟수와 smoothing값을 더함.
추출된 각 키워드에 대해서 확률분포값과 smoothing 값을 더하여서 위의 분모로 나눈 log를 계산함(위에 베르누이 확률 계산 공식을 참고)
각 클래스의 점수를 누적하여 예측함.

BernoulliModel::predict(string fe, string lang, string charset, hash<string,double>& score_hash, double alpha){
	list<string> tok;
	list<string> cls_list;
	double denom;
	double score;
	string cls;
	string t;
	
	tok = extract_word(fe.trim(), lang, charset);
	cls_list = m_n_cls.key();
	
	for cls in cls_list {
		socre = 0.0;
		denom = double(m_n_cls[cls]) + 2*alpha;
		for t in tok{
			score += log(m_n_cls_wor[cls+"_"+t]+alpha) / denom);
		}
		score_hash[cls] += score;
	}
}

다음을 예측해서 Score가 가장 높은 cls 소속임을 예측한다. 다항분포 모델이랑 비교하여 새로 구현한 베르누이 나이브 베이즈 문서 분류기의 성능을 테스트 해 보았을 때 81~~82% 정도의 정확성을 보이는 것을 확인했다. 다항분포는 84~~85%정도의 성능이었던 것을 고려해보면 확실히 정확한 횟수보다 여부만을 가지고 계산하는 베르누이 분류기의 성능이 다소 떨어지는 것을 확인할 수 있었다.

결과:

Bernoulli

[참고 자료]: https://nbviewer.jupyter.org/github/metamath1/ml-simple-works/blob/master/naive/naive.ipynb, https://wikidocs.net/22892, https://heung-bae-lee.github.io/2020/04/14/machine_learning_07/

베이즈의 정리(Bayes’ theorem)를 사용한 분류 기법
나이브 베이즈를 활용한 스팸 분류기
나이브 베이즈 분류기 3종류
Bernoulli Naive Bayes 분류기
Implementation - 문서 분류기 구현
- 학습 Learn
- 예측 Predict