Tag Archives: decision tree

Data Mining – Decision Tree

Decision Tree atau Pohon Keputusan merupakan salah satu cara Data Mining dalam memprediksi masa depan dengan membangun klasifikasi atau regresi model dalam bentuk struktur pohon. Hal tersebut dilakukan dengan cara memecah terus ke dalam himpunan bagian yang lebih kecil lalu pada saat itu juga sebuah pohon keputusan secara bertahap dikembangkan. Hasil akhir dari proses tersebut adalah pohon dengan node keputusan dan node daun. Sebuah node keputusan (misalnya, Cuaca/ Outlook) memiliki dua atau lebih cabang (misalnya, Panas, Berawan dan Hujan). Node daun (misalnya, Bermain) merupakan klasifikasi atau keputusan. Node keputusan paling atas di pohon yang sesuai dengan prediktor terbaik disebut simpul akar. pohon keputusan dapat menangani data deskriptif maupun numerik.

decision_tree_1

Algoritma
Algoritma inti untuk membangun pohon keputusan disebut ID3 oleh J. R. Quinlan dengan cara kerja top-down pada pencarian greedy melalui ruang cabang tanpa teknik backtracking. ID3 menggunakan Entropi dan Information Gain untuk membangun pohon keputusan.

Entropi
Sebuah pohon keputusan dibangun secara top-down dari simpul akar dan melibatkan partisi data ke dalam himpunan bagian yang berisi contoh dengan nilai yang sama (homogen). Algoritma ID3 menggunakan entropi untuk menghitung homogenitas sampel. Jika sampel sudah benar-benar homogen, entropi bernilai nol dan jika pembagian sampel dibagi rata maka entropi bernilai satu.

entropy

Untuk membangun pohon keputusan, kita perlu menghitung dua jenis entropi menggunakan tabel frekuensi sebagai berikut:
a) Entropi yang menggunakan tabel frekuensi satu atribut:

entropy_3

b) Entropi yang menggunakan tabel frekuensi dua atribut:

entropy_2

Information Gain
Information gain didasarkan pada penurunan entropi setelah dataset dibagi oleh atribut. Membangun pohon keputusan adalah seluruh hal tentang penemuan atribut yang mengembalikan information gain tertinggi (yaitu, cabang yang paling homogen).
Langkah 1: Hitung entropi dari target.

entropy_targetLangkah 2: dataset tersebut kemudian dibagi pada atribut yang berbeda. Entropi untuk setiap cabang dihitung. Kemudian ditambahkan secara proporsional, untuk mendapatkan jumlah entropi untuk perpecahan. entropi yang dihasilkan dikurangi dari entropi sebelum perpecahan. Hasilnya adalah Information Gain, atau penurunan entropi.

entropy_attributes

entropy_gainLangkah 3: Pilih atribut dengan Information Gain terbesar sebagai simpul keputusan, membagi dataset oleh cabang-cabangnya dan ulangi proses yang sama pada setiap cabang.

entropy_attribute_best

decision_tree_slices
Langkah 4a: Sebuah cabang dengan entropi 0 adalah simpul daun.

entropy_overcast
Langkah 4b: Sebuah cabang dengan entropi lebih dari 0 akan dipecah kembali.

entropy_sunny
Langkah 5: Algoritma ID3 dijalankan secara rekursif pada cabang-cabang non-daun, sampai semua data terklasifikasikan.

Pohon Keputusan Untuk Aturan keputusan
Sebuah pohon keputusan dapat dengan mudah diubah untuk satu set aturan oleh pemetaan dari simpul akar ke simpul daun satu per satu.

decision_rules

Isu pada Pohon Keputusan
– Bekerja dengan atribut berkelanjutan (binning)
– Menghindari overfitting (terlalu bagus)
– Super Atribut (atribut dengan banyak nilai)
– Bekerja dengan nilai-nilai yang hilang

Sumber : Data Mining