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