☀️ haejun

Today-·Total-

BallTree 알고리즘

6 min read

Summary

  • BallTree는 유클리드 거리를 기반으로 데이터 공간을 구체(Ball)로 감싸 계층적인 이진 트리를 구성하는 최근접 이웃 탐색 알고리즘이다.
  • 탐색 과정에서 불필요한 자식 노드들을 효율적으로 제거하여 데이터가 많아질수록 계산량을 획기적으로 줄여준다.
  • KD-Tree에 비해 초기 트리 구축 비용은 더 들지만, 차수가 커질수록 데이터를 훨씬 빠르게 탐색할 수 있다.
  • 가장 거리가 먼 포인트들을 기준으로 재귀적으로 하위 Ball을 생성하고, 탐색 시에는 상위 Ball에서 리프 노드까지 좁혀가는 방식을 사용한다.
  • sklearn 라이브러리로 쉽게 구현할 수 있으며, 특정 반경 내의 격자 데이터를 추출하는 등 공간 데이터 분석에 유용하다.

개요

BallTree 알고리즘이란?

BallTree는 최근접 이웃 탐색(KNN search)과 유사하며, 특정 데이터를 탐색하는 tree 구조 알고리즘이다.

  • 목적: 유클리드 거리를 기반으로 빠르게 최근접 이웃을 탐색
  • 핵심: 데이터 공간을 Ball로 감싸는 방식인 이진 트리를 구성
  • 주요 용도: KNN, 유사도 검색, 고차원 거리 계산

주요 용어

용어의미
Ball중심점 와 을 가지는 구체(데이터 포인트는 해당 Ball에 존재)
Leaf Node실제 데이터 포인트들이 저장된 하위 노드
Internal Node두 개의 자식 Ball을 갖는 노드
TreeBall들이 계층적으로 구성된 이진 트리 구조

특징

BallTree는 KD-Tree와 비교하여, 초기 트리 구성 비용이 크지만 차수가 커질수록 데이터를 훨씬 빠르게 탐색할 수 있는 장점이 있다.

구분특징
단순 거리 계산데이터 수 증가할수록 계산량 기하급수적 증가
BallTree질의한 거리보다 먼 노드는 자식 노드까지 모두 버려 계산량 감소

알고리즘

BallTree는 다음 순서로 Input Data와 가장 가까운 Point를 탐색한다.

  1. 랜덤한 point를 선택하는 과정을 재귀적으로 수행하여 Ball 생성
  2. Ball 기반 Tree 구성
  3. Input data가 속한 Ball을 찾는 트리 노드 탐색하여 가장 가까운 Ball 탐색
  4. 해당 Ball에 있는 Point 중 가장 가까운 Point 탐색

Ball 생성

랜덤한 Point P1을 선택한 후, 가장 거리가 먼 포인트 P2와 P2에서 가장 거리가 먼 포인트 P3를 선택한다.

P2와 P3를 잇는 선을 생성하여 해당 선의 중간점을 기준으로 선을 나눈다 → l1, l2.

다른 Point들을 나누어진 각 선에 수선의 발을 내리고(projection), 각 선들에 투영된 점들의 축 성분에 합의 평균을 새로운 Ball의 중심점으로 각각 생성한다.

Tree 구성

위 과정을 재귀적으로 반복하여 최종 Ball을 생성한 후, Ball의 위계 구조에 맞게 Tree를 구성한다.

Ball 탐색

트리 노드 탐색을 통해 Input Data(8,5)가 속한 Ball을 찾으며, 단계적으로 가장 가까운 Ball을 선택한다 (B1 - B3 - B6).

최근접 Point 탐색

최종 Ball(B6) 내 Point들과의 유클리드 거리를 산출한 후, 가장 가까운 Point (8,3)을 선택한다.

Python 코드 예시

격자 데이터 활용하여, 각 격자별 반경 내 속한 격자 목록 산출

from sklearn.neighbors import BallTree
import numpy as np
 
# 각 격자별 중심좌표 생성
coords = np.array([(geom.centroid.x, geom.centroid.y) for geom in gdf.geometry])  # geometry 존재
coords = np.vstack([gdf['x'].values, gdf['y'].values]).T  # 좌표값만 존재, (N,2) array 생성
 
# BallTree 초기화 (유클리디안 거리, 미터 단위)
tree = BallTree(coords, metric='euclidean')
 
# 특정 거리 반경 이내 인덱스 추출 (예. 3000 미터)
neighbors_idx = tree.query_radius(coords, r=3000)
 
# 추출 예시: 0번째 index 격자 기준 반경 3000m 이내의 격자들
gdf.iloc[neighbors_idx[0]]

Reference

Graph View