최근접 이웃 탐색

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

최근접 이웃 탐색(Nearest neighbor search, NNS)은 주어진 데이터 중 특정 질의점과 가장 유사한 데이터를 찾는 최적화 문제로, 유클리드 거리 등을 활용하여 유사성을 정의한다. 패턴 인식, 통계적 분류, 컴퓨터 비전, 데이터베이스, 추천 시스템, 자연어 처리 등 다양한 분야에 응용되며, 대한민국에서도 맞춤법 검사, 표절 판별, 온라인 광고, 상품 추천 등에 활용된다. 해결 방법으로는 선형 탐색, 공간 분할, 지역성 의존 해싱(LSH), 근사 최근접 이웃 탐색 등이 있으며, 차원의 저주로 인해 효율적인 해법을 찾기 어렵다는 한계가 있다. 변종으로는 k-최근접 이웃 탐색, ε-근사 최근접 이웃 탐색, 고정 반지름 근접 이웃 등이 있다.

최근접 이웃 탐색

개요

종류	검색 알고리즘
문제	가장 가까운 이웃 탐색 문제
다른 이름	최근접 이웃 탐색 근접 탐색 유사성 탐색 가장 가까운 점 탐색

설명

목표	주어진 공간에서 특정 쿼리 점에 가장 가까운 점을 찾는 것
응용 분야	패턴 인식 기계 학습 데이터 마이닝 컴퓨터 비전 정보 검색 추천 시스템 데이터베이스 마케팅 온라인 광고 표절 검사 DNA 시퀀싱
변형	근사 최근접 이웃 탐색 (Approximate Nearest Neighbor Search, ANNS) k-최근접 이웃 탐색 (k-Nearest Neighbor Search, k-NN) 최근접 이웃 연결 (Nearest neighbor chain)

알고리즘

선형 탐색	모든 점과의 거리를 계산하여 가장 가까운 점을 찾음 단순하지만 고차원 데이터에 부적합
공간 분할	k-d 트리 R 트리 보로노이 다이어그램
근사 최근접 이웃 탐색 (ANNS)	지역 민감 해싱 (Locality-Sensitive Hashing, LSH) 계층적 탐색 가능한 작은 세계 (Hierarchical Navigable Small World, HNSW) 곱셈 양자화 (Product Quantization, PQ)

성능

정확도	정확한 최근접 이웃 탐색은 최적의 결과를 보장 근사 최근접 이웃 탐색은 정확도를 희생하여 속도를 향상
속도	선형 탐색은 데이터 크기에 비례하여 느림 공간 분할 방법은 데이터 분포에 따라 성능이 달라짐 근사 최근접 이웃 탐색은 빠른 검색 속도를 제공
메모리 사용량	공간 분할 방법은 추가적인 메모리를 필요로 함 근사 최근접 이웃 탐색은 인덱스 크기를 조절하여 메모리 사용량을 관리

고려 사항

거리 측정 방법	유클리드 거리 맨해튼 거리 민코프스키 거리 코사인 유사도 편집 거리 (문자열)
차원의 저주	고차원 데이터에서 성능이 저하될 수 있음 차원 축소 기법을 사용하여 해결 가능
데이터 전처리	데이터 정규화 및 표준화를 통해 성능 향상 가능

📚 더 읽어볼만한 페이지

정보 검색 - 검색 엔진
검색 엔진은 사용자가 입력한 검색어에 따라 웹 정보를 찾아 순위를 매겨 보여주는 도구로, 다양한 형태의 검색어를 처리하고, 알고리즘을 통해 결과를 순위화하며, 검색 최적화 및 정보 편향 문제와 사용자 경험 향상이라는 과제를 안고 있다.
정보 검색 - 해시태그 운동
검색 - 패턴 매칭
패턴 매칭은 데이터 구조나 문자열에서 특정 패턴을 찾아 식별하는 기법으로, 다양한 프로그래밍 언어와 시스템에서 사용되며 데이터 필터링, 추출 및 선언적 프로그래밍에 중요한 역할을 수행한다.
검색 - 색인
색인은 책, 데이터베이스 등에서 특정 항목의 위치를 쉽게 찾도록 돕는 도구이며, 서적 색인은 19세기 말 상세한 챕터 제목을 포함하는 형태로 발전했고, 데이터베이스와 인터넷에서도 활용되며, 일관성, 관련성, 정확성을 갖춰 전문적인 과정을 통해 작성된다.
근사 알고리즘 - 크리스토피데스 알고리즘
크리스토피데스 알고리즘은 삼각 부등식을 만족하는 완전 그래프에서 외판원 문제의 근사해를 구하는 O(n<sup>3</sup>) 복잡도의 알고리즘으로, 최소 비용 신장 트리 생성, 홀수 차수 정점 집합 식별, 최소 가중치 완전 매칭 계산을 통해 해밀턴 회로를 구성하며 최적해의 3/2 이내의 근사 비율을 보장하고 다양한 분야에 응용된다.
근사 알고리즘 - L-환산
L-환산은 최적화 문제 간의 관계를 정의하는 개념으로, 한 문제의 입력과 해를 다른 문제의 입력과 해로 변환하는 함수와 특정 조건을 만족하며, 이를 통해 한 문제의 근사 알고리즘을 다른 문제에 적용할 수 있게 한다.

1. 개요
2. 정의
3. 응용 분야
- 3.1. 대한민국 내 응용 사례
4. 방법
5. 변종
6. 한계 및 과제

2. 정의

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

최근접 이웃 탐색은 최적화 문제의 하나로, n개의 데이터가 주어졌을 때, 특정 질의점에 대해 n개의 데이터 중 가장 유사한 데이터를 찾는 문제이다. 데이터는 주로 R^d 공간 위의 점으로 표현되며, 유사성은 유클리드 거리 등 특정 목적 함수를 최소화하는 방식으로 정의된다.

3. 응용 분야

최근접 이웃 탐색은 다양한 분야에서 활용된다.

* 패턴 인식: 특히, 광학 문자 인식(OCR)에 사용된다.
* 통계적 분류: K-최근접 이웃 알고리즘은 가장 기본적인 분류 규칙 중 하나이다.
* 컴퓨터 비전: 이미지 인식, 객체 추적 등에 활용된다.
* 데이터베이스: 콘텐츠 기반 이미지 검색(CBIR) 등에 사용된다.
* 코딩 이론: 복호 방법론에 활용된다.
* 데이터 압축: MPEG-2 표준에서 사용된다.
* 추천 시스템: 협업 필터링 등 사용자 맞춤형 상품, 콘텐츠 추천에 활용된다.
* 온라인 광고: 컨텐츠 연동형 광고, 행동형 타게팅 등에 사용된다.
* DNA 염기서열 결정법: 유전자 분석 등에 활용된다.
* 맞춤법 검사기: 올바른 맞춤법 제안에 사용된다.
* 표절 판별: 유사도 검사를 통한 표절 판별에 활용된다.
* 유사도 점수: 프로 운동 선수들의 경력 예측 등에 사용된다.
* 클러스터 분석: 유클리드 거리를 기반으로 유사한 요소들을 묶는 데 사용된다.
* 화학적 유사도: 화학 물질 분석 및 예측에 활용된다.
* 샘플링에 기반한 모션 플래닝

3.1. 대한민국 내 응용 사례

최근접 이웃 탐색(NN)은 대한민국 내 다양한 분야에서 활용되고 있지만, 구체적인 사례는 원본 문서에 명시되어 있지 않다. 다만, 일반적인 응용 분야는 다음과 같이 추정해 볼 수 있다.

공공 서비스:

* 맞춤법 검사기: 한국어 맞춤법 검사기는 사용자가 입력한 단어와 가장 유사한 올바른 맞춤법을 제안하는 데 NN을 활용할 수 있다.
* 표절 판별: 학술 논문이나 과제물 등에서 표절 여부를 판별하기 위해 NN 알고리즘을 사용하여 기존 문서와의 유사도를 검사할 수 있다.

산업:

* 추천 시스템: 협업 필터링과 같은 추천 시스템은 사용자의 선호도와 가장 유사한 상품이나 콘텐츠를 추천하는 데 NN을 활용할 수 있다.
* 온라인 광고: 컨텐츠 연동형 광고와 행동형 타게팅은 사용자의 관심사와 가장 관련성이 높은 광고를 노출하는 데 NN을 사용할 수 있다.

연구 개발:

* [[DNA 염기서열 결정법]]: 새로운 생명체의 게놈과 가장 유사한 게놈을 찾는 데 NN을 활용할 수 있다.
* [[화학적 유사도]]: 새로운 화합물을 개발하거나 기존 화합물의 특성을 예측하는 데 NN을 사용하여 유사한 구조의 화합물을 탐색할 수 있다.

4. 방법

최근접 이웃 탐색(NN) 문제에는 다양한 해법이 제시되었다. 알고리즘의 효율성은 질의 시간 복잡도와 자료 구조의 공간 복잡도로 결정된다. 차원의 저주로 인해, 고차원 유클리드 공간에서 다항 전처리와 다항 연산 시간을 사용하는 효율적이고 정확한 해법은 없다고 알려져 있다.

* 주요 해법:
* k-d 트리: 탐색 공간을 재귀적으로 이등분한다. 고정 차원에서 질의 처리 시간은 O(log N)이다.
* R-트리: 최근접 이웃 탐색용으로 설계된 자료 구조다.
* VP 트리, Bk 트리: 일반적인 거리 공간에서 사용되는 분기 한정법의 예시다.

4.1. 선형 탐색

최근접 이웃 탐색의 가장 간단한 해법은 데이터베이스 안의 모든 점과 질의점 사이의 거리를 일일이 계산하여 가장 가까운 이웃을 찾는 것이다. 이 방법은 단순하지만, 집합의 크기를 N, 차원을 d라고 할 때, $O(dN)$ 의 시간 복잡도를 가진다. 별도로 유지해야 할 자료 구조가 없으므로, 데이터베이스 용량 외 추가적인 공간 복잡도는 없다.

거리 비교에는 상대적인 거리만 필요하므로, 제곱근 계산을 생략하면 거리 계산 속도를 높일 수 있다.

이 방법은 데이터베이스가 작을 때는 괜찮지만, 크기나 차원이 증가하면 매우 느려진다. 선형 탐색의 처리 시간은 O(Nd)이며, N은 데이터베이스의 기수, d는 차원이다.

4.2. 공간 분할

분기 한정법은 1970년대부터 최근접 이웃 탐색 문제에 적용되어 왔다. 유클리드 공간에서는 공간 인덱스 또는 공간 접근 방법이라고 불리는 여러 공간 분할 방법들이 고안되었다. 가장 간단한 방법인 k-d 트리는 탐색 공간을 반복적으로 이등분하여 트리를 구성한다. 질의는 트리의 뿌리 정점부터 잎 정점까지 운행하면서 처리되며, 각 분할점에서 질의 포인트의 평가가 이루어진다. 고정 차원에서 질의 시간은 임의로 분포된 점들에 대해 평균 O(log N)의 복잡도를 갖는다.

R-트리는 동적 데이터 환경에서 근접 이웃 탐색을 지원하기 위해 고안된 자료구조이다. R* 트리와 같이 삽입과 제거에 효율적인 알고리즘을 갖는다. R-트리는 유클리드 거리 뿐만 아니라 다른 거리 계산법에도 사용될 수 있다.

일반적인 거리 공간에서는 거리 트리(metric tree)로 알려진 분기 한정법 접근이 사용된다. vp-트리와 BK-트리는 일반적인 거리 공간에서 사용 가능한 트리 구조의 예시이다.

4.3. 지역성 의존 해싱 (LSH)

지역성 의존 해싱(locality sensitive hashing)은 고차원 데이터를 낮은 차원 데이터로 변환하는 기법으로, 비슷한 아이템들은 높은 확률로 동일한 "양동이(bucket)"에 할당된다. 이때 양동이의 수는 가능한 아이템들의 수보다 훨씬 작다. 지역성 의존 해싱은 비슷한 아이템들에 대한 충돌(collision)을 최대화한다는 점에서 기존의 (암호학론적) 해싱 기법과 대조된다. 최근접 이웃 탐색 문제에서 비슷한 아이템들이란 어느 특정 거리 계산법에 의해 서로 근접하게 판정된 포인트들을 뜻한다. 국소 민감 해싱(LSH)은 공간상의 점들을 특정 거리 척도를 기반으로 '버킷'으로 그룹화하는 기술로, 선택된 척도 하에서 서로 가까운 점들은 높은 확률로 같은 버킷에 매핑된다.

4.4. 근사 최근접 이웃 탐색

몇몇 응용 프로그램에서는 최근접 이웃을 통해 "좋은 추론"을 하는 것이 가능하다. 이러한 경우, 속도 향상이나 메모리 절약을 위해 실제 최근접 이웃 대신 근사적인 이웃을 반환하는 알고리즘을 사용할 수 있다. 대개 이러한 알고리즘은 대부분의 경우에 최근접 이웃을 찾아주지만, 이는 질의된 데이터셋에 따라 달라진다.

근사 최근접 이웃 탐색(approximate nearest neighbor search^영어)을 지원하는 알고리즘에는 지역 민감 해싱, 최적 빈 우선, 균형 상자 분해 트리 기반 탐색 등이 있다.

근사 최근접 이웃 탐색 알고리즘은 질의에서 가장 가까운 점까지의 거리가 질의에서 가장 가까운 점까지의 거리의 $c$ 배를 넘지 않는 점을 반환하도록 허용한다. 이 접근 방식은 많은 경우 근사 최근접 이웃이 정확한 이웃만큼이나 유용하다는 장점이 있다. 특히, 거리 측정법이 사용자 품질에 대한 개념을 정확하게 포착한다면, 거리의 작은 차이는 중요하지 않다.

4.5. 기타 방법

커버 트리는 다른 저차원 데이터들을 색인하는 자료 구조들과 밀접한 연관성을 띄며, 최근접 이웃 탐색 문제의 속도를 높이기 위해 특별히 고안된 자료 구조이다. 커버 트리는 데이터 세트의 배가 상수에 따른 이론적 한계를 갖는다. 최근접 이웃 탐색에 걸리는 시간은 O(c¹² log n)이며, 이때 c는 데이터 세트의 확장 상수이다.

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

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

근접 그래프 방식(예: 항해 가능한 스몰 월드 그래프 및 HNSW)는 근사 최근접 이웃 탐색의 현재 최첨단 기술로 간주된다. 이 방법은 모든 점 $x_i \in S$ 가 정점 $v_i \in V$ 와 고유하게 연관되는 근접 이웃 그래프 $G(V,E)$ 에서 탐욕적 탐색을 기반으로 한다. 집합 S에서 질의 q에 대한 최근접 이웃을 찾는 것은 그래프 $G(V,E)$ 에서 정점을 찾는 형태로 이루어진다.

기본 알고리즘인 탐욕적 탐색은 다음과 같이 작동한다. 탐색은 입력점 정점 $v_i \in V$ 에서 시작하여 질의 q에서 이웃 $\{v_j:(v_i,v_j) \in E\}$ 의 각 정점까지의 거리를 계산한 다음, 최소 거리 값을 가진 정점을 찾는다. 만약 질의와 선택된 정점 사이의 거리 값이 질의와 현재 요소 사이의 거리 값보다 작으면 알고리즘은 선택된 정점으로 이동하고, 이것이 새로운 입력점이 된다. 알고리즘은 지엽적(local) 최솟값에 도달했을 때 멈춘다.

근접 이웃 그래프 아이디어는 평면을 위한 VoroNet 시스템, $\mathbb{E}^n$ 를 위한 RayNet 시스템, 그리고 거리 함수가 있는 공간의 일반적인 경우에 대한 항해 가능한 스몰 월드, 계량된 스몰 월드 및 HNSW 알고리즘을 포함한 여러 출판물에서 활용되었다.

5. 변종

k-최근접 이웃 탐색은 질의에 가장 가까운 k개의 이웃을 식별한다.

근사 최근접 이웃 탐색 (approximate nearest neighbor^영어)은 차원의 저주에 대한 대책으로 최근 특히 인기가 있다.

고정 반지름 근접 이웃은 특정한 점으로부터 주어진 거리 이내에 있는 유클리드 공간의 모든 점을 효율적으로 찾는 문제이다.

어떤 응용 분야(예: 엔트로피 추정)에서는 모든 N개의 점에 대해 각각 가장 가까운 이웃을 알아야 할 수 있다. 물론 모든 점에 대해 최근접 이웃 탐색을 실행하여 이를 수행할 수 있지만, 더 효율적인 탐색을 위해 N개 쿼리의 불필요한 중복 정보를 이용하는 개선된 전략을 사용할 수 있다. 예를 들어, X점에서 Y점으로의 거리를 알면, Y점에서 X점으로의 거리 역시 알 수 있으므로, 하나의 계산은 두 쿼리에 다시 활용할 수 있다.

고정된 차원과 반정부호 놈(모든 L^p 놈 포함)이 주어지고, 이 공간에 n개의 점이 있다면, 모든 점의 최근접 이웃은 O(n log n) 시간 내에, 모든 점의 m개 최근접 이웃은 O(mn log n) 시간 내에 찾을 수 있다.

6. 한계 및 과제

차원의 저주라고 불리는 현상 때문에, 고차원 유클리드 공간에서 NNS(최근접 이웃 탐색)에 대한 범용적인 정확한 해는 없다. 일반적으로 다항식 전처리와 다항 로그 탐색 시간을 사용하는 해는 존재하지 않는다고 알려져 있다.