Seperti semua model supervised machine learning, pohon keputusan dilatih untuk menjelaskan satu set contoh pelatihan. Pelatihan yang optimal dari pohon keputusan adalah masalah NP-hard. Oleh karena itu, pelatihan umumnya dilakukan menggunakan heuristik — sebuah algoritma pembelajaran yang mudah dibuat yang memberikan hasil tidak optimal, tetapi mendekati pohon keputusan yang optimal.
Sebagian besar algoritma yang digunakan untuk melatih pohon keputusan bekerja dengan adanya kesenjangan dan strategi penaklukkan. Algoritma dimulai dengan membuat satu {i>node<i} ({i>root<i}) dan secara berulang dan serakah menumbuhkan pohon keputusan.
Pada setiap node, semua kondisi yang mungkin akan dievaluasi dan diberi skor. Tujuan algoritma memilih "terbaik" yaitu kondisi dengan nilai tertinggi, skor. Untuk saat ini, ketahuilah bahwa skor adalah metrik yang berkorelasi dengan tugas, dan kondisi dipilih untuk memaksimalkan metrik tersebut.
Misalnya, di Palmer Penguin {i>dataset<i} (digunakan untuk contoh kode nanti dalam materi ini), sebagian besar Adelie dan Chinstrap penguin memiliki panjang paruh lebih besar dari 16mm, sementara sebagian besar penguin memiliki paruh 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 menumbuhkan pohon.
Algoritma kemudian diulang secara rekursif dan independen pada kedua node turunan. Jika tidak ditemukan kondisi yang memuaskan, node akan menjadi sebuah daun. Daun prediksi ditentukan sebagai nilai label yang paling mewakili 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 bahas langkah-langkah pelatihan pohon keputusan tertentu dalam 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 sebuah daun:
Langkah 4: Kembangkan node #3. Kondisi "x2 ≥ 0,5" ditemukan. Dua anak node akan dibuat.
Ada metode lain untuk menumbuhkan pohon keputusan. Alternatif yang populer adalah mengoptimalkan node secara global alih-alih menggunakan strategi membagi dan menaklukkan.
growing_strategy="BEST_FIRST_GLOBAL".
Lihat
baca dokumentasi untuk
mengetahui detail lebih lanjut.
Tergantung pada jumlah dan jenis fitur input, jumlah kondisi yang mungkin untuk {i>node<i} tertentu bisa sangat besar, umumnya tak terbatas. Misalnya, dengan kondisi ambang batas $\mathrm{feature}_i \geq t$, kombinasi dari semua mungkin nilai minimum untuk $t \in \mathbb{R}$ tidak terbatas.
Rutinitas yang bertanggung jawab untuk menemukan kondisi terbaik disebut pemisah. Karena perlu menguji banyak kondisi yang mungkin, splitter adalah hambatan saat melatih pohon keputusan.
Skor yang dimaksimalkan oleh pemisah bergantung pada tugas. Contoh:
- Pengumpulan informasi dan Gini (keduanya akan dibahas nanti) biasanya digunakan untuk klasifikasi.
- Rata-rata kesalahan kuadrat biasanya digunakan untuk regresi.
Ada banyak algoritma pemisah, masing-masing dengan dukungan yang berbeda untuk:
- Jenis fitur; misalnya, numerik, kategorikal, teks
- Tugas: misalnya, klasifikasi biner, kelas klasifikasi, regresi
- Jenis kondisi; misalnya, kondisi ambang batas, kondisi dalam set, kondisi miring
- Kriteria regularisasi; misalnya, splitter yang tepat atau perkiraan untuk kondisi nilai minimum
Selain itu, ada varian pemisah yang setara dengan kompromi yang berbeda mengenai penggunaan memori, penggunaan CPU, distribusi komputasi, dan sebagainya.