لید: وهاب میررکنی، پژوهشگر ایرانی و دانشآموخته دانشگاه صنعتی شریف و MIT، با توسعه روش «هش حساس به مجاورت» مبتنی بر توزیعهای پایدار، راهی برای جستوجوی سریعتر دادههای چندبعدی ارائه کرد؛ روشی که در برخی کاربردها سرعت جستوجوی دادههای مشابه را تا ۴۰ برابر افزایش داد.
وقتی حجم دادهها به میلیونها یا حتی میلیاردها رکورد میرسد، پیدا کردن نزدیکترین یا شبیهترین داده به یک نمونه مشخص، به مسئلهای پیچیده تبدیل میشود. این مشکل در حوزههایی مانند پردازش تصویر، تحلیل متن، سیستمهای پیشنهاددهنده و دادههای ژنتیکی اهمیت زیادی دارد.
در چنین شرایطی، بررسی تکتک دادهها و مقایسه مستقیم آنها نهتنها زمانبر، بلکه از نظر محاسباتی نیز بسیار پرهزینه است. یکی از راهکارهای مهم برای حل این مشکل، الگوریتم «هش حساس به مجاورت» یا LSH است؛ روشی که دادههای مشابه را در گروههای نزدیک به یکدیگر قرار میدهد تا جستوجو به جای کل مجموعه، روی بخش محدودی از دادهها انجام شود.
وقتی پیدا کردن داده مشابه شبیه جستوجوی سوزن در انبار کاه میشود
تصور کنید در یک خط مستقیم قرار دارید و میخواهید نزدیکترین فرد به خود را پیدا کنید. کافی است افراد اطراف را بررسی کنید. اما با اضافه شدن ابعاد بیشتر، مسئله پیچیدهتر میشود.
در فضای دوبعدی باید موقعیت افراد را در طول و عرض بررسی کرد و در فضای سهبعدی، ارتفاع نیز به مسئله اضافه میشود. اگر ابعاد بیشتری وارد محاسبات شوند، جستوجوی نزدیکترین نقطه بهسرعت دشوار میشود.
این وضعیت در بسیاری از دادههای واقعی رخ میدهد. یک تصویر، متن، داده ژنتیکی یا حتی اطلاعات مربوط به رفتار کاربران میتواند در فضایی با صدها، هزاران یا حتی میلیونها ویژگی نمایش داده شود.
وهاب میررکنی، پژوهشگر ایرانی و دانشآموخته دانشگاه صنعتی شریف و مؤسسه فناوری ماساچوست، از پژوهشگرانی است که در توسعه روشهای جستوجوی دادههای چندبعدی نقش داشته است. او در سال ۲۰۲۵ نیز به عنوان یکی از برگزیدگان جایزه مصطفی(ص) معرفی شد.
یک تصویر چگونه به میلیونها بُعد تبدیل میشود؟
برای درک پیچیدگی این مسئله، کافی است یک تصویر رنگی را در نظر بگیریم. یک تصویر ۱۰۰۰ در ۱۰۰۰ پیکسلی، برای هر پیکسل سه مقدار رنگی قرمز، سبز و آبی دارد. بنابراین نمایش خام چنین تصویری میتواند فضایی با حدود سه میلیون مقدار ایجاد کند.
البته در کاربردهای عملی از روشهای مختلف کاهش ابعاد استفاده میشود، اما حتی پس از این فرآیند نیز دادههای تصویری معمولاً دارای تعداد زیادی ویژگی هستند.
در پردازش زبان طبیعی نیز وضعیت مشابهی وجود دارد. کلمات و متنها با روشهای مختلف به بردارهای عددی تبدیل میشوند. هر کلمه میتواند با برداری چندبعدی نمایش داده شود و یک متن متشکل از تعداد زیادی کلمه، در نهایت دادهای با ابعاد بسیار بالا ایجاد میکند.
دادههای ژنتیکی نیز نمونه دیگری هستند. DNA انسان حدود سه میلیارد جفت باز دارد و حتی بررسی بخشهایی از اطلاعات ژنتیکی میتواند مجموعهای بسیار بزرگ از دادهها ایجاد کند.
«نفرین ابعاد بالا» چیست؟
افزایش تعداد ابعاد، پدیدهای را ایجاد میکند که در علوم داده با عنوان نفرین ابعاد بالا شناخته میشود.
در فضاهای بسیار پرُبعد، دادهها بهتدریج پراکندهتر میشوند و تشخیص میزان شباهت میان آنها دشوارتر خواهد شد. در نتیجه، روشهای سنتی جستوجوی نزدیکترین همسایه که در فضاهای کمبعد عملکرد مناسبی دارند، با افزایش ابعاد کارایی خود را از دست میدهند.
مسئله «نزدیکترین همسایه» یکی از مسائل مهم در علوم داده، یادگیری ماشین و بازیابی اطلاعات است. هدف آن، پیدا کردن نزدیکترین داده به یک نمونه مشخص بر اساس یک معیار فاصله یا شباهت است.
فاصله اقلیدسی و فاصله منهتن از شناختهشدهترین معیارها در این حوزه هستند؛ اما در کاربردهای پیچیدهتر، معیارهای دیگری نیز مورد استفاده قرار میگیرند.
LSH چگونه جستوجو را سریعتر میکند؟
ایده اصلی LSH این است که به جای مقایسه مستقیم یک داده با تمام دادههای موجود، دادههای مشابه در گروههایی نزدیک به هم قرار بگیرند.
برای مثال، یک کتابخانه با میلیونها کتاب را تصور کنید. اگر بخواهید کتابی مشابه یک اثر مشخص پیدا کنید، منطقی نیست تمام کتابها را بررسی کنید. میتوان کتابها را ابتدا بر اساس موضوع، دوره تاریخی، حجم یا ویژگیهای دیگر دستهبندی کرد و سپس جستوجو را در گروههای مرتبط انجام داد.
در LSH نیز ایده مشابهی به شکل ریاضی پیادهسازی میشود. توابع هش به گونهای طراحی میشوند که دادههای مشابه احتمال بیشتری داشته باشند که در یک گروه قرار بگیرند.
البته طراحی چنین توابعی ساده نیست؛ زیرا هدف این است که ویژگی مهمی از شباهت دادهها در فرآیند تبدیل حفظ شود.
میررکنی چگونه LSH را توسعه داد؟
ایده LSH پیش از پژوهش میررکنی مطرح شده بود، اما محدودیتهایی داشت و در برخی شرایط نمیتوانست برای انواع مختلف معیارهای فاصله به شکل مطلوب استفاده شود.
در سال ۲۰۰۴، وهاب میررکنی و همکارانش رویکردی مبتنی بر توزیعهای پایدار ارائه کردند که دامنه استفاده از این روش را گسترش داد.
در این روش، به جای محدود شدن به یک نوع توزیع، امکان طراحی توابع هش متناسب با معیارهای مختلف فاصله فراهم شد. در نتیجه، LSH میتوانست برای طیف گستردهتری از دادهها و مسائل مورد استفاده قرار گیرد.
اهمیت این رویکرد در این بود که دادههای مشابه، حتی پس از انتقال به فضای جدید، با احتمال بالاتری در نزدیکی یکدیگر باقی میماندند و میتوانستند با بررسی بخش کوچکتری از مجموعه داده پیدا شوند.
از تصویر و متن تا سیستمهای پیشنهاددهنده
کاربرد چنین الگوریتمهایی تنها به یک حوزه محدود نمیشود. جستوجوی تصاویر مشابه، مقایسه متنها، تشخیص شباهت یا تقلب متنی، تحلیل دادههای ژنتیکی و ایجاد سیستمهای پیشنهاددهنده از جمله مسائلی هستند که به جستوجوی دادههای مشابه نیاز دارند.
برای نمونه، یک فروشگاه اینترنتی میتواند با استفاده از شباهت میان رفتار کاربران، محصولات مشابه با علایق آنها را پیشنهاد کند. در حوزه تصویر نیز میتوان به دنبال تصاویری مشابه یک نمونه مشخص در یک پایگاه داده بزرگ گشت.
در پردازش متن نیز مقایسه اسناد، پیدا کردن محتوای مشابه و برخی کاربردهای تحلیل زبان به چنین روشهایی نیاز دارند.
جستوجوی دادهها تا ۴۰ برابر سریعتر
بر اساس گزارش ارائهشده درباره این پژوهش، روش توسعهیافته توسط میررکنی و همکارانش در برخی آزمایشها توانست عملکرد جستوجو را تا ۴۰ برابر نسبت به روشهای سنتی بهبود دهد.
اهمیت این دستاورد در این است که با افزایش حجم و پیچیدگی دادهها، امکان جستوجوی سریعتر دادههای مشابه فراهم میشود؛ بدون آنکه لازم باشد تمام دادههای موجود به صورت مستقیم با یکدیگر مقایسه شوند.
این رویکرد نمونهای از تلاش برای تبدیل مسائل پیچیده و پرهزینه در فضای دادههای چندبعدی به مسئلهای سادهتر و قابل مدیریتتر است؛ رویکردی که میتواند در بسیاری از کاربردهای علوم داده و هوش مصنوعی مورد استفاده قرار گیرد.
