Algoritma C4.5

Algoritma C4.5

Algoritma C4.5 adalah hasil dari pengembangan algoritma ID3 (Iterative Dichotomiser) yang dikembangkan oleh Quinlan [16]. Algoritma ini digunakan untuk membangun sebuah pohon keputusan yang mudah dimengerti, fleksibel, dan menarik karena dapat divisualisasikan dalam bentuk gambar [17]. Sebelumnya diakhir tahun 1970 sampai awal tahun 1980 J. Ross Quinlan, seorang peneliti dibidang machine learning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Kalau ID3, pengukuran seleksi atribut ditentukan oleh Information Gain,  sedangkan C4.5 pengukuran seleksi atribut ditentukan oleh GainRatio [16].

Algoritma C4.5 atau pohon keputusan mirip sebuah pohon dimana terdapat node internal (bukan daun) yang mendeskripsikan atribut-atribut, setiap cabang menggambarkan hasil dari atribut yang diuji, dan setiap daun menggambarkan kelas. Pohon keputusan dengan mudah dapat dikonversi ke aturan klasifikasi. Secara umum keputusan pengklasifikasi pohon memiliki akurasi yang baik, namun keberhasilan penggunaan tergantung pada data yang akan diolah. Decision tree merupakan salah satu metode klasifikasi yang menggunakan representasi struktur pohon (tree) di mana setiap node merepresentasikan atribut, cabangnya merepresentasikan nilai dari atribut, dan daun merepresentasikan kelas. Node yang paling atas dari decision tree disebut sebagai root.  Pada decision tree terdapat 3 jenis node, yaitu: 

a.       Root Node, merupakan node paling atas, pada node ini tidak ada input dan bisa tidak mempunyai output atau mempunyai output lebih dari satu.

b.      Internal Node , merupakan node percabangan, pada node ini hanya terdapat satu input dan mempunyai output minimal dua.

c.       Leaf node atau terminal node , merupakan node akhir, pada node ini hanya terdapat satu input dan tidak mempunyai output.

Pohon keputusan bekerja mulai dari akar paling atas, jika diberikan sejumlah data uji, misalnya X dimana kelas dari data X belum diketahui, maka pohon keputusan akan menelusuri mulai dari akar sampai node dan setiap nilai dari atribut sesuai data X diuji apakah sesuai dengan aturan pohon keputusan, kemudian pohon keputusan akan memprediksi kelas dari tupel X.

 Telah dijelaskan diatas bahwa C4.5 adalah successor atau penerus dari ID3, oleh karena itu rumus C4.5 untuk mengukur pemilihan atribut juga menyempurnakan dari ID3.

Langkah-langkah untuk membuat sebuah pohon keputusan algoritma C4.5 yang merupakan pengembangan dari ID3 tersebut, seperti di bawah ini [16]:

1.      Mempersiapkan data training, data training yaitu data yang diambil dari data histori yang pernah terjadi sebelumnya atau disebut data masa lalu dan sudah dikelompokan dalam kelas-kelas tertentu.

2.      Menentukan akar pohon. Akar pohon ditentukan dengan cara menghitung GainRatio tertinggi dari masing-masing atribut. Sebelum menghitung GainRatio, terlebih dahulu menghitung Total Entropy sebelum dicari masing-masing Entropy class, adapun rumus mencari Entropy seperti di bawah ini:

Keterangan:

S = Himpunan kasus

n = jumlah partisi S

pi = proporsi dari S_i terhadap S

Dimana log₂pi dapat dihitung dengan cara:

(2)

3.      Menghitung nilai GainRatio sebagai akar pohon, tetapi sebelumnya menghitung Gain dan SplitEntropy (SplitInfo), rumus untuk menghitung Gain seperti dibawah ini:

(3)

(4)

Rumus untuk menghitung SplitEntropy, seperti di bawah ini:

Rumus untuk menghitung GainRatio, dibawah ini:

(5)

Keterangan:

S = Himpunan Kasus

A = Atribut

n = jumlah partisi atribut A

|S_i| = jumlah kasus pada partisi ke-i

|S| = jumlah kasus dalam S

4.      Ulangi langkah ke-2 dan ke-3 hingga semua tupel terpartisi

5.      Proses partisi pohon keputusan akan berhenti disaat:

a.       Semua tupel dalam node N mendapatkan kelas yang sama

b.      Tidak ada atribut didalam tupel yang dipartisi lagi

Tidak ada tupel didalam cabang yang kosong