Minggu, 18 November 2012

Makalah Pohon Keputusan


BAB I
PENDAHULUAN
1.1  Latar Belakang
Seperti yang kita ketahui bahwa manusia selalu berhadapan dengan suatu masalah. Masalah-masalah ini memiliki tingkat kesulitan dan kompleksitas yang sangat bervariasi, mulai dari yang teramat sederhana dengan sedikit faktor-faktor atau hal-hal yang berkaitan dengan masalah tersebut dan perlu diperhitungkan, sampai dengan yang sangat rumit dengan banyak sekali faktor-faktor atau hal-hal yang turut serta berkaitan dengan masalah tersebut dan perlu untuk diperhitungkan juga.
Untuk menghadapi masalah-masalah ini, manusia mulai mengembangkan sebuah sistem / cara yang dapat membantu manusia agar dapat dengan mudah mampu untuk menyelesaikan masalah-masalah tersebut. Adapun pohon keputusan ini adalah sebuah jawaban akan sebuah sistem / cara yang manusia kembangkan untuk membantu mencari dan membuat keputusan untuk masalah-masalah tersebut dan dengan memperhitungkan berbagai macam factor yang ada di dalam lingkup masalah tersebut. Dengan pohon keputusan, manusia dapat dengan mudah melihat mengidentifikasi dan melihat hubungan antara faktor-faktor yang mempengaruhi suatu masalah dan dapat mencari penyelesaian terbaik dengan memperhitungkan faktor-faktor tersebut. Pohon keputusan ini juga dapat menganalisa nilai resiko dan nilai suatu informasi yang terdapat dalam suatu alternatif pemecahan masalah.
Pohon keputusan merupakan sebuah sistem atau cara yang manusia kembangkan untuk membantu mencari dan membuat keputusan untuk masalah-masalah tersebut dan dengan memperhitungkan berbagai macam faktor yang ada di dalam lingkup masalah tersebut. Secara umum, pohon keputusan adalah suatu gambaran permodelan dari suatu persoalan yang terdiri dari serangkaian keputusan yang mengarah ke solusi.

1.2  Tujuan Penulisan
Tujuan penulisan ini adalah untuk memenuhi salah satu tugas dari mata kuliah . selain itu penulisan makalah ini adalah untuk mengetahui apa yang dikatakan dengan pohon keputusan, kegunaan pohon keputusan dalam memecahkan masalah serta kelebihan dan kekurangan pohon keputusan.

1.3  Manfaat Penulisan
Penulisan makalah ini diharapkan dapat memberikan manfaat bagi penulis khususnya serta bagi para pembaca pada umumnya. Diharapkan dengan membaca makalah ini dapat memberikan pengetahuan mengenai pohon keputusan.





BAB I
PEMBAHASAN

Secara umum pohon keputusan digunakan untuk memodelkan persoalan yang terdiri dari serangkaian keputusan yang mengarah ke solusi. Tiap simpul pada pohon keputusan menyatakan keputusan, setiap daun menyatakan solusi dan seitap cabang menyatakan keputusan yang diambil. Pohon keputusan adalah salah satu metode klasifikasi yang paling populer karena mudah untuk diinterpretasi oleh manusia. Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Konsep dari pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan.

Kelebihan dari metode pohon keputusan adalah:
·       Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik.
·       Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sample diuji hanya berdasarkan kriteria atau kelas tertentu.
·        Fleksibel untuk memilih fitur dari internal node 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.
Dalam analisis multivariat, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu untuk mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan criteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.
Kekurangan metode pohon keputusan, yaitu:
·       Terjadi overlap terutama ketika kelas-kelas dan criteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan.
·       Pengakumulasian jumlah eror dari setiap tingkat dalam sebuah pohon keputusan yang besar.
·       Kesulitan dalam mendesain pohon keputusan yang optimal. Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.
Skema Pohon keputusan
Skema dan struktur pohon keputusan adalah suatu permodelan dari struktur pohon menurut teori graf.

Struktur Dasar Pohon
Berdasarkan teori graf, definisi pohon adalah “sebuah graf, tak-berarah, terhubung, yang tidak mengandung sirkuitGraf adalah suatu representasi visual dari objek-objek diskrit yang dinyatakan dengan noktah, bulatan, atau titik, serta hubungan yang ada antara objek-objek tersebut.

Secara matematis, graf didefinisikan sebagai psangan himpunan (V,E) yang dalam hal ini :
V = himpunan tidak-kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }
E = himpunan sisi (edges) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }

Beberapa contoh graf antara lain:
Tak-Berarah di sini adalah graf tersebut sisinya tidak mempunyai arah.
Terhubung maksudnya adalah semua simpulnya dapat terhubung oleh sisi-sisi yang ada pada graf tersebut.
Tidak mengandung sirkuit maksudnya adalah graf tersebut tidak mengandung suatu lintasan yang melalui masing-masing sisi/simpul dalam graf tepat satu kali yang kembali ke simpul asal.
Adapun permodelan pohon yang biasa dipakai dalam pohon keputusan adalah rooted tree (pohon berakar). Pohon berakar adalah pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah.
 


















Gambar 3. Pohon Berakar
Sebagai konvensi, tanda arah panah dapat dibuang

Beberapa terminologi dalam pohon berakar :
·      Anak/Child atau Orangtua/Parent : b,c, dan d adalah anak dari a dan a adalah orangtua dari b,c, dan d.
  • Lintasan/Path : lintasan dari a ke j adalah a,b,e,j. Panjang lintasan dari a ke j adalah jumlah sisi yang dilalui, yaitu 3.
  • Saudara kandung/Sibling : b,c,dan d adalah saudara kandung sebab mempunyai orangtua yang sama yaitu a.
  • Derajat : derajat adalah jumlah anak yang ada pada simpul tersebut. A berderajat 3, dan b berderajat 2. Derajat suatu pohon adalah derajat maksimum dari semua simpul yang ada. Pohon pada gambar 3 berderajat
  • Daun : daun adalah simpul yang tidak mempunyai anak. c,f,g,h,i,dan j adalah daun Simpul dalam/Internal nodes : simpul yang mempunyai anak. Simpul a,b, dan d adalah simpul dalam.
  • Tingkat/Level : adalah 1 + panjang lintasan dari simpul teratas ke simpul tersebut. Simpul teratas mempunyai tingkat = 1.
  • Pohon n-ary : pohon yang tiap simpul cabangnya mempunyai banyaknya n buat anak disebut pohon nary. Jika n=2, pohonnya disebut pohon biner.

Struktur Pohon Keputusan
Secara umum, pohon keputusan dalah suatu gambaran permodelan dari suatu persoalan yang terdiri dari serangkaian keputusan yang mengarah ke solusi. Tiap simpul dalam menyatakan keputusan dan
daun menyatakan solusi. Permodelan pohon keputusan di sini berupa permodelan pohon n-ary, dengan jumlah anak yang dapat berbeda-beda tiap simpulnyaOval: b>a>cOval: b>c>aOval: a>c>bOval: a>b>cOval: c>b>b
a : c
 
b : c
 
b : c
 
Oval: c>a>b
a : c
 
a : b
 











Gambar 2. Pohon keputusan untuk mengurutkan 3 buah bilangan a, b, dan c.

Pohon keputusan pada gambar 5 dibaca dari atas ke bawah. Simpul paling atas pada pohon keputusan ini adalah simpul akar. Simpul yang ditandai dengan tanda kotak di simpul tersebut disebut dengan simpul keputusan. Cabang-cabang yang mengarah ke kanan dan kekiri dari sebuah cabang keputusan merepresentasikan kumpulan dari alternative keputusan yang bisa diambil. Hanya satu keputusan yang dapat diambil dalam suatu waktu. Dalam beberapa pohon keputusan, juga sering disertakan simpul tambahan, yaitu simpul probabilitas. Simpul ini biasa ditandai dengan gambar lingkaran kecil yang disertai dengan angka pada cabang-cabang yang mengakar pada simpul probabilitas itu. Angka-angka yang terletak pada cabang-cabang tersebut merupakan probalitas kesempatan akan munculnya keputusan yang ada di cabang tersebut dalam pilihan.
Sebagai sebuah catatan, pohon keputusan tidak hanya dapat ditulis secara vertikal, namun juga dapat secara horizontal. Pada penulisan secara horizontal, pembacaan pohon keputusan dimulai dari kiri ke kanan.
Selain itu, di posisi paling bawah sebuah pohon keputusan juga dapat ditambahkan sebuah titik akhir (endpoint), yang merepresentasikan hasil akhir dari sebuah lintasan dari akar pohon keputusan pohon tersebut sampai ke titik akhir itu.
Expected value / hasil estimasi adalah sebuah estimasi hasil dari sebuah keputusan tertentu. Hasil ini didapatkan dari mengkalikan setiap kemungkinan peluang terjadinya suatu kemungkinan lalu menambahkan hasilnya menhadi suatu jumlah.
Expected value decision criterion / kriteria keputusan hasil estimasi adalah suatu seleksi agar dapat memilih sebuah alternatif keputusan yang mempunyai hasil estimasi yang paling baik / yang paling diinginkan. Dalam situasi bila “more is better” atau lebih banyak itu lebih baik, maka pilihan keputusan dengan hasil estimasi paling tinggi adalah yang terbaik, sedangkan dalam situasi bila ”less is better”, maka pilihan keputusan dengan hasil estimasi paling rendah adalah yang terbaik.
Decision tree rollback adalah suatu teknik untuk menghitung selama suksesif hasil estimasi yang ada dari simpul keputusan di akhir pohon sampai kembali ke akar pohon keputusan tersebut.
Decision strategy/ strategi pengambilan keputusanvadalah semua spesifikasi lengkap dari semua kemungkinan pilihan yang sesuai dengan kriteriahasil dari sebuah pengambilan keputusan suatu masalah secara sekuensial dengan menggunakan sebuah pohon keputusan.
Dalam decision analysis, pohon keputusan dapat diartikan sebagai sebuah alat untuk membuat ide yang secara umum dapat mengacu kepada sebuah graf atau sebuah model dari keputusan-keputusan dan akibat-akibat yang dapat muncul dari keputusankeputusan tersebut, termasuk peluang terjadinya suatu kejadian, biaya yang dibutuhkan, dan utilitas. Melalui pohon ini strategi terbaik untuk menyelesaikan suatu masalah dapat diketahui. Pohon keputusan juga digunakan untuk mengkalkulasikan peluang kondisi-kondisi yang mungkin akan terjadi desertai dengan analisis-analisis faktor-faktor yang mempengaruhi keputusan yang diambil dengan menggunakan pohon keputusan tersebut.
Aplikasi Pohon Keputusan

                                                                         12 juta
                                                      s1
Oval: 2                                                                                              
 


                 d1                                   s2               6 juta
Oval: 2
1
 
                   20 juta                          
                 d2                             s1                     15 juta
                 30 juta
                 d3                                 s2                2 juta
Oval: 2                 40 juta                           s1                 20 juta
 

                                                        s2               3 juta

                         Gambar 3. Pohon keputusan bagi masalah pembelian computer
Dari poohon keputusan di atas dapat kita lihat bagaimana proses pembuatan keputusan dalam pembelian computer:
1.      Pembuatan keputusan dimulai dari suatu titik keputusan ( decision node ) no. 1 yang digambarkan sebagai, dimana pembuat keputusan harus mempertimbangkan 3 alternatif keputusan d1, d2 dan d3.
2.      Oval: 2Tiap alternative menghadapi dua kemungkinan situasu masa depan yaitu dimana permintaan jasa lembaga penelitian adalah tinggi ( S1) atau permintaan jasa lembaga penelitian adalah rendah ( S2 ). Tiap ujung dari keputusan (alternative) ditandai oleh symbol                yang disebut sebagai “ state of nature node”, symbol ini merupakan pangkal dari “ state of nature branches “ atau cabang pohon keputusan yang menggambarkan kemungkinan – kemungkinan situasi masa depan.
Tiap ujung pohon keputusan mewakili hasil (payoff) dari alternative yang dipilih berdasarkan situasi masa depan yang diperkirakan terjadi. Contohnya, ujung pohon keputusan yang paling atas dalam gambar 3 menunjukkan hasil Rp. 12 juta untuk system computer yang kecil (d1) dan keadaan situasi masa depan adalah S1 yang berarti permintaan jasa lembaga penelitian adalah tinggi. Sebaliknya bila permintaan terhadap jasa computer adalah rendah maka payoff untuk alternative tersebut di atas hanya akan menghasilkan Rp. 6 Juta.

Contoh Kasus Untuk Pohon Keputusan
0,80
 
50.000.000
 
Sukses
 
Proyek A
 
0,20
 
Asumsikan Anda mempunyai sejumlah dana untuk di investasikan pada dua alternative proyek, yaitu proyek A dan Proyek B akan memberikan keuntungan sebesar 20% dengan nilai keuntungan 50 Juta, peluang proyek B akan memberikan keuntungan adalah 45% dengan nilai keuntungan 10 juta, Buat lah Pohon keputusan dalam mengambil keputusan.
Gagal
 
                                                                                  
0


 
Proyek B
 
 





Pengambilan Keputusan berdasarkan pada nilai ekonomi yang diharapkan dengan Rumus
EMV =  (Probility x nilai Fayoff yang diharapkan)
Keterangan :
EMV = Expented Monetari Value
EMV proyek A =  (Probility x nilai Fayoff yang diharapkan)
= (0,2 x 50.000.000) + (0,8 x 0) = 10.000.000
EMV proyek B =  (Probility x nilai Fayoff yang diharapkan)
Proyek A
 
= (0,45 x 10.000.000) + (0,55 x 0) = 4.500.000
 



Jadi kesimpulannya dengan menggunakan pohon keputusan ini adalah yang memberikan keuntungan yang lebih besar Proyek A




BAB III
KESIMPULAN

Dapat dilihat bahwa menggunakan pohon keputusan sebagai support tool dalam menganalis suatu masalah pengambilan keputusan dapat sangat membantu kita dalam melakukan pengambilan keputusan. Kegunaan pohon keputusan yang dapat melihat berbagai macam alternatif keputusan-keputusan yang dapat kita ambil serta mampu memperhitungkan nilai-nilai dari faktor-faktor yang mempengaruhi alternatif-alternatif keputusan tersebut adalah sangat penting dan berguna, karena membuat kita dapat mengetahui alternatif mana yang paling menguntungkan untuk kita ambil.
Pohon keputusan juga dapat dipergunakan untuk memperhitungkan dan melakukan analisa terhadap resiko-resiko yang mungkin muncul dalam suatu alternatif pemilihan keputusan. Selain itu, pohon keputusan juga dapat dipakai untuk memperhitungkan berapa nilai suatu informasi tambahan yang mungkin kita perlukan agar kita dapat lebih mampu dalam membuat suatu pilihan keputusan dari suatu alternatif-alternatif keputusan yang ada.
Dengan melihat kegunaan pohon keputusan dan kemampuannya dalam memperhitungkan berbagai alternatif pemecahan masalah termasuk faktor-faktor yang mempengaruhinya serta nilai resiko dan nilai informasi dalam alternatif keputusan itu, maka jelaslah bahwa pohon keputusan ini dapat menjadi alat bantu yang sangat berguna dalam pengambilan keputusan.


DAFTAR PUSTAKA

Munir, Rinaldi. (2006) .Diktat Kuliah IF2153 Matematika Diskrit Edisi Keempat. Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung.

Wikipedia. (2006) . Decision Tree. http://en.wikipedia.org/wiki/Decision_tree.


Wikipedia. (2006) . Decision Analysis. http://en.wikipedia.org/wiki/Decision_analysis.

Wikipedia. (2006) .Data Mining. http://en.wikipedia.org/wiki/Data_mining.

1 komentar:

  1. saya juga mempunyai artikel tentang pohon keputusan, bisa dibaca di: Pohon Keputusan, Demo Pohon Keputusan berbasis web, Jurnal Pohon Keputusan. semoga bermanfaat

    BalasHapus