Decisition Tree Learning adalah salah satu metode yang cukup banyak digunakan pada mesin learning. Ada beberapa algoritma yang dapat digolongkan sebagai Decision Tree (DT), yaitu ID3, ASSISTANT dan C4.5.

DT adalah metode untuk memprediksi nilai diskret dari fungsi target. Fungsi yang dipelajari direpresentasikan dalam bentuk decision tree. Tree dapat direpresentasikan juga dengan rules if-then. DT melakukan klasifikasi menggunakan sebuah tree, mulai dari root, node sampai ke leaf (daun). Setiap node melakukan pengujian atribute tertentu, dan mengikuti cabang dari tree ke bawah sampai daun.

Contoh kasus adalah tabel decision tree tentang klasifikasi cuaca yang cocok untuk main tenis. Dengan 3 fitur yaitu: outlook (ramalan cuaca), Humidity (Kelembapan udara) dan Kecepatan Angin.

Outlook memiliki tiga cabang yaitu: sunny (cerah), Overcast (mendung), Rain (Hujan)

Humidity: ada high dan normal

Wind: Strong dan weak

Secara umum DT cocok untuk permasalahan dengan karakteristik berikut:

1. Kondisi dapat digambarkan dengan sepasang nilai atribut (karakter) tertentu.
2. Fungsi target memiliki nilai diskrit
3. Diperlukan Hipotesis yang logis
4. Training data yang mengandung noise, atau data dengan nilai yang hilang

Contohnya penggunaan: diagnosa data medis, analisa resiko kredit,

Algoritma dasar yang digunakan untuk DT adalah ID3 yang diteliti oleh Quinlan pada tahun 1986, dan kemudian dikembangkan menjadi C4.5 juga oleh Quinlan tahun 1993.

Pertanyaan pertama adalah atribut apa yang dipilih menjadi root? Untuk menentukannya, setiap atribut diuji secara statistik untuk menentukan seberapa baik atribut tersebut melakukan klasifikasi data training. Atribut terbaik kemudian dipilih menjadi root. Kemudian cabangnya dipilih lagi berdasarkan atribut mana yang terbaik dst.

Untuk menentukan atribut mana yang terbaik digunakan information gain. Information gain mengukur seberapa baik atribut tersebut memisahkan data berdasarkan klasifikasi yang diinginkan.

Untuk mendapatkan information gain, kita harus mengukur entropy terlebih dahulu. Entropy adalah ukuran impurity (keteracakan) dari data

Contoh dari tabel tentang Cuaca yang baik untuk main tenis:

Kita hitung nilai Gain dengan rumus berikut:

dengan rumus entropi:

diperoleh nilai Gain berikut:

Nilai Gain tertinggi adalah Outlook, sehingga outlook kita pilih menjadi root.

Kemudian untuk memilih cabang dari sunny harus dihitung lagi gain terbaik sebagai berikut:

Karena nilai gain tertinggi adalah humidity maka dipilih cabang dari sunny adalah humidity. kemudian dilakukan perhitungan lagi sehingga diperoleh Decision Tree akhir adalah sebagai berikut:

Contoh video yang menjelaskan tentang merancang decision tree:

Sampai disini dulu. semoga Bermanfaat!

referensi:

Mitchell, Tom Michael. The discipline of machine learning. Vol. 9. Pittsburgh: Carnegie Mellon University, School of Computer Science, Machine Learning Department, 2006