[ Week 3-1 ] Instance-based Learning KNN

Lecture : Machine Learning

Date : week 3, 2024/03/11

Topic : Instance-based Learning 

 

 

1. Instance-based Learning 

2. KNN

   1) KNN

   2) Tie breaking 방법

   3) weighted KNN

   4) 장단점

 

---

1. Instance-based Learning (사례 기반 학습) 

- 모델이 훈련 데이터를 기억한 상태에서, 새로운 input을 기존의 훈련 데이터와 비교해 가장 유사한 instance를 찾아내는 방식으로 일반화

- labeled data가 필요한 지도학습의 한 방법으로, instance 간 유사도를 측정하기 위해 유사도 함수를 선택해야한다. 

- KNN을 비롯한 Nearest Neighbour Classification 

 

 

※ Model Based Learing (모델 기반 학습)

- 머신러닝 모델의 일반화 방식에 따라 구분된다. 
- 훈련 데이터를 기반으로 예측 모델을 생성함으로써 새로운 데이터에 대해 예측하는 방식으로 일반화 

 

 

 

 

 

2. KNN

1) KNN 

- Supervised learning, instance-based Model for Classification 

- 새로운 데이터에 대하여, 기존의 훈련 데이터셋 내에서 가장 유사한 K개의 '이웃' 데이터를 찾고 해당 이웃들이 가장 많이 가지고 있는 label을 새로운 데이터의 label로 분류하는 모델 

출처 : https://mlarchive.com/machine-learning/k-nearest-neighbor-knn-explained/

 

 

 

2) Design decisions

: Data scaling/normalization, Distance Metric, size of K, The way to break tie 

 

※ Tie breaking 방법 

- K를 홀수로 둠으로써 tie 가능성 낮춤 

- (k+1)-th neighbor를 포함했을때 tie를 해결할 수 있는지 확인 

- random breaking 혹은 전체에서 probability가 더 높은 class를 선택 

 

 

 

3) Weighted KNN 

- K개의 neighbors에 대하여 유사도에 따라 가중치를 부여 

- 유사도가 높을수록 해당 이웃에 더 높은 가중치를 줌으로써 최종 결과에 더 많이 반영하는 방식 

- 일반 KNN의 경우, 유사도가 높은 K개에 대하여 모두 같은 가중치를 두는 방식(단순 다수결 방식)을 사용하기 때문에 유사도 순에 대한 정보가 반영되지 않는다는 점을 개선함 

 

- 가중치 계산 방식 

inverse linear distance	inverse distance

 

 

 

4) 장단점

- 장점

① 모델이 간단하고 이해하기 쉬움 

② 별도의 모델 학습이 필요없는 lazy learning 모델 

 

- 단점

① 적절한 유사도 함수, K의 크기, tie breaking 방법을 직접 결정해야함 

② 예측값이 일부 영역에 의해 국소적으로 결정 → 지역 정보와 이상치에 취약함 

③ 예측시 모든 훈련 데이터 내 모든 instance와 유사도를 계산해야하므로 연산량이 많음 

 

=> 훈련은 쉽지만, 예측시 연산이 많이 요구되는 모델 

 

 

 

 

 

 

 

Reference

https://awesomejane.tistory.com/entry/%EC%82%AC%EB%A1%80-%EA%B8%B0%EB%B0%98-%ED%95%99%EC%8A%B5-vs-%EB%AA%A8%EB%8D%B8-%EA%B8%B0%EB%B0%98-%ED%95%99%EC%8A%B5
https://spring-cherry.tistory.com/19
https://velog.io/@juuurr/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-k-%EC%B5%9C%EA%B7%BC%EC%A0%91-%EC%9D%B4%EC%9B%83-k-Nearest-Neighbor-kNN#41-%EC%9E%A5%EC%A0%90