최근접 이웃 검색

최근접 이웃 검색은 모아 둔 데이터 가운데 주어진 것과 가장 가까운 것을 찾아 줍니다. 데이터 하나하나를 공간의 점으로 놓습니다. 그 점들 사이의 거리를 잽니다. 가까운 순서로 몇 개를 고르는 일도 같은 이름으로 부릅니다. 닮은 글을 찾는 검색도 이 문제로 풉니다.

상세

아래 소절들은 편의점 네 곳과 손님 한 명이라는 작은 예 하나로 최근접 이웃 검색을 봅니다.

문제의 입력과 출력

최근접 이웃 검색에 넣는 것은 둘입니다. 미리 모아 둔 점 n 개와 질문으로 건네는 점 하나입니다. 질문으로 건네는 점을 쿼리라고 부릅니다. 「이것과 가장 가까운 것을 찾아 달라」며 내미는 기준입니다.

나오는 것은 모아 둔 점 가운데 쿼리와 거리가 가장 짧은 점입니다. 편의점 좌표 네 개를 모아 둡니다. 손님이 선 곳을 쿼리로 주면 손님과 가장 가까운 편의점이 답입니다.

점을 숫자로 적을 때는 벡터를 씁니다. 벡터는 숫자를 정해진 개수만큼 늘어놓은 목록입니다. 편의점 좌표 (2, 3) 은 숫자 둘짜리 벡터입니다.

벡터에 든 숫자의 개수를 차원이라고 부릅니다. 지도 좌표는 2차원입니다. 글이나 상품을 숫자 수백 개로 적으면 수백 차원이 됩니다. 글을 숫자로 바꾸는 법은 뒤의 「이 문제가 쓰이는 곳」에서 봅니다.

가까움을 재는 거리

「가깝다」를 정하려면 두 점 사이를 수 하나로 재는 규칙이 있어야 합니다. 이 규칙을 거리 함수라고 부릅니다. 같은 점들이라도 어느 거리 함수를 쓰느냐에 따라 가장 가까운 점이 달라집니다.

아래 표는 흔히 쓰는 셋입니다. 이 항목은 거리 함수와 유사도를 함께 척도라고 이릅니다. 앞의 둘은 거리라서 값이 작을수록 가깝습니다. 코사인 유사도는 값이 클수록 가깝습니다.

어느 척도를 쓰든 이 항목은 「가깝다」로 묶어 부릅니다. 아래 예는 모두 유클리드 거리로 잽니다.

하나 대신 여럿을 찾는 변형

가장 가까운 점 하나가 아니라 k 개를 돌려받는 일이 더 흔합니다. 이것을 k-최근접 이웃 검색(k-NN 검색, k-Nearest Neighbors search)이라고 부릅니다. 추천 목록 열 칸을 채우려면 k 를 10 으로 줍니다.

개수 대신 거리로 끊기도 합니다. 쿼리에서 반지름 r 안에 드는 점을 전부 돌려받습니다. 이 방식을 반경 검색이라고 부릅니다. 「반경 1km 안의 편의점」이 이 꼴입니다.

전부 견주는 풀이

가장 쉬운 풀이는 쿼리와 모아 둔 점 전부의 거리를 하나씩 재는 것입니다. 그중 가장 짧은 것을 남깁니다. 이렇게 빠짐없이 훑는 풀이를 완전 탐색이라고 부릅니다.

아래 코드는 편의점 A~D 네 곳의 좌표를 모아 둡니다. 그리고 (2, 2) 에 선 손님에게 가까운 곳을 찾습니다. 오른쪽 주석이 그 줄이 내는 값입니다.

import heapq, math

shops = {"A": (1, 1), "B": (4, 5),
         "C": (2, 3), "D": (6, 1)}
me = (2, 2)

def dist(name):
    return math.dist(shops[name], me)

dist("C")             # 1.0
dist("D")             # 4.123...
min(shops, key=dist)  # 'C'

top2 = heapq.nsmallest(2, shops, key=dist)
top2                  # ['C', 'A']

dist 는 편의점 이름을 받아 손님까지의 유클리드 거리를 돌려줍니다. min 은 네 곳을 전부 훑습니다. 그중 dist 가 가장 작은 곳을 고릅니다. 그래서 답은 거리가 1 인 C 입니다.

heapq.nsmallest 는 가까운 순서로 k 개를 고릅니다. 여기서는 k 가 2 라서 C 와 그다음으로 가까운 A 가 나옵니다.

k 개를 고를 때 전부 정렬할 필요는 없습니다. 훑는 동안 후보 k 개만 남겨 두면 됩니다. 이 후보를 담아 두는 자료구조로 힙을 씁니다.

힙은 담긴 값 가운데 가장 큰 것을 늘 맨 위에 두는 자료구조입니다. 맨 위 값은 바로 꺼낼 수 있습니다. 값을 넣고 빼도 이 순서가 저절로 유지됩니다.

후보를 담을 때 힙에 넣는 값은 거리입니다. 그래서 가장 큰 값, 곧 후보 가운데 가장 먼 점이 맨 위에 옵니다. 더 가까운 점이 나오면 맨 위의 가장 먼 후보를 꺼내고 그 점을 넣습니다.

전부 견주는 비용

비용은 빅오 표기법으로 적습니다. 입력이 커질 때 계산량이 무엇에 비례해 느는지를 O(…) 꼴로 적는 법입니다. O(n) 이면 입력이 두 배가 될 때 계산도 두 배가 됩니다.

완전 탐색의 비용은 점의 수 n 과 차원 d 가 정합니다. 점 하나와 거리를 재려면 숫자 d 쌍을 계산합니다. 이것을 n 번 하므로 쿼리 한 번에 O(n·d) 가 듭니다.

k 개를 힙에 넣고 빼는 데는 한 번에 log k 에 비례하는 비용이 듭니다. 그래서 전체는 O(n·d + n log k) 입니다. log k 는 대개 d 보다 훨씬 작으므로 비용은 앞쪽 항이 정합니다.

점이 백만 개이고 차원이 500 이면 쿼리 한 번에 숫자 5억 쌍을 계산합니다. 쿼리마다 이 일을 하므로 데이터가 늘수록 응답이 늦어집니다.

대신 미리 지어 둘 구조가 없습니다. 점을 더하거나 빼면 다음 쿼리부터 바로 반영됩니다. 언제나 정답을 낸다는 것도 완전 탐색의 몫입니다.

정렬로 풀리지 않는 까닭

보통의 데이터베이스 인덱스는 값을 한 줄로 정렬해 둡니다. B-tree 인덱스가 그 예입니다. 정렬해 두면 값이 같은 것이나 범위 안에 드는 것을 몇 단계 만에 찾습니다.

값이 수 하나라면 가장 가까운 값도 이렇게 찾습니다. 정렬된 줄에서 쿼리가 들어갈 곳을 찾습니다. 그 양옆만 보면 됩니다. 가운데 값과 견주어 절반씩 버리는 이진 탐색으로 O(log n) 에 끝납니다.

축이 둘만 돼도 이 방법이 무너집니다. 이 소절에서만 편의점 E 가 (2, 9) 에 하나 더 있다고 해 봅시다. 편의점을 가로 좌표로만 정렬하면 손님 (2, 2) 와 가로 좌표가 같은 E 가 줄 위에서 바로 옆에 옵니다. 세로로는 7 이나 떨어져 있습니다.

점을 한 줄로 세우면 2차원에서 먼 점이 줄 위에서 옆에 오기도 합니다. 그래서 줄 위의 양옆만 봐서는 가장 가까운 점을 못 찾습니다. 최근접 이웃 검색에는 정렬과 다른 구조가 필요합니다. 다음 소절의 공간 나누기가 그 하나입니다.

공간을 나눠 건너뛰기

차원이 낮으면 공간을 미리 구역으로 나눠 둘 수 있습니다. 그러면 쿼리에서 먼 구역을 통째로 건너뜁니다. 대표가 k-d 트리입니다.

k-d 트리는 축 하나를 골라 점들을 둘로 가릅니다. 이때 점 하나를 기준으로 골라 그 노드에 담습니다. 나머지 점은 기준점의 그 축 좌표보다 작은 쪽과 크거나 같은 쪽으로 나눕니다.

갈린 쪽은 다른 축으로 또 가릅니다. 이 일을 되풀이하면 트리가 됩니다. 이름의 k-d 는 k 차원(k-dimensional)을 뜻합니다.

편의점 넷으로 지으면 아래와 같습니다. 맨 위 노드에는 B 를 담고, B 의 가로 좌표 4 로 나머지 셋을 가릅니다. 왼쪽 노드에는 C 를 담고, C 의 세로 좌표 3 으로 한 번 더 가릅니다.

flowchart TD
    R["B (4, 5) · 가로 4 로 가른다"]
    R -->|"가로 4 보다 작다"| L["C (2, 3) · 세로 3 으로 가른다"]
    R -->|"가로 4 이상"| D["D (6, 1)"]
    L -->|"세로 3 보다 작다"| A["A (1, 1)"]

쿼리 (2, 2) 는 맨 위 노드부터 내려가며 지나는 점마다 거리를 잽니다. 맨 위의 B 까지는 약 3.61 입니다. 쿼리의 가로 좌표 2 가 4 보다 작으므로 왼쪽으로 내려갑니다. C 까지는 1, A 까지는 약 1.41 이라 지금까지 가장 가까운 것은 C 입니다.

이제 오른쪽 구역을 열지 판단합니다. 오른쪽에는 B 를 뺀 점 가운데 가로 좌표가 4 이상인 점만 있습니다. 쿼리에서 그 구역까지는 적어도 2 만큼 떨어져 있습니다. 이미 거리 1 짜리를 찾았으므로 D 는 재 보지도 않고 건너뜁니다.

점이 고르게 퍼져 있고 차원이 낮으면 쿼리 한 번이 평균 O(log n) 가까이에 끝납니다. 점의 분포에 따라서는 모든 점을 보는 O(n) 까지 늘어납니다.

대신 트리를 미리 지어야 합니다. 지은 뒤에 점을 많이 더하거나 빼면 트리가 한쪽으로 기웁니다. 한쪽 가지만 길어져 내려가는 단계가 늘어난다는 뜻입니다. 그러면 트리를 다시 지어야 합니다.

차원이 높을 때

앞에서 비용을 셈한 500차원 점들로 돌아가 봅시다. 차원이 수십을 넘기 시작하면 건너뛰기가 잘 통하지 않습니다. 차원이 높아질수록 쿼리에서 모든 점까지의 거리가 서로 비슷해지기 때문입니다.

거리는 축마다 난 차이를 모두 더해 얻습니다. 축이 수백 개면 차이가 쌓여 어느 점까지든 거리가 크게 나옵니다. 점끼리 거리가 다른 정도는 그 큰 값에 비하면 작아집니다. 그러면 어느 구역도 멀다고 버릴 수 없으니 결국 대부분을 견주게 됩니다.

차원이 높아질수록 거리와 공간 나누기가 힘을 잃는 이 현상을 차원의 저주라고 부릅니다. 그래서 k-d 트리가 완전 탐색보다 빠른 것은 대개 차원이 낮을 때뿐입니다.

가끔 놓치고 빨리 찾는 근사 검색

점이 많고 차원이 높으면 정답을 조금 내줍니다. 가장 가까운 k 개를 대부분 찾되 가끔 놓치는 것을 받아들입니다. 그 대신 살펴볼 점을 크게 줄입니다.

이 풀이를 근사 최근접 이웃 검색(ANN, Approximate Nearest Neighbor search)이라고 부릅니다. 놓치지 않는 앞의 풀이들은 근사 검색과 견줄 때 정확한 최근접 이웃 검색이라고 부릅니다.

얼마나 놓쳤는지는 재현율로 잽니다. 정확한 풀이가 찾을 k 개 가운데 근사 풀이도 찾은 몫입니다. 10 개 가운데 9 개를 찾았으면 재현율은 0.9 입니다.

후보를 추리는 방법은 크게 셋입니다. 아래 표는 각 갈래가 후보를 어떻게 줄이는지만 보입니다.

어느 갈래든 미리 지어 둔 구조를 담을 메모리와 짓는 시간이 더 듭니다. 살펴볼 후보를 늘리면 재현율이 오르는 대신 검색은 느려집니다.

이 문제가 쓰이는 곳

글이나 이미지처럼 숫자가 아닌 데이터도 이 문제로 다룰 수 있습니다. 뜻이 비슷할수록 가까운 벡터로 바꾸면 됩니다. 이렇게 바꾼 벡터를 임베딩이라고 부릅니다. 바꾸는 일은 학습한 모델이 맡습니다.

임베딩을 쓰면 「이것과 비슷한 것 찾기」가 「이 벡터와 가장 가까운 벡터 찾기」가 됩니다. 「차량 수리」로 검색했을 때 낱말이 하나도 안 겹치는 「자동차 정비 안내」가 나오는 것이 이 덕분입니다. 이런 검색을 시맨틱 검색이라고 부릅니다.

아래 표는 이 문제를 쓰는 곳마다 무엇이 점이 되고 무엇이 쿼리가 되는지 보입니다.

맨 아래 둘은 찾은 이웃을 사용자에게 보여 주지 않고 판단에 씁니다. 최근접 이웃 분류는 찾은 이웃의 답을 빌려 새 데이터의 답으로 삼습니다. 이상치 찾기는 가장 가까운 이웃마저 멀리 있으면 그 데이터를 이상치로 봅니다.

풀이를 고르는 기준

앞에서 본 세 풀이는 데이터의 양과 차원, 놓쳐도 되는지에 따라 갈립니다. 아래 표가 그 갈림입니다.

가장 가까운 것이 아니라 값이 같은 것을 찾는다면 이 문제가 아닙니다. 그때는 보통의 인덱스로 충분합니다.

관련 항목

최근접 이웃 검색이 속하는 상위 분류

알고리즘 · 검색 · 유사도 검색 · 벡터 검색 · 계산 기하학

가까움을 재는 거리 척도

거리 함수 · 유클리드 거리 · 맨해튼 거리 · 코사인 유사도 · 내적 · 해밍 거리 · 민코프스키 거리

최근접 이웃 검색을 정확하게 푸는 방법과 구조

완전 탐색 · k-d 트리 · 볼 트리 · R-트리 · 공간 인덱스 · 보로노이 다이어그램 · 힙

정답을 조금 내주고 빠르게 푸는 근사 방법

근사 최근접 이웃 · HNSW · IVF · 곱 양자화 · 지역 민감 해싱 · 재현율

최근접 이웃 검색 위에 서는 응용

시맨틱 검색 · 추천 시스템 · 최근접 이웃 · 이상 탐지 · 이상치 · 검색 증강 생성 · 중복 탐지

최근접 이웃 검색이 다루는 데이터 표현과 저장소

벡터 · 차원 · 임베딩 · 특성 벡터 · 벡터 데이터베이스 · 인덱스

최근접 이웃 검색과 맞세워지는 다른 검색 방식

반경 검색 · 범위 검색 · 이진 탐색 · B-tree · 해시테이블

최근접 이웃 검색의 비용을 재는 기준과 걸림돌

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 차원의 저주