k-최근접 이웃 알고리즘(k-NN)

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

 학습한 후 저장된 데이터 세트와 하나의 데이터 요소를 근접성을 이용해 비교하고 예측을 수행하는 머신 러닝 알고리즘입니다. 조금 더 자세히 들어가면 분류(classification)나 회귀(regression)에 사용되는 비모수 방식의 알고리즘입니다. 비모수적, 즉 non-parametric하다는 것은 모델 학습 시 명시적인 가정(데이터의 분포 가정 등)을 하지 않는 대신 전체 데이터(학습 샘플)를 저장하고, 예측 시 해당 데이터를 참조하여 결과를 도출하는 것을 의미합니다.

 

분류(Classification); 통계적 분류

분류는 머신러닝에서 여러 개의 클래스(class, 종류) 중 하나를 구별해 내는 것을 말하는데요.

# 2개의 클래스 중 하나를 고르는 문제를 이진 분류(binary classification)라고도 합니다.

k-NN 알고리즘에서 분류 문제의 동작 원리를 먼저 살펴볼게요!

1️⃣ 데이터 저장: 학습 데이터셋을 메모리에 저장

2️⃣ 거리 측정: 새로운 데이터 포인트(테스트 샘플)가 주어지면, 저장된 모든 학습 샘플과의 거리를 측정

거리 측정 방법으론 일반적으로 유클리드 거리를 많이 사용하나, 맨하탄 거리, 민코프스키 거리 등도 사용됩니다.

3️⃣ 가장 가까운 k개의 샘플 선택: 계산된 거리를 기준으로 가장 가까운 k개의 이웃(학습 샘플)을 선택

4️⃣ 과반수 의결: k개의 이웃 중 가장 많이 등장하는 클래스를 예측 결과로 선택

 

회귀(Regression); 회귀 분석

관찰된 연속형 변수들에 대해 두 변수 사이의 모형을 구한 뒤 적합도를 측정해 내는 분석 방법을 말해요.

회귀도 데이터 저장, 거리 측정, 가장 가까운 k개의 샘플을 선택한다는 점에선 분류와 같은데요.

하지만 회귀는 과반수 의결 방식이 아니라 k개의 이웃의 타깃 값(연속적인 값)의 평균 혹은 가중 평균을 계산하여 예측값으로 사용한다는 점에서 다릅니다. 예측값을 계산하는 거죠!

---

🤔 분류와 회귀에 대해 조금 더 자세히 설명해주세요ㅠㅠ 헷갈려요!

🐢 예측 대상과 출력 값의 특성에서의 차이를 중심으로 설명할게요!

1️⃣ 예측 대상

분류

입력 데이터에 대한 이산적인(불연속적인) 클래스 또는 범주를 예측

예시) 스팸 분류, 이미지 분류

회귀

입력 데이터에 대한 연속적인 값을 예측

예시) 주가 예측, 온도나 강수량 예측

2️⃣ 출력 값

분류

결과가 클래스(범주)로 표현

예측 결과가 명확한 카테고리로 구분, 각 카테고리에 확률 값 부여 가능

회귀

결과가 연속적인 실수 값으로 표현

예측 결과가 특정 범위 내의 숫자로 나타나며, 오차의 크기가 중요한 평가 기준

---

📢 k-NN 알고리즘 고려사항

🌟 파라미터 k의 선택

k-NN 알고리즘에서 k 값은 굉장히 중요한데요. 작은 k 값은 모델이 학습 데이터에 민감해져서 과적합(overfitting). 즉 기계 학습 데이터를 너무 과하게 학습하여 새 데이터를 정확하게 예측하지 못하게 돼요. 하지만 반대로 k 값이 너무 커지면 너무 넓은 범위의 데이터를 고려하게 되어 일반화 능력이 떨어지게 됩니다! 그래서 보통 교차 검증을 통해 최적의 k 값을 선택하게 됩니다.

🌟 거리 측정

유클리드 거리: 두 점 사이의 직선 거리

맨하탄 거리: 각 축 방향의 차이 합

민코프스키 거리: 유클리드 거리와 맨하탄 거리의 일반화된 형태

🌟 차원의 저주(Curse of Dimensionality)

특성(feature)(; 데이터의 특징)의 수가 많아질수록 데이터 포인트가 고르게 퍼지게 되어, '가까운' 이웃을 찾는 것이 어려워 질 수 있어요.

---

장점

이해하기 쉽고 구현이 간단

비모수적 접근: 데이터의 분포에 대한 가정이 필요 X, 다양한 데이터에 유연하게 적용

실시간 예측: 예측 시 단순히 거리 계산과 투표만 수행하므로, 새로운 데이터를 추가할 때 모델 재학습 필요 없음

단점

계산 비용: 예측 단계에서 모든 학습 데이터를 탐색하므로, 데이터셋이 크면 계산 비용 많이 듦

메모리 소모: 모든 데이터를 저장하므로

차원의 저주: 고차원 데이터에서는 성능 저하

---

라이브러리(scikit-learn)에서 제공하는 k-NN 함수

분류: KNeighborsClassifier / 회귀: KNeighborsRegressor

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)
predictions = knn.predict(X_test)
distances, indices = knn.kneighbors(X_test)
accuracy = knn.score(X_test, y_test)

KNeighborsClassifier()

주요 파라미터

n_neighbors (default=5)

예측 시 고려할 이웃의 수

weights (default='uniform')

이웃의 가중치를 어떻게 부여할지

'uniform': 모든 이웃에 동일한 가중치

'distance': 이웃과의 거리에 반비례하는 가중치, 가까운 이웃의 영향력 증가

algorithm (default='auto')

최근접 이웃 검색에 사용할 알고리즘을 결정

'auto': 데이터에 따라 가장 적합한 알고리즘을 자동 선택

'ball_tree': Ball Tree 자료구조를 사용

'kd_tree': KD Tree 자료구조를 사용

'brute': 모든 데이터를 순회하는 브루트 포스 방식

leaf_size (default=30)

Ball Tree 또는 KD Tree를 구성할 때의 리프 노드의 크기를 지정

metric (default='minkowski')

두 샘플 간의 거리를 계산할 때 사용할 거리 측정 방식을 지정

'minkowski' (기본): 민코프스키 거리를 사용

'euclidean': 유클리드 거리를 사용

'manhattan': 맨하탄 거리를 사용

p (default=2)

민코프스키 거리 계산 시 사용되는 지수 값

metric_params

거리 계산 함수에 추가적으로 전달할 매개변수를 딕셔너리 형태로 지정

n_jobs (default=None)

최근접 이웃 검색을 수행할 때 사용할 CPU 코어 수를 지정

n_jobs=-1로 설정하면, 사용 가능한 모든 코어를 사용하여 병렬 처리

 

fit(x, y)

학습 데이터를 입력받아 모델을 학습

predict(x)

학습된 데이터를 기반으로 새로운 데이터 x에 대한 클래스 예측

kneighbors(x)

각 샘플에 대해 최근접 이웃의 거리와 인덱스 반환

score(x, y)

예측 겨로가 실제 레이블을 비교하여 모델의 정확도 반환