KNN 알고리즘

📍분류/예측을 위한 학습 방법

☑️Model-based Learning (모델 기반 학습)

• 데이터로부터 모델을 생성하여 분류/예측 진행 (즉, 분류/예측 모델을 학습)
• linear regression, logistic regression, decision tree, SVM, neural network, ...

☑️Instance-based Learning (사례 기반 학습)

• 별도의 모델 생성없이 데이터 베이스에 있는 자료들을 분류/예측에 사용
• 각각의 관측치 (instance) 만을 이용하여 새로운 데이터에 대한 예측을 진행
• 대표적으로 KNN 알고리즘이 있음.

 

📍K-최근접 이웃(K-Nearest Neighbors, KNN) 알고리즘

- 새로운 데이터 포인트의 분류를 결정하기 위해 가장 가까운 k개의 이웃 데이터 포인트를 참조

- Instance-based learning으로 분류와 회귀 모두 사용 가능

- 별도의 모델 생성 없이 인접한 데이터를 분류 / 예측 

 

📍K-최근접 이웃(KNN) 알고리즘 개요

☑️분류(범주형)

- 데이터를 가장 가까운 속성에 따라 분류하여 레이블링 하는 알고리즘

- 새로운 데이터를 분류할 때, 해당 데이터와 거리가 가까운 k개의 다른 데이터를 선택하고, 이 k개의 데이터 중 가장 빈도 수가 높은 레이블을 새로운 데이터의 레이블로 분류

- ex ) K=3이고, 이웃들이 각각 클래스 A, A, B에 속한다면, 새로운 데이터 포인트는 클래스 A로 분류

☑️회귀(예측)(연속형)

-  K개의 이웃의 평균값을 사용하여 새로운 데이터 포인트의 값을 예측

☑️ k 결정 

- k 가 작은 경우:  오버피팅 overfitting 발생  : 새로운 데이터 대한 일반화 능력이 떨어지는 현상 

- k가 큰 경우 : 언더피팅 underfitting 발생: 모델이 훈련 데이터와 테스트 데이터 모두에 대해 일반화 능력이 부족한 상태 

 

=> k의 값을 조정해가며 가장 높은 예측 성능을 보이는 k 값을 찾아야 됨

 

☑️ 데이터 간의 거리 측정

- KNN 알고리즘에서 거리를 기반으로 데이터를 분류하므로, 각 특징(feature)의 스케일(크기)이 매우 중요

- 거리 측정 전 feature scaling 필수! 

→ 단위가 큰 특정 변수에 의해 거리가 결정되는 것을 방지하기 위함

ex : 자치시 별 1인당 범죄율: 0~1, 주택 1가구 당 평균 방의 개수: 1~7, 주택가격: $120,000~

 

☑️ 거리 측정 함수 

(1)Euclidean Distance

• X, Y값 간 차이 제곱합의 제곱근

• 데이터의 분포나 상관관계 고려 x

• 두 관측 치 사이의 직선 거리 (최단거리)

• 𝑑(𝑋,𝑌)= σ𝑖=1𝑛 (𝑥𝑖− 𝑦𝑖)2  ( σ𝑖=1𝑛 -> i=1에서 n까지의 합)

• L2 distance라고도 함

(2) Manhattan Distance

 

• Taxicab distance 혹은 L1 distance라고도 함

• X에서 Y로 각 좌표축 방향으로만 이동할 때

계산되는 거리 (격자거리)

• 𝑑(𝑋,𝑌)= σ𝑖=1𝑛 |𝑥𝑖− 𝑦𝑖|

(3) Mahalanobis Distance

 

• 𝑋 − 𝑌 𝑇𝛴−1 𝑋 − 𝑌 = 𝑐2

→ 즉, 타원의 방정식

• 데이터의 분포나 상관관계 고려

- 원일 경우 Euclidean Distance 와 동일

 

 

(4) Correlation Distance

 

• 데이터 간의 Pearson correlation을 거리측도로 사용함

• 두 벡터 간의 상관 관계를 기반으로 한 측정 방법  ( 두 변수간의 상관관계 고려 ) 

• 데이터 패턴의 유사도 반영이 가능함

• 𝑑𝑐𝑜𝑟𝑟(𝑋,𝑌)= 1 − 𝑟, 𝑤ℎ𝑒𝑟𝑒 𝑟 = ( 𝐶𝑜𝑣(𝑋,𝑌) )  /  ( 𝜎𝑋∙𝜎𝑌 ) (correlation)

• −1 ≤ r ≤ 1

• 0 ≤ 𝑑𝑐𝑜𝑟𝑟(𝑋,𝑌) ≤ 2

 

 

☑️weighted KNN 

- KNN 알고리즘의 확장으로, 각 이웃의 중요도를 고려하여 예측 수행

- 기본 KNN은 단순히 가장 가까운 ( k )개의 이웃의 다수결로 새로운 데이터 포인트를 분류하는 반면, Weighted KNN은 각 이웃의 거리에 따라 가중치를 부여하여 더 정확한 예측을 수행

 

- 가중치 

• 거리 기반 가중치: 가까운 이웃일수록 더 큰 가중치를 부여하고, 먼 이웃일수록 더 작은 가중치를 부여합니다.
• 가중치 함수: 일반적으로 사용하는 가중치 함수는 거리의 역수입니다. 즉, 거리 ( d )에 대해 가중치는 ( \frac{1}{d} )로 주어집니다.

 

 

 

☑️ KNN 적용 시 고려사항

1. K 값 선택: K의 값은 모델의 성능에 큰 영향을 미칩니다. 일반적으로 교차 검증(cross-validation)을 통해 최적의 K 값을 찾습니다.
2. 거리 척도 선택: 데이터의 특성에 따라 적절한 거리 척도를 선택해야 합니다.
3. 데이터 전처리: 특성 값의 범위가 크게 다를 경우, 표준화 또는 정규화(normalization)를 통해 각 특성의 값을 스케일링하는 것이 중요합니다.

 

📍KNN의 장점과 단점

 

☑️장점

 

- 단순함: 이해하고 구현하기 쉬운 알고리즘

- 수치 기반 데이터 분류 작업에서 우수함

- 적은 하이퍼파라미터

- 학습 데이터가 많을 때 효과적 
- 유연성: 분류와 회귀 모두에 사용 가능
- 비모수적: 데이터의 분포에 대한 가정이 필요 없음

☑️단점

- 계산 비용: 모든 거리 계산이 필요하므로 데이터 양이 많아지면 계산 비용이 증가

- 시간이 오래걸림 

- 파라미터 k 값과 데이터 특성에 맞는 거리측도를 찾아야 하며, k의 선택이 중요함

- 공간 복잡 : 모든 학습 데이터를 메모리에 저장해야 하므로 공간 복잡도가 큽니다.
- 고차원 데이터에서 성능 저하: 고차원 데이터에서는 거리 계산의 효율성이 떨어져 성능이 저하될 수 있습니다. 이를 "차원의 저주(Curse of Dimensionality)" 라고 합니다.