Entropy, Information Gain and Gini Impurity

🌐 Language

Section 01

The Story: Why "Impurity" Matters

📖 Real-World Story

The Sorting Machine That Learned to Ask Questions

Imagine you work at a fruit-packing factory. Your job: sort a pile of mixed fruit into boxes — one box per type. You have two strategies.

Strategy A: Grab fruit randomly, put it anywhere.
Strategy B: First ask "Is it round?" Then "Is it yellow?" Then "Is it bumpy?"

After Strategy A your boxes are still a mess — apples mixed with oranges, bananas mixed with limes. After Strategy B each box has mostly one type. The boxes are purer.

A Decision Tree is Strategy B. But it needs a number to measure how messy a box is right now, and how much cleaner each possible question would make it. That number is Entropy (or Gini Impurity). The improvement from asking a question is Information Gain.

These three concepts are the entire mathematical engine inside a decision tree. Everything else is just bookkeeping.

▶️

This Tutorial Has Eight Simulators

Look for the interactive boxes: the Impurity Mixer (Section 02), the Entropy Curve (03), Multi-Class Entropy (04), the Split Lab (05), the Random Label Game (06), Entropy vs Gini Race (08), the Cardinality Trap (09) and the Threshold Finder (11). Every number is computed live with the formulas in this tutorial.

Section 02

What Is Impurity? — The Core Concept

Before we touch any formula, let's build the intuition. A node in a decision tree contains a group of training samples. Impurity measures how mixed the class labels are in that group.

🔵 Impurity Spectrum — From Pure to Chaotic

💡

The Goal of Every Split

A Decision Tree split is good if the child nodes are purer than the parent. The algorithm's job is to find the split that reduces impurity the most. Two different formulas measure impurity: Entropy (information theory) and Gini Impurity (probability theory). Both measure the same thing — just with different maths.

Try It — The Impurity Mixer

Fill a node with Yes and No samples. Watch how mixed it is — and what the two impurity numbers say — before you learn a single formula.

सेक्शन 01

कहानी: "Impurity" क्यों ज़रूरी है

📖 असली दुनिया की कहानी

छाँटने वाली मशीन, जिसने सवाल पूछना सीखा

सोचिए, आप एक फल-पैकिंग फ़ैक्टरी में काम करते हैं। आपका काम है: मिले-जुले फलों के ढेर को डिब्बों में छाँटना — हर किस्म का एक डिब्बा। आपके पास दो तरीके हैं।

तरीका A: कोई भी फल उठाओ, कहीं भी रख दो।
तरीका B: पहले पूछो "क्या यह गोल है?" फिर "क्या यह पीला है?" फिर "क्या यह खुरदुरा है?"

तरीका A के बाद आपके डिब्बे अब भी गड़बड़ हैं — सेब संतरों में मिले हैं, केले नींबू में मिले हैं। तरीका B के बाद हर डिब्बे में ज़्यादातर एक ही किस्म है। डिब्बे ज़्यादा pure हैं।

Decision Tree तरीका B है। पर उसे एक संख्या चाहिए, जो बताए कि अभी डिब्बा कितना गड़बड़ है, और हर मुमकिन सवाल उसे कितना साफ़ करेगा। वह संख्या है Entropy (या Gini Impurity)। सवाल पूछने से जो सुधार होता है, वह है Information Gain।

ये तीन concept ही decision tree के अंदर का पूरा गणित वाला इंजन हैं। बाकी सब बस हिसाब-किताब है।

▶️

इस Tutorial में आठ Simulator हैं

Interactive boxes ढूँढिए: Impurity Mixer (सेक्शन 02), Entropy Curve (03), Multi-Class Entropy (04), Split Lab (05), Random Label Game (06), Entropy vs Gini Race (08), Cardinality Trap (09) और Threshold Finder (11)। हर संख्या इसी tutorial के formulas से live निकाली जाती है।

सेक्शन 02

Impurity क्या है? — मूल concept

कोई भी formula छूने से पहले, चलिए समझ बनाते हैं। Decision tree का एक node training samples का एक समूह रखता है। Impurity नापती है कि उस समूह में class labels कितने मिले-जुले हैं।

🔵 Impurity का दायरा — Pure से पूरी गड़बड़ तक

💡

हर Split का लक्ष्य

Decision Tree का split तब अच्छा है जब child nodes parent से ज़्यादा pure हों। Algorithm का काम है वह split ढूँढना जो impurity को सबसे ज़्यादा घटाए। Impurity नापने के दो अलग formulas हैं: Entropy (information theory) और Gini Impurity (probability theory)। दोनों एक ही चीज़ नापते हैं — बस गणित अलग है।

ख़ुद आज़माइए — Impurity Mixer

एक node को Yes और No samples से भरिए। देखिए वह कितना मिला-जुला है — और दोनों impurity संख्याएँ क्या कहती हैं — एक भी formula सीखने से पहले।

第 01 节

故事：为什么 “impurity” 很重要

📖 真实故事

学会提问的分拣机器

想象你在一家水果包装厂工作。你的任务是：把一堆混在一起的水果分进箱子里，每种水果一个箱子。你有两种方法。

方法 A：随手拿起水果，随便放。
方法 B：先问 “它是圆的吗？” 再问 “它是黄色的吗？” 然后问 “它表面凹凸不平吗？”

用方法 A 之后，箱子还是一团乱：苹果和橙子混在一起，香蕉和青柠混在一起。用方法 B 之后，每个箱子里基本只有一种水果。箱子变得更 pure 了。

Decision Tree 就是方法 B。但它需要一个数字，来衡量一个箱子现在有多乱，以及每个可能的问题能让它变得多干净。这个数字就是 Entropy（或 Gini Impurity）。提一个问题带来的改进，就是 Information Gain。

这三个概念就是 decision tree 里面全部的数学引擎。其他的都只是记账而已。

▶️

本教程有八个模拟器

请留意这些互动框：Impurity Mixer（第 02 节）、Entropy Curve（03）、 Multi-Class Entropy（04）、Split Lab（05）、Random Label Game（06）、 Entropy vs Gini Race（08）、Cardinality Trap（09）和 Threshold Finder（11）。每个数字都用本教程里的公式实时计算。

第 02 节

什么是 impurity？—— 核心概念

在接触任何公式之前，我们先建立直觉。decision tree 里的一个 node 包含一组 training samples。Impurity 衡量的是这组 samples 里 class labels 混得有多厉害。

🔵 Impurity 光谱 —— 从 pure 到混乱

💡

每次 split 的目标

如果 child nodes 比 parent 更 pure，这个 Decision Tree split 就是好的。算法的任务是找到最能降低 impurity 的 split。有两个不同的公式可以衡量 impurity： Entropy（信息论）和 Gini Impurity （概率论）。两者衡量的是同一件事，只是数学方法不同。

动手试试 —— Impurity Mixer

往一个 node 里放入 Yes 和 No samples。在学任何公式之前，先看看它混得有多厉害，以及两个 impurity 数字分别说了什么。

🧪 The Impurity MixerPure → mixed → pure again.

Try:

Yes samples

No samples

Section 03

Entropy — Disorder Measured in Bits

💡 Intuition First

Claude Shannon's Letter Guessing Game

In 1948, Claude Shannon invented Information Theory to measure how much "surprise" is in a message. He asked: if I pick a letter from a text, how many yes/no questions do I need to guess it?

If the text is all A's — you need 0 questions. You already know the answer. Zero surprise. Zero entropy.

If every letter is equally likely — you need about 4.7 questions (log₂ 26 ≈ 4.7). Maximum surprise. Maximum entropy.

A node in a decision tree is like a bag of letters. If all samples belong to one class — zero surprise, entropy = 0. If classes are perfectly balanced — maximum surprise, entropy = 1.0 (for binary). The tree wants to ask questions that reduce surprise as fast as possible.

Entropy Formula

H(S) = −Σ pᵢ · log₂(pᵢ)

pᵢ = proportion of samples belonging to class i.
Sum over all classes. Convention: 0 · log₂(0) = 0.
Unit: bits. Range: 0 (pure) to log₂(n) for n classes.

Binary Entropy (2 classes)

H = −p·log₂p − (1−p)·log₂(1−p)

Most common case: Yes/No, Spam/Ham, Default/No Default.
Maximum = 1.0 bit when p = 0.5 (50/50 split).
Minimum = 0 bits when p = 0 or p = 1 (pure node).

The Entropy Curve — Visualised

📈 Binary Entropy H(p) vs Class Probability p

The entropy curve is a symmetric hill. It peaks at 1.0 bit when classes are 50/50 (maximum uncertainty) and falls to 0 at both extremes (complete certainty). The tree wants to move nodes leftward or rightward — away from the peak.

Step-by-Step Entropy Calculation — Weather Dataset

We have 14 days of weather data. The target is Play Tennis? The full set S contains 9 Yes and 5 No.

🧮 H(S) — Parent Entropy for [9+, 5−]

Step 1

Calculate class proportions:
p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

Step 2

Compute each term −pᵢ · log₂(pᵢ):
−(0.643 · log₂ 0.643) = −(0.643 · −0.637) = +0.410
−(0.357 · log₂ 0.357) = −(0.357 · −1.486) = +0.530

Step 3

Sum: H(S) = 0.410 + 0.530 = 0.940 bits
This is the baseline. Every split's quality is measured against this.

Try It — The Entropy Curve

Set the number of Yes and No samples. The dot moves along the entropy hill, and the box works out H step by step — exactly like the calculation above. Try [9, 5] first.

सेक्शन 03

Entropy — Bits में नापी गई गड़बड़ी

💡 पहले समझ

क्लॉड शैनन का अक्षर पहचानने वाला खेल

1948 में, क्लॉड शैनन ने Information Theory बनाई, यह नापने के लिए कि किसी संदेश में कितना "सरप्राइज़" है। उन्होंने पूछा: अगर मैं किसी text से एक अक्षर चुनूँ, तो उसे बूझने के लिए मुझे कितने हाँ/ना वाले सवाल चाहिए?

अगर text में सब A ही हैं — तो आपको 0 सवाल चाहिए। आपको जवाब पहले से पता है। Zero सरप्राइज़। Zero entropy।

अगर हर अक्षर के आने का मौका बराबर है — तो आपको लगभग 4.7 सवाल चाहिए (log₂ 26 ≈ 4.7)। सबसे ज़्यादा सरप्राइज़। सबसे ज़्यादा entropy।

Decision tree का एक node अक्षरों के एक थैले जैसा है। अगर सारे samples एक ही class के हैं — zero सरप्राइज़, entropy = 0। अगर classes पूरी तरह बराबर बँटी हैं — सबसे ज़्यादा सरप्राइज़, entropy = 1.0 (binary के लिए)। Tree चाहता है ऐसे सवाल पूछना जो सरप्राइज़ को जितनी जल्दी हो सके घटाएँ।

Entropy Formula

H(S) = −Σ pᵢ · log₂(pᵢ)

pᵢ = class i वाले samples का हिस्सा।
सभी classes पर जोड़िए। नियम: 0 · log₂(0) = 0।
इकाई: bits। दायरा: 0 (pure) से n classes के लिए log₂(n) तक।

Binary Entropy (2 classes)

H = −p·log₂p − (1−p)·log₂(1−p)

सबसे आम केस: Yes/No, Spam/Ham, Default/No Default।
अधिकतम = 1.0 bit जब p = 0.5 (50/50 split)।
न्यूनतम = 0 bits जब p = 0 या p = 1 (pure node)।

Entropy Curve — चित्र में

📈 Binary Entropy H(p) बनाम Class Probability p

Entropy curve एक बराबर (symmetric) पहाड़ी जैसा है। जब classes 50/50 हों (सबसे ज़्यादा अनिश्चितता), तो यह 1.0 bit पर सबसे ऊपर होता है, और दोनों छोरों पर 0 तक गिर जाता है (पूरी निश्चितता)। Tree चाहता है कि nodes बाएँ या दाएँ जाएँ — चोटी से दूर।

Entropy का Step-by-Step हिसाब — Weather Dataset

हमारे पास 14 दिनों का मौसम data है। Target है Play Tennis? पूरे set S में 9 Yes और 5 No हैं।

🧮 H(S) — [9+, 5−] के लिए Parent Entropy

Step 1

Class का हिस्सा (proportion) निकालिए:
p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

Step 2

हर term −pᵢ · log₂(pᵢ) निकालिए:
−(0.643 · log₂ 0.643) = −(0.643 · −0.637) = +0.410
−(0.357 · log₂ 0.357) = −(0.357 · −1.486) = +0.530

Step 3

जोड़: H(S) = 0.410 + 0.530 = 0.940 bits
यह baseline है। हर split की quality इसी से तुलना करके नापी जाती है।

ख़ुद आज़माइए — Entropy Curve

Yes और No samples की गिनती सेट कीजिए। बिंदु entropy की पहाड़ी पर चलता है, और box H को step-by-step निकालता है — बिल्कुल ऊपर वाले हिसाब की तरह। पहले [9, 5] आज़माइए।

第 03 节

Entropy —— 用 bits 来衡量混乱程度

💡 先建立直觉

Claude Shannon 的猜字母游戏

1948 年，Claude Shannon 发明了信息论，用来衡量一条消息里有多少 “意外”。他问：如果我从一段文字里挑一个字母，需要问多少个是/否问题才能猜中它？

如果文字全是 A，你需要 0 个问题。你早就知道答案了。零意外。零 entropy。

如果每个字母出现的可能性都一样，你大约需要 4.7 个问题（log₂ 26 ≈ 4.7）。最大的意外。最大的 entropy。

decision tree 里的一个 node 就像一袋字母。如果所有 samples 都属于同一个 class，就是零意外，entropy = 0。如果各个 class 完全平衡，就是最大的意外，entropy = 1.0（二分类时）。tree 希望提出能尽快降低意外的问题。

Entropy 公式

H(S) = −Σ pᵢ · log₂(pᵢ)

pᵢ = 属于 class i 的 samples 所占的比例。
对所有 class 求和。约定：0 · log₂(0) = 0。
单位：bits。范围：0（pure）到 log₂(n)，n 是 class 的个数。

二分类 Entropy（2 个 class）

H = −p·log₂p − (1−p)·log₂(1−p)

最常见的情况：Yes/No、Spam/Ham、Default/No Default。
当 p = 0.5（50/50 split）时，最大值 = 1.0 bit。
当 p = 0 或 p = 1（pure node）时，最小值 = 0 bits。

Entropy 曲线 —— 画出来看看

📈 二分类 Entropy H(p) 与 class probability p 的关系

Entropy 曲线是一座对称的小山。当 class 是 50/50 时，它在 1.0 bit 达到顶点（最大的不确定）；在两端都降到 0（完全确定）。tree 希望把 node 往左或往右推，远离山顶。

一步一步计算 Entropy —— 天气 dataset

我们有 14 天的天气数据。目标是 Play Tennis? 整个集合 S 包含 9 个 Yes 和 5 个 No。

🧮 H(S) —— [9+, 5−] 的 parent entropy

第 1 步

计算各 class 的比例：
p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

第 2 步

计算每一项 −pᵢ · log₂(pᵢ)：
−(0.643 · log₂ 0.643) = −(0.643 · −0.637) = +0.410
−(0.357 · log₂ 0.357) = −(0.357 · −1.486) = +0.530

第 3 步

求和：H(S) = 0.410 + 0.530 = 0.940 bits
这就是基准线。每个 split 的好坏都拿它来比较。

动手试试 —— Entropy Curve

设置 Yes 和 No samples 的数量。圆点会沿着 entropy 小山移动，下面的框会一步一步算出 H，和上面的计算完全一样。先试试 [9, 5]。

📈 The Entropy CurveH = −p·log₂p − q·log₂q, live.

Try:

Yes

Section 04

Entropy for Multiple Classes

Entropy works for any number of classes — not just binary. The formula is identical; you just sum more terms. The maximum possible entropy scales with the number of classes.

Number of Classes (n)	Maximum Entropy = log₂(n)	Example Problem	Max Entropy Value
2 (Binary)	log₂(2)	Play Tennis: Yes / No	1.000 bits
3	log₂(3)	Weather: Sunny / Overcast / Rain	1.585 bits
4	log₂(4)	Seasons: Spring / Summer / Autumn / Winter	2.000 bits
5	log₂(5)	Risk: Very Low / Low / Med / High / Very High	2.322 bits
10	log₂(10)	Digit recognition: 0 – 9	3.322 bits

🧮 3-Class Entropy Example — Fruit Sorting

Dataset

A box contains 6 Apples, 3 Oranges, 3 Bananas. Total = 12 fruit.
p(Apple) = 6/12 = 0.50 | p(Orange) = 3/12 = 0.25 | p(Banana) = 3/12 = 0.25

Compute

H = −(0.50 · log₂0.50) − (0.25 · log₂0.25) − (0.25 · log₂0.25)
= −(0.50 · −1.0) − (0.25 · −2.0) − (0.25 · −2.0)
= 0.500 + 0.500 + 0.500 = 1.500 bits

Interpret

Maximum for 3 classes = log₂(3) = 1.585 bits.
Our box is close to maximum impurity (1.5/1.585 = 94.6% of maximum). A good split should bring this down significantly.

📐

Three Essential Properties of Entropy

1. Always ≥ 0 — entropy is zero only when the node is perfectly pure (one class only).
2. Maximum when classes are equally likely — this is when you have the least information.
3. Additive for independent events — this is what makes it theoretically elegant and why Shannon chose it over alternatives.

Try It — Multi-Class Entropy

A fruit box with up to five kinds of fruit. Each bar shows one term of the sum. Start with the 6 / 3 / 3 example, then make all counts equal and see the entropy reach log₂(n).

सेक्शन 04

कई Classes के लिए Entropy

Entropy कितनी भी classes के लिए काम करती है — सिर्फ़ binary के लिए नहीं। Formula वही है; बस आप ज़्यादा terms जोड़ते हैं। सबसे बड़ी मुमकिन entropy classes की गिनती के साथ बढ़ती है।

Classes की गिनती (n)	अधिकतम Entropy = log₂(n)	उदाहरण समस्या	अधिकतम Entropy मान
2 (Binary)	log₂(2)	Play Tennis: Yes / No	1.000 bits
3	log₂(3)	मौसम: Sunny / Overcast / Rain	1.585 bits
4	log₂(4)	ऋतुएँ: वसंत / गर्मी / पतझड़ / सर्दी	2.000 bits
5	log₂(5)	जोखिम: बहुत कम / कम / मध्यम / ज़्यादा / बहुत ज़्यादा	2.322 bits
10	log₂(10)	अंक पहचानना: 0 – 9	3.322 bits

🧮 3-Class Entropy उदाहरण — फल छाँटना

Dataset

एक डिब्बे में 6 सेब, 3 संतरे, 3 केले हैं। कुल = 12 फल।
p(Apple) = 6/12 = 0.50 | p(Orange) = 3/12 = 0.25 | p(Banana) = 3/12 = 0.25

हिसाब

H = −(0.50 · log₂0.50) − (0.25 · log₂0.25) − (0.25 · log₂0.25)
= −(0.50 · −1.0) − (0.25 · −2.0) − (0.25 · −2.0)
= 0.500 + 0.500 + 0.500 = 1.500 bits

मतलब

3 classes के लिए अधिकतम = log₂(3) = 1.585 bits।
हमारा डिब्बा अधिकतम impurity के क़रीब है (1.5/1.585 = अधिकतम का 94.6%)। एक अच्छा split इसे काफ़ी नीचे लाना चाहिए।

📐

Entropy की तीन ज़रूरी ख़ूबियाँ

1. हमेशा ≥ 0 — entropy तभी zero होती है जब node पूरी तरह pure हो (सिर्फ़ एक class)।
2. सबसे ज़्यादा तब, जब सभी classes का मौका बराबर हो — यही वह हालत है जब आपके पास सबसे कम जानकारी होती है।
3. अलग-अलग (independent) घटनाओं के लिए जुड़ती है — इसी वजह से यह theory में सुंदर है, और इसीलिए शैनन ने दूसरे विकल्पों की जगह इसे चुना।

ख़ुद आज़माइए — Multi-Class Entropy

एक फलों का डिब्बा, जिसमें पाँच तरह तक के फल हैं। हर bar जोड़ का एक term दिखाता है। 6 / 3 / 3 वाले उदाहरण से शुरू कीजिए, फिर सारी गिनतियाँ बराबर कीजिए और देखिए entropy log₂(n) तक पहुँचती है।

第 04 节

多个 class 的 Entropy

Entropy 适用于任意数量的 class，不只是二分类。公式完全一样，只是要多加几项。最大可能的 entropy 会随着 class 的数量变大。

class 数量（n）	最大 Entropy = log₂(n)	示例问题	最大 Entropy 值
2（二分类）	log₂(2)	Play Tennis：Yes / No	1.000 bits
3	log₂(3)	天气：Sunny / Overcast / Rain	1.585 bits
4	log₂(4)	季节：春 / 夏 / 秋 / 冬	2.000 bits
5	log₂(5)	风险：很低 / 低 / 中 / 高 / 很高	2.322 bits
10	log₂(10)	数字识别：0 – 9	3.322 bits

🧮 3 个 class 的 Entropy 示例 —— 水果分拣

Dataset

一个箱子里有 6 个苹果、3 个橙子、3 根香蕉。总共 = 12 个水果。
p(Apple) = 6/12 = 0.50 | p(Orange) = 3/12 = 0.25 | p(Banana) = 3/12 = 0.25

计算

H = −(0.50 · log₂0.50) − (0.25 · log₂0.25) − (0.25 · log₂0.25)
= −(0.50 · −1.0) − (0.25 · −2.0) − (0.25 · −2.0)
= 0.500 + 0.500 + 0.500 = 1.500 bits

解读

3 个 class 的最大值 = log₂(3) = 1.585 bits。
我们的箱子很接近最大 impurity（1.5/1.585 = 最大值的 94.6%）。一个好的 split 应该能把它大幅降下来。

📐

Entropy 的三个重要性质

1. 永远 ≥ 0 —— 只有当 node 完全 pure（只有一个 class）时，entropy 才是零。
2. 各 class 可能性相同时最大 —— 这时你掌握的信息最少。
3. 对独立事件可以相加 —— 这让它在理论上很优美，也是 Shannon 选它而不选其他方案的原因。

动手试试 —— Multi-Class Entropy

一个水果箱，最多可以有五种水果。每根柱子表示求和中的一项。先从 6 / 3 / 3 的例子开始，然后把所有数量设成一样，看看 entropy 如何达到 log₂(n)。

🍎 Multi-Class EntropyMore classes → a higher ceiling.

Try:

Apples

Oranges

Bananas

Limes

Grapes

Section 05

Information Gain — Measuring Split Quality

Information Gain answers the question: "How much does asking this question reduce my uncertainty about the answer?" It is simply the difference in entropy before and after the split, weighted by the size of each child group.

Information Gain

IG(S, A) = H(S) − Σ (|Sᵥ|/|S|) · H(Sᵥ)

S = parent node samples. A = attribute being tested.
Sᵥ = subset of samples where attribute A has value v.
The weighted entropy of all children is subtracted from parent entropy.

What Good IG Looks Like

IG = 0 → useless split

IG = 0 means the split didn't reduce entropy at all — the attribute carries no information about the target. Maximum IG = H(parent) — both children are perfectly pure. The algorithm picks the attribute with highest IG.

Worked Example: Which Attribute Splits the Weather Data Best?

Day	Outlook	Temp	Humidity	Wind	Play Tennis?
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

Parent entropy H(S) = 0.940 bits. Now we calculate IG for each attribute.

🧮 IG(S, Outlook)

Sunny (5)

D1,D2,D8,D9,D11 → [2+, 3−] p+=2/5=0.4, p−=3/5=0.6
H(Sunny) = −0.4·log₂0.4 − 0.6·log₂0.6 = 0.529 + 0.442 = 0.971 bits

Overcast (4)

D3,D7,D12,D13 → [4+, 0−] perfectly pure!
H(Overcast) = 0 − 0 = 0.000 bits

Rain (5)

D4,D5,D6,D10,D14 → [3+, 2−] p+=3/5=0.6, p−=2/5=0.4
H(Rain) = −0.6·log₂0.6 − 0.4·log₂0.4 = 0.442 + 0.529 = 0.971 bits

Weighted

(5/14)·0.971 + (4/14)·0.000 + (5/14)·0.971
= 0.347 + 0.000 + 0.347 = 0.694 bits

IG(S, Outlook) = 0.940 − 0.694 = 0.246 bits ✓ WINNER

🧮 IG(S, Humidity)

High (7)

D1,D2,D3,D4,D8,D12,D14 → [3+, 4−]
H(High) = −(3/7)·log₂(3/7) − (4/7)·log₂(4/7) = 0.524 + 0.461 = 0.985 bits

Normal (7)

D5,D6,D7,D9,D10,D11,D13 → [6+, 1−]
H(Normal) = −(6/7)·log₂(6/7) − (1/7)·log₂(1/7) = 0.191 + 0.401 = 0.592 bits

Weighted = (7/14)·0.985 + (7/14)·0.592 = 0.493 + 0.296 = 0.789
IG(S, Humidity) = 0.940 − 0.789 = 0.151 bits

🧮 IG(S, Wind) and IG(S, Temp)

Wind

Strong [3+,3−] H=1.0 Weak [6+,2−] H=0.811
Weighted = (6/14)·1.0 + (8/14)·0.811 = 0.893
IG(S, Wind) = 0.940 − 0.893 = 0.048 bits

Temp

Hot [2+,2−] H=1.0 Mild [4+,2−] H=0.918 Cool [3+,1−] H=0.811
Weighted = (4/14)·1.0 + (6/14)·0.918 + (4/14)·0.811 = 0.911
IG(S, Temp) = 0.940 − 0.911 = 0.029 bits

📊 Information Gain Comparison — All Four Attributes

Outlook is selected as the root node with IG = 0.246 bits. Temp earns only 0.029 bits — it is outcompeted at every node and ends up never being used in the final tree.

Try It — The Split Lab

Pick an attribute to split the 14 days. See the child nodes, their impurity, the weighted average and the gain. The bars on the right rank all four attributes. Switch the measure to Gini and compare.

सेक्शन 05

Information Gain — Split की Quality नापना

Information Gain इस सवाल का जवाब देता है: "यह सवाल पूछने से जवाब के बारे में मेरी अनिश्चितता कितनी घटती है?" यह बस split से पहले और बाद की entropy का अंतर है, जिसमें हर child समूह के साइज़ के हिसाब से वज़न दिया जाता है।

Information Gain

IG(S, A) = H(S) − Σ (|Sᵥ|/|S|) · H(Sᵥ)

S = parent node के samples। A = जिस attribute को जाँचा जा रहा है।
Sᵥ = samples का वह हिस्सा जहाँ attribute A का मान v है।
सभी children की weighted entropy को parent entropy से घटाया जाता है।

अच्छा IG कैसा दिखता है

IG = 0 → बेकार split

IG = 0 का मतलब है split ने entropy बिल्कुल नहीं घटाई — attribute में target के बारे में कोई जानकारी नहीं है। अधिकतम IG = H(parent) — दोनों children पूरी तरह pure हैं। Algorithm वह attribute चुनता है जिसका IG सबसे ज़्यादा हो।

हल किया हुआ उदाहरण: कौन-सा Attribute Weather Data को सबसे अच्छा Split करता है?

दिन	Outlook	Temp	Humidity	Wind	Play Tennis?
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

Parent entropy H(S) = 0.940 bits। अब हम हर attribute के लिए IG निकालते हैं।

🧮 IG(S, Outlook)

Sunny (5)

D1,D2,D8,D9,D11 → [2+, 3−] p+=2/5=0.4, p−=3/5=0.6
H(Sunny) = −0.4·log₂0.4 − 0.6·log₂0.6 = 0.529 + 0.442 = 0.971 bits

Overcast (4)

D3,D7,D12,D13 → [4+, 0−] पूरी तरह pure!
H(Overcast) = 0 − 0 = 0.000 bits

Rain (5)

D4,D5,D6,D10,D14 → [3+, 2−] p+=3/5=0.6, p−=2/5=0.4
H(Rain) = −0.6·log₂0.6 − 0.4·log₂0.4 = 0.442 + 0.529 = 0.971 bits

Weighted

(5/14)·0.971 + (4/14)·0.000 + (5/14)·0.971
= 0.347 + 0.000 + 0.347 = 0.694 bits

IG(S, Outlook) = 0.940 − 0.694 = 0.246 bits ✓ विजेता

🧮 IG(S, Humidity)

High (7)

D1,D2,D3,D4,D8,D12,D14 → [3+, 4−]
H(High) = −(3/7)·log₂(3/7) − (4/7)·log₂(4/7) = 0.524 + 0.461 = 0.985 bits

Normal (7)

D5,D6,D7,D9,D10,D11,D13 → [6+, 1−]
H(Normal) = −(6/7)·log₂(6/7) − (1/7)·log₂(1/7) = 0.191 + 0.401 = 0.592 bits

Weighted = (7/14)·0.985 + (7/14)·0.592 = 0.493 + 0.296 = 0.789
IG(S, Humidity) = 0.940 − 0.789 = 0.151 bits

🧮 IG(S, Wind) और IG(S, Temp)

Wind

Strong [3+,3−] H=1.0 Weak [6+,2−] H=0.811
Weighted = (6/14)·1.0 + (8/14)·0.811 = 0.893
IG(S, Wind) = 0.940 − 0.893 = 0.048 bits

Temp

Hot [2+,2−] H=1.0 Mild [4+,2−] H=0.918 Cool [3+,1−] H=0.811
Weighted = (4/14)·1.0 + (6/14)·0.918 + (4/14)·0.811 = 0.911
IG(S, Temp) = 0.940 − 0.911 = 0.029 bits

📊 Information Gain की तुलना — चारों Attributes

Outlook को root node चुना जाता है, IG = 0.246 bits के साथ। Temp को सिर्फ़ 0.029 bits मिलते हैं — यह हर node पर दूसरों से हार जाता है और final tree में कभी इस्तेमाल ही नहीं होता।

ख़ुद आज़माइए — Split Lab

14 दिनों को split करने के लिए एक attribute चुनिए। Child nodes, उनकी impurity, weighted average और gain देखिए। दाईं ओर के bars चारों attributes की रैंकिंग दिखाते हैं। Measure को Gini पर बदलिए और तुलना कीजिए।

第 05 节

Information Gain —— 衡量 split 的好坏

Information Gain 回答的问题是：“问这个问题，能让我对答案的不确定减少多少？”它就是 split 前后 entropy 的差值，并按每个 child 组的大小加权。

Information Gain

IG(S, A) = H(S) − Σ (|Sᵥ|/|S|) · H(Sᵥ)

S = parent node 的 samples。A = 正在测试的 attribute。
Sᵥ = attribute A 取值为 v 的那部分 samples。
用 parent entropy 减去所有 child 的加权 entropy。

好的 IG 是什么样的

IG = 0 → 没用的 split

IG = 0 表示这个 split 完全没有降低 entropy —— 这个 attribute 对目标没有任何信息。最大 IG = H(parent) —— 两个 child 都完全 pure。算法会选择 IG 最高 的 attribute。

例题：哪个 attribute 最适合 split 天气数据？

日期	Outlook	Temp	Humidity	Wind	Play Tennis?
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

Parent entropy H(S) = 0.940 bits。现在我们为每个 attribute 计算 IG。

🧮 IG(S, Outlook)

Sunny (5)

D1,D2,D8,D9,D11 → [2+, 3−] p+=2/5=0.4, p−=3/5=0.6
H(Sunny) = −0.4·log₂0.4 − 0.6·log₂0.6 = 0.529 + 0.442 = 0.971 bits

Overcast (4)

D3,D7,D12,D13 → [4+, 0−] 完全 pure！
H(Overcast) = 0 − 0 = 0.000 bits

Rain (5)

D4,D5,D6,D10,D14 → [3+, 2−] p+=3/5=0.6, p−=2/5=0.4
H(Rain) = −0.6·log₂0.6 − 0.4·log₂0.4 = 0.442 + 0.529 = 0.971 bits

加权

(5/14)·0.971 + (4/14)·0.000 + (5/14)·0.971
= 0.347 + 0.000 + 0.347 = 0.694 bits

IG(S, Outlook) = 0.940 − 0.694 = 0.246 bits ✓ 胜出

🧮 IG(S, Humidity)

High (7)

D1,D2,D3,D4,D8,D12,D14 → [3+, 4−]
H(High) = −(3/7)·log₂(3/7) − (4/7)·log₂(4/7) = 0.524 + 0.461 = 0.985 bits

Normal (7)

D5,D6,D7,D9,D10,D11,D13 → [6+, 1−]
H(Normal) = −(6/7)·log₂(6/7) − (1/7)·log₂(1/7) = 0.191 + 0.401 = 0.592 bits

加权 = (7/14)·0.985 + (7/14)·0.592 = 0.493 + 0.296 = 0.789
IG(S, Humidity) = 0.940 − 0.789 = 0.151 bits

🧮 IG(S, Wind) 和 IG(S, Temp)

Wind

Strong [3+,3−] H=1.0 Weak [6+,2−] H=0.811
加权 = (6/14)·1.0 + (8/14)·0.811 = 0.893
IG(S, Wind) = 0.940 − 0.893 = 0.048 bits

Temp

Hot [2+,2−] H=1.0 Mild [4+,2−] H=0.918 Cool [3+,1−] H=0.811
加权 = (4/14)·1.0 + (6/14)·0.918 + (4/14)·0.811 = 0.911
IG(S, Temp) = 0.940 − 0.911 = 0.029 bits

📊 Information Gain 对比 —— 全部四个 attribute

Outlook 以 IG = 0.246 bits 被选为 root node。Temp 只得到 0.029 bits —— 它在每个 node 都比不过别人，最后在最终的 tree 里从来没被用到。

动手试试 —— Split Lab

选一个 attribute 来 split 这 14 天。看看 child nodes、它们的 impurity、weighted average 和 gain。右边的柱子给全部四个 attribute 排名。把衡量方式切换成 Gini，再比较一下。

⚖️ The Split LabParent impurity − weighted child impurity = gain.

Entropy / IG Gini

All attributes (click a bar to split on it)

Section 06

Gini Impurity — The CART Algorithm's Measure

💡 Different Formula, Same Goal

The Probability of Mislabelling a Random Sample

Gini Impurity asks a different question: "If I randomly pick a sample from this node and randomly assign it a class label based on the class distribution in this node, what is the probability I label it wrong?"

If the node is pure (all one class), I'll never mislabel it — Gini = 0.
If the node is 50/50, I'll mislabel half the time — Gini = 0.5.

No logarithms. No bits. Just a probability between 0 and 0.5 (for binary problems). This is why scikit-learn defaults to Gini — it's computationally faster while capturing the same information.

Gini Impurity

Gini(S) = 1 − Σ pᵢ²

pᵢ = proportion of samples in class i.
Sum the squared proportions, subtract from 1.
Range: 0 (pure) to (n−1)/n for n classes. Binary max = 0.5.

Weighted Gini After Split

Gini_split = Σ (|Sᵥ|/|S|) · Gini(Sᵥ)

Weighted average of child node Gini values.
Gini Gain = Gini(parent) − Gini_split.
Pick the split with the highest Gini Gain.

Gini Values Across Class Distributions

Distribution [Yes, No]	p(Yes)	Gini = 1 − (p² + q²)	Interpretation
[10, 0] — all Yes	1.00	1 − (1.00² + 0.00²) = 0.000	Pure — no impurity
[8, 2] — mostly Yes	0.80	1 − (0.80² + 0.20²) = 1 − 0.68 = 0.320	Low impurity
[6, 4] — slightly skewed	0.60	1 − (0.60² + 0.40²) = 1 − 0.52 = 0.480	Moderate impurity
[5, 5] — perfectly mixed	0.50	1 − (0.50² + 0.50²) = 1 − 0.50 = 0.500	Maximum impurity (binary)

Gini Calculation — Same Weather Dataset

🧮 Gini(S) — Parent Node [9+, 5−]

Proportions

p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

Formula

Gini(S) = 1 − (0.643² + 0.357²) = 1 − (0.413 + 0.127) = 1 − 0.540 = 0.460

🧮 Gini Gain — Outlook Split

Sunny (5) [2+,3−]

Gini = 1 − ((2/5)² + (3/5)²) = 1 − (0.16 + 0.36) = 0.480

Overcast (4) [4+,0−]

Gini = 1 − (1² + 0²) = 0.000 ← Pure!

Rain (5) [3+,2−]

Gini = 1 − ((3/5)² + (2/5)²) = 1 − (0.36 + 0.16) = 0.480

Weighted Gini

(5/14)·0.480 + (4/14)·0.000 + (5/14)·0.480 = 0.171 + 0 + 0.171 = 0.343

Gini Gain

0.460 − 0.343 = 0.117

🧮 Gini Gain — Humidity Split

High (7) [3+,4−]

Gini = 1 − ((3/7)² + (4/7)²) = 1 − (0.184 + 0.327) = 0.490

Normal (7) [6+,1−]

Gini = 1 − ((6/7)² + (1/7)²) = 1 − (0.735 + 0.020) = 0.245

Gini Gain

Weighted = (7/14)·0.490 + (7/14)·0.245 = 0.245 + 0.122 = 0.367
Gain = 0.460 − 0.367 = 0.093

Try It — The Random Label Game

Play the Gini game for real. Each round picks a random sample from the node and gives it a random label, drawn from the node's own class mix. Count how often the label is wrong. After many rounds, that rate is the Gini impurity.

सेक्शन 06

Gini Impurity — CART Algorithm का पैमाना

💡 Formula अलग, लक्ष्य एक

किसी Random Sample को ग़लत Label देने की Probability

Gini Impurity एक अलग सवाल पूछती है: "अगर मैं इस node से कोई भी sample random चुनूँ, और इस node की class distribution के हिसाब से उसे random class label दूँ, तो ग़लत label देने की probability कितनी है?"

अगर node pure है (सब एक ही class), तो मैं कभी ग़लत label नहीं दूँगा — Gini = 0।
अगर node 50/50 है, तो मैं आधी बार ग़लत label दूँगा — Gini = 0.5।

कोई logarithm नहीं। कोई bits नहीं। बस 0 और 0.5 के बीच एक probability (binary समस्याओं के लिए)। इसीलिए scikit-learn default में Gini लेता है — यह हिसाब में तेज़ है और वही जानकारी पकड़ता है।

Gini Impurity

Gini(S) = 1 − Σ pᵢ²

pᵢ = class i में samples का हिस्सा।
हिस्सों के square जोड़िए, फिर 1 में से घटाइए।
दायरा: 0 (pure) से n classes के लिए (n−1)/n तक। Binary में अधिकतम = 0.5।

Split के बाद Weighted Gini

Gini_split = Σ (|Sᵥ|/|S|) · Gini(Sᵥ)

Child nodes के Gini मानों का weighted average।
Gini Gain = Gini(parent) − Gini_split।
वह split चुनिए जिसका Gini Gain सबसे ज़्यादा हो।

अलग-अलग Class बँटवारों पर Gini के मान

बँटवारा [Yes, No]	p(Yes)	Gini = 1 − (p² + q²)	मतलब
[10, 0] — सब Yes	1.00	1 − (1.00² + 0.00²) = 0.000	Pure — कोई impurity नहीं
[8, 2] — ज़्यादातर Yes	0.80	1 − (0.80² + 0.20²) = 1 − 0.68 = 0.320	कम impurity
[6, 4] — थोड़ा एकतरफ़ा	0.60	1 − (0.60² + 0.40²) = 1 − 0.52 = 0.480	मध्यम impurity
[5, 5] — पूरी तरह मिला-जुला	0.50	1 − (0.50² + 0.50²) = 1 − 0.50 = 0.500	अधिकतम impurity (binary)

Gini का हिसाब — वही Weather Dataset

🧮 Gini(S) — Parent Node [9+, 5−]

हिस्से

p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

Formula

Gini(S) = 1 − (0.643² + 0.357²) = 1 − (0.413 + 0.127) = 1 − 0.540 = 0.460

🧮 Gini Gain — Outlook Split

Sunny (5) [2+,3−]

Gini = 1 − ((2/5)² + (3/5)²) = 1 − (0.16 + 0.36) = 0.480

Overcast (4) [4+,0−]

Gini = 1 − (1² + 0²) = 0.000 ← Pure!

Rain (5) [3+,2−]

Gini = 1 − ((3/5)² + (2/5)²) = 1 − (0.36 + 0.16) = 0.480

Weighted Gini

(5/14)·0.480 + (4/14)·0.000 + (5/14)·0.480 = 0.171 + 0 + 0.171 = 0.343

Gini Gain

0.460 − 0.343 = 0.117

🧮 Gini Gain — Humidity Split

High (7) [3+,4−]

Gini = 1 − ((3/7)² + (4/7)²) = 1 − (0.184 + 0.327) = 0.490

Normal (7) [6+,1−]

Gini = 1 − ((6/7)² + (1/7)²) = 1 − (0.735 + 0.020) = 0.245

Gini Gain

Weighted = (7/14)·0.490 + (7/14)·0.245 = 0.245 + 0.122 = 0.367
Gain = 0.460 − 0.367 = 0.093

ख़ुद आज़माइए — Random Label Game

Gini वाला खेल सच में खेलिए। हर round में node से एक random sample चुना जाता है और उसे एक random label दिया जाता है, जो node के अपने class मिश्रण से निकाला जाता है। गिनिए कि label कितनी बार ग़लत होता है। बहुत सारे rounds के बाद, वही दर Gini impurity है।

第 06 节

Gini Impurity —— CART 算法的衡量方式

💡 公式不同，目标相同

给随机 sample 贴错 label 的 probability

Gini Impurity 问的是另一个问题：“如果我从这个 node 里随机挑一个 sample，再按照这个 node 里的 class 分布，随机给它一个 class label，我贴错的 probability 是多少？”

如果 node 是 pure 的（全是一个 class），我永远不会贴错 —— Gini = 0。
如果 node 是 50/50，我有一半的时候会贴错 —— Gini = 0.5。

没有 log。没有 bits。只是一个 0 到 0.5 之间的 probability（二分类问题）。这就是 scikit-learn 默认用 Gini 的原因 —— 它计算更快，同时能抓住同样的信息。

Gini Impurity

Gini(S) = 1 − Σ pᵢ²

pᵢ = class i 中 samples 所占的比例。
把比例的平方加起来，再用 1 减去。
范围：0（pure）到 (n−1)/n，n 是 class 的个数。二分类最大值 = 0.5。

split 之后的加权 Gini

Gini_split = Σ (|Sᵥ|/|S|) · Gini(Sᵥ)

child node Gini 值的 weighted average。
Gini Gain = Gini(parent) − Gini_split。
选 Gini Gain 最高的 split。

不同 class 分布下的 Gini 值

分布 [Yes, No]	p(Yes)	Gini = 1 − (p² + q²)	解读
[10, 0] —— 全是 Yes	1.00	1 − (1.00² + 0.00²) = 0.000	Pure —— 没有 impurity
[8, 2] —— 大多是 Yes	0.80	1 − (0.80² + 0.20²) = 1 − 0.68 = 0.320	impurity 低
[6, 4] —— 稍微偏斜	0.60	1 − (0.60² + 0.40²) = 1 − 0.52 = 0.480	impurity 中等
[5, 5] —— 完全混合	0.50	1 − (0.50² + 0.50²) = 1 − 0.50 = 0.500	最大 impurity（二分类）

Gini 计算 —— 同一个天气 dataset

🧮 Gini(S) —— Parent Node [9+, 5−]

比例

p(Yes) = 9/14 = 0.643 | p(No) = 5/14 = 0.357

公式

Gini(S) = 1 − (0.643² + 0.357²) = 1 − (0.413 + 0.127) = 1 − 0.540 = 0.460

🧮 Gini Gain —— 按 Outlook split

Sunny (5) [2+,3−]

Gini = 1 − ((2/5)² + (3/5)²) = 1 − (0.16 + 0.36) = 0.480

Overcast (4) [4+,0−]

Gini = 1 − (1² + 0²) = 0.000 ← Pure！

Rain (5) [3+,2−]

Gini = 1 − ((3/5)² + (2/5)²) = 1 − (0.36 + 0.16) = 0.480

加权 Gini

(5/14)·0.480 + (4/14)·0.000 + (5/14)·0.480 = 0.171 + 0 + 0.171 = 0.343

Gini Gain

0.460 − 0.343 = 0.117

🧮 Gini Gain —— 按 Humidity split

High (7) [3+,4−]

Gini = 1 − ((3/7)² + (4/7)²) = 1 − (0.184 + 0.327) = 0.490

Normal (7) [6+,1−]

Gini = 1 − ((6/7)² + (1/7)²) = 1 − (0.735 + 0.020) = 0.245

Gini Gain

加权 = (7/14)·0.490 + (7/14)·0.245 = 0.245 + 0.122 = 0.367
Gain = 0.460 − 0.367 = 0.093

动手试试 —— Random Label Game

真的来玩一次 Gini 游戏。每一轮从 node 里随机挑一个 sample，再随机给它一个 label，这个 label 按照 node 自己的 class 比例来抽。数一数 label 错了多少次。玩了很多轮之后，这个错误率就是 Gini impurity。

🎲 The Random Label GameGini = chance of a wrong random label.

Try:

Yes

Section 07

Gini for Multiple Classes — Maximum Values

Just like entropy, the maximum Gini Impurity increases with the number of classes. The formula for maximum Gini is (n−1)/n — occurring when all classes are equally likely.

Classes (n)	Max Gini = (n−1)/n	Worked Example (equal probs)
2	0.500	p=0.5 each: 1−(0.5²+0.5²) = 1−0.5 = 0.500
3	0.667	p=1/3 each: 1−3·(1/3)² = 1−3·(1/9) = 1−1/3 = 0.667
4	0.750	p=0.25 each: 1−4·(0.25²) = 1−4·0.0625 = 1−0.25 = 0.750
5	0.800	p=0.2 each: 1−5·(0.2²) = 1−5·0.04 = 1−0.20 = 0.800
10	0.900	p=0.1 each: 1−10·(0.1²) = 1−10·0.01 = 1−0.10 = 0.900

Section 08

Entropy vs Gini — Head-to-Head

📈 Entropy vs Gini vs Misclassification Rate (binary, normalised to 0–1)

All three curves are symmetric and peak at p = 0.5. Entropy (purple) rises more steeply away from the extremes — it is more sensitive to small probability changes near p=0 and p=1. Gini (blue) is a smoother quadratic approximation. Misclassification rate (dashed) is linear and less smooth — rarely used because it lacks the mathematical properties the other two have.

🔵 Gini Impurity (CART — sklearn default)

Property	Detail
Formula	1 − Σ pᵢ²
Binary range	0 to 0.5
n-class max	(n−1)/n
Computation	Fast — squaring only, no log
Behaviour	Tends toward larger balanced partitions
Sensitivity	Less sensitive at extremes (near-pure nodes)
Used by	CART, sklearn DecisionTree (default)

🟢 Entropy / Information Gain (ID3, C4.5)

Property	Detail
Formula	−Σ pᵢ · log₂(pᵢ)
Binary range	0 to 1.0
n-class max	log₂(n)
Computation	Slower — log per class per node
Behaviour	More sensitive to subtle class changes
Sensitivity	Higher sensitivity at near-pure nodes
Used by	ID3, C4.5, sklearn with criterion='entropy'

Try It — Entropy vs Gini Race

Left: slide p to compare the three curves at any point (Gini and misclassification are doubled so all three top out at 1). Right: a race. Hundreds of random nodes each get 8 random candidate splits. Do entropy and Gini pick the same winner?

सेक्शन 07

कई Classes के लिए Gini — अधिकतम मान

Entropy की तरह, अधिकतम Gini Impurity भी classes की गिनती के साथ बढ़ती है। अधिकतम Gini का formula है (n−1)/n — यह तब होता है जब सभी classes का मौका बराबर हो।

Classes (n)	अधिकतम Gini = (n−1)/n	हल किया उदाहरण (बराबर probabilities)
2	0.500	हर एक p=0.5: 1−(0.5²+0.5²) = 1−0.5 = 0.500
3	0.667	हर एक p=1/3: 1−3·(1/3)² = 1−3·(1/9) = 1−1/3 = 0.667
4	0.750	हर एक p=0.25: 1−4·(0.25²) = 1−4·0.0625 = 1−0.25 = 0.750
5	0.800	हर एक p=0.2: 1−5·(0.2²) = 1−5·0.04 = 1−0.20 = 0.800
10	0.900	हर एक p=0.1: 1−10·(0.1²) = 1−10·0.01 = 1−0.10 = 0.900

सेक्शन 08

Entropy vs Gini — आमने-सामने

📈 Entropy vs Gini vs Misclassification Rate (binary, 0–1 पर normalised)

तीनों curves बराबर (symmetric) हैं और p = 0.5 पर सबसे ऊपर होते हैं। Entropy (बैंगनी) छोरों से दूर ज़्यादा तेज़ी से चढ़ती है — p=0 और p=1 के पास probability के छोटे बदलावों पर यह ज़्यादा संवेदनशील है। Gini (नीला) एक ज़्यादा smooth quadratic अंदाज़ा है। Misclassification rate (dashed) सीधी रेखा वाला और कम smooth है — इसका इस्तेमाल कम होता है, क्योंकि इसमें वे गणितीय ख़ूबियाँ नहीं हैं जो बाकी दोनों में हैं।

🔵 Gini Impurity (CART — sklearn default)

ख़ूबी	विवरण
Formula	1 − Σ pᵢ²
Binary दायरा	0 से 0.5
n-class अधिकतम	(n−1)/n
हिसाब	तेज़ — सिर्फ़ square, कोई log नहीं
बर्ताव	बड़े, बराबर हिस्सों की ओर झुकती है
संवेदनशीलता	छोरों पर (लगभग pure nodes पर) कम संवेदनशील
कौन इस्तेमाल करता है	CART, sklearn DecisionTree (default)

🟢 Entropy / Information Gain (ID3, C4.5)

ख़ूबी	विवरण
Formula	−Σ pᵢ · log₂(pᵢ)
Binary दायरा	0 से 1.0
n-class अधिकतम	log₂(n)
हिसाब	धीमा — हर node पर हर class के लिए log
बर्ताव	class के बारीक बदलावों पर ज़्यादा संवेदनशील
संवेदनशीलता	लगभग pure nodes पर ज़्यादा संवेदनशील
कौन इस्तेमाल करता है	ID3, C4.5, sklearn with criterion='entropy'

ख़ुद आज़माइए — Entropy vs Gini Race

बाएँ: किसी भी बिंदु पर तीनों curves की तुलना के लिए p को खिसकाइए (Gini और misclassification को दोगुना किया गया है, ताकि तीनों का शिखर 1 पर हो)। दाएँ: एक दौड़। सैकड़ों random nodes में से हर एक को 8 random candidate splits मिलते हैं। क्या entropy और Gini एक ही विजेता चुनते हैं?

第 07 节

多个 class 的 Gini —— 最大值

和 entropy 一样，最大的 Gini Impurity 会随着 class 的数量增加。最大 Gini 的公式是 (n−1)/n，出现在所有 class 可能性都相同的时候。

class 数量（n）	最大 Gini = (n−1)/n	计算示例（probability 相同）
2	0.500	每个 p=0.5：1−(0.5²+0.5²) = 1−0.5 = 0.500
3	0.667	每个 p=1/3：1−3·(1/3)² = 1−3·(1/9) = 1−1/3 = 0.667
4	0.750	每个 p=0.25：1−4·(0.25²) = 1−4·0.0625 = 1−0.25 = 0.750
5	0.800	每个 p=0.2：1−5·(0.2²) = 1−5·0.04 = 1−0.20 = 0.800
10	0.900	每个 p=0.1：1−10·(0.1²) = 1−10·0.01 = 1−0.10 = 0.900

第 08 节

Entropy 与 Gini —— 正面对比

📈 Entropy、Gini 与 misclassification 率（二分类，归一化到 0–1）

三条曲线都是对称的，都在 p = 0.5 达到顶点。Entropy（紫色）离开两端时上升得更陡 —— 在 p=0 和 p=1 附近，它对 probability 的小变化更敏感。Gini（蓝色）是一个更平滑的二次近似。misclassification 率（虚线）是直线，不够平滑 —— 很少使用，因为它缺少另外两个所具备的数学性质。

🔵 Gini Impurity（CART —— sklearn 默认）

性质	说明
公式	1 − Σ pᵢ²
二分类范围	0 到 0.5
n 个 class 的最大值	(n−1)/n
计算	快 —— 只做平方，不用 log
行为	倾向于更大、更均衡的划分
敏感度	在两端（接近 pure 的 node）不太敏感
使用者	CART、sklearn DecisionTree（默认）

🟢 Entropy / Information Gain（ID3、C4.5）

性质	说明
公式	−Σ pᵢ · log₂(pᵢ)
二分类范围	0 到 1.0
n 个 class 的最大值	log₂(n)
计算	较慢 —— 每个 node 的每个 class 都要算一次 log
行为	对细微的 class 变化更敏感
敏感度	在接近 pure 的 node 上更敏感
使用者	ID3、C4.5、sklearn 设置 criterion='entropy' 时

动手试试 —— Entropy vs Gini Race

左边：拖动 p，在任意位置比较三条曲线（Gini 和 misclassification 都乘了 2，所以三条曲线的最高点都是 1）。右边：一场比赛。几百个随机 node，每个都有 8 个随机的候选 split。entropy 和 Gini 会选出同一个赢家吗？

🏆 Entropy vs Gini RaceDifferent curves, nearly the same choices.

— entropy — Gini × 2 - - misclassification × 2

Most of the time both measures crown the same split. They only disagree when two candidate splits are almost equally good — which is why the final trees are usually the same or very close.

Section 09

The Bias Problem — and Gain Ratio (C4.5)

⚠️

ID3's Fatal Flaw: Information Gain Favours High-Cardinality Features

Imagine you add a "Day ID" column (D1, D2, … D14) to the weather dataset. Splitting on Day ID gives 14 child nodes, each with exactly 1 sample — perfectly pure! IG = 0.940 bits — maximum possible. But it's useless — it memorises training data and can't generalise. ID3 would always pick it. This is why Ross Quinlan upgraded ID3 to C4.5, which normalises IG by the feature's own entropy (its "split information").

Split Information

SplitInfo(S, A) = −Σ (|Sᵥ|/|S|) · log₂(|Sᵥ|/|S|)

Measures the entropy of the split itself — how many branches it creates and how evenly data is distributed across them. High-cardinality features have high SplitInfo.

Gain Ratio (C4.5)

GainRatio(S, A) = IG(S, A) / SplitInfo(S, A)

Normalises IG by the split's own entropy. A split into 14 pure nodes of 1 sample has SplitInfo = log₂(14) ≈ 3.81, so GainRatio = 0.940/3.81 ≈ 0.247. A useful 3-way split scores proportionally higher.

🧮 Gain Ratio — Outlook vs a Hypothetical "Day ID" Column

Outlook

IG = 0.246 bits
SplitInfo = −(5/14)·log₂(5/14) − (4/14)·log₂(4/14) − (5/14)·log₂(5/14)
= 0.531 + 0.464 + 0.531 = 1.577 bits
GainRatio = 0.246 / 1.577 = 0.156

Day ID (14 values)

IG = 0.940 bits (max — 14 pure leaf nodes)
SplitInfo = 14 × −(1/14)·log₂(1/14) = log₂(14) = 3.807 bits
GainRatio = 0.940 / 3.807 = 0.247
Still wins numerically here but much less dominant — and in real datasets Day ID would never appear as a feature for prediction.

Try It — The Cardinality Trap

Add a completely random feature to the weather data: each day gets one of k values by chance. The feature knows nothing about tennis. Move k and watch Information Gain get fooled badly, while Gain Ratio grows much more slowly.

सेक्शन 09

Bias की समस्या — और Gain Ratio (C4.5)

⚠️

ID3 की बड़ी कमी: Information Gain High-Cardinality Features को पसंद करता है

सोचिए, आप weather dataset में एक "Day ID" column (D1, D2, … D14) जोड़ देते हैं। Day ID पर split करने से 14 child nodes बनते हैं, हर एक में ठीक 1 sample — पूरी तरह pure! IG = 0.940 bits — सबसे ज़्यादा मुमकिन। पर यह बेकार है — यह training data को रट लेता है और नए data पर काम नहीं कर पाता। ID3 इसे हमेशा चुन लेगा। इसीलिए रॉस क्विनलन ने ID3 को सुधारकर C4.5 बनाया, जो IG को feature की अपनी entropy (उसकी "split information") से normalise करता है।

Split Information

SplitInfo(S, A) = −Σ (|Sᵥ|/|S|) · log₂(|Sᵥ|/|S|)

यह ख़ुद split की entropy नापती है — यह कितनी शाखाएँ बनाता है और data उनमें कितना बराबर बँटा है। High-cardinality features की SplitInfo ज़्यादा होती है।

Gain Ratio (C4.5)

GainRatio(S, A) = IG(S, A) / SplitInfo(S, A)

IG को split की अपनी entropy से normalise करता है। 1-1 sample वाले 14 pure nodes में split की SplitInfo = log₂(14) ≈ 3.81 होती है, इसलिए GainRatio = 0.940/3.81 ≈ 0.247। एक काम का 3-तरफ़ा split अनुपात में ज़्यादा score पाता है।

🧮 Gain Ratio — Outlook बनाम एक काल्पनिक "Day ID" Column

Outlook

IG = 0.246 bits
SplitInfo = −(5/14)·log₂(5/14) − (4/14)·log₂(4/14) − (5/14)·log₂(5/14)
= 0.531 + 0.464 + 0.531 = 1.577 bits
GainRatio = 0.246 / 1.577 = 0.156

Day ID (14 मान)

IG = 0.940 bits (अधिकतम — 14 pure leaf nodes)
SplitInfo = 14 × −(1/14)·log₂(1/14) = log₂(14) = 3.807 bits
GainRatio = 0.940 / 3.807 = 0.247
यहाँ संख्या में अब भी जीतता है, पर उसका दबदबा बहुत कम है — और असली datasets में Day ID कभी prediction के लिए feature के रूप में नहीं आएगा।

ख़ुद आज़माइए — Cardinality Trap

Weather data में एक पूरी तरह random feature जोड़िए: हर दिन को संयोग से k में से एक मान मिलता है। इस feature को tennis के बारे में कुछ नहीं पता। k को बदलिए और देखिए Information Gain बुरी तरह धोखा खाता है, जबकि Gain Ratio बहुत धीरे बढ़ता है।

第 09 节

偏向问题 —— 以及 Gain Ratio（C4.5）

⚠️

ID3 的致命缺陷：Information Gain 偏爱 high-cardinality 的 feature

想象你给天气 dataset 加上一列 “Day ID”（D1, D2, … D14）。按 Day ID split 会得到 14 个 child nodes，每个正好只有 1 个 sample —— 完全 pure！IG = 0.940 bits —— 达到最大可能值。但它毫无用处 —— 它只是背下了 training 数据，无法推广到新数据。ID3 每次都会选它。这就是为什么 Ross Quinlan 把 ID3 升级成了 C4.5，它用 feature 自己的 entropy（也就是它的 “split information”）来对 IG 做归一化。

Split Information

SplitInfo(S, A) = −Σ (|Sᵥ|/|S|) · log₂(|Sᵥ|/|S|)

衡量 split 本身的 entropy —— 它产生多少个分支，以及数据在这些分支之间分布得有多均匀。high-cardinality 的 feature 有很高的 SplitInfo。

Gain Ratio（C4.5）

GainRatio(S, A) = IG(S, A) / SplitInfo(S, A)

用 split 自己的 entropy 对 IG 做归一化。一个分成 14 个 pure node、每个只有 1 个 sample 的 split，SplitInfo = log₂(14) ≈ 3.81，所以 GainRatio = 0.940/3.81 ≈ 0.247。一个有用的三路 split 按比例会得分更高。

🧮 Gain Ratio —— Outlook 与假设的 “Day ID” 列对比

Outlook

IG = 0.246 bits
SplitInfo = −(5/14)·log₂(5/14) − (4/14)·log₂(4/14) − (5/14)·log₂(5/14)
= 0.531 + 0.464 + 0.531 = 1.577 bits
GainRatio = 0.246 / 1.577 = 0.156

Day ID（14 个值）

IG = 0.940 bits（最大值 —— 14 个 pure leaf node）
SplitInfo = 14 × −(1/14)·log₂(1/14) = log₂(14) = 3.807 bits
GainRatio = 0.940 / 3.807 = 0.247
在这里从数字上看它仍然赢了，但优势小多了 —— 而且在真实的 dataset 里， Day ID 永远不会被当作 prediction 用的 feature。

动手试试 —— Cardinality Trap

给天气数据加一个 完全随机 的 feature：每天随机得到 k 个值中的一个。这个 feature 对打网球一无所知。调整 k，看看 Information Gain 被骗得多厉害，而 Gain Ratio 涨得慢得多。

🪤 The Cardinality TrapMore values → more fake purity.

values k

this shuffle — the groups it makes (green = Yes, red = No):

— average IG — average gain ratio (300 shuffles per k) · dots = this shuffle

Section 10

Python Implementation — From Scratch and with sklearn

Manual Calculation — Entropy, Gini and Information Gain

import numpy as np

# ── Helper functions ──────────────────────────────────────────
def entropy(labels):
    """Shannon entropy of a list of class labels."""
    n = len(labels)
    if n == 0:
        return 0.0
    classes, counts = np.unique(labels, return_counts=True)
    probs = counts / n
    # Convention: 0 * log2(0) = 0
    return -np.sum(probs * np.log2(probs + 1e-12))

def gini(labels):
    """Gini impurity of a list of class labels."""
    n = len(labels)
    if n == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    probs = counts / n
    return 1 - np.sum(probs ** 2)

def information_gain(parent_labels, child_groups):
    """IG = H(parent) - weighted sum of H(children)."""
    n_parent = len(parent_labels)
    h_parent = entropy(parent_labels)
    weighted_child = sum(
        (len(group) / n_parent) * entropy(group)
        for group in child_groups
    )
    return h_parent - weighted_child

def gini_gain(parent_labels, child_groups):
    """Gini Gain = Gini(parent) - weighted Gini(children)."""
    n_parent = len(parent_labels)
    g_parent = gini(parent_labels)
    weighted_child = sum(
        (len(group) / n_parent) * gini(group)
        for group in child_groups
    )
    return g_parent - weighted_child

# ── Play Tennis Dataset ───────────────────────────────────────
y = np.array([0,0,1,1,1,0,1,0,1,1,1,1,1,0])  # 0=No, 1=Yes

# Outlook split: Sunny=[0,1,2,7,10] → indices → labels
sunny    = y[[0,1,7,8,10]]   # D1,D2,D8,D9,D11
overcast = y[[2,6,11,12]]    # D3,D7,D12,D13
rain     = y[[3,4,5,9,13]]   # D4,D5,D6,D10,D14

print("=== ENTROPY ===")
print(f"H(parent)  = {entropy(y):.4f}")
print(f"H(Sunny)   = {entropy(sunny):.4f}")
print(f"H(Overcast)= {entropy(overcast):.4f}")
print(f"H(Rain)    = {entropy(rain):.4f}")
print(f"IG(Outlook)= {information_gain(y, [sunny, overcast, rain]):.4f}")

print("\n=== GINI ===")
print(f"Gini(parent)  = {gini(y):.4f}")
print(f"Gini(Sunny)   = {gini(sunny):.4f}")
print(f"Gini(Overcast)= {gini(overcast):.4f}")
print(f"Gini(Rain)    = {gini(rain):.4f}")
print(f"Gini Gain(Outlook) = {gini_gain(y, [sunny, overcast, rain]):.4f}")

Output

=== ENTROPY === H(parent) = 0.9403 H(Sunny) = 0.9710 H(Overcast)= 0.0000 H(Rain) = 0.9710 IG(Outlook)= 0.2467 === GINI === Gini(parent) = 0.4592 Gini(Sunny) = 0.4800 Gini(Overcast)= 0.0000 Gini(Rain) = 0.4800 Gini Gain(Outlook) = 0.1167

Compare All Attributes at Once

import pandas as pd

# Full dataset as a DataFrame
df = pd.DataFrame({
    'Outlook' : ['Sunny','Sunny','Overcast','Rain','Rain','Rain',
                 'Overcast','Sunny','Sunny','Rain','Sunny',
                 'Overcast','Overcast','Rain'],
    'Temp'    : ['Hot','Hot','Hot','Mild','Cool','Cool','Cool',
                 'Mild','Cool','Mild','Mild','Mild','Hot','Mild'],
    'Humidity': ['High','High','High','High','Normal','Normal','Normal',
                 'High','Normal','Normal','Normal','High','Normal','High'],
    'Wind'    : ['Weak','Strong','Weak','Weak','Weak','Strong','Strong',
                 'Weak','Weak','Weak','Strong','Strong','Weak','Strong'],
    'Play'    : [0,0,1,1,1,0,1,0,1,1,1,1,1,0]
})

results = []
for col in ['Outlook', 'Temp', 'Humidity', 'Wind']:
    groups = [df[df[col] == v]['Play'].values for v in df[col].unique()]
    ig = information_gain(df['Play'].values, groups)
    gg = gini_gain(df['Play'].values, groups)
    results.append({'Attribute': col, 'Info Gain': ig, 'Gini Gain': gg})

summary = pd.DataFrame(results).sort_values('Info Gain', ascending=False)
print(summary.to_string(index=False, float_format='{:.4f}'.format))

Output

Attribute Info Gain Gini Gain Outlook 0.2467 0.1167 Humidity 0.1516 0.0926 Wind 0.0481 0.0286 Temp 0.0293 0.0183

sklearn: Switching Between Gini and Entropy

from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.preprocessing import OrdinalEncoder
import numpy as np

X_raw = df[['Outlook','Temp','Humidity','Wind']].values
y     = df['Play'].values

enc = OrdinalEncoder()
X   = enc.fit_transform(X_raw)

for criterion in ['gini', 'entropy']:
    dt = DecisionTreeClassifier(criterion=criterion, random_state=42)
    dt.fit(X, y)
    print(f"\n=== criterion='{criterion}' ===")
    print(export_text(dt, feature_names=['Outlook','Temp','Humidity','Wind']))
    print("Feature importances:")
    for f, imp in zip(['Outlook','Temp','Humidity','Wind'], dt.feature_importances_):
        print(f"  {f:<12} {imp:.4f}")

Output

✅

Both criteria build the same tree on this clean dataset

Gini and Entropy agree on Outlook as the root, Humidity on the Sunny branch, and Wind on the Rain branch. Temp gets zero importance from both. On real-world noisy data, they may diverge slightly — but the difference in final accuracy is almost always under 1%. Use Gini for speed (default), Entropy when theoretical correctness matters.

Section 11

Side-by-Side Split Quality Diagram

The diagram below shows the same parent node being split two ways. Split A is good — children are purer. Split B is poor — children are as mixed as the parent.

🌳 Good Split vs Poor Split — Entropy and Gini Before and After

Try It — The Threshold Finder

Real features are often numbers. Here are the same 14 days with the actual humidity and temperature values (the numeric version of this dataset). Drag the purple line to try a cut, or press Jump to best. The chart below shows the gain of every possible cut.

✅

इस साफ़ dataset पर दोनों criteria एक ही tree बनाते हैं

Gini और Entropy दोनों मानते हैं कि root Outlook है, Sunny शाखा पर Humidity है, और Rain शाखा पर Wind है। दोनों से Temp को zero importance मिलती है। असली दुनिया के noisy data पर ये थोड़ा अलग हो सकते हैं — पर final accuracy का अंतर लगभग हमेशा 1% से कम होता है। तेज़ी के लिए Gini (default) लीजिए, और जब theory के हिसाब से सही होना ज़रूरी हो तब Entropy।

सेक्शन 11

Split Quality का आमने-सामने Diagram

नीचे का diagram एक ही parent node को दो तरह से split होते दिखाता है। Split A अच्छा है — children ज़्यादा pure हैं। Split B कमज़ोर है — children उतने ही मिले-जुले हैं जितना parent।

🌳 अच्छा Split बनाम कमज़ोर Split — पहले और बाद की Entropy और Gini

ख़ुद आज़माइए — Threshold Finder

असली features अक्सर संख्याएँ होते हैं। यहाँ वही 14 दिन हैं, humidity और temperature के असली मानों के साथ (इस dataset का numeric रूप)। कोई cut आज़माने के लिए बैंगनी रेखा को खींचिए, या सबसे अच्छे पर जाओ दबाइए। नीचे का chart हर मुमकिन cut का gain दिखाता है।

🎯 The Threshold FinderTry every cut between neighbouring values. Keep the best.

Section 12

Common Pitfalls and How to Avoid Them

Comparing IG across different datasets

IG = 0.246 on one dataset vs IG = 0.246 on another does NOT mean the splits are equally good. The parent entropy differs. Always compare IG as a fraction of the parent entropy (i.e. Gain Ratio) for cross-dataset comparisons.

Using IG with high-cardinality features

ID3 / raw IG will always prefer features with many unique values (zip codes, IDs, timestamps) because more branches = lower weighted entropy. Use Gain Ratio (C4.5) or Gini to mitigate. Or simply exclude ID-like columns.

Confusing Entropy with Gini ranges

Entropy can exceed 1.0 for multi-class problems (max = log2(n)). Gini always stays below 1.0 (max = (n-1)/n). Comparing raw values across criteria is meaningless — always compare IG/Gain within the same criterion.

Forgetting the 0·log₂(0) convention

When a class has zero probability (pure node), the term 0·log₂(0) is mathematically undefined (0 × −∞). By convention it equals 0. This is why H(pure node) = 0, not undefined. Always add a small epsilon (1e-10) when implementing to avoid NaN.

Assuming Gini is always faster

Gini avoids log₂ but still iterates over all classes. For problems with very few classes (binary), the speed difference is negligible. For 100+ class problems, the logarithm cost becomes more significant — but so does the benefit of entropy's richer gradient.

Ignoring class imbalance effects

Both Entropy and Gini behave strangely when one class dominates (e.g. 99/1 split). A node with 990 negatives and 10 positives has low entropy (≈0.08 bits) — it looks almost pure. But those 10 positives might be critical (e.g. fraud cases). Use class_weight='balanced' or custom sample weights.

Section 13

Golden Rules

🎯 Entropy, Information Gain and Gini — Key Rules

Entropy and Gini measure the same thing differently. Both are zero for a pure node and maximum for a balanced node. Entropy uses logarithms (sensitive to small probability changes), Gini uses squares (faster computation). For binary classification, they produce nearly identical trees — the choice rarely matters in practice.

Information Gain is always non-negative. A split can never increase entropy in expectation — the weighted average of children can only be ≤ parent entropy. If a split gives IG = 0, it provides no useful information and should not be made.

Raw Information Gain is biased toward high-cardinality features. Always consider Gain Ratio (C4.5) or Gini when features have widely different numbers of unique values. This is one reason sklearn defaults to Gini — it is less susceptible to this bias than raw entropy IG.

Maximum entropy depends on the number of classes: log₂(n). Maximum Gini depends on the number of classes: (n−1)/n. Never compare impurity values across problems with different numbers of classes without normalising first.

These measures are only used during training — never during prediction. Once the tree is built, prediction is simply following branches based on feature values. Entropy and Gini are training-time search criteria, not runtime components. They add zero cost to inference.

A feature with zero Information Gain is always outcompeted. In the Play Tennis example, Temperature scored only 0.029 bits of IG and was never selected at any node. Zero (or near-zero) feature importance in a trained tree is the direct result of that feature never having the highest IG/Gini Gain at any split — a powerful signal for feature selection.

सेक्शन 12

आम ग़लतियाँ और उनसे कैसे बचें

अलग-अलग datasets में IG की तुलना करना

एक dataset पर IG = 0.246 और दूसरे पर IG = 0.246 का मतलब यह नहीं कि दोनों splits बराबर अच्छे हैं। Parent entropy अलग होती है। अलग-अलग datasets की तुलना के लिए, IG को हमेशा parent entropy के हिस्से के रूप में (यानी Gain Ratio) देखिए।

High-cardinality features के साथ IG का इस्तेमाल

ID3 / सीधा IG हमेशा उन features को पसंद करेगा जिनमें बहुत सारे अलग मान हों (zip codes, IDs, timestamps), क्योंकि ज़्यादा शाखाएँ = कम weighted entropy। इसे कम करने के लिए Gain Ratio (C4.5) या Gini इस्तेमाल कीजिए। या ID जैसे columns को बस हटा दीजिए।

Entropy और Gini के दायरों में उलझना

Multi-class समस्याओं में Entropy 1.0 से ज़्यादा हो सकती है (अधिकतम = log2(n))। Gini हमेशा 1.0 से नीचे रहती है (अधिकतम = (n-1)/n)। अलग-अलग criteria के सीधे मानों की तुलना का कोई मतलब नहीं — IG/Gain की तुलना हमेशा एक ही criterion के अंदर कीजिए।

0·log₂(0) वाला नियम भूल जाना

जब किसी class की probability zero हो (pure node), तो term 0·log₂(0) गणित में परिभाषित नहीं है (0 × −∞)। नियम के हिसाब से इसे 0 माना जाता है। इसीलिए H(pure node) = 0 है, अपरिभाषित नहीं। Code लिखते समय NaN से बचने के लिए हमेशा एक छोटा epsilon (1e-10) जोड़िए।

यह मान लेना कि Gini हमेशा तेज़ है

Gini log₂ से बचती है, पर फिर भी सभी classes पर चलती है। बहुत कम classes वाली समस्याओं (binary) में, रफ़्तार का अंतर न के बराबर है। 100+ classes वाली समस्याओं में logarithm की लागत ज़्यादा मायने रखती है — पर entropy के बेहतर gradient का फ़ायदा भी उतना ही बढ़ता है।

Class imbalance के असर को नज़रअंदाज़ करना

जब एक class बहुत ज़्यादा हो (जैसे 99/1 split), तो Entropy और Gini दोनों अजीब बर्ताव करते हैं। 990 negatives और 10 positives वाले node की entropy कम होती है (≈0.08 bits) — वह लगभग pure दिखता है। पर वे 10 positives बहुत ज़रूरी हो सकते हैं (जैसे fraud के cases)। class_weight='balanced' या अपने sample weights इस्तेमाल कीजिए।

सेक्शन 13

सुनहरे नियम

🎯 Entropy, Information Gain और Gini — मुख्य नियम

Entropy और Gini एक ही चीज़ को अलग तरीके से नापते हैं। दोनों pure node के लिए zero और बराबर बँटे (balanced) node के लिए अधिकतम होते हैं। Entropy logarithm इस्तेमाल करती है (probability के छोटे बदलावों पर संवेदनशील), Gini square इस्तेमाल करती है (तेज़ हिसाब)। Binary classification में ये लगभग एक जैसे trees बनाते हैं — असल में चुनाव शायद ही कभी मायने रखता है।

Information Gain कभी negative नहीं होता। औसत में कोई split entropy को कभी नहीं बढ़ा सकता — children का weighted average हमेशा ≤ parent entropy होता है। अगर किसी split से IG = 0 मिले, तो उससे कोई काम की जानकारी नहीं मिलती और वह split नहीं करना चाहिए।

सीधा Information Gain high-cardinality features की ओर झुका होता है। जब features में अलग मानों की गिनती बहुत अलग-अलग हो, तो हमेशा Gain Ratio (C4.5) या Gini पर विचार कीजिए। sklearn के default में Gini होने की एक वजह यह भी है — इस bias का असर उस पर सीधे entropy IG से कम होता है।

अधिकतम entropy classes की गिनती पर निर्भर है: log₂(n)। अधिकतम Gini भी classes की गिनती पर निर्भर है: (n−1)/n। अलग-अलग गिनती की classes वाली समस्याओं के impurity मानों की तुलना पहले normalise किए बिना कभी मत कीजिए।

ये पैमाने सिर्फ़ training में इस्तेमाल होते हैं — prediction में कभी नहीं। Tree बन जाने के बाद, prediction बस feature मानों के हिसाब से शाखाओं पर चलना है। Entropy और Gini training के समय के खोज वाले criteria हैं, runtime के हिस्से नहीं। Inference पर इनकी लागत zero है।

Zero Information Gain वाला feature हमेशा हार जाता है। Play Tennis उदाहरण में, Temperature को सिर्फ़ 0.029 bits IG मिला और वह किसी भी node पर नहीं चुना गया। Trained tree में zero (या लगभग zero) feature importance का सीधा मतलब है कि उस feature का IG/Gini Gain किसी भी split पर कभी सबसे ज़्यादा नहीं रहा — feature selection के लिए यह एक मज़बूत संकेत है।

第 12 节

常见错误以及如何避免

在不同的 dataset 之间比较 IG

一个 dataset 上 IG = 0.246，另一个 dataset 上 IG = 0.246，并不表示这两个 split 一样好。因为 parent entropy 不一样。跨 dataset 比较时，一定要把 IG 当作 parent entropy 的一个比例来比较（也就是 Gain Ratio）。

对 high-cardinality 的 feature 使用 IG

ID3 / 原始 IG 总是偏爱有很多不同值的 feature（邮政编码、ID、时间戳），因为分支越多 = 加权 entropy 越低。可以用 Gain Ratio（C4.5）或 Gini 来缓解。或者干脆去掉类似 ID 的列。

把 Entropy 和 Gini 的范围搞混

在多分类问题中，Entropy 可以超过 1.0（最大值 = log2(n)）。Gini 永远小于 1.0（最大值 = (n-1)/n）。跨 criterion 比较原始数值没有意义 —— 一定要在同一个 criterion 内比较 IG/Gain。

忘记 0·log₂(0) 的约定

当某个 class 的 probability 为零时（pure node），0·log₂(0) 这一项在数学上没有定义（0 × −∞）。按照约定，它等于 0。这就是为什么 H(pure node) = 0，而不是没有定义。写代码时，一定要加一个很小的 epsilon（1e-10）来避免 NaN。

以为 Gini 总是更快

Gini 不用 log₂，但仍然要遍历所有 class。对于 class 很少的问题（二分类），速度差别可以忽略。对于 100 个以上 class 的问题，log 的开销会变得更明显 —— 但 entropy 更丰富的梯度带来的好处也会更明显。

忽略 class 不平衡的影响

当一个 class 占绝大多数时（例如 99/1 split），Entropy 和 Gini 的表现都会很奇怪。一个有 990 个负例和 10 个正例的 node，entropy 很低（≈0.08 bits）—— 看起来几乎是 pure 的。但这 10 个正例可能非常关键（例如欺诈案例）。请使用 class_weight='balanced' 或自定义的 sample 权重。

第 13 节

黄金法则

🎯 Entropy、Information Gain 和 Gini —— 关键法则

Entropy 和 Gini 用不同的方法衡量同一件事。 对 pure node 两者都是零，对平衡的 node 两者都最大。 Entropy 用 log（对 probability 的小变化很敏感）， Gini 用平方（计算更快）。对于二分类 classification，它们建出的 tree 几乎一样 —— 实际中选哪个很少有影响。

Information Gain 永远不会是负数。 从期望上看，split 永远不会增加 entropy —— child 的 weighted average 只能 ≤ parent entropy。如果一个 split 的 IG = 0，它就没有提供任何有用的信息，不应该做这个 split。

原始的 Information Gain 偏向 high-cardinality 的 feature。 当各个 feature 不同值的数量相差很大时，一定要考虑 Gain Ratio（C4.5）或 Gini。这也是 sklearn 默认用 Gini 的原因之一 —— 它比原始的 entropy IG 更不容易受这种偏向影响。

最大 entropy 取决于 class 的数量：log₂(n)。 最大 Gini 也取决于 class 的数量：(n−1)/n。如果两个问题的 class 数量不同，没有先归一化，就永远不要比较它们的 impurity 值。

这些衡量方法只在 training 时使用 —— prediction 时从不使用。 tree 建好之后，prediction 就只是根据 feature 值沿着分支往下走。Entropy 和 Gini 是 training 时的搜索 criterion，不是运行时的组件。它们不会给推理增加任何开销。

Information Gain 为零的 feature 总会被比下去。 在 Play Tennis 的例子里，Temperature 的 IG 只有 0.029 bits，在任何 node 都没有被选中。在训练好的 tree 里，feature importance 为零（或接近零），直接说明这个 feature 在任何 split 上都没有拿到最高的 IG/Gini Gain —— 这是做 feature 选择的一个强有力的信号。

The Story: Why "Impurity" Matters

What Is Impurity? — The Core Concept

Try It — The Impurity Mixer

कहानी: "Impurity" क्यों ज़रूरी है

Impurity क्या है? — मूल concept

ख़ुद आज़माइए — Impurity Mixer

故事：为什么 “impurity” 很重要

什么是 impurity？—— 核心概念

动手试试 —— Impurity Mixer

Entropy — Disorder Measured in Bits

The Entropy Curve — Visualised

Step-by-Step Entropy Calculation — Weather Dataset

Try It — The Entropy Curve

Entropy — Bits में नापी गई गड़बड़ी

Entropy Curve — चित्र में

Entropy का Step-by-Step हिसाब — Weather Dataset

ख़ुद आज़माइए — Entropy Curve

Entropy —— 用 bits 来衡量混乱程度

Entropy 曲线 —— 画出来看看

一步一步计算 Entropy —— 天气 dataset

动手试试 —— Entropy Curve

Entropy for Multiple Classes

Try It — Multi-Class Entropy

कई Classes के लिए Entropy

ख़ुद आज़माइए — Multi-Class Entropy

多个 class 的 Entropy

动手试试 —— Multi-Class Entropy

Information Gain — Measuring Split Quality

Worked Example: Which Attribute Splits the Weather Data Best?

Try It — The Split Lab

Information Gain — Split की Quality नापना

हल किया हुआ उदाहरण: कौन-सा Attribute Weather Data को सबसे अच्छा Split करता है?

ख़ुद आज़माइए — Split Lab

Information Gain —— 衡量 split 的好坏

例题：哪个 attribute 最适合 split 天气数据？

动手试试 —— Split Lab

Gini Impurity — The CART Algorithm's Measure

Gini Values Across Class Distributions

Gini Calculation — Same Weather Dataset

Try It — The Random Label Game

Gini Impurity — CART Algorithm का पैमाना

अलग-अलग Class बँटवारों पर Gini के मान

Gini का हिसाब — वही Weather Dataset

ख़ुद आज़माइए — Random Label Game

Gini Impurity —— CART 算法的衡量方式

不同 class 分布下的 Gini 值

Gini 计算 —— 同一个天气 dataset

动手试试 —— Random Label Game

Gini for Multiple Classes — Maximum Values

Entropy vs Gini — Head-to-Head

Try It — Entropy vs Gini Race

कई Classes के लिए Gini — अधिकतम मान

Entropy vs Gini — आमने-सामने

ख़ुद आज़माइए — Entropy vs Gini Race

多个 class 的 Gini —— 最大值

Entropy 与 Gini —— 正面对比

动手试试 —— Entropy vs Gini Race

The Bias Problem — and Gain Ratio (C4.5)

Try It — The Cardinality Trap

Bias की समस्या — और Gain Ratio (C4.5)

ख़ुद आज़माइए — Cardinality Trap

偏向问题 —— 以及 Gain Ratio（C4.5）

动手试试 —— Cardinality Trap

Python Implementation — From Scratch and with sklearn

Manual Calculation — Entropy, Gini and Information Gain

Python Implementation — शुरू से, और sklearn के साथ

हाथ से हिसाब — Entropy, Gini और Information Gain

Python 实现 —— 从零写起，以及用 sklearn

手动计算 —— Entropy、Gini 和 Information Gain

Compare All Attributes at Once

सभी Attributes की एक साथ तुलना

一次比较所有 attribute

sklearn: Switching Between Gini and Entropy

sklearn: Gini और Entropy के बीच बदलना

sklearn：在 Gini 和 Entropy 之间切换

Side-by-Side Split Quality Diagram

Try It — The Threshold Finder

Split Quality का आमने-सामने Diagram

ख़ुद आज़माइए — Threshold Finder

split 好坏的并排对比图