패턴인식 - 5. Data Driven Classification

- 확률 모델이 존재하지 않아서 데이터로부터 확률을 꺼내는 방법을 공부했다. 이를 기반으로 분류기에 적용하는 방법을 알아보자. 

 

- 1990년대 : 베이지안 룰에 근거한 패턴인식 등장, k-NN classifier

- 2000년대 : ML, NN, SVM

- 2010 : AI

- 순으로 발전해 왔지만 여전히 베이지안 룰에 근거한 판단과 분류가 이루어진다. 그동안 달라진 점은 데이터의 양이 매우 많아졌고 컴퓨팅 파워가 향상되었다는 것이다. 이 덕분에 베이지안 룰을 더 확장해서 사용할 수 있게 되었다.

1. k-NN classifier

- 특징 x1, x2를 갖는 x에 대해서 x가 c1,인지 c2인지 분류하기 위해서는 P(c1|x)와 P(c2|x)를 구해야 한다. 두 조건부확률을 구하기 위해서는 P(x)를 구해야한다.

- (자신을 제외) 구간 안에 총 8개의 원소가 되도록 한다. k = 8

- x를 중심으로 한 변의 길이가 1인 정사각형 R이 되었다. V = 1*1 = 1

- 전체 원소 수 n = 13 + 11 = 24

- 따라서 P(x) = 8/24/1 = 1/3

- P(x|c1) = 4/11/1 = 4/11 = (사각형 안에 c1의 수) / (전체 c1의 수) / (부피)

- P(x|c2) = 4/13/1 = 4/13

- P(c1) = 11/24

- P(c2) = 13/24

- 자 이제 본 목적인 P(c1|x)와 P(c2|x)를 구할 수 있다(사후확률). 두 확률을 비교하면 c1, c2 분류가 가능하다.

- P(c1|x) = P(x|c1) * P(c1) / P(x)

- P(c2|x) = P(x|c2) * P(c2) / P(x)

* P(c1|x) ><=  P(c2|x) 부등식을 간단히 하면 P(x∩c1) <>= P(x∩c2) 부등식을 간단히 하면 k1/k ><= k2/k 부등식을 간단히 하면 k1 ><= k2 가 된다.

*즉 k1 ><= k2 : region 안에 더 많이 들어오는 샘플 종류에 따라서 x의 분류가 이루어진다. (region안에 x1의 수 k1, region안에 x2의 수 k2)

 

- 참고로 kNN의 판단오류는 베이어 판단 오류와 같거나 베이어 판단 오류의 2배보다는 작다. 또한 데이터(샘플)가 많을수록 kNN판단 오류가 줄어든다.

2. 1-NN

- 1-NN은 사실상 입력 값 x에서 가장 가까운 class 1개를 찾는 문제가 된다. 

- 즉 영역 분할기이다.

- 만약 영역을 분할하는 직선 위에 x가 들어온다면 판단을 할 수 없다.

2. 5-NN

- region 모양은 사각형, 원 모두 가능하다. 주로 원을 많이 사용한다.

- 위 예시에서는 black 3개 red 2개 이므로 x는 black class로 분류된다.

3. k-NN

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- 표시된 영역에 x가 들어오면 c1, c2, c3로 분류된다.

- 보통 class가 두개일 때는 5, 7, 9을 k로 많이 사용한다.

- class가 세개일 때는 15, 21를 k로 많이 사용한다.

4. 장단점

- k-NN은 간단하고 데이터로부터 바로 classification을 수행할 수 있다. 상대적으로 성능도 우수하고 오류도 작다.

- 샘플이 작을때는 p(x) = 0 인 지점이 많이 생길 수 있기 때문에 parzen window는 잘 사용하지 않는다.

 

- 데이터가 무수히 많아지면 모든 데이터마다 region에 포함되는지 안되는지 계산을 해보아야 한다.

- 즉 데이터가 무수히 많아지면 computing 소요시간이 매우 커진다. 그래서 A* search등의 heuristic한 방식으로 탐색 시간을 줄이는 방법이 생겨났다.

 

- 특징 x1, x2가 수치로 된 데이터라면 가깝다 멀다의 거리 비교가 쉬울 것이다. 하지만 만약 color 처럼 노란색, 파란색이 가깝냐 머냐를 판단하려면 쉽지 않다. color space라는 것을 고안해서 가깝냐 머냐를 판단해야 한다. 이렇게 k-NN 응용에 따라서 distance를 정의하는 문제가 있다.