Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 39 ยท Classification

Nearest Neighbors and Naive Bayes

Learn two classic classifiers: k-nearest neighbors (lazy learning, distance, scaling, choosing k) and Naive Bayes (Bayes rule, independence, smoothing), built from scratch and with scikit-learn.

Decision trees build an explicit model. Two other classic methods take very different routes. k-nearest neighbors (k-NN) keeps the training data and classifies a new record by looking at the most similar stored records. Naive Bayes uses probability: it estimates how likely each class is given the evidence. Both are easy to implement, which is why we will write them from scratch before using scikit-learn.

k-nearest neighbors

k-NN is called a lazy learner: "training" only stores the data, and all the work happens at prediction time. To classify a record:

  1. Compute the distance from it to every training record.
  2. Take the k closest records.
  3. Predict the majority class among them.

The usual distance for numeric attributes is Euclidean distance, sqrt(sum((a_i - b_i)^2)); Manhattan distance sums absolute differences instead.

Python k-NN from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the answer can change with k. A small k follows local noise (low bias, high variance); a large k smooths the boundary and eventually predicts the global majority. Odd values of k avoid ties in two-class problems, and the best value is found with cross-validation.

Scaling matters

Distance treats every attribute equally, so an attribute measured in thousands (salary) drowns out one measured in single digits (children). Always standardize or normalize numeric features for k-NN.

Python k-NN with and without scaling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Scaling gives a large jump because the wine dataset has one attribute (proline) with values in the hundreds that otherwise dominates all distances.

k-NN has weaknesses: prediction is slow on big data (every query scans the training set unless an index such as a KD-tree is used), it suffers in many dimensions where "nearest" loses meaning (the curse of dimensionality), and it stores everything. A common improvement is distance weighting, where closer neighbors vote with more weight (weights="distance").

Naive Bayes

Naive Bayes applies Bayes' theorem:

P(class | x) = P(x | class) * P(class) / P(x)

For a record with attributes x1, x2, ... it makes the "naive" assumption that attributes are independent given the class, so P(x | class) becomes a product of simple per-attribute probabilities. The class with the largest P(class) * product(P(xi | class)) wins; P(x) is the same for every class and can be ignored when comparing.

Python Naive Bayes by counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The alpha term is Laplace smoothing. Without it, an attribute value never seen with a class gives probability 0 and wipes out the whole product.

Three flavors in scikit-learn

  • GaussianNB: numeric attributes, assumed bell-shaped inside each class.
  • MultinomialNB: counts, such as word frequencies in text.
  • BernoulliNB: yes/no features, such as word present or absent.
Python GaussianNB versus k-NN

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Naive Bayes trains in a single pass, copes with many attributes and little data, and gives class probabilities. Its independence assumption is often false (height and weight are correlated), which makes the probabilities overconfident, but the ranking of classes is frequently still right. See Naive Bayes in scikit-learn for text spam filters and Text Mining Basics for how documents become counts.

Comparing the two

k-NN Naive Bayes
Learning Lazy (stores data) Eager (counts and means)
Prediction speed Slow on large data Very fast
Needs scaling Yes No for Gaussian
Handles irrelevant features Poorly Reasonably
Gives probabilities Rough (vote share) Yes (often overconfident)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is k-NN called a lazy learner?

    k-NN only stores the training records; distances are computed at prediction time.
  2. 2. Why should numeric features be scaled before k-NN?

    Distance sums over attributes, so an attribute with a large range controls the result unless features are scaled.
  3. 3. What does the 'naive' in Naive Bayes refer to?

    The independence assumption lets the joint probability be a product of per-attribute probabilities.
  4. 4. What problem does Laplace smoothing solve?

    Adding a small count to every value keeps unseen combinations from multiplying the score by 0.

Summary

  • k-NN predicts by majority vote of the k closest stored records; scale features and tune k with cross-validation.
  • Naive Bayes multiplies per-attribute probabilities with the class prior, using smoothing to avoid zeros.
  • k-NN is flexible but slow and sensitive to scale and dimensionality; Naive Bayes is fast, simple and often a strong baseline.

Next: Rule-Based and Associative Classification