מפצל מדויק לסיווג בינארי עם תכונות מספריות

ביחידה זו, תעיינו באלגוריתם המפצל הפשוט והנפוץ ביותר, שיוצר תנאים בצורת $\mathrm{feature}_i \geq t$ בהגדרה הבאה:

• משימה של סיווג בינארי
• חסרים ערכים בדוגמאות
• ללא אינדקס מחושבת מראש בדוגמאות

נניח קבוצה של $n$ דוגמאות עם תכונה נומרית ותווית בינארית "orange" ו-"blue". באופן רשמי, תאר את מערך הנתונים $D$ כ:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

כאשר:

• $x_i$ הוא הערך של תכונה מספרית ב-$\mathbb{R}$ (קבוצת המספרים האמיתיים).
• $y_i$ הוא ערך של תווית סיווג בינארית ב-{orange, כחול}.

המטרה שלנו היא למצוא ערך סף של $t$ (סף) כך שחלוקת הדוגמאות $D$ לקבוצות $T(rue)$ ו-$F(alse)$ בהתאם לתנאי $x_i \geq t$ משפרת את ההפרדה של התוויות; לדוגמה, יותר "orange" דוגמאות ב-$T$ ועוד "כחול"דוגמאות ב-$T$ ועוד "כחול.

אנכרון אננון הוא מדד של הפרעה. עבור תווית בינארית:

• השיפוע של שנון הוא לכל היותר כאשר התוויות בדוגמאות מאוזנות (50% כחול ו-50% כתום).
• השיפוע של שנון הוא לכל הפחות (ערך אפס) כאשר התוויות בדוגמאות הן טהורות (100% כחול או 100% כתום).

איור 8. שלוש רמות אנטרופיה שונות.

 

באופן רשמי, אנחנו רוצים למצוא תנאי שמקטין את הסכום המשוקלל של החלוקה של התוויות ב-$T$ וב-$F$. הציון המתאים הוא שיפור המידע, שהוא ההבדל בין האנטרופיה של $D$' לבין האנטרופיה של ${$T$,$F$}. ההבדל הזה נקרא שיפור מידע.

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

איור 9. פיצול לא תקין לא מצמצם את האנטרופיה של התווית.

 

לעומת זאת, באיור הבא מוצג פיצול טוב יותר שבו האנטרופיה מצטמצמת (והמידע עולה):

איור 10. פיצול טוב מצמצם את האנטרופיה של התווית.

 

באופן רשמי:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

כאשר:

• $IG(D,T,F)$ הוא רווח המידע של פיצול $D$ ל-$T$ ו-$F$.
• $H(X)$ הוא השורש של קבוצת הדוגמאות $X$.
• $|X|$ הוא מספר הרכיבים ברכיב $X$.
• $t$ הוא ערך הסף.
• $pos$ הוא ערך התווית חיובי, למשל "blue" בדוגמה שלמעלה. אם בוחרים תווית אחרת כ "תווית חיובית&quot, לא משנה את הערך של האנטרופיה או של ערך המידע.
• $R(X)$ הוא היחס של ערכי תוויות חיוביים בדוגמאות של $X$.
• $D$ הוא מערך הנתונים (כפי שמוגדר קודם לכן ביחידה זו).

בדוגמה הבאה נחשב מערך נתונים בינארי של מאפיין בינארי עם תכונה מספרית אחת $x$. האיור הבא מוצג עבור ערכי סף $t$ (ציר X):

1. ההיסטוגרמה של התכונה $x$.
2. היחס בין "blue" דוגמאות בקבוצות $D$, $T$ ו-$F$ בהתאם לערך הסף.
3. האנטרופיה ב-$D$, $T$ ו-$F$.
4. המידע מתעדכן. כלומר, הדלתא של האנטרופיה בין $D$ לבין {$T$,$F$} משוקללת לפי מספר הדוגמאות.

איור 11. ארבע עליות סף.

 

תרשימים אלה מציגים את המידע הבא:

• עלילה &תדירות המשמעות של חלוקה רחבה של ערכי ההמרות היא שיש הרבה פיצולים פוטנציאליים. שיטה זו מתאימה לאימון המודל.

• היחס בין תוויות "blue" במערך הנתונים הוא כ-25%. &הדירוג של תווית כחולה&מירכאות; התרשים מציג כי ערכי הסף הם בין 20 ל-50:

  • קבוצת $T$ מכילה עודף של "כחול"דוגמאות לתווית (עד 35% עבור סף 35).
  • קבוצת ה-$F$ מכילה גימור משלים של דוגמאות ב-"blue" תוויות (רק 8% לסף 35).

  שני הערכים "היחס של תוויות כחולות&quot, ותרשימי המירכאות וה&מירכאות; מציינים שהתוויות יכולות להיות מופרדות יחסית בטווח זה של סף.

• תצפית זו מאושרת בחלק & אנחנו רואים שהשגת המידע המקסימלי היא t~=28, בערך של העלאת ערך של 0.074~. לכן, התנאי שיוחזר על ידי המפצל יהיה $x \geq 28$.

• קבלת המידע היא תמיד חיובית או ריקה. הערך מתכוונן לאפס כי ערך הסף מתקרב לערך המקסימלי / המינימלי שלו. במקרים כאלה, הערך $F($)$ או $T$ ריק

ערכי המועמדים עבור $t$ בקבוצת המספרים האמיתיים ($\mathbb{R}$) הם אינסופיים. עם זאת, בהינתן מספר סופי של דוגמאות, יכול להיות רק מספר מוגבל של חטיבות של $D$ ל-$T$ ול-$F$. לכן, רק מספר סופי של ערכים בסכום של $t$ הוא משמעותי לבדיקה.

גישה קלאסית היא מיון הערכים x_i בסדר עולה x_s(i) כך:

$$ x_{s(i)} \leq x_{s(i+1)} $$

לאחר מכן, בודקים את הערך $t$ לכל ערך באמצע הדרך בין ערכים ממוינים רצופים של $x_i$. לדוגמה, נניח שיש לכם 1,000 ערכים של נקודות צפות לתכונה מסוימת. לאחר המיון, נניח ששני הערכים הראשונים הם 8.5 ו-8.7. במקרה כזה, ערך הסף הראשון לבדיקה יהיה 8.6.

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

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

מורכבות הזמן של האלגוריתם הזה היא $\mathcal{O} ( n \log n) $ עם $n$ מספר הדוגמאות בצומת (בגלל מיון הערכים של התכונות). כשמחילים את הנתונים על עץ החלטות, אלגוריתם הפיצול חל על כל צומת ובכל תכונה. לתשומת ליבכם: כל צומת מקבל כ-1/2 מהדוגמאות שהוא כולל. לכן, בהתאם למשפט הראשי, מורכבות הזמן של אימון עץ עם המפצל הזה היא:

$$ \mathcal{O} ( m n \log^2 n ) $$

כאשר:

• $m$ הוא מספר התכונות.
• $n$ הוא מספר הדרכות.

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