Membangun Decision Tree dengan Entropy (Manual)







  • Pembentukkan decison tree dimulai dari pembentukkan root.
  • Entropy diperlukan untuk membangun sebuah decision tree yaitu pada saat memilih attribut mana yang terbaik sebagai root decision tree.
  • Kali ini kita coba menghitung entropy secara manual.
  • Misalkan S adalah data yang digunakan untuk membuat decision tree.
  • p+ adalah probabilitas instances yang mendukung dalam S.
  • p- adalah probabilitas instances yang tidak mendukung dalam S.
  • Rumus untuk menghitung entropy(S) adalah sbb:

  • Supaya lebih mudah dimengerti, kita masuk saja langsung ke contoh kasusnya.
  • Misalkan kita memiliki data yang akan kita gunakan untuk membuat decison tree sbb:
    • Ada 8 record  data sample
    • Target Attribute label klasifikasi adalah DataScientist (Yes) atau bukan (No)
    • Ada 3 attribute yang bisa digunakan sebagai parameter yaitu Analisis (Baik, Sedang, Kurang), Programming (Baik, Kurang), dan Pendidikan (S2,S3).   


  • Langkah I: Menentukan Root

    • Menentukan node dengan menggunakan nilai Entropy dari setiap kriteria dengan data sample yang ditentukan. 
    • Node terpilih adalah node dengan nilai Entropy yang paling kecil.
    • Okay, attribute yang penting disini adalah Target Attribute yaitu Data Scientist dimana akan dipasangkan dengan masing-masing attribute Analisis, Programming, dan Pendidikan.
    • Kita mulai saja dulu dari attribute Programming. 

    • Kemudian kita hitung Entropy Programming sbb:.
    • E(Programming=Baik)= -(1/4)log(1/4) -(3/4)log2 (3/4) = 0.81
    • E(Programming=Kurang)= -(2/4)log(2/4) -(2/4)log(2/4) = 1
    • E(Programming) = (4/8) E(Programming=Baik)+ (4/8) E(Programming=Kurang) = 1/2 (0.81) + (1/2) (1) = 0.91
    • Kemudian kita hitung entropy untuk Pendidikan sbb:
    • E(Pendidikan=S2)= -(2/6)log(2/6) -(4/6)log(4/6) = 0.92
    • E(Pendidikan=S3)= -(1/2)log(1/2) -(1/2)log(1/2) = 1
    • E(Programming) = (6/8) E(Pendidikan=S2)  + (2/8) E(Pendidikan=S3) = 6/8(0.92) + (2/8) (1) = 0.94


    • Kemudian kita hitung entropy untuk Analisis sbb:
    • E(Analisis=Baik)= -(3/4)log(3/4) -(1/4)log(1/4) = 0.81
    • E(Analisis=Sedang)= -(0)log(0) -(2/2)log(2/2) = 0
    • E(Analisis=Kurang)= -(2/2)log(2/2) -(0)log(0) = 0
    • E(Analisis) = (4/8) E(Analisis=Baik) + (2/8) E(Analisis=Sedang) + 2/8 E(Analisis=Kurang)= 4/8(0.81) + 0 + 0 = 0.41 
    • Catatan disini (0)log(0) bernilai 0 khusus untuk perhitungan entropy. Dengan demikian, kita tidak perlu menyediakan instances lengkap untuk masing-masing attribute.Bila tidak ada instancesnya maka entropy untuk attribut tsb dihitung nol.
    • Karena untuk Entropy Analisis memiliki nilai terkecil, maka kita pilih Analisis sebagai Attribute di root.
    • Maka sampai langkah 1 kita sudah dapat membuat sebuah pohon awal sbb:

Proses Pembentukan decision tree ini belum selesai, masih akan berlanjut pada proses split.

Bacaan berikutnya kembali ke Classification
























Pembentukan Model Decision Tree Dengan ctree



  • fungsi ctree() dapat ditemukan pada library party dalam paket party. Bagi yang belum memilikinya silakan instal paket party sbb:

install.packages("party")
library("party")
  • Memanggil data iris. Data iris sudah ada dalam R. 
  • Kelemahan ctree() adalah tidak bisa mengolah data yang berbentuk character.
  • Pastikan tidak ada character. Bila ada silakan transform dulu ke bentuk factor.
> # memeriksa data iris
> str(iris)
'data.frame': 150 obs. of  5 variables:
 $ Sepal.Length: num  5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
 $ Sepal.Width : num  3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
 $ Petal.Length: num  1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
 $ Petal.Width : num  0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
 $ Species     : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...


Membuat Model Decision Tree dengan 1 attribute.
  • Disini kita gunakan attribute Sepal.Length dengan target attribute Species
  • Pada bagian formula hanya tertulis Species~Sepal.Length karena cuma attribute Sepal.Length saja yang dipergunakan untuk membuat klasifikasi Spesies bunga iris.
> #membuat decision tree model dengan 1 attribute Sepal.Length
> tree_sl<-ctree(Species~Sepal.Length, data=iris)
> #membuat plot model tree 1 attribute Sepal.Length
> plot(tree_sl)
  • Hasilnya:


Interpretasi Model:

  • Pertama-tama selalu mulai dari root. Decison seluruhnya ditentukan oleh attribute Sepal.Length.
  • Sepal.length yang lebih kecil atau sama dengan 5.4 cm masuk ke terminal node (leaf) 2 di sebelah kiri dan yang lain masuk ke internal node 3.
  • Pada terminal node (leaf) 2:
    • Disebelah atas, ada informasi bahwa 52 bunga yang memiliki Sepal.Length kurang atau sama dengan 5.4cm. 
    • Disebelah bawah menunjukkan klas yaitu tiga species bunga iris.
    • Disebelah kiri ada garis vertikal yang menunjukkan prosentase hasil klasifikasi. Dari 52 bunga ini, 80% nya adalah setosa, 15% masuk ke versicolor, dan sisanya ke klas virginica. 
  • Pada internal node 3,  ditentukan oleh attribute Sepal. Length yang terbagi menjadi 2 grup Ada 43 Bunga dengan Sepal.Length yang kurang atau sama dengan 6.1 cm, sisanya masuk ke node 5. Dari 43 bunga ini, terdapat semua variasi klas yaitu yang terbanyak versicolor 70%, kemudian virginica 20% dan sisanya setosa 10%.   
  • Terakhir, pada internal node 5,  ditentukan oleh tentu saja attribute Sepal. Length terbagi menjadi 2 grup Ada 43 Bunga denga Sepal.Length yang kurang atau sama dengan 7 cm, dimana 60% merupakan virgica dan 40% versicolor. Sedangkan sisanya ada 12 bunga dengan Sepal.Length lebih dari 7cm yang seluruhnya ada virginica.  
  • Jangan lupa tarik kesimpulan juga. Kesimpulannya, bunag iris dengan klas setosa memiliki Sepal.length yang lebih pendek, yang terpanjang adalah virginica, dan versicolor berada ditengah-tengah tidak pendek dan juga tidak panjang.  


Membuat Model Decision Tree dengan 2 attribute.
  • Disini kita gunakan attribute Sepal.Length dan Sepal.Width dengan target attribute Species
  • Format formula adalah Target Attribute ~ Attribute1 + Attribute2 + ... artinya proses klasifikasi target attribute ditentukan oleh beberapa attribuet yaitu attribute1, attribute 2 dst. 
  • Pada bagian formula, kita tambahkan Sepal.Width sehingga formula yang baru menjadi Species~Sepal.Length+Sepal.Width artinya kita membuat klasifikasi Spesies berdasarkan 2 attribute ini.
> #membuat decision tree model dengan attribute Sepal.Length dan Sepal.Width
> tree_slsw<-ctree(Species~Sepal.Length+Sepal.Width, data=iris)
> #membuat plot model tree 2 attribute Sepal.Length dan Sepal.Width
> plot(tree_slsw)
  • Hasilnya:



Membuat Model Decision Tree dengan semua attribute.
  • Disini kita gunakan semua attribute  dengan target attribute Species
  • Perhatikan pada bagian formula ternyata ada cara singkat menuliskan seluruh attribut yaitu cukup dengan satu titik sehingga formulanya menjadi Species~.
> #membuat decision tree model dengan all attributes
> tree_all<-ctree(Species~., data=iris)
> #membuat plot model tree all attributes
> plot(tree_all)
  • Hasilnya:



  • Perhatikan, meskipun kita sudah gunakan semua attribute, namun hanya Petal.Length dan Petal.Width yang terpilih untuk membuat model decision tree.
  • Ini menandakan ada attribute yang penting dan ada juga yang tidak penting.
  • Kesimpulannya attribute Petal.Length dan Petal.Width adalah attribute yang penting untuk membuat model decision tree bunga iris.


Bacaan berikutnya kembali ke Classification









Pengertian Decision Tree


  • Proses klasifikasi juaga merupakan proses menentukan kategori tertentu pada suatu objek berdasarkan rule tertentu.
  • Misalkan: 
    • klasifikasi negara-negara dengan kategori negara miskin, berkembang, maju dengan rule menggunakan interval GDP.
    • Klasifikasi harga suatu barang komersil dengan kategori mahal, wajar, murah dengan rule menggunakan interval harga barang. 
  • Pada saat proses klasifikasi ini, akan lebih mudah bila kita sudah mendapatkan rulenya.
  • Namun bagaimana bila kita belum memiliki rulenya? Disinilah kegunaan decision tree yang mampu membuat rule menjadi sebuah model pohon keputusan sehingga dari model ini dapat ditarik rulenya
Kelebihan Decision Tree:

  • mudah dimengerti dan dijelaskan
  • membantu untuk menentukan hasil yang diharapkan dari berbagai macam scenario
  • membantu untuk menentukan nilai terbaik dan nilai terburuk dari berbagai macam scenario
  • dapat dikombinasikan dengan teknik decision yang lain
  • membutuhkan persiapan data yang minimal 
  • masih dapat menghandledata yang hilang 
  • terpengaruh pada outliers mungkin ada tapi sangat kecil
  • tidak usah repot-repot menghitung hubungan nonlinear antar parameters
  • beberapa teknik decion tree dapat memprosed data numerik dan kategorikal
  • dapat membuat rule dari model decision tree 

Kekurangan
  • Pada beberapa data kategorikal, hasil akan menjadi bias bila jumlah perbedaan kategorinya banyak.
  • Kalau over-fitted terhadap data, hasil prediksi akan sangat buruk


Bentuk Decision Tree
  • Bentuknya memang seperti pohon dan juga banyak dipergunakan untuk mengambil keputusan, makanya disebut pohon keputusan
  • Struktur pohon keputusan terdiri dari
    • komponen pohon hanya terdiri dari node dan edge
    • jenis-jenis node:
      • Root node adalah node di bagian pohon keputusan yang paling atas dimana tidak ada lagi edge yang menunjuknya.Root node digambarkan sebagai ellips.
      • Internal node adalah di bagian tengah pohon keputusan dimana ada edge yang menunjuknya dan ada juga edge yang keluar darinya. Internal node digambarkan sebagai ellips. 
      • Terminal node (leaf) adalah node di bagian ujung bawah pohon keputusan, dimana hanya ada edge yang menunjukknya dan tidak ada lagi edge yang keluar darinya. Terminal node digambarkan sebagai persegi panjang.

Data yang diperlukan
  • Data berbentuk sebuah tabel yang terdiri dari kolom (attributes) dan baris (records).
  • Attribute ini penting karena dipergunakan sebagai parameter untuk membangun pohon keputusan.
  • Attribute Identity adalah attribute unik yang menunjuk kepada satu objek tertentu, Contoh bila objeknya pelajar, maka attribute identitynya adalah Nomor Induk Pelajar (NIP).  
  • Attribute yang dipergunakan sebagai tujuan klasifikasi disebut dengan target attribute.

Proses-proses dalam pembentukkan Decision Tree:
  • Proses pengembangan decison tree yaitu proses split satu node jadi beberapa node dan seterusnya. Split ini pada dasarnya merupakan proses untuk membagi suatu dataset menjadi beberapa subset. Proses split ini terus dilakukan sampai dilakukannya proses pemberhentian split.
  • Proses pemberhentian split dilakukan apabila setiap record sudah memiliki suatu klasifikasi yang tidak berubah lagi. Namun ada kalanya diperlukan prosedur untuk menghentikan proses secara dini.
  • Proses membuat rule dari model decision tree.
  • Proses Prunning yaitu penyederhaan rule.

Bacaan berikutnya kembali ke Classification