निगरानी में रखे गए मशीन लर्निंग मॉडल की तरह, डिसिज़न ट्री को ट्रेनिंग के उदाहरणों के सेट को बेहतर तरीके से समझाने के लिए ट्रेनिंग दी गई है. डिसिज़न ट्री का सबसे सही ट्रेनिंग एनपी-हार्ड सवाल है. इसलिए, ट्रेनिंग में आम तौर पर अनुभव से जुड़ी चीज़ों का इस्तेमाल किया जाता है. यह सीखने में आसान एल्गोरिदम है, जो न तो बहुत अच्छा देता है, लेकिन फ़ैसले ट्री के करीब होता है.
फ़ैसला लेने वाले पेड़ों को ट्रेनिंग देने में इस्तेमाल किए जाने वाले ज़्यादातर एल्गोरिदम, लालची विभाजन और जीतने की रणनीति के साथ काम करते हैं. एल्गोरिदम एक सिंगल नोड (रूट) बनाने से शुरू होता है और बार-बार और लालच से डिसिज़न ट्री को बढ़ाता है.
हर नोड पर, सभी संभावित शर्तों का आकलन और स्कोर किया जाता है. एल्गोरिदम "सबसे अच्छी" स्थिति को चुनता है, यानी कि सबसे ज़्यादा स्कोर वाली स्थिति. फ़िलहाल, यह जान लें कि स्कोर एक ऐसी मेट्रिक है जो टास्क के साथ जुड़ी है और उस मेट्रिक को बढ़ाने के लिए शर्तों को चुना जाता है.
उदाहरण के लिए, पामर पेंग्विन डेटासेट (इस कोर्स में आगे कोड के उदाहरण के लिए इस्तेमाल किया गया) में, ज़्यादातर अडेली और चिनस्ट्रैप पेंग्विन के बिल की लंबाई 16 मि॰मी॰ से ज़्यादा होती है, जबकि ज़्यादातर जेनटू पेंग्विन के बिल कम होते हैं. इसलिए, स्थिति bill_length_mm ≥ 16, जेंटू पेंग्विन के लिए करीब-करीब सटीक अनुमान लगाती है, लेकिन एडली और चिनस्ट्रैप के बीच अंतर नहीं कर सकती. एल्गोरिदम इस स्थिति को चुनेगा.
सातवीं इमेज. पेड़ उगाने का पहला कदम.
इसके बाद, एल्गोरिदम को दोनों चाइल्ड नोड पर बार-बार और स्वतंत्र रूप से दोहराया जाता है. कोई संतोषजनक शर्त नहीं मिलने पर नोड, लीफ़ बन जाता है. उदाहरणों में लीफ़ के अनुमान को लेबल की सबसे सही वैल्यू के तौर पर दिखाया गया है.
एल्गोरिदम इस तरह का होता है:
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)
आइए, किसी खास डिसिज़न ट्री को ट्रेनिंग देने के चरण के बारे में ज़्यादा विस्तार से जानते हैं.
पहला चरण: रूट बनाएं:
दूसरा चरण: नोड #1 बढ़ाएं. "x1 ≥ 1" स्थिति मिली थी. दो चाइल्ड नोड बनाए जाते हैं:
तीसरा चरण: नोड #2 बढ़ाएं. कोई संतोषजनक स्थिति नहीं मिली. इसलिए, नोड को एक लीफ़ में बनाएं:
चौथा चरण: नोड #3 बढ़ाएं. "x2 ≥ 0.5" स्थिति मिली है. इसके लिए, दो चाइल्ड नोड बनाए जाते हैं.
फ़ैसले लेने वाले पेड़ बढ़ाने के दूसरे तरीके भी मौजूद हैं. एक लोकप्रिय विकल्प है कि आप दोनो को बांटने और जीतने की रणनीति का इस्तेमाल करने के बजाय, दुनिया भर में नोड को ऑप्टिमाइज़ करें.
growing_strategy="BEST_FIRST_GLOBAL" पैरामीटर से ग्लोबल ग्रोथ को चालू किया जा सकता है.
ज़्यादा जानकारी के लिए,
दस्तावेज़ देखें.
इनपुट सुविधाओं की संख्या और प्रकार के आधार पर, किसी नोड के लिए हो सकने वाली शर्तों की संख्या बहुत ज़्यादा हो सकती है, आम तौर पर अनंत हो सकती है. उदाहरण के लिए, दी गई थ्रेशोल्ड शर्त $\mathrm{feature}_i \geq t$, $t \in \mathbb{R}$ के लिए सभी संभावित थ्रेशोल्ड वैल्यू का कॉम्बिनेशन अनंत है.
सबसे अच्छी स्थिति का पता लगाने वाले रूटीन को स्प्लिटर कहा जाता है. इसे कई संभावित स्थितियों की जांच करनी होती है. इसलिए, डिसिज़न ट्री को ट्रेनिंग देते समय स्प्लिटर समस्या का हिस्सा होते हैं.
स्प्लिटर से अधिकतम स्कोर टास्क पर निर्भर करता है. उदाहरण के लिए:
- आम तौर पर, जानकारी पाने का फ़ायदा और Gini (दोनों कवर किए गए) को कैटगरी में बांटने के लिए आम तौर पर इस्तेमाल किया जाता है.
- मीन स्क्वेयर एरर का इस्तेमाल, आम तौर पर रिग्रेशन के लिए किया जाता है.
ऐसे कई स्प्लिटर एल्गोरिदम हैं, जिनमें से हर एक के लिए अलग-अलग सहायता है:
- सुविधाएं किस तरह की हैं; उदाहरण के लिए, संख्या वाली, कैटगरी से जुड़ी जानकारी, टेक्स्ट
- टास्क; उदाहरण के लिए, बाइनरी क्लासिफ़िकेशन, कई कैटगरी में बांटा जाना, रिग्रेशन
- स्थिति का टाइप; उदाहरण के लिए, थ्रेशोल्ड की शर्त, इन-सेट स्थिति, तिरछी शर्त
- रेगुलराइज़ेशन की शर्तें. उदाहरण के लिए, थ्रेशोल्ड की शर्तों के लिए एग्ज़ैक्ट या अनुमानित स्प्लिटर
इसके अलावा, स्प्लिटर के एक जैसे वैरिएंट भी होते हैं, जिनमें मेमोरी के इस्तेमाल, सीपीयू के इस्तेमाल, कंप्यूटेशन डिस्ट्रिब्यूशन वगैरह के मामले में अलग-अलग फ़ायदे होते हैं.