Model Pohon Keputusan
Pohon keputusan adalah model prediksi menggunakan struktur pohon atau
struktur berhirarki. Contoh dari pohon keputusan dapat dilihat di Gambar
berikut ini.
Model Pohon Keputusan (Pramudiono,2008)
Disini setiap percabangan menyatakan kondisi yang harus dipenuhi dan
tiap ujung pohon menyatakan kelas data. Contoh di Gambar 1 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 tersebut 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 daun. Record yang kelasnya tidak diketahui kemudian diberikan kelas yang sesuai dengan kelas yang ada pada node daun.
Pada pohon keputusan setiap simpul daun menandai label kelas. Proses
dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model
pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule).
ALGORITMA C4.5
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 C4.5 merupakan pengembangan dari ID3. Sedangkan pada
perangkat lunak open source WEKA mempunyai versi sendiri C4.5 yang dikenal sebagai J48.
Algoritma C4.5
Pohon dibangun dengan cara membagi data secara rekursif hingga tiap
bagian terdiri dari data yang berasal dari kelas yang sama. Bentuk
pemecahan (split) yang digunakan untuk membagi data tergantung dari jenis atribut yang digunakan dalam split. Algoritma C4.5 dapat menangani data numerik (kontinyu) dan diskret. Split untuk atribut numerik yaitu mengurutkan contoh berdasarkan atribut kontiyu A, kemudian membentuk minimum permulaan (threshold)
M dari contoh-contoh yang ada dari kelas mayoritas pada setiap partisi
yang bersebelahan, lalu menggabungkan partisi-partisi yang bersebelahan
tersebut dengan kelas mayoritas yang sama. Split untuk atribut diskret A mempunyai bentuk value (A) ε X dimana X ⊂ domain(A).
Jika suatu set data mempunyai beberapa pengamatan dengan missing value yaitu record dengan beberapa nilai variabel tidak ada, Jika jumlah pengamatan terbatas maka atribut dengan missing value dapat diganti dengan nilai rata-rata dari variabel yang bersangkutan.[Santosa,2007]
Untuk melakukan pemisahan obyek (split) dilakukan tes terhadap atribut dengan mengukur tingkat ketidakmurnian pada sebuah simpul (node). Pada algoritma C.45 menggunakan rasio perolehan (gain ratio).
Sebelum menghitung rasio perolehan, perlu menghitung dulu nilai
informasi dalam satuan bits dari suatu kumpulan objek. Cara
menghitungnya dilakukan dengan menggunakan konsep entropi.
S adalah ruang (data) sampel yang digunakan untuk pelatihan, p+ adalah jumlah yang bersolusi positif atau mendukung pada data sampel untuk kriteria tertentu dan p- adalah jumlah yang bersolusi negatif atau tidak mendukung pada data sampel untuk kriteria tertentu. ntropi(S)
sama dengan 0, jika semua contoh pada S berada dalam kelas yang sama.
Entropi(S) sama dengan 1, jika jumlah contoh positif dan negative dalam S
adalah sama. Entropi(S) lebih dari 0 tetapi kurang dari 1, jika jumlah
contoh positif dan negative dalam S tidak sama [Mitchell,1997].Entropi
split yang membagi S dengan n record menjadi himpunan-himpunan S1 dengan n1 baris dan S2 dengan n2 baris adalah :
Kemudian menghitung perolehan informasi dari output data atau variabel dependent y yang dikelompokkan berdasarkan atribut A, dinotasikan dengan gain (y,A). Perolehan informasi, gain (y,A), dari atribut A relative terhadap output data y adalah:
nilai (A) adalah semua nilai yang mungkin dari atribut A, dan yc adalah subset dari y dimana A mempunyai nilai c. Term pertama dalam persamaan diatas adalah entropy total y dan term kedua adalah entropy sesudah dilakukan pemisahan data berdasarkan atribut A.
Untuk menghitung rasio perolehan perlu diketahui suatu term baru yang disebut pemisahan informasi (SplitInfo). Pemisahan informasi dihitung dengan cara :
bahwa S1 sampai Sc adalah c subset yang dihasilkan dari pemecahan S dengan menggunakan atribut A yang mempunyai sebanyak c nilai. Selanjutnya rasio perolehan (gain ratio) dihitung dengan cara :
Contoh Aplikasi
CREDIT RISK
Berikut ini merupakan contoh dari salah satu kasus resiko kredit (credit risk) yang menggunakan decision tree untuk menentukan apakah seorang potential customer dengan karakteristik saving, asset dan income tertentu memiliki good credit risk atau bad credit risk.
Dapat dilihat pada gambar tersebut, bahwa target variable dari decision
tree tersebut atau variable yang akan diprediksi adalah credit risk
dengan menggunakan predictor variable : saving, asset, dan income.
Setiap nilai atribut dari predictor variable akan memiliki cabang menuju
predictor variable selanjutnya, dan seterusnya hingga tidak dapat
dipecah dan menuju pada target variable.
Penentuan apakah diteruskan menuju predictor variable (decision node)
atau menuju target variable (leaf node) tergantung pada keyakinan
(knowledge) apakah potential customer dengan nilai atribut variable
keputusan tertentu memiliki keakuratan nilai target variable 100% atau
tidak. Misalnya pada kasus di atas untuk saving medium, ternyata
knowledge yang dimiliki bahwa untuk seluruh potential customer dengan
saving medium memiliki credit risk yang baik dengan keakuratan 100%.
Sedangkan untuk nilai low asset terdapat kemungkinan good credit risk
dan bad credit risk.
Jika tidak terdapat pemisahan lagi yang mungkin dilakukan, maka
algoritma decision tree akan berhenti membentuk decision node yang baru.
Seharusnya setiap branches diakhiri dengan “pure” leaf node, yaitu leaf
node dengan target variable yang bersifat unary untuk setiap records
pada node tersebut, di mana untuk setiap nilai predictor variable yang
sama akan memiliki nilai target variable yang sama. Tetapi, terdapat
kemungkinan decision node memiliki “diverse” atributes, yaitu bersifat
non‐unary untuk nilai target variablenya, di mana untuk setiap record
dengan nilai predictor variable yang sama ternyata memiliki nilai target
variable yang berbeda. Kondisi tersebut menyebabkan tidak dapat
dilakukan pencabangan lagi berdasarkan nilai predictor variable.
Sehingga solusinya adalah membentuk leaf node yang disebut “diverse”
leaf node, dengan menyatakan level kepercayaan dari diverse leaf node
tersebut. Misalnya untuk contoh data berikut ini :
Dari training data tersebut kemudian disusunlah alternatif untuk
candidate split, sehingga setiap nilai untuk predictor variable di atas
hanya membentuk 2 cabang, yaitu sebagai berikut:
Kemudian untuk setiap candidate split di atas, dihitung
variabel‐variabel berikut berdasarkan training data yang dimiliki.
Adapun variabel‐variabel tersebut, yaitu :
,di mana
Adapun contoh hasil perhitungannya adalah sebagai berikut :
Dapat dilihat dari contoh perhitungan di atas, bahwa yang memiliki nilai
goodness of split * Φ(s/t) + yang terbesar, yaitu split 4 dengan nilai
0.64275. Oleh karena itu split 4 lah yang akan digunakan pada root node,
yaitu split dengan : assets = low dengan assets = {medium, high}.
Untuk penentuan pencabangan, dapat dilihat bahwa dengan assets=low maka
didapatkan pure node leaf, yaitu bad risk (untuk record 2 dan 7).
Sedangkan untuk assets = {medium, high} masih terdapat 2 nilai, yaitu
good credit risk dan bad credit risk. Sehingga pencabangan untuk assets =
{medium, high} memiliki decision node baru. Adapun pemilihan split yang
akan digunakan, yaitu dengan menyusun perhitungan nilai Φ(s/t) yang
baru tanpa melihat split 4, record 2 dan 7.
Demikian seterusnya hingga akhirnya dibentuk leaf node dan membentuk decision tree yang utuh (fully grown form) seperti di bawah ini :
SISTEM PAKAR DIAGNOSA PENYAKIT (KUSRINI)
Dalam aplikasi ini terdapat tabel-tabel sebagai berikut:
- Tabel Rekam_Medis, berisi data asli rekam medis pasien
- Tabel
Kasus, beisi data variabel yang dapat mempengaruhi kesimpulan diagnosis
dari pasien-pasien yang ada, misalnya Jenis Kelamin, Umur,
Daerah_Tinggal, Gejala_1 s/d gejala_n, Hasil_Tes_1 s/d Hasi_Tes_n.
Selain itu dalam tabel ini juga memiliki field Hasil_Diagnosis.
- Tabel Aturan, berisi aturan hasil ekstrak dari pohon keputusan.
Proses akuisisi pengetahuan yang secara biasanya dalam sistem pakar
dilakukan oleh sistem pakar, dalam sistem ini akan dillakukan dengan
urutan proses ditunjukkan pada gambar berikut:
Hasil pembentukan pohon keputusan bisa seperti pohon keputusan yang tampak pada gambar:
Lambang bulat pada pohon keputusan melambangkan sebagai node akar atau cabang (bukan daun) sedangkan kotak
melambangkan node daun. Jika pengetahuan yang terbentuk beruka kaidah produksi dengan format:
Jika
Premis Maka Konklusi Node-node akar akan menjadi Premis dari aturan
sedangkan node daun akan menjadi bagian konklusinya. Dari gambar pohon
keputusan pada gambar 4, dapat dibentuk aturan sebagai berikut:
- Jika Atr_1 = N_1
Dan Atr_2 = N_4
Dan Atr_3 = N_9
Maka H_1
- Jika Atr_1 = N_1
Dan Atr_2 = N_4
Dan Atr_3 = N_10
Dan Atr_4 = N_11
Maka H_2
- Jika Atr_1 = N_1
Dan Atr_2 = N_4
Dan Atr_3 = N_10
Dan Atr_4 = N_12
Maka H_2
- Jika Atr_1 = N_1
Dan Atr_2 = N_5
Maka H_4
- Jika Atr_1 = N_2
Maka H_5
- Jika Atr_1 = N_3
Dan Atr_5 = N_6
Maka H_6
- Jika Atr_1 = N_3
Dan Atr_5 = N_7
Maka H_7
- Jika Atr_1 = N_3
Dan Atr_5 = N_8
Maka H_8
Model case based reasoning dapat digunakan sebagai metode akuisisi
pengetahuan dalam aplikasi system pakar diagnosis penyakit. Aturan yagn
dihasilkan system ini mampu digunakan untuk mendiagnosis penyakit
didasarkan pada data-data pasien. Dalam penentuan diagnosis penyakit
belum diimplementasikan derajat kepercayaan terhadap hasil diagnosis
tersebut.