יערות אקראיים
יער אקראי (RF) הוא קבוצה של עצי החלטה שבה כל עץ החלטה מאומן באמצעות רעש אקראי ספציפי. יערות אקראיים הם הצורה הפופולרית ביותר של אנסמבל של עצי החלטות. ביחידה הזו נסביר על כמה שיטות ליצירת עצי החלטות עצמאיים כדי לשפר את הסיכויים ליצירת יער אקראי יעיל.
אריזה
Bagging (bootstrap aggregating) הוא אימון של כל עץ החלטה על קבוצת משנה אקראית של הדוגמאות בקבוצת האימון. במילים אחרות, כל עץ החלטות ביער האקראי מאומן על קבוצת משנה שונה של דוגמאות.
האריזות הן ייחודיות. כל עץ החלטות מאומן על סמך אותו מספר דוגמאות כמו בקבוצת האימון המקורית. לדוגמה, אם קבוצת האימון המקורית מכילה 60 דוגמאות, כל עץ החלטות יתאמן על 60 דוגמאות. עם זאת, ב-bagging כל עץ החלטות מאומן רק על קבוצת משנה (בדרך כלל 67%) של הדוגמאות האלה. לכן, צריך להשתמש מחדש בחלק מ-40 הדוגמאות האלה בקבוצת המשנה במהלך האימון של עץ החלטות נתון. שימוש חוזר כזה נקרא אימון 'עם החלפה'.
לדוגמה, בטבלה 6 מוצג איך bagging יכול לחלק שש דוגמאות בין שלושה עצי החלטות. חשוב לשים לב לפרטים הבאים:
- כל עץ החלטות מתאמן על סך של שש דוגמאות.
- כל עץ החלטות מתאמן על קבוצה שונה של דוגמאות.
- בכל עץ החלטות נעשה שימוש חוזר בדוגמאות מסוימות. לדוגמה, דוגמה מס' 4 משמשת פעמיים באימון של עץ ההחלטות מס' 1. לכן, המשקל של דוגמה מס' 4 שהתקבל מהאימון כפול בערך בעץ ההחלטות מס' 1.
טבלה 6. קיבוץ של שש דוגמאות אימון בשלושה עצי החלטות. כל מספר מייצג את מספר הפעמים שדוגמה מסוימת לאימון (1-6) חוזרת על עצמה במערך הנתונים לאימון של עץ החלטות נתון (1-3).
דוגמאות לאימון | ||||||
---|---|---|---|---|---|---|
#1 | #2 | #3 | #4 | #5 | #6 | |
מערך הנתונים המקורי | 1 | 1 | 1 | 1 | 1 | 1 |
עץ החלטות 1 | 1 | 1 | 0 | 2 | 1 | 1 |
עץ החלטות 2 | 3 | 0 | 1 | 0 | 2 | 0 |
עץ החלטות 3 | 0 | 1 | 3 | 1 | 0 | 1 |
ב-bagging, כמעט תמיד כל עץ החלטות מאומן על סמך המספר הכולל של הדוגמאות בקבוצת האימון המקורית. אימון של כל עץ החלטה על יותר דוגמאות או על פחות דוגמאות נוטה לפגוע באיכות של יער האקראי.
האפשרות הזו לא מופיעה במאמר המקורי על יער אקראי, אבל לפעמים הדגימה של דוגמאות מתבצעת "ללא החלפה". כלומר, דוגמה לאימון לא יכולה להופיע יותר מפעם אחת בקבוצת אימון של עץ החלטות. לדוגמה, בטבלה הקודמת, כל הערכים יהיו 0 או 1.
bootstrap_training_dataset=False
דגימת מאפיינים
דגימת מאפיינים: במקום לחפש את התנאי הטוב ביותר בכל התכונות הזמינות, נבדקת רק קבוצת משנה אקראית של תכונות בכל צומת. קבוצת התכונות שנבדקות נבחרת באופן אקראי בכל צומת של עץ ההחלטות.
בעץ ההחלטות הבא מוצגת הדגימה של המאפיינים. כאן עץ החלטות מאומן על 5 מאפיינים (f1-f5). הצמתים הכחולים מייצגים את התכונות שנבדקו, והצומתים הלבנים לא נבדקו. התנאי נוצר מהתכונות שנבדקו בצורה הטובה ביותר (התכונות האלה מיוצגות בקו מתאר אדום).
איור 21. דגימת מאפיינים.
היחס של דגימת המאפיינים הוא היפר-פרמטר חשוב של רגולריזציה. בתרשים הקודם נעשה שימוש ביחס של כ-⅗. בהרבה הטמעות של יער אקראי, כברירת מחדל נבדקים 1/3 מהמאפיינים לצורך רגרסיה ו-sqrt(מספר המאפיינים) לצורך סיווג.
ב-TF-DF, הפרמטרים האלגוריתמיים הבאים שולטים בדגימת המאפיינים:
num_candidate_attributes
num_candidate_attributes_ratio
לדוגמה, אם num_candidate_attributes_ratio=0.5
, מחצית מהתכונות ייבדקו בכל צומת.
השבתת רגולריזציה של עץ החלטות
עצי החלטה ספציפיים ביער אקראי עוברים אימון ללא גיזום. (ראו התאמה יתר וצמצום). התוצאה היא עצים מורכבים מדי עם איכות חיזוי נמוכה. במקום לנרמל עצים נפרדים, העצים מורכבים יחד כדי ליצור תחזיות כלליות מדויקות יותר.
צפוי שהדיוק של אימון ועריכת בדיקה של יער אקראי יהיה שונה. בדרך כלל, דיוק האימון של יער אקראי גבוה בהרבה (לפעמים הוא שווה ל-100%). עם זאת, דיוק אימון גבוה מאוד ביער אקראי הוא נורמלי ולא מעיד על כך שהיער האקראי עבר התאמה יתר.
שני מקורות האקראיות (bagging ודגימת מאפיינים) מבטיחים את העצמאות היחסית בין עצי ההחלטות. העצמאות הזו מתקנת את ההתאמה היתרה של עצי ההחלטות הנפרדים. כתוצאה מכך, האנסמבל לא מותאם יתר על המידה. נציג את ההשפעה הלא אינטואיטיבית הזו ביחידה הבאה.
יער אקראי טהור מתאמן בלי עומק מקסימלי או מספר מינימלי של תצפיות לכל עלה. בפועל, מומלץ להגביל את העומק המקסימלי ואת מספר התצפיות המינימלי לכל עלה. כברירת מחדל, הרבה יערות אקראיים משתמשים בברירת המחדל הבאה:
- עומק מקסימלי של כ-16
- מספר מינימלי של תצפיות לכל עלה של כ-5.
אפשר לשנות את הפרמטרים האלה.
הבהירות של הרעש
למה רעש אקראי ישפר את האיכות של יער אקראי? כדי להמחיש את היתרונות של רעש אקראי, באיור 22 מוצגים התחזיות של עץ החלטות קלאסי (קצוץ) ושל יער אקראי שהוכשרו על כמה דוגמאות לבעיה דו-ממדית פשוטה עם דפוס של אליפס.
דפוסי אליפסות קשים במיוחד לאלגוריתמים של עצי החלטות ויערות החלטות ללמוד עם תנאים שמותאמים לציר, ולכן הם דוגמה טובה. שימו לב שאי אפשר לקבל את אותה איכות חיזוי בעץ ההחלטות שנחתך כמו ביער האקראי.
איור 22. עובדות מוכרות לעומת תחזיות שנוצרו על ידי עץ החלטות יחיד שעבר גיזום ותחזיות שנוצרו על ידי יער אקראי.
בתרשים הבא מוצגים התחזיות של שלושת עצי ההחלטה הראשונים של יער האקראי שלא עברו גיזום. כלומר, עצי ההחלטה הוכשרו באמצעות שילוב של:
- bagging
- דגימת מאפיינים
- השבתת הצמצום
שימו לב שהתחזיות הנפרדות של שלושת עצי ההחלטה האלה גרועות מהתחזיות של עץ ההחלטה שנחתך באיור הקודם. עם זאת, מאחר שהשגיאות של עצי ההחלטות הנפרדים קשורות זו לזו רק באופן רופף, שלושת עצי ההחלטות משולבים בקבוצה כדי ליצור תחזיות יעילות.
איור 23. שלושה עצי החלטות ללא גיזום, שיוצרים אנסמבל יעיל.
מכיוון שעצבי העץ של יער אקראי לא נחתכים, אימון של יער אקראי לא מחייב מערך נתונים לאימות. בפועל, ובמיוחד במערכי נתונים קטנים, מומלץ לאמן מודלים על כל הנתונים הזמינים.
כשמאמנים יער אקראי, ככל שמוסיפים עוד עצי החלטות, הטעות בדרך כלל קטנה. כלומר, איכות המודל בדרך כלל משתפרת. כן, הוספת עוד עצי החלטה כמעט תמיד מצמצמת את השגיאה של יער האקראי. במילים אחרות, הוספת עוד עצי החלטה לא יכולה לגרום להתאמה יתר של יער האקראי. בשלב מסוים, המודל פשוט מפסיק להשתפר. Leo Breiman אמר את המשפט המפורסם: "Random Forests לא נוטים להתאמה יתר ככל שמוסיפים עצים".
לדוגמה, בתרשים הבא מוצגת הערכת הבדיקה של מודל יער אקראי ככל שמוסיפים עוד עצי החלטה. הדיוק משתפר במהירות עד שהוא מגיע לשיא של כ-0.865. עם זאת, הוספת עוד עצי החלטות לא גורמת לירידה ברמת הדיוק. במילים אחרות,המודל לא מתאים יותר מדי. ההתנהגות הזו תמיד נכונה (בדרך כלל) ולא תלויה בהיפר-פרמטרים.
איור 24. הדיוק נשאר קבוע כשמוסיפים עוד עצי החלטות ליערות האקראיים.