볼 트리는 다차원 공간의 점들을 볼(ball)이라고 불리는 중첩된 초구(hypersphere)의 계층 구조로 분할하는 데 사용되는 이진 트리 데이터 구조이다. 트리의 각 노드는 데이터 점들의 부분 집합을 포함하는 볼을 나타내며, 루트 노드는 모든 점을 포함한다. 트리는 데이터 점들을 재귀적으로 두 그룹으로 분할하고, 각 그룹을 자체 볼로 감싸는 과정을 최대 리프 크기나 최소 볼 반지름과 같은 중지 기준이 충족될 때까지 반복하여 구축된다. 볼 트리는 주로 최근접 이웃 질의, 유사도 검색, 커널 밀도 추정을 가속화하는 데 사용되며, 일반적으로 기계 학습 응용 분야, 예를 들어 데이터 증강 및 클러스터링에서 활용된다.
볼 트리가 k-d 트리와 같은 대체 공간 인덱싱 구조보다 갖는 주요 장점은 고차원 공간에서의 성능이다. k-d 트리는 축 정렬 초평면을 사용하여 공간을 분할하는데, 이는 차원의 저주로 인해 차원이 증가함에 따라 비효율적이 될 수 있다. 반면 볼 트리는 데이터의 국소 분포에 적응하는 메트릭 볼을 사용하여 분할한다. 이러한 특성 덕분에 볼 트리는 검색 공간의 큰 부분을 더 효과적으로 가지치기할 수 있으며, 특히 데이터가 클러스터링되거나 낮은 고유 차원 구조를 가질 때 유리하다. 결과적으로 볼 트리는 로봇 공학, 천문학, 신경망 하이퍼파라미터 튜닝을 포함한 다양한 과학 및 공학 분야에서 채택되었다.
구조 및 구축
볼 트리는 각각 중심과 반지름으로 표시되는 일련의 중첩된 볼로 정의된다. 중심은 종종 볼 내에 포함된 점들의 중심점(centroid)으로 선택되며, 반지름은 중심에서 해당 볼의 임의의 점까지의 최대 거리이다. 트리는 재귀 알고리즘을 사용하여 구축된다. 각 단계에서 알고리즘은 현재 중심에서 가장 먼 점을 선택한 다음, 첫 번째 선택된 점에서 가장 먼 두 번째 점을 선택한다. 이 두 점은 피벗 역할을 하여 나머지 점들을 각 피벗과의 근접성에 따라 두 클러스터로 분할한다. 이 과정은 각 결과 클러스터에 대해 반복되며, 리프 노드가 지정된 수(일반적으로 작은 상수)보다 적은 점을 포함할 때까지 계속된다.
볼 트리의 구축 시간은 저차원에서 n개의 점에 대해 O(n log n)이지만, 고차원에서는 거리 계산 비용 증가로 인해 성능이 저하될 수 있다. 구축을 개선하기 위한 여러 전략이 존재하며, 여기에는 근사 최원점 선택과 로그 깊이를 보장하기 위한 트리 균형화가 포함된다. 메트릭 선택도 구조에 영향을 미치며, 유클리드 거리가 일반적이지만 볼 트리는 삼각 부등식을 만족하는 모든 메트릭(예: 맨해튼 또는 민코프스키 거리)을 사용하여 구축할 수 있다.
최근접 이웃 검색
볼 트리의 가장 일반적인 용도는 분류 및 회귀 작업에서 기본적인 k-최근접 이웃(k-NN) 검색이다. 검색 알고리즘은 트리를 재귀적으로 탐색하며 지금까지 발견된 최상의 후보 점들의 우선순위 큐를 유지한다. 각 노드에서 알고리즘은 질의 점에서 노드의 볼 중심까지의 거리를 계산한다. 이 거리에서 볼의 반지름을 뺀 값이 현재 k번째 최근접 거리보다 크면 해당 하위 트리 전체를 가지치기할 수 있는데, 이는 볼 내의 어떤 점도 현재 최적보다 가까울 수 없기 때문이다. 이 가지치기는 볼 내의 임의의 점이 질의로부터 최소한 특정 거리 이상 떨어져 있음을 보장하는 삼각 부등식을 활용한다.
실제로 볼 트리는 k-NN의 계산 복잡도를 질의당 O(n)(단순 스캔)에서 저고유 차원 데이터의 경우 평균적으로 대략 O(log n)으로 줄일 수 있다. 그러나 차원이 증가함에 따라 가지치기 효율성은 감소한다. 연구자들은 질의 트리와 데이터 트리를 동시에 탐색하는 이중 트리 알고리즘과 같은 변형을 제안하여 고차원 설정에서 성능을 더욱 개선했다. 이러한 기술은 인공 지능 프레임워크, 예를 들어 scikit-learn 및 아마존 웹 서비스 SageMaker에 통합된 라이브러리에 적용되었다.
응용 분야
볼 트리는 기계 학습 파이프라인에서 널리 사용된다. 커널 밀도 추정에서 볼 트리는 개별 점 대신 점 클러스터의 기여를 집계하여 국소 밀도 추정 계산을 가속화한다. 또한 교차 주의 메커니즘과 트랜스포머 모델의 다중 헤드 주의 아키텍처에도 등장하며, 관련 키의 효율적 검색이 유용할 수 있지만 전통적인 구현은 밀집 주의를 사용한다.
기계 학습 외에도 볼 트리는 로봇 공학의 경로 계획 및 충돌 감지, 컴퓨터 그래픽스의 광선 추적, 지리 정보 시스템의 공간 질의에 사용된다. 예를 들어 웨이모 및 기타 자율 주행 차량 시스템은 센서 데이터를 인덱싱하여 지도 특징의 빠른 최근접 이웃 검색을 위해 볼 트리를 사용한다. 천문학에서 볼 트리는 빠른 근접 질의로 별을 목록화하는 데 도움을 준다. 이러한 다양성은 해시 기반 근사 방법과 달리 기본 메트릭의 단순성과 정확한 질의 결과 보장에서 비롯된다.
다른 구조와의 비교
볼 트리는 종종 k-d 트리, R-트리, 국소성 민감 해싱(LSH)과 비교된다. k-d 트리는 축 정렬 분할을 사용하며, 이는 저차원(일반적으로 20 미만)에서 효율적이지만 고차원에서는 과도한 역추적으로 인해 성능이 저하된다. 볼 트리는 축 정렬 분할을 요구하지 않으며 데이터의 형태에 적응할 수 있다. 데이터베이스에서 경계 사각형에 주로 사용되는 R-트리는 임의 메트릭에 대해 덜 유연하다. LSH는 근사 결과를 제공하며 극도로 높은 차원에서 더 빠르지만 정확한 최근접 이웃을 보장하지 않는다. 볼 트리는 중간 지점을 제공한다: k-d 트리보다 고차원 성능이 우수한 정확한 질의를 제공하지만, 매우 높은 차원에서는 여전히 선형 검색을 초과한다.
한계 및 확장
볼 트리의 주요 한계는 차원의 저주이다: 차원 수가 증가함에 따라 주변 공간에 대한 볼 부피의 비율이 극히 작아져 가지치기가 비효율적이 된다. 이러한 경우 LSH와 같은 근사 방법이 선호된다. 또한 볼 트리는 정적 구조이며, 점을 삽입하거나 삭제하려면 트리를 재구축해야 하므로 균형 변형을 사용하지 않는 한 동적 데이터셋에는 적합하지 않다.
확장에는 상위 수준에서 볼 분할을 사용하고 하위 수준에서 축 정렬 분할을 사용하는 k-d 트리 볼 하이브리드와 특정 데이터 가정 하에 거의 로그 질의 시간을 보장하는 커버링 트리가 포함된다. 딥 러닝 모델이 분할 경계를 예측하는 적응형 메트릭 및 학습된 인덱스에 대한 연구가 계속되고 있지만, 이러한 접근 방식은 여전히 틈새 시장에 머물러 있다.
같이 보기
- k-d 트리
- 최근접 이웃 검색
- 메트릭 트리
- 차원 축소