KD-Tree for nearest neighbors in SciPy

Introduction

A KD-Tree helps find points closest to a target quickly. It organizes data so searching neighbors is fast and easy.

Finding the closest store to your location on a map.

Recommending similar products based on user preferences.

Grouping similar images by their features.

Finding nearest friends in a social app.

Matching a new data point to existing clusters.

Syntax

SciPy

from scipy.spatial import KDTree

tree = KDTree(data_points)
distances, indexes = tree.query(target_points, k=number_of_neighbors)

data_points is a list or array of points (each point is a list of numbers).

k is how many nearest neighbors you want to find.

Examples

Find the single nearest neighbor to point [2, 3].

SciPy

from scipy.spatial import KDTree

data = [[1, 2], [3, 4], [5, 6]]
tree = KDTree(data)
dist, idx = tree.query([2, 3], k=1)
print(dist, idx)

Find the two nearest neighbors for two target points.

SciPy

from scipy.spatial import KDTree

data = [[0, 0], [1, 1], [2, 2], [3, 3]]
tree = KDTree(data)
dist, idx = tree.query([[1, 1], [2, 2]], k=2)
print(dist)
print(idx)

Sample Program

This program finds the closest store to a customer's location using KD-Tree.

SciPy

from scipy.spatial import KDTree

# Data points: locations of 5 stores
stores = [[1, 2], [3, 5], [4, 4], [7, 8], [9, 1]]

# Build KD-Tree
store_tree = KDTree(stores)

# Customer location
customer = [3, 3]

# Find nearest store
distance, index = store_tree.query(customer, k=1)

print(f"Nearest store is at {stores[index]} with distance {distance:.2f}")

Important Notes

KD-Tree works best with low to medium dimensions (usually less than 20).

For very high dimensions, other methods might be faster.

Distances are usually Euclidean by default.

Summary

KD-Tree organizes points to quickly find nearest neighbors.

Use scipy.spatial.KDTree to build and query the tree.

It helps in tasks like location search, recommendations, and clustering.