[DIP] K-Means Tree: Nearest Neighbor Search

https://gist.github.com/dsaint31x/f7f59e6b99f6ef3dc46e4e7da8826cd9

dip_kmeans_tree.ipynb

 

---

0. 소개

K-Means Tree는

• 대규모 데이터에서
• 효율적으로 Nearest Neighbor Search (최근접 이웃 검색)을 수행하기 위해
• 계층적으로 데이터를 K개의 cluster로 clustering하여
• 일종의 Binary Tree 자료구조 를 만드는 알고리즘.

k-d Tree에서 k는 검색하는 vector space의 dimensionality에 해당하며,
K-Means Tree는 각 depth에서 K-Means Clustering이 수행됨을 의미: K는 클러스터의 갯수임.

 

OpenCV에서는 K-Means Tree를

• 주로 FLANN(또는 다른 유사한 데이터 검색 알고리즘)에서
  • k-d Tree 와 함께 기본 알고리즘으로 제공되어,
• Approximate Nearest Neighbor Search를 구현함.
• Matching Task 수행에서 자주 사용됨.

K-Means Tree는
OpenCV의 FLANN (Fast Library for Approximate Nearest Neighbors)에서
사용 가능한 고속 근사 검색 알고리즘 중 하나임.

---

1. 목적:

각 depth별로 데이터 세트를 K개의 Clusters로 나누어( Clustering 또는 Partitioning이라고도 불림),
검색 범위를 좁히는 계층적 데이터 구조(tree)를 생성.

---

2. 동작 원리:

1. 데이터 입력
   • 고차원 데이터나 특징 벡터 집합을 입력으로 받음.
2. 트리 생성
   • 입력 데이터를 기반으로 K-Means 알고리즘을 반복적으로 수행하여 트리 형태로 클러스터링.
   • 첫 번째 레벨에서 데이터를 K개의 클러스터로 나눔.
   • 각 클러스터에 대해 다시 K-Means를 수행하여 하위 클러스터 생성: Tree에서 Depth증가
   • 이 과정을 데이터가 충분히 작은 크기로 나뉠 때까지 반복.
3. 검색(Query)
   1. 검색 시, 입력된 query vector는 root 노드에서부터 시작하여 가장 가까운 centroid(중심)을 따라 이동.
   2. leaf 노드에 도달하면 해당 클러스터에서 가장 가까운 이웃(Nearest Neighbor)을 찾음.

---

3. K-Means Tree의 장점

1. 효율적인 검색:
   • K-Means Tree는 검색 공간을 계층적으로 줄이므로
   • 대규모 데이터에서도 빠른 검색 가능.
2. 근사 검색:
   • 정확도를 약간 희생하여 속도를 높이는 근사 알고리즘.
3. 계층적 구조:
   • 트리 구조는 메모리 사용량이 적고, 높은 차원에서도 유리함.

---

4. K-Means Tree와 다른 알고리즘 비교

k-d Tree:

• K-Means Tree는 k-d Tree보다 고차원 데이터에서 더 효율적.
• k-d Tree는 데이터 분포에 따라 성능 저하가 발생할 수 있음.

Linear Search:

• 모든 데이터를 하나씩 확인하는 Linear Search보다 일반적으로 훨씬 빠름.
• 보다 자세한 것은 다음 URL참고.
  2024.11.16 - [Computer/CE] - [CE] Linear Search, Naive Search, Brute Force Search

---

5. OpenCV에서 K-Means Tree 사용 예시

다음은 OpenCV의 FLANN을 사용하여 K-Means Tree 기반 근사 최근접 이웃 검색을 수행하는 예시 코드임:

import cv2
import numpy as np

# 샘플 데이터 생성
features = np.random.rand(1000, 128).astype(np.float32) # 1000개의 128차원 특징 벡터
query = np.random.rand(1, 128).astype(np.float32)  # 검색할 query vector

# FLANN 파라미터 설정
index_params = dict(
                    algorithm=1,   # cv2.FLANN_INDEX_KMEANS 가 정의 안된 경우가 많음.1
                    branching=32,  # 각 노드의 자식 수 = 한 노드가 나눠지는 클러스터의 숫자!
                    iterations=11, # k-means 클러스터링에서 centroid 찾기 위한 반복횟수
                    centers_init=cv2.KMEANS_RANDOM_CENTERS,
                    )
search_params = dict(checks=50)    # 트리 탐색 횟수

# FLANN matcher 객체 생성
flann = cv2.FlannBasedMatcher(index_params, search_params)

# 인덱스 구축 및 검색
matches = flann.knnMatch(query, features, k=2)  # 각 쿼리에 대해 2개의 최근접 이웃 찾기

# 결과 출력
for m, n in matches:
    print(f"최근접 거리: {m.distance :.2f}, 두 번째 근접 거리: {n.distance:.2f}")
    print(f"ratio: {m.distance/n.distance :.2f}")

이 코드는 FLANN을 사용하여 K-Means Tree 기반의 고속 근사 검색을 수행하는 방법을 보여줌.

 

관련된 Hyperparameters 의 상세 설명은 다음을 참고:

2024.11.25 - [Programming/DIP] - [OpenCV] K-Means Tree Hyper-parameters: FLANN based Matcher

[OpenCV] K-Means Tree Hyper-parameters: FLANN based Matcher

 

 

---

관련자료들

2023.02.20 - [Computer/CE] - [CE] Tree vs. Graph

[CE] Tree vs. Graph

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

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