بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه يک الگوريتم يادگير مبتني بر خصيصه هاي ذاتي جهت رتبه بندي صفحات وب
چکيده - قبل از پيدايش وب ، سامانه هاي بازيابي اطلاعات براي اسناد استاندارد با ساختار منظم که عموماً بر مبناي کلمه بودند، مورد استفاده قرار مي گرفت . اما با بوجودآمدن وب و ايجاد حجم وسيعي از اطلاعات ، بازيابي اطلاعات با چالش هاي جديدي مواجه شد. در حال حاضر موتورهاي جستجو سامانه هاي بازيابي اطلاعات در وب به حساب می آيند. با توجه به رشد روزافزون اطلاعات و محتواي وب و همچنين تغييرات پويايي اطلاعات ، استفاده از الگوريتم هاي رتبه بندي براي تعيين ترتيب و نتايج مرتبط و دقت نمايش اطلاعات يافت شده به کاربر، اهميت بسيار يافته است .
در اين مقاله جهت پيدا کردن سريع صفحات مهم و با کيفيت ، الگوريتم يادگيري مبتني بر خصيصه هاي صفحات وب ارائه شده است . الگوريتم ارائه شده با اعمال وزن روي خصيصه هاي صفحات و مقايسه وزن اعمال شده با ارزش خصيصه صفحات ، سعي در يافتن رتبه مناسب به منظور دسترسي راحت تر کاربران به صفحات با کيفيت از لحاظ محتويات داخلي شده است . جهت ارزيابي مجموعه داده ايي LETOR بکار برده شده است . نتايج آزمايشات حاکي از آن است که الگوريتم ارائه شده در مقايسه با الگوريتم هاي يادگيري که تاکنون ارائه شده است نتايج قابل توجهي را ارائه ميدهد.
همچنين الگوريتم ارائه شده با الگوريتمBM25 که مبتني بر محتوا است مقايسه ميشود و ميزان اختلاف بين اين دو الگوريتم در رتبه بندي بدست ميآيد، که بسيار مورد توجه است .
کليد واژه - الگوريتم يادگير، رتبه بندي، موتور جستجو، صفحات وب .
١- مقدمه
رتبه بندي، عملي است که نتايج ارائ شده از آن بهترين پيشنهادات از صفحات را براي کاربران به ارمغان ميآورد و همچنين کيفيت يک صفحه توسط رتبه بندي ارائه شده تخمين زده ميشود. بخش رتبه بندي يکي از مهمترين قسمت هاي موتور جستجو ميباشد. برخي از الگوريتم هاي رتبه بندي، مشکلاتي اعم از غنيترشدن اغنيا، پهنش رتبه و ... را به همراه دارند. براي رفع اين مشکلات ، الگوريتم هاي مختلفي ارائه شده است که هر کدام به نوبه خود برخي از مشکلات را از بين برده اند، اما ممکن است مشکلاتي ديگر را براي بخش رتبه بندي فراهم آورند [١،٢].
بسياري از استراتژي هاي رتب بندي نتايج جستجو از الگوريتم PageRank جهت رتبه بندي استفاده مينمايند.
اما به دليل برخي مشکلات اين الگوريتم ، به عنوان مثال ، "مشکل غنيتر شدن اغنيا"١، نميتوان به آن اکتفا نمود.
الگوريتم هاي ديگري نيز براي رتبه بندي صفحات ايجاد شده اند، اما هر کدام از الگوريتم ها مشکلات خاص خود را دارند. برخي از مشکلاتي که موتورهاي جستجو بايد بر آنها فائق آيند، شامل [١-٥].
• مشکلي که براي پيداکردن اسناد مرتبط وجود دارد، مشکل پهنش رتبه ٢ ميباشد. شرکت هاي مختلف براي بالابردن رتبه خود در موتورهاي جستجو، با استفاده از Spammerها سعي در تغييردادن محتواي صفحات و اضافه کردن کلمات کليدي به داخل اسناد، سعي در بالابردن شباهت صفحه خود با پرس وجوي آن حوزه دارند. بدين ترتيب ، با زياد اشاره کردن به يک صفحه وب ، رتبه آن افزايش مييابد. بنابر اين موتورهاي جستجو با ارائه الگوريتم هاي ضد پهنش ، سعي به از بين بردن اين مشکل شده اند. اما انجام اين عمل موتورهاي جستجو، صفحات با کيفيت فدا مي شوند.
• مشکل ديگري که در رتبه بندي بر اساس پيوند وجود دارد، مشکل غنيترشدن اغنيا ميباشد. از آنجا که تجربه ثابت کرده است که کاربران فقط به نتيجه هاي ابتدايي ليست رتبه بندي شده اکتفا ميکنند و همچنين در اين نوع الگوريتم ها صفحات محبوب در صدر ليست ارائه شده به کاربر قرار ميگيرند، لذا اين الگوريتم ها باعث ميشوند که صفحات محبوب ، محبوب تر شده و تعداد پيوند به آنها افزايش يابد و در نتيجه صفحات تازه متولدشده نتوانند موقعيت رتبه بندي بالايي را به دليل تازگيشان و بنابر شهرت کم ، بدست آورند.
که در اين صورت موتورهاي جستجو با ارائه ناعادلانه اطلاعات به کاربران باعث صرف وقت زياد و همچنين کندي روند علم و دانش خواهند شد.
• مشکل ديگري مشخص کردن صفت "مرتبط " در مسئله بازيابي ميباشد که منجر به تلاش زياد موتورهاي جستجو براي رتبه بندي اسناد ميشود.
• کيفيت يک موتور جستجو بستگي به تازگي اسناد و کامل بودن اطلاعات آن دارد. حجم زياد اطلاعات ، مشکلاتي را براي موتور جستجو پديد ميآورد. بروزبودن موتورهاي جستجو براي صفحات تازه متولدشده و صفحاتي با پيوندهاي شکسته با وجود سيل عظيم اطلاعات ديجيتالي، کار دشواري است . بنابر اين موتورهاي جستجو فقط اطلاعات مهم ، با کيفيت بالا را مجبور ميشوند نمايه سازي ٣ کنند.
• مبهم بودن کلمات پرس وجو، مشکل ديگري است که با آن مواجه هستيم . به عبارت ديگر، کاربر نميتواند درخواست خود را در قالب چند کلمه بصورت کامل بيان کند. بنابر اين به علت چند معنيبودن يک کلمه و هم معنيبودن چند کلمه ، نتايج ارائه شده به کاربر مناسب نخواهد بود.
در اين مقاله ، ارائه يک الگوريتم يادگير مبتني بر
خصيصه ها ذاتي صفحات وب به منظور فراه آوردن رتبه بندي با کيفيت بالا پيشنهاد م گردد. الگوريتم ارائه شده به دليل استفاده از خصيصه ها و خصيص ها ذاتي صفحات ، نتيجه با کيفيت تر و کاراتري نشان مي دهد.
ادامه اين مقاله بدين ترتيب سازماندهي ميشود.
کارهاي گذشته در بخش ٢ آمده است . بخش هاي ٣ و ٤ به ترتيب الگوريتم پيشنهادي و ارزيابي کارايي را ارائه مي دهند. بخش آخر نيز نتيجه گيري ميباشد.
٢- کارهاي گذشته
رتبه بندي را م توان به سه دسته الگوريتم هاي مبتني بر محتوا و الگوريتم هاي مبتني بر اتصال و الگوريتم هاي مبتني بر يادگيري تقسيم بندي کرد. الگوريتم هاي مبتني بر محتوا سعي دارند تا با بررسي محتواي صفحه ، ميزان ارتباط آن با پرس وجو را تخمين بزنند. در اين روش ها، مدل هايي مانند بولي، احتمالي و فضايبرداري جهت رتب بندي اسناد بر مبناي محتواي آنها ارائه شده است .
مهمترين اين روش ها در مدل برداري، الگوريتم TF-IDF
[٤] و در مدل احتمالي، الگوريتمBM25 [٥] ميباشد.
الگوريتم هاي مبتني بر اتصال ، با استفاده از گراف وب ، اطلاعات بيشتري در مورد اهميت صفحه استخراج مي نمايند. در اين روش ها، پيوندها، بيان کننده کيفيت محتواي يک صفحه از منظر صفحات بيروني ميباشد. به عبارت ديگر، در رتبه بندي بر مبناي پيوند از محتواي صفحات ديگر براي ارزيابي يک صفحه استفاده ميشود[٦]. اين خاصيت باعث ميشود الگوريتم رتبه بندي با استفاده از اطلاعات استخراجي از پيوندها به مسائلي مانند پهنش حساسيت کمتري نشان دهد. از جمله الگوريتم هاي مبتني بر اتصال را ميتوان PageRank
[٧]، HITS [٨] و HostRank [٩] نام برد. يکي از روش هاي رتبه بندي مبتني بر محتوا، مدل احتمالي ميباشد که اخيراً در بازيابي اطلاعات نتايج چمشگيري داشته است . هدف از مدل ارتباط احتمالي ٤ پيداکردن احتمال وابستگي هر سند به هر پرس وجو ميباشد. به عبارت ديگر، هدف از يک سيستم بازيابي بر مبناي مدل احتمالي، رتبه بندي اسناد با توجه به احتمال مرتب بودن هر سند با پرس وجوي کاربر مي باشد. بنابر اين ، اين مدل به طور قطعي درجه شباهت ميان پرس وجو و سند را پيدا نمي کند. اين مدل از تئوري احتمال [١٠] پيروي ميکند. از بهترين روش هاي احتمالي، روش BM25 ميباشد. در بازيابي اطلاعات ، الگوريتم BM25 تابع رتبه بندي مورد استفاده موتورهاي جستجو براي رتبه بندي اسناد، طبق ارتباط سندها به يک پرس وجوي داده شده است . الگوريتم BM25 تابع بازيابي کلماتي است که مجموعه ايي از اسناد را براساس پرس وجوي موجود در سند، صرف نظر از ارتباط متقابل بين شرايط پرس وجو در يک سند (به عنوان مثال ، نزديکي نسبي آنها)، رتبه بندي ميکند. اين روش احتمالي از بهترين روش هاي رتبه بندي به شمار ميرود که طبق آزمايشات انجام شده داراي دقت بالايي ميباشد.
الگوريتم PageRank يک الگوريتم مستقل از پرس وجوي است . اين الگوريتم براساس تعداد لينک هاي ورودي از يک صفحه با اهميت ، محاسبه ميشود. به عبارت ديگر، اهميت يک سند بالا است ، به شرط اينکه رتبه سندهاي لينک شده به آن بالا باشد. بنابر اين در اين الگوريتم تعداد لينک هاي ورودي براي اندازه گيري يک سند از اهميت بالايي برخوردار است . PageRank يک سند، همواره بطور بازگشتي توسط PageRank صفحات
ديگر محاسبه ميشود.
در الگوريتم WPR5 در [١١] توسعه يافته الگوريتم
PageRank است . Weighted PageRank اهميت لينک هاي ورودي و لينک هاي خروجي صفحات را به حساب ميآورد و امتيازهاي رتبه را مبني بر محبوبيت صفحات توزيع ميکند. اين الگوريتم توانايي شناسايي تعداد بيشتري از صفحات مربوط به يک پرس وجوي داده شده را در مقايسه با PageRank استاندارد دارد. در [١٢] روشي به نام TrustRank براي مقابله با پهنش رتبه ارائه شده است . با توجه به اينکه مشخص کردن همه صفحات مشکل دار (بد) توسط افراد خبره کاري غير ممکن ميباشد، لذا در اين مقاله يک روش نيمه -خودکار براي تشخيص صفحات خوب و بد ارائه شده است . در ابتدا مجموعه اي از صفحات که توسط افراد خبره ارزيابي شده اند به عنوان نقطه شروع انتخاب ميشوند. به دنبال آن با استفاده از ساختار گراف وب و صفحات شروعِ خوب ، بقيه صفحات خوب تشخيص داده ميشوند.
آزمايشات بر روي صفحات جمع آوري شده توسط موتور جستجوي AltaVista در سال ٢٠٠٣ انجام شده است و با انتخاب کمتر از ٢٠٠ سايت به عنوان نقطه شروع ، نتايج قابل توجهي بدست آمده است . الگوريتم فوق در مقايسه با الگوريتم PageRank، صفحات خوب را بهتر تشخيص ميدهد.
الگوريتم هاي ذکرشده ي مبتني بر اتصال ، عمل رتبه بندي را بر مبناي گراف مسطح انجام ميدهند و ساختار سلسله مراتبي وب را ناديده ميگيرند. آنها از دو مشکل عمده رنج ميبرند: پراکندگي زياد صفحات وب و سوگيري نسبت به صفحات قديمي که باعث ميشود صفحات جديد با درجه ورودي کم ، از رتبه ي پاييني برخوردار شوند (غنيترشدن اغنيا). الگوريتم HostRank [٩] که براي فائق آمدن بر دو مشکل فوق ارائه شده است هر دوي ساختار سلسله مراتبي و اتصالي وب را در رتبه بندي لحاظ ميکند. در اين روش صفحات ابتدا در يک ساختار سلسله مراتبيِ دايرکتوري، هاست و يا دامنه که گره برتر ناميده ميشود، قرارداده ميشوند و عمل آناليز اتصال بر روي گراف بدست آمده انجام ميشود.
سپس درجه ي اهميت محاسبه شده ي هر گره بين صفحاتي که آن گره را شامل ميشود، توسط ساختار سلسله مراتبي توزيع مي شود. نتايج آزمايشات روي TREC٠٣ و TREC٠٤ افزايش چشمگيري را نسبت به روش هاي ديگر مبتني بر اتصال مانند PageRank و روش هاي ديگر مبتني بر ساختار سلسله مراتبي نشان ميدهد.
بطور کلي، روش هاي مطرح شده در حوزه رتبه بندي که بر اساس يادگيري عمل ميکنند، به سه دسته اصلي تقسيم بندي ميشوند: روش هاي نقطه اي ٦، روش هاي جفتي ٧ و نيز روش هاي ليستي . در روش هاي نقطه اي، به هر جفت سند-پرس وجو، يک عدد نشان دهنده ميزان ارتباط بين آنها، نسبت داده ميشود. هدف از يادگيري، بدست آوردن مدلي است که بتواند حتيالمقدور به اين جفت ها، مقاديري را نسبت دهد که به ميزان ارتباط واقعي آنها، نزديک باشد. يک نمونه از اين روش ها، الگوريتم Prank است که اين کار را به کمک يک شبکه عصبي از نوع پرسپترون انجام ميدهد[١٣]. در روش هاي جفتي، با دريافت خصيصه هاي اسناد و نيز رتبه نسبي آنها، تلاش ميشود به هر دخادصه يصشه و،دروتببه ايين حتترتيي اب لمقندهاويرتاًبه خرصتبيه صه اهقاعيد اش دوندسسبتت کلي" بصورت صحيح رتبه بندي شده " و" بصورت نادرست رتبه بندي شده "، طبقه بندي ميشوند. شايان ذکر است که اغلب روش هاي موجود رتبه بندي مبتني بر يادگيري از اين نوع هستند. به عنوان مثال ميتوان به روش هايRanking SVM [١٤] و RankBoost [١٥]
اشاره کرد. در Ranking SVM از ابزار SVM٩ براي طبقه بندي جفت هاي اشياء در کران هاي اصلي استفاده ميشود. الگوريتم RankBoost از روش هايBoosting براي يافتن رتبه بندي ترکيبي استفاده ميکند تا جفت هايي را که بصورت اشتباه رتبه بندي شده اند را کمينه کند.
٣- روش پيشنهادي
الگوريتم پيشنهادي با استفاده از رابطه نسبي جفت خصيصه ها و استفاده از عملگر 10OWA، ميتوان به بردار وزن دار مناسب به منظور رتبه بندي صفحات وب دست پيدا کرد. تابع بدست آمده ، درجه ارتباط پرس وجو و سند را نشان ميدهد. روش ارائه شده سوگيري به تعداد پرس وجوها نداشته و در هر تکرار جفت سند از پرس وجوي مختلف را استفاده ميکند. معماري الگوريتم پيشنهادي در شکل (١) ارائه شده است . به صورت رسمي، تجميع ١١ عبارتست از تجميع يک n-تايي از اشياء عضو مجموعه اي خاص به يک شي از همان مجموعه . عملگر تجميع تابعي است که يک n-تايي از اعداد حقيقي مثل را به يک عدد حقيقي چون y ، نسبت ميدهد:
در سال ١٩٨٨ توسط آقاي ياگر، انواع جديدي از عملگرهاي تجميع موسوم به عملگرهاي ميانگين گيري مرتب وزن دار معرفي شد[١٦]. عملگر ميانگين گيري مرتب وزن دار ازُ بعد n ، يک با يک بردار وابسته تايي می باشد
بطوريکه :
که در معادله (١)، bj، برابر با j اُمين عنصر بزرگ در ميان ai ها ميباشد. خاصيت شناخته شده از اپراتورهاي
OWA اين است که شامل حداکثر، حداقل و ميانگين حسابي عملگرها براي انتخاب مناسب بردار W است .
مجموعه داده هاي مورد استفاده شامل دو مجموعه ميباشند، که عبارتند از:
اگر مجموعه داده هاي مورد استفاده را يک مجموعه دوتايي <q,d> در نظر بگيريم ، که در اين ارتباط ، مرتبط بودن يا نبودن پرس وجويي q با سند d مشخص ميشود. با استفاده از OWA [١٧] ميتوان تابع وزن هر يک از جفت سند و پرس وجو را با استفاده از معادله (٢) استخراج نمود.
براي بدست آوردن وزن هر خصيصه در هر پرس جو، و از لحاظ مرتبط بودن با پرس وجو، اسناد متناظر با يکديگر مقايسه مي شوند. در اينصورت سه نتيجه را از اين ارتباط ميتوان بدست آورد. اگر دو سند مجاور را u و v در نظر
