Algoritma C4.5 dan Decision Tree: Hitung Entropy dan Gain Manual

Algoritma C4.5 membangun decision tree dengan cara milih atribut yang punya gain ratio tertinggi di tiap simpul. Hitungannya tiga tahap: entropy, information gain, lalu gain ratio.

C4.5 dibuat Ross Quinlan sebagai penerus ID3. Bedanya bukan cuma di rumus pemilihan atribut, tapi juga kemampuan nangani angka kontinu, nilai kosong, dan pemangkasan pohon.

Di bawah ini aku hitung semuanya pakai tangan, pakai data 12 pengajuan kredit UMKM. Angkanya sengaja kecil biar kamu bisa ngikutin tanpa kalkulator ilmiah.

Apa itu algoritma C4.5?

Algoritma C4.5 adalah metode klasifikasi yang menghasilkan pohon keputusan dari data berlabel. Tiap simpul pohon berisi pertanyaan tentang satu atribut, tiap cabang jawaban dari pertanyaan itu, dan tiap daun berisi kelas hasil prediksi. Kelebihannya, hasilnya bisa dibaca sebagai aturan jika-maka tanpa perlu ngerti matematikanya.

Buat kamu yang lagi milih metode buat proyek, C4.5 masuk kelompok klasifikasi. Kelompok metode yang lain aku bahas di metode data mining.

Rumus entropy, information gain, dan gain ratio

Tiga rumus ini yang dipakai berulang di tiap simpul.

Entropy ngukur seberapa campur aduk isi sebuah kumpulan data. Nilainya 0 kalau semua baris punya label sama, dan 1 kalau labelnya terbagi rata dua kelas.

Entropy(S) = -p1 * log2(p1) - p2 * log2(p2)

Information gain ngukur berapa banyak ketidakpastian yang hilang setelah data dipecah pakai satu atribut.

Gain(S, A) = Entropy(S) - jumlah( (|Sv| / |S|) * Entropy(Sv) )

Split information ngukur seberapa banyak dan seberapa merata atribut itu mecah data.

SplitInfo(S, A) = -jumlah( (|Sv| / |S|) * log2(|Sv| / |S|) )

Gain ratio hasil bagi dua angka terakhir. Ini yang dipakai C4.5 buat milih pemenang.

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

Data latihan: 12 pengajuan kredit UMKM

Dataset latihan ngulikdata bernama kredit_umkm berisi 12 pengajuan dengan tiga atribut dan satu label. Label yang diprediksi: status kredit setelah 12 bulan.

No	lama_usaha	catatan_keuangan	jaminan	status
1	kurang dari 2 tahun	nggak	ada	macet
2	kurang dari 2 tahun	nggak	nggak	macet
3	kurang dari 2 tahun	nggak	nggak	macet
4	kurang dari 2 tahun	ya	nggak	lancar
5	2 sampai 5 tahun	ya	ada	lancar
6	2 sampai 5 tahun	ya	ada	lancar
7	2 sampai 5 tahun	ya	ada	lancar
8	2 sampai 5 tahun	ya	ada	lancar
9	lebih dari 5 tahun	ya	ada	lancar
10	lebih dari 5 tahun	nggak	nggak	lancar
11	lebih dari 5 tahun	nggak	nggak	lancar
12	lebih dari 5 tahun	ya	nggak	macet

Total 12 baris: 8 lancar dan 4 macet.

Langkah 1: hitung entropy seluruh data

Proporsinya 8/12 lancar dan 4/12 macet.

p(lancar) = 8/12 = 0,6667
p(macet)  = 4/12 = 0,3333

Entropy(S) = -0,6667 * log2(0,6667) - 0,3333 * log2(0,3333)
           = -0,6667 * (-0,5850) - 0,3333 * (-1,5850)
           = 0,3900 + 0,5283
           = 0,9183

Angka 0,9183 ini titik awal. Semua atribut bakal dinilai dari seberapa banyak mereka nurunin angka tersebut.

Langkah 2: hitung gain tiap atribut

Atribut lama_usaha

Tiga nilai, masing-masing 4 baris.

kurang dari 2 tahun (4 baris): 1 lancar, 3 macet
  Entropy = -0,25*log2(0,25) - 0,75*log2(0,75)
          = 0,5000 + 0,3113 = 0,8113

2 sampai 5 tahun (4 baris): 4 lancar, 0 macet
  Entropy = 0 (semua labelnya sama)

lebih dari 5 tahun (4 baris): 3 lancar, 1 macet
  Entropy = 0,8113

Entropy gabungan = (4/12)*0,8113 + (4/12)*0 + (4/12)*0,8113
                 = 0,2704 + 0 + 0,2704 = 0,5409

Gain = 0,9183 - 0,5409 = 0,3774

Atribut catatan_keuangan

ya (7 baris): 6 lancar, 1 macet  -> Entropy = 0,5917
nggak (5 baris): 2 lancar, 3 macet -> Entropy = 0,9710

Entropy gabungan = (7/12)*0,5917 + (5/12)*0,9710
                 = 0,3452 + 0,4046 = 0,7498

Gain = 0,9183 - 0,7498 = 0,1685

Atribut jaminan

ada (6 baris): 5 lancar, 1 macet -> Entropy = 0,6500
nggak (6 baris): 3 lancar, 3 macet -> Entropy = 1,0000

Entropy gabungan = 0,5*0,6500 + 0,5*1,0000 = 0,8250

Gain = 0,9183 - 0,8250 = 0,0933

Langkah 3: ubah gain jadi gain ratio

Di sinilah C4.5 beda dari ID3. Gain dibagi split information dulu sebelum dibandingkan.

SplitInfo(lama_usaha) = -3 * (4/12) * log2(4/12) = 1,5850
SplitInfo(catatan)    = -(7/12)*log2(7/12) - (5/12)*log2(5/12) = 0,9799
SplitInfo(jaminan)    = -(6/12)*log2(6/12) - (6/12)*log2(6/12) = 1,0000

Atribut	Gain	SplitInfo	Gain Ratio
lama_usaha	0,3774	1,5850	0,2381
catatan_keuangan	0,1685	0,9799	0,1719
jaminan	0,0933	1,0000	0,0933

Perhatiin jaraknya. Pakai information gain, lama_usaha unggul lebih dari dua kali lipat dari catatan_keuangan. Pakai gain ratio, jaraknya nyusut jadi 0,2381 lawan 0,1719, gara-gara lama_usaha punya tiga nilai sementara catatan cuma dua.

Pemenangnya tetap lama_usaha, jadi dia jadi simpul akar.

Langkah 4: lanjutkan ke tiap cabang

Cabang 2 sampai 5 tahun udah murni, semuanya lancar. Cabang itu jadi daun, selesai.

Cabang kurang dari 2 tahun berisi baris 1 sampai 4 dengan entropy 0,8113. Dipecah pakai catatan_keuangan: nilai ya berisi baris 4 (lancar), nilai nggak berisi baris 1, 2, 3 (semuanya macet). Dua-duanya murni, gain-nya penuh 0,8113. Selesai juga.

Cabang lebih dari 5 tahun berisi baris 9 sampai 12 dengan entropy 0,8113. Dipecah pakai catatan_keuangan: nilai nggak berisi baris 10 dan 11 yang dua-duanya lancar, nilai ya berisi baris 9 dan 12 yang masih campur. Baris 9 dan 12 dipisah lagi pakai jaminan, dan langsung murni.

Pohon jadinya:

lama_usaha?
|- 2 sampai 5 tahun  -> LANCAR
|- kurang dari 2 tahun
|   |- catatan_keuangan = ya    -> LANCAR
|   |- catatan_keuangan = nggak -> MACET
|- lebih dari 5 tahun
    |- catatan_keuangan = nggak -> LANCAR
    |- catatan_keuangan = ya
        |- jaminan = ada   -> LANCAR
        |- jaminan = nggak -> MACET

Aturan keempat kelihatan aneh: usaha lama tanpa catatan keuangan kok diprediksi lancar. Itu tanda pohon kekecilan datanya. Cabang tersebut cuma ditopang 2 baris, jadi aturannya belum tentu berlaku di data baru. Di C4.5 beneran, cabang kayak gini yang bakal kena pemangkasan.

Hitung entropy di spreadsheet

Kalau kamu mau ngecek hitungan tanpa Python, spreadsheet cukup. Taruh jumlah kelas positif di B2 dan negatif di C2.

=IFERROR(-B2/(B2+C2)*LOG(B2/(B2+C2),2) - C2/(B2+C2)*LOG(C2/(B2+C2),2), 0)

IFERROR dipasang buat nangani kelompok murni, karena log dari nol bikin error. Buat ngitung jumlah baris per kombinasi atribut, COUNTIFS paling cepat.

Kode Python untuk decision tree

Sekarang bandingin hasil hitung tangan tadi sama library.

import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text

data = pd.DataFrame({
    "lama_usaha": ["<2","<2","<2","<2","2-5","2-5","2-5","2-5",">5",">5",">5",">5"],
    "catatan":    ["nggak","nggak","nggak","ya","ya","ya","ya","ya","ya","nggak","nggak","ya"],
    "jaminan":    ["ada","nggak","nggak","nggak","ada","ada","ada","ada","ada","nggak","nggak","nggak"],
    "status":     ["macet","macet","macet","lancar","lancar","lancar",
                   "lancar","lancar","lancar","lancar","lancar","macet"]
})

X = pd.get_dummies(data.drop(columns="status"))
y = data["status"]

model = DecisionTreeClassifier(criterion="entropy", random_state=42)
model.fit(X, y)

print(export_text(model, feature_names=list(X.columns)))

Satu hal yang harus kamu tau: DecisionTreeClassifier di scikit-learn memakai varian CART, bukan C4.5. Dia nggak ngitung gain ratio dan cabangnya selalu dua per simpul. Pilihan criterion="entropy" cuma nyamain rumus ketidakpastiannya. Rinciannya ada di dokumentasi scikit-learn.

Jadi kalau skripsimu nulis "algoritma C4.5" tapi kodenya pakai scikit-learn, sebutkan bedanya di bab metodologi. Penguji yang teliti bakal nanya.

Kesalahan umum waktu ngitung C4.5 manual

1. Pakai log basis 10. Entropy pakai basis 2. Di spreadsheet tulis LOG(nilai;2), bukan LOG(nilai).
2. Lupa bobot proporsi. Entropy tiap cabang harus dikali jumlah baris cabang dibagi total baris sebelum dijumlahkan.
3. Ngitung gain doang terus ngaku pakai C4.5. Tanpa gain ratio, itu ID3.
4. Masukin kolom id sebagai atribut. Kolom unik selalu menang di information gain dan bikin pohon nggak berguna. Ini persis alasan gain ratio dibikin.
5. Nggak bersihin data dulu. Kategori yang ditulis beda bikin cabang pecah palsu. Cek dulu kualitas data sebelum ngitung.

FAQ

Apa bedanya ID3 dan C4.5?

ID3 milih atribut pakai information gain, C4.5 pakai gain ratio. C4.5 juga bisa nangani atribut angka kontinu, nilai yang hilang, dan punya tahap pemangkasan pohon. ID3 nggak punya ketiganya.

Kenapa entropy dihitung pakai log basis 2?

Basis 2 bikin satuannya jadi bit, dan satu bit mewakili satu pertanyaan ya atau nggak. Data yang terbagi rata dua kelas punya entropy persis 1 bit.

Kapan gain ratio lebih baik dari information gain?

Waktu ada atribut dengan banyak nilai unik. Information gain selalu kasih nilai besar ke kolom kayak id_transaksi, karena tiap kelompoknya otomatis murni. Gain ratio motong nilai atribut semacam itu.

Apakah scikit-learn punya implementasi C4.5?

Nggak persis. DecisionTreeClassifier memakai varian CART, jadi dia nggak menghitung gain ratio dan cabangnya selalu dua per simpul.

Berapa data minimal buat decision tree yang masuk akal?

Buat latihan manual, 10 sampai 15 baris cukup. Buat model yang dipakai beneran, usahakan tiap daun punya minimal 20 sampai 30 baris biar aturannya nggak kebetulan.

Penutup

Tiga hal yang perlu nempel. Entropy ngukur campur aduknya data, gain ngukur pengurangannya setelah dipecah, gain ratio nghukum atribut yang terlalu banyak nilai.

Coba ulang hitungannya pakai data kamu sendiri, minimal 12 baris, tiga atribut. Hitung tangan dulu, baru bandingin sama Python.

Lanjut baca: KDD vs CRISP-DM vs SEMMA buat nyusun alur proyeknya dari awal sampai dipakai orang.