بررسی الگوریتم های PageRank و HITS برای استخراج صفحات وب

موتور های جستجو در چند دهه اخیر به یکی از ضروری ترین برنامه ها تبدیل شده اند؛ به طوری که حتی تصور یافتن اطلاعات بدون آنها برای بسیاری غیر ممکن است.

وب یک منبع غنی از داده ها می باشد که گسترش اندازه و پیچیدگی آن همواره ادامه دارد. از این رو، بازیابی موثر و کارآمد صفحات وب یک چالش بزرگ است. با توجه به حجم وسیع اطلاعات در وب، مدیریت آن با ابزار های سنتی تقریبا غیر ممکن بوده و موجب مشکلات زیادی برای کاربران جهت جستجوی اطلاعات می شود لذا نیاز به تکنیک هایی جهت رفع مشکلات موجود داریم.

در این مقاله، الگوریتم های تحلیل لینک مانند PageRank و HITS مورد بررسی و مقایسه (با استفاده از مثال) قرار گرفته اند.

الگوریتم های تحلیل لینک (Link Analysis)

الگوریتم Page Rank

پیج‌رنک یا رتبه صفحه، به الگوریتمی گفته می‌شود که بر پایه آن موتورهای جستجو، صفحات وبی که به هدف جستجوگر نزدیکترند را در رده‌های بالاتری نسبت به دیگران قرار می‌دهد. الگوریتم Page Rank اولین بار در سال ۱۹۹۸ توسط Larry Page و Sergey Brin در دانشگاه استنفرد ارائه شده است. با این روش کاربرانی که کلمه ویژه‌ای را جستجو می‌کنند می‌توانند ابتدا صفحات وبی را ببینند که هم به خواسته آن‌ها نزدیکتر است و هم بازدید بیشتری داشته‌است.

این الگوریتم به هر صفحه وب، امتیازی اختصاص داده و از این امتیاز با درنظر گرفتن پرس و جوی کاربر، جهت رتبه بندی صفحات وب استفاده می کند. رتبه هر صفحه با اختصاص وزن به لینکی که به آن صفحه داده شده است به دست می آید که مقدار این وزن به کیفیت صفحه ای که لینک در آن قرار گرفته بستگی دارد. بدین صورت لینک های صفحات مهم تر وزن بیشتری می گیرند. جهت مشخص کردن کیفیت صفحه های رجوع کننده، از رتبه آن صفحه که به صورت بازگشتی تعیین می شود، استفاده می گردد. اگر n صفحه وب در دسترس باشد، مقدار اولیه رتبه یک صفحه وب برابر با n^-1 می شود.

PR(A) = (1-d) + d(PR(Ti)/C(Ti)) (۱)

فرمول شماره ۱ برای محاسبه رتبه یک صفحه مانند A استفاده می شود. در این فرمول Ti صفحاتی می باشند که به صفحه A اتصال دارند و C(Ti) تعداد لینک های خروجی صفحه Ti و d ضریب اثر می باشد که مقداری بین ۰ و ۱ است.

الگوریتم HITS

الگوریتم HITS یا Hyperlink-Induced Topic Search یکی از الگوریتم های رایج برای رتبه بندی صفحات است که در سال ۱۹۹۸ توسط Kleinberg ارائه شد. این الگوریتم از دسته روش های وابسته به پرس و جو است. در این نوع روش ها برای هر پرس و جو تحلیل لینک انجام می شود. برای انجام تحلیل لینک، ابتدا می بایست گراف خاص پرس و جو به نام گراف همسایگی ساخته شود.

در حالت ایده آل این گراف تنها شامل صفحات مرتبط با پرس و جو است. برای ساخت گراف همسایگی، ابتدا یک مجموعه از صفحات مربوط با پرس و جو به وسیله موتور جست و جو بازیابی می شوند. سپس این الگوریتم برای هر گره در گراف همسایگی، به طور تناوبی دو امتیاز Authority و Hub را محاسبه می کند و سپس گره ها را با توجه به این امتیازات رتبه بندی می کند.

در این گراف دو نوع گره وجود دارد:

1. گره Hub : صفحاتی که به عنوان لیست های منبع عمل می کنند.
2. گره Authority : صفحاتی که محتویات مهمی دارند.

گره های با امتیاز بالای Authority ،Authority خوب و گره های با امتیاز بالای Hub ،Hub خوبی هستند. این الگوریتم فرض می کند صفحه ای که به صفحات وب دیگر بیشتری اشاره می کند، Hub خوبی است و صفحه ای که صفحات وب بیشتری به آن اشاره می کنند، Authority خوبی می باشد. به طور بازگشتی می توان به این نتیجه رسید که صفحه ای که به تعداد Authority های خوب بیشتری اشاره می کند، Hub بهتری است و صفحه ای که Hub های خوب بیشتری به آن اشاره می کنند، Authority بهتری می باشد. در نتیجه یک صفحه به طور همزمان می تواند Hub و Authority خوبی باشد.

این الگوریتم بازگشتی دارای دو مرحله می باشد.

1. مرحله Sampling (نمونه گیری) : در این مرحله یک مجموعه از صفحات مرتبط با پرس و جو جمع آوری می شوند
2. مرحله بازگشتی: در این مرحله، Hub و Authority صفحات بدست آمده در مرحله اول، محاسبه می شود.

برای محاسبه Hub یک صفحه مانند p از فرمول ۲ استفاده می شود که مجموع Authority صفحات مرجع p می باشد

در فرمول ۲، Hp امتیاز Hub صفحه p است و Aq امتیاز Authority صفحه q است.

برای محاسبه Authority صفحه p از فرمول ۳ استفاده می شود که مجموع Hub صفحات مرجع صفحه p می باشد.

در فرمول ۳، Ap امتیاز Authority صفحه p است و Hq امتیاز Hub صفحه q است.

شبه کد الگوریتم HITS

محدودیت های الگوریتم HITS

1. تشخیص بین صفحات Hub و Authority مشکل است، زیرا یک صفحه می تواند همزمان Hub و Authority باشد.
2. این الگوریتم گاهی اوقات به دلیل وزن یکسان صفحات ممکن است صفحات نامرتبط با پرس و جوی کاربر را نمایش دهد.
3. این الگوریتم در real time کارایی خوبی ندارد.
4. برای لینک هایی که خودکار ایجاد شده و به پرس و جوی کاربر مرتبط نیستند امتیاز یکسانی تخصیص می دهد.

مقایسه دو الگوریتم Page Rank و HITS

کار با الگوریتم های Page Rank و HITS

جهت مقایسه نتایج الگوریتم های Page Rank و HITS، سه صفحه فرضی B ،A و C را به صورت زیر در نظر می گیریم.

گراف جهت دار حاصل از این صفحات به صورت زیر می باشد که در آن رئوس گراف همان صفحات و یال های گراف همان اتصال های بین صفحات می باشد. برای هرکدام از رئوس یک رتبه اولیه در نظر گرفته شده است.

ماتریس نشان داده شده در شکل زیر نیز ارتباط بین صفحات را نمایش می دهد که با توجه به گراف همسایگی ایجاد شده است. به طوری که عدد یک نشان دهنده وجود لینک بین صفحات و عدد صفر نشان دهنده عدم وجود لینک بین صفحات می باشد. برای مثال عدد یک درایه سطر اول و ستون دوم نشان دهنده وجود لینک از صفحه A به صفحه B است.

ابتدا رتبه صفحات را با استفاده از الگوریتم Page Rank محاسبه می کنیم.

فرض: d=0.85

PR(A) = (1-0.85) + 0.85(R(C) / c(C)) = 0.25 + 0.85(0.4 / 1) = 0.25 + 0.34 = 0.59

PR(B) = (1-0.85) + 0.85(R(A) / c(A)) = 0.25 + 0.85(0.4 / 2) = 0.25 + 0.17 = 0.42

PR(C) = (1-0.85) + 0.85(R(A) / c(A) + R(B) / c(B)) = 0.25 + 0.85(0.4 / 2 + 0.2 / 1) = 0.59

جهت محاسبه رتبه صفحات با استفاده از الگوریتم HITS ابتدا مقادیر اولیه Hub و Authority یعنی H0 و A0 را به صورت پیش فرض 1 در نظر میگیریم سپس مقادیر جدید را همان طور که در جدول زیر نشان داده شده است، با استفاده از فرمول های 2 و 3 محاسبه می نماییم.

چون الگوریتم HITS یک الگوریتم تکرار شونده است پس دائما مقادیر Hub و Authority صفحات، محاسبه می شوند. رتبه های نهایی الگوریتم های Page Rank و HITS به صورت زیر می باشد:

همانطور که در جدول بالا مشاهده می شود، طبق الگوریتم Page Rank صفحه A رتبه بالاتری نسبت به صفحه B دارد. در الگوریتم HITS این دو صفحه دارای Authority یکسانی می باشند ولی طبیعتا طبق تعریف یک Hub خوب، صفحه A دارای مقدار Hub بیشتری می باشد زیرا به صفحات بیشتری اشاره می کند. صفحه C در الگوریتم Page Rank رتبه یکسانی با صفحه A دارد و این الگوریتم اهمیت آنها را یکسان در نظر گرفته است درحالی که در الگوریتم HITS مقدار Authority صفحه C بیشتر است و اهمیت آن نیز بیشتر می باشد که نشان دهنده این است که الگوریتم HITS از Page Rank بهتر عمل می کند.

نتیجه

الگوریتم های رتبه بندی نقش بسیار مهمی را در ترتیب نمایش صفحات وب به کاربر پرس و جو کننده دارد. الگوریتم Page Rank از روش ساختارکاوی وب استفاده می کند که توسط موتور جستجوگر Google استفاده می شد. مشکل روش Page Rank این است که کاربران ممکن است صفحات وب مرتبط مورد نیاز خود را در چند صفحه بالا به راحتی به دست نیاورند. الگوریتم دیگری که نسبت به الگوریتم Page Rank بهتر عمل میکند الگوریتم HITS است که علاوه بر روش ساختارکاوی وب، از روش محتوا کاوی وب نیز جهت رتبه بندی صفحات استفاده می کنند. نتایج تجزیه و تحلیل الگوریتم ها نشان می دهد که عملکرد الگوریتم HITS از Page Rank بهتر است ولی این الگوریتم محدودیت های مهمی جهت رتبه بندی دارد.

مراجع

[1] Tamanna Bhatia, "Link Analysis Algorithms For Web Mining"

[2] Rekha Jain, G. N. Purohit, "Page Ranking Algorithms For Web Mining"