분류 모델 - knn과 데이터 기반 분류 모델

최근접이웃 분류기의 개념

최근접이웃 분류기의 개념

분류 문제를 생각해봤을 때, 간단한 분류 방법으로는 새로 주어진 데이터 xnew에 대해 거리가 가장 가까운 데이터를 식별하고, 식별된 근접 데이터의 클래스를 xnew으 클래스로 할당한다. 와 같이, 근처에 있는 데이터와 동일한 클래스로 분류하는 방법을 생각해 볼 수 있을 것이다. 이것이 바로 최근접이웃 분류기의 개념이다.

최근접이웃 분류기의 수식화

데이터 x와 x1간 거리를 d(x, x1)이라고 했을 때 x의 클래스를 결정짓는 함수 즉, 최근접이웃 분류기의 결정규칙을 식으로 표현하면 아래와 같다.

최근접이웃 분류기의 처리과정

순서	단계	설명
1	거리 계산	새로운 데이터 x와 모든 학습 데이터 {x1, x2, … xn}과의 거리를 계산한다.
2	최근접 이웃 식별	거리가 가장 가까운 데이터 xmin을 식별한다.
3	클래스 할당	새로운 데이터 x에 대해 xmin의 클래스와 같은 클래스를 할당하도록 결정한다.

최근접이웃 분류기의 문제점

이러한 최근접이웃 분류기는 문제점을 가지고 있는데 그것은 (1)데이터 잡음에 민감하다는 것과 (2)과다적합이 발생한다는 점이다.

문제점	설명
데이터 잡음에 민감	- 데이터 잡음이란, 이상치와 같이 일반적이지 않은 데이터를 의미한다. - 최근접이웃 분류기는 가장 가까운 “하나의 데이터”만을 참고하기 때문에, 참고하는 데이터가 이상치인 경우에는 오분류가 발생할 가능성이 높다.
과다적합	- 과다적합 또는 과적합이라고 부르는 것은, 분류 모델이 학습 데이터에만 너무 적합하여 현실 세계 혹은 테스트 데이터에서 분류율이 떨어지는 문제를 말한다. - 앞서 살펴본 데이터 잡음에 민감하다는 문제와 일정 부분 비슷한 면이 있다.

구분	KNN (K=1)	베이즈 분류기
학습 정확도	1.00	0.95
테스트 정확도	0.87	0.96

K-최근접이웃 분류기의 개념

K-최근접이웃 분류기(K-Nearest Neighbors)는 새로 주어진 데이터 xnew에 대해, 학습데이터에서 이와 가장 가까운 순서대로 K개의 데이터를 선별하여 후보 데이터집합 N(x)를 만든 뒤, 이 집합에 포함된 각 데이터의 클래스 중 가장 등장빈도가 높은 클래스를 xnew의 클래스로 할당하는 방법이다.

최근접이웃 분류기가 데이터 잡음에 민감하고, 과다적합 문제에 따른 오분류율이 높은 문제를 보완하고자 나온 분류기이다. 최근접이웃 분류기가 xnew 데이터와 가장 가까운 데이터 하나 만을 참고했다면, K-최근접이웃 분류기는 xnew 데이터와 가장 가까운 순으로 k 개의 데이터 를 참고한다는 점에서 차이가 있다.

K-최근접이웃 분류기의 수식화

K-최근접이웃 분류기는 학습 데이터 중 xnew와 거리가 가까운 K개의 데이터의 클래스를 확인하고, 이 클래스들 중 가장 등장빈도가 높은 클래스를 xnew에 할당하는 것이다.

K-최근접이웃 분류기의 처리과정

순서	단계	설명
1	거리 계산	새로운 데이터 x와 모든 학습 데이터 {x1, x2, … xn}과의 거리를 계산한다.
2	근접 이웃 식별	거리가 가장 가까운 순서로 K개의 데이터를 찾아, 후보 집합 N(x)를 만든다.
3	클래스 빈도 탐색	후보 집합 N(x)에 속한 각 데이터들이 속한 클래스들을 확인하고 식별된 클래스들 각각의 등장빈도수를 탐색한다.
4	클래스 할당	3번 단계에서 식별된 가장 빈도수가 높은 클래스를 새로운 데이터 x의 클래스로 할당한다.

K-최근접이웃 분류기의 특징

특징	설명
결정 경계	- 가우시안 베이즈 분류기에 비해 매우 비선형적인 결정경계를 가짐 - 데이터 분포 형태에 따라 성능이 크게 좌우되지 않음 즉, 비선형적 경계를 갖는 데이터분포에서 좋은 분류성능을 보일 수 있음
분류 시간 오래걸림	- 새로운 데이터가 주어질 때마다(분류 요청이 있을 때마다) 학습 데이터 전체와 거리 계산 필요 - 때문에 계산 시간이 오래 걸리며, - 항상 학습 데이터를 저장하고 있어야 하기 때문에 메모리 소모

K-최근접이웃 분류기의 결정경계

K-최근접이웃 분류기는 확률이 아닌 “데이터”에 기반한 분류기이다 보니, 데이터 자체의 특성값을 더 잘 반영할 수 있다는 특징이 있다. (이를 바꾸어 말하면 데이터 노이즈에 민감하다는 단점으로도 볼 수 있다.) K-최근접이웃 분류기는 베이즈 분류기보다 매우 비선형적인 결정경계를 가지는 특징이 있으며, 데이터 분포 형태에 따라 성능이 크게 좌우되지 않는다.

예를 들어 위 그래프처럼 데이터들의 경계가 비선형적이라면, 가우시안 베이즈 분류기보다는 KNN의 분류 성능이 더 좋을 수 있다.

K-최근접이웃 분류기의 한계

KNN 분류모델은 데이터 간 거리를 기반으로 하여 분류를 한다는 원리를 가지고 있다. 여기서 태생적 한계점이 도출되는데, 바로 새로이 분류 대상 데이터가 주어질 때마다 모든 학습데이터와의 거리계산을 수행해야 한다는 문제점이다. 이는 (1)분류를 할 때마다 계산해야 하므로, 계산량이 많다. (2)계산을 위해 항상 학습 데이터를 가지고 있어야 하므로 메모리 소모가 크다. 라는 두 가지 문제점을

반면 베이즈 분류기의 경우엔 확률밀도함수를 기반으로 분류를 진행한다. 확률밀도함수는 평균과 표준편차에만 의존하므로, 학습시 학습 데이터를 이용해서 일단 파라미터(확률밀도함수)를 추정하고 나면 이후부터는 분류시에 학습데이터가 필요하지 않고, 학습된 파라미터 혹은 평균과 표준편차만을 이용해 분류가 가능하다는 특징이 있다. 즉, 계산량과 메모리상에 KNN보다 장점을 가지고 있다.

때문에 분류 모델을 선정할 때에는 해결해야 하는 문제의 데이터 특성과 개발 환경, 각 분류 방법이 가지는 특성을 파악해서 목적에 맞는 분류기를 선택해야 하는 안목을 길러야 한다.

K-최근접이웃 분류기 설계시 고려사항

고려사항	설명
적절한 K의 값	- K 값(몇 개의 근접이웃)이 너무 작을 경우 노이즈에 민감, 학습 과적합 - K 값이 너무 클 경우 데이터 전체적인 비율(선험 확률)에 너무 의존 - 적절한 K값으로, 주변의 특성과 전체적인 데이터 특성을 모두 반영하도록 해야함
거리 함수	- 데이터간 거리 계산 방법은 다양함 - 어떤 거리계산 방법을 사용하느냐에 따라 선택되는 이웃이 달라짐 - 선택되는 이웃이 달라지면 분류 성능에 직접적인 영향

적절한 K의 값

KNN 모델의 K값에 따라 정확도 즉, 분류기의 성능은 크게 좌우된다. K의 값이 너무 작을 경우엔 근처의 데이터에만 적응하는 과적합 문제가 발생하고, K의 값이 너무 클 경우엔 너무 데이터 전체적인 분포(=선험 확률)에 적응하여 근처의 데이터 특성이 적응되지 않는 문제가 발생할 수도 있다. 따라서 주어진 데이터에 대해 가장 좋은 성능을 보이는 K값을 도출해내는 것은 KNN 모델 구축에 있어 굉장히 중요한 문제이다.

예시 : k의 값에 따른 정확도의 차이

적절한 K의 값을 찾는 데에는 여러 방법이 있을 것이지만, 특정한 정답이 있는 것은 아니며, 데이터의 특성과 문제의 특성에 맞는 K값을 찾아가는 것이 중요하다. 아래는 적정 K값을 찾기 위한 대표적인 탐색 방법 두 가지이다.

K값 탐색 방법	설명
전체 데이터 수 반영	- 전체 데이터 수의 경향성에 맞춰 K 값을 지정하는 방식 - 예시 : 전체 데이터 수가 N일 때 K=N의 제곱근 - 여러 가지 방법 중 하나이며, K 값은 데이터 수 뿐만이 아니라 데이터 분포 특성에도 의존하므로 정답이라고 할 수 없다.
실험적 검증	- K값에 변화를 줘가면서 실험적으로 어떤 K에서 가장 좋은 성능을 보이는지 측정하는 방법 - 예시 : K를 5, 10, 20, 30 으로 변화시키면서 성능 경향성을 파악 - 현실적인 방법이며, 따라서 많은 경우에 이 방식으로 K값을 찾는다. - 다만 이 또한 정답은 아니다. 정답은 없다.

거리 함수

KNN 모델에서 고려해야 할 두 번째는 거리 함수이다. 거리 함수란, 이웃과의 거리를 계산할 때 사용하는 수식 혹은 방법론을 지칭하는 말로 유클리디안 거리, 마할라노비스 거리, 코사인 거리, 노름 등 다양한 거리 함수가 있다. 위 예시에서는 각각 유클리디안 거리, 그리고 맨해튼 거리를 거리함수로 사용했을 때 선택되는 데이터가 달라지는 예시이다.

거리 함수에는 다양한 함수가 있으며, 대표적인 종류는 아래 표를 참고한다.

번호	거리 함수
1	유클리디안 거리
2	1차 노름
3	p차 노름
4	내적
5	코사인 거리
6	정규화 유클리디안 거리
7	마할라노비스 거리
…	…

Reference

머신러닝 (이관용, 박혜영 공저)