KD-Tree for nearest neighbors in SciPy - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find nearest neighbor using KD-Tree

Given the following code that builds a KD-Tree and queries the nearest neighbor for a point, what is the output printed?

SciPy

from scipy.spatial import KDTree
import numpy as np
points = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
tree = KDTree(points)
distance, index = tree.query([4, 5])
print(index, distance)

A 3 4.242640687119285

B 2 1.4142135623730951

C 0 4.242640687119285

D 1 1.4142135623730951

💡 Hint

Remember that KDTree.query returns the distance first and then the index of the closest point.

The point [4,5] is closest to [3,4] which is at index 1. The Euclidean distance is sqrt((4-3)^2 + (5-4)^2) = sqrt(1 + 1) = 1.414...

❓ data_output

intermediate

Number of neighbors within a radius

Using KD-Tree, how many points lie within a radius of 3 units from the point [5, 5]?

SciPy

from scipy.spatial import KDTree
import numpy as np
points = np.array([[1, 2], [3, 4], [5, 6], [7, 8], [6, 5]])
tree = KDTree(points)
indices = tree.query_ball_point([5, 5], r=3)
print(len(indices))

A 4

B 3

C 2

D 5

💡 Hint

Check which points are within distance 3 from [5,5].

Points at indices 1 ([3,4]), 2 ([5,6]), 4 ([6,5]), and 3 ([7,8]) are within radius 3 except [7,8] is farther than 3. Actually, [7,8] distance is sqrt(4+9)=3.605 >3, so excluded. So points 1,2,4 are within radius 3, total 3 points.

❓ visualization

advanced

Visualizing KD-Tree nearest neighbors

Which option correctly describes the plot generated by the code below?

SciPy

import matplotlib.pyplot as plt
from scipy.spatial import KDTree
import numpy as np
points = np.random.rand(10, 2) * 10
tree = KDTree(points)
query_point = np.array([5, 5])
dist, idx = tree.query(query_point, k=3)
plt.scatter(points[:,0], points[:,1], label='Points')
plt.scatter(query_point[0], query_point[1], color='red', label='Query Point')
plt.scatter(points[idx,0], points[idx,1], facecolors='none', edgecolors='green', s=150, label='Nearest Neighbors')
plt.legend()
plt.show()

A A scatter plot showing 10 points, a red query point at (5,5), and 3 green circles around the nearest neighbors.

B A line plot connecting the query point to all points with green lines.

C A bar chart showing distances of all points from the query point.

D A scatter plot with only the query point and no other points.

💡 Hint

Look at the scatter and color parameters used in the plot.

The code plots all points as dots, the query point in red, and highlights the 3 nearest neighbors with green circles (no fill).

🔧 Debug

advanced

Identify the error in KD-Tree query usage

What error will this code raise when executed?

SciPy

from scipy.spatial import KDTree
import numpy as np
points = np.array([[1, 2], [3, 4], [5, 6]])
tree = KDTree(points)
result = tree.query([1, 2, 3])
print(result)

A ValueError: query point dimension must match data dimension

B TypeError: 'KDTree' object is not callable

C IndexError: index out of range

D No error, prints nearest neighbor index and distance

💡 Hint

Check the dimension of the query point compared to the points used to build the tree.

The KDTree was built with 2D points, but the query point has 3 dimensions, causing a ValueError.

🚀 Application

expert

Using KD-Tree for batch nearest neighbor search

Given a KD-Tree built from 1000 random 3D points, which option correctly returns the indices of the 5 nearest neighbors for each of 10 query points?

SciPy

from scipy.spatial import KDTree
import numpy as np
points = np.random.rand(1000, 3)
tree = KDTree(points)
queries = np.random.rand(10, 3)
result = tree.query(queries, k=5)
print(result[1].shape)

A (10,)

B (5, 10)

C (10, 5)

D (5,)

💡 Hint

Check the shape of the indices array returned by KDTree.query when querying multiple points with k neighbors.

When querying multiple points with k neighbors, the indices array shape is (number_of_queries, k). Here, 10 queries and 5 neighbors gives (10,5).