k-최근접 이웃 알고리즘

k-최근접 이웃(kNN) 알고리즘은 데이터 분류에 사용되는 아주 간단한 지도학습 알고리즘입니다. 지도학습이나 데이터 분류라는 이 두 개념에 익숙지 않다면 이론을 시작하기에 앞서 두 개념의 정의를 다시 한번 살펴봅시다. 

• 지도학습: 머신러닝 학습 시 데이터와 함께 데이터에 대한 레이블(정답)을 함께 부여하는 학습 방식
• 데이터 분류: 새로운 데이터를 기존 데이터의 레이블 중 하나로 분류하는 작업 

지도학습 데이터 분류의 대표적인 예로 손글씨 숫자를 인식하는 머신러닝 모델이 있습니다. 숫자 인식 모델을 학습시킬 때 학습할 데이터와 함께 그 데이터가 무슨 숫자를 의미하는지 명시적인 레이블과 함께 학습을 시킵니다. 학습이 완료된 모델은 입력된 손글씨 숫자에 대해 분류를 진행하는데, 이 분류값은 학습에 사용됐던 기존 데이터들의 레이블 중 하나에 해당합니다. 이번 주제인 KNN 알고리즘은 모든 지도학습 데이터 분류 예제에 활용될 수 있는 기술이니 차근차근 알아보겠습니다. 

kNN 알고리즘은 상대적으로 이해하기 쉽다는 장점이 있지만, 다른 알고리즘에 비해서 연산 속도가 느리다는 단점이 있습니다. 이러한 장단점 및 특징은 아래 이론 부분에서 차근차근 알아보겠습니다. 

k-최근접 이웃 알고리즘(kNN)의 이해

k-최근접 이웃 알고리즘은 이름에서 알 수 있듯이 핵심은 이웃입니다. 이웃이 나와 가까운 거리에 사는 사람들을 뜻하듯이 이 알고리즘에서 이웃이란 가까이 존재하는 데이터들을 의미합니다. 따라서 KNN 알고리즘이란 현재 데이터를 특정값으로 분류하기 위해 기존의 데이터 안에서 현재 데이터로부터 가까운 k개의 데이터를 찾아 k개의 레이블 중 가장 많이 분류된 값으로 현재의 데이터를 분류하는 알고리즘입니다. 

실생활에서 KNN 알고리즘의 예를 찾아보겠습니다. 만약 여러분을 서울 어딘가에 데려다 놓고, ’이곳이 강남일까요. 강북일까요?’라고 물어보면 어떻게 현재의 위치를 알 수 있을까요? 한 가지 방법은 주변에 보이는 가까운 사람들에게 똑같은 질문을 던져서 많은 답을 얻은 쪽으로 대답하는 것입니다. 가령 주변에 5명이 있다고 가정할 경우 4명이 강남이라고 대답했고 1명이 강북이라고 대답했다면 현재 위치가 강남이라고 예측할 수 있습니다. 바로 이 방법이 kNN 알고리즘입니다. 

위의 사례에서는 5명의 주변 사람들에게 물어봤기 때문에 k = 5인 kNN 알고리즘을 사용한 것입니다. 즉, KNN 알고리즘의 k는 몇 개의 이웃을 살펴볼 것인지를 나타내는 변수이고, NN(Nearest Neighbor)이란 현재 알고자 하는 데이터로부터 근접한 데이터를 의미합니다. 

kNN 알고리즘 관점으로 본다면 우린 방금 테스트 데이터(현재 자신의 위치)로부터 가까운 5개의 기존 (이웃) 데이터들을 찾아 3개 이상 대답된 레이블(강남)로 테스트 데이터를 분류했습니다. 참고로 강남/강북 문제와 같은 이진 분류를 할 때는 과반수의 대답을 얻기 위해 k를 홀수로 지정하는 것이 좋습니다. 

방금 살펴본 강남, 강북 예제는 실제로 나와 주변 사람까지의 거리를 잴 수 있기 때문에 최근접 이웃을 찾는 과정이 어렵지 않았습니다. 하지만 위치(현실 공간) 데이터가 없는 예측 분류 문제에는 어떻게 kNN 알고리즘을 적용할 수 있을까요? 

kNN 알고리즘을 포함한 대다수의 머신러닝 알고리즘에서 사용되는 공간이란 개념은 사실 벡터 공간을 의미합니다. 이 시점에서 우리가 사는 현실 공간과 벡터 공간을 확실히 구분하고 이해하는 것이 좋겠습니다. 

• 현실 공간: 평면 이동 및 수직 이동이 가능한 3차원 공간
• 벡터 공간: 벡터 연산이 가능한 N차원 공간 

사실 머신러닝에서의 공간은 벡터 공간이며, 우리가 살고 있는 공간보다 더 포괄적인 개념이기 때문에 특별히 현실 공간의 데이터(위도, 경도)가 없어도 데이터의 특성을 벡터 공간의 축으로 지정해서 데이터 간의 거리를 계산할 수 있습니다. 좀 더 쉽게 이해하기 위해 예제를 보겠습니다. 농구선수의 3점 슛 성공 횟수와 블로킹 성공 횟수 정보를 이용해 임의의 농구선수의 포지션이 센터인지 슈팅가드인지 예측해 봅시다. 

표는 농구선수들의 게임 기록 데이터이며, 이미 포지션을 알고 있는 선수 데이터는 이웃 데이터로 활용하고, 포지션을 모르는 홍길동 선수에 대해 KNN 알고리즘을 활용해 포지션을 예측해 보겠습니다. 

선수 데이터 중에서 3점 슛 성공 횟수를 벡터 공간의 x축으로, 블로킹 성공 횟수를 y축으로 나타내어 각 선수들을 2차원 벡터 공간에 시각화하면 그림과 같습니다. 세모는 포지션이 센터인 농구선수를, 동그라미는 포지션이 슈팅가드인 농구선수를 의미하며, 별로 표시된 데 이터가 바로 우리가 포지션을 예측할 선수(홍길동)의 데이터입니다. 

이제 KNN 알고리즘을 사용해서 3점 슛 성공 횟수와 블로킹 성공 횟수만을 사용해 홍길동 선수의 포지션이 슈팅가드인지 센터인지 예측해 보겠습니다. 이번 예제에서 이웃이란 이미 포 지션을 알고 있는 선수들을 의미하며, k는 예측을 위해 몇 명의 선수 포지션을 참조할 것인지를 의미합니다. 

이제 KNN 알고리즘의 k를 조정해가며 예측값을 비교해 보겠습니다. 제일 먼저 k가 1일 경우, 즉 홍길동 선수로부터 가장 가까운 농구선수 데이터 1개를 찾아 그와 동일한 선수 포지션으로 홍길동의 포지션을 예측해 보겠습니다. k가 1일 경우의 kNN 알고리즘은 홍길동의 선수 포지션을 무엇으로 분류할까요? 

그림에서 볼 수 있듯이 (5,4) 좌표에 위치한 홍길동 선수로부터 가장 가까운 이웃은 (4,4)에 위치한 센터 포지션의 김윤석 선수이므로 kNN 알고리즘은 홍길동 선수를 센터로 분류합니다. k가 5일 경우의 kNN 알고리즘은 홍길동 선수를 무슨 포지션으로 분류할까요? 

그림에서 볼 수 있듯이 3점 슛과 블로킹 횟수를 기준으로 홍길동 선수와 비슷한 패턴(이웃)을 보이는 5명의 농구선수 포지션 중 3개는 슈팅가드, 2개는 센터이므로 kNN 알고리즘은 홍길동 선수를 이웃이 더 많은 슈팅가드로 분류합니다. 

그렇다면 k가 9일 경우의 kNN 알고리즘은 홍길동 선수의 포지션을 무엇으로 분류할까요? 

그림에서 볼 수 있듯이 9개의 이웃 포지션 중 6개는 슈팅가드, 3개는 센터이므로 kNN 알고리즘은 홍길동 선수의 포지션을 슈팅가드로 분류합니다. 

이처럼 kNN 알고리즘은 k(탐색할 이웃의 개수)에 따라 데이터를 다르게 예측할 수도 있습니다. 보통 k는 1로 설정하지 않는데, 그 이유는 하나의 이웃으로 현재의 데이터를 판단하기에는 정보가 너무 한쪽으로 편향돼 있기 때문입니다. 그리고 k는 보통 홀수로 설정하는데, 그 이유는 k가 짝수일 경우 과반수 이상의 이웃이 나오지 않을 수 있기 때문입니다. 예를 들면, k =4일 때 가까운 4개의 이웃이 2개의 슈팅가드와 2개의 센터일 경우 동률이기 때문에 어느 하나의 포지션이라고 예측하기 어려워집니다. 

최적의 k를 찾기 위해서는 보통 검증 데이터를 통해 가장 정확도가 높은 k를 kNN 알고리즘의 k로 선정합니다. 최적의 k를 찾는 과정은 실습 과정에서 좀 더 구체적으로 다루겠습니다. 

다중 분류 

분류는 보통 이진 분류(binary classification)와 다중 분류(multiclass classification)로 나뉩니다. 위에서 다뤄본 예제처럼 두 가지 중 하나를 분류하는 경우를 이진 분류라고 합니다. 다중 분류는 여러 개의 가능한 레이블 중 하나로 분류하는 경우입니다. 

이진 분류	다중 분류
악성 코드 분류(일반 파일 또는 악성 코드)	임의의 손글씨 숫자가 입력됐을 때 1에서 9 중 가장 가까운 숫자로 분류하는 모델
위조 지폐 분류(일반 지폐 또는 위조 지폐)	서울의 도시가 입력됐을 때 강동, 강서, 강남, 강북 중 한 곳으로 도시를 분류하는 모델
문장에서 사람의 감정을 분류할 때 행복 또는 슬픔으 로만 분류하는 모델	문장에서 사람의 감정을 분류할 때 행복, 슬픔, 화남으 로 분류하는 모델

KNN 알고리즘은 다중 분류에도 탁월한 성능을 보입니다. 예를 들어, 서울의 강동, 강서, 강남, 강북을 2차원 공간에 표시하면 그림 4.2.5와 같습니다. 

임의의 지점을 입력받아 그곳이 강동, 강서, 강남, 강북 중 한 곳으로 분류하는 문제를 kNN(k=7)인 모델로 분류할 경우 아래와 같이 나타낼 수 있습니다. 

입력이 (3,4) 위치에 있을 때 총 7개의 이웃 중 강서가 4개의 이웃으로 과반수를 차지하므로 KNN은 입력된 위치가 강서라고 분류하게 됩니다. 이처럼 kNN은 이진 분류뿐 아니라 다중 분류에서도 활용 가능한 알고리즘입니다. 

kNN 알고리즘의 수학적 이해 

앞의 예제에서 볼 수 있듯이 kNN 알고리즘은 데이터의 속성으로 만들어진 벡터 공간 속에서 새로운 데이터와 기존 데이터와의 거리를 계산해서 가장 가까운 이웃부터 먼 이웃까지 판단한 후 가장 가까운 이웃부터 두 번째로 가까운 이웃, k번째로 가까운 이웃의 레이블을 측정해서 가장 많이 측정된 레이블로 새로운 데이터를 분류하는 알고리즘입니다. 

앞서 다룬 농구선수 분류 예제에서 3점 슛 성공 횟수와 블로킹이라는 두 가지 속성을 사용한 공간 속에서 최근접 이웃을 찾았습니다. 두 가지 속성이므로 벡터 공간에서 두 가지 속성은 2차원 공간에 나타낼 수 있습니다. 그럼 2차원 공간에서의 거리는 어떻게 구할 수 있을까요? 학교에서 배운 피타고라스의 정리를 여기에 적용할 수 있습니다. 

그림 4.2.7에서 별과 동그라미 사이의 거리는 3점 슛 성공 횟수의 차이를 제곱한 값과 블로킹 성공 횟수의 차이를 제곱한 값을 더한 값에 루트를 취한 값으로 구할 수 있습니다. 

같은 방법으로 속성이 3개인 경우를 알아보겠습니다. 이번에는 농구선수 게임 데이터에서 3점 슛 성공 횟수, 블로킹 성공 횟수, 리바운드 성공 횟수의 데이터를 찾아 각 속성을 좌표축으로 두고 데이터를 위치시켜 봅시다. 거리를 비교하려는 두 데이터가 있을 때 3점 슛 성공 횟수의 차이를 x1, 블로킹 성공 횟수 차이를 72, 리바운드 성공 횟수 차이를 3이라고 할 경우 두 데이터의 거리 y는 다음과 같은 공식으로 계산할 수 있습니다. 

속성이 3개가 넘는 경우에도 마찬가지입니다. 단 속성이 3개가 넘을 때부터는 사람의 눈이 3차원 이상을 볼 수 없다는 한계로 시각화가 불가능할 뿐입니다. 하지만 3차원이 넘는 벡터 공간을 시각화할 수 없을 뿐이지 거리 계산은 여전히 가능합니다. 머신러닝에서 사용되는 벡터 공간에서는 3차원을 넘는 N차원(N개의 속성) 공간에서도 거리를 계산하는 방법은 동일합니다. 

예를 들어, 농구선수 데이터에 총 5개의 속성이 있다고 가정해 보겠습니다. 시각화할 수는 없지만 이 5차원 벡터 공간에서의 두 데이터의 거리는 다음과 같이 구할 수 있습니다. 

kNN 알고리즘의 장점과 단점

지금까지 KNN 알고리즘에 대해 알아봤습니다. 실습하기에 앞서 마지막으로 이 알고리즘의 장점과 단점을 간략히 정리해보겠습니다. 먼저 장점은 다음과 같습니다. 

첫째, kNN 알고리즘은 다른 머신러닝 알고리즘보다 이해하기가 상당히 쉽습니다. 다른 알고리즘은 미적분, 확률 및 정보 이론 등의 기본 지식이 필요한데 비해 kNN 알고리즘은 수학적으로 거리를 계산하는 방법만 알면 이해하기가 쉽습니다. 

둘째, 숫자로 구분된 속성에 우수한 성능을 보입니다. 거리, 횟수, 점수와 같이 수치화된 데이터에 대해서는 거리 기반 머신러닝 알고리즘인 kNN 알고리즘을 사용하면 높은 정확도를 기대할 수 있습니다. 

셋째, 별도의 모델 학습이 필요 없습니다. kNN 알고리즘은 예측을 하는 시점에서 모든 기존 데이터와의 거리를 계산하기 때문에 예측 전에 모델을 따로 학습시킬 필요가 없습니다. 이러한 특성을 게으른 학습(lazy learning)이라고도 합니다. 게으른 학습은 데이터베이스의 실시간 데이터를 사용해야 할 때 유용하게 쓰입니다. 

반면 단점은 다음과 같습니다.

첫째, 예측 속도가 느립니다. 하나의 데이터를 예측할 때마다 전체 데이터와의 거리를 계산하기 때문에 연산 속도가 다른 알고리즘에 비해 느립니다. 비교할 속성이 많아질수록 연산 속도는 더 느려집니다.

둘째, 다른 머신러닝 알고리즘에 비해 예측값이 지역 정보에 많이 편향될 수 있습니다. 이는 다른 머신러닝 알고리즘은 예측값이 기존의 전체 데이터에서 학습된 모델에서 나오는 반면 kNN 알고리즘은 오직 가까운 이웃을 통해 예측하기 때문입니다. 아무리 양적으로나 질적으로나 좋은 데이터를 가지고 있더라도 KNN 알고리즘에서는 k의 개수가 적거나 몇 개의 예외적인 데이터가 이웃으로 존재할 경우 예측값이 틀릴 가능성이 높아집니다.