Naive Bayes & K-Nearest Neighbors

This chapter covers two models at opposite ends of the spectrum. Naive Bayes is model-based, tiny, and probabilistic — it learns a handful of numbers from the data. K-Nearest Neighbors is instance-based (Chapter 18): it stores the data and defers all "learning" to prediction time. Both are simple, fast, and surprisingly strong on the right problems.

Understanding Bayes' Theorem

You met Bayes' theorem in Chapter 15; here it becomes a classifier. Bayes' rule updates a prior belief with evidence:

P(A | B) = P(B | A) * P(A) / P(B)

• P(A) — the prior: how likely class A is before seeing any features.
• P(B | A) — the likelihood: how likely the evidence B is, assuming class A.
• P(A | B) — the posterior: the updated belief after seeing the evidence.
• P(B) — a normalizing constant that makes probabilities sum to one.

To classify a new point with features x1, x2, ..., xd, we compute the posterior for every class and pick the most probable one. The denominator is the same for all classes, so it can be ignored during the comparison.

Variants of Naive Bayes

The word naive is the catch: the model assumes all features are conditionally independent given the class. That is almost never literally true (word "free" and "prize" co-occur in spam), yet the simplification makes the math tractable and the model still performs well. The joint likelihood factors into a product:

P(x1, x2, ..., xd | C) = P(x1|C) * P(x2|C) * ... * P(xd|C)

The three variants differ in how each individual P(xj | C) is modeled:

Gaussian Naive Bayes

For continuous features, each class is described by a normal distribution per feature, captured by a mean and a variance. P(xj | C) is the height of that Gaussian at xj. This is the natural choice for numeric data like heights, measurements, or pixel intensities.

Multinomial Naive Bayes

For counts — word frequencies in a document, say — each class holds a distribution over feature counts. It is the classic engine of text classification: spam detection and sentiment analysis are built on it, often boosted by TF-IDF features.

Bernoulli Naive Bayes

For binary features — a word is present or absent — each class holds a single probability per feature: the chance that feature j is turned on. It models presence/absence rather than frequency.

Naive Bayes Practical Implementation

from sklearn.naive_bayes import GaussianNB
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris

data = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.2, random_state=42)

gnb = GaussianNB()
gnb.fit(X_train, y_train)
print(gnb.score(X_test, y_test))

Training is nearly instantaneous: the model merely computes priors and per-class means and variances. For text, swap in MultinomialNB with a CountVectorizer; for binary feature vectors, use BernoulliNB. Despite its crude assumption, Naive Bayes often wins when features are weak but numerous — exactly the situation in spam filtering.

KNN Classification and Regression In-Depth Intuition

K-Nearest Neighbors embodies the "birds of a feather" idea: a new point is classified by asking its k nearest stored neighbors and following their lead.

KNN Classification

For a new point, compute its distance (usually Euclidean) to every stored training point, take the k closest ones, and predict the majority class among them. The vote can be weighted by distance so that nearer neighbors count more.

KNN Regression

For regression, the same k neighbors vote numerically: the prediction is the average of their target values, again optionally weighted by distance. If your three nearest houses sold for 1.2M, 1.4M, and 1.1M, you predict roughly 1.23M.

The choice of k is the heart of the model:

• k = 1: extreme sensitivity — every prediction copies its single closest point; boundaries are jagged and noise is memorized (overfitting).
• Large k: smoother boundaries, more resistance to noise, but the model becomes bland and may drown real structure under faraway points (underfitting).
• A good k is found by cross-validation, and an odd k avoids tie votes in two-class problems.

KNN has no training phase at all in the classical sense — prediction cost grows linearly with the number of stored points, which is why the data structures below matter.

Optimization of KNN: KD-Trees and Ball Trees

Naively finding k nearest neighbors requires comparing a query against every training point — too slow for large datasets. Two index structures speed up the search:

KD-Trees

A k-dimensional tree splits the feature space recursively, alternating the axis at each level (split on feature 1, then feature 2, then feature 1 again...). Searching descends the tree, and — crucially — whole branches whose bounding region is farther than the current best candidate can be pruned without inspecting the points inside them. KD-trees work beautifully in low dimensions (a handful of features) but degrade as dimensionality climbs, because the boxes spread out and pruning stops paying off.

Ball Trees

A ball tree instead partitions space into nested hyperspheres, each with a center and radius. The same pruning logic applies — if a query point is closer to the current k-th best neighbor than a candidate ball's edge, the whole ball is skipped. Ball trees tolerate higher dimensions better than KD-trees because the spherical geometry remains useful longer.

Scikit-learn exposes both through algorithm="kd_tree" and algorithm="ball_tree"; the default auto picks a reasonable choice for your data. For very high dimensions, even these structures struggle and exact nearest neighbor search is better replaced by approximate methods.

KNN Classifier and Regressor Implementation

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5, weights="distance")
knn.fit(X_train_s, y_train)
print(knn.score(X_test_s, y_test))

from sklearn.neighbors import KNeighborsRegressor

knn_r = KNeighborsRegressor(n_neighbors=7, weights="uniform")
knn_r.fit(X_train_s, y_train)
print(knn_r.predict(X_test_s))

Two practical points stand out:

• Distance-based models are only as meaningful as the scale of their axes. A feature in rupees will silently dominate one measured in years, so standardization is mandatory.
• Tune k with cross-validation — one neighbor is usually too jumpy, and half the dataset is too smooth. The elbow where error flattens is your k.