분류 시스템 - 저작자표시-비영리-변경금지 2.0 대한민국 이용자는 아래의 ...

데이터를 분류한다면

②

를 분리경계면으로 할 때보다 오분류를 줄일 수 있을 것이다

.

Figure 2-4. Boundary Hyperplanes

※ 출처 : 오일석. 패턴인식. 2008.[50]

훈련데이터

(input)

는 두개의 클래스인

‘-1’

또는

‘+1’

에 속하는

y

i와

d

차 원 공간의 특징

x

(x

⊆X)

로 구성되며

,

훈련데이터로 생성된 분류기

(classifier)

에 의해 실험데이터

(output) x (x⊆X)

를

‘-1’

또는

‘+1’

로 분류 한다

.



 



 

  



→     ∈



식

(2.1)

과 같은 경계면

(hyperplane) H

가 있다고 가정하자

.



   ′    

(

식

2.1)

여기서

w

는 단위길이를 갖는 경계면과 직교하는 벡터이며

,

원점에서 이 경계면과의 수직거리는 ∥∥

 가 된다

.

또한 식

(2.1)

과 평행인 경계면

H

1과

H

2가 있다고 가정하자

.

단

,

두 경 계면 사이에는 데이터가 없어야 한다

.



_    ′    

(

식

2.2a)



_   ′     

(

식

2.2b)

식

(2.2a)

의 경계면은 클래스

1

의 데이터 중 식

(2.1)

의 분리경계면에서 가장 가까운 데이터를 지나며

,

식

(2.2b)

의 경계면은 분리경계면에서 클래 스

-1

의 가장 가까운 데이터를 지나게 된다

.

따라서

H

1과

H

2의 거리

(margin)

는 ∥∥

 이다

.

Figure 2-5. Optimal Hyperplane decision

※ 출처 : 김재필. 구간별 집합 근사 알고리즘과 Support vector machine을 이용한 심전도 패턴분류에 관한 연구. 2006.[58]

선형

(linear) SVM

은 이 거리를 최대로 하는 분리경계면을 찾는 문제로

귀착되며

,

식

(2.3)

과 같은 최적화 문제가 된다

.

Max

′



(

식

2.3)

Subject to

′_   ≥  for _ 

′_   ≥  for _  

(2.4) .

이것은 이차

(quadratic)

식의 고전적인 형태가 된다

.

따라서

Convex

최 적화 문제가 되며

,

라그랑주 방법

(Lagrangian method)

을 이용하여 라그 랑주 곱셈자

(Lagrange multiplier)

를 최대화하는 쌍대문제

(dual problem)

로 식

(2.5)

와 같이 식을 변환할 수 있다

[51].



 



_{  }^ ^^ ^{ }_^



_{  }^ _{  }



^ ^^^^^^^^^′^^^

⁽

^식

^2.5)

Subject to

_{  }



^ ^^^^^{ }

_ ≥     



이렇게  값을 찾게 되면 최적의 분리경계면을 결정하는 ′ 를 구 할 수 있다

.

최적해에서 _  인 객체를

support vector

라고 하는데

,

이는 경계면

H

1 또는

H

2 상에 놓이게 된다

.

그리고

H

1 또는

H

2 상에 놓이지 않는 객 체들은 _  이 된다

.

따라서

support vector

를 찾을 수 있다면 이들만 을 대상으로 식

(2.5)

를 통해 분리경계면을 도출할 수 있다

.

Figure 2-6. Support Vectors

※ 출처 : Vert JP. Support Vector Machines in bioinformatics. 2002.[51]

SVM

을 학습시킨 후 새로운 객체

x

에 대한 분류규칙은 식

(2.6a), (2.6b)

와 같다

.

  ′     이면

,

클래스

1

로 분류

(

식

2.6a)

  ′     이면

,

클래스

-1

로 분류

(

식

2.6b)

SVMlight[48]

는

SVM

을

C

로 구현해 놓은 오픈 소스로

,

학습모듈

(learning module)

과 분류모듈

(classification module)

로 이루어져 있다

.

데이터와

support vector

로 이루어진 모델을 입력 받아 실험데이터의 예 측값

(predicted value)

을 생성한다

.

실험데이터는 식

(2.6a)

와 식

(2.6b)

와 같이 예측값이

0

보다 크면 클래스

1

로

, 0

보다 작으면 클래스

-1

로 분류 된다

.

본 연구에서는 디폴트 커널인

linear kernel

과 디폴트 세팅으로 실 험하였다

.

나

. Na ї ve Bayesian

Na

ve Bayesian

도

SVM

과 같이 지도학습 방법을 사용하여 정답이 있 는 훈련데이터의 특징이 특정 클래스에 출현하는 빈도에 따라 사전 확률

(prior probability)

분포를 구한 후

,

실험데이터의 특징 출현 빈도에 따 라 특정 클래스로 분류될 사후 확률

(posterior probability)

을 베이즈 이 론

(Bayes' theorem)

에 따라 계산하여 확률값이 높은 클래스로 실험데이 터를 분류하는 기계학습 방법이다

. Na

ve Bayesian

은 특징 간 독립성을 가정하고 있어 계산이 빠르고

,

훈련데이터가 적은 경우에도 효과적으로 분류해 주는 것이 가장 큰 특징이다

[52-54].

실험데이터의 사후 확률







_ _는 베이즈 이론에 따라 식

(2.7)

과 같 이 계산된다

.

  ^

 _



_{ }

_

_









_



_



_

(

식

2.7)

_는 임의의 실험데이터를 의미하고

, 

_는 임의의 클래스

(-1

또는

1)

를 의미한다

. 

_는 모든 클래스에 대하여 같은 값을 가지므로 확률을 계 산하는데 고려하지 않아도 되기 때문에 사전 확률값인







_와 우도

(likelihood)

인



_



_를 구하면

,

_가



_로 분류될 확률을 계산할 수 있 다

.

사전 확률







_는 모든 훈련데이터 수

(n)

와



_ 클래스에 속하는 훈 련데이터 수

(

_



)

의 비율로 구할 수 있으며

,

이는 식

(2.8)

과 같다

.

  ^





_{ }^_^^

(

식

2.8)

Na

ve Bayesian

은 조건부 확률



_



_를 간단히 계산하기 위해 실험 데이터에 존재하는 특징

(feature, F)

들이 서로 독립적

(independent)

이라는 가정을 하며

,

이 가정을 통해



_



_는 식

(2.9)

와 같이 변환하여 계산 할 수 있다

.



_



_ 



_{  }^

^

^

^

^^

^

^^

⁽

^식

^2.9)

그러나 식

(2.9)

는 특정 클래스에 존재하지 않는 특징에 대해서는

‘0’

의 값을 가져 전체 식의 값을

‘0’

이 되게 할 수 있다

.

따라서 사후 확률이

'0'

의 값을 갖지 않도록

Laplace smoothing[55]

을 적용하여 식

(2.10)

과 같이 계산해 주며

,

실험데이터는 가장 큰 사후 확률값을 가지는 클래스 로 분류된다

.

  

클래스에 출현하는 특징



_의 빈도수이다

. | Vocabulary |

는 훈련데이터에 포함되어 있는 서로 다른 특징 수이다

.

Na

ve Bayesian

훈련 방법은 특징을 표현하는 방법에 따라

multi- variate Bernoulli

방법과

multi-nomial Na

ve Bayesian

방법으로 나누어 진다

. Multi-variate Bernoulli

방법은 특징을 존재 유무인 불리언 벡터로 표현하고

, multi-nomial Na

ve Bayesian

방법은 특징을 빈도로 표현한다

.

본 연구에서 사용한 특징은 빈도로 표현되어 있고

, multi-nomial Na

ve Bayesian

의 분류성능이

multi-variate Bernoulli

보다 좋다는 이전 연구

[53]

에 따라 본 연구에서는

multi-nomial Na

ve Bayesian

방법을 사용하였 다

.

문서에서 저작자표시-비영리-변경금지 2.0 대한민국 이용자는 아래의 ... - S-Space (페이지 45-54)