מה זה KNN (K-Nearest Neighbors)?

מה זה K-Nearest Neighbors (KNN)?

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

סקירה כללית של K-Nearest Neighbors (KNN)

צילום: Antti Ajanki AnAj דרך Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

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

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

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

כיצד פועל אלגוריתם KNN

אלגוריתם KNN עובר שלושה שלבים עיקריים תוך כדי ביצועו:

1. הגדרת K למספר השכנים הנבחר.
2. חישוב המרחק בין דוגמה שסופקה/בדיקה לבין דוגמאות מערך הנתונים.
3. מיון המרחקים המחושבים.
4. קבלת התוויות של ערכי K העליון.
5. החזרת תחזית לגבי דוגמה למבחן.

בשלב הראשון, K נבחר על ידי המשתמש והוא אומר לאלגוריתם כמה שכנים (כמה נקודות נתונים מסביב) יש לקחת בחשבון בעת ​​מתן פסק דין לגבי הקבוצה שאליה שייכת דוגמת היעד. בשלב השני, שים לב שהמודל בודק את המרחק בין דוגמת היעד לכל דוגמה במערך הנתונים. לאחר מכן המרחקים מתווספים לרשימה וממוינים. לאחר מכן, הרשימה הממוינת מסומנת והתוויות עבור רכיבי K העליון מוחזרות. במילים אחרות, אם K מוגדר ל-5, המודל בודק את התוויות של 5 נקודות הנתונים הקרובות ביותר לנקודת נתוני היעד. בעת עיבוד תחזית לגבי נקודת נתוני היעד, זה משנה אם המשימה היא א נסיגה or מיון מְשִׁימָה. עבור משימת רגרסיה, נעשה שימוש בממוצע של תוויות K העליון, בעוד שהמצב של תוויות K העליון משמש במקרה של סיווג.

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

למה הערך של K חשוב

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

תמונה: Agor153 באמצעות Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

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

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

יתרונות וחסרונות של KNN

בואו נבחן כמה מהיתרונות והחסרונות של מודל KNN.

יתרונות:

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

KNN מדויק מאוד ופשוט לשימוש. קל לפרש, להבין וליישם.

KNN אינו מניח הנחות לגבי הנתונים, כלומר ניתן להשתמש בהם למגוון רחב של בעיות.

חסרונות:

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

KNN מתגלה כרגיש מאוד לקנה המידה של מערך הנתונים והוא יכול להישלף על ידי תכונות לא רלוונטיות די בקלות בהשוואה למודלים אחרים.

סיכום של K-Nearest Neighbors (KNN)

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