אלגוריתם שכן קרוב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לסיווג עבור אלגוריתם K-NN. המבחן לדוגמה (עיגול ירוק) צריך להיות מסווג או אל מדרגה ראשונה של מרובע כחול או ברמה השנייה של אדום משולש. אם K = 3 (עיגול מקו אחיד) הוא מוקצה לרמה השנייה כי ישנם 2 משולשים ורק מרובע אחד בתוך המעגל הפנימי.אם "K = 5" (עיגול מקו מקווקו) הוא מוקצה לרמה הראשונה (שלושה ריבועים לעומת שני משולשים בתוך המעגל החיצוני).

אלגוריתם השכן הקרוב או K-Nearest Neighbors algorithm (או בקיצור K-NN) הוא אלגוריתם חסר פרמטרים לסיווג ולרגרסיה מקומית.[1] בשני המקרים הקלט תלוי ב-k התצפיות הקרובות במרחב התכונות (פיצ'רים). שימוש ב-K-NN יכול להיעשות לסיווג או לרגרסיה:

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

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

שקלול תרומתם של השכנים יכול להיות שימושי גם במקרה של סיווג וגם במקרה של רגרסיה, כך שמשקל השכנים הקרובים תורם יותר לממוצע מהשכנים הרחוקים יותר. לדוגמה שיטת שקילה נפוצה מורכבת כך שנותנים לכל שכן משקל של 1/d, כאשר d הינו המרחק לאותו שכן.[2]

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

חסרון של אלגוריתם "K-NN" הוא שהוא רגיש למבנה המקומי של הנתונים.

אלגוריתם[עריכת קוד מקור | עריכה]

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

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

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

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

בחירת פרמטרים[עריכת קוד מקור | עריכה]

הבחירה הטובה ביותר של "K" תלויה בנתונים; בדרך כלל, ערכים גבוהים יותר של "K" גורמים לצמצום ההשפעה של הרעש על סיווג,[4] אבל גורמים לגבולות בין מחלקות להיות פחות מובהקים.”K” טוב יכול להיבחר באמצעות מספר שיטות. במקרה המיוחד בו נחזתה מראש סוג המחלקה כמחלקה הקרובה ביותר לנקודות האימון (כלומר כאשר K=1) נקרא אלגוריתם השכן הקרוב ביותר.

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

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

מאפיינים[עריכת קוד מקור | עריכה]

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

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

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

הורדת ממד[עריכת קוד מקור | עריכה]

עבור נתונים רב ממדים (לדוגמה, עם מספר ממדים יותר מ 10) הורדת ממדים מבוצעות בדרך כלל לפני החלת אלגוריתם "k" -NN כדי למנוע את ההשפעות של קללת הממד (Curse of dimensionality). [9]

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

ניתן לשלב בפעולה אחת חילוץ תכונות והורדת ממד באמצעות שיטות ניתוח גורמים ראשיים (PCA), ניתוח הבחנה לינארי (LDA) או ניתוח מתאם קנוני (CCA) כשלב טרום עיבודי, ולאחר מכן יצירת אשכולות על ידי "k" -NN במרחב בממד נמוך יותר. embedding.[10] הורדת ממד יכולה להיעשות גם באמצעות הורדת ממד אקראית.

גבול ההחלטה[עריכת קוד מקור | עריכה]

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

הפחתת נתונים[עריכת קוד מקור | עריכה]

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

  1. בחירת "Class-outliers", כלומר, דוגמאות שסווגו לא נכון על ידי K-NN עבור K נתון.
  2. יש להפריד את שאר הנתונים לתוך שתי קבוצות: (i) אבות הטיפוס המשמשים לסיווג (ii) "הנקודות הנבלעות"- נקודות ש 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) השכן הקרוב ביותר מרוכז (CNN, the Hart algorithm) הוא אלגוריתם שנועד להפחית את דוגמאות "k" -NN סיווג.[12] הוא בוחר את אבות הטיפוס "U" מתוך דוגמאות האימון, כך ש 1NN עם "U" ניתן לסווג את דוגמאות כמעט במדויק כפי ש 1NN עושה עם כל הנתונים.

חישוב יחס של הגבול.
שלושה סוגים של נקודות: Class-outliers, אבות טיפוס ונקודות נבלעות.

CNN עובד באופן איטרטיבי בהינתן מדגם אימון:

  1. סורק את כל האלמנטים של "X", מחפש רכיב "x" שלאב הטיפוס הקרוב אליו מקרב "U" יש תווית שונה מ “x”.
  2. הסר "x" מתוך "X" ולהוסיף אותו ל "U"
  3. חזור על סריקה עד אשר לא מתווספים יותר אבות טיפוס ל "U".

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

הוא יעיל כדי לסרוק את דוגמאות האימון על מנת להקטין את יחס הגבול.[13] יחס הגבול של דוגמאות האימון "x" מוגדר כ:

a(x) = ||x'-y|| / ||x-y||

כאשר || "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'-y||/||x-y|| היא התכונה הראשונית של נקודת "x".

להלן איור של CNN בסדרה של תבניות. ישנן שלוש מחלקות תבנית 1 (אדום, ירוק וכחול): בתחילה יש 60 נקודות בכל מחלקה. תבנית 2- מראה את מפת הסיווג 1NN: כל פיקסל מסווג על ידי 1NN באמצעות כל הנתונים. תבנית 3- מציגה את מפת הסיווג 5NN. אזורים לבנים תואמים את האזורים הלא מסווגים, בעת שהצבעת 5NN קשורה (למשל, אם יש שתי נקודות ירוקות, שתי נקודות אדומות ונקודה אחת כחולה מקרב חמשת השכנים הקרובים ביותר). תבנית 4- מציגה את צמצום מערך נתונים. הקווים החוצים הינם ה Class-outliers שנבחרו על ידי כלל (3,2)NN (כל שלושת השכנים הקרובים ביותר של מקרים אלה שייכים למחלקות אחרות); הריבועים הם אבי הטיפוס, והעיגולים הריקים הם הנקודות הנבלעות. צד שמאל מטה מציג את מספר ה class-outlier אבי הטיפוס והנקודות הנבלעות לכל שלוש המחלקות. מספר אבי הטיפוס משתנה בין 15% עד 20% עבור מחלקות שונות בדוגמה זו. תבנית 5- מראה שמפת הסיווג 1NN עם אבי הטיפוס דומה מאוד למפה עם הנתונים הראשוניים. The figures were produced using the Mirkes applet.[13]

K-NN רגרסיה[עריכת קוד מקור | עריכה]

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

  1. חישוב המרחק האוקלידי או מרחק מהלנוביס (Mahalanobis) מנקודת האימון לנקודות האימון המתויגות.
  2. סדר את הבדיקות המתויגות בסדר לפי מרחק עולה.
  3. מצא מספר K אופטימלי שעוזר לגילוי מתוך השכנים הקרובים ביותר, על סמך RMSE. נעשה באמצעות אימות צולב.
  4. חישוב פונקציה הפוכה של מרחק ממוצע משוקלל עם "k" – שכנים קרובים רב משתנים.

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Altman, N. S. (1992). "An introduction to kernel and nearest-neighbor nonparametric regression". The American Statistician 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. 
  2. ^ This scheme is a generalization of linear interpolation.
  3. ^ D. Coomans; D.L. Massart (1982). "Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules". Analytica Chimica Acta 136: 15–27. doi:10.1016/S0003-2670(01)95359-0. 
  4. ^ 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.
  5. ^ Hall P, Park BU, Samworth RJ (2008). "Choice of neighbor order in nearest-neighbor classification". Annals of Statistics 36 (5): 2135–2152. doi:10.1214/07-AOS537. 
  6. ^ D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation". Annals of Statistics 20 (3): 1236–1265. doi:10.1214/aos/1176348768. 
  7. ^ Mills, Peter. "Efficient statistical classification of satellite measurements". International Journal of Remote Sensing. 
  8. ^ Cover TM, Hart PE (1967). "Nearest neighbor pattern classification". IEEE Transactions on Information Theory 13 (1): 21–27. doi:10.1109/TIT.1967.1053964. 
  9. ^ Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful?. Database Theory—ICDT’99, 217-235|year 1999
  10. ^ Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009
  11. ^ Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). "Output-sensitive algorithms for computing nearest-neighbor decision boundaries". Discrete and Computational Geometry 33 (4): 593–604. doi:10.1007/s00454-004-1152-0. 
  12. ^ P. E. Hart, The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory 18 (1968) 515–516. doi: 10.1109/TIT.1968.1054155
  13. ^ 13.0 13.1 E. M. Mirkes, KNN and Potential Energy: applet. University of Leicester, 2011.