ברוכים הבאים ליחידת הלימוד בנושא "סיווג: עצי החלטה" במסגרת הקורס "כריית מידע" (20595). יחידה זו תעסוק באחד המודלים הפופולריים והאינטואיטיביים ביותר ללמידה חיזויית קטגוריאלית – עצי החלטה. נלמד כיצד עצי החלטה פועלים, מהם העקרונות לבנייתם, וכיצד להתמודד עם האתגרים הנפוצים הכרוכים בשימוש בהם. הבנה מעמיקה של עצי החלטה, ובפרט של נושא הגיזום והתאמת יתר, היא קריטית להצלחה בבחינה.
עצי החלטה: עקרונות יסוד
עץ החלטה הוא מודל לחיזוי המייצג סדרת החלטות בצורת עץ. הוא משמש בעיקר למשימות סיווג (Classification), בהן המטרה היא לחזות משתנה יעד קטגוריאלי (לדוגמה: האם לקוח ירכוש מוצר? האם מייל הוא ספאם?).
מבנה העץ
- צומת שורש (Root Node): הצומת העליון בעץ, המייצג את התכונה הראשונה לפיה מתבצעת ההחלטה.
- צומתי פנימיים (Internal Nodes): צמתים המייצגים בדיקה של תכונה מסוימת. מכל צומת כזה יוצאים ענפים (Edges) המייצגים את התוצאות האפשריות של הבדיקה.
- ענפים (Edges): מייצגים את הערכים האפשריים של התכונה הנבדקת בצומת.
- עלי העץ (Leaf Nodes): צמתים סופיים המייצגים את התוצאה הסופית של הסיווג (הקטגוריה החזויה).
תהליך הסיווג מתבצע על ידי מעבר מהשורש כלפי מטה, תוך בדיקת ערכי התכונות והתקדמות בענפים המתאימים, עד הגעה לעלה המכיל את החיזוי. יתרונם הבולט של עצי החלטה הוא יכולת הפרשנות הגבוהה שלהם: ניתן להבין בקלות את הכללים שהעץ למד.
בניית עץ החלטה: אלגוריתמים ומדדים
בניית עץ החלטה היא תהליך רקורסיבי של "חלק וכיבוש" (Divide and Conquer). המטרה היא למצוא את התכונה הטובה ביותר לפצל לפיה את הנתונים בכל צומת, כך שהצמתים שנוצרים יהיו "טהורים" ככל האפשר – כלומר, יכילו מקרים השייכים ברובם המכריע לאותה קטגוריה.
מדדי אי-טוהר (Impurity Measures)
כדי לבחור את התכונה הטובה ביותר לפיצול, אנו משתמשים במדדי אי-טוהר. תכונה טובה היא כזו שמפחיתה את האי-טוהר בצורה המקסימלית לאחר הפיצול.
מדד ג'יני (Gini Index)
מדד הסתברותי המודד את הסיכוי שפריט שנבחר באקראי ממערך נתונים יהיה מסווג באופן שגוי אם קטגוריית היעד שלו תיבחר באקראי על בסיס התפלגות הקטגוריות במערך. ערך נמוך יותר מצביע על טוהר גבוה יותר (פחות אי-ודאות).
נוסחה: \(Gini = 1 - \sum_{i=1}^{C} (p_i)^2\)
אנטרופיה (Entropy) ורווח אינפורמציה (Information Gain)
אנטרופיה מודדת את אי-הוודאות או אי-הסדר במערך נתונים. רווח אינפורמציה הוא ההפחתה באנטרופיה לאחר פיצול הנתונים לפי תכונה מסוימת. אנו בוחרים את התכונה שמספקת את רווח האינפורמציה הגבוה ביותר.
נוסחה לאנטרופיה: \(Entropy = - \sum_{i=1}^{C} p_i \log_2(p_i)\)
תנאי עצירה
בניית העץ נמשכת עד שמתקיים אחד מתנאי העצירה הבאים:
- כל המקרים בצומת שייכים לאותה קטגוריה (צומת "טהור").
- אין יותר תכונות זמינות לפיצול.
- מספר המקרים בצומת קטן מסף מינימלי שהוגדר מראש.
- עומק העץ הגיע למקסימום שהוגדר.
טיפול בתכונות רציפות
עבור תכונות רציפות, יש לבצע דיסקרטיזציה (Discretization) על ידי מציאת נקודות חיתוך אופטימליות. לדוגמה, עבור תכונה "גיל", האלגוריתם יחפש את נקודת הפיצול הטובה ביותר, למשל "גיל <= 30" ו"גיל > 30", על בסיס מדדי אי-הטוהר.
אתגרים ופתרונות בעצי החלטה
למרות יתרונותיהם, עצי החלטה מתמודדים עם מספר אתגרים מרכזיים, שהחשוב שבהם הוא התאמת יתר.
גיזום (Pruning)
גיזום הוא תהליך של הסרת ענפים או צמתים מהעץ כדי להפחית את מורכבותו ולשפר את יכולת ההכללה שלו.
גיזום מוקדם (Pre-pruning)
עצירת בניית העץ מוקדם, לפני שהוא מגיע למורכבות יתר. דוגמאות: הגבלת עומק העץ המקסימלי, הגבלת מספר המקרים המינימלי בעלה, או עצירה כאשר רווח האינפורמציה אינו עולה על סף מסוים. גישה זו עלולה להוביל ל"גיזום יתר" (underfitting) אם העץ נעצר מוקדם מדי.
גיזום מאוחר (Post-pruning)
בניית עץ מלא ולאחר מכן הסרת ענפים או צמתים מהשורש כלפי מעלה (או מלמטה למעלה) על ידי החלפתם בעלים. ההחלטה אם לגזום מבוססת לרוב על ביצועי העץ על קבוצת ולידציה נפרדת. גישה זו נחשבת לרוב ליעילה יותר אך דורשת יותר משאבי חישוב.
חסרונות נוספים
- חוסר יציבות (Instability): שינויים קטנים בנתוני האימון יכולים להוביל לעצים שונים מאוד.
- הטיה לתכונות עם ערכים רבים: מדדי אי-טוהר מסוימים (כמו רווח אינפורמציה) נוטים להעדיף תכונות עם מספר רב של ערכים ייחודיים, גם אם אינן אינפורמטיביות באמת. אלגוריתמים כמו C4.5 מתמודדים עם זה באמצעות מדד ה-Gain Ratio.
פתרונות לאתגרים אלו כוללים שימוש באלגוריתמים מתקדמים יותר ובמודלים מבוססי אנסמבל (Ensemble Methods) כגון יערות אקראיים (Random Forests), המשלבים מספר רב של עצי החלטה כדי לשפר את היציבות והדיוק.
שאלות לדיון
- הסבירו את ההבדל בין מדד ג'יני לרווח אינפורמציה בבחירת תכונה לפיצול בעץ החלטה. מתי תעדיפו להשתמש בכל אחד מהם?
- תארו את תופעת ההתאמת יתר (Overfitting) בעצי החלטה והסבירו כיצד גיזום מוקדם (Pre-pruning) וגיזום מאוחר (Post-pruning) מסייעים להתמודד איתה. תנו דוגמה לכל שיטת גיזום.
- נתונה קבוצת נתונים קטנה עם תכונה רציפה "שכר" ותכונה קטגוריאלית "השכלה". הסבירו כיצד תטפלו בכל אחת מהתכונות הללו בעת בניית עץ החלטה.
- מהם היתרונות והחסרונות המרכזיים של עצי החלטה בהשוואה למודלי סיווג אחרים שלמדתם (לדוגמה, למידה בייסיאנית)?
נקודות לתשובת מודל
- הבדל בין מדדי אי-טוהר: הגדרת ג'יני ואנטרופיה, הסבר על רווח אינפורמציה כהפחתה באנטרופיה. הדגשת המטרה המשותפת – מציאת הפיצול שמפחית את אי-הטוהר בצורה המקסימלית. ציון רגישות של אנטרופיה (ולכן רווח אינפורמציה) לתכונות עם ערכים רבים, וכיצד Gain Ratio מתקן זאת.
- התאמת יתר וגיזום: הגדרת התאמת יתר (ביצועים טובים באימון, גרועים בבחינה עקב שינון רעשים). הסבר מפורט על Pre-pruning (עצירה מוקדמת, דוגמאות: עומק מקסימלי, מינימום דוגמאות בעלה, סף רווח אינפורמציה). הסבר מפורט על Post-pruning (בניית עץ מלא, הסרת ענפים, שימוש בקבוצת ולידציה להערכת ביצועים). השוואה בין הגישות מבחינת יעילות ועלות חישובית.
- טיפול בתכונות: תכונה רציפה – דיסקרטיזציה (מציאת נקודות חיתוך אופטימליות על ידי מיון הערכים ובחינת כל נקודת אמצע כפיצול פוטנציאלי). תכונה קטגוריאלית – פיצול לפי כל ערך (אם מעט ערכים) או קיבוץ ערכים (אם הרבה ערכים).
- יתרונות וחסרונות: יתרונות (פרשנות קלה, לא דורש סקאלינג/נורמליזציה, מטפל בנתונים מעורבים – קטגוריאליים ורציפים). חסרונות (התאמת יתר, חוסר יציבות, הטיה לתכונות עם ערכים רבים, בניית עץ אופטימלי היא בעיה NP-קשה ולכן משתמשים בהיוריסטיקות). השוואה קצרה למודל בייסיאני (לדוגמה, בייסיאני מניח אי-תלות מותנית, עץ אינו מניח זאת מראש).