최근접 이웃 알고리즘: 유사한 사례를 찾아서
예측의 지혜, 유사 사례 찾기
낯선 환경에서 길을 잃었을 때, 우리는 주변 사람들에게 도움을 요청하곤 한다. 최근접 이웃 알고리즘(Nearest Neighbor Algorithm)도 이와 같은 원리를 사용한다. 즉, 새로운 데이터 포인트의 값을 예측하기 위해 특징 공간에서 가장 가까운 이웃을 찾고, 그 이웃의 값을 이용하여 예측을 수행한다.
최근접 이웃 알고리즘: 예측 단계
최근접 이웃 알고리즘의 예측 단계는 다음과 같다.
- 거리 계산: 새로운 데이터 포인트와 기존 데이터 포인트들 사이의 거리를 계산한다.
- 최근접 이웃 찾기: 계산된 거리 값을 기반으로 새로운 데이터 포인트와 가장 가까운 이웃을 찾는다.
- 예측 값 결정: 찾은 최근접 이웃의 값을 새로운 데이터 포인트의 예측 값으로 사용한다.
최근접 이웃 알고리즘 의사 코드 (Pseudocode)
Require : a set of training instances Require : a query instance1. Iterate across the instances in memory to find the nearest neighbor - this is the instance with the shortest distance across the feature space to the query instance 2. Make a prediction for the query instance that is equal to the value of the target feature of the nearest neighbor
보로노이 테셀레이션(Voronoi Tessellation): 수백만 개 데이터의 효율적 처리
데이터셋의 크기가 매우 클 경우, 모든 데이터 포인트와의 거리를 계산하는 것은 매우 비효율적이다. 이러한 문제를 해결하기 위해 보로노이 테셀레이션(Voronoi tessellation)을 사용할 수 있다.
보로노이 테셀레이션은 특징 공간을 각 데이터 포인트를 중심으로 하는 영역으로 분할하는 방법이다. 각 영역은 해당 데이터 포인트와 가장 가까운 모든 지점을 포함한다.
보로노이 테셀레이션을 사용하면 새로운 데이터 포인트가 어떤 영역에 속하는지 빠르게 판단할 수 있으며, 해당 영역의 중심 데이터 포인트를 최근접 이웃으로 사용하여 예측을 수행할 수 있다.
 |
| Local model |
이와 같이 보로노이 테셀레이션은 특징 공간을 지역 모델(local model)로 분할한다. 이러한 지역 모델을 결합하여 전역 예측 모델(global prediction model)을 생성할 수 있다.
 |
| Global representation of the predictions |
이렇게 되면 최근접 이웃 알고리즘은 새로운 데이터 인스턴스가 추가될 때 모델을 쉽게 업데이트할 수 있다는 장점이 있다. 새로운 데이터 포인트를 특징 공간에 추가하고, 보로노이 테셀레이션을 업데이트하면 된다.
노이즈 처리: k 값 조정
k-최근접 이웃 알고리즘은 k개의 최근접 이웃을 사용하여 예측을 수행한다. k 값을 조정하여 노이즈(noise)를 처리하고 과적합(overfitting)을 방지할 수 있다.
 |
| Majority vote |
k 값이 작을수록 모델은 학습 데이터에 더 민감해져 과적합될 가능성이 높아진다. 반대로 k 값이 클수록 모델은 학습 데이터에 덜 민감해져 과소적합(underfitting)될 가능성이 높아진다.
 |
| overfitting |
 |
| underfitting |
결론
최근접 이웃 알고리즘은 유사성 기반 학습의 대표적인 알고리즘으로, 새로운 데이터 포인트와 가장 가까운 이웃을 찾아 예측을 수행한다. 보로노이 테셀레이션을 사용하여 수백만 개의 데이터를 효율적으로 처리하고, k 값을 조정하여 노이즈를 처리하고 과적합을 방지할 수 있다. 다음에는 probability based learning에 대해 다뤄보겠다.
추천글 :
[인공지능개론] similarity based learning - feature space, measures of similarity
(https://hyeonb.blogspot.com/2024/10/similarity-based-learning.html)
(https://hyeonb.blogspot.com/2024/10/information-based-learning-decision-tree.html)
