PART 2 • CORE MACHINE LEARNING • LEVEL 08

k-Nearest Neighbours & Naive Bayes

Learn two beautifully different ways to classify: ask the nearest examples, or combine probabilistic evidence. Build intuition, derive the mathematics and compare when each algorithm succeeds.

⏱️ 190–220 min🎯 Beginner → Interview Ready🧪 2 Interactive Labs💼 Placement Algorithms
Start Learning →Open Neighbourhood Lab
?
INSTANCE-BASEDk-NN: distance → votePROBABILISTICNB: prior × evidence
LEARNING OUTCOMES

By the End of This Level, You Can

01Calculate Euclidean, Manhattan and Minkowski distances.
02Explain scaling, choosing k and weighted neighbour voting.
03Diagnose dimensionality, runtime and memory limitations.
04Derive Naive Bayes scores from priors and likelihoods.
05Select Gaussian, Multinomial or Bernoulli Naive Bayes.
06Compare both algorithms using validation and deployment needs.
QUICK REVISION

Six Ideas to Bring Forward

Distance methods need geometry; probability methods need reliable evidence.

FEATURE VECTORx = [x₁,…,xₙ]

One sample represented numerically.

CLASS LABELy ∈ {C₁,…,Cₖ}

The outcome a classifier predicts.

DISTANCEd(x,q)

How near two feature vectors are.

PRIORP(C)

Class belief before new evidence.

LIKELIHOODP(x|C)

How expected evidence is in a class.

VALIDATIONTune safely

Choose settings without touching test data.

CONCEPT 01

k-NN Learns by Remembering Examples

k-Nearest Neighbours delays most work until prediction time.

TRAINStore labelled examples

No coefficient-fitting loop is required.

QUERYMeasure every relevant distance

Compare the new sample with stored training samples.

NEIGHBOURSSelect the closest k

Keep the most local evidence.

PREDICTVote or average

Classification votes; regression averages targets.

DETAILED EXPLANATION

k-NN is a non-parametric, instance-based algorithm. It does not compress the training set into a fixed equation. At prediction time it measures similarity between a query and stored examples, selects the nearest k, then combines their labels. This gives flexible local boundaries but makes inference dependent on dataset size.

WORKED INTUITION

If the three nearest students to a query contain two placed students and one not-placed student, unweighted k-NN predicts placed.

AI / PLACEMENT CONNECTION

Interviewers expect the distinction between lazy learning, non-parametric modelling and model-free memorization.

COMMON MISCONCEPTION

“No training” does not mean no preparation: scaling, imputation, feature selection and indexing are still fitted or constructed.

CONCEPT 02

Distance Defines What “Similar” Means

The selected metric encodes the geometry of the problem.

EUCLIDEAN • L2√Σ(xᵢ−qᵢ)²

Straight-line distance; sensitive to large coordinate differences.

MANHATTAN • L1Σ|xᵢ−qᵢ|

Axis-aligned distance; often more robust to isolated large differences.

MINKOWSKI • Lp(Σ|xᵢ−qᵢ|ᵖ)¹⁄ᵖ

A family containing Manhattan at p=1 and Euclidean at p=2.

COSINE DISTANCE1 − (x·q)/(‖x‖‖q‖)

Compares direction and is useful for magnitude-independent representations.

DETAILED EXPLANATION

A distance metric converts feature differences into one dissimilarity score. Euclidean distance emphasizes squared differences, Manhattan adds absolute differences and cosine compares direction. The correct choice depends on whether magnitude, direction, sparse coordinates or domain-specific costs express genuine similarity.

WORKED INTUITION

Between (1,2) and (4,6), Euclidean distance is 5 while Manhattan distance is 7.

AI / PLACEMENT CONNECTION

Be prepared to calculate a complete distance table and identify nearest neighbours by hand.

COMMON MISCONCEPTION

A familiar formula is not automatically the best metric; it must match the representation and problem.

CONCEPT 03

Feature Scaling Is Essential for k-NN

Distance is dominated by features with larger numeric ranges.

WITHOUT SCALING

Age: 18–60

Salary: 20,000–2,000,000

Salary controls the distance
→
AFTER STANDARDIZATIONz = (x−μ)/σ

Both features use comparable standardized units.

Each feature can contribute meaningfully
DETAILED EXPLANATION

Because k-NN compares coordinate differences, a large-unit feature can overwhelm every smaller-unit feature even when it is less informative. Standardization or another training-fitted transformation puts numeric features on comparable scales. The scaler must be fitted only on training data and reused for validation, test and production samples.

WORKED INTUITION

A ₹100,000 salary gap numerically hides a five-year age gap unless the features are rescaled.

AI / PLACEMENT CONNECTION

This is one of the most frequent “Which algorithms need scaling?” interview questions.

COMMON MISCONCEPTION

Scaling the complete dataset before splitting leaks evaluation distribution information.

CONCEPT 04

Choosing k Controls Local Flexibility

Small k follows local detail; large k produces smoother decisions.

k = 1Very local

Low bias, high variance and sensitivity to noise.

Moderate kValidated balance

Uses enough neighbours to resist isolated noise while preserving structure.

Large kVery smooth

Higher bias; minority and local patterns may disappear.

DETAILED EXPLANATION

k is a hyperparameter that determines neighbourhood size. With k=1, boundaries can twist around individual points. Increasing k averages more evidence and smooths the boundary. Choose k inside cross-validation, usually testing a meaningful range rather than applying a fixed square-root rule.

WORKED INTUITION

A noisy neighbour can control k=1, while k=5 may outvote it using four consistent nearby examples.

AI / PLACEMENT CONNECTION

For binary classification, odd k can reduce simple ties, but weighted votes and multiclass tasks can still tie.

COMMON MISCONCEPTION

Increasing k does not always improve accuracy; excessive smoothing causes underfitting.

CONCEPT 05

Voting, Weighting and Tie Handling

Neighbours can contribute equally or according to proximity.

UNIFORMvote(C)=count(label=C)

Every selected neighbour contributes one vote.

DISTANCE-WEIGHTEDvote(C)=Σ 1/(dᵢ+ε)

Closer examples contribute more evidence.

TIE POLICYnearest / prior / fixed rule

Define deterministic behaviour before deployment.

DETAILED EXPLANATION

Uniform voting treats the first and kth neighbour equally. Distance weighting lets nearer samples exert more influence, commonly using inverse distance with a small numerical safeguard. Exact duplicates at zero distance need explicit handling, and all tie-breaking must remain deterministic.

WORKED INTUITION

Two moderately distant blue neighbours can win a count vote, while one almost identical red neighbour can win a weighted vote.

AI / PLACEMENT CONNECTION

Explain how weighting changes the effective boundary without changing which neighbours are selected.

COMMON MISCONCEPTION

Distance weighting cannot rescue irrelevant features or a badly chosen metric.

CONCEPT 06

Complexity and the Curse of Dimensionality

k-NN becomes slower and neighbourhoods become less meaningful as data grows.

STORAGEO(nd)

Retain n samples with d features.

NAIVE QUERYO(nd + n log n)

Measure distances and fully sort; partial selection can reduce sorting work.

HIGH DIMENSIONSDistances concentrate

Nearest and farthest samples become less distinguishable.

MITIGATIONSelect, reduce, index

Use meaningful features, PCA or approximate-neighbour systems when justified.

DETAILED EXPLANATION

In high-dimensional spaces, volume grows rapidly and available samples become sparse. Distances can concentrate, so the nearest point is not much nearer than the farthest. k-NN also stores training data and performs substantial work per query, making latency and memory important deployment constraints.

WORKED INTUITION

A dense neighbourhood in two dimensions can become an almost empty region after adding many independent dimensions.

AI / PLACEMENT CONNECTION

State training, storage and inference complexity separately; “training is O(1)” ignores preprocessing and indexing.

COMMON MISCONCEPTION

More features can reduce k-NN quality when those features add noise rather than signal.

CONCEPT 07

Naive Bayes Reverses the Probability Question

Bayes rule combines prior class belief with evidence likelihood.

POSTERIORP(C|x) = P(x|C)P(C) / P(x)

P(C) — prior class probability

P(x|C) — likelihood of evidence under the class

P(C|x) — updated class probability

DETAILED EXPLANATION

Naive Bayes scores each class by multiplying its prior probability by the likelihood of observed features under that class. The shared evidence term P(x) is identical while comparing classes, so prediction can use an unnormalized score and normalize only when posterior probabilities are required.

WORKED INTUITION

If “winner” is much more common in spam than normal mail, observing it increases the posterior probability of spam.

AI / PLACEMENT CONNECTION

Interview calculations often omit P(x) during argmax because it is constant across candidate classes.

COMMON MISCONCEPTION

P(evidence|class) and P(class|evidence) are different conditional probabilities.

CONCEPT 08

The “Naive” Conditional-Independence Assumption

Features are treated as independent after the class is known.

P(x₁,…,x_d | C) ≈ ∏ᵢ P(xᵢ | C)
Prior×Evidence 1×Evidence 2×…
DETAILED EXPLANATION

The assumption says features become conditionally independent once the class is fixed. It is frequently false—words and measurements can be correlated—but it reduces a difficult joint-density problem into manageable one-feature estimates. Classification can still work well when the resulting class ranking remains useful.

WORKED INTUITION

“machine” and “learning” are correlated words, yet their separate class likelihoods may still produce a useful document score.

AI / PLACEMENT CONNECTION

Say conditional independence, not absolute independence.

COMMON MISCONCEPTION

Naive Bayes does not require each feature to be unrelated in the complete dataset.

CONCEPT 09

Gaussian Naive Bayes for Continuous Features

Each feature is modeled with a class-specific Gaussian distribution.

LIKELIHOODP(xⱼ|C)=𝒩(xⱼ; μCj, σ²Cj)

Estimate one mean and variance per feature per class.

USE CASESMeasurements and dense numeric features

Examples include sensor values, flower dimensions and standardized scores.

DETAILED EXPLANATION

Gaussian NB estimates a mean and variance for every feature within every class, then evaluates the Gaussian density of each query value. It is fast and works well when class-conditional feature shapes are reasonably bell-like, though classification can remain useful without perfect normality.

WORKED INTUITION

A height close to one class mean and far from another receives a larger density under the first class.

AI / PLACEMENT CONNECTION

Know that variance smoothing protects calculations when a feature has nearly zero within-class variance.

COMMON MISCONCEPTION

The complete dataset need not be Gaussian; the assumption is feature-wise and class-conditional.

CONCEPT 10

Multinomial Naive Bayes for Counts

Token counts or non-negative frequencies become class evidence.

DOCUMENT“free course winner”
→
COUNT VECTOR[free:1, course:1, winner:1]
→
CLASS SCORElog P(C)+Σ countⱼ log P(wordⱼ|C)
DETAILED EXPLANATION

Multinomial NB models how often discrete events such as words occur in each class. With text, vocabulary counts are estimated from training documents. The document score adds the class log-prior and each token count multiplied by its class-specific log-likelihood.

WORKED INTUITION

Repeated spam-associated terms contribute repeatedly to the spam score in a count representation.

AI / PLACEMENT CONNECTION

Multinomial NB is a strong, fast baseline for bag-of-words and TF-IDF-like non-negative inputs.

COMMON MISCONCEPTION

Standardized negative feature values are not suitable inputs for a multinomial count model.

CONCEPT 11

Bernoulli Naive Bayes for Presence or Absence

Binary features record whether each event occurred.

FREE1

Present

WINNER0

Absent

MEETING1

Present

CLICK0

Absent

DETAILED EXPLANATION

Bernoulli NB treats every feature as a binary event. Unlike Multinomial NB, absence can also contribute evidence because the likelihood contains a term for present and absent features. It is suitable when occurrence matters more than repetition.

WORKED INTUITION

Ten occurrences and one occurrence both become present=1 after binarization.

AI / PLACEMENT CONNECTION

Compare the data-generating assumptions of Bernoulli and Multinomial variants before selecting one.

COMMON MISCONCEPTION

Bernoulli NB is not merely Multinomial NB with small counts; absent features affect its likelihood.

CONCEPT 12

Smoothing and Log-Probabilities Keep Scores Stable

One unseen event should not erase an entire class score.

ZERO-FREQUENCY PROBLEMone likelihood = 0 ⇒ product = 0

An unseen training event removes all other evidence.

LAPLACE / ADD-α(count+α)/(total+αV)

Add pseudocount evidence across vocabulary size V.

LOG SPACElog ∏pᵢ = Σlog pᵢ

Avoid floating-point underflow from many tiny products.

DETAILED EXPLANATION

Additive smoothing assigns non-zero probability to events absent from a class’s training examples. α=1 is Laplace smoothing; smaller positive values provide gentler smoothing. Logarithms transform products into sums, preserving the class ranking while preventing products of many small probabilities from underflowing to zero.

WORKED INTUITION

A word unseen in spam receives a small smoothed likelihood instead of making the spam document probability exactly zero.

AI / PLACEMENT CONNECTION

Be ready to calculate a smoothed categorical probability including the vocabulary term αV.

COMMON MISCONCEPTION

Smoothing does not mean adding α only to the numerator; the denominator must also change.

CONCEPT 13

k-NN and Naive Bayes Solve Different Problems Well

Model choice should follow data representation, latency and validation evidence.

QUESTION
k-NN
NAIVE BAYES
Learning style
Local, instance-based
Probabilistic, parameter-estimating
Training cost
Low, apart from preparation/indexing
Very low count/statistic estimation
Prediction cost
Potentially high
Usually very low
Key assumption
Nearby means similar
Conditional feature independence
Typical strength
Flexible local boundaries
High-dimensional sparse text
DETAILED EXPLANATION

k-NN makes few distribution assumptions but strongly depends on a meaningful metric and sufficiently dense local data. Naive Bayes makes a strong independence assumption but learns compact statistics and predicts quickly. Neither is universally superior; compare pipelines with identical leakage-safe validation.

WORKED INTUITION

k-NN may suit a small geometric dataset, while Multinomial NB can classify thousands of sparse word features efficiently.

AI / PLACEMENT CONNECTION

A strong interview comparison covers assumptions, scaling, training, inference, memory and interpretability.

COMMON MISCONCEPTION

Algorithm simplicity does not make evaluation, preprocessing or deployment design optional.

CONCEPT 14

The CodeBhavya Neighbour-to-Evidence Workflow

Build each baseline as a complete, testable pipeline.

  1. 01
    Frame

    Define class, prediction unit, available evidence and error costs.

  2. 02
    Split

    Protect test data using stratified, grouped or time-aware logic.

  3. 03
    Represent

    Impute, encode and scale according to the algorithm.

  4. 04
    Validate

    Tune k, metric, weighting, NB variant and smoothing.

  5. 05
    Diagnose

    Inspect neighbours, likelihoods, errors and subgroup behaviour.

  6. 06
    Deploy

    Version the entire pipeline and monitor drift, latency and quality.

knn = Pipeline([("scale", StandardScaler()), ("model", KNeighborsClassifier())])
nb = Pipeline([("vectorize", CountVectorizer()), ("model", MultinomialNB())])
# Compare both with suitable cross-validation and task metrics.
INTERACTIVE LEARNING • CODEBHAVYA PREMIUM VISUALIZER

🎬 k-NN Neighbourhood Decision Laboratory

Move the query, change k, metric and vote weighting, then inspect exactly which neighbours control the prediction.

LIVE

Tip: click anywhere on the plot to move the query.

BLUE VOTE0
PINK VOTE0
PREDICTION—Move the query to experiment
SELECTED NEIGHBOURS

INTERACTIVE LEARNING • PROBABILITY ENGINE

🧠 Naive Bayes Message Classifier

Select words, adjust the spam prior and smoothing, then watch each likelihood update the competing log-scores.

LIVE
SELECT MESSAGE WORDS
SPAM POSTERIOR—
NORMAL POSTERIOR—
log score • spam—
log score • normal—
MODEL DECISION—

WORD-BY-WORD EVIDENCE
PROGRAM TRACING • TRUE LOOP AND SORT FLOW

Trace k-NN Classification from Scratch

Follow every coordinate difference, squared distance, sorted neighbour and class vote.

CORE ALGORITHM

k-NN Classification Without a Library

This compact implementation exposes distance calculation, neighbour selection and majority vote.

from math import sqrt
points = [(1, 1, "Blue"), (2, 2, "Blue"),
          (5, 4, "Pink"), (6, 5, "Pink")]
query = (3, 3)
k = 3
distances = []
for x, y, label in points:
    distance = sqrt((x-query[0])**2 + (y-query[1])**2)
    distances.append((distance, label))
distances.sort()
neighbors = distances[:k]
votes = {}
for distance, label in neighbors:
    votes[label] = votes.get(label, 0) + 1
prediction = max(votes, key=votes.get)
print(prediction)
TRACE RESULT
Blue
  • Compute one distance per training sample.
  • Sort ascending so the nearest evidence comes first.
  • Keep exactly k neighbour records.
  • Count labels and select the largest vote.
PROGRAMMING PROBLEMS • CODEBHAVYA PATTERN

Build Distance and Probability Skills

Attempt each problem independently. Workspaces, hints and programs remain collapsed initially.

0 / 5Solved independently0 / 500Best score
QUICK KNOWLEDGE CHECK

Test Neighbour and Bayesian Reasoning

Select one answer per question. Results show your answer, the correct answer and an explanation.

Not checked yet
PLACEMENT CHECKPOINT

How k-NN and Naive Bayes Appear in Hiring Rounds

Strong answers connect formulas with preprocessing, complexity and model choice.

ROUND 01

Manual Calculation

Compute distances, nearest neighbours, votes and smoothed likelihoods.

ROUND 02

Algorithm Comparison

Contrast assumptions, scaling, training time, latency and memory.

ROUND 03

Scenario Selection

Choose k-NN for local geometry or an NB variant for suitable distributions.

ROUND 04

Production Design

Discuss leakage-safe pipelines, indexing, drift and probability quality.

CodeBhavya interview pattern:Define representation → State assumption → Show formula → Trace prediction → Give complexity → Name failure mode → Validate.
INTERVIEW PREPARATION

🎤 k-NN & Naive Bayes — Interview Questions

Answer aloud before selecting Show Answer for each explanation.

KEY TAKEAWAY

Two Routes from Evidence to Class

1Represent

Create leakage-safe numeric evidence.

→
2Assume

Nearby means similar, or features factor by class.

→
3Combine

Vote among neighbours or add log-likelihoods.

→
4Validate

Select the model that generalizes and deploys well.

k-NN asks “Which examples resemble this query?” Naive Bayes asks “Under which class is this evidence most probable?”
EXTRA TIPS

Habits of Strong Classical-ML Practitioners

01

Scale distance-sensitive features inside the validation pipeline.

02

Inspect the actual nearest neighbours to diagnose surprising k-NN decisions.

03

Tune k, metric and weighting together because their effects interact.

04

Choose the Naive Bayes variant from the feature distribution—not the task name.

05

Use log-probabilities and smoothing for stable Bayesian calculations.

06

Compare accuracy with latency, memory, calibration and failure costs.

EXTRA PRACTICE QUESTIONS

Strengthen Distance and Bayes Reasoning

Calculate intermediate values before checking any library output.

  1. 01

    Compute Euclidean and Manhattan distances between (2,3) and (6,8).

  2. 02

    Predict a query using k=1, k=3 and k=5 from a supplied point table.

  3. 03

    Show how standardization changes the nearest neighbour.

  4. 04

    Compare uniform and inverse-distance votes for the same neighbours.

  5. 05

    Explain the bias–variance effect of increasing k.

  6. 06

    Give storage and naive-query complexity for n samples and d features.

  7. 07

    Explain distance concentration in high-dimensional data.

  8. 08

    Calculate P(class|evidence) using two priors and likelihoods.

  9. 09

    Apply Laplace smoothing to an unseen word.

  10. 10

    Compare Gaussian, Multinomial and Bernoulli Naive Bayes.

  11. 11

    Explain why log-scores preserve the prediction argmax.

  12. 12

    Design cross-validation to compare k-NN with Naive Bayes fairly.