|  10/17/2018 - چهارشنبه 25 مهر 1397
Menu
نوع جستجو را انتخاب کنید.
  • سایت
  • وب
جستجو
بایگانی اطلاعات > مشاهده

بهسازی الگوريتم HITS برای لينکهای Spam ( ابراهیم عباسپور )


به نام خدا

 

 

بهسازی الگوريتم HITS

برای لينکهای Spam

 

 

درس بازیابی اطلاعات

استاد : دکتر محمودی

دانشجو : ابراهیم عباسپور

 

1390

 

با تشکر از همه آنانی که ساختن و ساخته شدن را به ما آموختند

 

فهرست

مقدمه

الگوریتمها رتبه دهی برای صفحات وب

الگوریتم Page Rank

الگوریتم HITS

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

اﻟﮕﻮرﻳﺘﻤﻲ ﻣﺒﺘﻨﻲ ﺑﺮ ﺳﺎﺧﺘﺎر ﭘﻴﻮﻧﺪي ﺻﻔﺤﺎت و اﻃﻼﻋﺎت اﺳﺘﻔﺎده ﻛﺎرﺑﺮان

ﺍﻟﮕﻮﺭﻳﺘﻢ ﺗﺮﻛﻴﺒﻲ ﻭﻓﻘﻲ

الگوریتمهای ﺍﻟﮕﻮﺭﯾﺘﻢ ‪iRank ‫

بهسازی الگوريتم HITS برای لينکهای Spam(صفحه 25)

1- خلاصه

2- مقدمه

3- مقدمات

ضوابط و شرایط

الگوریتم Hits اصلی

اصلاحات

خارج کردن linkformها

4- الگوریتم Trust-Score

5- چهار الگوریتم امتیاز دهی

6- نتایج آزمایش

7- توضیحات نتیجه گیری

8- پیاده سازی و بررسی نتیجه ( صفحه 40 )

 

مقدمه :

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

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

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

داده کاوری (Web Mining) یکی از کاربردهای داده کاوی است که در آن به کشف الگوها در وب پرداخته میشود. تحقیقات انجام شده در وبکاوی میتوان به سه قسمت تقسیم نمود:

1- کاربردکاوی وب (Web Usage Mining)

2- محتواکاوی وب (Web Content Mining)

3- ساختارکاوی وب (Web Structure Mining)

در کاربردکاوی وب به استخراج و تحلیل الگوهای علایق کاربران در استفاده از دادههای وب پرداخته میشو هدف از محتواکاوی وب نیز بدست آوردن اطلاعات مفید از متن و محتوای وب است. اما در ساختارکاوی وب هدف تحلیل ساختار وب با استفاده از مبانی تئوری گراف است. در واقع وب به عنوان گرافی در نظر گرفته میشود که هر گره آن متناظر با یک صفحه در وب و هر یال بین دو گره به عنوان یک پیوند Link یا Hyperlink بین دو صفحه متناظر میباشد.

یکی از مواردی که تحت عنوان ساختارکاوی وب بررسی میشود، طراحی الگوریتمهایی برای رتبه دهی صفحات وب بر اساس ساختار پیوندهای بین صفحات است. کاربرد الگوریتمهای رتبه دهی (Ranking Algorithms) صفحات وب در موتورهای جستجوی وب است. یک موتور جستجو از اجزای مختلفی نظیر پیمایشگر (Crawler)، تحلیلگر پرسوجو (Query Analyzer) فهرستگر (Indexer) تشکیل شده است. وظیفه قسمت تحلیلگر پرسوجو دریافت پرسوجوهای کاربران و بازگرداندن صفحات وب متناسب با پرسوجو است. بعد از استخراج صفحات متناسب با استفاده از الگوریتم رتبه دهی پاسخها بر اساس میزان تناسب و اهمیت مرتب میشوند تا کاربران به صفحات باکیفیت تر سریعتر دسترسی یابند. الگوریتم رتبه دهی یک موتور جستجو از مهمترین اجزا تعیین کننده توانایی و کیفیت یک موتور جستجوست. موتورهای جستجوی نسل اول مربوط به قبل از سال ۱۹۹۸ از الگوریتمهای مبتنی بر تحلیل متن Text Analysis برای رتبه دهی صفحات استفاده میکردند که در آنها تاکید بر موقعیت و بسامد واژههای مورد استفاده در صفحه است. اما الگوریتمهایی که صرفاً بر ویژگیهای متنی تاکید دارند از کارآیی مناسب برخورار نبودند. سال ۱۹۹۸ انقلابی در این زمینه به وجود آمد و دو الگوریتم رتبه دهی PageRank و (Hypertext Induced Topic Search) HITS بر اساس تحلیل پیوند(Link Analysis) ارائه شد. این الگوریتمها باعث ایجاد تحول در کارآیی موتورهای جستجو شدند و قابلیت آنها با استفاده در موتور جستجویی نظیر Google اثبات شده است. در سالهای اخیر نیز تحقیقات بسیاری در جهت اصلاح و بهبود این الگوریتمها توسط محققان انجام شده است.

 

الگوریتمهای رتبه دهی برای صفحات وب

سال ۱۹۹۸ یک سال مهم برای تحلیل پیوند در وب و همچنین جستجو در وب بود. چرا که هر دو الگوریتم HITS و PageRank در این سال معرفی شد. الگوریتم HITS توسط John Kleinberg در نهمین کنفرانس ACM-SIAM در الگوریتم های گسسته در ژانویه سال 1998 مطرح شد و PageRank نیز توسط Larry Page و Sergey Brin در هفتمین کنفرانس(WWW7) World Wide Web در آوریل سال ۱۹۹۸ ارائه شد که این مساله باعث ایجاد موتور جستجوی Google توسط این دو نفر شد. ایده اصلی الگوریتمهای HITS و PageRank بسیار به یکدیگر شبیه است. از آن سال الگوریتم PageRank تبدیل به الگوریتم غالب جهت جستجو در وب شد.دلیل این امر مستقل از پرس و جو بودن و مبارزه با هرزی (Spamming) این الگوریتم و همچنین موفقیتهای تجاری Googleبوده است. در این بخش به شرح این دو الگوریتم معر وف رتبه دهی برای صفحات وب میپردازیم.

 

الگوریتم PageRank

PageRank یک رتبه دهی استاتیک به صفحات وب است که مقدار مربوط به هر صفحه به صورت بر ون خط(off-line) محاسبه میشود و همچنین این الگوریتم مستقل از پرسوجو است. محاسبه PageRank یک صفحه بر اساس ایده محاسبه اعتبار(Prestige) یک عامل در شبکه اجتماعی(Social Network) است.

پیوند ور ودی (In-Links) صفحه I : پیوندهایی است که از صفحات دیگر به صفحه i اشاره میکند. معمولًا پیوندهایی که از صفحات در ون سایت صفحهi میرسند محاسبه نمیشود

پیوند خر وجی (Out-Links) صفحه I : پیوندهایی است که از صفحه به صفحات دیگر اشاره میکند. معمولًا پیوندهایی که صفحات در ون سایت صفحهi میرسند محاسبه نمیشود

 

بر اساس مفهوم اعتبار در شبکه اجتماعی میتوان موارد زیر را مطرح نمود:

۱. وجود یک پیوند از یک صفحه به صفحه دیگر به طور ضمنی نشان دهنده نفوذ (Authority) صفحه مقصد است. بنابراین پیوند ور ودی بیشتر برای صفحه i نشاندهنده نفوذ بیشتر این صفحه است.

۲. صفحاتی که به i اشاره میکنند خود نیز دارای اعتبارهای متفاوت هستند. پیوند رسیده از یک صفحه با اهمیت بالاتر ارزش بیشتری نسبت به پیوند رسیده از یک صفحه با ار زش کمتر دارد. میتوان نتیجه گرفت که صفحه ای مهم است که از صفحات مهم دیگر پیوند گرفته باشد.

بر اساس مفاهیم مطرح شده درباره اعتبار در شبکه های اجتماعی امتیاز PageRank صفحه i برابر است با مجموع امتیاز PageRank صفحاتی است که به I پیوند داده اند از طرفی چون ممکن است یک صفحه به تعداد زیادی صفحه پیوند داده باشد پس باید امتیاز PageRank آن بین تمام این صفحات تقسیم شود.

برای فرموله کردن این ایده، وب را به عنوان یک گراف جهتدار G = (V,E) فرض می کنیم که V مجموعه گره ها یعنی تمام صفحات موجود در وب و E نیز نیز مجموعه یالها یعنی پیوند بین صفحات است فرض میکنیم تعداد صفحات در وب n است یعنی |V | = n حال PageRank صفحه i یعنی P(i) به شکل زیر محاسبه می شود: کخ Oi تعداد پیوندهای خروجی صفحه i است. . در این حالت در واقع ما دارای n معادله با n مجهول یعنی PageRank صفحات، هستیم. حال از یک ماتریس برای نمایش تمام معادله ها استفاده میکنیم. P را به عنوان یک بردار ستونی n بعدی از مقادیر PageRank در نظر می گیریم،

P = (P(۱), P(۲), . . . , P(n))T

همچنین A را به عنوان ماتریس همسایگی گراف وب در نظر میگیریم ،حال سیستم n معادله را میتوان به صورت زیر نوشت

P = AT P

که معادله مشخصه بدست آوردن بردار ویژه است. برای بدست آوردن p از یک ر وش معر وف به نام Power Iterationاستفاده میشود. اما برای حل این مساله بایستی گراف مورد نظر قیدهای خاصی داشته باشد که گراف وب فاقد آنهاست. برای شرح این قیدها این مساله را از زاویه مبحث زنجیر مارکوف (Markov Chain)بر رسی میکنیم.

در زنجیر مارکوف هر صفحه وب یا گره در گراف وب به عنوان یک حالت (State)در نظر گرفته میشود و یک پیوند نیز به عنوان یک گذر (Transition) از یک حالت به حالت دیگر لحاظ میشود. بنابراین حرکت در وب (Web Surfing)به عنوان یک فرآیند اتفاقی (StocHOSTic) مدل میشود که اگر حرکت کننده (Surfer) در وب به صورت یکنواخت (Uniformly) پیوندهای موجود در صفحه i را انتخاب کند، احتمال گذر (Transition Probability) برابر با 1/Oiاست. با این اوصاف ماتریس احتمال گذر A یک ماتریس مربعی به شکل زیر خواهد بود،

 

اما رابطه دوم برای صغحات وبی که هیچ پیوند خر وجی ندارند صحیح نیست. اگر ماتریس A یک ماتریس A این رابطه را ارضا کند، گفته میشود اتفاقی (StocHOSTic Matrix) یک زنجیر مارکوف است.

m ،P در یک زنجیر مارکوف سوال مطرح این است: با داشتن توزیع احتمال اولیهp احتمال حضور زنجیر مارکوف بعد ازm گذر یا مرحله در حالت j چیست؟، احتمال حضور حرکتکننده در حالتj بعد از ۱ مرحله را میتوان با رابطه زیر محاسبه نمود

 

بر اساس قضیه Ergodic در زنجیر مارکوف یک زنجیر مارکوف متناهی تعریف شده با ماتریس گذر اتفاقی دارای یک توزیع احتمال ایستای (Stationary) یکتا (Unique) خواهد بود اگرA ناکاستنی (Irreducible) و غیرچرخهای (Aperiodic) باشد. توزیع احتمال ایستا بدین معناست که بعد از تعدادی گذرPK به یک بردار احتمال پایدار π مستقل از بردار احتمال اولیه P همگرا خواهد شد، یعنی، limk→∞Pk = π

حال آیا واقعاً ماتریس A اتفاقی و گراف وب ناکاستنی و غیرچرخهای است ؟A یک ماتریس گذر اتفاقی نیست. چون ماتریسی برای یک زنجیر مارکوف اتفاقی است که درایههای آن اعداد حقیقی غیرمنفی است و مجموع مقادیر هر سطر نیز برابر با یک است. برای اینکه این شرط برای گراف وب برقرار باشد لازم است که هر صفحه وب حداقل دارای یک پیوند خر وجی باشد. اما در وب ما تعداد زیادی صفحه داریم که دارای پیوند خر وجی نمیباشد و این باعث میشود که درایههای بعضی سطرهای ماتریسA همگی صفر باشند. صفحات اینگونه در وب آویزان (Dangling) گفته میشود.

این مشکل را به شیوه های مختلف میتوان حل کرد که دو نمونه از آنها را بیان میکنیم:

1- ﺻﻔﺤﺎﺗﯽ ﮐﻪ ﺩﺍﺭﺍﯼ ﭘﯿﻮﻧﺪ ﺧﺮ ﻭﺟﯽ ﻧﯿﺴﺘﻨﺪ ﺩﺭ ﻓﺮﺁﯾﻨﺪﻣﺤﺎﺳﺒﻪ ‪ PageRankﺣﺬﻑ ﺷﻮﻧﺪ ﭼﻮﻥﺑﻪ ﻃﻮﺭ ﻣﺴﺘﻘﯿﻢ ﺩﺭ ﺭﺗﺒﻪﺩﻫﯽ ﺻﻔﺤﺎﺕ ﺩﯾﮕﺮ ﺗﺎﺛﯿﺮﯼ ‫ﻧﺪﺍﺭﻧﺪ. ﺑﺎﯾﺪ ﭘﯿﻮﻧﺪﻫﺎ ﺑﻪ ﺍﯾﻦ ﺻﻔﺤﺎﺕ ﺭﺍ ﻧﯿﺰ ﺣﺬﻑ ﻧﻤﻮﺩ. ﺍﻟﺒﺘﻪ ﺑﺎﺍﯾﻦ ﺭ ﻭﺵ ﺍﻣﺘﯿﺎﺯ ﺻﻔﺤﺎﺗﯽ ﮐﻪ ﭘﯿﻮﻧﺪ ﺁﻧﻬﺎ ﺑﻪ ﺻﻔﺤﺎﺕ ﺁﻭﯾﺰﺍﻥ ﺣﺬﻑ ﻣﯽﺷﻮﻧﺪ، ‫ﺩﺳﺘﺨﻮﺵ ﺗﻐﯿﯿﺮ ﺧﻮﺍﻫﺪ ﺷﺪ. ﺍﻣﺎ ﺍﯾﻦ ﺗﻐﯿﯿﺮ ﺑﺴﯿﺎﺭ ﺟﺰﯾﯽ ﺍﺳﺖ.

2- ‫ﺍﺿﺎﻓﻪ ﻧﻤﻮﺩﻥ ﯾﮏ ﻣﺠﻤﻮﻋﻪ ﮐﺎﻣﻞﺍﺯ ﭘﯿﻮﻧﺪﻫﺎﯼ ﺧﺮ ﻭﺟﯽ ﺍﺯ ﻫﺮ ﺻﻔﺤﻪ ﺁﻭﯾﺰﺍﻥ ‪ hﺑﻪ ﺗﻤﺎﻣﯽ ﺻﻔﺤﺎﺕ ﺩﯾﮕﺮ ﺩﺭ ﻭﺏ ﺭ ﻭﺵ ﺩﯾﮕﺮﯼ ﺍﺳﺖ. ﺍﺣﺘﻤﺎﻝﮔﺬﺭ ﺍﺯ ﺻﻔﺤﻪ ‪ hﺑﻪ ﻫﺮﺻﻔﺤﻪ ﺩﺭﻭﺏ ﺑﺮ ﺍﺳﺎﺱ ﺗﻮﺯﯾﻊ ﯾﮑﻨﻮﺍﺧﺖ 1/n ﺧﻮﺍﻫﺪ ﺑﻮﺩ. ﺑﻨﺎﺑﺮﺍﯾﻦ ﻫﺮ ﺳﻄﺮﯼﮐﻪ ﺗﻤﺎﻣﯽ ﺩﺭﺍﯾﻪﻫﺎﯼ ﺁﻥ ﺻﻔﺮ ﺍﺳﺖ ﺑﺎ e/n ﺟﺎﯾﮕﺰﯾﻦ ﺧﻮﺍﻫﺪ ﺷﺪ ﮐﻪ ‪ eﯾﮏ ﺑﺮﺩﺍﺭ ‪nﺑﻌﺪﯼ ﺍﺳﺖ ﮐﻪﺗﻤﺎﻣﯽ ﺩﺭﺍﯾﻪﻫﺎﯼ ﺍﻥ ۱ ﻣﯽﺑﺎﺷﺪ

‫ﻣﺎﺗﺮ ﯾﺲ ‪ Aﯾﮏ ﻣﺎﺗﺮ ﯾﺲ ﻧﺎﮐﺎﺳﺘﻨﯽ ﻧﯿﺰ ﻧﯿﺴﺖ. ﻧﺎﮐﺎﺳﺘﻨﯽ ﺑﺪﯾﻦ ﻣﻌﻨﺎﺳﺖﮐﻪ ﮔﺮﺍﻑ ﻭﺏ ‪ Gﻗﻮﯾﺎ ﻫﻤﺒﻨﺪ ﺑﺎﺷﺪ.

ﺗﻌﺮ ﯾﻒ ﻗﻮﯾﺎﻫﻤﺒﻨﺪ: ﯾﮏ ﮔﺮﺍﻑ ﺟﻬﺖﺩﺍﺭ (‪ G = (V, Eﻗﻮﯾﺎ ﻫﻤﺒﻨﺪ ﺍﺳﺖ ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ ﺑﺮﺍﯼ ﻫﺮ ﺟﻔﺖ ﮔﺮﻩ ‪ ،u, v ∈ Vﯾﮏ ﻣﺴﯿﺮ ﺍﺯ ‪ uﺑﻪ ‪ vﻭﺟﻮﺩ ﺩﺍﺷﺘﻪ ‫ﺑﺎﺷﺪ.

ﺑﺪﯾﻬﯽ ﺍﺳﺖ ﮐﻪﮔﺮﺍﻑ ﻭﺏ ﻧﻤﺎﯾﺶ ﺩﺍﺩﻩ ﺷﺪﻩ ﺑﻪ ﻭﺳﯿﻠﻪ ‪ Aﻗﻮﯾﺎ ﻫﻤﺒﻨﺪ ﻧﺒﺎﺷﺪ. ﭼﻮﻥ ﺑﯿﻦ ﺟﻔﺖ ﮔﺮﻩﻫﺎﯾﯽ ﻧﻈﯿﺮ ‪ uﻭ ‪ vﻣﺴﯿﺮﯼ ﻭﺟﻮﺩ ﻧﺨﻮﺍﻫﺪ ﺩﺍﺷﺖ‫‪ Aﻏﯿﺮﭼﺮﺧﻪﺍﯼ ﻧﯿﺰ ﻧﯿﺴﺖ. ﭼﺮﺧﻪﺍﯼ ﺑﻮﺩﻥ ﯾﮏ ﺣﺎﻟﺖ ﺩﺭ ﺯﻧﺠﯿﺮﻣﺎﺭﮐﻮﻑ ﺑﻪ ﻣﻌﻨﺎﯼ ﺍﯾﻦ ﺍﺳﺖ ﮐﻪ ﯾﮏ ﺩﻭﺭCycleﺟﻬﺖﺩﺍﺭ ﺑﺮ ﺭﻭﯼ ﺍﯾﻦ ﺣﺎﻟﺖ ‫ﻭﺟﻮﺩ ﺩﺍﺭﺩ ﮐﻪ ﺯﻧﺠﯿﺮ ﻣﺠﺒﻮﺭ ﺑﻪ ﭘﯿﻤﺎﯾﺶ ﺁﻥ ﺍﺳﺖ.

‫ ‫ﺗﻌﺮ ﯾﻒ ﻏﯿﺮﭼﺮﺧﻪﺍﯼ ﺑﻮﺩﻥ: ﺣﺎﻟﺖ ‪ iﺑﺎ ﺩﻭﺭ ۱ > ‪ kﭼﺮﺧﻪﺍﯼ ﺍﺳﺖ ﺍﮔﺮ ‪ kﮐﻮﭼﮑﺘﺮﯾﻦ ﻋﺪﺩﯼ ﺑﺎﺷﺪ ﮐﻪ ﺗﻤﺎﻡ ﻣﺴﯿﺮﻫﺎﯼ ﺷﺮﻭﻉ ﺍﺯ‪ i ﻭ ﭘﺎﯾﺎﻥ ﺑﻪ ‪ iﻃﻮﻟﺶ ‫ﻣﻀﺮﺑﯽ ﺍﺯ ‪ kﺑﺎﺷﺪ. ﺍﮔﺮ ﯾﮏ ﺣﺎﻟﺖ ﭼﺮﺧﻪﺍﯼ ﻧﺒﺎﺷﺪ ﯾﻌﻨﯽ ۱= kﺁﻧﮕﺎﻩ ﻏﯿﺮﭼﺮﺧﻪﺍﯼﺍﺳﺖ. ﺯﻧﺠﯿﺮ ﻣﺎﺭﮐﻮﻓﯽ ﻏﯿﺮﭼﺮﺧﻪﺍﯼ ﺍﺳﺖ ﮐﻪ ﺗﻤﺎﻡ ﺣﺎﻟﺖﻫﺎﯼ ﺁﻥ ‫ﻏﯿﺮﭼﺮﺧﻪﺍﯼ ﺑﺎﺷﺪ.

‫ ‫ﺑﺮﺍﯼ ﺣﻞ ﺍﯾﻦ ﺩﻭ ﻣﺸﮑﻞ ﺍﺯ ﯾﮏ ﺍﺳﺘﺮﺍﺗﮋﯼ ﺳﺎﺩﻩ ﺍﺳﺘﻔﺎﺩﻩﻣﯽﺷﻮﺩ. ﯾﮏ ﭘﯿﻮﻧﺪ ﺍﺯ ﻫﺮ ﺻﻔﺤﻪ ﺑﻪ ﻫﺮ ﺻﻔﺤﻪ ﺩﯾﮕﺮ ﺍﺿﺎﻓﻪ ﻣﯽﺷﻮﺩ ﻭ ﺑﻪ ﻫﺮ ﭘﯿﻮﻧﺪ ﯾﮏ ‫ﺍﺣﺘﻤﺎﻝ ﮔﺬﺭ ﮐﻮﭼﮏ ﺑﺎ ﭘﺎﺭﺍﻣﺘﺮ ‪ dﺩﺍﺩﻩ ﻣﯽﺷﻮﺩ.

‫ً‫ﻣﺎﺗﺮ ﯾﺲ ﺍﺣﺘﻤﺎﻝ ﮔﺬﺭ ﺍﻓﺰ ﻭﺩﻩ ﺷﺪﻩ ﻧﺎﮐﺎﺳﺘﻨﯽﺧﻮﺍﻫﺪ ﺑﻮﺩ ﭼﻮﻥ ﺑﺪﯾﻬﯽ ﺍﺳﺖ ﮐﻪ ﻗﻮﯾﺎ ﻫﻤﺒﻨﺪ ﺧﻮﺍﻫﺪ ﺑﻮﺩ. ﺍﺯ ﻃﺮﻓﯽ ﺍﯾﻦ ﻣﺎﺗﺮ ﯾﺲ ﻏﯿﺮﭼﺮﺧﻪﺍﯼ ﻧﯿﺰﺍﺳﺖ ‫ً ‫ﭼﻮﻥ ﻣﺴﯿﺮﻫﺎﯼ ﺑﺎ ﻃﻮﻝ ﻣﺘﻔﺎﻭﺕ ﺷﺮ ﻭﻉﺷﻮﻧﺪﻩ ﺍﺯﺣﺎﻟﺖ ‪ iﻭ ﭘﺎﯾﺎﻥ ﺑﻪﺣﺎﻟﺖ ‪ iﻭﺟﻮﺩ ﺩﺍﺭﺩﻭ ﺣﺮﮐﺖﮐﻨﻨﺪﻩ ﻣﺠﺒﻮﺭ ﻧﯿﺴﺖ ﺩﺭ ﻫﯿﭻ ﺣﺎﻟﺘﯽ ﯾﮏ ﭼﺮﺧﻪ ﺭﺍ ﺗﮑﺮﺍﺭ ‫ﻧﻤﺎﯾﺪ. ﺑﺎ ﺍﯾﻦ ﻣﺎﺗﺮ ﯾﺲ ﺍﻓﺰ ﻭﺩﻩ ﺑﻪ ﯾﮏ ﻣﺪﻝﺗﻮﺳﻌﻪﯾﺎﻓﺘﻪ ‪ PageRankﻣﯽﺭﺳﯿﻢ. ﺩﺭﺍﯾﻦ ﻣﺪﻝ ﺩﺭ ﻫﺮ ﺻﻔﺤﻪ ﺣﺮﮐﺖﮐﻨﺪﻩ ﺩﻭ ﮔﺰﯾﻨﻪ ﺩﺍﺭﺩ:

1- ﺑﺎ ﺍﺣﺘﻤﺎﻝ ‪ ،dﺑﻪ ﺷﮑﻞ ﺗﺼﺎﺩﻓﯽﯾﮏ ﭘﯿﻮﻧﺪ ﺧﺮ ﻭﺟﯽ ﺑﺮﺍﯼ ﺍﺩﺍﻣﻪ ﮐﺎﺭ ﺍﻧﺘﺨﺎﺏ ﻧﻤﺎﯾﺪ.

2- ‫ﺑﺎ ﺍﺣﺘﻤﺎﻝ ‪1-dﺑﻪ ﯾﮏ ﺻﻔﺤﻪ ﺩﯾﮕﺮ ﺑﻪ ﺷﮑﻞ ﺗﺼﺎﺩﻓﯽ ﺑﭙﺮﺩJumping

‫ﺭﺍﺑﻄﻪ ﺯﯾﺮ ﻣﺪﻝ ﺗﻮﺳﻌﻪﯾﺎﻓﺘﻪ ﺭﺍ ﺑﯿﺎﻥ ﻣﯽﮐﻨﺪ:

 

ﺑﻪ ﭘﺎﺭﺍﻣﺘﺮ ‪ dﺿﺮﯾﺐ ﺗﻌﺪﯾﻞ Damping Factor ﮔﻔﺘﻪ ﻣﯽﺷﻮﺩ ﻭ ﻗﺎﺑﻞ ﺗﻨﻈﯿﻢ ﺑﯿﻦ ۰ ﻭ ۱. ﺑﺮﺍﯼ ﻣﺤﺎﺳﺒﻪ ‪ PageRankﺻﻔﺤﺎﺕ ﻭﺏ ﺍﺯ ‪ Power Iteration Methodﺍﺳﺘﻔﺎﺩﻩ ﻣﯽﺷﻮﺩ ﮐﻪ ﺑﺮﺩﺍﺭ ﻭﯾﮋﻩ ﺍﺻﻠﯽ Principal Eigenvector ‫ﯾﮏ ﻣﺎﺗﺮﯾﺲ ﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﻧﻤﺎﯾﺪ. ﻓﺮﺁﯾﻨﺪ ﺗﮑﺮﺍﺭ ﺭﺍ ﻣﯽﺗﻮﺍﻥ ﺑﺎ ﻫﺮ ﻣﻘﺎﺩﯾﺮ ﺍﻭﻟﯿﻪ ﺍﺯ ‪ PageRankﺷﺮ ﻭﻉ ﻧﻤﻮﺩ. ﻫﻤﭽﻨﯿﻦ ﻓﺮﺁﯾﻨﺪ ﺗﮑﺮﺍﺭ ﻫﻨﮕﺎﻣﯽ ﭘﺎﯾﺎﻥ ﻣﯽﭘﺬﯾﺮﺩ

ﮐﻪ ﺩﯾﮕﺮ ﻣﻘﺎﺩﯾﺮ ‪ PageRankﺗﻐﯿﯿﺮﻧﮑﻨﺪ ﯾﺎ ﺑﻪ ﻋﺒﺎﺭﺕ ﺩﯾﮕﺮ ﺍﯾﻦ ﻣﻘﺎﺩﯾﺮ ﻫﻤﮕﺮﺍ ﺷﻮﻧﺪ. ﺩﺭ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ﺍﺭﺍﺋﻪﺷﺪﻩ ﺩﺭ ﺯﯾﺮ ﺑﺮﺍﯼ ‪ PageRank ﺗﮑﺮﺍﺭ ﻫﻨﮕﺎﻣﯽ ‫ﮐﻤﺘﺮﺷﻮﺩ. ﻧﺮﻡ ﻣﺮﺗﺒﻪ ﺍﻭﻝ ﯾﮏ ﺑﺮﺩﺍﺭ ﻣﺠﻤﻮﻉ ‫ﻣﺘﻮﻗﻒﻣﯽﺷﻮﺩ ﮐﻪ ﻧﺮﻡ ﻣﺮﺗﺒﻪ ﺍﻭﻝ 1-Normﺑﺮﺩﺍﺭ ﻣﻘﺎﺩﯾﺮ ‪ Pagerankﺍﺯﯾﮏ ﻣﻘﺪﺍﺭ ﺗﻌﯿﯿﻦ ﺷﺪﻩ ﻧﻈﯿﺮ ‫ﻣﻘﺎﺩﯾﺮﺩﺭﺍﯾﻪﻫﺎﯼ ﺁﻥ ﺍﺳﺖ.

 

ﭼﻮﻥ ﺩﺭ ﺍﯾﻨﺠﺎ ﻫﺪﻑ ﻣﺤﺎﺳﺒﻪ ﺭﺗﺒﻪﺩﻫﯽ ﺻﻔﺤﺎﺕ ﻭﺏ ﺍﺳﺖ، ﻫﻤﮕﺮﺍﯾﯽ ﻭﺍﻗﻌﯽﻣﻤﮑﻦ ﺍﺳﺖ ﺿﺮ ﻭﺭﺗﯽ ﻧﺪﺍﺷﺘﻪ ﺑﺎﺷﺪ

 

 

ﺍﻟﮕﻮﺭﯾﺘﻢ ‪HITS

ﻗﺒﻞ ﺍﺯ ﺗﺸﺮ ﯾﺢ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ‪ HITSﺍﺑﺘﺪﺍﻧﺤﻮﻩ ﺟﻤﻊﺁﻭﺭﯼ ﺻﻔﺤﺎﺕ ﺑﺮﺍﯼ ﺭﺗﺒﻪﺩﻫﯽ ﺁﻧﻬﺎ ﺭﺍ ﺗﻮﺿﯿﺢ ﻣﯽﺩﻫﯿﻢ. ﺑﺎ ﺩﺍﺷﺘﻦ ﭘﺮﺱﻭﺟﻮq HITS ﻣﺠﻤﻮﻋﻪﺍﯼ ﺍﺯ ‫ﺻﻔﺤﺎﺕﺭﺍ ﺑﻪ ﺷﮑﻞ ﺯﯾﺮ ﺟﻤﻊ ﻣﯽﮐﻨﺪ:

1- ‫ ‫ﭘﺮﺱﻭﺟﻮﯼ ‪ qﺑﻪﯾﮏ ﺳﯿﺴﺘﻢ ﻣﻮﺗﻮﺭ ﺟﺴﺘﺠﻮ ﻓﺮﺳﺘﺎﺩﻩ ﻣﯽﺷﻮﺩ. ﺳﭙﺲ ﺗﻌﺪﺍﺩ ‪ tﺻﻔﺤﻪﺑﺎ ﺑﺎﻻﺗﺮ ﯾﻦ ﺭﺗﺒﻪ ﮐﻪ ﺗﺼﻮﺭ ﻣﯽﺷﻮﺩ ﻣﺮﺗﺒﻂﺗﺮ ﯾﻦ ﺻﻔﺤﺎﺕ ﺑﻪ ‫ﭘﺮﺱﻭﺟﻮﻫﺴﺘﻨﺪ، ﺍﺳﺘﺨﺮﺍﺝ ﻣﯽﺷﻮﻧﺪ. ﺍﯾﻦ ﺗﻌﺪﺍﺩ ﺩﺭ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ﺍﺭﺍﺋﻪﺷﺪﻩ ﺩﺭ ﻣﻘﺎﻟﻪ ﻣﺮﺑﻮﻁ ﺑﻪ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ‪ t = 200 ﺍﺳﺖ. ﺍﯾﻦ ﻣﺠﻤﻮﻋﻪ، ‫ﻣﺠﻤﻮﻋﻪﺭ ﯾﺸﻪ Root Set ، Wﻧﺎﻣﯿﺪﻩﻣﯽﺷﻮﺩ.

2- ﺑﺮﺍﯼ ﮔﺴﺘﺮﺵ ﻣﺠﻤﻮﻋﻪ ‪ Wﺻﻔﺤﺎﺗﯽ ﮐﻪ ﺑﻪ ﺻﻔﺤﻪﺍﯼ ﺩﺭ ‪ Wﭘﯿﻮﻧﺪﺩﺍﺩﻩﺍﻧﺪ ﻭ ﻫﻤﭽﻨﯿﻦ ﺻﻔﺤﺎﺗﯽ ﮐﻪ ﺍﺯ ﺻﻔﺤﻪﺍﯼ ﺍﺯ ‪ Wﺑﻪﺁﻧﻬﺎ ﭘﯿﻮﻧﺪ ﺯﺩﻩ ﺷﺪﻩ ‫ﺍﺳﺖﺑﻪ ﻣﺠﻤﻮﻋﻪ ‪ Wﺍﺿﺎﻓﻪﻣﯽﺷﻮﺩ. ﺑﻪ ﺍﯾﻦ ﺗﺮﺗﯿﺐ ﻣﺠﻤﻮﻋﻪ ﺑﺰ ﺭﮔﺘﺮ ‪ Sﮐﻪﻣﺠﻤﻮﻋﻪ ﭘﺎﯾﻪ Base Rootﮔﻔﺘﻪﻣﯽﺷﻮﺩ ﺑﻪ ﺩﺳﺖ ﻣﯽﺁﯾﺪ. ﺍﯾﻦ ‫ﻣﺠﻤﻮﻋﻪﻣﯽﺗﻮﺍﻧﺪ ﺑﺴﯿﺎﺭ ﺑﺰﺭﮒ ﺑﺎﺷﺪ. ﺑﻪ ﻫﻤﯿﻦ ﺟﻬﺖ ﺍﯾﻦ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ﺗﻌﺪﺍﺩ ﺻﻔﺤﺎﺗﯽ ﮐﻪ ﯾﮏ ﺻﻔﺤﻪ ﺩﺭ ‪ Wﻣﯽﺗﻮﺍﻧﺪﺑﻪ ﻣﺠﻤﻮﻋﻪ ‪ S ﺑﯿﺎﻭﺭﺩﺭﺍ ﺑﻪ ‫ﺗﻌﺪﺍﺩ ‪ kﻣﺤﺪﻭﺩﻣﯽﮐﻨﺪ. ﺩﺭ ﻣﻘﺎﻟﻪ ﻣﺮﺑﻮﻁ ﺑﻪ ‪ k = 50 ،HITSﺍﺳﺖ.

‫ ‫ﺑﻌﺪﺍﺯ ﺍﯾﻦ ﻣﺮﺍﺣﻞ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ‪ HITSﺑﺮﺭ ﻭﯼ ﻣﺠﻤﻮﻋﻪ ﺻﻔﺤﻪ ‪ Sﮐﺎﺭﻣﯽﮐﻨﺪ ﻭ ﺑﻪ ﻫﺮ ﺻﻔﺤﻪ ﺩﺭ ‪ Sﯾﮏﺍﻣﺘﺒﺎﺯ ﻧﻔﻮﺫ Authority Scoreﻭ ﯾﮏ ‫ﺍﻣﺘﯿﺎﺯﻗﻄﺒﯿﺖ Hub Scoreﺍﺧﺘﺼﺎﺹ ﻣﯽﺩﻫﺪ. ﻓﺮﺽ ﻣﯽﮐﻨﯿﻢ ﺗﻌﺪﺍﺩﺻﻔﺤﺎﺕ ﺩﺭ ‪ n ،Sﻣﯽﺑﺎﺷﺪ. ﮔﺮﺍﻑ (G = (V, Eﺭﺍ ﺑﻪ ﻋﻨﻮﺍﻥ ﮔﺮﺍﻑ ﺟﻬﺖﺩﺍﺭ ‫ﻣﺠﻤﻮﻋﻪ ‪ Sﺩﺭﻧﻈﺮ ﻣﯽﮔﯿﺮ ﯾﻢ ﮐﻪ ‪ Vﻧﻤﺎﯾﺎﻥﮔﺮﻣﺠﻤﻮﻋﻪ ﮔﺮﻩﻫﺎ ﯾﺎ ﺻﻔﺤﺎﺕ ﻭ ‪ Eﻧﯿﺰﯾﺎﻝﻫﺎ ﯾﺎ ﭘﯿﻮﻧﺪﻫﺎﯼ ﺟﻬﺖﺩﺍﺭ ﺩﺭ ﻣﺠﻤﻮﻋﻪ ‪ Sﺍﺳﺖ. ﻣﺎﺗﺮ ﯾﺲ ‪ Lﺭﺍ ﺑﻪ ‫ﻋﻨﻮﺍﻥﻣﺎﺗﺮ ﯾﺲ ﻫﻤﺴﺎﯾﮕﯽ ﮔﺮﺍﻑ ‪ Gﺩﺭﻧﻈﺮ ﻣﯽﮔﯿﺮ ﯾﻢ

 

ﺍﺯ ﺑﺮﺩﺍﺭ ‪ aﺑﻪﺻﻮﺭﺕ

‪ a = (a(۱), a(۲), . . . , a(n)T

ﺑﺮﺍﯼ ﻧﺸﺎﻥ ﺩﺍﺩﻥ ﺍﻣﺘﯿﺎﺯ ﻧﻔﻮﺫ ﻭ ﺍﺯ ﺑﺮﺩﺍﺭ ‪ hﺑﻪ ﺻﻮﺭﺕ

‪h = (h(۱), h(۲), . . . , h(n)T

‫ﺑﺮﺍﯼ ﻧﺸﺎﻥ ﺩﺍﺩﻥ ﺍﻣﺘﯿﺎﺯ ﻗﻄﺒﯿﺖ ﺗﻤﺎﻡ ﺻﻔﺤﺎﺕﺩﺭ ﻣﺠﻤﻮﻋﻪ ‪ Sﺍﺳﺘﻔﺎﺩﻩ ﻣﯽﮐﻨﯿﻢ. ﭘﺲ ﺧﻮﺍﻫﯿﻢ ﺩﺍﺷﺖ: ‪ h = La a = LT hﻣﺤﺎﺳﺒﻪ ﺍﻣﺘﯿﺎﺯ ﻧﻔﻮﺫ ﻭ ﻗﻄﺒﯿﺖ ‫ﺷﺒﯿﻪ ﻣﺤﺎﺳﺒﻪﺍﻣﺘﯿﺎﺯ ‪ PageRankﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ‪ Power Iteration Methodﺍﺳﺖ. ﺍﮔﺮ ‪ akﻭ ‪ hkﻧﻤﺎﯾﺎﻥﮔﺮ ﺍﻣﺘﯿﺎﺯﻫﺎﯼ ﻧﻔﻮﺫ ﻭ ﻗﻄﺒﯿﺖ ﺩﺭ ‪kﺍﻣﯿﻦ ﺗﮑﺮﺍﺭﺑﺎﺷﺪ ‫ﺁﻧﮕﺎﻩ ﻓﺮﺁﯾﻨﺪ ﺗﮑﺮﺍﺭﯼ ﺑﺎ ﺗﺮﮐﯿﺐ ﺩﻭ ﺭﺍﺑﻄﻪﺑﺎﻻ ﺟﻬﺖ ﺗﻮﻟﯿﺪ ﺟﻮﺍﺏ ﻧﻬﺎﯾﯽ ﺑﻪ ﺻﻮﺭﺕ

‫ ‫1−‪ak = LT Lak

‫1−‪hk = LLT hk

‫ﺑﺎ ﻣﻘﺎﺩﯾﺮﺍﻭﻟﯿﻪ (۱ , . . . , ,۱ ,۱)= a0=h0ﺧﻮﺍﻫﺪ ﺑﻮﺩ.

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

اﻟﮕﻮرﻳﺘﻤﻲ ﻣﺒﺘﻨﻲ ﺑﺮ ﺳﺎﺧﺘﺎر ﭘﻴﻮﻧﺪي ﺻﻔﺤﺎت و اﻃﻼﻋﺎت اﺳﺘﻔﺎده ﻛﺎرﺑﺮان ﺑﺮاي ‫ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎت وب
‫ ﻣﺤﻤﺪرﺿﺎ ﻣﻴﺒﺪي (‫داﻧﺸﻜﺪه ﻣﻬﻨﺪﺳﻲ ﻛﺎﻣﭙﻴﻮﺗﺮ و ﻓﻨﺎوري اﻃﻼﻋﺎت ‫داﻧﺸﮕﺎه ﺻﻨﻌﺘﻲ اﻣﻴﺮﻛﺒﻴﺮ ‫ﺗﻬﺮان اﻳﺮان)

رعنا فرصتي(دانشكده مهندسي برق، رايانه و فناوري اطلاعات دانشگاه آزاد اسلامي قزوين ايران)

اﺳﺘﻔﺎده ﻫﻤﺰﻣﺎن از اﻃﻼﻋﺎت ﺳﺎﺧﺘﺎري و اﻃﻼﻋﺎت ﭘﻴﻤﺎﻳﺶ ﻛﺎرﺑﺮان ﻳﻜﻲ از ﭼﺎﻟﺶﻫﺎي ﻣﻄﺮح در ﺑﻬﺒﻮد ﻛﺎراﻳﻲ اﻟﮕﻮرﻳﺘﻢﻫﺎي ‫ﺷﺨﺼﻲﺳﺎزي وب ﻣﻲﺑﺎﺷﺪ. اﻟﮕﻮرﻳﺘﻤﻲ ﺗﺮﻛﻴﺒﻲ ﻛﻪ از اﻃﻼﻋﺎت ﭘﻴﻤﺎﻳﺶ ﻛﺎرﺑﺮان و ﭘﻴﻮﻧﺪ ﺑﻴﻦ ﺻﻔﺤﺎت ‫ﺑﻪﻣﻨﻈﻮر ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎت ﺑﻪ ﻛﺎرﺑﺮان اﺳﺘﻔﺎده ﻣﻲﻛﻨﺪ، اراﺋﻪ ﺷﺪه اﺳﺖ. ﻣﻌﻴﺎر ﻣﻌﺮﻓﻲ ﺷﺪه ﺑﺮاي ﻣﺤﺎﺳﺒﻪ وزن ﺻﻔﺤﺎت ﻣﺸﺎﻫﺪه ﺷﺪه ﺗﻮﺳﻂ ‫ﻛﺎرﺑﺮان از "ﻣﺪت زﻣﺎن ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ" و "ﻓﺮﻛﺎﻧﺲ ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ" اﺳﺘﻔﺎده ﻣﻲﻛﻨﺪﻛﻪ ﺑﻪ ﺧﻮﺑﻲ ﻣﻴﺰان اﻫﻤﻴﺖ و ﻋﻼﻗﻪ ﻛﺎرﺑﺮان ﺑﻪ آن ﺻﻔﺤﻪ را ‫ﻧﺸﺎن ﻣﻲدﻫﺪ. اﻟﮕﻮرﻳﺘﻢ اراﺋﻪ ﺷﺪه دو ﻣﺸﻜﻞ اﺳﺎﺳﻲ را در ﺷﺨﺼﻲ ﺳﺎزي ﺻﻔﺤﺎت وب ﺣﻞ ﻣﻲ ﻛﻨﺪ. ﻣﺸﻜﻞ اول ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎت ﺟﺪﻳﺪي اﺳﺖ ‫ﻛﻪ اﺧﻴﺮا ﺑﻪ ﺳﺎﻳﺖ اﺿﺎﻓﻪ ﺷﺪه اﻧﺪ و ﻣﺸﻜﻞ دوم ﻛﺎﻫﺶ دﻗﺖ اﻟﮕﻮرﻳﺘﻤﻬﺎ ﺑﺎ اﻓﺰاﻳﺶ ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي ﻣﻲ ﺑﺎﺷﺪ. در اﻟﮕﻮرﻳﺘﻢ اراﺋﻪ ﺷﺪه ‫اوﻟﻴﻦﺻﻔﺤﻪ ﺑﺎ اﺳﺘﻔﺎده از ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ورن دار ﺟﺪﻳﺪ اراﺋﻪ ﺷﺪه ﭘﻴﺸﻨﻬﺎد ﻣﻲ ﺷﻮد. ﺳﭙﺲ اﻳﻦﺻﻔﺤﻪ ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﻳﺘﻢ ‪ HITSو ‫ﺻﻔﺤﺎﺗﻲﻛﻪ ﺑﺎ آن در ﻳﻚ دﺳﺘﻪ ﺑﻨﺪي ﻫﺴﺘﻨﺪ ﺑﺴﻂ داده ﻣﻲ ﺷﻮد ﺗﺎ ﺻﻔﺤﺎﺗﻲ ﻛﻪ اﺧﻴﺮا ﺑﻪ ﺳﺎﻳﺖ اﺿﺎﻓﻪﺷﺪه اﻧﺪ ﻧﻴﺰ ﻓﺮﺻﺖ ﺣﻀﻮر در ﻣﺠﻤﻮﻋﻪ ‫ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي را داﺷﺘﻪ ﺑﺎﺷﻨﺪ. ﺑﺮاي دﺳﺘﻪ ﺑﻨﺪي ﺻﻔﺤﺎت اﻟﮕﻮرﻳﺘﻤﻲ ﺑﺮ اﺳﺎس آﺗﺎﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ و اﻟﮕﻮرﻳﺘﻢ ﻫﺎي اﻓﺮاز ﮔﺮاف اراﺋﻪ ﺷﺪه اﺳﺖ. ‫

در اﻳﻦ اﻟﮕﻮرﻳﺘﻢ ﺻﻔﺤﺎت ﺑﺮ ‫اﺳﺎس ﻣﻌﻴﺎر ﺟﺪﻳﺪي ﻛﻪ ﺑﻪ ﺧﻮﺑﻲ ﻣﻴﺰان ﻋﻼﻗﻪ ﻛﺎرﺑﺮان و اﻫﻤﻴﺖ آن ﺻﻔﺤﻪ را ﻧﺸﺎن ﻣﻲدﻫﺪ، وزندﻫﻲﻣﻲﺷﻮﻧﺪ. از آﻧﺠﺎ ﻛﻪ دﻗﺖ اوﻟﻴﻦ ﺻﻔﺤﻪ ‫ﭘﻴﺸﻨﻬﺎدي در اﻟﮕﻮرﻳﺘﻢﻫﺎي اراﺋﻪ ﺷﺪه ﺑﺎﻻ ﻣﻲﺑﺎﺷﺪ و ﺑﺎ اﻓﺰاﻳﺶ ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي، دﻗﺖ ﺑﻪ ﻣﻴﺰان ﻗﺎﺑﻞ ﺗﻮﺟﻬﻲ ﻛﺎﻫﺶ ﭘﻴﺪا ﻣﻲ ‫ﻛﻨﺪﭘﻴﺸﻨﻬﺎد اوﻟﻴﻦ ﺻﻔﺤﻪ ﺑﺮ اﺳﺎس دادهﻫﺎي اﺳﺘﻔﺎده ﻛﺎرﺑﺮان ﺻﻮرت ﻣﻲﮔﻴﺮد و ﭘﻴﺸﻨﻬﺎد ﺑﻘﻴﻪ ﺻﻔﺤﺎت ﺑﺎ اﺳﺘﻔﺎده از دﺳﺘﻪﺑﻨﺪي ‫ﺻﻔﺤﺎت و دادهﻫﺎي ﺳﺎﺧﺘﺎر ﺳﺎﻳﺖ ﺻﻮرت ﻣﻲﮔﻴﺮد. اﻳﻦ روش ﻛﻴﻔﻴﺖ ﭘﻴﺸﻨﻬﺎد را ﺗﺎ ﺣﺪ زﻳﺎدي ﺑﻬﺒﻮد ﻣﻲدﻫﺪ. ﺷﻬﻮد اﻳﻦ اﻳﺪه ﺑﺮ اﺳﺎس اﻃﻼﻋﺎت ‫ﺿﻤﻨﻲﭘﻴﻮﻧﺪ ﺻﻔﺤﺎت اﺳﺖ، زﻳﺮا ﻛﻪ ﻃﺮاﺣﺎن ﺻﻔﺤﺎت وب از ﻳﻚ ﺻﻔﺤﻪ ﺑﻪ ﺻﻔﺤﻪاي دﻳﮕﺮ در ﺻﻮرﺗﻲ ﭘﻴﻮﻧﺪﻗﺮار ﻣﻲدﻫﻨﺪ ﻛﻪ ﻋﻨﻮان و ﻣﺤﺘﻮاي ‫ﺻﻔﺤﺎت ﻣﺬﻛﻮر در راﺳﺘﺎي ﻣﺤﺘﻮاي ﻫﻢ ﺑﺎﺷﻨﺪ. از ﻃﺮﻓﻲ، اﺳﺘﻔﺎده از ﺳﺎﺧﺘﺎر ﺳﺎﻳﺖ، ﺑﺮاي ﺻﻔﺤﺎت ﺟﺪﻳﺪﻳﺎ ﺻﻔﺤﺎت ﺑﺎ ﻓﺮﻛﺎﻧﺲ ﻣﺸﺎﻫﺪه ﻛﻢ ﻧﻴﺰ ﻓﺮﺻﺖ ﺣﻀﻮر در ﻣﺠﻤﻮﻋﻪ ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي را ﻓﺮاﻫﻢ ﻣﻲﻛﻨﺪ و ﻣﺸﻜﻞ ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎت ﺟﺪﻳﺪ را در ﺳﺎﻳﺖﻫﺎي ﭘﻮﻳﺎ ﺣﻞ ﻣﻲﻛﻨﺪ. ﻣﻌﻤﺎري ﻛﻠﻲ ‫ﺳﻴﺴﺘﻢﭘﻴﺸﻨﻬﺎدي در ﺷﻜﻞ 1 ﻧﻤﺎﻳﺶ داده ﺷﺪه اﺳﺖ. در اداﻣﻪ در زﻳﺮﺑﺨﺶﻫﺎي ﺟﺪاﮔﺎﻧﻪ ﻫﺮ ﻳﻚ از ﺑﺨﺶﻫﺎي اﻟﮕﻮرﻳﺘﻢ ﺑﻪ ﺗﻔﺼﻴﻞ ﺑﺮرﺳﻲ ﺷﺪه ‫اﺳﺖ.

 

1- ﺗﻌﻴﻴﻦ وزن ﺻﻔﺤﺎت

‫در اﻳﻦ ﺑﺨﺶ روﺷﻲ ﺑﺮاي وزندﻫﻲ ﺻﻔﺤﺎت در ﻧﺸﺴﺖﻫﺎي ﻛﺎرﺑﺮان اراﺋﻪ ﻣﻲﻛﻨﻴﻢ. ﻓﺮض ﻛﻨﻴﻢ ﻛﻪ ‪ Pﻣﺠﻤﻮﻋﻪﺻﻔﺤﺎت ﻗﺎﺑﻞ دﺳﺘﺮﺳﻲ ‫ﺗﻮﺳﻂﻛﺎرﺑﺮان ﻳﻚ ﺳﺎﻳﺖ ﺑﺎﺷﺪ، } ‪ P = { p1 , p 2 ,..., p mﻛﻪ ﻫﺮ ﺻﻔﺤﻪ ﺑﺎ ‪ URLﻣﻨﺤﺼﺮﺑﻔﺮد ﻣﻮﺟﻮد ﻣﻲﺑﺎﺷﺪ. ﻫﻤﭽﻨﻴﻦ ‪ Tﻣﺠﻤﻮﻋﻪ ‫ﺗﺮاﻛﻨﺶﻫﺎي ﻛﺎرﺑﺮان در ﻓﺎﻳﻞ ﭘﻴﺶ ﭘﺮدازش ﺷﺪه ﺛﺒﺖ وﻗﺎﻳﻊ ﺑﺎﺷﺪ {‪ T = {t1 , t 2 ,..., t nﻛﻪ در آن ﺗﺮاﻛﻨﺶ ‪ t i ∈ Tزﻳﺮﻣﺠﻤﻮﻋﻪ اي از ‫ﺻﻔﺤﺎت ‪ Pﻣﻲﺑﺎﺷﺪ. ﻫﺮ ﺗﺮاﻛﻨﺶ ‪ t iرا ﺑﺼﻮرت ﺑﺮدار ‪ mﺗﺎﻳﻲ از ﺻﻔﺤﺎت ﻣﺪل ﻣﻲﻛﻨﻴﻢ

}(‪ ti = {( p1 , w1 ), ( p2 , w2 ),..., ( pm , wm

ﻛﻪ ‫‪ wiوزن ﺻﻔﺤﻪ ‪ p iدرﺗﺮاﻛﻨﺶ ‪ t iﻣﻲ ﺑﺎﺷﺪ. در اﻳﻦ ﻣﻘﺎﻟﻪ ﺑﺮﺧﻼف اﻛﺜﺮ ﻣﻘﺎﻻت ﻛﻪ از روش ﺑﺎﻳﻨﺮي ﺑﻪﻋﻨﻮان وزن ﺻﻔﺤﻪ اﺳﺘﻔﺎده ﻣﻲﻛﻨﻨﺪ، از ‫ﻣﻌﻴﺎر ﺟﺪﻳﺪي ﻣﺒﻨﻲ ﺑﺮ "ﻣﺪت زﻣﺎن ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ" و "ﻓﺮﻛﺎﻧﺲ ﺻﻔﺤﻪ" ﺑﺮاي وزندﻫﻲﺻﻔﺤﺎت اﺳﺘﻔﺎده ﻣﻲﺷﻮد ﻛﻪ ﻣﺸﺎﻫﺪات زﻳﺮ اﻋﺘﺒﺎر اﻳﻦ ‫ﻣﻌﻴﺎر را ﺗﺎﻳﻴﺪ ﻣﻲﻛﻨﻨﺪ:

‫1 - در ﻳﻚ ﻧﺸﺴﺖ، اﻣﻜﺎن دارد ﻛﺎرﺑﺮ ﺑﻪ ﻳﻚ ﺻﻔﺤﻪ ﭼﻨﺪ ﺑﺎر ﻣﺮاﺟﻌﻪ ﻛﻨﺪ ﻛﻪ ﻫﺮ ﭼﻘﺪر ﺗﻌﺪاد اﻳﻦ ارﺟﺎع ﻫﺎ ﺑﻪ ﻳﻚ ﺻﻔﺤﻪ در ﻳﻚ ﻧﺸﺴﺖ ‫ﺑﻴﺸﺘﺮﺑﺎﺷﺪ ، آن ﺻﻔﺤﻪ در ﻧﺸﺴﺖ ﻣﺬﻛﻮر ﻧﺴﺒﺖ ﺑﻪ ﺳﺎﻳﺮ ﺻﻔﺤﺎت ﻧﺸﺴﺖ ﻣﻬﻤﺘﺮ اﺳﺖ. ﻫﻤﭽﻨﻴﻦ در ﻣﻘﺎﻳﺴﻪ دو ﺻﻔﺤﻪاي ﻛﻪ ﺗﻌﺪاد دﻓﻌﺎت ﻳﻜﺴﺎﻧﻲ در ﻳﻚ ﻧﺸﺴﺖ ﻣﻼﻗﺎت ﺷﺪهاﻧﺪ، ﺻﻔﺤﻪاي ﻛﻪ ﺑﻪ آن از ﺗﻌﺪاد ﺻﻔﺤﺎت ﻛﻤﺘﺮي ﭘﻴﻮﻧﺪ وﺟﻮد دارد، ﻣﻬﻤﺘﺮ اﺳﺖ زﻳﺮا ﻛﻪ اﻳﻦ ﺻﻔﺤﻪ اﺣﺘﻤﺎل ‫ﻣﻼﻗﺎت ﺑﺎﻟﻘﻮه ﭘﺎﻳﻴﻦﺗﺮي دارد.

‫2- "ﻣﺪت زﻣﺎن ﻣﺸﺎﻫﺪه" ﺻﻔﺤﻪ ﺗﻮﺳﻂ ﻛﺎرﺑﺮ ﻣﻴﺰان اﻫﻤﻴﺖ ﺻﻔﺤﻪ را ﻧﺸﺎن ﻣﻲ دﻫﺪ زﻳﺮا اﮔﺮ ﺻﻔﺤﻪاي ﺑﺮاي ﻛﺎرﺑﺮ ﺟﺬاب ﻧﺒﺎﺷﺪ ‫ﺻﻔﺤﻪ را رد ﻛﺮده و ﺑﻪ ﺻﻔﺤﻪ دﻳﮕﺮي ﻣﺮاﺟﻌﻪ ﻣﻲﻛﻨﺪ، در ﺣﺎﻟﻴﻜﻪ اﮔﺮ ﺻﻔﺤﻪ ﻣﻮرد ﻋﻼﻗﻪ ﻛﺎرﺑﺮ ﺑﺎﺷﺪ زﻣﺎن ﻗﺎﺑﻞ ﻣﻼﺣﻈﻪاي را ﺻﺮف ﻣﺸﺎﻫﺪه آن ‫ﺧﻮاﻫﺪﻛﺮد. اﻟﺒﺘﻪ ﺑﺎﻳﺪ در ﻧﻈﺮ داﺷﺖ ﻛﻪ اﮔﺮ ﻃﻮل ﺻﻔﺤﻪ وﺑﻲ ﻛﻢ ﺑﺎﺷﺪ، زﻣﺎن ﻣﺸﺎﻫﺪه آن ﺻﻔﺤﻪ ﻧﻴﺰﻣﺘﻨﺎﺳﺒﺎ ﻛﻤﺘﺮ ﻣﻲﺷﻮد. ﻟﺬا زﻣﺎن ﻣﺸﺎﻫﺪه ‫ﺻﻔﺤﻪﻣﺘﻨﺎﺳﺐ ﺑﺎ اﻧﺪازه ﺻﻔﺤﻪ اﺳﺖ و در ﻣﺤﺎﺳﺒﻪ اﻫﻤﻴﺖ ﺻﻔﺤﻪ اﻳﻦ ﺗﻨﺎﺳﺐ ﺑﺎﻳﺪ در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﺷﻮد.

‫ﺑﻨﺎﺑﺮاﻳﻦ "ﻣﺪت زﻣﺎن ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ" و "ﻓﺮﻛﺎﻧﺲ ﺻﻔﺤﻪ" دو ﻣﻌﻴﺎر اﺳﺎﺳﻲ در ﺗﻌﻴﻴﻦ اﻫﻤﻴﺖ و ﻣﻴﺰان ﻋﻼﻗﻪ ﻛﺎرﺑﺮ ﺑﻪ ﺻﻔﺤﻪ ﻣﻲﺑﺎﺷﺪ. در ‫رواﺑﻂ زﻳﺮ (f p (P ﻓﺮﻛﺎﻧﺲ ﺻﻔﺤﻪ و ( d p (Pﻣﺪت زﻣﺎن ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ را ﻧﻤﺎﻳﺶ ﻣﻲ دﻫﺪ.

 

 

‫2-2- ﭘﻴﺸﻨﻬﺎد ﺗﻚ ﺻﻔﺤﻪاي ﺑﺮ اﺳﺎس ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ وزن دار

‫در اﻳﻦ ﻗﺴﻤﺖ اﻟﮕﻮرﻳﺘﻲ ﻣﺒﺘﻨﻲ ﺑﺮ ﻗﻮاﻋﺪ اﻧﺠﻤﻨﻲ ﺑﺮاي ﭘﻴﺸﻨﻬﺎد ﺗﻚ ﺻﻔﺤﺎت اراﺋﻪ ﻣﻲﻛﻨﻴﻢ. ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﺑﻪ ﻃﻮر ﻣﻮﻓﻘﻴﺖ آﻣﻴﺰي در ‫ﺳﻴﺴﺘﻢﻫﺎي ﭘﻴﺸﻨﻬﺎد دﻫﻨﺪه وب اﺳﺘﻔﺎده ﺷﺪهاﻧﺪ و ﻧﺘﺎﻳﺞ ﺗﺠﺮﺑﻲ ﺧﻮﺑﻲ ﺑﺮاي ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﺑﻪ ﻋﻨﻮان ﺳﻴﺴﺘﻢ ﭘﻴﺸﻨﻬﺎددﻫﻨﺪه ﺻﻔﺤﺎت ﮔﺰارش ‫ﺷﺪه اﺳﺖ . در ﻛﺎرﻫﺎي اﻧﺠﺎم ﺷﺪه ﻫﻤﻪ آﻳﺘﻢ ﻫﺎ (ﺻﻔﺤﺎت) ﺑﺪون ﺗﻮﺟﻪ و ﻣﺤﺎﺳﺒﻪ وزن ﺻﻔﺤﺎت در ﺗﺮاﻛﻨﺶﻫﺎ ارزش و اﻫﻤﻴﺖ ﻳﻜﺴﺎﻧﻲ ‫دارﻧﺪ. در اﻳﻦ روشﻫﺎ، ﭘﺎﻳﮕﺎهداده ﻣﺠﻤﻮﻋﻪاي از ﺻﻔﺤﺎت ﻣﻮﺟﻮد در ﻧﺸﺴﺖ ﻫﺎي ﻛﺎرﺑﺮان {{ T = {t1 , t 2 ,..., t nدر ﺗﺮاﻛﻨﺶﻫﺎ ﻣﻲ ﺑﺎﺷﺪ. ‫درﺻﻮرﺗﻴﻜﻪﻫﺮ ﺻﻔﺤﻪ را در ﭘﺎﻳﮕﺎه داده ﻳﻚ آﻳﺘﻢﺳﺖ در ﻧﻈﺮ ﺑﮕﻴﺮﻳﻢ, ﻳﻚ ﻣﺠﻤﻮﻋﻪ آﻳﺘﻢﺳﺖ ﺑﻪ ﺻﻮرت

{ ‪ I = {i1 , i2 ,..., inﺧﻮاﻫﻴﻢ داﺷﺖ. ‫ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﻛﻪ ﺑﺮاي ﻳﺎﻓﺘﻦ ارﺗﺒﺎط ﺑﻴﻦ دادهﻫﺎي ذﺧﻴﺮهﺷﺪه در ﺗﺮاﻛﻨﺶﻫﺎ ﺑﻜﺎر ﻣﻲروﻧﺪ ﺑﻪ ﺷﻜﻞ ‫‪ X ⇒ Y , where X ⊂ I , Y ⊂ I , X ∩ Y = φﺗﻌﺮﻳﻒﻣﻲﮔﺮدد ﻛﻪ ‪ X ,Yآﻳﺘﻢﺳﺖ ﻣﻲﺑﺎﺷﻨﺪ. ﻫﺪف از ﺗﻮﻟﻴﺪ اﻳﻦ ﻗﻮاﻧﻴﻦ ﻣﺤﺎﺳﺒﻪ اﻳﻦ ‫ْ ‫اﺣﺘﻤﺎل اﺳﺖ ﻛﻪ ﭼﻪ ﺗﻌﺪاد از ﺗﺮاﻛﻨﺶ ﻫﺎﻳﻲ ﻛﻪ ‪ Xرا دارﻧﺪ , ‪ Yرا ﻧﻴﺰﺷﺎﻣﻞ ﻣﻲﺷﻮﻧﺪ ﻛﻪ ﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن ﻗﻮاﻧﻴﻦ ﻧﺎﻣﻴﺪه ﻣﻲﺷﻮد. ﻗﻮاﻧﻴﻦ ‫اﻧﺠﻤﻨﻲ ارﺗﺒﺎط ﺑﻴﻦ آﻳﺘﻢﻫﺎ را ﺑﺮ اﺳﺎس اﻳﻨﻜﻪ در ﺗﺮاﻛﻨﺶﻫﺎ ﺑﺎ ﻫﻢ اﺗﻔﺎق ﻣﻲاﻓﺘﻨﺪ ﺑﻴﺎن ﻣﻲﻛﻨﺪ. در ﺗﺮاﻛﻨﺶﻫﺎي وب، ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ارﺗﺒﺎط ﺑﻴﻦ ‫ﺻﻔﺤﺎت را ﺑﺮ اﺳﺎس رﻓﺘﺎر ﻫﺪاﻳﺘﻲ ﻛﺎرﺑﺮان ﺑﻴﺎن ﻣﻲﻛﻨﺪ.

در اﻳﻦ ﻣﻘﺎﻟﻪ ﺑﺮﺧﻼف روشﻫﺎي ﻗﺒﻠﻲ ﻛﻪ ﺑﺮاي ﻫﻤﻪ ﺻﻔﺤﺎت وزن ﻳﻜﺴﺎﻧﻲ در ﻧﻈﺮ ﻣﻲﮔﻴﺮﻧﺪ، ﺑﻪ ﻫﺮ ﺻﻔﺤﻪ در ﺗﺮاﻛﻨﺶ ﻣﻄﺎﺑﻖ راﺑﻄﻪ 3 وزﻧﻲ ‫ﺗﺮاﻛﻨﺶﻫﺎي ﻛﺎرﺑﺮان ﺑﻪ ‫ﻧﺴﺒﺖ داده ﻣﻲﺷﻮد. ﺳﭙﺲﺑﺎ اﺳﺘﻔﺎده از ﻛﺎوش ﻗﻮاﻧﻴﻦ، ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ وزندار از ﻣﺠﻤﻮﻋﻪ ‫ﺷﻜﻞ ‪ C } ∈ Rو ‪ Sو (‪ r = {( p i , wi ), ( p j , w j ),...( p K , wk ) ⇒ ( p m , wm ),...( p n , wnاﺳﺘﺨﺮاج ﻣﻲﺷﻮد ﻛﻪ در آن ‫‪ Sﺿﺮﻳﺐﭘﺸﺘﻴﺒﺎﻧﻲ و ‪ Cﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن ﻗﻮاﻧﻴﻦ و ‪ wiوزن ﺻﻔﺤﺎت ﻣﻲﺑﺎﺷﺪ. در اﻳﻦ ﻣﺪل در ﺣﻴﻦ ﺗﻮﻟﻴﺪ ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ در ﻛﻨﺎر ﺿﺮاﻳﺐ ‫ﭘﺸﺘﻴﺒﺎﻧﻲ5 و اﻃﻤﻴﻨﺎن ﻗﻮاﻧﻴﻦ6، وزن ﺻﻔﺤﻪ ( ﻣﻴﺰان اﻫﻤﻴﺖ و ﻋﻼﻗﻪ ﻛﺎرﺑﺮ ﺑﻪ آن ﺻﻔﺤﻪ) ﻧﻴﺰ ﻧﻤﺎﻳﺶ داده ﻣﻲ ﺷﻮد. ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ وزن دار ارﺗﺒﺎط ‫ﺑﻴﻦﺻﻔﺤﺎت را ﺑﻬﺘﺮ ﺑﻴﺎن ﻣﻲﻛﻨﻨﺪ ﭼﺮا ﻛﻪ ﺑﻪ ﺻﻔﺤﺎﺗﻲ ﻛﻪ وزن ﺑﺎﻻﺗﺮي دادﻧﺪ ﺗﻮﺟﻪ ﺑﻴﺸﺘﺮي ﻣﻲﺷﻮد و اﻧﺘﺴﺎب وزن ﺑﺎﻻﺗﺮ ﺑﻪ ﺻﻔﺤﺎت ﻣﻬﻤﺘﺮ، ﺑﻪ ‫اﺳﺘﺨﺮاج ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﻣﻬﻤﺘﺮ اﻣﺎ ﺑﺎ ﺗﻜﺮار ﻛﻤﺘﺮ ﻛﻤﻚ ﻣﻲ ﻛﻨﺪ. ‫ﺿﺮﻳﺐﭘﺸﺘﻴﺒﺎﻧﻲ در راﺑﻄﻪ ﺑﺎﻻ ﺑﻴﺎﻧﮕﺮ درﺻﺪ ﺗﺮاﻛﻨﺶ ﻫﺎﻳﻲ اﺳﺖ ﻛﻪ ﺷﺎﻣﻞ آﻳﺘﻢ ﻫﺎ ﻣﻲ ﺑﺎﺷﻨﺪ. ﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن ﻗﻮاﻧﻴﻦ ﻣﻄﺎﺑﻖ راﺑﻄﻪ 4 ﻣﺤﺎﺳﺒﻪ ‫ﻣﻲﺷﻮد.

 

ﻫﺪف از ﺳﻴﺴﺘﻢ ﻫﺎي ﺷﺨﺼﻲ ﺳﺎزي ﻣﺤﺎﺳﺒﻪ ﻳﻚ ﻣﺠﻤﻮﻋﻪ ﭘﻴﺸﻨﻬﺎدي، ‪ ، rsﺑﺮاي ﻧﺸﺴﺖ ﻛﺎرﺑﺮ ﺟﺎري ﻣﻲﺑﺎﺷﺪﻛﻪ ﺑﻴﺸﺘﺮﻳﻦ ﺗﻄﺎﺑﻖ را ﺑﺎ ‫ﻋﻼﻳﻖﻛﺎرﺑﺮ داﺷﺘﻪ ﺑﺎﺷﺪ. اﻳﻦ ﺟﺰ ﺗﻨﻬﺎ ﺟﺰ ﺑﺮﺧﻂ ﺳﻴﺴﺘﻢ ﺑﻮده و ﺑﺎﻳﺪ از ﻛﺎراﻳﻲ و دﻗﺖ ﺑﺎﻻﻳﻲ ﺑﺮﺧﻮردار ﺑﺎﺷﺪ. ﻓﺮض ﻛﻨﻴﻢ ﻛﻪ ﻛﺎرﺑﺮي در ﺣﺎل ‫ﮔﺮدش در ﺳﺎﻳﺖ اﺳﺖ و ﻣﺴﻴﺮ ‪ p1 → p 2 → p3 → ... → p kرا ﭘﻴﻤﻮده اﺳﺖ. ﺗﻌﺪاد آﺧﺮﻳﻦ ﺻﻔﺤﺎﺗﻲ را ﻛﻪ ﺗﻮﺳﻂ ﻛﺎرﺑﺮ در ﻧﺸﺴﺖ ‫ﺟﺎري ﻣﺸﺎﻫﺪه ﺷﺪه و ﺑﺮاي ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎت ﺟﺪﻳﺪ ﻣﻮرد اﺳﺘﻔﺎده ﻗﺮارﻣﻲﮔﻴﺮد را ﭘﻨﺠﺮه ﭘﻴﺸﻨﻬﺎد ﻣﻲﻧﺎﻣﻴﻢ و اﻧﺪازه آن را ﺑﺎ ‪ rwﻧﺸﺎن ﻣﻲدﻫﻴﻢ ‫ﻛﻪ ﺣﺪاﻛﺜﺮ ﺑﺮاﺑﺮ ﺑﺎ ﺗﻤﺎم ﺻﻔﺤﺎت ﻣﺸﺎﻫﺪه ﺷﺪه و ﺣﺪاﻗﻞ ﺑﺮاﺑﺮ ﺑﺎ آﺧﺮﻳﻦ ﺻﻔﺤﻪ ﻣﺸﺎﻫﺪه ﺷﺪه ﻣﻲﺑﺎﺷﺪ. در ﭘﻨﺠﺮه ﻣﺸﺎﻫﺪه، ﺻﻔﺤﺎت اﺑﺘﺪاﻳﻲ ﻧﺸﺴﺖ ‫ﺟﺎري ﻛﺎرﺑﺮ ﻳﻌﻨﻲ ﺻﻔﺤﺎت اوﻟﻴﻪ ﻣﺸﺎﻫﺪه ﺷﺪه ﺗﻮﺳﻂ ﻛﺎرﺑﺮ، ﻧﻴﺎز ﺟﺎري ﻛﺎرﺑﺮ را ﺑﻪ ﺧﻮﺑﻲ ﺑﻴﺎن ﻧﻤﻲﻛﻨﻨﺪ و ﺻﻔﺤﺎت اﻧﺘﻬﺎﻳﻲ ﻧﺸﺴﺖ ﺑﻴﺸﺘﺮ ﮔﻮﻳﺎي ‫ﻧﻴﺎز آﺗﻲ ﻛﺎرﺑﺮ ﻫﺴﺘﻨﺪ. ﺑﻪ ﻋﺒﺎرت دﻳﮕﺮ ﺻﻔﺤﺎت ﺗﺎزه ﻣﺸﺎﻫﺪه ﺷﺪه ﺗﻮﺳﻂ ﻛﺎرﺑﺮ ﺑﺮاي اﺳﺘﻔﺎده در اﻟﮕﻮرﻳﺘﻢ ﭘﻴﺸﻨﻬﺎد ﻣﻨﺎﺳﺐﺗﺮ ﻣﻲﺑﺎﺷﻨﺪ.

. ‫اﻛﺜﺮﻣﻘﺎﻻﺗﻲ ﻛﻪ از ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﺑﺮاي ﻛﺸﻒ داﻧﺶ رﻓﺘﺎر ﭘﻴﻤﺎﻳﺸﻲ ﻛﺎرﺑﺮان اﺳﺘﻔﺎده ﻣﻲ ﻛﻨﻨﺪ، ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ را ﺑﺎ ﺑﺨﺶ ﻣﻘﺪم ‫ﻣﺠﻤﻮﻋﻪﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ اﺳﺘﺨﺮاج ﺷﺪه ﺗﻄﺎﺑﻖ دﻗﻴﻖ ﺻﻔﺤﻪ ﺑﻪ ﺻﻔﺤﻪ ﻣﻲﻛﻨﻨﺪ ﺗﺎ ﻣﺠﻤﻮﻋﻪ اي از ﺻﻔﺤﺎت را ﻛﻪ ﺗﺎ ﺑﻪ ﺣﺎل ﻛﺎرﺑﺮ ﻣﺸﺎﻫﺪه ﻧﻜﺮده ‫اﺳﺖﺑﻪ او ﭘﻴﺸﻨﻬﺎد دﻫﻨﺪ. وﻟﻲ ﻫﻴﭻ ﻛﺪام از آﻧﻬﺎ از وزن ﺻﻔﺤﺎت ﺑﺮاي رﺗﺒﻪ ﺑﻨﺪي ﺻﻔﺤﺎت ﻛﺎﻧﺪﻳﺪ اﺳﺘﻔﺎده ﻧﻜﺮدهاﻧﺪ. اﺳﺘﻔﺎده از اﻳﻦ روش و ﺗﻨﻬﺎ ‫ﺑﺎ اﺗﻜﺎ ﺑﻪ ﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن ﺑﻪ ﻋﻨﻮان ﻣﻴﺰان ﺗﺸﺎﺑﻪ ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ و ﻗﺎﻧﻮن اﻧﺠﻤﻨﻲ، ﺑﺎﻋﺚ ﻣﻲﺷﻮد ﻛﻪ ﻛﻴﻔﻴﺖ ﭘﻴﺸﻨﻬﺎد ﭘﺎﻳﻴﻦ ﺑﺎﺷﺪ زﻳﺮا ﻣﻤﻜﻦ ‫اﺳﺖ دو ﻗﺎﻧﻮن ﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن ﺑﺮاﺑﺮي داﺷﺘﻪ ﺑﺎﺷﻨﺪ، اﻣﺎ ﻛﺎرﺑﺮ ﻗﺎﻧﻮن اول زﻣﺎن ﺑﻴﺸﺘﺮي را در ﺑﺮﺧﻲ ﺻﻔﺤﺎت ﺧﺎص ﺻﺮف ﻛﺮده ﺑﺎﺷﺪ ﻛﻪ ﺗﻄﺎﺑﻖ ‫ﺑﻴﺸﺘﺮي ﺑﺎ ﻧﺸﺴﺖ ﻛﺎرﺑﺮ ﺟﺎري داﺷﺘﻪ ﺑﺎﺷﺪ ﻛﻪ در اﻳﻦ ﻣﻮارد ﺳﻴﺴﺘﻢﻫﺎي ﻣﻮﺟﻮد ﺑﻪ ﺻﻮرت ﺗﺼﺎدﻓﻲ ﻋﻤﻞﻣﻲﻛﻨﻨﺪ.

. ‫در اﻳﻦ ﻣﻘﺎﻟﻪ ﺑﺮاي ﭘﻴﺸﻨﻬﺎد ﺻﻔﺤﺎﺗﻲ ﺑﺎ ﺑﻴﺸﺘﺮﻳﻦ ﺷﺒﺎﻫﺖ ﺑﻪ ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ، ﺑﻪ ﺟﺎي ﺗﻄﺎﺑﻖﺻﻔﺤﻪ ﺑﻪ ﺻﻔﺤﻪ ﺑﻴﻦ ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ و ‫ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ، ﺷﺒﺎﻫﺖ ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ ﺑﺎ ﻣﺠﻤﻮﻋﻪ ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ وزن دار ﺗﻮﻟﻴﺪ ﺷﺪه ﻛﻪ در ﺑﺎﻻﺑﺮرﺳﻲ ﺷﺪ را ﺑﺎ اﺳﺘﻔﺎده از راﺑﻄﻪ 5 ‫ﻣﺤﺎﺳﺒﻪﻣﻲﻛﻨﻴﻢ و ﻗﻮاﻧﻴﻨﻲ ﺑﺎ ﺑﻴﺸﺘﺮﻳﻦ ﺷﺒﺎﻫﺖ و ﺑﺎﻻﺗﺮﻳﻦ ﺿﺮﻳﺐ اﻃﻤﻴﻨﺎن را ﺟﺴﺘﺠﻮ ﻣﻲ ﻛﻨﻴﻢ و اﻣﺘﻴﺎز آﻧﻬﺎ را ﺑﺮ اﺳﺎس راﺑﻄﻪ 6 ﻣﺤﺎﺳﻴﻪ ‫ﻣﻲﻛﻨﻴﻢ و ﺳﭙﺲ ﻣﺠﻤﻮﻋﻪاي از ﺻﻔﺤﺎت ﻣﺸﺎﺑﻪ ﻛﻪ ﺗﺎ ﺑﻪ ﺣﺎل ﺗﻮﺳﻂ ﻛﺎرﺑﺮ ﻣﻼﻗﺎت ﻧﺸﺪه اﻧﺪ را ﺑﺮاي ﭘﻴﺸﻨﻬﺎد اﻧﺘﺨﺎب ﻣﻲﻛﻨﻴﻢ. در ﺳﻤﺖ ‫راﺳﺖ(ﺑﺨﺶﺗﺎﻟﻲ) ﻗﻮاﻧﻴﻦ اﻧﺠﻤﻨﻲ ﻣﻤﻜﻦ اﺳﺖ ﭼﻨﺪﻳﻦ آﻳﺘﻢ (ﺻﻔﺤﻪ) ﺑﺎﺷﺪ اﻣﺎ ﺑﻪ ﺧﺎﻃﺮ ﻃﺒﻴﻌﺖ ﻣﺴﺎﻟﻪ ﭘﻴﺶﺑﻴﻨﻲ در اﻳﻦ ﻣﻘﺎﻟﻪ)ﭘﻴﺸﻨﻬﺎد ﺗﻚ ‫ﺻﻔﺤﻪ اي( و ﺗﻮﺳﻌﻪ آن ﺗﻮﺳﻂ داده ﻫﺎي ﺳﺎﺧﺘﺎر ﺳﺎﻳﺖ، ﻣﺎ ﺑﻪ ﺑﺮرﺳﻲ ﻗﻮاﻧﻴﻨﻲ ﻛﻪ ﻓﻘﻂ ﻳﻚ ﺻﻔﺤﻪ در ﺳﻤﺖ راﺳﺖ آﻧﻬﺎ ﺑﺎﺷﺪ ﻣﻲ ﭘﺮدازﻳﻢ. ﺑﻨﺎﺑﺮاﻳﻦ

‫‪s ‫ﻧﺸﺴﺖ ﺟﺎري ﻛﺎرﺑﺮ ‪( Sﭘﻨﺠﺮه ﭘﻴﺸﻨﻬﺎد ﺑﻪ ﻃﻮل ‪ )nو ﺑﺨﺶ ﻣﻘﺪم ﻗﻮاﻧﻴﻦ را ﺑﻪ ﺻﻮرت ﺑﺮداري

‪ S =< w1 , w 2 ,..., wn ‫>

‪ R =< w 1 , w 2 ,..., wm>

ﻧﻤﺎﻳﺶ داده و ﺷﺒﺎﻫﺖ آﻧﻬﺎ ﻣﻄﺎﺑﻖ راﺑﻄﻪ 5 ﺑﺪﺳﺖ ﻣﻲ آﻳﺪ.

 

ﺑﺎ ﻣﺮﺗﺐ ﻛﺮدن ﺻﻔﺤﺎت ﺑﺮ اﺳﺎس اﻣﺘﻴﺎز آﻧﻬﺎ، ﺑﺮاي ﺣﻞ ﻣﺸﻜﻞ ﻛﺎﻫﺶ دﻗﺖ اﻟﮕﻮرﻳﺘﻢﻫﺎ ﺑﺎ اﻓﺰاﻳﺶ ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي، ﻓﻘﻂ ﺻﻔﺤﻪ اي ‫را ﻛﻪ ﺑﻴﺸﺘﺮﻳﻦ اﻣﺘﻴﺎز را دارد اﻧﺘﺨﺎب ﻣﻲﻛﻨﻴﻢ. در اداﻣﻪ ﺑﺎ اﺳﺘﻔﺎده از ﻧﺘﺎﻳﺞ دﺳﺘﻪ ﺑﻨﺪي ﺻﻔﺤﺎت ﻛﻪ در ﺑﺨﺶ2-3 ﺑﺮرﺳﻲ ﻣﻲ ﺷﻮد دﺳﺘﻪاي ﻛﻪ ‫ﺻﻔﺤﻪﺑﻪ آن ﻣﺘﻌﻠﻖ اﺳﺖ را ﻳﺎﻓﺘﻪ و ‪ Nﺻﻔﺤﻪ (اﻧﺪازه ﭘﻨﺠﺮه ﭘﻴﺸﻨﻬﺎد) را از آن دﺳﺘﻪ ﺑﻪ ﻫﻤﺮاه ﺻﻔﺤﻪ اﺻﻠﻲ اﻧﺘﺨﺎب ﻣﻲ ﻛﻨﻴﻢ. در ﮔﺎم ﺑﻌﺪي ‫اﻟﮕﻮرﻳﺘﻢ، 1 + ‪ Nﺻﻔﺤﻪ اﻧﺘﺨﺎب ﺷﺪه در اﻳﻦ ﻣﺮﺣﻠﻪ را ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﻳﺘﻢ ‪ HITSﺑﺴﻂﻣﻲ دﻫﻴﻢ.

 

‫2-3- دﺳﺘﻪ ﺑﻨﺪي ﺻﻔﺤﺎت وب

‫ﻫﻤﺎﻧﻄﻮر ﻛﻪ ﮔﻔﺘﻪ ﺷﺪ، ﺑﺮاي ﺣﻞ ﻣﺸﻜﻞ ﻛﻴﻔﻴﺖ ﭘﺎﻳﻴﻦ ﭘﻴﺸﻨﻬﺎد ﺑﻴﺶ از ﻳﻚ ﺻﻔﺤﻪ، اﺑﺘﺪا ﻳﻚ ﺻﻔﺤﻪ را ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﻳﺘﻢ ﻗﻮاﻧﻴﻦ ‫اﻧﺠﻤﻨﻲ وزندار ﺗﻮﻟﻴﺪ ﻣﻲﻛﻨﻴﻢ و ﺳﭙﺲ اﻳﻦ ﺻﻔﺤﻪ را ﺑﺮ اﺳﺎس ﺻﻔﺤﺎت ﻣﺸﺎﺑﻪ ﺑﺴﻂ ﻣﻲدﻫﻴﻢ ﺗﺎ ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﻳﺘﻢ ‪ HITSﺻﻔﺤﺎت را ‫رﺗﺒﻪﺑﻨﺪي ﻛﺮده و ﭼﻨﺪ ﺻﻔﺤﻪ را ﭘﻴﺸﻨﻬﺎد ﻛﻨﻴﻢ. ﺑﺮاي ﺑﺴﻂ ﺻﻔﺤﻪ، در اﻳﻦ ﻗﺴﻤﺖ اﻟﮕﻮرﻳﺘﻢ ﺧﻮﺷﻪﺑﻨﺪي ﺟﺪﻳﺪي ﻣﺒﺘﻨﻲ ﺑﺮ اﺗﻮﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ و اﻓﺮاز ‫ﮔﺮاف اراﺋﻪ ﻣﻲﻛﻨﻴﻢ.

‫روشﻫﺎي ﻣﺘﻌﺪدي ﺑﺮاي ﺧﻮﺷﻪ ﺑﻨﺪي و ﺗﺸﺨﻴﺺ ﺷﺒﺎﻫﺖ ﺑﻴﻦ اﺳﻨﺎد وﺟﻮد دارد. ﻣﺘﺪاوﻟﺘﺮﻳﻦ روش اﺳﺘﻔﺎده از ﻛﻠﻤﺎت ﻛﻠﻴﺪي ﻣﻲﺑﺎﺷﺪ‫. اﺳﺘﻔﺎده از ﻛﻠﻤﺎت ﻛﻠﻴﺪي داراي ﻣﺸﻜﻼﺗﻲ ﻣﺎﻧﻨﺪ وﺟﻮد ﻛﻠﻤﺎت ﻣﺘﺮادف (ﻛﻠﻤﺎﺗﻲ ﺑﺎ ﻇﺎﻫﺮ ﻣﺘﻔﺎوت وﻟﻲ ﻣﻌﻨﺎي ﻳﻜﺴﺎن)، ﻛﻠﻤﺎت ﻣﺘﺸﺎﺑﻪ (ﻛﻠﻤﺎﺗﻲ ‫ﺑﺎ ﻇﺎﻫﺮ ﻳﻜﺴﺎن وﻟﻲ در ﻣﻌﻨﻲ ﻣﺘﻔﺎوت) ﻣﻲﺑﺎﺷﺪ. ﻋﻼوه ﺑﺮ اﻳﻦ، اﻳﻦ روﺷﻬﺎ ﺑﺮاي اﺳﻨﺎد ﻏﻴﺮ ﻣﺘﻨﻲ ﻣﺎﻧﻨﺪ ﺗﺼﺎوﻳﺮ، ﻓﻴﻠﻤﻬﺎ و اﺳﻨﺎد ﺻﻮﺗﻲ ﻛﻪ ﻣﺤﺘﻮاي ‫آﻧﻬﺎﻗﺎﺑﻞ اﺳﺘﺨﺮاج9 ﻧﻴﺴﺖ، ﻗﺎﺑﻞ اﺳﺘﻔﺎده ﻧﻤﻲﺑﺎﺷﺪ. ﺑﻨﺎﺑﺮاﻳﻦ در اداﻣﻪ روﺷﻲ ﻣﻌﺮﻓﻲ ﻣﻲﻛﻨﻴﻢ ﻛﻪﺑﺪون اﺳﺘﻔﺎده از ﻫﻴﭽﮕﻮﻧﻪ اﻃﻼﻋﺎﺗﻲ در ﺑﺎره ‫ﻣﺤﺘﻮاي اﺳﻨﺎد و ﺻﺮﻓﺎ ﺑﺎ ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮي رﻓﺘﺎر ﻛﺎرﺑﺮان، ﺑﺪون ﻧﻴﺎز ﺑﻪ اﺳﺘﻔﺎده از روﺷﻬﺎي ﺷﺒﺎﻫﺖ ﻓﺎﺻﻠﻪ و ﺑﺎ اﺳﺘﻔﺎده از روشﻫﺎي ﻣﺒﺘﻨﻲ ﺑﺮ ‫ﮔﺮاف ﺻﻔﺤﺎت را دﺳﺘﻪﺑﻨﺪي ﻣﻲﻛﻨﺪ.

‫اﻳﺪه اﻳﻦ روش ﺑﺮ اﻳﻦ اﺳﺎس اﺳﺖ ﻛﻤﺘﺮ ﭘﻴﺶ ﻣﻲآﻳﺪ ﻛﻪ ﻛﺎرﺑﺮان ﺳﺮاغ ﺻﻔﺤﺎت ﻏﻴﺮ ﻣﺮﺗﺒﻂ ﺑﺎ ﻳﻜﺪﻳﮕﺮﺑﺮوﻧﺪ و ﻟﺬا اﮔﺮ ﺗﻌﺪادي از ﻛﺎرﺑﺮان ‫ﺗﻌﺪادي از ﺻﻔﺤﺎت وب را ﭘﻲ در ﭘﻲ درﺧﻮاﺳﺖ ﻛﻨﻨﺪ، آﻧﮕﺎه اﺣﺘﻤﺎﻻ اﻳﻦ ﺻﻔﺤﺎت ﺑﻪ ﻧﻴﺎزﻫﺎي اﻃﻼﻋﺎﺗﻲﻳﻜﺴﺎﻧﻲ ﭘﺎﺳﺦ دادهاﻧﺪ و ﺑﻪ ﻳﻜﺪﻳﮕﺮ ﺷﺒﻴﻪ ‫ﻣﻲﺑﺎﺷﻨﺪ. اﻳﻦ روش ﺑﺮﮔﺮﻓﺘﻪ از اﻳﻦ واﻗﻌﻴﺖ ﻣﻲ ﺑﺎﺷﺪ ﻛﻪ ﺣﺮﻛﺖ ﻛﺎرﺑﺮان در ﺑﻴﻦ ﺻﻔﺤﺎت وب اﺗﻔﺎﻗﻲ ﻧﻴﺴﺖﺑﻠﻜﻪ ﻛﺎرﺑﺮان از ﻣﺤﺘﻮﻳﺎت ﺻﻔﺤﺎﺗﻲ ﻛﻪ ‫ﻣﻲﺧﻮاﻫﻨﺪ آﻧﺮا در ﮔﺎم ﺑﻌﺪي ﺧﻮد اﻧﺘﺨﺎب ﻛﻨﻨﺪ آﮔﺎﻫﻲ دارﻧﺪ و ﺑﺮ اﺳﺎس ﻧﻴﺎز اﻃﻼﻋﺎﺗﻲ ﺧﻮد ﺻﻔﺤﻪ ﺑﻌﺪي را اﻧﺘﺨﺎب ﻣﻲﻛﻨﻨﺪ

در اﻟﮕﻮرﻳﺘﻢ ﭘﻴﺸﻨﻬﺎد ﺷﺪه ﺑﺮاي دﺳﺘﻪ ﺑﻨﺪي ﺻﻔﺤﺎت وب ، از ﻳﻚ اﺗﻮﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ ﺗﻮزﻳﻊﺷﺪه ﺑﺎ ‪ nاﺗﻮﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ ﺑﺎ ﺗﻌﺪاد اﻗﺪاﻣﻬﺎي ﻣﺘﻐﻴﺮ ‫31 ﻛﻪ ﻫﺮ ﻳﻚ 1-‪ nاﻗﺪام دارﻧﺪ، اﺳﺘﻔﺎده ﻣﻲﺷﻮد ﺗﺎ در ﻧﻬﺎﻳﺖ ﻣﺎﺗﺮﻳﺲ اﻧﺘﻘﺎل ‪ Pﺑﺮ اﺳﺎس رﻓﺘﺎر ﻫﻤﻪ ﻛﺎرﺑﺮان ﺗﻮﻟﻴﺪ ﺷﻮد. ﺑﺮاي ﻫﺮ اﺗﻮﻣﺎﺗﺎي ‫ﻳﺎدﮔﻴﺮ در ﻫﺮ زﻣﺎن ﺗﻨﻬﺎ زﻳﺮﻣﺠﻤﻮﻋﻪاي از اﻗﺪاﻣﻬﺎﻳﺶ ﻓﻌﺎل و ﻣﻴﺘﻮاﻧﺪ ﻗﺎﺑﻞ اﺳﺘﻔﺎده ﺑﺎﺷﺪ. ﺗﻌﺪاد اﻗﺪاﻣﻬﺎي اﺗﻮﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ ﻣﺘﻨﺎﻇﺮ ﺑﺎ ﻫﺮ ﺻﻔﺤﻪ ‫ﻣﺎﻧﻨﺪ ‪ iﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ﺗﻌﺪاد ﺻﻔﺤﺎﺗﻲ ﻛﻪ ﻣﻤﻜﻦ اﺳﺖ ﻛﺎرﺑﺮ ﺑﻌﺪ از آن ﺻﻔﺤﻪ ﻣﺸﺎﻫﺪه ﻛﻨﺪ. ﻫﻨﮕﺎﻣﻴﻜﻪ ﻳﻚ ﻛﺎرﺑﺮﭘﺲ از ﻣﺸﺎﻫﺪه ﺻﻔﺤﻪ ‪ ،iﺻﻔﺤﻪ ‪j ‫را ﻣﺸﺎﻫﺪه ﻣﻲﻛﻨﺪ اﻗﺪام ‪jام در اﺗﻮﻣﺎﺗﺎي ‪iام ﭘﺎداش ﻣﻲﮔﻴﺮد. در اﻳﻦ روش ﺑﻌﺪ از اﺗﻤﺎم ﻳﺎدﮔﻴﺮي از اﻃﻼﻋﺎت ﭘﻴﻤﺎﻳﺶ ﺗﻤﺎم ﻛﺎرﺑﺮان، اﺣﺘﻤﺎل ‫اﻗﺪام ‪jام در اﺗﻮﻣﺎﺗﺎي ‪iام در دراﻳﻪ ‪ pijﻗﺮار ﻣﻲﮔﻴﺮد ﻛﻪ ﺑﻴﺎﻧﮕﺮ اﺣﺘﻤﺎل ﻣﺸﺎﻫﺪه دو ﺻﻔﺤﻪ ‪iام و ‪jام ﺑﻪ ﻃﻮر ﻣﺘﻮاﻟﻲ اﺳﺖ.

‫ﻣﺎﺗﺮﻳﺲﻧﺎﻣﺘﻘﺎرن ﺗﻮﻟﻴﺪ ﺷﺪه ﻣﺒﺘﻨﻲ ﺑﺮ آﺗﻮﻣﺎﺗﺎي ﻳﺎدﮔﻴﺮ ‪ p ij ≠ p ji ) P)را ﻣﺎﺗﺮﻳﺲ اﻧﺘﻘﺎل ﺻﻔﺤﺎت ﻣﻲ ﻧﺎﻣﻴﻢ. از ﺣﺎﺻﻠﻀﺮب ﻣﺎﺗﺮﻳﺲ ‫ﻧﺎﻣﺘﻘﺎرن ‪ Pﺑﺎﻣﺎﺗﺮﻳﺲ وارون10 آن ‪ P Tﻣﺎﺗﺮﻳﺲﻣﺘﻘﺎرن ﺟﺪﻳﺪي ﺑﻪ ﻧﺎم ﻣﺎﺗﺮﻳﺲ ﺷﺒﺎﻫﺖ ‪ Sﺣﺎﺻﻞﻣﻲ ﺷﻮد. دراﻳﻪ ‪ sijدر اﻳﻦﻣﺎﺗﺮﻳﺲ، ‫درﺟﻪ ﺷﺒﺎﻫﺖ دو ﺻﻔﺤﻪ ‪iام و ‪jام را ﻧﺸﺎن ﻣﻲ دﻫﺪ.

 

در ﻣﺮﺣﻠﻪ ﺑﻌﺪي ﻳﻚ ﮔﺮاف ﺑﻪ روش زﻳﺮ از روي ﻣﺎﺗﺮﻳﺲ ﺷﺒﺎﻫﺖ ‪ Sاﻳﺠﺎد ﻣﻲ ﺷﻮد. ﺻﻔﺤﺎت را ﺑﻪ ﻋﻨﻮان ﻣﺠﻤﻮﻋﻪ راس ﻫﺎس ﮔﺮاف و دراﻳﻪ ‫ﻫﺎي ﻏﻴﺮ ﺻﻔﺮ ﻣﺎﺗﺮﻳﺲ ﻳﺎل ﻫﺎي اﻳﻦ ﮔﺮاف را ﺗﺸﻜﻴﻞ ﻣﻲ دﻫﻨﺪ. ﺳﭙﺲ ﺑﺎ اﺳﺘﻔﺎده از اﺑﺰارﻫﺎي ﻣﻮﺟﻮد اﻓﺮاز ﮔﺮاف، ﻣﺎﻧﻨﺪ ‪ ،hMeTisﮔﺮاف ﺗﻮﻟﻴﺪ ‫ﺷﺪه را اﻓﺮاز ﻣﻲﻛﻨﻴﻢ. ﻣﻌﻴﺎر اﻓﺮاز، ﻛﻤﻴﻨﻪ ﺳﺎزي ﺑﺮش ﺑﻴﻦ اﻓﺮازﻫﺎ ﻣﻲﺑﺎﺷﺪ. اﻳﻦ ﻣﻌﻴﺎر ﺑﺎﻋﺚ ﻣﻲ ﺷﻮد ﻛﻪ ﺷﺒﺎﻫﺖ ﺑﻴﻦﺑﺨﺶﻫﺎي اﻳﺠﺎد ﺷﺪه از اﻓﺮاز ‫ﻛﻤﻴﻨﻪﺷﻮد و ﻫﻤﭽﻨﻴﻦ ﺻﻔﺤﺎﺗﻲ ﻛﻪ در ﻳﻚ ﺑﺨﺶ از اﻓﺮاز ﻗﺮار ﻣﻲﮔﻴﺮﻧﺪ، ﺻﻔﺤﺎﺗﻲ ﺑﺎﺷﻨﺪ ﻛﻪ ﺑﻴﻦ ﻛﺎرﺑﺮان زﻳﺎدي ﻣﺸﺘﺮك ﺑﻮدهاﻧﺪ و ﻣﺠﻤﻮﻋﻪ ‫ﺻﻔﺤﺎت ﻣﻮﺟﻮد در آن ﺑﺨﺶ ﻳﻚ دﺳﺘﻪ ﺑﻨﺪي از ﺻﻔﺤﺎت را ﺗﺸﻜﻴﻞ ﻣﻲدﻫﻨﺪ.

2-4 ﺗﻮﺳﻌﻪ ﺻﻔﺤﺎت اﻧﺘﺨﺎب ﺷﺪه ﺑﻮﺳﻴﻠﻪ اﻟﮕﻮرﻳﺘﻢ ‪HITS

‫ﺑﺮاي ﺑﻬﺒﻮد دﻗﺖ ﭘﺎﻳﻴﻦ اﻟﮕﻮرﻳﺘﻢ ﺑﺎ اﻓﺰاﻳﺶ ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي و ﻣﺸﻜﻞ ﺻﻔﺤﺎت ﺟﺪﻳﺪي ﻛﻪ ﻣﻤﻜﻦ اﺳﺖ در ﻓﺎﻳﻞ ﺛﺒﺖ وﻗﺎﻳﻊ ﻇﺎﻫﺮ ‫ﻧﺸﻮﻧﺪ، از ﺳﺎﺧﺘﺎر ﭘﻴﻮﻧﺪ ﺳﺎﻳﺖ ﺑﻪ ﺻﻮرت زﻳﺮ اﺳﺘﻔﺎده ﻣﻲﻛﻨﻴﻢ. ﺻﻔﺤﺎت ﻣﺸﺎﺑﻪ ﺑﺎ ﻧﺸﺴﺖ ﻛﺎرﺑﺮ 1 + ‪ Nﺻﻔﺤﻪ، ﻛﻪ در ﺑﺨﺶ ﻗﺒﻞ اﻧﺘﺨﺎب ﺷﺪﻧﺪ را ‫ﺑﻪﻋﻨﻮان رﻳﺸﻪ ﮔﺮاف ﻫﻤﺴﺎﻳﮕﻲ در اﻟﮕﻮرﻳﺘﻢ ‪ HITSاﻧﺘﺨﺎب ﻣﻲﻛﻨﻴﻢ. در اداﻣﻪ اﻳﻦ رﻳﺸﻪ ﺑﻪ وﺳﻴﻠﻪ ﻫﻤﺴﺎﻳﮕﺎﻧﺶ ﺗﻜﻤﻴﻞ ﻣﻲ ﮔﺮدد. ﻫﻤﺴﺎﻳﻪ ‫ﻫﺎ، ﻣﺠﻤﻮﻋﻪاي از ﺻﻔﺤﺎﺗﻲ ﻫﺴﺘﻨﺪ ﻛﻪ ﻳﺎ از رﻳﺸﻪ ﺑﻪ آﻧﻬﺎ ﭘﻴﻮﻧﺪ داده ﺷﺪه اﺳﺖ و ﻳﺎ ﺑﻪ رﻳﺸﻪ ﭘﻴﻮﻧﺪ دادهاﻧﺪ. ﺳﭙﺲ ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﻳﺘﻢ ‪HITS ‫ﺑﺮاي ﻫﺮ ﮔﺮه در ﮔﺮاف ﻫﻤﺴﺎﻳﮕﻲ، ﺑﻪ ﻃﻮر ﺗﻨﺎوﺑﻲ دو اﻣﺘﻴﺎز درﺟﻪ اﻋﺘﺒﺎر و ﻣﺮﻛﺰﻳﺖ را ﻣﺤﺎﺳﺒﻪ ﻣﻲ ﻛﻨﺪ. ﺻﻔﺤﺎت ﺟﺪﻳﺪ و ﺻﻔﺤﺎت ﺑﺎ ﻓﺮﻛﺎﻧﺲ ﻛﻢ ، ‫ﺑﻪﻋﻠﺖ اﻳﻨﻜﻪ ﺑﻪ آﻧﻬﺎ ﭘﻴﻮﻧﺪﻫﺎي زﻳﺎدي وﺟﻮد ﻧﺪاﺷﺘﻪ اﺳﺖ ، در ﻓﺎﻳﻞ ﺛﺒﺖ وﻗﺎﻳﻊ ﻛﺎرﺑﺮان ﻛﻤﺘﺮﻣﺸﺎﻫﺪه ﺷﺪه اﻧﺪ. ﺑﻨﺎﺑﺮاﻳﻦ درﺟﻪ اﻋﺘﺒﺎر ﺑﺎﻻﻳﻲ ‫ﻫﻢﻧﺨﻮاﻫﻨﺪ داﺷﺖ،ﭘﺲ ﮔﺮه ﻫﺎ را ﺗﻨﻬﺎ ﺑﺮ اﺳﺎس اﻣﺘﻴﺎز ﻣﺮﻛﺰﻳﺖ آﻧﻬﺎ ﻣﺮﺗﺐ ﻣﻲﻛﻨﻴﻢ و ﻓﻘﻂ ﺻﻔﺤﺎﺗﻲﺑﺎ ﺑﻴﺸﺘﺮﻳﻦ اﻣﺘﻴﺎز ﻣﺮﻛﺰﻳﺖ ﺑﻪ ﻛﺎرﺑﺮ ﭘﻴﺸﻨﻬﺎد ‫ﻣﻲﺷﻮﻧﺪ. ﺑﺮاي ﻛﻨﺘﺮل ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي از ﻓﺎﻛﺘﻮر ﺣﺪآﺳﺘﺎﻧﻪ ﭘﻴﺸﻨﻬﺎد اﺳﺘﻔﺎده ﻣﻲﺷﻮد ﻛﻪ ﺑﺎ ‪ rtﻧﺸﺎن ﻣﻲدﻫﻴﻢ. ﺻﻔﺤﺎﺗﻲ ﻛﻪ اﻣﺘﻴﺎز آﻧﻬﺎ ‫از ‪ rtﺑﻴﺸﺘﺮﺑﺎﺷﺪ ﺑﻪ ﻛﺎرﺑﺮ ﭘﻴﺸﻨﻬﺎد ﻣﻲﺷﻮد. ﺑﺪﻳﻬﻲ اﺳﺖ ﻛﻪ ﺑﺎ اﻓﺰاﻳﺶ ‪ rtﺗﻌﺪاد ﺻﻔﺤﺎت ﻣﺠﻤﻮﻋﻪ ‪ rsﻛﺎﻫﺶﻣﻲﻳﺎﺑﺪ. ‪ rtرا ﻣﻲﺗﻮان ﻋﻼوه ﺑﺮ ‫ﺗﻨﻈﻴﻢ ﺑﺮ اﺳﺎس اﻣﺘﻴﺎز، ﺑﺮ اﺳﺎس ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي ﻧﻴﺰ ﻣﻘﺪار دﻫﻲ ﻧﻤﻮد.

‫3- ارزﻳﺎﺑﻲ اﻟﮕﻮرﻳﺘﻢ ﭘﻴﺸﻨﻬﺎدي

‫3-1 ﻣﺪل ﺷﺒﻴﻪ ﺳﺎزي

دو روش ﻋﻤﺪه ﺑﺮاي ارزﻳﺎﺑﻲ اﻟﮕﻮرﻳﺘﻢﻫﺎﻳﻲ ﻛﻪ از اﻃﻼﻋﺎت ﭘﻴﻤﺎﻳﺶﻛﺎرﺑﺮان اﺳﺘﻔﺎده ﻣﻲﻛﻨﻨﺪ وﺟﻮد دارد. روش اول، اﺳﺘﻔﺎده از ﺻﻔﺤﺎت وب ‫واﻗﻌﻲ و دادهﻫﺎي واﻗﻌﻲ ﻛﺎرﺑﺮان وب ﻣﻮﺟﻮد در ﻓﺎﻳﻞﻫﺎي ﺛﺒﺖ رﺧﺪاد ﺳﺎﻳﺖﻫﺎ ﻣﻲﺑﺎﺷﺪ. ﺑﺮاي اﺳﺘﻔﺎده از اﻳﻦ روش ﻣﺠﻤﻮﻋﻪ دادهﻫﺎي اﺳﺘﺎﻧﺪاردي ‫ﻛﻪ از ﭼﻨﺪ ﺳﺎﻳﺖ ﻣﻌﺘﺒﺮ اﺳﺘﺨﺮاج ﺷﺪهاﻧﺪ در دﺳﺘﺮس ﻣﻲﺑﺎﺷﺪ. در اﻳﻦ روش ‪ Luiو ﻫﻤﻜﺎراﻧﺶ ﻧﻈﻢ ‫ﻣﻮﺟﻮد در رﻓﺘﺎرﻫﺎي ﻛﺎرﺑﺮان در ﻣﺤﻴﻂ وب را ﺑﺎ اﺳﺘﻔﺎده از ﻳﻚ ﻣﺪل ﻣﺒﺘﻨﻲ ﺑﺮ ﻋﺎﻣﻞ، ﻣﺸﺨﺺ و اﻋﺘﺒﺎر ﻣﺪل ﺧﻮد را ﺑﺎ اﺳﺘﻔﺎده از اﻃﻼﻋﺎت اﺳﺘﻔﺎده ‫از وب ﭼﻨﺪﻳﻦ ﺳﺎﻳﺖ وب ﺑﺰرگ ﻣﺎﻧﻨﺪ ﻣﺎﻳﻜﺮوﺳﺎﻓﺖ، ﺗﺎﻳﻴﺪ ﻛﺮدهاﻧﺪ. در اﻳﻦ ﻣﻘﺎﻟﻪ ﻣﺎ از دادهﻫﺎي اﺳﺘﺎﻧﺪارد ﺳﺎﻳﺖ ‪ CTI DePaulاﺳﺘﻔﺎده ﻣﻲﻛﻨﻴﻢ. ‫اﻳﻦ ﻣﺠﻤﻮﻋﻪ داده اﻃﻼﻋﺎت ﻧﺸﺴﺖ ﻛﺎرﺑﺮان را ﺑﻪ ﻣﺪت 2 ﻫﻔﺘﻪ در ﺳﺎﻳﺖ ‪ CTI DePaulدر ﺳﺎل 2002 ﺷﺎﻣﻞ ﻣﻲﺷﻮد. اﻳﻦ اﻃﻼﻋﺎت ‫ﭘﻴﺶﭘﺮدازش ﺷﺪه و ﻧﺸﺴﺖﻫﺎي ﺑﺎ اﻧﺪازه 1 و ﻏﻴﺮ اﺳﺘﺎﻧﺪارد از آن ﺣﺬف ﺷﺪهاﻧﺪ و در ﻧﻬﺎﻳﺖ اﻃﻼﻋﺎت 54731 ﻛﺎرﺑﺮ ﻛﻪ از 386 ﺻﻔﺤﻪ دﻳﺪن ‫ﻛﺮدهاﻧﺪ در ﻓﺎﻳﻞﻫﺎي ﺟﺪاﮔﺎﻧﻪ ﻗﺮار داده ﺷﺪه اﺳﺖ.

‫3-2 ﻣﻌﻴﺎر و ﻣﺘﺪﻟﻮژي ارزﻳﺎﺑﻲ

‫ﭘﺎراﻣﺘﺮﻫﺎي ﺗﺎﺛﻴﺮﮔﺬار در ﻛﺎراﻳﻲ اﻟﮕﻮرﻳﺘﻢ ﻋﺒﺎرﺗﻨﺪ از: ‪ rwاﻧﺪازه ﭘﻨﺠﺮه ﭘﻴﺸﻨﻬﺎد، ‪ rtﺣﺪ آﺳﺘﺎﻧﻪ ﭘﻴﺸﻨﻬﺎد. ﺑﺮاي ﺑﺮرﺳﻲ دﻗﺖ اﻟﮕﻮرﻳﺘﻢ اراﺋﻪ ‫ﺷﺪه روﻳﻪ زﻳﺮ اﺗﺨﺎذ ﺷﺪه اﺳﺖ. اﺑﺘﺪا ﺑﺎ اﺳﺘﻔﺎده از ﻣﺠﻤﻮﻋﻪ ﻳﺎدﮔﻴﺮي اﻟﮕﻮرﻳﺘﻢ را اﺟﺮا ﻣﻲﻛﻨﻴﻢ. ﺑﺮ اﺳﺎس ﻣﻘﺪار ‪ ، rwاز ﻫﺮ ﻧﺸﺴﺖ در ﻣﺠﻤﻮﻋﻪ ‫ﺗﺴﺖﻛﻪ اﻧﺪازه آن ﺣﺪاﻗﻞ ‪ rw + rtﻣﻲﺑﺎﺷﺪ، ‪ rwﺻﻔﺤﻪﻣﺘﻮاﻟﻲ را اﻧﺘﺨﺎب ﻛﺮده و ﺑﻪ اﻟﮕﻮرﻳﺘﻢ ﻣﻲدﻫﻴﻢ. ﻣﻌﻴﺎر ارزﻳﺎﺑﻲ رواﺑﻂ ﻣﻌﺮﻓﻲ ﺷﺪه در ‫ اﺳﺖ. ﻓﺮض ﻛﻨﻴﻢ ﻣﺠﻤﻮﻋﻪ { ‪ rp = {x rw+1 , x rw+ 2 ,..., x rw+ rsﺻﻔﺤﺎت ﻣﺸﺎﻫﺪه ﺷﺪه ﺗﻮﺳﻂﻛﺎرﺑﺮ در اداﻣﻪ ﻧﺸﺴﺖ واﻗﻌﻲ ﺑﺎﺷﺪ. درﺟﻪ ‫ﺷﺒﺎﻫﺖﻣﺠﻤﻮﻋﻪ ﭘﻴﺸﻨﻬﺎدي و ﻣﺠﻤﻮﻋﻪ ﺻﻔﺤﺎت واﻗﻌﻲ و درﺻﺪ ﭘﻮﺷﺶ آﻧﻬﺎ از رواﺑﻂ زﻳﺮ ﺑﻪ دﺳﺖ ﻣﻲآﻳﻨﺪ:

 

ﻣﻌﻴﺎر ‪ Pr ecisionﻫﻤﭙﻮﺷﺎﻧﻲ دو ﻣﺠﻤﻮﻋﻪ ﻳﻌﻨﻲ ﻧﺴﺒﺖ ﭘﻴﺸﻨﻬﺎدات ﻣﻨﺎﺳﺐ را ﺑﻪ ﺗﻌﺪاد ﻛﻞ ﭘﻴﺸﻨﻬﺎدات ﻧﺸﺎن ﻣﻲ دﻫﺪ. ﻫﺪف اﻳﻦ اﺳﺖ ‫ﻛﻪﭼﻨﺪ ﺗﺎ از ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي در ﻣﺠﻤﻮﻋﻪ ﺗﺴﺖ ﺑﺮاي آن ﻛﺎرﺑﺮ وﺟﻮد دارد. در اﻳﻦ راﺑﻄﻪ ﺗﺮﺗﻴﺒﻲﺑﺮاي ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﻧﺸﺪه ‫اﺳﺖ. در ﺻﻮرﺗﻲ ﻛﻪ ﺗﻌﺪاد ﺻﻔﺤﺎت ﭘﻴﺸﻨﻬﺎدي را ﺑﻪ ﻳﻚ ﺻﻔﺤﻪ ﻣﺤﺪود ﻛﻨﻴﻢ، ﻛﺎﻓﻲ اﺳﺖ ﺗﺎ ﺻﻔﺤﻪ ﭘﻴﺸﻨﻬﺎدي اﻟﮕﻮرﻳﺘﻢ را ﺑﺎ ﺻﻔﺤﻪ 1 + ‪ rwام ‫در ﻧﺸﺴﺖ ﻛﺎرﺑﺮ ﻣﻘﺎﻳﺴﻪ ﻣﻲﻛﻨﻴﻢ. در اﻳﻦ ﺻﻮرت دﻗﺖ اﻟﮕﻮرﻳﺘﻢ درﺻﺪ ﻧﺸﺴﺖﻫﺎﻳﻲ ﻣﻲﺑﺎﺷﺪ ﻛﻪ در آﻧﻬﺎ ﺻﻔﺤﻪ ﭘﻴﺸﻨﻬﺎدي اﻟﮕﻮرﻳﺘﻢﺑﺎ ﺻﻔﺤﻪ ‫واﻗﻌﻲﻳﻜﺴﺎن ﻣﻲﺑﺎﺷﺪ. ﻣﻌﻴﺎر ‪ Coverageﺗﻮاﻧﺎﻳﻲﺳﻴﺴﺘﻢ را ﺑﺮاي ﭘﻴﺸﻨﻬﺎد ﻫﻤﻪ ﺻﻔﺤﺎﺗﻲ ﻛﻪ ﺑﺎﻳﺪﺗﻮﺳﻂ ﻛﺎرﺑﺮ ﻣﻼﻗﺎت ﺷﻮﻧﺪ ﻳﺎ درﺻﺪي از ﻛﻞ ‫ﺻﻔﺤﺎﺗﻲ ﻛﻪ ﺳﻴﺴﺘﻢ ﻗﺎدر اﺳﺖ ﭘﻴﺸﻨﻬﺎد ﺑﺪﻫﺪ را ﻧﺸﺎن ﻣﻲ دﻫﺪ . ﻣﻌﻴﺎر ﭘﻮﺷﺶ ﻧﺴﺒﺖ ﭘﻴﺸﻨﻬﺎدات ﻣﻨﺎﺳﺐ را ﺑﻪ ﻛﻞ ﺗﻌﺪاد ﺻﻔﺤﺎت ﻣﺸﺎﻫﺪه ﺷﺪه ‫ﺗﻮﺳﻂﻛﺎرﺑﺮ ﻛﻪ ﺑﺎﻳﺪ ﭘﻴﺸﻨﻬﺎد ﺷﻮد ﻧﺸﺎن ﻣﻲ دﻫﺪ.

‫ﺍﻟﮕﻮﺭﻳﺘﻢ ﺗﺮﻛﻴﺒﻲ ﻭﻓﻘﻲ ﺟﻬﺖ ﺭﺗﺒﻪﺑﻨﺪﻱﺻﻔﺤﺎﺕ ﻭﺏ ‫ِ

ﺍﻣﻴﺮﺣﺴﻴﻦ ﻛﻴﻬﺎﻧﻲﭘﻮﺭ(‫ﭘﮋﻭﻫﺸﻜﺪﻩﻓﻨﺂﻭﺭﻱ ﺍﻃﻼﻋﺎﺕ، ‫ﻣﺮﻛﺰ ﺗﺤﻘﻴﻘﺎﺕ ﻣﺨﺎﺑﺮﺍﺕ ﺍﻳﺮﺍﻥ)

‫ﻧﺎﺻﺮ ﻳﺰﺩﺍﻧﻲ(‫ﺩﺍﻧﺸﻜﺪﻩﻣﻬﻨﺪﺳﻲﺑﺮﻕ ﻭ ﻛﺎﻣﭙﻴﻮﺗﺮ، ‫ﺩﺍﻧﺸﮕﺎﻩﺗﻬﺮﺍﻥ)

‫ﻣﺤﻤﺪ ﺁﺯﺍﺩﻧﻴﺎ(‫ﭘﮋﻭﻫﺸﻜﺪﻩﻓﻨﺂﻭﺭﻱ ﺍﻃﻼﻋﺎﺕ، ‫ﻣﺮﻛﺰﺗﺤﻘﻴﻘﺎﺕ ﻣﺨﺎﺑﺮﺍﺕ ﺍﻳﺮﺍﻥ)

‫ﻋﻠﻲﻣﺤﻤﺪ ﺯﺍﺭﻉ ﺑﻴﺪﻛﻲ(‫ﭘﮋﻭﻫﺸﻜﺪﻩﻓﻨﺂﻭﺭﻱ ﺍﻃﻼﻋﺎﺕ، ‫ﻣﺮﻛﺰﺗﺤﻘﻴﻘﺎﺕ ﻣﺨﺎﺑﺮﺍﺕ ﺍﻳﺮﺍﻥ)

ﺩﺭ ﺣﺎﻝ ﺣﺎﺿﺮ ﻣﻬﻤﺘﺮﻳﻦ ﺑﺨﺶ ﻣﻮﺗﻮﺭﻫﺎﻱ ﺟـﺴﺘﺠﻮﻱ ﻓﻌﻠـﻲ ﺭﺍ ﻛــﺎﺭﺁﻳﻲ ﭘــﺎﻳﻴﻦ ﻣــﻲﺑﺎﺷــﻨﺪ ﻭ ‫ﻧﻴﺎﺯﻣﻨﺪﻳﻬﺎﻱﻛﺎﺭﺑﺮ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﻣﻨﺎﺳﺐ ﺑﺮﺁﻭﺭﺩﻩ ﻧﻤﻲﻛﻨﻨﺪ ‫ﻳﻚ ﺍﻟﮕﻮﺭﻳﺘﻢﺭﺗﺒﻪ ﺑﻨﺪﻱ ﻭﻓﻘﻲِ ﺗﺮﻛﻴﺒﻲ ﺑﺮﺍﻱ ﺩﺳﺘﻴﺎﺑﻲ ﺑﻪ ﺩﻗﺖ ﻭ ﻛـﺎﺭﺍﻳﻲ ‫ﺑﺎﻻﺗﺮﺍﺭﺍﺋﻪ ﺷﺪﻩ ﺍﺳﺖ. ﺍﻳﻦ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﺗﺮﻛﻴـﺐ ﺍﻟﮕـﻮﺭﻳﺘﻢﻫـﺎﻱ ‫ﻣﻮﺟﻮﺩ ﺑﻪ ﻛﻤﻚ ﻓﺮﺁﻳﻨﺪ ﻳﺎﺩﮔﻴﺮﻱﺳﻌﻲ ﺧﻮﺍﻫﺪ ﻛﺮﺩ ﺑـﻪ ﺍﻟﮕـﻮﺭﻳﺘﻢ ﺑﻬﺘـﺮﻱ ‫ﺩﺳﺖﭘﻴﺪﺍ ﻛﻨﺪ. ﻓﺮﺁﻳﻨﺪ ﻳﺎﺩﮔﻴﺮﻱ ﺟﻬﺖ ﺗﺮﻛﻴﺐ ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ﻣﺨﺘﻠـﻒ ﺑـﺎ ‫ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ‪ OWAﺑﺎﺗﻮﺟﻪ ﺑﻪ ﻧﻈـﺮ ﺍﻓـﺮﺍﺩ ﺧﺒـﺮﻩ ﺩﺭ ﻣـﻮﺭﺩ ﺩﺭﺟـﻪ ﺍﺭﺗﺒـﺎﻁ ‫ﭘﺮﺳﺶﻭ ﺳﻨﺪ ﺍﻧﺠﺎﻡ ﻣﻲﺷﻮﺩ. ﺑﺮﺍﻱ ﺍﺭﺯﻳﺎﺑﻲ ﻭ ﻣﻘﺎﻳﺴﻪ ﺑـﺎ ﺳـﺎﻳﺮ ﺭﻭﺷـﻬﺎ ﺍﺯ ‫ﻣﺠﻤﻮﻋـﻪ ﺩﺍﺩﻩﻫـﺎﻱ ﻣﺤـﻚ 4002 ‪ TRECﺍﺳـﺘﻔﺎﺩﻩﺷـﺪﻩ ﺍﺳـﺖ.

‫٢- ﻋﻤﮕﺮ ﺗﺠﻤﻴﻊ ‪OWA

ﺑﺼﻮﺭﺕ ﺭﺳﻤﻲ، ﺗﺠﻤﻴﻊ ٩ ﻋﺒﺎﺭﺗﺴﺖ ﺍﺯ ﺗﺠﻤﻴﻊ ﻳﮏ ‪- nﺗﺎﻳﻲﺍﺯ ﺍﺷﻴﺎﺀ ﻋـﻀﻮ ‫ﻣﺠﻤﻮﻋﻪﺍﻱ ﺧﺎﺹ ﺑﻪ ﻳﮏ ﺷـﻲ ﺍﺯ ﻫﻤـﺎﻥ ﻣﺠﻤﻮﻋـﻪ. ﺩﺭ ﺧـﺼﻮﺹ ﻋﻤﻠﮕـﺮ ‫ﺭﻳﺎﺿﻲﺗﺠﻤﻴﻊ، ﺍﻳﻦ ﻣﺠﻤﻮﻋﻪ، ﻫﻤﺎﻥ ﻣﺠﻤﻮﻋﻪ ﺍﻋﺪﺍﺩ ﺣﻘﻴﻘﻲ ﺍﺳﺖ. ﺩﺭ ﺍﻳﻦ ‫ﺣﺎﻟﺖ، ﺍﻳـﻦ ﻋﻤﻠﮕـﺮ، ﺗـﺎﺑﻌﻲ ﺍﺳـﺖ ﮐـﻪ ﻳـﮏ ‪ nﺗـﺎﻳﻲﺍﺯ ﺍﻋـﺪﺍﺩ ﺣﻘﻴﻘـﻲ ‫ﻣﺜ ـﻞ ‪ ( x1 , x2 ,..., xn)ﺭﺍ ﺑ ـﻪ ﻳ ـﮏ ﻋ ـﺪﺩ ﺣﻘﻴﻘ ـﻲ ﭼ ـﻮﻥ ‪ ، yﻧــﺴﺒﺖ ‫‫ﻣﻲﺩﻫﺪ:

( ‪y = Aggreg (x 1 , x2 ,..., x n

 

. ‫ﺑ ـﺮﺍﯼ ﺑﺪﺳ ـﺖ ﺁﻭﺭﺩﻥ ﻭﺯﻧﻬ ـﺎ ﺩﺭ ﻋﻤﻠﮕ ـﺮ ﻣﻴ ـﺎﻧﮕﻴﻦﮔﻴ ـﺮﻱ ﻣﺮﺗـﺐ ﻭﺯﻥﺩﺍﺭ، ‫ﺭﺍﻩﺣﻞﻫﺎﻱﻣﺘﻌﺪﺩﯼ ﺍﺯ ﺟﻤﻠﻪ ﺗﻮﺳﻂ ‪ O’Hagan ﻣﻄﺮﺡ ﺷـﺪﻩ ﺍﺳـﺖ ﮐـﻪ ‫ﻧﻴﺎﺯﻣﻨﺪﺣﻞ ﻳﮏ ﻣﺴﺎﻟﻪ ﺑﺮﻧﺎﻣﻪﺭﻳﺰﻱ ﻏﻴﺮ ﺧﻄﻲ ﻣﻘﻴﺪ ﺍﺳﺖ . ﺩﺭ ﮐـﻼﺱ ﻋﻤﻠﮕﺮﻫﺎﻱ ﻣﻴﺎﻧﮕﻴﻦﮔﻴﺮﻱ ﻣﺮﺗﺐ ﻭﺯﻥ ﺩﺍ ﺭِ ﻧﻤﺎﻳﻲ، ﺭﺍﺑﻄﻪ ﺑﺴﻴﺎﺭ ﺳﺎﺩﻩﺍﻱ ﺑﻴﻦ ‫ﺩﺭﺟﻪ ‪ ornessﻭﭘﺎﺭﺍﻣﺘﺮ ﺗﻌﻴﻴﻦﮐﻨﻨـﺪﻩ ﻭﺯﻥﻫـﺎﻱ ﻣﻴـﺎﻧﮕﻴﻦﮔﻴـﺮﻱ ﻣﺮﺗـﺐ ‫ﻭﺯﻥﺩﺍﺭﻭﺟﻮﺩ ﺩﺍﺭﺩ. ﺩﺭﺟﻪ ‪ ornessﻧﻤﺎﻳﺎﻧﮕﺮﺍﻳﻦ ﺍﺳﺖ ﻛﻪ ﻋﻤﻠﮕﺮ ﺗﺠﻤﻴـﻊ ‫ﺗﺎﭼﻪ ﺣﺪ ﺑﻪ ﻣﻘﺪﺍﺭ ﺑﻴﺸﺒﻴﻨﻪ ﻳﺎ ﻛﻤﻴﻨﻪ ﻧﺰﺩﻳﻚ ﻣﻲﺷﻮﺩ. ﺑﻪ ﻋﺒـﺎﺭﺕ ﺩﻳﮕـﺮ، ‫‪ ornessﻧﺰﺩﻳﻚﺑﻪ ﻳﻚ ﻧﺸﺎﻧﻪ ﻧﺰﺩﻳﻜﻲ ﺗﺎﺑﻊ ﺑﻪ ﻋﻤﮕﮕـﺮ ‪ MAXﻭﺑـﺎﻟﻌﻜﺲ ‫‪ ornessﻧﺰﺩﻳﻚﺑﻪ ﺻﻔﺮ، ﻧﻤﺎﻳﺎﻧﮕﺮ ﻧﺰﺩﻳﻜﻲ ﺗﺎﺑﻊ ﺗﺠﻤﻴـﻊ ﺑـﻪ ﻋﻤﮕـﺮ ‪MIN ‫ﺍﺳﺖ. ﻳﻜﻲ ﺍﺯ ﺭﻭﺷﻬﺎﻱ ﻣﺤﺎﺳﺒﺴﻪ ﻭﺯﻧﻬـﺎ ﺭﻭﺵ ﺧﻮﺷـﺒﻴﻨﺎﻧﻪ ﻣـﻲﺑﺎﺷـﺪ.ﺩﺭ ‫ﺭﻭﺵﺧﻮﺵﺑﻴﻨﺎﻧﻪ، ﻭﺯﻥﻫﺎﻱ ﻣﻴﺎﻧﮕﻴﻦﮔﻴﺮﻱ ﻣﺮﺗﺐ ﻭﺯﻥﺩﺍﺭ ﺑﺮ ﺍﺳﺎﺱ ﻓﺮﻣﻮﻝ ‫ﺯﻳﺮ، ﺗﻬﻴﻪ ﻣﻲﺷﻮﻧﺪ:

 

ﮐـــﻪ ﺩﺭ ﺁﻥ ﭘـــﺎﺭﺍﻣﺘﺮ 1,0 ‪ a εﺍﺳـــﺖ. ﺑـــﻪﺍﺯﺍﻱ 1 = ‪ aﺑـــﻪﺑـــﺮﺩﺍﺭ ‫ﻭﺯﻥ ‪ W = [1 0 ... 0 ]Tﻣــﻲﺭﺳــﻴﻢ ﮐــﻪ ﺩﺍﺭﺍﻱ

1 = ‪ ornessﺍﺳــﺖ. ‫ﺑﻪﻫﻤﻴﻦ ﺗﺮﺗﻴﺐ ﺑـﻪ ﺍﺯﺍﻱ 0 = ‪ aﺑـﻪﺑـﺮﺩﺍﺭ ﻭﺯﻥ 1 ... 0 0 = ‪W ‫ــ ‫ـ ‫ﻣ ـﻲﺭﺳ ـﻴﻢ ﮐ ـﻪ ﺩﺍﺭﺍﻱ

0 = ‪ ornessﺍﺳ ـﺖ. ﻣﻴ ـﺰﺍﻥ ‪ ornessﺍﻳ ـﻦ ﻋﻤﻠﮕ ـﺮ ﻣﻴﺎﻧﮕﻴﻦﮔﻴﺮﻱ ﻣﺮﺗـﺐ ﻭﺯﻥ ﺩﺍﺭ ﺑـﻪﺍﺯﺍﻱ ﻣﻘـﺎﺩﻳﺮ ﻣﺨﺘﻠـﻒ ‪ aﺑـﺼﻮﺭﺕﺯﻳـﺮ ‫ﻣﻲﺑﺎﺷﺪ

 

‫٣- ﺍﻟﮕﻮﺭﻳﺘﻢ ‪ComRank

‫ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﻣﻄﺎﻟﺐ ﺫﻛﺮ ﺷﺪﻩ ﺩﺭﻣﻘﺪﻣﻪ، ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ﻓﻌﻠـﻲ ﺩﺍﺭﺍﻱ ﺩﻗـﺖ ‫ﭘﺎﻳﻴﻨﻲﻣﻲﺑﺎﺷﻨﺪ ﻭ ﺑﺴﺘﻪ ﺑﻪ ﻣﺤﺘﻮﺍ ﺩﺭ ﺷﺮﺍﻳﻂ ﺧﺎﺹ ﺩﺍﺭﺍﻱ ﺟﻮﺍﺏ ﻣﻨﺎﺳـﺐ ‫ﻣﻲﺑﺎﺷﻨﺪ. ﺑﺪﻳﻦ ﻣﻨﻈﻮﺭ ﺳﻌﻲ ﺷـﺪﻩ ﺍﺳـﺖ ﺑـﺎ ﺍﺳـﺘﻔﺎﺩﻩ ﺍﺯ ﺗﺮﻛﻴـﺐ ﻧﺘـﺎﻳﺞ ‫ﺣﺎﺻﻞﺍﺯ ﺧﺼﻮﺻﻴﺎﺕ ﻳﻚ ﺻﻔﺤﻪ ﺑﻪ ﻋﻨﻮﺍﻥ ﻭﻳﮋﮔﻲ ١١ ﺑﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﻋﻤﻠﮕـﺮ ‫ﺗﺠﻤﻴﻊ ‪ OWAﺍﻟﮕﻮﺭﻳﺘﻢﺗﺮﻛﻴﺒﻲ ﺟﺪﻳﺪﻱ ﺍﺭﺍﺋﻪ ﺷﻮﺩ. ﺑﺎ ﺗﻮﺟـﻪ ﺑـﻪ ﺍﻳﻨﻜـﻪ ‫ﻫﺪﻑﻛﺸﻒ ﺻﻔﺤﺎﺕ ﺑﺎ ﻛﻴﻔﻴﺖ ﺑﺎﻻ ﻣﻲﺑﺎﺷﺪ، ﺑﺪﻳﻬﻲ ﺍﺳﺖ ﻛﻪ ﺧﺼﻮﺻﻴﺎﺕ ‫ﺫﺍﺗـﻲﺻ ـﻔﺤﻪ ﻧﻘ ـﺶ ﻣﻬﻤ ـﻲ ﺩﺭ ﻛﻴﻔﻴ ـﺖ ﺁﻥ ﺑ ـﺎﺯﻱ ﻣ ـﻲﻛﻨ ـﺪ. ﻟ ـﺬﺍ ﺍﻳ ـﻦ ‫ــــ ‫ـ ‫ـ ‫ـ ‫ـ ‫ــ ‫ﺧﺼﻮﺻﻴﺎﺕﺑﻪ ﻋﻨﻮﺍﻥ ﻭﻳﮋﮔﻴﻬﺎﻱ ﻳﻚ ﺻﻔﺤﻪ ﺩﺭ ﻧﻈـﺮ ﮔﺮﻓﺘـﻪ ﻣـﻲ ﺷـﻮﻧﺪ. ‫ﺧﺼﻮﺻﻴﺎﺕﺻﻔﺤﻪ ﺭﺍ ﻣﻲﺗﻮﺍﻥ ﺩﺭ ﺩﻭ ﺩﺳﺘﻪ ﺭﻳﺰ ﺩﺍﻧﻪ ﻭ ﺩﺭﺷﺖ ﺩﺍﻧﻪ ﺩﺳـﺘﻪ ‫ﺑﻨﺪﻱﻛﺮﺩ. ﺍﺯ ﺧﺼﻮﺻﻴﺎﺕ ﺭﻳﺰﺩﺍﻧﻪ ﺻﻔﺤﻪ ﻣـﻲﺗـﻮﺍﻥ ‪ ، IDF ، TFﺗﻌـﺪﺍﺩ ‫ﭘﻴﻮﻧﺪﻫﺎﻱ ﻭﺭﻭﺩﻱ‪ in-linkﺍﻧﺪﺍﺯﻩﺻﻔﺤﻪ ﻭ ﻏﻴـﺮﻩ ﻧـﺎﻡ ﺑـﺮﺩ. ﻫﻤﭽﻨـﻴﻦ ‫ﺍﻟﮕﻮﺭﻳﺘﻤﻬﺎﻱﺭﺗﺒﻪ ﺑﻨـﺪﻱ ﻣﺨﺘﻠـﻒ ﻣﺒﺘﻨـﻲ ﺑـﺮ ﺍﺗـﺼﺎﻝ ﻭ ﻣﺤﺘـﻮﺍ ﺭﺍ ﻣﺎﻧﻨـﺪ ‫‪ PageRankﻭ 52‪BMﺭﺍ ﻣﻲﺗﻮﺍﻥﺑﻪ ﻋﻨﻮﺍﻥ ﻭﻳﮋﮔﻲ ﺩﺭﺷـﺖ ﺩﺍﻧـﻪ ﻳـﻚ ‫ﺻــﻔﺤﻪﺩﺭ ﻧﻈــﺮ ﮔﺮﻓــﺖ. ﺩﺭ ﺭﻭﺵ ﺍﺭﺍﺋــﻪ ﺷــﺪﻩﻱ ﺩﺭ ﺍﻳــﻦ ﻣﻘﺎﻟــﻪ ﻛــﻪ ‫‪ ComRankﻧﺎﻡﺩﺍﺭﺩ ﺗﺮﻛﻴﺒﻲ ﺍﺯ ﺭﻭﺷﻬﺎﻱ ﺩﺭﺷﺖ ﺩﺍﻧﻪ ﺑﺮﺍﻱ ﺭﺳـﻴﺪﻥ ﺑـﻪ ‫ﺭﺍﻩﺣﻞﻣﻨﺎﺳﺐ ﺗﺮ ﺍﺭﺍﺋﻪ ﺷﺪﻩ ﺍﺳﺖ. ﺷﻜﻞ )۱( ﻧﻤﺎﻱ ﻛﻠﻲ ﺍﻟﮕـﻮﺭﻳﺘﻢ ﺟﻬـﺖ ‫ﺗﺮﻛﻴﺐ ﭼﻨﺪﻳﻦ ﻭﻳﮋﮔﻲ ﺭﺍ ﻧﺸﺎﻥ ﻣﻲﺩﻫﺪ.

 

ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ﺭﺗﺒﻪﺑﻨﺪﻱ ﻣﻮﺟﻮﺩ ﺩﺍﺭﺍﻱ ﻣﺸﻜﻼﺕ ﻣﺨﺘﻠﻒ ﻋـﻼﻭﻩ ﺑـﺮ ﺩﻗـﺖ ‫ﭘﺎﻳﻴﻦ ﻣـﻲ ﺑﺎﺷـﻨﺪ. ﺑـﺮﺍﻱ ﻣﺜـﺎﻝﺍﻟﮕﻮﺭﻳﺘﻤﻬـﺎﻱ ﻣﺒﺘﻨـﻲ ﺑـﺮ ﺍﺗـﺼﺎﻝ ﻣﺎﻧﻨـﺪ ‫‪ PageRankﺍﺯﻣﺸﻜﻞ "ﻏﻨﻲﺗﺮ ﺷﺪﻥ ﺍﻏﻨﻴﺎﺀ" ﺭﻧـﺞ ﻣـﻲﺑﺮﻧـﺪﻭ ﺑـﻪ ‫ﭘﻬﻨﺶﺭﺗﺒﻪ ﺑﻨﺪﻱ ﺣﺴﺎﺳﻴﺖ ﻛﻤﺘﺮﻱ ﺩﺍﺭﻧﺪ.

‫ﻗﺮﺍﺭﮔﺮﻓﺘﻦﻫﻤﻴﺸﮕﻲ ﺻﻔﺤﺎﺕ ﻣﺤﺒﻮﺏ ﺩﺭ ﺻﺪﺭ ﻟﻴـﺴﺖ ﺍﺭﺍﺋـﻪﺷـﺪﻩﺑـﻪ ‫ﻛﺎﺭﺑﺮ، ﺑﺎﻋﺚ ﻣﻲﺷﻮﺩ ﺗﺎ ﻛﺎﺭﺑﺮ ﻓﻘﻂ ﺻﻔﺤﺎﺕ ﺧﺎﺻﻲ ﺭﺍ ﺑﺒﻴﻨـﺪ ﻭ ﺩﺭ ﻧﺘﻴﺠـﻪ ‫ﺻﻔﺤﺎﺕ ﺗﺎﺯﻩ ﻣﺘﻮﻟﺪ ﺷﺪﻩ ﺑﺎ ﻛﻴﻔﻴﺖﺑﺎﻻ ﻛﻪ ﻛﺴﻲ ﺑﻪ ﺁﻧﻬﺎ ﺍﺷﺎﺭﻩ ﻧﻤـﻲﻛﻨـﺪ ‫ﻧﺘﻮﺍﻧﻨﺪﺩﺭ ﺩﻳﺪ ﻛﺎﺭﺑﺮﺍﻥ ﻗﺮﺍﺭ ﮔﻴﺮﻧﺪ. ﺍﻳﻦ ﻣﺸﻜﻞ ﻛﻪ "ﻏﻨﻲﺗﺮ ﺷـﺪﻥ ﺍﻏﻨﻴـﺎﺀ" ‫ﻧﺎﻡ ﺩﺍﺭﺩ ﺑﺎﻋﺚ ﻣﻲﺷﻮﺩ ﺻﻔﺤﺎﺕ ﻣﺤﺒﻮﺏﻣﺮﺗﺒﺎﹰ ﻣﺤﺒﻮﺏﺗـﺮ ﺷـﺪﻩ ﻭ ﺗﻌـﺪﺍﺩ ‫ﭘﻴﻮﻧﺪ ﺑﻪ ﺁﻧﻬﺎ ﺍﻓﺰﺍﻳﺶ ﻳﺎﺑﺪ. ﺩﺭﺣﺎﻟﻴﻜـﻪ ﺍﻟﮕﻮﺭﻳﺘﻤﻬـﺎﻱ ﻣﺒﺘﻨـﻲ ﺑـﺮ ﺍﺗـﺼﺎﻝ ‫ﻣﺎﻧﻨﺪ 52‪ BMﻭ ‪ TF-IDFﺑﻪﻣﺸﻜﻞ ﻓﻮﻕ ﺣﺴﺎﺳﻴﺖ ﻧﺪﺍﺷـﺘﻪ ﻭﻟـﻲ ﺩﺍﺭﺍﻱ ‫ﻣﺸﻜﻞﭘﻬﻨﺶ ﺭﺗﺒﻪ ﻣﻲﺑﺎﺷﻨﺪ. ﻣﺴﻠﻤﺎﹰ ﺗﺮﻛﻴﺐ ﺍﻟﮕـﻮﺭﻳﺘﻢﻫـﺎﻱ ﻓـﻮﻕ ﺑﺎﻋـﺚ ‫ﻣﻲﺷﻮﺩ ﺗﺎ ﻣﺸﻜﻼﺕ ﻳﻜﺪﻳﮕﺮ ﺭﺍ ﺗﺤﺖﭘﻮﺷﺶ ﻗﺮﺍﺭ ﺩﻫﻨﺪ.

‫ﻣﻬﻤﺘﺮﻳﻦﻣﺴﺌﻠﻪ ﺑﺎﻗﻴﻤﺎﻧﺪﻩ ﭼﮕﻮﻧﮕﻲ ﺗﺮﻛﻴﺐ ﻭﻳﮋﮔﻴﻬﺎﻱ ﻣﺨﺘﻠﻒ ﻣﻲﺑﺎﺷـﺪ. ‫ﺟﻬﺖﺗﺮﻛﻴﺐ ﺍﺯ ﻗﻀﺎﻭﺗﻬﺎﻱ ﻗﺒﻠﻲ ﻛـﺎﺭﺑﺮ ﺑـﺎ ﺗﻮﺟـﻪ ﺑـﻪ ﭘﺮﺳـﺸﻬﺎ ﻭ ﺍﺳـﻨﺎﺩ ‫ﻣﺘﻨﺎﻇﺮ ﺍﺳﺘﻔﺎﺩﻩ ﺷـﺪﻩ ﺍﺳـﺖ. ﻫﻤﭽﻨـﻴﻦﺍﺯ ﻋﻤﮕـﺮ ﺗﺠﻤﻴـﻊ ‪ OWAﺑـﺮﺍﻱ ‫ﺗﺮﻛﻴﺐ ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ ﺍﺳﺖ. ﺑﺮﺍﻱﺑﺪﺳﺖ ﺁﻭﺭﺩﻥ ﻭﺯﻧﻬﺎﻱ ﺑـﺮﺩﺍﺭ ‪ OWAﺍﺯ ‫ﻣﻜﺎﻧﻴﺰﻡ ﻳﺎﺩﮔﻴﺮﻱ ﻣﻨﺎﺳﺐ ﺑﺮ ﻣﺒﻨﺎﻱ ﻗﻀﺎﻭﺕ ﻛـﺎﺭﺑﺮ ﺑـﻪ ﺻـﻮﺭﺕ ﺯﻳـﺮ ‫ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ ﺍﺳﺖ. ‫ﻓﺮﺽ ﻛﻨﻴﺪ ‪ mﺭﺩﻳﻒﺍﻃﻼﻋﺎﺕ ﺩﺭ ﺩﺳﺘﺮﺱ ﺑﺎﺷﺪ ﻛﻪ ﻫﺮ ﺭﺩﻳﻒ ﺁﻥ ﺷـﺎﻣﻞ ‫ﻳﻚﺑﺮﺩﺍﺭ ﺑﺎ ‪ nﺁﺭﮔﻮﻣﺎﻥﺑﻪ ﺻﻮﺭﺕ ) ‪ A = ( a k1 , a k 2 ,..., a knﻭ ﺑﺮﺩﺍﺭِ ‫ﻣﺘﻨﺎﻇﺮ ‪ ((bk 1 , bk 2 ,..., bknﻛﻪ ‪ bkjﻣﺘﻨﺎﻇﺮﺑﺎ ﺑﺰﺭﮔﺘﺮﻳﻦ ﻋﻨﺼﺮ ‪jﺍﻡﺩﺭ ﺑﺮﺩﺍﺭ ‪ Aﺍﺳﺖ (jﺍﻣﻴﻦ ﻋﻨﺼﺮ ﺑﻌﺪ ﺍﺯ ﻣﺮﺗﺐ ﻛﺮﺩﻥA ‪ ) ﺩﺭﺍﻳﻨﺠﺎ ﺁﺭﮔﻮﻣﺎﻧﻬﺎﻱ ‫ﻫﺮﺭﺩﻳﻒ ﻣﺘﻨﺎﻇﺮ ﺑﺎ ﻣﻘﺎﺩﻳﺮ ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ﺭﺗﺒﻪﺑﻨﺪﻱ ﻣﺨﺘﻠﻒ ﺑﻪ ﺍﺯﺍﻱ ﻳـﻚ ‫ﭘﺮﺳﺶ ﻭ ﻳﻚ ﺳﻨﺪ ﻣﻲ ﺑﺎﺷﻨﺪ. ﺑﻨﺎﺑﺮﺍﻳﻦ ‪ nﺍﻟﮕﻮﺭﻳﺘﻢﺭﺗﺒﻪﺑﻨـﺪﻱ ﺑـﻪ ﻋﻨـﻮﺍﻥ ‫ﻭﻳﮋﮔﻲﺑﺎ ‪ mﺟﻔﺖﭘﺮﺳﺶ ﻭ ﺳﻨﺪ ﻣﻮﺟﻮﺩ ﺧﻮﺍﻫﺪ ﺑـﻮﺩ. ﺩﺭ ﺑﺨـﺶ ﻧﺘـﺎﻳﺞ ‫ﺍﻧﻮﺍﻉﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ﺍﺳﺘﻔﺎﺩﻩ ﺷـﺪﻩ ﻭ ﭼﮕـﻮﻧﮕﻲ ﭼﻴـﻨﺶ ﺩﺭ ﻳـﻚ ﻣﺠﻤﻮﻋـﻪ ‫ﺁﺯﻣﻮﻥﺗﻮﺿﻴﺢ ﺩﺍﺩﻩ ﺷﺪﻩ ﺍﺳﺖ.

‫ﻓﺮﺽﻛﻨﻴﺪ ﻳﻚ ﻓﺮﺩ ﺧﺒﺮﻩ ﺑﻪ ﺍﺯﺍﻱ ﻫﺮ ﻫﺮ ﺭﺩﻳﻒ ﺍﻃﻼﻋﺎﺗﻲ ﻳـﻚ ﻣﻘـﺪﺍﺭﻱ ‫ﺑﻪﻧﺎﻡ ‪ d kﺩﺍﺩﻩ ﺑﺎﺷﺪ )ﺩﺭ ﺍﻳﻨﺠﺎ ﻧﺸﺎﻧﮕﺮ ﺩﺭﺟﻪ ﻣﺮﺗﺒﻂ ﺑﻮﺩﻥ ﻫﺮ ﭘﺮﺳﺶﺑـﺎ ‫ﺳﻨﺪﻣﻲﺑﺎﺷﺪ(. ﻫﺪﻑ ﻣﺎ ﭘﻴﺪﺍ ﻛﺮﺩﻥ ﻳﻚ ﻋﻤﻠﮕﺮ ‪ OWAﻳﺎﺑﺮﺩﺍﺭ ﻭﺯﻧـﺪﺍﺭ ‫‪ OWAﺑـﻪﺻـﻮﺭﺕ ) ‪ W = ( w1 , w2 ,..., wnﻣـﻲﺑﺎﺷـﺪ ﻛـﻪ ﻓﺮﺁﻳﻨـﺪ ‫ﺗﺠﻤﻴﻊ ﺭﺍ ﺭﻭﻱ ﺩﺍﺩﻩﻫﺎ ﻣﻄﺎﺑﻖ ﻧﻈﺮﻓﺮﺩ ﺧﺒﺮﻩ ﻣﺪﻝ ﻛﻨﺪ. ﺑﻪ ﻋﺒﺎﺭﺕ ﺩﻳﮕﺮ ﺑﻪ ‫ﻳﻚﺗﺎﺑﻊ ﺗﺠﻤﻴﻊ ﺑﺎ ﺷﺮﻁ ﺯﻳﺮ ﺑﻪ ﺍﺯﺍﻱ ﻫﺮ ‪ kﻧﻴﺎﺯﻣﻲﺑﺎﺷﺪ:

‫‪f (ak 1 , ak 2 ,..., akn ) = d k

 

‫ﺍﻟﮕﻮﺭﻳﺘﻢ ﻳﺎﺩﮔﻴﺮﻱ ﻭﺯﻧﻬﺎ ﺑﻪ ﺻﻮﺭﺕﺳﻨﺎﺭﻳﻮﻱ ﺗﻜﺮﺍﺭﻱ ﺩﺭ ﺷﻜﻞ )۲( ﻧﺸﺎﻥ ‫ﺩﺍﺩﻩﺷﺪﻩ ﺍﺳﺖ. ﺍﺛﺒﺎﺕ ﺷﺪﻩ ﺍﺳـﺖ ﻛـﻪ ﺍﻳـﻦ ﺍﻟﮕـﻮﺭﻳﺘﻢ ﺑـﺎ ﭘﻴـﺪﺍ ‫ﻛﺮﺩﻥﻣﻘﺎﺩﻳﺮ ﻭﺯﻧﻲ ﻣﻨﺎﺳـﺐ ﻫﻤﮕـﺮﺍ ﺧﻮﺍﻫـﺪ ﺷـﺪ. ﻣﻘـﺪﺍﺭ 0<=β<=1 ‫ﻧﺸﺎﻧﮕﺮ ﻧﺮﺥ ﻳﺎﺩﮔﻴﺮﻱ ﺍﺳﺖ ﻭ ‪ lﺑﺮﺍﻱﻣﺤﺎﺳﺒﻪ ‪ wiﻣﻄﺎﺑﻖﻣﻌﺎﺩﻟﻪ )۴( ﺑﻪ ‫ﻛﺎﺭﻣﻲ ﺭﻭﺩ. ﻫﻤﭽﻨﻴﻦ ‪ dﺣﺎﺻﻞﺗﺠﻤﻴﻊ ﺩﺍﺩﻩﻫﺎﻱ ﺭﺩﻳﻒ ‪ kﺑﺎﺗﻮﺟﻪ ﺑـﻪ ‫ﻭﺯﻧﻬﺎﻱﻓﻌﻠﻲ ﺑﺪﺳﺖ ﺁﻣﺪﻩ ﺍﺳﺖ.

 

ﺑﻨﺎﺑﺮﺍﻳﻦ ﭘﺎﺭﺍﻣﺘﺮ ‪ λi ﺗﻌﻴﻴﻦ ﻛﻨﻨﺪﻩ ﻭﺯﻧﻬﺎﻱ ‪ OWAﺍﺳﺖﻛﻪ بوسیلهسورد خطای (dk-dk) بروز آوری می شود. الگوریتم فوق آنقدر تکرارﻣﻲﺷﻮﺩ ﺗﺎ ﺑﺎ ﺧﻄﺎﻱ ‪ eﻣﺘﻮﻗـﻒﺷـﻮﺩ. ﺩﺭ ﺁﺯﻣﺎﻳـﺸﺎﺕ ﻧـﺸﺎﻥ ﺩﺍﺩﻩ شده که نرخ یادگیری 0.3 مناسب می باشد.

ﺍﻟﮕﻮﺭﯾﺘﻢ ‪iRank ‫

 

‫ﺍﻭﻟﯿﻦﺍﻟﮕﻮﺭ ﯾﺘﻢ ﺍﺭﺍﺋﻪﺷﺪﻩ ﺑﺮﺍﯼ ﺭﺗﺒﻪﺩﻫﯽ ﺻﻔﺤﺎﺕ ﺑﻼﮒ ﻣﺘﻌﻠﻖ ﺑﻪ ‪ Adarﻭﻫﻤﮑﺎﺭﺍﻥ ﻣﯽﺑﺎﺷﺪ. ﺁﻧﻬﺎ ﺭ ﻭﺵ ﺟﺪﯾﺪﯼ ﺑﻪ ﻧﺎﻡ ‪ iRankﺭﺍﺑﺮ ﭘﺎﯾﻪ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ‫‪ PageRankﺍﺭﺍﺋﻪﺩﺍﺩﻧﺪ. ﺩﺭ ﺍﯾﻦ ﺭ ﻭﺵ ‪ Adarﺳﻌﯽﻧﻤﻮﺩ ﺍﻃﻼﻋﺎﺕ ﻣﻮﺟﻮﺩ ﺩﺭ ﺳﺎﺧﺘﺎﺭ ﺿﻤﻨﯽ ﻭ ﻏﯿﺮﺻﺮ ﯾﺢ ﮔﺮﺍﻑ ﻓﻀﺎﯼ ﺑﻼﮒ ﺭﺍ ﺩﺭ ﺭﺗﺒﻪﺩﻫﯽ ﺻﻔﺤﺎﺕ ‫ﺑﻼﮒﺗﺎﺛﯿﺮ ﺩﻫﺪ. ﺩﺭ ﻭﺍﻗﻊ ﺗﻤﺮﮐﺰ ‪ Adarﺑﺮﺭ ﻭﯼ ﻫﻤﺎﻥ ﻭﯾﮋﮔﯽ ﺑﺮﭼﺴﺐ ﺯﻣﺎﻥ ﺩﺭ ﻓﻀﺎﯼ ﺑﻼﮒ ﻣﯽﺑﺎﺷﺪ. ﺩﺭ ﺍﯾﻦ ﺭ ﻭﺵ ﯾﺎﻝﻫﺎﯼ ﮔﺮﺍﻑ ﺑﻼﮒ ﺑﺮ ﺍﺳﺎﺱ ‫ﻓﺎﺻﻠﻪ ﺯﻣﺎﻧﯽ ﻓﺮﺁﯾﻨﺪ ﭘﯿﻮﻧﺪ ﺩﺍﺩﻥ، ﻭﺯﻥ ﺩﺍﺩﻩﻣﯽﺷﻮﺩ. ﺑﻪ ﺍﯾﻦ ﻣﻌﻨﺎ ﮐﻪ ﺍﮔﺮ ﻓﺎﺻﻠﻪ ﺯﻣﺎﻧﯽ ﻓﺮﺁﯾﻨﺪ ﭘﯿﻮﻧﺪ ﺩﺍﺩﻥ ﺑﻼﮒ ‪ jﺑﻪﺑﻼﮒ ‪ iﺑﺎﻓﺎﺻﻠﻪ ﺯﻣﺎﻧﯽ ﮐﻤﺘﺮﯼ ﺭﺥ ‫ﺩﻫﺪ، ﺁﻥﮔﺎﻩ ﺑﻪ ﺍﯾﻦ ﭘﯿﻮﻧﺪ ﺍﻣﺘﯿﺎﺯ ﺑﯿﺸﺘﺮﯼ ﺩﺍﺩﻩﻣﯽﺷﻮﺩ. ﺩﻟﯿﻞ ﺍﯾﻦ ﺭ ﻭﺵ ﺑﺮﺍﯼ ﺍﯾﻦ ﮐﺎﺭ ﺍﯾﻦ ﺍﺳﺖ ﮐﻪ ﺍﮔﺮ ﺑﻼﮔﯽ ﺯ ﻭﺩﺗﺮ ﻣﺘﻮﺟﻪ ﻣﻄﻠﺒﯽ ﺩﺭ ﺑﻼﮒﺩﯾﮕﺮ ﺷﺪ ﻭu ‫ﻓﺎﺻﻠﻪﺯﻣﺎﻧﯽ ‫ﺑﻪﺁﻥ ﭘﯿﻮﻧﺪ ﺩﺍﺩ، ﺁﻥ ﭘﯿﻮﻧﺪ ﺩﺍﺭﺍﯼ ﺍﺭ ﺯﺵ ﺑﯿﺸﺘﺮﯼ ﺍﺳﺖ. ﺩﺭ ﺍﯾﻦ ﺭ ﻭﺵ ﺑﻪ ﻫﺮ ﯾﺎﻝ ﻭﺯﻥ ( ‪ wji = w( dijﺗﺨﺼﯿﺺ ﺩﺍﺩﻩ ﻣﯽﺷﻮﺩ ﮐﻪ ‪d ∆ ﺗﻌﺪﺍﺩ ﺭ ﻭﺯ ﮐﻪ ﺩﻭ ﺑﻼﮒ ﺑﻪ ﯾﮏ ﻣﻄﻠﺐ ﯾﺎ ‪ URLﺍﺷﺎﺭﻩﮐﺮﺩﻩﺍﻧﺪ ﻣﯽﺑﺎﺷﺪ، ﯾﻌﻨﯽ ‪ .dji = dj − diﻫﻤﭽﻨﯿﻦ W(dji)ﻧﯿﺰﺗﺎﺑﻌﯽ ﺍﺳﺖ ﮐﻪ ﺑﻪ ﭘﯿﻮﻧﺪﯼ ﮐﻪ ‫ﺑﺎ ﻓﺎﺻﻠﻪ ﺯﻣﺎﻧﯽ ﮐﻤﺘﺮﯼﺑﻪ ﻣﻄﻠﺒﯽ ﺍﺷﺎﺭﻩ ﮐﺮﺩﻩ ﺍﺳﺖ ﺍﻫﻤﯿﺖ ﺑﯿﺸﺘﺮﯼ ﻣﯽﺩﻫﺪ. ‪

‫ﺣﺎﻝﺍﮔﺮ ﺑﻼﮒ ‪ bjﺑﻪ ‪ URL njﻣﺘﻔﺎﻭﺕ ﺍﺷﺎﺭﻩ ﮐﺮﺩﻩ ﺑﺎﺷﺪ ﺁﻥﮔﺎﻩ ﺑﻪ ﻫﺮ ﮐﺪﺍﻡ ﺍﺯ ﺍﯾﻦ ﭘﯿﻮﻧﺪﻫﺎ ﺑﺎﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﺭﺍﺑﻄﻪ ﺯﯾﺮ ﯾﮏ ﻣﻘﺪﺍﺭ ﻧﺮﻣﺎﻝﺷﺪﻩ ﻧﺴﺒﺖ ﺩﺍﺩﻩ ‫ﻣﯽﺷﻮﺩ:

 

ﻭﻗﺘﯽ ﻧﺤﻮﻩ ﻭﺯﻥﺩﻫﯽ ﺑﻪ ﯾﺎﻝﻫﺎ ﺑﻪ ﺍﯾﻦ ﺻﻮﺭﺕ ﻧﺮﻣﺎﻝ ﺷﺪﻩ ﺑﺎﺷﺪ ﻣﺠﻤﻮﻉﻭﺯﻥ ﯾﺎﻝﻫﺎﯼ ﺧﺎﺭﺝ ﺷﺪﻩ ﺍﺯ ﯾﮏ ﺑﻼﮒ ﺑﺮﺍﺑﺮ ﯾﮏ ﺧﻮﺍﻫﺪ ﺑﻮﺩ. ‪ Adarﺍﯾﻦ ‫ﮔﺮﺍﻑﺭﺍ ﮔﺮﺍﻑ ﺟﺮ ﯾﺎﻥ ﺍﻃﻼﻋﺎﺕ ﺿﻤﻨﯽ Implicit Informataion Flow Graphﻣﯽﻧﺎﻣﺪ. ﺑﻌﺪ ﺍﺯ ﺗﻮﻟﯿﺪ ﺍﯾﻦ ﮔﺮﺍﻑ، ﺍﻟﮕﻮﺭ ﯾﺘﻢ ‪ PageRankﺑﺮﺭ ﻭﯼ ‫ﺍﯾﻦﮔﺮﺍﻑ ﺍﻋﻤﺎﻝ ﻣﯽﺷﻮﺩ. ﺑﺎ ﺍﻋﻤﺎﻝ ﺍﯾﻦ ﺍﻟﮕﻮﺭ ﯾﺘﻢ ﺩﻭ ﺭ ﻭﺵ ﺑﺮﺍﯼ ﺍﺭﺗﻘﺎﯼ ﯾﮏ ﺻﻔﺤﻪ ﺑﻼﮒ ﻭﺟﻮﺩ ﺩﺍﺭﺩ: ﯾﮑﯽ ﻣﻌﺮﻓﯽ ﯾﮏ ﻣﻄﻠﺐ ﺟﺎﻟﺐ ﮐﻪ ﺑﺎﻋﺚ ﺍﯾﺠﺎﺩ ‫ﭘﯿﻮﻧﺪ ﺍﺯ ﺳﺎﯾﺮ ﺑﻼﮒﻫﺎ ﺑﻪ ﺍﯾﻦ ﺑﻼﮒ ﺷﻮﺩ ﻭ ﯾﺎ ﻣﻌﺮﻓﯽﯾﮏ ‪ URLﺧﺎﺹﺑﻼﻓﺎﺻﻠﻪ ﻗﺒﻞ ﺍﺯ ﭘﺨﺶ ﺷﺪﻥ ﺁﻥ ﺩﺭ ﻓﻀﺎﯼ ﺑﻼﮒ.

علاوه بر الگوریتمهای یاد شده الگوریتمهای دیگری نیز ارائه و آزمایش شده مانند ( الگوریتم ﺗﺮﻛﻴﺒﻲ ﻣﺒﺘﻨﻲ ﺑﺮ اﻟﮕﻮرﻳﺘﻢ ‪ HITSو ﺗﺸﺨﻴﺺ آﻧﻮﻣﺎﻟﻲ ﺑﺮاي ﻛﺸﻒ ‫ﻣﺎﺷﻴﻨﻬﺎي ارﺳﺎل ﻛﻨﻨﺪه ﻫﺮزﻧﺎﻣﻪ در ﻳﻚ ﺷﺒﻜﻪ ﻫﺪف) که به علت حجم بالای توضیحات در این مقال نمی نگنجد

بهسازی الگوریتمhits برای spam links

خلاصه:

الگوریتمhits که Kleinberg آن را پیشنهاد داده است یکی از روشهای نمونه امتیاز دهی به صفحات وب است که hyperlink ها (کلید یا تصویر یا دکمه ای که در صفحه وب که در صورت انتخاب کاربر را به صفحه دیگری می برد).در ان روزها وقتی الگوریتم پیشنهاد شد ،بیشتر صفاتی که بوسیله الگوریتم امتیازات بالا داشتند واقعاً با عنوان ارائه شده مرتبط بودند و از این رو،الگوریتم می توانست جهت پیدا کردن صفهات مرتبط مورد استفاده قرار بگیرد.هر چند از الگوریتم و انواع مختلف آن مشتمل بر الگوریتم hits بازسازی شده بوسیله bharat که مختصراً bhitخوانده شده و توسط bharatو henzinger پیشنهاد شد امروزه نمیتوان جهت پیدا کردن صفحات مربوطه بیشتر از این مورد استفاده قرار بگیرند که به علت افزایش spamlink(لینکهای spam) می باشد در این مقاله ،ما درابتدا سه روش را جهت پیدا کردن "link form" پیشنهاد می کنیم "link form" یعنی مجموعه ای از لینکهای spam است که یک زیرگراف همبسته متراکم از وب گراف هستند را شکل می دهند .شش الگوریتمی را معرفی می کنیم ،الگوریتم امتیاز راستی (trust-score) که امتیازات بالایی را به صفحاتی می دهند که با احتمال بالا یی صفحه spam نیستند .با ترکیب این سه روش با الگوریتم trut-score و bhits، چندین نوع مختلف از الگوریتم hits را بدست می آوریم با آزمایشات معلوم کردیم که یکی از آنها که tan+ bhits نام دارد و از الگوریتم (trust-score) استفاده می کنند و روش پیدا کردن link form با بکار گیری اسم سرور می باشد،مناسب ترین روش جهت پیدا کردن صفحات مرتبط در وبهای امروزی است .الگوریتمهای ما زمان و حافظه بیشتری را از آنچه الگوریتم hits اصلی می برد مصرف نکرده و میتوان بررسی یک pc با مقدار کمی از حافظه اصلی اجرا شود.

1- مقدمه introduction.

موتورهای جستوجوگر به طور گسترده به عنوان ابزاری جهت دستیابی بروی یک عنوان از وب مورد استفاده می باشند.با دادن کلمات کلیدی که یک موضوع را ویژه می کنند،موتورهای جستوجو گر به صفحات وبی که دارای آن کلمات کلیدی می باشند با استفاده از چندین الگوریتم امتیاز داده و صفحات را با حالت ترولی از امتیاز بر روی وب قرار می دهند.به عنوان نمونه page rank به وسیله Brine پیشنهاد شد و صفحه به عنوان یک الگوریتم امتیاز دهی به وسیله گوگل مورد ایتفاده قرار گرفته است.الگوریتم امتیاز دهی دیگر به نام Hyperlink Induced Topic Search که به صورت hits مخفف شده است که بوسیله Kleinberg یشنهاد گردیده،سه ویژگی آشکار زیر را دارد:

1) اگوریتم hitsامتیاز بالایی را به صفحاتی می دهد که به عنوان مرتبط بوده و بوسیله کلمات کلیدی ویژه شده باشند حتی اگر صفحات شامل کلمات کلیدی نباشند.به عبارت دیگر، بیشتر موتورهای جستوجوتنها صفحاتی را بر روی خروجی می آورند که شامل کلمات کلیدی داده شده باشند.از این رو الگوریتم HITSمی تواند بعضی صفحاتی را پیدا کند که نمی توان آن را بوسیله دیگر موتورهای جستوجویدا کرد.

2) الگوریتم HITS می تواند بر روی یک کامپیوتر شخصی با مقدار کمی از حافظه اصلی اجرا شود،بخاط اینکه الگوریتم فوق به داده های تعدا کمی از صفهات نیاز دارد،آن را با الگوریتم page rank و بیشتر الگوریتم های امتیاز دهی مورد استفاده موتورهای جستوجو گر مقایسه کنید.

3) الگوریتم HITS به محض تقاضا اجرا می شود ،بدلیل اینکه نیاز به داده های کمی داشته که در سراسر شبکه به محض تقاضا جمه اوری می شود.به عبارت دیگر،الگوریتم page rank چندین هفته زمان می برد تا داده ها را جمع اوری کند.بنا بر این نمی تواند به محض تقاضا اجرا گردد.

الگوریتم HITS در آن زمانی که پیشنهاد گردید به خوبی کار کرد.پس از آن چندین الگوریتم پایه HITS معرفی شده است.هرچند،الگوریتم اصلی والگوریتم های بر مبنای HITS به خوبی امروزه کار نمیکنند که به علت افزایش لینک های spam می باشد.چندین روش پیدا کردن لینک های spam اخیرا ایجاد شده است اما آنها نیاز به داده های خیلی زیادی از صفحات دارند تا با یک PC یه محض تقاضا اجرا شوند.به عنوان مثال،روشهای پیشنهادی بوسیله Fretty نیاز به داده هایی از محتوای صفحات دارد که خیلی بزرگتر از داده های لینکهای صفحاتی است که به وسیله الگوریتم HITS مورد استفاده قرار می گیرد.

در این مقایسه ما، در ابتدا 3 روس جهت پیدا کردن "link form" ها را یشنهاد می کنیم که از اطلاعات شبکه استفاده می کنند،یک وب گراف Webgraf یک گراف جهت دار است که مجموعه رأس ان (vertex set) مجموعه ای از صفحات وب و کرانه (لبه)اس مجموعه ای از لینکها بین صفحات است.روش ما "link form" های بیشتری را از روش پیشنهادی Wusdarisonپیدا می کند.سپس ما الگوریتم (trust-score) را پیشنهاد نموده ایم تا امتیازات بالا را به صفحاتی بدهند که با احتمال بالایی spam نبود که از توسعه و بسط عقاید مورد استفاده الگوریتم Trust rank می باشد.سپس 4 الگوریتم امتیاز دهی را ایجاد نمودیم،اولی از مرکب الگوریتم (trust-score) با bhits، حاصل شد،3 الگوریتم دیگر از ترکیب هر یک 3 روش پیدا کردن link formبا دو الگوریتم فوق بدست آمده است.در نهایت الگوریتم های خودمان و چندین الگوریتم بر مبنای HITS را با آزمایشاتی ارزیابی نمودیم.

به منظور ازریابی الگوریتم های متنوع امتیاز دهی ،ما از "کیفیت ده نفوذ اول"که بوسیله یک الگوریتم برای عنوان داده شده است پیدا گردیده استفاده می کنیم،ده نفوذ اول ،صفحاتی از ده امتیاز بالا هستند که بوسیله الگوریتم داده شده است،کیفیت ده نفوذ اول بوسیله تعداد صفحات مرتبط با عنوان در بین ده نفوذ اول اندازگیری می شود و از این رو کیفیت ده نفوذ اول خیلی که باشد 10 مورد می شود.ما کیفیت ده نفوذ اول را با آزمایشات محاسباتی با استفاده از 14 عنوان آزمایش نمودیم.برای تقریبا هم عنوان ها ،الگوریتم ما تقریبا هم 10 نفوذ اول را با کیفیت بالا تر از الگوریتم های موجود پیدا نمود علی الخصوص یکی از الگوریتم های ما،Tan+Bhits که الگوریتم (trust-score) و یک روش پیدا کردن link form بوسیله استفاده از اسم سرورها را بکار می گیرد،10 نفوذ اول با میانگین کیفیت79/8 را پیدا نموده در حالی که الگوریتم های موجود با میانگین کیفیت 07/3 آن را پیدا کردند.(جدول 1 بخش 4)از الگوریتم Tan+Bhits می توان جهت پیدا کردن صفحات مرتبط با یک عنوان داده شده بر روی وب های امروزی استفاده نموده که بیشتر صفحات که بوسیله الگوریتم امتیازات بالایی به آنها داده شده به درستی مرتبط با یک عنوان داده شده جهت تقریباً هم عناوین مورد استفاده در آزمایشهایمان بود.هر چهار الگوریتم نیاز به هیچ داده ای از صفحات دیگر به غیر از داده های جمع آوری شده بوسیله الگوریتم Hits اصلی ندارند،از این رو می تواند به محض تقاضا برای یک عنوان درخواستی بر روی یک Pc با مقدار کمی از حافظه اصلی اجرا شود. بقسه اسن مقاله به صورت ریز سازماندهی شده است.در بخش دو ما خلاصه ای ا الگوریتم Hits پیشنهادی Kleinberg را تهیه کرده و کارهای مرتبط با آن را معرفی می کنیم،در بخش 3،ما ابتدا سه روش پیدا کردن "link form" را پیشنهاد نموده و سپس الگوریتم (trust-score) را پیشنهاد می کنیم،و در نهایت 4 متغیر تصحیح شده الگوریتم Hits را با ترکیب نمودن الگوریتم BHITS با 3 روش پیدا نمودن "link form" و الگوریتم (trust-score) بدست می آوریم.در بخش 4 ،ما نتیجه بدست آمده از آزمایشات محاسباتی را آنالیز می کنیم .بخش 5 ،ملاحظات نتیجه گیری را نشان می دهیم .یک نسخه مقدماتی از مقاله در {2} مرجع ارائه شده است.

2. مقدمات Preliminarilies

در ابتدا ما یک HOST name و Domain name را برای بخش 2.1 تعریف می کنیم سپس الگوریتم Hits اصلی را در بخش 2.2 معرفی نموده و در نهایت خلاصه از الگوریتم BHITS که بوسیله Henzingerو Bharal پیشنهاد شده را می آوریم (بخش 2.3).

2.1: ضوابط و شرایط Terms

چون که عبارت " HOST name" بعضی اوقات با عبارت " Domain name" اشتباه می شود ،ما از تعاریف ذیل در کل مقاله استفاده می کنیم:

HOST name یک صفحه وب p ، اسم HOST (میزبان) که شامل pاست به عنوان HOST name (اسم میزبان یا وب )p، ما از یک زیررشته p'URI بین http:// و علامت / بعدی استفاده می کنیم .به عنوان نمونه ،اگر یک صفحه p ، آدرس url، www.gecities.jp/ken/index/.... را داشت سپس HOST name،p عبارت آدرس www.gecities.jp می باشد.

اجازه بدهید که dam level(p) یک بعلاوه تعداد علائم "." در (dot) صفحه p باشد.بنابر این dam level(p)=3 برای صفحه بالا می باشد.یک p را بوسیله (dot) به تعدادی dam level(p)از زیررشته ها تقسیم کنید،سپس -iامین زیر رشته از سمت راست-iامین سطح Domain نمیده می شود.به عنوان مثال اگر HOST nameیک صفحه p ، آدرسwww.geocities.com است، پس geocitiesسطح دوم Domain از p می باشد. می گوئیم که دو صفحه p،q همان Domain nameرا دارند اگر p،qهمان HOST nameرا داشته باشند یا>3dam level(p)=dam level(q) و-iامین سطح Domain از p مساوی با q است اگر که-11<i< dam level(p) باشد .به عنوان مثال اگر صفحه p آدرس urlhttp//news.www.infoseek.co.jp و صفحه q به ادرس http//music.infoseek.co باشد بنابر اینp,q همان Domain nameرا دارند ، بخاطر اینکه=5dam level(p)=dam level(q)وp,q همان سطح Domain های اول،دوم، سوم و چهارم را که به ترتیب gp.co.infiseek.www هستند را دارا می باشد. به عبارت دیگر،اگر صفحه p به آدرس http://qsk.jp و صفحه q به آدرس http://slashdot.jp باشند،پس p,q همان Domain را ندارند بخاطر اینکه HOST nameهمان را نداشته و =2dam level(p)=dam level(q)است.

.2.2 . الگوریتم Hits اصلی .

الگوریتم Hits که بوسیلهkleinberg پیشنهاد گردید نفوذها و قطبیتهایی را برای یک عنوان خاص یا کلمات کلیدی ارائه شده پیدا می کند.الگوریتم یک صفحه را که از سوی صفحهات بسیاری به آن وصل شده اند را بعنوان یک نفوذ و یک صفحه را که ارتباط با نفوذ های زیادی دارد را بعنوان قطبیت در نظر می گیرد.دقیقتر الگوریتم یک،"امتیاز نفوذ"و"امتیاز قطبیت"از هر صفحه را محاسبه می کند.همانطوریکه در زیر فهرست شده است:

1- اجازه بدهد مجموعه ریشه rمجموعهای از x صفحه اول نتیجه بعضی موتور های جستجو گر برای کلمات کلیده داده شده باشد که در ان x یک پارامتر عدد صحیح است. kleinbergمعمولاً x=200 را انتخاب می کردد.

2- یک گراف وب g=(v.e)درست کنید که در آن مجموعه رأس v یک تابع منطقی از r و مجموعه ای از همه صفحاتی باشد که یا به r یا از r ارتباط گرفته باشد و مجموعه کناره(لبه) e شامل هم ارتباطات بین صفحات در v بجزء ارتباطات بین صفحاتی که همان HOST nameرا دارند ،باشند.

3- برای هر رأس1<i<IVI ، یک امتیاز نفوذ Ai تا 1 یک امتیاز قطبیت Hi تا 1 را قرار دهید.

4- دستورالعمل زیر به تعداد l مرتبه تکرار کنید ،lپارامتر عدد صحیح داده شده است.

 

5- بردار های a,h و ر را روی خروجی قرار دهید.

kleinbergمعمولاً l=50 می گیرد،بخاطر اینکه aوh اغلب پس از تکرار مراحل (A)-(C)در گام 50 بار تکرار می شوند.

در سرتاسر مقاله،منظور از ده نفوذ اول که بوسیله یک الگوریتم بر مبنای Hits پیدا شده ،ده صفحه با بالاترین امتیاز نفوذ در بین صفحاتی که بوسیله الگوریتم یافت شده است،و ما کیفیت ده نفوذ اول را با تعداد صفحات مرتبط با یک عنوان ارائه سده در بین ده نفوذ اندازه گیری می کنیم ،به عنوان مثال،اگر ده نفوذ اول پیدا شده با الگوریتمی بر مبنای Hits شامل هفت صفحه مرتبط عنوان داده شده باشند.پس کیفیت ده نفوذ اول ،عدد 7(هفت)است.اندازه گیریهای مشابهی بوسیله چندین محقق بر روی الگوریتم مورد استفاده قرار گرفته است.

الگوریتم Hits اصلی می تواند ده نفوذ اولیه با کیفیت تقریبا خوب را پیدا کند و می تواند در جهت پیدا کردن صفحات مرتبط با یک عنوان داده شده را در زمانی که پیشنهاد گرید به کار رود.متعاقباً،چندین محقق به یک مشکل تقویت کننده دو سوی و"اغراق موضوع" از الگوریتم Hits اشاره نموده اند و انواع متنوعی از الگوریتم ها را بر مبنای Hits با راه حل های موثر برای این مشکلات را پیشنهاد نمودند.ما مسئله"تقویت کننده دو سوی"را در بخش 2.3 توضیح خواهیم داده الگوریتم HITS اصلی بعضی اوقات به طور غیر درست امتیازات بالایی را به صفحاتی می دهد که به عنوان داده شده مربوط نمی شود،این مشکل،انحراف موضوع"نامیده میشود. (topicdift)

تعداد صفحات روی وب به صورت نمایی از زمان تولد وب در حال افزایش است و انچه که spam نامیده می شود هم در حال افزایش می باشد.در وب امروزی ،الگوریتم Hits و متغیر ها نمی توانند ده نفوذ اول با کیفیت خوب را پیدا کنندبه دلیل اینکه لینکهای spamافزایش یافته است.

بعضی محققین یک لینک spam زا به صورت زیر تعریف کرده اندیک لینک از یک صفحه q یک لینک spamاست اگر محتوای ض به محتوای ح ربطی نداشته باشد و لینک ایجاد شده تا روش امتیاز دهی را مجبور سازد تا امتیاز بالایی را به سایت ض دارای صفحه ح بدهد.پیدا کردن لینک های spamبر طبق این تعریف مشکل است،از این رو محققین تلاش دارند تا به طور تقریبی لینکهای ر را با استفاده از روش ای ذهنی و ابتکاری پیدا کند.به عنوان مثالfetterly چنین روش ابتکاری را جهت پیدا کرد spamپیشنهاد نمود.روشهای ابتکاری از اطلاعات محتوایی صفحات استفاده می کنند،در حالی که Hits اصلی تنها از اطلاعات ارتباطی صفحات استفاده می کنند. Castacarvslho چندین روش ذهنی و ابتکاری را پیشنهاد نمود تا لینکهای spamرا بااستفاده از ساختارهای مشخصه گراف لینکهای inter-host (درون-اسمی)،هرکدام بین یک صفحه در یک host و یک صفحه در hostدیگر پیدا کند.هم این روش نیاز به داده صفحات زیادی بیش از صفحات مورد استفاده بوسیله الگوریتم اصلی Hits ،دارد.بنابر این،روشهای موجود پیدا کردن لینکها ی spamنیاز به داده ای بیشتر داشته پس،برای هدف ما از برقراری یک الگوریتم امتیاز دهی که می تواند به محض تقاضا بر روی یک pc اجرا گردد،مناسب نباشد.

2.3.

الگوریتم Hits اصلی مشکل زیر را دارد.اگر شخصی نادرست (یا بد خواه)یک hostدرست کند که دارای تعدادی صفحه باشد که به همان صفحهp در سایتی دیگر مرتبط باشد ،پس امتیاز نفوذ صفحه p به طور نادرستی بالا می شود.یک فرد به راحتی چنین host را می تواند درست کند.بنابر این ،ده نفوذ اول پیدا شده توسعه الگوریتم Hits اصلی می تواند با کار شخصی نادرست غیر قابل اعتماد شود.این مشکل یک مسئله تقویت کننده دو سوی “matualveinforcing” نامیده می شود.

با اصلاح الگوریتم اصلِیbharatالگوریتم bhits را پیشنهاد نمود که تقریبا مسئله مزبور را حل می نموده هم اکنون ما چندین نماد و علامت گذاری را معرفی می کنیم تا اصلاحیات او را شرح دهد.برای هر رأس Vi در مجموعه پایگاه V مورد استفاده درhits اصلی ، Γ-(vi) مجموعه رئوس { Vj є V | (Vj,Vi) є E} و Γ+(vi) مجموعه رئوس { Vj є V | (Vi,Vj) є E} می باشند. H-(vi) , H+(vi) مجموعه هم host هایی می باشد که دارای صفحاتی مشابه با رئوس در Γ-(vi) یا Γ+(vi) هستند.برای هر host ،

 

، تعداد لینکهایی هستند که از صفحاتی در HOSTk به صفحه Vi می روند.برای هر

 

را در مرحله 4از الگوریتم اصلی را با روش aوb به ترتیب ، جابجا نموده است.

 

پس،حتی اگر یک تعداد از صفحات در یک host به همان صفحه مرتبط شد،امتیاز نفوذ صفحه p بوسیله الگوریتم Bhits زیاد نمی شودو بنا بر این مسئله تقویت کننده دو سوی تقریبا حل می شود.

3- اصلاحات .

در بخش 3.1 ،در ابتدا ما سه روش پیدا کردن linkform را پیشنهاد می دهیم سپس در بخش 3.2،ما الگوریتم trust-score را پیشنهاد نموده ایم و در نهایت در بخش 3.3 ما چهار الگوریتم امتیاز دهی جدید را با ترکیب الگوریتم Bhits با 3 روش پیدا کردنlinkform و الگوریتم trust-scoreطرح ریزی می کنیم.

3.1 خارج کردن linkformها

Wu وdavison یک linkformرا بعنوان مجموعه لینکهای spam تعریف نموده اند که یک زیر گراف همیشه متراکم را بر روی یک وب گراف تشکیل می دهند،و گفتند که یک صفحه به یک linkformمتعلق می باشد اگر صفحه انتهای یک لینک spamدر linkformباشد .الگوریتم HITS امتیازات نفوذ و قطبیت بالایی را به صفحاتی می دهد که متعلق به زیر گراف همیشه متراکم باشد و بنابر این صفحات متعلق به یک زیر گراف امتیاز نفوذ و امتیاز قطبیت بالایی را می گیرد.در نتیجه ،ده نفوذ اول بدست آمده توسط الگوریتم دارای تعداد صفحاتی است که به متعلق به linkformها می باشد. Wu وdavisonالگوریتمی را جهت پپدا کردن linkformها پیشنهاد کردند و ازریابی کردند که الگوریتم شان جهت الگوریتمهای امتیاز دهی چقدر بهبودد یافته است.جهت ارزیابی آن ها از یک الگوریتم امتیاز دهی ساده استفاده کردنند که به هر صفحه یک امتیاز برابر با تعداد لینک هایی که به صفحه وارد می شوند را می دهند.برای بیشتر عناوین استفاده در آزمایشات،الگوریتم امتیاز دهی ساده می تواند ده نفوذ اول با کیفیت خوب را بدست اورد اگر از همه لینک هایی که بوسیله الگوریتم linkformها پیدا شده صرفنظر شود.بنابر این الگوریتم شان جهت بهبود الگوریتم امتیاز دهی شان موثر می باشد.هرچند آنها تأیید نکرده اند که آیا الگوریتمشان جهت بهبود الگوریتم های بر مبنای HITSموثر است یا خیر که این مسأله از الگوریتم امتیاز دهی شان پیچیده تر می شود.

ما ارزیابی کرده ایم الگوریتم انها جهت بهبود الگوریتم BHITS چقدر موثر می باشد فرض کنید LF+ BHITS الگوریتم BHITSاز هم لینکهایی که از linkformهایی که توسط Wu وdavisonپیدا شده صرفنظر می کند .ما کیفیت ده نفوذ اول پیدا شده توسط LF+ BHITSرا ددر بخش 4 ارزیابی خواهیم کرد.

ما کشف کرده ایم که یک linkformنمونه از صفحاتی تشکیل شده است که بعضی از انواع اطلاعات شبکه را تسهیم می کنند که می توان به host nameو domain name.ip address .name server اشاره نمود.(هر دوی .ip addressهای host که صفحه دارند و اسم name serverمورد استفاده host می تواند به آسانی با چند روش مثل ns lookupunix بدست آید)به عنوان نمونه یک linkformشامل پنج صفحه زیر همان domain nameرا تسهیم می کنند.

 

یک linkformمشتمل بر 5 صفحه زیر وجود دارد که همان.ip addressرا تسهیم می کن.

همه صفحات در هر کدام از دو linkformبالا همان name serverرا تسهیم میکند.

الگوریتم اصلی هر لینک بین 2 صفحه را که متعلق به همان host باشد را نادیده می گیرید ،اما هنوز از تعدادی linkformصدمه می خورد.نویسنده مراجع 7 و 9 .اشاره کرده است که مجموعه صفحه هات spam ایجاد شده توسط فرد بد اندیش (خرابکار)بطور مداوم همان نوع از اطلاعات شبکه را تسهیم میکند حتی اگر صفحات همان host nameرانداشته باشد.با جستوجوی تعدادی از صفحات که همان domain name.ipaddress.domain.را تسهیم می کردند،فهمیدیم که آناه معمولاً همان name server را تسهیم می کنند.

بنابراین الگوریتم Bhits راپیشنهاد می کنیم که به طور اختصار N+BHITS نامیده می شود این الگوریتم ،الگوریتم Bhitsبا دو اصلاح و تغییر زیر است:

1- در مرحله 2الگوریتم اصلی، هر لینک بین دو صفحه که همان name server را وب گراف g تسهیم می کند خارج سازید و:

2- از یک name serverبه جای host name در مرحله u(A)) و (B) از الگوریتم BHITS استفاده می کنید.

فرض کنید الگوریتم IP+BHITS،مخفف I+BHITS همان الگوریتم N+BHITS باشد به جز اینکه از یکIP address به جای Nameserver+BHITS استفاده می کند.به طور مشابه،الگوریتم DOMAIN+BHITS را، مخفف D+HITS، همان N+BHITS فرض کنید به جای اینکه از یک Domain name به جای Nameserver استفاده کند.این عقیده ای جدید نیست که از لینک های بین دو صفحه که همان IP address یا Domain name صرفنظر شود،اما ما تأثیر این عقاید را با روش پیشنهادی مقایسه می کنیم.ما کییفیت ده نفوذ اول پیدا شده توسط I+BHITS , D+HITS N+BHITS ور را در بخش 4 ارزیابی خواهیم نمود.

3.2Trust-Score

Gyougyi،الگوریتم فوق را پیشنهاد که به طور تقریبی "صفحات قابل اعتماد" را پیدا نموده که با انگیزه های خرابکارانه ایجاد نشده باشد.این الگوریتم یک امتیاز قابلیت اعتماد"Reliability score"به یک صفحه از وب را می دهد.عقیده اصلی مورد ااستفاده این الگوریتم این است که"یک صفحه لینک شده از صفحات قابل اعتماد،قابل اطممینان خواهد بود"این عقیده مشابه با عقیده اصلی مورد استفاده الگوریتم PageRank است،"یک صفحه لینک شده از صفحات مهم،مهم خواهد بود".

الگوریتم PageRank نیاز به تعداد زیادی صفحه بر روی وب مشابه با الگوریتم PageRank داشته و نمی تواند مستقیما مورد استفاده قرار بگیرد تا به صفحات بر روی یگ وب گراف کوچک مورد استفاده الگوریتم HITS امتیاز بدهدبدین معنی که،ما نمی توانیم مستقیماً از الگوریتم PageRank جهت بهبود الگوریتم HITS استفاده کنیم.

ما الگوریتمی را پیشنهاد کردیم که یک Trust-Score را به هر صفحه ای که دارای مجموعه پایگاه مورد استفاده HITS است ، می دهد.با بکارگرفتن عقاید دو الگوریتم فوق ،می گوئیم که یک صفحه دارای اعتماد است اگربه بیشتر صفحات قابل اعتماد مرتبط با یک موضوع ارائه شده لینک شود و این مسئله یک صفحه قطب خوب برای موضوع است.برای بیشترعناوین مورد استفاده در آزمایشات مقدماتی مان ،پیدا کرده ایم که بیشتر از نصف صفحات در ریشه R قابل اعتماد بوده و به عنوان داده شده مرتبط هستند.الگوریتم Trust-Score ما به عنوان یک صفحه U تحت عنوان صفحه قطب Hub قابل اعتماد نگاه می شوداگر صفحه U به بیشتر صفحات در مجموعه ریشه لینک شود و به یک صفحه v به عنوان یک صفحه نفوذ قابل اعتماد نگاه می شود اگر صفحه v از بیشتر صفحات قطب Hub لینک شود.اگر دو یا بیشتر Host وجود داشته باشد،هرکدام داری صفحهای هستند که متعلق به مجموعه ریشه می باشد که از یک صفحه U لینک شده باشد ،پس الگوریتم Trust-Scoreیک U می دهد،T hub(u) برابر با تعداد این Host ها را می دهد،در غیر این صورت T hub(u)=0 همچنین الگوریتم یک صفحه V ،T auth(v) برابر با مجموعه امتیازات قطب درست از صفحات U که به V لینک می شود را می دهد. Trust-Score صفحه V امتیاز نفوذ درستی است که بوسیله مجموع امتازات نفوذ درست عادی سازی شده اند.امتیاز قطب درست یک صفحه U یک مقداری است تا نشان بدهد که یک U به عنوان صفحه قطب چقدر قابل اعتماد است و Trust-Score یک صفحه V یک مقداری است تا نشان بدهد صفحه ؤ بعنوان یک صفحه نفوذ چقدر قابل اعتماد است.بنابر این الگوریتم Trust-Score به صورت زیر است.

الگوریتم Trust-Score

فرض کنید R ,V,E به ترتیب مجموعه ریشه،رأس و کنار مورد استفاده در الگوریتم HITS می باشد.

01 هر صفحه U ،{s1,s2,…,sk} و U€V مجموعه ای از همه صفحات هستند که از U لینک شده اند و متعلق به مجموعه ریشه R است،.

یعنی اینکه ،(u,si)€Eو1<=i<=Kو Si€R.فرض کنید Host(u)تعداد Hostnameهای مجزا از s1,s2,…skمی باشد .اگر Host(u)>=2پش مجموعه Host(u)=Thub(u).در غیر این صورت Thub(u)=0

 

3.3 چهار الگوریتم امتیاز دهی ما.

ما چهار الگوریتم زیر را که از الگوریتم Trust-Score استفاده می کنند را پیشنهاد نموده ایم فرض کنید Trust-Score+ BHITS مخففT+ BHITS الگوریتمی می باشد که به یک صفحهP ،امتیاز t(p)+a(p) را می دهد که t(p) , Trust-Score از صفحه P بوده و a(p) امتیاز نفوذ p است که بوسیله BHITS محایبه می شود.به طور مشابه ،فرض کنید TaI+BHITS ، TaD+HITS، TaN+BHITS الگوریتم هایی هستند که به یک صفحه P امتیاز t(p)+a(p) را می دهند که a(p) امتیاز نفوذ P است که به وسیله 3 الگوریتم فوق محاسبه می شود.3 الگوریتم فوق به ترتیب : Trust-Score+) (IP+BHITS،( DOMAIN+BHITS، Trust-Score) ، (Nameserver+BHITS، Trust-Score) می باشد. با استفاده از فاکتور وزنی X , Y فرد می تواند الگوریتمی ایجاد کند که به یک صفحه امتیاز t(p)+y.a(p)را می دهد. ما بعضی آزمایشات مقدماتی را درست کرده ایم که در آن وزنهای X , Y را تغییر می دهیم ، و ثابت کردیم که برای بیشتر عناوین مورد استفاده،ده نفوذ اول با بهترین کیفیت وقتی حاصل می شود کهX=y=1 باشد.ما کیفیت ده نفوذ اول که حاصله از T,TaI,TaD. ، TaN+BHITS را در بخش 4 ارزیابی خواهیم نمود.

4. نتایج آزمایش

 

جدول 1 نتایج آزمایشاتی را که از دسامبر 2005 تا زانویه 2006 برای یازده الگوریتم بر مبنای HITS انجام داده ایم را نشان می دهد.3 تای اول الگوریتم های HITS ، B HITS، WB HITS هستند که بوسیله پیشنهاد شده اند،در جدول 1 این الگوریتم به ترتیب به طور اختصاری H.B.W نامیده شده اند.4 الگوریتم بعدی N+BHITS ،1 ،D، LF هستند که به طور اختضاری NB،IB ، DB، LB هستند که در بخش 3.1 معرفی شدند ومتغیر های الگوریتم BHITS هستند که از روش های پیدا کردن LinkFormهاستفاده می کنند، LF+BHITS از روشWU درپیدا کردن LinkFormها ،استفاده کرده،D+BHITS از یک DomaiName از یک I+BHITS از IPaddress استفاده کرده اند.چهار الگوریتم آخری به ترتیب به طور اختصاری Tan,TaI,Tadهستند که الگوریتم هایی هستند که از الگوریتم Trust-Score در بخش 3.2 استفاده نموده اند، T+BHITS الگوریتم Trust-Score را با BHITS و بطور مشابه به 3 الگوریتم TaN+BHITS و TaI+BHITS و TaD+HITS الگوریتم Trust-Score را به ترتیب با N+BHITS، I،D ترکیب نموده است.

هر یک از چهارده عنوان داده شده ،به وسیله یکی از چهارده کلمه کلیدی زیر ویزه و معین شده اند:

 

برای هر عنوان ،مجموعه ریشه مورد استفاده در آزمایشات ،شامل دویست صفحه اول نتایجGoogle برای عنوان های بالا بوده است.الگوریتم های بر مبنای HITS که شامل الگوریتم ما هم می شود می تواند چندین کلمه کلیدی را به عنوان یک ورودی علاوه بر کلمه کلیدی مفرد دریافت کننده نتایج برای دیگر موضوعات که توسط یک یا چند کلمه کلیدی ارائه گردیده به عنوان های مورد استفاده در آزمایشات شبیه بر ده نتایج حاصل شده از موتورهای جستوجوگر غیر از Google هم مشابه با موتور جستوجوگرGoogleمی باشد.

هرسلول در ردیف های "عنوان 1"تا "عنوان 14" از جدول 1 کیفیت ده نفوذ اول پیدا شده توسط هر الگوریتم را برای موضوع داده شده نشان می دهد همانطور که قبلاً شرح دادیم،کیفیت ده نفوذ اول به عنوان تعدادی صفحه تعریف می شود که مرتبط با عنوان داده شده و متعلق به ده نفوذ اول پیدا شده توسط هر الگوریتم می باشند.این مسأله توسط بازرسی و بررسی دستی اشخاص مورد قضاوت قرار می گیرد که آیا یک صفحه به درستی مرتبط با موضوع داده شده است؟ خیلی از محققین از روش های مشابه جهت ارزیابی روش های بر مبنای HITS استفاده کرده اند.{3}{4}{12}.{18}-{14}.برای هر الگوریتم "میانگین" ردیف در جدول یک کیفیت میانگین ده نفوذ اول بدست آمده برای چهارده عنوان را نشان می دهد . برای هر الگوریتم "مقدار کافی" ردیف، تعداد عناوین را برای هر عنوانی نشان می دهد که کیفیت کافی را داشته باشند،ما می گوئیم به کیفیت ده نفوذ اول "کافی" است اگر ده نفوذ اول شامل تنها دست کم یک صفحه غیر مرتبط با موضوع باشد.به عنوان مثال HITS اسلی ده نفوذ اول با کیفیت کافی را برای تنها دو عنوان در بین 14 عنوان پیدا می کند،و TaN+BHITS ده نفوذ اول با کیفیت کافی را برای دوازده عنوان پیدا می کند.

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

می گوئیم که دو Hosts به نام های Hosts1 و Hosts2 به طور دو سویه با هم مرتبط و لینک هستند اگر یک لینک از یک صفحه در Hosts1 به یک صفحه در Hosts2 و یک لینک از یک صفحه در Hosts2 به یک صفحه در Hosts وجود داشته باشد و می گوئیم یک لینک از یک صفحه در یک Hosts2 به یک صفحه دیگر یک لینک درون هاست دو سویه"mutual inter-host link" است اگر این Hosts ها به صورت دو سویه لینک باشند .برای 4 عنوان F1(عناون3) ،olympic(عنوان 9) Poporger(عنوان 10)وRok-climbing(عنوان 12) ،ما تعدای LinkForm را پیدا نمودیم که هرکدام شامل چندین لینک درون هاست دو سویه بودند.این LinkForm ها نمی توانند به وسیله LF+BHITS با روش WU که LinkForm ها را پیدا می کنند،پیدا شود،بخاط اینکه روش فوق تنها LinkForm هایی را پیدا می کنند که شامل تعدادی لینک های درون هاست دو سویه باشند.به عبارتی دیگر هر یک از LinkForm ها متشکل از لینک هایی بین صفحاتی است که بعضی اطلاعات شبکه را تسهیم می کنند،و بنابر این دست کم یکی از الگوریتم های I+BHITS و N+BHITS و D+BHITS چنین LinkForm هایی پیدا می کنند.این دلیل است که چرا الگوریتم های پیشنهادی و I+BHITSو N+BHITS و D+BHITS ده نفوذ اول با کیفیت بهتر را از LFبهتر پیدا می کنند از این رو ، روشهای پیشنهادی ما در پیدا کردن LinkForm ها جهت اصلاح الگوریتم BHITS از روش WU وDavison موثر تر می باشد.برای بیشتر 14 عنوان داده شده N+BHITS ده نفوذ اول را با کیفیت بهتری نسبت به I+BHITS و D+BHITS پیدا می کند،از این رو روش پیدا کردن LinkForm ها با بکار گیری namesarver بهتر از دو روش دیگر جهت اصلاح الگوریتم BHITS می باشد.

برای بیشتر 14 عنوان ،الگوریتم های چهار گانه ما که از الگوریتم Trust-Score استفاده نمودندTan,TaI,Tadو TaN+BHITS ده نفوذ اول را با کیفیت بهتری نسبت به دیگر الگوریتم ها پیدا کردند،از این رو الگوریتم Trust-Score جهت اصلاح الگوریتم BHITS موثر می باشد.به طور خاص برای بیشتر عناوین،الگوریتم TaN+BHITS ده نفوذ را با کیفیت بهتری نسبت به آنهایی که توسط دیگر الگوریتم ها پیدا می شوند را می یابد.

میانگین کیفیت 8.79 در ده نفوذ اول که توسط TaN+BHITS پیدا می شوند به طور چشمگیری از کیفیت میانگین 1.71 و3.07 به ترتیب برای HITS ، BHITSوWBHITS بهتر می باشد. TaN+BHITS همچنین ده نفوذ اول را با کیفیت مناسب برای بیشتر عنوان ها پیدا می کند 12 عنوان – در حالی الگوریتم های موجود بر مبنای HITS چون HITS ، BHITSوWBHITS یافته های خود را برای تعداد محدودی عنوان با کیفیت مناسب دارند.برای عنوان "Kabuki(عنوان 6)" "olympic"(عنوان 9) ،Pipe-organ(عنوان 10) ،Rock-climbing(عنوان 12) Tennisعنوان (13)،.ده نتیجهGoogle شامل بعضی صفحات غیر مرتبط با عنوان بود،تما همه صفحات در ده نفوذ اول یافت شده توسط TaN+BHITS مرتبط با عنوان بودند همه 11 الگورتیم از مجموعه ریشه استفاده کردند که متشکل از دویست صفحه اولی بود که امتیاز بالا یی را از Google گرفته بودندوGoogle از بعضی تفکیک ها استفاده می کند تا از عهده لینک هایSPAM LinkForm ها بر بیاد.بنابر این، مجموعه ریشه لینک های SPAM کمتری از مجموع دوست صفحه دارد که شامل کلمه کلیدی داده شد و اتنخاب دلخواه از وب می شود.هر چند،الگوریتم TaN+BHITS ،ده نفوذ اولی را پیدا می کند که شامل بیشتر صفحات مرتبط با عنوان داده شده باشد هرچند که الگوریتم HITS اصلی ده نفوذ اولی را پیدا می کند صفحات مرتبط کمتری را دارد.بنا بر این،روش پیشنهادی پیدا کردن LinkForm که از یک Nameserver و الگوریتم Trust-Score استفاده میکنند جهت دستیابی به ده نفوذ اول با کیفیت خوب موثر می باشد.

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

1- آنها به عنوان ارئه شده مربوط بوده.

2- آنها متعلق به ده نفوذ اولی هستند که توسط الگوریتم پیدا شده اند.

3- آنها متعلق به مجموعه ریشه نمی باشند.

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

می توان 3 حقیقت زیر را مشاهده نمود:

a) الگوریتم هایی که از روس ما در پیدا کردن LinkForm ها استفاده می کنندBHITSوTaIوTaDوNوD، I مقدار عدد بزگی را در ردیف بسبت به الگوریتم های HITS ، BHITSوWBHITS دارند.

B) : D+BHITS مقدار بزرگتری را در ردیف از الگوریتم TaN+BHITS که الگوریتم حاصل شده از ترکیب: D+BHITS با Trust-Score است دارد می باشد.

TaN+BHITS مقدار بزرگتری ار از دیگر الگوریتم ها با استفاده از Trust-Score دارد.

C) D) این مفهوم را می رساند که روشهای ما در پیدا کردن LinkForm برای پیدا کردن صفحات مربوطه که توسط Google پیدا نمی شود موثر تر می باشد. B می تواند به صورت زیر توضیح داد شود:الگوریتم Trust-Score به طور مداوم امتیاز بالاتری را به صفحاتی می دهد که متعلق به مجموعه ریشه باشد و از این رو،هم الگوریتم هایی که از Trust-Score استفاده می کنند به طور مداوم ده نفوذ اول را که شامل صفحات متعلق به مجموعه ریشه می باشد را پیدا می کنند،در نتیجه این ده نفوذ اول دارای چند صفحه هستند که متعلق به مجموعه ریشه نمی باشد،بنا بر این TaD+BHITS (یا TaN+BHITS و TaI)که از ر استفاده می کند مقدار کوچکتری را در ردیف از D+BHITS (یا N+BHITS وI)بدون الگوریتم Trust-Score دارا می باشد .همانطور که در بال توضیح دادیم ،الگورتم هابا Trust-Score ؟ ده نفوذ اول را با کیفیت بهتری نسبت به الگوریتم های بدون Trust-Score پیدا می کنند و از این رو حقیقت(b) این مطلب را می رساندد که یک تعادل بین کیفیت ده نفوذ اول و مقدار در ردیف وجود دارد.کیفیت ده نفوذ اول عموماً مهمتر از ارزش در ردیف است و از این رو،حقیقت(c) نشان می دهدکه TaN+BHITS بهترین گزینه جهت پیدا کردن ده نفوذ اول با کیفیت مناسب و تعداد صفحات مرتبطی است که نمی توان آنها را بوسیله Google یافت.

برای هر الگوریتم ، ردیف انتهایی"non- Google " جدول یک عددمیانگین صفحاتی را می دهد که متعلق به ده نفوذ اول پیدا شده توسط الگوریتم و نه Google می باشد.به عنوان مثال ، ده نفوذذ اول پیدا شده توسط TaN+BHITS شامل 5.93 صفحه به صورت میانگین است که متعلق به صفحات یافت شده توسط Google نمی باشد.می توان مشاهده کرد که الگوریتم ها BHITSوTaIوTaDوT،ده نفوذ اولی را پیدا می کنند که 5 یا 6 تای آناه در صفحات یافت شده توسط Google رتبه بندی نشده اند.از این رو، الگوریتم های ،جهت پیدا کردن صفحات مرتبط از نتایج Google متفاوت و متمایز می باشد.حال ما بعصی از مسایل باقیمانده از الگوریتم های بر مبنای HITS مان را مطرح می کنیم.برای عنوان"Chess "0عنوان 2) هم الگوریتم های به جزء T+BHITS ده نفوذ اولی را پیدا کردند که صفحات مرتبط با عنوان را اصلاً نداشتند.بر روی وب گراف مورد استفاده T+BHITS برای عنوان 2، چندین لینک وجود دارد که از صفحاتی با امتیاز قطب درستی بالا ناشی شده اند و به بعضی صفحات مرتبط در ده نفوذ اول وارد می شوند و از این رو به این صفحات مرتبط امتیاز درستی بالایی Trust-Score داده شده است.بیشتر این لینک ها به صفحاتی محلق می شوند که چنین اطلاعات شبکه ای را به جز Hostnameمثل domain name،IPaddress، name server تسهیم می کنند.از این لینک ها BHITSوTaIوTaDوNوD، I و TaN+BHITS صرفنظر شد و بنابر این ده نفوذ اول این الگورتیم ها شامل چنین صفحات مرتبطی نیستند.به عبارت دیگر،این الگوریتم ها به طور نادرستی به این لینکه به عنوان LinkForm نگاه نموده و آنها را خارج می سازند.این مسئله یکی از مسائل باقیمانده جهت تشخیص چنین لینک های از LinkForm های واقعی می باشند.

روش های ما در پیدا کردن LinkForm ،ها ی کند مشکل دیگری را ایجاد می کند.تعدادی وبلاگ یاBBS وجود دارد که همان domain name،IPaddress، name server راتسهیم میکنند و همین لینک ها بین سایت ها به عنوان یک LinkForm توسط الگوریتم های ما در نظر گرفته می شود.اگر یک وبلاگ از تعدادی سایت لینک شده باشد،بر طبق نظر اولیه و اصلی الگوریتم HITS باید امتیاز نفوذ بالایی را بگیرد. هر چند اگر وبلاگ از تعدادی وبلاگ که همان name server را تسهیم می کنند لینک شد اما از تعداد دیگر لینک نشده باشند،پس همه این لینک ها بین این وبلاگ ها به عنوان یک LinkForm توسط TaN+BHITS و N در نظر گرفته میشود،بنابر این،مشکل ظاهر می شود که به وبلاگ امتیاز نفوذ بالایی توسط دو الگوریتم فوق داده می شودجهت توجه به این وبلاگ ها به عنوان یک نفوذ ، فردنیاز به روش دسته بندی لینک بین صفحاتی که همان name server را به داخل لینک های Spamوnon-Spam تسهیم میکنند دارد،بدست آوردن چنین روشی یکی از کارهای بعدی خواهد بود.

برای هر یک از چهار ده عنوان جدول یک ،هم الگوریتم ها از همان محموعه رئوس استفاده می کنند.جدول 2 تعداد رئوس مورد استفاده الگوریتم ها را برای چهارده عنوان نشان می دهد.به عبارت دیگر،هر الگوریتمی که از یک مجموعه که آن استفاده می کند آشکار متفاوت از مجموعه ای از کرانه ای است که توسط دیگر الگوریتم ها استفاده می شود،بخاطر اینکه هر الگوریتم از چندین لینک در روش خود صرفنظر می کند.الگوریتم های HITS ، BHITSوWBHITS از همان مجموعه کرانه مورد استفاده توسط این جهار الگوریتم در ستون "Edgech" در جدول 2 نشان داده شده است.به طور مشابه هر یک از سه جفت الگوریتم (D+HITS , TaD)،( TaI+BHIT, I)و(TaN+BHITS , N ) از همان مجموعه کرانه استفاده می کنند و لینکهای بین صفحاتی را خارج می سازند که به ترتیب همان domain name،IPaddress، name server ورا دارند.تعداد لبه های مورد استفاده این سه جفت الگوریتم به ترتیب در ستون های "edge aو edge b و edge n"نشان داده شده اند.

 

مقدار حافظه مورد استفاده هر یک از الگورتیم های پیشنهادی ما تقریباً برابر با الگوریتمHITS اصلی می باشد.بیشتر قسمت زمان کار (اجرا)الگورتم های بر مبنای HITS صرف جمع آوری داده ها ی صفحات در اینتر نت می شود.هر الگوریتم از داده های همان مجموعه صفحات استفاده می کند،و بنا بر این زمان کار الگوریتم های پیشنهادی ما تقریباً برابر با الگوریتم ها HITS اصلی می باشد.در آزمایشات ما،همه الگوریتم ده نفوذ اول را در چند ثانیه بر روی خروجی می آورند در حالیکه یکمرتبه داده ای مورد نیاز در اینترنت جمع آوری می شود.الگوریتم ها برای موضوع 8 از حدود 10MBحافظه استفاده می کنند که بزرگتر هر عنوان دیگری است. همه الگوریتم ها در برنامه c++ پیاده سازی.الگوریتم امتیاز دهی TaN+BHITS می تواند دخ نفوذ اول را با کیفیت خوب بر روی وب های امروزی پیدا کند و می توان آن را به محض تقاضا با یک ؟pc اجرا نمود.الگوریتم به طور خاص ده نفوذ اول را با بهترین کیفیت برابر بیشتر عناوین داده شده پیدا می کنند.

توضیحات نتیجه گیری

ما چندین متغیر اصلاح شده از الگوریتم HITS را با پیشنهاد دادن الگوریتم Trust-Score و سه روش پیدا کردن LinkForm معرفی نمودیم.یکی از الگوریتم های مان ، TaN+BHITS ،ده نفوذ اول را خیلی بهتر از بقیه الگوریتم ها پیدا نمود ده نفوذ پیدا شده توسط این الگوریتم شامل تعدادی صفحه است که آن ها را نمی توان توسط HITS پیدا نمود.بنابر این ما موفق به اصلاح یک الگوریتم بر مبنای HITS شدیم که می توان ده نفوذ اول را با کیفیت نسبتاً خوب بر روی وب های امروزی پیدا کند.الگوریتم های ما تقریباً همان مقدار حافظه و زمان کار(اجرا) را می برند که الگوریتم اصلی می برد پس، الگوریتم های مما می تواند ب ه محض تقاضا با یک pc که حافظه اصلی کوچکی هم دارد اجرا گردد.هدف از این مقاله بهبود الگوریتم های HITS است که تنها از همان اطلاعات لینکی استفاده می کنند که الگوریتم اصلی استفاده می کند.یکی از کارهای بعدی ما ترکیب نمودن الگوریتم های مان با چندین تکنیک است که از اطلاعات متنی مثل عنوان صفحه استفاده می کنند.

پیاده سازی:

الگوریتم مقاله مذکور داری دو ایده مشخص است:

1- امتیاز منفی دادن به دامین هایی که از آنها تعداد لینکهای زیادی به یک صفحه شده است. بردن تعداد آنها در مخرج کسر باعث بار منفی تعداد آنها می شود

2- امتیاز مثبت به صفحاتی دادن که امتیاز و اعتبار خود آنها بالا است. بردن آنها در صورت کسر باعث با مثبت تعداد آنها می شود

الگوریتم را به صورت دستی پیاده نموده و نتایج را مورد بررسی قرار دادم ( در مقاله هم ذکر شده است که بررسی ها و ارزیابی ها به صورت دستی انجام شده است)

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

مراحل انجام کار :

1- 14 عنوان ذکر شده را در Google جستجو نموده و 100 صفحه ابتدایی را به عنوان مبنای پیاده سازی در نظر گرفتم ( در مقاله 200 صفحه را آزمایش نموده اند )

2- علاوه بر 14 عنوان بجز Kabuki ( کشتی ژاپنی) بقیه موارد معنی آنها در فارسی نیز مورد جستجو قرار گرفت

3- تعداد صفحات مرتبط با جستجو به صورت درصد محاسبه شد

4- در Source تمامی صفحات URL های موجود ( لینکهای صفحات) در صفحه Excel نوشته شد

5- در صورتی که لینکی به یکی از 100 صفحه مورد ارزیابی اشاره می کرد مشخص شد

6- با استفاده از این اطلاعات و تعداد لینکهایی که به یک صفحه شده است الگوریتم HITS محاسبه شد ( برای محاسبه الگوریتم HITS را چهار مرتبه تکرار کردم در مقاله مشخص نیست چند بار تکرار شده است )

7- تعداد صفحاتی که هم دامین و هم IP بودند محاسبه شد و در الگوریتم HITS تأثیر داده شد (به عنوان بار منفی در مخرج کسر آورده شد)

8- در صورتی که تعداد صفحات با اعتبار بالا و جزو یک LINK form به صفحه لینک داشتند در صورت کسر به عنوان بار مثبت پیاده سازی شد

9- بدلیل اینکه نتوانستم الگوریتم BHITS را محاسبه نمایم ( روش محاسبه گفته نشده ) آنرا با HITS یکی گرفتم. در مقاله هم اختلاف ناچیزی بین ایندو وجود دارد

10-ده نفوذ اول برای محاسبه های فوق اندازی گیری شد

نتایج به صورت زیر مشخص شد

algorithm

google

 

 

 

HITS

BHITS

D+BHITS

I+BHITS

TaD+BHITS

TaI+BHITS

Canoe

69%

3

2

2

8

8

6

7

قایقرانی

94%

10

10

10

9

9

9

9

Monochrom-photograph

67%

5

5

5

5

5

5

5

عکس تک رنگ

18%

7

7

7

3

3

4

5

Movie

95%

10

10

10

10

10

10

10

فیلم

91%

10

9

9

8

8

10

10

Olympic

87%

10

10

10

10

10

10

10

المپیک

75%

9

9

9

10

10

10

10

Railway

76%

7

7

7

7

7

7

7

راه آهن

77%

7

7

7

5

5

6

6

Rock-Climbing

93%

8

8

8

8

8

8

8

صخره نوردی

92%

10

10

10

9

9

9

9

Formula one

55%

10

9

9

5

5

6

6

فرمولا یک

41%

7

7

7

4

4

5

5

Cheese

62%

8

8

8

8

8

8

8

پنیر

62%

8

9

9

6

6

7

7

Tennis

67%

10

9

9

9

9

9

9

تنیس

78%

10

9

9

9

9

10

10

Wine

44%

10

10

10

10

10

10

10

شراب

67%

10

8

8

5

5

8

7

Drinking

69%

8

8

8

8

8

8

8

آشامیدن

97%

10

10

10

10

10

10

10

میانگین

72%

8.5

8.23

8.23

7.55

7.55

7.95

8.00

 

بررسی نتایج:

الف )در نگاه اول اختلاف زیادی بین نتایج ریز خودم و مقاله مشاهده کردم یعنی در بعضی موارد الگوریتم فوق نه تنها باعث بهبود نشده بود بلکه باعث کاهش کارایی جستجو نیز شده بود . ولی اختلاف در مجموع ارزیابی ناچیز بود. شاید بدلیل استفاده از لغات فارسی این اختلاف ایجاد شد (؟) به هر حال بعضی موارد را دوباره محاسبه نمودم عدد تغییر نکرد

ب )نکات جالب توجه :

1- در تمامی موارد الگوریتم HITS با نتایج گوگل برابری می کند. شاید به این دلیل است که ما در نمونه آماری اولیه از نتایج گوگل استفاده کردیم

2- بین استفاده از IP و دامین اختلافی مشاهده نشد ( البته در مواردی IP بهتر عمل کرد ولی جزءی بود)

ج )در مواردی که ما از اسامی با حیطه معنی کوچک مانند قایقرانی استفاده کردیم با اسامی که دارای معانی متفاوتی بودند اختلافی مشاهده نشد در صورتی که به علت استفاده در دامین های یکسان انتظار می رفت اسامی که دارای معانی بیشتری بودند در الگوریتم فوق بهتر عمل کند

د) دلیل کاهش ده نفوذ اول در تمامی موارد خارج شدن صفحات هم دامین از جستجوی اولین گوگل است ( مثلا در جستجوی اولیه گوگل در مورد راه آهن سایت رجا دارای سه صفحه هم هاست و دامنه مرتبط بود ولی در الگوریتم فوق این صفحات به عنوان اسپم شناخته شد و رتبه منفی پیدا کرد)

ه ) ما نمونه آماری خود را مانند مقاله از گوگل گرفتیم که این خود شامل معایب زیر است :

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

2- در مقاله ده نفوذ اول برای الگوریتمها محاسبه شد ولی برای خود گوگل محاسبه نشد. ما این عمل را انجام دادیم و مشاهده کردیم که گوگل در تمامی موارد بهتر عمل می کند ولی در مقاله فقط در حد ایده با یکدیگر مقایسه شده است

و) تمامی وبلاگها و صفحات مشابه به عنوان اسپم شناخته شده و از ده نفوذ اول کم شد

ز )صفحاتی مانند ویکیپیدیا که عموما جزو ده صفحه نخست نتایج گوگل هستند در صورت که تعداد آنها بیشتر شود در الگوریتم فوق به عنوان اسپم شناخته شده و دارای بار منفی می شود ( چون تعداد لینکها به این صفحات ناچیز است- ماپیدا نکردیم- هر چه تعداد آنها بالاتر برود نه تنها امتیازی نگرفتند بلکه باعث بار منفی بیشتری نیز می شود)

ح)در مواردی که نتیجه دامنه آماری اولیه بالا بود ( تعداد صفحات مرتبط پیدا شده توسط گوگل در زمان ابتدایی بالا بود) الگوریتم های فوق تأثیری بر روی نتایج نداشتند این امر را می توان اینگونه بیان کرد که به علت تعدا کم صفحه های نامرتبط احتمال اینکه صفحه های نا مرتبط به رده های بالا بیایند خیلی کم است

ط) در بین جستجو اسامی فارسی و انگلیسی در بعضی موارد تفاوت بسیار زیادی مشاهده می شود که این امر بیانگر این موضوع است که نحوه انتخاب موارد جستجو برای آزمایش و زبان مورد جستجو نقش مهمی در کارآیی الگوریتم فوق دارد مثلا ممکن است در جستجوی اجناسی که در بازار بسیار خرید و فروش می شوند خوب عمل نماید ولی در مورد اسامی خاص نه تنها به خوبی جواب ندهد بلکه سایتهای مرجع را نیز به عنوان اسپم شناخته و حذف نماید

 

نتیجه : این الگوریتم از نظر عملی کاربردی ندارد و تنها به عنوان یک ایده قابل توجه کارایی دارد

 

با تشکر و احترام فراوان

ابراهیم عباسپور

تاریخ خبر : 1392/10/21      آدرس خبر : http://majame.tehran.irhttp://majame.tehran.ir/default.aspx?tabid=341&ArticleId=1413
تعداد مشاهده : 3142
چاپprint

  نظرات

هیچ نظری ثبت نشده است.

نام شما
پست الکترونیک
وب سایت
عنوان
نظر
تصویر امنیتی CAPTCHA
کد را وارد کنید