خانه / علم داده / مفاهیم پایه / سیستم های بازیابی اطلاعات به زبان ساده
IR

سیستم های بازیابی اطلاعات به زبان ساده

ممکن است برای شما هم این سوال پیش آمده باشد که زمانی که یک عبارت را در گوگل جستجو می کنیم، در بین میلیون ها صفحه ذخیره شده، گوگل چگونه تشخیص می دهد کدام صفحات با عبارت جستجو شده مرتبط هستند ؟

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

سیستم های بازیابی اطلاعات

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

یک سامانه بازیابی اطلاعات، اجزاء و مولفه های مختلفی دارد که از جمله مولفه های اصلی آن بخش پردازش زبان طبیعی یا NLP است به گونه ای که بتواند بفهمد منظور اصلی یک کاربر از این سوال چیست و کلمات بی ربط و بی ارزش را هم از عبارت جستجو شده توسط کاربر، حذف کند. یعنی برای هر سه جستجوی زیر باید یک جواب برگشت داده شود :

  • وبلاگهای راجع به مهندسی داده
  • وبلاگ مهندسی داده
  • وبلاگ های حوزه مهندسی داده

یکی دیگر از اجزای این سامانه ها، تطبیق جواب ها با کاربر است به گونه ای که با داشتن اطلاعات کاربر و اینکه در دفعات قبل روی کدام نتایج  کلیک کرده است.نتایج دقیق تری را به او ارائه کنند که مباحثی از این دست جزء هوش مصنوعی و یادگیری ماشین در حوزه متن کاوی است .

در ادامه مقاله قصد طراحی یک سیستم بازیابی اطلاعات را برای یک کتابخانه با هزاران کتاب داریم و می خواهیم سیستمی طراحی کنیم که جوابگوی پرس و جوهای مختلف کاربران باشیم و نزدیکترین کتاب را به پرس و جوی کاربر به او نمایش دهیم . البته این ایده را برای صفحات وب، محصولات یک فروشگاه و … هم می توانیم اعمال کنیم . در این کتابخانه کتابهای شماره یک تا پنج عناوین زیر را دارند :

  1. Analytics and Big-Data
  2. The Hanging Tree
  3. Broken Dreams
  4. Blessed kid
  5. Girl with a Dragon Tattoo

جدول تکرار کلمات (TF : Term Frequency)

روش اصلی یافتن صفحات مرتبط با یک جستجو، روش سنجش  تعداد تکرار (TF) یک کلمه است . هر چه که یک کلمه در یک صفحه بیشتر تکرار شده باشد، آن صفحه ارتباط بیشتری با آن کلمه دارد بنابراین اگر کاربر کلمه ای را جستجو کرد، صفحاتی را نمایش خواهیم داد که آن کلمه در آنها بیشتر تکرار شده  باشد.

جدول زیر تعداد تکرار مجموعه ای از کلمات را در پنج صفحه مختلف وب نشان می دهد که زیر هر کلمه، تعداد تکرار آن را در کتاب متناظر آن سطر آورده شده است :

table1

اگر لغت X‌ در صفحه A‌ یک بار و در صفحه B ده بار تکرار شده باشد الزاماً به معنای آن نیست که ارتباط  صفحه B با لغت X  ده برابر بیشتر از صفحه A‌ است . یعنی تعداد تکرار کلمات به صورت خام ملاک دقیقی نیست و گاهی مثلاً در یک کتاب یا متن طولانی کلمات به صورت طبیعی بیشتر تکرار می شوند اما بیشتر بودن یک لغت، به خاطر ارتباط بیشتر آن با یک کتاب نیست  بلکه به دلیل طولانی بودن کتاب یا صفحه است .

بنابراین باید تا حدودی این عدد خام تکرار را نرمال کرد تا عددی که ملاک سنجش یک کتاب با کتاب دیگر باشد، درجه اطمینان بیشتری داشته باشد. معمولاً از فرمول های لگاریتمی برای این موضوع استفاده می کنند. فرمول زیر از جمله آنهاست :

1
2
TF = 1 + log (TF)   if  TF > 0
0             if TF = 0

البته این فرمول بسته به نیاز و ماهیت کار قابل تغییر خواهد بود. با فرمول بالا مجدداً جدول قبل را محاسبه می کنیم :

table2

با در نظر گرفتن جدول بالا و عبارت « Book for Analytics newbie » میزان مرتبط بودن یک صفحه با با آن به صورت زیر محاسبه خواهد شد :

1
2
3
4
5
Document 1 : 1.7 + 3.1 + 2.8 + 1 = 8.6
Document 2 :2.3 + 3.0 + 0 + 27.3
Document 3 : 2.5 + 3.0 + 0 + 2 = 7.5
Document 4 : 2.6 + 3.0 + 0 + 2.3 = 7.9
Document 5 : 2.3 + 3.0 + 0 + 2.5 = 7.8

با این محاسبات، کتاب یک به عنوان اولین جواب و مربوط ترین نتیجه باید به کاربر نمایش داده شود اما هنوز نمی توان با قطعیت این حرف را زد. شاید کتاب ۵ و ۴ هم که امتیاز بالایی دارند، کتاب های مربوطی باشند و حتی از دید کاربر ، مناسب تر و بهتر از کتاب اول به نظر برسند. در این صورت،‌اشکال کار از کجا ممکن است باشد؟ ایراد کار این است که ما تعداد تکرار را در هر کتاب به صورت مستقل نگاه کرده ایم و به تکرار آن در بقیه صفحات کاری نداشته ایم .

اگر لغتی در چند کتاب ، زیاد تکرار شده باشد پس به احتمال زیاد یک لغت عمومی و کم ارزش است مثل لغت باید و اگر  که در بسیاری از صفحات هستند و از لحاظ سامانه های بازیابی اطلاعات ارزش خاصی ندارند. از طرفی اگر یک لغت در یک کتاب چندین بار تکرار شده باشد و در بقیه کتابها تکرار نشده باشد یا تعداد تکرار محدودی داشته باشد، پس لغت ارزشمندی است مثلاً عبارت کلان داده یک عبارت بسیار کم تکرار است و اگر در کتابی چندین بار به کار رفته باشد به احتمال زیاد آن کتاب باید مربوط به کلان داده باشد.

بنابراین نیاز به اطلاعات تکرار کلمه در سایر صفحات هم داریم که بتوانیم تصمیم دقیق تری بگیریم .

جدول معکوس تکرار در صفحات (IDF)

به ازای هر لغت، باید فرمولی را استفاده کنیم که هر چه تکرار یک لغت در یک کتاب کمتر باشد، به آن امتیاز بیشتری بدهد (رابطه معکوس) مثلاً می توانیم از فرمول N/DF استفاده کنیم که N تعداد کل کتابها و DF تعداد کتابهای حاوی آن لغت است . با این فرمول هر چه یک لغت کمتر تکرار شده باشد، عدد بزرگتری تولید می شود. برای این که این عدد را هم نرمال و اثر اشتباهات محاسباتی را کمتر کنیم از لگاریتم آن استفاده می کنیم که همان اثر قبلی را هم دارد یعنی لغت کم تکرار، امتیاز بیشتری می گیرد اما خیلی به تعداد دقیق کلمات و صفحات حساس نیست (لگاریتم عدد اصلی ) بنابراین داریم :

1
IDF = Log(N/DF)

جدول TF-IDF

با داشتن جدول TF ‌و IDF ، می توانیم مرتبط بودن یک لغت با یک صفحه را با ضرب این دو در هم نمایش دهیم :

میزان ارتباط لغت با یک صفحه  = TF * IDF

یعنی هر چه یک لغت در یک متن بیشتر به کار رفته باشد و در سایر کتابها هم خیلی کم به کار رفته باشد، امتیاز آن صفحه برای آن لغت بیشتر می شود که منطقی هم به نظر می رسد.

حال مجدداً برای عبارت Book for Analytics newbie محاسبات نهایی را انجام می دهیم :

TFIDF

که همانطور که مشخص می است کتاب اول، بیشترین ارتباط را با جستجوی کاربر دارد.

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

متولد ۱۳۵۹ ، کارشناس نرم افزار دانشگاه تهران و ارشد نرم افزار دانشگاه تربیت مدرس و عضو هیأت علمی دانشگاه بزرگمهر قائنات
علاقه مند به برنامه نویسی ، مهندسی نرم افزار و به طورخاص حوزه پردازش داده و زیرحوزه کلان داده که تجربه کار عملی با اکثر بانکهای اطلاعاتی نوین (نو اسکیو ال) را در کارنامه خود دارد. وب سایت فودلیست که جزء کارهای اخیر تحت مدیریت نامبرده است، در جشنواره وب ۹۳ در حوزه صنایع غذایی کشور، تندیس وبسایت برگزیده را از آن خود کرد.

یک نظر

  1. با سلام واحترام

    و تشکر فراوان از زحمات شما – مطالب کلی سایت علاقه زیادی را در من ایجاد کرده تا در زمینه Big Data  و مهندسی داده شروع به فعالیت و اگر خداوند توانایی دهد تحقیق نمایم.

    بنده حقیر جهت ارائه در محیط داشگاهی از مطلب فوق قصد استفاده را دارم لطفا حلال فرمائید و اجازه ارائه ملب فوق را به بنده حقیر دهید

    التماس دعا

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Time limit is exhausted. Please reload CAPTCHA.