최근접 이웃 탐색

정의

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

방법

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

선형 탐색

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

공간 파티셔닝

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 문제의 변종이 있으며, 가장 잘 알려진 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ᵖ norm를 포함한다), 그리고 이 공간 내의 n개의 점들이 주어졌을때, 모든 점들에 있어서 최근접 이웃은 O(n log n)시간 내에서 찾을 수 있고, 모든 점의 m 개의 최근접 이웃들은  O(mn log n) 시간 내에 찾을 수 있다.