מבוא ל-KNN

שיעור 6 מתוך 19 בקורס מבוא ללמידת מכונה של Coddy.

‏K-Nearest Neighbors (KNN) הוא אלגוריתם למידה מונחית שמשמש לבעיות סיווג ורגרסיה. הוא פשוט אך רב־עוצמה, ומשמש לעיתים קרובות כמודל בסיס להשוואה למודלים מורכבים יותר.

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

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

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

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

בחנו את עצמכם

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

בחנו את עצמכם

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

בחנו את עצמכם

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

אתגר

קל

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

צרו פונקציה בשם distances_option_calculator שמקבלת שלושה משתנים: X, y ו-distance_type. הפונקציה תחזיר את המרחק בין X ל-y בהתאם ל-distance_type.

הנה רשימה של חישובי מרחק נפוצים:

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

מרחק Manhattan ידוע גם כמרחק Taxicab או מרחק City Block. סכום ההפרשים המוחלטים בין הנקודות בכל הממדים. עבור שתי נקודות ( P ) ו-( Q ), בעלות הקואורדינטות ( (p_1, p_2, …, p_n) ) ו-( (q_1, q_2, …, q_n) ) בהתאמה:

מרחק Hamming: מספר המיקומים שבהם הסמלים התואמים שונים. משתמשים בו לעיתים קרובות עבור נתונים קטגוריים.
לדוגמה, ניקח שתי מחרוזות בינאריות:

String 1: 1101
String 2: 1001

כשמשווים ביניהן מיקום אחר מיקום, רואים שבמיקום השני הביטים שונים (1 ב-String 1 ו-0 ב-String 2). כל שאר המיקומים זהים. לכן, מרחק Hamming בין שתי המחרוזות האלה הוא 1.

ה-distance_type יכול לקבל את הערכים הבאים: hamming, manhattan, euclidian.

נסו בעצמכם

def distances_option_calculator(X, y, distance_type):
    # כתבו כאן את הקוד
    if distance_type == "euclidian":
        pass
    elif distance_type == "manhattan":
        pass
    elif distance_type == "hamming":
        pass