Membongkar Rahasia Klasifikasi Data: Bedah Tuntas Contoh Soal Algoritma C4.5 dan Pohon Keputusan

Dalam dunia Data Mining, kemampuan untuk mengklasifikasikan data dan memprediksi hasil di masa depan adalah inti dari banyak aplikasi, mulai dari prediksi kelayakan kredit hingga diagnosis medis. Salah satu algoritma paling populer dan efektif yang digunakan untuk tugas ini adalah Algoritma C4.5, yang merupakan evolusi dari algoritma ID3.

Algoritma C4.5 bekerja dengan membangun Pohon Keputusan (Decision Tree) dari sekumpulan data pelatihan. Keputusan tentang simpul (node) mana yang akan dipilih sebagai akar pohon ditentukan oleh perhitungan statistik yang disebut Gain Ratio, sebuah peningkatan dari metrik Information Gain yang digunakan oleh pendahulunya.

Artikel ini akan memandu Anda melalui langkah-langkah kerja Algoritma C4.5 secara detail, menyajikan contoh soal komprehensif, dan menyingkap setiap perhitungan matematika yang mendasarinya (Entropy, Information Gain, dan Gain Ratio).

baca juga: Panduan Praktis Biar Kariermu Ngebut Jadi Spatial Computing Engineer

I. Dasar Konseptual Algoritma C4.5

Algoritma C4.5 dirancang oleh Ross Quinlan pada tahun 1993 sebagai perbaikan dari ID3. Keunggulan utamanya adalah:

1. Menangani Atribut Berkelanjutan (Continuous): C4.5 dapat membagi data numerik menjadi rentang diskrit (thresholds).
2. Menangani Nilai Hilang (Missing Values): C4.5 dapat memperhitungkan data yang tidak lengkap.
3. Menggunakan Gain Ratio: Metrik ini mengatasi bias pada Information Gain yang cenderung memilih atribut dengan jumlah nilai (distinct values) yang banyak.
4. Pruning: C4.5 menyertakan mekanisme pemangkasan pohon untuk mengurangi overfitting.

Tujuan utama dari C4.5 adalah menemukan atribut yang paling efektif dalam membagi data menjadi sub-himpunan yang murni (homogen) sehubungan dengan variabel target (kelas keputusan).

II. Pilar Matematika C4.5

Pembangunan pohon keputusan oleh C4.5 didasarkan pada tiga metrik utama:

A. Entropy (Entropi)

Entropy mengukur tingkat ketidakmurnian (impurity) atau ketidakpastian dalam sekumpulan data. Jika semua data berada dalam satu kelas yang sama, entropi bernilai nol (murni). Jika data terbagi rata (paling tidak pasti), entropi bernilai satu (maksimal).

$$\text{Entropy}(S) = \sum_{i=1}^{c} (-P_i \cdot \log_2(P_i))$$

Di mana:

• $S$: Himpunan kasus (dataset).
• $c$: Jumlah kelas (keputusan).
• $P_i$: Proporsi kasus kelas $i$ terhadap total kasus $S$.

B. Information Gain (Perolehan Informasi)

Gain mengukur seberapa banyak informasi yang diperoleh (penurunan entropi) jika kita memilih atribut tertentu sebagai simpul. Atribut dengan Gain tertinggi adalah kandidat terbaik.

$$\text{Gain}(S, A) = \text{Entropy}(S) – \sum_{v \in \text{Values}(A)} \left( \frac{|S_v|}{|S|} \cdot \text{Entropy}(S_v) \right)$$

Di mana:

• $A$: Atribut yang akan diuji.
• $\text{Values}(A)$: Nilai-nilai unik dari atribut $A$.
• $S_v$: Sub-himpunan kasus untuk nilai $v$ dari atribut $A$.

C. Gain Ratio (Rasio Perolehan)

C4.5 menggunakan Gain Ratio untuk menormalkan Gain dan menghindari bias terhadap atribut dengan banyak nilai unik.

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

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

Atribut dengan Gain Ratio tertinggi dipilih sebagai simpul pemisah (akar atau cabang).

III. Contoh Soal Komprehensif: Prediksi Kelayakan Kredit

Sebuah bank ingin memprediksi apakah seorang nasabah LAYAK atau TIDAK LAYAK mendapatkan pinjaman berdasarkan riwayat data historis.

Data Pelatihan (14 Sampel):

Total Sampel ($|S|=14$):

• LAYAK ($P$): 9
• TIDAK LAYAK ($N$): 5

Diminta: Tentukan atribut yang paling optimal sebagai Node Akar pertama dalam Pohon Keputusan menggunakan Algoritma C4.5.

IV. Penyelesaian Algoritma C4.5

Langkah 1: Hitung Entropy Total (Dataset S)

$$\text{Entropy}(S) = \left( – \frac{9}{14} \cdot \log_2 \left( \frac{9}{14} \right) \right) + \left( – \frac{5}{14} \cdot \log_2 \left( \frac{5}{14} \right) \right)$$

$$\text{Entropy}(S) = (-0.643 \cdot (-0.638)) + (-0.357 \cdot (-1.485))$$

$$\text{Entropy}(S) = 0.409 + 0.530 = \mathbf{0.939}$$

Langkah 2: Hitung Gain dan Gain Ratio untuk Setiap Atribut

A. Atribut: Riwayat Kredit

1. Hitung Gain (S, Riwayat Kredit):

$$\text{Gain} = 0.939 – \left[ \left(\frac{6}{14} \cdot 0.000\right) + \left(\frac{4}{14} \cdot 0.000\right) + \left(\frac{4}{14} \cdot 0.811\right) \right]$$

$$\text{Gain} = 0.939 – [0 + 0 + 0.232] = \mathbf{0.707}$$

2. Hitung SplitInfo (S, Riwayat Kredit):

$$\text{SplitInfo} = – \left[ \left(\frac{6}{14} \log_2 \frac{6}{14}\right) + \left(\frac{4}{14} \log_2 \frac{4}{14}\right) + \left(\frac{4}{14} \log_2 \frac{4}{14}\right) \right]$$

$$\text{SplitInfo} = – [(-0.428 \cdot -1.222) + (-0.286 \cdot -1.807) + (-0.286 \cdot -1.807)]$$

$$\text{SplitInfo} = – [0.523 + 0.517 + 0.517] = \mathbf{1.557}$$

3. Hitung Gain Ratio (S, Riwayat Kredit):

$$\text{Gain Ratio} = \frac{0.707}{1.557} = \mathbf{0.454}$$

B. Atribut: Penghasilan

1. Hitung Gain (S, Penghasilan):

$$\text{Gain} = 0.939 – \left[ \left(\frac{6}{14} \cdot 0.918\right) + \left(\frac{8}{14} \cdot 0.954\right) \right]$$

$$\text{Gain} = 0.939 – [0.393 + 0.545] = \mathbf{0.001}$$

2. Hitung SplitInfo (S, Penghasilan):

$$\text{SplitInfo} = – \left[ \left(\frac{6}{14} \log_2 \frac{6}{14}\right) + \left(\frac{8}{14} \log_2 \frac{8}{14}\right) \right] = \mathbf{0.985}$$

3. Hitung Gain Ratio (S, Penghasilan):

$$\text{Gain Ratio} = \frac{0.001}{0.985} = \mathbf{0.001}$$

C. Atribut: Jaminan

1. Hitung Gain (S, Jaminan):

$$\text{Gain} = 0.939 – \left[ \left(\frac{8}{14} \cdot 0.544\right) + \left(\frac{6}{14} \cdot 0.918\right) \right]$$

$$\text{Gain} = 0.939 – [0.311 + 0.393] = \mathbf{0.235}$$

2. Hitung SplitInfo (S, Jaminan):

$$\text{SplitInfo} = – \left[ \left(\frac{8}{14} \log_2 \frac{8}{14}\right) + \left(\frac{6}{14} \log_2 \frac{6}{14}\right) \right] = \mathbf{0.985}$$

3. Hitung Gain Ratio (S, Jaminan):

$$\text{Gain Ratio} = \frac{0.235}{0.985} = \mathbf{0.238}$$

Langkah 3: Pilih Node Akar

Kita membandingkan nilai Gain Ratio tertinggi dari ketiga atribut:

Kesimpulan: Atribut Riwayat Kredit memiliki Gain Ratio tertinggi (0.454). Oleh karena itu, Riwayat Kredit akan dipilih sebagai Node Akar pertama dalam Pohon Keputusan.

baca juga: Rektor Universitas Teknokrat Indonesia Nasrullah Yusuf Lepas Atlet Pekan Olahraga Mahasiswa Nasional XIX Jawa Tengah, Bawa Nama Baik Kampus Sang Juara

V. Membangun Cabang Lanjutan dan Aturan Keputusan

Setelah memilih Riwayat Kredit sebagai akar, proses diulangi secara rekursif pada setiap cabangnya:

1. Cabang “Baik”: Semua 6 kasus adalah LAYAK. Cabang ini menjadi Node Daun (Leaf Node) dengan keputusan akhir.
2. Cabang “Buruk”: Semua 4 kasus adalah TIDAK LAYAK. Cabang ini menjadi Node Daun dengan keputusan akhir.
3. Cabang “Sedang”: Ada 4 kasus (3 LAYAK, 1 TIDAK LAYAK). Kasus ini masih “tidak murni” (Entropy $0.811$). Perhitungan C4.5 harus diulangi pada 4 kasus ini menggunakan atribut sisa (Penghasilan dan Jaminan).

Jika proses dilanjutkan hingga semua cabang murni, pohon keputusan akan menghasilkan serangkaian aturan (rules), misalnya:

$$\text{IF Riwayat Kredit} = \text{Baik} \rightarrow \text{Keputusan} = \text{LAYAK}$$

$$\text{IF Riwayat Kredit} = \text{Buruk} \rightarrow \text{Keputusan} = \text{TIDAK LAYAK}$$

$$\text{IF Riwayat Kredit} = \text{Sedang AND Jaminan} = \text{Ada} \rightarrow \text{Keputusan} = \text{LAYAK}$$

penulis:laurashintiarengganis