위키백과

k-최근접 이웃 알고리즘

패턴 인식에서 k-최근접 이웃 알고리즘(또는 줄여서 k-NN)은 분류나 회귀에 사용되는 비모수 방식이다.[1] 두 경우 모두 입력이 특징 공간 내 k개의 가장 가까운 훈련 데이터로 구성되어 있다. 출력은 k-NN이 분류로 사용되었는지 또는 회귀로 사용되었는지에 따라 다르다.

  • k-NN 분류에서 출력은 소속된 항목이다. 객체는 k개의 최근접 이웃 사이에서 가장 공통적인 항목에 할당되는 객체로 과반수 의결에 의해 분류된다(k는 양의 정수이며 통상적으로 작은 수). 만약 k = 1 이라면 객체는 단순히 하나의 최근접 이웃의 항목에 할당된다.
  • k-NN 회귀에서 출력은 객체의 특성 값이다. 이 값은 k개의 최근접 이웃이 가진 값의 평균이다.

k-NN은 함수가 오직 지역적으로 근사하고 모든 계산이 분류될 때까지 연기되는 인스턴스 기반 학습 또는 게으른 학습의 일종이다. k-NN 알고리즘은 가장 간단한 기계 학습 알고리즘에 속한다.

분류와 회귀 모두 더 가까운 이웃일수록 더 먼 이웃보다 평균에 더 많이 기여하도록 이웃의 기여에 가중치를 주는 것이 유용할 수 있다. 예를 들어, 가장 흔한 가중치 스키마는 d가 이웃까지의 거리일 때 각각의 이웃에게 1/d의 가중치를 주는 것이다.[2]

이웃은 항목(k-NN 분류의 경우)이나 객체 특성 값(k-NN 회귀의 경우)이 알려진 객체의 집합으로부터 구해진다. 이것은 명시적인 훈련 과정이 필요하지는 않지만, 알고리즘을 위한 훈련 집합이라고 생각될 수 있다.

k-NN 알고리즘의 단점은 데이터의 지역 구조에 민감하다는 것이다. 이 알고리즘은 유명한 기계 학습 기법, k-평균과 아무 관련이 없으므로 혼동하지 않아야 한다.

알고리즘

편집
 
검증 표본(초록색 원)은 첫 번째 파랑 네모의 항목이나 빨강 삼각형의 두 번째 항목으로 분류되어야 한다. 만약 “k = 3” (실선으로 그려진 원)이면 두 번째 항목으로 할당되어야 한다. 왜냐하면 2개의 삼각형과 1개의 사각형만이 안쪽 원 안에 있기 때문이다. 만약 “k = 5” (점선으로 그려진 원)이면 첫 번째 항목으로 분류되어야 한다. (바깥쪽 원 안에 있는 3개의 사각형 vs. 2개의 삼각형).

훈련 데이터는 각각이 항목 분류명을 갖는 다차원 특징 공간에서의 벡터이다. 알고리즘의 훈련 단계는 오직 훈련 표본의 특징 벡터와 항목 분류명을 저장하는 것이다.

분류 단계에서 k는 사용자 정의 상수이고 분류명이 붙지 않은 벡터(질의 또는 검증점)는 k개의 훈련 표본 사이에서 가장 빈번한 분류명을 할당함으로써 분류된다.

연속 변수에서 가장 흔하게 사용되는 거리 척도는 유클리드 거리이다. 문자 분류와 같은 이산 변수의 경우 중첩 거리(또는 해밍 거리)와 같은 다른 척도가 사용될 수 있다. 예를 들어 유전자 표현 미세 배열 데이터의 경우, k-NN은 피어슨과 스피어만 같은 상관 계수를 사용해 왔다.[3] 종종 거리 척도가 큰 여백 최근접 이웃이나 이웃 성분 분석과 같은 특별한 알고리즘으로 학습된다면 k-NN의 분류의 정확성을 상당히 향상시킬 수 있다.

“과반수 의결”에 따른 분류의 단점은 항목 분포가 편향될 때 나타난다. 다시 말해서, 더 빈번한 항목의 데이터가 새로운 데이터의 예측을 지배하는 경향이 있다. 왜냐하면, 더 빈번한 항목의 데이터가 다수를 이루어서 k개의 최근접 이웃의 대부분이 되는 경향이 있기 때문이다.[4] 이 문제를 해결하는 한 가지 방법은 검증점과 k개의 최근접 이웃 각각의 거리를 고려하여 분류에 가중치를 주는 것이다. 각각 k개의 최근접 점의 항목(회귀 문제의 경우 값)에 그 점에서 검증점까지의 거리에 반비례하는 가중치를 곱한다. 편향을 해결하는 또 다른 방법은 데이터 표현을 추상화하는 것이다. 예를 들어 자기 조직화 지도(SOM)에서 각 노드는 원래의 훈련 데이터 밀도와 상관없이 유사점의 군집 대표(중심)이다. k-NN은 SOM에도 적용될 수 있다.

매개변수 선택

편집

최선의 k값을 선택하는 것은 데이터에 의존적이다. 일반적으로 k 값이 커질수록 분류에서 잡음의 영향이 줄어들지만[5] 항목 간 경계가 불분명해진다. 좋은 k는 다양한 발견적 기법으로 선택될 수 있다(초월매개변수 최적화 참고). 어떤 항목이 가장 가까운 훈련 표본의 항목으로 예측되는 특별한 경우(즉, k = 1 일 때)를 최근접 이웃 알고리즘이라고 부른다.

k-NN 알고리즘의 정확성은 잡음 또는 무관한 특징이 존재하거나 특징 크기가 중요성과 일치하지 않을 경우 상당히 감소한다. 많은 연구가 분류를 개선하기 위해 특징을 선택하거나 크기 조정하는 식으로 노력하고 있다. 특히 유명한 접근법은 특징 크기를 최적화하기 위해 진화형 알고리즘을 사용하는 것이다.[6] 또 다른 유명한 접근법은 훈련 항목과 훈련 데이터의 상호 정보를 이용해 특징의 크기를 정하는 것이다.

이진(2개 항목) 분류 문제에서는 동률의 투표를 피하기 위해 홀수인 k를 선택하는 것이 바람직하다. 이런 환경에서 최적의 k를 경험적으로 선택하는 유명한 한 가지 방법은 부트스트랩 방식이다.[7]

특징

편집

k-NN은 균등한 핵을 가지는 변동 핵 밀도 추정의 특별한 경우이다.[8] [9] 이 알고리즘은 시험 데이터와 모든 저장된 데이터 사이의 거리를 계산하는 방식으로 쉽게 구현할 수 있지만, 다량의 훈련 집합에 대해 많은 계산량을 요구한다. 적절한 최근접 이웃 탐색 알고리즘을 사용하면 다량의 데이터 집합에 대해서도 k-NN 계산이 가능하도록 할 수 있다. 많은 최근접 이웃 탐색 알고리즘들은 일반적으로 실제로 수행되는 거리 계산 횟수를 줄이는 방법을 찾는 방식으로 제안되어 왔다.

k-NN은 매우 일관성 있는 결과를 도출한다. 이 알고리즘은 데이터의 수가 무한대로 증가할수록 오차율이 베이즈 오차율(주어진 데이터의 분포에서 달성할 수 있는 최소 오차율)의 두 배보다 항상 나쁘지 않음을 보장한다.[10] k-NN은 어떤 k값에 대해 베이즈 오차율에 항상 접근함을 보장한다(여기서 k는 데이터 수에 따라 증가). 근접 그래프를 사용하면 k-NN의 결과를 다양하게 개선할 수 있다.[11]

거리 척도 학습

편집

(지도) 거리 척도 학습을 활용하면 종종 k-최근접 이웃 분류의 성능을 상당히 개선할 수 있다. 유명한 알고리즘으로는 이웃 성분 분석과 큰 여백 근접 이웃이 있다. 지도 거리 척도 학습 알고리즘은 새로운 거리 또는 유사 거리를 학습하기 위해 분류명 정보를 사용한다.

특징 추출

편집

알고리즘의 입력 데이터가 처리하기에 매우 크고 심각하게 불필요한 중복이 있다고 의심이 된다면(예를 들면 동일한 측정값이 피트와 미터 단위로 존재하는 경우), 입력 데이터를 특징들의 축소된 표현 집합(또는 특징 벡터)으로 변환할 수 있다. 입력 데이터를 특징들의 집합으로 변환하는 과정을 특징 추출이라고 한다. 만약 추출된 특징들이 세심하게 선택되었다면, 특징 집합이 전체 입력 데이터를 사용하지 않고 축소된 표현값만을 사용해 원하는 작업을 수행하도록 입력 데이터에서 적절하게 관련 있는 정보를 추출했음을 기대할 수 있다. 특징 추출은 특징 공간으로 변환된 데이터에 k-NN 알고리즘을 적용하기 전에 미가공 데이터에 수행된다.

특징 추출과 차원 축소 전처리 과정을 포함해 k-NN으로 구현된 대표적인 컴퓨터 비전 계산 파이프라인 안면 인식 예시(대부분 OpenCV로 구현됨):

  1. Haar 안면 인식
  2. 평균 이동 추적 분석
  3. 특징 공간으로의 주성분 분석 또는 Fisher 선형 판별 분석 투영 후 k-NN 분류

차원 축소

편집

고차원의 데이터(예를 들어 10차원을 넘는 경우)에 대해선 차원의 저주를 피하기 위해 보통 k-NN 알고리즘을 사용하기 전에 차원 축소를 수행한다. [12]

k-NN에서 차원의 저주는 기본적으로 유클리드 거리가 고차원에선 도움이 되지 않음을 의미한다. 왜냐하면, 모든 벡터가 탐색 질의 벡터와 대부분 같은 거리를 갖고 있기 때문이다(많은 점들이 대부분 질의 점을 중심으로 하는 원 위에 있다고 생각해 보면, 검색 공간에서 질의 점과 모든 데이터 점 사이의 거리는 대부분 같다).

특징 추출과 차원 축소는 주성분 분석(PCA), 선형 판별 분석(LDA), 또는 정준 상관 분석(CCA) 기술을 전처리 과정으로 사용하면 한 과정으로 합칠 수 있다. 그 후 k-NN을 사용해 축소된 차원 공간에서 군집화를 할 수 있다. 기계 학습에서 이 과정을 저차원 매장이라 부른다.[13]

초고차원의 데이터 집합(예를 들어 실시간 비디오 스트림, DNA 데이터 또는 고차원 시계열)에 대해선 지역 민감 해싱, "무작위 투영",[14] "스케치"[15] 또는 VLDB 툴박스의 다른 고차원 유사도 탐색 기법들을 사용한 빠른 근사 k-NN 탐색을 수행하는 것이 유일하게 실행 가능한 방법일 수 있다.

결정 경계

편집

실제로 최근접 이웃 규칙은 잠재적으로 결정 경계를 계산한다. 결정 경계는 명시적이고 효율적으로 계산될 수 있고, 계산 복잡도가 경계 복잡도의 함수가 되도록 할 수 있다.[16]

데이터 축소

편집

데이터 축소는 대량의 데이터 집합을 다룰 때 가장 중요한 문제 중 하나이다. 보통 정확한 분류를 위해선 데이터 점의 일부만 필요하다. 그 데이터를 프로토타입이라 하고 다음과 같은 방법으로 찾을 수 있다:

  1. 어떤 주어진 k에 대해 k-NN이 부정확하게 분류시키고 있는 훈련 데이터인 항목 이상치를 선택한다
  2. 남은 데이터를 두 종류의 집합으로 분리한다: (i) 분류 결정으로 사용할 프로토타입과 (ii) 프로토타입을 사용하는 k-NN이 정확하게 분류시킬 수 있는 흡수된 점들. 그 후 훈련 데이터 집합에서 흡수된 점들은 제거할 수 있다.

항목 이상치 선택

편집

다른 항목의 데이터로 둘러싸여 있는 훈련 데이터를 항목 이상치라 한다. 항목 이상치가 발견되는 이유는 다음과 같다:

  • 무작위 오류
  • 해당 항목의 충분하지 않은 훈련 데이터(군집 대신 고립된 데이터가 나타난다)
  • 중요한 특징의 누락 (항목이 우리가 모르는 다른 차원으로 분리된다)
  • 주어진 적은 항목에 대해 어려운 배경을 제공하는 너무 많은 다른 항목의 훈련 데이터(불균형 항목)

k-NN에서 항목 이상치는 잡음을 생성한다. 항목 이상치는 추후 분석 과정에서 발견되고 분리될 수 있다. 주어진 두 자연수 k>r>0에 대해서 어떤 훈련 데이터의 k 최근접 이웃이 r개 이상의 다른 항목을 포함하고 있으면, 그 훈련 데이터를 (k,r)NN 항목 이상치라고 한다.

데이터 축소를 위한 CNN

편집

압축된 근접 이웃(CNN, Hart 알고리즘)은 k-NN 분류를 위해 데이터 집합을 축소하려는 목적으로 설계된 알고리즘이다.[17] 이 알고리즘은 훈련 데이터로부터 프로토타입의 집합 U를 선택하고, 이를 통해 1NN이 모든 데이터 집합을 분류하는 것만큼 정확하게 U와 1NN이 데이터들을 분류할 수 있다.

 
경계율의 계산
 
세 종류의 점: 프로토타입, 항목 이상치, 흡수된 점

주어진 훈련 집합 X에 CNN을 반복적으로 수행한다.

  1. X의 모든 요소를 탐색하여, U로부터 가장 가까운 프로토타입을 가지는 x를 찾는다(U는 x와 다른 분류명을 가진다).
  2. X로부터 x를 삭제하고 그것을 U에 더한다.
  3. U에 더 이상 프로토타입을 더할 수 없을 때까지 탐색을 반복한다.

분류하기 위해 X 대신에 U를 사용한다. 프로토타입이 아닌 데이터들은 "흡수된" 점이라고 한다.

경계율을 줄이기 위해서는 학습 데이터들을 탐색하는 것이 효율적이다.[18] 학습 데이터 x의 경계 비율은 아래와 같다.

a(x) = || x' - y || / || x - y ||

|| x - y || 는 x와 색이 다른 가장 가까운 데이터인 y까지의 거리를 나타내고, || x' - y || 는 y와 가장 가까운 데이터인 x' 까지의 거리를 나타낸다(x' 는 x와 같은 분류명을 가진다).

경계율은 [0,1] 구간 내의 값인데, 왜냐하면 || x' - y || 는 || x - y || 를 절대 초과하지 않기 때문이다. 이 순서는 프로토타입의 집합인 U로의 포함을 위한 우선권을 항목들의 경계에 준다. x와 다른 분류명을 가지는 점은 x 외부에 있다고 한다. 경계율의 계산은 오른쪽에 도식으로 나타나 있다. 점 데이터들은 색으로 분류명이 붙여졌는데, 초기의 점은 x이고 분류명은 빨간색이다. 외부의 점들은 파란색과 초록색이다. x의 외부 점들 중 가장 가까운 점은 y이다. y에 가장 가까운 빨간 점은 x' 이다. 경계율 a(x) = || x' - y || / || x - y ||은 초기의 점 x의 속성이다.

아래 도식은 CNN의 과정을 보여준다. 3개의 항목(빨강, 초록, 파랑)이 있다. 그림 1: 초기에, 각 항목별로 60개의 점이 존재한다. 그림 2: 1NN 분류 지도를 보여주는데, 각각의 픽셀은 모든 데이터를 사용하여 1NN에 의해 분류된다. 그림 3: 5NN 분류 지도를 보여준다. 하얀 구역은 5NN 투표에서 결과가 동률이 나와 분류되지 않은 지역에 대응된다(예를 들어, 5개의 최근접 이웃들 중 2개의 초록, 2개의 빨강과 1개의 파란 점이 있는 경우). 그림 4: 축소된 데이터 집합을 보여준다. X 표시는 (3,2)NN 규칙에 의해 선택된 항목 이상치들을 나타낸다(이 인스턴스들의 모든 세 최근접 이웃들이 다른 항목에 속한다). 사각형은 프로토타입을 나타내며, 빈 원은 흡수된 점을 나타낸다. 좌하측 모서리는 항목 이상치, 프로토타입, 흡수된 점들의 개수를 나타낸다. 이 예시에서는 프로토타입의 수가 항목에 따라 15%에서 20%까지로 다양하다. 그림 5: 프로토타입에 기초한 1NN 분류 지도를 나타낸 것인데, 초기 데이터 집합에 기반한 1NN 분류 지도와 매우 비슷함을 알 수 있다. 이 그림들은 Mirkes 애플릿을 사용하여 만들었다.[18]

  • k-NN 분류기(classfier)를 위한 CNN 모델
  •  
    그림 1. 데이터 집합.
  •  
    그림 2. 1NN 분류 지도.
  •  
    그림 3. 5NN 분류 지도.
  •  
    그림 4. CNN을 통해 축소된 데이터셋.
  •  
    그림 5. CNN을 통해 추출한 프로토타입에 기반한 1NN 분류 지도.

k-NN 회귀

편집

k-NN 회귀에서, k-NN 알고리즘은 연속 변수를 예측하기 위해서 사용된다. 하나의 알고리즘은 k개의 최근접 이웃들의 거리의 역수를 가중치로 한 가중 평균을 사용한다. 이 알고리즘은 다음과 같이 동작한다.

  1. 질의 데이터로부터 분류된 데이터까지의 유클리드 거리 혹은 마할라노비스 거리를 계산한다.
  2. 분류명이 붙은 데이터를 거리가 증가하는 순으로 정렬한다.
  3. 평균 제곱근 편차에 기반한 최근접 이웃들의 발견적인 최적 수를 찾는다. 이것은 교차 검증을 통해 이뤄진다.
  4. k-최근접 다변량 이웃들에서 거리의 역수를 가중치로 한 가중 평균을 계산한다.

결과의 타당성 검증

편집

혼동 행렬 또는 일치 행렬은 k-NN 분류의 정확성을 검증하기 위한 도구로 자주 사용된다. 우도비 검정 같은 더 강한 통계적 방법을 적용할 수도 있다.

같이 보기

편집

각주

편집
  1. ↑ Altman, N. S. (1992). “An introduction to kernel and nearest-neighbor nonparametric regression”. 《The American Statistician》 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. 
  2. ↑ 이 스키마는 선형보간법을 일반화한 것이다.
  3. ↑ Jaskowiak, P. A.; Campello, R. J. G. B. “Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data”. 《http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.993》. Brazilian Symposium on Bioinformatics (BSB 2011). 1–8쪽. 2014년 10월 16일에 확인함.  |website=에 외부 링크가 있음 (도움말)
  4. ↑ D. Coomans; D.L. Massart (1982). “Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules”. 《Analytica Chimica Acta》 136: 15–27. doi:10.1016/S0003-2670(01)95359-0. 
  5. ↑ Everitt, B. S., Landau, S., Leese, M. and Stahl, D. (2011) Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK.
  6. ↑ Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). “Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization”. 《Journal of Chemical Information and Modeling》 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183. 
  7. ↑ Hall P, Park BU, Samworth RJ (2008). “Choice of neighbor order in nearest-neighbor classification”. 《Annals of Statistics》 36 (5): 2135–2152. doi:10.1214/07-AOS537. 
  8. ↑ D. G. Terrell; D. W. Scott (1992). “Variable kernel density estimation”. 《Annals of Statistics》 20 (3): 1236–1265. doi:10.1214/aos/1176348768. 
  9. ↑ Mills, Peter (2012년 8월 9일). “Efficient statistical classification of satellite measurements”. 《International Journal of Remote Sensing》. 
  10. ↑ Cover TM, Hart PE (1967). “Nearest neighbor pattern classification”. 《IEEE Transactions on Information Theory》 13 (1): 21–27. doi:10.1109/TIT.1967.1053964. 
  11. ↑ Toussaint GT (April 2005). “Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining”. 《International Journal of Computational Geometry and Applications》 15 (2): 101–150. doi:10.1142/S0218195905001622. 
  12. ↑ Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful?. Database Theory—ICDT’99, 217-235|year 1999
  13. ↑ Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009
  14. ↑ Bingham, Ella, and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM | year 2001
  15. ↑ Shasha, D High Performance Discovery in Time Series.Berlin: Springer, 2004, ISBN 0-387-00857-8
  16. ↑ Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). “Output-sensitive algorithms for computing nearest-neighbor decision boundaries”. 《Discrete and Computational Geometry》 33 (4): 593–604. doi:10.1007/s00454-004-1152-0. 
  17. ↑ P. E. Hart, The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory 18 (1968) 515–516. doi: 10.1109/TIT.1968.1054155
  18. ↑ 가 나 E. M. Mirkes, KNN and Potential Energy: applet. Archived 2012년 1월 19일 - 웨이백 머신 University of Leicester, 2011.

외부 링크

편집
원본 주소 "https://ko.wikipedia.org/w/index.php?title=K-최근접_이웃_알고리즘&oldid=37945398"