KNN and Naive Bayes — Distance and Probability in Classification

Not every classification problem needs a model that learns parameters. KNN makes predictions by looking at what your neighbours are doing. Naive Bayes computes a probability from scratch using Bayes' theorem. Neither algorithm "trains" in the usual sense. Both can be surprisingly effective in specific situations — and both will fail you badly when used in the wrong context.

Learning Objectives

• Explain how KNN classifies a new point using distance
• Tune k and understand the bias-variance tradeoff it controls
• Describe the curse of dimensionality and why it limits KNN
• Explain the Naive Bayes independence assumption and when it holds well enough
• Choose between GaussianNB and MultinomialNB based on the data type
• Know when to reach for these algorithms and when to walk away

---

K-Nearest Neighbors

The Core Idea

KNN makes no assumptions about the functional form of the boundary between classes. It does not fit a line or a curve. When you ask it to classify a new point, it:

1. Computes the distance from that point to every training example
2. Finds the k closest training examples
3. Takes a majority vote among their labels

That is the entire algorithm. There is no training phase in the traditional sense — the training data itself is the model.

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report

cancer = load_breast_cancer(as_frame=True)
X_train, X_test, y_train, y_test = train_test_split(
    cancer.data, cancer.target,
    test_size=0.2, random_state=42, stratify=cancer.target
)

knn_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("model", KNeighborsClassifier(n_neighbors=7))
])

knn_pipeline.fit(X_train, y_train)
y_pred_knn = knn_pipeline.predict(X_test)

print(classification_report(y_test, y_pred_knn, target_names=["malignant", "benign"]))
# Output:
#               precision    recall  f1-score   support
#    malignant       0.93      0.93      0.93        43
#       benign       0.96      0.96      0.96        71
#     accuracy                           0.95       114

Warning

KNN without feature scaling is broken. If one feature ranges from 0 to 1000 and another from 0 to 1, the first feature will completely dominate the distance calculation. Always scale before using KNN.

---

Choosing K — The Bias-Variance Tradeoff

k is the most important hyperparameter in KNN. It directly controls how smooth or jagged the decision boundary is:

• k=1: The model assigns the label of the single nearest neighbour. The boundary perfectly fits the training data, including noise. Overfit.
• k=N (all training points): Every point is classified as the majority class. Maximum underfit.
• k in between: The right balance depends on your data.

import numpy as np
from sklearn.metrics import accuracy_score

k_values = [1, 3, 5, 7, 11, 15, 21, 31, 51]
train_scores = []
test_scores = []

for k in k_values:
    pipe_k = Pipeline([
        ("scaler", StandardScaler()),
        ("model", KNeighborsClassifier(n_neighbors=k))
    ])
    pipe_k.fit(X_train, y_train)
    train_scores.append(accuracy_score(y_train, pipe_k.predict(X_train)))
    test_scores.append(accuracy_score(y_test, pipe_k.predict(X_test)))

print(f"{'k':>5} {'Train Acc':>12} {'Test Acc':>12}")
print("-" * 32)
for k, tr, te in zip(k_values, train_scores, test_scores):
    print(f"{k:>5} {tr:>12.4f} {te:>12.4f}")

# Output (approximate):
#     k    Train Acc     Test Acc
# --------------------------------
#     1       1.0000       0.9298
#     3       0.9670       0.9561
#     5       0.9626       0.9561
#     7       0.9582       0.9649
#    11       0.9538       0.9649
#    15       0.9626       0.9561
#    21       0.9560       0.9561
#    31       0.9516       0.9561
#    51       0.9473       0.9386

Tip

Use cross-validation rather than a single train/test split to find the optimal k. A good rule of thumb for a starting point is k = sqrt(n_training_samples), but always validate empirically.

---

The Curse of Dimensionality

KNN is fundamentally a distance-based algorithm. As the number of features grows, distance becomes meaningless. In high-dimensional space, all points are approximately equidistant from each other — the nearest neighbours are barely closer than the farthest ones.

import numpy as np

# Demonstrate how distances become more uniform in higher dimensions
np.random.seed(42)
n_samples = 1000
query_point = np.zeros(1)  # origin

for n_dims in [2, 10, 50, 100, 500]:
    data = np.random.randn(n_samples, n_dims)
    query = np.zeros(n_dims)
    distances = np.linalg.norm(data - query, axis=1)
    ratio = distances.max() / distances.min()
    print(f"Dimensions: {n_dims:>5} | Max dist: {distances.max():>8.3f} | "
          f"Min dist: {distances.min():>8.3f} | Ratio: {ratio:>6.2f}")

# Output:
# Dimensions:     2 | Max dist:    3.915 | Min dist:    0.019 | Ratio: 204.30
# Dimensions:    10 | Max dist:    5.695 | Min dist:    1.541 | Ratio:   3.70
# Dimensions:    50 | Max dist:   11.219 | Min dist:    8.137 | Ratio:   1.38
# Dimensions:   100 | Max dist:   14.706 | Min dist:   11.859 | Ratio:   1.24
# Dimensions:   500 | Max dist:   31.012 | Min dist:   27.617 | Ratio:   1.12
# As dimensions grow, the ratio collapses toward 1 — distances lose meaning

Warning

KNN works well with a small number of meaningful features (under ~20). Beyond that, apply dimensionality reduction (PCA) first, or switch to a tree-based model that is not distance-dependent.

---

When to Use KNN

Use KNN when:

• Dataset is small (under ~10,000 rows) — prediction time grows with training set size
• Decision boundary is genuinely non-linear and complex
• You need a quick non-parametric baseline
• Features are few and meaningful (under ~20 features)

Avoid KNN when:

• Dataset is large — prediction is O(n) per query
• High-dimensional features — curse of dimensionality kicks in
• You need fast real-time predictions in production
• Features are not scaled and you cannot preprocess them

---

Naive Bayes

The Core Idea

Naive Bayes is a probabilistic classifier built on Bayes' theorem:

$$P(\text{class} \mid \text{features}) = \frac{P(\text{features} \mid \text{class}) \times P(\text{class})}{P(\text{features})}$$

The "naive" part is the independence assumption: it assumes each feature is independent of every other feature given the class. In reality, features are almost never independent. Despite this obviously wrong assumption, Naive Bayes performs remarkably well in practice — especially for text.

The reason: even if the probabilities are not perfectly calibrated, the ranking between classes is often correct. The model says "this email is 0.0001 times more likely to be spam than ham" — the absolute number is wrong, but the direction is right.

Gaussian Naive Bayes — For Continuous Features

When your features are continuous and roughly normally distributed, use GaussianNB. It models each feature's distribution within each class as a Gaussian.

from sklearn.naive_bayes import GaussianNB
from sklearn.metrics import classification_report, accuracy_score

gnb_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("model", GaussianNB())
])

gnb_pipeline.fit(X_train, y_train)
y_pred_gnb = gnb_pipeline.predict(X_test)

print(f"GaussianNB accuracy: {accuracy_score(y_test, y_pred_gnb):.4f}")
print(classification_report(y_test, y_pred_gnb, target_names=["malignant", "benign"]))
# Output:
# GaussianNB accuracy: 0.9386
#               precision    recall  f1-score   support
#    malignant       0.92      0.93      0.92        43
#       benign       0.95      0.94      0.95        71
#     accuracy                           0.94       114

Multinomial Naive Bayes — For Text and Count Data

When features are counts (word frequencies, event counts), use MultinomialNB. This is the classic model behind spam filters.

from sklearn.naive_bayes import MultinomialNB
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.pipeline import Pipeline
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Minimal spam classifier example
emails = [
    "win cash prize free offer limited time", "buy viagra online cheap",
    "free money guaranteed click here", "meet me for lunch tomorrow",
    "project update deadline moved to friday", "can you review my pull request",
    "you won a lottery claim your prize", "discount offer expires tonight buy now",
    "team meeting at 3pm conference room", "quick question about the deployment"
]
labels = [1, 1, 1, 0, 0, 0, 1, 1, 0, 0]  # 1 = spam, 0 = ham

X_emails_train, X_emails_test, y_emails_train, y_emails_test = train_test_split(
    emails, labels, test_size=0.3, random_state=42
)

spam_pipeline = Pipeline([
    ("vectorizer", CountVectorizer()),
    ("model", MultinomialNB(alpha=1.0))  # alpha is Laplace smoothing
])

spam_pipeline.fit(X_emails_train, y_emails_train)
y_pred_spam = spam_pipeline.predict(X_emails_test)

print(f"Spam filter accuracy: {accuracy_score(y_emails_test, y_pred_spam):.2%}")
print("Predictions:", y_pred_spam.tolist())
# Output:
# Spam filter accuracy: 100.00%
# Predictions: [1, 0, 0]

Info

The alpha parameter in MultinomialNB is Laplace smoothing. If a word appears in test data but never in training data for a given class, its probability would be zero — which would make the entire product zero regardless of other features. Laplace smoothing adds a small count to every word to prevent this. alpha=1.0 is the standard setting.

---

Comparing GaussianNB and MultinomialNB

Property	GaussianNB	MultinomialNB
Feature type	Continuous	Count / frequency
Distribution assumed	Normal (Gaussian)	Multinomial
Common use case	Medical / biological data	Text classification, NLP
Handles negative values	Yes	No (requires non-negative counts)
Needs scaling	No	No

---

When to Use Naive Bayes

Use Naive Bayes when:

• Features are genuinely or approximately independent (text word frequencies approximate this)
• Dataset is small or you need extremely fast training
• You are building a text classifier and want a strong baseline
• You need probability outputs that are fast to compute

Avoid Naive Bayes when:

• Features have strong correlations (e.g., height and weight)
• You need the most accurate probability estimates
• Feature independence is clearly violated and predictions are poor

Success

For spam filtering, sentiment analysis, and document categorisation, a TF-IDF + MultinomialNB pipeline is still a competitive baseline that trains in milliseconds. It beats complex models when data is limited.

---

Head-to-Head: KNN vs Naive Bayes vs Logistic Regression

from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import KNeighborsClassifier
from sklearn.naive_bayes import GaussianNB
from sklearn.model_selection import cross_val_score
import pandas as pd

cancer = load_breast_cancer(as_frame=True)
X_all = cancer.data
y_all = cancer.target

models = {
    "Logistic Regression": Pipeline([
        ("scaler", StandardScaler()),
        ("model", LogisticRegression(max_iter=1000))
    ]),
    "KNN (k=7)": Pipeline([
        ("scaler", StandardScaler()),
        ("model", KNeighborsClassifier(n_neighbors=7))
    ]),
    "Gaussian Naive Bayes": Pipeline([
        ("scaler", StandardScaler()),
        ("model", GaussianNB())
    ])
}

results = []
for name, model in models.items():
    cv_scores = cross_val_score(model, X_all, y_all, cv=5, scoring="roc_auc")
    results.append({
        "Model": name,
        "Mean AUC": cv_scores.mean(),
        "Std AUC": cv_scores.std()
    })

comparison_df = pd.DataFrame(results).sort_values("Mean AUC", ascending=False)
print(comparison_df.to_string(index=False))
# Output (approximate):
#                   Model  Mean AUC  Std AUC
#        Logistic Regression    0.9958   0.0031
#                  KNN (k=7)    0.9937   0.0044
#       Gaussian Naive Bayes    0.9934   0.0060

---

Interview Questions

Q: Why does KNN require feature scaling?

Show answer

KNN classifies based on distance. If one feature has a range of 0–1000 and another has a range of 0–1, the first feature dominates the Euclidean distance calculation. Features on different scales contribute unevenly, so the model effectively ignores small-scale features. Scaling brings all features to a comparable range so distance is computed fairly.

Q: What is the "naive" assumption in Naive Bayes?

Show answer

Naive Bayes assumes that all features are conditionally independent given the class label. This means knowing the value of one feature gives you no additional information about another feature's value, once you know the class. In practice this is almost never true — in an email, the words "win" and "prize" are correlated. Despite this, Naive Bayes often works well because even though the exact probabilities are wrong, the ranking between classes is usually correct.

Q: What is the curse of dimensionality and how does it affect KNN?

Show answer

In high-dimensional space, all points tend to be approximately equidistant from each other. The ratio of the maximum to minimum distance approaches 1 as dimensions grow. For KNN, this means the "nearest neighbours" are barely closer than random points — the concept of locality breaks down. KNN's assumption that nearby points share the same class becomes invalid, so the model's predictions become unreliable.

---

---

What's Next

You've covered KNN's distance-based prediction, the k-selection method with cross-validation, why KNN requires scaling, the naive independence assumption behind Bayes classifiers, GaussianNB for continuous features, MultinomialNB for text/count data with Laplace smoothing, and a head-to-head comparison of all three against logistic regression. Next up: 04-trees-forests-boosting — where you'll learn how decision trees split on feature thresholds, why bagging in Random Forests reduces variance, and how Gradient Boosting sequentially corrects errors to achieve state-of-the-art performance on tabular data.

Optional Deep Dive

Read "Machine Learning: A Probabilistic Perspective" by Kevin Murphy, Chapter 3 (Generative models for discrete data) — it covers the full derivation of Naive Bayes from Bayes' theorem, including the effect of the independence assumption and how the model generalises to different likelihood functions beyond Gaussian and Multinomial.

Previous: Logistic Regression | Next: Trees, Forests, and Boosting