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).

Practice

1. What is the main purpose of using a KD-Tree in data science?

easy

A. To visualize data distributions

B. To sort data in ascending order

C. To perform linear regression

D. To quickly find nearest neighbors in a set of points

Solution

1. Step 1: Understand KD-Tree functionality

   A KD-Tree is a data structure designed to organize points in space for fast nearest neighbor searches.

2. Step 2: Compare with other options

   Sorting, regression, and visualization are different tasks not related to KD-Tree's main use.

3. Final Answer:

   To quickly find nearest neighbors in a set of points -> Option D

4. Quick Check:

   KD-Tree = nearest neighbors [OK]

Hint: KD-Tree = fast nearest neighbor search [OK]

Common Mistakes:

• Confusing KD-Tree with sorting algorithms
• Thinking KD-Tree is for regression
• Assuming KD-Tree is for visualization

2. Which of the following is the correct way to create a KD-Tree using scipy.spatial for points stored in a variable points?

easy

A. tree = KDTree(points)

B. tree = KDTree.build(points)

C. tree = scipy.KDTree(points)

D. tree = spatial.KDTree(points)

Solution

1. Step 1: Recall correct import and usage

   The KDTree class is imported from scipy.spatial and instantiated directly with points.

2. Step 2: Check each option

   tree = KDTree(points) correctly calls KDTree(points). tree = KDTree.build(points) uses a non-existent build method. tree = scipy.KDTree(points) misses the spatial submodule. tree = spatial.KDTree(points) uses spatial without import.

3. Final Answer:

   tree = KDTree(points) -> Option A

4. Quick Check:

   Instantiate KDTree with points directly [OK]

Hint: Use KDTree(points) after importing from scipy.spatial [OK]

Common Mistakes:

• Trying to call a build method that doesn't exist
• Missing the spatial submodule in import
• Using wrong module prefixes

3. Given the following code, what is the output?

from scipy.spatial import KDTree
points = [[1, 2], [3, 4], [5, 6]]
tree = KDTree(points)
dist, idx = tree.query([2, 3])
print(idx)

medium

A. 1

B. 0

C. 2

D. [0, 1]

Solution

1. Step 1: Understand the query point and points list

   The query point is [2, 3]. The points are [1, 2], [3, 4], and [5, 6].

2. Step 2: Calculate distances to each point

   Distance to [1, 2] is sqrt((2-1)^2+(3-2)^2)=sqrt(1+1)=1.414.
   Distance to [3, 4] is also 1.414.
   Distance to [5, 6] is larger.

3. Step 3: KDTree.query returns the index of the first nearest neighbor found

   Since [1, 2] is at index 0 and [3, 4] at index 1 with same distance, it returns index 0.

4. Final Answer:

   0 -> Option B

5. Quick Check:

   Nearest neighbor index = 0 [OK]

Hint: KDTree.query returns index of closest point (first if tie) [OK]

Common Mistakes:

• Assuming it returns multiple indices for ties
• Mixing up distance and index output
• Forgetting zero-based indexing

4. Identify the error in the following code snippet:

from scipy.spatial import KDTree
points = [[0, 0], [1, 1], [2, 2]]
tree = KDTree(points)
nearest = tree.query([1, 1, 1])
print(nearest)

medium

A. KDTree.query requires two arguments

B. KDTree cannot be created from a list

C. The query point has wrong dimension

D. Missing import for numpy

Solution

1. Step 1: Check dimensions of points and query

   Points are 2D (each has 2 coordinates). Query point has 3 coordinates.

2. Step 2: Understand KDTree.query requirements

   The query point must have the same dimension as points used to build the tree.

3. Final Answer:

   The query point has wrong dimension -> Option C

4. Quick Check:

   Query point dimension must match points [OK]

Hint: Query point dimension must match KDTree points [OK]

Common Mistakes:

• Ignoring dimension mismatch errors
• Thinking KDTree needs numpy arrays only
• Assuming query needs multiple arguments

5. You have a dataset of 2D points and want to find the 3 nearest neighbors for each point efficiently. Which code snippet correctly builds a KD-Tree and queries for 3 neighbors of the point [4, 5]?

hard

A. from scipy.spatial import KDTree
points = [[1,2],[3,4],[5,6],[7,8]]
tree = KDTree(points)
dist, idx = tree.query([4,5], k=3)
print(idx)

B. from scipy.spatial import KDTree
points = [[1,2],[3,4],[5,6],[7,8]]
tree = KDTree(points)
idx = tree.query([4,5], neighbors=3)
print(idx)

C. from scipy.spatial import KDTree
points = [[1,2],[3,4],[5,6],[7,8]]
tree = KDTree(points)
dist, idx = tree.query([4,5], k=1)
print(idx)

D. from scipy.spatial import KDTree
points = [[1,2],[3,4],[5,6],[7,8]]
tree = KDTree(points)
dist, idx = tree.query([4,5], k=[3])
print(idx)

Solution

1. Step 1: Build KDTree with points

   Instantiate KDTree with the list of 2D points.

2. Step 2: Query for 3 nearest neighbors correctly

   Use k=3 in tree.query to get distances and indices of 3 nearest neighbors.

3. Step 3: Check each option

   from scipy.spatial import KDTree points = [[1,2],[3,4],[5,6],[7,8]] tree = KDTree(points) dist, idx = tree.query([4,5], k=3) print(idx) uses correct syntax and parameters.
   from scipy.spatial import KDTree points = [[1,2],[3,4],[5,6],[7,8]] tree = KDTree(points) idx = tree.query([4,5], neighbors=3) print(idx) uses invalid parameter neighbors.
   from scipy.spatial import KDTree points = [[1,2],[3,4],[5,6],[7,8]] tree = KDTree(points) dist, idx = tree.query([4,5], k=1) print(idx) queries only 1 neighbor.
   from scipy.spatial import KDTree points = [[1,2],[3,4],[5,6],[7,8]] tree = KDTree(points) dist, idx = tree.query([4,5], k=[3]) print(idx) uses list for k, which is invalid.

4. Final Answer:

   Option A code snippet -> Option A

5. Quick Check:

   Use k=3 in query for 3 neighbors [OK]

Hint: Use k=3 in query() to get 3 nearest neighbors [OK]

Common Mistakes:

• Using wrong parameter name instead of k
• Querying only one neighbor when more needed
• Passing list instead of integer for k