End-to-End Machine Learning Algorithm : Decision Tree

Memahami konsep dasar hingga implementasi algortima machine learning Decision Tree

Sumber : https://www.snexplores.org/article/lets-learn-about-trees

Pada artikel ini, saya akan membahas konsep dasar dari algoritma Decision Tree sebagai salah satu algoritma Machine Learning yang dapat dikatakan mudah untuk dimengerti dan diimplementasikan ketika kita ingin mulai memahami konsep atau cara kerja Machine Learning. Selain pemahaman secara kontekstual, kita akan mempelajari bagaimana cara mengimplementasikan algortima Decision Tree secara teknikal dengan studi kasus sederhana.

1. Pengenalan Decision Tree

Decision Tree sendiri merupakan algritma Machine Learning yang termasuk dalam algoritma Supervised Learning dan Decision Tree sendiri merupakan salah satu dari berbagai macam algortima Supervised Learning yang dapat menyelesaikan Classification dan Regression.

Jenis-Jenis Algoritma Decision Tree

Decision Tree dibagi menjadi 2 jenis berdasarkan dari jenis target class (dependent variable) pada dataset, yaitu :

1. Categorical Variable Decision Tree (Classification Tree)

Merupakan algoritma Decision Tree yang khusus menangani/memprediksi dataset yang variabel target nya berupa data kategorik (categorical data).

2. Continuous Variable Decision Tree (Regression Tree)

Merupakan algoritma Decision Tree yang khusus menangani/memprediksi dataset yang variabel target nya berupa data kontinu (continuous data)

Komponen Penting Decision Tree

Interpretasi komponen dalam Decision Tree hampir menyerupai komponen pada pohon, dan komponen pada Decision Tree sangat lah beragam sehingga kita perlu memahami komponen tersebut agar kedepannya mempermudah kita dalam memahami terminologi-terminologi Decision Tree kedepannya. Berikut merupakan komponen-komponen pentingnya :

Sumber : https://www.kdnuggets.com/2020/01/decision-tree-algorithm-explained.html

• Root Node : Secara umum dapat dikatakan sebagai dasar dari Decision Tree yang letaknya paling atas dan paling awal.
• Splitting : Merupakan proses membagi sebuah node menjadi dua atau lebih sub-node.
• Decision Node : Ketika sebuah sub-node dipecah menjadi sub-node lebih lanjut, maka itu disebut decision node.
• Leaf node/Terminal Node : Node yang tidak terbelah disebut Leaf atau Terminal node.
• Branch/Sub-Tree : Sebuah subbagian dari keseluruhan Decision Tree yang terdiri dari beberapa node. disebut branch atau sub-tree. branch memiliki arah panah yang menunjuk pada branch itu sendiri dan memiliki arah panah yang menunjuk ke arah lain
• Pruning/Pemangkasan : Ketika kita menghapus/menghilangkan sub-node dari decision node atau Decision Tree, proses ini disebut pemangkasan.
• Parent Node dan Child Node : Sebuah node, yang dibagi menjadi sub-node disebut parent node dari sub-node sedangkan sub-node adalah anak atau child node dari parent node.

Tambahan : root node dan decision node biasanya merupakan representasi dari atribut dan leaf node merupakan representasi dari target class

2. Konsep dan Tantangan Decision Tree

Tantangan dalam pengimplementasian Decision Tree adalah proses mengidentifikasi dan memilih atribut (data independent) yang perlu kita pertimbangkan sebagai root node atau node selanjutnya di setiap proses percabanyannya. Hal ini dikenal dengan pemilihan atribut. Kita dapat menggunakan metode dan langkah-langkah pemilihan atribut yang berbeda untuk mengidentifikasi atribut mana yang bagus untuk dianggap sebagai root node atau node di setiap percabangannya.

Hal yang perlu kita ingat adalah proses pengambilan keputusan dalam proses pemisahan (splitting) mempengaruhi akurasi pada model. Hal ini juga memungkinkan terjadinya perbedaan Kriteria keputusan untuk kasus Decision Tree klasifikasi dan Decision Tree regresi. Berikut pengambaran dari Decision Tree:

Sumber : https://slideplayer.com/slide/13018181/

Penjelasan Gambar:

• Node dalam Decision Tree sendiri merupaka representasi dari atribut-atribut dalam Data Training.
• Node-node pada Decision Tree normalnya mengandung atribut-atribut yang bersifat numerical data (1,2,3,..) dan categorical data (yes/no) dalam satu tree.
• Atribut dengan data numerik juga memungkinkan untuk memiliki node lebih dari satu dengan nilai thresholds yang berbeda.

3. Memahami Algoritma Entropy dan Gini Impurity Pada proses Pembuatan Decision Tree

Seperti yang sudah di singgung sebelumnya, tantangan dalam membangun model Decision Tree adalah menentukan atribut untuk root node dan atribut untuk node di cabang selanjutnya, yaitu dengan mengukur tingkat impurity atribut (independent variable) terhadap target (dependent variable). Atribut yang sempurna untuk dijadikan root node atau node adalah atribut yang yang memiliki nilai purity (homogenitas) tinggi, atau dengan kata lain atribut yang memiliki nilai impurity (heterogenitas) rendah.

Tambahan : Impurity merupakan ukuran homogenitas label pada node atau juga pada atribut

Dalam proses menghitung impurity , Decision Tree biasanya melakukan perulangan untuk membuat simple tree untuk setiap atribut. Pada kasus classification tree, simple tree tersebut nantinya akan menghitung seberapa baik atribut tersebut memprediksi label class pada target class.

Disclaimer : penggambaran yang digunakan merupakan properti milik akun youtube Statquest with Josh Starmer. Digunakan karena ilustrasi lebih mudah untuk diinterpretasikan dan dipahami.

Berikut contoh ilustrasi dan penjelasan dalam memahami impurity pada sebuah node dalam Decision Tree:

Sumber : https://statquest.org/

Kita akan menggunakan dataset/table pada gambar diatas untuk penjelasan ini agar mudah untuk dipahami

Step 1

Secara umum, Decision Tree akan memroses satu per satu atribut terhadap class target nya. Model memilih atribut pertama (Loves Popcorn) untuk dibuatkan simple tree (kanan gambar). Lalu, kita akan melihat hasil prediksi dari setiap nilai pada baris dalam atribut “Loves Popcorn” dengan alur atau workflow berikut :

• If “Loves Popcorn” == “Yes” then move to “True (leaf on the left)” else move to “False (leaf on the right)”

and then

• if “Loves Cool As Ice” == “No” then fill in Part “No” else fill in Part “Yes”

Hal tersebut dilakukan hingga baris paling akhir dalam sebuah dataset dan lanjut ke dalam atribut selanjutnya, seperti pada ilustrasi dibawah.

Step 2

Setelah menghitunng nilai impurity pada atribut “Loves Popcorn”, maka dapat melanjutkan perhitungan ke atribut selanjutnya. Hingga selesai seperti pada gambar ilustrasi dibawah.

• Setelah membuat simple tree pada setiap atribut, maka kita dapat melihat impurity pada setiap atribut.
• 3 leaves (Popcorn True, Popcorn False, and Soda True) digambar atas, menunjukan bahwa leaf tersebut bersifat impure dan 1 leaf (Soda False) bersifat pure.
• Secara visual, 2 leaves dari atribut “Loves Popcorn” merepresentasikan bahwa atribut tersebut impure atau buruk dalam memprediksi target class.
• Sedangkan pada atribut “Loves Soda” memiliki 1 leaf yang bersifat pure (Soda False), maka atribut soda merupakan atribut yang baik dalam memprediksi target class.

Begitulah cara Decision Tree menentukan atrbut yang pas pada sebuah node. Namun, Menjadi sangat jelas dan bagus apabila kita dapat memahami perbedaan impuity pada setiap atribut dengan hal yang bersifat kuantitatif. Oleh karena itu, ada beberapa cara untuk mengkalkulasikan nilai impurity pada setiap atribut, yaitu dengan :

1. Gini Impurity
2. Entropy & Information Gain

3.1 Gini Impurity

Gini Impurity merupakan metode pengukuran yang digunakan untuk membangun Decision Tree untuk menentukan bagaimana feature/attribute dari kumpulan data harus membagi node untuk membentuk pohon.

Rumus Gini Impurity adalah

Penjelasan : Rumus Gini Impurity adalah dengan mengurangkan jumlah probabilitas kuadrat dari setiap kelas dari satu

Berikut langkah-langkah pembuatan Decision Tree dengan menggunakan Gini Impurity sebagai metode perhitungan impurity pada suatu atribut dengan menggunakan dataset/tabel yang sama pada kasus sebelumnya:

Step 1

Untuk melakukan perhitungan Gini Impurity, kita dapat memulainya pada individual leaves pada simple tree atribut. Kita menghitung prediksi leaf “True” terhadap atribut “Popcorn” terlebih dahulu.

Setelah itu, kita menghitung nilai Gini Impurity dengan :

artinya, nilai Gini Impurity leaf “True” adalah 0.375

Lalu kita menghitung prediksi leaf “False” terhadap atribut “Popcorn”

Setelah itu, kita menghitung nilai Gini Impurity dengan :

artinya, nilai Gini Impurity leaf “False” adalah 0.444

Step 2

Karena leaf “True” dan leaf “False” pada atribut “Popcorn” tidak merepresentasikan jumlah total nilai yang sama, dengan total leaf “True” adalah 4 dan total leaf “False” adalah 3. Maka, kita menggunakan Weighted Average (rerata tertimbang) dari nilai impurity setiap leaf nya untuk menghitung total Gini Impurity pada atribut “Popcorn”.

Maka, nilai Gini Impurity pada atribut “Popcorn” adalah 0.405

Step 3

Hal yang sama juga dilakukan pada atribut selanjutnya, yaitu atribut “Soda” dengan mengulang pada step 1 dan 2.

HIngga ditemukan hasil Gini Impurity pada atribut “Soda”, yaitu 0.214

Step 4

Selanjutnya kita menghitung Gini Impurity pada atribut “Age”. Karena atribut “Age” merupakan atribut yang nilanya numerik (diskrit ataupun kontinu), maka penghitungan Gini Impurity akan sedikit rumit.

Step 4.1

• Mengurutkan baris pada atribut “Age” berdasarkan dari nilai terendah ke nilai tertinggi (Ascending)
• Lalu, kita menghitung rata-rata pada 2 baris secara berkelanjutan, seperti pada ilustrasi dibawah

• Sehingga, kita bisa menghitung Gini Impurity pada setiap nilainya, dengan cara membuat simple tree pada setiap nilai (sama seperti mencari nilai impurity terendah menggunakan Gini Impurity pada setiap atribut) dan nilai Gini Impurity terendah akan merepresentasikan atribut numerik tersebut sebagai node.

Step 4.1.1

• Kita membuat simple tree berdasarkan nilai “Age < 9.5” terlebih dahulu, dengan cara kita melihat nilai tersebut terhadap kolom hasil prediksi.

If “Age < 9.5” == “Yes” then move to “True (leaf on the left)” else move to “False (leaf on the right)”

and then

If “Loves Cool As Ice” == “No” then fill in Part “No” else fill in Part “Yes”

• Lalu, menghitung Gini Impurity pada masing-masing leaf :
• Leaf “True”

• Leaf “False”

• Total Gini Impurity

Begitu pula pada nilai selanjutnya

Dari Gini Impurity semua nilai, nilai 15 dan 44 memiliki nilai Gini Impurity terendah dari semua nilai Gini Impurity, jadi kita dapat menggunakan salah satu dari 15 dan 44.

Di kasus ini, kita menggunakan nilai 15 untuk atribut “Age”. maka node atribut “Age” akan menjadi “Age < 15” dengan nilai Gini Impurity 0.343.

Step 5

Setelah kita mengetahui nilai Gini Impurity dari masing-masing atribut, maka kita dapat membandingkan nilai untuk mencari nilai Gini Impurity mana yang paling terkecil untuk dijadikan root node

Atribut dengan nilai Gini Impurity paling rendah adalah “Loves Soda”

Step 6

Maka kita menempatkan atribut “Loves Soda” sebagai root node dari Decision Tree yang kita buat.

Pada leaf “False”, leaf tersebut sudah bersifat pure dengan 0 Yes dan 3 No. Namun, kita masih menemukan sifat impure pada leaf “True” dengan 3 Yes dan 1 No, sehingga node tersebut perlu dilakukan splitting lagi menjadi node-node baru berdasarkan atribut selanjutnya.

Karena sisa 2 atribut, atribut “Love Popcorn” dan “Age”, maka kita akan mengkalkulasikan dan membandingkan nilai Gini Impurity 2 atribut tersebut untuk menjadi node di proses splitting selanjutnya berdasarkan baris (row) yang nilai atribut “Love Soda” bernilai Yes/True, Seperti pada gambar dibawah

Setelah melakukan proses pencarian nilai Gini Impurity pada tiap atribut dengan cara yang sama pada proses sebelumnya, maka didapat nilai berikut:

Maka, node untuk percabangan atau proses splitting selanjutnya adalah menggunakan “Age < 12.5” sebagai representatif dari atribut “Age” dan menjadi leaf karena sudah bersifat pure dan tidak ada lagi nilai lagi yang terbagi pada class label “Yes” ataupun “No”.

Step 7

Langkah terkahir adalah kita menetapkan nilai pada tiap leaf berdasarkan class label yang memiliki nilai terbanyak (Majority Value), seperti pada gambar berikut:

Tambahan :

Berdasarkan gambar diatas, karena hanya sedikit orang yang berhasil mencapai tahap tersebut dengan ditandai hanya terdapat 1 nilai pada class label “No”, hal ini sudah untuk mendapatkan tingkat kepercayaan tinggi dan memungkinkan untuk terjadinya overfit atau nilai variance tinggi pada model Decision Tree kita, maka dapat dilakukan 2 cara:

• Melakukan Pruning
• Memberikan Limitasi nilai label class pada setiap leaf untuk membatasi pertumbuhan tree pada model Decision Tree kita

3.2 Entropy dan Information Gain

Selain menggunakan Gini Impurity, penggunaan Entropy juga dapat menjadi alternatif dalam menentukan proses pemilihan root node, node, dan splitting/percabangan pada Decision Tree.

3.2.1 Entropy

• Entropy merupakan sebuah nilai informasi yang merepresentasikan tingkat/ukuran impurity pada suatu atribut.
• Semakin besar nilai Entropy, artinya proporsi class label 1 dan class label 2 semakin seimbang (balance). Kebalikannya, nilai Entropy akan semakin mengecil apabila proporsi salah satu class label mendekati 1 ataupun 0. Berikut penggambarannya :

Rumus Entropy adalah

Contoh perhitungan Entropy:

Pada sebuah dataset, terdapat 10 instance dan 2 label class, “ya” dan “tidak”

Maka, kita dapat kita simpulkan bahwa :

N = 10

P1 (Ya) = 0.9

P2 (Tidak) = 0.1

E(D) = — 0.9 Log2 0.9–0.1 Log2 0.1

E(D) = 0.469

Diketahui bahwa, nilai Entopy nya 0.469

3.2.2 Information Gain

• Pada dasarnya, Information Gain menggunakan nilai Entropy untuk membuat keputusan pada proses spliting atau percabangan berdasarkan atribut dalam Decision Tree.
• Information Gain merupakan selisih antara Entropy dataset awal dengan rata-rata dari Entropy masing-masing bagian partisi
• Jika nilai pada Entropy kecil, maka Information Gain akan tinggi nilainya dan begitupula sebaliknya.
• Algortima Information Gain:

1. Untuk menghitung Information Gain pada suatu atribut, kita akan mempartisi data target class berdasarkan label atribut tersebut. Contoh : kita menggunakan atribut “Umur”
2. Atribut gender merupakan data kategorik, yang berisi label “Muda” dan “Tua”
3. Setelah melakukan mempartisi menjadi 2 bagian (Muda dan Tua), lalu kita menghitung nilai Entropy pada masing-masing label atribut (Muda dan Tua).
4. Setelah mendapatkan nilai Entropy dari 2 label tersebut, kita menghitung nilai Information Gain menggunakan nilai Entropy dari masing-masing label (Muda dan Tua)
5. Lalu, didapatkan nilai Information Gain dari atribut tersebut.
6. Lakukan kembali pada atribut selanjutnya untuk mendapatkan nilai Information Gain dari semua atribut untuk nantinya dilakukan perbandingan dalam menentukan atribut mana yang akan menjadi root node atau node dari cabang selanjutnya. Semakin tinggi nilai information Gain, maka semakin homogen atribut tersebut terhadap class label, dan begitu pula sebaliknya.

• Rumus Information Gain adalah

Contoh perhitungan Information Gain:

Dari dataset/table tersebut, kita akan menentukan atribut mana yang akan menjadi root node pada Decision Tree kita

Step 1

Pertama, kita menghitung nilai daripada entropy dataset/table

N = 10

P1 (Ya) = 0.5

P2 (Tidak) = 0.5

E(D) = — 0.5 Log2 0.5–0.5 Log2 0.5

E(D) = 1

Nilai entropy pada dataset/table adalah 1

Step 2

Kedua, kita akan mempartisi berdasarkan atribut “Umur” dulu dan menghitung Information Gain nya

• Muda

N = 5

P1 (Ya) = 0.4

P2 (Tidak) = 0.6

E(D) = — 0.4 Log2 0.4–0.6 Log2 0.6

E(D) = 0.971

• Tua

N = 5

P1 (Ya) = 0.4

P2 (Tidak) = 0.6

E(D) = — 0.4 Log2 0.4–0.6 Log2 0.6

E(D) = 0.971

• Information Gain

IG = 1.000–5/10 (0.971) — 5/10 (0.971)

IG = 0.029

Step 3

Kedua, kita akan mempartisi berdasarkan atribut “Gender” dan menghitung Information Gain nya

• Laki-Laki

N = 6

P1 (Ya) = 0.83

P2 (Tidak) = 0.17

E(D) = — 0.83 Log2 0.83–0.17 Log2 0.17

E(D) = 0.650

• Perempuan

N = 4

P1 (Ya) = 0.0

P2 (Tidak) = 1.0

E(D) = — 0.0 Log2 0.0–1.0 Log2 1.0

E(D) = 0

• Information Gain

IG = 1–6/10 (0.650) — 4/10 (1.0)

IG = 0.610

Step 4

Setelah mendapatkan nilai Information Gain setiap atribut, kita membandingkan terkait mana atribut dengan nilai Information Gain tertinggi.

Step 5

Maka, kita memilih atribut “Gender” untuk menjadi root node pada Decision Tree yang ingin kita buat. Dalam hal ini, pendekatan selanjutnya sama dengan pendekatan jika kita menggunakan “Gini Impurity”. Yang membedakan adalah bagaiaman cara menentukan atribut untuk root node dan node pada setiap akar percabangan.

Kelebihan Decision Tree

• Decision Tree merupakan salah satu dari algoritma machine learning lainnya yang mudah diimplementasikan dan mudah dipahami
• Simple dalam mengaplikasikan kasus Klasifikasi dan Regresi
• Tidak perlu menggunakan proses Feature Transformation dan normalisasi jika data kita bersifat non-linear

Kekurangan Decision Tree

• Jumlah feature yang digunakan mempengaruhi kompleksitas dan waktu yang dibutuhkan. Termasuk waktu pada saat proses training model
• Jika ukuran data terlalu banyak atau bersifat Big Data, maka Decision Tree tersebut dapat menumbuhkan banyak node dan percabangan yang dapat mengakibatkan terjadinya Overfitting
• Hanya cocok untuk data yang tidak terlalu banyak dan pada kasus regresi belum bisa memberikan performa yang baik dibandingkan algoritma regresi lainnya.

4. Implementasi Decision Tree

Setelah kita memahami bagaimana cara kerja suatu algortima yang bernama Decision Tree menggunakan data Car Evaluation Dataset yang kita unduh dari platform Kaggle. Dengan data tersebut, kita akan memprediksi apakah mobil tersebut layak digunakan data tidak.

Step 1

Import Library

proses pertama yang akan kita lakukan adalah proses import beberapa library sebagai tools/media dalam menjalankan proses pembangunan model Machine Learning

Step 2

Import Dataset

Kita memasukan dataset “car_evaluation.csv” yang sebelumnya sudah kita masukan ke repository GitHub agar lebih mudah prosesn pemanggilan datanya

Step 3

Data Investigation

Dalam data investigation ini, kita melakukan beberapa hal yang berkaitan dengan struktur dan kelengkapan pada data, termasuk data duplikat, data kosong, dan data typo. Dalam proses ini mungkin dapat dikatakan sebagai proses data cleaning.

Step 4

Exploratory Data Analysis (EDA)

Dalam tahap ini, kita melakukan beberapa pendekatan untuk mendapatkan insight lebih dari hasil dari dataset kita. Namun, karena tipe data dari keseleuruna kolom dalam dataset yang kita gunakan bertipe katogrik ordinal, maka tidak banyak yang bisa kita lakukan analisa lebih lanjut.

Step 5

Data Preparation

Tahap ini kita melakukan persiapan dalam membagi data menjadi data training dan data testing. Karena semua atribut bersifat kategorikal ordinal, maka kita melakukan feature enginerring dengan ordinal encoder pada semua atribut.

Step 7

Decision Tree using Gini Impurity

Pada proses modelling Decision Tree ini, kita menggunakan Gini Impurity pada parameter “criterion” dengan max_depth=3. Nilai accuracy yang didapatkan adalah 0.8179 dan model yang kita buat tidak overfit

Step 8

Decision Tree using Entropy

Pada proses modelling Decision Tree ini, kita menggunakan Entropy pada parameter “criterion” dengan max_depth=3. Sama dengan Gini Impurity, Nilai accuracy yang didapat adalah 0.8179 dan juga model yang kita buat tidak overfit.

Kesimpulan

• Dalam project ini, saya mencoba membandingkan model Decision Tree menggunakan Gini Impurity dengan Entropy & Information Gain
• Model bekerja dengan baik, yang mana hal ini direpresentasikan oleh skor akurasi model pada kedua kasus model yang sama-sama ditemukan sebesar 0.8179.
• Model pada kedua tipe tidak mengalami ovefitting ataupun under fitting, hal ini juga direpresentasikan dengan nilai akurasi pada data training sebesar 0.8025 dan akurasi data testing sebesar 0.8179
• Hal yang perlu ditingkatkan adalah proses pengimplementasian pada data yang lebih banyak daripada data ini. Secara spesifik mungkin dapat dilakukan Hyperparameter tuning pada model, dan menghitung Cross Validation pada model untuk membandingkan Hyperparameter limitasi kedalaman pada Decision Tree.
• Kita tidak melakukan pruning pada model, karena model kita dinilai tidak overfit

Referensi :

• https://www.kdnuggets.com/2020/01/decision-tree-algorithm-explained.html
• https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/
• https://statquest.org/statquest-decision-trees/
• https://towardsdatascience.com/decision-trees-14a48b55f297
• https://towardsdatascience.com/tagged/information-gain

Project lengkap nya dapat dilihat disini