Decision Tree C4.5: Contoh Perhitungan Entropy, Gain Ratio, dan Pohon Keputusan

Tutorial ini membahas Decision Tree C4.5 dan contoh perhitungannya untuk membentuk pohon keputusan dari data latih. Contoh kasus yang digunakan adalah klasifikasi kelayakan kredit berdasarkan penghasilan, pekerjaan, jaminan, dan riwayat kredit.

Perhitungan dilakukan mulai dari entropy, information gain, split information, gain ratio, pemilihan atribut terbaik, pembentukan cabang pohon, hingga klasifikasi data baru menggunakan pohon keputusan yang terbentuk.

---

Daftar Isi

• Pengertian Decision Tree C4.5
• Rumus Entropy, Gain, Split Information, dan Gain Ratio
• #01 Data Latih
• #02 Menghitung Entropy Total
• #03 Menghitung Gain Ratio Setiap Atribut
• #04 Menentukan Root Node
• #05 Perhitungan Detail Setiap Cabang
• #06 Pohon Keputusan Akhir
• #07 Klasifikasi Data Uji
• Ringkasan
• FAQ C4.5
• Referensi
• Source Code C4.5

---

Pengertian Decision Tree C4.5

C4.5 adalah algoritma klasifikasi berbasis decision tree yang mengembangkan konsep ID3. Salah satu karakteristik penting C4.5 adalah penggunaan Gain Ratio untuk membantu memilih atribut pemisah pada setiap node.

Pada setiap tahap, data dibagi berdasarkan atribut yang memiliki nilai Gain Ratio terbaik. Proses dilanjutkan pada setiap cabang sampai data pada cabang tersebut sudah berada dalam satu kelas atau tidak ada atribut yang dapat digunakan lagi.

Rumus Entropy, Gain, Split Information, dan Gain Ratio

Entropy

Entropy mengukur tingkat ketidakmurnian atau keberagaman kelas pada sebuah kumpulan data.

$$ Entropy(S) = -\sum_{i=1}^{n} p_i \log_2(p_i) $$

Information Gain

Information Gain menunjukkan pengurangan entropy setelah data dibagi berdasarkan atribut tertentu.

$$ Gain(S,A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v) $$

Split Information

Split Information mengukur seberapa besar data terbagi ke dalam nilai-nilai sebuah atribut.

$$ SplitInfo(S,A) = -\sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \left( \frac{|S_v|}{|S|} \right) $$

Gain Ratio

C4.5 menggunakan Gain Ratio untuk membantu menentukan atribut yang dipilih sebagai node.

$$ GainRatio(S,A) = \frac{Gain(S,A)} {SplitInfo(S,A)} $$

#01 Data Latih

Contoh menggunakan 12 data latih dengan kelas target Kelayakan.

#02 Menghitung Entropy Total

Sebelum melihat hasil perhitungan atribut, entropy seluruh data dihitung terlebih dahulu. Pada data contoh terdapat:

• Tidak Layak = 5 data
• Layak = 7 data

Dengan 12 data, contoh perhitungannya:

$$ Entropy(S) = -\left( \frac{5}{12} \log_2\frac{5}{12} + \frac{7}{12} \log_2\frac{7}{12} \right) = 0.9799 $$

Jadi entropy total data adalah 0.9799.

#03 Menghitung Gain Ratio Setiap Atribut

Setelah entropy total diperoleh, masing-masing atribut diuji sebagai kandidat pemisah. Sebelum melihat tabel seluruh atribut, berikut contoh perhitungan menggunakan atribut Jaminan.

Contoh Entropy Setiap Nilai Jaminan

Jaminan = Tidak memiliki 6 data (Tidak Layak: 5) (Layak: 1) . Entropy = 0.65.

Jaminan = Ada memiliki 6 data (Layak: 6) . Entropy = 0.

Entropy setelah data dibagi berdasarkan Jaminan adalah:

(6/12 × 0.65) + (6/12 × 0) = 0.325

Maka Information Gain:

0.9799 - 0.325 = 0.6549

Split Information atribut Jaminan = 1.

Sehingga Gain Ratio:

0.6549 / 1 = 0.6549

Perhitungan yang sama dilakukan pada seluruh atribut.

#04 Menentukan Root Node

Berdasarkan perhitungan di atas, atribut dengan Gain Ratio terbesar adalah Jaminan dengan nilai 0.6549. Oleh karena itu, atribut tersebut dipilih sebagai root node.

Selanjutnya data dipisahkan berdasarkan setiap nilai Jaminan. Cabang yang seluruh datanya sudah memiliki kelas yang sama menjadi leaf, sedangkan cabang yang masih memiliki lebih dari satu kelas harus dihitung kembali.

#05 Perhitungan Detail Setiap Cabang

Setelah root node diperoleh, perhitungan harus dilanjutkan pada setiap cabang yang masih mengandung lebih dari satu kelas. Bagian berikut menampilkan seluruh perhitungan node dan cabang secara berurutan sampai setiap jalur menghasilkan leaf pada pohon keputusan.

Tahap 1: Root Node

Data pada node ini berjumlah 12 dengan entropy 0.9799. Distribusi kelas: Tidak Layak = 5, Layak = 7.

Perhitungan entropy node: -(5/12 × log2(5/12)) + -(7/12 × log2(7/12)) = 0.9799

Perhitungan Atribut Penghasilan

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Penghasilan.

Entropy setelah split: (4/12 × 1) + (4/12 × 1) + (4/12 × 0.8113) = 0.9371

Information Gain: 0.9799 - 0.9371 = 0.0428

Split Information: -(4/12 × log2(4/12)) + -(4/12 × log2(4/12)) + -(4/12 × log2(4/12)) = 1.585

Gain Ratio: 0.0428 / 1.585 = 0.027

Perhitungan Atribut Pekerjaan

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Pekerjaan.

Entropy setelah split: (4/12 × 1) + (4/12 × 1) + (4/12 × 0.8113) = 0.9371

Information Gain: 0.9799 - 0.9371 = 0.0428

Split Information: -(4/12 × log2(4/12)) + -(4/12 × log2(4/12)) + -(4/12 × log2(4/12)) = 1.585

Gain Ratio: 0.0428 / 1.585 = 0.027

Perhitungan Atribut Jaminan (Terpilih)

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Jaminan.

Entropy setelah split: (6/12 × 0.65) + (6/12 × 0) = 0.325

Information Gain: 0.9799 - 0.325 = 0.6549

Split Information: -(6/12 × log2(6/12)) + -(6/12 × log2(6/12)) = 1

Gain Ratio: 0.6549 / 1 = 0.6549

Perhitungan Atribut Riwayat

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Riwayat.

Entropy setelah split: (3/12 × 0) + (9/12 × 0.7642) = 0.5732

Information Gain: 0.9799 - 0.5732 = 0.4067

Split Information: -(3/12 × log2(3/12)) + -(9/12 × log2(9/12)) = 0.8113

Gain Ratio: 0.4067 / 0.8113 = 0.5013

Perbandingan Kandidat Atribut

Setelah seluruh atribut pada node Root dihitung, hasilnya dirangkum sebagai berikut.

Gain Ratio terbesar adalah atribut Jaminan dengan nilai 0.6549. Maka atribut Jaminan digunakan sebagai node pada jalur ini.

Hasil Pembagian Cabang Jaminan

Setelah node dipilih, data dibagi berdasarkan nilai Jaminan. Cabang dengan satu kelas langsung menjadi leaf, sedangkan cabang yang masih memiliki lebih dari satu kelas harus dihitung lagi.

Pohon Keputusan Sementara Setelah Tahap Ini

Berdasarkan tabel pembagian cabang di atas, bentuk pohon sementara setelah Jaminan dipilih pada jalur Root adalah:

Keterangan: Belum dihitung berarti cabang tersebut masih memiliki lebih dari satu kelas dan akan dihitung pada tahap berikutnya.

---

Tahap 2: Cabang Jaminan = Tidak

Data pada node ini berjumlah 6 dengan entropy 0.65. Distribusi kelas: Tidak Layak = 5, Layak = 1.

Perhitungan entropy node: -(5/6 × log2(5/6)) + -(1/6 × log2(1/6)) = 0.65

Perhitungan Atribut Penghasilan (Terpilih)

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Penghasilan.

Entropy setelah split: (2/6 × 0) + (2/6 × 0) + (2/6 × 1) = 0.3333

Information Gain: 0.65 - 0.3333 = 0.3167

Split Information: -(2/6 × log2(2/6)) + -(2/6 × log2(2/6)) + -(2/6 × log2(2/6)) = 1.585

Gain Ratio: 0.3167 / 1.585 = 0.1998

Perhitungan Atribut Pekerjaan

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Pekerjaan.

Entropy setelah split: (3/6 × 0.9183) + (2/6 × 0) + (1/6 × 0) = 0.4591

Information Gain: 0.65 - 0.4591 = 0.1909

Split Information: -(3/6 × log2(3/6)) + -(2/6 × log2(2/6)) + -(1/6 × log2(1/6)) = 1.4591

Gain Ratio: 0.1909 / 1.4591 = 0.1308

Perhitungan Atribut Riwayat

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Riwayat.

Entropy setelah split: (3/6 × 0) + (3/6 × 0.9183) = 0.4591

Information Gain: 0.65 - 0.4591 = 0.1909

Split Information: -(3/6 × log2(3/6)) + -(3/6 × log2(3/6)) = 1

Gain Ratio: 0.1909 / 1 = 0.1909

Perbandingan Kandidat Atribut

Setelah seluruh atribut pada node Jaminan = Tidak dihitung, hasilnya dirangkum sebagai berikut.

Gain Ratio terbesar adalah atribut Penghasilan dengan nilai 0.1998. Maka atribut Penghasilan digunakan sebagai node pada jalur ini.

Hasil Pembagian Cabang Penghasilan

Setelah node dipilih, data dibagi berdasarkan nilai Penghasilan. Cabang dengan satu kelas langsung menjadi leaf, sedangkan cabang yang masih memiliki lebih dari satu kelas harus dihitung lagi.

Pohon Keputusan Sementara Setelah Tahap Ini

Berdasarkan tabel pembagian cabang di atas, bentuk pohon sementara setelah Penghasilan dipilih pada jalur Jaminan = Tidak adalah:

Keterangan: Belum dihitung berarti cabang tersebut masih memiliki lebih dari satu kelas dan akan dihitung pada tahap berikutnya.

---

Leaf: Jaminan = Tidak → Penghasilan = Rendah

Cabang ini memiliki 2 data dengan entropy 0. Semua data pada cabang sudah berada dalam satu kelas. Hasil akhir cabang adalah kelas Tidak Layak.

---

Leaf: Jaminan = Tidak → Penghasilan = Sedang

Cabang ini memiliki 2 data dengan entropy 0. Semua data pada cabang sudah berada dalam satu kelas. Hasil akhir cabang adalah kelas Tidak Layak.

---

Tahap 3: Cabang Jaminan = Tidak → Penghasilan = Tinggi

Data pada node ini berjumlah 2 dengan entropy 1. Distribusi kelas: Tidak Layak = 1, Layak = 1.

Perhitungan entropy node: -(1/2 × log2(1/2)) + -(1/2 × log2(1/2)) = 1

Perhitungan Atribut Pekerjaan (Terpilih)

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Pekerjaan.

Entropy setelah split: (1/2 × 0) + (1/2 × 0) = 0

Information Gain: 1 - 0 = 1

Split Information: -(1/2 × log2(1/2)) + -(1/2 × log2(1/2)) = 1

Gain Ratio: 1 / 1 = 1

Perhitungan Atribut Riwayat

Sebelum melihat nilai akhirnya, berikut rincian pembagian data berdasarkan setiap nilai pada atribut Riwayat.

Entropy setelah split: (1/2 × 0) + (1/2 × 0) = 0

Information Gain: 1 - 0 = 1

Split Information: -(1/2 × log2(1/2)) + -(1/2 × log2(1/2)) = 1

Gain Ratio: 1 / 1 = 1

Perbandingan Kandidat Atribut

Setelah seluruh atribut pada node Jaminan = Tidak → Penghasilan = Tinggi dihitung, hasilnya dirangkum sebagai berikut.

Gain Ratio terbesar adalah atribut Pekerjaan dengan nilai 1. Maka atribut Pekerjaan digunakan sebagai node pada jalur ini.

Hasil Pembagian Cabang Pekerjaan

Setelah node dipilih, data dibagi berdasarkan nilai Pekerjaan. Cabang dengan satu kelas langsung menjadi leaf, sedangkan cabang yang masih memiliki lebih dari satu kelas harus dihitung lagi.

Pohon Keputusan Sementara Setelah Tahap Ini

Berdasarkan tabel pembagian cabang di atas, bentuk pohon sementara setelah Pekerjaan dipilih pada jalur Jaminan = Tidak → Penghasilan = Tinggi adalah:

Keterangan: Belum dihitung berarti cabang tersebut masih memiliki lebih dari satu kelas dan akan dihitung pada tahap berikutnya.

---

Leaf: Jaminan = Tidak → Penghasilan = Tinggi → Pekerjaan = Kontrak

Cabang ini memiliki 1 data dengan entropy 0. Semua data pada cabang sudah berada dalam satu kelas. Hasil akhir cabang adalah kelas Layak.

---

Leaf: Jaminan = Tidak → Penghasilan = Tinggi → Pekerjaan = Tetap

Cabang ini memiliki 1 data dengan entropy 0. Semua data pada cabang sudah berada dalam satu kelas. Hasil akhir cabang adalah kelas Tidak Layak.

---

Leaf: Jaminan = Ada

Cabang ini memiliki 6 data dengan entropy 0. Semua data pada cabang sudah berada dalam satu kelas. Hasil akhir cabang adalah kelas Layak.

---

Setelah seluruh cabang di atas selesai dihitung, setiap jalur sudah berakhir pada node lanjutan atau leaf. Dari hasil tersebut, pohon keputusan akhir dapat disusun seperti pada bagian berikut.

#06 Pohon Keputusan Akhir

Setelah proses pemilihan atribut dilakukan secara berulang pada setiap cabang, diperoleh struktur pohon keputusan berikut.

Setiap jalur dari root menuju leaf dapat dibaca sebagai aturan keputusan. Leaf menunjukkan kelas akhir Layak atau Tidak Layak.

#07 Klasifikasi Data Uji

Setelah pohon keputusan terbentuk, data baru dapat diklasifikasikan dengan mengikuti cabang sesuai nilai atributnya.

Jalur Keputusan

Sebelum melihat hasil akhir, berikut jalur yang dilewati data uji pada pohon:

1. Jaminan = Tidak
2. Penghasilan = Tinggi
3. Pekerjaan = Kontrak

Jalur tersebut berakhir pada leaf Layak. Dengan demikian, hasil klasifikasi data uji adalah Layak.

Ringkasan

Algoritma C4.5 membentuk pohon keputusan dengan menghitung entropy, Information Gain, Split Information, dan Gain Ratio. Atribut dengan Gain Ratio terbaik dipilih sebagai node, kemudian proses diulangi pada cabang yang masih memiliki lebih dari satu kelas. Pohon yang terbentuk selanjutnya dapat digunakan untuk mengklasifikasikan data baru.

FAQ C4.5

Apa perbedaan ID3 dan C4.5?

ID3 dikenal menggunakan Information Gain untuk memilih atribut, sedangkan C4.5 mengembangkan pendekatan tersebut dengan Gain Ratio dan mendukung kemampuan tambahan seperti penanganan atribut kontinu.

Apa fungsi entropy?

Entropy digunakan untuk mengukur tingkat ketidakmurnian kelas pada data. Nilai entropy semakin kecil ketika data semakin homogen.

Mengapa C4.5 menggunakan Gain Ratio?

Gain Ratio menyesuaikan Information Gain dengan Split Information sehingga membantu mengurangi kecenderungan memilih atribut yang membagi data ke terlalu banyak nilai.

Kapan cabang pohon berhenti?

Cabang dapat berhenti ketika seluruh data pada cabang sudah berada dalam kelas yang sama atau tidak ada atribut yang dapat digunakan untuk pemisahan lebih lanjut.

Apakah C4.5 dapat menggunakan data numerik?

Ya. C4.5 dapat menangani atribut kontinu dengan mencari titik pemisah atau threshold. Contoh pada artikel ini menggunakan atribut kategorikal agar perhitungan manual lebih mudah dipahami.

---

Referensi

1. Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
2. Han, J., Kamber, M. & Pei, J. (2012). Data Mining: Concepts and Techniques, 3rd Edition. Morgan Kaufmann.

---

Source Code Metode C4.5

Berikut adalah beberapa source code yang menggunakan algoritma Decision Tree C4.5, baik berbasis web maupun desktop.

• Source Code Data Mining Klasifikasi Algoritma C4.5 PHP
• Source Code Data Mining Klasifikasi Algoritma C45 CodeIgniter
• Source Code Sistem Pakar Metode C45 Forward Chaining PHP

Ada yang Ditanyakan?

Jika anda masih ada kesulitan atau kekeliruan tentang penjelasan metode di atas, bisa menghubungi kami lewat WA/Email sesuai halaman Kontak.

Jika ingin memiliki file excel dari metode di atas bisa melihat cara download di halaman Download.

Jika ingin memiliki source code dari metode di atas, baik berbasis web maupun desktop bisa melihat daftar harga donasi di halaman Daftar Source Code.

Donasi ini digunakan oleh penulis untuk membayar server dan membeli kopi sembari membuat tutorial Metode/Algoritma lainnya :).