חיפוש שכן קרוב

חיפוש שכן קרוב (Nearest neighbor search או בקיצור: NNS) הוא סוג של חיפוש מקורב עבור בעיית האופטימיזציה של איתור הנקודה הקרובה ביותר (או הדומה ביותר) לנקודה נתונה במערך נתון מסוים. הקרבה (מידת השכנות; Closeness) מתבטאת בדרך כלל במונחים של פונקציית שונות: ככל שהאובייקטים דומים פחות, כך ערכי הפונקציה גדולים יותר. באופן פורמלי, בעיית החיפוש של השכן הקרוב ביותר (NN) מוגדרת באופן הבא: נתון S, אוסף של נקודות במרחב M ונקודת שאילתה q∈M, מצא את הנקודה ב-S הקרובה ביותר ל- q .
הכללה ישירה של בעיה זו היא חיפוש k -NN כלומר, חיפוש k נקודות קרובות ביותר לנקודה נתונה.
לרוב, מרחב הבעיה M הוא מרחב מטרי ושונות בו מתבטאת כערך מרחק, שהוא סימטרי ומקיים את אי-השוויון המשולש. מרחב נפוץ אפילו יותר הוא כאשר M הוא כמרחב וקטור d ממדי שבו ההפרש נמדדת באמצעות המרחק האוקלידי, מרחק מנהטן או מרחק סטטיסטי אחר. עם זאת, פונקציית השונות יכולה להיות שרירותית. כולל מקרים בהם אי שוויון המשולש אינו מתקיים.

שיטות

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

חיפוש ליניארי

הפתרון הפשוט ביותר לבעיית NNS הוא לחשב את המרחק מנקודת השאילתה לכל נקודה אחרת במסד הנתונים, ולעקוב אחר הנתון "הטוב ביותר עד כה". שימוש באלגוריתם זה, המכונה לעיתים גישה נאיבית, יש זמן ריצה כאשר N הוא כמות האיברים ב-S ו- d הוא המימד של M. במקרה זה, אין מבני נתונים נוספים שיש לשמור מעבר למסד הנתונים עצמו.

חלוקת המרחב

מאז שנות השבעים הוחל על הבעיה שיטה של הפרד ומשול. במקרה של מרחב אוקלידי גישה זו כוללת אינדקס מרחבי. מספר שיטות לחלוקת המרחב פותחו לפתרון בעיית ה- NNS. אולי הפשוטה ביותר היא שיטת עץ kd, אשר באופן איטרטיבי חוצה את מרחב החיפוש לשני אזורים המכילים מחצית הנקודות של אזור האב. שאילתות מבוצעות באמצעות חציית העץ מן השורש אל העלה על ידי הערכת נקודת השאילתה בכל פיצול. בהתאם למרחק שצוין בשאילתה, ייתכן שיהיה צורך להעריך גם את הענפים השכנים שעשויים להכיל התאמות. עבור זמן שאילתה במימד קבוע, סיבוכיות זמן הריצה הממוצעת היא  במקרה של נקודות מסודרות באופן אקראי. שיטה חלופית היא באמצעות שימוש בעצי-R. מבנה נתונים שנועד לתמוך בחיפוש שכן הקרוב ביותר בהקשר דינמי, שכן יש אלגוריתמים יעילים עבור הוספה ומחיקה כגון עץ *R .עצי-R יכולים לתת תשובה לשאלת השכנים הקרובים גם ביחס למרחק אוקלידי וגם ביחס למרחקים אחרים.
במקרה של מרחב מטרי כללי, הגישה של הפרד ומשול ידועה כגישת עץ המטרי. דוגמאות מיוחדות כוללות עץ-VP ועץ-BK שיטות.

שיטות קירוב לפתרון הבעיה

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

רגישות מקומית (Locality sensitive hashing)

Locality sensitive hashing (LSH) היא טכניקה לקיבוץ נקודות במרחב ל"דליים "המבוססים על מרחק מסוים בין הנקודות. נקודות הקרובות זו לזו תחת המרחק הנבחר ממופות לאותו דלי בסבירות גבוהה.

k-nearest neighbor search

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

Approximate nearest neighbor

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