최근접 이웃 탐색

최근접 이웃 탐색(영어: nearest neighbor search)은 가장 가까운 (또는 가장 근접한) 점을 찾기 위한 최적화 문제이다. 근접 탐색(proximity search), 유사도 탐색(similarity search), 최근접 점쌍 문제(closest point search)라고도 불린다. 근사(近似)라는 개념은 보편적으로 물체와 물체가 덜 유사할수록 그 함수의 값은 커지는 상이(相異) 함수에 의해서 표현된다. 엄밀하게, 최근접 이웃 탐색 문제는 다음과 같이 정의된다: 공간 M에서의 점들로 이루어진 집합 S 가 주어졌을 때, 쿼리점 q ∈ M에 대해 S 안에서 가장 q와 가까운 점을 찾는다. 도널드 커누스는 그의 저서 《컴퓨터 프로그래밍의 예술》(1973) 제 3권에서 사람들의 거주지를 가장 가까운 우체국에 배정하는 프로그램이라는 의미에서 이를 우체국 문제라고 명명했다. 이 문제의 직접적인 일반화 문제로써는, k 개의 가장 가까운 점을 찾는 K-최근접 이웃 알고리즘이 있다.

보편적으로, M은 거리 공간이고 상이(相異)도는 대칭성을 갖고 삼각 부등식을 만족하는 거리 계측에 의해 표현된다. 이보다도 일반적으로 표현하자면, M은 d차원의 벡터 공간이고 상이도는 유클리드 거리, 맨해튼 거리 등을 사용해 계측한다. 그러나 상이함수는 임의성을 갖기 때문에, 예를 들면 대칭성을 띄지 않고 삼각 부등식을 만족하지 않는 브레그만 발산(Bregman Divergence)등을 사용하여 정의할 수 있다.

정의

2차원 평면에서 주어진 테이터에서 가장 근접한 점을 찾는다. 이 그림의 경우에는 카테고리가 지정되어 있는 점에서 가장 비슷한 것을 고르는 문제이다.

최근접 이웃 탐색문제는 최적화 문제의 하나로, n개의 데이터가 주어져있을 때, 어떠한 요청에 대한 응답으로 n개의 데이터 중 가장 비슷한 것을 고르는 문제이다. 이 때, 데이터는 R^d 공간 위 점으로 표현된다. 가장 비슷한 점은 보통 유클리드 거리가 최소인 점을 말하지만, 때에 따라서는 특정 목적 함수를 최소화 시키는 점이기도 하다.

응용 분야

최근접 이웃 탐색의 적용 분야는 다양하다. 데이터 압축, 데이터베이스, 데이터 마이닝, 정보 검색, 기계 학습, 패턴 인식, 통계학의 분야에서 사용될 수 있다. 예컨대, 최근접 이웃 규칙은 기계 학습에서 가장 기본적인 분류 규칙이며, 새로운 생명체의 게놈과 가장 유사한 게놈을 찾는 것도 최근접 이웃 탐색문제이다.

최근접 이웃 탐색 문제는 다음과 같은 분야에 적용된다:

• 패턴 인식 - 특히, 광학 문자 인식
• 통계적 분류- K-최근접 이웃 알고리즘 참조
• 컴퓨터 비전
• 계산기하학 - 최근접 점쌍 문제
• 데이터베이스 - 예를 들어, 컨텐츠 기반 영상 추출
• 코딩 이론 - 복호 방법론 참조
• 데이터 압축 - MPEG-2 표준 참조
• 추천 시스템, 예를 들어, 협업 필터링 참조
• 온라인 광고 - 컨텐츠 연동형 광고와 행동형 타게팅 참조
• DNA 염기서열 결정법
• 맞춤법 검사기 - 올바른 맞춤법을 추천해 줌
• 표절 판별
• Contact searching algorithms in FEA
• 유사도 점수 - 예를 들어, 프로 운동 선수들의 커리어 패스를 추천
• 클러스터 분석 - 관측량의 집합을 클러스터라고 불리는 부분집합으로 배정하여, 같은 클러스터 안의 요소들은 어떤 공통점을 갖는다.
• 화학적 유사도
• 샘플링에 기반한 모션 플래닝

방법

최근접 이웃 탐색 문제에 대해 다양한 해법이 제시되었다. 알고리즘의 유용성과 우수성은 쿼리에 대한 시간 복잡도와 유지되어야 하는 자료 구조의 공간 복잡도에 의해 결정된다. 비공식적으로 관측되는 현상인 차원의 저주에 의해 높은 차원의 유클리드 공간에서 다항 선처리와 다항 연산의 탐색 시간을 이용했을 때 최근접 이웃 탐색 문제의 효율적이고 정확한 해법은 존재하지 않는다고 받아들여지고 있다.

선형 탐색

최근접 이웃 탐색의 가장 간단한 해법은 데이터베이스 안의 쿼리 포인트로부터 다른 모든 데이터 포인트까지의 거리를 일일이 계산하면서, 그 중 '가장 좋은 결과' 만을 기록하는 것이다. N이 집합의 크기이고 M의 차원이 d라고 할 때, 단순한 방법으로도 일컬어지는 이 방법은 $O(dN)$ 의 시간 복잡도를 가지고 있다. 유지하여야 할 자료구조가 없으므로, 선형 탐색은 데이터베이스의 용량 외에 별도의 공간 복잡도를 갖지 않는다. 평균적으로, 이 단순한 방법은 높은 차원의 공간에서 공간 분할 방식보다 더 나은 결과를 낸다.

공간 파티셔닝

1970년대부터 분기 한정법 방법론이 본 문제에 적용되어 왔다. 유클리드 공간에서 이 접근법은 공간 색인(spatial index) 또는 공간 접근(spatial access) 방법들로 불린다. 여러 공간-분할 방법들이 최근접 이웃 탐색 문제를 풀기 위해 고안되었다. 그 중 가장 간단한 방법으로 k-d 트리를 들 수 있는데, 이는 반복적으로 탐색 공간을 부모 지역에 속한 포인트들이 절반으로 나뉘게 분할하는 방식이다. 질의는 트리의 뿌리 정점부터 잎 정점까지의 운행을 통해 수행되는데, 매 분할점마다 질의 포인트의 평가가 이루어진다. 질의에서 명시된 거리에 따라 명중(hit)할 수 있는 이웃 분기점들에 대한 평가도 수행된다. 일정한 차원의 질의 시간은 임의로 분포된 점들에 대해 평균 O(log N)의 복잡도를 갖는다. 다른 대안으로 R-트리 자료구조가 동적 환경에서의 근접 이웃 탐색을 위해 고안되었다. 이는 R* 트리와 같이 삽입과 제거에 효율적인 알고리즘을 갖는다. R-트리는 유클리드 거리 뿐만 아니라 다른 거리 계산법에도 사용될 수 있다.

일반적인 거리 공간에서 분기 한정법 접근은 거리 트리(metric tree)로 알려져 왔다. 예시로 vp-트리와 BK-트리를 들 수 있다.

만약 3차원 공간에 속한 포인트의 집합이 BSP-트리에 속해 있고, 같은 공간에 속한 질의 포인트가 주어졌다고 하자. 이 질의 포인트와 가장 가까운 포인트-구름을 찾는 문제에 대한 가능한 답은 다음과 같은 알고리즘으로 얻을 수 있다. (엄밀히 말하면, 그러한 포인트는 유일하지 않을 수 있기 때문에 존재하지 않을 수 있다. 하지만 실생활 문제에서는 대부분 주어진 질의 포인트와 가장 근접한 거리에 있는 포인트-구름의 임의 점을 찾으면 충분한 경우가 대부분이다.) 알고리즘의 핵심은, 각각의 트리 분기점에 대해서, 질의 포인트와 가장 근접한 포인트는 질의 포인트를 포함하는 반-공간(half space)에 속해 있을 것이라고 추측하는 것이다. 추측이 틀릴 수도 있지만, 일반적으로 이는 괜찮은 휴리스틱이다. 추측된 모든 반-공간에 대해 재귀적으로 문제를 풀어 얻은 거리 결과와, 질의 포인트와 분할면의 최단 거리를 비교해보자. 이때 후자는 탐색하지 않은 반-공간에서 존재할 수 있는 가장 가까운 포인트와 질의 포인트 사이의 거리를 말한다. 만약 이 거리가 재귀적 탐색을 통해 얻은 거리보다 크다면, 당연히 더 이상 다른 반-공간에 대한 탐색을 수행할 필요가 없다. 반대의 경우라면, 탐색하지 않은 반-공간에 대해 다시 탐색을 진행하고 이전 탐색 결과의 거리와 비교하여 답을 구한다. 질의 포인트가 포인트-구름과 근접하다면, 이 알고리즘의 시간 복잡도는 선형 시간보다 대수 시간에 더 근접한다. 왜냐하면 질의 포인트와 포인트-구름의 거리가 0에 가까워질수록 알고리즘은 질의 포인트를 활용하여 정답을 찾는 키로써 검색만 하면 되기 때문이다.

지역성 의존 해싱

지역성 의존 해싱(locality sensitive hashing)은 고차원의 데이터를 낮은 차원의 데이터로 변환하는데, 이때 비슷한 아이템들은 높은 확률로 동일한 "양동이(bucket)"에 할당이 된다 (이때 양동이의 수는 가능한 아이템들의 수보다 훨씬 작음). 지역성 의존 해싱은 비슷한 아이템들에 대한 충돌(collision)을 최대화한다는 점에서 기존의 (암호학론적) 해싱 기법과 대조된다. 최근접 이웃 탐색 문제에서 비슷한 아이템들이란 어느 특정 거리 계산법에 의해 서로 근접하게 판정된 포인트들을 뜻한다.

작은 고유 차원 내 최근접 이웃 탐색

커버 트리(cover tree)는 최근접 이웃 탐색 문제의 속도를 높이기 위해 특별히 고안된 자료 구조로써 다른 저차원 데이터들을 색인하는 자료 구조들과 밀접한 연관성을 띤다. 커버 트리는 데이터 세트의 배가 상수(doubling constant)에 따른 이론적 한계를 갖는다. 최근접 이웃 탐색에 걸리는 시간은 O(c¹² log n)이며, 이때 c는 데이터 세트의 확장 상수(expansion constant)이다. 빠른 검색 시간에 비해, 새로운 아이템을 삽입하는 시간은 O(c⁶ log n)이 걸리는데 이는 새로운 아이템을 트리의 순서를 보존하면서 추가해야 하기 때문이다. 하지만 실제 평균 시간은 이보다 적은 것으로 알려져 있다.

벡터 근사 파일

고차원 공간에서는, 관찰해야 하는 마디(node)의 증가하는 비율 때문에 트리 기반 인덱싱 구조가 유용하지 않게 된다. 선형 탐색의 속도를 높이기 위해서, 동적 할당 메모리(RAM)에 저장되어 있는 요소 벡터의 압축된 버전이 첫 실행에서 데이터세트(datasets)를 사전 필터링(pre-filtering)하는 데 사용된다. 최종 후보는 두 번째 단계에서 결정되는데, 디스크에서 거리 계산을 위한 압축되지 않은 데이터를 이용하여 결정된다.

압축/클러스터링 기반 탐색

VA-파일 접근은 압축 기반 탐색의 특별한 한 사례인데, 각 특성요소는 균일하고 독립적으로 압축된다. 다차원 공간에서의 가장 최적화된 압축 기술은 클러스터링(Clustering)을 통해 구현되는 Vector Quantization (VQ)이다. 데이터베이스는 군집화(clustered)되고 가장 “유망한” 군집들이 되돌아온다. VA-파일, 트리 기반 인덱스, 그리고 순차적 스캔에 비해 큰 이점이 있는 것으로 나타났다. 또한 클러스터링과 LSH는 서로 유사하다는 것 또한 참고할 만 하다.

탐욕 보행

NNS를 푸는 한 가지 방법은, 모든 점 $x_{i}\in S$에 대해 각각 대응되는 꼭지점 $v_{i}\in V$ 을 갖는 그래프 $G(V,E)$를 만드는 것이다. 집합 S에서 질의 q에 가장 가까운 점을 찾는 것은 그래프 $G(V,E)$에서 꼭지점을 찾는 형태가 된다. 그래프에서 가장 기본적인 꼭지점 찾기 알고리즘(vertex search algorithms)은 탐욕 탐색 알고리즘(greedy search algorithm)이다. 이 알고리즘은 임의의 꼭지점 $v_{i}\in V$에서 시작한다. 이 알고리즘은 질의 q로부터의 거리 값(distance value)을 현재 꼭지점 $v_{i}$ 에 이웃하는 각 꼭지점 $\{v_{j}:(v_{i},v_{j})\in E\}$에서의 거리를 계산한 다음, 그 중 거리 값이 가장 작은 꼭지점을 선택한다. 만약 선택된 꼭지점과 질의 사이의 거리 값이 ‘현재’ 꼭지점과 질의 사이의 거리 값보다 작은 경우, 이 알고리즘은 선택된 꼭지점으로 이동하여 이것이 새로운 ‘현재’ 꼭지점이 된다. 이 알고리즘은 지엽적(local) 최솟값 – 이웃하는 꼭지점 중에 질의에 더 가까운 꼭지점을 가지고 있지 않은 어떤 꼭지점 – 에 도달했을 때 멈춘다. 이 아이디어는 plane을 위한 VoroNet 시스템 에, 거리화된 작은 세계 알고리즘 (Metrized Small World algorithm)에서의 $\mathbb {E} ^{n}$ 과 일반적 거리 공간을 위한 RayNet 시스템에서 활발하게 이용되었다.

최근접 이웃 탐색 알고리즘은 외판원 문제에 대한 해법을 제시된 첫번째 알고리즘 중 하나이다. 이 문제에서, 외판원은 임의의 도시로부터 시작하여 모든 도시를 다 방문 할 때까지 순회한다. 최근접 이웃 탐색은 가까운 거리를 제시하지만, 항상 최적의 해법을 제시하지는 않는다.

알고리즘은 다음과 같은 순서로 진행된다.

1. 임의의 정점(頂點)에서 시작한다.
2. 현재 정점을 잇는 가장 짧은 간선과 그것이 연결하는 정점 V를 찾는다.
3. 현재의 정점을 정점 V로 지정한다.
4. 정점 V를 방문한 정점 중 하나로 기록한다.
5. 지역 내의 모든 정점을 방문하였으면 알고리즘을 종료한다.
6. 2로 이동한다.

방문한 정점들의 시퀀스가 알고리즘의 결과물로서 리턴된다.

최근접 이웃 탐색 알고리즘은 쉽게 구현할 수 있고 짧은 러닝타임을 가지고 있다. 그러나 이는 알고리즘의 탐욕적 성질로 인해 종종 최적의 여정을 놓치기 마련이다. 일반적으로, 여정의 마지막 부분의 길이가 초반부의 길이랑 비슷하면, 알고리즘은 용인되는 수준의 결과를 리턴한다. 반면, 여정의 마지막 부분의 길이가 초반부보다 훨씬 길면, 보통 최적의 여정 길이와 최근접 이웃 탐색 알고리즘이 제시하는 여정의 길이는 큰 차이가 난다.

이 알고리즘은 최적의 경로가 존재함에도 불구하고 아예 유한한 길이의 여정 자체를 리턴하지 못하는 경우가 있다.

변종

수많은 NNS 문제의 변종이 있으며, 가장 잘 알려진 2가지는 k-최근접 이웃 탐색과 ε- 근사 최근접 이웃 탐색이다.

k-최근접 이웃

k-최근접 이웃 탐색은 질의에 해당하는 상위 k개의 가장 근접한 이웃을 찾는 것이다. 이 기법은 보통 이웃과의 일치성 기반으로 점을 추정하거나 분류하는 예측 분석에 사용된다. K-근접 이웃 그래프는 모든 점이 그 점들의 k개의 가장 근접한 이웃들과 연결된 그래프이다.

근사 근접 이웃

근사 근접 이웃(approximate nearest neighbor)에서 몇몇 애플리케이션들에서는 최근접 이웃을 통해 "좋은 추론"을 하는 것이 용인된다. 이런 경우들에 있어서, 우리는 모든 경우에 있어서 속도의 향상과 메모리의 절약을 위해 실제의 최근접 이웃의 반환을 보장해주지 않는 알고리즘을 사용할 수 있다. 대개 이런 알고리즘은 대부분의 경우에 있어서 최근접 이웃을 찾아주지만, 이것은 질의된 데이터셋에 매우 강하게 의존한다.

근사 근접 이웃 탐색(approximate nearest neighbor search)을 지원하는 알고리즘들은 지역 민감 해싱, best bin first, balanced box-decomposition tree에 기반을 둔 검색을 포함한다.

최근접 이웃 거리 비율

최근접 거리 비율(Nearest neighbor distance ratio)은 원래 노드로부터 challenger neighbor까지의 direct distance를 사용하지 않지만 그것의 비율은 예전의 이웃과의 거리의 비율에 의지한다. 이것은 극소 특징점(local features)들의 유사성을 이용하여 예시 질의(query by example)를 통해 사진들을 추출하기 위한 CBIR에 사용된다. 더 일반적으로, 이것은 여러 형식 일치 문제에 적용된다.

고정 반지름 근접 이웃

고정 반지름 근접 이웃(Fixed-radius near neighbors)은 특정한 점으로부터 주어진 거리 이내의 유클리드 공간에 주어진 모든 점들을 효율적으로 찾는 문제이다. 이 데이터구조는 고정된 거리에 작용해야하지만, 점의 질의(query point)는 임의여도 된다.

모든 최근접 이웃

어떤 애플리케이션들에서는(예 : entropy estimation) 우리는 N 개의 데이터 점들을 가지고, 어떤 모든 N개의 점들중 한 점이 근접 이웃인지 알고 싶을 수 있다. 이것은 물론 모든 점에 있어서 최근접 이웃 탐색을 실행하는 것으로 수행될 수 있지만, 더 효율적인 탐색을 이뤄내기 위해 이 N개의 쿼리의 불필요한 중복된 정보들을 이용(exploit)한 알고리즘이 개선된 전략(strategy)이 될 수 있다. 하나의 간단한 예로, X점에서 Y점으로의 거리를 알려고 할때, Y'점에서 X점으로의 거리를 역시 알 수 있으며, 그렇기 때문에 어떤 하나의 계산은 두개의 다른 쿼리들에 다시 활용될 수 있다.

고정된(fixed) 차원(dimension)과, 반 확정적인(semi-definite) positive norm (그래서 모든 L^p norm를 포함한다), 그리고 이 공간 내의 n개의 점들이 주어졌을때, 모든 점들에 있어서 최근접 이웃은 O(n log n)시간 내에서 찾을 수 있고, 모든 점의 m 개의 최근접 이웃들은 O(mn log n) 시간 내에 찾을 수 있다.

같이 보기

• 범위 탐색
• 집합 덮개 문제
• 최근접 점쌍 문제
• 클러스터 분석
• 내용 기반 영상 검색
• 차원의 저주
• 디지털 신호 처리
• 차원축소
• 고정 반지름 근접 이웃
• 푸리에 분석
• 인스턴스 기반 학습
• K-최근접 이웃 알고리즘
• 최소 제곱 선형
• 다차원 분석
• 주성분 분석
• 특잇값 분해
• 시계열
• 보로노이 다이어그램
• 웨이블릿

참고 문헌

• Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal, vol. 19, no 11 (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
• Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891–923
• Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
• Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE 2002: 617-627
• Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9
• Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6

읽을 거리

• Shasha, Dennis (2004). 《High Performance Discovery in Time Series》. Berlin: Springer. ISBN 0-387-00857-8. 

외부 링크

• Nearest Neighbors and Similarity Search Archived 2013년 11월 3일 - 웨이백 머신 – a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits
• Similarity Search Wiki – a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours
• KGraph Archived 2021년 1월 23일 - 웨이백 머신 – a C++ library for fast approximate nearest neighbor search with user-provided distance metric by Wei Dong.
• FLANN – a library for performing fast approximate nearest neighbor searches in high dimensional spaces by Marius Muja and David G. Low
• Metric Spaces Library – An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez
• Non-Metric Space Library – An open-source C++ library for exact and approximate searching in non-metric and metric spaces
• ANN – A library for Approximate Nearest Neighbor searching by David M. Mount and Sunil Arya
• Product Quantization – Matlab implementation of approximate nearest neighbor search in the compressed domain by Herve Jegou
• MESSIF – Metric Similarity Search Implementation Framework by Michal Batko and David Novak
• OBSearch – Similarity Search engine for Java (GPL); implementation by Arnoldo Muller, developed during Google Summer of Code 2007
• KNNLSB – K Nearest Neighbors Linear Scan Baseline (distributed, LGPL); implementation by Georges Quénot (LIG-CNRS)
• NearTree – An API for finding nearest neighbors among points in spaces of arbitrary dimensions by Lawrence C. Andrews and Herbert J. Bernstein
• NearPy – Python framework for fast approximated nearest neighbor search by Ole Krause-Sparmann
• dD Spatial Searching in CGAL – the Computational Geometry Algorithms Library
• Panns – A Python library for searching approximate nearest neighbors, optimized for large dataset with high dimensional features, developed by Liang Wang