Nearest Neighbour

Question 1

What is Voronoi tesselation?

Answer 1

Partitions space into regions where all points are closer to the regions training point than any other point

Question 2

What is a Voronoi cell?

Answer 2

A single region in a Voronoi tessalation

Question 3

What is the decision boundary for 1 nearest neighbor?

Answer 3

The edges of all pairs of Voronoi cell that contain training examples from diffrent classes

Question 4

kNN classification algorithm

Answer 4

1. Compute distance D(x, x_i) to every training example
2. Select k closest instances
3. Output the most frequent class

Question 5

kNN regression algorithm

Answer 5

1. Compute distance D(x, xi) to every training example
2. Select k closest instances
3. Output the mean of closest instances

Question 6

What is interpolation?

Answer 6

Prediction within range of the training examples

Question 7

What is extrapolation?

Answer 7

Prediction outside the range of training examples

Question 8

What happens when you pick small values for k in kNN?

Answer 8

Small changes in training set produce large changes in classification

Question 9

What happens when you pick very large values for k in kNN?

Answer 9

Everything is classified as the most probable class P(y)

Question 10

How can we choose the right value for k in kNN?

Answer 10

Train kNN for k = 1, 2, 3, … then pick the model with the smallest validation error on the validation set

Question 11

Whats the definition of D(x, x’) if D is the euclidian distance function and x has d dimensions?

Answer 11

Question 12

Whats the definition of D(x, x’) if D is the hamming distance function and x has d dimensions?

Answer 12

Question 13

Whats the definition of D(x, x’) if D is the minkowski (p-norm) distance function and x has d dimensions?

Answer 13

Question 14

What is distance function obtained when p=2 for p-norm?

Answer 14

Euclidian

Question 15

What is distance function obtained when p=1 for p-norm?

Answer 15

Manhatten

Question 16

How does p-norm behave when p approaches 0?

Answer 16

logical and

Question 17

How does p-norm behave when p approaches infinitity?

Answer 17

logical or

Question 18

How can you resolve ties in kNN? (4)

Answer 18

• randomly
• prior (class with greatest probability)
• nearest: use 1-nn
• use odd k (doesnt solve multiclass)

Question 19

What is a reasonable choice to fill in missing values (kNN)?

Answer 19

Mean of the value across entire data set

Question 20

How does Parzen Windows differ from kNN?

Answer 20

Instead of picking k nearest neighbors, parzen windows looks at all the training examples that are in a fixed radius from the point

Question 21

How can kNN be modified to use a kernal?

Answer 21

Replace the distance function with a kernal K(x’, x)

Question 22

Whats the cons of kNN? (4)

Answer 22

• Need to handle missing data (fill in or special distance function)
• Sensitive to class outliers
• Sensitive to irrelevant attributes (affects distance)
• Computationaly expensive

Question 23

What is the runtime complexity of kNN? (testing)

Answer 23

O(nd)

n - training examples

d - dimensions

Question 24

What can we reduce d in kNN?

Answer 24

Dimensionality reduction

Question 25

What datasets are K-D trees effective (kNN)?

Answer 25

low-dimensional, real-valued data

Question 26

What datasets are inverted lists effective (kNN)?

Answer 26

high-dimensional, discrete (sparse) data (e.g. text)

Question 27

What datasets are locality-sensitive hashing effective (kNN)?

Answer 27

high-dimensional, real-valued or discrete

Question 28

Which methods are inexact at finding neighbors in kNN?

• K-D trees
• inverted lists
• locality-sensitive hashing

Answer 28

K-D trees and locality-sensitive hashing

Question 29

Which methods are exact at finding neighbors in kNN?

• K-D trees
• inverted lists
• locality-sensitive hashing

Answer 29

inverted lists

Question 30

How are K-D trees built from training data?

Answer 30

1. Pick a random dimension
2. Find median
3. Split data
4. Repeat until the nodes have the desired amount of points

Question 31

How is a dataset split with locality-sensitive hashing?

Answer 31

Create random hyper-planes h₁, …, h_k that split the dataset into 2^k regions