חיסרון משמעותי של סיווג כזה, לפי השכיח המקומי, הוא כאשר התפלגות המחלקות מוטה, כלומר: מספר דוגמאות האימון באחת המחלקות גדול בהרבה ממספר דוגמאות האימון במחלקות האחרות. במקרה כזה, רוב הדוגמאות החדשות יסווגו למחלקה זו, כי בשל מספרן הגדול, דוגמאות האימון ממחלקה זו נוטות להיות נפוצות בקרב k השכנים הקרובים לדוגמה החדשה. דרך אחת להתמודדות עם בעיה זו היא הקצאת משקל לסיווג, שייקבע לפי מרחק הדוגמה מ־k השכנים הקרובים. הסיווג (או הערך, במקרה של בעיית רגרסיה) של כל אחת מ־k הנקודות הקרובות יוכפל במשקל הפרופורציונלי להופכי של המרחק מנקודת האימון לנקודה הנוכחית. דרך אחרת כדי להתגבר על סטיות במדידה היא הפשטה בייצוג נתונים. לדוגמה, ברשת קוהונן, כל צומת מייצגת מרכז של קבוצת נקודות דומות, ללא קשר לצפיפותן בנתוני האימון המקוריים.
בחירת פרמטרים.
הבחירה הטובה ביותר של k תלויה בנתונים; בדרך כלל, ערכים גבוהים יותר של k גורמים לצמצום ההשפעה של הרעש על סיווג, אבל גורמים לגבולות בין מחלקות להיות פחות מובהקים. k טוב יכול להיבחר באמצעות מספר שיטות. במקרה המיוחד בו נחזתה מראש סוג המחלקה כמחלקה הקרובה ביותר לנקודות האימון (כלומר כאשר k=1) נקרא אלגוריתם השכן הקרוב ביותר.
הדיוק של אלגוריתם k-NN יכול להיפגע קשות על ידי נוכחות של רעש או תכונות לא רלוונטיות, או אם סקלת התכונה אינה עקבית עם חשיבותה. מאמצי מחקר רבים הושקעו עבור בחירת תכונות או דירוג תכונות לשיפור סיווגם.
בסיווג בינארי (דו-ערכי; כאשר יש שתי מחלקות), כדאי לבחור את k להיות מספר אי-זוגי כדי להימנע ממצבי תיקו. דרך אחת פופולרית לבחירת k אופטימלי באופן אמפירי למצב זה היא באמצעות שיטת אתחול .
מאפיינים.
k-NN הוא מקרה פרטי של הערכת צפיפות משתני קרנל, של הערכת רוחב פס משתנים ושל הערכת צפיפות קרנל "בלון" עם אחידות סטטיסטית בקרנל.
בצורתו הפשוטה של האלגוריתם הוא נדרש לחשב המרחקים בין הדוגמה לסיווג לכל דוגמאות האימון, אך גישה נאיבית כזו דורשת חישובים רבים כאשר יש דוגמאות אימון רבות. עם זאת שימוש באלגוריתם יעיל לחיפוש שכן קרוב מאפשר להשתמש ב־k-NN גם עבור דוגמאות רבות. במהלך השנים הוצעו מספר רב של אלגוריתמי חיפוש לשכן הקרוב; בכלל ניסו אלגוריתמים אלה לצמצם את מספר הערכות המרחק שמבוצעות בפועל.
כאשר מספר הדוגמאות שואף לאינסוף, לאלגוריתם מובטח שיעור שגיאה מרבי לא יותר מפעמיים שיעור השגיאה של בייס (השגיאה המינימלית הניתן להשגה בהתחשב בהתפלגות הנתונים).
הפחתת ממדים.
עבור נתונים רב־ממדיים (לדוגמה, אם מספר ממדים גדול מ־10), הפחתת ממדים מבוצעת בדרך כלל לפני הפעלת k-NN על הנתונים, כדי למנוע את ההשפעות של קללת הממד (Curse of dimensionality).
משמעותה של קללת הממד, בהקשר של k-NN, היא שהמרחק האוקלידי אינו מדד יעיל למרחק במרחב מממד גבוה, כיוון שכל הווקטורים הם שווי מרחק ביחס לווקטור הנבדק (דמיינו מספר נקודות מונחות פחות או יותר על עיגול שלם עם נקודת שאילתה במרכז; המרחק בין נקודות השאילתה לכל נקודות המידע הוא כמעט זהה).
ניתן לשלב בפעולה אחת חילוץ תכונות והורדת ממד באמצעות שיטות ניתוח גורמים ראשיים (PCA), ניתוח הבחנה ליניארי (LDA) או ניתוח מתאם קנוני (CCA) כשלב טרום עיבודי, ולאחר מכן יצירת אשכולות על ידי k-NN בשיכון במרחב בממד נמוך יותר (embedding). הורדת ממד יכולה להיעשות גם באמצעות הורדת ממד אקראית.
גבול ההחלטה.
כללי השכן הקרוב ביותר למעשה מחשבים במרומז את גבול ההחלטה. כמו כן ניתן לחשב את גבול ההחלטה באופן מפורש, כדי לעשות זאת באופן יעיל כך שמורכבות החישוביות היא פונקציה של מורכבות הגבול.
צמצום נתונים.
צמצום נתונים היא אחת הבעיות החשובות ביותר בבעיות עם מספר דוגמאות רב. בדרך כלל, לסיווג מדויק דרושות רק כמה נקודות, או "אבות טיפוס" וניתן למצוא אותן כך:
בחירה של Class-outliers.
דוגמאות האימון המוקפות בדוגמאות של מחלקות אחרות נקראות Class outlier. הגורמים של Class outliers כוללים:
בשילוב עם k-NN מייצר רעשים. הרעשים יכולים להיות מזוהים ומופרדים לצורך ניתוח עתידי. בהינתן שני מספרים טבעיים, k&gt;r&gt;0, דוגמת אימון נקראת k,r-NN class-outlier, אם k שכנים קרובים כוללים יותר מ־r דוגמאות של מחלקות אחרות.
CNN עבור צמצום כמות הנתונים.
אלגוריתם ממוקד לשכן הקרוב ביותר (Condensed Nearest Neighbor, CNN, מכונה גם אלגוריתם הארט) הוא אלגוריתם שנועד לצמצם את מספר הדוגמאות לסיווג k-NN. אלגוריתם זה בוחר את אבות הטיפוס U מתוך דוגמאות האימון, כך ש־1NN יכול לסווג את U כמעט במדויק, כפי ש־1NN מסווג את כל הנתונים.
CNN עובד באופן איטרטיבי, בהינתן מדגם אימון:
השתמש ב־U במקום ב־X לשם הסיווג. הדוגמאות שאינן אבות טיפוס נקראות נקודות בלועות.
יחס הגבול.
לשם שיפור יעילות הסריקה של CNN, נגדיר את יחס הגבול לדוגמת אימון x:
formula_3
כאשר ||x-y|| הוא המרחק הקרוב ביותר לדוגמה y בעלת תווית שונה מאשר x, והמרחק ||x'-y|| הוא המרחק בין y לדוגמה הקרובה ביותר אליה 'x, המסווגת כמו x.יחס הגבול הוא בין 0 ל־1, היות שערכו של ||x'-y|| לעולם אינו גדול יותר מערכו של ||x-y||. סדר זה מעניק עדיפות לגבולות המחלקות לשם הכללתם בקבוצת אבות-הטיפוס U. נקודה בעלת תווית שונה מאשר x נקראת נקודה חיצונית ל־x. חישוב יחס הגבול מודגם באיור משמאל. הנתונים מסומנים בצבעים: נקודת הפתיחה היא x, והיא מסומנת באדום. הנקודות החיצוניות הן כחולות וירוקות. הנקודה החיצונית הקרובה ביותר ל־x היא הנקודה y. הנקודה האדומה הקרובה ביותר ל־y היא הנקודה 'x. יחס הגבול a(X) הוא תכונה של נקודת הפתיחה x.
בעזרת יחס הגבול, ניתן לייעל את סריקת דגימות האימון ב-CNN, אם הסריקה מבוצעת בסדר יורד של a(x).
דוגמה.
להלן המחשה של CNN על קבוצת דוגמאות אימון המחולקות לשלוש מחלקות: אדום, ירוק וכחול. איור 1 מראה את המצב ההתחלתי, שבו יש 60 נקודות בכל מחלקה. איור 2 מציג את מפת הסיווג 1NN: כל פיקסל מסווג על ידי 1NN באמצעות כל הנתונים. איור 3 מציג את מפת הסיווג 5NN. אזורים לבנים תואמים את האזורים הלא מסווגים, שבהם היה תיקו בין מחלקות (למשל, אם יש שתי נקודות ירוקות, שתי נקודות אדומות ונקודה אחת כחולה מקרב חמשת השכנים הקרובים ביותר). איור 4 מציג את מקבץ הדוגמאות המצומצם. ה-x-ים הם Class-outliers שנבחרו על ידי כלל (3,2)NN (כל שלושת השכנים הקרובים ביותר של מקרים אלה שייכים למחלקות אחרות); הריבועים הם אבות־הטיפוס, והעיגולים הריקים הם הנקודות הבלועות. בצד שמאל למטה מוצגים מספרי ה־class-outlier, אבות־הטיפוס והנקודות הבלועות לכל אחת משלוש המחלקות. מספר אבות־הטיפוס נע בין 15% ל־20% עבור מחלקות שונות בדוגמה זו. איור 5 מראה שמפת הסיווג 1NN עם אבות־הטיפוס דומה מאוד למפה עם הנתונים הראשוניים. האיורים נוצרו בעזרת היישומון של מירקס.
k-NN לרגרסיה.
אלגוריתם K-NN משמש להערכת משתנים רציפים. אלגוריתם לדוגמה עשוי להשתמש בממוצע משוקלל של K השכנים הקרובים ביותר, משוקללים לפי ההופכי של מרחקם. אלגוריתם זה פועל כדלהלן:
ידית הסתערות
דרייס מרטנס
דיקנית
אנרי אבולקר
אנרי אבולקר (בצרפתית: Henri Aboulker; 18 ביוני 1876 - 19 בספטמבר 1957) היה פרופסור לרפואה ופוליטיקאי יהודי-אלג'יראי. כיהן כנשיא השלוחה האלג'יראית של "המפלגה הרדיקלית" הצרפתית, כסגן ראש עיריית אלג'יר ועמד בראש "הפדרציה הציונית של אלג'יריה" במשך כשלושה עשורים. קיבל את מדליית ההתנגדות על פעילותו במהלך מלחמת העולם השנייה.
קורות חיים.
אנרי אבולקר נולד באלג'יר בשנת 1876, למשפחה יהודית-אלג'יראית מיוחסת. סבו היה ר' שמואל אבולקר, רב ודיין, שילדיו היו מהיהודים האלג'יראים הראשונים שלמדו רפואה בצרפת. ר' שמואל אבולקר עלה לארץ ישראל בשנת 1890 ונפטר לאחר מספר שנים, בעוד אנרי המשיך במסורת הוריו ונסע ללימודי רפואה בפריז. הוא השלים את הדיסרטציה שלו ברפואה בשנת 1899. מאוחר יותר, בשנת 1927, הוא ביקר בארץ ישראל ואיתר את קבר סבו בהר הזיתים (שנהרס מאוחר יותר על ידי הירדנים).
בשנת 1908 נישא לברת בנישו, סופרת ומשוררת, מראשונות הסופרות שפרסמו את יצירותיהן באלג'יריה. לבני הזוג היו שלושה ילדים: קולט, מרסל וז'וזה אבולקר. בת רביעית נפטרה בילדות.
בזמן מלחמת העולם הראשונה גויס לצבא צרפת כרופא ואף נפצע בקרב, פציעה שליוותה אותו בהמשך חייו. על תפקודו במלחמה קיבל את אות לגיון הכבוד. בשנת 1915 היה ממייסדי "הוועד האלג'יראי למחקרים חברתיים" (Comité Algérien d'Études Sociales; 1915-1921), שנועד לחקור את הסיבות לאנטישמיות באלג'יריה הצרפתית וכיצד ניתן להילחם בה. הארגון הדגיש את נאמנותם של היהודים לצרפת והתרומה של היהודים למאבק המלחמתי במלחמת העולם הראשונה וכך ניסה לשלול את התעמולה האנטישמית שהציגה את היהודים בתור גורם לא-נאמן. אחד ההישגים של הארגון היה לשכנע את הסתדרות הסטודנטים האלג'יראית הכללית לבטל את האיסור על הצטרפות חברים יהודים.
מבחינה פוליטית אבולקר היה חבר במפלגה הרדיקלית, מפלגת מרכז ליברלית צרפתית ותיקה, וכיהן לתקופה כנשיא השלוחה המקומית שלה.
אבולקר היה הנציג האלג'יראי של העיתון הציוני ל'אווניר אילוסטרה שיצא לאור בקזבלנקה, והיה האחראי להפצתו באלג'יריה ופעל במישורים ציבוריים נוספים למען הציונות וגיוס כספים לקרן היסוד. הוא היה היושב ראש של "הפדרציה הציונית של אלג'יריה" למשך למעלה משלושה עשורים (1925-1957), עד פטירתו.