k-Nearest Neighbors and Naive Bayes

Overview#

This notebook covers two classic, conceptually simple but genuinely useful algorithms that work very differently from everything else in this course. k-Nearest Neighbors (KNN) is "instance-based" — it makes no explicit model at all, just memorizes the training data and compares new points against it directly. Naive Bayes is a probabilistic classifier built on Bayes' theorem with a deliberately simplifying (and usually wrong, but often good-enough) independence assumption. Despite their simplicity, both remain widely used as fast baselines and, in Naive Bayes's case, for text classification specifically.

1. k-Nearest Neighbors: The Core Idea#

KNN classifies a new point by looking at the k closest points in the training data, and predicting the majority class among them (or, for regression, averaging their values).

Python
CopyAsk AI
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

print(f"Test accuracy: {knn.score(X_test_scaled, y_test):.3f}")

There is no real "training" step in the traditional sense — fit() simply stores the training data. All the actual computation happens at prediction time, when the model has to search for and compare against the nearest neighbors of each new point. This is why KNN is called instance-based (or "lazy") learning, in contrast to "eager" learners like linear regression or decision trees, which build an explicit, compact model during training.

Distance metrics#

Python
CopyAsk AI
knn_euclidean = KNeighborsClassifier(n_neighbors=5, metric="euclidean")   # default
knn_manhattan = KNeighborsClassifier(n_neighbors=5, metric="manhattan")
knn_minkowski = KNeighborsClassifier(n_neighbors=5, metric="minkowski", p=3)

Architecture & Data Flow
Copy
Euclidean distance: straight-line ("as the crow flies") distance
                      sqrt(sum((x1_i - x2_i)^2))

Manhattan distance: sum of absolute differences along each dimension
                      (like navigating a city grid)
                      sum(|x1_i - x2_i|)

Minkowski distance: a generalization of both — p=2 is Euclidean, p=1
                      is Manhattan

2. Choosing k: The Central Hyperparameter#

Python
CopyAsk AI
from sklearn.model_selection import cross_val_score
import numpy as np

k_values = range(1, 31, 2)
cv_scores = []

for k in k_values:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)
    cv_scores.append(scores.mean())

best_k = list(k_values)[np.argmax(cv_scores)]
print(f"Best k: {best_k}, CV accuracy: {max(cv_scores):.3f}")

text
Ask AICopy
Small k (e.g. k=1): the prediction depends on just the SINGLE closest
                      point — highly sensitive to noise in that one point
                      → LOW bias, HIGH variance (overfitting risk)

Large k (e.g. k=n):  the prediction averages over many/most points,
                       washing out local structure and approaching the
                       overall class majority everywhere
                       → HIGH bias, LOW variance (underfitting risk)

This is the exact same bias-variance tradeoff seen throughout this course, now expressed through the number of neighbors instead of a regularization parameter or tree depth. Odd values of k are typically preferred for binary classification, to avoid tied votes.

3. Feature Scaling Is Absolutely Essential for KNN#

Python
CopyAsk AI
# WITHOUT scaling: a feature measured in the thousands will completely
# dominate the distance calculation over a feature measured in single
# digits, regardless of which is actually more informative
X_unscaled_example = np.array([[25, 50000], [30, 55000], [45, 51000]])
# "age" (25-45) vs "income" (50000-55000) — income differences would
# swamp age differences entirely in a raw Euclidean distance calculation

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_unscaled_example)

Because KNN's predictions depend directly on distance calculations between raw feature values, unscaled features with different ranges will distort those distances arbitrarily — scaling (typically with StandardScaler) is not optional for KNN the way it might be for tree- based methods, which are scale-invariant.

4. The Curse of Dimensionality#

Python
CopyAsk AI
# As the number of features grows, the notion of "nearest neighbor"
# becomes increasingly meaningless — in high dimensions, distances
# between points tend to become similar to one another, making it hard
# to distinguish "close" from "far"

import numpy as np

def average_distance_ratio(n_dims, n_points=1000):
    points = np.random.rand(n_points, n_dims)
    from scipy.spatial.distance import pdist
    distances = pdist(points)
    return distances.max() / distances.min()   # ratio approaches 1 as dims grow

for dims in [2, 10, 50, 100]:
    ratio = average_distance_ratio(dims)
    print(f"{dims} dimensions: max/min distance ratio = {ratio:.2f}")

text
Ask AICopy
2 dimensions:   max/min distance ratio = 8.34
10 dimensions:  max/min distance ratio = 2.61
50 dimensions:  max/min distance ratio = 1.51
100 dimensions: max/min distance ratio = 1.32

As dimensionality increases, the ratio between the farthest and nearest point shrinks toward 1 — meaning every point starts looking roughly equidistant from every other point. This "curse of dimensionality" is a fundamental limitation of KNN (and other distance-based methods) in high-dimensional feature spaces; dimensionality reduction (covered in its own notebook) is a common remedy.

5. KNN for Regression#

Python
CopyAsk AI
from sklearn.neighbors import KNeighborsRegressor

knn_reg = KNeighborsRegressor(n_neighbors=5, weights="distance")
knn_reg.fit(X_train_scaled, y_train_continuous)

# weights="uniform" (default): every neighbor votes equally
# weights="distance": closer neighbors have MORE influence on the
#                       prediction than farther ones, within the k chosen

weights="distance" often improves results slightly, since it doesn't treat the 1st and 5th nearest neighbors as equally informative — the closer point genuinely tells you more about the local region.

6. Naive Bayes: The Core Idea#

Naive Bayes classifiers apply Bayes' theorem to compute the probability of each class given the observed features, using a deliberately simplifying assumption: that all features are conditionally independent given the class.

Architecture & Data Flow
Copy
Bayes' theorem:
P(class | features) = P(features | class) * P(class) / P(features)

The "naive" independence assumption lets this be computed as:
P(features | class) ≈ P(feature_1 | class) * P(feature_2 | class) * ...

This assumption is almost always technically FALSE in real data (features
are usually somewhat correlated), but the resulting classifier is often
still surprisingly effective in practice, especially for text data.

Gaussian Naive Bayes (for continuous features)#

Python
CopyAsk AI
from sklearn.naive_bayes import GaussianNB

gnb = GaussianNB()
gnb.fit(X_train, y_train)   # note: no scaling needed for Naive Bayes
print(f"Test accuracy: {gnb.score(X_test, y_test):.3f}")

Gaussian Naive Bayes assumes each feature, within each class, follows a normal (Gaussian) distribution — it estimates the mean and variance of each feature per class from the training data, then uses those to compute the probability of a new point belonging to each class.

Multinomial Naive Bayes (for count/frequency data — common in text)#

Python
CopyAsk AI
from sklearn.naive_bayes import MultinomialNB
from sklearn.feature_extraction.text import CountVectorizer

texts = ["free money now", "meeting scheduled for tomorrow", "win free prize now", "project deadline reminder"]
labels = [1, 0, 1, 0]   # 1 = spam, 0 = not spam

vectorizer = CountVectorizer()
X_counts = vectorizer.fit_transform(texts)   # converts text to word count vectors

mnb = MultinomialNB()
mnb.fit(X_counts, labels)

new_text = vectorizer.transform(["free prize meeting"])
print(mnb.predict(new_text))   # predicts based on learned word frequencies per class

Multinomial Naive Bayes is the classic algorithm for spam filtering and basic text classification — it models the probability of each word appearing, conditional on the document's class, which works well despite the independence assumption being obviously violated by real language (word order and co-occurrence clearly matter, but the model ignores this).

Bernoulli Naive Bayes (for binary/boolean features)#

Python
CopyAsk AI
from sklearn.naive_bayes import BernoulliNB

# Useful when features represent PRESENCE/ABSENCE rather than counts —
# e.g. "does this document contain the word 'free'?" (yes/no), rather
# than "how many times does it appear?"
bnb = BernoulliNB()
bnb.fit(X_binary_features, y)

Choosing which Naive Bayes variant#

7. Why Naive Bayes Works Despite the "Naive" Assumption#

text
Ask AICopy
Even when the independence assumption is technically violated, Naive
Bayes can still produce the CORRECT classification decision, because
classification only requires correctly ranking the classes by
probability — not accurately estimating the exact probability values
themselves. Even biased/distorted probability estimates can still
preserve the correct RELATIVE ordering between classes often enough to
make good predictions, especially when class-distinguishing features
dominate the signal.

This is why Naive Bayes remains a genuinely useful, fast baseline for text classification and other high-dimensional, sparse feature problems, despite its core assumption rarely holding exactly.

8. Naive Bayes vs KNN: A Direct Comparison#

9. Practical Tips#

Python
CopyAsk AI
# KNN: use cross-validation to select k, and always scale features
from sklearn.pipeline import Pipeline

knn_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier()),
])

# Naive Bayes: for text, pair with TF-IDF instead of raw counts for
# often-improved results
from sklearn.feature_extraction.text import TfidfVectorizer

tfidf = TfidfVectorizer()
X_tfidf = tfidf.fit_transform(texts)
mnb = MultinomialNB()
mnb.fit(X_tfidf, labels)

TF-IDF (Term Frequency-Inverse Document Frequency) down-weights very common words (like "the", "and") that appear in nearly every document and carry little distinguishing information, often improving on raw word counts for text classification tasks.

Notes#

• KNN has no real training phase — nearly all computational cost happens at prediction time, the opposite of most other algorithms in this course.
• Feature scaling is essential for KNN (distance-based) but unnecessary for Naive Bayes (probability-based, not distance-based).
• The curse of dimensionality is a genuine, fundamental limitation for KNN specifically — it degrades meaningfully as feature count grows, unlike tree ensembles or Naive Bayes.
• Naive Bayes's independence assumption is almost always technically false in real data, yet the classifier often still performs well, because classification only needs correct relative class ranking, not perfectly calibrated probabilities.
• Both algorithms remain popular as fast, simple baselines — establishing what a "good enough" score looks like before investing in more complex models like ensembles or SVMs.

Best Practices Checklist#

• Always scale features before using KNN
• Use cross-validation to select k, rather than an arbitrary default
• Prefer odd values of k for binary classification to avoid tied votes
• Be cautious applying KNN to high-dimensional data — consider dimensionality reduction first if performance seems poor
• Choose the right Naive Bayes variant for the feature type (Gaussian for continuous, Multinomial/Bernoulli for text/counts)
• Pair Multinomial Naive Bayes with TF-IDF rather than raw counts for typically better text classification results
• Use both KNN and Naive Bayes as fast baselines early in a project, before investing in more complex models
• Remember Naive Bayes needs no feature scaling, unlike KNN and SVM