본문으로 이동

최근접 이웃 탐색: 두 판 사이의 차이

위키백과, 우리 모두의 백과사전.
입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
58번째 줄: 58번째 줄:
| doi = 10.1007/BF00263763
| doi = 10.1007/BF00263763
| postscript = .
| postscript = .
}}</ref> 에, 거리화된 작은 세계 알고리즘 (Metrized Small World algorithm)에서의 과 일반적 거리 공간을 위한 RayNet 시스템[11]에서 활발하게 이용되었다.
}}</ref> 에, 거리화된 작은 세계 알고리즘 (Metrized Small World algorithm)에서의 과 일반적 거리 공간을 위한 RayNet 시스템<ref name=rayNet>{{Cite journal
| last1 = Olivier | first1 = Beaumont
| last2 = Kermarrec | first2 = Anne-Marie
| last4 = Rivière | first4 = Etienne
| year = 2007
| title = Peer to Peer Multidimensional Overlays: Approximating Complex Structures
| journal = Principles of Distributed Systems
| volume = 4878
| issue = .
| pages = 315–328
| doi = 10.1007/978-3-540-77096-1_23
| isbn = 978-3-540-77095-4
| postscript = .
}}</ref>에서 활발하게 이용되었다.


==변종==
==변종==

2015년 4월 30일 (목) 02:36 판

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

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

애플리케이션

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

방법

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

선형 탐색

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

공간 파티셔닝

지역성 의존 해싱

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

벡터 근사 파일

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

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

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

탐욕 보행

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

변종

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


k-최근접 이웃

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

근사 근접 이웃

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

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

최근접 이웃 거리 비율

최근접 거리 비율(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 (그래서 모든 Lp norm를 포함한다), 그리고 이 공간 내의 n개의 점들이 주어졌을때, 모든 점들에 있어서 최근접 이웃은 O(n log n)시간 내에서 찾을 수 있고, 모든 점의 m 개의 최근접 이웃들은 O(mn log n) 시간 내에 찾을 수 있다.[6][7]

같이 보기

각주

  1. ↑ Cayton, Lawerence (2008). “Fast nearest neighbor retrieval for bregman divergences.”. 《Proceedings of the 25th international conference on Machine learning》: 112–119. 
  2. ↑ Weber, Schek, Blott. “A quantitative analysis and performance study for similarity search methods in high dimensional spaces” (PDF). 
  3. ↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). “VoroNet: A scalable object network based on Voronoi tessellations”. 《INRIA》. RR-5833 (1): 23–29. doi:10.1007/BF00263763. 
  4. ↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). “Peer to Peer Multidimensional Overlays: Approximating Complex Structures”. 《Principles of Distributed Systems》 4878 (.): 315–328. doi:10.1007/978-3-540-77096-1_23. ISBN 978-3-540-77095-4.  이름 목록에서 |성3=이(가) 없음 (도움말)
  5. ↑ S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Wu, An optimal algorithm for approximate nearest neighbor searching, Journal of the ACM, 45(6):891-923, 1998. [1]
  6. ↑ Clarkson, Kenneth L. (1983), 〈Fast algorithms for the all nearest neighbors problem〉, 《24th IEEE Symp. Foundations of Computer Science, (FOCS '83)》, 226–232쪽, doi:10.1109/SFCS.1983.16, ISBN 0-8186-0508-1 .
  7. ↑ Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. 《Discrete and Computational Geometry》 4 (1): 101–115. doi:10.1007/BF02187718. 

참고 문헌

  • 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 – 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 – 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
원본 주소 "https://ko.wikipedia.org/w/index.php?title=최근접_이웃_탐색&oldid=14033322"