🌴Decision tree

1. Pengertian Decision tree

Decision tree merupakan salah satu model machine learning yang termasuk kedalam supervised learning. decision tree berbentuk seperti graph yang memodelkan keputusan. Digunakan untuk merepresentasikan keputusan dan pengambilan keputusan secara visual dan eksplisit. Decision tree disebut juga dengan istilah CART (Classification and Regression Trees) yang diperkenalkan oleh Leo Breiman untuk merujuk pada algoritma Decision Tree yang dapat digunakan untuk masalah klasifikasi atau regresi. Algoritma CART menyediakan dasar untuk algoritma penting seperti bagged decision trees, random forest and boosted decision trees.

Istilah penting dalam Decision tree

Gambar 7. 1 Decision tree

Model decision tree adalah binary tree dimana tree tersebut terdiri dari bebrapa komponen yaitu :

1. Setiap Node mewakili Fitur (Atribut/ variable x) pada gambar 7.1 node disimbolkan dengan persegi Panjang

2. Setiap Branch atau Link atau Edge mewakili Keputusan atau Aturan yang disimbolkan dengan panah

3. Setiap leaf mewakili Hasil keputusan yang merupakan output variable digunakan sabagai hasil prediksi, disimbolkan dengan bentuk elips.

Selain komponen diatas terdapat beberapa istilah yang ada dalam decision tree

1. Splitting / Pemisahan: Ini adalah proses membagi node menjadi dua atau lebih sub-node.

2. Decision Node: Ketika sub-node terpecah menjadi sub-node lebih lanjut, maka itu disebut node keputusan.

3. Pruning / Pemangkasan: Saat dilakukan penghapusan sub-node dari node keputusan, proses ini disebut pemangkasan.

4. Branch / Sub-Tree: Sebuah sub-bagian dari seluruh pohon disebut cabang atau sub-pohon.

5. Parent and Child Node (Node Induk dan Anak): Node, yang dibagi menjadi beberapa sub-node disebut node induk dari sub-node sedangkan sub-node adalah anak dari node induk

Pada permasalahan klasifikasi leaf node dari decision tree mewakili kelas sedangkan pada permasalahan regresi nilai variabel respons untuk instance yang terdapat dalam leaf node dapat dirata-ratakan untuk menghasilkan estimasi untuk variabel respons. Cara untuk melakukan prediksi pada decision tree untuk data pengujian hanya perlu mengikuti edge sampai mencapai leaf node.

1. Contoh Decision tree

Example Decision Tree

Gambar 7.2 merupakan contoh dari decision tree, contoh tersebut merupakan data fiktif yang bertujuan untuk memudahkan gambaran decision tree. Pada gambar 7.2 terdapat dua buah fitur/ input variable (x) yaitu height dalam satuan cm dan weight dalam satuan kg. contoh diatas merupakan tree yang digunakan untuk permasalahan klasifikasi yang memiliki dua buah keputusan/kelas yaitu kelas Male dan Kelas Female. Contoh tree pada gambar 7.2 juga dapat disimpan dalam bentuk file sebagai grafik atau seperangkat aturan seperti gambar 7.3

Gambar 7. 3 Kumpulan Aturan Decision tree

1. Tahapan Algoritma Decision Tree

Pada Decision tree pembuatan tree merupakan Langkah awal yang harus dilaksanan. Dalam pembuatan tree diperlukan perhitungan menggunakan Information Gain ataupun Gini Index untuk menentukan Root node/ node selanjutnya. Berikut merupakah tahapan pembuatan tree secara top-down:

1. Pada iterasi pertama dilakukan pemilihan Root Node didasarkan pada Gini Indeks terendah atau Information Gain tertinggi dari keseluruhan fitur (variable x) pada data training.

2. Kemudian memisahkan himpunan S untuk menghasilkan subset data

3. Selanjut proses akan diulang untuk mencari decision node yang akan menjadi cabang selanjutnya. Penentuan decision node juga menggunakan Gini Indeks terendah atau Information Gain tertinggi. Akan tetapi yang membedakan adalah fitur yang digunakan adalah fitur yang tidak pernah menggunakan sebelum nya (subset data)

4. Algoritma terus menerus berulang pada setiap subset data hingga menemukan leaf yang merupakan label kelas

5. Information Gain dengan menggunkan Entropy

Entropy digunakan untuk menghitung ketidakteraturan dalam artian entropy akan menghitung homogenitas suatu fitur atribut (A) dari sebuah fitur yang ada di sample data (S). Entropy digunakan untuk mengukur jumlah ketidakpastian dalam variable. Berikut merupakan formula yang digunakan untuk mengukur entropy:

$[ H(X) = - \sum_{i=1}^{n} P(x_i) \log_b P(x_i) ]$

Di sini:

• $H(X)$ adalah entropi Shannon dari distribusi probabilitas $x$

• $P(x_i)$ adalah probabilitas kemunculan nilai $x_i$

• $\log_b$ adalah logaritma basis $b$

• $n$ adalah jumlah kemungkinan nilai $x$

Karena log dari angka kurang dari 1 akan negatif, seluruh jumlah dinegasikan untuk menghasilkan nilai positif.

Penjumlahan dari total entropy bisa lebih dari 1.

Gambar 7. 4 Ilustrasi Entropy

Pada gambar 7.4 menunjukan ilustrasi entropy untuk ountcome/kelas yang memiliki dua buah label. Entropy(S) adalah jumlah bit yang diperkirakan dibutuhkan untuk dapat mengekstrak suatu kelas (+ atau -) dari sejumlah data acak pada ruang sample S. Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas. Semakin kecil nilai Entropy maka semakin baik untuk digunakan dalam mengekstraksi suatu kelas.

Contoh : lemparan koin hanya akan memiliki dua outcome(kelas) yaitu kelas kepala dan kelas ekor. Probabilitas koin akan mendarat kepala adalah 0,5, dan probabilitas koin akan mendarat di ekor adalah 0,5. Sehingga dari contoh tersebut didapatkan Entropi nya adalah :

Information Gain merupakan perbedaan antara entropi pada parent node, 𝐻 (𝑇)), dan rata-rata bobot dari entropi pada child node. Information Gain berdasarkan pada penurunan entropi setelah pemisahan kumpulan data pada atribut. Membangun decision tree adalah tentang bagaimana menentukan node berdasarkan information gain tertinggi (yaitu cabang yang paling homogen). Formula untuk menghitung information gain adalah sebagai berikut :

𝑇 adalah kumpulan instance (banyaknya instance). 𝑎 adalah fitur yang sedang diuji.

Pembuatan tree dengan menggunakan information gain

1. Hitung entropy untuk sekumpulan dataset H(X)

2. Untuk setiap atribut / feature, lakukan

3. Hitung entropy untuk setiap fitur 𝒙𝒊

4. Ambil Entropi Informasi Rata-rata dari Atribut / Fitur Saat Ini, 𝒙𝒊

5. Hitung information gain untuk Atribut / Fitur saat ini

6. Pilih atribut / fitur yang memiliki information gain tertinggi

7. Ulangi proses hingga mendapatkan tree yang di inginkan.