Nearest Neighbour Flashcards
What is Voronoi tesselation?
Partitions space into regions where all points are closer to the regions training point than any other point
What is a Voronoi cell?
A single region in a Voronoi tessalation
What is the decision boundary for 1 nearest neighbor?
The edges of all pairs of Voronoi cell that contain training examples from diffrent classes
kNN classification algorithm
- Compute distance D(x, xi) to every training example
- Select k closest instances
- Output the most frequent class
kNN regression algorithm
- Compute distance D(x, xi) to every training example
- Select k closest instances
- Output the mean of closest instances
What is interpolation?
Prediction within range of the training examples
What is extrapolation?
Prediction outside the range of training examples
What happens when you pick small values for k in kNN?
Small changes in training set produce large changes in classification
What happens when you pick very large values for k in kNN?
Everything is classified as the most probable class P(y)
How can we choose the right value for k in kNN?
Train kNN for k = 1, 2, 3, … then pick the model with the smallest validation error on the validation set
Whats the definition of D(x, x’) if D is the euclidian distance function and x has d dimensions?
Whats the definition of D(x, x’) if D is the hamming distance function and x has d dimensions?
Whats the definition of D(x, x’) if D is the minkowski (p-norm) distance function and x has d dimensions?
What is distance function obtained when p=2 for p-norm?
Euclidian
What is distance function obtained when p=1 for p-norm?
Manhatten
How does p-norm behave when p approaches 0?
logical and
How does p-norm behave when p approaches infinitity?
logical or
How can you resolve ties in kNN? (4)
- randomly
- prior (class with greatest probability)
- nearest: use 1-nn
- use odd k (doesnt solve multiclass)
What is a reasonable choice to fill in missing values (kNN)?
Mean of the value across entire data set
How does Parzen Windows differ from kNN?
Instead of picking k nearest neighbors, parzen windows looks at all the training examples that are in a fixed radius from the point
How can kNN be modified to use a kernal?
Replace the distance function with a kernal K(x’, x)
Whats the cons of kNN? (4)
- Need to handle missing data (fill in or special distance function)
- Sensitive to class outliers
- Sensitive to irrelevant attributes (affects distance)
- Computationaly expensive
What is the runtime complexity of kNN? (testing)
O(nd)
n - training examples
d - dimensions
What can we reduce d in kNN?
Dimensionality reduction
What datasets are K-D trees effective (kNN)?
low-dimensional, real-valued data
What datasets are inverted lists effective (kNN)?
high-dimensional, discrete (sparse) data (e.g. text)
What datasets are locality-sensitive hashing effective (kNN)?
high-dimensional, real-valued or discrete
Which methods are inexact at finding neighbors in kNN?
- K-D trees
- inverted lists
- locality-sensitive hashing
K-D trees and locality-sensitive hashing
Which methods are exact at finding neighbors in kNN?
- K-D trees
- inverted lists
- locality-sensitive hashing
inverted lists
How are K-D trees built from training data?
- Pick a random dimension
- Find median
- Split data
- Repeat until the nodes have the desired amount of points
How is a dataset split with locality-sensitive hashing?
Create random hyper-planes h1, …, hk that split the dataset into 2k regions
