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

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

הכללה ישירה של בעיה זו היא חיפוש k -NN כלומר, חיפוש k נקודות קרובות ביותר לנקודה נתונה.

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

יישומים

בעיית חיפוש השכן הקרוב ביותר קיימת בתחומים יישומיים רבים ושונים, בתוך כך:

• זיהוי תבניות - במיוחד לטובת זיהוי תווים אופטי
• סיווג סטטיסטי - ראו אלגוריתם שכן קרוב
• ראייה ממוחשבת
• גאומטריה חישובית
• מאגרי מידע - לדוגמה, אחזור תמונות מבוסס תוכן
• תורת הקידוד -
• דחיסת נתונים - ראו תקן MPEG-2
• חישה רובוטית
• מערכות המלצה, למשל, סינון שיתופי
• שיווק באינטרנט - במה שנוגע לפרסום לפי הקשר ומיקוד התנהגותי
• ריצוף DNA
• בדיקת איות - הצעת איות נכון
• גילוי פלגיאט
• ניתוח אשכולות - הקצאה של קבוצת תצפיות בתת-קבוצות (הנקראות אשכולות) כך שהתצפיות באותו אשכול דומות במובן מסוים, בדרך כלל על בסיס המרחק האוקלידי
• דמיון כימי
• תכנון תנועה מבוסס דגימה

שיטות

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

שיטות מדויקות

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

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

חלוקת המרחב

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

במקרה של מרחב מטרי כללי, הגישה של הפרד ומשול ידועה כגישת עץ המטרי. דוגמאות מיוחדות כוללות עץ-VP ועץ-BK שיטות.

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

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

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

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

גרסאות

ישנן כמה וריאציות לבעיית NNS ושני הידועים ביותר הם:

• k-nearest neighbor search
• approximate nearest neighbor search

k-nearest neighbor search

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

Approximate nearest neighbor

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

קישורים חיצוניים

מדיה וקבצים בנושא חיפוש שכן קרוב בוויקישיתוף

• Nearest Neighbors and Similarity Search - אתר המוקדש לנושא הערך וכולל חומרים חינוכיים, תוכנות, ספרות, חוקרים, בעיות פתוחות ואירועים הקשורים לחיפוש השכן הקרוב. מנוהל על ידי יורי ליפשיץ.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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