Decision Tree Model From Scratch

Link GitHub : https://github.com/axeltanjung/decision_tree_from_scratch

A. Latar Belakang

Dalam project ini, saya akan membangun algoritma Decision Tree tanpa menggunakan library atau framework yang sudah ada, melainkan membangunnya dari nol menggunakan bahasa pemrograman python.

Decision Tree adalah salah satu algoritma machine learning yang populer dan digunakan untuk task klasifikasi dan regresi. Tujuannya adalah untuk membuat model prediksi yang dapat mempelajari pola dari data training dan menghasilkan decision atau prediksi berdasarkan fitur-fitur yang ada. Dalam pengenalan ini, saya akan menjelaskan langkah-langkah utama dalam membangun Decision Tree dari awal.

Pertama, kita perlu mempersiapkan data training yang terdiri dari contoh-contoh dengan fitur-fitur dan label kelas yang terkait.

Selanjutnya, kita akan memilih atribut splitting yang paling informatif untuk membangun node-node dalam Decision Tree. Proses pemilihan ini dapat dilakukan menggunakan kriteria seperti information gain, indeks Gini, atau pengurangan kesalahan klasifikasi. Setelah pemilihan atribut splitting, kita akan membagi data training menjadi subset yang lebih kecil berdasarkan nilai-nilai atribut pada setiap node. Langkah ini akan terus diulangi untuk setiap subset data yang dihasilkan, sehingga terbentuklah struktur decision tree.

Selama proses pembangunan Decision Tree, kita juga perlu memperhatikan kondisi stop yang menghentikan proses splitting dan pembentukan node baru. Kondisi stop ini dapat ditentukan berdasarkan kedalaman maksimum (max_depth), jumlah minimum sample dalam setiap node, atau ketika tidak ada atribut splitting yang tersisa. Setelah Decision Tree selesai dibangun, kita dapat menggunakan model ini untuk melakukan prediksi pada data baru. Model Decision Tree akan mengikuti cabang-cabang berdasarkan fitur-fitur pada data uji dan menghasilkan prediksi berdasarkan label kelas yang terkait dengan leaf yang dicapai.

Melalui paparan ini, saya berharap dapat memberikan pemahaman dasar tentang langkah-langkah yang terlibat dalam membangun Decision Tree dari awal. Algoritma Decision Tree sangat berguna dalam memecahkan masalah klasifikasi dan regresi, dan pemahaman tentang bagaimana mereka bekerja dari dasar dapat menjadi landasan yang kuat dalam memahami algoritma machine learning lainnya.

B. Advantage and Disadvantage Model

Dibandingkan dengan metode yang lebih tradisional, decision tree untuk regresi dan klasifikasi memberikan beberapa manfaat berikut:

• Beberapa orang berpikir bahwa decision tree, dibandingkan dengan metode regresi dan klasifikasi lainnya, lebih mirip dengan pengambilan keputusan manusia.
• Orang-orang dapat dengan mudah memahami decision tree. Sebenarnya, decision tree membutuhkan penjelasan yang lebih sedikit dibandingkan dengan regresi linear.
• Decision tree dengan mudah mengatasi prediktor kualitatif dan tidak memerlukan penggunaan variabel dummy.
• Decision tree dapat direpresentasikan secara grafis dan cukup sederhana untuk dipahami oleh non-pakar (terutama jika pohon tersebut kecil).

Namun, terdapat beberapa kekurangan dalam menggunakan model decision tree sebagai berikut:

• Sayangnya, dibandingkan dengan beberapa metode regresi dan klasifikasi lainnya, decision tree biasanya tidak memiliki tingkat akurasi prediksi yang sama.
• Decision tree mungkin juga tidak sangat tangguh. Dengan kata lain, perubahan kecil pada data dapat memiliki dampak besar pada bentuk akhir decision tree yang diprediksi. Namun, kinerja prediksi decision tree dapat signifikan meningkat dengan menggabungkan banyak decision tree menggunakan teknik seperti bagging, random forests, dan boosting.

C. Component of Learning

1. Part of Algorithm

• Root Node: Node pertama dalam decision tree. Ini mewakili fitur atau atribut yang paling penting dalam pembagian data.
• Node Internal: Node dalam decision tree yang tidak termasuk root node atau leaf. Node internal mewakili keputusan berdasarkan fitur-fitur atau atribut-atribut yang lebih spesifik.
• Leaf Node: Node-terminal dalam decision tree yang tidak memiliki anak. Node leaf mewakili hasil atau label kelas yang dihasilkan oleh decision tree.
• Cabang (Branch): Cabang-cabang dalam decision tree yang menghubungkan node-node. Cabang mewakili penghubung antara fitur atau atribut dengan keputusan atau sub-tree berikutnya.
• Test Attribut: Fitur atau atribut yang digunakan untuk membagi data menjadi kelompok-kelompok yang lebih kecil dalam setiap node.
• Pengelompokan Data (Data Partitioning): Proses memisahkan data ke dalam subset yang lebih kecil berdasarkan nilai-nilai fitur atau atribut yang digunakan dalam pengujian.
• Kriteria Pemilihan Test Attribut: Kriteria yang digunakan untuk memilih atribut terbaik untuk membagi data, seperti information gain, indeks Gini, atau pengurangan kesalahan klasifikasi.
• Pruning: Proses menghapus cabang-cabang yang tidak relevan atau node leaf yang tidak memberikan keuntungan informasi yang signifikan.

2. Hypothesis

Set seluruh splitting variable

Pilih best feature untuk predictor categorical (Contoh)

Hitung classification error pada keputusan

A. Root node

— Prediction : Practice

— Mistake : 8

— Error : 8/10 = 0.4

B. Split pada Windy

— Yes node

1. Prediction : Practice
2. Mistake : 0
3. Error : 0/18 = 0

— No node

1. Prediction : Not Practice
2. # Mistake : 2
3. Error : 2/18 = 0.111

— Total Error : 0 + 0.11 = 0.11

C. Split pada Walk Cart

— Cart node

1. Prediction : Practice
2. # Mistake : 0
3. Error : 0/18 = 0

— No node

1. Prediction : Not Practice
2. # Mistake : 2
3. Error : 4/18 = 0.22

— Total Error : 0 + 0.22 = 0.22

Pada contoh diatas, mana yang menjadi best splitting fitur?

Improvement

• Root →Windy

0.4–0.11 = 0.29

Gain improvement 0.29 (Best features fitur split)

• Root →Walk Cart

0.4–0.22 = 0.18

Gain improvement 0.18

Pilih best feature untuk Numerical Predictor (Contoh)

• Memilih threshold yang membagi data menjadi dua region, R1 dan R2

• Memprediksi output dari setiap region, klasifikasi (majority vote) and regresi (average vote)
• Selanjutnya, hitung klasifikasi error untuk tiap region

1. R1 error = 2/15
2. R2 error = 1/15
3. Total = 3/15 = 0.2

• Terdapat beberapa threshold yang mungkin untuk melakukan splitting predictor numerical dengan mempertimbangkan mid point

Feature Split Algorithm

• Terdapat subset dari data X pada node tree
• Pada setiap fitur di X, split data berdasarkan fitur p and hitung classification error split
• Pilih feature-p* dengan error gain tertinggi

1. Impurity : Hitung ketidakseragaman data,

more uncertainty → more impure

2. Information gain : Bandingkan impurity sebelum & setelah split,

more gain → more information

Hyperparameter

- Impurity criterion

C. Parameter

Tidak ada, Decision Tree adalah instance-based atau non-parametric algorithm

D. Learning Objective

Gunakan greedy algorithms and maksimalkan information gain

Untuk memecahkan masalah dengan memilih opsi terbaik, decision tree menggunakan pendekatan greedy dan rekursif. Berikut adalah langkah-langkah untuk membuat algoritma tersebut:

1. Mulai dengan blank tree

2. Pilih best attribute (feature) selanjutnya yang memaksimalkan information gain

1. Bagi node

2. Recursively step #2

• note : Jangan membagi node jika sudah pure, dan jangan membagi jika tidak ada fitur yang dapat membedakan kelas-kelas.

Avoiding Overfitting

1. Mulai dengan pohon bagian teratas (root node)

2. Tumbuhkan pohon dengan “splitting” atribut satu persatu dengan mempertimbangkan “node impurity” untuk menentukan atribut yang di split. Tumbuhkan pohon yang besar pada data training menggunakan splitting biner rekursif, berhenti hanya ketika setiap node terminal memiliki jumlah observasi yang lebih sedikit dari jumlah minimum yang telah ditentukan sebelumnya.

3. Buat leaf node pada leaf menggunakan majority vote atau average

4. Lakukan tree pruning pada saat decision tree telah mencapai cabang dasar. Cost complexity pruning harus diterapkan pada pohon besar tersebut untuk menghasilkan list subtrees terbaik sebagai fungsi

5. Pilih α menggunakan Cross Validation K-fold. Secara khusus, buat K lipatan dari observasi training. Ketika k = 1, …, K:

(a) Ulangi Langkah 1 dan 2 pada semua lipatan data pelatihan kecuali lipatan k.

(b) Hitung kesalahan prediksi kuadrat rata-rata sebagai fungsi dari menggunakan data dari lipatan k yang dikecualikan. Untuk mengurangi kesalahan rata-rata, tambahkan hasil untuk setiap nilai dan pilih. Subtree dari Langkah 2 yang sesuai dengan nilai terpilih dari dikembalikan.

Kompleksitas dan kesesuaian subtrees dengan data pelatihan disesuaikan berdasarkan parameter tuning α. Subtree T akan sama dengan T0 jika α = 0, karena akan hanya mengukur kesalahan traning. Namun, angka tersebut kemungkinan akan diminimalkan untuk subtree yang lebih kecil karena memiliki pohon dengan banyak node terminal datang dengan cost yang meningkat seiring dengan peningkatan α. Persamaan di atas serupa dengan lasso, yang menggunakan formulasi serupa untuk menggunakan kompleksitas model linear.

Cabang dihapus dari pohon secara bertingkat dan dapat diprediksi saat α meningkat dari nol, sehingga mudah untuk menghasilkan urutan lengkap subtrees sebagai fungsi dari α. Dengan menggunakan set validasi atau cross validation, kita dapat memilih nilai α. Subtree yang sesuai dengan α kemudian diperoleh dengan kembali ke set data lengkap.

e. Input

- X : Input training dataset

- y : Output training dataset

• Criteria

For Regression Cases

Untuk setiap dari N observasi, data kita terdiri dari p input dan sebuah respons, atau (xi, yi) untuk i = 1, 2,…, N, dengan xi = (xi1, xi2,…, xip). Dibutuhkan pengambilan keputusan otomatis untuk faktor-faktor pemisahan, titik pemisahan, dan topologi (bentuk) dari decision tree. Jika responsnya pertama kali dimodelkan sebagai konstan cm dalam setiap dari M region R1, R2,…, RM pada partisi:

Jika kita mengadopsi kriteria minimisasi jumlah kuadrat P(yi−2f(xi)), mudah untuk melihat bahwa ˆcm terbaik hanya merupakan rata-rata dari yi di region Rm:

Sekarang, umumnya tidak mungkin secara komputasi mengidentifikasi partisi biner optimal dengan jumlah kuadrat terkecil. Oleh karena itu, kita menggunakan algoritma greedy. Pertimbangkan variabel pemisah j dan titik pemisahan s yang dimulai dengan semua data, kemudian tentukan pasangan setengah bidang.

Variabel pemisahan j dan titik pemisahan s yang memecahkan masalah kemudian dicari.

Pemilihan j dan s di dalam minimisasi tersebut diselesaikan dengan menggunakan.

Setiap pohon yang dapat dibuat dengan memangkas T0, atau menggabungkan beberapa simpul internal (non-terminal) dari T0, disebut sebagai subtrees, atau T ⊂ T0. Menggunakan Node M untuk mengindeks simpul terminal, di mana Rm direpresentasikan oleh simpul m. T menjadi jumlah simpul terminal.

Definisikan cost complexity criterion

Tujuannya adalah mengidentifikasi subtrees T ⊆ T0 untuk setiap α dengan tujuan mengurangi C(T). Keseimbangan antara ukuran pohon dan kemampuannya untuk secara akurat cocok dengan data dikendalikan oleh parameter penyetelan α ≥ 0. Pohon T yang lebih kecil dihasilkan oleh nilai yang besar, dan sebaliknya untuk nilai yang besar. Pohon T0 lengkap adalah jawabannya ketika α = 0, seperti yang ditunjukkan oleh notasi tersebut. Di bawah ini, kita akan membahas cara membuat pilihan yang dapat disesuaikan. Dapat ditunjukkan bahwa untuk setiap α, ada subtree T terendah tertentu yang meminimalkan C(T). Untuk menentukan T, kita menggunakan metode pruning weakest link. Untuk melakukannya, pertama-tama kita menyatukan simpul internal yang menghasilkan peningkatan terkecil per simpul dalam Pm NmQm(T), kemudian kita melanjutkan hingga pohon dengan satu node (root) dihasilkan.

For Classification Cases

Qm(T), sebagai ukuran ketidakmurnian dalam regresi, tidak sesuai untuk klasifikasi. Kita anggap ada simpul m yang mewakili region Rm dengan Nm observasi.

Gini index:

Cross-entropy or deviance

Indeks Gini dan cross entropy dapat dihitung turunan sehingga lebih mudah untuk dioptimasi secara numerik, bahkan jika ketiga ukuran tersebut identik. Dengan membandingkannya, kita dapat melihat bahwa jumlah NmL dan NmR dari observasi dalam dua node child yang dihasilkan dari pemisahan node m harus digunakan untuk memperhitungkan pengukuran ketidakmurnian node. Selain itu, dibandingkan dengan tingkat kesalahan klasifikasi, cross-entropy dan skor Gini lebih sensitif terhadap perubahan dalam probabilitas node.

Node impurity dihitung untuk dua kelas klasifikasi, sebagai fungsi dari proporsi p pada kelas 2. Cross-entropy telah di skalakan menjadi (0.5,0.5)

f. Output

Set feature & threshold yang digunakan untuk splitting

g. Stopping criteria as hyperparameter

• max_depth : Membatasi jumlah splitting dan mengontrol kompleksitas dari pohon.
• sample_leaf_min : Menentukan jumlah minimum sampel (instansi) yang diperlukan dalam sebuah node leaf (simpul akhir) pada decision tree. Jika jumlah sampel dalam node leaf turun di bawah ambang batas ini, pemisahan lebih lanjut dihentikan, dan node tersebut menjadi node leaf.
• sample_split_min : Menentukan jumlah minimum sampel yang diperlukan untuk melakukan pemisahan pada suatu node. Jika jumlah sampel pada suatu node kurang dari ambang batas ini, proses pemisahan dihentikan, dan node tersebut menjadi node leaf.
• impurity_reduction_min : Mengatur threshold untuk jumlah minimum pengurangan impurity yang diperlukan untuk melakukan splitting. Pengurangan impurity mengukur seberapa banyak pemisahan suatu node meningkatkan purity atau homogenitas keseluruhan variabel target. Jika pengurangan impurity yang dicapai oleh pemisahan potensial berada di bawah threshold ini, splitting tidak dianggap, dan node tersebut menjadi node leaf.

F. Reference

[1] L. Breiman, J. Friedman, R. Olshen, and C. Stone, “Classification and Regression Trees”, Wadsworth, Belmont, CA, 1984

[2] T. Hastie, R. Tibshirani and J. Friedman. “Elements of Statistical Learning”, Springer, 2009.

[3] Gareth James, et. al. An Introduction to Statistical Learning

[5] Lecture Notes :

https://ocw.mit.edu/courses/15-097-prediction-machine-learning-and-statistics-spring-2012/f5678de0e329ce097fc6ec6182ebaea2_MIT15_097S12_lec08.pdf

https://cs229.stanford.edu/notes2021fall/lecture11-decision-trees.pdf