עץ החלטה

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

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

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

תיאור המודל

עץ החלטה הוא עץ בינארי מלא המורכב מצמתי החלטה שבכל אחד מהם נבדק תנאי מסוים על מאפיין מסוים של התצפיות ועלים המכילים את הערך החזוי עבור התצפית המתאימה למסלול שמוביל אליהם בעץ. סוגים של עצי החלטה הם עצי רגרסיה שבהם מותאם ערך רציף לכל תצפית ועצי סיווג שבהם מותאם ערך בדיד או מחלקת סוג לכל תצפית. כמו כן קיימים עצי החלטה מסוג (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 - שיטה המתבססת על בניית N עצים על N מדגמי Bootstrap (מדגמים הנוצרים באמצעות דגימה חוזרת עם החזרה מהמדגם המקורי), ושקלול תוצאותיהם לכדי החלטה. שיטה זו חסינה באופן יחסי להתאמת יתר (Over-fitting) ובעלת ביצועים טובים יותר בהשוואה לעץ יחיד. עם זאת, חסרונה הוא שעציה דומים זה לזה, לפיכך, השיטה עלולה לגרום לפתרון שהוא מינימום מקומי מבחינת צמצום הטעות .
• יער אקראי (Random Forest) - פיתוח של שיטת ה-Bagging, אשר משתמשת גם היא בבניית עצי החלטה מבוססי מדגמי Bootstrap, אך גורמת לשונות רבה יותר בין העצים הנוצרים על בסיס מדגמי ה-Bootstrap באמצעות הסתרת חלקי מידע בהליך יצירת העץ. בכך שקלול התוצאות הסופי מתבצע על עצים מגוננים יותר בהשוואה ל-bagging, ולרוב מאופיין גם בביצועים טובים יותר, לצד שימור החסינות היחסית להתאמת יתר.
• עצים משופרים (boosted trees) - הליך סדרתי, בו כל עץ לומד לנבא את החלקים במידע אשר לא הצליח לנבא העץ הקודם (השארית - residuals). לרוב בשיטה זו משתמשים בעצים פשוטים ביותר, לרוב עם צומת אחת או שתיים, וקובעים משקל מאוד נמוך (לדוגמה w=0.001) לכל עץ, כך שהשאריות מצטמצמות באופן איטי. בשל כך הליך הלמידה boosted trees נחשב הליך של 'לומד איטי' (A slow learner). השם עצים משופרים ניתן למודל מאחר וכל עץ תלוי בעץ הקודם, והוא בעצם מהווה 'שיפור' שלו.

מדדים

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

מדד GINI

בעץ CART (עץ סיווג ורגרסיה) משתמשים במדד ג'יני (Gini). מדד זה מודד הומוגניות של קבוצה, ויש לו שימושים רבים באפיון אי-שווין כלכלי של מדינות. ערכי המדד נעים בין 0 ל-1, כאשר 1 מייצג הומוגניות מוחלט - כל הערכים בקבוצה זהים.

על מנת לחשב את מדד ג'יני עבור קבוצת פריטים, מ-1 עד m, כאשר $f_{i}$ מייצג את מספר התצפיות עם הערך $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).

ראו גם

• תרשים עץ (הסתברות)
• רשת השפעה
• רשימת החלטה

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

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