k-Nearest Neighbors and Naive Bayes Explained: Distance, Bayes, Spam Filters

Imagine a classifier that never really learns anything. It just memorizes your data and, when asked a question, looks at the closest examples. Now imagine another that makes a wildly wrong assumption about the world, and still powers spam filters. Today we build both: k-Nearest Neighbors and Naive Bayes.

• Lookup versus counting
• Both surprisingly strong

In the last episode we tamed overfitting with regularization and feature engineering. Those ideas modified linear models. Today we leave lines behind. Our two new models make predictions in very different ways: one from geometry and distance, the other from probability and Bayes' theorem.

• Last time: regularization
• Today: Module 10

Here is the plan. First, distance metrics, because kNN is nothing but distance. Then the algorithm, choosing k, and weighting neighbors. We will watch distance fall apart in high dimensions. After that, Bayes' theorem for classification, a full spam example by hand, smoothing, log probabilities, and finally code.

• Distances and kNN
• Curse of dimensionality
• Naive Bayes and smoothing
• Code from scratch

Each example in our dataset is a point, with one coordinate per feature. Two houses described by size and age are two points on a plane. If we want to say two examples are similar, we need a number for how far apart they are. That number is a distance, and the choice of distance changes everything.

• Similarity as distance
• Features are coordinates

Euclidean distance is the straight line you would draw with a ruler. Take the difference in each coordinate, square it, add them up, and take the square root. For the points one comma one and four comma five, the differences are three and four. Nine plus sixteen is twenty five, and the square root is five.

• Straight-line distance
• Pythagoras in disguise

Manhattan distance is how a taxi travels in a city of square blocks. You cannot cut diagonally, so you add the absolute differences in each coordinate. For the same two points, that is three plus four, which equals seven. It is larger than the Euclidean five, and it is less dominated by one big coordinate gap.

• Walk along the grid
• Sum of absolute differences

Minkowski distance unifies both. Raise each absolute difference to the power p, add them, then take the p-th root. Set p to one and you get Manhattan. Set p to two and you get Euclidean. With p equal to three on our example, twenty seven plus sixty four is ninety one, whose cube root is about four point five.

• One formula, a dial p
• p=1 Manhattan, p=2 Euclidean

Here is the classic mistake. Suppose one feature is salary in dollars and another is age in years. A salary gap of ten thousand swamps an age gap of ten, so age is effectively ignored. Distance based methods demand feature scaling. Standardize each feature, using only training statistics, as we discussed in the previous episode.

• Big units dominate
• Standardize first

The k-Nearest Neighbors algorithm is wonderfully simple. To classify a new point, compute its distance to every training point, pick the k closest, and let them vote. The majority class wins. For regression, average their target values instead. There is no fitting step, which is why it is called a lazy learner.

• No training phase
• Vote among nearest points

Let us do a tiny example. Five training points, with distances to our query already computed. Two blue points sit at distance one point zero and one point four. Three red points sit at two point zero, two point two, and three point zero. Sort them, and we have the neighbor ranking ready for different values of k.

• Query at (2, 3)
• Sort by distance

With k equal to one, the nearest neighbor is blue, so we predict blue. With k equal to three, we have two blue and one red, so blue still wins. But with k equal to five, we have three red against two blue, and the prediction flips to red. The same query, three different answers, depending only on k.

• k=1: blue
• k=3: blue
• k=5: red

If you color every location in the plane by what kNN would predict there, you get a decision boundary. Unlike logistic regression, which draws a line, kNN draws whatever shape the data demands. It can carve out islands around single points. That flexibility is powerful, but it also means it can chase noise.

• Boundary follows the data
• Jagged for small k

Choosing k is the bias-variance trade-off from episode thirteen in action. With k equal to one, the model fits training data perfectly, with high variance and jagged boundaries. With k equal to the whole dataset, it always predicts the majority class, which is pure underfitting. Good models live somewhere in between.

• Small k: low bias, high variance
• Large k: smooth, may underfit

We pick k with cross-validation, never with the test set. Try k equal to one, three, five, and so on, and measure validation error for each. Plot the curve and choose the value near the minimum. Odd values avoid ties in binary problems. A common starting rule of thumb is the square root of the number of samples, but treat it only as a starting point.

• Try odd values of k
• Pick the validation minimum

A neighbor that is very close should matter more than one that is barely inside the circle. Distance weighting gives each neighbor a weight of one divided by its distance. Closer points get larger votes. This also softens the sensitivity to the exact choice of k, because far away neighbors contribute little.

• Closer neighbors count more
• Weight = 1 / distance

Return to our five points with k equal to five. The unweighted vote gave red. Now weigh by inverse distance. Blue gets one over one point zero, which is one, plus one over one point four, about zero point seven one, for a total of one point seven one. Red gets zero point five, zero point four five, and zero point three three, about one point two nine. Blue wins.

• Blue: 1.0 + 0.71 = 1.71
• Red: 0.50+0.45+0.33 = 1.29

kNN has real strengths. It is easy to explain, makes no assumption about data shape, and handles multiple classes naturally. Its costs show up at prediction time, since it must compare against every stored example. It also needs scaling, and, as we will see next, it struggles when there are many features.

• Simple, no training
• Slow at prediction time
• Needs scaling

Now the curse of dimensionality. Put ten points on a line, and they cover it nicely. Spread the same ten points over a square, and they are sparse. Over a cube, they are lonely. Every new feature multiplies the volume of space, while our number of data points stays the same.

• More features, more volume
• Data becomes sparse

Here is a concrete demonstration. Suppose data is uniform in a unit cube, and you want a neighborhood containing ten percent of it. The edge length needed is zero point one raised to the power one over d. For d equal to two, that is about zero point three two. For ten dimensions, zero point seven nine. For one hundred, zero point nine eight.

• Capture 10 percent of data
• Edge length = 0.1^(1/d)

The result is that a local neighborhood is no longer local. It spans almost the whole range of every feature. A related effect is distance concentration: in high dimensions, the nearest and the farthest points end up at similar distances. When everything is about equally far away, nearest neighbor stops carrying useful information.

• Nearest and farthest look alike
• Neighbors lose meaning

What can you do? Remove irrelevant features, since each noisy feature adds distance without adding signal. Reduce dimensions, which we will do properly with principal component analysis in a later episode. Or gather far more data. Also remember that real data often lies near a lower dimensional structure, which is why kNN still works on many practical problems.

• Select useful features
• Reduce dimensions with PCA
• Collect more data

Let us switch to the second model. Instead of asking who is nearby, we ask a probabilistic question. Given the features of this example, which class is most probable? Written precisely, we want the probability of class y given features x. Bayes' theorem from episode eight is exactly the tool for flipping probabilities around.

• From geometry to probability
• Ask: which class is most probable?

Bayes' theorem says the posterior, the probability of the class given the features, equals the likelihood of the features given the class, times the prior probability of the class, divided by the evidence. The evidence is the same for every class, so for picking the winner we can ignore it. We just compare likelihood times prior.

• Posterior = likelihood × prior / evidence
• Evidence is the same for all classes

There is a catch. The likelihood of all features together, given the class, is a joint distribution over many variables. With even thirty binary features, there are over a billion combinations, and most never appear in training data. Estimating this directly is hopeless. We need a simplifying assumption.

• P(x1,...,xd | y) is huge
• Needs exponentially many counts

Naive Bayes assumes that, once we know the class, the features are conditionally independent. Then the joint likelihood factors into a product of one dimensional terms. Each term is easy to estimate from counts. This assumption is almost never exactly true, which is why it is called naive, yet the classifier often performs well anyway.

• Features independent given the class
• Joint = product of simple terms

Why does a wrong assumption still work? Classification only needs the correct class to have the highest score, not exact probabilities. Naive Bayes also has very few parameters, so it has low variance and trains quickly even with small data. The cost is that its probability outputs are often overconfident, which connects back to calibration from episode sixteen.

• Ranking matters, not exact values
• Few parameters, low variance

Time for the spam example. Our training set has ten emails: four spam and six ham, so the priors are zero point four and zero point six. We use a vocabulary of four words. Across all spam emails, free appears six times, win three, meeting once, report zero. That is ten word tokens. In ham, free appears once, win zero, meeting five, and report four, also ten tokens.

• 4 spam, 6 ham emails
• Vocabulary: free, win, meeting, report

A new email contains the words free, win, and meeting. Estimate each word probability as its count divided by the class total. For spam, that is zero point six, zero point three, and zero point one. Multiply with the prior of zero point four to get zero point zero zero seven two. For ham, win has zero count, so the whole product is zero.

• Query: free win meeting
• Ham score becomes zero

That is a serious flaw. One word that never appeared with ham in training erased all other evidence. But not seeing a word in a small sample does not make it impossible. We need a way to give unseen events a small, nonzero probability. That fix is called Laplace smoothing, and it is next.

• Zero count means zero probability
• Unseen is not impossible

Laplace smoothing pretends we saw every vocabulary word alpha extra times in each class. With alpha equal to one, we add one to every count, and add the vocabulary size to the denominator. The probability of a word becomes count plus alpha, divided by total tokens plus alpha times V. Here V is four, so the denominators become fourteen.

• Add alpha to every count
• Add alpha times V to the total

Now recompute. For spam, free is seven fourteenths, which is zero point five. Win is four fourteenths, about zero point two eight six. Meeting is two fourteenths, about zero point one four three. For ham, free is two fourteenths, win is one fourteenth, about zero point zero seven one, and meeting is six fourteenths, about zero point four two nine.

• Spam: free 7/14, win 4/14, meeting 2/14
• Ham: free 2/14, win 1/14, meeting 6/14

Spam score: zero point four times zero point five times zero point two eight six times zero point one four three, about zero point zero zero eight one six. Ham score: zero point six times zero point one four three times zero point zero seven one times zero point four two nine, about zero point zero zero two six two. Spam is larger, so we predict spam.

• Spam: 0.4×0.5×0.286×0.143 ≈ 0.00816
• Ham: 0.6×0.143×0.071×0.429 ≈ 0.00262

To get actual probabilities, normalize. The two scores add up to about zero point zero one zero seven nine. Divide spam's score by that and we get roughly zero point seven five seven. Ham receives about zero point two four three. The email is about seventy six percent likely to be spam, according to the model, with the usual caveat about overconfidence.

• Normalize: divide by the sum
• Spam ≈ 0.757, ham ≈ 0.243

A real email may have hundreds of words, and multiplying hundreds of numbers below one gives an astronomically small result. Computers store numbers with limited precision, so the product underflows to exactly zero. Then every class scores zero, and the classifier cannot decide. This is the numerical stability issue we flagged back in the optimization material.

• Hundreds of tiny factors
• Floating point rounds to zero

The cure is logarithms. The log of a product is the sum of the logs, so we add log probabilities instead of multiplying. Since the log is increasing, the class with the largest score is unchanged. For our example, the natural log of spam's score is about negative four point eight one, and ham's is about negative five point nine four. Spam still wins.

• log turns products into sums
• Compare log scores instead

The naive assumption says how features combine, but we still choose how each single feature is modeled. For real valued measurements, use Gaussian Naive Bayes. For word counts, use multinomial. For binary features, such as whether a word is present, use Bernoulli. Same framework, different one dimensional distributions.

• Gaussian: continuous features
• Multinomial: counts
• Bernoulli: present or absent

Gaussian Naive Bayes fits a mean and standard deviation for each feature in each class. Suppose height has mean one seventy and standard deviation ten for class A, and mean one sixty for class B. A person of one eighty is one deviation from A and two from B. The densities are about zero point zero two four and zero point zero zero five four, so A is favored.

• Fit mean and std per class
• Evaluate the bell curve density

Multinomial Naive Bayes is what we used in the spam example. Each class has a probability for every vocabulary word, estimated from counts with smoothing. A word appearing three times contributes its probability three times, which in log space means multiplying its log probability by three. It is the classic choice for text classification.

• Word counts per class
• Repeated words repeat evidence

Bernoulli Naive Bayes only records whether each word is present or absent. The difference is important: it also uses the evidence from absent words. If the word meeting is missing from an email, that is information, and the model multiplies by the probability of absence. Multinomial ignores words that do not appear.

• Models word absence too
• Binary feature vectors

Naive Bayes trains in a single pass over the data, scales to huge vocabularies, and works with little data. Its weakness is correlated features. If two words always appear together, the model counts their evidence twice. Its probabilities tend toward extremes, so use it for ranking, or calibrate the outputs as we studied before.

• Fast, tiny data friendly
• Correlated features double count
• Probabilities overconfident

Now code. For kNN from scratch with NumPy, compute the difference between the query and the training matrix, square, sum along axis one, and take the square root. Use argsort to get the indices of the k smallest distances. Then take the labels at those indices and return the most common one, using bincount and argmax.

• Distances via NumPy
• argsort and majority vote

For multinomial Naive Bayes, we compute the log prior of each class from class frequencies. Then we sum the word counts per class, add alpha, divide by the total plus alpha times vocabulary size, and take logs. To predict, multiply the count matrix by the log probability matrix, add log priors, and take the argmax across classes.

• Priors and smoothed log likelihoods
• Argmax of log scores

In scikit-learn, kNN is KNeighborsClassifier, with arguments for n_neighbors, weights set to distance, and the metric. Place it in a pipeline after a StandardScaler so scaling happens without leakage. Naive Bayes comes as GaussianNB, MultinomialNB, and BernoulliNB, with an alpha parameter for smoothing. Both follow the same fit and predict pattern.

• KNeighborsClassifier
• MultinomialNB, GaussianNB, BernoulliNB

Always check your scratch code against the library on the same data. Predictions should match, and class probabilities should agree closely. Then tune. Use cross-validation to search over k, weighting, and the metric for kNN, and over alpha for Naive Bayes. Remember that the library kNN also uses tree structures to speed up neighbor search on larger data.

• Match scratch to library
• Cross-validate k and alpha

Let us recap. kNN classifies by letting the nearest training points vote. Euclidean, Manhattan, and Minkowski distances define nearness, and scaling is essential. Small k means high variance, large k means high bias, and cross-validation picks the balance. Distance weighting helps, and high dimensions break the whole idea of closeness.

• Distance defines similarity
• Scale features
• k controls bias and variance

Naive Bayes applies Bayes' theorem, comparing prior times likelihood across classes. The naive conditional independence assumption turns an impossible joint into a product of simple terms. Choose Gaussian, multinomial, or Bernoulli to fit your features. Use Laplace smoothing to avoid zeros, and log probabilities to avoid underflow.

• Posterior ∝ likelihood × prior
• Conditional independence
• Smooth and use logs

Next time, we meet decision trees, which classify by asking a sequence of yes or no questions about features. We will derive entropy, information gain, and Gini impurity, and build a small tree by hand.

• Split features with questions
• Entropy and Gini