مانند همه مدل‌های یادگیری ماشینی تحت نظارت، درخت‌های تصمیم برای توضیح بهتر مجموعه‌ای از نمونه‌های آموزشی آموزش داده می‌شوند. آموزش بهینه درخت تصمیم یک مسئله NP-hard است. بنابراین، آموزش به طور کلی با استفاده از اکتشافی انجام می شود - یک الگوریتم یادگیری آسان برای ایجاد یک درخت تصمیم غیر بهینه، اما نزدیک به بهینه.
بیشتر الگوریتم‌هایی که برای آموزش درخت‌های تصمیم استفاده می‌شوند، با استراتژی حریصانه تقسیم و غلبه کار می‌کنند. الگوریتم با ایجاد یک گره واحد (ریشه) شروع می شود و درخت تصمیم را به صورت بازگشتی و حریصانه رشد می دهد.
در هر گره، تمام شرایط ممکن ارزیابی و امتیازدهی می شود. الگوریتم شرایط "بهترین" را انتخاب می کند، یعنی شرطی که بالاترین امتیاز را داشته باشد. در حال حاضر، فقط بدانید که امتیاز یک متریک است که با کار مرتبط است و شرایط برای به حداکثر رساندن آن معیار انتخاب شده است.
به عنوان مثال، در مجموعه داده Palmer Penguins (برای مثال‌های کد بعدی در این دوره استفاده می‌شود)، بیشتر پنگوئن‌های Adelie و Chinstrap دارای طول اسکناس بیشتر از 16 میلی‌متر هستند، در حالی که بیشتر پنگوئن‌های جنتو اسکناس‌های کوچک‌تری دارند. بنابراین، شرط bill_length_mm ≥ 16 پیش‌بینی‌های تقریباً کاملی را برای پنگوئن‌های جنتو انجام می‌دهد، اما نمی‌تواند بین Adelies و Chinstraps تفاوت قائل شود. الگوریتم احتمالاً این شرط را انتخاب خواهد کرد.
شکل 7. اولین مرحله در رشد یک درخت.
سپس الگوریتم به صورت بازگشتی و مستقل در هر دو گره فرزند تکرار می شود. هنگامی که هیچ شرایط رضایت بخشی یافت نمی شود، گره تبدیل به یک برگ می شود. پیش بینی برگ به عنوان نماینده ترین مقدار برچسب در مثال ها تعیین می شود.
الگوریتم به شرح زیر است:
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: ایجاد یک ریشه:
مرحله 2: گره شماره 1 را رشد دهید. شرط "x1 ≥ 1" پیدا شد. دو گره فرزند ایجاد می شود:
مرحله 3: گره شماره 2 را رشد دهید. هیچ شرایط رضایت بخشی پیدا نشد. بنابراین، گره را به یک برگ تبدیل کنید:
مرحله 4: گره شماره 3 را رشد دهید. شرایط "x2 ≥ 0.5" پیدا شد. دو گره فرزند ایجاد می شود.
روش های دیگری برای رشد درختان تصمیم وجود دارد. یک جایگزین محبوب، بهینه سازی گره ها در سطح جهانی به جای استفاده از استراتژی تفرقه و غلبه است.
growing_strategy="BEST_FIRST_GLOBAL" فعال کنید. برای جزئیات بیشتر به مستندات مراجعه کنید.بسته به تعداد و نوع ویژگی های ورودی، تعداد شرایط ممکن برای یک گره معین می تواند بسیار زیاد و به طور کلی بی نهایت باشد. برای مثال، با توجه به شرایط آستانه $\mathrm{feature}_i \geq t$، ترکیب همه مقادیر آستانه ممکن برای $t \in \mathbb{R}$ بی نهایت است.
روتینی که مسئول یافتن بهترین شرایط است اسپلیتر نامیده می شود. از آنجایی که نیاز به آزمایش بسیاری از شرایط ممکن دارد، اسپلیترها در هنگام آموزش درخت تصمیم‌گیری گلوگاه هستند.
امتیاز حداکثر شده توسط اسپلیتر به کار بستگی دارد. مثلا:
- کسب اطلاعات و جینی (هر دو بعداً پوشش داده می شوند) معمولاً برای طبقه بندی استفاده می شوند.
- میانگین مربعات خطا معمولاً برای رگرسیون استفاده می شود.
الگوریتم های تقسیم کننده زیادی وجود دارد که هر کدام از آنها پشتیبانی متفاوتی دارند:
- نوع ویژگی ها؛ به عنوان مثال، عددی، مقوله ای، متنی
- وظیفه؛ به عنوان مثال، طبقه بندی باینری، طبقه بندی چند طبقه، رگرسیون
- نوع شرایط؛ به عنوان مثال، شرط آستانه، شرط در مجموعه، شرط مورب
- معیارهای منظم سازی؛ به عنوان مثال، تقسیم کننده های دقیق یا تقریبی برای شرایط آستانه
علاوه بر این، انواع تقسیم کننده معادل با مبادلات مختلف در مورد استفاده از حافظه، استفاده از CPU، توزیع محاسباتی و غیره وجود دارد.