K-NN

728x90

"주변 사람을 보면 그 사람을 알 수 있다"는 말처럼,
K-최근접 이웃(K-NN, K-Nearest Neighbors)은 가장 직관적인 머신러닝 알고리즘이다.
새로운 데이터가 들어오면 가장 가까운 K개의 이웃을 찾아, 그 이웃들의 다수결로 분류하거나 평균으로 예측한다.
별도의 학습 과정 없이 데이터를 그대로 기억하는 게으른 학습(Lazy Learning)의 대표 알고리즘이다.

1. K-NN의 핵심 아이디어

K-NN의 작동 원리는 매우 단순하다.

새로운 데이터 포인트와 학습 데이터의 모든 포인트 사이의 거리를 계산한다.
거리가 가장 가까운 K개의 이웃을 선택한다.
분류: K개 이웃 중 가장 많은 클래스로 분류 (다수결)
회귀: K개 이웃의 값을 평균내어 예측

📌 K=3일 때 분류 예시 — 새 데이터(별)는 어느 클래스?

K=3 이웃: 파란 원 2개 vs 빨간 사각 1개 → 다수결: 클래스 A (파란 원)로 분류 클래스 A클래스 B새 데이터

💡 K-NN은 모델을 "학습"하지 않는다
대부분의 머신러닝 알고리즘은 학습 단계에서 파라미터를 업데이트하며 모델을 만든다.
K-NN은 학습 데이터를 그냥 전부 기억해두고, 예측 시점에 거리를 계산한다.
이를 게으른 학습(Lazy Learning) 또는 인스턴스 기반 학습(Instance-based Learning)이라 한다.
→ 학습은 빠르지만, 예측 시 모든 데이터와 거리를 계산해야 해서 예측이 느리다.

2. 거리 척도 — 이웃을 어떻게 정의하는가

K-NN에서 "가장 가까운 이웃"을 찾으려면 거리를 정의해야 한다. 데이터 유형과 상황에 따라 다양한 거리 척도를 사용한다.

유클리드 거리
(Euclidean)

√Σ(xᵢ − yᵢ)²

가장 많이 사용.
직선 거리 (피타고라스 정리).
연속형 수치 데이터에 적합.

맨해튼 거리
(Manhattan)

Σ|xᵢ − yᵢ|

격자 이동 거리.
이상치에 덜 민감.
고차원에서 유클리드보다 강건.

민코프스키 거리
(Minkowski)

(Σ|xᵢ−yᵢ|^p)^(1/p)

p=1: 맨해튼
p=2: 유클리드
p를 조절해 일반화.

💡 고차원에서의 거리 문제 — 차원의 저주
특성(차원)이 많아질수록 모든 데이터 포인트 사이의 거리가 비슷해지는 현상이 발생한다.
예를 들어 100차원에서는 가장 가까운 이웃과 가장 먼 이웃의 거리 차이가 거의 없어진다.
→ K-NN은 고차원 데이터에서 성능이 급격히 떨어질 수 있다 (차원의 저주, Curse of Dimensionality)
→ PCA 등 차원 축소 기법을 먼저 적용하는 것이 도움이 된다.

3. K 값 설정 — 가장 중요한 하이퍼파라미터

K-NN에서 K는 고려할 이웃의 수다. K 선택이 모델 성능을 크게 좌우한다.

K가 너무 작을 때 (예: K=1)

훈련 데이터의 개별 포인트 하나에 의존.
이상치(노이즈)에 매우 민감하다.
결정 경계가 복잡하고 불규칙해진다.
→ 과적합(Overfitting) 위험

K가 너무 클 때 (예: K=n)

너무 많은 이웃을 고려해 경계가 지나치게 단순해진다.
전체 다수 클래스를 항상 예측하게 된다.
→ 과소적합(Underfitting) 위험

📌 K 값에 따른 결정 경계 변화

K=1 (과적합) 복잡한 경계 K=5 (적절) 균형 잡힌 경계 K=n (과소적합)단순한 직선 경계

💡 K 선택 실무 팁
• 일반적으로 홀수 K를 선택한다 — 이진 분류에서 동점(tie) 방지
• 경험적 출발점: K = √n (n: 훈련 데이터 수)
• 교차 검증으로 여러 K값을 시험하고 최적값 탐색
• 클래스가 많을수록 더 큰 K가 필요한 경우가 많다

4. 단계별 계산 예시

📌 예시: 새 아파트의 가격대(고가/저가) 분류 (K=3)

면적(㎡)과 역까지 거리(분)로 아파트 가격대를 분류한다.

학습 데이터

아파트 면적(㎡) 역 거리(분) 가격대
A 84 5 고가
B 59 15 저가
C 76 8 고가
D 45 20 저가
E 90 3 고가
F 50 18 저가

새 데이터: 면적 70㎡, 역 거리 10분

① 유클리드 거리 계산

dist(새, A) = √((70-84)² + (10-5)²) = √(196+25) = √221 ≈ 14.87
dist(새, B) = √((70-59)² + (10-15)²) = √(121+25) = √146 ≈ 12.08
dist(새, C) = √((70-76)² + (10-8)²) = √(36+4) = √40 ≈ 6.32 ← 1위
dist(새, D) = √((70-45)² + (10-20)²) = √(625+100) = √725 ≈ 26.93
dist(새, E) = √((70-90)² + (10-3)²) = √(400+49) = √449 ≈ 21.19
dist(새, F) = √((70-50)² + (10-18)²) = √(400+64) = √464 ≈ 21.54

② K=3 최근접 이웃 선택

1위: C (6.32) → 고가
2위: B (12.08) → 저가
3위: A (14.87) → 고가

③ 다수결 분류

고가 2표 vs 저가 1표
→ 새 아파트 분류: 고가

5. 가중 K-NN (Weighted K-NN)

기본 K-NN은 K개의 이웃에 동일한 가중치를 준다. 그런데 가까운 이웃이 먼 이웃보다 더 큰 영향을 줘야 합리적이지 않을까? 가중 K-NN은 거리에 반비례하는 가중치를 부여한다.

가중치 wᵢ = 1 / d(x, xᵢ)²

거리가 가까울수록 가중치가 크다
분류: 가중 다수결 | 회귀: 가중 평균 = Σ(wᵢ · yᵢ) / Σwᵢ

📌 위 예시에 가중 K-NN 적용

w_C = 1/6.32² = 1/39.94 ≈ 0.025 (고가)
w_B = 1/12.08² = 1/145.93 ≈ 0.007 (저가)
w_A = 1/14.87² = 1/221.12 ≈ 0.005 (고가)

고가 가중합 = 0.025 + 0.005 = 0.030
저가 가중합 = 0.007
→ 가중 다수결: 고가 (동일한 결론이지만 차이가 더 명확)

6. K-NN 회귀 (KNN Regression)

K-NN은 분류뿐만 아니라 연속값을 예측하는 회귀에도 사용된다. 분류에서 다수결을 쓰는 대신, K개 이웃의 값을 평균내어 예측값으로 사용한다.

ŷ = (1/K) · Σᵢ∈N_k(x) yᵢ

N_k(x): x의 K-최근접 이웃 집합
가중 회귀: ŷ = Σ(wᵢ · yᵢ) / Σwᵢ

📌 K-NN 회귀 실용 예시
• 아파트 가격 예측: 비슷한 조건(면적, 층수, 위치)의 K개 실거래가 평균
• 추천 시스템: 비슷한 취향의 K명 사용자가 좋아한 콘텐츠의 평점 평균
• 결측값 대체: 비슷한 관측치 K개의 값 평균으로 결측값 채우기 (KNN Imputation)

7. K-NN 전처리 — 반드시 해야 하는 것들

① 특성 스케일링 (필수)

K-NN은 거리 기반 알고리즘이므로 특성의 단위와 범위가 다르면 큰 값을 가진 특성이 거리를 지배한다. 예를 들어 면적(20~200㎡)과 역 거리(1~30분)를 그대로 사용하면 면적이 거리 계산을 압도한다. 반드시 StandardScaler나 MinMaxScaler로 정규화해야 한다.

② 차원 축소 고려

고차원 데이터는 차원의 저주로 K-NN 성능이 떨어진다. PCA나 t-SNE로 차원을 줄이거나, 불필요한 특성을 제거한 후 적용한다.

③ 이상치 처리

K=1처럼 K가 작을 때는 이상치 하나가 결과를 바꿀 수 있다. 이상치를 제거하거나 K를 충분히 크게 설정해 영향을 줄인다.

8. K-NN의 장단점과 활용

장점

구현이 단순하고 직관적
학습 단계가 없어 데이터 추가 시 즉시 반영
비선형 결정 경계를 자연스럽게 처리
다중 클래스 분류에 바로 적용 가능
하이퍼파라미터가 K 하나뿐

단점

예측 시 모든 학습 데이터와 거리 계산 → 느림
메모리에 전체 학습 데이터를 저장해야 함
고차원 데이터에서 성능 저하 (차원의 저주)
특성 스케일링 없으면 결과가 크게 왜곡
불균형 클래스에서 다수 클래스에 편향

📌 K-NN이 잘 작동하는 상황
• 데이터 수가 적당하고 차원이 낮을 때
• 결정 경계가 복잡하고 비선형일 때
• 추천 시스템 (협업 필터링의 기초)
• 이상치 탐지: 가장 가까운 이웃까지의 거리가 먼 데이터 = 이상치
• 결측값 대체 (KNN Imputation)

⚠️ 클래스 불균형 주의
학습 데이터에서 클래스 A가 90%, 클래스 B가 10%라면,
어떤 새 데이터든 K개 이웃 중 클래스 A가 많을 가능성이 높다.
→ 가중 K-NN 사용, 오버샘플링/언더샘플링, 또는 K를 줄여 소수 클래스의 영향을 높이는 방법을 고려한다.

9. 나이브 베이즈 vs SVM vs K-NN 비교

구분	나이브 베이즈	SVM	K-NN
접근 방식	확률 기반	기하학적	거리 기반
학습 속도	매우 빠름	느림(대용량)	없음(즉시)
예측 속도	빠름	빠름	느림
비선형 처리	어렵다	커널 트릭	자연스럽게
고차원 성능	좋음	좋음	나쁨 (차원의 저주)
스케일링	불필요	필수	필수
파라미터	거의 없음	C, γ	K
메모리	적음	적음	많음 (전체 저장)
강점	텍스트, 빠른 분류	고차원 소규모	단순, 비선형

📌 핵심 정리

K-NN 원리: 새 데이터에서 가장 가까운 K개 이웃을 찾아 다수결(분류) 또는 평균(회귀)
게으른 학습: 학습 단계 없이 데이터를 그대로 저장. 예측 시 계산
거리 척도: 유클리드(p=2), 맨해튼(p=1), 민코프스키(p=p)
K가 작으면: 과적합, 이상치에 민감 | K가 크면: 과소적합, 경계 단순화
K 선택 팁: 홀수 사용(동점 방지), √n 출발점, 교차 검증으로 최적화
가중 K-NN: 가중치 = 1/거리². 가까운 이웃에 더 큰 영향
차원의 저주: 고차원에서 모든 거리가 비슷해짐 → PCA 등 차원 축소 필요
특성 스케일링 필수: 거리 기반이므로 StandardScaler 등 전처리 필요
강점: 단순, 비선형 처리, 즉각 학습 반영
약점: 예측 느림, 메모리 많음, 고차원에 약함, 불균형 클래스에 편향