Decision Tree Algorithm

Materi: Algoritma Decision Tree

Pengertian Decision Tree
Algoritma Decision Tree merupakan salah satu metode supervised learning yang digunakan baik untuk classification maupun regression. Struktur Decision Tree menyerupai bentuk pohon, yang terdiri atas:

• Root Node — Node awal yang mewakili seluruh dataset.
• Internal Node — Node pengambilan keputusan berdasarkan atribut.
• Leaf Node — Node akhir yang memuat hasil prediksi kelas atau nilai.

Tujuan Decision Tree:
Membagi dataset menjadi subset yang semakin homogen (purity meningkat), dengan membangun aturan keputusan dari atribut fitur.

---

Konsep Pemilihan Atribut: Entropy & Information Gain

Entropy mengukur ketidakpastian dalam dataset. Rumus Entropy untuk variabel target dengan kelas $k$:

$$
Entropy(S) = -\sum_{i=1}^k p_i \log_2(p_i)
$$

dengan:

• $S$ = dataset
• $p_i$ = proporsi elemen di kelas ke-$i$

Information Gain (IG) mengukur seberapa besar pengurangan Entropy jika dataset dibagi berdasarkan atribut $A$:

$$
Gain(S, A) = Entropy(S) – \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)
$$

dengan:

• $S_v$ = subset data untuk nilai atribut $v$

Atribut terbaik adalah yang memiliki Information Gain tertinggi.

---

Contoh Sederhana

Misalkan dataset berikut:

Cuaca	Bermain
Cerah	Tidak
Cerah	Tidak
Berawan	Ya
Hujan	Ya
Hujan	Tidak

Target: Prediksi Bermain berdasarkan Cuaca.

Langkah 1: Hitung Entropy(S)

• Kelas “Ya”: 2
• Kelas “Tidak”: 3

$$
Entropy(S) = -\frac{2}{5}\log_2(\frac{2}{5}) – \frac{3}{5}\log_2(\frac{3}{5}) \approx 0.971
$$

Langkah 2: Hitung Information Gain atribut Cuaca
(Langkah perhitungannya dapat diperinci pada latihan.)

---

Latihan & Pembahasan

Latihan 1
Diberikan dataset:

Atribut A	Kelas
Tinggi	Ya
Tinggi	Ya
Rendah	Tidak
Rendah	Tidak
Tinggi	Tidak

1. Hitung Entropy dataset $S$
2. Hitung Information Gain untuk atribut A

---

Pembahasan

Jumlah total data: 5

• Kelas Ya = 2
• Kelas Tidak = 3

1. Entropy(S):

$$
Entropy(S) = -\frac{2}{5}\log_2(\frac{2}{5}) – \frac{3}{5}\log_2(\frac{3}{5}) \approx 0.971
$$

2. Gain(S, A)

• A = Tinggi → 3 data (2 Ya, 1 Tidak)
• A = Rendah → 2 data (0 Ya, 2 Tidak)

Entropy(Tinggi):

$$
Entropy = -\frac{2}{3}\log_2(\frac{2}{3}) – \frac{1}{3}\log_2(\frac{1}{3}) \approx 0.918
$$

Entropy(Rendah):

$$
Entropy = -\frac{0}{2}\log_2(0) – \frac{2}{2}\log_2(1) = 0
$$

Maka,

$$
Gain(S, A) = 0.971 – \Big( \frac{3}{5} * 0.918 + \frac{2}{5} * 0 \Big) \approx 0.971 – 0.550 = 0.421
$$

---

Penugasan

1. Carilah minimal 2 referensi ilmiah tentang Decision Tree.
2. Buatlah dataset minimal 6 baris dengan 2 atribut dan 1 target.
3. Hitung Entropy dan Information Gain untuk masing-masing atribut.
4. Buatlah Decision Tree sketsa (bisa gambar tangan atau software).
5. Implementasikan Decision Tree menggunakan Python (lihat kode).

---

Kode Python

# Decision Tree Classifier Example
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text

# Dataset
data = {
    'Cuaca': ['Cerah', 'Cerah', 'Berawan', 'Hujan', 'Hujan'],
    'Bermain': ['Tidak', 'Tidak', 'Ya', 'Ya', 'Tidak']
}

df = pd.DataFrame(data)

# Encode categorical data
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
df['Cuaca_enc'] = le.fit_transform(df['Cuaca'])
df['Bermain_enc'] = le.fit_transform(df['Bermain'])

# Features dan Target
X = df[['Cuaca_enc']]
y = df['Bermain_enc']

# Decision Tree
clf = DecisionTreeClassifier(criterion='entropy', random_state=0)
clf.fit(X, y)

# Visualisasi pohon
tree_rules = export_text(clf, feature_names=['Cuaca'])
print(tree_rules)

# Prediksi contoh baru
cuaca_baru = le.transform(['Berawan'])  # contoh input
prediksi = clf.predict([[cuaca_baru[0]]])
print('Prediksi:', le.inverse_transform(prediksi))

---

Referensi

• Quinlan, J. R. (1986). Induction of decision trees. Machine learning.
• Han, J., Kamber, M., & Pei, J. (2011). Data Mining: Concepts and Techniques.

---

#data science #ilmu data #machine learning #matematika #supervised learning