Algoritma C4.5

Algoritma C4.5 merupakan algoritma penjabaran pohon keputusan yang banyak dipakai alasannya yaitu mempunyai kelebihan utama dari algoritma yang lainnya. Kelebihan algoritma C4.5 sanggup menghasilkan pohon keputusan yang gampang diinterprestasikan, mempunyai tingkat akurasi yang sanggup diterima, efisien dalam menangani atribut bertipe diskret dan numeric (Han & Kamber, 2001). Dalam mengkonstruksi pohon, algoritma C4.5 membaca seluruh sampel data pembinaan dari storage dan memuatnya ke memori. Hal inilah yang menjadi salah satu kelemahan algoritma C4.5 dalam kategori skalabilitas alasannya yaitu hanya sanggup dipakai jikalau data pembinaan sanggup disimpan secara keseluruhan dan pada waktu yang bersamaan dimemori (Moertini, 2007).

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

1.    C4.5 sanggup menangani atribut kontinyu dan diskrit.
2.    C4.5 sanggup menangani pembinaan data dengan missing value.
3.    Hasil pohon keputusan C4.5 akan dipangkas sesudah dibentuk.
4.    Pemilihan atribut yang dilakukan dengan memakai Gain Ratio.

Information gain pada ID3 lebih mengutamakan pengujian yang menghasilkan banyak keluaran. Dengan kata lain, atribut yang mempunyai banyak nilailah yang dipilih sebagai splitting atribut. Sebagai contoh, pembagian terhadap atribut yang berfungsi sebagai unique identifier, ibarat 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 info yang diperlukan untuk mengklasifikasi D menurut partisi ibarat ini yaitu sebesar Infoproduct_ID(D) = 0. Sebagai akibatnya, information gain yang dimiliki atribut product_ID menjadi maksimal. Padahal, terang 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 dipakai rumus ibarat yang tertera berikut:

 

Keterangan:

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

Sebelum mendapat nilai Gain yaitu dengan mencari nilai Entropy. Entropy dipakai untuk memilih seberapa informatif sebuah masukan atribut untuk menghasilkan sebuah atribut. Rumus dasar dari Entropy yaitu sebagai berikut:

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

Dimana:

S = ruang (data) sample yang dipakai 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 yaitu information gain. Pendekatan ini menerapkan normalisasi pada information gain dengan memakai apa yang disebut sebagai split information. SplitInfo menyatakan entropy atau info potensial dengan rumus:

Dimana:
S = ruang (data) sample yang dipakai untuk training.
A = atribut.
Si = jumlah sample untuk atribut i
Secara umum Algoritma C4.5 untuk membangun pohon keputusan yaitu sebagai berikut (Kusrini & Lutfi, 2009):
    a. Pilih atribut sebagai akar
    b. Buat cabang untuk masing-masing nilai
    c. Bagi masalah dalam cabang
    d. Ulangi proses untuk masing-masing cabang hingga semua masalah pada cabang mempunyai 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.