—

Data Mining

Decision Trees

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

The classification dataset: attributes, train and test — covered in Lecture 2 (The Classification Dataset: Attributes, Train and Test)
Attribute types: nominal, ordinal, interval, ratio — covered in Lecture 3 (The Four Attribute Types)
Discrete and continuous attributes — covered in Lecture 3 (Discrete and Continuous Attributes) and Lecture 5 (Converting Continuous Attributes into Ordinal Attributes)
Training and testing a classifier — covered in Lecture 6 (Training and Testing a Classifier)
Overfitting and underfitting — covered in Lecture 6 (Overfitting and Underfitting)
Rule-based classification — covered in Lecture 5 (Rule-Based Classification)

These notes cover decision trees, the first full classification algorithm of this course. We start from the intuitive picture — a tree of questions that mirrors how people narrow choices — and then build it up formally: the tree structure, the divide-and-conquer partition of the input space into rectangles, the greedy top-down construction algorithm (ID3), and the three criteria used to pick which attribute to split on (entropy with information gain, the Gini index, and misclassification error). Along the way we work through several full numerical examples, answer the questions students actually ask, and finish with the stopping rules, why decision trees are so popular, and how they feed into ensemble methods like random forests and AdaBoost.

7.1 What a Decision Tree Is

7.1.1 The Tree Structure

Hook: Have you ever narrowed 500 search results down to the one product you wanted, using only a handful of yes/no questions? If you have, you have already run a decision tree in your head. This lecture takes that everyday skill and turns it into the first full classification algorithm of the course.

A decision tree is a classification algorithm, and its structure is a tree-like flowchart. It starts at a root node — the topmost decision point. Below the root come non-leaf nodes, which are also decision points. At the bottom sit leaf nodes, which carry the final answer: each leaf is labeled with a class. So the picture is: every non-leaf node asks a question about an attribute, and every leaf node outputs a class label.

The idea is familiar from any algorithms course: a tree-shaped structure with a single root, internal (non-leaf) nodes in the middle, and leaves at the bottom. The only new thing here is what the nodes do — they ask questions about the data instead of storing values.

Three kinds of nodes, and they are easy to tell apart by what they do:

Root node — the very first question the model asks about any sample. There is exactly one root, at the top of the tree. Every sample enters the tree here.
Non-leaf node (also called an internal node) — a middle-of-the-tree question. Each non-leaf node tests one attribute: "is the processor an i7?", "is the RAM 32 GB or more?". The answer to the question decides which branch the sample follows.
Leaf node — the bottom of the tree. A leaf asks no question; it only carries a prediction. Each leaf is labeled with a class, so a sample that reaches a leaf is assigned that leaf's class.

The important consequence of this layout: a decision tree is a sequence of tests, and the sequence is what makes the model explainable. For any sample you can trace the path from root to leaf and read off every test that was applied along the way.

The basic intuition is that this structure mirrors how humans actually make decisions, which is why it is so simple and intuitive. The example used in class is laptop shopping on Amazon. You type "laptop" and get roughly 500 laptops on screen. You want exactly one. How do you go from 500 to 1? You pick the most important property for you. Suppose that is the processor — you want an i7. So you filter: is the processor i7 or not? If yes, a limited set of laptops survives; if no, those laptops are discarded. Now the survivors are still too many, so you pick your second-most-important property, say memory: is the RAM 32 GB or more? Again the field narrows. Then the third property, say disk space: is the disk more than 2 TB? Each filter discards more laptops, and you keep moving until you reach the one laptop that matches your interests.

Worked trace: 500 laptops down to 1.

Let us write the shopping trip the way a tree would, with the numbers filled in.

Step 1 — the root question: is the processor an i7? Say 380 of the 500 laptops have a different processor: they are discarded immediately. The surviving 120 move to the next question.
Step 2 — is the RAM 32 GB or more? Say 90 of the 120 laptops fall short. The field drops to 30.
Step 3 — is the disk more than 2 TB? Say 29 laptops have smaller disks. One laptop survives — that one is the purchase.

Question asked	Survivors before	Survivors after
processor is i7?	500	120
RAM 32 GB or more?	120	30
disk more than 2 TB?	30	1

Sense-check: notice what makes this a tree rather than a random scan. The questions come in a fixed order, the most important property first, and at every question the remaining candidates split into two groups — those that pass and those that are dropped. That is a root node followed by two more decision nodes, with leaves at the end of each branch. A different shopper who cares most about weight would put a different question at the root and end up with a different tree — the tree encodes whose priorities were used.

Look at what just happened: that whole process is a decision tree. When you face many options, you ask which property matters most, apply it first, then the second most important, then the third, and so on. That is exactly how humans think, and it is exactly the structure a decision tree encodes: an ordered chain of attribute tests, most important first, each test splitting the remaining candidates.

So the formal description of a decision tree model is: a flowchart in which each node tests one attribute, and at each leaf node a prediction is made. Because you can trace the path from root to leaf for any sample — "this sample went down this branch because of this test, then that branch because of that test" — the model tells you exactly why it predicted what it predicted.

7.1.2 A Model Is a Flowchart

Put differently, a decision tree is a flowchart where each non-leaf node tests an attribute and each leaf node makes a prediction. You can look at a trained tree and understand the decision-making process just by reading it: reach this leaf and the sample is predicted as class B; reach that leaf and it is predicted as class A, and so on.

Reading a tree is a two-step habit, and it is worth practicing on every tree you meet:

Follow the tests from the root down. At each node, look at the value of that attribute in your sample and take the matching branch. Continue until you reach a leaf.
Read the label at the leaf. That label is the prediction — and the path you just walked is the justification for it.

The same habit is how the model is explained to other people. In a credit-check tree, a customer who was rejected can be shown the exact tests that led to the rejection leaf: "refund = no, so you went right; marital status = married, so you went right; that leaf says no." That level of transparency is rare among classifiers.

This interpretability is one of the tree's biggest selling points, especially for business users. It is easy to set up, and easy to interpret — you can trace the path and see exactly why a particular sample was predicted as one class and not another.

Intuition: the flowchart is a contract with the reader. A black-box classifier is a "trust me" model: it gives an answer, but the reasoning stays inside the math. A decision tree is a "here is my reasoning" model: the flowchart is the reasoning, written out as questions a non-technical person can follow. That is why trees appear wherever the decision must be audited — loan applications, medical triage, fraud review — and why a business user can read the tree without a statistician translating the model.

Scope — what the flowchart does not do. A tree predicts one class per leaf; it does not claim the leaf's answer is guaranteed correct. The path explains which tests were applied, not whether the tree was right. Trees also assume the questions can be answered from the attributes you have: if the attribute used at a node is missing for a sample, the path breaks unless the implementation defines a fallback. And the tree only mirrors the ordering of importance that was used to build it — it is not a statement of causal truth (more on this when we discuss bias and greedy construction in Section 7.4).

Recap: a decision tree is a flowchart of attribute tests — one root question, middle decision nodes, and leaves that carry class predictions. Its superpower is interpretability: every prediction comes with a readable path from root to leaf. Next, we look at what the tree is actually doing to the data space: cutting it into rectangles, one test at a time.

Decision trees are everywhere in practice for exactly this reason: e-commerce product filters (the laptop example), credit and fraud screening (the cheat-detection dataset of Section 7.3), medical decision support, and quality control in manufacturing are all places where the decision and its explanation must travel together. And as Section 7.12 shows, trees also form the core of random forests and AdaBoost — so the interpretable flowchart you learn here is the building block of some of the most powerful models in use.

7.2 Partitioning the Space into Rectangles

7.2.1 Divide and Conquer on the Vector Space

The core working idea of a decision tree classifier: it uses a divide and conquer strategy to partition the input vector space into rectangles. Here is how to see it.

Imagine a classification problem with four classes. Draw the two attributes as an X axis and a Y axis, and project every point from the training data into this two-dimensional space. Each class appears as a cluster of points. To build a classifier we have to partition this 2-D space into multiple parts so that we can predict: when a test sample arrives, we want to say which class it belongs to. Before predicting, we build the model — and building the model means partitioning the space.

A simple way to partition: take the attribute you consider more important. If X is the more important attribute, partition on X first. The dividing line is placed where the class labels separate cleanly.

The recursive recipe is: take the current rectangle of space, split it along one attribute's value, look at each resulting sub-rectangle, and if a sub-rectangle still mixes classes, split it again — until every sub-rectangle contains points of only one class. Each split is a test in the tree, each final rectangle is a leaf.

Intuition: cutting a pizza, not carving a statue. Divide and conquer is like slicing a pizza for people with different toppings: you cut the whole pie into two pieces, check whether each piece is still mixed (someone wants a piece with both toppings), and keep cutting only the mixed pieces until every piece contains a single topping. The tree records the cutting order — root cut first, then the sub-cuts — and each final piece is a leaf whose label is the topping inside it. The analogy breaks in one way: a tree always cuts straight lines across a whole rectangle (one attribute test at a time), so the final pieces are always rectangles — never freeform shapes.

Note something the recipe deliberately does not do: it never cuts diagonally. Every split is of the form "is X greater than 0.4?" or "is Y greater than 0.5?" — a single attribute compared to a threshold. That is why the pieces are rectangles: each cut runs parallel to one axis, from one edge of the current rectangle to the other. This axis-aligned style is a property of classic decision trees, and it will matter when we discuss scope below.

The connection between the two views of the same model:

Tree view: a path of tests from root to leaf (Section 7.1).
Rectangle view: the same tests, seen as cutting a space. Each test is a cut along one axis; each leaf is one final rectangle.
The tree and the partition are the same object: the tree is the cutting recipe, and the partition is the tree drawn on the data space.

Keep both pictures in mind — some questions (like why a split helps or hurts) are easier to answer in rectangle language, and others (like why a prediction was made) are easier in tree language.

7.2.2 Worked Example: Four-Class Partition and Prediction

The full walkthrough from class: four classes, attributes X and Y, all training points projected into the plane. The classes appear as four symbol clusters — crosses and pluses on the right side of the plot, zeros and dashes on the left side — and the tree will separate them with three cuts.

The root test is on X: is X > 0.4? This divides the big rectangle into two rectangles. The right side (X > 0.4) still contains two classes — cross and plus — so it cannot be decided yet. The left side (X ≤ 0.4) also contains two classes.

On the right rectangle (X > 0.4), split on Y: is Y > 0.5? If yes, the sample lies in the upper right rectangle and the prediction is class B. If no, the prediction is class A. Both sub-rectangles now hold a single class, so these become leaves.

On the left rectangle (X ≤ 0.4), split on Y as well: is Y > 0.7? If yes, the prediction is class C. If no, the prediction is class D. Again both sides become leaves.

The letter-to-symbol mapping follows uniquely from the walkthrough: the right side holds the cross and plus classes, and Step 2 assigns class B to the upper right and class A to the lower right, so the plus class is B and the cross class is A. On the left side, Step 3 assigns class C to the upper left (Y > 0.7) and class D to the lower left, so the zero class is C and the dash class — also called the negative class in class — is D. The lecture used the letters and the symbols interchangeably; the pairs below are what both descriptions agree on.

Trace a test sample through the tree.

A new sample arrives with, say, X = 0.6 and Y = 0.8. Only its attribute values are known — the class is what the tree must predict.

Start at the root. Check is X > 0.4? Here 0.6 > 0.4, so yes — move right.
At the right node, check is Y > 0.5? Here 0.8 > 0.5, so yes — move to the upper right rectangle.
That rectangle is a leaf holding only the plus class. Prediction: class B.

Try a second sample, X = 0.2, Y = 0.1: X ≤ 0.4 so we move left; Y ≤ 0.7 so we move down; the lower-left rectangle holds only the dash class. Prediction: class D.

Sense-check: both samples were classified by three yes/no tests, no arithmetic beyond comparing two numbers. The tree's predictions are exactly as fast and exactly as explainable as the flowchart promised in Section 7.1.

The same example in rectangle language: the full dataset starts as one big rectangle. The root condition (X > 0.4) cuts it into rectangle 1 (right) and rectangle 2 (left). Rectangle 1 is still mixed, so the condition Y > 0.5 breaks it into rectangle 3 and rectangle 4; all samples in rectangle 3 belong to one class and all samples in rectangle 4 to the other (the cross class). Rectangle 2 is also mixed (classes C and D), so the condition Y > 0.7 breaks it into rectangle 5 — one class (the negative/dash class) — and rectangle 6 — the other (the zero class).

The takeaway: take a big vector space, repeatedly apply divide and conquer, and partition the dataset into rectangles until each rectangle contains elements of a single class only. That is how a decision tree works.

Scope — what this partition can and cannot express.

Every boundary is axis-aligned: a cut is always "X > t" or "Y > t", never a diagonal line. A dataset whose classes are best separated by a diagonal boundary (say, class above the line Y = X) will need many staircase-like splits to approximate that diagonal — or will stay mixed if the tree stops early. Tree learners accept this limitation in exchange for speed and interpretability.
The classes must be separable by rectangles with at least one sample each. If two classes occupy exactly the same region of space, no axis-aligned tree can separate them — they share a rectangle forever.
The split order is the tree's shape: X first, then Y, gives a different partition than Y first. Which order is better is decided by the splitting criteria of Sections 7.7–7.10, not by intuition.
Small data traps: with one training point per class cluster, the tree may cut "between" points that are only 0.01 apart; the model then fits the training noise instead of the real class shape.

Recap: a decision tree is divide and conquer on the data space — cut a rectangle along one axis, keep cutting any sub-rectangle that still mixes classes, and stop when every piece holds one class. The tree of tests and the partition of rectangles are the same object in two languages. The next question is practical: when there are many attributes, which one should be cut first? That is the attribute-selection problem that the rest of this lecture answers.

7.3 Decision Trees for Classification: Process and Algorithms

7.3.1 From Training Data to Predictions

The classification process has two phases. First, from the training dataset, the algorithm learns and builds the final decision tree. Second, once the tree is built, the testing dataset is passed through the tree to make predictions.

The two phases, in the order the data flows:

Training (model building). Input: the training dataset — samples with both attributes and known class labels. Output: a finished tree. The tree's questions, their order, and the leaf labels are all decided here. From now on the training data is not consulted again.
Prediction (testing). Input: a test sample — attributes only, class label unknown. Output: a predicted class. The sample enters at the root, follows branches according to its attribute values, and exits at a leaf, whose label is the prediction.

The two phases must not be mixed: the tree is built on training data alone, and test data is only passed through the finished tree. This separation is what lets you measure whether the tree generalizes — if the tree had already "seen" the test samples while being built, its reported accuracy would be meaningless.

Worked example: cheat-detection prediction. Suppose the tree has already been built from the training examples of a cheat-detection system with three attributes — refund, marital status, and taxable income. A test sample arrives. Start at the root: the root tests what is the value of refund? In this test sample refund is no, so we move to the right branch. The next node tests what is the marital status? The sample says married, so we move right again. We have now reached a leaf — a decision point — so no more attributes need to be checked: the class label for this test data is no. The tree predicts no for this sample.

Trace: the cheat-detection test sample.

The sample: refund = no, marital status = married, taxable income = 95K.

Root: refund = ? The sample says no — take the right branch.
Second node: marital status = ? The sample says married — take the right branch again.
Leaf reached: prediction = no (not a cheat).

Two details worth noticing. First, the prediction was made without ever using taxable income: the path ended at a leaf before that attribute was needed. That is normal — a test sample only answers the questions along its own path, not every question in the tree. Second, the tree did not say "no because taxable income was low" — the reason is the path actually taken: refund was no, marital status was married, and samples like that are labeled no.

Sense-check: the trace took exactly two attribute tests, both answered from the sample's own values, and the leaf's label became the prediction — the same read-the-flowchart habit from Section 7.1, now on a real fraud-detection example.

The same reasoning that placed attributes in this order — refund at the root, marital status next, taxable income after that — is exactly what the rest of these notes formalizes with entropy, information gain, and the Gini index.

7.3.2 Algorithms for Building Trees

Several decision tree algorithms exist in the literature: Hunt's algorithm, CART, and ID3. They are all very similar, differing in small details; we focus on ID3. All of them are fundamentally decision trees. The original decision tree research paper was shared for reading — it explains the minute details of why a tree is built the way it is and what the criteria are.

The algorithm family, at a glance:

Hunt's algorithm — the oldest and most general formulation. It is a recursive recipe: a node is a leaf if all its training records belong to one class; otherwise pick a test that best separates the records into children and recurse. The other algorithms are best understood as particular ways of filling in the two open choices in Hunt's recipe — which test to apply, and how many children to create.
ID3 — the algorithm this course uses as its running example. It builds a tree top-down, choosing at each node the attribute with the highest information gain (Section 7.8) and creating one branch per attribute value.
CART — the algorithm behind the Gini criterion (Section 7.9). It is restricted to binary splits: every node creates exactly two children, even when the attribute has many values.

The three differ in small details — the impurity measure used, whether splits are binary or multi-way, and how stopping and pruning are handled — but the shared core is the same divide-and-conquer build we saw in Section 7.2.

Pitfall — treating the algorithm name as a single thing. "ID3" is a specific algorithm with a specific criterion (information gain) and multi-way splits; "CART" is another with binary splits and the Gini index. On the exam, be ready to say which algorithm uses which criterion, because that pairing is tested. Also be careful with the phrase "the decision tree algorithm": there is no single one — there is a family (Hunt, ID3, CART, C4.5, and others) that all produce trees but differ in these details.

Recap: classification with trees is a two-phase process — build the tree from training data, then pass test samples through it. The cheat-detection example showed a prediction made in two tests (refund, then marital status), and the algorithm family (Hunt's algorithm, ID3, CART) explains how the tree gets built. Before we can build one, we need to settle a question the laptop analogy raised: many trees are possible for one dataset — so which one should we build? That is the question of bias, next.

7.4 Many Possible Trees, One Bias

7.4.1 Same Dataset, Different Trees

On the same dataset you can build many different trees. Return to the laptop example: for one person, processor is the most important criterion, so processor sits at the root. For someone else, the weight of the laptop is the most important criterion, so weight would be at the root instead, and the rest of the tree would look completely different. The cheat-detection dataset likewise supports many trees: the tree we saw put refund at the root, then marital status, then taxable income — but that is just one choice among many.

So: from one dataset, we can build N different trees. Which one should we choose? That choice is defined by something called bias.

Intuition: bias is the tie-breaker you cannot see. If a dataset supports N trees that all classify the training data perfectly, the data alone gives you no reason to prefer one over the others — the choice has to come from outside the data. That outside preference is the algorithm's bias: the built-in assumption that tells the builder which of the many equally-correct-looking trees to actually construct. Every classification algorithm carries one; trees just make theirs easy to name.

7.4.2 The Bias of Decision Trees: Smallest Tree Wins

Every classification algorithm has some bias — this holds for K-nearest neighbors, for decision trees, for all classification algorithms. Given a dataset you can make N different models; you want to make the model that is most efficient and effective. For decision trees, the bias is: the tree should be as small as possible. From one dataset you could make, say, 15 different tree models, but the final tree you actually build should be the smallest in size. The splitting criteria exist precisely to help you build smaller trees.

Why "smallest" is a sensible preference, and why it is called a bias:

A small tree is a short path from root to leaf, which means fewer tests per prediction — the model is fast to run.
A small tree is easier to read, explain, and audit — the interpretability of Section 7.1 gets better as the tree shrinks.
A small tree is more likely to have found real class structure instead of memorizing accidents in the training data — it tends to generalize better.

The textbooks justify the same preference under the name Occam's razor: among models that fit the data equally well, prefer the simpler one. The lecture's version is the operational one — "the tree should be as small as possible" — and the splitting criteria we study next (entropy, information gain, Gini) are the machinery that makes small trees happen.

How do you get a small tree without trying all trees? With the greedy strategy, which works on local factors. That is why the bias and the greedy strategy go together: the greedy choices aim at small children and so at a small final tree.

7.4.3 The Greedy Strategy and No Backtracking

Decision tree construction is greedy. The idea of a greedy strategy: you do not have a vision of the final solution. Locally, you decide a criterion that helps you choose, out of all the attributes, the most important one, and based on that you start building the tree. You do not see the final tree; you look at local factors and build, hoping the final tree will be the most optimized one.

The key property: decision tree building has no backtracking. If you chose attribute A at the root and later discover the tree is not predicting well, you cannot go back and say "A was not the best attribute, let me choose B and redraw the tree." Greedy strategy has no such option. You make the locally best choice at each node, start building, and hope the final tree is a global optimum — with no backtracking. (There is a downside to this, which the questions below unpack: the local choice is not guaranteed to produce the global optimum.)

Trace: a greedy choice that you cannot take back.

Suppose the root has two candidate attributes. Attribute A splits the data into children that are almost pure; attribute B splits into children that are all mixed. Greedy says: pick A now.

Later the tree is built out. It turns out that B, although its children started mixed, would have led to a tiny subtree overall, while A forces three more splits below it. The final tree built on A is larger than the one that would have been built on B.

Under the no-backtracking rule, that discovery changes nothing: A stays at the root, and the larger tree is the delivered model. The greedy algorithm simply never evaluates the alternative — it committed to A when A looked best locally, and it cannot undo the commitment.

Sense-check: this is exactly why the lecture says the greedy strategy "hopes" for a global optimum. A global search would have tried both A and B at the root and compared the final trees, but with many attributes that search is too expensive (Section 7.11 discusses why). Greedy trades the guarantee away for tractability.

Pitfalls around bias and greed:

Confusing "locally best" with "globally best." The greedy root choice is optimal only for that node, not for the final tree — the no-backtracking rule means an early mistake is never repaired.
Thinking the bias makes the tree literally the smallest possible. The bias is a preference, not a search guarantee: greedy construction with a good splitting criterion produces a small tree, but not necessarily the minimum-size tree for the dataset.
Forgetting that bias exists in every classifier. If an exam question asks why trees are built the way they are, the answer chain is: many trees possible → bias says smallest → greedy strategy with no backtracking is how smallness is pursued without trying all trees.

Recap: one dataset, N possible trees, one bias — build the smallest tree you can. The greedy strategy pursues that bias one local decision at a time, with no backtracking, hoping the local choices add up to a small final tree. Everything that follows — split types, homogeneity, entropy, information gain, Gini — is machinery for making good local choices. Next: what a local choice looks like, starting with how a single node can be split.

7.5 Types of Splits

When building a tree you must decide how to split a node. Three separate questions arise:

How many ways to split? — two child nodes, three, four, or more;
Which attribute should be used for the split — A or B or C;
When do we stop building?

The first question depends on the type of attribute. Attributes come in three kinds — nominal, ordinal, and continuous — and for each you can choose a two-way (binary) split or an n-way (multi-way) split.

7.5.1 Splitting Nominal Attributes

A nominal attribute is one whose values are names or identifiers. "Name" is nominal; car type is nominal — it has three distinct values: family, sports, luxury. The only mathematical operation allowed on nominal values is distinctness: equality and inequality (is a equal to b, or not equal to b). There is no ordering among the values.

What "no ordering" buys and costs. A nominal attribute supports exactly one comparison: value equality. "Family < luxury" is meaningless for a car type — you cannot ask whether one car type is greater than another. So every split on a nominal attribute is a question about membership: "is the car type one of these values?" That one restriction is also the only restriction — nominal splits can group values in any way, because there is no order to preserve.

With nominal attributes you can choose a multi-way split or a binary split.

A multi-way split: as the name says, you create multiple child nodes. The number of children is decided by looking at the distinct values. Car type has three distinct values, so you split into three children: family, sports, luxury. If car type had five distinct values, you would make five children; with 50 distinct values, 50 children. Each child holds exactly one distinct value.

A binary split: each node gets exactly two children. When you have more distinct values than two, you club multiple distinct values together into one set. For car type with three values: put sports and luxury in the first child and family in the second — or the other way around, family and luxury together and sports alone. With five distinct values you can combine them any way — three and two, four and one, one and four. Any combination is allowed; there is no restriction.

Nominal car type, both flavors.

Car type = {family, sports, luxury}.

Multi-way split: three children — child 1: family, child 2: sports, child 3: luxury. Every distinct value gets its own branch.
Binary split, choice 1: child 1 = {sports, luxury}, child 2 = {family}.
Binary split, choice 2: child 1 = {family, luxury}, child 2 = {sports}.

Both binary groupings are legal, and so is the third grouping {family, sports} vs {luxury}. Nothing in the nominal type forbids any of them — the values carry no order, so there is no order to break.

Sense-check: each binary grouping is a question of the form "is the car type in this set?" — equality and inequality, the only operations nominal values allow.

7.5.2 Splitting Ordinal Attributes

An ordinal attribute is one where the order of the values is important. Size is the classic example: small, medium, large with the natural order small < medium < large. The order exists, and that is what makes size ordinal.

Ordinal attributes also allow multi-way or binary splits. A multi-way split works exactly like nominal: each child node gets a distinct value — small, medium, large — and with five values you could have extra small, small, medium, large, extra large.

For a binary split on an ordinal attribute there is one important constraint: when you club distinct values together, the order must not be broken. Combining small and medium into one child and large into the other is fine — the order stays intact. Putting medium and large together and small alone is also fine. But putting small and large together while the middle element (medium) goes elsewhere is not allowed, because inside the first child the order is broken — the middle value is missing.

For a nominal attribute such a "broken" grouping is allowed; for an ordinal attribute it is not. When clubbing distinct values of an ordinal attribute, maintain the order.

Pitfall — the ordinal split that looks fine and is not. Grouping {small, large} vs {medium} is illegal for an ordinal attribute, because the interval from small to large contains medium, which now lives in the other child — the first child claims to cover a contiguous range but has a hole in it. Any exam-style question that asks you to spot the invalid grouping is testing exactly this rule. Grouping {small, medium} vs {large} is legal: the first child is a contiguous range with no missing middle value.

7.5.3 Splitting Continuous Attributes

The third category of attributes — ratio and interval attributes — falls into the broad category of continuous attributes. A continuous attribute takes values like 1.0, 1.1, 1.2, 1.3, and so on — think of the price of petrol, which can be 100, 200, 300, and many values in between.

Two ways to handle a continuous attribute:

Discretization (making buckets). Round values into buckets. For example, use a rounding formula and round to zero decimal places: 1.1 rounds to 1, 1.5 rounds to 2. Buckets can be decided statically — "this is how the buckets look" — or dynamically, by looking at the data, for example with frequency bucketing. (That topic may appear later in the course.)
Binary split with a threshold. If the value is less than 5, go left; if greater than 5, go right. This gives two children with a condition on the attribute value.

Why continuous attributes need a special treatment at all. A continuous attribute can take infinitely many values, so "one branch per value" (the multi-way split that works for nominal and ordinal) is impossible — the tree would never end. The two strategies compress the infinite value line first: discretization groups values into a handful of buckets (each bucket becomes one branch), while the threshold split groups the line into two halves ("left of the cut, right of the cut"). Either way the tree's question becomes a finite choice again. The price for this is that the split position matters: a threshold at 5 and a threshold at 5.5 can produce different trees, so tree learners consider many candidate thresholds and pick the one the splitting criterion likes best.

The cheat-detection dataset's taxable income attribute illustrates both. A binary split: if taxable income is greater than 80K, go to this child; otherwise go to that child. A multi-way split with predefined buckets: less than 10K; 10K to 25K; 25K to 50K; 50K to 80K; greater than 80K.

Taxable income as a continuous attribute, both strategies.

Threshold split: income > 80K → child 1 (say, high earners); income ≤ 80K → child 2. Two children, one comparison.
Bucket split: five children — < 10K, 10K–25K, 25K–50K, 50K–80K, > 80K. Five children, one range check.

A sample earning 95K goes to the "> 80K" child in the first tree and to the "> 80K" bucket child in the second — same destination, different machinery. A sample earning 30K goes to the "≤ 80K" child in the first tree, but to the "25K–50K" bucket in the second — here the two trees disagree about where the sample sits, which is exactly why the choice between threshold and buckets changes the tree.

Sense-check: the threshold question is "is income greater than 80K?" — one comparison; the bucket question is "which of five ranges contains income?" — the same information, carved differently.

Summary of the options: binary attributes give two branches; multi-way attributes give more than two branches. Nominal attributes support both binary and multi-way splits. Ordinal attributes also support both, with the constraint that order must not be violated. Continuous attributes must first be broken into ranges (buckets) or thresholds, then split.

Comparison — the split menu at a glance.

Attribute type	Multi-way split	Binary split	Constraint
Nominal	one child per distinct value	club values into 2 groups, any grouping	none (values unordered)
Ordinal	one child per distinct value	club values into 2 groups	order must not be broken
Continuous	buckets (discretization)	threshold: value < t vs value ≥ t	needs discretization or a threshold first

When to pick which: multi-way splits are the natural fit for attributes with few distinct values (a car type with three values), while binary splits keep the tree small when an attribute has many values — and binary is the only option for continuous attributes unless you discretize first.

7.5.4 Student Questions and Answers

Q: Is SUV an ordinal attribute? Can you put an order on SUVs and MUVs?

A: It depends. If you can order the vehicles — say, by size — then you should treat them as ordinal and maintain that order while splitting. But if you cannot put them into an order, they are nominal, and then you have no ordering constraint. Typically, SUV and MUV are not ordinal; they are nominal attributes.

The test to apply on the exam: ask yourself whether a meaningful ordering between the values exists and is preserved by the split. SUV and MUV are names of vehicle body styles — there is no natural "SUV < MUV" relation — so they are treated as nominal, and any grouping of them in a binary split is legal.

7.6 Choosing the Attribute to Split: Homogeneity and Confidence

7.6.1 Why We Want Homogeneous Children

Back to the question that started this section: if you have five attributes, how do you choose the one to split on? Why should processor sit at the top of the laptop tree and not RAM or weight?

The answer connects to bias. Since the tree should be as small as possible, we want each split to move us quickly toward decision points. A child node is a decision point exactly when it is homogeneous — when all (or nearly all) of its samples belong to one class. A homogeneous child has less entropy; it is more pure. You want children that are homogeneous because once you reach a homogeneous node, you can take the decision easily.

In greedy terms: choose the attribute such that the child nodes are more homogeneous and have a lower degree of impurity, so you can reach a decision faster. You compare against attributes whose children are non-homogeneous (high degree of impurity), where you cannot yet decide.

Intuition: homogeneity is "one answer in the room." A node is like a committee that must reach a verdict. If everyone in the room agrees (all samples one class), the verdict is instant and unanimous — that is a homogeneous node, a decision point. If the room is evenly split between two opinions, the committee must either argue or call in more evidence — that is a heterogeneous node, and the tree must split it again. The smaller the tree, the fewer committees need to argue, which is why homogeneity and the small-tree bias are two views of the same goal.

7.6.2 Worked Example: Own Car, Car Type, or Student ID

Suppose before the split you have one node with 10 samples of class C0 and 10 samples of class C1. Three attributes are available: own car, car type, and student ID. Which gives the smallest final tree?

Walk through all three candidate attributes.

Splitting on own car. You get two children, A and B. Child A has 6 tuples of class C0 and 6 tuples of class C1 — perfectly mixed, so you cannot reach a decision there. Child B is also mixed. Neither child allows an immediate decision, so both must be split again below.

Splitting on car type. You get three children. Look at them: child B has all samples of class C0 and none of class C1 — perfectly homogeneous, a leaf node; the prediction at that leaf is class C0. Child C holds a majority of class C1, so it is close to a decision (maybe in the next iteration). Child A is also close. The three car-type children are more homogeneous than the two own-car children. One of the three children already ends the branch — the other two need at most one more split.

Splitting on student ID. You get four children, one per student — each child has a single sample, so every child is homogeneous. You do reach a decision point, but ask: are you reaching it with confidence? Student-ID node A has one sample of class C0 and zero of C1, so it predicts C0 — but based on one sample. Contrast with own-car child B, which had 8 samples of class C0: it also predicts C0, but with far more evidence behind it.

Choice. By homogeneity alone, student ID looks unbeatable — every child is pure. But that purity is bought with one-sample leaves, and a prediction supported by a single training sample is worth almost nothing. Car type wins the comparison: it produces a truly pure leaf (child B) with many samples behind it, and its remaining children are close to decisions. Own car produces only mixed children and is the worst choice here.

Sense-check: the criterion is not "purest children" alone, but "pure children with evidence." Student ID achieves purity by shredding the data into singletons — the tree becomes deep and every leaf is fragile. Car type achieves purity where it counts, with sample counts intact.

7.6.3 Where Confidence Comes From

This is the general principle: any classification algorithm outputs two things — a class label and a probability value telling you how confident the prediction is. A decision tree predicting "cheat / not cheat" outputs the class label and a probability: the fraction of samples of the predicted class at the leaf. That is where the confidence comes from — the number of samples at the leaf node. A leaf with 8 samples of C0 supports the C0 prediction far better than a leaf with 1 sample of C0. More samples at the leaf, more confidence.

So when choosing an attribute, think: this attribute should help me reach homogeneous nodes where I can decide — but among homogeneous outcomes, prefer the split that keeps more samples per leaf, because confidence comes from sample counts.

The leaf as a vote. When the tree predicts class C0 at a leaf, the leaf is really reporting a small vote: "x of my y training samples were C0." The natural confidence value is the fraction $x / y$ :

Leaf with 8 samples of C0 out of 8 → predicts C0 with confidence 8/8 = 1.0.
Leaf with 8 of C0 and 2 of C1 → predicts C0 with confidence 8/10 = 0.8.
Leaf with 1 sample of C0 → predicts C0 with confidence 1/1 = 1.0 — formally the same, but built on a sample size of one.

This is why student-ID-style splits are dangerous: they deliver perfect-looking leaves whose votes come from a sample size of one. A large training set protects against this — with more samples per leaf, the leaf's vote is based on real evidence. The textbooks note the same idea when they describe leaf probabilities and tree pruning: reliability grows with leaf sample size.

7.6.4 Student Questions and Answers

Q: We are building the tree on training data only, right?

A: Yes. The tree is built purely on the training data. (The test data is only passed through the finished tree to make predictions.)

Q: Do we select the most homogeneous classifier at every step, or is it greedier and only locally optimal?

A: This is the greedy part. At the root we choose the attribute that gives the most homogeneous children — but take the car-type split: one child came out homogeneous while the other two children did not. We do not know how those two will behave; we will have to split them again. We only see the local level — the middle child is homogeneous, the others are question marks, and we have no vision one more level down. Still, we take the call, hoping the choice leads to decision points quickly for the other children too. Whether local optimality ends up giving a global optimum, we simply do not know. That is why it is a greedy strategy: local call, no backtracking, hope for global optimality.

Pitfalls for this section:

Chasing purity at any cost. The student-ID split reaches pure children and still loses, because homogeneity without sample counts is worthless. If a tree builder's criterion rewards only purity, it can shred the data into one-sample leaves — deep, brittle, and ungeneralizable.
Reading a leaf's confidence as a probability of being right. The leaf fraction (8/10 = 0.8) is a confidence about the training samples in that leaf; it is not a guarantee about new samples.
Forgetting that test data never participates in building. The tree is trained on training data only; test samples only travel through the finished tree.

Recap: the best attribute is the one whose children become decision points fastest — homogeneous children — but only if the homogeneity is backed by sample counts. Confidence at a leaf is the fraction of samples of the predicted class among the samples at that leaf, which is why one-sample leaves are a trap. Now we need a quantitative way to say "how mixed is this node?" — that number is entropy, the first of the three famous splitting criteria.

7.7 Entropy

There are three famous criteria for choosing the best attribute in the literature: entropy (used via information gain), the Gini index, and misclassification error. These are the ones available in scikit-learn. We start with entropy.

7.7.1 What Entropy Measures

Entropy measures the amount of chaos in the system — the chaos in a node. A node is chaotic when it is heterogeneous: it mixes classes, so you cannot reach a decision point. Entropy quantifies that heterogeneity.

You want entropy to become zero, because at zero the node is homogeneous — all samples belong to one class. Ideally, you reduce the chaos in the system with every split; another way to say it is: choose the purer set, the one that gives homogeneous children.

Intuition: entropy is surprise, counted in bits. From the earlier lecture on information theory: a coin that always lands heads surprises nobody — it carries no information, entropy 0. A fair coin surprises every toss — maximum information, maximum entropy. A node works the same way: if a sample drawn from the node is certain to be class C2 (all samples are C2), the node's class "surprises" nobody — entropy 0. If a sample is equally likely to be either class (half C1, half C2), every draw is a coin flip — entropy at its maximum. So "how mixed is this node?" and "how surprising is its class?" are the same question.

7.7.2 The Entropy Formula

The entropy of a node is:

$H = - i = 1 \sum C p_{i} lo g_{2} p_{i}$

where $p_{i}$ is the probability of class $i$ in the node — the number of samples of class $i$ divided by the total number of samples in the node — and $C$ is the number of classes.

Let us name every piece before using it:

$H$ is the entropy of the node, measured in bits (because the log is base 2 — the same base used in the textbooks, where information is encoded in bits).
$p_{i}$ is the class probability in the node: $p_{i} = (number of class- i samples) / (total samples in the node)$ . The $p_{i}$ over all classes sum to 1.
$C$ is the number of classes (2 for a cheat/not-cheat node, 3 for a family/sports/luxury node, and so on).
The sum runs over all classes, $i = 1$ to $C$ .

The professor's spoken description preserved alongside the formula: "entropy is given by minus pi log pi where pi is the probability of a class in a child node," with the sum over classes $i = 1$ to $C$ .

The log of a probability is negative (probabilities lie in [0, 1]), so the minus sign in front makes entropy non-negative. A convention used implicitly in the worked example: $0 \cdot lo g_{2} 0$ is treated as 0, since $lo g_{2} 0$ is not defined.

Why the minus sign, and why the convention, are needed.

A probability $p_{i}$ is at most 1, so $lo g_{2} p_{i} \leq 0$ — every term $p_{i} lo g_{2} p_{i}$ is zero or negative. The minus sign flips the sum so that entropy is zero or positive. A pure node gives all-zero terms: $H = 0$ .
A class with zero samples contributes the term $0 \cdot lo g_{2} 0$ . Since $lo g_{2} 0$ is undefined, the convention $0 \cdot lo g_{2} 0 = 0$ is adopted — a class that is absent adds no chaos, which matches the meaning: no samples of a class means that class cannot mix anything.
The base matters for the numbers, not the ranking. Base 2 gives entropy in bits and the clean maximum of 1 for a 50/50 two-class node; base $e$ (natural log) would scale all values by a constant factor and rank attributes identically. The lecture and the reference texts use base 2, so $lo g_{2}$ is used throughout these notes.

7.7.3 Worked Example: Three Attributes A, B, C

Take three attributes, A, B, C. Splitting on each one produces a child node; we compute the entropy of each child and pick the attribute whose child is most homogeneous.

Compute the entropy of one child per attribute.

Attribute A. The child node has 0 samples of class C1 and 6 samples of class C2. Probabilities:

$p_{C 1} = \frac{0}{0 + 6} = 0, p_{C 2} = \frac{6}{6} = 1$

Entropy:

$H_{A} = - (0 \cdot lo g_{2} 0 + 1 \cdot lo g_{2} 1) = - (0 + 0) = 0$

Entropy zero means the child is homogeneous — all 6 samples are class C2 — so this is already a decision point.

Attribute B. The child node has 1 sample of class C1 and 5 of class C2:

$p_{C 1} = \frac{1}{6}, p_{C 2} = \frac{5}{6}$

$H_{B} = - \frac{1}{6} lo g_{2} (\frac{1}{6}) - \frac{5}{6} lo g_{2} (\frac{5}{6})$

Working the logs: $lo g_{2} (1/6) \approx - 2.585$ and $lo g_{2} (5/6) \approx - 0.263$ , so

$H_{B} = - \frac{1}{6} (- 2.585) - \frac{5}{6} (- 0.263) \approx 0.431 + 0.219 \approx 0.65$

An entropy of 0.65 means you should not be able to take a decision at this child: one sample is C1 and five are C2, so the node is mixed.

Attribute C. The child node gives entropy:

$H_{C} = 0.92$

The value corresponds to a child with 4 samples of class C1 and 2 of class C2 — the composition implied by the result, worked in full:

$H_{C} = - \frac{4}{6} lo g_{2} (\frac{4}{6}) - \frac{2}{6} lo g_{2} (\frac{2}{6})$

with $lo g_{2} (4/6) \approx - 0.585$ and $lo g_{2} (2/6) \approx - 1.585$ :

$H_{C} = - \frac{4}{6} (- 0.585) - \frac{2}{6} (- 1.585) \approx 0.390 + 0.528 \approx 0.918 \approx 0.92$

The same computation pattern appears in the reference text for nodes with counts (0,6), (1,5), and (3,3), giving 0, 0.650, and 1 — so the (4,2) mix at 0.92 sits consistently between the (1,5) and (3,3) cases.

Choice. Compare: 0 (A), 0.65 (B), 0.92 (C). Choose A, because its child has zero entropy — reaching that child lands you at a leaf node. In general, if no child reaches zero, choose the attribute whose children have the least entropy.

Sense-check: the ordering matches intuition from Section 7.6 — the most homogeneous child (all 6 samples of one class) wins, and the more mixed the child, the higher its entropy and the worse the attribute.

7.7.4 The Entropy Curve

There is a famous plot for the binary classification case (positive class vs negative class). Plot entropy against the probability of the positive class $p_{+}$ :

$p_{+} = 0$ : all samples are negative. Entropy = 0.
$p_{+} = 1$ : all samples are positive. Entropy = 0.
$p_{+} = 0.5$ : half positive, half negative. Entropy = 1 — its maximum.

The two endpoints are ideal cases: a homogeneous node. The middle is the worst case: entropy 1 means half the samples belong to one class and half to the other, you cannot reach a decision point, and you should not choose such an attribute. The curve is concave — high in the middle, zero at both ends — because of the log in the formula.

Scope — when the curve's numbers change. The shape (zero at both ends, peak in the middle) is universal, but the peak height is not always 1: for a node with $C$ classes the maximum entropy is $lo g_{2} C$ . The lecture's plot shows the two-class case, where $lo g_{2} 2 = 1$ — the cleanest example and the one used in the textbook comparison chart. A three-class node can reach $lo g_{2} 3 \approx 1.58$ , and a four-class node $lo g_{2} 4 = 2$ . The ranking logic never changes — lower entropy is always more homogeneous — only the scale does. Entropy is also invariant to which class you call "positive": swapping the labels swaps $p_{+}$ and $1 - p_{+}$ , and the curve is symmetric about $p_{+} = 0.5$ , as the two zero endpoints and the single peak show.

Visual intuition for the curve: put $p_{+}$ on the horizontal axis (from 0 to 1) and entropy on the vertical axis (from 0 up to 1). The curve leaves the origin at (0, 0), rises steeply, crests at the peak (0.5, 1), and falls back to (1, 0) — a single smooth, bell-less arch, concave everywhere. Landmarks: the two endpoints (0, 0) and (1, 0) are pure nodes — the two ideal decision points; the peak (0.5, 1) is the maximally mixed node — the "avoid me" point. One-sentence takeaway: the closer a node sits to either end of the axis, the closer it is to a decision; the closer to the middle, the more splits it will need.

Recap: entropy $H = - \sum p_{i} lo g_{2} p_{i}$ counts the chaos in a node in bits — 0 for a pure node, $lo g_{2} C$ for a maximally mixed one, with the convention $0 \cdot lo g_{2} 0 = 0$ . The attribute whose children have the lowest entropy is the one that reaches decision points fastest. But a tree builder needs more than a single child's entropy: it needs to compare whole splits, parent and children together. That comparison is the information gain, next.

7.8 Information Gain

7.8.1 From Entropy to Information Gain

The basic entropy of a single child is not used directly in scikit-learn. What is used is information gain, which is derived from entropy. The motivation: instead of looking at the entropy of one child node in isolation, look at the entropy of the whole subset — the parent together with all its children.

Suppose you split on attribute A and get children B and C. Do not just compute the entropy of one child. Compute the entropy of the parent, subtract the (weighted) entropy of all the children, and that difference is the gain. The spoken description: "information gain split is entropy of the parent minus entropy of the children, and it should be a positive value."

The idea: if you choose attribute A, the entropy of the dataset should come down drastically compared to the parent — that is the ideal case. So:

entropy of the parent should be high (it usually is, starting from the root),
entropy of the children should be as low as possible,
their difference — the information gain — should be maximized.

Maximizing the gain is how the tree stays small: with a minimum number of attributes you reach decision points, so the height of the tree is reduced. Choose the attribute with the highest information gain, i.e., the biggest drop from parent entropy to children entropy.

Intuition: gain is the knowledge you bought with the question. Before the split you are maximally unsure about a sample's class; after the split, samples fall into children where the class is (on average) much clearer. Information gain measures how much uncertainty that one question removed — how much the answer to "which child?" tells you about "which class?". A split that sends each class to its own pure child removes all uncertainty: gain is large. A split that shuffles classes around removes almost nothing: gain is near zero. The greedy builder asks, for every attribute, "which question buys me the most certainty?" — and picks the winner.

7.8.2 The Formula and the Weighting

$Gain (parent, A) = H (parent) - i = 1 \sum K \frac{N _{i}}{N} H (child_{i})$

where $H (\cdot)$ is entropy, $K$ is the number of children of the split (2 for a binary split, K for a multi-way split — the sum runs over all K children), $N_{i}$ is the number of samples going into child $i$ , and $N$ is the total number of samples at the parent. The fraction $N_{i} / N$ is a weight.

Every piece, named:

$H (parent)$ — the entropy of the node before the split. Since the tree starts at the root with all classes present, this is usually a relatively high value, and it is the same number for every candidate attribute at the same node.
$K$ — the number of children the split creates. A binary split has $K = 2$ ; a multi-way split has $K$ equal to the number of branches (3 for a car type with three values, 5 for the income buckets).
$N_{i}$ — the number of samples that fall into child $i$ after the split.
$N$ — the number of samples at the parent, before the split. Note that the children together hold all of them: $\sum_{i} N_{i} = N$ .
$\frac{N _{i}}{N} H (child_{i})$ — child $i$ 's entropy, weighted by the child's share of the parent's samples.

Why weight the children at all? Because children do not have equal numbers of samples. Suppose the parent had 10 samples; 7 went to one child and 3 to the other. If we are computing the entropy of the subset, the two children should not be counted equally — the first holds more of the data. So the weights are $7/10$ for the first child and $3/10$ for the second: more samples in a child, more weight in the sum.

Worked example 1 — the weighting, on the professor's numbers.

Parent: 10 samples. Split gives child 1 with 7 samples and child 2 with 3 samples.

$i = 1 \sum 2 \frac{N _{i}}{N} H (child_{i}) = \frac{7}{10} H (child_{1}) + \frac{3}{10} H (child_{2})$

The 7-sample child contributes more to the sum than the 3-sample child — its impurity matters more, because it holds more of the data. If both children had 5 samples, the weights would be 5/10 and 5/10, and the two children would count equally.

Sense-check: the weight is exactly the share of the parent's samples in that child. A child holding 70% of the data is 70% of the remaining-entropy bill.

Worked example 2 — full gain computation on a 20-sample node.

Parent: 20 samples, 10 of class C0 and 10 of class C1. Since both classes are equally likely:

$H (parent) = - \frac{10}{20} lo g_{2} (\frac{10}{20}) - \frac{10}{20} lo g_{2} (\frac{10}{20}) = - \frac{1}{2} (- 1) - \frac{1}{2} (- 1) = 1$

Candidate attribute A splits into child 1 (7 C0, 3 C1) and child 2 (3 C0, 7 C1). Each child has the same mix, so one entropy computation serves both:

$H (child) = - \frac{7}{10} lo g_{2} (\frac{7}{10}) - \frac{3}{10} lo g_{2} (\frac{3}{10}) \approx 0.8813$

The children hold 10 samples each, so the weights are $10/20$ and $10/20$ :

$Gain (A) = 1 - (\frac{10}{20} (0.8813) + \frac{10}{20} (0.8813)) = 1 - 0.8813 \approx 0.1187$

Candidate attribute B splits into child 1 (all 10 C0) and child 2 (all 10 C1). Both children are pure, so $H (child) = 0$ for each:

$Gain (B) = 1 - (\frac{10}{20} (0) + \frac{10}{20} (0)) = 1 - 0 = 1$

Choose B: its gain (1) far exceeds A's gain (0.1187). Sense-check: B's split is perfectly separating — after it, every sample is already classified, so the tree ends immediately at depth 1. A's split leaves both children 88% mixed, so the tree would need more splits below — exactly the "smallest tree" logic from Section 7.4, now driven by a number.

7.8.3 Student Questions and Answers

Q: What is $N_{i} / N$ in the information gain formula? What does it mean?

A: $N_{i} / N$ is the number of samples going into each child node divided by the total. Say the parent had 10 samples: 7 went one way, 3 the other. Both children should not be weighted equally, because one has more samples. The weight is $7/10$ for the bigger child and $3/10$ for the smaller one. We give more weight to the child that holds more samples.

Q: Can we use two attributes at one node — combine them in a dictionary-like condition?

A: No. Each node has exactly one attribute; we never combine two attributes at a single node. But note that the final tree as a whole is a combination of multiple attributes in a pattern — "refund AND/OR marital status AND/OR taxable income" — and that combined form is how trees will be written when we cover rule-based classification. The clear answer to the direct question is: at any single node, only one attribute.

Pitfalls for the gain formula:

Weighting but forgetting to sum all children. A split with three children contributes three weighted terms; leaving one child out overstates the gain and can crown the wrong attribute.
Comparing gains across different nodes. Gain is computed per node with that node's own $H (parent)$ as baseline; a gain at the root and a gain at a deep node are on different scales and are never compared — only sibling candidates at the same node compete.
Expecting gain to be huge for every split. A gain near zero just means the attribute barely separates the classes at this node — exactly the "should not choose such an attribute" situation from the entropy curve.

Recap: information gain = parent entropy minus the sample-weighted entropy of the children; maximize it to minimize tree height. The weight $N_{i} / N$ makes bigger children count more. Gain is the criterion behind ID3 and the default way scikit-learn-style trees pick attributes. The second famous criterion approaches the same goal with a different formula — the Gini index, next.

7.9 Gini Index

7.9.1 The Gini Formula

The second famous criterion is the Gini index (some say "Gini", some say "Ginny"). The basic idea is the same as entropy: the child nodes should be homogeneous. The Gini index of a node is:

$G = 1 - j \sum p_{j}^{2}$

where $p_{j}$ is the probability of class $j$ in the node — the number of samples of that class divided by the total number of samples in the node. Note this is not a conditional probability; it is the plain class probability in the node.

The extreme values: Gini is 0 when you reach a pure set (a homogeneous node — all samples in one class). Gini reaches its maximum of 1 when the node is completely heterogeneous (an impure set).

Intuition: Gini asks how often two random draws disagree. Pick two samples from the node at random, with replacement. The chance that the first draw is class $j$ is $p_{j}$ , and the chance the second draw is also class $j$ is again $p_{j}$ — so the chance they agree on class $j$ is $p_{j}^{2}$ , and the chance they agree on any class is $\sum_{j} p_{j}^{2}$ . The Gini index is 1 minus that agreement probability: it is the probability that two random draws come from different classes. In a pure node the draws always agree — Gini 0. In a perfectly mixed node the draws usually disagree — Gini near its maximum. That is why Gini is also called a measure of "disagreement" or "impurity."

One correction worth writing down once. The lecture describes the maximum as 1, which is the right picture for a node with very many classes; the strict formula is tighter: with $C$ classes the maximum is

$G_{m a x} = 1 - \frac{1}{C}$

because the most mixed node has all classes equally likely, $p_{j} = 1/ C$ , giving $\sum p_{j}^{2} = C \cdot (1/ C)^{2} = 1/ C$ . For the two-class case that is $1 - 1/2 = 0.5$ — which is exactly the value the comparison table in Section 7.10 reports at the 50/50 point. So for the binary case the practical statements are: Gini = 0 at pure nodes, Gini = 0.5 at the fully mixed node, and the value 1 is the limit as the number of classes grows without bound.

7.9.2 Worked Example: Three Attributes A, B, C

Same setup as entropy: attributes A, B, C each produce a child node; compute Gini for each and pick the best.

Compute the Gini index of one child per attribute.

Attribute A. Child has 0 samples of C1 and 6 of C2:

$p_{C 1} = \frac{0}{6} = 0, p_{C 2} = \frac{6}{6} = 1$

$G_{A} = 1 - p_{C 1}^{2} - p_{C 2}^{2} = 1 - 0^{2} - 1^{2} = 0$

Gini 0 = pure set: all elements belong to class C2, so this child is a decision point.

Attribute B. Child has 1 sample of C1 and 5 of C2:

$p_{C 1} = \frac{1}{6}, p_{C 2} = \frac{5}{6}$

$G_{B} = 1 - (\frac{1}{6})^{2} - (\frac{5}{6})^{2} = 1 - \frac{1}{36} - \frac{25}{36} = \frac{10}{36} \approx 0.28$

The lecture read the value on the slide as "0.25, 0.27"; the arithmetic from the stated counts (1 and 5 of 6 samples) gives exactly $10/36 \approx 0.278 \approx 0.28$ , which matches the value the reference text computes for the same counts, so 0.28 is the number to use.

Attribute C. Gini:

$G_{C} = 0.44$

The value corresponds to the same 4/2 class mix used in the entropy example: with $p_{C 1} = 4/6$ and $p_{C 2} = 2/6$ ,

$G_{C} = 1 - (\frac{4}{6})^{2} - (\frac{2}{6})^{2} = 1 - \frac{16}{36} - \frac{4}{36} = \frac{16}{36} \approx 0.444 \approx 0.44$

Choice. We want Gini of the child to be zero — the child homogeneous, a decision point. Attribute A wins with Gini 0.

Sense-check: the ranking is identical to entropy's — A (pure) beats B (0.28) beats C (0.44). Gini and entropy agree on which child is most homogeneous here; where they differ, the numbers — not the intuition — decide (Section 7.10 compares the two curves).

7.9.3 Gini Split: Weighted Children, No Parent

Just as plain entropy is not used directly, the Gini index is not used directly either. The version used in scikit-learn builds on it and is called Gini split. The idea: when splitting on an attribute, look at all the child nodes that come out of that attribute — but do not look at the parent's Gini.

This is the key difference from information gain: in information gain, the parent's entropy appears explicitly in the formula. In Gini split, the parent's Gini is ignored; only the children's Gini values matter.

$GiniSplit (A) = i = 1 \sum K \frac{N _{i}}{N} G (child_{i})$

The formula in the speaker's words: "calculate the Gini of each child node and add them up" — with each child's Gini multiplied by its weight, exactly the weighting used in information gain. $N_{i}$ is the number of samples in child $i$ , $N$ is the total number of samples at the parent, and $G (child_{i})$ is the Gini index of child $i$ .

How do we compare children from different levels? We do not compare across levels. If you split on B, only the children generated by B are considered; if you split on A, only A's children. For every attribute, compute the Gini split; whichever attribute gives the lowest value, choose that attribute.

Comparison — gain vs Gini split, side by side.

	Information gain (entropy)	Gini split
Parent's own measure	appears explicitly: $H (parent)$	ignored entirely
Children's measures	weighted sum $\sum \frac{N _{i}}{N} H (child_{i})$	weighted sum $\sum \frac{N _{i}}{N} G (child_{i})$
Direction of choice	maximize the gain	minimize the split value
Same node baseline	$H (parent)$ constant for all candidates	no parent term at all

Both end up preferring the attribute whose children are most homogeneous. The structural difference to remember: gain subtracts the weighted children from the parent's entropy; Gini split is just the weighted children. When to pick which: both are valid and usually agree; the lecture returns to their different curves in Section 7.10, and the homework on choosing a criterion compares them there.

7.9.4 Worked Example: Gini Split with N1 and N2

A parent node holds 12 samples. Split on attribute B, producing two children: node N1 with 5 samples of C1 and 2 of C2 (7 samples total), and node N2 with 5 samples.

Compute the Gini split for attribute B.

Gini of N1:

$G (N 1) = 1 - (\frac{5}{7})^{2} - (\frac{2}{7})^{2} = 1 - \frac{25}{49} - \frac{4}{49} = \frac{20}{49} \approx 0.41$

Gini of N2 is computed the same way from its own class counts. The lecture did not state N2's exact composition; the method is identical — take each class count, divide by N2's 5 samples, square, and subtract from 1. As an illustration with a typical mix (3 samples of one class, 2 of the other), $G (N 2) = 1 - (3/5)^{2} - (2/5)^{2} = 1 - 9/25 - 4/25 = 12/25 = 0.48$ .

Now combine the children with weights. N1 has 7 of the parent's 12 samples, N2 has 5 of 12:

$GiniSplit (B) = \frac{7}{12} G (N 1) + \frac{5}{12} G (N 2)$

With the values above:

$GiniSplit (B) = \frac{7}{12} \cdot \frac{20}{49} + \frac{5}{12} \cdot \frac{12}{25} \approx 0.238 + 0.200 = 0.438$

The weights come from sample counts: 7 is the number of samples in N1, 12 the total number of samples in the parent, and similarly 5/12 for N2. Child N1 gets more weight because it holds more samples. Repeat this computation for every candidate attribute (A, B, C, D, ...), compute the Gini split for each, and pick the attribute with the lowest Gini split.

Sense-check: the parent's own Gini never entered the calculation — exactly the no-parent property of Gini split. And N1's heavier weight pulled the split value toward its own 0.41, as a 7/12 share should.

Pitfalls for Gini:

Mixing the two criteria's directions. Information gain is maximized; Gini split is minimized. Forgetting which way each points is a classic exam slip: for gain, bigger is better; for Gini split, smaller is better.
Dragging the parent's Gini into Gini split. The parent term belongs only to information gain. Adding $G (parent)$ (or subtracting it) changes the formula's meaning and breaks comparability with the lecture's version.
Comparing children across different attributes or levels. Only the children produced by one candidate attribute are combined for that attribute's split value; children from different splits or different depths are never mixed.
Misremembering the binary maximum as 1. For two classes the fully mixed node has Gini 0.5, as the Section 7.10 chart shows; 1 is the many-class limit.

Recap: the Gini index $G = 1 - \sum p_{j}^{2}$ is 0 for a pure node and grows with mixing; Gini split — the scikit-learn default — is the weighted sum of children's Gini values with the parent excluded, minimized across candidate attributes. The third and simplest criterion completes the set: misclassification error, whose formula is just 1 minus the largest class probability.

7.10 Misclassification Error

7.10.1 The Formula

The third criterion is misclassification error. The formula is simple — it is the loss you would incur if you predicted the majority class at the node:

$E = 1 - i max p_{i}$

where $p_{i}$ is the probability of class $i$ in the node and the max is taken over all classes. If a node is pure, the max probability is 1 and the error is 0. In the worked example: a child with $p_{C 1} = 0$ and $p_{C 2} = 1$ has max 1, so error = 0. At a 50/50 node, max = 0.5, so error = 0.5.

Compute the error on the same child nodes as entropy and Gini.

Child A — 0 samples of C1, 6 of C2:

$p_{C 1} = 0, p_{C 2} = 1, E_{A} = 1 - max (0, 1) = 1 - 1 = 0$

Pure node, no error under the majority guess — the same "decision point" verdict as $H_{A} = 0$ and $G_{A} = 0$ .

Child B — 1 sample of C1, 5 of C2:

$E_{B} = 1 - max (\frac{1}{6}, \frac{5}{6}) = 1 - \frac{5}{6} = \frac{1}{6} \approx 0.17$

The majority guess (C2) is wrong on 1 of the 6 samples — a modest error, matching a mostly-mixed-but-leaning node.

Child C — 4 samples of C1, 2 of C2:

$E_{C} = 1 - max (\frac{4}{6}, \frac{2}{6}) = 1 - \frac{4}{6} = \frac{1}{3} \approx 0.33$

50/50 node — 3 samples of each class:

$E_{50/50} = 1 - max (0.5, 0.5) = 1 - 0.5 = 0.5$

Sense-check: the error is simply the fraction of samples that the node's own majority guess would misclassify — 0 for a pure node, 1/6 for a 1-vs-5 mix, 1/3 for 4-vs-2, and 0.5 when no majority exists. Notice it never counts the majority class at all: the max removes it, which is exactly why the curve is piecewise linear rather than curved like Gini and entropy.

Why this formula is the "obvious" criterion. If you had to commit to one class for every sample in the node, the rational pick is the class with the most samples — the majority class — and the fraction of samples you would get wrong is exactly $1 - max_{i} p_{i}$ . So the misclassification error is the error rate of the node's best single guess. It is the simplest of the three criteria, needs no log and no square, and yet it behaves differently from entropy and Gini when used to rank attributes — which is the surprise of this section.

7.10.2 Comparing All Three Criteria

For binary classification, plot all three criteria against the probability of the positive class $p_{+}$ :

$p_{+}$	Entropy	Gini	Misclassification error
0 (all negative)	0	0	0
1 (all positive)	0	0	0
0.5 (perfectly mixed)	1	0.5	0.5

The two ideal cases are the endpoints: entropy, Gini, and misclassification error are all zero when all samples belong to one class. The worst cases are in the middle: at $p_{+} = 0.5$ , misclassification error is 0.5, entropy is 1, and Gini is 0.5.

The three curves differ in shape. Misclassification error is piecewise linear — a "triangle": it rises linearly from 0 at $p_{+} = 0$ to 0.5 at $p_{+} = 0.5$ and falls linearly back to 0 at $p_{+} = 1$ . Gini and entropy are smooth curves.

Visual intuition: the chart to redraw from memory. Horizontal axis: $p_{+}$ from 0 to 1. Vertical axis: impurity from 0 to 1. Three curves share the two endpoints (0, 0) and (1, 0) and the middle point (0.5, 1) for entropy. The error curve is a triangle — two straight line segments meeting at the peak. The Gini curve is a smooth arch peaking at 0.5. The entropy curve is a smooth arch peaking at 1, lying above the other two everywhere in between. Landmarks: the shared endpoints (pure nodes, all criteria agree it is a decision point) and the shared peak position (the 50/50 point, where all three say "most impure"). Takeaway: the three agree about which node is purest or most mixed; they differ in how sharply they punish intermediate mixes — and those differences change which attribute wins, which is the point of the homework below.

Q: Why is the misclassification error curve not a parabola?

A: Look at the formula — it uses the max function. A max gives you straight line segments, so the plot is a triangle. Gini has the squared terms, and entropy has the log, and those are what make their curves bend.

Depending on the circumstances you can choose any of the three criteria. Deciding when to prefer entropy, when Gini, and when misclassification error by studying the comparison chart is assigned as homework: look at where your node sits on the chart and reason about which criterion behaves the way you want there.

Exam note: the homework question — "when should you use entropy, when Gini, when misclassification error?" — is a natural exam question, and the chart above is the tool for it. The reasoning template: all three agree at pure nodes (all 0) and at the fully mixed point; they differ in the middle. Entropy punishes mid-range mixes hardest (it rises to 1), Gini to 0.5, error only linearly to 0.5. So if your split's children sit in the mid-range, the three criteria can rank attributes differently — which one you choose is a modeling decision, and the reference texts note that in practice entropy and Gini usually choose the same attribute while misclassification error can disagree near the middle of the chart.

Pitfalls:

Forgetting the max makes it piecewise linear. The error curve is not smooth: at $p_{+} = 0.5$ the majority class switches, which is exactly where the slope changes sign — that kink is the signature of the max function.
Assuming all three criteria always agree. They agree on the extremes but can rank mid-range splits differently; a criterion comparison, not a habit, should decide.
Using error on a multi-class node without naming the max. The formula works for any number of classes — $E = 1 - max_{i} p_{i}$ — just make sure you know which class holds the maximum at the node you are evaluating.

Recap: misclassification error $E = 1 - max_{i} p_{i}$ is the error rate of the majority-class guess: 0 at pure nodes, 0.5 at the 50/50 point, and piecewise linear because of the max. With entropy and Gini it completes the trio of attribute-selection criteria available in scikit-learn. Now we have the full toolkit to build a tree — the next section assembles it into the actual algorithm, ID3.

7.11 The ID3 Algorithm

7.11.1 Top-Down Construction

ID3 — the algorithm used to build decision trees in scikit-learn — is a top-down approach: first the root, then the non-leaf nodes, and finally the leaf nodes. Its steps:

Take the best decision attribute. A criterion (like information gain) identifies which attribute is best. In the lecture's words: "the criteria says that is the best attribute."
Put it at the root node. The chosen attribute becomes the first decision node — the root — with a condition around it.
Sort the examples by the value of that attribute. Some samples go to one child, some to another; the children should be more homogeneous (less impurity) so you can reach a decision point.
Check the children. If a child is perfectly homogeneous, it becomes a leaf — stop. If a child is not homogeneous, go back to step 1 and repeat: choose the best attribute for that child, split, and continue recursively until all leaf nodes are homogeneous.

In the lecture's phrasing: "you choose the most important attribute, split based on it, then the second most important attribute, split on it, and so on, iterating until all the leaf nodes are homogeneous."

Purpose, inputs, and outputs of ID3, spelled out:

Purpose: build the smallest decision tree possible for a labeled training set, by making a greedy local choice at every node (the bias of Section 7.4, executed mechanically).
Inputs: the training dataset (samples with attributes and class labels), the set of candidate attributes, and a splitting criterion (typically information gain for ID3; the lecture's examples also use Gini).
Outputs: a decision tree — an ordered sequence of attribute tests ending in class-labeled leaves.

The structure of the algorithm is a recursion: choose the best attribute for the current node, split, and call the same procedure on each child that is not yet homogeneous. Top-down means the root is decided before anything deeper — there is no later revision of an earlier choice, which is the no-backtracking property of Section 7.4 built into the algorithm itself.

Scope — what ID3 assumes. ID3 builds trees greedily on the training data alone (test data never participates). Its criterion rankings are local to each node; it assumes the training sample is representative enough that locally good choices accumulate into a good tree. When the training data is small or noisy, the greedy recursion can keep splitting to perfect purity — fitting noise — which is why real systems stop early or prune (the stopping criteria below are the lecture's answer to this).

7.11.2 Worked Example: Choosing Between Attributes with the Gain Formula

Before splitting, a node contains $N_{0}$ samples of class C0 and $N_{1}$ samples of class C1, with an entropy of $M_{0}$ .

We may split on attribute A or attribute B. If we split on A, we get two children whose weighted entropies are $M_{1}$ and $M_{2}$ . If we split on B, we get children with weighted entropies $M_{3}$ and $M_{4}$ . The gain of each split is the parent's information minus the children's information:

$Gain (A) = M_{0} - i \in children of A \sum \frac{N _{i}}{N} M_{i}, Gain (B) = M_{0} - i \in children of B \sum \frac{N _{i}}{N} M_{i}$

Compare the two gains and split on the attribute with the larger gain. This is the local criterion that drives the whole tree: at every node, compute the information gain of each candidate attribute and choose the one with the highest gain; if a child is a decision point, stop there; otherwise recurse.

Naming the slide's symbols. The lecture drew this example from a slide with a generic parent (N0 samples of class C0, N1 of class C1, entropy M0) and two candidate splits with child entropies M1/M2 and M3/M4; the exact numbers on the slide were not read aloud, but the structure is the standard gain formula:

$N_{0}, N_{1}$ — the class counts at the parent (total $N = N_{0} + N_{1}$ ).
$M_{0}$ — the parent's entropy, the baseline shared by both candidates: $M_{0} = - \frac{N _{0}}{N} lo g_{2} \frac{N _{0}}{N} - \frac{N _{1}}{N} lo g_{2} \frac{N _{1}}{N}$ .
$M_{1}, M_{2}$ — the weighted child terms for split A, i.e. $M_{1} = \frac{N _{A 1}}{N} H (child_{A 1})$ and $M_{2} = \frac{N _{A 2}}{N} H (child_{A 2})$ .
$M_{3}, M_{4}$ — the same weighted child terms for split B.
The comparison is then simply $M_{0} - (M_{1} + M_{2})$ versus $M_{0} - (M_{3} + M_{4})$ ; the parent term $M_{0}$ cancels on both sides, so picking the larger gain is equivalent to picking the smaller weighted-children sum.

This matches the formula of Section 7.8 exactly — the slide's $M$ -notation is just the same computation with names.

Work the gain choice with real numbers.

Parent: 10 samples of C0 and 10 of C1, so $N_{0} = N_{1} = 10$ , $N = 20$ , and

$M_{0} = - \frac{10}{20} lo g_{2} \frac{10}{20} - \frac{10}{20} lo g_{2} \frac{10}{20} = 1$

Split A: child A1 = (8 C0, 2 C1), child A2 = (2 C0, 8 C1). Each child has entropy

$H = - \frac{8}{10} lo g_{2} \frac{8}{10} - \frac{2}{10} lo g_{2} \frac{2}{10} \approx 0.722$

and each child holds half the samples, so the weighted terms are

$M_{1} = \frac{10}{20} \cdot 0.722 = 0.361, M_{2} = \frac{10}{20} \cdot 0.722 = 0.361$

$Gain (A) = M_{0} - (M_{1} + M_{2}) = 1 - 0.722 = 0.278$

Split B: child B1 = (10 C0, 0 C1), child B2 = (0 C0, 10 C1). Both children are pure, so

$M_{3} = \frac{10}{20} \cdot 0 = 0, M_{4} = \frac{10}{20} \cdot 0 = 0$

$Gain (B) = M_{0} - (M_{3} + M_{4}) = 1 - 0 = 1$

Choose B — its gain of 1 beats A's 0.278, and the tree terminates immediately since both children are leaves.

Sense-check: B's split is perfectly separating (gain equal to the full parent entropy), A's leaves 72% of the uncertainty in place. The numbers reproduce the Section 7.8 example in the slide's $M$ -notation — same formula, same winner.

7.11.3 Stopping Criteria

The recursion stops when:

you reach a pure subset — the children are homogeneous nodes, meaning all samples in the node belong to one class;
no more attributes remain; or
you terminate earlier based on domain knowledge.

Domain-knowledge-based early stopping is allowed: you do not always have to split until purity.

Why the third stop exists. Pure-set stopping can overfit: a tiny training set can be carved into perfect but meaningless leaves (the student-ID trap of Section 7.6). The third criterion lets the builder stop while a node is still slightly mixed, accepting a small training error to keep the tree simple — a domain call that trades a little accuracy for much more reliability on new data. In practice this shows up as limits like "maximum depth" or "minimum samples per leaf," which Section 7.12 lists among the scikit-learn parameters.

7.11.4 A Recursive Gini Example from a Slide

A slide-based illustration of recursion: at a node, split on the third attribute $X_{3}$ with condition $X_{3} \leq 0.8$ . The left branch reaches a homogeneous node — Gini 0, all samples of one class — so it becomes a leaf. The right branch still has Gini 0.5, so it is split again, this time on the second attribute $X_{2}$ , and the process recurses until every branch reaches a decision point.

This is also how the scikit-learn iris demo behaves: the tree picks petal length as the most important criterion at the root, then petal width, arranging attributes in an order that minimizes tree size.

Trace the recursion on the slide's numbers.

Step 1 — at the root node, the chosen test is $X_{3} \leq 0.8$ .
Left branch: every sample satisfies $X_{3} \leq 0.8$ and all belong to one class → Gini = 0 → leaf, stop.
Right branch: samples with $X_{3} > 0.8$ still mix classes → Gini = 0.5 → not a leaf, continue.
Step 2 — on the right branch, the next-best test is on $X_{2}$ . The branch splits into two children.
Each child is evaluated the same way: Gini 0 → leaf; Gini > 0 → split again on the best remaining attribute.
The recursion ends when every open branch has reached Gini 0.

The lecture's exact Gini values per branch were read from the diagram and partly garbled in the audio; the reliable structure is the one traced above — Gini 0 makes a leaf, Gini 0.5 means "keep splitting," and each new node re-chooses its attribute. The threshold $X_{3} \leq 0.8$ is the lecture's stated value and is kept throughout.

Sense-check: each recursion step is the same two-decision loop — is this child homogeneous? If yes, leaf; if no, split again. That loop, driven by the gain or Gini criterion, is the whole ID3 algorithm.

Recap: ID3 builds trees top-down — choose the best attribute by the criterion, split, recurse on non-homogeneous children — and stops at pure subsets, exhausted attributes, or a domain-knowledge early stop. The gain example showed the parent-entropy baseline canceling so that only the weighted children matter, and the recursion slide showed Gini driving the same loop. Next: the practical side — the scikit-learn API, why trees are popular, and the ensembles built on them.

7.12 Decision Trees in Practice

7.12.1 The scikit-learn API

The decision tree API exposed in scikit-learn has a criterion parameter. Its options are Gini (the default), entropy, and log loss. There is also a splitter option: best. If you set the criterion to entropy, the tree is built using entropy and information gain; the default is Gini.

Other parameters of interest: the depth of the tree (how many levels), the minimum number of samples required at each split, the minimum number of samples allowed at a leaf node, and the maximum number of features. In the scikit-learn API these are the parameters max_depth, min_samples_split, min_samples_leaf, and max_features — the lecture named them verbally as "what would be the depth of the tree, how many samples should be there at each split, how many samples should be at the leaf node, maximum number of features," which is exactly what these four parameters control:

The scikit-learn knobs, named and explained:

criterion — the impurity measure: gini (default), entropy, or log_loss. This is the choice of Section 7.7–7.10 in action: gini and entropy produce the curves of Section 7.10; log loss is the same family, derived from the log of the class probabilities (one mention in the lecture of "normal loss" was a slip for log loss — the API's third criterion is log loss).
splitter — how candidate splits are searched: best picks the best split among all candidates (the lecture's best), random picks a random best split among the best ones.
max_depth — how many levels the tree may have. This is the practical version of the domain-knowledge stopping criterion from Section 7.11.3.
min_samples_split — the minimum number of samples a node must hold before it is allowed to split again. A node with fewer samples becomes a leaf regardless of purity.
min_samples_leaf — the minimum number of samples a leaf must hold. This directly enforces the "confidence comes from sample counts" principle of Section 7.6: no leaf may be a one-sample leaf.
max_features — the maximum number of attributes considered when searching for the best split at each node. Limiting it speeds up large trees and is the mechanism behind random-forest-style randomization.

These knobs map one-to-one onto the lecture's stopping and split vocabulary: depth, split size, leaf size, and feature count are the dials that keep a greedy tree small and reliable.

The API also exposes feature importance: which feature is the most important. Feature importance is calculated from the same criterion you chose — Gini, entropy, or log loss. Each time a node splits on a feature, the criterion's improvement (the drop in impurity) is credited to that feature, and the credits accumulate over the whole tree, normalized so they sum to 1. The feature with the largest share is the most important one.

The classic demo uses the iris dataset: the tree picks petal length as the most important feature at the root, then petal width (see the recursive example in the ID3 section).

Reading feature importance on the iris demo. The iris dataset describes three flower species (setosa, versicolor, virginica) with four features: sepal length, sepal width, petal length, petal width. The demo tree puts petal length at the root and petal width next, and the importance ranking follows the same order — petal length receives the largest share of the impurity drop, petal width the second largest, and sepal features close to zero. Sense-check: this matches the data — petal length alone separates setosa from the other two species, so the greedy criterion promotes it to the root, exactly as the lecture described.

7.12.2 Why Decision Trees Are So Popular

Decision trees are famous because:

they are relatively inexpensive to construct;
they are extremely fast at making decisions;
they are highly interpretable;
their accuracy is pretty high.

The interpretability point matters in practice: a business user can read the tree and see exactly how decisions are made, without a statistician translating the model.

Recap of the four selling points: cheap to build (greedy, one pass of local choices), fast to run (a prediction is a root-to-leaf walk of a handful of comparisons), interpretable (the flowchart is the explanation), and accurate enough to be competitive. No single one of these is unique to trees, but the combination is — which is why they appear both as standalone models and as the building blocks of much stronger ensembles.

7.12.3 Ensemble Methods Built on Trees

Most ensemble algorithms used today are based on decision trees. Ensemble algorithms combine multiple smaller models to produce a more powerful one — and the two most famous examples, random forest and AdaBoost, are essentially built on decision trees. This is a major reason decision trees are hugely popular and well accepted in the data mining, machine learning, and data science communities: they are the building block of the ensemble methods that dominate practical use.

Intuition: many trees, one vote. A single tree can be wrong — its greedy choices might have locked in a suboptimal root (Section 7.4). An ensemble attacks that weakness with numbers: random forest grows many trees, each on a different random sample of the data and a different random sample of the attributes, and lets them vote; AdaBoost grows trees in sequence, each one focusing on the samples the previous trees got wrong. In both cases the individual trees may be small and imperfect, but the combined model is far more accurate and stable than any one tree. The two techniques are why "decision tree" in practice often means "random forest or boosting" — the single tree you learn here is the unit these models are built from.

7.12.4 Resources and Practice

The lecture points to textbooks covering this material, and notes that a set of numerical problems will be posted in the tutorial section — solving them is recommended practice for the exam. The original decision tree research paper is also available for reading; it explains the minute details of why a tree is built the way it is and what the criteria are.

Q: Can we have a high-level discussion of previous year papers in the next class?

A: This course was not taught last year, so previous year question papers may not be relevant — the question paper will be built from what is taught this year, with my own strategy rather than the old papers. Still, the discussion is possible if you want it. If you study what is taught in class thoroughly, practice it thoroughly, listen to it thoroughly, and do the numericals, it will be enough.

Recap: in practice, decision trees mean scikit-learn — a criterion choice (Gini default, entropy, or log loss), knobs for depth and sample counts, and feature importance from the criterion's impurity drops. Trees are popular because they are cheap, fast, interpretable, and accurate, and they matter most as the engine of random forests and AdaBoost. The numerical problems posted in the tutorial section are the recommended exam practice, and the next class moves on to K-nearest neighbors and rule-based classification.

Exam Guidance Summary

Practice numericals. A set of decision tree numericals will be posted in the tutorial section; solve them before the exam so you are comfortable with the computations. Working through them by hand builds the same skill the exam requires: computing entropy, information gain, and the Gini index from class counts, applying the sample weights, and choosing the winning attribute.
Know all three criteria cold. Entropy (and information gain), Gini index (and Gini split), and misclassification error are the three attribute-selection criteria. Expect to compute them by hand: probabilities per class, the formula, the weighted children sum, and the final choice of attribute. Remember the direction of each rule: information gain is maximized, Gini split is minimized.
Homework to think about: when should you use entropy, when Gini, and when misclassification error? The comparison chart (entropy/Gini/error vs probability of positive class, all 0 at pure nodes, entropy 1 / Gini 0.5 / error 0.5 at the 50/50 point) is the tool for this — this homework topic is a natural exam question. Be ready to explain the curve shapes: the error curve is piecewise linear because of the max function, while Gini's squares and entropy's log make smooth curves.
Question paper basis. The exam is based on what is taught in this course, not on previous year papers — the course was not taught last year, so previous year question papers may not be relevant. Studying thoroughly, practicing the numericals, and working through the material is stated to be enough.
Know the concepts, not just formulas. Be ready to explain why the tree wants homogeneous children, why confidence depends on sample counts at the leaf (the student-ID trap), why the greedy strategy has no backtracking, why one attribute per node is the rule (the AND/OR combination form returns in rule-based classification), and the stopping criteria: pure subsets, no attributes left, or domain-knowledge early termination.
Know the algorithm-family pairings. Hunt's algorithm is the general recursive recipe; ID3 uses information gain with multi-way splits; CART uses the Gini index with binary splits; scikit-learn's default criterion is Gini, with entropy and log loss as options.
Next class covers K-nearest neighbors and rule-based classification, with more tutorials posted for exam practice.

Key Industry Applications

Laptop / e-commerce filtering — the motivating example: narrowing 500 Amazon search results to one laptop using sequential filters (processor, RAM, disk space) is literally human decision-tree thinking, and is how product filters work on shopping sites. The question order is the tree; the final list is the leaf.
Fraud / cheat detection — the classic decision tree dataset used in class: refund, marital status, and taxable income attributes predicting a cheat (fraud) outcome; this is the canonical bank/insurance fraud-detection scenario in the data mining literature. Its value in practice is twofold: accurate screening, and a readable path that explains why a claim was flagged, which regulators and customers expect.
scikit-learn — the standard open-source Python library implements decision trees with Gini (default), entropy, and log loss criteria, a best splitter, depth/sample/feature constraints (max_depth, min_samples_split, min_samples_leaf, max_features), and feature importance derived from the chosen criterion. The knobs map directly to the lecture's stopping rules.
Iris dataset demo — the well-known scikit-learn example where the tree chooses petal length first and petal width second, showing how feature order is decided to minimize tree size and how feature importance ranks attributes.
Random forests and AdaBoost — the two most widely used ensemble algorithms are built on decision trees; ensembles combine many smaller models into one more powerful model, which is why decision trees matter far beyond the single-tree case. A single tree's greedy weakness is corrected by aggregating many trees (random forest) or by focusing each new tree on the samples the previous ones got wrong (AdaBoost).

DM Lecture 7 notes · Decision Trees

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

1What a Decision Tree Is

The root-non-leaf-leaf anatomy of a tree, the flowchart view, interpretability, and the laptop-shopping motivation

2Partitioning the Space into Rectangles

Divide-and-conquer splitting of the input space into axis-aligned rectangles, with a worked four-class partition and prediction

3Decision Trees for Classification: Process and Algorithms

The training and testing phases, the cheat-detection example, and the Hunt/ID3/CART algorithm family

4Many Possible Trees, One Bias

Why one dataset supports many trees, the smallest-tree bias, and the greedy strategy with no backtracking

5Types of Splits

Multi-way and binary splits for nominal, ordinal, and continuous attributes, with the order-preservation constraint and student Q&A

6Choosing the Attribute to Split: Homogeneity and Confidence

Homogeneous children, the own-car/car-type/student-ID worked example, and confidence from leaf sample counts

7Entropy

Entropy as chaos in bits, the formula, a three-attribute worked example, and the entropy curve for binary classification

8Information Gain

Parent entropy minus weighted children entropy, the N_i/N weighting, and full worked gain computations

9Gini Index

The Gini formula, the correction for the maximum, Gini split with the parent excluded, and worked examples

10Misclassification Error

The 1 - max p_i formula and the comparison chart of all three criteria against p_+

11The ID3 Algorithm

Top-down greedy construction, the M-notation gain example, stopping criteria, and a recursive Gini trace

12Decision Trees in Practice

The scikit-learn API, feature importance, why trees are popular, and random forests and AdaBoost

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

What a Decision Tree Is

Must-know: A decision tree = flowchart with root node (first question), non-leaf nodes (attribute tests), leaf nodes (class labels); every prediction has a traceable root-to-leaf path, which is the source of its interpretability.

⚠️ Top pitfall: Treating a tree's path as proof of correctness: the path shows which tests were applied, not that the prediction is right; a missing attribute value can break the path.

Self-check: In the laptop analogy, what decides which property becomes the root question? (The shopper's most important property — the tree encodes whose priorities were used.)

Connects to: Partitioning the Space into Rectangles; Many Possible Trees, One Bias; Decision Trees in Practice

Partitioning the Space into Rectangles

Must-know: The tree = a partition of the vector space into axis-aligned rectangles via divide and conquer; each cut is one attribute test, each final rectangle is one leaf holding one class.

⚠️ Top pitfall: Assuming a tree can cut diagonally or separate overlapping classes: every boundary is axis-aligned ('X > t'), so diagonal or overlapping class structures need many cuts or cannot be separated at all.

Self-check: In the four-class example, which rectangle does a sample with X = 0.6, Y = 0.8 land in, and what is its class? (Upper right, Y > 0.5 branch, class B.)

Connects to: What a Decision Tree Is; Entropy

Decision Trees for Classification: Process and Algorithms

Must-know: Two phases: training (build the tree from labeled data) and testing (pass samples through the finished tree); a sample only answers the questions on its own path. Hunt's algorithm is the general recursive recipe; ID3 uses information gain with multi-way splits, CART uses Gini with binary splits.

⚠️ Top pitfall: Treating 'the decision tree algorithm' as one method: Hunt, ID3, and CART differ in impurity measure and split arity, and the algorithm-criterion pairing is examinable.

Self-check: In the cheat-detection trace, why was taxable income never tested? (The path reached a leaf before that attribute was needed; samples only answer the questions on their own path.)

Connects to: What a Decision Tree Is; Partitioning the Space into Rectangles; Information Gain; Gini Index

Many Possible Trees, One Bias

Must-know: The tree bias is 'smallest tree wins' (Occam's razor: prefer the simpler model); construction is greedy — locally best attribute at each node, no backtracking, hope for global optimality with no guarantee.

⚠️ Top pitfall: Confusing locally best with globally best: the greedy root choice is never re-evaluated, so an early suboptimal choice permanently enlarges the final tree.

Self-check: If the greedy root choice later turns out to be suboptimal, what can the algorithm do? (Nothing — decision tree construction has no backtracking.)

Connects to: What a Decision Tree Is; Choosing the Attribute to Split: Homogeneity and Confidence; Entropy

Types of Splits

Must-know: Split arity depends on attribute type: nominal -> multi-way or binary with any grouping; ordinal -> multi-way or binary but order must be preserved (never {small, large} vs {medium}); continuous -> buckets (discretization) or a threshold split.

⚠️ Top pitfall: Grouping ordinal values so the order breaks (e.g. small and large together without medium): legal for nominal, illegal for ordinal; continuous attributes cannot be split multi-way without first discretizing.

Self-check: Why can't a continuous attribute use one branch per value? (It has infinitely many values, so a threshold or discretization is required first.)

Connects to: Partitioning the Space into Rectangles; Entropy

Choosing the Attribute to Split: Homogeneity and Confidence

Must-know: Choose the attribute whose children are most homogeneous (fastest path to decision points) but keep sample counts: confidence at a leaf = fraction of samples of the predicted class at that leaf; one-sample leaves are pure but worthless (student-ID trap).

$confidence at leaf = \frac{# samples of predicted class at leaf}{# samples at leaf}$

⚠️ Top pitfall: Chasing purity alone: a student-ID split makes every child homogeneous with one sample each, but a leaf's prediction needs many samples behind it; the tree is built on training data only.

Self-check: Why does the student-ID split lose despite every child being homogeneous? (Each leaf holds one sample, so the confidence — the sample count behind the prediction — is nearly zero.)

Connects to: Many Possible Trees, One Bias; Entropy

Entropy

Must-know: H = -sum_i p_i log2(p_i), with 0*log2(0) = 0; pure node H = 0, binary 50/50 node H = 1 (max, worst case); choose the attribute whose children have the least entropy; maximum for C classes is log2 C.

$H = - i = 1 \sum C p_{i} lo g_{2} p_{i}$

⚠️ Top pitfall: Misapplying the maximum: entropy 1 is the max only for the two-class case; with C classes the max is log2 C. Also forgetting the 0*log2(0) = 0 convention for absent classes.

Self-check: A child node holds 1 sample of C1 and 5 of C2. Its entropy is? (-(1/6)log2(1/6) - (5/6)log2(5/6) ≈ 0.65 bits.)

Connects to: Choosing the Attribute to Split: Homogeneity and Confidence; Information Gain

Information Gain

Must-know: Gain(parent, A) = H(parent) - sum_{i=1..K} (N_i/N) H(child_i); children weighted by sample share so bigger children count more; pick the attribute with the highest gain; the parent entropy is the same baseline for all candidates at a node.

$Gain (parent, A) = H (parent) - i = 1 \sum K \frac{N _{i}}{N} H (child_{i})$

⚠️ Top pitfall: Forgetting to weight children (counting a 3-sample child equally with a 7-sample child) or comparing gains across different nodes instead of only among sibling candidates.

Self-check: Parent (10 C0, 10 C1) splits into two children of 10 each with entropy 0.8813. Gain = ? (1 - (10/20)(0.8813) - (10/20)(0.8813) ≈ 0.1187.)

Connects to: Entropy; The ID3 Algorithm

Gini Index

Must-know: G = 1 - sum_j p_j^2, 0 at a pure node, max 1 - 1/C (0.5 for two classes); Gini split = sum (N_i/N) G(child_i) with the parent's Gini excluded — choose the attribute with the lowest Gini split; never compare children across levels.

$G = 1 - j \sum p_{j}^{2}, GiniSplit (A) = i = 1 \sum K \frac{N _{i}}{N} G (child_{i})$

⚠️ Top pitfall: Inverting the optimization direction (gain is maximized, Gini split minimized), or including the parent's Gini in Gini split when the parent term belongs only to information gain.

Self-check: Child N1 has 5 samples of C1 and 2 of C2. G(N1) = ? (1 - (5/7)^2 - (2/7)^2 = 20/49 ~ 0.41.)

Connects to: Entropy; Information Gain; Misclassification Error

Misclassification Error

Must-know: E = 1 - max_i p_i: error rate of predicting the majority class; 0 at pure nodes, 0.5 at 50/50; the curve is piecewise linear (a triangle) because the max function makes straight segments, unlike Gini's squares and entropy's log which curve.

$E = 1 - i max p_{i}$

⚠️ Top pitfall: Expecting the error curve to be smooth (a parabola): the max function switches majority class at p+ = 0.5, creating a kink and straight-line segments.

Self-check: At p+ = 0.5, what are entropy, Gini, and misclassification error? (1, 0.5, 0.5.)

Connects to: Entropy; Gini Index

The ID3 Algorithm

Must-know: ID3: top-down greedy recursion — best attribute at the root by the criterion, split, recurse until leaves are homogeneous; stop at pure subsets, no attributes left, or early domain-knowledge termination; gain comparison = parent entropy minus weighted children, and M0 cancels when comparing splits.

$Gain (A) = M_{0} - i \in children of A \sum \frac{N _{i}}{N} M_{i}$

⚠️ Top pitfall: Splitting to perfect purity always: pure-set stopping overfits (student-ID trap); domain-knowledge early stopping is explicitly allowed, and Gini > 0 on a branch means it must be split again.

Self-check: In the recursion slide, when does a branch become a leaf? (When its Gini is 0 — all samples of one class; Gini 0.5 means split again.)

Connects to: Many Possible Trees, One Bias; Information Gain; Gini Index

Decision Trees in Practice

Must-know: The scikit-learn tree API: criterion = gini (default) | entropy | log_loss; splitter = best; knobs max_depth, min_samples_split, min_samples_leaf, max_features; feature importance sums to 1 and comes from the chosen criterion's impurity drops (iris: petal length first, petal width second).

⚠️ Top pitfall: Forgetting the tree's knobs map to stopping rules: min_samples_leaf enforces the sample-count confidence principle, max_depth implements the domain-knowledge early stop; 'normal loss' is a slip for log loss.

Self-check: Why is petal length at the root of the iris demo tree? (It produces the largest impurity drop — highest feature importance — because it separates setosa cleanly.)

Connects to: Many Possible Trees, One Bias; Gini Index; The ID3 Algorithm

Exam Guidance Summary

Must-know: Hand-compute all three criteria (entropy + information gain, Gini index + Gini split, misclassification error) with weights; maximize gain, minimize Gini split; the comparison chart (0 at pure, entropy 1 / Gini 0.5 / error 0.5 at 50/50) decides which criterion to prefer; the exam follows this year's material, not old papers.

⚠️ Top pitfall: Learning formulas without concepts: be ready to explain homogeneous children, confidence from leaf sample counts, greedy no-backtracking, and why the error curve is piecewise linear (max function).

Self-check: Which direction does each criterion optimize? (Information gain: maximize; Gini split: minimize; misclassification error: minimize.)

Connects to: Entropy; Information Gain; Gini Index; Misclassification Error; The ID3 Algorithm

Key Industry Applications

Must-know: Trees power product filters, fraud screening with readable explanations, and — most importantly — the ensembles (random forest, AdaBoost) that dominate practical data mining.

⚠️ Top pitfall: Treating decision trees as a niche model: they are the unit from which the most widely used ensemble methods are built.

Self-check: What two ensemble algorithms are built on decision trees? (Random forest and AdaBoost.)

Connects to: What a Decision Tree Is; Decision Trees in Practice

Previous LectureLecture 06 · Classification, Performance Measures, and Overfitting

Next LectureLecture 08 · Rule-Based Classification

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

7.1 What a Decision Tree Is

7.1.1 The Tree Structure

7.1.2 A Model Is a Flowchart

7.2 Partitioning the Space into Rectangles

7.2.1 Divide and Conquer on the Vector Space

7.2.2 Worked Example: Four-Class Partition and Prediction

7.3 Decision Trees for Classification: Process and Algorithms

7.3.1 From Training Data to Predictions

7.3.2 Algorithms for Building Trees

7.4 Many Possible Trees, One Bias

7.4.1 Same Dataset, Different Trees

7.4.2 The Bias of Decision Trees: Smallest Tree Wins

7.4.3 The Greedy Strategy and No Backtracking

7.5 Types of Splits

7.5.1 Splitting Nominal Attributes

7.5.2 Splitting Ordinal Attributes

7.5.3 Splitting Continuous Attributes

7.5.4 Student Questions and Answers

7.6 Choosing the Attribute to Split: Homogeneity and Confidence

7.6.1 Why We Want Homogeneous Children

7.6.2 Worked Example: Own Car, Car Type, or Student ID

7.6.3 Where Confidence Comes From

7.6.4 Student Questions and Answers

7.7 Entropy

7.7.1 What Entropy Measures

7.7.2 The Entropy Formula

7.7.3 Worked Example: Three Attributes A, B, C

7.7.4 The Entropy Curve

7.8 Information Gain

7.8.1 From Entropy to Information Gain

7.8.2 The Formula and the Weighting

7.8.3 Student Questions and Answers

7.9 Gini Index

7.9.1 The Gini Formula

7.9.2 Worked Example: Three Attributes A, B, C

7.9.3 Gini Split: Weighted Children, No Parent

7.9.4 Worked Example: Gini Split with N1 and N2

7.10 Misclassification Error

7.10.1 The Formula

7.10.2 Comparing All Three Criteria

7.11 The ID3 Algorithm

7.11.1 Top-Down Construction

7.11.2 Worked Example: Choosing Between Attributes with the Gain Formula

7.11.3 Stopping Criteria

7.11.4 A Recursive Gini Example from a Slide

7.12 Decision Trees in Practice

7.12.1 The scikit-learn API

7.12.2 Why Decision Trees Are So Popular

7.12.3 Ensemble Methods Built on Trees

7.12.4 Resources and Practice

Exam Guidance Summary

Key Industry Applications

DM Lecture 7 notes · Decision Trees

Sections Breakdown

Exam Revision Notes

What a Decision Tree Is

Partitioning the Space into Rectangles

Decision Trees for Classification: Process and Algorithms

Many Possible Trees, One Bias

Types of Splits

Choosing the Attribute to Split: Homogeneity and Confidence

Entropy

Information Gain

Gini Index

Misclassification Error

The ID3 Algorithm

Decision Trees in Practice

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat