8. KNN

K-mearest neighbor: K개의 가장 가까운 이웃

Complex patterns of real-world dataset

• 실제 세계의 데이터는 선형적인 패턴을 가지고 있지 않은 경우가 많음

KNN

회귀, 분류 / 지도학습 / Non-parametric Method

• 주어진 데이터의 값을 예측하기 위해 K개의 가장 가까운 이웃의 정답을 참조.
• 가지고 있는 데이터와 유사도를 비교 (n번 비교)

1. 예측하고자 하는 데이터 x와 주어진 데이터 사이의 거리를 구한다.

1. x와 가장 거리가 가까운 K개의 데이터를 찾는다.
2. x와 근접한 K개의 데이터의 Label들 중 가장 많은 Label로 ${\hat y}$ 예측 or
3. x와 근접한 K개의 데이터의 Label의 평균값으로 ${\hat y}$ 예측

데이터 객체간의 거리 측정

• 유클리디안 거리 [유사도 매칭]

[예시1]

A (2, 4)

B (1, 3)

C (5, 1)

[예시2] K=2, New data = (3, 3)

데이터 x1 X2 Y (분류) 거리 (분류) Y (회귀)

1	3	4	0	1	3
2	2	1	1	${\sqrt5}$	4
3	4	2	0	${\sqrt2}$	2

• 분류

데이터 1과 데이터3이 가까움, y=0이 2개 → New data y = 0

• 회귀

데이터 1과 데이터3이 가까움, y=0, 0이 (3+2)/2=2.5 → New data y = 2.5

KNN의 하이퍼 패러미터: K

• 인접한 이웃의 개수 K

K ⬇️

• 경계선이 근처 소수의 점에 의해 결정
• 경계선 주변 점에 매우 민감
• 유연성 ⬆️ (Much Flexible)
• Bumpy Line

K ⬆️

• 경계선이 근처 많은 수의 점에 의해 결정
• 경계선이 주변 점에 매루 둔감
• 유연성 ⬇️ (Less Flexible)
• Smoother Line

Hyper Parameter Tuning

KNN의 장점과 단점

장점

1. 예측이 주변 데이터에 의해 결정됨 → 모형의 학습이 필요 없다.
2. 데이터의 구조 사전 지식이 필요없음.
3. 하이퍼 패러미터 K 단순, 생각보다 성능 좋음.

단점

1. 데이터 특성의 수(x의 수)가 커지면 성능 저하 → 차원의 저주

: 데이터의 차원이 높아질수록 데이터 공간이 희소해지고, 이로 인해 학습 알고리즘이 **과적합(Overfitting)**될 가능성이 높아지는 문제

Overfitting의 이유

1. 모델을 복잡하게 만듦.
2. 차원이 커짐 → 특성의 개수가 많음 → 더 많은 매개변수를 사용함 → 모델의 복잡도 증가
3. 데이터가 희소해짐. Sparse
4. 데이터공간의 크기 증가 (1차원 → 2차원 → 3차원..) → 샘플링 된 데이터가 전체 데이터를 대표하기 어렵게 됨. → 일반화 능력이 떨어짐.
5. 데이터 사이의 변별력이 줄어듦.
6. 차원증가 → 이웃하는 데이터 사이의 거리가 멀어지게 됨. → 서로 구분되는 패턴을 만들기 어렵게 됨 → 일반화 능력이 떨어짐.

극복방법

1. 특성 선택
2. 중요 변수만 선택
3. 모델의 복잡도 제한
4. 정규화 (모델규제를 높힘. ${\lambda}$ ⬆️)
5. 차원축소
   • PCA, Manifolds Methods
6. 적은 수의 새로운 차원으로 원래 데이터를 변환 (해석 어케함?)
7. 더 많은 데이터 확보
8. 증가한 차원만틈 더 많은 데이터 확보 필요

2. 변수의 척도가 다름 → 스케일링 필요

: 유클리디안 거리는 각 특성(feature)의 스키일(scale)이 크게 다르면, 해당 특성이 거리 계산에 더 큰 영향을 미치게 됨.

1. 변수들의 단위(metric)가 같고, 서로 비교 가능할 때
2. 변수들 간의 단위가 다르고, 서로 비교할 수 없을 때
   • Z-normalization: 모든 변수들이 평균 0, 표준편차 1
   • ${\frac{x_i-\mu_i}{\sigma_i}}$ scale-free
   • Min-max Scaling: 모든 변수들이 최대값 1, 최소값 0
   • ${\frac{X-min}{max-min}}$
3. → Scaling

end.