KD-Tree for nearest neighbors in SciPy - Mini Project: Build & Apply

KD-Tree for nearest neighbors

📖 Scenario: You work at a delivery company. You have a list of warehouse locations with their coordinates. You want to find the closest warehouse to a customer's location quickly.

🎯 Goal: Build a KD-Tree from warehouse coordinates and find the nearest warehouse to a given customer location.

📋 What You'll Learn

Create a list of warehouse coordinates as tuples

Create a KD-Tree from the warehouse coordinates

Query the KD-Tree to find the nearest warehouse to a customer location

Print the nearest warehouse coordinates

💡 Why This Matters

🌍 Real World

Delivery companies use KD-Trees to quickly find the closest warehouse or delivery center to a customer, saving time and fuel.

💼 Career

Data scientists and engineers use KD-Trees for fast spatial searches in logistics, mapping, and recommendation systems.

1

Create warehouse coordinates list

Create a list called warehouses with these exact coordinate tuples: (2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2).

SciPy

# Create the list called warehouses with the given coordinates
# Your code here

Hint

Use square brackets to create a list and put tuples inside it.

2

Import KDTree and create tree

Import KDTree from scipy.spatial. Then create a KD-Tree called tree using the warehouses list.

SciPy

warehouses = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
# Import KDTree and create tree from warehouses
# Your code here

Hint

Use from scipy.spatial import KDTree to import. Then call KDTree(warehouses).

3

Query nearest warehouse

Create a variable called customer_location and set it to the tuple (6, 3). Then use the tree.query() method with customer_location to find the nearest warehouse. Store the result distance in distance and the index in index.

SciPy

from scipy.spatial import KDTree
warehouses = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
tree = KDTree(warehouses)
# Set customer_location and query the tree for nearest warehouse
# Your code here

Hint

Use tree.query(customer_location) to get distance and index.

4

Print nearest warehouse coordinates

Print the string Nearest warehouse: followed by the coordinates of the nearest warehouse using warehouses[index].

SciPy

from scipy.spatial import KDTree
warehouses = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
tree = KDTree(warehouses)
customer_location = (6, 3)
distance, index = tree.query(customer_location)
# Print nearest warehouse coordinates
# Your code here

Hint

Use print("Nearest warehouse:", warehouses[index]) to show the result.

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