Decision Tree Classifier Concepts

Definition

Decision Tree atau pohon keputusan merupakan algoritma yang menggunakan graph berbentuk seperti pohon yang digunakan sebagai pendukung pengambilan keputusan. Struktur dari Decision Tree sama seperti flowchart, sehingga untuk setiap sub-node akan menggunakan output dari node sebelumnya, dimana sub-node tersebut bertindak sebagai penguji untuk setiap atribut. Decision Tree adalah pengklasifikasi yang dinyatakan sebagai partisi rekursif dari ruang instance.

Berikut merupakan ilustrasi mengenai Decision Tree :

Istilah yang digunakan pada Decision Tree

• Root Node : representasi semua sampel atribut. Pada Gambar , Root Node adalah atribut Age.
• Internal Node : sub-node hasil pemecahan dari Root Node yang memiliki output. Pada Gambar, Internal Node adalah atribut Gender dan Last R.
• Leaf / Terminal Node : sub-node yang tidak memiliki output. Pada Gambar, Leaf dilambangkan dengan segitiga.

Subset of Supervised Learning

Algoritma Decision Tree termasuk kedalam kategori Supervised Learning. Oleh sebab itu, untuk mengimplementasikan Decision Tree harus memiliki variabel target yang telah ditentukan sebelumnya. Pendekatan yang dilakukan untuk membagi node menjadi 2 atau lebih sub-node dapat mempengaruhi akurasi Decision Tree.

Gini Index

Salah satu algortima yang dapat digunakan adalah Gini Index. Aturan dari Gini Index adalah dari suatu populasi secara acak, jika kita memilih dua item maka mereka harus dari kelas yang sama dan memiliki probabilitas 1 jika populasinya murni.

Berikut cara membagi node menggunakan Gini Index:

• Hitung menggunakan rumus jumlah kuadrat probabilitas sukses dan gagal

• Hitung pemisah menggunakan Gini Index skor hasil perhitungan dari setiap node

Decision Tree Algorithm

Adapun algoritma dari Decision Tree adalah sebagai berikut:

• Mulai bangun Tree dari Root Node
• Menentukan atribut dari data
• Hitung skor dari tiap atribut dengan berbagai algoritma yang ada, menggunakan Gini Index
• Tempatkan atribut sesuai dengan sub-node berdasarkan perhitungan pada langkah sebelumnya
• Ulangi langkah tersebut pada tiap sub-node.
• Hilangkan sub-node yang tidak meningkatkan akurasi. Hal ini bertujuan untuk mengurangi resiko overfitting

See the tutorial here