Naive Bayes Classifier

1. 왜 Naive Bayes Classifier인가?

먼저 베이즈 분류기(bayes Classifier)는 베이즈 이론(bayes theorem)에 기반한다. 분류 알고리즘의 성능 비교를 연구하는 학자들은 의사결정나무나 신경망과 비슷한 성능을 가지느 단순 베이즈 분류기(Naive Bayes Classifier)간단한 베이즈 분류기를 발견하게 된다.

단순 베이즈 분류기는 주어진 클래스의 한 속성 값이 다른 속성의 값과 상호독립임을 가정한다. 이 가정을 클래스 조건부 독립(class conditional independence)라고 한다. 이 가정은 계산과정을 간단하게 하므로 그런의미에서 단순(naive) 하다고 한다.

(클래스 조건부 독립에 대해서는 밑에서 설명을 참고)

2. 베이즈 정리(Bayes theorem)

를 데이터 투플, 를 데이터 투플 가 임의의 특정 클래스 에 속한다는 것과 같은 어떤 가설이라고 하자. 분류 문제를 해결하기 위해, 관찰된 데이터 투플 가 주어질 때, 가설 가 성립할 확률 를 구해야 한다. 다시말해, 의 속성서술(attribute description)을 알고 있을 때, 투플 가 클래스 에 속 할 확률을 찾고자 한다.

• 는 에 대한 의 조건부 확률, 즉 사후확률(Posterior probability)이다.
• 는 의 사전확률(Prior probability)이다.

예를 들어, 가 35세이고 수입 $40,000인 고객이라고 하자. 가 고객이 컴퓨터를 살 것이라는 가설이라고 한다면 는 그 고객의 나이와 수입을 알고 있는 상태에서 고객 가 컴퓨터를 살 확률을 나타낸다. 는 고객의 나이나 수입을 모르는 임의의 어떤 고객이 컴퓨터를 살 확률이다.

• 사후확률 는 와 독립인 사전확률 보다 더 많은 정보(예: 고객정보)에 근거를 두고 있다.
• 는 의 조건하에 의 사후확률이다. 즉, 어떤 고객이 컴퓨터를 살 것이라고 알고 있을 때, 그 고객 가 35세이고 수입이 $40,000일 확률을 나타낸다.
• 는 X에 대한 사전확률이다. 위 예에서, 고객 집합에 있는 한 고객이 35세이고 수입이 $40,000일 확률이다.

위의 , , 는 주어진 데이터로 부터 추정할 수 있다.

베이즈 정리(Bayes theorem)는 , , 로부터 사후확률 을 계산하는 방법을 제공한다.

$$P(H|X)=\frac { P(X|H)P(H) }{ P(X) } \qquad \qquad \qquad (1)$$

3. Naive Bayes Classifier

Naive Bayes Classifier는 다음과 같이 수행된다.

1. 를 투플들과 클래스 레이블로 이루어진 Training Set이라고 하자. 각 데이터 투플은 개의 속성 으로 구성되는 투플에대한 -차원의 속성벡터 로 표현된다.
   
   
2. 개의 클래스 이 있다고 하자. 어떤 투플 가 주어지면, 분류기는 사후확률이 최대가되는 클래스에 를 분류할 것이다. 즉, Naive Bayes Classifier는 다음과 같은 필요 충분 조건을 만족할 때, 투플 가 클래스 에 속한다고 예측한다.

   $$P({ C }_{ i }|X)>P({ C }_{ j }|X)\quad for\quad 1\le j\le m,\quad j\neq i$$

   따라서 를 최대화한다. 가 최대인 클래스 를 최대사후가설(Maximum posteriori hypothesis)라고 한다. 베이즈 정리(식 1)에 의하면 다음 식이 성립한다.

$$P({ C }_{ i }|X)=\frac { P(X|{ C }_{ i })P({ C }_{ i }) }{ P(X) } \qquad \qquad \qquad (2)$$



3. 가 모든 클래스에서 상수 이므로 만을 최대화 하면 된다. 클래스 사전확률이 알려져 있지 않은 경우는 일반적으로 모든 클래스 확률은 동일하다고 가정한다. 즉, 로 하여 를 최대화한다. 그렇지 않은 경우는 를 최대화한다. 클래스 사전확률은 에 의해 추정하며, 여기서 는 에 있는 클래스 의 Training 투플의 수이다.
   
   

4. 많은 속성을 가진 데이터 집합이 주어지면 를 계산하기 위해서 매우 큰 계산 비용이 소요된다. 각각의 속성 k개에 대해 값이 2개가 있는 경우 개의 계산이 필요하다.의 계산비용을 감소하기 위해서 클래스 조건부 독립성(class conditional independence)과 같은 단순한 가정을 세운다. 클래스 조건부 독립성이란 가정은 한 속성값은 다른 속성값들과 조건부 독립이라는 것으로, 투플의 클래스 레이블이 주어지면 속성들 간에느 어떠한 종속관계가 없다는 것을 의미한다. 따라서 다음 식이 성립한다.

   $$P(X|{ C }_{ i })\quad =\quad \prod _{ k=1 }^{ n }{ P({ x }_{ k }|{ C }_{ i }) } \\ \qquad \qquad =\quad P({ x }_{ 1 }|{ C }_{ i })\times P({ x }_{ 2 }|{ C }_{ i })\times ...\times P({ x }_{ n }|{ C }_{ i })\qquad \qquad (3)$$

   확률는 Training Set으로 부터 추정한다.


(a) 가 범주형이면, 는 에 대해 값 를 가지는 클래스 의 투플의 수를 로 나누어 계산한다.

(b) 가 연속형이면, 통상 속성이 평균이 이고 표준편차가 인 정규분포(가우시안 분포)를 갖는다고 가정한다.

$$g(x,\mu ,\sigma )=\frac { 1 }{ \sqrt { 2\pi  } \sigma  } { e }^{ -\frac { (x-\mu )^{ 2 } }{ 2{ \sigma  }^{ 2 } }  }\qquad \qquad (4)$$

따라서

$$P({ x }_{ k }|{ C }_{ i })\quad =\quad g({ x }_{ k },{ \mu  }_{ { C }_{ i } },{ \sigma  }_{ { C }_{ i } })\qquad \qquad (5)$$




5. 의 클래스 레이블을 예측하기 위해서, 를 각 클래스 에 대해서 계산한다. 다음과 같은 필요충분 조건이 만족하면 투플 의 클래스를 라고 예측한다.

   $$P(X|{ C }_{ i })P({ C }_{ i })>P(X|{ C }_{ j })P({ C }_{ j })\qquad for\quad 1\le j \le m,\quad j\neq i\qquad (6)$$

4. Naive Bayes Classifier 예제

아래의 표에 나와있는 Training 데이터에 대해 Naive Bayes classifier를 적용하여 클래스 레이블을 예측하고자 한다.

데이터 투플은 age, income, student, credit_rating 의 속성으로 설명된다. 클래스 레이블 속성은 buys-computer의 두 가지 값(yes, no)로 구별된다. 은  buys-computer="yes" , 은 buys-computer="no" 이다. 다음 투플 에 대해 분류를 해보자.

$$ X = (age = youth, income = medium, student = yes, credit_rating = fair) $$

각각의 i = 1, 2에 대해 를 최대화해야 한다. 는 각 클래스에 대한 사전확률이며 Training data를 이용하여 계산한다.

각각의 i = 1,2에 대해 를 계산하기 위해 다음의 조건부 확률을 계산한다.

$$P(age=youth|buys\, computer=yes)=2/9=0.222\\ P(age=youth|buys\, computer=no)=3/5=0.600\\ P(income=medium|buys\, computer=yes)=4/9=0.444\\ P(income=medium|buys\, computer=no)=2/5=0.400\\ P(student=yes|buys\, computer=yes)=6/9=0.667\\ P(student=yes|buys\, computer=no)=1/5=0.200\\ P(credit\, rating=fair|buys\, computer=yes)=6/9=0.667\\ P(credit\, rating=fair|buys\, computer=no)=2/5=0.400$$

위의 확률들을 이용하여가 buys-computer="yes" ,  buys-computer="no" 일 확률을 다음과 같이 계산한다.

위와 같은 방법으로

를 최대화하는 를 찾기 위하여 다음을 계산한다.

따라서 Naive Bayes Classifier에 의해 투플 는 buys_computer="yes" 로 예측된다. 

5. 라플라시안 수정(Laplacian correction)

만약에 어떤 속성값의 확률이 0일 경우, 식 3에서 의 계산 값은 결국 0이 되어 버린다. 그렇게 되면 자동으로 또한 0이 된다. 이렇게 되면 가 에 분류될 가능성이 높은 경우에도 예측확률이 0이 되버리는 셈이다.

이러한 문제를 피하고자 라플라시안 수정(Laplacian correction) 혹은 라플라스 추정량(Laplace estimator)이란 것을 하게된다. 라플라시안 수정은 Training 데이터 집합 가 각 개수에 1을 더해도 추정된 확률에 거의 차이가 없을 만큼 매우 크다고 가정하는 것이다. 

예를 들어 buys_computer="yes" 에 대하여 1,000개의 투플이 있고, 그 중 income = low인 투플이 0개, income = medium인 투플이 990개, income = high인 투플이 10개있다고 가정하자. 이러한 사건들에 대한 확률은 라플라시안 수정을 취하지 않으면 각각 0, 0.990(=990/1000), 0.010(10/1000)이 된다. 여기에 각각 1을 더하는 라플라스 추정량을 적용하면 다음과 같이 계산된다.