[AI] k-nn 알고리즘

1. k-NN
k-NN(최근접 이웃, k-Nearest Neighbors) 알고리즘은 지도 학습(Supervised Learning)에서 사용되는 간단하면서도 효과적인 분류(Classification) 및 회귀(Regression) 알고리즘입니다.

import math
from collections import Counter

train_data = [
    [1, 2],
    [2, 3],
    [3, 3],
    [6, 5],
    [7, 7],
    [8, 6]
]

train_labels = ['A', 'A', 'A', 'B', 'B', 'B']

def euclidean_distance(train_data, test_point):
    distance = []
    for i, data_point in enumerate(train_data):
        dist = math.sqrt(sum((a-b)**2 for a, b in zip(data_point, test_point)))
        distance.append((dist, train_labels[i]))
    return distance  # for문 바깥으로 이동

def knn_classify(train_data, train_labels, test_point, k):
    distance = euclidean_distance(train_data, test_point)
    sorted_distance = sorted(distance, key=lambda x: x[0])
    k_nearest_labels = [label for _, label in sorted_distance[:k]]
    most_common = Counter(k_nearest_labels).most_common(1)
    return most_common[0][0]

# 예측 결과 출력
print(knn_classify(train_data, train_labels, [5,5], 3))

2. 핵심 개념
새로운 데이터 포인트가 주어지면, 학습 데이터 중에서 가장 가까운 k개의 이웃을 찾습니다.
이웃의 "가장 많은" 클래스(분류) 또는 평균값(회귀)을 예측값으로 사용합니다.

3. 동작 방식

• 1) k값(이웃의 수)을 정합니다.
• 2) 예측하려는 데이터와 학습 데이터 간의 거리를 계산합니다(주로 유클리드 거리 사용).
• 3) 거리가 가까운 k개의 데이터를 선택합니다.
• 4) 분류 문제라면, 이웃 중 가장 많은 클래스가 예측 결과가 됩니다.
  예: k=3, 이웃 클래스가 [A, B, A]라면 예측은 A
  회귀 문제라면, 이웃의 값 평균을 예측값으로 사용합니다.

4. 특징
학습 과정이 거의 없고, 예측 시 계산이 집중됩니다(메모리 기반).
k값과 거리 측정 방법에 따라 성능이 달라집니다.
데이터의 스케일(정규화)이 중요합니다.

5. 장점/단점
구현이 쉽고, 직관적입니다.
소규모 데이터에 효과적입니다.
데이터가 많아지면 속도가 느려집니다.
차원이 높아질수록(특징이 많아질수록) 성능이 저하될 수 있습니다(차원의 저주).

6.5-way 다중 분류 문제 평가

• Accuracy 정의 : $\text{Accuracy} = \frac{1}{N} \sum_{i=1}^{N} 1(y_i = \hat{y}_i)$
• error 정의 : 1 - Accuracy