Algoritma ID3 pada Pohon Keputusan

Algoritma ID3

Iterative  Dichotomicer 3 (ID3) adalah algoritma decision tree learning (algoritma pembelajaran pohon keputusan) yang  paling dasar. Algoritma ini melakukan   pencarian secara   rakus /menyeluruh   (greedy)    pada semua kemungkinan pohon keputusan. 

Salah   satu   algoritma   induksi   pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Algoritma ID3 dapat diimplementasikan menggunakan   fungsi rekursif (fungsi  yang memanggil   dirinya   sendiri).  Algoritma   ID3 berusaha  membangun decision  tree  (pohon keputusan)  secara top-down (dari atas ke bawah),  mulai  dengan  pertanyaan: “atribut mana yang pertama kali  harus  dicek  dan diletakkan  pada root?” pertanyaan  ini  dijawab dengan mengevaluasi semua atribut yang ada dengan  menggunakan  suatu  ukuran  statistik (yang  banyak  digunakan  adalah information gain)  untuk  mengukur  efektivitas  suatu  atribut dalam   mengklasifikasikan   kumpulan   sampel data.

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) merepresentasikankelompok  kelas  tertentu.Level  node  teratas  dari  sebuah  decision  treeadalah node akar (root) yang biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu.   

Entropy dan Information Gain

Sebuah  obyek  yang  diklasifikasikan  dalam pohon  harus  dites  nilai  entropinya. Entropyadalah  ukuran  dari  teori  informasi  yang  dapat mengetahui   karakteristik   dari impuryt   ,dan homogenity   dari   kumpulan   data.   Dari   nilai entropy    tersebut    kemudiandihitung    nilai information gain (IG) masing-masing atribut.

Entropy(S) = - p+ log2p + -p -log2p-

dimana :

·         S  adalah  ruang  (data)  sample  yang digunakan untuk training.

·     P+  adalah   jumlah    yang   bersolusi positif (mendukung) pada data sample untuk kriteria tertentu.

·     P+  adalah   jumlah  yang  bersolusi negatif  (tidak  mendukung)  pada  data sample untuk kriteria tertentu.Dari rumus entropy diatas dapat disimpulkan bahwa definisi entropy (S) adalah  jumlah  bit  yang  diperkirakan dibutuhkan  untuk  dapat  mengekstrak suatu  kelas  (+  atau  -)  dari  sejumlah data acak pada suatu ruang sampel S. Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas.  

Semakin  kecil  nilai  entropy maka  semakin  baik  digunakan  dalam mengekstraksi suatu kelas.  Panjang  kode  untuk  menyatakan informasi secara optimal  adalah  –log2p  bits untuk messages yang mempunyai probabilitas p. Sehingga jumlah bit yang diperkirakan untuk mengekstraksi  S  ke  dalam  kelas  adalah  :  - p+log2 p+ - p- log2 p- 

Information Gain 

setelah  mendapat  nilai  entropy  untuk  suatu kumpulan  data,  maka  kita  dapat  mengukur efektivitas suatu atribut dalam mengklasifikasikan data. Ukuran  efektifitas  ini disebut  information  gain.  Secara  matematis, infomation  gain  dari  suatu  atribut  A, dituliskan sebagai berikut :

dimana :

A : atribut

V : suatu nilai yang mungkin untuk atribut A

Values  (A)  :  himpunan  yang  mungkin  untuk  atribut A

|Sv| : jumlah sampel untuk nilai v

|S| : jumlah seluruh sampel data Entropy

(Sv):   entropy   untuk   sampel-sampel yang memilki nilai v

Sumber:

Wahyudin, Desember 2009, "Metode Iterative Dichotomizer 3 ( ID3 ) Untuk Penyeleksian Penerimaan Mahasiswa Baru". Jurnal Pendidikan Teknologi Informasi dan Komunikasi. Volume 2, No.2, http://file.upi.edu/Direktori/JURNAL/PENDIDIKAN_TIK/Jurnal_Pend_TIK_Vol_2_No_2/Metode_Iterative_Dichotomizer_3_(_ID3_)_Untuk_Penyeleksian_Penerimaan_Mahasiswa_Baru.PDF, Januari 2017.