2022-08-02

Algoritma Decision Tree

Pendahuluan

Decision Tree menggunakan berbagai algoritma untuk menentukan pembagian optimal sebuah node menjadi dua atau lebih sub-node. Pembentukan sub-node ini meningkatkan homogenitas mereka. Secara mendasar, ini berarti bahwa kemurnian node dalam hubungannya dengan variabel target meningkat. Decision Tree memeriksa semua variabel yang mungkin untuk dipisahkan dan memilih yang menghasilkan sub-node paling homogen.

Dalam artikel ini, saya akan memperkenalkan lima algoritma Decision Tree kunci: ID3, C4.5, CART, CHAID, dan MARS.

Algoritma ID3

Algoritma Iterative Dichotomiser 3 (ID3) adalah salah satu algoritma Decision Tree paling awal dan terkenal. Ini digunakan terutama untuk tugas klasifikasi dengan fitur kategorikal. Algoritma ID3 beroperasi dengan memilih atribut terbaik untuk membagi dataset berdasarkan kriteria Information Gain, yang mengukur pengurangan entropi yang dicapai dengan membagi data. Algoritma ini rekursif, terus membagi dataset hingga semua instansi termasuk dalam satu kelas atau kriteria berhenti terpenuhi. Information Gain (IG) dihitung sebagai berikut:

$IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$

di mana $S$ adalah dataset, $A$ adalah atribut, $S_v$ mewakili subset $S$ dengan nilai atribut $v$ , dan $H$ adalah fungsi entropi:

$H(S) = - \sum_{c \in Classes} p(c) \log_2 p(c)$

Algoritma C4.5

C4.5 adalah perluasan dari algoritma ID3. Ini mengatasi beberapa keterbatasan ID3, seperti ketidakmampuannya untuk menangani atribut kontinu dan data yang hilang. Algoritma C4.5 menggunakan kriteria Gain Ratio, modifikasi dari Information Gain, untuk memilih atribut terbaik untuk pemisahan. Gain Ratio (GR) didefinisikan sebagai:

$GR(S, A) = \frac{IG(S, A)}{IV(S, A)}$

di mana $IV(S, A)$ adalah Nilai Intrinsik atribut $A$ :

$IV(S, A) = - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}$

Algoritma CART

Classification and Regression Trees (CART) adalah algoritma Decision Tree lain yang populer yang dapat menangani tugas klasifikasi dan regresi. Berbeda dengan ID3 dan C4.5, CART menghasilkan pohon biner, dengan setiap node internal memiliki tepat dua node anak. Algoritma CART menggunakan kriteria Gini Impurity untuk tugas klasifikasi dan Mean Squared Error (MSE) untuk tugas regresi untuk memilih atribut terbaik untuk pemisahan. Gini Impurity (GI) dihitung sebagai berikut:

$GI(S) = 1 - \sum_{c \in Classes} p(c)^2$

Untuk tugas regresi, MSE didefinisikan sebagai:

$MSE(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2$

di mana $y_i$ adalah nilai target untuk instansi $i$ , dan $\bar{y}$ adalah nilai target rata-rata dari dataset.

Algoritma CHAID

Algoritma Chi-squared Automatic Interaction Detector (CHAID) adalah algoritma Decision Tree yang mengandalkan uji chi-squared untuk independensi untuk menentukan atribut terbaik untuk pemisahan. CHAID sangat berguna untuk mengeksplorasi interaksi antara variabel kategorikal dan dapat membuat pohon multiway, dengan setiap node internal memiliki lebih dari dua node anak. Algoritma ini juga mampu menangani data yang hilang melalui pemisahan pengganti, yang merupakan aturan pemisahan alternatif berdasarkan atribut yang tersisa.

Statistik Chi-squared dihitung sebagai:

$\chi^2 = \sum_{i=1}^n \sum_{j=1}^m \frac{(O_{ij} - E_{ij})^2}{E_{ij}}$

di mana $O_{ij}$ adalah frekuensi observasi dari instansi dalam kategori $i$ dari atribut dan kelas $j$ , $E_{ij}$ adalah frekuensi yang diharapkan di bawah asumsi independensi, $n$ adalah jumlah kategori untuk atribut, dan $m$ adalah jumlah kelas. Algoritma CHAID memilih atribut dengan nilai Chi-squared tertinggi untuk pemisahan, asalkan memenuhi tingkat signifikansi yang telah ditentukan sebelumnya.

Algoritma MARS

Multivariate Adaptive Regression Splines (MARS) adalah algoritma berbasis Decision Tree yang dikembangkan oleh Jerome H. Friedman. MARS terutama digunakan untuk tugas regresi dan dirancang untuk menangani data dengan dimensi tinggi dan bising. Algoritma ini membangun model dengan memasangkan fungsi regresi linier bertingkat yang disebut fungsi dasar ke data. MARS menggabungkan teknik seperti seleksi maju, eliminasi mundur, dan seleksi knot untuk membuat model yang mudah diinterpretasikan, fleksibel, dan akurat. Meskipun MARS bukan algoritma Decision Tree tradisional, tetapi memiliki beberapa kesamaan dalam struktur dan pendekatannya dalam memodelkan hubungan yang kompleks.

Model MARS dapat direpresentasikan sebagai:

$y(x) = \beta_0 + \sum_{i=1}^M \beta_i B_i(x)$

di mana $y(x)$ adalah nilai target yang diprediksi untuk masukan $x$ , $\beta_0$ adalah istilah konstan, $M$ adalah jumlah fungsi dasar $B_i(x)$ dalam model, dan $\beta_i$ adalah koefisien yang sesuai. Fungsi dasar adalah fungsi linear bertingkat dengan bentuk: