Constructing a Simple Decision Tree ID3 with Attribute Selection for a Small Dataset | AI Research

Constructing a Simple Decision Tree (ID3) with Attribute Selection for a Small Dataset

Verified Sources

Nov 4, 2026

We will build a decision tree for the dataset with features Weather and Temp to predict the label Play?. The dataset is:

Weather	Temp	Play?
Sunny	Hot	No
Sunny	Cool	Yes
Rainy	Cool	Yes
Rainy	Hot	No

A standard way to “construct a simple decision tree” from categorical data is the ID3 criterion, which chooses the attribute that maximizes Information Gain based on Entropy.

Key selection idea: choose the attribute that best separates the classes (Yes/No) in the resulting subsets.

Note: I attempted web research for authoritative formulas, but the web-search tool is unavailable due to a usage-limit error; therefore, the mathematics below is derived directly from the standard ID3 definitions (entropy and information gain).

Decision Tree (ID3) Intuition: Entropy and Information Gain

Step-by-step: compute entropy and choose the best attribute (ID3-style)

1
Step 1
At the root, there are 2 instances with Play?=Yes and 2 instances with Play?=No, so the class distribution is (Yes:2, No:2).
2
Step 2
Use $H(S)=-\sum_{c \in \{Yes,No\}} p(c)\log_2 p(c)$ . Here $p(Yes)=\tfrac{2}{4}=0.5$ and $p(No)=\tfrac{2}{4}=0.5$ , so $H(S)= -2\cdot 0.5\log_2(0.5)=1$ .
3
Step 3
Partition by Weather: (Sunny: 2 records: {No, Yes} ⇒ one Yes and one No) and (Rainy: 2 records: {Yes, No} ⇒ one Yes and one No). Each subset has entropy 1.
4
Step 4
$IG(S,Weather)=H(S)-\sum_{v} \frac{|S_v|}{|S|}H(S_v)$ . Since both subsets have entropy 1 and each has size 2, the weighted entropy is $\tfrac{2}{4}\cdot 1+\tfrac{2}{4}\cdot 1=1$ . Hence $IG(S,Weather)=1-1=0$ .
5
Step 5
Partition by Temp: (Hot: 2 records: {No, No} ⇒ all No) and (Cool: 2 records: {Yes, Yes} ⇒ all Yes). Each subset is pure, so entropy is 0.
6
Step 6
$IG(S,Temp)=H(S)-\sum_{v} \frac{|S_v|}{|S|}H(S_v)=1-(\tfrac{2}{4}\cdot 0+\tfrac{2}{4}\cdot 0)=1$ .
7
Step 7
Because $IG(S,Temp)=1$ is greater than $IG(S,Weather)=0$ , choose Temp as the root split. Then create leaves: if Temp=Hot ⇒ Play?=No; if Temp=Cool ⇒ Play?=Yes.
8
Step 8
The resulting tree has one internal node (Temp) and two leaves.

1) Entropy and information gain (computed explicitly)

Let $S$ be the full dataset and $H(S)$ its entropy.

Root: $p(Yes)=0.5$ , $p(No)=0.5$ $H(S) = -\left(0.5\log_2 0.5 + 0.5\log_2 0.5\right)=1$

Split on [Weather]{def="A categorical input attribute used to split data in a decision tree}

Sunny subset has 1 Yes and 1 No ⇒ entropy: $H(S_{Sunny}) = 1$
Rainy subset has 1 Yes and 1 No ⇒ entropy: $H(S_{Rainy}) = 1$
Weighted entropy: $\frac{2}{4}\cdot 1 + \frac{2}{4}\cdot 1 = 1$
Information gain: $IG(S,Weather)=1-1=0$

Split on [Temp]{def="A categorical input attribute used to split data in a decision tree}

Hot subset has all No ⇒ entropy: $H(S_{Hot})=0$
Cool subset has all Yes ⇒ entropy: $H(S_{Cool})=0$
Weighted entropy: $\frac{2}{4}\cdot 0 + \frac{2}{4}\cdot 0 = 0$
Information gain: $IG(S,Temp)=1-0=1$

2) Constructed decision tree

The best attribute is Temp because it yields the highest Information Gain ( $1$ ) and produces pure child nodes (entropy $0$ ).

Information Gain by Attribute

ID3-style selection prefers the attribute with larger information gain.

Pro Tip: When IG is 0

If an attribute split does not change class purity (both subsets remain equally mixed), its weighted entropy equals the parent entropy, so $IG=0$ . In this dataset, Weather leaves the class composition unchanged within each Weather value.

Beware: Decision trees can overfit on tiny datasets

With only 4 samples, many splits may look “perfect.” In practice, you’d validate using cross-validation or pruning; but for this exercise, we correctly follow the information-gain criterion.

Attribute Selection Criteria (Explanation)

How to Construct the Tree (Conceptual Roadmap)

Compute root impurity

Calculate root entropy from class counts."

Try each candidate attribute

Split data by attribute values and compute weighted child entropies."

Select best attribute (max gain)

Choose the attribute with largest information gain."

Stop when nodes are pure (or no attributes remain)

If a subset has only one class, output a leaf label."

Decision Tree Attribute Selection (ID3) Flashcards

1 / 4

Question · Term

What does entropy measure in decision trees?

Click to reveal

Answer · Definition

Entropy $H(S)=-\sum_c p(c)\log_2 p(c)$ measures label uncertainty/mixedness. Pure subset ⇒ entropy 0.

Knowledge Check

Question 1 of 4

Q1Single choice

At the root, there are 2 'Yes' and 2 'No'. What is the entropy $H(S)$ ?

$0$

$0.5$

$1$

$2$

Explore Related Topics

Word Meaning Selection in Context: Fuzzy Logic, Shallow Semantic Analysis, and Word Sense Disambiguation

Synthesized Attributes for Evaluating Arithmetic Expressions (E→E+T|T, T→T*F|F)

Data Warehouse Schema for Decision Support: Star vs Snowflake

Browse all research articles