k-최근접 이웃(KNN) 알고리즘이란 무엇인가요?

KNN 알고리즘은 회귀 또는 분류 문제에 사용할 수 있지만, 일반적으로 유사한 점이 서로 근처에서 발견될 수 있다는 가정하에 작동하는 분류 알고리즘으로 사용됩니다.

분류 문제의 경우, 클래스 레이블은 과반수 투표에 기초하여 할당됩니다. 즉, 주어진 데이터 포인트 주변에서 가장 자주 표현되는 레이블이 사용됩니다. 이는 기술적으로 '다수결 투표(plurality voting)'로 간주되지만 '과반수 투표(majority vote)'라는 용어가 문헌에서 더 일반적으로 사용됩니다. 이러한 용어의 차이점은 '과반수 투표'는 기술적으로 50% 이상의 과반수가 필요하다는 것이며, 이는 주로 카테고리가 두 가지만 있을 때 작동합니다. 여러 클래스가 있는 경우, 예를 들어, 카테고리가 네 개일 때 반드시 50%의 득표가 있어야 클래스에 대한 결론을 내릴 수 있는 것은 아니며, 25% 이상의 득표로 클래스 레이블을 지정할 수 있습니다. 위스콘신대학교 매디슨(University of Wisconsin-Madison)은 여기에서 예시를 들어 이를 잘 요약해 보여 주고 있습니다.

회귀 문제는 분류 문제와 유사한 개념을 사용하지만, 이 경우 분류에 대한 예측을 하기 위해 k-최근접 이웃 평균을 사용합니다. 여기서 주요 차이점이라면, 분류는 불연속 값에 사용되는 반면 회귀는 연속 값에 사용된다는 것입니다. 그러나 분류를 하기 전에 거리를 정의해야 합니다. 가장 일반적으로 사용되는 유클리드 거리는 아래에서 더 자세히 살펴보겠습니다.

또한 KNN 알고리즘은 '지연 학습' 모델 제품군의 일부라는 점도 주목할 만합니다. 이는 학습 데이터 세트만 저장하고 학습 단계를 거치지 않는다는 것을 의미합니다. 이는 또한 분류 또는 예측이 이루어질 때 모든 계산이 이루어진다는 것을 의미합니다. 모든 학습 데이터를 저장하기 위해 메모리에 크게 의존하기 때문에 인스턴스 기반 또는 메모리 기반 학습 방법이라고도 합니다.

Evelyn Fix와 Joseph Hodges는 이 1951년 논문에서 KNN 모델에 대한 초기 아이디어를 제시했으며, Thomas Cover는 자신의 연구인 '최근접 이웃 패턴 분류(Nearest Neighbor Pattern Classification)에서 이 개념을 확장했습니다. 예전만큼 인기가 있지는 않지만, 그 단순성과 정확성이라는 장점으로 데이터 과학에서 배우는 첫 번째 알고리즘 중 하나입니다. 그러나 데이터 세트가 증가함에 따라 KNN의 효율성이 점점 더 저하되어 전체 모델 성능이 저하됩니다. 간단한 추천 시스템, 패턴 인식, 데이터 마이닝, 금융 시장 예측, 침입 탐지 등에 일반적으로 사용됩니다.

요약하자면, k-최근접 이웃 알고리즘의 목표는 주어진 쿼리 포인트의 가장 가까운 이웃을 식별하여 해당 포인에 클래스 레이블을 할당하는 것입니다. KNN에는 이를 수행하기 위한 몇 가지 요구 사항이 있습니다.

지정된 쿼리 포인트에 가장 가까운 데이터 포인트를 확인하려면 쿼리 포인트와 다른 데이터 포인트 사이의 거리를 계산해야 합니다. 이러한 거리 메트릭은 쿼리 포인트를 다른 지역으로 분할하는 결정 경계를 형성하도록 합니다. 일반적으로 Voronoi 다이어그램으로 시각화된 결정 경계를 볼 수 있습니다.

선택할 수 있는 몇 가지 거리 측정이 있지만, 이 문서에서는 다음과 같은 내용만 다룹니다.

유클리드 거리(p=2)(Euclidean distance): 이는 가장 일반적으로 사용되는 거리 측정이며 실수 값 벡터로 제한됩니다. 아래 공식을 사용하여 쿼리 포인트와 측정되는 다른 포인트 사이의 직선을 측정합니다.

맨해튼 거리(p=1)(Manhattan distance): 이는 인기 있는 또 다른 메트릭으로 두 지점 사이의 절댓값을 측정합니다. 택시 거리(taxicab distance) 또는 도시 블록 거리(city block distance)라고도 하며 일반적으로 그리드로 시각화되어 도시 거리를 통해 한 주소에서 다른 주소로 이동하는 방법을 보여 줍니다.

민코프스키 거리(Minkowski distance): 이 거리 측정은 유클리드 및 맨해튼 거리(Manhattan distance) 메트릭의 일반화된 형태입니다. 아래 공식에서 매개 변수 p를 사용하면 다른 거리 메트릭을 생성할 수 있습니다. 유클리드 거리는 p가 2이고 맨해튼 거리(Manhattan distance)는 p가 1인 경우 이 공식으로 나타냅니다.

해밍 거리(Hamming distance): 이 기술은 일반적으로 불리언(Boolean) 또는 문자열 벡터와 함께 사용되며 벡터가 일치하지 않는 포인트를 식별합니다. 그래서 중복 메트릭이라고도 합니다. 이는 다음 공식으로 나타낼 수 있습니다.

예를 들어, 다음과 같은 문자열이 있는 경우 두 값만 다르므로 해밍 거리는 2가 됩니다.

k-NN 알고리즘의 k 값은 특정 쿼리 포인트의 분류를 결정하기 위해 검사할 이웃의 수를 정의합니다. 예를 들어, k=1인 경우 인스턴스는 단일 최근접 이웃과 동일한 클래스에 할당됩니다.

값에 따라 과적합 또는 과소 적합이 발생할 수 있으므로 k를 정의하면 균형 잡힌 작업이 될 수 있습니다. k의 값이 작을수록 분산이 높을 수 있지만, 편향이 낮고 k 값이 클수록 편향이 높아지고 분산이 낮아질 수 있습니다. k의 선택은 주로 입력 데이터에 따라 달라지는데, 이상값 또는 잡음이 더 많은 데이터는 k 값이 높을수록 더 나은 성능을 발휘할 가능성이 높기 때문입니다. 전반적으로 분류에서 동점을 피하기 위해 k에 홀수를 사용하는 것이 권장되며, 교차 검증 전술은 데이터 세트에 대한 최적의 k를 선택하는 데 도움이 됩니다.

더 자세히 알아보고 싶다면 Python 및 scikit-learn(sklearn이라고도 함)을 사용해 k-NN 알고리즘을 자세히 알아볼 수 있습니다. Watson Studio의 튜토리얼은 이 라이브러리에서 기본 구문을 배울 수 있도록 도와줍니다. 이 라이브러리에는 NumPy, pandas 및 Matplotlib 같은 다른 인기 라이브러리도 포함되어 있습니다. 다음 코드는 KNN 모델을 통해 생성하고 예측하는 방법의 예시입니다.

k-NN 알고리즘은 다양한 응용 분야, 주로 분류에 활용되고 있습니다. 이러한 사용 사례 중 일부는 다음과 같습니다.

• 데이터 전처리: 데이터 세트에 누락된 값이 있는 경우가 많지만, KNN 알고리즘은 누락된 데이터 대입이라는 프로세스를 통해 이러한 값을 추정할 수 있습니다.
• 추천 엔진: 웹사이트의 클릭스트림 데이터를 사용하여 KNN 알고리즘을 통해 사용자에게 추가 콘텐츠를 자동으로 추천합니다. 이 연구는 사용자가 특정 그룹에 할당되고 해당 그룹의 사용자 행동에 따라 권장 사항이 제공된다는 것을 보여 줍니다. 그러나 KNN의 확장 문제를 감안할 때 이 접근 방식은 대규모 데이터 세트에 적합하지 않을 수 있습니다.
• 금융: 또한 다양한 금융 및 경제적 사용 사례에서 사용되고 있습니다. 예를 들어, 한 논문에서는 신용 데이터에 KNN을 활용하면 은행이 조직이나 개인에 대한 대출 위험을 평가할 때 어떤 도움을 얻을 수 있는지 보여 줍니다. 이는 대출 신청자의 신용도를 판단하는 데 사용됩니다. 또 다른 학술지는 주식 시장 예측, 환율, 선물 거래 및 자금 세탁 분석에서의 활용을 강조합니다.
  
  
• 의료: KNN은 의료 산업에도 적용되어 심장 마비와 전립선 암 등의 위험도를 예측하는데 활용됩니다. 알고리즘은 가장 가능성이 높은 유전자 발현을 계산하는 방식으로 작동합니다.
• 패턴 인식: KNN은 텍스트 및 숫자 분류 같은 패턴을 식별하는 데에도 도움이 됩니다. 이 기능은 특히 양식이나 우편 봉투에서 발견할 수 있는 필기된 숫자를 식별하는 데 유용합니다. 

다른 머신 러닝 알고리즘과 마찬가지로 k-NN에도 장단점이 있습니다. k-NN은 프로젝트와 애플리케이션에 따라 올바른 선택이 될 수도 있고 그렇지 않을 수도 있습니다.

• - 구현 용이성: k-NN은 알고리즘의 단순성과 정확성 덕분에 신임 데이터 과학자가 배우게 될 첫 번째 분류자 중 하나입니다.
  
  
• 적응성: 새로운 학습 샘플이 추가되면 모든 학습 데이터가 메모리에 저장되므로 알고리즘이 새로운 데이터를 고려하도록 조정됩니다.
• 소수의 하이퍼파라미터: KNN은 k 값과 거리 메트릭만 필요하며, 이는 다른 머신 러닝 알고리즘과 비교해 낮습니다.

• 확장성 부족: KNN은 지연 알고리즘이기 때문에 다른 분류자에 비해 더 많은 메모리와 데이터 스토리지를 차지합니다. 이로 인해 시간과 비용 측면에서 모두 손실이 클 수 있습니다. 더 많은 메모리와 스토리지는 비즈니스 비용을 증가시키며 데이터가 많아지면 계산 시간이 오래 걸릴 수 있습니다. 계산 비효율성을 해결하기 위해 Ball-Tree와 같은 다양한 데이터 구조가 만들어졌지만, 비즈니스 문제에 따라 다른 분류자 이상적일 수 있습니다.
• 차원의 저주(Curse of dimensionality): KNN 알고리즘은 차원의 저주의 희생양이 되는 경향이 있는데, 이는 고차원 데이터 입력에서 잘 수행되지 않는다는 것을 의미합니다. 이를 피킹 현상이라고도 하는데, 알고리즘이 최적의 특징 수에 도달한 후 추가적인 특징으로 인해 분류 오류의 양이 늘어나는 것으로, 특히 표본 크기가 작을 때 그렇습니다.
• 과적합에 취약: '차원의 저주'로 인해 KNN은 과적합에 더 취약합니다. 이러한 현상을 방지하기 위해 기능 선택 및 차원 축소 기술이 활용되지만, k 값도 모델의 동작에 영향을 줄 수 있습니다. k의 값이 낮으면 데이터가 과적합될 수 있는 반면, k의 값이 높을수록 더 넓은 면적 또는 이웃에 대한 값의 평균을 구하기 때문에 예측 값이 '평활화'되는 경향이 있습니다. 그러나 k의 값이 너무 높으면 데이터가 과소 적합될 수 있습니다.