Algoritma ID3: Contoh Perhitungan Entropy dan Information Gain Lengkap

Algoritma ID3 (Iterative Dichotomiser 3) adalah algoritma pembentukan decision tree yang memilih atribut terbaik berdasarkan nilai Information Gain. Atribut dengan Information Gain terbesar dipilih sebagai node pada pohon keputusan.

Tutorial ini menggunakan contoh klasifikasi Play Tennis dengan 14 data latih. Perhitungan dilakukan mulai dari entropy dataset, entropy setiap nilai atribut, Information Gain, menentukan root node, menghitung cabang berikutnya, hingga membentuk pohon keputusan akhir.

ID3 cocok digunakan untuk mempelajari konsep dasar decision tree karena proses pemilihan atributnya relatif mudah dihitung secara manual. Namun, ID3 juga memiliki keterbatasan, misalnya cenderung memilih atribut dengan banyak nilai dan pada bentuk dasarnya lebih cocok untuk atribut kategorikal.

---

Daftar Isi

• Pengertian Algoritma ID3
• Konsep Decision Tree pada ID3
• Istilah Penting pada ID3
• Rumus Entropy
• Rumus Information Gain
• Cara Kerja Algoritma ID3
• Contoh Kasus Perhitungan ID3
  • #01 Menentukan Atribut
  • #02 Menyiapkan Data Latih
  • #03 Menghitung Entropy Total
  • #04 Menghitung Gain Outlook
  • #05 Menghitung Gain Temperature
  • #06 Menghitung Gain Humidity
  • #07 Menghitung Gain Wind
  • #08 Menentukan Root Node
  • #09 Menghitung Cabang Outlook = Sunny
  • #10 Menghitung Cabang Outlook = Rain
  • #11 Membentuk Pohon Keputusan
  • #12 Membentuk Rule IF-THEN
  • #13 Prediksi Data Baru
• Kondisi Berhenti pada ID3
• Pseudocode ID3
• ID3 vs C4.5
• ID3 vs CART
• Kelebihan dan Kekurangan ID3
• Kapan ID3 Cocok Digunakan?
• Kesalahan Umum Implementasi
• Ringkasan
• FAQ ID3
• Referensi
• Source Code ID3

---

Pengertian Algoritma ID3

ID3 adalah algoritma decision tree yang dikembangkan oleh J. Ross Quinlan. Algoritma ini membangun pohon secara top-down dengan memilih atribut yang paling mampu memisahkan kelas pada setiap node.

Ukuran yang digunakan ID3 adalah:

• Entropy untuk mengukur ketidakmurnian data.
• Information Gain untuk mengukur seberapa besar suatu atribut mengurangi entropy.

Secara sederhana:

Data Latih
    ↓
Hitung Entropy
    ↓
Hitung Information Gain setiap atribut
    ↓
Pilih Gain terbesar
    ↓
Buat Node
    ↓
Bagi Data
    ↓
Ulangi pada setiap cabang
    ↓
Decision Tree

---

Konsep Decision Tree pada ID3

Decision tree terdiri dari:

Misalnya pohon sederhana:

Outlook
├── Sunny
│   └── Humidity
│       ├── High   → No
│       └── Normal → Yes
├── Overcast → Yes
└── Rain
    └── Wind
        ├── Weak   → Yes
        └── Strong → No

Pada contoh ini, Outlook menjadi root karena mempunyai Information Gain terbesar pada dataset awal.

---

Istilah Penting pada ID3

---

Rumus Entropy

Entropy untuk dataset \(S\):

Keterangan:

• \(S\) = dataset,
• \(c\) = jumlah kelas,
• \(p_i\) = proporsi data pada kelas ke-\(i\).

Untuk dua kelas Yes dan No:

Jika seluruh data berada pada satu kelas:

Artinya node sudah murni.

Jika dua kelas memiliki proporsi yang sama:

untuk kasus dua kelas.

---

Rumus Information Gain

Information Gain atribut \(A\):

Keterangan:

• \(S\) = dataset,
• \(A\) = atribut,
• \(v\) = nilai pada atribut \(A\),
• \(S_v\) = subset data yang memiliki nilai \(v\).

Atribut dengan Gain terbesar dipilih sebagai node.

---

Cara Kerja Algoritma ID3

Secara umum ID3 bekerja melalui langkah berikut:

1. Hitung entropy dataset.
2. Hitung entropy setiap subset nilai atribut.
3. Hitung Information Gain seluruh atribut kandidat.
4. Pilih atribut dengan Gain terbesar sebagai node.
5. Bagi data berdasarkan nilai atribut tersebut.
6. Jika suatu cabang hanya memiliki satu kelas, jadikan leaf.
7. Jika cabang masih memiliki lebih dari satu kelas, ulangi proses pada atribut yang tersisa.
8. Proses berhenti setelah seluruh cabang menghasilkan kelas atau tidak ada atribut yang dapat digunakan lagi.

---

Contoh Kasus Perhitungan ID3

Contoh berikut menggunakan data Play Tennis.

Target:

PLAY = Yes / No

#01 Menentukan Atribut

Atribut yang digunakan:

---

#02 Menyiapkan Data Latih

Digunakan 14 data latih:

Jumlah kelas:

Yes = 9
No  = 5
Total = 14

---

#03 Menghitung Entropy Total

Proporsi kelas:

Maka:

Jadi entropy dataset awal adalah:

---

#04 Menghitung Gain Outlook

Atribut Outlook memiliki tiga nilai:

Sunny
Overcast
Rain

Outlook = Sunny

Terdapat 5 data:

Yes = 2
No  = 3

Entropy:

Outlook = Overcast

Terdapat 4 data:

Yes = 4
No  = 0

Karena semua data berada pada kelas Yes:

Outlook = Rain

Terdapat 5 data:

Yes = 3
No  = 2

Weighted entropy:

Information Gain:

Ringkasan:

---

#05 Menghitung Gain Temperature

Atribut Temperature memiliki:

Hot
Mild
Cool

Temperature = Hot

Total = 4
Yes = 2
No = 2

Temperature = Mild

Total = 6
Yes = 4
No = 2

Temperature = Cool

Total = 4
Yes = 3
No = 1

Weighted entropy:

Gain:

Ringkasan:

---

#06 Menghitung Gain Humidity

Humidity memiliki dua nilai:

High
Normal

Humidity = High

Total = 7
Yes = 3
No = 4

Humidity = Normal

Total = 7
Yes = 6
No = 1

Weighted entropy:

Gain:

Ringkasan:

---

#07 Menghitung Gain Wind

Wind memiliki:

Weak
Strong

Wind = Weak

Total = 8
Yes = 6
No = 2

Wind = Strong

Total = 6
Yes = 3
No = 3

Weighted entropy:

Gain:

Ringkasan:

---

#08 Menentukan Root Node

Sebelum melihat tabel perbandingan, nilai yang sudah dihitung adalah:

Gain Outlook     = 0.246750
Gain Temperature = 0.029223
Gain Humidity    = 0.151836
Gain Wind        = 0.048127

Hasil:

Information Gain terbesar adalah:

Maka:

Outlook dipilih sebagai root node.

Pohon sementara:

Outlook
├── Sunny     → belum murni
├── Overcast  → Yes
└── Rain      → belum murni

Cabang Overcast langsung menjadi leaf karena seluruh data pada subset tersebut memiliki kelas Yes.

---

#09 Menghitung Cabang Outlook = Sunny

Subset Sunny:

Jumlah:

Yes = 2
No  = 3

Entropy subset Sunny:

Sekarang hitung Gain dari atribut yang tersisa.

Gain Temperature pada Sunny

Subset Temperature:

• Hot: 2 No → entropy 0
• Mild: 1 Yes, 1 No → entropy 1
• Cool: 1 Yes → entropy 0

Weighted entropy:

Gain:

Gain Humidity pada Sunny

Humidity High:

3 data
Semua No

Humidity Normal:

2 data
Semua Yes

Weighted entropy:

Gain:

Gain Wind pada Sunny

Wind Weak:

Yes = 1
No = 2

Wind Strong:

Yes = 1
No = 1

Weighted entropy:

Gain:

Perbandingan:

Gain terbesar:

Maka pada cabang Sunny, node berikutnya adalah Humidity.

Hasil:

Sunny
└── Humidity
    ├── High   → No
    └── Normal → Yes

---

#10 Menghitung Cabang Outlook = Rain

Subset Rain:

Jumlah:

Yes = 3
No  = 2

Entropy:

Gain Temperature pada Rain

Temperature Mild:

Yes = 2
No = 1

Temperature Cool:

Yes = 1
No = 1

Weighted entropy:

Gain:

Gain Humidity pada Rain

Humidity High:

Yes = 1
No = 1

Humidity Normal:

Yes = 2
No = 1

Weighted entropy:

Gain:

Gain Wind pada Rain

Wind Weak:

Yes = 3
No = 0

Wind Strong:

Yes = 0
No = 2

Weighted entropy:

Gain:

Perbandingan:

Gain terbesar adalah:

Maka node pada cabang Rain adalah Wind.

Hasil:

Rain
└── Wind
    ├── Weak   → Yes
    └── Strong → No

---

#11 Membentuk Pohon Keputusan

Setelah seluruh cabang dihitung, decision tree akhir:

Outlook
├── Sunny
│   └── Humidity
│       ├── High
│       │   └── No
│       └── Normal
│           └── Yes
│
├── Overcast
│   └── Yes
│
└── Rain
    └── Wind
        ├── Weak
        │   └── Yes
        └── Strong
            └── No

Semua leaf sudah murni sehingga proses pembentukan pohon selesai.

---

#12 Membentuk Rule IF-THEN

Decision tree dapat diubah menjadi rule.

Rule 1

IF Outlook = Sunny
AND Humidity = High
THEN Play = No

Rule 2

IF Outlook = Sunny
AND Humidity = Normal
THEN Play = Yes

Rule 3

IF Outlook = Overcast
THEN Play = Yes

Rule 4

IF Outlook = Rain
AND Wind = Weak
THEN Play = Yes

Rule 5

IF Outlook = Rain
AND Wind = Strong
THEN Play = No

---

#13 Prediksi Data Baru

Misalnya terdapat data baru:

Penelusuran:

Outlook = Sunny
↓
periksa Humidity
↓
Humidity = Normal
↓
Play = Yes

Jadi hasil klasifikasi:

Perhatikan bahwa Temperature dan Wind tidak perlu diperiksa pada jalur tersebut karena pohon yang terbentuk hanya membutuhkan Outlook dan Humidity untuk cabang Sunny.

---

Kondisi Berhenti pada ID3

Pembentukan cabang pada ID3 dapat berhenti ketika:

1. Seluruh data pada node memiliki kelas yang sama.
2. Tidak ada atribut tersisa untuk digunakan.
3. Tidak ada data pada suatu cabang.
4. Implementasi menggunakan kondisi berhenti tambahan.

Jika tidak ada atribut tersisa tetapi kelas masih bercampur, salah satu strategi adalah menggunakan kelas mayoritas pada node tersebut.

---

Pseudocode ID3

Pseudocode sederhana:

function ID3(data, attributes, target):

    if semua data memiliki kelas yang sama:
        return leaf(kelas)

    if attributes kosong:
        return leaf(kelas mayoritas)

    hitung entropy(data)

    for each attribute:
        hitung information_gain(data, attribute)

    best_attribute =
        attribute dengan gain terbesar

    tree = node(best_attribute)

    for each value pada best_attribute:

        subset =
            data dengan best_attribute = value

        if subset kosong:
            child = leaf(kelas mayoritas data)
        else:
            child = ID3(
                subset,
                attributes - best_attribute,
                target
            )

        tambahkan child ke tree

    return tree

---

ID3 vs C4.5

C4.5 dikembangkan sebagai pengembangan dari ID3.

ID3 cocok untuk memahami dasar decision tree, sedangkan C4.5 menambahkan beberapa mekanisme untuk mengatasi keterbatasan ID3.

---

ID3 vs CART

---

Kelebihan dan Kekurangan ID3

Kelebihan ID3

• Konsep relatif mudah dipahami.
• Perhitungan entropy dan gain dapat dilakukan manual.
• Menghasilkan rule yang mudah dibaca.
• Cocok untuk data kategorikal.
• Dapat memilih atribut secara otomatis.
• Baik untuk memahami dasar decision tree.

Kekurangan ID3

• Information Gain cenderung memilih atribut dengan banyak nilai.
• Tidak memiliki mekanisme pruning seperti pengembangan decision tree yang lebih baru.
• Data numerik kontinu memerlukan penanganan atau diskretisasi pada implementasi dasar.
• Dapat mengalami overfitting.
• Missing value memerlukan penanganan tambahan.
• Hasil pohon dapat berubah jika data latih berubah.

---

Kapan ID3 Cocok Digunakan?

ID3 cocok digunakan ketika:

• target berupa kelas kategorikal;
• atribut sebagian besar kategorikal;
• dibutuhkan decision tree yang mudah dijelaskan;
• jumlah data tidak terlalu besar;
• penelitian membutuhkan perhitungan entropy dan Information Gain;
• atau ingin mempelajari konsep dasar algoritma decision tree.

Contoh penerapan:

• klasifikasi kelayakan,
• prediksi keputusan sederhana,
• klasifikasi pelanggan,
• klasifikasi risiko,
• klasifikasi kondisi,
• sistem pendukung klasifikasi,
• dan pembentukan rule dari data kategorikal.

---

Kesalahan Umum Implementasi

1. Menggunakan log basis 10

Entropy ID3 umumnya menggunakan:

bukan log basis 10.

2. Salah menghitung bobot subset

Weighted entropy harus dikalikan proporsi jumlah data subset:

3. Memilih Gain terkecil

ID3 memilih atribut dengan Information Gain terbesar.

4. Menggunakan kembali atribut yang sudah menjadi node

Pada ID3 kategorikal standar, atribut yang sudah digunakan pada suatu jalur dikeluarkan dari kandidat berikutnya.

5. Menganggap entropy tinggi berarti node bagus

ID3 memilih split yang paling banyak mengurangi entropy, sehingga yang dibandingkan adalah Information Gain.

6. Tidak memeriksa leaf yang sudah murni

Jika seluruh data pada subset memiliki kelas sama, tidak perlu melakukan split lagi.

7. Menganggap ID3 sama dengan C4.5

C4.5 merupakan pengembangan dari ID3 dan menggunakan Gain Ratio serta fitur tambahan.

---

Ringkasan

Pada contoh Play Tennis:

Yes = 9
No  = 5

Entropy dataset:

Information Gain awal:

Karena Outlook memiliki Gain terbesar, Outlook menjadi root.

Pada cabang:

Outlook = Sunny

Humidity memiliki Gain terbesar:

Sedangkan pada:

Outlook = Rain

Wind memiliki Gain terbesar:

Pohon akhir:

Outlook
├── Sunny → Humidity
│   ├── High   → No
│   └── Normal → Yes
├── Overcast → Yes
└── Rain → Wind
    ├── Weak   → Yes
    └── Strong → No

---

FAQ ID3

Apa kepanjangan ID3?

ID3 adalah singkatan dari Iterative Dichotomiser 3.

Apa fungsi algoritma ID3?

ID3 digunakan untuk membentuk decision tree untuk masalah klasifikasi.

Apa itu entropy pada ID3?

Entropy adalah ukuran ketidakmurnian atau ketidakpastian kelas pada suatu dataset.

Apa itu Information Gain?

Information Gain adalah pengurangan entropy setelah dataset dibagi berdasarkan suatu atribut.

Atribut mana yang dipilih ID3?

ID3 memilih atribut dengan Information Gain terbesar.

Kapan sebuah node menjadi leaf?

Node menjadi leaf ketika seluruh data pada node memiliki kelas yang sama atau kondisi berhenti lain tercapai.

Apakah ID3 dapat menggunakan data numerik?

ID3 dasar lebih cocok untuk data kategorikal. Data numerik biasanya perlu didiskretisasi atau menggunakan pengembangan algoritma yang menangani split numerik.

Apakah ID3 menggunakan pruning?

Pruning bukan bagian utama dari algoritma ID3 klasik. C4.5 menyediakan mekanisme pruning yang lebih lengkap.

Apa perbedaan ID3 dan C4.5?

ID3 menggunakan Information Gain, sedangkan C4.5 menggunakan Gain Ratio dan menambahkan dukungan yang lebih baik untuk atribut kontinu, missing value, dan pruning.

Apakah ID3 termasuk supervised learning?

Ya. ID3 menggunakan data latih yang sudah memiliki label kelas.

Apakah ID3 termasuk data mining?

Ya. ID3 banyak digunakan sebagai algoritma klasifikasi pada data mining dan machine learning.

Mengapa atribut Outlook menjadi root pada contoh?

Karena Outlook memiliki Information Gain terbesar, yaitu sekitar 0.246750.

Apakah decision tree dapat diubah menjadi rule?

Bisa. Setiap jalur dari root menuju leaf dapat diterjemahkan menjadi rule IF-THEN.

Apa kelemahan Information Gain?

Information Gain dapat cenderung memilih atribut dengan banyak nilai unik. Salah satu pendekatan untuk mengurangi bias tersebut adalah Gain Ratio pada C4.5.

---

Referensi

1. Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1, 81–106.
2. Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
3. Han, J., Kamber, M., & Pei, J. (2011). Data Mining: Concepts and Techniques. Third Edition. Morgan Kaufmann.

---

Source Code ID3

Berikut source code yang menggunakan algoritma ID3 pada RumahSourceCode.

Source Code Sistem Pakar Metode ID3 PHP

Rp600,000

Source Code Data Mining Klasifikasi Metode ID3 PHP

Rp600,000