CS-GY 6923: Machine Learning
1.0.0
1.0.0
  • Introduction
  • What is Machine Learning?
  • Types of Machine Learning
    • Supervised Learning
      • Notations
      • Probabilistic Modeling
        • Naive Bayes Classifier
      • Linear Regression
      • Nearest Neighbor
      • Evaluating a Classifier
      • Parametric Estimation
        • Bayesian Approach to Parameter Estimation
        • Parametric Estimation for Simple Linear Regression
        • Parametric Estimation for Multivariate Linear Regression
        • Parametric Estimation for Simple Polynomial Regression
        • Parametric Estimation for Multivariate Polynomial Regression
      • Bias and Variance of an Estimator
      • Bias and Variance of a Regression Algorithm
        • Model Selection
      • Logistic Regression
      • Decision Trees
        • Using Decision Trees for Regression
        • Bias and Variance
      • Dimensionality Reduction
      • Neural Networks
        • Training a Neuron
        • MLP
          • Regression with Multiple Outputs
          • Advice/Tricks and Issues to Train a Neural Network
        • Deep Learning
      • Support Vector Machines
      • Ensemble Learning
    • Unsupervised Learning
      • K-Means Clustering
      • Probabilistic Clustering
    • Reinforcement Learning
Powered by GitBook
On this page

Was this helpful?

  1. Types of Machine Learning
  2. Supervised Learning

Nearest Neighbor

PreviousLinear RegressionNextEvaluating a Classifier

Last updated 5 years ago

Was this helpful?

Idea: Similar examples tend to have the same label.

The barebones algorithm for Nearest Neighbor is as follows:

Given a new example to label, find the "most similar" example (i.e. the nearest neighbor) in the dataset.
Predict using the label of the nearest neighbor.

How do we compute the distance between examples? What is the distance measure?

For real-valued attributes, we can use the Euclidean Distance.

The feature space gets divided into polygonal cells based on the distances to existing examples. The result resembles a Voronoi Diagram:

Issues with NN

  • One issue with the NN algorithm is that we have to compute the distance to each and every example in the dataset. This can be time consuming.

  • NN is a lazy learner: there is no training. The only processing that happens is when a test example is to be labeled.

  • The scale of attributes: Attributes may have different scales. This leads to attributes with smaller scales being ignored when we compute the Euclidean Distance. Therefore, it is important to scale the attributes i.e. to bring them to the same scale.

  • The Curse of Dimensionality: As the number of attributes increases, the amount of training data needed for effective classification (i.e. fast classification) increases exponentially. This impacts the NN algorithm because the examples move further and further apart as the number of dimensions (attributes) increases. Therefore, we need a lot more examples to be able to use NN effectively.

  • High Variance: Predictions are very sensitive to which examples are in the training set. This also makes it very sensitive to outliers. To overcome this, we use the k-NN algorithm. This uses the majority label of the k closest examples to predict the label of a test example.

    Note: The kNN algorithm can also be used for Regression! The average (or maybe the weighted average) of the outcomes of the k closest examples can be used to predict the outcome of a test example.