Day 01. K-Nearest Neighbor ( KNN )

 K-Nearest Neighbor

데이터셋에 라벨을 포함한 피처가 N개 있을때 하나의 레코드를 N차원 공간상의 점으로 맵핑한후, 새로운 N차원의 데이터가 들어왔을때

해당 데이터와 제일 가까운 K개의 점을 고르고 그 점들이 가장 많이 속해있는 그룹으로 새로운 데이터를 분류하는 알고리즘.

개선 여지 

1. 데이터의 전처리

KNN의 경우 노이즈가 포함된 피처에 굉장히 취약하다. 철저한 Feature selection이 사전에 시행되지 않으면 엉뚱한 결과가 나올 수 있다.

2.적절한 K 값의 설정.

K-Fold Cross validation을 하면서 Test Error를 확인하고, 적절한 K값을 찾아야 한다, K값이 특정 값 이상으로 높게 되면 각 그룹간의 경계가 애매해져서 오히려

성능이 떨어진다.

3. 적절한 거리 측정 방식 선정.

단순히 유클리디안거리를 사용한 KNN의 경우 특정 데이터 형태에는 적합하지 않다. 예를 들어 이미지의 경우,

숫자 1이 있을때 1이라는 형태가 조금만 오른쪽으로 가게 되면 유클리디안 거리는 이미지상의 강체의 형태가 전혀 변하지 않았음에도 불구하고

이미지내 도형위치에 해당하는 픽셀값이 전부 변했기 때문에 두 이미지는 전혀 연관이 없는 이미지로 취급된다.

이를 보완하기 위해서 약간의 이동이나 기울기 변화에 비교적 둔감한 Tangent distance을 사용하거나, shape context를 이용하는것을 권장한다.

4. 분류 속도의 비효율성.

 N개의 데이터로 훈련된 분류기로 새로운 데이터를 분류할경우 N개의 모든 데이터와 거리를 구하게 되기때문에 N 이 커질수록 분류 속도가 저하된다.

Locality sensitive hashing , ball trees, K-d trees 알고리즘으로 최대 Log N 까지 낮출수 있다.

출처 및 참고자료 : edx -  Machine Learning Fundamentals_week.1