decision trees naive bayes and k nearest neighbors notes

Chapter Roadmap: Decision Trees, Naive Bayes and k-NN

@keyframes stepReveal { from { opacity: 0; transform: translateX(-10px); } to { opacity: 1; transform: translateX(0); } } .roadmap-step { animation: stepReveal 0.5s ease forwards; opacity: 0; } .roadmap-step:nth-child(1) { animation-delay: 0.1s; } .roadmap-step:nth-child(2) { animation-delay: 0.3s; } .roadmap-step:nth-child(3) { animation-delay: 0.5s; } Chapter Roadmap Decision Trees, Naive Bayes & k-NN 01 | k-Nearest Neighbors Instance-based, lazy learning. Distance metrics, choosing k, decision boundaries. 02 | Naive Bayes Generative, probability-based. Conditional independence, priors, likelihoods. 03 | Decision Trees Eager, rule-based. Attribute splits, impurity measures, pruning. What you will master: How each classifier predicts, solving numerical problems step-by-step, and comparing methods by cost and assumptions.

k-Nearest Neighbors Classification

k-Nearest Neighbors "A point is classified by the company it keeps." What you will learn Why k-NN is an instance-based and lazy learner. How to use distance metrics to find nearest points. How the choice of k changes the decision boundary. How to solve small numerical prediction problems safely. Common traps: ties, even k, and high-dimensional data. Context: The simplest non-parametric classifier in this chapter, showing a purely distance-driven way of thinking.

The Core Mechanism of k-NN

The Core Mechanism k-NN is a non-parametric, lazy learner . It stores training examples and delays computation until prediction. TRAINING PHASE Store dataset D = {(x_{i}, y_{i})}_{i = 1}^{N} . No explicit objective function is optimized. PREDICTION PHASE Compute distances, select k closest points N_{k} (x_{q}), and assign the majority class. Majority-Vote Rule \overset{y}{^} = ar g c max i \in N_{k} (x_{q}) \sum I (y_{i} = c) I (y_{i} = c) is 1 if neighbor i has class c, else 0.

57 more cards in this chapter

Decision Trees, Naive Bayes and k-Nearest Neighbors Notes for GATE DA

Decision Trees, Naive Bayes and k-Nearest Neighbors notes for GATE DA: 60 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Decision Trees, Naive Bayes and k-NN

Chapter Roadmap

Decision Trees, Naive Bayes & k-NN

01 | k-Nearest Neighbors

Instance-based, lazy learning. Distance metrics, choosing k, decision boundaries.

02 | Naive Bayes

Generative, probability-based. Conditional independence, priors, likelihoods.

03 | Decision Trees

Eager, rule-based. Attribute splits, impurity measures, pruning.

What you will master: How each classifier predicts, solving numerical problems step-by-step, and comparing methods by cost and assumptions.

k-Nearest Neighbors Classification

k-Nearest Neighbors

"A point is classified by the company it keeps."

What you will learn

Why k-NN is an instance-based and lazy learner.
How to use distance metrics to find nearest points.
How the choice of k changes the decision boundary.
How to solve small numerical prediction problems safely.
Common traps: ties, even k, and high-dimensional data.

Context: The simplest non-parametric classifier in this chapter, showing a purely distance-driven way of thinking.

The Core Mechanism of k-NN

The Core Mechanism

k-NN is a non-parametric, lazy learner. It stores training examples and delays computation until prediction.

TRAINING PHASE

Store dataset

D = {(x_{i}, y_{i})}_{i = 1}^{N}

. No explicit objective function is optimized.

PREDICTION PHASE

Compute distances, select

k

closest points

N_{k} (x_{q})

, and assign the majority class.

Majority-Vote Rule

\overset{y}{^} = ar g c max i \in N_{k} (x_{q}) \sum I (y_{i} = c)

I (y_{i} = c)

is 1 if neighbor

i

has class

c

, else 0.

Choosing k: The Bias-Variance Tradeoff

Choosing k: Bias-Variance

The value of $k$ controls how smooth or sensitive the classifier is.

Small k (e.g., 1)

Low Bias, High Variance

Highly flexible, jagged boundary
Sensitive to noise/outliers
Risk of overfitting

Trusts local detail

Large k (near N)

High Bias, Low Variance

Very smooth boundary
Ignores local structure
Risk of underfitting

Trusts broader majority

Rule: Use cross-validation to find optimal

k

. For binary classification, prefer an odd $k$ to reduce exact voting ties.