k-Nearest Neighbors

K-Nearest Neighbor, KNN, K-최근접 이웃

• 지도학습 알고리즘
• Definition: It is one of the simplest Machine learning algorithms based on supervised learning techniuqe.
• 분류와 회귀에 모두 사용
• 데이터로부터 거리가 가까운 k개의 다른 데이터의 레이블을 참조하여 분류하는 알고리즘
• 거리를 측정할 때, 유클리디안 거리 계산법 사용
• 사용하는 곳: 영상에서 글자 인식, 얼굴 인식, 의료, 유전자 데이터 패턴 인식

KNN 프로세스

1. k를 선택한다. (*k는 주로 홀수)
2. k개 이웃의 유클리드 거리 계산
3. 계산된 유클리드 거리에 따라 k개의 가장 가까운 이웃 선택
4. k개의 이웃 중에서 각 범주의 데이터 포인트 수 카운팅
5. 이웃 수가 최대인 해당 범주에 새 데이터 포인트를 할당

고려사항

결정경계(모델의 복잡도) Noise(이상치)

K값 높을수록	경계 완만, 복잡도 낮음	이상치에 덜민감
K값 낮을수록	경계 각짐, 복잡도 증가	이상치에 민감

거리 측정 방법

*Norm: 유한 차원의 벡터 공간에서 벡터의 절대적인 크기(Magnitude) or 벡터 간 거리

L1 Norm

:Manhattan distance

• 두 벡터 간의 거리를 절댓값으로 구한 것
• 두 벡터를 빼고 절댓값을 취한 뒤 모두 더한 것
• 맨하탄 거리 혹은 택시 거리라 하며, 택시가 도시의 블록 사이를 이동해 다른 지점으로 이동하는 공식

그림1. Manhattan distance

L2 Norm

: 유클리안 거리 계산법

공식

그림2. 유클리안 거리 계산법

• 두 점 사이의 거리 계산
• 피타고라스의 성질에 대입하여 d를 계산

L1 norm L2 norm

다른 점으로 이동하는 방법	여러개	한 가지
Outlier 영향	robust	큼
Gradient-based learning	0에서 미분 불가능	Regularization 효과 큼

*Regularization

: 학습 기반의 알고리즘에서 모델이 과적합 되지 않도록 손실 함수에 특정한 규제 함수를 더하여 손실함수가 너무 작아지지 않도록 weight에 페널티를 주는 것

 

Lk Norm, Linifite Norm

공식

 

Cosine similarity

• magnitude(거리)가 중요x, 성분의 ratio가 중요
• 두 벡터 간의 코사인 각도를 구하여 두 벡터의 유사도를 의미
• 1에 가까울 수록 유사도가 높다고 표현

유사도에 따른 벡터의 방향

공식 

유사도 구하는 공식

 

Jaccard similarity

공식

Jaccard similarity

변수 값 범위 재조정

• K-NN 알고리즘을 사용하기 위해 변수들의 범위를 재종해야함

1. 최소-최대 정규화
2. z-점수 표준

장점 & 단점

장점 단점

장점	단점
• 단순하고 효율적 • 훈련 단계가 없음 (No training, Only inference step) • 수치 기반 데이터 분류 작업에서 성능이 우수 • No lose of information	• Sensitive to noise • If training data is imbalanced, major class may dominate • Have to keep all data → Memory space • Affected by local structure of training data • Need to calculate the distance from all training data → Time • Calaulating distance in high dimensional space is expensive • In high dimensional space, nearest neighbours are not near (Curse of dimensionality)

cf.) Clustering

• 거리기반으로 분류
• 비지도학습(Unsupervised Learning)