הצגת המקור של הדף "אלגוריתם שכן קרוב"

{{אלגוריתם
| תמונה = KnnClassification.svg
| כיתוב = דוגמה לסיווג עבור אלגוריתם k-NN. המבחן לדוגמה (העיגול הירוק) צריך להיות מסווג או אל המחלקה הראשונה - קבוצת המרובעים הכחולים או לחלופין, אל המחלקה השנייה - קבוצת המשולשים האדומים. אם k=3 (המעגל הפנימי) הוא מוקצה לקבוצה השנייה כי ישנם 2 משולשים ורק מרובע אחד בתוך המעגל הפנימי. אם k=5 (עיגול מקווקו) הוא מסווג למחלקה הראשונה (שלושה ריבועים לעומת שני משולשים בתוך המעגל החיצוני).
| שם בשפת המקור = k nearest neighbor
| מחלקה = למידה חישובית, למידת מכונה, אלגוריתם מבוסס דוגמאות (Instance-based Learning)
| סוג = אלגוריתם חיזוי, משמש לסיווג (Classification) ורגרסיה (Regression)
| מבנה נתונים = רשימה/מערך, עץ KD (בגרסאות מותאמות)
| סיבוכיות זמן = חיפוש נאיבי: O(n)
| סיבוכיות מקום = O(n)
| ממציא = אוולין פיקס וג'וזף הודג'ס
}}

'''אלגוריתם השכן הקרוב''' או '''''k''-Nearest Neighbors algorithm''' (או בקיצור '''k-NN''') הוא אלגוריתם חסר [[פרמטר סטטיסטי|פרמטרים]] ל[[סיווג (סטטיסטיקה)|סיווג]] ול[[רגרסיה מקומית]]{{הערה|{{cite journal |last=Altman |first=N. S. |title=An introduction to kernel and nearest-neighbor nonparametric regression |journal=The American Statistician |volume=46 |issue=3 |year=1992 |pages=175–185 |doi=10.1080/00031305.1992.10475879}}}} שפותח לראשונה על ידי אוולין פיקס וג'וזף הודג'ס ב 1951<ref>{{צ-מאמר|מחבר=Fix, Evelyn; Hodges, Joseph L.|שם=Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties|שנת הוצאה=1951|קישור=https://apps.dtic.mil/dtic/tr/fulltext/u2/a800276.pdf}}</ref>. בשני המקרים הקלט תלוי ב-k התצפיות הקרובות במרחב התכונות. k-NN יכול לשמש לסיווג או לרגרסיה:
* '''k-NN לסיווג''' – בהינתן [[קלט]] של דוגמה חדשה, האלגוריתם משייכה לקבוצה. הדוגמה משויכת למחלקה הנפוצה ביותר בקרב k השכנים הקרובים (כאשר k מוגדר כמספר חיובי שלם, בדרך כלל מספר קטן). אם k=1 האובייקט משויך למחלקה של השכן הבודד הקרוב ביותר.
* '''k-NN לרגרסיה''' – בהינתן דוגמה חדשה, האלגוריתם מחזיר ערך מאפיין לדוגמה. ערך זה הוא ממוצע ערכים של ערכי k השכנים הקרובים ביותר.

k-NN הוא אלגוריתם לימוד מבוסס מופעים, או [[למידה עצלה]], שבו הפונקציה מקורבת באופן מקומי בלבד וכל החישובים נדחים עד סיווגה. אלגוריתם k-NN הוא מבין האלגוריתמים הפשוטים ביותר בתחום [[למידת מכונה|למידת המכונה]].

שקלול תרומתם של השכנים יכול להיות שימושי גם במקרה של סיווג וגם במקרה של רגרסיה, כך שמשקל השכנים הקרובים תורם יותר לממוצע מהשכנים הרחוקים יותר. לדוגמה שיטת [[שקלול]] נפוצה מורכבת כך שנותנים לכל שכן משקל של {{D}}{{הצגת שבר|d}}, כאשר d הוא המרחק לאותו שכן.{{הערה|זוהי הכללה של [[אינטרפולציה ליניארית]].}}

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

==אלגוריתם==
הקלט לשלב האימון של האלגוריתם הוא דוגמאות אימון, וקטורי תכונות ב[[מרחב (מתמטיקה)|מרחב]] רב ממדי כל אחד עם תווית סיווג (למשל <math>\mathbb{R}^d \times \{1,2\}</math> עבור וקטור תכונות של d ממדים ושתי מחלקות סיווג). שלב האימון מתבסס רק על אחסון תכונת הווקטור ותווית הסיווג של דוגמאות האימון במבנה נתונים שיאפשר בהמשך חיפוש מהיר בהם, כדוגמת [[עץ kd]].

הקלט לשלב הסיווג הוא וקטור ללא תווית (למשל <math>\mathbb{R}^d </math>). בשלב הסיווג k מוגדר כקבוע, והמסווג קובע את תווית הסיווג על פי התווית השכיחה ביותר בקרב k דוגמאות האימון הקרובות לדוגמה הנבדקת.

===מטריקת מרחק===
[[מטריקה]] מקובלת למדידת מרחק בין משתנים רציפים היא [[מרחק אוקלידי]]. עבור משתנים בדידים, כגון בבעיית [[סיווג טקסט]], ניתן להשתמש במטריקה אחרת, כגון [[מרחק המינג]]. לעיתים קרובות, דיוק הסיווג של k-NN ניתן לשיפור באופן משמעותי אם המטריקה שבשימוש נלמדת באמצעות [[אלגוריתם|אלגוריתמים]] מיוחדים כמו "Large margin nearest neighbor" או "Neighbourhood components analysis".

===מחלקות לא מאוזנות===
חיסרון משמעותי של סיווג כזה, לפי ה[[שכיח]] המקומי, הוא כאשר [[התפלגות]] המחלקות מוטה, כלומר: מספר דוגמאות האימון באחת המחלקות גדול בהרבה ממספר דוגמאות האימון במחלקות האחרות. במקרה כזה, רוב הדוגמאות החדשות יסווגו למחלקה זו, כי בשל מספרן הגדול, דוגמאות האימון ממחלקה זו נוטות להיות נפוצות בקרב k השכנים הקרובים לדוגמה החדשה.{{הערה|שם=Coomans_Massart1982|{{Cite journal
 | doi = 10.1016/S0003-2670(01)95359-0
 | author1 = D. Coomans
 | author2 = D.L. Massart
 | title = Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules
 | journal = [[Analytica Chimica Acta]]
 | volume = 136
 | issue =
 | pages = 15–27
 | year = 1982
}}
}} דרך אחת להתמודדות עם בעיה זו היא הקצאת משקל לסיווג, שייקבע לפי מרחק הדוגמה מ־k השכנים הקרובים. הסיווג (או הערך, במקרה של בעיית רגרסיה) של כל אחת מ־k הנקודות הקרובות יוכפל במשקל הפרופורציונלי להופכי של המרחק מנקודת האימון לנקודה הנוכחית. דרך אחרת כדי להתגבר על סטיות במדידה היא הפשטה בייצוג נתונים. לדוגמה, ב[[רשת קוהונן]], כל צומת מייצגת מרכז של קבוצת נקודות דומות, ללא קשר לצפיפותן בנתוני האימון המקוריים.

==בחירת פרמטרים==
הבחירה הטובה ביותר של k תלויה בנתונים; בדרך כלל, ערכים גבוהים יותר של k גורמים לצמצום ההשפעה של הרעש על סיווג,{{הערה|Everitt, B. S., Landau, S., Leese, M. and Stahl, D. (2011) Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK.}} אבל גורמים לגבולות בין מחלקות להיות פחות מובהקים. k טוב יכול להיבחר באמצעות מספר שיטות. במקרה המיוחד בו נחזתה מראש סוג המחלקה כמחלקה הקרובה ביותר לנקודות האימון (כלומר כאשר k=1) נקרא אלגוריתם השכן הקרוב ביותר.

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

בסיווג בינארי (דו-ערכי; כאשר יש שתי מחלקות), כדאי לבחור את k להיות מספר אי-זוגי כדי להימנע ממצבי תיקו. דרך אחת פופולרית לבחירת k אופטימלי באופן אמפירי למצב זה היא באמצעות שיטת אתחול {{אנ|Bootstrapping (statistics)}}.{{הערה|שם=HPS2008|{{Cite journal
 | author = Hall P, Park BU, Samworth RJ
 | title = Choice of neighbor order in nearest-neighbor classification
 | journal = [[Annals of Statistics]]
 | volume = 36
 | issue = 5
 | pages = 2135–2152
 | year = 2008
 | doi = 10.1214/07-AOS537
}}
}}

==מאפיינים==
k-NN הוא [[מקרה פרטי]] של הערכת צפיפות משתני קרנל, של הערכת רוחב פס משתנים ושל הערכת צפיפות קרנל "בלון" עם אחידות סטטיסטית בקרנל.{{הערה|שם=Terrell_Scott1992|{{Cite journal

 | doi = 10.1214/aos/1176348768
 | author1 = D. G. Terrell
 | author2 = D. W. Scott
 | title = Variable kernel density estimation
 | journal = [[Annals of Statistics]]
 | volume = 20
 | issue = 3
 | pages = 1236–1265
 | year = 1992
}}
}}{{הערה|שם=Mills2010|{{Cite journal
 | last = Mills
 | first = Peter
 | title = Efficient statistical classification of satellite measurements
 | date = 2012-08-09
 | url = https://archive.org/details/arxiv-1202.2194
 | journal = International Journal of Remote Sensing
}}
}}

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

כאשר מספר הדוגמאות [[אינסוף|שואף לאינסוף]], לאלגוריתם מובטח שיעור שגיאה מרבי לא יותר מפעמיים [[שיעור השגיאה של בייס]] (השגיאה המינימלית הניתן להשגה בהתחשב בהתפלגות הנתונים).{{הערה|{{cite journal |doi=10.1109/TIT.1967.1053964 |author=[[Thomas M. Cover|Cover TM]], [[פיטר הארט|Hart PE]] |title=Nearest neighbor pattern classification |journal=IEEE Transactions on Information Theory |year=1967 |volume=13 |issue=1 |pages=21–27}}}}

==הפחתת ממדים==
עבור נתונים רב־ממדיים (לדוגמה, אם מספר ממדים גדול מ־10), הפחתת ממדים מבוצעת בדרך כלל לפני הפעלת k-NN על הנתונים, כדי למנוע את ההשפעות של [[קללת הממד]] (Curse of dimensionality).{{כ}}{{הערה|Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful? Database Theory—ICDT’99, 217-235{{!}}year 1999}}

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

ניתן לשלב בפעולה אחת חילוץ תכונות והורדת ממד באמצעות שיטות [[ניתוח גורמים ראשיים]] (PCA), ניתוח הבחנה ליניארי (LDA) או ניתוח [[מתאם]] קנוני (CCA) כשלב טרום עיבודי, ולאחר מכן יצירת אשכולות על ידי k-NN ב[[שיכון (מתמטיקה)|שיכון]] במרחב בממד נמוך יותר (embedding).{{הערה|Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009}} [[הורדת ממד]] יכולה להיעשות גם באמצעות הורדת ממד אקראית.

== גבול ההחלטה ==
כללי השכן הקרוב ביותר למעשה מחשבים במרומז את גבול ההחלטה. כמו כן ניתן לחשב את גבול ההחלטה באופן מפורש, כדי לעשות זאת באופן יעיל כך שמורכבות החישוביות היא פונקציה של מורכבות הגבול.{{הערה|{{cite journal |doi=10.1007/s00454-004-1152-0 |author=Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G |title=Output-sensitive algorithms for computing nearest-neighbor decision boundaries |journal=Discrete and Computational Geometry |volume=33 |issue=4 |year=2005 |pages=593–604}}}}

== צמצום נתונים ==
צמצום נתונים היא אחת הבעיות החשובות ביותר בבעיות עם מספר דוגמאות רב. בדרך כלל, לסיווג מדויק דרושות רק כמה נקודות, או "אבות טיפוס" וניתן למצוא אותן כך:
# בחירת "Class-outliers", כלומר, דוגמאות שסווגו לא נכון על ידי k-NN עבור k נתון.
# יש להפריד את שאר הנתונים לתוך שתי קבוצות: (א) אבות הטיפוס המשמשים לסיווג (ב) "הנקודות הנבלעות"- נקודות ש־k-NN יכול לתקן את סיווגן באמצעות אבות הטיפוס, ונקודות אלו ניתן להסיר ממדגם האימון.

=== בחירה של Class-outliers ===
דוגמאות האימון המוקפות בדוגמאות של מחלקות אחרות נקראות Class outlier. הגורמים של Class outliers כוללים:
* שגיאה אקראית
* לא מספיק דוגמאות אימון במחלקה זו (קיימת דוגמה בודדת במקום מקבץ דוגמאות)
* חוסר בתכונות חשובות (המחלקות מופרדות בממדים שונים לא ידועים)
* ריבוי דוגמאות ממחלקות אחרות (מחלקות לא מאוזנות) אשר יוצרות רקע עוין למחלקה הקטנה

בשילוב עם k-NN מייצר רעשים. הרעשים יכולים להיות מזוהים ומופרדים לצורך ניתוח עתידי. בהינתן שני [[מספר טבעי|מספרים טבעיים]], k>r>0, דוגמת אימון נקראת k,r-NN class-outlier, אם k שכנים קרובים כוללים יותר מ־r דוגמאות של מחלקות אחרות.

=== CNN עבור צמצום כמות הנתונים===
אלגוריתם ממוקד לשכן הקרוב ביותר (Condensed Nearest Neighbor, CNN, מכונה גם אלגוריתם [[פיטר הארט|הארט]]) הוא אלגוריתם שנועד לצמצם את מספר הדוגמאות לסיווג k-NN.{{כ}}{{הערה|P. E. Hart, The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory 18 (1968) 515–516. doi: 10.1109/TIT.1968.1054155}} אלגוריתם זה בוחר את אבות הטיפוס U מתוך דוגמאות האימון, כך ש־1NN יכול לסווג את U כמעט במדויק, כפי ש־1NN מסווג את כל הנתונים.

CNN עובד באופן [[איטרציה|איטרטיבי]], בהינתן מדגם אימון:
# סרוק את כל האיברים ב־X, וחפש רכיב x שיש לו תווית שונה מאב הטיפוס הקרוב אליו (מקרב U).
# הסר את x מ־X, והוסף אותו ל־U.
# סרוק שוב, עד שלא יתווספו עוד אבות טיפוס ל־U.

השתמש ב־U במקום ב־X לשם הסיווג. הדוגמאות שאינן אבות טיפוס נקראות נקודות בלועות.

====יחס הגבול====
[[קובץ:BorderRAtio.PNG|ממוזער|130px|חישוב יחס הגבול.]]
לשם שיפור יעילות הסריקה של CNN, נגדיר את יחס הגבול לדוגמת אימון x:
<math>a\left(x\right)=\frac{\lVert x'-y \rVert}{\lVert x-y \rVert}</math>

כאשר ||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){{D}} הוא תכונה של נקודת הפתיחה x.

בעזרת יחס הגבול, ניתן לייעל את סריקת דגימות האימון ב-CNN, אם הסריקה מבוצעת בסדר יורד של a(x){{D}}{{כ}}.{{הערה|שם=MirkesKnn|E. M. Mirkes, [http://www.math.le.ac.uk/people/ag153/homepage/KNN/KNN3.html KNN and Potential Energy: applet.] University of Leicester, 2011.}}

====דוגמה====
[[קובץ:PointsTypes.png|ממוזער|130px|שלושה סוגים של נקודות: Class-outliers, אבות טיפוס ונקודות בלועות.]]
להלן המחשה של CNN על קבוצת דוגמאות אימון המחולקות לשלוש מחלקות: אדום, ירוק וכחול. איור 1 מראה את המצב ההתחלתי, שבו יש 60 נקודות בכל מחלקה. איור 2 מציג את מפת הסיווג 1NN: כל [[פיקסל]] מסווג על ידי 1NN באמצעות כל הנתונים. איור 3 מציג את מפת הסיווג 5NN. אזורים לבנים תואמים את האזורים הלא מסווגים, שבהם היה תיקו בין מחלקות (למשל, אם יש שתי נקודות ירוקות, שתי נקודות אדומות ונקודה אחת כחולה מקרב חמשת השכנים הקרובים ביותר). איור 4 מציג את מקבץ הדוגמאות המצומצם. ה-x-ים הם Class-outliers שנבחרו על ידי כלל {{D}}(3,2)NN{{כ}} (כל שלושת השכנים הקרובים ביותר של מקרים אלה שייכים למחלקות אחרות); הריבועים הם אבות־הטיפוס, והעיגולים הריקים הם הנקודות הבלועות. בצד שמאל למטה מוצגים מספרי ה־class-outlier, אבות־הטיפוס והנקודות הבלועות לכל אחת משלוש המחלקות. מספר אבות־הטיפוס נע בין 15% ל־20% עבור מחלקות שונות בדוגמה זו. איור 5 מראה שמפת הסיווג 1NN עם אבות־הטיפוס דומה מאוד למפה עם הנתונים הראשוניים. האיורים נוצרו בעזרת היישומון של מירקס.{{הערה|שם=MirkesKnn}}

<gallery caption="צמצום CNN עבור k-NN לסיווג" widths="200px">
File:Data3classes.png|איור 1. דוגמאות האימון.

File:Map1NN.png|איור 2. מפת סיווג 1NN.

File:Map5NN.png|איור 3. מפת סיווג 5NN.

File:ReducedDataSet.png|איור 4. דוגמאות האימון, לאחר צמצום CNN.

File:Map1NNReducedDataSet.png|איור 5. מפת סיווג 1NN, על בסיס אבות הטיפוס שנבחרו על ידי CNN.

</gallery>

== k-NN לרגרסיה ==
אלגוריתם K-NN משמש להערכת משתנים רציפים. אלגוריתם לדוגמה עשוי להשתמש בממוצע משוקלל של K השכנים הקרובים ביותר, משוקללים לפי ה[[מספר הופכי|הופכי]] של מרחקם. אלגוריתם זה פועל כדלהלן:

# חשב את המרחק האוקלידי או [[מרחק מהלנוביס]] (Mahalanobis) מהנקודה הנבדקת לנקודות האימון המתויגות.
# סדר את הנקודות המתויגות לפי מרחק עולה.
# מצא k אופטימלי לאלגוריתם, על סמך שורש [[טעות ריבועית ממוצעת|הטעות הריבועית הממוצעת]]. נעשה באמצעות אימות צולב.
# חשב [[ממוצע משוקלל]] לפי המרחק ה[[מספר הופכי|הופכי]] מ־k שכנים קרובים.

==לקריאה נוספת==
<div class="mw-content-ltr">
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1422 When Is "Nearest Neighbor" Meaningful?]
* {{cite book |editor=Belur V. Dasarathy |year=1991 |title=Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques |isbn=0-8186-8930-7}}
* {{cite book |title=Nearest-Neighbor Methods in Learning and Vision |editor=Shakhnarovish, Darrell, and Indyk |publisher=[[MIT Press]] |year=2005 |isbn=0-262-19547-X}}
* {{cite journal |doi=10.1016/j.foreco.2004.02.049 |author=Mäkelä H Pekkarinen A |title=Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data |journal=[[Forest Ecology and Management]] |volume=196 |issue=2–3 |date=2004-07-26 |pages=245–255}}
* Fast k nearest neighbor search using [[GPU]]. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
* [http://www.scholarpedia.org/article/K-nearest_neighbor Scholarpedia article on ''k''-NN]
* [https://code.google.com/p/google-all-pairs-similarity-search/ google-all-pairs-similarity-search]
</div>

==קישורים חיצוניים==
* [https://www.youtube.com/watch?v=zenh6DahgZU אלגוריתם השכן הקרוב], בקורס מבוא למערכות לומדות באוניברסיטה העברית {{וידאו}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{בינה מלאכותית}}

[[קטגוריה:אלגוריתמי חיפוש|שכן קרוב]]
[[קטגוריה:סיווג (סטטיסטיקה)]]
[[קטגוריה:אלגוריתמי למידת מכונה|שכן קרוב]]