جستجوی نزدیک‌ترین همسایه

جستجوی نزدیک‌ترین همسایه

جستجوی نزدیک‌ترین همسایه (به انگلیسی: Nearest Neighbor Search) (یاNNS)، که همچنین با نام‌های جستجوی مجاورت، جستجوی همسانی یا جستجوی نزدیک‌ترین نقطه شناخته می‌شود، یک مسئله بهینه‌سازی برای پیدا کردن نزدیک‌ترین نقطه‌ها در فضاهای متریک است. مسئله بدین صورت است که: مجموعه S شامل تعدادی نقطه در یک فضای متریک مانند M و نیز یک نقطهٔ پرس‌وجوی q∈ M داده شده‌است، هدف پیدا کردن نزدیک‌ترین نقطه در S به q است. در بسیاری از موارد، فضای M به صورت یک فضای اقلیدسی d-بعدی و فاصله بین نقاط با معیار فاصله اقلیدسی، فاصله منهتن یا دیگر فاصله‌های متریک سنجیده می‌شود. دونالد کنوت در جلد ۳ از هنر برنامه‌نویسی کامپیوتر (۱۹۷۳) این مسئله را «مسئله دفتر پست» نامید. این نام‌گذاری اشاره یک به برنامه کامپیوتری دارد که برای اختصاص نزدیکترین اداره پست به یک محل اقامت نوشته شده بود.

کاربردها

• بازشناخت الگو - به ویژه برای تشخیص کاراکتر به شیوه نوری
• دسته‌بندی آماری
• بینایی رایانه‌ای
• هندسه محاسباتی
• پایگاه داده - به عنوان مثال، بازیابی تصویر مبتنی بر محتوا
• نظریه رمزنگاری
• فشرده‌سازی داده‌ها
• سامانه توصیه‌گر - به عنوان مثال، پالایش گروهی
• بازاریابی اینترنتی – مانند تبلیغات محتوایی و هدف‌گیری رفتاری
• تعیین توالی DNA
• غلط‌یاب – پیشنهاد املای درست
• کشف دستبرد علمی
• الگوریتم‌های جستجوی تماس در FEA
• اندازه‌گیری شباهت برای پیش‌بینی مسیر زندگی ورزشکاران حرفه‌ای
• تجزیه و تحلیل خوشه‌ها - تخصیص مجموعه‌ای از مشاهدات به زیر مجموعه‌هایی (به نام خوشه) به‌طوری‌که مشاهدات در هر خوشه از برخی جهات مشابه باشند، (معمولاً بر اساس فاصله اقلیدسی)
• شباهت شیمیایی

روش‌ها

راه حل‌های متعددی برای مسئله NNS پیشنهاد شده‌اند. کیفیت و سودمندی این الگوریتم‌ها بر اساس پیچیدگی زمانی و همچنین پیچیدگی حافظه مصرفی ساختمان داده‌هاهای آنها، ارزیابی می‌شود. مشاهدات غیررسمی که معمولاً آن را با عنوان نفرین ابعاد (به انگلیسی: curse of dimensionality) یاد می‌کنند، بیان می‌دارد که در واقع هیچ راه حل دقیق و همه منظوره‌ای برای مسئله NNS در فضای اقلیدسی با ابعاد بالا وجود ندارد که از پیش پردازش با مرتبه چندجمله‌ای و زمان جستجوی چند لگاریتمی (O((log n)^k بهره ببرد.

جستجوی خطی

ساده‌ترین راه حل برای مسئله NNS، محاسبه فاصله نقطه پرسش شده تا تمامی نقاطِ پایگاه داده، همراه با نگهداری «بهترین جواب پیدا شده تا کنون» است. این الگوریتم که به آن الگوریتم سرراست نیز گفته می‌شود، دارای مرتبه زمانی (O(nd است که در آن N اندازه مجموعه S و d تعداد ابعاد فضای M است. در این روش هیچ داده ساختاری از جستجوها ذخیره نخواهد شد و الگوریتم بجز ذخیره نقاط پایگاه داده، هزینه حافظه‌ای دیگری ندارد. روش ذکر شده، به‌طور میانگین، از روش‌های پارتیشن‌بندی فضا، در ابعاد بالاتر، بهتر عمل می‌کند.

پارتیشن‌بندی فضا

از سال ۱۹۷۰، روش انشعاب و تحدید بر روی مسئله NNS اعمال شده‌است. در فضای اقلیدسی، این کار با نام شاخص‌های مکانی یا روش دسترسی مکانی شناخته می‌شود. روش‌های متعددی برای پارتیشن‌بندی فضا به منظور حل مسئله NNS ارائه و توسعه داده شده‌اند. در این بین، ساده‌ترین روش، استفاده از ساختمان داده درخت کی‌دی (به انگلیسی: k-d tree) است که به صورت تکراری فضای جستجو را در یکی از ابعاد، به دو نیم‌بخش تقسیم می‌کند به گونه‌ای که هر نیم‌بخش –تقریباً- نیمی از نقاط بخشِ بزرگتر را در برخواهد گرفت. پرس و جو با پیمایش درخت از ریشه تا برگ صورت می‌پذیرد به گونه‌ای که در هر مرحله، مقدار بردار گره در بُعد مشخصی، با همان بُعد از نقطه پرس و جو، مقایسه می‌شود؛ اگر مقدار نقطه پرس وجو بیشتر بود به زیر درخت سمت راست و در غیر این‌صورت به زیردرخت چپ حرکت می‌کنیم. همچنین بسته به اینکه فاصله این دو نقطه چقدر است، شاخه‌های کناری نیز ممکن است نیاز به بررسی داشته باشند. برای مسائلی که تعداد بعد فضا ثابت است، میانگین پیچیدگی زمانی این روش از مرتبه (O(log N است. در مورد نقاط راندم توزیع شده تحلیل پیچیدگی زمانی مربوط به بدترین حالت صورت می‌گیرد. روش دیگر، استفاده از ساختمان داده درخت مستطیلی است که برای استفاده NNS در زمینه‌های پویا بکار گرفته می‌شود. این ساختمان داده دارای الگوریتم‌های مؤثری برای درج و حذف از درخت می‌باشد.
در رابطه با فضاهای متریک کلی، روش انشعاب و تحدید با نام درخت متریک شناخته می‌شود. به عنوان نمونه می‌توان به vp-tree و BK-tree اشاره کرد.
با استفاده از مجموعه‌ای از نقاطی از یک فضای ۳ بعدی و قرار دادن آن‌ها در یک درخت BSP و نیز با داشتن یک نقطه پرس و جو از همان فضا، یک راه حل ممکن برای مسئله پیدا کردن نزدیک‌ترین نقطه در ابری از نقاط، به نقطه پرس و جو، در زیر در قالب یک الگوریتم توضیح داده می‌شود. گفتنی است، ممکن است هیچ نقطه‌ای به عنوان جواب وجود نداشته باشد، زیرا ممکن است این جواب، یکتا نباشد اما در عمل، معمولاً ما تنها دنبال پیدا کردن یکی از زیر مجموعه‌های تمام ابر-نقاط داده شده، که در کوتاه‌ترین فاصله نسبت به نقطه پرس و جو، واقع شده هستیم.
ایده این است که، برای هر شاخه از درخت، حدس می‌زنیم که نزدیک‌ترین نقطه در ابر، در نیم فضای شامل نقطه پرس و جو قرار دارد. اگر چه این حدس ممکن است درست نباشد، اما ابتکار خوبی است. پس از پیمایش بازگشتی نیم فضای حدس زده شده، فاصله محاسبه شده را با کمترین فاصلهٔ نقطه پرس و جو تا صفحه پارتیشن‌کننده فضا مقایسه می‌کنیم. این فاصله، کمترین فاصله ایست که بین نقطه پرس و جو و نقاط نیم فضای جستجو نشده می‌تواند وجود داشته باشد. اگر فاصله نزدیکترین نقطه در این نیم-فضا کمتر بود، پاسخ قطعاً در همین نیم-فضاست و نیازی به جستجوی نیم فضای مجاور نیست، در غیر اینصورت باید آن نیم-فضا نیز به صورت بازگشتی جستجو شده و پاسخِ آن با کوتاهترین فاصله بدست آمده تاکنون مقایسه گردد و مقدار درست برگردانده شود. عملکرد این الگوریتم زمانی که نقطه پرس و جو در نزدیکی ابر باشد، بیشتر به زمان لگاریتمی نزدیکتر است تا زمان خطی؛ زیرا هنگامی که فاصله بین نقطه پرس و جو و نزدیک‌ترین نقطه در ابر به صفر میل کند، الگوریتم تنها با استفاده از جستجوی نقطه پرس و جو به عنوان یک کلید می‌تواند به نتیجه درست برسد.

درهم سازی (به انگلیسی: Hash) براساس مکان

درهم‌سازی براساس مکان (LSH) تکنیکی برای دسته‌بندی نقاط فضا به تعدادی «سطل» است که بر اساس یک معیار فاصله که روی نقاط اعمال می‌شود، انجام می‌پذیرد. نقاطی که بر اساس این معیار فاصله، به یکدیگر نزدیک‌ترند با احتمال بالا در یک سطل دسته‌بندی خواهند شد.

جستجوی نزدیکترین همسایه در فضاهای با ابعاد درونی کوچک

درخت پوشش دارای یک حد تئوریک است که بر اساس ثابت doubling مجموعه داده تعیین می‌شود. محدودیت در زمان جستجو از مرتبه (O(c^12 log n است که در آن c ثابت گسترش مجموعه داده‌است.

فایل‌های تقریب بردار

در فضاهای بعدی بالا، ساختارهای درختی نمایه دار غیرقابل استفاده می‌شوند، زیرا هر بار نیاز است تا درصد بیشتری از گره‌ها بررسی شوند. برای سرعت بخشیدن به جستجو خطی، یک نسخه فشرده شده از بردار ویژگی‌های ذخیره شده در RAM برای پیش–فیلتر کردن مجموعه داده‌ها - در اولین اجرا - استفاده می‌شود. نامزدهای نهایی برای محاسبه فاصله در مرحلهٔ دوم و با استفاده از داده‌های غیر فشرده واقع در دیسک تعیین خواهند شد.

فشرده‌سازی / خوشه بندی مبنی بر جستجو

روش VA-File یک مورد خاص از یک جستجوی مبنی بر فشرده‌سازی است، که در آن هر ویژگی به‌طور یکنواخت و البته مستقل فشرده می‌شود. فشرده‌سازی بهینه در فضاهای چند بعدی، از رقمی (کوانتیزه) کردن بردارها (VQ) استفاده می‌کند، که توسط خوشه بندی پیاده‌سازی می‌شود. در این روش پایگاه داده، خوشه بندی می‌شود و سپس "امیدوارکننده"‌ترین خوشه‌ها بازیابی می‌شوند. جوابهای خیلی خوبی، از VA-File، اندیس‌های مبتنی بر درخت و اسکن‌های متوالی، مشاهده شده‌است. همچنین به تشابه بین خوشه بندی و LSH توجه کنید.

انواع دیگر

انواع متعددی از مسئله NNS وجود دارد و دو تا از شناخته شده‌ترین آن‌ها جستجوی k همسایه نزدیکترین و جستجوی نزدیکترین همسایه با ε-تقریب است.

جستجوی k نزدیکترین همسایه

جستجوی k نزدیکترین همسایه، K همسایه نزدیک تر به نقطه پرس و جو را برمی‌گرداند. این روش معمولاً در تجزیه و تحلیلِ پیش‌بینی، به منظور تخمین یا دسته‌بندی یک نقطه بر اساس اجماع همسایگان آن استفاده می‌شود. گراف k نزدیکترین همسایه گرافیست که در آن هر نقطه در گراف K نزدیک‌ترین همسایگان خود متصل است.

تقریب نزدیکترین همسایه

در برخی کاربردها برگرداندن یک «حدس خوب» از نزدیکترین همسایه می‌تواند قابل قبول باشد. در این موارد، می‌توان از الگوریتمی استفاده کرد که گرچه بازگشت نزدیکترین همسایه واقعی را در همه موارد تضمین نمی‌کند، اما درعوض در سرعت یا در حافظه صرفه جویی می‌شود. بیشتر این الگوریتم‌ها، در اکثر موارد، خودِ نزدیکترین همسایه را پیدا می‌کنند، اما این امر، به شدت به مجموعه دادهٔ در حال جستجو بستگی دارد. الگوریتم‌هایی که از تقریب جستجوی نزدیکترین همسایه پشتیبانی می‌کنند از درهم‌سازی حساس به مکان، جستجوی اول-بهترین-سطح و هم چنین از درخت متعادل با تجزیه جعبه‌ای (به انگلیسی: box-decomposition) استفاده می‌کنند. جستجو نزدیکترین همسایه با ε-تقریب به‌طور فزاینده‌ای در حال تبدیل شدن به یک ابزار محبوب برای مقابله با مسئله نفرین ابعاد است.

نسبت فاصله در نزدیکترین همسایه

نسبت فاصله در نزدیکترین همسایه، آستانه را بر روی فاصله مستقیم نقطه اصلی از همسایه رقیب اعمال نمی‌کند، بلکه روی یک نسبت از آن، و بسته به فاصله از همسایه‌های قبلی اعمال می‌گردد. در CBIR از این روش برای بازیابی تصاویر از طریق «پرس و جو با مثال» و با به‌کارگیری شباهت بین ویژگی‌های محلی استفاده می‌شود. به‌طور کلی تر، این روش در مسائل مشابه متعددی کاربر دارد.

همسایه‌های نزدیک در شعاع ثابت

همسایه‌های نزدیک در شعاع ثابت، مسئله‌ای است که در آن می‌خواهیم به شکلی مؤثر، تمام اعضای یک مجموعه نقاط در فضای اقلیدسی را در فاصله‌ای ثابت از یک نقطهٔ داده شدهٔ مشخص، پیدا کنیم. در این حالت، داده ساختارها باید روی یک فاصله ثابت کار کنند اگر چه نقطه پرس و جو، به صورت دلخواه است.

همه نزدیک‌ترین همسایگان

برای برخی کاربردها (به عنوان مثال برآورد آنتروپی)، ممکن است ما N داده نقطه داشته باشیم و مایل به دانستن نزدیک‌ترین همسایه برای هر یک از این N نقطه باشیم. البته این کار می‌تواند با اجرای جستجوی نزدیکترین همسایه برای هر کدام از نقاط به دست آید، اما یک استراتژی بهتر، الگوریتمی خواهد بود که اطلاعاتی اضافی از جستجوها را استفاده کرده تا جستجوی کارآمد تری ارائه دهد. به عنوان یک مثال ساده: هنگامی که ما فاصله نقطه X تا نقطه Y را پیدا کردیم، این مقدار، برابر با فاصله Y تا X نیز هست، از این‌رو برای محاسبه فاصله Y تا X، اطلاعات قبلی را مورد استفاده مجدد قرارمی‌دهیم. با دادن ابعاد ثابت، یک نُرم مثبت نیمه معین (که شامل هر جمله نرم LP است) و n نقطه در این فضا، نزدیکترین همسایه از هر نقطه را می‌توان در زمان (O(n log n یافت و m نزدیک‌ترین همسایگان هر نقطه را می‌توان در زمان (O(mn log n یافت.

منابع

Wikipedia: Nearest Neighbor Search