Tanggal :October 22, 2020

Penjelasan Mengenai Pohon Keputusan atau Decision Tree Beserta Contohnya !

Spread the love

 Pohon Keputusan (Decission Tree)

 
Pohon  keputusan  adalah  model  prediksi  menggunakan  struktur  pohon  atau struktur berhirarki. Decision  tree merupakan  salah  satu  metode  klasifikasi  yang  menggunakan representasi  struktur  pohon  (tree)  di  mana  setiap node merepresentasikan  atribut, cabangnya merepresentasikan nilai dari  atribut, dan daun merepresentasikan kelas. Node yang paling atas dari decisiontree disebut sebagai root. Decisiontreemerupakan metode  klasifikasi  yang  paling  populer digunakan.  Selain  karena  pembangunannya relatif cepat, hasil dari model yang dibangun mudah untuk dipahami. Pada decision tree terdapat 3 jenis node, yaitu:
a. Root  Node,  merupakan node paling  atas,  pada node ini  tidak  ada  input dan bisa tidak mempunyai output atau mempunyai output lebih dari satu.
b. Internalnode,  merupakan node percabangan,  pada node ini  hanya  terdapat satu input dan mempunyai output minimal dua.
c. Leafnode atau terminal node , merupakan node akhir, pada node ini hanya terdapat satu input dan tidak mempunyai output. Pada  pohon  keputusan,  simpul  dalam  menyatakan  pengujian  terhadap  suatu atribut (digambarkan dengan kotak), cabang menyatakan hasil dari suatu pengujian (digambarkan    dengan  panah  yang  memiliki  label  dan  arah),  sementara  daun menyatakan kelas yang diprediksi (digambarkan dengan lingkaran).

Karakteristik Decision Tree

Berikut ini adalah beberapa karakteristik decision tree secara umum :

• Decision tree merupakan suatu pendekatan nonparametrik untuk membangun model klasifikasi
• Teknik yang dikembangkan dalam membangun decision tree memungkinkan untuk membangun model secara cepat dari training set yang berukuran besar.
• Decision tree dengan ukuran tree yang kecil relatif mudah untuk menginterpretasinya
• Decision tree memberikan gambaran yang ekpresif dalam pembelajaran fungsi nilai diskret.
• Algoritma decision tree cukup robbust terhadap munculnya noise terutama untuk metode yang
dapat menangani masalah overfitting.
• Adanya atribut yang berlebihan tidak terlalu mengurangi akurasi decision tree .
• Karena sebagian algoritma decision tree menggunakan pendekatan topdown, yaitu partisi dilakukan secara rekursif maka jumlah record menjadi lebih kecil. Pada leaf node, jumlah record mungkin akan terlalu kecil untuk dapat membuat keputusan secara statistik tentang representasi kelas dari suatu node.
 • Sebuah subtree dapat direplikasi beberapa kali dalam decision tree tetapi ini akan menyebabkan decision tree menjadi lebih kompleks dan lebih sulit untuk diinterpretasi. (Sibaroni, 2008:8).
 

Algoritma-algoritma dalam Metode Pohon Keputusan

Beberapa algoritma yang ada pada metode pohon keputusan, sebagai berikut :
 

1. Algoritma ID3 (Iterative Dychotomyzer version 3)

ID3 adalah suatu algoritma pelajaran pohon keputusan yang sederhana yang dikembangkan  oleh  Ross  Quinlan  (1986). Algoritma  ID3  berusaha  membangun pohon keputusan secara top-down yang disebut juga Top Down Induction Decision Tree (TDIDT) (Suyanto, 2007). Algoritma TDIDT memerlukan 2 langkah pengerjaan yaitu  membangun  pohon  keputusan  (Construction  Decision  Tree)  dan menyederhanakan pohon keputusan yang dibuat (Prunning Decision Tree).
 

2. Algoritma Assistant

Algoritma Assistant ini juga termasuk kepada keluarga ID3 yang merupakan sistem  induksi  atas-kebawah,  dari  pohon  keputusan.(Quinlan,  1986).Sistem  secara berulang  membangun  suatu  pohon  keputusan  yang biner. simpul dari pohon  sesuai dengan atribut, dan daun-daun (simpul terminal) ke kelas diagnostik /peramalan.Pada setiap  langkah  yang  berulang  tentang  konstruksi pohon  keputusan, atribut “paling informatif’” (  suatu  atribut  yang  memperkecil    jumlah  test yang  diharapkan  yang diperlukan  untuk  penggolongan  dari  kasus  yang  baru)  terpilih  dan  suatu  subtree dibangun.Assistant menyamaratakan  lebih  lanjut  di  atribut  dihargai-bilangan  bulat
dari  ACLS  dengan  mengijinkan  atribut  dengan  nilai  kontinyu.Assistant tidak membentuk  suatu  pohon  keputusan  secara  berulang-ulangseperti  cara  ID3, tetapi meliputi algoritma untuk pilih pelatihan bernilai baik dari objek tersedia.
 

3. Algoritma C4.5

C4.5 adalah ekstensi dari algoritma decision-tree ID3. Algoritma ID3/C4.5 ini secara rekursif membuat sebuah decision tree berdasarkan training data yang telah disiapkan. Algoritma ini mempunyai inputan berupa training samples dan samples (Heryanti 2005 dalam Kusrini 2009). Training samples berupa data contoh yang akan digunakan untuk membangun sebuah tree yang telah diuji kebenarannya.

Pembuatan Pohon Keputusan


Algoritma C4.5  membangun  pohon  keputusan  dengan  strategi divide dan conquer.  Algoritma  ini  memilih  pemecahan  kasus-kasus  yang  terbaik  dengan menghitung  dan  membandingkan Gain Ratio,  kemudian  pada  node-node  yang terbentuk dilevel berikutnya, algoritma divide dan conquer akan diterapkan kembali.
 
a. Information Gain
Information gain adalah salah satu atribute selection measure yang digunakan
untuk  memilih  test  atribut  tiap  node  pada tree.  Atribut  dengan information  gain
tertinggi dipilih sebagai test atribut dari suatu node. Ada 2 kasus berbeda pada saat
penghitungan Information  Gain,  pertama  untuk  kasus  penghitungan  atribut  tanpa
missing value dan kedua, penghitungan atribut dengan missing value.
• Perhitungan InformationGain tanpa MissingValue
Untuk menghitung information gain tanpa missing value digunakan rumus
seperti tertera pada persamaan 1 berikut:
Dimana :
S : himpunan kasus
A : atribut
n : jumlah partisi atribut A
|S i | : jumlah kasus pada partisi ke-i
|S| : jumlah kasus dalam S
Sementara itu, untuk menghitung nilai Entopy dapat dilihat pada persamaan 2
berikut:
Dimana:S : himpunan kasusA : fiturn : jumlah partisi Sp i : proporsi dari S i terhadap S

Setelah nilai information gain pada semua atribut dihitung, maka atribut yangmempunyai nilai information gain terbesar yang dipilih menjadi test atribut.• Perhitungan Information Gain dengan MissingValueUntuk  atribut  dengan missing  value penghitungan  information  gain-nyadiselesaikan dengan Gain Ratio.

b. Penanganan Atribut Kotinyu

Algoritma  C4.5  juga  menangani  masalah  atribut  kontinyu.  Salah  satu  caraadalah  dengan Entropy-Based  Discretization yang  melibatkan  penghitungan  classentropy.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *