Seperti semua model supervised machine learning, pohon keputusan dilatih untuk menjelaskan dengan sebaik-baiknya serangkaian contoh pelatihan. Pelatihan pohon keputusan yang optimal adalah masalah NP-hard. Oleh karena itu, pelatihan umumnya dilakukan menggunakan heuristik, algoritma pembelajaran yang mudah dibuat yang memberikan pohon keputusan yang tidak optimal tetapi mendekati optimal.
Sebagian besar algoritma yang digunakan untuk melatih pohon keputusan bekerja dengan strategi greedy membagi dan menaklukkan. Algoritma dimulai dengan membuat node tunggal (root) dan secara rekursif serta menumbuhkan pohon keputusan.
Pada setiap {i>node<i}, semua kondisi yang mungkin dievaluasi dan dinilai. Algoritma memilih kondisi "terbaik", yaitu kondisi dengan skor tertinggi. Untuk saat ini, perlu diketahui bahwa skor adalah metrik yang berhubungan dengan tugas, dan kondisi dipilih untuk memaksimalkan metrik tersebut.
Misalnya, dalam {i>dataset<i} Palmer Penguins (digunakan untuk contoh kode nanti dalam materi ini), kebanyakan penguin Adelie dan Chinstrap memiliki panjang paruh lebih besar dari 16mm, sementara sebagian besar penguin Gentoo memiliki tagihan yang lebih kecil. Oleh karena itu, kondisi bill_length_mm ≥ 16 membuat prediksi yang hampir sempurna untuk penguin Gentoo, tetapi tidak dapat membedakan antara Adelies dan Chinstraps. Algoritma mungkin akan memilih kondisi ini.
Gambar 7. Langkah pertama dalam menanam pohon.
Algoritma kemudian diulang secara rekursif dan independen pada kedua node turunan. Jika tidak ditemukan kondisi yang memuaskan, node akan menjadi daun. Prediksi daun ditentukan sebagai nilai label yang paling representatif dalam contoh.
Algoritmanya adalah sebagai berikut:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Mari kita pelajari langkah-langkah pelatihan pohon keputusan tertentu secara lebih mendetail.
Langkah 1: Buat root:
Langkah 2: Kembangkan node #1. Kondisi "x1 ≥ 1" ditemukan. Dua node turunan dibuat:
Langkah 3: Kembangkan node #2. Tidak ditemukan kondisi yang memuaskan. Jadi, buat node menjadi leaf:
Langkah 4: Kembangkan node #3. Kondisi "x2 ≥ 0.5" ditemukan. Dua node turunan dibuat.
Ada metode lain untuk menumbuhkan pohon keputusan. Alternatif yang populer adalah dengan mengoptimalkan node secara global, bukan menggunakan strategi membagi dan menaklukkan.
growing_strategy="BEST_FIRST_GLOBAL".
Lihat
dokumentasi untuk mengetahui detail selengkapnya.
Bergantung pada jumlah dan jenis fitur input, jumlah kemungkinan kondisi untuk node tertentu bisa sangat besar, umumnya tak terbatas. Misalnya, dengan kondisi ambang batas $\mathrm{feature}_i \geq t$, kombinasi dari semua nilai ambang batas yang memungkinkan untuk $t \in \mathbb{R}$ tidak terbatas.
Rutinitas yang bertanggung jawab untuk menemukan kondisi terbaik disebut pemisah. Karena perlu menguji banyak kemungkinan kondisi, pemisah adalah bottleneck saat melatih pohon keputusan.
Skor yang dimaksimalkan oleh pemisah bergantung pada tugas. Contoh:
- Perolehan informasi dan Gini (keduanya dibahas nanti) biasanya digunakan untuk klasifikasi.
- Rata-rata kesalahan kuadrat biasanya digunakan untuk regresi.
Ada banyak algoritma pemisah, masing-masing dengan dukungan yang beragam untuk:
- Jenis fitur; misalnya, numerik, kategoris, teks
- Tugas; misalnya, klasifikasi biner, klasifikasi multikelas, regresi
- Jenis kondisi; misalnya, kondisi ambang batas, kondisi dalam setelan, kondisi miring
- Kriteria regularisasi; misalnya, pemisah tepat atau perkiraan untuk kondisi ambang batas
Selain itu, ada varian pemisah yang setara dengan kompromi yang berbeda terkait penggunaan memori, penggunaan CPU, distribusi komputasi, dan sebagainya.