#5 (KNN) k-Nearest Neighbors

k-최근접 이웃 알고리즘(k-Nearest Neighbors, KNN)

지도 학습(supervised learning) 알고리즘의 일종으로, 분류(classification) 및 회귀(regression) 문제에 사용된다.

이 알고리즘의 기본 아이디어는 새로운 데이터 포인트가 주어졌을 때, 가장 가까운 k개의 이웃 데이터를 기준으로 분류하거나 값을 예측하는 것이다.

https://www.pinecone.io/learn/k-nearest-neighbor/

위의 사진에서 ★모양의 새로운 데이터가 들어왔을 때, 근접한 3개의 이웃 데이터를 분류한다고 했을 때(K=3), Class A이웃이 1개, Class B이웃이 2개이므로 ★은 Class B로 분류될 것이다.

그러나 K=6라면 Class A가 4개, Class B가 2개로 ★은 Class A로 분류된다.

 

장점

1. 학습 Data에 대한 가정이 필요없다.

-> 선형 회귀에서는 데이터가 선형적으로 분포한다고 가정하지만, KNN은 이러한 가정을 하지 않으므로 다양한 유형의 데이터에 유연하게 적용될 수 있다.

2. 분류, 회귀 모두 가능하다.

3. 적절한 K에서는 새로운 데이터에 대한 예측이 빠르다.

단점

1. 높은 계산 비용이 발생한다.

-> 새로운 데이터를 예측할 때마다 전체 학습 데이터와의 거리를 계산해야 하기 때문이다.

2. Dataset이 많을수록 느려진다.

-> 데이터셋의 크기가 커질수록 모든 데이터 포인트와의 거리를 계산하는 데 시간이 많이 걸리므로 예측 속도가 느려진다.

3. 적절한 K를 찾는 것이 어렵다.

-> k값의 선택은 KNN 알고리즘의 성능에 큰 영향을 미친다. 너무 작은 k값은 모델이 노이즈에 민감해져 과적합(overfitting)될 수 있으며, 너무 큰 k값은 모델이 과도하게 일반화되어 성능이 떨어질 수 있다.

 

적절한 K

 

• 모든 문제에 적용되는 올바른 k값은 존재하지 않는다.
• 최적의 k값을 찾기 위해 여러 k값을 시도해 볼 수 있다.
• 경험적으로, k값으로 train examples 수의 제곱근을 추천.
• 특정 클래스가 매우 드문 경우, 충분한 수의 예제를 보기 위해 더 큰 k값이 (about10?) 더 좋다.