این تحقیق جهت ارتقاء رتبه شغلی آموزگاران عزیز ارائه شده و دارای کلیه فرمت ها از قبیل چکیده ، مقدمه ، فهرست ، نتیجه گیری و منابع می باشد. فایل به صورت وورد بوده و کاملا قابل ویرایش می باشد.
رتبه بندی صفحات یا پیج رنک (PageRank)
مقاله ای مفید و کامل
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه:23
چکیده:
در این سری مقالات سعی بر اینست که بطور کلی و تخصصی راجع به الگوریتم پی آر گوگل و اهمیت آن از لحاظ بهینه سازی و بازاریابی موتورهای جستجو صحبت کنیم و تکنیک های لازم جهت بهبود سایتها را در اختیار خوانندگان قرار دهیم.
پی آر یک متغیر عددی است که نشان می دهد یک سایت در دنیای اینترنت از چه اهمیتی برخوردار است. گوگل این اهمیت را از طریق لینک ها تشخیص می دهد و وقتی یک سایت به سایت دیگری لینک می شود، از لحاظ گوگل بدین معنی است که آن سایت یک رای به سایت دیگر داده است. هرگاه رای های زیادی از طریق سایتهای دیگر به یک سایت می رسد این بدین معنی است که آن سایت از اهمیت بالاتری برخوردار است. همچنین سایت رای دهنده اهمیت رایش به اهمیت خودش بستگی دارد بدین معنی که هرچه اهمیت بالاتری داشته باشد ، رای های آن نیز پر اهمیت تر است. گوگل اهمیت صفحات وب را از روی همین رای ها و اهمیت آنها حساب می کند.
پی آر روشی است که گوگل به واسطه آن اهمیت صفحات وب را تا یین میکند. این امر از این لحاظ برای گوگل مهم است زیرا که بواسطه این اهمیتو رای ، گوگل رتبه بندی صفحات وب را تایین میکند و صفحه ای که رتبه پی آر بالاتری دارد از صفحه همتای خود رتبه بالاتری خواهد داشت و این به خاطر پی آر است. در حالی که این تنها فاکتور رتبه بندی نیست ولی جزو فاکتورهای مهم موتور جستجوی گوگل است و اخیرا تمام موتورهای جستجو به نوعی از این فاکتور پراکندگی برای رتبه بندی های خود استفاده می کنند.
در اینجا باید خاطر نشان کنم که همه لینکهایی که به یک سایت بر میگردد، توسط گوگل به حساب نمی آید و فقط تعداد محدودی از آنها را به شمار می آورد. در حال حاضر گوگل اکثر لینکهایی را که از مزرعه لینکهای شناخته شده می آید فیلتر می کند. مزرعه لینکها سایتهایی هستند که فقط لینک در خود نگه داری می کنند و خاصیت مثبتی در اینترنت ندارند و چون این عمل ماهیت اهمیت سایتها را برهم می زند ، گوگل آنها را فیلتر می کند. بعضی از این لینکها حتی می تواند منجر به جریمه شدن سایت شما در گوگل شود. گوگل می داند که صاحبان سایت نمی توانند لینکهایی را که به آنها می شود کنترل کنند ولی می توانند اینکه به چه سایتی لینک شوند را کنترل کنند ، پس خیلی دقت کنید به چه سایتهایی لینک می دهید.
رتبه بندی صفحات یا پیج رنک قسمت دوم
پیج رنک چگونه محاسبه می شود ؟
برای محاسبه پی آر یک صفحه ، تمامی لینکهایی که به آن صفحه بر میگردند مورد محاسبه قرار می گیرند. و این هم لینکهایی که از داخل سایت به آن متصل میشوند را در بر می گیرد و هم لینکهای خارجی.
PR(A) = (1-d) + d(PR(t1)/C(t1) + ... + PR(tn)/C(tn))
این تساوی است که طی آن پی آر یک صفحه محاسبه می شود. این الگوریتم پی آر است که هنگام راه اندازی ابتدایی پی آر انتشار یافت. و احتمال اینکه گوگل نیز از مشابه همین فرمول استفاده کند وجود دارد ولی آنها راجع به الگوریتم هایشان صحبتی نمی کنند و ما اطلاع دقیقی از آن نداریم ولی این مسئله مهمی نیست زیرا که این الگوریتم به اندازه کافی خوب می باشد.
در این تساوی 't1 - tn' صفحاتی هستند که به صفحه A لینک شده اند و ‘C’ تعداد لینکهای بیرونی که یک صفحه دارد و در نهایت ‘d’ فاکتور اشباع شدن است که معمولا آنرا 0.85 در نظر می گیریم.
اگر بخواهیم بطور ساده آنرا بررسی کنیم می توان به صورت زیر آنرا بررسی کرد ؛
پی آر = 0.15 + 0.85 * ( سهمی از پی آر هر سایتی که به آن متصل می شود )
"سهم" ؛ پی آر صفحه لینک شونده تقسیم بر تعداد لینکهای خروجی بروی آن صفحه !
جالب است نه ؟ در واقع هر صفحه با لینکی که به صفحات دیگر می دهد ، به آنها رای می دهد و مقدار این پی آر کمی کمتر از مقدار پی آر خود آن صفحه است (مقدار پی آر خود صفحه * 0.85 ). این مقدارتقریبا بطور مساوی بین تمامی صفحاتی که به آنها لینک شده است ، تقسیم می شود.
از این فرمول اینگونه بدست می آید که یک لینک از یک سایت با پی آر 4 و 5 لینک خروجی با ارزش تر از گرفتن لینک از یک سایت با پی آر 8 و 100 لینک خروجی است. پی آر صفحه ای که از آن لینک می گیرید مهم است ولی به همان اندازه تعداد لینکهای خروجی آن صفحه نیز مهم است. هر چقدر تعداد لینکها در صفحه لینک دهنده بیشتر باشد ، پی آر کمتری به صفحات لینک شده تعلق می گیرد.
اگر تفاوت بین پی آر های 1 تا 10 ثابت و مساوی بود ، فرض بالا قوت بیشتری می داشت اما بسیاری بر این عقیده هستند که مقادیر بین پی آر های 1 تا 10 بصورت لگاریتمی تغییر می کنند و دلایل قانع کننده ای برای باور کردن این تصاعد لگاریتمی وجود دارد. هیچ کس خارج از گوگل نمی داند که گوگل از چه الگوریتمی برای پی آر استفاده می کند ولی احتمال استفاده گوگل از مقیاس لگاریتمی و یا مشابه آن زیاد است. با توجه به این مطلب ، بدست می آید که پی آر بسیار بیشتری در مقایسه با پی آر لازم برای پی آری که بدست آمده لازم است تا از یک پی آر به پی آر بعدی برسیم. نتیجه این می شود که فرض قبلی می شود ، پس یک لینک از سایتی با پی آر 8 که لینکهای خروجی زیادی دارد باارزش تر از صفحه ای با پی آر 4 و لینکهای خروجی کمتر خواهد بود.
هر کدام از این الگوریتمها را که گوگل استفاده کند ، ما می توانیم از یک چیز مطمئن باشیم. لینک هایی که از سایتهای دیگر می آیند باعث افزایش پی آر سایت ما می شوند. فقط در خاط داشته باشید که باید از قرار دادن لینکهای خود در مزرعه های لینکها و سایتهایی که لینک جمع می کنند و خاصیت دیگری ندارند خودداری کنید.
در نظر داشته باشید که اگر صفحه ای لینک به صفحه دیگری بدهد ، پی آر خودش کم نمی شود و چیزی از دست نمی دهد بلکه فقط رای می دهد. پس دادن رای ، جابجا شدن پی آر نیست ، بلکه بطور ساده فقط دادن یک رای است که قوت آن به مقدار پی آر آن صفحه بستگی دارد. این مسئله مانند مجمع سهام داران است. وقتی سهام داران جمع می شوند و هر کس به ازای درصد سهمش رای می دهد ، از تعداد سهامشان کم نمی شود و این قضیه کاملا مشابه است. با این حال ، صفحات گاهی تحت شرایطی بطور غیر مستقیم ، پی آر از دست می دهند که جلوتر راجع به آن صحبت می کنیم.
خوب اکنون به نحوه انجام شدن محاسبات می پردازیم.
برای محاسبه یک صفحه ، ابتدا پی آر آن ، اگر پی آری داشته باشد ، کاملا کنار گذاشته می شود و یک محاسبه کاملا جدید که فقط بر پایه لینکها و رای هایی که پس از آخرین محاسبه پی آر به آن داده شده و ممکن است تغییر کرده باشد انجام می شود. ولی آنچه در این ابتدا مشخص نیست اینست که این کار انجام شدنی نیست اگر این محاسبات یکبار انجام شوند. توضیح بیشتر آنکه فرض کنید ما دو صفحه آ و ب داشته باشیم که به یکدیگر نیز لینک شده باشند و هیچ لینک دیگری در این دو وجود نداشته باشد. آنچه اتفاق می افتد ، از قرار زیر است ؛
قدم اول ؛ محاسبه پی آر صفحه اول از مقدار لینکهای ورودی به آن
صفحه آ اکنون یک مقدار پی آر دارد. برای این محاسبه از لینک ورودی از صفحه ب استفاده شد ، اما صفحه ب یک لینک ورودی از صفحه آ دارد و پی آر جدید آن هنوز محاسبه نشده پس آنچه به عنوان پی آر برای صفحه آ بدست آماده بر اساس پی آر غیر دقیق صفحه ب است که در کل دقیق نمی باشد.
قدم دوم ؛ محاسبه پی آر صفحه ب با توجه به مقدار لینکهای ورودی
صفحه ب اکنون پی آر جدیدی دارد اما نمی تواند دقیق باشد زیرا که محاسباتی که به کار گرفته شده ، با استفاده از پی آر غیر دقیق صفحه آ است پس کل این دو محاسبه غیر دقیق است.
از آنجایی که ایندو محاسبه به یکدیگر وابسطه هستند ، ما نمی توانیم هیچکدام از این پی آر ها را بطور دقیق محاسبه کنیم تا زمانی که پی آر دقیق یکی را جلوتر از دیگری داشته باشیم. اما حالا که دو مقدار پی آر جدید خالص هرکدام را داریم ، آیا می توان دوباره این محاسبات را انجام داد تا جوب دقیق گرفت ؟ خیر
ما میتوانیم این محاسبات را مجدد انجام دهیم و نتایج دقیق تر نیز می شوند ولی ما همیشه جوابهای غیر دقیق را برای محاسبه های بعدی استفاده می کنیم پس نتایج ما همیشه غیر دقیق می باشند.
این مشکل با تکرار کردن بسیار محاسبات حل می شود. هر بار نتایج کمی دقیقتر از بارهای قبل می باشد اما دقت محض در این محاسبات وجود ندارد. 40 تا 50 بار محاسبه کافی است زیرا از آن به بعد نتایج تغییر چشم گیری نمی کنند. اینست آنچه گوگل در هر بار بروزرسانی انجام می دهد و دلیل طولانی بودن بروزرسانی های پی آر در گوگل می باشد که معمولا 70 روزمی باشد.
قانون پیج رنک توسط برین و پیج در گوگل
پیج رنک ( برین و پیج ، سال 1998 )
توضیح مفصل و باز کردن این الگوریتم را از دیدگاه بهینه سازی و مارکتینگ در اینجا مقتنم نمی دانم. ولی لازم است که در انجا راجع به پیج رنک صحبت کنیم چرا که نشان می دهد همیشه لازم نیست رتبه بندی بر اساس وزن لغات بکار رفته در متن باشد ، بلکه می تواند بر اساس وزن و ارزش لینکها و پیوندها نیز باشذ. اولین باری این الگوریتم ظاهر شد و دنیای بهینه سازس صفحات وب را عوض کرد ، با بهره گرفتن از طبیعت اجتماعی و متعحد وب و ساختار متصل لینکها توانست به دنیای وب بصورت یک وب واحد نگاه کرده و موقعیت هر صفحه تنها را ارزش گذاری کند. رتبه بندی صفحات که طی این قانون PR نام گرفته است از لحاظ عددی مقداریست بین صفر و یک که گوگل آنرا در نرم افزار خود ععدی بین یک تا ده نشان میدهد ، زیرا که تمامی لینکها در یک ماتریس جای داده می شود. حال آنچه مسلم است اینکه دنیای وب دیگر محیطی اجتماعی نیست و لینک دادن سایتی به سایت دیگر با هزاران حساب و کتاب انجام میشود و این به واسطه همین PR است که خود نابودی خود را در آینده رقم زده است.
قانون بردفرد
قانون بردفرد که در سال 1934پای به عرصه جستجو گزارد در مورد شواهدی از جستجو در پروندهای کتابخانه ای صحبت میکند که میتوان توسط آنها تعداد نتایج و پروندههای مرتبط را تخمین زد.
برای روشن شدن بیشتر این نحوه یافتن و مرتب کردن پروندها ، مثالی میاوریم تا مطلب باز شود. برای مثال اگر شما 5 نتیجه دارید که برای شما از درجه اهمیت برخوردار است و در این 5 وب سایت 12 پرونده برای شما مهم است و مورد نظر شما در مطلب خاصی است. حال اگر شما بخواهید 12 پرونده یا صفحه دیگر را که مطلبی مرتبط داشته باشند بدست آورید ، شما باید 10 سایت را مطالعه و مورد بررسی قرار دهید.
پس نتیجه گیری میشود که در قانون بردفرد ما با یک ترکیب مضاعف کننده 5/10روبرو هستیم. هر بار که شما بخواهید 12 صفحه مرتبط دیگر داشته باشید باید 10 سایت دیگر وجود داشته باشد. پس این بصورت تساعدی بالا رفته و در نهایت به ارقام 5 ، 10، 20 ، ... میرسد.
البته در جستجو داخل نتایج موتور های جستجو ، کمتر پیش میآید کسی انقدر عمیق جستجو کند.
و...
بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل 2 بیان شده است. مقوله ای که مورد بررسی قرار دادیم بهینه سازی تقاضا تحت رتبه بندی می باشد که برای بدست آوردن Kجواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتیبانی کارای تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمین سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.
موضوع مهم در این زمینه تعیین اندازه مورد نیاز ورودی ها در N رابطه برای پاسخگویی به تقاضای تحت رتبه بندی می باشد تا بدین وسیله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازی اطلاعات در مقیاس بالا، انتخاب جوابهای رتبه بندی K جواب بهتر ازچندین منبع خیلی حیاتی می باشد و در کمینه کردن هزینه انتقال نقش اساسی دارد. زیرا هر چه اندازه رابطه ها کوچکتر باشد، هزینه کمتری برای انتقال صرف می گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل 2 مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.
1- تشریح مسئله
هنگامیکه یک تقاضا تحت رتبه بندی داریم که هدف بدست آوردن K جواب بهترمی باشد، در این حالت به تمامی رکورد های جدول نیاز نداریم، بر اساس مقدار K تعدادی از رکوردها در رابطه ها که امتیاز کمی دارند در نتیجه نهایی نقشی ندارند و بهتر است آنها هرس شوند و برای محاسبات و انتقال اطلاعات زمانی را برای این رکوردها تلف نکنیم. ابتدا تعریفی از یک تقاضای تحت رتبه بندی را در زیر بیان می کنیم.
در تقاضای تحت رتبه بندی، تقاضا بر روی M صفت A1، A2، ... ، AN و N رابطه به صورت R1، R2، ... ، RN تعریف می شود که هر Ai(i=1:M) متعلق به یک رابطه Rj (j=1:N) می باشد. هر یک از صفتها نسبت به نوع شان دارای دامنه خاصی می باشند. R1، R2، ... ، RN در M سیستم به صورت توزیع شده قرار دارند به صورتیکه هر رابطه به طور کامل بر روی یک سیستم قرار دارد. به عبارت دیگر عمل قسمت بندی بر روی رابطه ها را در پایگاه توزیع شده بین سیستمها را در این تحقیق نداریم.
فهرست مطالب و
فهرست شکلهاط
فصل اول: مقدمه 1
1: تشریح مسئله 3
2: چالشها 5
فصل دوم: مفاهیم اولیه و کار های پیشین6
1: پردازش تقاضا7
1-1: تجزیه تقاضا7
1-2:بهینه سازی تقاضا 7
1-3: اجرای تقاضا 8
2: روشهای بهینه سازی تقاضا 9
3: تقاضایتحت رتبه بندی 11
4: کارهای پیشین12
4-1: یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر 12
4-1-1: مساله مورد بررسی12
4-1-2: معماری کلی روش14
4-2: بهینه سازی تقاضای تحت رتبه بندی15
عنوان صفحه
4-2-1: رتبه بندی تجمعی 16
4-2-2: عملگرهای تقاضای اتصال رتبه بندی 16
4-2-3: بهینه سازی تقاضا بر پایه هزینه 17
4-2-4: طرح شمارش با استفاده از برنامه نویسی پویا17
4-2-5: توسعه فضای شمارشی 18
4-2-6: طرح های هرس 19
4-3: بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای22
4-3-1: اجرای تطبیقی تقاضای رتبه‌بندی 23
4-3-2: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی 23
4-3-3: تغییر طرح بر اساس بهینه‌ساز:25
4-3-4: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره25
4-4: بهینه سازی تقاضای محدود شده بهK26
4-4-1: استنتاج فضای وضعیت ایندکس28
4-4-2: وضعیتهدف 29
4-4-3: الگوریتم *OPT 32
فصل سوم: روش پیشنهادی34
1: بیان برخی از نقصهای کارهای پیشین 35
2: تجزیه کننده تقاضا 36
3: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز37
3-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها38
3-1-1: ساختار کلی الگوریتم 40
3-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه48
4: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده57
4-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها61
4-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه72
فصل چهارم: پیاده سازی و آزمایشها 74
عنوان صفحه
1: پیاده سازی های انجام شده75
2: پایگاه داده های نمونه77
3: پارامترهای مورد نظر برای مقایسه روشها 79
4: آزمایشهای انجام شده80
فصل پنجم: نتایج و پیشنهادها91
1: نتایج92
2: پیشنهادها 92
مراجع 94
به همراه فایل powerpoint
شامل 120 صفحه فایل word