[Machine Learning] k-NN Algorithm | k-최근접 이웃 알고리즘

k-NN Algorithm (k-Nearest Neighbors Algorithm)

 

k-최근접 이웃 알고리즘

 

- 패턴 인식에서 Classification(분류) 혹은 Regression(회귀)에 사용되는
  Non-Parametric Statistics(비모수 통계) 방식 알고리즘이다.

 

- 새로운 데이터가 주어졌을 때, 새로운 데이터 주위에 가장 가까운 k개의 기존 데이터들의 정보로
  새로운 데이터를 분류(예측)하는 방법이다.
  (이를 Regression에 적용하는 경우, 레이블의 평균값으로 새로운 데이터를 예측한다.)

 

- 학습 데이터에 존재할 수 있는 노이즈의 영향을 크게 받지 않는다.

- 학습 데이터의 수가 많을 때 보다 효과적인 알고리즘이다.

 

* Non-Parametric Statistics (비모수 통계)

- 모수에 대한 가정을 전제로 하지 않고, 모집단의 형태에 관계없이 주어진 데이터에서 직접 확률을 계산하여
  통계학적 검정을 수행하는 분석법이다.

- 표본수가 적고, 모집단의 분포를 모르는 경우에 적용할 수 있는 통계 기법이다.

 

- k-NN을 분류와 회귀 중 어느 모델에 적용하느냐에 따라 아래처럼 출력 형식이 달라진다:

• k-NN Classification
  - k개의 최근접 이웃 사이에서 가장 공통적인 항목에 해당되는 객체가 출력된다.
   
• k-NN Regression
  - k개의 최근접 이웃이 가진 값의 평균치가 출력된다.

 

---

Mechanism (원리)

 

- k-NN 알고리즘에서는 새로 입력된 데이터와 기존 데이터 사이의 거리를 계산하고,
 새로 입력된 데이터는 가장 가까운 거리에 있는 k개의 데이터들 중 대다수의 특성을 따라간다.

- 이때, 새로운 데이터와 기존 데이터 사이의 거리를 계산하는 방법은 아래와 같다:

• Euclidean Distance (유클리드 거리) (URL)
  - 직교좌표계에서 두 점 사이의 거리
   
• Hamming Distance (해밍 거리, 중첩 거리) (URL)
  - 같은 길이의 두 문자열에서 같은 위치에서 서로 다른 Symbol들의 개수

 

* C++

// C++ program to find groups of unknown
// Points using K nearest neighbour algorithm.
#include <algorithm>
#include <math>

using namespace std;
  
struct Point
{
    int val;     // Group of point
    double x, y;     // Co-ordinate of point
    double distance; // Distance from test point
};
  
// Used to sort an array of points by increasing
// order of distance
bool comparison(Point a, Point b)
{
    return (a.distance < b.distance);
}
  
// This function finds classification of point p using
// k nearest neighbour algorithm. It assumes only two
// groups and returns 0 if p belongs to group 0, else
// 1 (belongs to group 1).
int classifyAPoint(Point arr[], int n, int k, Point p)
{
    // Fill distances of all points from p
    for (int i = 0; i < n; i++)
        arr[i].distance =
            sqrt((arr[i].x - p.x) * (arr[i].x - p.x) +
                 (arr[i].y - p.y) * (arr[i].y - p.y));
  
    // Sort the Points by distance from p
    sort(arr, arr+n, comparison);
  
    // Now consider the first k elements and only
    // two groups
    int freq1 = 0;     // Frequency of group 0
    int freq2 = 0;     // Frequency of group 1
    for (int i = 0; i < k; i++)
    {
        if (arr[i].val == 0)
            freq1++;
        else if (arr[i].val == 1)
            freq2++;
    }
  
    return (freq1 > freq2 ? 0 : 1);
}

 

---

Implementation (구현)

 

* Python Scikit-Learn (URL)

# Survivor Prediction of Titanic using k-NN Algorithm (Scikit-Learn)

import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns

from sklearn.neighbors import KNeighborsClassifier

# Load the dataset
titanic_bunch = sns.load_dataset('titanic')
titanic_bunch = titanic_bunch.dropna(axis=0) # Drop the rows including NaN 
titanic_bunch['sex'] = titanic_bunch['sex'].replace({'female':0, 'male':1}) # Numericalization of Column 'sex'
titanic_bunch['embarked'] = titanic_bunch['embarked'].replace({'C':0, 'S':1, 'Q':2}) # Numericalization of Column 'embarked'
numeric_column = ['pclass', 'sex', 'age', 'sibsp', 'parch', 'fare', 'embarked']

# Data separation
X = titanic_bunch.loc[:, numeric_column]
y = titanic_bunch.loc[:, 'survived']

# Model Evaluatiuon (Finding the optimum k)
from sklearn.model_selection import train_test_split
x_train, x_test, y_train, y_test = train_test_split(
    X,
    y,
    random_state=100
)

model = KNeighborsClassifier(n_neighbors=3)
model.fit(x_train, y_train)

k_range = range(1, 11)
train_score = []
test_score = []

for k in k_range:
    model = KNeighborsClassifier(n_neighbors=k).fit(x_train, y_train)
    train_score.append(model.score(x_train, y_train))
    test_score.append(model.score(x_test, y_test))

# Visualization
plt.plot(k_range, train_score, label='Train Accuracy')
plt.plot(k_range, test_score, label='Test Accuracy')
plt.xticks(k_range)
plt.title('Find Best K-Value in titanic')
plt.legend()
plt.grid()
plt.show()

# Scoring
print('Training Score:', model.score(x_train, y_train))
print('Evaluation Score:', model.score(x_test, y_test))

---

Reference: "k-nearest neighbors algorithm"; Wikipedia; 2022년 8월 31일 작성; 2022년 9월 15일 검색, URL.