Algoritma C4.5

Algoritma C4.5 merupakan algoritma klasifikasi pohon keputusan yang banyak digunakan karena memiliki kelebihan utama dari algoritma yang lainnya. Kelebihan algoritma C4.5 dapat menghasilkan pohon keputusan yang mudah diinterprestasikan, memiliki tingkat akurasi yang dapat diterima, efisien dalam menangani atribut bertipe diskret dan numeric (Han & Kamber, 2001). Dalam mengkonstruksi pohon, algoritma C4.5 membaca seluruh sampel data training dari storage dan memuatnya ke memori. Hal inilah yang menjadi salah satu kelemahan algoritma C4.5 dalam kategori skalabilitas karena hanya dapat digunakan jika data training dapat disimpan secara keseluruhan dan pada waktu yang bersamaan dimemori (Moertini, 2007).

Algoritma Classification version 4.5 atau biasa disebut C4.5 adalah pengembangan dari algoritma ID3. Oleh karena pengembangan tersebut, algoritma C4.5 mempunyai prinsip dasar kerja yang sama dengan algoritma ID3. Perbedaan utama C4.5 dari ID3 adalah:

1.    C4.5 dapat menangani atribut kontinyu dan diskrit.
2.    C4.5 dapat menangani training data dengan missing value.
3.    Hasil pohon keputusan C4.5 akan dipangkas setelah dibentuk.
4.    Pemilihan atribut yang dilakukan dengan menggunakan Gain Ratio.

Information gain pada ID3 lebih mengutamakan pengujian yang menghasilkan banyak keluaran. Dengan kata lain, atribut yang memiliki banyak nilailah yang dipilih sebagai splitting atribut. Sebagai contoh, pembagian terhadap atribut yang berfungsi sebagai unique identifier, seperti product_ID¸ akan menghasilkan keluaran dalam jumlah yang banyak, di mana setiap keluaran hanya terdiri dari satu tuple. Partisi semacam ini tentu saja bersifat pure, sehingga informasi yang dibutuhkan untuk mengklasifikasi D berdasarkan partisi seperti ini adalah sebesar Infoproduct_ID(D) = 0. Sebagai akibatnya, information gain yang dimiliki atribut product_ID menjadi maksimal. Padahal, jelas sekali terlihat bahwa partisi semacam ini tidaklah berguna.

Proses pemilihan atribut sebagai akar, didasarkan pada nilai gain tertinggi dari atribut-atribut yang ada.Untuk menghitung gain digunakan rumus seperti yang tertera berikut:

 

Keterangan:

S : Himpunan kasus
A : Atribut
n : Jumlah partisi atribut A
|Si| : Jumlah kasus pada partisi ke i
|S| : Jumlah kasus dalam S

Sebelum mendapatkan nilai Gain adalah dengan mencari nilai Entropy. Entropy digunakan untuk menentukan seberapa informatif sebuah masukan atribut untuk menghasilkan sebuah atribut. Rumus dasar dari Entropy adalah sebagai berikut:

Karena itu algoritma C4.5 yang merupakan suksesor dari ID3 menggunakan gain ratio untuk memperbaiki information gain, dengan rumus gain ratio:

Dimana:

S = ruang (data) sample yang digunakan untuk training.
A = atribut.
Gain(S,A) = information gain pada atribut A
SplitInfo(S,A) = split information pada atribut A

Atribut dengan nilai Gain Ratio tertinggi dipilih sebagai atribut test untuk simpul. Dengan gain adalah information gain. Pendekatan ini menerapkan normalisasi pada information gain dengan menggunakan apa yang disebut sebagai split information. SplitInfo menyatakan entropy atau informasi potensial dengan rumus:

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
Si = jumlah sample untuk atribut i
Secara umum Algoritma C4.5 untuk membangun pohon keputusan adalah sebagai berikut (Kusrini & Lutfi, 2009):
    a. Pilih atribut sebagai akar
    b. Buat cabang untuk masing-masing nilai
    c. Bagi kasus dalam cabang
    d. Ulangi proses untuk masing-masing cabang sampai semua kasus pada cabang memiliki kelas yang sama.


Daftar Pustaka

1. Han, J &Kamber, M., 2001a, Data Mining: Concepts and Techniques, Second Edition, Morgan Kauffman Publishers, USA
2. Moertini, V.S., 2007, Pengembangan Skalabilitas Algoritma Klasifikasi C4.5 Dengan Pendekatan Konsep Operator Relasi, Studi Kasus: Pra-pengolahan dan Klasifikasi Citra Batik, Disertasi, Program Studi Teknik Informatika, Institut Teknologi Bandung, Bandun
3. Kusrini&Lutfi, E.T., 2009, Algoritma Data Mining, PenerbitAndi, Yogyakarta.