بخشی از مقاله
چکیده
خزشگر یکی از اصلیترین بخشهای یک موتور جستجو میباشد که وظیفهی آن کشف و دانلود صفحات وب است. هیچ موتور جستجویی نمیتواند کل وب را پوشش دهد و تنها به درصدی از صفحات با ارزش بالاتر اکتفا میکند؛ بنابراین چالش اصلی در موتورهای جستجو خزش صفحات مؤثر وب در سریعترین زمان ممکن است. در این مقاله جهت پوشش مناسب صفحات وب - پیدا کردن سریع صفحات مهم - ، الگوریتم خزشی مبتنی بر یادگیری تقویتی ارائه میگردد. سیگنال تقویتی براساس تابعی از درجه خروجی هر صفحه تعریف میشود و ارزش هر صفحه برابر مجموع تخفیف یافتهی جوایز دریافتی در گذر از صفحات وب تا رسیدن به صفحهی جاری است. جهت ارزیابی الگوریتم پیشنهادی از گراف وب ایران استفاده شده است. نتایج آزمایشها نشان میدهد که روش پیشنهادی روی گراف مذکور نسبت به سایر روشهای بررسی شده کاراتر است..
مقدمه
امروزه وب جهان گستر به عنوان بهترین محیط برای تولید اطلاعات، انتشار و دسترسی به دانش مورد نیاز کاربران تبدیل شده است، اما محیط وب از پویایی بالایی برخوردار بوده و از لحاظ ساختار و محتوا در حال رشد میباشد. هر روز حدود %8 صفحه جدید ساخته میشود و در یک سال %80 صفحات ناپدید میشوند، در هر هفته %25 پیوند جدید ساخته میشود و در یک سال %80 پیوندها ناپدید میشوند .[2] یکی از اصلیترین بخشهای یک موتور جستجو خزشگر1 میباشد.
خزشگر برنامهای است برای دانلود کردن بخش عمدهای از صفحات وب [3]، به این صورت که مجموعهای از صفحات وب را به عنوان ورودی دریافت کرده - صفحات ریشه - و لینکهای خروجی صفحات را بهعنوان خروجی استخراج میکند و بر اساس یک معیار خاص لینکی که در مرحلهی بعد باید ملاقات شود را مشخص میکند. اکثر خزشگرها به سه دلیل پر هزینه بودن پهنای باند [4] ، محدود بودن فضای ذخیرهسازی [5] و حفظ تازگی صفحات نمایه شده نمیتوانند تمام صفحات موجود در وب را بار گذاری کنند.
این آمارها حاکی از حیاتی بودن دقت موتورهای جستجو در پیدا کردن صفحات مهم در کوتاهترین زمان ممکن است. الگوریتمهای خزش معمولاً از یک مکانیزم رتبهدهی در حین خزش جهت تعیین اولویت صفحات برای بارگذاری استفاده میکنند .[1] به عبارتی دیگر یک مکانیزم رتبهدهی بر گراف ناقصی که در حین فرآیند خزش ایجاد شده است اعمال میشود و براساس آن اولویت صفحات مشخص میگردد. در این مقاله به منظور پیادهسازی روش پیشنهادی از روش رتبهبندی 2RL-Rank استفاده میشود. روش پیشنهادی 3RL-Crawler نامیده شد. در بخش بعد کارهای مرتبط گذشته مرور میشود. بخش 3 به معرفی روش پیشنهادی میپردازد و نهایتاً در بخش 4 نتیجهگیری و کارهای آینده گفته خواهد شد.
پیشینه و کارهای مرتبط
به دلیل حجم زیاد و پویایی اطلاعات در وب کشف صفحات مهم از اهمیت ویژهای برخوردار است. در بخش خزش موتور جستجو مسئلهی مهم ارزشگذاری صفحات است تا براساس آن صفحات برای بارگذاری انتخاب شوند. در حوزه بازیابی اطلاعات وب روشهای زیادی جهت خزش ارائه شدهاند که در ادامه تعدادی از مهمترین و کاراترین آنها مورد بحث قرار میگیرد. در [4] از الگوریتم عرض اول بهعنوان یک الگوریتم خزش استفاده شده است.
در این الگوریتم پس از تعیین صفحهی هسته کلیهی صفحات هم عمق با یکدیگر مشخص میشوند و پس از رجوع به کلیهی صفحات موجود در آن سطح، سطح دوم مورد بررسی قرار میگیرد. درواقع خزشگر در الگوریتم عرض اول از ریشه شروع و گراف را بهصورت درختی - سطح به سطح - پیمایش میکند. بهطوریکه فاصله صفحات بارگذاری شده از ریشه همیشه کمتر یا مساوی صفحات بارگذاری نشده میباشد.
الگوریتم PageRank روش رتبهبندی مشهوری است که موتور جستجوی گوگل برای تعیین اهمیت صفحات وب از آن استفاده میکند. در این الگوریتم هر لینک بر اساس اهمیت سندی که از آن منتشر شده و تعداد لینکهای خروجی آن سند وزن دهی میشود. ایدهی الگوریتم PageRank بر مبنای قدم زدن تصادفی است که مدل موجسوار تصادفی نامیده میشود .[6] در مدل موجسوار تصادفی کاربران بر روی لینکهای صفحات ملاقات شده بهطور تصادفی کلیک میکنند.
در این روش اگر خزشگر به صفحهای برود که لینک خروجی نداشته باشد بهصورت تصادفی به صفحهی دیگری پرش میکند در واقع فرض میشود که کاربر یا لینک صفحهی جاری را دنبال میکند یا به یک صفحهی تصادفی در گراف وب پرش میکند. در این رابطه n تعداد کل صفحات وب را نشان میدهد. O - j - بیانگر تعداد لینکهای خروجی صفحه j و B - p - مجموعه صفحاتی است که به p اشاره میکنند. از پارامتر d، ضریب استهلاک، به منظور تضمین همگرایی الگوریتم PageRank و از بین بردن تأثیر صفحات بدون ورودی و خروجی و یا اصطلاحاً صفحات چاهک استفاده میشود.
در [7] مقایسهای بین الگوریتمهای PageRank، درجه ورودی و عرض-اول انجام شده است. آنها به این نتیجه رسیدند که الگوریتم خزش مبتنی بر PageRank صفحات مهمتر را سریعتر از دو الگوریتم دیگر پیدا میکند. الگوریتم 4OPIC جز الگوریتمهای خزش برخط میباشد. نحوهی کار این الگوریتم به این صورت است که در شروع خزش کلیهی صفحات دارای اعتبار یکساناند و با انتخاب یک صفحه جهت بارگذاری اعتبار آن بین فرزندانش بهصورت مساوی تقسیم میگردد .[8] مزیتی که به روش PageRank دارد سرعت بالای آن در اجرا است.
زارع بیدکی و یزدانی [9] یک الگوریتم خزش هوشمند مبتنی بر یادگیری تقویتی5 با عنوان 6FICA معرفی کردهاند. الگوریتم FICA همانند روش عرض-اول با تعریف جدید فاصله عمل میکند. تعریف: 1 اگر صفحهی i به صفحهی j اشاره کند وزن پیوند میان i و j برابر است با logO - i - که O - i - نشاندهندهی درجه خروجی صفحهی i میباشد. تعریف:2 فاصلهی لگاریتمی میان i و j عبارت است از وزن کوتاهترین مسیر میان آنها - جمع وزنهای پیوندهای در مسیر - که با dij نشان داده میشود. در شکل 1 به ترتیب وزنهای پیوندهای خروجی در صفحات p، q و s مساوی log2، log3 و log4 میباشد. فاصلهی میان دو صفحهی p و t برابر log2+log3 و همچنین فاصلهی میان v و p برابر log2+log2 خواهد بود؛ بنابراین گرچه t و v در یک سطح از p هستند - دو کلیک - ولی v به p نزدیکتر است.
نرخ یادگیری7، djt+1 فاصلهی صفحهی j در زمان t+1 و dit و djt به ترتیب نشاندهندهی فاصلهی صفحهی i و j در زمان t میباشند. در این محیط هدف کمینه کردن جمع توبیخهای دریافتی میباشد. نرخ یادگیری با استفاده از رابطه 3 محاسبه میشود که t زمان - شماره تکرار - است و ثابت جهت تنظیم نرخ یادگیری استفاده میشود. آزمایشهای انجامشده نشان میدهد که در صورت تنظیم مناسب ، سیستم بازدهی بالاتری خواهد داشت. در ابتدا به علت نداشتن مقدار فاصلهی هیچکدام از صفحات، مساوی یک بوده و با گذشت زمان بهصورت نمایی-نزولی به صفر میل میکند .[11]
از t برای برقراری تعادل بین دانش بهدست آمده توسط عامل خزشگر و ویژگی ساختاری وب استفاده میشود. فاکتور بالانس به عامل خزشگر در سیاست انتخاب صفحه بخصوص در مراحل اولیه خزش کمک میکند؛ بنابراین در مراحل اولیهی خزش که عامل هیچ پسزمینهای راجع به ساختار وب ندارد =1 و t بالاترین مقدار خودش را دارد. با گذشت زمان عامل دانش بیشتری دربارهی محیط کسب کرده، بنابراین t بهصورت خطی کاهش مییابد بهطوریکه در مراحل پایانی خزش که عامل خزشگر تقریباً دانش کاملی از محیط به دست آورده t به صفر میرسد .[10] آزمایشها نشان داده است که اگر مقدار اولیه t در دامنه [0.35,0.45] قرار داشته باشد، الگوریتم FICA بهترین کارایی را خواهد داشت .
-2-2 الگوریتم DistanceRank
در [12] الگوریتمی مبتنی بر یادگیری تقویتی به نام DistanceRank معرفی شده است و از فاصله لگاریتمی میان صفحات استفاده کرده است. با توجه به آنکه اساس الگوریتم یادگیری تقویتی بر مبنای جایزه و توبیخ است در این روش فاصله لگاریتمی بین صفحات بهعنوان توبیخ دریافتی استفاده میشود . هدف روش ارائه شده، کمینه کردن کل توبیخهای دریافتی است، در واقع صفحهای که فاصله آن کمتر است رتبهی بالاتری دارد.
