الگوریتم محاسبه امتیاز در Elasticsearch

الگوریتم محاسبه امتیاز در Elasticsearch

در قسمت قبل دیدیم که کوئری‌های جستجو از دو نظر قابل تقسیم‌بندی هستند:

  • از نظر ساختار (structure): کوئری‌های جستجوی در Elasticsearch ممکن است از نوع leaf query باشند که یک کوئری مستقل بوده و یا ممکن است از نوع compound query باشند که یک کوئری ترکیبی شامل یک یا چند کوئری دیگر درون خود است.
  • از نظر زمینه عملکرد (context): با توجه به اینکه برخی از کوئری‌های جستجو در Elasticsearch علاوه بر یافتن موارد تطبیق‌یافته با عبارت مورد جستجو، کیفیت ارتباط نتایج را نیز اندازه‌گیری می‌کنند، این مساله مطرح است که یک کوئری را بتوان در قالب filter context اجرا کرد تا فقط پاسخگوی تطبیق یا عدم تطبیق باشد و یا اینکه در query context اجرا کرد تا علاوه بر تطبیق داده‌ها، امتیاز میزان ارتباط آن‌ها را نیز محاسبه کند.

حال در این قسمت آموزشی قصد داریم روش محاسبه امتیاز و فاکتور‌های تاثیرگذار در آن را با هم بررسی کنیم.

Elasticsearch تا قبل از نسخه‌ی 5 از الگوریتم TF-IDF برای محاسبه‌ی امتیاز و رتبه‌بندی نتایج جستجو استفاده می‌کرد. این الگوریتم تحت تاثیر 2 فاکتور عمل می‌کند:

  • تعداد تکرار term در document: الگوریتم TF-IDF برای تشخیص میزان ارتباط بیشتر، تکرار بیشتر term در document را مدنظر قرار می‌دهد. هرچه تعداد تکرار در document بیشتر، آن document مرتبط‌تر!
  • تعداد تکرار term در کل document های موجود در index های مورد جستجو: به دلیل اینکه برخی کلماتِ عمومی ممکن است تعداد تکرار بالایی داشته باشند اما اهمیت آن‌ها پایین باشد (مانند کلمات بی‌اثر یا همان Stop words)، این الگوریتم فاکتور تکرار بالای کلمات در کل مجموعه document ها را به عنوان یک عامل منفی برای اهمیت در نظر می‌گیرد و به طور خلاصه به کمیاب (rare) بودن term در کل مجموعه‌ی هدف اهمیت بیشتری می‌دهد.

با توجه به دو فاکتور بالا در صورتی که یک term به تعداد زیاد در یک document تکرار شده باشد (بدون محدودیت!) و در کل مجموعه‌ی مورد جستجو هم به نسبت کمتری تکرار شده باشد (نسبت به تعداد کل document ها)، طبق این الگوریتم امتیاز بالاتری خواهد گرفت.

اما معایب این الگوریتم چیست:

  1. document هایی که شامل متن‌های طولانی‌تر باشند به صورت ضمنی شانس بیشتری در تکرار یک term در آن‌ها وجود دارد و این باعث تاثیر مثبت در امتیاز خواهد شد در صورتی که ممکن است واقعا میزان ارتباط آن‌ها به نسبت document هایی که متن کوتاه‌تر دارند، بیشتر نباشد!
  2. در مواردی که عبارت مورد جستجو شامل چندینterm  باشد، تمامی term ها به طور یکسان مورد محاسبه قرار خواهند گرفت و زمانی که مجموع امتیاز term ها محاسبه شود ممکن است تاثیر منفی برای سایر term های پراهمیت داشته باشد. برای مثال عبارت "laravel and vuejs" را درنظر بگیرید. ممکن است تنها یک یا دو document در کل مجموعه‌ی هدف شامل هر سه term (laravel | and | vuejs) باشند و به جای اینکه این document ها در صدر نتایج جستجو ظاهر شوند، document هایی امتیاز بالاتر بگیرند که واژه‌ی “and” در آن‌ها تکرار زیادی دارد (طبق فاکتور اول یعنی تکرار بیشتر در document بدون هیچ محدودیتی!). البته که شاید در این مثال فاکتور دوم یعنی کمیاب بودن term، بتواند تا حدودی از اهمیت واژه‌ی “and” بکاهد اما به هرحال میزان زیادی هم فاکتور اول تاثیر مثبت خواهد داشت که این تاثیر مثبت مطلوب نخواهد بود.

به همین دلایل Elasticsearch از نسخه‎ی 5 به بعد، از الگوریتم BM25 به عنوان الگوریتم پیش‌فرض در محاسبه‌ی امتیاز ارتباط استفاده کرده است. این الگوریتم بر مبنای همان الگوریتم TF-IDF رفتار می‌کند اما فاکتور‌های دیگری را نیز در محاسبه‌ی امتیاز دخالت می‌دهد که باعث بهبود رفتار TF-IDF شده است. علاوه بر دو فاکتور قبلی، فاکتور‌های زیر نیز در این الگوریتم موثر هستند:

  • چگالی(saturation) term در document: در TF-IDF دیدیم که هرچه تکرار term در document بیشتر باشد، اهمیت آن بالاتر در نظر گرفته می‌شود، اما هیچ محدوده‌ای برای آن درنظر گرفته نشده بود. یعنی اگر در یک document 20 بار کلمه‌ی "sokanacademy" تکرار شده باشد آیا اهمیت آن دو برابر document ای است که 10 بار کلمه‌ی “sokanacademy” در آن تکرار شده است؟!

در BM25 چگالی یک term به عنوان فاکتور محدودکننده برای تاثیر مثبت درنظر گرفته می‌شود و شیب افزایش اهمیت term در اثر تکرار بیشتر در یک document، نزولی خواهد بود!

  • طول متن در document: فاکتور دیگری که در TF-IDF نادیده گرفته شده بود، طول متنی است که term در آن قرار گرفته است. برای مثال اگر کلمه‌ی DevOps یک بار در یک متن با طول 100 تکرار شده باشد نسبت به 1 بار تکرار آن در متنی با طول 400 اهمیت بالاتری دارد و نشان‌دهنده‌ی ارتباط بیشتر متن 100 کاراکتری با این کلمه دارد. در BM25 طول متن مورد نظر نسبت به میانگین طول متن‌ها در کل مجموعه‌ی document ها مقایسه شده و هر چه از میانگین کمتر باشد تاثیر مثبت و هرچه بلندتر از میانگین باشد تاثیر منفی در امتیاز خواهد داشت.
نکته: الگوریتم BM25 در فرمول خود شامل دو پارامتر (k و b) است که قابل تنظیم بوده و می‌توانند بر شدت عملکرد دو فاکتور بالا یعنی چگالی term در document و طول متن document تاثیرگذار باشند. البته این پارامتر‌ها در Elasticsearch طبق مطالعات تجربی به صورت پیش‌فرض و در بهینه‌ترین حالت تنظیم شده است و نیازی به تغییر آن‌ها در شرایط استاندارد نخواهد بود.

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