כמו כל המודלים של למידת מכונה בפיקוח, עצי ההחלטות מאומנים כדי להסביר בצורה הטובה ביותר קבוצת דוגמאות אימון. האימון האופטימלי של עץ החלטות הוא בעיה חמורה NP. לכן, בדרך כלל האימון מתבצע באמצעות היוריסטיקה – אלגוריתם למידה שקל ליצור, שמספק עץ החלטות לא אופטימלי, אבל כמעט אופטימלי.
רוב האלגוריתמים שמשמשים לאימון עצי החלטות פועלים בשיטה של חילוק וכובש באלגוריתם חמדן (חמדן). האלגוריתם מתחיל ביצירת צומת יחיד (השורש) ומגדיל את עץ ההחלטות באופן רקורסיבי.
בכל צומת, כל התנאים האפשריים נבדקים ומקבלים ציון. האלגוריתם בוחר את התנאי 'הטוב ביותר', כלומר התנאי עם הציון הגבוה ביותר. כרגע, דעו שהציון הוא מדד שתואם למשימה, והתנאים נבחרים כדי למקסם את המדד הזה.
לדוגמה, במערך הנתונים של פינגווינים פאלמר (שמשמשים לדוגמאות לקודים בהמשך הקורס), לרוב הפינגווינים אדלי וצ'ינסטראפ יש אורך חשבון של יותר מ-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: יצירת מקור נתונים (root):
שלב 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}$ הוא אינסופי.
התרחיש שאחראי למציאת המצב הטוב ביותר נקרא מפצל. מכיוון שצריך לבדוק הרבה תנאים אפשריים, המפצלים הם צוואר הבקבוק בזמן אימון עץ החלטות.
התוצאה שהמפצל מקצה תלוי במשימה. לדוגמה:
- בדרך כלל משמשים לסיווג מידע ו-Gini (שניהם מכוסים מאוחר יותר).
- 'השגיאה הממוצעת בריבוע' משמשת בדרך כלל לרגרסיה.
יש הרבה אלגוריתמים של מפצלים, כל אחד עם תמיכה משתנה:
- סוג התכונות. לדוגמה: מספריים, קטגוריות, טקסט
- המשימה, למשל סיווג בינארי, סיווג מרובה מחלקות, רגרסיה
- סוג התנאי. לדוגמה, תנאי סף, תנאי מוגדר, תנאי עקום
- הקריטריונים של הרגולטור. לדוגמה, מפצלים מדויקים או משוערים של תנאי הסף
בנוסף, יש וריאנטים מקבילים של מפצלים עם פשרות שונות לגבי שימוש בזיכרון, שימוש במעבד (CPU), התפלגות החישובים וכן הלאה.