עץ החלטה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
עץ החלטה המציג את שיעורי ההישרדות מבין נוסעי הספינה טיטאניק. 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^{m}_{i=1} {f_i}^{2}
  2. מדד Information Gain המוגדר על פי נוסחת האנטרופיה

I_{E}(f) = - \sum^{m}_{i=1} f_i \log^{}_2 f_i

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

גיזום[עריכת קוד מקור | עריכה]

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