עץ החלטה

עץ החלטה (באנגלית: Decision Tree) הוא מודל חיזוי בתחומי הסטטיסטיקה, כריית נתונים והלמידה החישובית המספק מיפוי בין תצפיות לערכים המתאימים עבורן. עץ החלטה יכול לשמש כמודל חיזוי, הממפה תצפיות על פריט ויוצר מסקנות על ערך היעד של הפריט. שמות תיאוריים יותר עבור עץ ההחלטות הם עצי סיווג או עצי רגרסיה. במבנה של עצים אלה, עלים מייצגים סיווגים אפשריים וענפים מייצגים צירופים של תכונות אשר יובילו למחלקות הסיווג.
בניתוח החלטה, עץ ההחלטה יכול לשמש לצורך הדמיה ויזואלית ובנוסף, לקבל את ההחלטות. בכריית נתונים, עץ החלטה מתאר את הנתונים, אך לא את ההחלטות. לעומת זאת, עץ לקבלת החלטות יכול לקבל משתנה כניסה מסוים ולייצר החלטה בהתאם לנתונים. דף זה עוסק בעצי החלטה בכריית נתונים.
עצי החלטה מופעלים על תצפיות מהצורה  כך ש  הם מאפייני התצפית ו Y הוא הערך המתאים עבור תצפית זו (ערך המטרה שאותו האלגוריתם לומד).

תיאור המודל

עץ החלטה הוא עץ בינארי מלא המורכב מצמתי החלטה שבכל אחד מהם נבדק תנאי מסוים על מאפיין מסוים של התצפיות ועלים המכילים את הערך החזוי עבור התצפית המתאימה למסלול שמוביל אליהם בעץ. סוגים של עצי החלטה הם עצי ריגרסיה שבהם מותאם ערך רציף לכל תצפית ועצי סיווג שבהם מותאם ערך בדיד או מחלקת סוג לכל תצפית. כמו כן קיימים עצי החלטה מסוג (CART (Classification And Regression Tree המשלבים את שני סוגי החיזוי.
עץ החלטה הוא ייצוג פשוט לסיווג דוגמאות. למידה מבוססת עץ החלטה היא אחת הטכניקות המוצלחות ביותר ללמידה מפוקחת באמצעות סיווג. עץ יכול "ללמוד" על ידי פיצול קבוצת המקור לתתי קבוצות, המתבססות על מתן ערך לתכונה. תהליך זה חוזר על עצמו בכל תת-קבוצה באופן רקורסיבי, ונקרא מחיצות רקורסיביות. הרקורסיה מושלמת כאשר כל קבוצות המשנה בצומת בעלות אותו ערך מטרה, או כאשר הפיצול כבר אינו מוסיף ערך לתחזיות. תהליך זה של אינדוקציה מלמעלה למטה בעצי החלטה, הוא דוגמה לאלגוריתם נפוץ במיוחד לעצים אשר לומדים החלטה מהנתונים.
בכריית נתונים, ניתן לתאר עצי החלטה גם כשילוב של טכניקות מתמטיות וחישוביות, המסייעות בתיאור, סיווג והכללה של קבוצה נתונה של נתונים.

מדדים

אלגוריתמים לבניית עצי החלטה בדרך כלל עובדים מלמעלה למטה, על ידי בחירה משתנה בכל שלב שמחלק את קבוצת הפריטים בצורה הטובה ביותר. אלגוריתמים שונים משתמשים במדדים שונים על מנת למדוד בצורה הטובה ביותר. אלה מודדים בדרך כלל את ההומוגניות של משתנה היעד בתוך תת-קבוצות. מדדים אלה יחולו על כל קבוצת משנה מועמדת, והערכים שהתקבלו משולבים (למשל, בממוצע) כדי לספק מדד לאיכות של הפיצול.

מדד GINI

בעץ CART (עץ סיווג ורגרסיה) משתמשים במדד GINI. מדד זה מודד כמה פעמים אלמנט שנבחר באופן אקראי מהסט יתויג בצורה שגויה אם הוא תויג באופן אקראי בהתאם לחלוקת התוויות בקבוצות המשנה. מדד GINI ניתן לחישוב על ידי סכימה של ההסתברות של כל פריט להיבחר כפול בהסתברות של סיווג שגוי של פריט זה. הוא מגיע למינימום (אפס) כאשר כל המקרים שייכים לקטגוריית מטרה אחת. 
על מנת לחשב GINI עבור קבוצת פריטים, נניח שניקח את הערכים: {1,2,…m} ו-Fi יהיה חלק מהערכים המתויגים עם משתנה i בקבוצת הפריטים.

רווח מידע

באלגוריתמים של עצי החלטה מהסוגים: ID3, C4.5 ,C5.0 משתמשים במדד זה. רווח מידע מבוסס על מושג האנטרופיה מתיאורית המידע.

גרף החלטה

בעצי החלטה, כל הנתיבים מצומת השורש לצומת העלה ממשיכים בדרך של השתלבות, או AND. בגרף החלטה ניתן להשתמש בהתפצלות (ORs) כדי לצרף שני נתיבים נוספים יחד באמצעות אורך מסר מינימלי.
גרפי החלטה הורחבו יותר כדי לאפשר לתכונות חדשות שלא נאמרו קודם להילמד ולשמש באופן דינמי במקומות שונים בגרף. הקידוד הסכמתי הכללי מניב חיזוי מדויק וטוב יותר. באופן כללי, גרפי החלטה מסיקים מודלים עם פחות עלים מאשר עצי החלטה.

שיטות חיפוש חלופיות

אלגוריתמים אבולוציוניים משמשים כדי למנוע החלטות אופטימום מקומיות ולחפש את מרחב העץ עם מעט הטיה מראש.
אפשרי גם, שעץ ידגם על ידי MCMC בתבנית בייס (Bayesian). 
ניתן לחפש בעץ בשיטת מלמטה למעלה.

גיזום

כדי להתמודד עם בעיית תאימות יתר (overfitting) שבו העץ מספק תחזיות מדויקות עבור התצפיות שלפיהן נבנה, אך בעל שיעור שגיאה גבוה עבור תצפיות אחרות מבוצע תהליך גיזום (pruning) שבו מוחלפים חלק מהצמתים בעץ בעלים עם סיווג שנקבע על פי הסיווג של רוב הדוגמאות ששייכות לתת העץ שתחת אותו הצומת.