가장 가까운 네이버 검색

근접 검색의 한 형태로 NNS(Neighbor Search)는 특정 집합에서 특정 포인트에 가장 가까운(또는 가장 유사한) 점을 찾는 최적화 문제입니다.근접도는 일반적으로 다른 함수로 표현됩니다.즉, 객체가 비슷하지 않을수록 함수 값이 커집니다.

형식적으로 가장 가까운 이웃(NN) 검색 문제는 다음과 같이 정의된다. 공간 M과 쿼리 포인트 q m M의 집합 S가 주어지면 S에서 q에 가장 가까운 점을 찾는다. The Art of Computer Programming (1973) vol. 3의 도널드 Knuth는 그것을 우체국 문제라고 하며, 주소 할당 어플리케이션에 가장 가까운 것을 참조한다.이 문제의 직접적인 일반화는 k-NN 검색입니다. 여기서 k개의 가장 가까운 점을 찾아야 합니다.

가장 일반적으로 M은 미터법 공간이고, 차이는 거리 측정법으로 표현되며, 이것은 대칭이며 삼각 부등식을 만족한다.더 일반적으로 M은 유클리드 거리, 맨해튼 거리 또는 다른 거리 메트릭을 사용하여 차이가 측정되는 d차원 벡터 공간으로 간주된다.단, 차분 함수는 임의일 수 있습니다.한 가지 예는 비대칭 브레그만 발산인데, 삼각형 부등식이 ^[1]유지되지 않는다.

적용들

가장 가까운 네이버 검색 문제는 다음과 같은 다양한 응용 분야에서 발생합니다.

• 패턴 인식 – 특히 광학 문자 인식용
• 통계 분류: "k-nearest neighbor 알고리즘" 참조
• 컴퓨터 비전 – 포인트 클라우드^[2] 등록용
• 계산 기하학 – 가장 가까운 점 쌍 문제 참조
• 데이터베이스 – 콘텐츠 기반 이미지 검색 등
• 코딩 이론 – "최대우도 디코딩" 참조
• 데이터 압축– MPEG-2 표준 참조
• 로봇^[3] 감지
• 권장 시스템(예: 협업 필터링 참조)
• 인터넷 마케팅 – 상황별 광고 및 행동 타깃팅 참조
• DNA순서결정
• 맞춤법 검사 – 올바른 맞춤법 제안
• 표절 검출
• 프로 선수의 진로 예측을 위한 유사성 점수.
• 클러스터 분석 – 관측치 집합을 하위 집합(클러스터라고 함)에 할당하여 동일한 군집의 관측치가 어떤 의미에서는 유사하도록 하며, 일반적으로 유클리드 거리를 기반으로 합니다.
• 화학적 유사성
• 샘플링 기반 모션 플래닝

방법들

NNS 문제에 대한 다양한 해결책이 제안되었습니다.알고리즘의 품질과 유용성은 쿼리의 시간 복잡성 및 유지해야 하는 검색 데이터 구조의 공간 복잡성에 따라 결정됩니다.일반적으로 차원성의 저주라고 불리는 비공식적인 관찰은 다항식 전처리 및 다항식 탐색 시간을 사용하는 고차원 유클리드 공간에는 NNS에 대한 범용적인 정확한 해법이 없다는 것이다.

정확한 방법

선형 검색

NNS 문제에 대한 가장 간단한 해결책은 쿼리 포인트에서 데이터베이스 내의 다른 모든 포인트까지의 거리를 계산하여 "지금까지의 최고"를 추적하는 것입니다.이 알고리즘은 순진한 어프로치라고도 불리며 실행시간은 O(dN)입니다.여기서 N은 S의 카디널리티, d는 M의 치수입니다.유지할 검색 데이터 구조가 없으므로 선형 검색은 데이터베이스 저장 공간 이상의 복잡성이 없습니다.Naigive 검색은 평균적으로 고차원 ^[4]공간에서 공간 분할 방식을 능가할 수 있습니다.

절대 거리는 거리 비교에 필요하지 않고 상대 거리만 필요합니다.기하학적 좌표계에서 거리 계산은 두 좌표 사이의 거리 계산에서 제곱근 계산을 생략함으로써 상당히 고속화할 수 있다.거리 비교에서도 동일한 결과가 나타납니다.

공간 파티션

1970년대부터 분기 및 제한 방법론이 이 문제에 적용되어 왔다.유클리드 공간의 경우, 이 접근법은 공간 색인 또는 공간 접근 방법을 포함한다.NNS 문제를 해결하기 위해 몇 가지 공간 분할 방법이 개발되었습니다.아마도 가장 단순한 것은 k-d 트리로, 탐색 공간을 상위 영역의 점의 절반을 포함하는 두 영역으로 반복적으로 이등분한다.쿼리는 각 분할에서 쿼리 포인트를 평가하여 루트에서 리프까지 트리를 트래버설하여 수행됩니다.쿼리에서 지정된 거리에 따라 히트를 포함할 수 있는 인접 브랜치를 평가해야 할 수도 있습니다.일정 차원 쿼리 시간의 경우 랜덤으로 분산된 포인트의 경우 평균 복잡도는 O(log N), 최악의 경우 복잡도는 O(kN^(1-1/k)^[6]입니다.또한 R 트리 데이터 구조는 R 트리 ^[7]등의 삽입 및 삭제에 효율적인 알고리즘을 갖추고 있기 때문에 동적 컨텍스트에서 가장 가까운 네이버 검색을 지원하도록 설계되었습니다.R-트리는 유클리드 거리뿐만 아니라 다른 거리에서도 가장 가까운 이웃을 산출할 수 있다.

일반 메트릭 공간의 경우 분기 및 경계 접근 방식을 메트릭 트리 접근 방식이라고 합니다.구체적인 예로는 vp-tree 및 BK-tree 방식이 있습니다.

3차원 공간에서 가져와 BSP 트리에 넣고 동일한 공간에서 가져온 쿼리 포인트를 사용하여 쿼리 포인트에 가장 가까운 포인트 클라우드 포인트를 찾는 문제에 대한 가능한 해결책을 알고리즘에 대한 다음 설명에 제시합니다.

이 기사는 독자들에게 혼란스럽거나 불분명할 수 있다. 글의 명확화를 도와주세요. 토크 페이지에 이 건에 대한 논의가 있을 수 있습니다.( 2021년 11월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

(엄밀히 말하면, 그러한 점은 존재하지 않을 수 있습니다.왜냐하면, 그것은 유일하지 않을 수 있기 때문입니다.그러나 실제로는 보통 특정 쿼리 포인트에서 최단 거리에 있는 모든 포인트 클라우드 포인트의 서브셋 중 하나를 찾는 데만 관심이 있습니다.)이 개념은 트리의 각 분기에 대해 클라우드에서 가장 가까운 점이 쿼리 포인트를 포함하는 절반 공간에 있다고 가정하는 것입니다.그렇지 않을 수도 있지만 좋은 발견적 접근법이다.추측된 반공간에 대해 문제를 해결하는 모든 문제를 반복적으로 겪은 후, 이제 이 결과로 반환된 거리를 쿼리 포인트에서 분할 평면까지의 최단 거리로 비교합니다.이 후자의 거리는 검색되지 않은 절반 공간에 존재할 수 있는 쿼리 포인트와 가장 가까운 점 사이의 거리입니다.이 거리가 이전 결과에서 반환된 거리보다 클 경우 다른 반쪽 공간을 검색할 필요가 없습니다.이러한 요구가 있는 경우는, 나머지 절반의 공간에 대해서 문제를 해결하고, 그 결과를 앞의 결과와 비교한 후, 적절한 결과를 반환하는 수고를 할 필요가 있습니다.이 알고리즘의 성능은 쿼리 포인트가 클라우드 근처에 있을 때 선형 시간보다 로그 시간에 가깝습니다. 쿼리 포인트와 가장 가까운 포인트 클라우드 포인트 사이의 거리가 0에 가까워지면 알고리즘은 쿼리 포인트를 키로 조회만 수행하면 올바른 결과를 얻을 수 있기 때문입니다.

근사법

근접 근접 근접 탐색 알고리즘은 쿼리로부터의 거리가 쿼리로부터 가장 가까운 지점까지의 거리의 $최대{\displaystyle }$ c$$$\displaystyle$c}이 접근법의 매력은 대부분의 경우 거의 가까운 이웃이 거의 정확한 이웃만큼 좋다는 것입니다.특히 거리 측정이 사용자 품질의 개념을 정확하게 포착하는 경우 거리의 작은 차이는 ^[8]중요하지 않습니다.

근접 근린 그래프에서 탐욕스러운 검색

근접 그래프 방식(HNSW^[9] 등)은 근접 네이버 ^[9][10][11]검색의 최신 기술로 간주됩니다.

이 방법은 근접 근린 $그래프{\displaystyle }$G ( ${\displaystyle V}$,${\displaystyle E}$) ( \ $displaystyle$ G ( V , E ) \ $displaystyle$ G $( V$ , $E$) 。이$$ 그래프 G ( V , E ) 。여기서 모든 ${\displaystyle {점x}_{}}$ i${\displaystyle {}_{}s}$S \ $displaystyle$ x$_$$${ $i$$$}\ $in$ S$$}는$$ ${\displaystyle {정점vi}_{}v}$V \ $displaysty$v V$$와 일의적으로 관련지어집니다.집합 S 내의 쿼리 q에 가장 가까운 네이버 검색은 $그래프{\displaystyle G}$ ( V${\displaystyle }$,${\displaystyle E}$) \ $displaystyle$G ($V$ , $E$)$$。기본 알고리즘인 그리디 검색은 다음과 같이 동작합니다.검색은 연산 쿼리 거리에서 입력점 $정점{\displaystyle {}_{}}$ ${\displaystyle {vi}_{}v}$V \ $displaystyle v_{i}\in$V에서$$ 시작됩니다.q는 인근${\displaystyle }${ ${\displaystyle v_{}}$j :${\displaystyle }$( ${\displaystyle {}_{}{i}_{}}$ , ${\displaystyle v_{}}$j )${\displaystyle e}$ E$}$ { $displaystyle$\ { $v _$ { $j$} : ( v$_$ i , v _ { j } )\ $in E$의 각 정점에 도달한 후 최소 거리 값을 가진 정점을 찾습니다.쿼리와 선택된 정점 사이의 거리 값이 쿼리와 현재 요소 사이의 거리 값보다 작을 경우 알고리즘은 선택된 정점으로 이동하며 새로운 엔터 포인트가 됩니다.알고리즘은 로컬 최소값에 도달하면 정지합니다.이 정점은 정점 자체보다 쿼리에 가까운 정점이 인접해 있지 않은 정점입니다.

근접 이웃 그래프의 생각 여러 간행물에, 아리아와 Mount,[12]이 VoroNet 시스템의 RayNet 시스템의 En(^{n}},[14]의 plane,[13]고 Metrized 중소 World[15]과 HNSW[9]알고리즘에 열린 공간의 일반적인 경우에 대한 논문을 포함해 개발되고 있다 거리 재미 있게ction. 이 작품들은 Tous Saint가 상대 근린 ^[16]그래프의 개념을 소개한 선구적인 논문이 선행되었다.

지역 구분 해시

LSH(Locality Sensitive Hashing)는 공간에 있는 점을 해당 포인트에서 작동하는 거리 메트릭에 따라 '버킷'으로 그룹화하는 기술입니다.선택한 메트릭에서 서로 가까운 지점은 높은 ^[17]확률로 동일한 버킷에 매핑됩니다.

내재가 작은 공간에서 가장 가까운 네이버 검색

커버 트리에는 데이터 집합의 두 배 상수를 기반으로 하는 이론적 한계가 있습니다.검색 시간에 바인딩되는 시간은¹² O(c log n)입니다. 여기서 c는 데이터 세트의 확장 상수입니다.

투영된 방사형 검색

데이터가 기하학적 점의 밀도가 높은 3D 맵인 특별한 경우, 감지 기술의 투영 형상을 사용하여 검색 문제를 극적으로 단순화할 수 있습니다.이 접근방식은 3D 데이터가 2차원 그리드에 투영되어 구성되어야 하며, 객체 경계를 제외하고 인접 그리드 셀에서 데이터가 공간적으로 매끄럽다고 가정합니다.이러한 가정은 측량, 로보틱스 및 스테레오 비전 등의 애플리케이션에서 3D 센서 데이터를 다룰 때 유효하지만 일반적으로 체계화되지 않은 데이터에는 적용되지 않을 수 있습니다.실제로 이 기술은 실제 스테레오 비전 데이터에 적용될 때 k-근접 이웃 문제에 대한 평균 검색 시간이 O(1) 또는 O(K)입니다.^[3]

벡터 근사 파일

고차원 공간에서는 노드 비율이 증가하기 때문에 트리 인덱싱 구조가 무용지물이 됩니다.선형 검색 속도를 높이기 위해 RAM에 저장된 특징 벡터의 압축 버전을 사용하여 첫 번째 실행에서 데이터 세트를 프리필터링합니다.최종 후보는 디스크로부터의 비압축 데이터를 사용하여 거리 계산을 ^[18]위해 두 번째 단계에서 결정된다.

압축/클러스터 기반 검색

VA 파일 접근 방식은 각 기능 구성요소가 균일하고 독립적으로 압축되는 압축 기반 검색의 특수한 경우입니다.다차원 공간에서 최적의 압축 기술은 클러스터링을 통해 구현되는 벡터 양자화(VQ)입니다.데이터베이스가 클러스터되고 가장 "유망성이 높은" 클러스터가 검색됩니다.VA-File, 트리 기반 인덱스 및 시퀀셜 스캔에 비해 큰 이점을 얻었습니다.^[19][20]클러스터링과 LSH의 유사성도 주의해 주십시오.

변종

NNS 문제에는 다양한 종류가 있으며 가장 잘 알려진 두 가지는 k-근접 네이버 검색과 "근접 근접 네이버 검색"입니다.

k-param 네이버

k-internal 네이버 검색에서는 쿼리에 가장 가까운 상위k개의 네이버를 식별합니다.이 기술은 예측 분석에서 일반적으로 인접 라우터의 합의에 따라 점을 추정하거나 분류하기 위해 사용됩니다. k-가장 가까운 인접 라우터는 모든 점이 k개의 가장 가까운 인접 라우터에 연결되는 그래프입니다.

근접 근접 근접 라우터

어플리케이션에 따라서는 가장 가까운 네이버의 '적절한 추측'을 얻을 수 있습니다.이 경우 속도 또는 메모리 절감의 대가로 모든 경우에 실제로 가장 가까운 네이버를 반환하는 것을 보증하지 않는 알고리즘을 사용할 수 있습니다.이러한 알고리즘은 대부분의 경우 가장 가까운 인접 라우터를 찾지만, 이는 쿼리되는 데이터 세트에 크게 좌우됩니다.

근접 근접 네이버 검색을 지원하는 알고리즘에는 지역 의존형 해시, best bin first 및 balanced box-decomposition tree 기반 ^[21]검색이 있습니다.

근접 근접 근접 거리 비율

가장 가까운 네이버 거리비율은 원래 포인트부터 챌린저 네이버까지의 직접 거리에 문턱값을 적용하지 않고 이전 네이버까지의 거리에 따라 문턱값을 적용합니다.CBIR에서 로컬 기능 간의 유사성을 사용하여 "예시로 쿼리"를 통해 이미지를 검색하기 위해 사용됩니다.보다 일반적으로는, 몇개의 일치 문제에 관련하고 있습니다.

근접 네이버 고정 반지름

인접 고정 반지름은 지정된 점으로부터 주어진 고정 거리 내에서 유클리드 공간에 주어진 모든 점을 효율적으로 찾고자 하는 문제이다.거리는 고정된 것으로 간주되지만 쿼리 포인트는 임의입니다.

가장 가까운 모든 네이버

일부 애플리케이션(예: 엔트로피 추정)의 경우, N개의 데이터 포인트가 있을 수 있으며, 어느 것이 이들 N개의 모든 포인트에 가장 가까운 인접 네트워크인지 알고자 합니다.이것은 물론 모든 포인트에 대해 1회 가장 가까운 네이버 검색을 실행함으로써 실현될 수 있지만, 보다 효율적인 검색을 위해 이들 N개의 쿼리 간의 정보 용장성을 이용하는 알고리즘이 개선될 것입니다.간단한 예로서, 점 X에서 점 Y까지의 거리를 찾으면 점 Y에서 점 X까지의 거리도 알 수 있으므로 동일한 계산을 두 개의 다른 쿼리에서 재사용할 수 있습니다.

고정 치수, 반확정 양의 노름(모든^p L 노름을 포함) 및 이 공간의 n개 점이 주어졌을 때, 모든 점의 가장 가까운 이웃은 O(n log n) 시간에,^[22][23] m개의 가장 가까운 이웃은 O(mn log n) 시간에 찾을 수 있다.

「 」를 참조해 주세요.

레퍼런스

인용문

원천

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

추가 정보

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

외부 링크

• Nearest Neighbors and Simority Search – 교육 자료, 소프트웨어, 문헌, 연구원, 미해결 문제 및 NN 검색에 관한 이벤트를 전문으로 하는 웹사이트.Yury Lifshits 유지 보수
• 유사성 검색 Wiki – 링크, 사람, 아이디어, 키워드, 논문, 슬라이드, 코드 및 데이터 세트 모음