K-최근접 이웃 알고리즘

3. 특징

k-NN은 구현이 쉽고 이해하기 쉬운 간단하고 직관적인 알고리즘이다. 알고리즘의 훈련 단계는 훈련 샘플의 특징 벡터와 클래스 레이블을 저장하는 것으로만 구성되어 별도의 훈련 과정이 필요하지 않으므로 새로운 데이터에 대한 적응이 빠르다.^[26] 하지만, 다량의 훈련 집합에 대해 많은 계산량을 요구하므로, 데이터가 많아질수록 계산량이 급격히 증가하는 단점이 있다. 적절한 최근접 이웃 탐색 알고리즘을 사용하면 다량의 데이터 집합에 대해서도 k-NN 계산이 가능하도록 할 수 있다.^[35]

"과반수 의결"에 따른 분류의 단점은 항목 분포가 편향될 때 나타난다. 더 빈번한 항목의 데이터가 새로운 데이터의 예측을 지배하는 경향이 있는데, 이 문제를 해결하는 한 가지 방법은 검증점과 k개의 최근접 이웃 각각의 거리를 고려하여 분류에 가중치를 주는 것이다.^[30]

k-NN은 매우 일관성 있는 결과를 도출한다. 이 알고리즘은 데이터의 수가 무한대로 증가할수록 오차율이 베이즈 오차율(주어진 데이터의 분포에서 달성할 수 있는 최소 오차율)의 두 배보다 항상 나쁘지 않음을 보장한다.^[36]

4. 차원 축소

k-NN 알고리즘은 고차원 데이터에서 차원의 저주로 인해 성능이 저하될 수 있다.^[38] 이는 고차원에서 유클리드 거리가 유용하지 않기 때문이다. 모든 벡터가 탐색 질의 벡터와 대부분 같은 거리를 갖게 되어, 탐색 공간에서 질의 점과 모든 데이터 점 사이의 거리가 거의 같아지기 때문이다.^[17]

이러한 문제를 해결하기 위해 k-NN 알고리즘을 사용하기 전에 차원 축소를 수행하는 것이 일반적이다. 특징 추출과 차원 축소는 주성분 분석(PCA), 선형 판별 분석(LDA), 또는 정준 상관 분석(CCA) 기법을 전처리 과정으로 사용하여 한 단계로 결합할 수 있다. 그 후 축소된 차원 공간에서 k-NN을 사용하여 군집화를 수행할 수 있다. 기계 학습에서 이 과정을 저차원 매장이라 부른다.^[39] k-NN 맥락에서 차원의 저주는 기본적으로 고차원에서는 모든 벡터가 검색 쿼리 벡터와 거의 등거리에 있기 때문에 유클리드 거리가 유용하지 않다는 것을 의미한다.

5. 데이터 축소

6. 통계적 설정

훈련 데이터 집합의 크기가 무한대로 접근함에 따라, 1-최근접 이웃 분류기(k=1)는 베이즈 오류율(데이터의 분포가 주어졌을 때 달성 가능한 최소 오류율)의 두 배보다 나쁘지 않은 오류율을 보장한다.^[29]

7. 가중 최근접 이웃 분류기

k-최근접 이웃 분류기는 k개의 가장 가까운 이웃에게 1/k의 가중치를 주고, 나머지 모든 이웃에게는 0의 가중치를 주는 방식으로 볼 수 있다.^[9] 이는 가중 최근접 이웃 분류기로 일반화할 수 있는데, 이 경우 i번째로 가까운 이웃에게 ${\displaystyle w_{ni}}$의 가중치를 할당하며, ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$이다. 가중 최근접 이웃 분류기의 강한 일관성에 대한 유사한 결과도 성립한다.^[9]

${\displaystyle C_{n}^{wnn}}$을 가중치 ${\displaystyle \{w_{ni}\}_{i=1}^{n}}$를 갖는 가중 최근접 이웃 분류기라고 하자. 클래스 분포에 대한 규칙성 조건 하에서, 과잉 위험은 다음과 같은 점근적 전개를 가진다.

:${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$

여기서 상수 ${\displaystyle B_{1}}$과 ${\displaystyle B_{2}}$에 대해 ${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$이고 ${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$이다.

최적 가중치 체계 ${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$는 위 식의 두 항을 균형있게 조정하여 다음과 같이 주어진다. ${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$로 설정하고,

:${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$ (${\displaystyle i=1,2,\dots ,k^{*}}$에 대해) 그리고

:${\displaystyle w_{ni}^{*}=0}$ (${\displaystyle i=k^{*}+1,\dots ,n}$에 대해).

최적 가중치를 사용하면 과잉 위험의 점근적 전개에서 주요 항은 ${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$가 된다. 배깅된 최근접 이웃 분류기를 사용할 때도 유사한 결과가 나타난다.

8. 오류율

k-최근접 이웃 분류기의 오류율에 대한 많은 연구 결과가 있다.^[15] k-최근접 이웃 분류기는 $k:=k\_n$이 발산하고 $k\_n/n$이 $n\; \backslash to\; \backslash infty$일 때 0으로 수렴하는 조건에서 강하게(즉, $(X,\; Y)$에 대한 모든 결합 분포에 대해) 일치한다.

크기가 $n$인 훈련 집합을 기반으로 하는 k-최근접 이웃 분류기를 $C\_n^\{knn\}$이라고 하자. 특정 규칙성 조건 하에서 초과 위험은 다음과 같은 점근적 전개를 제공한다.^[16]

:$$\backslash mathcal\{R\}\_\backslash mathcal\{R\}(C^\{knn\}\_\{n\})\; -\; \backslash mathcal\{R\}\_\{\backslash mathcal\{R\}\}(C^\backslash text\{Bayes\})\; =\; \backslash left\backslash \{B\_1\backslash frac\; 1\; k\; +\; B\_2\; \backslash left(\backslash frac\; k\; n\backslash right)^\{4/d\}\backslash right\backslash \}\; \backslash \{1+o(1)\backslash \},$$

여기서 $B\_1$과 $B\_2$는 상수이다.

$k^*\; =\; \backslash left\backslash lfloor\; B\; n^\{\backslash frac\; 4\; \{d+4\}\}\; \backslash right\backslash rfloor$를 선택하면 위 식의 두 항 사이에서 절충이 가능하며, 이 경우 $k^*$-최근접 이웃 오류는 최적의 (미니맥스) 비율 $\backslash mathcal\{O\}\backslash left(n^\{-\backslash frac\; 4\; \{d+4\}\}\backslash right)$로 베이즈 오류로 수렴한다.

9. 응용 분야

K-최근접 이웃 알고리즘(k-NN)은 패턴 인식, 추천 시스템, 의료, 금융, 이상 탐지 등 다양한 분야에 응용된다.

• 패턴 인식: 이미지 인식, 문자 인식, 얼굴 인식 등에 사용된다. 예를 들어, 손글씨 숫자를 인식하는 문제에서 k-NN 알고리즘은 새로운 손글씨 숫자의 특징 벡터를 기존에 학습된 숫자들의 특징 벡터와 비교하여 가장 가까운 k개의 숫자를 찾고, 그중 가장 많은 숫자로 분류한다.
• 추천 시스템: 사용자에게 상품, 영화, 음악 등을 추천하는 데 활용된다. 사용자의 과거 구매 기록이나 선호도를 바탕으로 유사한 사용자를 찾고, 그 사용자들이 선호하는 상품을 추천하는 방식이다.
• 의료: 질병 진단, 유전자 분석 등에 사용된다. 환자의 증상이나 유전자 정보를 바탕으로 유사한 환자들을 찾고, 그 환자들의 질병 정보를 참고하여 진단을 내릴 수 있다.
• 금융: 신용 평가, 주가 예측 등에 활용된다. 개인의 신용 정보나 과거 주가 데이터를 바탕으로 유사한 패턴을 찾고, 이를 통해 신용 등급을 평가하거나 미래 주가를 예측할 수 있다.
• 이상 탐지: 불량품 검출, 네트워크 침입 탐지 등에 사용된다. 정상적인 데이터와 다른 패턴을 보이는 데이터를 이상치로 간주하고, 이를 탐지하는 데 k-NN 알고리즘을 활용할 수 있다. 예를 들어, 제조 공정에서 불량품을 검출하기 위해 제품의 특징 벡터를 정상 제품의 특징 벡터와 비교하여 이상 여부를 판단할 수 있다.^[24][25]

참조

_[1] 보고서 Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties https://apps.dtic.mi[...] USAF School of Aviation Medicine, Randolph Field, Texas
_[2] 텍스트
_[3] 서적 The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations Springer 2001
_[4] 학술지 Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data
_[5] 학술지 Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules
_[6] 서적 Miscellaneous Clustering Methods John Wiley & Sons, Ltd.
_[7] 학술지 Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization
_[8] 학술지 Choice of neighbor order in nearest-neighbor classification
_[9] 학술지 Consistent nonparametric regression
_[10] 학술지 Variable kernel density estimation
_[11] 학술지 Efficient statistical classification of satellite measurements https://archive.org/[...] 2012-08-09
_[12] 학술지 Nearest neighbor pattern classification http://ssg.mit.edu/c[...]
_[13] 학술지 Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining 2005-04
_[14] 서적 A Probabilistic Theory of Pattern Recognition
_[15] 서적 A probabilistic theory of pattern recognition Springer
_[16] 학술지 Optimal weighted nearest neighbour classifiers
_[17] 학술지 When is "nearest neighbor" meaningful? https://minds.wiscon[...]
_[18] 학회 Structure preserving embedding http://www.cs.columb[...]
_[19] 학회 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '01
_[20] 서적 High Performance Discovery in Time Series Springer
_[21] 학술지 Output-sensitive algorithms for computing nearest-neighbor decision boundaries
_[22] 학술지 The Condensed Nearest Neighbor Rule
_[23] 웹사이트 KNN and Potential Energy: applet http://www.math.le.a[...] University of Leicester
_[24] 학회 Proceedings of the 2000 ACM SIGMOD international conference on Management of data - SIGMOD '00
_[25] 학술지 On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study
_[26] 웹사이트 第３章 機械学習(教師あり学習) https://www.stat.go.[...] 총務省統計研究研修所
_[27] 학술지 An introduction to kernel and nearest-neighbor nonparametric regression
_[28] 텍스트
_[29] 웹사이트 Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data http://citeseerx.ist[...] Brazilian Symposium on Bioinformatics (BSB 2011)
_[30] 학술지 Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules
_[31] 서적 Miscellaneous Clustering Methods John Wiley & Sons, Ltd
_[32] 학술지 Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization
_[33] 학술지 Choice of neighbor order in nearest-neighbor classification
_[34] 학술지 Variable kernel density estimation
_[35] 학술지 Efficient statistical classification of satellite measurements https://archive.org/[...] 2012-08-09
_[36] 저널 Nearest neighbor pattern classification
_[37] 저널 Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining 2005-04-00
_[38] 논문 When is “nearest neighbor” meaningful?
_[39] 논문 Structure preserving embedding ACM
_[40] 논문 Random projection in dimensionality reduction: applications to image and text data ACM
_[41] 서적 High Performance Discovery in Time Series Springer
_[42] 저널 Output-sensitive algorithms for computing nearest-neighbor decision boundaries
_[43] 저널 The Condensed Nearest Neighbor Rule
_[44] 웹사이트 KNN and Potential Energy: applet. http://www.math.le.a[...] 2012-01-19