SciPy cKDTree / 기존 NumPy 방법과 비교 Compare with NumPy Method

이전에 인접 감염 시뮬레이션을 작성하며 주어진 점들에 대해 쿼리 점과의 거리가 d 이하인 것들을 찾는 알고리즘을 다룬 적이 있습니다.

이 문제는 공간 지리에서 유용하게 사용될 수 있습니다. 가령, 우리가 사용하는 지도 앱에서 현위치로부터 가까운 음식점 리스트, 가장 가까운 약국을 찾을 때 이 문제를 해결해야 합니다. 또한 기계 학습 알고리즘의 하나인 k-NN 탐색에서도 이 문제를 빠르게 해결하여 모델의 성능을 높일 수 있습니다.

k-d 트리는 이러한 연산에 최적화된 트리 자료 구조로, 공간을 분할하여 자료를 저장합니다. 이는 특정 점 (또는 그 주변의 점)을 탐색하는데 $O(\log n)$의 시간복잡도가 소요되어, 일반적인 자료 구조($O(n)$)보다 효율적입니다. 이는 일반적인 자료 구조가 2차원 이상의 자료를 저장할 때, 특정 차원에 대해 정렬하더라도 이후 나머지 차원에 대해서는 선형적으로 탐색할 수 밖에 없기 때문이라는 한계를 가지고 있기에 가능한 것입니다.

최악의 경우가 $O(n)$인 이유는, 만일 점이 한 위치에 대해 몰려 있고, 그 밀도가 위치에 근접해감에 따라 높아지는 경우 공간 분할의 효율이 낮아지기 때문입니다. 따라서, k-d 트리는 점이 고루 분포해 있는 경우 사용하기 좋습니다.

SciPy의 cKDTree

과학/기술 컴퓨팅에 널리 사용되는 SciPy의 spatial 모듈에는 k-d 트리를 구현한 KDTree 클래스와 cKDTree 클래스가 있습니다.

두 클래스 모두 동일한 함수를 구현하고 있는 같은 모듈이지만, cKDTree는 C++를 바탕으로 구현하였기 때문에 훨씬 빠릅니다. 따라서 cKDTree를 사용하는 것이 더욱 바람직합니다.

트리를 생성하기 위해서는 단순히 점 자료를 인자에 넣기만 하면 됩니다. 추가적인 인자(leafsize, compact_nodes 등)는 여기를 참조하세요.

import numpy as np
from scipy.spatial import cKDTree

points = np.random.rand(100, 2) # 2차원 점 100개 생성
tree = cKDTree(points)

점의 차원에는 제한이 없지만, 차원이 커질 경우 Brute-force 보다 느려질 수 있다는 점을 유의하시기 바랍니다.

자주 사용하는 함수들

1. query

d, idx = tree.query(x, k=7, p=2, workers=1)

x는 점 또는 점 배열입니다. 쿼리 점으로부터 가장 가까운 k개의 점까지의 거리(d)와 그 색인(i)을 반환합니다. 이 때 p값은 p-norm이라 하여, 어떤 L^p 공간을 사용할 것인지를 결정합니다.

가령, 우리가 흔히 사용하는 좌표의 차의 제곱의 합을 제곱근한 것은 Euclidean 거리라고 합니다. 하지만, 좌표의 차의 절대값을 합한 Manhattan 거리를 사용하고자 한다면 p의 값은 1이 될 것입니다. 이를 임의의 수로 확장한 것이 Minkowski 거리입니다. query 함수에서는 이를 임의의 실수로 둘 수 있습니다.

worker 인자는 계산을 위해 얼마나 많은 스레드를 사용할 것인지를 설정하고, -1일 경우 모든 스레드를 사용합니다. 그 밖의 인자는 다음을 참조하세요.

2. query_ball_point

idx = tree.query_ball_point(x, r=0.5, p=2, return_sorted=True)

query 함수가 총 k개의 가까운 점을 반환하였다면, query_ball_point 함수는 쿼리 점으로부터 거리가 r보다 작은 모든 점을 반환합니다. 단, 이 때는 점까지의 거리는 반환하지 않으며 색인 값만을 반환합니다. 선택 인자인 return_sorted는 반환되는 색인 값을 정렬할 지를 결정합니다. 그 밖의 인자는 다음을 참조하세요.

NumPy를 이용한 방법과의 비교

어떤 N개의 2차원 점이 존재할 때, 총 M개의 쿼리점에 대하여 거리가 d 이하인 점의 색인을 반환하는 함수를 작성해 보겠습니다.

import numpy as np

points = np.random.rand(N, 2)
queries = np.random.rand(M, 2)
distance = d

1. Brute-force

가장 쉽게 생각하는 방법은 Brute-force를 이용한 방법입니다. NumPy의 벡터화된 연산을 이용하여 빠르게 계산할 수 있습니다.

return [np.where(np.sum((points - query) ** 2), axis=1) < distance ** 2)[0] for query in queries]

np.where이 Tuple을 반환하므로 첨자 0을 넣어주는 것이 좋습니다.

2. Pre-processed Sorting

모든 N개의 점으로부터 비교하기 보다는 점을 미리 $x$좌표에 대해 정렬한 후, 이분 탐색법을 이용하여 거리가 d 이하일 수 있는 점의 후보를 추리는 것도 좋은 방법입니다.

sorted_index = np.argsort(points[:,0])
points_sorted = points[sorted_index]
sorted_x = points_sorted[:,0]

result = []
for query in queries:
    left = np.searchsorted(sorted_x, query[0] - distance, side='left')
    right = np.searchsorted(sorted_x, query[0] + distance, side='right')
    candidates = points_sorted[left:right]
    
    result.append(sorted_index[np.where(np.sum((candidates - query) ** 2, axis=1) < distance ** 2)[0] + left])
   
return result

searchsorted 함수는 정렬된 배열에서 이분 탐색을 통해 요소를 찾아냅니다. 인자 side는 'left'와 'right'를 설정할 수 있으며, 각각 C++의 lower_bound와 upper_bound에 대응된다고 생각하면 됩니다.

이의 결과값은 left로부터의 색인 거리와 같으므로, 이를 sorted_index에 넣을 때는 다시 left를 더한 값을 넣어야 합니다.

3. k-d Tree

return tree.query_ball_point(points, distance)

어떤 방법이 가장 좋을까?

상황에 따라 세 방법 중 어떤 것이 가장 효율적일지가 달라집니다.

본 상황에서는 점의 분포를 균등하게 하였기 때문에 kd-Tree의 효율이 좋지만, 만약 점이 특정 위치에 편중되어 있는 상황이라면 성능이 낮아질 수도 있습니다.

점의 개수가 적거나, 쿼리량이 많지 않는 경우에는 Brute-force를 이용한 방법이 더 효과적일 수 있습니다. 2번과 3번의 방법은 각각 정렬/트리 생성에 따른 오버헤드가 있기 때문입니다. 반면 찾아야 할 점이 변하지 않는 상황이고 정렬된 배열이나 트리가 주어진 상황에서는 2번과 3번의 방법이 더 좋습니다.

세 방법 모두 쿼리량 $m$에 대해 $O(m)$로 소요 시간이 늘어나지만, 쿼리량이 매우 많을 경우 가장 효과적인 것은 k-d 트리입니다.

하지만 모든 것에 절대란 존재하지 않기 때문에 서비스에 이러한 기능을 구현할 경우, 미리 방법을 테스트하여 가장 효과적인 방법을 택할 수 있기 바랍니다.