Pembahasan Decision Tree

Download Pembahasan Decision Tree

Post on 12-Aug-2015

753 views

Category:

Documents

42 download

Embed Size (px)

DESCRIPTION

aa

TRANSCRIPT

<p>BAB I</p> <p>PENDAHULUAN</p> <p>1.1. Latar Belakang Masalah</p> <p>Sebagian besar keputusan yang dibuat manusia, terutama di bidang bisnis dan konstruksi akan selalu beresiko karena informasi yang tersedia adalah informasi yang tidak sempurna atau imperfect information. Hal inilah yang menyebabkan para pembuat keputusan tidak pernah lelah dalam mencari informasi tambahan untuk memperoleh hasil keputusan terbaik. Visualisasi tersebut menggambarkan bagaimana putusan harus memilih berbagai alternatif yang berdasar perhitungan dengan nilai keputusan berbeda. </p> <p>Dalam suatu analisis keputusan, Decision Tree (Pohon Keputusan) merupakan salah satu alat untuk mencapai keputusan terbaik tersebut. Dimana Decision Tree adalah suatu decision support tool yang menggunakan sebuah grafik atau model suatu keputusan dan konsekuensi-konsekuensi dari keputusan tersebut. Disebut Decision Tree karena bila digambarkan mirip sebuah pohon dengan cabang-cabang dan ranting-rantingnya. Decision Tree biasanya digunakan untuk mengidentifikasi strategi terbaik yang harus digunakan untuk mencapai tujuan. </p> <p>Kegunaan lain dari Decision Tree adalah sebagai alat deskriptif untuk menghitung probabilitas kondisional. Dibandingkan dengan decision support tools yang lain, Decision Tree memiliki beberapa kelebihan yakni mudah dimengerti dan diinterpretasikan. Orang akan mudah memahami model dari Decision Tree setelah memperoleh penjelasan singkat. Selain itu Decision Tree tetap memiliki nilai bahkan dengan data yang sulit. Untuk pengertian yang lebih mendalam dapat diperoleh berdasarkan gambaran dari tenaga ahli mengenai situasinya (alternatifnya, probabilitasnya, dan biaya-biayanya) dan pilihan mereka untuk hasilnya. </p> <p>Decision Tree menggunakan white box model. Jika kita memperoleh hasil dari model tersebut maka penjelasannya akan dapat dengan mudah dimengerti dengan matematika sederhana. Decision Tree juga bisa dikombinasikan dengan teknik pengambilan keputusan yang lainnya contohnya dengan metode NPV, PERT dan distribusi linear. Bukan hanya itu, Decision Tree dapat digunakan untuk mengoptimalisasikan suatu investasi. </p> <p>Berdasarkan hal tersebut, makan dalam penyusunan makalah ini akan dibahas lebih lanjut mengenai Decision Tree. </p> <p>1.2. Rumusan Masalah</p> <p>Dari latar belakang tersebut, maka permasalahan yang penulis angkat dalam tugas ini adalah :</p> <p>1. Apa saja manfaat dari penggunanaa Decision Tree?</p> <p>2. Bagaimana penerapan Decision Tree dalam suatu kasus?</p> <p>1.3. Sistematika Penulisan.</p> <p>Sistematika penulisan dalam tugas ini, meliputi : </p> <p>BAB I PENDAHULUAN </p> <p>Pada bab ini diuraikan tentang latar belakang, rumusan masalah dan sistematika penulisan.</p> <p>BAB II KONSEP DAN TEORI</p> <p>Bab ini menguraikan tentang konsep dan teori yang diperlukan sebagai pendukung dalam pembahasan.</p> <p>BAB III METODE PEMBAHASAN</p> <p>Bab ini menguraikan secara singkat tentang metode yang digunakan.</p> <p>BAB IV PEMBAHASAN </p> <p>Bab ini berisi proses pembahasan yang relevan dengan permasalahan.</p> <p>BAB V SIMPULAN </p> <p>Bab ini berisi simpulan terhadap hasil pembahasan.</p> <p>BAB II</p> <p>KONSEP DAN TEORI</p> <p>2.1. Pengertian Decision Tree</p> <p>Secara konsep Decision Tree adalah salah satu dari teknik decision analysis.Tries sendiri pertama kali diperkenalkan pada tahun 1960-an oleh Fredkin. Trie atau digital tree berasal dari kata retrival (pengambilan kembali) sesuai dengan fungsinya. Secara etimologi kata ini diucapkan sebagai tree. Meskipun mirip dengan penggunaan kata try tetapi hal ini bertujuan untuk membedakannya dari general tree. Dalam ilmu komputer, trie, atau prefix tree adalah sebuah struktur data dengan representasi ordered tree yang digunakan untuk menyimpan associative array yang berupa string. Berbeda dengan binary search tree (BST) yang tidak ada node di tree yang menyimpan elemen yang berhubungan dengan node sebelumnya dan, posisi setiap elemen di tree sangat menentukan. Semua keturunan dari suatu node mempunyai prefix string yang mengandung elemen dari node itu, dengan root merupakan string kosong. Values biasanya tidak terkandung di setiap node, hanya di daun dan beberapa node di tengah yang cocok dengan elemen tertentu.</p> <p>Secara singkat bahwa Decision Tree merupakan salah satu metode klasifikasi pada Text Mining. Klasifikasi adalah proses menemukan kumpulan pola atau fungsi-fungsi yang mendeskripsikan dan memisahkan kelas data satu dengan lainnya, untuk dapat digunakan untuk memprediksi data yang belum memiliki kelas data tertentu (Jianwei Han, 2001).</p> <p>Decision Tree adalah sebuah struktur pohon, dimana setiap node pohon merepresentasikan atribut yang telah diuji, setiap cabang merupakan suatu pembagian hasil uji, dan node daun (leaf) merepresentasikan kelompok kelas tertentu. Level node teratas dari sebuah Decision Tree adalah node akar (root) yang biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu. Pada umumnya Decision Tree melakukan strategi pencarian secara top-down untuk solusinya. Pada proses mengklasifikasi data yang tidak diketahui, nilai atribut akan diuji dengan cara melacak jalur dari node akar (root) sampai node akhir (daun) dan kemudian akan diprediksi kelas yang dimiliki oleh suatu data baru tertentu.</p> <p>2.2 Node dan Algoritma Penyusun Decision Tree</p> <p>Decision Tree merupakan salah satu metode klasifikasi yang menggunakan representasi struktur pohon (tree) dimana setiap node merepresentasikan atribut, cabang nya merepresentasikan nilai dari atribut, dan daun merepresentasikan kelas. Node yang paling atas dari Decision Tree disebut sebagai root. Decision Tree merupakan metode klasifikasi yang paling populer digunakan. Selain karena pembangunannya relatif cepat, hasil dari model yang dibangun mudah untuk dipahami. </p> <p>Pada Decision Tree terdapat 3 jenis node, yaitu:</p> <p>a. Root Node, merupakan node paling atas, pada node ini tidak ada input dan bisa tidak mempunyai output atau mempunyai output lebih dari satu.</p> <p>b. Internal Node , merupakan node percabangan, pada node ini hanya terdapat satu input dan mempunyai output minimal dua.</p> <p>c. Leaf node atau terminal node , merupakan node akhir, pada node ini hanya terdapat satu input dan tidak mempunyai output.</p> <p>Decision Tree menggunakan algoritma ID3 atau C4.5, yang diperkenalkan dan dikembangkan pertama kali oleh Quinlan yang merupakan singkatan dari Iterative Dichotomiser 3 atau Induction of Decision 3 (baca: Tree). Algoritma ID3 membentuk pohon keputusan dengan metode divide-and-conquer data secara rekursif dari atas ke bawah. Strategi pembentukan Decision Tree dengan algoritma ID3 adalah:</p> <p> Pohon dimulai sebagai node tunggal (akar/root) yang merepresentasikan semua data.</p> <p> Sesudah node root dibentuk, maka data pada node akar akan diukur dengan information gain untuk dipilih atribut mana yang akan dijadikan atribut pembaginya.</p> <p> Sebuah cabang dibentuk dari atribut yang dipilih menjadi pembagi dan data akan didistribusikan ke dalam cabang masing-masing.</p> <p> Algoritma ini akan terus menggunakan proses yang sama atau bersifat rekursif untuk dapat membentuk sebuah Decision Tree. Ketika sebuah atribut telah dipilih menjadi node pembagi atau cabang, maka atribut tersebut tidak diikutkan lagi dalam penghitungan nilai information gain.</p> <p> Proses pembagian rekursif akan berhenti jika salah satu dari kondisi dibawah ini terpenuhi:</p> <p>1. Semua data dari anak cabang telah termasuk dalam kelas yang sama.</p> <p>2. Semua atribut telah dipakai, tetapi masih tersisa data dalam kelas yang berbeda. Dalam kasus ini, diambil data yang mewakili kelas yang terbanyak untuk menjadi label kelas pada node daun.</p> <p>3.Tidak terdapat data pada anak cabang yang baru. Dalam kasus ini, node daun akan dipilih pada cabang sebelumnya dan diambil data yang mewakili kelas terbanyak untuk dijadikan label kelas.</p> <p>Beberapa contoh pemakaian Decision Tree,yaitu :</p> <p> Diagnosa penyakit tertentu, seperti hipertensi, kanker, stroke dan lain-lain</p> <p> Pemilihan produk seperti rumah, kendaraan, komputerdanlain-lain</p> <p> Pemilihan pegawai teladan sesuai dengan kriteria tertentu</p> <p> Deteksi gangguan pada computer atau jaringan computer seperti Deteksi Entrusi, deteksi virus (Trojan dan varians),dan lain-lain</p> <p>BAB III</p> <p>METODE PENULISAN</p> <p>Metode pembahasan dalam penulisan tugas ini disampaikan secara deskriptif, mengacu pada beberapa sumber literatur/pustaka sebagai acuan dan sarana pendukung, baik cetak maupun elektronik. Selanjutnya dikaji secara mendalam mengikuti kaidah-kaidah ilmiah.</p> <p>BAB IV</p> <p>HASIL DAN PEMBAHASAN</p> <p>4.1. Decision Tree dan Manfaatnya </p> <p>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. </p> <p>Pohon Keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Pohon keputusan memadukan antara eksplorasi data dan pemodelan, sehingga sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain. </p> <p>Kelebihan dari metode pohon keputusan (Decision Tree) adalah:</p> <p>Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik.</p> <p>Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sample diuji hanya berdasarkan kriteria atau kelas tertentu.</p> <p> 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</p> <p>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.</p> <p>Kekurangan dari metode pohon keputusan (Decision Tree) adalah:</p> <p>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.</p> <p>Pengakumulasian jumlah eror dari setiap tingkat dalam sebuah pohon keputusan yang besar.</p> <p> Kesulitan dalam mendesain pohon keputusan yang optimal.</p> <p>Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.</p> <p>4.3. Penerapan Decision Tree dalam Suatu Kasus</p> <p>Pohon keputusan digunakan untuk memodelkan persoalan yang terdiri dari serangkaian keputusan yang mengarah ke solusi. Tiap simpul dalam menyatakan keputusan, sedangkan daun menyatakan solusi.</p> <p>Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.</p> <p>Gambar 4.1 Contoh Pohon</p> <p>Secara matematis, graf dapat didefinisikan sebagai berikut :</p> <p>Graf G (V,E) adalah suatu sistem yang terdiri dari himpunan titik berhingga tak kosong V = V (G) dan himpunan sisi E = E (G) yaitu himpunan pasangan tak terurut dari anggotaanggota V. Sebagai contoh, gambar 1 adalah graf dengan himpunan titik V(G) = {u, v, x, y ,z, w}dan himpunan sisi E (G) = {vx, vy, yz, zu, zw}.</p> <p>(</p> <p>)</p> <p>(</p> <p>)</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>P</p> <p>P</p> <p>P</p> <p>P</p> <p>Tua</p> <p>Entropy</p> <p>P</p> <p>P</p> <p>P</p> <p>P</p> <p>Muda</p> <p>Entropy</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>log</p> <p>log</p> <p>log</p> <p>log</p> <p>-</p> <p>-</p> <p>=</p> <p>-</p> <p>-</p> <p>=</p> <p>Gambar 4.2 Contoh Graf</p> <p>Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan anatara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah atau simpul, sedangkan hubungan antar objek sebagai garis atau sisi. Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :</p> <p>1) Graf tak-berarah (undirected graph)</p> <p>Graf yang sisinya tidak mempunyai orientasi arah.</p> <p>2) Graf berarah (directed graph atau digraph)</p> <p>Graf yang setiap sisinya diberikan orientasi arah.</p> <p>Keputusan dapat dijelaskan sebagai hasil pemecahan masalah, selain itu juga harus didasari atas logika dan pertimbangan, penetapan alternatif terbaik, serta harus mendekati tujuan yang telah ditetapkan. Seorang pengambil keputusan haruslah memperhatikan logika, realita, rasional, dan pragmatis.</p> <p>Teori pengambilan keputusan adalah teknik pendekatan yang digunakan dalam proses pengambilan keputusan atau proses memilih tindakan sebagai cara pemecahan masalah. Fungsi pengambilan keputusan adalah individual atau kelompok baik secara institusional ataupun organisasional, sifatnya futuristik.</p> <p>Terlepas dari kerumitan sebuah keputusan atau kecanggihan teknik yang digunakan untuk menganalisis keputusan tersebut, semua pengambil keputusan dihadapkan dengan berbagai alternatif dan kondisi alami. Pada saat membuat sebuah pohon keputusan, harus dipastikan bahwa semua alternatif dan kondisi alami berada di tempat yang benar dan logis serta semua alternatif yang mungkin serta kondisi alami telah disertakan. Notasi yang digunakan adalah :</p> <p>1. Istilah :</p> <p>a. Alternatif sebuah tindakan atau strategi yang dapat dipilih oleh seorang pengambil keputusan.</p> <p>b. Kondisi alami sebuah kejadian atau situasi dimana pengambil keputusan hanya memiliki sedikit kendali atau tidak sama sekali.</p> <p>2. Simbol yang digunakan dalam sebuah pohon keputusan:</p> <p>(</p> <p>)</p> <p>(</p> <p>)</p> <p>(</p> <p>)</p> <p>(</p> <p>)</p> <p>0,955</p> <p>0,424</p> <p>0,531</p> <p>0.678</p> <p>-</p> <p>625</p> <p>.</p> <p>0</p> <p>-1.415</p> <p>375</p> <p>.</p> <p>0</p> <p>625</p> <p>.</p> <p>0</p> <p>log</p> <p>625</p> <p>.</p> <p>0</p> <p>375</p> <p>.</p> <p>0</p> <p>log</p> <p>375</p> <p>.</p> <p>0</p> <p>8</p> <p>5</p> <p>log</p> <p>8</p> <p>5</p> <p>8</p> <p>3</p> <p>log</p> <p>8</p> <p>3</p> <p>2</p> <p>2</p> <p>2</p> <p>2</p> <p>=</p> <p>+</p> <p>=</p> <p>-</p> <p>-</p> <p>=</p> <p>-</p> <p>-</p> <p>=</p> <p>-</p> <p>-</p> <p>=</p><p>a. sebuah titik keputusan dimana terdapat satu alternatif atau lebih yang dapat dipilih.</p> <p>(</p> <p>)</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>negatif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>positif</p> <p>ce</p> <p>ins</p> <p>P</p> <p>P</p> <p>P</p> <p>P</p> <p>Hipertensi</p> <p>Entropy</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>_</p> <p>tan</p> <p>2</p> <p>_</p> <p>tan</p> <p>log</p> <p>log</p> <p>-</p> <p>-</p> <p>=</p><p>b. se...</p>