و b به صورت پیش فرض ۲/۱ و ۷۵/۰ مقدار دهی می شوند. اما مقادیر کوچکتر b بعضی وقت‌ها سودمندتر است. برای پرس‌وجوهای با طول بزرگ،اغلب مساوی ۷ یا ۱۰۰۰ مقدار دهی می‌شود و اغلب صفر است.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۲-۳ رتبه‌بندی مبتنی بر اتصال[۴۰]
برخلاف محیط بازیابی اطلاعات سنتی، وب دارای یک ساختار ناهمگن بزرگ بوده که اسناد به یکدیگر متصل هستند و یک گراف بزرگ را تشکیل می‌دهند. پیوندهای وب شامل اطلاعات ارزشمندی هستند، بنابراین الگوریتم‌های رتبه‌بندی جدید بر اساس پیوند ایجاد شده‌اند. قدرت اصلی آن‌ها استفاده از محتوای دیگر صفحات جهت رتبه‌بندی یک صفحه می‌باشد.
در نگاه کلی الگوریتم‌های بر مبنای اتصال، به دو دسته وابسته به پرس‌و‌جو و مستقل از پرس‌و‌جو تقسیم می‌شوند. در روش‌های مستقل از پرس‌و‌جو مانند هاست‌رنک[۴۱]، پیجرنک اُپایس[۴۲] رتبه‌بندی به صورت برون خط و با بهره گرفتن از کل گراف وب انجام می‌شود، در نتیجه به ازای هر پرس‌و‌جو رتبه هر صفحه ثابت است. اما روش وابسته به پرس‌و‌جو یا حساس به موضوع مانند هیتس، رتبه‌بندی در گرافِ شامل مجموعه صفحات مرتبط با پرس‌وجوی کاربر انجام می‌شود. قابل ذکر است که در رتبه‌بندی مستقل از پرس‌و‌جو مانند پیجرنک، بعد از دریافت پرس‌و‌جو ابتدا تعدادی صفحه‌ی مرتبط با پرس‌و‌جو با بهره گرفتن از روش‌های رتبه‌بندی مبتنی بر محتوا، انتخاب می‌شوند و سپس بر اساس رتبه‌ی بدست آمده‌ی حاصل از پیجرنک، مرتب می‌شوند.
۲-۳-۱ رتبه‌بندی مستقل از پرس‌و‌جو
همان‌طور که می‌دانیم کلاسیک‌ترین الگوریتم استخراج ساختار وب، الگوریتم پیجرنک است که توسط سرگی برین و لری پیج در دانشگاه استنفورد ارائه شد تا بدین ترتیب عملکرد الگوریتم را بررسی نمایند[۲۴]. آن‌ها با موفقیت این الگوریتم را در نمونه مدل موتور جستجوی گوگل بکار گرفتند و در حال حاضر گوگل به شناخته شده ترین موتور جستجوی جهان بدل شده است. البته الگوریتم پیجرنک، به طور ساده از منظر آنالیز ساختاری بر مبنای فراپیوندها، برای سنجش اهمیت نسبی صفحات وب شروع می‌کند که به طور کامل سایر فاکتورهای وب را نادیده می‌گیرد و در برخی موارد دست‌یابی به نتایج بهتر مشکل است[۲۵].
پیجرنک، یک الگوریتم مستقل از پرس‌و‌جو است که در موتور جستجوی گوگل استفاده شده است و بر اساس اتصال بین صفحات عمل می‌کند. برای مثال اگر صفحه p1 به صفحه p2 اشاره کند، موضوع p2 برای ایجاد کننده p1 جذاب می‌باشد. بنابراین تعداد پیوندهای ورودی به یک صفحه درجه جذابیت آن صفحه برای دیگران را نشان می‌دهد. در نتیجه درجه جذابیت یک صفحه با تعداد پیوندهای ورودی آن افزایش می‌یابد. به علاوه وقتی به یک صفحه از صفحات مهم (با تعداد پیوند زیاد) اشاره شود، آن صفحه نیز رتبه بالایی خواهد داشت. به عبارت دیگر وزن هر صفحه در پیجرنک جمع وزن دار صفحاتی است که به آن اشاره می‌کنند. بنابراین الگوریتم پیجرنک بازگشتی بوده و می‌توان آن را با بهره گرفتن از زنجیره مارکف مدل کرد.[۲۶] فرض کنید N(i) و B(i) به ترتیب نشان دهنده تعداد پیوندهای خروجی و مجموعه صفحات ورودی صفحه i باشند. رتبه صفحه i با بهره گرفتن از پیجرنک به صورت زیر محاسبه می‌شود:
در نتیجه رتبه صفحه i مساوی جمع رتبه صفحات ورودی تقسیم بر درجه خروجی آن‌ها می‌باشد. تقسیم بر درجه خروجی باعث می‌شود تا اولاً رتبه صفحه به صورت عادلانه بین فرزندانش (خروجی‌ها) تقسیم شود و ثانیاً جمع رتبه‌ی همه صفحات به عدد ثابت (یک) نرمال شود. شکل(۲-۱) مثالی از پیجرنک را نشان می‌دهد.

شکل ۲-۲۱: مثالی از پیجرنک]۲۶[
فرمول فوق برای حالتی که گراف کاملاً پیوسته باشد مناسب است (هر گره به تمام گره‌ها دسترسی داشته باشد). در صورتی گراف وب پیوسته نبوده یا صفحات بدون ورودی یا خروجی[۴۳] موجود باشند، الگوریتم موجب ایجاد اشکال می‌شود (الگوریتم همگرا نخواهد شد). به عبارت دیگر بعد از اجرای کامل الگوریتم تعداد زیادی از صفحات دارای مقدار پیجرنک صفر خواهند بود. برای حل این مشکل از پارامتر d به نام ضریب استهلاک[۴۴] به صورت زیر استفاده شده است که n نشانگر تعداد کل صفحات می‌باشد.
بنابراین هر صفحه به تمام صفحات با احتمال یک پیوند خروجی خواهد داشت. مکانیزم فوق معادل یک موج سوار تصادفی[۴۵] که در وب قدم می‌زند و به صورت تصادفی روی پیوندها کلیک می‌کند، می‌باشد. زمانی که به یک صفحه با درجه خروجی صفر[۴۶] یا به حلقه بسته[۴۷] می‌رسد به یک صفحه دیگر پرش خواهد کرد. لذا وقتی کاربر در یک صفحه است با احتمال d یکی از پیوندهای آن را به صورت تصادفی انتخاب، یا با احتمال (۱-d) به صفحات دیگر پرش می‌کند.
معادله پیجرنک را می‌توان به صورت یک رابطه جبر خطی r = AT * r نوشت که r یک بردار n بعدی است و هر عضو i آن نشان دهنده رتبه صفحه i می‌باشد. همچنین هر عضو ماتریس A به صورت است اگر صفحه i به صفحه j اشاره کند و در غیر این صورت خواهد بود.
به عبارت دیگر هدف محاسبه بردار ویژه r از ماتریس AT با مقدار ویژه ۱ است. با توجه به وجود موضوعات مختلف روی وب و همپوشانی موضوعی آن‌ها با یکدیگر، در بیشتر مواقع باعث می‌شود موضوعات مختلف با یکدیگر رقابت کنند و در نتیجه دقت سیستم پایین بیاید. مدل گسترش یافته پیجرنک به نام TSPR برای حل مشکل فوق ارائه شده است[۲۷]. در این روش برای کل وب N عنوان در نظر گرفته شده است و صفحات به ازای هر عنوان جداگانه با بهره گرفتن از پیجرنک رتبه‌بندی می‌شوند و لذا N رتبه جداگانه برای هر صفحه خواهیم داشت. رتبه صفحه v در عنوان t به صورت زیر محاسبه می‌شود:
برای هر عنوان یک بردار E متناظر خواهیم داشت. در صورتیکه بدانیم کاربر به چه عنوانی علاقه دارد یا پرس‌وجوی او متناظر با کدام عنوان است، روش فوق نسبت به پیجرنک پیشرفت چشمگیری خواهد داشت.
روشی به نام تراسترنک[۴۸] برای مقابله با گسترش رتبه ارائه شده است. با توجه به اینکه مشخص کردن همه صفحات مشکل دار (بد) توسط افراد خبره کاری غیر ممکن می‌باشد، لذا در این مقاله یک روش نیمه‌خودکار برای تشخیص صفحات خوب و بد ارائه شده است. در ابتدا مجموعه‌ای از صفحات که توسط افراد خبره ارزیابی شده‌اند به عنوان نقطه شروع[۴۹] انتخاب می‌شوند. به دنبال آن با بهره گرفتن از ساختار گراف وب و صفحات شروع خوب بقیه صفحات خوب تشخیص داده می‌شوند[۲۸]. آزمایشات بر روی صفحات جمع آوری شده توسط موتور جستجوی Alta Vista در سال ۲۰۰۳ انجام شده است و با انتخاب کمتر از ۲۰۰ سایت به عنوان نقطه شروع نتایج قابل توجهی بدست آمده است. الگوریتم فوق در مقایسه با الگوریتم پیجرنک صفحات خوب را بهتر تشخیص می‌دهد. برای هر صفحه دو تابع O(p) به صورت زیر که اُراکل[۵۰] صفحه P نامیده می‌شود و T(p) که نشان دهنده درجه‌ی اعتماد به صفحه P می‌باشد (T(p)=Pr(o(p)=1) ) تعریف شده است.
برای تمام صفحات شروع O(p) مشخص می‌باشد و هدف از الگوریتم بدست آوردن درجه اعتماد به بقیه صفحات است. الگوریتم تراسترنک در حقیقت گسترش یافته پیجرنک می‌باشد که ضریب می‌شود و با توجه به صفحات شروع مقداردهی می‌شود، برای مثال اگر صفحات ۵ و۱۰ و ۱۵ به عنوان صفحات خوب انتخاب شوند، ۳۳(۵)=E (10)=E (15 )= 0. Eو بقیه صفر می‌شوند. به عبارت دیگر مطابق مدل موج سوار تصادفی پرش کاربر در صورت خسته شدن از یک صفحه به صفحات خاصی که داری O(p) یک می‌باشند محدود می‌شود.
در نهایت بردار اعتماد حاصل الگوریتم خواهد بود و نتایج مطابق این بردار به صورت نزولی به کاربر ارائه می‌شوند. ایده اصلی این الگوریتم بر این پایه استوار است که اغلب صفحات خوب به صفحات خوب دیگر اشاره می کنند. به عبارت دیگر درجه اعتماد این صفحات که یک است به صفحات دیگر انتشار پیدا می‌کنند و با زیاد شدن فاصله اثر اعتماد کم خواهد شد (ضریب استهلاک این نقش را بازی می کند). الگوریتم های ذکر شده‌ی مبتنی بر اتصال عمل رتبه‌بندی را بر مبنای گراف مسطح[۵۱] انجام می‌دهند و ساختار سلسله مراتبی[۵۲] وب را نادیده می‌گیرند. آنها از دو مشکل عمده رنج می‌برند: پراکندگی زیاد صفحات وب و سوگیری نسبت به صفحات قدیمی که باعث می‌شود صفحات جدید با درجه ورودی کم از رتبه‌ی پایینی برخوردار شوند (غنی تر شدن اغنیاء). الگوریتم هاسترنک[۵۳] که برای فائق آمدن بر دو مشکل فوق ارائه شده است. هر دوی ساختار سلسله مراتبی و اتصالی وب را در رتبه‌بندی لحاظ می‌کند. در این روش صفحات ابتدا در یک ساختار سلسله مراتبیِ دایرکتوری، هاست[۵۴] و یا دامنه[۵۵] که گره برتر[۵۶] نامیده می‌شود قرار داده می‌شوند و عمل آنالیز اتصال بر روی گراف بدست آمده انجام می‌شود. سپس درجه‌ی اهمیت (ارزش) محاسبه شده‌ی هر گره بین صفحاتی که آن گره شامل می شود توسط ساختار سلسله مراتبی توزیع می‌شود[۲۹]. نتایج آزمایشات روی TREC 03 و TREC 04 افزایش چشمگیری را نسبت به روش‌های دیگر مبتنی بر اتصال مانند پیجرنک و روش‌های دیگر مبتنی بر ساختار سلسله مراتبی نشان می‌دهند. همچنین آزمایشات برتری تجمیع صفحات در هاست نسبت به دامنه و دایرکتوری را نشان می‌دهند.
۲-۳-۲ رتبه‌بندی وابسته به پرس‌و‌جو
الگوریتم هیتس توسط کلینبرگ[۵۷] برای رتبه‌بندی صفحات مرتبط با پرس‌و‌جو، ارائه شده است. این الگوریتم فرض می‌کند که صفحات وب دو جنبه را ارائه می‌دهند: جنبه اول، فراهم آوردن اطلاعات درباره یک موضوع است و جنبه دوم، مهیا کردن اتصالات به صفحات دیگر که اطلاعاتی در مورد موضوع مورد نظر دارند، این مطلب منجر به دسته بندی صفحات وب به دو شکل می‌شود. اول این که فرض شود که یک صفحه وب در صورت داشتن اطلاعات کافی به عنوان مرجع درباره موضوع خاصی در نظر گرفته شود. دوم این که، صفحه به عنوان مرکز انتقال در صورت داشتن اتصال مناسب به صفحات دارای اطلاعات در مورد موضوع مورد نظر فرض شود. بنابراین صفحات دارای دو مشخصه هستند. مشخصه اول که به آن هاب[۵۸] می‌گویند نشان دهنده کیفیت صفحه به عنوان اشاره‌گر به منابع با ارزش است و مشخصه دوم اتورینگ[۵۹] است که نشانگر کیفیت خود صفحه به عنوان منبعی مفید است. اگر دو کپی از هر صفحه در نظر گرفته شود، می‌توان گراف G را به عنوان یک گراف دو بخشی فرض کرد که در آن گره‌های هاب به گره‌های اتورینگ اشاره می‌کنند. ارتباط دو طرفه‌ای که در این بخش می‌توان دید به این صورت است که یک هاب خوب صفحه‌ای است که به اتورینگ‌های خوب اشاره می‌کند و یک اتورینگ خوب صفحه‌ای است که به هاب‌های خوبی اشاره کند. الگوریتم هیتس یک الگوریتم تکراری است که کیفیت هر صفحه را بر اساس مقادیر اتورینگ و هاب آن می‌سنجد[۳۰].
الگوریتم هیتس جزء دسته الگوریتم‌های وابسته به پرس‌وجو بوده و بر روی همه گراف وب عمل نمی‌کند بلکه بر روی زیر گرافی از آن اعمال می‌شود که این زیر گراف با بهره گرفتن از روش‌های سنتی بازیابی متن انتخاب می‌شود. نحوه عملکرد این الگوریتم بدین صورت است که با در نظر گرفتن گراف جهت دار G، به هر گره i یک مقدار اولیه وزن اتورینگ، a0(i) و وزن اولیه هاب، h0 (i)را نسبت می‌دهد. برای شروع الگوریتم این وزن‌ها به شکل مساوی مقداردهی می‌شوند. الگوریتم مراحل زیر را تا زمانی که خطا در حد قابل قبول باشد تکرار می‌کند:
در تکرار k ام، گره i یک مقدار جدید اتورینگ، ak(i) که مساوی مجموع hk-1(j) است را می‌گیرد. به عبارتی دیگر مقدار آن برابر است با مجموع هاب‌های مربوط به گره‌های j که به گره i اشاره می‌کنند. این مرحله برای تمام گره‌های موجود در گراف G تکرار می‌شود. مقدار جدید وزن هاب برای hk(i) ، مجموع ak(j) ها است که در آن j تمام صفحاتی هستند که به گره i اشاره می‌کنند. این مرحله نیز برای تمام گره‌های گراف G تکرار می‌شود. توجه داشته باشید که وزن‌های هاب از مقادیر کنونی وزن‌های اتورینگ محاسبه می‌شوند که در عوض، آن‌ها نیز از مقادیر قبلی وزن‌های هاب محاسبه شده بودند.
در مرحله k ام بعد از محاسبه وزن‌های جدید برای همه گره‌ها، وزن‌ها نرمال سازی می‌شوند به شکلی که رابطه ۲-۱ برقرار است:
برای ساخت یک فرمول جبر خطی از این الگوریتم بردار ak از وزن‌های اتورینگ در تکرار k ام و بردار hk از وزن‌های هاب در نظر گرفته می‌شود به صورتی که:
برای مقدار دهی اولیه به طور یکنواخت می‌توان از روابط(۲-۱۴)و (۲-۱۵) استفاده کرد :
اگرw ماتریس همجواری گراف G باشد روابط محاسباتی الگوریتم را می‌توان به شکل زیر نوشت:
که در آن و ثابت های نرمال‌سازی هستند و به صورتی انتخاب می‌شوند که مجموع مربعات وزن‌ها در تکرار k ام برابر با یک باشد. می‌توان از ترکیب دو رابطه (۱۶-۲) و (۲-۱۷) به روابط زیر رسید:
در این روابط محاسبه مربوط به هاب و اتورینگ به شکل مستقل از یکدیگر و بازگشتی قابل پیاده سازی است.
تحلیل بیشتر الگوریتم هیتس جهت شناخت نقاط ضعف آن: یک صفحه با اتورینگ خوب صفحه‌ای است که توسط چندین صفحه با هاب خوب اشاره شده باشد و یک هاب خوب صفحه‌ای است که به صفحات با اتورینگ بالا اشاره کرده باشد بنابراین کیفیت یک صفحه p به عنوان اتورینگ به کیفیت صفحات هاب که به آن اشاره می‌کنند بستگی دارد و بالعکس .[۲۶]
همان گونه که در الگوریتم هیتس دیده شده وزن اتورینگ برای صفحه p عبارت بود از مجموع وزن‌های هاب صفحاتی که بر صفحه p اشاره می‌کردند و وزن هاب برای صفحه‌ی p عبارت بود از مجموع وزن‌های اتورینگ صفحات اشاره شده توسط صفحه p. این تعریف دارای دو خصوصیت است: اول این که متقارن است به این شکل که هر دو وزن هاب و اتورینگ به یک روش تعریف شده‌اند. اگر جهت یال‌های گراف G را تغییر دهیم جای هاب و اتورینگ عوض می‌شود. و دوم این که حالت مساوات در آن برقرار است به این صورت که هنگام محاسبه وزن هاب از صفحه‌ای مانند p وزن اتورینگ صفحاتی که توسطp به آن‌ها اشاره شده است به شکل مساوی تحت تأثیر قرار می‌گیرند.
این دو خصوصیت ممکن است منجر به نتایج غیر مشهودی شوند به عنوان مثال گراف شکل(۲-۲)را در نظر بگیرید. در این گراف دو جز وجود دارد. بخش سیاه گراف شامل یک اتورینگ است که توسط هاب‌های زیادی به آن اشاره شده است و بخش سفید شامل یک هاب است که توسط اتورینگ‌های فراوانی به آن اشاره شده است. از آن جا که تعداد هاب‌های سفید بیش از تعداد هاب‌های سیاه است. الگوریتم هیتس همه وزن اتورینگ را به اتورینگ سفید اختصاص می‌دهد که در نتیجه رتبه‌ی گره سفید بیش از گره سیاه تشخیص داده می‌شود. دلیل این رخداد این است که هاب‌های سفید به عنوان بهترین هاب پنداشته شده‌اند و بنابراین باعث شده است که وزن‌های بیشتری را دریافت کنند. حتی اگر از لحاظ شهودی بتوان پیشنهاد کرد که اتورینگ سیاه بیشتر از سفید است و باید دارای رتبه بالاتری باشند.
شکل ۳۲-۲: نمایی از اتورینگ و هاب در الگوریتم هیتس]۲۶[
در این مثال، ترکیبی از دو خصوصیت یاد شده، باعث ایجاد یک نتیجه‌ی غیر شهودی شد. مساوات، به این معنی که تمام وزن‌های اتورینگ از گره‌هایی که توسط یک هاب به آن‌ها اشاره شده است به شکل برابر در محاسبه وزن هاب آن گره شرکت می‌کنند. در نتیجه کمیت به کیفیت تبدیل شده است. وزن هاب گره سفید به این دلیل افزایش پیدا کرده است که به تعداد زیادی از اتورینگ‌های ضعیف اشاره کرده است. این باعث زیر سوال رفتن تعریف وزن هاب و به طبع آن، طبیعت متقارن بودن الگوریتم هیتس شده است. بنابر خاصیت تقارن فرض بر این است که هاب‌ها و اتورینگ‌ها از لحاظ کیفیت دارای ارزش یکسانی هستند. حال آنکه بین این دو تفاوت وجود دارد. برای مثال از لحاظ شهودی پیشنهاد می‌شود که یک گره با درجه ورودی زیاد احتمالاً دارای اتورینگ خوبی است. از جهت دیگر یک گره با درجه خروجی زیاد لزوماً یک هاب خوب نیست. اگر چنین باشد، به راحتی می‌توان با افزودن ابر اتصال به یک صفحه ارزش آن را بالا برد که این ارزش کاذب می‌باشد و واقعی نیست. پس باید بین هاب و اتورینگ تفاوت قائل شد. در الگوریتم‌هایی که در ادامه می‌آید این تفاوت بین هاب و اتورینگ در نظر گرفته شده و سعی بر این است که در خصوصیت تقارن و مساوات شکسته شود.
محدودیت‌های الگوریتم هیتس:
یک تعریف جامع از هاب و اتورینگ وجود ندارد، زیرا بسیاری از سایت‌ها در عین حال که اتورینگ خوبی می‌باشند هاب خوبی نیز می‌باشند.
برخی صفحاتی که به عنوان نتیجه جستجو ارائه می‌شود در حقیقت به دلیل وجود اتصال قوی بین گره‌های گراف وب می‌باشند، در حالی که ممکن است هیچ ارتباطی با جستجوی کاربر نداشته باشند.
برخی لینک‌های وب به صورت اتوماتیک ایجاد می‌شوند و منطق انسان در آن دخیل نمی‌باشد در حالی که الگوریتم هیتس مانند لینک‌های عادی با آن‌ها رفتار می‌کند.
برخی جستجوها می‌توانند صفحات غیر مرتبط را ارائه دهند و صفحات غیر مرتبط زمانی که در الگوریتم هیتس به عنوان گراف ریشه قرار گیرد نتایج اشتباهی را اعلام می‌کند.
عملکرد الگوریتم در زمان واقعی قابل قبول نیست.
۲-۳-۳ چالش‌های رتبه‌بندی بر اساس پیوند
موتورهای جستجوی فعلی با نشان دادن صفحات محبوب[۶۰]، در صدر لیست رتبه‌بندی شده، باعث می‌شوند تا صفحات تازه متولد شده‌ی باکیفیت[۶۱]، هیچ وقت نشان داده نشوند یا بعد از زمان طولانی در لیست قرار گیرند. این مشکل «غنی‌تر شدن اغنیاء» نامیده می‌شود. به عبارت دیگر موتورهای جستجو با تقویت این مشکل، جهت رشد و تغییرات وب را به صورت مخاطره انگیز تعیین می‌کنند. مشکل «غنی‌تر شدن اغنیاء» و زمانی که طول می‌کشد تا یک صفحه باکیفیت توسط کاربران شناخته و مورد توجه قرار گیرد به صورت عملی در موتورهای جستجو مطالعه شده است. دو مدل جهت دست‌یابی کاربران به صفحات وب جدید ارائه شده است[۳۱]:
مدل موج سوار تصادفی: در این مدل کاربر برای کشف و دست‌یابی به صفحات از مکانیزم دنبال کردن پیوندها (مرور و کلیک کردن) به صورت تصادفی استفاده می‌کند و از موتور جستجو به هیچ وجه استفاده نمی‌کند.
مدل محدود به جستجو[۶۲]: در این مدل کاربر همیشه جهت کشف و دست‌یابی به صفحات فقط از موتور جستجو استفاده می‌کند.
جهت مقایسه مدل‌های فوق تعاریف زیر ارائه شده است: ( p(p,t- محبوبیت صفحه p در زمان t (ردیف Pدر لیست رتبه‌بندی شده).
در مدل موج سوار تصادفی رابطه مستقیم بین محبوبیت و نرخ بازدید وجود دارد (r1 ثابت است):

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...