Tüm gözetimli makine öğrenimi modelleri gibi karar ağaçları da bir dizi eğitim örneğini en iyi şekilde açıklayacak şekilde eğitilir. Karar ağacı için optimum eğitim NP zor problemdir. Bu nedenle, eğitim genellikle buluşsal yöntemler kullanılarak gerçekleştirilir. Bu, optimum olmayan ancak ideale yakın bir karar ağacı veren, oluşturulması kolay bir öğrenim algoritmasıdır.
Karar ağaçlarını eğitmek için kullanılan çoğu algoritma, açgözlü bir bölme ve fethetme stratejisiyle çalışır. Algoritma, ilk olarak tek bir düğüm (kök) oluşturur. Ardından, karar ağacını yinelemeli bir şekilde büyütür.
Her düğümde, mümkün olan tüm koşullar değerlendirilir ve puanlanır. Algoritma "en iyi" koşulu, yani en yüksek puana sahip koşulu seçer. Şimdilik puanın görevle ilişkili olan bir metrik olduğunu ve bu metriği en üst düzeye çıkarmak için koşulların seçildiğini bilmeniz yeterlidir.
Örneğin, Palmer Penguenler veri kümesinde (bu kursun sonraki kod örnekleri için kullanılır) çoğu Adelie ve Chinstrap pengueninin fatura uzunluğu 16 mm'den büyükken Gentoo penguenlerinin çoğunun daha küçük faturaları vardır. Bu nedenle, bill_length_mm ≥ 16 koşulu Gentoo penguenleri için neredeyse mükemmel tahminlerde bulunsa da Adelies ile Chinstraps'ı birbirinden ayırt edemez. Algoritma muhtemelen bu koşulu seçer.
Şekil 7. Ağaç büyütmenin ilk adımı.
Daha sonra algoritma, her iki alt düğümde de yinelemeli ve bağımsız olarak tekrar eder. Uygun koşullar bulunamadığında, düğüm bir yaprak haline gelir. Yaprak tahmini, örneklerdeki en temsili etiket değeri olarak belirlenmiştir.
Algoritma şu şekildedir:
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)
Belirli bir karar ağacını eğitme adımlarını daha ayrıntılı bir şekilde ele alalım.
1. Adım: Bir kök oluşturun:
2. Adım: 1. düğümü büyütün. "x1 ≥ 1" koşulu bulundu. İki alt düğüm oluşturulur:
3. Adım: 2. düğümü büyütün. Uygun koşul bulunamadı. Düğümü bir yaprak haline getirin:
4. Adım: 3. düğümü büyütün. "x2 ≥ 0,5" koşulu bulundu. İki alt düğüm oluşturulur.
Karar ağaçları yetiştirmek için başka yöntemler de vardır. Popüler bir alternatif de böl ve fethet stratejisi kullanmak yerine düğümleri küresel olarak optimize etmektir.
growing_strategy="BEST_FIRST_GLOBAL" parametresiyle küresel büyümeyi etkinleştirebilirsiniz.
Daha fazla bilgi için
belgeleri inceleyin.
Giriş özelliklerinin sayısına ve türüne bağlı olarak, belirli bir düğüm için olası koşul sayısı çok büyük, genellikle sonsuz olabilir. Örneğin, $\mathrm{feature}_i \geq t$ eşik koşulu verildiğinde $t \in \mathbb{R}$ için olası tüm eşik değerlerinin kombinasyonu sonsuzdur.
En iyi durumu bulmaktan sorumlu rutine ayırıcı adı verilir. Çok sayıda olası koşulu test etmesi gerektiğinden, ayırıcılar karar ağacını eğitmek için dar boğazdır.
Bölücü tarafından en üst düzeye çıkarılacak puan, göreve bağlıdır. Örneğin:
- Bilgi edinme ve Gini (her ikisi de ileride ele alınır) sınıflandırma için yaygın olarak kullanılır.
- Regresyonda ortalama karesel hata yaygın olarak kullanılır.
Her biri farklı şekilde desteklenen çok sayıda ayırıcı algoritma vardır:
- Özelliklerin türü; örneğin, sayısal, kategorik, metin
- Görev; örneğin ikili sınıflandırma, çok sınıflı sınıflandırma, regresyon
- Koşulun türü; örneğin, eşik koşulu, ayarlı koşul, eğik koşul
- Normalleştirme kriterleri; örneğin, eşik koşulları için tam veya yaklaşık ayırıcılar
Ayrıca bellek kullanımı, CPU kullanımı, hesaplama dağıtımı vb. konularda farklı dengeleri olan eşdeğer ayırıcı varyantları da vardır.