kNN(k-최근접 이웃)과 이웃처럼 지내보기

• 데이터 분류에 사용되는 아주 간단한 지도학습 알고리즘
• 상대적으로 이해하기 쉽지만, 다른 알고리즘에 비해서 연산 속도가 느리다.

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

---

• 핵심은 '이웃'
  • 이웃은 나와 가까운 거리에 사는 사람들을 뜻함
  • 알고리즘에서 이웃이란 가까이 존재하는 데이터들을 의미
  • 따라서 kNN 알고리즘이란 현재 데이터를 특정값으로 분류하기 위해 기존 데이터 안에서 현재 데이터로부터 가까운 k개의 데이터를 찾아 k개의 레이블 중 가장 많이 분류된 값으로 현재의 데이터를 분류하는 알고리즘
• 예시
  • 만약 서울 어딘가에 데려다 놓고 이곳이 강남인지 강북인지 알려면?
  • 주변에 보이는 가까운 사람들에게 똑같은 질문을 던져서 많은 답을 얻은 쪽으로 대답하는 한다.
  • 주변 5명에게 물어 4명이 강남, 1명이 강북이라고 대답했다면 지금 현재 위치는 강남으로 분류하는 것
  • 다섯 명에게 물었기 때문에 k=5인 kNN 알고리즘을 사용한 것.
  • 즉, kNN 알고리즘의 k는 몇 개의 이웃을 살펴볼 것인지 나타내는 변수이고, NN이란 현재 알고자 하는 데이터로부터 근접한 데이터를 의미.
  • 강남/강북 문제와 같은 이진 분류를 할 때는 과반수의 대답을 얻기 위해 k를 홀수로 지정하는 것이 좋다.

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

kNN 알고리즘을 포함한 대다수의 머신러닝 알고리즘에서 사용되는 공간이라는 개념은 사실 벡터 공간을 의미한다.

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

kNN 알고리즘은 k(탐색할 이웃의 개수)에 따라 데이터를 다르게 예측할 수도 있다.

• 보통 k는 1로 설정하지 않음.
  • 그 이유는 하나의 이웃으로 현재 데이터를 판단하기에는 정보가 너무 한쪽으로 편향돼 있기 때문.
• k는 보통 홀수로 설정한다.
  • 그 이유는 k가 짝수일 경우 과반수 이상의 이웃이 나오지 않을 수 있기 때문.

최적의 k를 찾기 위해서는 보통 검증 데이터를 통해 가장 정확도가 높은 k를 알고리즘의 k로 선정한다.

다중 분류

---

• 이진 분류(binary classification) : 두 가지 중 하나를 분류하는 경우
• 다중 분류(multiclass classification) : 여러 개의 가능한 레이블 중 하나로 분류하는 경우

kNN 알고리즘은 다중 분류에도 활용이 가능하다!

kNN 알고리즘의 수학적 이해

---

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

• 점과 점 사이의 거리를 구하는 법
  • 피타고라스의 정리

kNN 알고리즘의 장점과 단점

---

장점

1. 다른 머신러닝 알고리즘보다 이해하기가 상당히 쉽다.
   • 수학적으로 거리를 계산하는 방법만 알면 이해하기 쉽다.
2. 숫자로 구분된 속성에 우수한 성능을 보인다.
   • 거리, 횟수, 점수와 같이 수치화된 데이터
3. 별도의 모델 학습이 필요없다.
   • 이러한 특성을 게으른 학습(lazy learning)이라고 한다.
   • 게으른 학습은 데이터베이스의 실시간 데이터를 사용해야 할 때 유용하다.

단점

1. 예측 속도가 느리다.
   • 예측할 때마다 전체 데이터와의 거리를 계산하기 때문
   • 비교할 속성이 많아질수록 연산 속도는 더 느려진다.
2. 다른 머신러닝 알고리즘에 비해 예측값이 지역 정보에 많이 편향될 수 있다.
   • 다른 머신러닝 알고리즘은 예측값이 기존의 전체 데이터에서 학습된 모델에서 나온다.
   • kNN 알고리즘은 오직 가까운 이웃을 통해 예측한다.
   • 아무리 좋은 데이터를 가지고 있더라도 k의 개수가 적거나 몇 개의 예외적인 데이터가 이웃으로 존재할 경우 예측값이 틀릴 가능성이 높아진다.

결론

---

k-최근접 이웃 알고리즘과 조금은 친해졌다!

이제는 이웃사촌까지는 아니어도 이웃이라고는 할 수 있지 않을까?

친구 따라 강남 간다는 옛 성현들의 지혜를 다시 한번 되새기면서 오늘의 블로그 글을 마친다.

실습

---

• 2017 NBA 농구선수 데이터를 활용해 선수의 포지션을 예측해봤다.
• 코드 보러 가기

참고자료

• 책) 나의 첫 머신러닝 딥러닝
• https://www.youtube.com/watch?v=0nqvO3AM2Vw&feature=youtu.be
• http://aikorea.org/cs231n/classification/