Studi Kasus 2

Algoritma C4.5

Algoritma C4.5

Pada akhir tahun 1970 sampai awal tahun 1980 J. Ross Quinlan, seorang peneliti di bidang machine

learning, membuat sebuah algoritma decision tree

yang dikenal dengan ID3 (Iterative Dichotomiser).

Quinlan kemudian membuat algoritma C4.5 (sering disebut dengan pohon keputusan) yang merupakan

pengembangan dari algoritma ID3 (Han, 2006).

Algoritma C4.5-2

Algoritma ini memiliki kelebihan, yaitu mudah dimengerti, fleksibel, dan menarik karena dapat

divisualisasikan dalam bentuk gambar (pohon keputusan) (Gorunescu, 2011).

Algoritma C4.5 merupakan struktur pohon dimana terdapat simpul yang mendeskripsikan atribut-

atribut, setiap cabang menggambarkan hasil dari

atribut yang diuji, dan setiap daun menggambarkan kelas

Algoritma C4.5-3

Algoritma C4.5 secara rekursif mengunjungi setiap simpul keputusan, memilih pembagian yang optimal,

sampai tidak bisa dibagi lagi.

Algoritma C4.5 menggunakan konsep information gain atau entropy reduction untuk memilih pembagian

yang optimal (Han, 2006).

Ada beberapa tahap dalam membuat sebuah pohon keputusan dengan algoritma C4.5 (Kusrini, 2009),

yaitu :

Algoritma C4.5-4

1. Menyiapkan data training.

Data training biasanya diambil dari data histori yang pernah terjadi sebelumnya dan sudah dikelompokkan ke dalam kelas-kelas tertentu.

Algoritma C4.5-5

2. Menentukan akar dari pohon

Akar akan diambil dari atribut yang terpilih, dengan

cara menghitung nilai gain dari masing-masing atribut, nilai gain yang paling tinggi yang akan menjadi akar pertama. Sebelum menghitung nilai gain dari atribut, hitung dahulu nilai entropy. Untuk menghitung nilai

entropy digunakan rumus:

Keterangan:

S = himpunan kasus

n = jumlah partisi S

pi = proporsi Si terhadap S

Algoritma C4.5-6

3. Kemudian hitung nilai gain menggunakan rumus:

Keterangan:

S = himpunan kasus

A = fitur

n = jumlah partisi atribut A

│Si│ = proporsi Si terhadap S │S│ = jumlah kasus dalam S

Algoritma C4.5-7

4. Ulangi langkah ke-2 hingga semua record terpartisi.

5. Proses partisi pohon keputusan akan berhenti saat :

a. Semua record dalam simpul N mendapat kelas yang

sama.

b. Tidak ada atribut di dalam record yang dipartisi lagi.

c. Tidak ada record di dalam cabang yang kosong.

Contoh Pohon keputusan menjadi Rule

• R1 = IF Berat=Average Or

berat = Underweight THEN Hipertensi = Tidak

• R2 = IF Berat = Overweight And Kelamin = wanita THEN

Hipertensi = Yes

• R3 = IF Berat = Overweight And Kelamin = Pria And Usia

= Muda THEN Hipertensi = Yes

• R4 = IF Berat = Overweight And Kelamin = Pria And Usia = Tua THEN Hipertensi = Tidak

ALGORITMA C4.5

CONTOH KASUS

STUDY KASUS Algoritma C4.5

Tabel dibawah adalah contoh data training apakah seorang nasabah bermasalah dalam kredit atau tidak (Larose, 2005).

http://web2.0calc.com/

Node

Attribut

Nilai

Jum. Kasus

Good

Bad

Entropy

Gain

1

Saving

High

2

1

1

Medium

3

3

0

Low

3

1

2

2

Assets

High

2

2

0

Medium

4

3

1

Low

2

0

2

3

Income

STUDY KASUS Algoritma C4.5 -2

Data training pada Tabel diatas adalah untuk menentukan apakah seorang nasabah bermasalah atau

tidak, ditentukan oleh kolom predictor saving, asset, dan income.

Kolom credit risk adalah kelas dari masing-masing record.

Langkah-Langkah Algoritma C4.5

1. Tabel diatas adalah data training beserta kelasnya.

Untuk atribut income yang bernilai angka, dibuat dalam bentuk kategori, yaitu income<=25, income>25,

income<=50, income>50, income<=75, income>75.

2. Hitung nilai entropy.

Dari data training diketahui jumlah kasus ada 8, yang beresiko kredit good 5 record dan Bad 3 record sehingga didapat entropy:

Langkah-Langkah Algoritma C4.5 -2

3. Hitung nilai gain untuk tiap atribut, lalu tentukan nilai gain tertinggi.

Yang mempunyai nilai gain tertinggi itulah yang akan dijadikan akar dari pohon.

Misalkan untuk atribut saving dengan nilai low didapat nilai gain:

Langkah-Langkah Algoritma C4.5 -3

Hasil perhitungan gain untuk tiap atribut terlihat pada Tabel berikut. Nilai gain tertinggi akan manjadi akar dari pohon.

angkah-Langkah Algoritma C4.5 -4

Terlihat dari tabel diatas atribut, asset mempunyai nilai low, medium, dan high.

Nilai low dan high masing-masing sudah menjadi satu klasifikasi karena pada data training, semua

asset menghasilkan keputusan yang sama yaitu bad

untuk nilai low dan good untuk nilai high.

Sedangkan untuk simpul dengan nilai medium perlu dipartisi lagi.

Langkah-Langkah Algoritma C4.5 -5

Gambar diatas adalah hasil pembentukan pohon keputusan berdasarkan perhitungan yang terdapat pada Tabel diatas.

Dari hasil perhitungan didapat nilai gain tertinggi untuk atribut asset, maka asset menjadi akar dari pohon

keputusan.

Untuk menentukan akar dari atribut medium, dilakukan lagi perhitungan nilai gain.

STUDY KASUS

ALGORITMA C4.5

ALGORITMA C4.5

Algoritma C4.5 merupakan salah satu algoritma machine learning.

Dengan algoritma ini, mesin (komputer) akan diberikan sekelompok data untuk dipelajari yang disebut learning

dataset.

Kemudian hasil dari pembelajaran selanjutnya akan digunakan untuk mengolah data-data yang baru yang

disebut test dataset.

Karena algoritma C4.5 digunakan untuk melakukan klasifikasi, jadi hasil dari pengolahan test dataset berupa

pengelompokkan data ke dalam kelas-kelasnya.

ALGORITMA C4.5 -2

Berikut ini adalah uraian langkah-langkah dalam algoritma C4.5 untuk menyelesaikan kasus suatu

pertandingan tenis akan dilakukan atau tidak, berdasarkan keadaan cuaca, suhu, kelembaban, dan angin.

Data yang telah ada pada Tabel 1, akan digunakan untuk membentuk pohon keputusan.

ALGORITMA C4.5 -3

ALGORITMA C4.5 -4

A. Menghitung Jumlah Kasus

Jumlah kasus untuk keputusan Yes, jumlah kasus untuk keputusan No, dan Entropy dari semua kasus dan kasus

yang dibagi berdasarkan atribut Cuaca, Suhu, Kelembaban, dan Berangin.

Berikut rumus Entropy

ALGORITMA C4.5 -5

A. Menghitung Jumlah Kasus

Setelah itu lakukan penghitungan Gain untuk masing-masing atribut.

ALGORITMA C4.5 -6

A. Menghitung Jumlah Kasus

Pada Tabel 1, atribut-atributnya adalah Cuaca, Suhu, Kelembaban, dan Berangin.

Setiap atribut memiliki nilai.

Sedangkan kelasnya ada pada kolom Main yaitu kelas “Tidak” dan kelas “Ya”.

Kemudian data tersebut dianalisis; dataset tersebut memiliki 14 kasus yang terdiri 10 “Ya” dan 4 “Tidak”

pada kolom Main

ALGORITMA C4.5 -7

A. Menghitung Jumlah Kasus

Setelah mendapatkan entropi dari keseluruhan kasus, lakukan analisis pada setiap atribut dan nilai-nilainya

dan hitung entropinya seperti yang ditampilkan pada Tabel dibawah ini

Perhitungan Nilai Entropi dan Gain

Perhitungan Nilai Entropi dan Gain

Untuk menghitung gain setiap atribut rumusnya adalah :

Perhitungan Nilai Entropi dan Gain

Hitung pula Gain (Suhu), Gain (Kelembaban), dan Gain (Berangin).

Hasilnya dapat dilihat pada Tabel dibawah ini.

Perhitungan Nilai Entropi dan Gain

Perhitungan Nilai Entropi dan Gain

Karena nilai gain terbesar adalah Gain (Kelembaban), Maka Kelembaban menjadi node akar (root node).

Berikut Pohon keputusan untuk node 1 yang

terbentuk

Perhitungan Nilai Entropi dan Gain -2

Kemudian pada kelembaban normal, memiliki 7

kasus dan semuanya memiliki jawaban Ya

(Sum(Total) / Sum(Ya) = 7/7 = 1).

Dengan demikian kelembaban normal menjadi daun atau leaf.

Lihat Tabel sebelumnya yang selnya berwarna hijau

Berdasarkan pembentukan pohon keputusan node 1 (root node), Node 1.1 akan dianalisis lebih lanjut.

Untuk mempermudah, Tabel 1 difilter, dengan

mengambil data yang memiliki Kelembaban = Tinggi sehingga jadilah Tabel seperti di bawah ini.

Kemudian data di Tabel diatas dianalisis dan dihitung lagi entropi atribut Kelebaban Tinggi dan

entropi setiap atribut serta gainnya sehingga hasilnya seperti data pada Tabel selanjutnya.

Setelah itu tentukan pilih atribut yang memiliki gain tertinggi untuk dibuatkan node berikutnya.

Berikut nilai Entropy dari tabel di atas

Nilai Entropi dan Gain

Nilai Entropi dan Gain secara lengkap

Dari Tabel diatas, gain tertinggi ada pada atribut Cuaca, dan Nilai yang dijadikan daun atau leaf adalah

Berawan dan Cerah.

Jika divualisasi maka pohon keputusan tampak seperti Gambar berikut.

Untuk menganalisis node 1.1.2, lakukan lagi

langkah-langkah yang sama seperti sebelumnya.

Hasilnya ditampilkan pada Tabel dibawah ini.

Nilai Entropi dan Gain secara lengkap

Pohon Keputusan

ALGORITMA C 4.5

Pada gambar diatas, semua kasus pada pohon keputusan sudah masuk ke dalam kelas sehingga tidak ada lagi

kasus/atribut yang dapat dipartisi.

Pohon keputusan dari gambar diatas dapat diekstraksi sejumlah aturan, yaitu :

1. R1: IF humidity=high AND THEN play=yes

2. R2: IF humidity=high AND outlook=rainy AND windy=false THEN play=yes

3. R3: IF humidity=high AND outlook=rainy AND windy=true THEN play=no

4. R4: IF humidity=high AND outlook=sunny THEN play=no

5. R5: IF humidity=normal THEN play=yes