Decision Trees & Naive Bayes for GATE DA: Entropy, Gini & Worked Classifications
The two most computation-heavy classifiers in the GATE DA paper — entropy and information gain calculated digit by digit, Gini compared on the same split, and a complete naive Bayes classification worked end to end.
By Piyush Wairale · GATE DA Educator & Course Instructor, IIT Madras BS Programme · Updated August 2026
Key Takeaways
• Entropy H = −Σp log₂p measures impurity in bits: 0 for a pure node, 1 for a 50–50 binary split. A 9+/5− node has H ≈ 0.940 — memorise it, GATE reuses this dataset.
• Information gain = parent entropy − weighted child entropy; ID3 splits on the attribute with the largest gain. CART uses Gini = 1 − Σp² instead.
• Naive Bayes assumes features are conditionally independent given the class, so P(class|x) ∝ P(class)·ΠP(xᵢ|class). You compare unnormalised scores — no denominator needed.
• Laplace smoothing (+1 to counts) rescues zero probabilities; unpruned trees overfit (low bias, high variance) while naive Bayes is fast, robust and surprisingly hard to beat on small data.
On this page
Entropy (worked) · Information gain (worked) · Gini vs entropy · ID3 vs CART · Overfitting & pruning · Naive Bayes (full classification) · Laplace smoothing · Tree vs NB table · Solved problems · Mistakes · Exam patterns · FAQs
Entropy: Impurity Measured in Bits
A decision tree grows by repeatedly asking: which question makes my data purest? To answer, it needs a number for “impurity”. Entropy is that number. For a node where class proportions are p₁, p₂, …:
Worked: a node with 9 positive and 5 negative examples has p₂ = 9/14, p₋ = 5/14:
H = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = −0.643(−0.637) − 0.357(−1.485) = 0.410 + 0.530 = 0.940 bits.
Both decision trees and naive Bayes are named in the official GATE DA syllabus; the ML pillar guide shows where they sit in the full preparation order.
▶ Watch: my complete Machine Learning playlist for GATE DA
Entropy, trees and naive Bayes numericals solved on camera — all playlists →
Information Gain, Fully Worked
Information gain of attribute A = entropy before the split minus the weighted average entropy after it:
Worked on the classic weather table (14 days, 9 Play / 5 Don’t-Play, so H(S) = 0.940). Take attribute Wind: 8 days are Weak (6 Play / 2 Don’t) and 6 days are Strong (3 Play / 3 Don’t).
H(Weak) = −(6/8)log₂(6/8) − (2/8)log₂(2/8) = 0.311 + 0.500 = 0.811.
H(Strong) = −(3/6)log₂(3/6) − (3/6)log₂(3/6) = 1.000 (a perfect 50–50 node).
Gain(S, Wind) = 0.940 − (8/14)(0.811) − (6/14)(1.000) = 0.940 − 0.463 − 0.429 = 0.048.
Repeat for every attribute and split on the largest gain (in the full weather dataset that’s Outlook, with gain 0.246). Every GATE tree numerical is this recipe on a smaller table — the only skill is careful log₂ arithmetic, so keep log₂3 ≈ 1.585 and log₂(1/3) ≈ −1.585 at your fingertips.
Gini Index on the Same Split — and How It Compares
CART’s impurity measure avoids logarithms entirely: Gini = 1 − Σpᵢ². Same node, 9+/5−: Gini = 1 − (9/14)² − (5/14)² = 1 − 0.413 − 0.128 = 0.459.
For the Wind split: Gini(Weak) = 1 − 0.75² − 0.25² = 0.375; Gini(Strong) = 1 − 0.5² − 0.5² = 0.500. Weighted: (8/14)(0.375) + (6/14)(0.500) = 0.429, so the Gini decrease is 0.459 − 0.429 = 0.030.
Properties GATE tests: for binary classes Gini maxes at 0.5 (entropy maxes at 1); both are 0 for pure nodes; both usually pick the same split; Gini is cheaper to compute. If a question says “impurity 0.5 at a 50–50 node”, it’s Gini; “1 bit” means entropy.
ID3 vs CART in 30 Seconds
ID3: entropy/information gain, multiway splits on categorical attributes, classification only, biased toward many-valued attributes (C4.5 fixes this with gain ratio). CART: Gini (classification) or variance reduction (regression), strictly binary splits, handles numeric thresholds naturally, supports pruning by cost-complexity. “Which algorithm produces only binary trees?” — CART. That MCQ appears constantly in GATE-adjacent papers.
Overfitting and Pruning
Grown to full depth, a tree can memorise every training row — pure leaves, 100% training accuracy, terrible test accuracy. That’s the low-bias/high-variance regime. Two remedies: pre-pruning (stop early: max depth, min samples per leaf, min gain threshold) and post-pruning (grow fully, then cut subtrees that don’t improve validation accuracy — e.g. CART’s cost-complexity pruning, which penalises tree size with a parameter α). Pruning trades a little training accuracy for a lot of generalisation — the same bias–variance bargain you saw with λ in ridge regression.
Naive Bayes: a Full Classification, Worked
Naive Bayes applies Bayes’ theorem with one bold assumption: features are conditionally independent given the class. Then:
The denominator P(x) is identical for every class, so you just compare unnormalised scores.
Worked: classify (Outlook = Sunny, Wind = Strong)
From the same 14-day weather table: P(Play) = 9/14, P(No) = 5/14, and the conditionals: P(Sunny|Play) = 2/9, P(Strong|Play) = 3/9, P(Sunny|No) = 3/5, P(Strong|No) = 3/5.
Score(Play) = (9/14)(2/9)(3/9) = 0.643 × 0.222 × 0.333 = 0.0476.
Score(No) = (5/14)(3/5)(3/5) = 0.357 × 0.600 × 0.600 = 0.1286.
Score(No) > Score(Play) → predict Don’t Play. If the question asks for the actual posterior, normalise: P(No|x) = 0.1286/(0.1286+0.0476) ≈ 0.73.
Laplace Smoothing, Worked
Suppose no “No” day was ever Overcast: P(Overcast|No) = 0/5, and one zero annihilates the whole product. Add-one (Laplace) smoothing fixes it: add 1 to every count and add k (the number of attribute values) to the denominator. With Outlook ∈ {Sunny, Overcast, Rain}, k = 3:
P(Overcast|No) = (0+1)/(5+3) = 1/8, and correspondingly P(Sunny|No) = (3+1)/8 = 1/2, P(Rain|No) = (2+1)/8 = 3/8 — still summing to 1. For continuous features, Gaussian naive Bayes instead models P(xᵢ|C) as a normal density with the class’s mean and variance.
Decision Tree vs Naive Bayes: the Comparison Table
| Aspect | Decision tree | Naive Bayes |
|---|---|---|
| Model type | Discriminative rules (axis-aligned splits) | Generative, probabilistic |
| Key assumption | None on feature dependence | Conditional independence given class |
| Training cost | Higher (search over splits) | One pass of counting — very fast |
| Overfitting risk | High unless pruned | Low (high bias, low variance) |
| Interpretability | Excellent — human-readable rules | Moderate — probability products |
| Decision boundary | Piecewise axis-parallel | Linear/quadratic in log-space |
Contrast both with the margin-based approach in the SVM guide — GATE enjoys “which classifier would you pick?” scenario MCQs across all three.
Three GATE-Style Problems, Solved
Problem 1 (NAT). A node holds 4 positive and 4 negative examples. An attribute splits it into (4+, 0−) and (0+, 4−). Find the information gain.
Solution. H(parent) = 1 bit (perfect 50–50). Both children are pure: H = 0. Gain = 1 − (4/8)(0) − (4/8)(0) = 1 bit — the maximum possible for a binary problem.
Problem 2 (NAT). Compute the Gini index of a node with 3 positives and 1 negative.
Solution. p₂ = 0.75, p₋ = 0.25. Gini = 1 − (0.5625 + 0.0625) = 0.375. (Its entropy would be 0.811 — knowing both values for the 3:1 node saves time.)
Problem 3 (NAT). 40% of emails are spam. The word “free” appears in 60% of spam and 10% of non-spam. An email contains “free” — probability it is spam?
Solution. P(spam|free) = (0.4)(0.6) / [(0.4)(0.6) + (0.6)(0.1)] = 0.24/0.30 = 0.8. One-feature naive Bayes is just Bayes’ theorem — revise the machinery in the Bayes’ theorem deep dive.
Common Mistakes to Avoid
Forgetting the weights in gain. Child entropies must be weighted by |Sv|/|S| before subtracting. Unweighted averages are the #1 wrong answer.
Using log₁₀ instead of log₂. Entropy in bits needs base 2: log₂x = ln x / ln 2.
Comparing normalised and unnormalised NB scores. Either compare raw P(C)ΠP(xᵢ|C) for both classes, or normalise both — never mix.
Skipping smoothing when a zero count appears. If the question says Laplace/add-one, smooth every conditional of that attribute, not just the zero one.
Confusing max Gini (0.5) with max entropy (1.0) for binary nodes.
How GATE DA Asks Trees and Naive Bayes
The recurring patterns: (1) NAT — entropy/Gini of a node or information gain of one attribute (2 marks, exactly the recipe above); (2) MCQ — which attribute does ID3 pick, or properties of pruning; (3) NAT — a naive Bayes posterior on a 2-class table, often with Laplace smoothing; (4) MCQ — the independence assumption, generative vs discriminative, or tree-vs-NB trade-offs. Budget ~3 minutes for the numericals and double-check your logs.
Master the full ML syllabus for GATE DA 2027
My complete Machine Learning course covers decision trees, naive Bayes, SVM, regression, clustering, neural networks and PCA with recorded lectures, notes and GATE-level practice — aligned exactly to the DA syllabus.
Explore the Machine Learning Course →FAQs: Trees & Naive Bayes for GATE DA
Do I need to memorise log₂ values for the exam?
A few anchors help enormously: log₂3 ≈ 1.585, log₂5 ≈ 2.322, log₂7 ≈ 2.807, and H = 0.940 for the 9/14–5/14 node. Everything else follows from log₂(a/b) = log₂a − log₂b.
Why is naive Bayes “naive”?
Because it assumes features are conditionally independent given the class — almost never true in reality, yet the classifier still works well because only the ranking of class scores matters, not the exact probabilities.
Entropy or Gini — which will GATE ask?
Both have appeared. Compute-wise Gini is faster (no logs), so check which measure the question names before you start. Their split choices rarely differ.
When does naive Bayes beat a decision tree?
Small training sets, high-dimensional sparse features (text!), or when you need training in one pass. Trees win when feature interactions matter and you need interpretable rules.
What should I study next?
Bias–variance and cross-validation — the evaluation machinery behind pruning and model selection. The ML pillar guide lists the full order.
Keep the streak going: revise the complete ML roadmap, go deeper on the probability behind NB in the Bayes’ theorem guide, compare with margins in the SVM deep dive, and track your coverage against the GATE DA 2027 syllabus. New ML problem-solving sessions drop regularly on my YouTube channel — subscribe so you don’t miss them.
Recent Post
A* search and alpha-beta pruning for GATE DA 2027: full open/closed-list trace, admissible heuristics, minimax with pruning counted leaf by leaf, solved problems.
Taylor series and maxima-minima for GATE DA 2027: standard expansions, e^0.1 and cos(0.2) approximated, derivative tests and the Hessian rule worked with solved problems.
Normal forms for GATE DA 2027: functional dependencies, attribute closure worked, 1NF to BCNF with full decompositions, checklist table and solved GATE problems.
SQL and relational algebra for GATE DA 2027: σ, π and joins worked on sample tables, GROUP BY and nested queries evaluated row by row, plus solved GATE problems.
BFS and DFS for GATE DA 2027: graph traversals traced step by step with queue and stack states, shortest paths, Python code, complexity and solved GATE problems.
Sorting algorithms in Python for GATE DA 2027: bubble, insertion, selection, merge and quick sort traced step by step, binary search, complexity table and solved problems.
Learn Daily, Wherever You Are
Free lectures, exam updates, PYQ discussions, and job alerts — delivered through our YouTube channel and Telegram communities.
