나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개

나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개

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

지금 부터 소개할 알고리즘은, 머신러닝 알고리즘 중에서 분류 알고리즘으로 많이 사용되는 나이브 베이스 알고리즘이다. 

배경 지식

나이브 베이스 알고리즘을 이해하려면 몇가지 배경 지식이 필요하다. 

베이스 정리

먼저 베이스 정리를 보면, 매개 변수, x,y가 있을때,  분류 1에 속할 확률이 p1(x,y)이고, 분류 2에 속할 확률이 p2(x,y)일때, 

• p1(x,y) > p2(x,y) 이면, 이 값은 분류 1에 속한다.
• p1(x,y) < p2(x,y) 이면, 이 값은 분류 2에 속한다.
• 나이브 베이스 알고리즘은 이 베이스의 정리를 이용하여, 분류하고자 하는 대상의 각 분류별 확률을 측정하여, 그 확률이 큰 쪽으로 분류하는 방법을 취한다.

예를 들어, 이메일에 대해서 분류가 스팸과 스팸이 아닌 분류가 있을때, 이메일에 들어가 있는 단어들 w1,…,wn 매개 변수 (“쇼핑”,”비아그라”,”보험”,….)에 대해서,  해당 이메일이 스팸일 확률과 스팸이 아닌 확률을 측정하여, 확률이 높은 쪽으로 판단한다.

조건부 확률

나이브 베이스를 이해하기 위해서는 확률의 개념 중 조건부 확률이란 것을 이해 해야 한다. 존건분 확률 이란, 사건 A에 대해서, 사건 A가 일어났을때, 사건 B가 일어날 확률

“사건 A에 대한 사건 B의 조건부 확률” 이라고 하며, P(B|A)로 표현한다.

예를 들어, 한 학교의 학생이 남학생인 확률이 P(A)라고 하고, 학생이 키가 170이 넘는 확률을 P(B)라고 했을때, 남학생 중에서, 키가 170이 넘는 확률은 B의 조건부 확률이 되며 P(B|A)로 표현 한다.

베이스 규칙

이 조건부 확률을 이용하면, 모르는 값에 대한 확률을 계산할 수 있는데

• P(A|B) = P(A∩B) / P(B) <- 1)
• P(B|A) = P(A∩B) / P(A) <- 2)

1),2)를 대입 하면

• P(A|B)*P(B) = P(B|A)*P(A)
• P(A|B) = P(B|A)*P(A)/P(B)

앞의 남학생인 확률 P(A)와 키가 170이상인 확률 P(B)를 알고, 남학생중에서 키가 170인 확률 P(B|A)를 알면, 키가 170인 학생중에, 남학생인 확률 P(A|B)를 알 수 있다.

나이브 베이스 알고리즘을 이용한 분류 예

다음과 같이 5개의 학습 문서가 존재하고, 분류가 comedy(코메디 영화), action(액션 영화) 두개가 존재한다고 하자. 

movie	단어(Word)	분류
1	fun,couple,love,love	Comedy
2	fast,furious,shoot	Action
3	Couple,fly,fast,fun,fun	Comedy
4	Furious,shoot,shoot,fun	Action
5	Fly,fast,shoot,love	Action

이제, 어떤 문서에 “fun,furious,fast” 라는 3개의 단어만 있는 문서가 있을 때, 이 문서가 코메디인지 액션 영화인지 분리를 해보자 

해당 영화가 코메디인 확률은

P(comedy|words) = P(words|comedy)*P(comedy)/P(words)  A.1 이며

액션 영화인 확률은

P(action|words) = P(words|action)*P(action)/P(words)  A.2 이 된다.

A.1 > A.2이면, 코메디 영화로 분류하고, A.1<A.2이면 액션 영화로 분리한다.

이때, A.1과 A.2는 모두 P(words)로 나누는데, 대소 값만 비교 하기 때문에 때문에 굳이 P(words)를 구해서 나눌 필요가 없이 

• P(comedy|words) = P(words|comedy)*P(comedy) <-- B.1
• P(action|words) = P(words|action)*P(action) <-- B.2

만 구하면 된다. 그러면, B.1과 B.2의 값을 실제로 계산해보자

먼저 각 단어의 빈도수를 계산하면

• Count (fast,comedy) = 1 (코메디 중, fast 라는 단어가 나오는 횟수)
• Count(furious,comedy) = 0
• Count(fun,comedy) = 3
• Count(fast,action)= 2
• Count(furious,action)=2
• Count(furious,action) = 1

P(words|comedy)는 comedy 영화중, 지정한 단어가 나타나는 확률로, 이를 개별 단어로 합치면펼치면 P(fast,furious,fun|comedy)으로, 각 단어가 상호 연관 관계가 없이 독립적이라면 (이를 조건부 독립 conditional independence라고 한다), 

P(fast|comedy)*P(furious|comedy)*P(fun|comedy)로 계산할 수 있다.

이를 계산 해보면, Comedy 영화에서 총 단어의 개수는 9번 나타났기 때문에, 모수는 9가 되고 그중에서 각 단어별로 comedy에서 나타난 횟수는 위와 같이 comedy이면서 fast인것이 1번, comedy 이면서 furious인것이 0번, comedy이면서 fun인것이 3번이 되서, 

P(fast|comedy)*P(furious|comedy)*P(fun|comedy) 는 { (1/9) * (0/9) * (3/9)} 가 된다.

그리고, P(comedy)는 전체 영화 5편중에서 2편이 comedy이기 때문에, P(comedy)=2/5가 된다.

이를 B.1에 대입해보면,

P(comedy|words) = { (1/9) * (0/9) * (3/9)} * 2/5 = 0 이 된다.

같은 방식으로 B.2를 계산하면 액션 영화에서 총 단어수는 11이고, 각 단어의 발생 빈도로 계산을 해보면

P(action|words) = { (2/11) * (2/11)*(1/11) } * 3/5 = 0.0018이 된다.

결과 “P(action|worlds) = 0.0018” > “P(comedy|word) = 0” 이기 때문에, 해당 문서는 액션 영화로 분류가 된다.

Laplace smoothing

위의 나이브 베이스 알고리즘을 사용할때, 하나의 문제점이 학습 데이타에 없는 단어가 나올때이다. 즉 분류를 계산할 문서에 “cars”라는 단어가 있다고 하자, 이 경우 학습 데이타를 기반으로 계산하면, cars는 학습 데이타에 없었기 때문에, P(cars|comedy)와 P(cars|action) 은 모두 0이 되고, P(comedy|words)와 P(action|words)도 결과적으로 모두 0이 되기 때문에, 분류를 할 수 없다.

즉 문서가 “fun,furious,fast,cars”로 되면

P(comedy|words) = { (1/9) * (0/9) * (3/9) * (0/9:cars 단어가 나온 확률) } * 2/5 = 0

P(action|words) = { (2/11) * (2/11)*(1/11) * (0/9:cars 단어가 나온 확률)  } * 3/5 = 0

이를 해결하기 위한 방법이 Smoothing이라는 기법으로, 이 기법은 새로운 단어가 나오더라도 해당 빈도에 +1을 해줌으로써 확률이 0이 되는 것을 막는다

다시 P(x|c)를 보자

 

이렇게 계산했다.

즉, P(“fun”|comedy) = “comedy중 fun”이 나오는 횟수 / “comedy 중 나오는 모든 단어의 수 중 중복을 제거한수” 로 계산했다.

.Laplace smoothing을 하려면 빈도에 1씩을 더해 줘야 하는데, 빈도를 더해주면 공식은

 

같이 된다.

여기서 |V|는 학습 데이타에서 나오는 전체 단어의 수(유일한 개수)가 된다. 위의 학습데이타에서는 fun,couple,love,fast,furious,shoot,fly로 총 7개가 된다.

이 공식에 따라 분자와 분모에 빈도수를 더하면

P(comedy|words) = { (1+1/9+7) * (0+1/9+7) * (3+1/9+7) * (0+1/9+7:cars 단어가 나온 확률) } * 2/5 = 0.00078

P(action|words) = { (2+1/11+7) * (2+1/11+7)*(1+1/11+7) * (0+1/9+7:cars 단어가 나온 확률)  } * 3/5 = 0.0018

※ 수식에서 편의상 (2+1)/(11+7) 등으로 괄호로 묶어야 하나 2+1/11+7과 같이 표현하였으나 분자에 +1, 분모에 +7을 해서 나눈 것으로 계산하기 바란다

로 액션 영화로 판정 된다.

Log를 이용한 언더 플로우 방지

이 알고리즘에서 문제는 P(words|comedy)나 P(words|action)은 각 단어의 확률의 곱으로 계산된다는 것인데, P(fun|comedy)*P(furios|comedy)*…. 각 확률은 <1 이하기이 때문에, 항목이 많은 경우 소숫점 아래로 계속 내려가서, 구분이 어려울 정도까지 값이 작게 나올 수 있다.

이를 해결 하기 위해서 로그 (log)를 사용하면 되는데

log(a*b) = log (a) + log(b)와 같기 때문에,

• P(comedy|words) = P(words|comedy)*P(comedy)  B.1
• P(action|words) = P(words|action)*P(action) B.2

양쪽 공식에 모두 Log를 취하면 (어짜피 대소 크기만 비교하는 것이니까)

• Log(P(comedy|words)) = Log(P(words|comedy)*P(comedy))<-- B.1
• Log(P(action|words)) = Log(P(words|action)*P(action))<--B.2

가 되고, B.1을 좀 더 풀어보면

Log(P(words|comedy)*P(comedy)) 

= Log(P(fun|comedy)*P(furios|comedy)*…*P(Comedy) ) 

= log(P(fun|comedy))+log(P(furios|comedy)+…+log(P(Comedy)) 로 계산할 수 있다.

위의 자료는 http://unlimitedpower.tistory.com/entry/NLP-Naive-Bayesian-Classification%EB%82%98%EC%9D%B4%EB%B8%8C-%EB%B2%A0%EC%9D%B4%EC%A6%88-%EB%B6%84%EB%A5%98 를 참고하였습니다.