אלגוריתם ID3

ממציא	רוס קווינלן

אלגוריתם ID3 הוא אלגוריתם חמדן שמייצר עץ החלטה מקבוצת דוגמאות נתונה. האלגוריתם פותח על ידי המתמטיקאי רוס קווינלן (Ross Quinlan)^[1]. האלגוריתם משמש בלמידת מכונה ובעיבוד שפות טבעיות.

אלגוריתם ID3 מתחיל עם קבוצת הדוגמאות המקורית ${\displaystyle S}$, ומגדיר אותה להיות שורש העץ. בכל איטרציה של האלגוריתם, הוא מסתכל על עלה של העץ הנוכחי, שמייצג קבוצת דוגמאות ${\displaystyle S}$. האלגוריתם עובר על כל הפיצ'רים של הקבוצה ${\displaystyle S}$ שאינם בשימוש, ומחשב את האנטרופיה ${\displaystyle \mathrm {H} {(S)}}$ של פיצ'ר זה או רווח המידע ${\displaystyle IG(S)}$ שלו, כלומר המידה בה השימוש בפיצ'ר יקטין את האנטרופיה. לאחר מכן האלגוריתם בוחר את הפיצ'ר בעל ערך האנטרופיה הקטן ביותר (או רווח המידע הגדול ביותר), ומחלק את קבוצה ${\displaystyle S}$ ל-2 תת-קבוצות או יותר. בהתבסס על חלוקה זו הוא מוסיף את הבנים של הצומת שמייצג את ${\displaystyle S}$. לדוגמה, אם ${\displaystyle S}$ היא קבוצת אנשים, ניתן לפצל אותה לתת-קבוצות של אנשים שהגיל שלהם נמוך מ-50, בין 50 ל-100, או גבוה מ-100.

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

הפיצול הרקורסיבי נפסק באחד מהמקרים הבאים:

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

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value, vi, of A,
            Add a new tree branch below Root, corresponding to the test A = vi.
            Let Examples(vi) be the subset of examples that have the value vi for A
            If Examples(vi) is empty
                Then below this new branch ad            Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A})
    End
    Return Root