מכאן שגם הוקטור הראשון וגם השלישי הם וקטורים עצמיים.
הוקטור הראשון בהטלה של PCA יהיה השלישי שכן הוא מתאים לערך עצמי גדול יותר:
u1=51(12),
2) חשבו את שני ה principal components של x=(1,0)⊤.
הרכיב העיקרי (principal component) הראשון יהיה נתון על ידי:
z1=u1⊤(x−μ)=51(12)(10)=51
והרכיב השני יהיה:
z2=u2⊤(x−μ)=51(−21)(10)=5−2
בעבור PCA עם k=2 נקבל:
z=51(1,−2)⊤
תרגיל 12.2
נתונות (1+3α)n נקודות שונות:
n נקודות בקואורדינאטות A=(−6,6)
αn נקודות בכל אחת מהקואורדינאטות B=(6,6),C=(8,6),D=(1,−6)
הנקודות יושבות אחת על השניה בכל קואורדינטה, ומצויירות כעיגולים רק לצורך השרטוט.
נרצה לבצע אשכול של הנקודות ל3 אשכולות בעזרת K-Means.
1) מאתחלים את המרכזים על ידי בחירה אקראית של 3 מתוך ארבעת הנקודות A,B,C,D. לאילו חלוקות יתכנס האלגוריתם בעבור כל אחת מארבעת האתחולים האפשריים?
2) מהו האשכול האופטימאלי (הממזער של פונקציית המטרה)? רשמו את הפתרון כתלות בפרמטר α. (ניתן להניח כי בפתרון האופטימאלי כל הנקודות שנמצאות באותו המקום משוייכות לאותו האשכול)
3) האם קיים אתחול שעבורו האלגוריתם לא יתכנס לפתרון האופטימאלי שמצאתם בסעיף הקודם? הדגימו.
פתרון 12.2
1) מאתחלים את המרכזים על ידי בחירה אקראית של 3 מתוך ארבעת הנקודות A,B,C,D. לאילו חלוקות יתכנס האלגוריתם בעבור כל אחת מארבעת האתחולים האפשריים?
נחשב את תוצאת האלגוריתם בעבור כל אחת מארבעת האתחולים:
מרכזים ב A,B ו C:
שיוך התחלתי (0a): נקודות בA,B ו C ישוייכו למרכז אשר הנמצא עליהם, והנקודות בD ישוייכו למרכז שבB.
עדכון מרכזים (0b): המרכז שב B יזוז לאמצע הדרך שבין הנקודות B ו D.
עדכון אשכולות (1a): הנקודת שבB ישוייכו כעת למרכז שבC.
עדכון מרכזים (1b): המרכז שבין B ל D יזוז לD, והמרכז שבC יזוז למחצית הדרך שבין B לC.
מרכזים ב A,B ו D:
שיוך התחלתי (0a): נקודות בA,B ו D ישוייכו למרכז אשר נמצא עליהם, והנקודות בC ישוייכו למרכז שבB.
עדכון מרכזים (0b): המרכז שב B יזוז לאמצע הדרך שבין הנקודות B ו C.
מרכזים ב A,C ו D:
שיוך התחלתי (0a): נקודות בA,C ו D ישוייכו למרכז אשר נמצא עליהם, והנקודות בB ישוייכו למרכז שבC.
עדכון מרכזים (0b): המרכז שב C יזוז לאמצע הדרך שבין הנקודות B ו C.
מרכזים ב B,C ו D:
שיוך התחלתי (0a): נקודות בB,C ו D ישוייכו למרכז אשר נמצא עליהם, והנקודות בA ישוייכו למרכז שבB.
עדכון מרכזים (0b): המרכז שב B יזוז לנקודה שהיא המרכז של הנקודות A ו B. (משום שכמות הנקודות בשתי הקבוצות שונה, נקודה זו היא לא אמצע הדרך בניהם).
השלב הבא של עידכון האשכולות תלוי במיקום של המרכז החדש.
מקרה 1: הנקודות ב-B קרובות יותר למרכז החדש מאשר למרכז שב-C ולכן האלגוריתם מסתיים.
מקרה 2, המרכז החדש רחוק יותר לנקודה B מאשר הנקודה C, אזי הנקודות בB יהיו מושייכות כעת למרכז בנקודה C, והמשך האלגוריתם יהיה:
נמצא את התנאי על α שבעבורו מתרחש מקרה 2.
נסמן ב μ1 את המרכז שבין A לB לאחר עדכון המרכזים הראשון.
המיקום של μ1 נתון על ידי הממוצע המשוקלל של הקואורדיאנטות A ו B:
2) מהו האשכול האופטימאלי (הממזער של פונקציית המטרה)? רשמו את הפתרון כתלות בפרמטר α. (ניתן להניח כי בפתרון האופטימאלי כל הנקודות שנמצאות באותו המקום משוייכות לאותו האשכול)
אנו מעוניינים למצוא את האשכול אשר מביא למינימום את הפונקציית המטרה הבאה:
k=1∑K2∣Ik∣1i,j∈Ik∑∥x(j)−x(i)∥22
נוכל לפסול פתרונות בהן ישנו אשכול ריק, משום שבמקרה זה נוכל לשייך אליו נקודות כלשהן על מנת להקטין את פונקציית המטרה.
לכן הפתרון האופטימאלי חייב להיות אחד מששת האישכולים הבאים:
(A,B), (C), (D)
(A,C), (B), (D)
(A,D), (B), (C)
(B,C), (A), (D)
(B,D), (A), (C)
(C,D), (A), (B)
התרומה של האשכולות שמכילים נקודה בודדת לפונקציית המטרה הינה 0.
לכן יש לחשב רק את התרומה של האשכול שמכיל זוג נקודות. למשל, עבור האשכול (A,B), (C), (D) נקבל:
נחזור למדגם של נסיעות מונית בניו-יורק בו השתמשנו בתרגולים הראשונים לחיזוי זמן הנסיעה. נציג את 10 הדגימות הראשונות במדגם (סה"כ במדגם זה 100,000 נסיעות).
passenger count
trip distance
payment type
fare amount
tip amount
pickup easting
pickup northing
dropoff easting
dropoff northing
duration
day of week
day of month
time of day
0
2
2.76806
2
9.5
0
586.997
4512.98
588.155
4515.18
11.5167
3
13
12.8019
1
1
3.21868
2
10
0
587.152
4512.92
584.85
4512.63
12.6667
6
16
20.9614
2
1
2.57494
1
7
2.49
587.005
4513.36
585.434
4513.17
5.51667
0
31
20.4128
3
1
0.965604
1
7.5
1.65
586.649
4511.73
586.672
4512.55
9.88333
1
25
13.0314
4
1
2.46229
1
7.5
1.66
586.967
4511.89
585.262
4511.76
8.68333
2
5
7.70333
5
5
1.56106
1
7.5
2.2
585.926
4512.88
585.169
4511.54
9.43333
3
20
20.6672
6
1
2.57494
1
8
1
586.731
4515.08
588.71
4514.21
7.95
5
8
23.8419
7
1
0.80467
2
5
0
585.345
4509.71
585.844
4509.55
4.95
5
29
15.8314
8
1
3.6532
1
10
1.1
585.422
4509.48
583.671
4507.74
11.0667
5
8
2.09833
9
6
1.62543
1
5.5
1.36
587.875
4514.93
587.701
4513.71
4.21667
3
13
21.7831
הבעיה: מציאת חניונים
חברת מוניות רוצה לשכור K מגרשי חניה ברחבי העיר NYC בהם יוכלו לחכות המוניות שלה בין הנסיעות.
לשם כך היא מעוניינת לבחור באופן אופטימאלי את המיקומים של מגרשי החניות האלו כך שהמרחק הממוצע מנקודת הורדת הנוסע למרגש החניה הקרוב יהיה מינימאלי.
שדות רלוונטיים
הפעם נתמקד בשתי השדות הבאים מהמדגם:
dropoff_easting - הקואורדינאטה האורכית (מזרח-מערב) של סיום הנסיעה
dropoff_northing - הקואורדינאטה הרוחבית (צפון-דרום) של סיום הנסיעה
(הקואורדינאטות נתונות בUTM-WGS84, היחידות הן בקירוב קילומטר).
ויזואליזציה של נקודות ההורדה
הגדרה פורמאלית של הבעיה
נשתמש בסימונים הבאים:
x הוקטור האקראי של מיקום סיום הנסיעה
N: מספר הנסיעות במדגם.
x(i) הוקטור של מיקום סיום הנסיעה ה i.
ck: המיקום של מגרש החניה ה k.
המטרה: למצוא את מיקומי החניונים האופטימאליים אשר ממזערים את הגודל הבא
{ck}k=1K∗={ck}k=1KargminE[kmin∥x−ck∥2]
מכיוון שהפילוג האמיתי של x לא ידוע ננסה למזער את התוחלת האמפירית:
קיבלנו דומה מאד לבעיה אותה K-Means מנסה לפתור, אם הבדל משמעותי אחד:
K-Means ממזער את המרחק הריבועי הממוצע בעוד שאנו מחפשים למזער את המרחק האוקלידי.
ישנם אלגוריתמים מורכבים יותר אשר פותרים את הבעיה שלנו, אך לבינתיים נשאר עם K-Means.
נציין שזהו מצב נפוץ שבו איננו מסוגלים לפתור בעיה מסויימת באופן ישיר אז אנו פותרים בעיה דומה לה בתקווה לקבל תוצאות מספקות, אך לא בהכרח אופטמאליות.
נשתמש באלגוריתם K-means על מנת לבחור את המיקום של 10 מגרשי חניה.
מרחק הנסיעה הממוצע המתקבל הינו:
N1k=1∑Ki∈Ik∑∥x(i)−ck∥2=700m
חשוב לציין שהפתרון הזה הוא לא בהכרח הפתרון האופטימאלי משתי סיבות:
K-Means לא מבטיח התכנסות למינימום הגלובלי.
דרך אחת לשפר את תוצאות האלגוריתם הינה להריץ אותו מספר פעמים עם איתחולים שונים.
כפי שציינו קודם K-Means ממזערת את השגיאה הריבועית הממוצעת. ניתן אם כן לשפר קלות את התוצאות על ידי שמירה על האשכולות אך תיקון המרכז לנקודה אשר ממזערת את המרחק עצמו.
הערה הנקודה אשר ממזערת את המרחק האוקלידי (בלי הריבוע) בינה לבין כל הנקודות באשכול נקראת החציון הגיאומטרי The Geometric Median (wiki). ניתן למצוא נקודה זו על ידי שימוש באלגוריתם המוכונה Weiszfeld's algorithm.
מציאת מספר החניונים האופטימאלי
עד כה השתמשנו ב10 חניונים.
נרצה כעת לבחור גם מספר זה בצורה מיטבית.
באופן כללי ככל שנגדיל את מספר החניונים מרחק הנסיעה לחניונים יקטן, אך מנגד התחזוקה של כל חניון עולה כסף.
נניח כי:
עלות האחזקה של חניון הינה 10k$ לחודש.
בכל חודש יהיו בדיוק 100k נסיעות.
עלות הנסיעה של מונית בדרך לחניון הינה 3$ לקילומטר.
נרשום תחת הנחות אלו את העלות החודשית של אחזקת החניונים והנסיעה אליהם:
10⋅K+100⋅3⋅E[kmin∥x−ck∥2]
והמקבילה האמפירית:
10⋅K+100⋅3⋅N1k=1∑Ki∈Ik∑∥x(i)−ck∥2
מספר החניונים כ Hyper parameter
כעת עלינו לבצע אופטימיזציה גם על מספר החניונים וגם המיקום שלהם. ראינו כיצד ניתן למצוא פתרון בעבור K נתון, אך אין לנו דרך פשוטה להכליל את זה ל K כלשהו.
נוכל לעבור על כל ערכי K הרלוונטים, לפתור את הבעיה עבורם ולבסוף לקחת את הפתרון הטוב ביותר.
K הוא למעשה hyper-parameter של הבעיה.
נריץ את אלגוריתם ה K-Means בעבור כל ערך של K∈[1,25], נשרטט את עלות הנסיעה, עלות אחזקת החניונים והעלות הכוללת: