studi kasus - univbsi.idunivbsi.id/pdf/2014/602/602-p10.pdflearning, membuat sebuah algoritma...

43
STUDI KASUS

Upload: ngonhan

Post on 30-Jul-2019

246 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

STUDI KASUS

Page 2: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5

Page 3: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5

Pada akhir tahun 1970 sampai awal tahun 1980 J.Ross Quinlan, seorang peneliti di bidang machinelearning, membuat sebuah algoritma decision treeyang dikenal dengan ID3 (Iterative Dichotomiser).

Quinlan kemudian membuat algoritma C4.5 (seringdisebut dengan pohon keputusan) yang merupakanpengembangan dari algoritma ID3 (Han, 2006).

Page 4: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5 -2

Algoritma ini memiliki kelebihan, yaitu mudahdimengerti, fleksibel, dan menarik karena dapatdivisualisasikan dalam bentuk gambar (pohonkeputusan) (Gorunescu, 2011).

Algoritma C4.5 merupakan struktur pohon dimanaterdapat simpul yang mendeskripsikan atribut-atribut, setiap cabang menggambarkan hasil dariatribut yang diuji, dan setiap daun menggambarkankelas

Page 5: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5 -3

Algoritma C4.5 secara rekursif mengunjungi setiapsimpul keputusan, memilih pembagian yang optimal,sampai tidak bisa dibagi lagi.

Algoritma C4.5 menggunakan konsep informationgain atau entropy reduction untuk memilih pembagianyang optimal (Han, 2006).

Ada beberapa tahap dalam membuat sebuah pohonkeputusan dengan algoritma C4.5 (Kusrini, 2009),yaitu :

Page 6: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5 -4

1. Menyiapkan data training.

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

Page 7: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5 -52. Menentukan akar dari pohon

Akar akan diambil dari atribut yang terpilih, dengancara menghitung nilai gain dari masing-masing atribut,nilai gain yang paling tinggi yang akan menjadi akarpertama. Sebelum menghitung nilai gain dari atribut,hitung dahulu nilai entropy. Untuk menghitung nilaientropy digunakan rumus:

Keterangan: S = himpunan kasus n = jumlah partisi S pi = proporsi Si terhadap S

Page 8: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Algoritma C4.5 -6

3. Kemudian hitung nilai gain menggunakan rumus:

Keterangan: S = himpunan kasusA = fiturn = jumlah partisi atribut A │Si│ = proporsi Si terhadap S │S│ = jumlah kasus dalam S

Page 9: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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.

Page 10: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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

Page 11: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5

CONTOH KASUS

Page 12: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

STUDY KASUS Algoritma C4.5

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

Page 13: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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

Page 14: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

STUDY KASUS Algoritma C4.5 -2

Data training pada Tabel diatas adalah untukmenentukan apakah seorang nasabah bermasalah atautidak, ditentukan oleh kolom predictor saving, asset,dan income.

Kolom credit risk adalah kelas dari masing-masingrecord.

Page 15: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Langkah-Langkah Algoritma C4.5

1. Tabel diatas adalah data training beserta kelasnya.

Untuk atribut income yang bernilai angka, dibuat dalambentuk 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, yangberesiko kredit good 5 record dan Bad 3 record sehinggadidapat entropy:

Page 16: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Langkah-Langkah Algoritma C4.5 -2

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

Yang mempunyai nilai gain tertinggi itulah yangakan dijadikan akar dari pohon.

Misalkan untuk atribut saving dengan nilai lowdidapat nilai gain:

Page 17: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Langkah-Langkah Algoritma C4.5 -3 Hasil perhitungan gain untuk tiap atribut terlihat pada Tabel

berikut. Nilai gain tertinggi akan manjadi akar dari pohon.

Page 18: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Langkah-Langkah Algoritma C4.5 -4

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

Nilai low dan high masing-masing sudah menjadisatu klasifikasi karena pada data training, semuaasset menghasilkan keputusan yang sama yaitu baduntuk nilai low dan good untuk nilai high.

Sedangkan untuk simpul dengan nilai medium perludipartisi lagi.

Page 19: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Langkah-Langkah Algoritma C4.5 -5

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

Dari hasil perhitungan didapat nilai gain tertinggi untukatribut asset, maka asset menjadi akar dari pohonkeputusan.

Untuk menentukan akar dari atribut medium, dilakukanlagi perhitungan nilai gain.

Page 20: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

STUDY KASUS

ALGORITMA C4.5

Page 21: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5

Algoritma C4.5 merupakan salah satu algoritma machinelearning.

Dengan algoritma ini, mesin (komputer) akan diberikansekelompok data untuk dipelajari yang disebut learningdataset.

Kemudian hasil dari pembelajaran selanjutnya akandigunakan untuk mengolah data-data yang baru yangdisebut test dataset.

Karena algoritma C4.5 digunakan untuk melakukanklasifikasi, jadi hasil dari pengolahan test dataset berupapengelompokkan data ke dalam kelas-kelasnya.

Page 22: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5 -2

Berikut ini adalah uraian langkah-langkah dalamalgoritma C4.5 untuk menyelesaikan kasus suatupertandingan tenis akan dilakukan atau tidak,berdasarkan keadaan cuaca, suhu, kelembaban, danangin.

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

Page 23: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5 -3

Page 24: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5 -4

A. Menghitung Jumlah Kasus

Jumlah kasus untuk keputusan Yes, jumlah kasus untukkeputusan No, dan Entropy dari semua kasus dan kasusyang dibagi berdasarkan atribut Cuaca, Suhu,Kelembaban, dan Berangin.

Berikut rumus Entropy

Page 25: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5 -5

A. Menghitung Jumlah Kasus

Setelah itu lakukan penghitungan Gain untukmasing-masing atribut.

Page 26: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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 yaitukelas “Tidak” dan kelas “Ya”.

Kemudian data tersebut dianalisis; dataset tersebutmemiliki 14 kasus yang terdiri 10 “Ya” dan 4 “Tidak”pada kolom Main

Page 27: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C4.5 -7

A. Menghitung Jumlah Kasus

Setelah mendapatkan entropi dari keseluruhan kasus,lakukan analisis pada setiap atribut dan nilai-nilainyadan hitung entropinya seperti yang ditampilkan padaTabel dibawah ini

Page 28: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Perhitungan Nilai Entropi dan Gain

Page 29: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Perhitungan Nilai Entropi dan Gain

Untuk menghitung gain setiap atribut rumusnya adalah :

Page 30: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Perhitungan Nilai Entropi dan Gain

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

Hasilnya dapat dilihat pada Tabel dibawah ini.

Page 31: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Perhitungan Nilai Entropi dan Gain

Page 32: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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 yangterbentuk

Page 33: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Perhitungan Nilai Entropi dan Gain -2

Kemudian pada kelembaban normal, memiliki 7kasus dan semuanya memiliki jawaban Ya(Sum(Total) / Sum(Ya) = 7/7 = 1).

Dengan demikian kelembaban normal menjadidaun atau leaf.

Lihat Tabel sebelumnya yang selnya berwarna hijau

Page 34: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat
Page 35: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

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

Untuk mempermudah, Tabel 1 difilter, denganmengambil data yang memiliki Kelembaban =Tinggi sehingga jadilah Tabel seperti di bawah ini.

Page 36: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Kemudian data di Tabel diatas dianalisis dandihitung lagi entropi atribut Kelebaban Tinggi danentropi setiap atribut serta gainnya sehingga hasilnyaseperti data pada Tabel selanjutnya.

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

Berikut nilai Entropy dari tabel di atas

Page 37: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Nilai Entropi dan Gain

Page 38: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Nilai Entropi dan Gain secara lengkap

Page 39: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Dari Tabel diatas, gain tertinggi ada pada atributCuaca, dan Nilai yang dijadikan daun atau leaf adalahBerawan dan Cerah.

Jika divualisasi maka pohon keputusan tampak sepertiGambar berikut.

Page 40: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Untuk menganalisis node 1.1.2, lakukan lagilangkah-langkah yang sama seperti sebelumnya.

Hasilnya ditampilkan pada Tabel dibawah ini.

Page 41: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Nilai Entropi dan Gain secara lengkap

Page 42: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

Pohon Keputusan

Page 43: STUDI KASUS - univbsi.idunivbsi.id/pdf/2014/602/602-P10.pdflearning, membuat sebuah algoritma decision tree yang dikenal dengan ID3 (Iterative Dichotomiser). Quinlan kemudian membuat

ALGORITMA C 4.5 Pada gambar diatas, semua kasus pada pohon keputusan

sudah masuk ke dalam kelas sehingga tidak ada lagikasus/atribut yang dapat dipartisi.

Pohon keputusan dari gambar diatas dapat diekstraksisejumlah 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