תרגול 12
Decision Trees & Boosting

עצי החלטה

תקציר התאוריה

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

דוגמא: מאפיינים קטגורים

Decision_trees_1

דוגמא: מאפיינים רציפים

Decision_trees_2

תכונות רצויות בבניית עץ החלטה

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

תכונה 2 חשובה משתי סיבות:

פשטות המימוש.
יכולת הכללה: מניעת התאמת-יתר לאוסף הדוגמאות הנתון.

בחירת מאפיין מיטבי

יהי $D$ אוסף של $N$ דוגמאות מסווגות $D=\{x_i,y_i\}_{i=1}^N$ , כך ש- $y_i \in \{1, \dots, K \}$ כאשר $K$ הינו מספר המחלקות האפשריות.
השכיחות היחסית (או “הפילוג האמפירי”) של כל אחד מהסיווגים האפשריים בקבוצת הדוגמאות נתונה ע”י:

$\hat{p}_j = \frac{1}{N} \sum_{i=1}^N I\{y_i = j \}\,, \quad \forall j = 1,\cdots, K$

מדדים אחידות של $D$ :

שגיאת הסיווג:

$Q(D) = 1 - \max_{j \in \{1, \dots, K \}} \hat{p}_j$

אינדקס Gini:

$Q(D) = \sum_{j \in \{1, \dots, K \}} \hat{p}_j(1 - \hat{p}_j)$

אנטרופיה:

$Q(D) = H(D) = \sum_{j \in \{1, \dots, K \}} \hat{p}_j \log \frac{1}{\hat{p}_j} = -\sum_{j \in \{1, \dots, K \}} \hat{p}_j \log {\hat{p}_j}$

תכונות של $Q(D)$ :

$Q(D)=0$ עבור פילוג חד-ערכי ( $\hat{p}_j=1$ עבור $j$ כלשהו).
$Q(D)$ מקבל את ערכו המכסימלי עבור פילוג אחיד ( $\hat{p}_j=\frac{1}{K}$ ).

info_plot

תוספת המידע של מאפיין:

נניח כי מאפיין $A$ כלשהו מחלק את $D$ למספר תת-קבוצות. נסמן תת-קבוצות אלו על ידי $\{D_m\,, m \in 1, \cdots, M\}$ , כאשר $M$ הינו אוסף הערכים האפשריים של $A$ .

מדד האחידות המשוקלל עבור האוסף $\{D_m\}$ יוגדר עתה על ידי:

$Q(D \lvert A) = \sum_{m=1}^M \frac{\lvert D_m \rvert }{N} Q(D_m)$

כאשר $Q(D_m)$ הוא מדד האחידות של תת-הקבוצה $D_m$ .

מדד טיב:

מדד הטיב של המאפיין $A$ ביחס לקבוצת הדוגמאות $D$ יוגדר עתה על ידי

$\Delta Q(D \lvert A) = Q(D) - Q(D \lvert A)$

ניתן לראות כי זהו הגידול באחידות (או הקטנה בחוסר-האחידות) של האוסף $\{D_m\}$ לעומת קבוצת הדוגמאות המקורית $D$ . כאשר $Q(\cdot)$ הינה האנטרופיה, $\Delta Q(D|A)$ נקרא גם תוספת המידע (information gain) של המאפיין $A$ .

המאפיין $A$ שנבחר הוא (כעיקרון) זה שעבורו השיפור $\Delta Q(D \lvert A)$ הינו מקסימלי כלומר $Q(D \lvert A)$ מינימלי.

שאלה 12.1 – בניית עץ החלטה

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

Name	Hair	Height	Weight	Lotion	Result (Label)
Sarah	blonde	average	light	no	sunburned (positive)
Dana	blonde	tall	average	yes	none (negative)
Alex	brown	short	average	yes	none
Annie	blonde	short	average	no	sunburned
Emily	red	average	heavy	no	sunburned
Pete	brown	tall	heavy	no	none
John	brown	average	heavy	no	none
Katie	blonde	short	light	yes	none

פתרון שאלה 12.1

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

$H(D) = -\frac{3}{8} \log{\frac{3}{8}} -\frac{5}{8} \log{\frac{5}{8}} = 0.954$

המשך פתרון:

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

Hair:

Hair	Result (Label)
blonde	sunburned (positive)
blonde	none (negative)
brown	none
blonde	sunburned
red	sunburned
brown	none
brown	none
blonde	none

המשך פתרון:

Hair:

Feature	Distribution	$H(D \lvert A)$
Blonde	$+2/-2$
Brown	$0/-3$
Red	$+1/0$

המשך פתרון:

Hair:

Feature	Distribution	$H(D \lvert A)$
Blonde	$+2/-2$	$H(D \lvert Hair = blonde ) = -\frac{1}{2} \log{\frac{1}{2}} -\frac{1}{2} \log{\frac{1}{2}} = 1$
Brown	$0/-3$	$H(D \lvert Hair = brown ) = - 0 \log{0} - 1 \log{1} = 0$
Red	$+1/0$	$H(D \lvert Hair = red ) = -1 \log 1 -0 \log{0} = 0$

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

$\Delta H(D \lvert Hair ) = H(S) -( \frac{1}{2} \cdot 1 + \frac{3}{8} \cdot 0 + \frac{1}{8} \cdot 0 )= H(D) - \frac{1}{2}$

המשך פתרון:

Height:

Feature	Distribution	$H(D \lvert A)$
Short	$+1/-2$	$H(D \lvert Height = Short ) = -\frac{1}{3} \log{\frac{1}{3}} -\frac{2}{3} \log{\frac{2}{3}} = 0.918$
Average	$2/-1$	$H(D \lvert Height = Average ) = -\frac{2}{3} \log{\frac{2}{3}} -\frac{1}{3} \log{\frac{1}{3}} = 0.918$
Tall	$0/-2$	$H(D \lvert Height = Tall ) = 0$

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

$\Delta H(D \lvert Height ) = H(S) -( \frac{3}{8} \cdot 0.918 + \frac{3}{8} \cdot 0.918 + \frac{2}{8} \cdot 0 ) = H(D) - 0.69$

המשך פתרון:

Weight:

Feature	Distribution	$H(D \lvert A)$
Light	$+1/-1$	$H(D \lvert Weight = Light ) = -\frac{1}{2} \log{\frac{1}{2}} -\frac{1}{2} \log{\frac{1}{2}} = 1$
Average	$1/-2$	$H(D \lvert Weight = Average ) = -\frac{1}{3} \log{\frac{1}{3}} -\frac{2}{3} \log{\frac{2}{3}} = 0.918$
Heavy	$+1/-2$	$H(D \lvert Weight = Heavy ) = -\frac{1}{3} \log{\frac{1}{3}} -\frac{2}{3} \log{\frac{2}{3}} = 0.918$

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

$\Delta H(D \lvert Weight ) = H(S) -( \frac{2}{8} \cdot 1 + \frac{3}{8} \cdot 0.918 + \frac{3}{8} \cdot 0.918 )= H(D) - 0.9385$

המשך פתרון:

Lotion:

Feature	Distribution	$H(D \lvert A)$
No	$+3/-2$	$H(D \lvert Lotion = No ) = -\frac{3}{5} \log{\frac{3}{5}} -\frac{2}{5} \log{\frac{2}{5}} = 0.97$
Yes	$0/-3$	$H(D \lvert Lotion = Yes ) = 0$

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

$\Delta H(D \lvert Lotion ) = H(S) -( \frac{5}{8} \cdot 0.97 + \frac{3}{8} \cdot 0 ) = H(D) - 0.606$

המשך פתרון:

מכאן שהמאפיין האופטימלי לפיצול הראשון (על פי קריטריון האנטרופיה) הוא Hair.

המשך פתרון:

עבור הפיצול של הרמה השנייה נשים לב כי הענפים של Hair=brown ו Hair=red בעלי אנטרופיה מקסימלית. כלומר, ניתן לסווג את הדוגמאות בצורה מושלמת לכן אין צורך בפיצולים נוספים. לגבי הענף Hair=blonde: קבוצת הדוגמאות בענף זה היא:

Name	Hair	Height	Weight	Lotion	Result (Label)
Sarah	blonde	average	light	no	sunburned (positive)
Dana	blonde	tall	average	yes	none (negative)
Annie	blonde	short	average	no	sunburned
Katie	blonde	short	light	yes	none

המשך פתרון:

פיצול לפי מאפיין height ייתן:

Feature	Distribution	$H(D \lvert A)$
Short	$+1/-1$	$H(D \lvert Height = Short ) = -\frac{1}{2} \log{\frac{1}{2}} -\frac{1}{2} \log{\frac{1}{2}} = 1$
Average	$1/0$	$H(D \lvert Height = Average ) = 0$
Tall	$0/-1$	$H(D \lvert Height = Tall ) = 0$

המשך פתרון:

לפי weight:

Feature	Distribution	$H(D \lvert A)$
Light	$+1/-1$	$H(D \lvert Weight = Light ) = -\frac{1}{2} \log{\frac{1}{2}} -\frac{1}{2} \log{\frac{1}{2}} = 1$
Average	$1/-1$	$H(D \lvert Weight = Average ) = -\frac{1}{2} \log{\frac{1}{2}} -\frac{1}{2} \log{\frac{1}{2}} = 1$
Heavy	$0/0$	$H(D \lvert Weight = Heavy ) = 0$

המשך פתרון:

לפי Lotion:

Feature	Distribution	$H(D \lvert A)$
No	$+2/0$	$H(D \lvert Lotion = No ) = 0$
Yes	$0/-2$	$H(D \lvert Lotion = Yes ) = 0$

לפיכך הקריטריון האופטימלי (זה שממזער את קריטריון הגידול) הוא Lotion.

עץ ההחלטה הסופי יראה כך:

Q10_tree

בעיית התאמת היתר (overfitting):

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

Name	Hair	Height	Weight	Lotion	Result (Label)
Sarah	blonde	average	light	no	sunburned (positive)
Dana	blonde	tall	average	yes	none (negative)
Alex	brown	short	average	yes	none
Annie	blonde	short	average	no	sunburned
Emily	red	average	heavy	no	sunburned
Pete	brown	tall	heavy	no	none
John	brown	average	heavy	no	none
Katie	blonde	short	light	yes	none

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

overfitting:

פתרון אפשרי: נרמול “תוספת המידע” של מאפיין $A$ באופן הבא:

$\Delta \widetilde{Q}(D \lvert A ) = \frac{\Delta Q(D \lvert A )}{\text{Split}(D , A)}$

$\text{Split}(D , A)$ כאשר הינו מקדם פיצול מתאים. הגדרה מקובלת:

$\text{Split}(D , A) = \log n(A)$

$n(A)$ כאשר, היינו מספר הערכים השונים של הנאפיין $A$ , המתקבלים על פני איברי הקבוצה $D$

מאפיינים רציפים:

$x=(x_1,…,x_d )^T$ כולל רכיבים $x_j$ בעלי ערכים רציפים. במקרה זה, המבחן המקובל לגבי $x_j$ הינו מהצורה $x_j \leq t_j$ . לפיכך, לבחירת המאפיין בכל צומת יש להוסיף את בחירת ערך הסף $t_j$ .
עבור כל מבחן $A=\{ x_j \leq t_j \}$ ניתן להגדיר את תוספת המידע באופן הרגיל:

$\Delta Q(S \lvert x_j,t_j )= \Delta Q(S \lvert A)$

השלב הבא הוא מקסימיזציה על הסף $t_i$ :

$\Delta Q(S \lvert x_j ,t_j^* )= \max_{t_j} \Delta Q(S \lvert x_j, t_j)$

ולאחר מכן בחירת המאפיין $x_j$ שעבורו מדד זה הינו מקסימלי.

Boosting - Adaboost

נסמן:

$N$ - גודל ה dataset
$\left\lbrace\boldsymbol{x}_i,y_i\right\rbrace$ - המדידות והמחלקות.
ערכי המחלקות הם $1,-1$

Adaboost algorithm

אתחל באופן אחיד את המשקולות עבור כל נקודה ב dataset: $D^{\left(t=0\right)}_i=\frac{1}{N}$

Adaboost algorithm

אתחל באופן אחיד את המשקולות עבור כל נקודה ב dataset: $D^{\left(t=0\right)}_i=\frac{1}{N}$
המשך באופן איטרטיבי עבור אינדקס עד להגעת תנאי עצירה:
1. בנה מסווג אופטימלי $h_t$ ביחס ל- dataset הממושקל

Adaboost algorithm

אתחל באופן אחיד את המשקולות עבור כל נקודה ב dataset: $D^{\left(t=0\right)}_i=\frac{1}{N}$
המשך באופן איטרטיבי עבור אינדקס עד להגעת תנאי עצירה:
1. בנה מסווג אופטימלי $h_t$ ביחס ל- dataset הממושקל
2. חשב את שגיאת הסיווג של $h_t$ עבור ה dataset הממושקל: $\varepsilon=\sum_i D^t_iI\left\lbrace h\left(\boldsymbol{x}_i\right)\neq y_i\right\rbrace$
3. חשב את משקל עבור המסווג $h_t$ לפי: $\alpha_t=\frac{1}{2}\ln\left(\frac{1-\varepsilon}{\varepsilon}\right)$
4. עדכן את המשקולות עבור כל נקודה ב-dataset : $D^t_i=D^{t-1}_i\exp\left(-\alpha_ty_ih_t\left(\boldsymbol{x}_i\right)\right)$
5. נרמל את המשקולות לפי: $Z=\sum_i D^t_i$ according to: $D^t_i=\frac{D^t_i}{Z}$

Adaboost algorithm

אתחל באופן אחיד את המשקולות עבור כל נקודה ב dataset: $D^{\left(t=0\right)}_i=\frac{1}{N}$
המשך באופן איטרטיבי עבור אינדקס עד להגעת תנאי עצירה:
1. בנה מסווג אופטימלי $h_t$ ביחס ל- dataset הממושקל
2. חשב את שגיאת הסיווג של $h_t$ עבור ה dataset הממושקל: $\varepsilon=\sum_i D^t_iI\left\lbrace h\left(\boldsymbol{x}_i\right)\neq y_i\right\rbrace$
3. חשב את משקל עבור המסווג $h_t$ לפי: $\alpha_t=\frac{1}{2}\ln\left(\frac{1-\varepsilon}{\varepsilon}\right)$
4. עדכן את המשקולות עבור כל נקודה ב-dataset : $D^t_i=D^{t-1}_i\exp\left(-\alpha_ty_ih_t\left(\boldsymbol{x}_i\right)\right)$
5. נרמל את המשקולות לפי: $Z=\sum_i D^t_i$ according to: $D^t_i=\frac{D^t_i}{Z}$

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

$H\left(\boldsymbol{x}_i\right)=\text{sign}\left(\sum_t\alpha_th_t\left(\boldsymbol{x}_i\right)\right)$

adboost_example

תרגיל 12.2: הדגמת האלגוריתם

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

$\{(x_i,y_i)\}_{i=1}^3=\{(0,-1), (1,1), (2,-1) \}.$

יהי המודל: $H\left(\boldsymbol{x}_i\right)=\text{sign}\left(\sum_t\alpha_th_t\left(\boldsymbol{x}_i\right)\right)$

האם קיימים מסווגים ליניאריים $\{h_t\}$ ופרמטרים $\{\alpha_t\}$ כך שהשגיאה של היפותזה $H(x)$ היא אפס על כל סט האימון? אם כן, מה ה-T המינימאלי לקבל שגיאה אפס?
רשום את שלבי אלגוריתם AdaBoost עבור הדוגמא.

פתרון סעיף א’

ראשית נסתכל בבעיה:

Q10_2

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

פתרון סעיף ב’

נאתחל את הפילוג:

$D_1=\frac{1}{3}$

המשך פתרון סעיף ב’

נקח את המסווג הבא: $h_1 (x_i )=\{-1,-1,-1\}$

עבורו נקבל:

$\epsilon_1=P_{D_1} (h_1 (x_i ) \neq y_i ) = \frac{1}{3} \\ a_1= \frac{1}{2} \log \frac{1 - \epsilon_1}{\epsilon_1} = 0.3466$

לעדכן את התפלגות הדוגמאות:

$Z_1= \sum_i D_1 (i) \cdot \exp (-a_1 y_i h_1 (x_i )) \\ D_2 (i) = D_1 \cdot \frac{\exp (-a_1 y_i h_1 (x_i ))}{Z_1} = \{0.25,0.5,0.25\}$

המשך פתרון סעיף ב’

באיטרציה הבאה נבחר את המסווג הבא:

$h_2 (x_i )=\{-1,+1,+1\}$

עבורו נקבל:

$\epsilon_2=P_{D_2} (h_2 (x_i ) \neq y_i ) = 0.25 \\ a_2 = \frac{1}{2} \log \frac{1-\epsilon_2}{\epsilon_2} = 0.5493$

נעדכן את הפילוג לפי המסווג הנוסף:

$Z_2 = \sum_i D_2 (i) \cdot \exp (-a_2 y_i h_2 (x_i )) \\ D_3(i) = D_2 \cdot \frac{\exp (-a_2 y_i h_2 (x_i ))}{Z_2} = \{0.1667,0.333,0.5\}$

המשך פתרון סעיף ב’

עבור הבעיה בדוגמה, מספיק עוד מסווג חלש אחד אותו נבחר כך:

$h_3 (x_i )=\{+1,+1,-1\}$

עבורו נקבל:

$\epsilon_3=P_(D_3 ) (h_3 (x_i ) \neq y_i ) = 0.1667 \\ a_3 = \frac{1}{2} \log \frac{1-ϵ_3}{ϵ_3} = 0.8047$

נעדכן את הפילוג לפי המסווג הנוסף:

$Z_3 = \sum_i D_3 (i) \cdot \exp (-a_3 y_i h_3 (x_i )) \\ D_4 (i) = D_3 \cdot \frac{\exp (-a_3 y_i h_3 (x_i ))}{Z_3} = \{0.5,0.2,0.3\}$

המשך פתרון סעיף ב’

לבסוף המסווג עם שגיאה אפס המתקבל היינו:

$H(x) = sign(\sum_{t=1}^3 (\alpha_t h_t (x)))= \{-1,+1,-1\}$

AdaBoost חלק מעשי

האתגר: בחזרה לטיטניק

ננסה לחזות האם נוסע בטיטניק ישרוד או לא על סמך רישום ונתונים של הנוסעים.

Dataset: The Titanic Manifest

ניתן להוריד את הdataset מהקישור הזה

🕵️ Data Inspection

התרשמות ראשונית ממאגר המידע, עשר השורות ראשונות מהרשומות:

	pclass	survived	name	sex	age	sibsp	parch	ticket	fare	cabin	embarked	boat	body	home.dest	numeric_sex
0	1	1	Allen, Miss. Elisabeth Walton	female	29	0	0	24160	211.3375	B5	S	2	NaN	St Louis, MO	1
1	1	0	Allison, Miss. Helen Loraine	female	2	1	2	113781	151.5500	C22 C26	S	NaN	NaN	Montreal, PQ / Chesterville, ON	1
2	1	0	Allison, Mr. Hudson Joshua Creighton	male	30	1	2	113781	151.5500	C22 C26	S	NaN	135.0	Montreal, PQ / Chesterville, ON	0
3	1	0	Allison, Mrs. Hudson J C (Bessie Waldo Daniels)	female	25	1	2	113781	151.5500	C22 C26	S	NaN	NaN	Montreal, PQ / Chesterville, ON	1
4	1	1	Anderson, Mr. Harry	male	48	0	0	19952	26.5500	E12	S	3	NaN	New York, NY	0
5	1	1	Andrews, Miss. Kornelia Theodosia	female	63	1	0	13502	77.9583	D7	S	10	NaN	Hudson, NY	1
6	1	0	Andrews, Mr. Thomas Jr	male	39	0	0	112050	0.0000	A36	S	NaN	NaN	Belfast, NI	0
7	1	1	Appleton, Mrs. Edward Dale (Charlotte Lamson)	female	53	2	0	11769	51.4792	C101	S	D	NaN	Bayside, Queens, NY	1
8	1	0	Artagaveytia, Mr. Ramon	male	71	0	0	PC 17609	49.5042	NaN	C	NaN	22.0	Montevideo, Uruguay	0
9	1	0	Astor, Col. John Jacob	male	47	1	0	PC 17757	227.5250	C62 C64	C	NaN	124.0	New York, NY	0

סה”כ ישנם $N=1001$ רשומות במאגר מידע.

The Data Fields and Types

נעשה שימוש בשדות (מאפיינים) הבאים:

pclass: מחלקת הנוסע: 1, 2 או 3
sex: מין הנוסע
age: גיל הנוסע
sibsp: מס’ של אחים ובני זוג של כל נוסע על האוניה
parch: מס’ של ילדים או הורים של כל נוסע על האונייה
fare: המחיר שהנוסע שילם על הכרטיס
embarked: הנמל בו עלה הנוסע על האונייה (C = Cherbourg; Q = Queenstown; S = Southampton)
survived: התיוג, האם הנוסע שרד או לא

📉 התרשמות ראשונית בעזרת גרפים

נציג את היחס בין המחלקות (שורדים ונספים) עבור המאפיינים:

plots

📜 הגדרת הבעיה :

משתנים אקראיים:
- $x_i$ : מאפייני הנוסע
- $y_i$ : תיוג הנוסע, שרד או נספה

נמצא מסווג $\hat{y}=h^*\left(\boldsymbol{x}\right)$ אשר מביא למינימום את ה- miscalssification rate:

$h^*=\underset{h}{\arg\min}\ E\left[I\left\lbrace h\left(\boldsymbol{x}\right)\neq y\right\rbrace\right]$

💡 Model & Learning Method Suggestion: Stumps + AdaBoost

.נשתמש בעץ בינארי בעל עומק אחד (נקרא Stump), שבעצם מסווג על פי מאפיין בודד בשילוב של אלגוריתם AdaBoost

הערה: ניתן להגיד שהשילוב הנ”ל הוא וריאציה של Random Forest, אלגוריתם שמשלב מספר עצים. כמו כן הטכניקה הזאת נקראת גם Ensemble.

קריטריון בניית עץ

עבור קריטריון בניית עץ נשתמש בGini אינדקס ממושקל הנובע מה-data הממושקל. עבור חלוקה של ה-data לשני סטים $\mathcal{C}_1$ and $\mathcal{C}_2$ , וסט המשקולות של הדגימות $\left\lbrace w_i\right\rbrace$ נקבל את Gini אינדקס ממושקל:

$N_1=\sum_{i\in\mathcal{C}_1}w_i\\ N_2=\sum_{i\in\mathcal{C}_2}w_i\\ p_1=\frac{1}{N_1}\sum_{i\in\mathcal{C}_1}w_iI\left\lbrace y_i=1\right\rbrace\\ p_2=\frac{1}{N_2}\sum_{i\in\mathcal{C}_2}w_iI\left\lbrace y_i=1\right\rbrace\\ G=N_1p_1\left(1-p_1\right)+N_2p_2\left(1-p_2\right)$

פרמטרים נלמדים:

החלוקה המתבצעת על ידי כל עץ.
משקול כל עץ: $\alpha_i$ .

Hyper-parameters

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

📚 חלוקת ה-dataset

נחלק ל 80% סט אימון ו 20% סט בוחן.

⚙️ אימון

נאתחל את המודל ונציג את עשר השורות הראשונות של הdataset הממושקל וההתפלגות לפי המאפיינים:

	age	embarked	fare	parch	pclass	sex	sibsp	survived	weights
724	11	2	46.9000	2	2	0	5	0	0.001252
77	27	2	30.5000	0	0	0	0	1	0.001252
879	6	2	21.0750	1	2	0	3	0	0.001252
615	22	2	7.2500	0	2	0	1	0	0.001252
905	24	2	8.6625	0	2	0	0	0	0.001252
533	42	2	7.5500	0	2	0	0	0	0.001252
401	50	2	13.0000	0	1	0	0	0	0.001252
454	39	2	26.0000	0	1	0	0	0	0.001252
31	58	2	26.5500	0	0	1	0	1	0.001252
358	18	2	13.0000	0	1	0	0	0	0.001252

Gini-Index $t=0$

png

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

Iteration: $t=1$

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

שגיאה: 0.22
$\alpha$ : 0.6320312618746508
Classifing sex according to: {0: [0], 1: [1]}

נציג את המשוקל של ה-data מחדש, וההתפלגויות החדשות:

	age	embarked	fare	parch	pclass	sex	sibsp	survived	weights
724	11	2	46.9000	2	2	0	5	0	0.000803
77	27	2	30.5000	0	0	0	0	1	0.002841
879	6	2	21.0750	1	2	0	3	0	0.000803
615	22	2	7.2500	0	2	0	1	0	0.000803
905	24	2	8.6625	0	2	0	0	0	0.000803
533	42	2	7.5500	0	2	0	0	0	0.000803
401	50	2	13.0000	0	1	0	0	0	0.000803
454	39	2	26.0000	0	1	0	0	0	0.000803
31	58	2	26.5500	0	0	1	0	1	0.000803
358	18	2	13.0000	0	1	0	0	0	0.000803

Gini-Index $t=1$

png

נשים לב

נבחין בכך, שככל שנתקדם באיטרציות של האלגוריתם, ה-data הממושקל יתפלג באופן אחיד כפונקציה של המחלקות, כלומר ההתפלגות של הדגימות שעבורן $y=1$ זהה להתפלגות של הדגימות שעבורן $y=-1$ .

כתוצאה מכך, הסיווג על פי מאפיין בודד יהיה קשה יותר והשגיאה למסווג בודד תתקרב ל-0.5, ובאופן ישיר המשקל של כל מסווג $\alpha_t$ ידעך.

בשלב הבא נסווג לפי pclass:

Iteration $t=2$

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

שגיאה: 0.66
$\alpha$ : -0.34
Classifing pclass according to: {1: [0], 0: [1, 2]}

	age	embarked	fare	parch	pclass	sex	sibsp	survived	weights
724	11	2	46.9000	2	2	0	5	0	0.000601
77	27	2	30.5000	0	0	0	0	1	0.002127
879	6	2	21.0750	1	2	0	3	0	0.000601
615	22	2	7.2500	0	2	0	1	0	0.000601
905	24	2	8.6625	0	2	0	0	0	0.000601
533	42	2	7.5500	0	2	0	0	0	0.000601
401	50	2	13.0000	0	1	0	0	0	0.000601
454	39	2	26.0000	0	1	0	0	0	0.000601
31	58	2	26.5500	0	0	1	0	1	0.000601
358	18	2	13.0000	0	1	0	0	0	0.000601

Gini-Index $t=2$

png

באיטרציה השלישית נסווג לפי embarked:

Iteration $t=3$

שגיאה: 0.53
$\alpha$ : -0.06
Classifing embarked according to: {1: [0], 0: [1, 2]}

	age	embarked	fare	parch	pclass	sex	sibsp	survived	weights
724	11	2	46.9000	2	2	0	5	0	0.000564
77	27	2	30.5000	0	0	0	0	1	0.002274
879	6	2	21.0750	1	2	0	3	0	0.000564
615	22	2	7.2500	0	2	0	1	0	0.000564
905	24	2	8.6625	0	2	0	0	0	0.000564
533	42	2	7.5500	0	2	0	0	0	0.000564
401	50	2	13.0000	0	1	0	0	0	0.000564
454	39	2	26.0000	0	1	0	0	0	0.000564
31	58	2	26.5500	0	0	1	0	1	0.000643
358	18	2	13.0000	0	1	0	0	0	0.000564

Gini-Index $t=3$

png

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

Iteration $t=4$

שגיאה : 0.5000000000000001
$\alpha$ : -2.2204460492503136e-16
Classifing embarked according to: {1: [0], 0: [1, 2]}

	age	embarked	fare	parch	pclass	sex	sibsp	survived	weights
724	11	2	46.9000	2	2	0	5	0	0.000564
77	27	2	30.5000	0	0	0	0	1	0.002274
879	6	2	21.0750	1	2	0	3	0	0.000564
615	22	2	7.2500	0	2	0	1	0	0.000564
905	24	2	8.6625	0	2	0	0	0	0.000564
533	42	2	7.5500	0	2	0	0	0	0.000564
401	50	2	13.0000	0	1	0	0	0	0.000564
454	39	2	26.0000	0	1	0	0	0	0.000564
31	58	2	26.5500	0	0	1	0	1	0.000643
358	18	2	13.0000	0	1	0	0	0	0.000564

Gini-Index $t=4$

png

באיטרציה האחרונה קיבלנו ששגיאת המסווג קרובה ל 0.5 והמשקל שלו $\alpha_t \approx 0$ , לכן ניתן להפסיק את תהליך הלימוד.

⏱️ ביצועים:

נריץ את האלגוריתם המאומן על סט המבחן ונקבל שהסיכון היינו: $0.225$

תרגול 12Decision Trees & Boosting

עצי החלטה

תקציר התאוריה

דוגמא: מאפיינים קטגורים

דוגמא: מאפיינים רציפים

תכונות רצויות בבניית עץ החלטה

בחירת מאפיין מיטבי

מדדים אחידות של D:

תכונות של Q(D) :

תוספת המידע של מאפיין:

מדד טיב:

שאלה 12.1 – בניית עץ החלטה

פתרון שאלה 12.1

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

המשך פתרון:

עץ ההחלטה הסופי יראה כך:

בעיית התאמת היתר (overfitting):

overfitting:

מאפיינים רציפים:

Boosting - Adaboost

Adaboost algorithm

Adaboost algorithm

Adaboost algorithm

Adaboost algorithm

תרגיל 12.2: הדגמת האלגוריתם

פתרון סעיף א’

פתרון סעיף ב’

המשך פתרון סעיף ב’

המשך פתרון סעיף ב’

המשך פתרון סעיף ב’

המשך פתרון סעיף ב’

AdaBoost חלק מעשי

האתגר: בחזרה לטיטניק

Dataset: The Titanic Manifest

🕵️ Data Inspection

The Data Fields and Types

📉 התרשמות ראשונית בעזרת גרפים

📜 הגדרת הבעיה :

💡 Model & Learning Method Suggestion: Stumps + AdaBoost

קריטריון בניית עץ

פרמטרים נלמדים:

Hyper-parameters

📚 חלוקת ה-dataset

⚙️ אימון

Gini-Index t=0

Iteration: t=1

Gini-Index t=1

נשים לב

Iteration t=2

Gini-Index t=2

Iteration t=3

Gini-Index t=3

Iteration t=4

Gini-Index t=4

⏱️ ביצועים:

תרגול 12
Decision Trees & Boosting

מדדים אחידות של $D$ :

תכונות של $Q(D)$ :

Gini-Index $t=0$

Iteration: $t=1$

Gini-Index $t=1$

Iteration $t=2$

Gini-Index $t=2$

Iteration $t=3$

Gini-Index $t=3$

Iteration $t=4$

Gini-Index $t=4$