[ML] Nearest Neighbor Search: k-d Tree

1. 소개

1975년 Nearest Neighbor Search를 위해

Binary Search Tree (BST)의 개념을 활용하여
k-diemensional vector space에서 동작하도록
Bently가 제안한 알고리즘.

Lowe와 Muja가 2014년 제안한 FLANN 에서는

보다 개선된 Multiple k-d Tree가 제안되었고,
이 Multiple k-d Tree가 openCV에서 matching에서 가장 많아 사용되는 방법 중 하나임.

GitHub - flann-lib/flann: Fast Library for Approximate Nearest Neighbors

Fast Library for Approximate Nearest Neighbors. Contribute to flann-lib/flann development by creating an account on GitHub.

github.com

2. k-d Tree 만들기

$n$개의 feature vector $X=\left\{ \textbf{x}_1, \cdots,\textbf{x}_n \right\}$가 있고,
각 feature vector는 $k$ dimensionality일 때,

k-d Tree는 다음과 같이 생성함 (Variance-Based Splitting).

$k$ dimensional vector이므로, $k$개의 component (=feature) 중에서 variance가 큰 component를 선택(이를 $d$ 열이라고 가정)하고, 해당 component로 $X$를 sorting.
k-d Tree도 Binary Tree이므로 좌우 균형을 맞추어야 성능이 좋은 특성을 보이므로
해당 column의 median 값을 가지는 Vector를 $X$에서 구하고 (sorting 된 것에서 중간을 선택!),
이를 root node로 설정 : $\textbf{x}_d$라고 가정.
$\textbf{x}_d$를 기준으로 $X_\text{left}$와 $X_\text{right}$를 나누고, 이들 각각에 대해 variance가 가장 큰 component를 구하고, 해당열로 정렬 후 해당 열의 median을 가지는 vector를 기준으로 좌/우 를 다시 분할.
3번을 재귀적으로 반복.

3. k-d Tree 분할방식

k-d Tree는 분할하는 축 선택 방식에 따라 다음으로 나뉨.

3-1. 순환 방식 (Cyclic Splitting)

설명:
- 트리의 depth에 따라 축을 순서대로 순환하며 선택하는 방식.
예: depth = 0일 때 x 축, depth = 1일 때 y 축, depth = 2일 때 다시 x 축 사용.
장점:
- 구현이 간단하고 계산 비용이 적음.
단점:
- 데이터가 특정 방향으로 편향된 경우, 비효율적일 수 있음.
- 고차원 데이터에서는 분할의 효율성이 떨어질 수 있음.

3-2. 분산 기반 방식 (Variance-Based Splitting)

설명:
- 각 축에 대해 데이터의 분산(variance) 을 계산하여, 분산이 가장 큰 축을 기준으로 분할.
장점:
- 데이터가 편향된 경우에도 균일한 분할 가능.
- 트리가 균형 있게 구성될 가능성이 높음.
단점:
- 각 노드에서 분산을 계산해야 하므로, 추가적인 계산 비용 발생.
- 대규모 데이터셋에서는 탐색 속도 저하 우려.

3-3. 균형 트리 방식 (Balanced Tree Splitting)

설명:
- 각 축에서 데이터를 반으로 나눌 수 있는 중간값을 기준으로 분할하여 균형 트리(balanced tree) 를 생성.
장점:
- 트리가 완벽한 균형에 가까워져, 탐색 성능이 향상됨.
- 특정 데이터 분포에 크게 영향을 받지 않음.
단점:
- 트리 생성 시 모든 데이터에 대한 정렬 필요.
- 정렬 과정에서 추가적인 시간 복잡도($O(n \log n)$) 발생.

3-4. 분할방식 비교 요약

방식	장점	단점
순환 방식	구현이 간단, 계산 비용이 낮음	데이터 편향 시 비효율적, 고차원에서 성능 저하
*분산 기반 방식*	편향된 데이터에도 어느정도 균일한 분할 가능	추가적인 분산 계산 비용 발생
균형 트리 방식	균형 트리로 탐색 성능 향상	데이터 정렬에 높은 시간 복잡도

3-5. 분할방식 선택 가이드

순환 방식: 차원이 낮고, 데이터가 고르게 분포된 경우 적합.
분산 기반 방식: 데이터가 특정 축으로 편향된 경우 효과적. ****
균형 트리 방식: 탐색 성능이 중요한 경우나 데이터의 분포를 알 수 없을 때 유리.

4. 예제: k-d Tree 구성

$X=\left\{ (3,1), (2,3), (6,2), (4,4), (3,6), (8,5), (7,6.5),(5,8),(6,10),(6,11)\right\}$의
2-d feature vector 집합으로 k-d Tree를 만드시오.

Ans.

- $d=2$ 이며, 2번째 component(← $x_2$)가 variance가 크므로 root node에서 이 축에서의 median을 고름.

- 앞서 설명한 방식으로 구한 k-d Tree는 다음 그림과 같음.

https://product.kyobobook.co.kr/detail/S000001743418

5. 예제: k-d Tree 로 Nearest Neighbor 탐색.

문제: $\textbf{x}=(7,5.5)$를 query feature vector라고 하고, 이의 nearest neighbor를 구하라.

답:

Node의 vector와 기준 component의 값을 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동(분기).

아래 그림에서 보이듯이 $(8,5)$ 노드에 도달.

문제는 더 가까운 $(7, 6.5)$가 반대쪽 Node에 존재함.

6. Back Tracking

위의 경우에서 보이듯이, k-d Tree에서의 back tracking을 수행하지않을 경우, 탐색 결과가 반드시 NN은 아님
(즉, back tracking을 수행하지 않을 경우, 가능성이 높은 후보를 구하게 됨.)

분할된 건너편 partition에 더 가까운 노드가 있을 수 있음.
탐색된 결과와의 거리를 계산후, Stack을 이용한 back tracking을 수행하여 진짜 NN을 구할 수 있음.

6-1. Back tracking 수행

위의 그림에서 주황색 원이 그려진 node들은 탐색과정에서 거쳐온 노드들임.

이들을 stack에 저장 (FILO)
탐색결과인 $(8,5)$ 와 query vector의 거리 계산하고 이를 최소거리로 저장.
Stack에서 노드를 하나 꺼냄.
- Stack 꺼낸 node에서 사용된 decision boundary(seperating boundary)와 query vector와의 거리를 계산
- seperating boundary와의 거리가 현재 최소거리 보다 클 경우, stack에서 다음 node를 뽑아서 앞의 과정을 반복
- seperating boundary와의 거리가 현재 최소거리 보다 작을 경우, 건너편 분할 영역에 보다 가까운 feature vector가 존재할 수 있으므로 현재 stack에서 나온 node에서 자식 노드 중 앞서 거쳐오지 않은 자식 노드에 대해 다시 k-d Tree 탐색을 수행.
- leaf node에 도달하면 다시 back tracking이 재귀적으로 수행됨.
이전 단계들을 stack이 비워질 때까지 수행.

참고: 백트래킹(Backtracking)

Backtracking은
문제를 단계적으로 해결하다가,
더 이상 진행할 수 없거나 해답이 아닌 것으로 판명되면 이전 단계로 돌아가 다른 가능성을 탐색하는 방식.
이 접근법은 주로 조합, 순열, 그래프 탐색, 미로 찾기와 같은 탐색 문제에서 사용되며,
모든 가능한 경우를 체계적으로 탐색하면서 최적의 해를 찾는 데 효과적인 방법.

6-2. back tracking을 이용할 경우 단점

10차원 이상의 feature vector에서 naive search(~brute force search)와 비슷($O(n)$)
high dimension으로 갈 경우엔 Tree구축을 위한 리소스 소모나 요구 계산량을 고려할 때 더 비효율적(Tree가 깊어지고 메모리 사용량이 증가함에도 실제 성능은 비슷하다는 단점을 가짐)이 됨.
물론, back tracking이 없을 경우 O($\log(n)$)의 계산복잡도로 매우 효율적임

2024.11.16 - [Computer/CE] - [CE] Linear Search, Naive Search, Brute Force Search

[CE] Linear Search, Naive Search, Brute Force Search

Linear Search (Naive Search)The simplest solution to the Nearest Neighbor Search problem is to compute the distance from the query point to every other point in the database, keeping track of the "best so far".이 방식에서는 모든 가능한 데이터

dsaint31.tistory.com

7. 대안: Lowe's Approximate Nearest Neighbor Search

back-tracking으로 인한 비효율을 제거
NN 혹은 NN과 가까운 approximate NN을 찾아줌.

Back tracking의 문제점 개선을 위해서,

stack대신에 priority queue인 heap을 이용하여
- 각 노드를 순서대로 back tracking하지 않고 query vector와의 거리가 가까운 것부터 처리.
동시에 heap의 모든 노드를 조사하지 않고 조사할 횟수(checks)를 제한함으로서 approximate NN을 찾음.

Lowe의 2004년 연구에 따르면,

n=100,000, d=128, SIFT feature를 사용한 경우,
200번으로 조사 횟수를 제한해도
95%의 NN을 찾고 5%의 approximate NN을 찾는 정확도를 보이면서도
기존 방법(backtracking)보다 100배 이상의 성능 향상을 보이는 것으로 보고됨.

https://link.springer.com/article/10.1023/B:VISI.0000029664.99615.94

ijcv04.pdf

0.43MB

[ML] Feature Importances for Decision Tree (0)	2024.11.10
[ML] Regularization (0)	2024.10.27
[ML] Linear Classification Model: Hyperplane and Decision Boundary (0)	2024.10.27
[ML] Diabetes Dataset (0)	2024.10.05
[ML] Yeast Dataset (0)	2024.10.05

[ML] Nearest Neighbor Search: k-d Tree

1. 소개

2. k-d Tree 만들기

3. k-d Tree 분할방식

3-1. 순환 방식 (Cyclic Splitting)

3-2. 분산 기반 방식 (Variance-Based Splitting)

3-3. 균형 트리 방식 (Balanced Tree Splitting)

3-4. 분할방식 비교 요약

3-5. 분할방식 선택 가이드

4. 예제: k-d Tree 구성

5. 예제: k-d Tree 로 Nearest Neighbor 탐색.

6. Back Tracking

6-1. Back tracking 수행

6-2. back tracking을 이용할 경우 단점

7. 대안: Lowe's Approximate Nearest Neighbor Search

관련 자료들

'Programming > ML' 카테고리의 다른 글

티스토리툴바