Seperti semua model machine learning tersupervisi, pohon keputusan dilatih untuk menjelaskan kumpulan contoh pelatihan dengan sebaik mungkin. Pelatihan optimal pohon keputusan 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 berfungsi dengan strategi bagi dan kuasai yang rakus. Algoritma dimulai dengan membuat satu node (root) dan memperluas pohon keputusan secara rekursif dan serakah.
Di setiap node, semua kemungkinan kondisi dievaluasi dan diberi skor. Algoritma memilih kondisi "terbaik", yaitu kondisi dengan skor tertinggi. Untuk saat ini, cukup ketahui bahwa skor adalah metrik yang berkorelasi dengan tugas, dan kondisi dipilih untuk memaksimalkan metrik tersebut.
Misalnya, dalam set data Penguin Palmer (digunakan untuk contoh kode nanti dalam kursus ini), sebagian besar penguin Adelie dan Chinstrap memiliki panjang paruh lebih dari 16 mm, sedangkan sebagian besar penguin Gentoo 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. Algoritme mungkin akan memilih kondisi ini.
Gambar 7. Langkah pertama dalam menanam pohon.
Kemudian, algoritma akan diulang secara rekursif dan independen di kedua node turunan. Jika tidak ada kondisi yang memuaskan, node akan menjadi node 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 bahas 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, ubah node menjadi daun:
Langkah 4: Kembangkan node #3. Kondisi "x2 ≥ 0,5" ditemukan. Dua node turunan dibuat.
Ada metode lain untuk mengembangkan pohon keputusan. Alternatif yang populer adalah mengoptimalkan node secara global, bukan menggunakan strategi bagi dan taklukkan.
growing_strategy="BEST_FIRST_GLOBAL".
Lihat
dokumentasi untuk mengetahui detail selengkapnya.
Bergantung pada jumlah dan jenis fitur input, jumlah kemungkinan kondisi untuk node tertentu dapat sangat besar, umumnya tidak terbatas. Misalnya, dengan kondisi nilai minimum $\mathrm{feature}_i \geq t$, kombinasi semua nilai minimum yang mungkin 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:
- Keuntungan informasi dan Gini (keduanya akan dibahas nanti) biasanya digunakan untuk klasifikasi.
- Rataan kuadrat galat biasanya digunakan untuk regresi.
Ada banyak algoritma pemisah, masing-masing dengan dukungan yang bervariasi untuk:
- Jenis fitur; misalnya, numerik, kategoris, teks
- Tugas; misalnya, klasifikasi biner, klasifikasi multi-class, regresi
- Jenis kondisi; misalnya, kondisi nilai minimum, kondisi dalam set, kondisi miring
- Kriteria regularisasi; misalnya, pemisah yang tepat atau mendekati untuk kondisi nilai minimum
Selain itu, ada varian pemisah yang setara dengan kompromi yang berbeda terkait penggunaan memori, penggunaan CPU, distribusi komputasi, dan sebagainya.