k-NN (k-Nearest Neighbors) 알고리즘은 지도 학습 알고리즘의 일종으로, 이미 특정한 항목 (라벨)로 분류되어 있는 데이터들을 가지고 아직 분류되지 않은 새로운 데이터를 자동으로 분류하는 알고리즘이다.
이 알고리즘은 회귀 (Regression)보다는 분류 (Classification)라고 볼 수 있다. 회귀의 경우에는 연속된 데이터에 관해서 다음 데이터의 값을 예측하고, 따라서 예측 결과는 연속변수 (continuous variable)이 될 것이다. 하지만 이 경우에는 불연속적인 데이터들의 집합에 대해서 분류를 수행하고, 예측 결과는 카테고리 라벨이 될 것이므로 분류가 적합하다.
(허나 회귀 알고리즘과 분류 알고리즘은 완전히 용도가 구별된 것이 아니다. 예를 들어 선형회귀를 이용해 경계면을 만드는 방식으로 분류를 할 수도 있고, k-NN을 이용해 회귀를 할 수도 있다.)
이미 분류되어 있는 기존 데이터셋이 있을 때, 아직 분류되지 않은 새로운 데이터가 들어온다고 하자. 그때 이미 분류된 데이터셋에서 새로운 데이터와 가장 유사한 k개의 데이터를 뽑아서 그 데이터들의 분류를 살펴본다. 그리고 그들 중 다수결로 새로운 분류를 결정하게 된다.
이에 대해 생각해 볼 요소는 크게 두가지인데, 첫번째는 유사한 데이터란 것을 어떻게 판단할지, 즉 **유사도 (혹은 근접성)**를 측정하는 기준이고, 두번째는 몇개의 유사 데이터를 뽑아서 투표하게 할 것인지, 즉 k가 몇인지이다. 한번 예제를 통해서 자세히 알아보도록 하자.
친한 친구와 안친한 친구를 분류한다고 치자. 우리에게는 각각의 친구에 대해 페북 메세지를 주고받은 횟수와 서로의 페북 게시글에 댓글을 단 횟수가 있고, 이 친구가 친한지, 친하지 않은지 분류해 놓았다.
이때 이 목록에 없는 또다른 새로운 친구인 준성이와 친한지 안친한지를 알아보고 싶다. 이때 k-NN 알고리즘을 통해서 알아볼 수 있다!
첫번째로, 위 기존 친구 데이터와 준성이의 데이터를 한번 그래프로 나타내 보자.
저 물음표는 준성이이며, 아직 친한지 안친한지 모르는 상태이다. 이를 대체 어떻게 알 수 있는가?
한번 그래프를 잘 보면 친한 친구와 친하지 않은 친구가 군집화되어있음을 볼 수가 있다. 따라서, 준성이와 다른 친구들간의 거리를 계산해서 준성이 주변에 있는 친구의 분류를 보면 그에 따라 준성이의 분류를 예측할 수 있을 것이다.
이것은 모든 친구들과 준성이간의 거리를 계산한 것이며, 이제 이를 오름차순 정렬하여 준성이와 가장 가까운 (즉, 유사한) k개의 친구를 찾을 것이다.
k=3이라고 하면 가장 가까운 친구 3명은 친한 김철수, 안친한 이민수, 친한 박길동이다. 다수결에 따라서 분류를 선정하면 2:1로 "친한" 분류가 이겼으므로, 준성이는 친한 친구라고 예측할 수 있다. k-NN 알고리즘은 이런 방식으로 동작한다.
위에서 설명한 두가지 생각해볼 요소를 다시 떠올려보자. 이 예제에서는 유사도 (근접성), 즉 데이터간의 거리가 이미 계산되어 있지만, 이를 계산하는 척도는 여럿을 생각해볼 수 있다.
가장 흔하게 생각할 수 있는것은 **유클리드 거리 (Euclidean Distance)**이며, 이는 다음과 같다.
이외에도 흔하게 쓰이는 것에는 *코사인 유사도 (Cosine Similarity)*나 자카드 거리 Jaccard Distance, 맨해튼 거리 (Manhattan Distance), 해밍 거리 (Hamming Distance) 등 많은 척도들이 있으며, 데이터의 종류와 상황에 따라 알맞은 상황을 선택해야 한다.
파이썬을 이용해서 직접 수행해보도록 하자. Machine Learning In Action 책 2단원의 코드를 사용했다.
먼저, 미리 알고리즘이 작성된 k-NN 모듈을 임포트한다. 자세한 구현은 해당 책에 나와 있으며 여기선 위의 알고리즘 원리로 대체하고 생략한다.
import knn as kNN이제 샘플 데이터세트를 로딩한다.
group, labels = kNN.createDataSet()데이터세트에 무엇이 들어있을까? mathplot 라이브러리를 이용해 그래프화할 수 있다.
import matplotlib
import matplotlib.pyplot as plt
from numpy import array
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(group[:, 1], group[: 2])
plt.show()
위와 같은 분포를 가짐을 볼 수 있다.
또한 이 데이터에 대한 분류는 다음과 같이 되어 있다.
>>> labels
['A', 'A', 'B', 'B']이제 새로운 벡터 [0, 0]에 대한 분류를 수행해보자.
>>> kNN.classify0([0, 0], group, labels, 3)
'B'그럼 한번 더 복잡한 데이터로... datingTestSet.txt의 정보를 로딩해 그래프상에 배치해보자.
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet.txt')
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2])
plt.show()
이제, 이 데이터를 이용해서 우리가 만든 분류기의 **참부정률 (오류율)**을 측정해 볼 수 있다.
현재 데이터, 즉 참인 데이터의 90%정도만 학습에 사용하고, 10%를 검증 데이터세트로 사용해 분류기에 돌려서 참이 나오는지 체크한다. 이때 검증 데이터셋과 비교해 불일치라면 실제로는 참인 데이터를 다르게 분류한 것이므로, 오류인 것이다.
이런 방식으로 분류기를 검증해보고 오류율을 측정해볼 수 있다.
>>> kNN.datingClassTest()
The total error rate is: 0.064%
The error count is 32
에러 카운트가 32라는 말은, 32개의 (실제) 데이터를 분류기가 잘못 분류했다는 뜻이다.