나이브 베이즈 분류

기계 학습분야에서, **'나이브 베이즈 분류**(Naïve Bayes Classification)는 특성들 사이의 독립을 가정하는 베이즈 정리를 적용한 확률 분류기의 일종으로 1950년대 이후 광범위하게 연구되고 있다.

통계 및 컴퓨터 과학 문헌에서 , 나이브 베이즈는 **단순 베이즈**, **독립 베이즈**를 포함한 다양한 이름으로 알려져 있으며, 1960년대 초에 텍스트 검색 커뮤니티에 다른 이름으로 소개되기도 하였다.

나이브 베이즈 분류는 텍스트 분류에 사용됨으로써 문서를 여러 범주 (예: 스팸, 스포츠, 정치)중 하나로 판단하는 문제에 대한 대중적인 방법으로 남아있다.
또한, 자동 의료 진단 분야에서의 응용사례를 보면, 적절한 전처리를 하면 더 진보된 방법들 (예: 서포트 벡터 머신 (Support Vector Machine))과도 충분한 경쟁력을 보임을 알 수 있다.

## 개요
나이브 베이즈는 분류기를 만들 수 있는 간단한 기술로써 단일 알고리즘을 통한 훈련이 아닌 일반적인 원칙에 근거한 여러 알고리즘들을 이용하여 훈련된다. 모든 나이브 베이즈 분류기는 공통적으로 모든 특성 값은 서로 독립임을 가정한다. 예를 들어, 특정 과일을 사과로 분류 가능하게 하는 특성들 (둥글다, 빨갛다, 지름 10cm)은 나이브 베이즈 분류기에서 특성들 사이에서 발생할 수 있는 연관성이 없음을 가정하고 각각의 특성들이 특정 과일이 사과일 확률에 독립적으로 기여 하는 것으로 간주한다.

나이브 베이즈의 장점은 다음과 같다.
첫째, 일부의 확률 모델에서 나이브 베이즈 분류는 지도 학습 (Supervised Learning) 환경에서 매우 효율적으로 훈련 될 수 있다. 많은 실제 응용에서, 나이브 베이즈 모델의 파라미터 추정은 최대우도방법 (Maximum Likelihood Estimation (MLE))을 사용하며, 베이즈 확률론이나 베이지안 방법들은 이용하지 않고도 훈련이 가능하다.
둘째, 분류에 필요한 파라미터를 추정하기 위한 트레이닝 데이터의 양이 매우 적다는 것이다.
셋째, 간단한 디자인과 단순한 가정에도 불구하고, 나이브 베이즈 분류는 많은 복잡한 실제 상황에서 잘 작동한다. 2004년의 한 분석은 나이브 베이즈 분류의 이러한 능력에 명확한 이론적인 이유가 있음을 보여 주었다. 또한 2006년에는 다른 분류 알고리즘과의 포괄적인 비교를 통하여 베이지안 분류는 부스트 트리 또는 랜덤 포레스트와 같은 다른 접근 방식을 넘어섰다는 것이 밝혀졌다.

## 확률 모델

나이브 베이즈는 조건부 확률 모델이다. 분류될 인스턴스들은 N 개의 특성 (독립변수)을 나타내는 벡터 \mathbf{x} = (x_1, \dots, x_n) 로 표현되며, 나이브 베이즈 분류기는 이 벡터를 이용하여 k개의 가능한 확률적 결과들 (클래스)을 다음과 같이 할당한다.
:p(C_k \vert x_1, \dots, x_n)\,

위의 공식은 특성 N의 수가 많은 경우나 하나의 특성이 많은 수의 값을 가질 수 있는 경우 확률 테이블에 베이지안 모델을 바로 적용하기 어려움이 있다.
그러므로, 위의 식은 베이즈 정리와 조건부 확률을 이용하여 다음과 같이 정리 가능하다.
:p(C_k \vert \mathbf{x}) = \frac{p(C_k) \ p(\mathbf{x} \vert C_k)}{p(\mathbf{x})}. \,

베이지안 확률 용어를 사용하여 위의 식은 다음과 같은 식으로도 표현 가능하다. (posterior : 사후 확률, prior : 사전확률, likelihood : 우도, evidence : 관찰값)
:\mbox{posterior} = \frac{\mbox{prior} \times \mbox{likelihood}}{\mbox{evidence}}. \,
실제로, 위 식에서 분자 부분만이 의미가 있다. 분모 부분의 경우에는 주어진 C 값에 의존하지 않고, 특성들의 값 F_i의 경우 분모의 값이 상수가 되도록 주어지기 때문이다. 분자 부분은 다음과 같은 결합확률 모델이다.

:p(C_k, x_1, \dots, x_n)\,

위의 식은 조건부 확률을 반복적으로 적용한 연쇄 법칙을 사용하여 다음 과 같이 다시 쓸 수 있다.
:
\begin{align}
p(C_k, x_1, \dots, x_n) & = p(C_k) \ p(x_1, \dots, x_n \vert C_k) \\
                        & = p(C_k) \ p(x_1 \vert C_k) \ p(x_2, \dots, x_n \vert C_k, x_1) \\
                        & = p(C_k) \ p(x_1 \vert C_k) \ p(x_2 \vert C_k, x_1) \ p(x_3, \dots, x_n \vert C_k, x_1, x_2) \\
                        & = p(C_k) \ p(x_1 \vert C_k) \ p(x_2 \vert C_k, x_1) \ \dots p(x_n \vert C_k, x_1, x_2, x_3, \dots, x_{n-1})
\end{align}


나이브 베이즈에서 조건부 독립성은 다음과 같이 표현될 수 있다 : 카테고리 종류 C 가 주어질 경우, 어떤 특성 F_i의 경우 모든 F_j (j\neq i)에 대해서 조건부 독립이다. 즉,

:p(x_i \vert C_k, x_j) = p(x_i \vert C_k)\,,
:p(x_i \vert C_k, x_j, x_k) = p(x_i \vert C_k)\,,
:p(x_i \vert C_k, x_j, x_k, x_l) = p(x_i \vert C_k)\,,

;
i \ne j,k,l에 대해 위식이 성립하게 된다. 결국, 이를 바탕으로 결합 모델은 다음과 같이 표현될 수 있다.
:
\begin{align}
p(C_k \vert x_1, \dots, x_n) & \varpropto p(C_k, x_1, \dots, x_n) \\
                             & \varpropto p(C_k) \ p(x_1 \vert C_k) \ p(x_2\vert C_k) \ p(x_3\vert C_k) \ \cdots \\
                             & \varpropto p(C_k) \prod_{i=1}^n p(x_i \vert C_k)\,.
\end{align}


위 식은 독립성 가정 하에서 클래스 변수 C의 조건부 분포는 :

:p(C_k \vert x_1, \dots, x_n) = \frac{1}{Z} p(C_k) \prod_{i=1}^n p(x_i \vert C_k)

여기서 Z = p(\mathbf{x})는 특성값들이 주어진 경우 상수가 되는, 즉 x_1, \dots, x_n 에만 의존하는 스케일링 팩터이다.

### 확률 모델로부터의 분류기 생성
지금까지의 논의는 독립 특성 모델, 즉 나이브 베이즈 확률 모델을 유도한다. 나이브 베이즈 분류는 이 확률 모델과 결정 규칙을 조합 한 것이다. 하나의 공통적인 규칙은 가장 가능성 높은 가설을 선택 하는 것이다. 이것은 사후 또는 MAP 결정 규칙의 최대치를 선택하는 것이다. 즉 나이브 베이즈 분류에서는 클래스 k, 즉  C_k에 대해서 다음 식을 통해 최대 확률을 갖는 클래스 k를 찾아낸다.

:\hat{y} = \underset{k \in \{1, \dots, K\}}{\operatorname{argmax}} \ p(C_k) \displaystyle\prod_{i=1}^n p(x_i \vert C_k).

## 모수추정과 이벤트 모델
클래스의 사전 확률은 클래스간의 동일확률을 가정하여 계산할 수 있고 (i.e., 사전 확률 = 1 / (클래스의 수)), 또한 트레이닝 셋(training set)으로부터 클래스의 확률의 추정치를 계산할 수 있다(i.e., (해당 클래스의 사전확률) = (해당 클래스의 샘플 수) / (샘플의 총 수)). 특성의 분포에 대한 모수들을 추정하기 위해서는, 트레이닝 셋의 특성들을 위한 비모수 모델이나 분포를 가정 또는 생성 해야한다.

특성의 분포에 대한 여러 가정들은 나이브 베이즈 분류 이벤트 모델이라고 불린다. 문서 분류에서 발생하는 것과 같은 이산적인 특성(스팸 필터링 포함)은 다항 분포와 베르누이 분포가 그 모델로 인기가 있다. 이러한 가정들로 인해 모델을 선택하는 데 있어서 혼동이 발생하는 경우도 종종 발생한다.

### 가우시안 나이브 베이즈
연속적인 값을 지닌 데이터를 처리 할때, 전형적으로 각 클래스의 연속적인 값들이 가우스 분포를 따른다고 가정한다. 예를 들어, 트레이닝 데이터가 연속적인 속성 x를 포함하는 것으로 가정하면, 먼저 클래스에 따라 데이터를 나눈 뒤에, 각 클래스에서 x의 평균과 분산을 계산한다. 클래스 *c*와 연관된 x 값의 평균을 \mu_c이라고 하고, 분산을 \sigma^2_c라고 하면, 주어진 클래스의 값들의 확률 분포가 M과 S로 매개변수화되어 정규분포식을 통해 계산될 수 있다. 즉,
:
p(x=v|c)=\frac{1}{\sqrt{2\pi\sigma^2_c}}\,e^{ -\frac{(v-\mu_c)^2}{2\sigma^2_c} }


연속적인 값을 처리하기 위한 다른 일반적인 기술은 특성 값들을 이산화하여 베르누이-분포화 된 새로운 셋을 얻기 위해 비닝을 사용하는 것이다. 일부 문헌은 이러한 셋에 단순한 베이스를 적용 할 필요가 있음을 시사하고 있지만, 이산화는 차별적인 정보들을 상실하게 할 수도 있음을 유의해야 한다.

### 다항분포 나이브 베이즈
다항 이벤트 모델에서는, 샘플(특성 벡터)들은 다항분포 (p_1, \dots, p_n)에 의해 생성된 어떤 이벤트의 빈도수를 나타낸다 (p_i는 해당 이벤트가 발생 할 확률이다). 특성벡터 \mathbf{x} = (x_1, \dots, x_n)는 빈도수를 나타내는 히스토그램으로 생각할 수 있다 (x_i는 특정 인스턴스에서 관찰된 이벤트의 수를 나타낸다). 이것은 하나의 문서에서 단어의 출현을 나타내는 이벤트를 가지고 문서 분류를 하는데 사용되는 이벤트 모델이다. 히스토그램 x를 관찰 할 우도는 다음 식으로 주어진다.

:
p(\mathbf{x} \vert C_k) = \frac{(\sum_i x_i)!}{\prod_i x_i !} \prod_i {p_{ki}}^{x_i}


다항 나이브 베이즈 분류는 로그 공간에서 표현될 때는 다음과 같은 선형 분류기가 된다:

:
\begin{align}
\log p(C_k|\mathbf{x}) & \varpropto \log \left( p(C_k) \prod_{i=1}^n {p_{ki}}^{x_i} \right) \\
                       & = \log p(C_k) + \sum_{i=1}^n x_i \cdot \log p_{ki}                 \\
                       & = b + \mathbf{w}_k^\top \mathbf{x}
\end{align}


(여기서 b = \log p(C_k) 그리고 w_{ki} = \log p_{ki}이다.)

클래스와 특성의 값이 훈련 데이터에서 발생 하지 않는 경우에는, 빈도수 기반의 확률 추정치는 0이 된다. 이것은 이 추정치가 곱해질 때 다른 확률의 모든 정보를 없앨 수 있기 때문에 문제가 될 수 있다. 따라서, 대부분의 확률 추정에서는 그 값이 0이 되지 않도록 가짜 수(pseudocount)라는 작은 샘플 보정값을 통합하여 사용하는 경우가 대부분이다. 나이브 베이즈의 이러한 정규화 방법은 가짜 수(pseudocount) 1일 경우 라플라스 정규화(Laplace smoothing)라고 불리고, 일반적으로 리드스톤 정규화(Lidstone smoothing)라고 불린다.

### 베르누이 나이브 베이즈
다변수 베르누이 이벤트 모델에서, 특성들은 입력들을 설명하는 독립적인 부울 값(이진 변수)이다. 다항 모델의 특성벡터가 이벤트의 빈도수를 나타내는 반면, 이 모델은 이벤트 발생 여부를 나타내는 부울 값을 가진다. 이진변수의 발생이 특성으로 사용되는 문서 분류 작업에 대하여 널리 이용된다. 만일 x_i가 어휘들 중 i번째 용어의 발생유무를 표현하는 부울일 경우, 주어진 클래스 C_k에 대한 문서의 우도는 다음 식으로 주어진다.
:
p(\mathbf{x} \vert C_k) = \prod_{i=1}^n p_{ki}^{x_i} (1 - p_{ki})^{(1-x_i)}

위 식에서 p_{ki}는 용어 w_i를 발생시키는 클래스 C_k의 확률이다.
이 이벤트 모델은 짧은 텍스트를 분류하는 데 특히 인기가 있고, 용어의 부재를 명시적으로 모델링하는 데 이점을 지닌다.

또한 베르누이 이벤트 모델을 통해 모델링 된 나이브 베이즈 분류는 빈도 수를 1로 가지는 다항식 NB 분류기 와 동일하지 않다는 점에 유의 해야한다.

### Semi-supervised 모수 추정

레이블 된 데이터로부터의 나이브 베이즈를 통해 훈련하는 방법으로, 레이블 된 데이터와 레이블되지 않은 데이터의 조합으로부터 지도학습 알고리즘을 이용하여 비지도학습 알고리즘을 구축할 수 있다. 레이블 된 샘플 *L* 과 되지 않은 샘플 *U*의 콜랙션 D = L \uplus U에서, 먼저 샘플 *L*에 나이브 베이즈를 이용한 훈련을 하는 것으로 시작한다.

:수렴할 때까지 다음을 시행한다:
::D에 속하는 모든 샘플 *X*에 대해서 확률 P(C|x)를 예측한다.
:: 이전 단계에서 예측 된 확률에 기반하여 다시 훈련한다.

수렴은 모델의 우도 P(D|\theta) 의 개선 에 따라 결정된다(여기서 \theta는 나이브 베이즈 모델의 파라미터를 나타냄).

이 훈련 알고리즘은 일반적인 기댓값 최대화 알고리즘의 한 요소이다(EM). 루프 내에서의 예측 단계는 EM에서 E 단계이고, 나이브 베이즈를 통해 다시 훈련 것은 M 단계로 볼 수 있다. 알고리즘은 데이터가 혼합 모델에 의해 생성되었다는 가정에 의해 정당화 되고, 이 혼합 모델의 구성요소는 정확히 분류 문제의 클래스이다.

## 예시

### 성별 분류하기
문제 : 주어진 사람들을 측정 된 특성 에 따라 남성(male) 또는 여성(female) 인지 여부를 분류한다.
특성은 신장(height), 체중(weight), 발의 크기(foot size)가 포함된다.

#### 훈련
훈련을 위해 쓰이는 샘플 셋은 다음과 같다.

가우스 분포의 가정 을 사용한 생성 된 훈련 셋으로부터 만들어진 분류기는 다음과 같다 ( 주어진 분산 은 '불편(unbiased)' 표본분산이다 )

먼저 P(남성) = P(여성) = 0.5로 각 클래스의 동등한 값을 할당한다. 이 사전 확률 분포는 전체 인구 구성에 대한 지식이나 혹은 트레이닝 셋에서의 각 클래스의 빈도수에 기반을 두어 정해진다.

#### 테스트

다음은 남성 또는 여성으로 분류될 샘플이다.

다음은 남성과 사후 확률을 나타낸다. 남성과 여성의 사후 확률 중 더 높은 그룹으로 분류한다.

:
posterior (male) = \frac{P(male) \, p(height | male) \, p(weight | male) \, p(foot size | male)}{evidence}


다음은 여성의 사후 확률을 나타낸다.
:
posterior (female) = \frac{P(female) \, p(height | female) \, p(weight | female) \, p(foot size | female)}{evidence}


증거(evidence) (또는 정규화 상수 라고도 함) 다음과 같이 계산한다.
:
evidence = P(male) \, p(height | male) \, p(weight | male) \, p(foot size | male) 
:
+ P(female) \, p(height | female) \, p(weight | female) \, p(foot size | female)


하지만 주어진 샘플에서 증거(evidence)의 값은 일정하기 때문에, 두 개의 사후 확률을 동일하게 스케일링한다. 따라서 이는 분류에 영향을 미치지 않아 무시할 수 있다.

:
P(male) = 0.5

:p(\mbox{height} | \mbox{male}) = \frac{1}{\sqrt{2\pi \sigma^2}}\exp\left(\frac{-(6-\mu)^2}{2\sigma^2}\right) \approx 1.5789,

여기서, \mu = 5.855 와 \sigma^2 = 3.5033 \cdot 10^{-2}는 트레이닝 셋으로부터 결정된 정규 분포의 매개변수이다. 그것은 확률이 아닌 확률밀도이기 때문에 1보다 큰 값도 허용된다.

:
p(\mbox{weight} | \mbox{male}) = 5.9881 \cdot 10^{-6}

:
p(\mbox{foot size} | \mbox{male}) = 1.3112 \cdot 10^{-3}

:
\mbox{posterior numerator (male)} = \mbox{their product} = 6.1984 \cdot 10^{-9}


:
P(\mbox{female}) = 0.5

:
p(\mbox{height} | \mbox{female}) = 2.2346 \cdot 10^{-1}

:
p(\mbox{weight} | \mbox{female}) = 1.6789 \cdot 10^{-2}

:
p(\mbox{foot size} | \mbox{female}) = 2.8669 \cdot 10^{-1}

:
\mbox{posterior numerator (female)} = \mbox{their product} = 5.3778 \cdot 10^{-4}

사후 확률이 여성일 경우가 더 크기 때문에, 주어진 샘플을 여성으로 예측한다.

### 문서 분류(스팸 메일 분류)
문제 : 문서의 내용에 따라서, 문서를 분류한다. 메일의 경우 문서에 적힌 내용에 따라서 스팸 및 비스팸 메일로 구분할 수 있다. 또한 여러 개의 클래스가 있을 경우에도 사후 확률이 가장 높은 클래스를 알아 낼 수 있다. 주어진 클래스 C에 대하여 문서의 단어 중에서 i 번째의 해당하는 경우 다음과 같이 나타낼 수 있다.
:p(w_i \vert C)\,
이러한 문제를 다루기 위해서, 문서에서 단어는 임의로 분포되어 있다고 가정한다. 즉 단어들은 문서의 길이나 위치, 다른 단어와의 관계 등에 종속되지 않는다는 것을 의미한다.

문서 내부의 모든 단어 w_i를 고려하여, 주어진 클래스 *C*에 대하여 문서 *D*가 속할 확률은 다음과 같다.
:p(D\vert C)=\prod_i p(w_i \vert C)\,

그러면 우리가 구하고자 하는 답은 "문서 D가 주어졌을 때, 클래스 C 에 속할 확률은 얼마인가?"이다. 다시말해서, p(C \vert D)\,를 구하고자 한다.

먼저 정의에 의해서 다음이 성립한다.
:p(D\vert C)={p(D\cap C)\over p(C)}
:p(C\vert D)={p(D\cap C)\over p(D)}

베이즈 정리를 통해 우도의 측면에서 다음과 같이 식을 바꿔줄 수 있다.
:p(C\vert D)={p(C)\over p(D)}\,p(D\vert C)

여기서 상호 배타적인 두 개의 클래스만 존재한다고 가정하면 (S 와 ¬S), 모든 문서는 D는 클래스 S 혹은 ¬S에 속하게 된다.
:p(D\vert S)=\prod_i p(w_i \vert S)\,
:p(D\vert\neg S)=\prod_i p(w_i\vert\neg S)\,

위의 식을 이용하면, 다음 식이 성립한다.

:p(S\vert D)={p(S)\over p(D)}\,\prod_i p(w_i \vert S)

:p(\neg S\vert D)={p(\neg S)\over p(D)}\,\prod_i p(w_i \vert\neg S)

이 둘을 나누면,

:{p(S\vert D)\over p(\neg S\vert D)}={p(S)\,\prod_i p(w_i \vert S)\over p(\neg S)\,\prod_i p(w_i \vert\neg S)}

다시 정리하면,

:{p(S\vert D)\over p(\neg S\vert D)}={p(S)\over p(\neg S)}\,\prod_i {p(w_i \vert S)\over p(w_i \vert\neg S)}

그러므로, 확률 비율 p(S | D) / p(¬S | D)는 우도(가능도)의 비율들로 표현 될 수 있다. 실제 확률 p(*S* | *D*)를 p(*S* | *D*) + p(¬*S* | *D*) = 1의 사실을 바탕으로 log (p(*S* | *D*) / p(¬*S* | *D*)) 로부터 계산할 수 있다.

양변에 로그를 취하면,
:\ln{p(S\vert D)\over p(\neg S\vert D)}=\ln{p(S)\over p(\neg S)}+\sum_i \ln{p(w_i\vert S)\over p(w_i\vert\neg S)}

( "로그 우도 비(로그 가능 비)"라고 불리는 이 기술은 통계학에서 일반적인 기술이다. 이 예제 같은 두 가지 상호 배타적 클래스의 경우는 확률의 대수 우도(가능) 비 변환은 시그모이드 곡선의 형태를 취한다. )

만일 p(S\vert D) > p(\neg S\vert D) 일 경우 스팸으로 (즉, \ln{p(S\vert D)\over p(\neg S\vert D)} > 0) 그렇지 않은 경우에는 비스팸으로 분류한다.

## 토론

나이브 베이즈 분류는 독립성 가정이 종종 부정확한 결과를 내기도 한다. 하지만 독립성 가정으로 나이브 베이즈 분류를 매우 편리하고 유용하게 사용할 수 있다. 특히 클래스의 조건부 특성 분포를 디커플링 하는 것은 각 분포가 독립적으로 일차원의 분포로 추정 할 수 있게 한다. 이를 통해서, 특성의 수에 비해 기하 급수적으로 많은 수의 데이터 셋을 필요로 하게 되는 차원의 저주의 문제를 완화 할 수 있다. 나이브 베이즈는 종종 올바른 클래스 확률을 도출하는 좋은 추정치를 생성하는데 실패하곤 하지만, 이 추정치가 많은 응용에서 반드시 필요한 요건은 아니다. 예를 들어, 올바른 클래스가 다른 클래스 보다 확률이 높을 가능성이 더 크기 때문에, 나이브 베이즈 분류는 올바른 MAP 결정 규칙에 따른 분류를 할 수 있다. 이는 확률 추정치가 약간 혹은 현저하게 부정확하더라도 항상 마찬가지이다. 그렇기 때문에, 이러한 분류는 나이브 확률 모델의 심각한 결함을 충분히 무시할 만큼 강력하다고 할 수 있다.

## 같이 보기
* 기계 학습
* 베이즈 이론
* 베이즈 확률론
* 베이즈 추론
* 베이즈 네트워크
* 랜덤 포레스트
* 퍼셉트론
* 서포트 벡터 머신

## 각주

### 추가 문헌
* 
* 
* 
* 
* 

## 참조
* Naive Bayes for Text Classification with Unbalanced Classes 
* Benchmark results of Naive Bayes implementations 
* Hierarchical Naive Bayes Classifiers for uncertain data (an extension of the Naive Bayes classifier).

;소프트웨어
* jBNC - Bayesian Network Classifier Toolbox
* Statistical Pattern Recognition Toolbox for Matlab.
* ifile - the first freely available (Naive) Bayesian mail/spam filter
* NClassifier - NClassifier is a .NET library that supports text classification and text summarization. It is a port of Classifier4J.
* Classifier4J - Classifier4J is a Java library designed to do text classification. It comes with an implementation of a Bayesian classifier.

분류:기계 학습
분류:분류 알고리즘
분류:통계적 분류