II. מסווג השכן הקרוב ביותר

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

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

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

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

מה אנחנו מתכוונים כשאנחנו אומרים “הקרוב ביותר”?

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

הערה

הגדרת “הקרוב ביותר”

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

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

שימוש בשיטה של השכן הקרוב ביותר כדי לחזות התנהגות משתמשים

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

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

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

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

התרגיל הבא ידגים את הרעיון הזה.

פה יבוא תרגיל 🙂

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

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

תרגיל נוסף??