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

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

שיטת ההתאמה בין חובבי סרטי האקשן תשתמש בפרמטרים השונים שהזין המשתמש, ובפרט תסתמך על השוני ביניהם - כלומר עד כמה הם קרובים או רחוקים זה מזה בכל פרמטר (כמו במדידת מרחק בין מקומות במפה). חישוב זה יכול להיעזר במרחק אוקלידי [1]. מרחק אוקלידי הוא אורך הקטע שבין שתי נקודות במרחב, והוא נמדד בעזרת השורש של סכום המרחק הריבועי בין ערכי הנקודות בכל ציר. למען הפשטות, נחשוב על שני פרמטרים: הנאה מהעלילה ודירוג הביצוע של ארנולד בסרט. משתמש מסוים מדרג את העלילה 5/5, אבל נותן רק 3/5 לביצוע של ארנולד, בעוד משתמש שני טוען שארנולד היה רק 2/5 אבל העלילה 4/5. את ההתאמה בין המשתמשים אפשר לחשב בעזרת משפט פיתגורס, ולמצוא את המרחק בין נקודות המידע השונות (5, 3) ו-(4, 2). תוצאת חישוב זה היא שורש 2, וזהו המרחק שבין שני משתמשי האפליקציה מבחינת העדפות הפרמטרים הנתונים.

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

השימושים באלגוריתם KNN מגוונים והוא נחשב לאחד האלגוריתמים הפשוטים ביותר בלמידת מכונה [2]. אלגוריתם זה יכול לשמש לסיווג נתונים או לביצוע ניבוי (רגרסיה).

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

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

אפשר למצוא דוגמאות נוספות לשימוש באלגוריתם KNN באפליקציות זיהוי פנים (זיהוי הפנים הדומות ביותר מתוך מאגר תמונות) [3], במערכות המלצה (אנשים דומים לך בחרו לראות את הסרט הזה, אולי גם לך הוא יתאים) [4], בבניית קהילות (יש לך 65 חברים משותפים ותחביבים דומים לפלונית המדענית, אולי אתם מכירים?) וכו'. אלגוריתם זה נמצא בשימוש נרחב בשל פשטותו בביצוע פעולות מורכבות אך יחד עם זאת, חיסרון בולט שלו הוא זמן הריצה. עבור כל חיפוש שכנים קרובים יש צורך בחישוב המרחק לכל נקודה במבנה הנתונים, ועבור מבנה גדול במיוחד זמן החישוב ייקח זמן רב. 

תיארנו בפוסט זה אלגוריתם בסיסי בלמידת מכונה אשר לו שימושים רבים בסיווג מידע חדש על סמך מידע קיים והמרחק ביניהם [5, 6]. בשלב זה נציע להוגי השיטה - אנא שקלו להחליף את שם השיטה מ-K השכנים הקרובים ביותר ל-K החברים הקרובים ביותר. שינוי זה יגרום לכך ששם השיטה יהיה K Best Buddies, או בקיצור - קבב. 

עריכה: שיר רוזנבלום-מן

מקורות לקריאה נוספת:

[1] הסבר על מרחק אוקלידי ומרחק מנהטן

[2] סרטון הסבר על שיטת KNN מתוך StatQuest

[3] זיהוי פנים בעזרת KNN

[4] המלצה על סרטים בעזרת KNN

[5] פוסט בנושא אלגוריתם K-means

[6] השוואה בין אלגוריתם KNN ובין K-means