بخشی از مقاله
چکیده
وبجهانگستر روزبهروز در حال گسترش است لذا با توجه به حجم انبوه اطلاعات، کاربران در ساختار وسیع وب سردرگم میشوند و از این رو بازیابی موثر صفحات وب به یک چالش بزرگ تبدیل شده است. در چنین سناریویی وظیفه فراهمکننده سرویس است که اطلاعات مرتبط و با کیفیت برای کاربر مطابق با پرسوجوهای ارائه شدهشان در موتورجستجو فراهم کند. در حال حاضر یکی از مهمترین چالشها پیداکردن صفحاتی با کیفیت بالا میباشد به این منظور از قسمت رتبهبندی موتور-جستجو استفاده میکنیم که باعث مرتبشدن صفحات مبتنی بر کیفیت آنها میشود. در این مقاله ضمن مطالعه روشهای مطرح شده در زمینه رتبهبندی صفحاتوب، روش جدید رتبهبندی با استفاده از رگرسیون بردار پشتیبان ارائه میگردد تامعیارهای کیفی روشهای رتبهبندی را بهبود دهد. در روش پیشنهادیRankSVR ، که یکی از روشهای دستهبندی ماشین بردار پشتیبان است همه ویژگیهای اساسی ماشینهای بردار پشتیبان را به کار میگیرد تا الگوریتم حاشیه بیشینه را توصیف کند و مدلی با دقت بالاتر برای رتبهبندی صفحات وب ارائه کند به گونه ای که با تلفیق یادگیری مبتنی بر تعمیم و متمایز سازی سعی در ساخت مدل بهتری کرده به گونه ای که نسبت به سایر روشهای رتبهبندی عملکرد و دقت بهتری خواهد داشت .
کلمات کلیدی:رتبهبندی صفحات وب، رتبهبندی در یادگیری، رگرسیون بردار پشتیبان
-1 مقدمه
وب جهان گستر، بزرگترین و سریعترین منبع اطلاعاتی شناخته شده در جهان میباشد حجم اطلاعات در وب روز به روز در حال افزایش است. همانطور که میزان اطلاعات موجود روی وب در حال افزایش است به دست آوردن اطلاعات مرتبط با درخواست کاربر دشوار است بنابراین مطالعات بسیاری در زمینه بازیابی اطلاعات انجام گرفته است که یکی از روشهای ارائه شده جهت بازیابی اطلاعات، موتورهای جستجو میباشد. موتورهای جستجو ممکن است میلیونها صفحه در پاسخ به یک پرسوجوی کاربر را بر-گردانند و از آنجائیکه کاربر کم حوصله بوده ، فقط به بررسی 10 تا 20 تای اول آنها میپردازد، رتبهبندی یکی از اجزای اصلی موتورهای جستجو می-باشدکه صفحات را مبتنی بر کیفیت آنها و درخواست کاربر مرتب میکند. با توجه به اینکه به ازای هر پرس و جو کاربر معمولاَ هزاران صفحه مرتبط وجود دارد لازم است آنها را اولویتبندی کرده و بهترینها را به کاربر نشان دهد .
مسائلی مانند حوصله کم کابر، کوتاه بودن طول پرس وجو، حجم زیاد اطلاعات و پویایی وب، فرایند رتبهبندی را با مشکلات مختلفی مانند غنی ترشدن اغنیا - صفحات معروف در صدر لیست نتایج قرار داده میشوند و صفحات تازه ایجاد شده با کیفیت بالا شانس کمتری دارند که توسط کاربر انتخاب شوند - ، به روز نبودن اطلاعات ارائه شده و همچنین دقت پایین مواجه میسازد . تکنیکهای رتبهبندی وب سایت ها بایستی سعی کنند تا بر این مشکلات فائق آیند. از این رو الگوریتمهای رتبهبندی در موتورهای جستجو حائز اهمیت است . به طور وسیع الگوریتمهای رتبهبندی صفحه میتوانند در دو گروه دستهبندی شوند، رتبهبندی صفحه بر اساس محتوا و رتبهبندی صفحه بر اساس اتصال.در رتبهبندی مبتنی بر محتوا برای هر پرسوجو،سندها با مشابه ترین محتوا به پرس و جو انتخاب خواهند شد.
جهت رتبهبندی اسناد بر مبنای محتوای آنها، مدل هایی مانند مدل بولی، احتمالی و فضای برداری ارائه شده است . مهم ترین این روشها در مدل برداری، الگوریتم TF-IDF و در مدل احتمالی،الگوریتم BM25 می باشد. عیب روشهای مبتنی بر محتوا پهنش رتبه1 میباشد، به علت آنکه این روشها مبتنی بر محتوا هستند و احتمال اینکه صفحات متناقص و شامل اطلاعات غلط باشد وجود دارد، به این معنا که صفحاتی که توسط این الگوریتمها بازگردانده شدهاند ممکن است مرتبط با پرسش کاربر باشند اما صفحات مرتبط و معروفی نباشند. برای رفع این مشکل رتبهبندی مبتنی بر اتصال مطرح شدند1]،. [2 این نوع از رتبهبندی بر اساس تحلیل پیوند کار میکند. آنها وب را به عنوان گراف مستقیم میبینند که صفحات وب و اسناد نودها را تشکیل میدهندو ابرپیوندهابین صفحات وب یالهای مستقیم بین این نودها را تشکیل می دهند[3,4] این ساختار گراف مستقیم به عنوان گراف وب شناخته شده است. [5 ]
در نگاه کلی الگوریتمهای مبتنی بر اتصال، به دو دسته وابسته به پرس-وجو و مستقل از پرسوجو تقسیم میشوند. در روشهای مستقل از پرسوجو مانند PageRank ، HostRank ،DistanceRank ، رتبهبندی به صورت برون خط انجام می شود و همچنین از کل گراف وب استفاده میکند، بنابراین رتبه هر صفحه به ازای هر پرسوجو ثابت میباشد، اما در روش وابسته به پرسوجو یا حساس به موضوع مانند HITS2 ، رتبهبندی به صورت برخط و در گراف شامل مجموعه صفحات مرتبط با پرسو جوی کاربر انجام می-شود5,6]،.[7به علت مشکلات موجود در روشهای مبتنی برمحتوا و اتصال، روشهای ترکیبی مورد توجه قرار گرفت که مهمترین مشکل این الگوریتم بر خط بودن میباشد که منجر به کم شدن سرعت سیستم در پاسخ کاربرمی-شود.برای رفع این مشکل مسئله یادگیری در رتبهبندی مطرح شد.
الگوریتمهای یادگیری در رتبهبندی انواع مختلفی دارد از جمله AdaRank،AdaBoost ، Frank ، RankSvm ، Listnet ،Ranknet و ...الگوریتم AdaRank این الگوریتم توسط آقای جان زو3 و همکاران ابداع شد که می تواند افت عملکرد را بر اساس سنجش عملکرد بازیابی اطلاعات بهینه کند همچنین از روش لیستی در مسئله رتبهبندی استفاده میکند و سعی میکند تابع زیان را که به طور مستقیم روی سنجش عملکرد تعریف شده است را کاهش دهد.[8]الگوریتم Listnet این الگوریتم توسط آقای جی کاو4 و همکاران ارائه گردید. Listnet روش لیستی مبتنی بر یادگیری می باشد که یک تابع احتمالی هزینه را بر اساس لیست اشیا، تعریف میکندو مدل پیشبینی لیست را به کمک روشهای یادگیری شبکه عصبی ارائه میدهد .[9]الگوریتم Regressionاین الگوریتم یک روش آماری برای تخمین ارتباط بین متغیرها است که توسط جک سوزیک5 ارائه شد . این الگوریتم شامل تعداد زیادی روش برای مدل سازی و تحلیل چندین متغیر میباشد.
در حالیکه تمرکز آن بر روی ارتباط بین یک متغیر وابسته و یک یا چند متغیر غیر مرتبط می باشد .[10]الگوریتم Frank این الگوریتم توسط آقای مینگ فینگ سای6 و همکاران ارائه شد که یکی از روشهای جفتی مبتنی بر یادگیری میباشد که بر اساس یک مدل جمعی تعمیم یافته به منظور حداقل کردن از دست دادن وفاداری - وفادارای زیان - و یادگیری یک تابع رتبهبندی موثر ارائه شده است.[11]الگوریتم RankSvmاین الگوریتم توسط آٌقای تورسن جوکیمز 7ارائه شده است که یک روش رتبهبندی جفتی میباشد که یک مدل رتبهبندی را با به حداقل رساندن خطای جفتی8 مبتنی برحاشیه متقارن شکل میدهد13]،.[ 12 از نقطه نظر ریاضیات روش مبتنی بر طراحی بردارها داده ورودی را در فضایی با ابعاد بزرگتر نگاشت میکند . مهمترین مزیت این روش تشخیص موثر توابع جداگانه غیر خطی در زمینه مسئله طبقهبندی است .الگوریتم رتبهبندی RankSvm یک روش جفتی میباشد که از ابزار ماشین بردار پشتیبان برای دستهبندی اشیا استفاده میکند و مسئله رتبهبندی در این حالت به یک مسئله دستهبندی دوتایی کاهش مییابد.
معایب این روش عبارتند از:
-نتیجه، دستهبندی دوتایی است که شامل هیچ اطلاعاتی در مورد درجه ارتباط اشیاء نمیباشد.
-حساسیت زیادی نسبت به دادههای نادرست در مجموعه آموزشی دارد که این حساسیت به طور منفی در کیفیت نتایج اثر میگذارد.
-وابسته بودن سرعت اجرا به اندازه دادههای ورودی و حتی وابسته بودن به نوع تابع هسته .[14]
به علت مشکلات فوق که در الگوریتم RankSvm موجود میباشد ما را بر این داشت تا در این مقاله با استفاده از رگرسیون بردار پشتیبان9، روش رتبهبندی جدیدی به نام" رتبهبندی بر اساس رگرسیون بردار پشتیبان " را جهت برطرف نمودن نقاط ضعف بالا پیشنهاد دهیم .
-2مطالب اصلی
یکی از روشهای رتبهبندی صفحات وب که در سالهای اخیرمورد استقبال واقع شده است، ماشین بردار پشتیبان10 میباشد که به طور گسترده در داده کاوی و جوامع یادگیری معمولاَ برای طبقه بندی یادگیری، رگرسیون یا توابع رتبه بندی استفاده میشود . ماشین بردار پشتیبان در سال 1963 توسط ولادیمیر واپنیک11 ابداع شدو در سال 1995 توسط واپنیک و همکاران برای حالت غیر خطی تعمیم داده شد. فرم اولیهی SVM، یک کلاسبندباینری است که خروجی تابع یادگیرنده یا مثبت است یا منفی . وظیفهی آن پیداکردن یک جداکنندهی خطی بهینه - ابرصفحهای - میباشد که بیشترین حاشیه را دارد. حاشیه عبارت است از جمع کوتاهترین فاصله از ابرصفحهی جداکننده به نزدیکترین نقطه داده از هر صفحه.[15]
به طور کلی فرایند یادگیری شامل دو مرحله آموزش و آزمون است. یادگیری در رتبهبندی برای آموزش، روش یادگیری ماشین استفاده شده است که می تواند ارتباط بین اسناد مرتبط در زمینه پرس و جوی مشخص کاربر را کشف کند و آنها را مطابق با ارتباطشان مکان دهی کند. در آموزش هم پرس وجو و هم اسناد فراهم شده است هر پرس و جو با لیست رتبهبندی کاملی از اسناد در ارتباط است. [16 ]یادگیری در رتبه بندی به سه دسته تقسیم میشود: روش نقطه ای12، روش جفتی13 و روش لیستی.14این مدل به وسیله رگرسیون بردار پشتیبان فقط به مجموعه داده آموزشی وابسته است زیرا تابع هزینه برای ساخت مدل از هرگونه داده آموزشی که آن را مسدود کند صرفنظر میکند. رگرسیون بردار پشتیبان به جای کاهش خطای آموزشی مشاهده شده تلاش میکندمحدوده خطای کلی را کاهش دهد به طوریکه به یک کارایی کلی و تعمیم یافته دست یابد.
ایده رگرسیون بردار پشتیبان بر اساس محاسبه تابع رگرسیون خطی در یک فضای ویژگی با ابعاد بالاست که داده ورودی از طریق تابع غیر خطی نگاشت شده است.رگرسیون بردار پشتیبان در زمینههای مختلفی از جمله سریهای زمانی وپیشبینیهای مالی، تخمین تحلیلهای مهندسی پیچیده، برنامهریزی درجه دوم محدب، انتخاب توابع زیان و غیره کاربرد دارد16]،. [17 با توجه به مطالعات انجام شده، الگوریتم ماشین بردار پشتیبان اگرچه قابل تعمیم برای اکثر مسائل است، ولی عملکرد آن وابسته به انتخاب هسته بوده و سرعت اجرای آن وابسته به اندازهی دادگان میباشد. از این رو برای حل مسائل با سایز بزرگ، خیلی کاربردی نمیباشند، همچنین در الگوریتم ماشین بردار پشتیبان، پیچیدگی زمانی زیاد میباشد و نیاز به حافظهی زیادی دارد، به علاوه دادهها بایستی گسسته باشند.
با توجه به بررسیهای انجام شده بر روی مقالات و پژوهشهای صورت گرفته در سالیان اخیر، تنها از الگوریتمهای مبتنی بر تعمیم استفاده شده است که امکان تقویت آموزش با آموزش نمونههای بیشتر و نیز تضعیف آن با در نظر گرفتن جریمه فراهم است.الگوریتمهای مبتنی بر تعمیم، توزیع کلاسهای منحصر به فرد را طراحی میکندو معمولاَ انعطافپذیرتر از مدل-های مبتنی بر متمایز سازی در بیان وابستگی در انجام وظایف پیچیده است. در مقابل، الگوریتمهای مبتنی بر متمایز سازی مانند الگوریتم ماشین بردار پشتیبان مرز بین کلاسها را مشخص میکند و به طور کلی میتواند روابط پیچیدهتری بین متغیرهای مشاهده شده را بیان کند، اما دیدگاه روشنی از روابط بین ویژگیها و کلاسها در مجموعه داده ارائه نمیکنند ولی بر روی مدلسازی مرزها بین کلاسها تمرکز مینماید.در نتیجه یک مدل متمایزسازی ممکن است بازنمایی پیچیدهتری از مرزها نسبت به مدل مبتنی بر تعمیم داشته باشد. [12]
در این مقاله روشی جدید برای رتبهبندی صفحات بر اساس رگرسیون بردار پشتیبان مطرح میشود، که همچنین هر دو معیار مبتنی بر تعمیم و مبتنی بر متمایز سازی را در نظر میگیرد تا از مزایای هر دو گروه را توماَ با هم داشته باشد.در روش پیشنهادی یک مجموعه از جفت های نمونه- هدف { - xi,yi - } را در نظربگیرید ، xiو yi ،1. … . / L ، رگرسیون بردار پشتیبان خطی یک مدل w را پیدا میکند به گونه ای که به مقدار هدف yi نزدیک است. آن مسئله بهینه سازی هدف تنظیم شده زیر را دنبال میکند :در معادله 1، C>0 ، پارامتر تنظیم است به گونه ای که :تابع زیان غیر حساس ε متناظر با - xi.yi - است پارامترε مشخص است به گونه ای که خطا صفر است اگر باشد. ما به رگرسیون بردار پشتیبان با استفاده از فرمولهای 1و 2 رجوع میکنیم، به طوریکه آنها خطای L1 و خطای L2 ، رگرسیون بردار پشتیبان هستند . یک تصویر از دو تابع در شکل 1 نشان داده شده است به طوریکه تابع پیشبینی است .دستهبندی بردار پشتیبان و رگرسیون بردار پشتیبان استاندارد شاملکلمه بایاس - - b هستند به گونهای که تابع پیشبینی است . اخیراَ ما روی دسته بندی خطی مقیاس بزرگ واژه بایاس را حذف کرده ایم زیرا آن در کارایی تاثیر چندانی ندارد.
