הועלה לאתר:  
מספר עמודים: 47
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

בינה מלאכותית

ספר אלקטרוני מאת: ניר אדר

7.2. ID3

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

ID3 תפתח צומת אם הוא מכיל דוגמאות חיוביות ושליליות, ותעצור אם כל הדוגמאות הן מאותו סוג.

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

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

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

תוספת האינפורמציה (gain) – לכל תכונה נמדדת תוספת האינפורמציה. התכונה המביאה לתוספת האינפורמציה הגדולה ביותר נבחרת לפיצול.

נסמן ב-p את מספר הדוגמאות החיוביות, וב-n את מספר הדוגמאות השליליות, אז ההסתברות ליפול בקבוצת החיוביים הינה plot:\[\frac{p}{{p + n}}\] וההסתברות ליפול בקבוצת השליליים הינה plot:\[\frac{n}{{p + n}}\].

אי הוודאות בצומת מוגדרת על ידי נוסחת שנון:

plot:\[I\left( {p,n} \right) = \frac{p}{{p + n}} \cdot {\log _2}\left( {\frac{p}{{p + n}}} \right) - \frac{n}{{p + n}} \cdot {\log _2}\left( {\frac{n}{{p + n}}} \right)\]

כאשר אנחנו משנים מעט את log ומגדירים כי plot:\[\mathop {\lim }\limits_{x \to 0} \left( {{{\log }_2}x} \right) = 0\] וכן plot:\[{\log _2}0 = 0\].

אי הוודאות בבנים של צומת נקבע על ידי הממוצע המשוקלל של אי הוודאות בכל אחד מהם.

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

plot:\[GAIN = I\left( {p,n} \right) - \sum\limits_{i = 0}^n {\frac{{{E_i}}}{{\left| {Examples} \right|}} \cdot I\left( {{p_i},{n_i}} \right)} \]

plot:\[{E_i}\] הוא מספר הדוגמאות שעברו לבן ה-plot:\[i\], plot:\[{p_i}\] זהו מספר הדוגמאות החיוביות בבן ה-plot:\[i\] ו-plot:\[{n_i}\] הוא מספר הדוגמאות השליליות בבן ה-plot:\[i\].

plot:\[GAIN\] נע בין 0 ל-1, כאשר 1 יסמל שיפור מקסימלי ו-0 פירושו שאין כלל שיפור.

מה יקרה במידה ועברנו על כל הדוגמאות ועדיין לא הגענו לחלוקה מוחלטת לפי ערכים חיוביים וערכים שליליים? שתי אפשרויות:

  • זריקת הדוגמאות הבעיות בהנחה שהן רעש.
  • קביעת ערך העלה לפי הערך של רוב הדוגמאות שבו.

האלגוריתם של ID3:

נגדיר: I היא קבוצת הדוגמאות. plot:\[A = {A_1},...,{A_n}\] היא קבוצת כל התכונות האפשריות, ו- plot:\[{V_1},...,{V_n}\] אלו התחומים של התכונות השונות, כאשר plot:\[{V_i} = \left\{ {{V_{i1}},...,{V_{ik}}} \right\}\]

ID3 (examples, Att)
      if examples = {} then return leaf(null)
      P plot:\[ \leftarrow \] positive examples
      N plot:\[ \leftarrow \] negative examples
      if N = { } then return leaf(P)
      if P = { } then return leaf(N)
      For each Ai in Att compute gain(Ai, examples)
      Select A' such that gain(A', examples) is maximal
      for each Vi in V' compute
            Ei = { e in examples | A'(e) = Vi }
            Si = ID3(Ei, Att - {A'})
      N plot:\[ \leftarrow \] new-node()
      test(N) plot:\[ \leftarrow \] A'
      children(N) plot:\[ \leftarrow \] {<Vi,Si> | i=1...n}
      Return N



תגיות המסמך:

לפרק הקודם7.1. בעית הלמידה
לפרק הבא7.3. בעיות לתוכניות ללימוד מסווגים
מאת: אוריה

אבל הוא עדיין לא נפתח...

מאת: אוריה

סליחה, זה ב-9

והקובץ יורד בסדר
מאת: ניר

אני עם אקרובט 8.1.1

הקובץ נפתח בלי שום בעייה
מאת: shoshan

אני מציע שתנסה שוב ב-acrobat 8

כי זה עובד לי בסדר גמור ב-Acrobat 9 וב-Foxit...

יכול להיות שהקובץ ירד לך לא טוב או חתוך או קטן מידי ?
מאת: אוריה

ב-5 זה נפתח

מאת: אוריה

לא נפתח

לא נפתח ב Acrobat Reader 8, הוא כותב שהקובץ לא נתמך או שהוא ניזוק.
שיתוף:
| עוד