[Artificial Intelligence / Machine Learning] k-Nearest Neighbor Algorithm

1. Concept of Algorithm

k-Nearest Neighbor(k-NN)는 어떤 데이터 오브젝트이 집합에 대하여 일정 규칙에 의하여 분류된 상태에서 새로운 데이터 오브젝트에 대한 분류를 하는 알고리즘입니다. 이 때 미리 분류된 데이터 오브젝트를 기계에 입력하여 기계가 분류 기준을 판단할 수 있도록 하는 것을 training이라고 합니다.

k-NN은 기계 학습(Machine Learning) 중 지도 학습(Supervised Learning)에 대한 분류(classification) 알고리즘입니다. 이 알고리즘은 여러 분야에 사용될 수 있으며 대표적으로 도서 나 영화 추천 서비스 등이 있습니다.

사실 알고리즘 컨셉은 의외로 단순합니다. 예를 들어, 기계에게 영화의 특성을 알려 주고 어떤 장르의 영화인지 맞춰보게 한다고 해보겟습니다. 이를 위해서는 영화의 특성을 우선 정의할 필요가 있다. 이미 장르가 분류된 여러 편의 영화에 대하여 각각 액션 씬의 횟수, 키스 씬의 횟수, 베드 씬의 횟수, 배우들의 대화 톤 등을 분석하여 각 장르에 대한 분류 집합을 만듭니다. 새로운 오브젝트에 대하여 이들 파라미터를 기반으로 거리(Distance Metric)을 계산하여 각 장르에 가장 근접한 것을 찾아냅니다.

2. Process

k-NN 알고리즘으로 분류를 알아내는 프로세스는 다음과 같습니다:

(1) Distance Metric을 정의합니다.

(2) 기존의 데이터셋을 트레이닝 및 테스트 데이터로 쪼갭니다.

(3) 여러 k값에 대하여 k-NN을 실행하여 계산값을 확인합니다.

(4) (3)에서 계산된 값에 대한 최적의 k값을 찾아냅니다.

(5) 선택된 k값에 대하여 새로운 오브젝트 데이터에 대하여 k-NN을 실행하고 결과를 평가합니다.

3. Distance Metric

어떠한 데이터가 어디에 속하는지 판단하려면 판단 기준이 있어야 합니다. k-NN에서의 판단 기준을 Distance Metric이라고 하며 이를 근거로 근접성(Closeness) 또는 유사성(Similarity)을 판단합니다.

3.1. Cosine Similarity

두 벡터의 방향이 얼마나 유사한지는 두 벡터의 내적을 계산하여 알 수 있습니다. 두 벡터의 내적을 두 벡터의 절대값이 곱으로 나누면 두 벡터 간의 각도에 대한 Cosine값을 알 수 있습니다. 즉,

\( \vec{x} \cdot \vec{y}= \vert \vert x \vert \vert \vert \vert y \vert \vert \mathrm{cos}(\vec{x}, \vec{y}) \)

로부터

\( \displaystyle { \mathrm{cos}(\vec{x}, \vec{y}) = \frac{\vec{x} \cdot \vec{y}}{\vert \vert x \vert \vert \vert \vert y \vert \vert} } \)

를 구할 수 있으며, 두 벡터 사이의 각이 같은 방향일수록 +1에 가까워지도 반대 방향일수록 -1에 가까워집니다. 이 값을 Cosine Distance라고 정의합니다.

3.2. Jaccard Distance

Jaccard Distance는 두 집합 간의 유사성을 평가하는 기준입니다. 집합 A와 집합 B에 대하여 두 집합의 합집합의 원소 개수에 대한 교집합의 원소 개수로 정의합니다. 즉,

\( \displaystyle{ J(A,B) = \frac{n(A \cap B)}{n(A \cup B)} } \)

으로 정의한다. 따라서, 두 집합의 원소가 동일할 경우 1이 되며, 교집합이 없는 경우 0이 된다.

3.3. Mahalanobis Distance

Mahalanobis Distance는 두 벡터 사이의 Distance를 정의하기 위한 것으로 두 벡터 간 상관관계를 고려하였다는 점에서 Euclidean Distance보다 장점이 있습니다. Mahalanobis Distance는 다음과 같이 정의합니다.

\( d(\vec{x}, \vec{y}) = \sqrt{ (\vec{x} - \vec{y})^{T} S^{-1} (\vec{x} - \vec{y}) } \)

여기서 S는 공분산 행렬(Covariance Matrix)이라고 하며, 다음과 같이 정의됩니다. 두 개의 열벡터(Column Vector) X와 Y는 다음과 같으며,

\( \mathbf{X} = \begin{bmatrix} X_1 \\ \vdots \\ X_n \end{bmatrix} \), \( \mathbf{Y} = \begin{bmatrix} Y_1 \\ \vdots \\ Y_n \end{bmatrix} \)

\(i,j\) 성분에 대하여 Covariance는

\( \sum_{i,j} = \mathrm{cov}(X_i, Y_i) = E[(X_i - \mu_i)(Y_j - \mu_j)] \)

이다. 여기서, \( \mu_i = E(X_i) \)입니다.

3.4. Hamming Distance

DNA의 염기서열에 대한 유사성을 평가하기 위한 Distance입니다. 동일한 위치의 염기를 기준으로 서로 다른 염기의 개수를 카운팅하여 계산합니다.

3.5. Manhattan Distance

바둑판과 같은 격자 모양의 뉴욕 맨하탄 거리에서 어느 한 지점에서 다른 한 지점으로 자동차가 움직이는 거리로 다음과 같이 정의한다.

\( d(\vec{x}, \vec{y}) = \displaystyle{\sum^{k}_{i} |X_i - Y_i|} \)

4. Example 1 - admission

"admission.csv" 데이터는 다음과 같습니다.

admission.csv

    GPA GMAT       De
1  2.96  596    admit
2  3.14  473    admit
3  3.22  482    admit
4  3.29  527    admit
5  3.69  505    admit
6  3.46  693    admit
7  3.03  626    admit
8  3.19  663    admit
9  3.63  447    admit
10 3.59  588    admit
11 3.30  563    admit
12 3.40  553    admit
13 3.50  572    admit
14 3.78  591    admit
15 3.44  692    admit
16 3.48  528    admit
17 3.47  552    admit
18 3.35  520    admit
19 3.39  543    admit
20 3.28  523    admit
21 3.21  530    admit
22 3.58  564    admit
23 3.33  565    admit
24 3.40  431    admit
25 3.38  605    admit
26 3.26  664    admit
27 3.60  609    admit
28 3.37  559    admit
29 3.80  521    admit
30 3.76  646    admit
31 3.24  467    admit
32 2.54  446 notadmit
33 2.43  425 notadmit
34 2.20  474 notadmit
35 2.36  531 notadmit
36 2.57  542 notadmit
37 2.35  406 notadmit
38 2.51  412 notadmit
39 2.51  458 notadmit
40 2.36  399 notadmit
41 2.36  482 notadmit
42 2.66  420 notadmit
43 2.68  414 notadmit
44 2.48  533 notadmit
45 2.46  509 notadmit
46 2.63  504 notadmit
47 2.44  336 notadmit
48 2.13  408 notadmit
49 2.41  469 notadmit
50 2.55  538 notadmit
51 2.31  505 notadmit
52 2.41  489 notadmit
53 2.19  411 notadmit
54 2.35  321 notadmit
55 2.60  394 notadmit
56 2.55  528 notadmit
57 2.72  399 notadmit
58 2.85  381 notadmit
59 2.90  384 notadmit
60 2.86  494   border
61 2.85  496   border
62 3.14  419   border
63 3.28  371   border
64 2.89  447   border
65 3.15  313   border
66 3.50  402   border
67 2.89  485   border
68 2.80  444   border
69 3.13  416   border
70 3.01  471   border
71 2.79  490   border
72 2.89  431   border
73 2.91  446   border
74 2.75  546   border
75 2.73  467   border
76 3.12  463   border
77 3.08  440   border
78 3.03  419   border
79 3.00  509   border
80 3.03  438   border
81 3.05  399   border
82 2.85  483   border
83 3.01  453   border
84 3.03  414   border
85 3.04  446   border

우선 데이터를 예측해 보겠습니다. 입학허가(admission)에 대한 데이터인 만큼 GMAT과 GPA(평균학점)의 점수가 높을수록 입학할 가능성이 높을 것입니다. ggplot을 이용하여 이를 가시화하여 보겠습니다.

R CODE:

library("ggplot2");

admission <- read.csv("admission.csv");

p <- ggplot(admission, aes(GPA, GMAT));
p + aes(shape = factor(De)) +
  geom_point(aes(colour = factor(De)), size = 4) +
  geom_point(colour="grey90", size = 1.5);

그림에서 볼 수 있듯이 예상대로 GPA와 GMAT 점수가 모두 높을수록 합격이 많습니다. 이제 85개의 admission 데이터에 대하여 이 중 일부를 training set으로 입력해 보겠습니다.

R에서 k-NN을 지원해주는 패키지는 여러 종류가 있지만 classification에 대한 가장 대표적인 패키지인 class가 제공하는 k-NN을 사용해 보도록 하겠습니다. 이를 위해 class 패키지를 설치합니다.

> install.packages("class")

(1) class 패키지 라이브러리를 로딩합니다.

library(class);

(2) admission.csv 데이터를 로딩합니다.

admission <- read.csv("admission.csv");

(3) Dataset의 전체 데이터 수를 저장합니다.

# dataset의 전체 row 수
n.points <- dim(admission)[1];

(4) Training을 위한 데이터 샘플은 전체의 80%를 취합니다.

# sample은 전체 데이터 중 80%를 취한다.
sampling.rate <- 0.8;

(5) Test를 위한 데이터의 개수를 저장합니다.

# test 데이터 수는 나머지 20%가 된다.
num.test.set.labels <- n.points * (1 - sampling.rate);

(6) Training 데이터 샘플을 추출합니다.

# training 데이터 샘플을 랜덤으로 추출한다.
training <- sample(1:n.points, sampling.rate * n.points, replace=FALSE);
train <- subset(admission[training, ], select = c(GPA, GMAT));

(7) 이제 전체 데이터에서 추출된 training 데이터를 제외한 나머지 데이터가 test 데이터가 됩니다.

# 전체 데이터에서 training 데이터를 제외한 것을 test 데이터로 정의한다.
testing <- setdiff(1:n.points, training);
test <- subset(admission[testing, ], select = c(GPA, GMAT));

(8) Classification의 대상을 정의합니다.

# classification이 타겟을 정의한다.
cl <- admission$De[training];

(9) k-NN 알고리즘이 판단한 분류 결과를 평가하기 위해 test 데이터에 대한 실제 값을 저장해 둡니다.

# 실제 분류된 값을 저장해 둔다.
true.labels <- admission$De[testing];

(10) k값에 대한 최적값을 찾습니다. 최적의 k값은 k-NN 알고리즘을 통해 계산된 결과와 실제 값이 가장 많이 일치시키는 값을 의미합니다.

# 여러 개의 k값에 대하여 실행하여 최적의 k값을 찾는다.
minVal <- 10000;
kk = 0;
for (k in 1:20) {
  predicted.labels <- knn(train, test, cl, k);
  
  num.incorrect.labels <- sum(predicted.labels != true.labels);
  misclassification.rate <- num.incorrect.labels / num.test.set.labels;
  
  if(misclassification.rate < minVal) {
    minVal = misclassification.rate;
    kk <- k;
    print("k = ");
    print(k);
    print("misclassification.rate = ");
    print(misclassification.rate);
  }
  
}

이에 대한 결과는 다음과 같습니다(컴퓨터마다 또는 try마다 다를 수 있습니다):

[1] "k = "
[1] 1
[1] "misclassification.rate = "
[1] 0.4117647
[1] "k = "
[1] 4
[1] "misclassification.rate = "
[1] 0.3529412

k = 4일 때 misclassification rate가 가장 낮은 것을 알 수 있습니다. 따라서 k = 4를 선택합니다.

(11) k-NN 계산을 수행합니다.

# k-NN 알고리즘으로 계산된 결과를 저장한다.
result <- knn(train, test, cl, k = kk);

(12) 결과를 평가합니다.

vecResult <- as.vector(result);
vecValue <- as.vector(value);

cnt <- 0;
for(k in 1:length(result)) {
  print(vecResult[k]);
  print(vecValue[k]);
  print("");
  if(vecResult[k] == vecValue[k])
    cnt = cnt + 1;
}

vecResult는 k-NN에 의하여 계산된 값들에 대한 벡터이며, vecValue는 실제 classification 값입니다. 각 요소에 대하여 일치될 때마다 cnt 값을 1씩 증가시킵니다. 즉, cnt 값이 클수록 k-NN에 의한 값이 실제 값과 일치하는 수가 많은 것입니다.

Classification의 예측율은 다음과 같습니다:

cnt/length(result)

필자의 컴퓨터에서 계산된 결과는 0.7647059, 약 76.5%입니다.

5. Example 2 - wine

"wine.csv" 데이터를 통해 Example 1과 마찬가지로 방법으로 k-NN 예제를 공부해 보도록 합니다.

wine.csv

"wine.csv" 데이터는 다음과 같습니다:

> head(wine)
  Class Alcohol MalicAcid  Ash AlcalinityAsh Magnesium PhenolsTotal Flavanoids NonflavanoidPhenols
1     1   14.23      1.71 2.43          15.6       127         2.80       3.06                0.28
2     1   13.20      1.78 2.14          11.2       100         2.65       2.76                0.26
3     1   13.16      2.36 2.67          18.6       101         2.80       3.24                0.30
4     1   14.37      1.95 2.50          16.8       113         3.85       3.49                0.24
5     1   13.24      2.59 2.87          21.0       118         2.80       2.69                0.39
6     1   14.20      1.76 2.45          15.2       112         3.27       3.39                0.34
  Proanthocyanins Color  Hue OD280.OD315 Proline
1            2.29  5.64 1.04        3.92    1065
2            1.28  4.38 1.05        3.40    1050
3            2.81  5.68 1.03        3.17    1185
4            2.18  7.80 0.86        3.45    1480
5            1.82  4.32 1.04        2.93     735
6            1.97  6.75 1.05        2.85    1450

Example 2에 대한 전체 R 소스 코드는 다음과 같습니다:

R CODE:

library(class);

wine <- read.csv("wine.csv");

# number of rows in the dataset
n.points <- 178;
sampling.rate <- 0.8;

# we need the number of points in the test set to calculate
# the misclassification rate
num.test.set.labels <- n.points * (1 - sampling.rate);

# randomly sample which rows will go in the training set
training <- sample(1:n.points, sampling.rate * n.points, replace=FALSE);
train <- subset(wine[training, ], select = c(Alcohol, MalicAcid, Ash, AlcalinityAsh, Magnesium, PhenolsTotal, Flavanoids, NonflavanoidPhenols, Proanthocyanins, Color, Hue, OD280.OD315, Proline));

# define the training set to be those rows
# the other rows are going into the test set
testing <- setdiff(1:n.points, training);

# define the test set to be the other rows
test <- subset(wine[testing, ], select = c(Alcohol, MalicAcid, Ash, AlcalinityAsh, Magnesium, PhenolsTotal, Flavanoids, NonflavanoidPhenols, Proanthocyanins, Color, Hue, OD280.OD315, Proline));
cl <- wine$Class[training];

# this is the subset of labels for the training set
true.labels <- wine$Class[testing];

# subset of labels for the test set, we're withholding these
# we'll loop through and see what the misclassification rate
# is for different values of k
minVal <- 10000;
kk <- 0;
for (k in 1:20) {
  predicted.labels <- knn(train, test, cl, k);
  
  # We're using the R function knn()
  num.incorrect.labels <- sum(predicted.labels != true.labels);
  misclassification.rate <- num.incorrect.labels / num.test.set.labels;
  
  if(misclassification.rate < minVal) {
    minVal <- misclassification.rate;
    kk <- k;
    print(k);
    print(misclassification.rate);
  }
  
}

result <- knn(train, test, cl, k = kk);
value <- wine$Class[testing];

vecResult <- as.vector(as.numeric(result));
vecValue <- as.vector(value);

cnt = 0;
for(k in 1:length(result)) {
  print(abs(vecResult[k] - vecValue[k]));
  if(abs(vecResult[k] - vecValue[k]) == 0)
    cnt <- cnt + 1;
}

cnt/length(result)

데이터를 다운받아 이 코드로 테스트 해보기 바라겠습니다.