Classic Classifiers: kNN, Naive Bayes and SVMs

Before deep learning and gradient boosting, three classifiers carried much of applied machine learning: k-nearest neighbours, naive Bayes and support vector machines. They are still worth mastering. k-nearest neighbours is the conceptual ancestor of today's vector search and retrieval-augmented generation; naive Bayes is a fast, strong baseline for text that trains in milliseconds; and support vector machines introduced the margin, hinge loss and kernel ideas that run throughout modern ML. Each embodies a different philosophy, and knowing when each fits is part of a practitioner's toolkit.

Three philosophies in one picture

Imagine sorting fruit at a market stall.

• k-nearest neighbours keeps every fruit it has ever seen. Given a new one, it finds the $k$ most similar fruits on the table and goes with the majority. No model, just memory and a notion of "similar".
• Naive Bayes keeps a tally per fruit type: how often oranges are orange, round, heavy. For a new fruit it asks which type would most probably produce these characteristics, pretending each characteristic is independent of the others given the type.
• A support vector machine draws the widest possible street between apples and oranges on the table, and only the fruits standing at the curb (the support vectors) determine where the street runs.

k-nearest neighbours (kNN)

The algorithm

Store the training set $\{(x_i, y_i)\}_{i=1}^{n}$. To classify a query $x$:

1. Compute the distance $d(x, x_i)$ to every training point.
2. Take the set $N_k(x)$ of the $k$ closest.
3. Predict the majority label among them (classification), or their average target (regression). Class probabilities are the label fractions within $N_k(x)$.

A variant weights each neighbour's vote by $1/d$, so closer points count more. There is no training step beyond storing data (kNN is a lazy or instance-based learner), so all the cost moves to prediction: a naive query is $O(nd)$. Tree indexes (KD-trees, ball trees) speed this up in low dimensions, and approximate nearest-neighbour indexes (such as HNSW graphs) make it practical for millions of high-dimensional vectors; this is exactly the machinery inside vector databases (see vector-databases-and-indexing).

Cover and Hart (1967) proved a classic guarantee: as the training set grows, the error rate of the 1-nearest-neighbour rule is at most twice the Bayes error rate, the lowest error achievable by any classifier on that problem. That is a striking result for such a simple method, but it is asymptotic; with finite data in many dimensions kNN can do badly, as we will see.

Distance metrics

For vectors $x, z \in \mathbb{R}^d$, the Minkowski distance of order $p$ is

$p = 2$ is Euclidean distance (straight line); $p = 1$ is Manhattan distance (sum of absolute differences), somewhat more robust to a single large coordinate difference. For text and embeddings, cosine distance $1 - \frac{x^\top z}{\lVert x\rVert \lVert z\rVert}$ compares direction and ignores length. For categorical data, Hamming distance counts mismatches. The metric encodes your notion of similarity, so choose it deliberately.

Worked example

Training points: $A(1,1)$ red, $B(2,3)$ red, $C(4,4)$ blue, $D(5,3)$ blue, $E(3,6)$ blue. Query $q = (3, 3)$.

With $k = 1$ the prediction is red (B). With $k = 3$ (B, C, D) it is blue, with estimated probability $2/3$. The choice of $k$ is a bias-variance knob: small $k$ gives jagged, high-variance boundaries that react to individual noisy points; large $k$ gives smooth, high-bias boundaries. Choose it by cross-validation, and prefer odd $k$ in binary problems to avoid ties.

Feature scaling is mandatory

Distances add up differences across features, so a feature measured in large units swamps the others. Query: age 30, income $50,000. Neighbour P1: age 31, income $52,000. Neighbour P2: age 60, income $50,500. Unscaled Euclidean distances: P1 $= \sqrt{1^2 + 2000^2} \approx 2000$; P2 $= \sqrt{30^2 + 500^2} \approx 501$. P2 is "nearer" despite a 30-year age gap, because income dominates. After standardising (say age standard deviation 10 years, income $20,000): P1 $= \sqrt{0.1^2 + 0.1^2} = 0.14$; P2 $= \sqrt{3^2 + 0.025^2} \approx 3.0$. Now P1 is correctly the near neighbour. Standardise (or otherwise scale) features inside a pipeline before any distance-based method.

The curse of dimensionality

In high dimensions, intuitions about "near" break down, for two reasons.

First, neighbourhoods stop being local. Suppose data are spread uniformly in the unit hypercube $[0,1]^d$ and you want a neighbourhood that captures 10% of the data. A sub-cube with that volume needs edge length $0.1^{1/d}$: 0.1 when $d = 1$, 0.32 when $d = 2$, 0.79 when $d = 10$ and 0.98 when $d = 100$. To capture even 10% of the points you must span almost the whole range of every feature, so the "neighbours" are not similar at all.

Second, distances concentrate: the nearest and farthest points become almost equally far away. This short simulation measures the ratio of the nearest to the farthest distance from a random query to 1,000 random points:

import numpy as np
rng = np.random.default_rng(0)
for d in [2, 10, 100, 1000]:
    X = rng.uniform(size=(1000, d))
    q = rng.uniform(size=d)
    dist = np.linalg.norm(X - q, axis=1)
    print(f"d={d:5d}  nearest/farthest distance ratio = {dist.min() / dist.max():.3f}")

The ratio climbs from about 0.01 in 2 dimensions to about 0.22 at 10, 0.72 at 100 and 0.90 at 1,000. When everything is roughly equally far, "nearest" carries little information. kNN works in practice in high dimensions only when the data actually lie near a lower-dimensional structure (as images and learned embeddings do), or after dimensionality reduction or a learned embedding has done the hard work.

Naive Bayes

The model

Bayes' theorem gives the posterior probability of class $c$ given features $x = (x_1, \dots, x_d)$:

Estimating $P(x \mid c)$ for all combinations of $d$ features is hopeless. The naive assumption is that features are conditionally independent given the class:

We work with sums of logs because a product of hundreds of small probabilities underflows to zero in floating point. Each factor is estimated by counting, so training is a single pass over the data.

The variants differ in how they model $P(x_j \mid c)$:

• Multinomial NB: features are counts (word counts in a document). $P(\text{word } w \mid c)$ is the share of all word tokens in class $c$ that are $w$.
• Bernoulli NB: features are binary (word present or absent), and absence is also evidence.
• Gaussian NB: continuous features, each modelled as a normal distribution with a per-class mean and variance.

Laplace smoothing

If a word never appeared in spam during training, its estimated probability is 0, and a single occurrence would veto the spam class no matter what else the email says. Additive (Laplace) smoothing adds a pseudo-count $\alpha$ (usually 1) to every word:

where $|V|$ is the vocabulary size.

Worked example: a tiny spam filter

Vocabulary $V = \{\text{free}, \text{win}, \text{meeting}, \text{report}\}$, so $|V| = 4$. Training data: 4 spam and 6 ham (legitimate) emails, so the priors are $P(\text{spam}) = 0.4$ and $P(\text{ham}) = 0.6$. Word counts:

New email: "free win meeting".

• Spam score: $0.4 \times 0.450 \times 0.300 \times 0.100 = 0.00540$.
• Ham score: $0.6 \times 0.107 \times 0.071 \times 0.357 = 0.00164$.
• Normalising: $P(\text{spam} \mid \text{email}) = 0.00540 / (0.00540 + 0.00164) = 0.767$.

In log space, the same computation compares $\log 0.4 + \log 0.45 + \log 0.3 + \log 0.1 = -5.22$ with $-6.41$ for ham; spam wins. "free" and "win" each favour spam by a factor of about 4, and "meeting" favours ham by about 3.6, not enough to overturn them. Note what the model ignores: word order, and the fact that "free" and "win" tend to co-occur. Because co-occurring words are counted as independent evidence, naive Bayes tends to produce overconfident probabilities (pushed toward 0 or 1), even when its ranking of emails is good. Use it for decisions or ranking, and calibrate before trusting its probabilities.

The same idea in scikit-learn, with real tokenisation:

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
from sklearn.pipeline import make_pipeline

emails = ["win free money now", "free prize win win", "claim your free reward",
          "meeting moved to monday", "quarterly report attached", "lunch meeting tomorrow?",
          "please review the report", "free pizza at the team meeting"]
labels = [1, 1, 1, 0, 0, 0, 0, 0]          # 1 = spam

nb = make_pipeline(CountVectorizer(), MultinomialNB(alpha=1.0))  # alpha = Laplace smoothing
nb.fit(emails, labels)
for msg in ["free money", "report for the meeting", "win a free meeting"]:
    p = nb.predict_proba([msg])[0, 1]
    print(f"{msg!r:28s} P(spam) = {p:.2f}")

This prints roughly 0.78, 0.03 and 0.69. Words never seen in training ("for", "a") are simply ignored by CountVectorizer. Eight emails is of course far too few for a real filter; production spam filtering today combines many signals and models, but naive Bayes on word counts remains a fast, hard-to-beat baseline for text classification.

Support vector machines (SVMs)

Maximum margin

Take binary labels $y_i \in \{-1, +1\}$ and a linear classifier $f(x) = w^\top x + b$ that predicts $\operatorname{sign} f(x)$. If the classes are linearly separable, infinitely many hyperplanes separate them. The SVM picks the one with the largest margin, the distance from the hyperplane to the closest training points. Scaling $w$ and $b$ so that the closest points satisfy $y_i f(x_i) = 1$, that distance is $1/\lVert w\rVert$ and the full width of the "street" between the two margin hyperplanes $f(x) = \pm 1$ is $2/\lVert w\rVert$, and the hard-margin SVM solves

A wide margin means small changes in the data are less likely to flip predictions, which is the geometric intuition for good generalisation. The solution depends only on the points lying on the margin, the support vectors; you could delete every other training point and get the same classifier.

Soft margin and hinge loss

Real data overlap, so we allow violations. The soft-margin SVM (Cortes and Vapnik, 1995) minimises

The second term is the hinge loss: zero for points correctly classified with functional margin $y_i f(x_i) \ge 1$, growing linearly as a point enters the margin or crosses to the wrong side. Compare logistic regression, whose log-loss never reaches exactly zero; the hinge's flat zero region is why only some points (those on or inside the margin) end up as support vectors. $C > 0$ trades margin width against violations: large $C$ punishes violations heavily (narrow margin, fits the training data closely, risk of overfitting); small $C$ tolerates them (wide margin, smoother boundary, more support vectors). $C$ plays the role of an inverse regularisation strength, like C in logistic regression.

Worked example. Take $w = (2, 1)$, $b = -4$, so the margin width is $2/\lVert w\rVert = 2/\sqrt5 = 0.894$.

Kernels

A linear boundary is often too simple. We could map inputs to a richer feature space $\phi(x)$ and find a linear separator there, but explicit maps can be huge. The key fact is that the SVM's dual optimisation problem and its decision function use the data only through dot products:

where the $\alpha_i \ge 0$ are learned dual coefficients, non-zero only for support vectors. A kernel $K$ computes the dot product in feature space without building $\phi$ at all: the kernel trick. Common kernels:

• Linear: $K(x, z) = x^\top z$.
• Polynomial: $K(x, z) = (\gamma\, x^\top z + r)^q$, for degree $q$.
• RBF (Gaussian): $K(x, z) = \exp(-\gamma \lVert x - z \rVert^2)$, corresponding to an infinite-dimensional feature space.

For instance, in two dimensions $(x^\top z)^2 = \phi(x)^\top \phi(z)$ with $\phi(x) = (x_1^2, \sqrt2\, x_1 x_2, x_2^2)$: the kernel evaluates a three-dimensional dot product using a two-dimensional one.

For the RBF kernel, $\gamma$ sets how far each support vector's influence reaches. Large $\gamma$ means each point influences only a tiny neighbourhood: wiggly boundaries that can wrap around individual points (overfitting). Small $\gamma$ means broad influence and nearly linear boundaries (underfitting). $C$ and $\gamma$ interact, so tune them jointly on a logarithmic grid (for example $10^{-3}$ to $10^{3}$) with cross-validation. RBF SVMs are distance-based, so feature scaling is essential.

Costs and practicalities

Kernel SVM training (scikit-learn's SVC, built on LIBSVM) scales at least quadratically with the number of samples, which becomes impractical beyond a few tens of thousands of rows. For large or very high-dimensional sparse data (text), use a linear SVM (LinearSVC or SGDClassifier with hinge loss), which scales roughly linearly. SVMs output scores, not probabilities; SVC(probability=True) fits an extra calibration step using internal cross-validation, which is slow and can disagree slightly with predict. Multiclass problems are handled by combining binary SVMs (scikit-learn's SVC uses one-vs-one internally).

Putting them side by side

The following compares the three on scikit-learn's wine dataset (178 wines, 13 chemical measurements on very different scales, 3 cultivars), with and without scaling:

from sklearn.datasets import load_wine
from sklearn.model_selection import cross_val_score, StratifiedKFold
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.naive_bayes import GaussianNB
from sklearn.svm import SVC
from sklearn.linear_model import LogisticRegression

X, y = load_wine(return_X_y=True)
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)
models = {
    "kNN, raw features":    KNeighborsClassifier(n_neighbors=5),
    "kNN, scaled":          make_pipeline(StandardScaler(), KNeighborsClassifier(5)),
    "Gaussian NB":          GaussianNB(),
    "SVM RBF, raw":         SVC(kernel="rbf", C=1.0),
    "SVM RBF, scaled":      make_pipeline(StandardScaler(), SVC(kernel="rbf", C=1.0)),
    "Logistic reg, scaled": make_pipeline(StandardScaler(), LogisticRegression(max_iter=1000)),
}
for name, m in models.items():
    s = cross_val_score(m, X, y, cv=cv)
    print(f"{name:21s} {s.mean():.3f} +/- {s.std():.3f}")

Typical results: kNN on raw features about 0.66, and 0.96 after scaling; the RBF SVM about 0.66 raw and 0.98 scaled; Gaussian naive Bayes about 0.97 (per-feature Gaussians are unaffected by scale); scaled logistic regression about 0.98. The lesson is less about which model wins on this small, easy dataset than about the 30-point swing that scaling causes for distance-based methods.

Common pitfalls

• Forgetting to scale features for kNN and SVMs, and fitting the scaler outside the cross-validation pipeline.
• Using kNN on raw high-dimensional features and blaming the algorithm when distances become meaningless.
• Choosing $k$, $C$ or $\gamma$ by test-set performance instead of cross-validation.
• Zero probabilities in naive Bayes from skipping smoothing, or multiplying probabilities instead of summing logs.
• Trusting naive Bayes probabilities as calibrated risks.
• Running kernel SVMs on hundreds of thousands of rows; use linear SVMs, kernel approximations or gradient boosting instead.
• Ignoring class imbalance: all three can be dominated by the majority class; use class weights (class_weight="balanced" for SVMs) or appropriate priors and metrics.

In practice

• For text classification, start with TF-IDF features and a linear model (logistic regression or a linear SVM) plus multinomial naive Bayes as a baseline; then compare with fine-tuned language-model embeddings.
• For small tabular datasets with complex boundaries, a scaled RBF SVM tuned over $C$ and $\gamma$ can still compete; on larger tabular data, gradient-boosted trees usually win.
• kNN's modern life is retrieval: with learned embeddings and approximate nearest-neighbour indexes, nearest-neighbour search powers semantic search, recommendation and RAG systems (embeddings-and-rag).
• Always compare against a logistic regression baseline under the same pipeline and cross-validation scheme, and report variability across folds.
• When a stakeholder needs probabilities, calibrate the chosen model and check calibration on held-out data (model-evaluation-and-metrics).