עץ החלטה

עץ החלטה המציג את שיעורי ההישרדות מבין נוסעי הספינה טיטאניק. sibsp הוא מספר קרובי המשפחה על סיפון האוניה. הסיווג בכל עלה מייצג את מרבית הדוגמאות המשויכות לעלה זה. המספרים המופיעים תחת כל עלה מציינים את ההסתברות להינצל ואת שיעור המופעים של התצפיות המתאימות לעלה מתוך כלל התצפיות באחוזים.

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

בניתוח החלטה, עץ ההחלטה יכול לשמש לצורך הדמיה ויזואלית ובנוסף, לקבל את ההחלטות. בכריית נתונים, עץ החלטה מתאר את הנתונים, אך לא את ההחלטות. לעומת זאת, עץ לקבלת החלטות יכול לקבל משתנה כניסה מסוים ולייצר החלטה בהתאם לנתונים. דף זה עוסק בעצי החלטה בכריית נתונים.

עצי החלטה מופעלים על תצפיות מהצורה $({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)$ כך ש $x_{1},x_{2},x_{3},...,x_{k}$ הם מאפייני התצפית ו Y הוא הערך המתאים עבור תצפית זו (ערך המטרה שאותו האלגוריתם לומד).

תיאור המודל

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

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

בניית עצי החלטה

אלגוריתמים נפוצים לבניית עצי החלטה הם CART ,ID3, C4.5, C5.0, MARS, CHAID. ברוב המקרים העץ נבנה על סמך המידע מלמעלה למטה, קרי עלים מפוצלים כצמתי החלטה בהתאם למידע שנוסף לעץ. בכל שלב נבחר מאפיין שעל פיו יתבצע פיצול בצומת ההחלטה וערך סף מתאים כך שהתצפיות שישויכו לכל תת-עץ תחת הצומת יהיו אחידות בערך ההחלטה עבורן ככל שניתן. קריטריונים נפוצים לבחירת המאפיין שעל פיו יתבצע הפיצול עבור צומת החלטה הם:

1. מדד Gini המוגדר בתור $I_{G}(f)=\sum _{i=1}^{m}f_{i}(1-f_{i})=\sum _{i=1}^{m}(f_{i}-{f_{i}}^{2})=\sum _{i=1}^{m}f_{i}-\sum _{i=1}^{m}{f_{i}}^{2}=1-\sum _{i=1}^{m}{f_{i}}^{2}$
2. מדד Information Gain המוגדר על פי נוסחת האנטרופיה

$I_{E}(f)=-\sum _{i=1}^{m}f_{i}\log _{2}^{}f_{i}$

כאשר בשני המקרים לעיל $i={1,2,...,m}$ הוא כלל מחלקות הסוג האפשרויות לתצפיות ו $f_{i}\in [0,1]$ הוא השיעור של מחלקת הסוג i בקרב כלל התצפיות המשויכות לצומת שיש לפצלו בעץ. ככל שהמדד קרוב יותר ל-0, כך הסיווג הומוגני יותר.

סוגים

עצי החלטה בשימוש בכריית נתונים הינם משני סוגים עיקריים:

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

עצים המשמשים לרגרסיה ועצים המשמשים לסיווג הם בעלי קווי דמיון, אך, גם בעלי הבדלים. הליך שונה לדוגמה הוא ההליך הקובע היכן לפצל.

טכניקות מסוימות, המכונות שיטות ההכללה, בונות יותר מעץ החלטה אחד:

• עץ החלטה Bagging- שיטת מכלול וותיקה אשר בונה עצי החלטות מרובים על ידי דגימה מחדש של הנתונים שוב ושוב עם החלפה, והצבעה לתחזית בה קיימת הסכמה כללית.
• יער אקראי- מסווג, אשר משתמש במספר עצי החלטה, על מנת לשפר את דירוג הסיווג.
• עצים משופרים- יכולים לשמש בבעיות מסוג רגרסיה ומסוג סיווג.
• עץ רוטציה- כל עץ החלטה "לומד" על ידי עקרונות ניתוח המרכיבים של היישום הראשון, על קבוצות משנה אקראיות של תכונות הקלט.

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

קיימים אלגוריתמים רבים ספציפיים עבור עצי החלטות:

• ID3- (איטרטיבי)
• C4.5- (יורשו של ID3)
• CART- (עץ סיווג ורגרסיה)
• CHAID- (אינטראקציה אוטומטית CHI-squared). מבצע פיצולים רבים כאשר מחשב עצי סיווג.
• MARS- עץ החלטה מורחב אשר מתמודד עם נתונים מספריים טוב יותר.

מדדים

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

מדד GINI

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

$I_{G}(f)=\sum _{i=1}^{m}f_{i}(1-f_{i})=\sum _{i=1}^{m}(f_{i}-{f_{i}}^{2})=\sum _{i=1}^{m}f_{i}-\sum _{i=1}^{m}{f_{i}}^{2}=1-\sum _{i=1}^{m}{f_{i}}^{2}$

רווח מידע

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

$I_{E}(f)=-\sum _{i=1}^{m}f_{i}\log _{2}^{}f_{i}$

יתרונות עץ ההחלטה

לעצי החלטה ישנם יתרונות שונים:

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

מגבלות

• הבעיה בלמידת עץ החלטות אופטימלי ידועה כ-NP-complete תחת כמה היבטים של אופטימלי ואפילו במושגים פשוטים. כתוצאה מכך, אלגוריתמים לומדים של עצי החלטה מעשיים מבוססים על שיטות היסטוריות כגון האלגוריתם ה"חמדני" שבו החלטות האופטימום המקומי נעשות בכל צומת. אלגוריתמים כאלה, לא מבטיחים החזרה של אופטימום גלובלי בעץ החלטות. על מנת להפחית את השפעת ה"חמדנים" על האופטימום המקומי הוצעו מספר שיטות כגון עץ מרחק המידע הכפול (DID).
• לומדי עצי החלטה יכולים ליצור עצים מורכבים מדיי שלא מכלילים בצורה טובה את נתוני האימון.
• ישנם מושגים קשים להבנה בגלל שעצי החלטה לא מבטאים אותם בקלות כמו XOR, בעיות שוויון ובעיות רבב. במקרים כאלה, עץ ההחלטה נהיה עצום בגודלו. גישות לפתרון הבעיה מערבות שינוי הצגת תחום הבעיה או שימוש באלגוריתמי למידה המבוססים על הצגה רחבה יותר של ביטויים (כמו למידת יחס סטטיסטי ותכנון תכנות הגיון מותווה).
• לנתונים הכוללים משתנים קטגוריאליים עם מספר רמות שונה, רווח מידע בעצי החלטה מוטה לטובת אלה עם תכונות עם יותר רמות. עם זאת, הנושא של בחירת מנבא מוטה נמנע עלי ידי הגישה מותנית ההסקה.

הרחבות

גרף החלטה

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

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

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

גיזום

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

מימושים

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

• Salford

Systems CART (אשר ברישיון על הקוד הקנייני של כותבי הCART המקוריים).

• IBM
• SPSS Modeler
• RapidMiner
• SAS Enterprise Miner
• R (סביבת תוכנה פתוחה לחישובים סטטיסטיים, הכוללת מספר יישומים של CART, כמו rpart וחבילות randomForest).
• Weka (חבילת תוכנת קוד-פתוח חינמית לכריית נתונים שמכילה אלגוריתמים רבים של עצי החלטה).
• Orange (חבילת תוכנה חינמית לכריית נתונים הכוללת את מודל עץ ההחלטה orngTree).
• KNIME
• Microsoft SQL Server
• scikit-learn (קוד פתוח חינמי ללמידת מכונה בשפת תכנות Python).

ראו גם

• תרשים עץ (הסתברות)

קישורים חיצוניים

מדיה וקבצים בנושא עץ החלטה בוויקישיתוף