לדלג לתוכן

משתמש:Moshe.benyamin/טיוטה

מתוך ויקיפדיה, האנציקלופדיה החופשית
דף זה אינו ערך אנציקלופדי
דף זה הוא טיוטה של Moshe.benyamin.
דף זה אינו ערך אנציקלופדי
דף זה הוא טיוטה של Moshe.benyamin.

{{DISPLAYTITLE:אלגוריתם שכן הקרוב}}

אלגוריתם שכן קרוב 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 -NN. המבחן לדוגמה (עיגול ירוק) צריך להיות מסווג או אל מדרגה ראשונה של מרובע כחול או ברמה השנייה של אדום משולש. אם K = 3 (עיגול מקו אחיד) הוא מוקצה לרמה השנייה כי ישנם 2 משולשים ורק מרובע אחד בתוך המעגל הפנימי.אם "K = 5" (עיגול מקו מקווקוו) הוא מוקצה לרמה הראשונה (שלושה ריבועים לעומת שני משולשים בתוך המעגל החיצוני).

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

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

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

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

בחירת פרמטרים

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

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

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

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

מאפיינים

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

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

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

”k-NN” כולל כמה תוצאות עקביות חזקות. בעת שכמות המידע שואפת לאינסוף, לאלגוריתם מובטח שיעור שגיאה מרבי לא יותר מפעמיים קצב שגיאות Bayes. (קצב השגיאה המינימלי הניתן להשגה בתחשב בהפצת הנתונים).[9] k-NN is guaranteed to approach the Bayes error rate for some value of k (where k increases as a function of the number of data points). Various improvements to k-NN are possible by using proximity graphs.[10]

חילוץ תכונות

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

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

דוגמה אופיינית  לחיזוי מחשב עבור מערכת לזיהוי פנים באמצעות "k" -NN הכוללים חילוץ תכונות ושלבי הסרת ממדים טרום עיבוד (בדרך כלל מיושם עם [ [opencv. ] ):
  1. Haar זיהוי פנים
  2. Mean-shift ניתוח מעקבים
  3. ניתוח מרכיבים ראשי או ניתוח הבחנה לינארי הקרנה לחלל, ומיד לאחר סיווג K-NN.


הפחתת ממד

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

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

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

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

לערכת נתונים בעלת ממדים רבים (למשל בעת ביצוע חיפוש דמיון בזרמי וידאו חי, נתוני DNA או נתונים רב ממדיים (סדרות זמן) המריצים חיפוש K-NN מהיר מקורב באמצעות תיוג מקומי, "הקרנות אקראיות", "random projections",[13] "sketches" [14] או טכניקות חיפושי דמיון רב ממדיים אחרים מתוך [vldb]- כלים העשויים להיות האפשרות המעשית היחידה.

גבול ההחלטה

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

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

הפחתת נתונים

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

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

  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 סיווג.[16] הוא בוחר את אבות הטיפוס "U" מתוך נתוני הבדיקות, כך ש 1NN עם "U" ניתן לסווג את דוגמאות כמעט במדויק כפי ש 1NN עושה עם כל הנתונים.

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

CNN עובד באופן איטרטיבי בהינתן סט בדיקות:

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

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

הוא יעיל כדי לסרוק את דוגמאות הבדיקה על מנת להקטין את יחס הגבול.[17] יחס הגבול של דוגמאות הבדיקה "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.[17]

  • CNN model reduction for k-NN classifiers
  • Fig. 1. The dataset.
    Fig. 1. The dataset.
  • Fig. 2. The 1NN classification map.
    Fig. 2. The 1NN classification map.
  • Fig. 3. The 5NN classification map.
    Fig. 3. The 5NN classification map.
  • Fig. 4. The CNN reduced dataset.
    Fig. 4. The CNN reduced dataset.
  • Fig. 5. The 1NN classification map based on the CNN extracted prototypes.
    Fig. 5. The 1NN classification map based on the CNN extracted prototypes.

K-NN רגרסיה

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

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

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


אימות התוצאות

[עריכת קוד מקור | עריכה]
[ [confusion matrix.] או "matching matrix" לעיתים קרובות משמש ככלי אימות הדיוק של סיווג "k" -NN. שיטות סטטיסטיות חזקות יותר כמו [ [likelihood-ratio test.] ניתנות בנוסף להחלה.

See also

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

הערות שוליים

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


שגיאות פרמטריות בתבנית:הערות שוליים
פרמטרים [ טורים ] לא מופיעים בהגדרת התבנית

  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. ^ Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). "Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization". Journal of Chemical Information and Modeling. 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183.{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)
  6. ^ 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.{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)
  7. ^ D. G. Terrell; D. W. Scott (1992). "Variable kernel density estimation". Annals of Statistics. 20 (3): 1236–1265. doi:10.1214/aos/1176348768.
  8. ^ Mills, Peter. "Efficient statistical classification of satellite measurements". International Journal of Remote Sensing.
  9. ^ Cover TM, Hart PE (1967). "Nearest neighbor pattern classification". IEEE Transactions on Information Theory. 13 (1): 21–27. doi:10.1109/TIT.1967.1053964.
  10. ^ Toussaint GT (באפריל 2005). "Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining". International Journal of Computational Geometry and Applications. 15 (2): 101–150. doi:10.1142/S0218195905001622. {{cite journal}}: (עזרה)
  11. ^ Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful?. Database Theory—ICDT’99, 217-235|year 1999
  12. ^ Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009
  13. ^ Bingham, Ella, and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM | year 2001
  14. ^ Shasha, D High Performance Discovery in Time Series.Berlin: Springer, 2004, ISBN 0-387-00857-8
  15. ^ 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.{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)
  16. ^ P. E. Hart, The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory 18 (1968) 515–516. doi: 10.1109/TIT.1968.1054155
  17. ^ 1 2 E. M. Mirkes, KNN and Potential Energy: applet. University of Leicester, 2011.

Further reading

[עריכת קוד מקור | עריכה]
אוחזר מתוך "https://he.wikipedia.org/w/index.php?title=משתמש:Moshe.benyamin/טיוטה&oldid=24751527"