Decision

Algoritma Decision Tree C4.5

Pohon Keputusan (Decision Tree) merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Aturan ini juga dapat diekspresikan dalam bentuk bahasa basis data seperti SQL untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan ini sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain(J R Quinlan, 1993).

Dalam situasi lain kemampuan untuk menjelaskan alasan pengambilan keputusan adalah sesuatu yang sangat penting. Misalnya pada perusahaan asuransi ada larangan resmi untuk mendeskriminasi berdasarkan variabel-variabel tertentu. Perusahaan asuransi dapat mencari sendiri keadaan yang mencerminkan bahwa mereka tidak menggunakan deskriminasi yang ilegal dalam memutuskan seseorang diterima atau ditolak. Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan. Anggota himpunan hasil menjadi mirip satu dengan yang lain dengan masing-masing rangkaian pembagian. Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen dengan memperhatikan pada variabel tujuannya. Sebuah pohon keputusan mungkin dibangun dengan seksama secara manual, atau dapat tumbuh secara otomatis dengan menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan himpunan data yang belum terklasifikasi (Tan dkk, 2004).

Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-masing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.

Kelebihan dari metode pohon keputusan adalah:

1.      Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik

2.      Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sampel diuji hanya berdasarkan kriteria atau kelas tertentu

3.      Fleksibel untuk memilih fitur dari node internal yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama. Kefleksibelan metode pohon keputusan ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih konvensional

4.      Dalam analisis multivarian, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.

Kekurangan pada pohon keputusan adalah:

1.      Terjadi overlapping terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan

2.      Pengakumulasian jumlah kesalahan dari setiap tingkat dalam sebuah pohon keputusan yang besar

3.      Kesulitan dalam mendesain pohon keputusan yang optimal

4.      Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.

Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Contoh dari pohon keputusan dapat dilihat pada Gambar berikut :

Gambar Model Pohon Keputusan (Pramudiono,2008)

Setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon menyatakan kelas data. Contoh pada Gambar diatas adalah identifikasi pembeli komputer. Dari pohon keputusan tersebut diketahui bahwa salah satu kelompok yang potensial membeli komputer adalah orang yang berusia di bawah 30 tahun dan juga pelajar. Setelah sebuah pohon keputusan dibangun maka dapat digunakan untuk mengklasifikasikan record  yang belum ada kelasnya. Dimulai dari node root,  menggunakan tes terhadap atribut dari record yang belum ada kelasnya ini lalu mengikuti cabang yang sesuai dengan hasil dari tes tersebut, yang akan membawa kepada internal node (node yang memiliki satu cabang masuk dan dua atau lebih cabang yang keluar), dengan cara harus melakukan tes lagi terhadap atribut atau node leaf. Record yang kelasnya tidak diketahui kemudian diberikan kelas yang sesuai dengan kelas yang ada pada node leaf. Pada pohon keputusan setiap simpul leafmenandai label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule) (J R Quinlan, 1993).

Salah satu algoritma induksi pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Dalam prosedur algoritma ID3, input berupa sampel training, label training dan atribut. Algoritma Decision Tree C4.5 merupakan pengembangan dari ID3. Sedangkan pada perangkat lunak open source WEKA mempunyai versi sendiri dari C4.5 yang dikenal sebagai J48.

Generate_decision_tree (Training samples, Atribute) // decision tree function

Method :

(1) Create node N;

(2) If samples are all of the same class C then

(3)    Return N as a leaf node labeled with the class  C;

(4) if atribute-list is empty then

(5)         Return N as a leaf node labeled with the most common class in samples;     // majority voting

(6) else

(7)       select test-atribute, atribute among atribute-list with the highest information gain;

(8) label node N with test-atribute;

(9)       for each known value a_i of test-atribute // partition the samples

(10)             grow a branch from node N for the condition test-atribute = a_i;

(11)   let s_i be the set of samples in samples for which test-atribute = a_i; // a  partition

(12)            if s_i is empty then

(13)     attach a leaf labeled with the most common class in samples;

         else attach the node returned by Generate_decision_tree(s_i, atribute-list-test-atribute);

Gambar Algoritma Decision Tree C4.5 (Han dan Khamber, 2001)

Secara umum algoritma Decision Tree C4.5 untuk membangun pohon keputusan adalah sebagai berikut (Kusrini, 2009) :

1.      Pilih atribut sebagai root

2.      Buat cabang untuk masing-masing nilai

3.      Bagi atribut terpilih dalam cabang

4.      Ulangi proses untuk masing-masing cabang sampai semua atribut terpilih pada cabang memiliki kelas yang sama.

Untuk menghitung gain diberikan rumus sebagai berikut:

Dimana

S = himpunan kasus

A = Atribut

n = jumlah partisi

|Si| = jumlah kasus pada partisi ke-i

|S| = jumlah kasus dalam S

Sedangkan untuk perhitungan nilai entropi adalah sebagai berikut:

Dimana,

S = himpunan kasus

n = jumlah pastisi S

pi = proposi dari Si terhadap S