06. 분류(1) - kNN(k Nearest Neighbor)

분류-Classify

분류는 레이블이 있는 학습 데이터를 이용해 미지의 데이터를 하나의 그룹으로 분류하는 지도학습의 일종이다

kNN 알고리즘(k-Nearest Neighbor Algorithm)

kNN은 학습을 미뤄두고 있다가 미지의 데이터가 입력되면 그제서야 학습을 시작하는 Lazy Learning의 방법이다. kNN 알고리즘은 미지의 데이터를 중심으로 k개의 가장 가까운 데이터를 기준으로 미지의 데이터를 분류한다.

kNN 알고리즘의 동작

 데이터세트 안에서, 미지의 데이터를 중심으로 가상의 원(3차원에서는 구)을 확장시켜 나가면 범위 안에 들어오는 데이터를 구할 수 있다. 이 때, k=1이라 하면, 이 미지의 데이터는 원을 확장시킬 때 가장 처음으로 만나는 데이터의 그룹에 속하게 된다.

다음으로, k=3일 때의 경우를 알아보자, k=3이면 원을 확장시킬 때 가장 먼저 만나는 3개의 데이터 중 가장 많은 그룹을 미지의 데이터의 그룹으로서 정한다. 

이런 식으로, k값을 조절하며 학습의 분별력을 조절할 수 있다. 주의할 점은, k값을 짝수로 사용하는 경우 최근접 데이터들이 속한 그룹의 수가 각각 같을 수 있기 때문에 짝수를 기피해야 하고, 전체 그룹 수의 배수일 경우에도 기피해야 한다. 어쩔 수 없을 경우, 동일한 그룹의 수가 나올 경우의 대비책을 구현해야 한다(예외 처리 등)

오버피팅, 언더피팅

오버피팅 : 노이즈에 너무 민감하게 반응하여 올바르게 분류하지 못하는 경우(k값이 너무 작다)

언더피팅 : 데이터에 너무 둔감하게 반응하여 올바르게 분류하지 못하는 경우(k값이 너무 크다)

오버피팅, 언더피팅을 방지하기 위해선 k값을 적당히 조절하는것이 중요하다

kNN의 장단

장점

1) 구현이 편리하다-간단한 알고리즘

2) 수치 기반 계산에 유용

단점

1) 연산량 과다

2) 차원의 저주(K-평균 알고리즘 참조)

3) 사전학습 불가(Lazy Learning의 단점)