بخشی از مقاله

*** اين فايل شامل تعدادي فرمول مي باشد و در سايت قابل نمايش نيست ***

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

کلمات کلیدی: وب کاوی، Page Rank، Weighted Page Content Rank WeightedPageRank، HITS


1. مقدمه
بعد از ایجاد بانکهای اطلاعاتی و ازدیاد اطلاعات موجود در دنیای وب برای دسترسی سریعتر به اطلاعات احتایج به جستجو و موتورهای جستجوگر امری اجتناب ناپذیر شد. جستجو در اطلاعات بسیار سریعتر شد ولی مشکل این بود که تمامی اطلاعات می بایست روی یک کامپیوتر ذخیره شده باشد و با چنین حجم بالایی از اطلاعات این کار عملا غیر ممکن بود. در این هنگام بود که جستجوهای غیر متمرکز و موتورهای جستجو به وجود آمدند و باعث تحول شگرفی در دنیا شدند. امروزه موتورهای جستجو به یکی از ضروری ترین برنامه ها تبدیل شده اند به طوری که حتی تصور یافتن اطلاعات بدون آنها برای بسیاری غیر ممکن است. از طرف دیگر این موتورها دارای چنان اهمیتی هستند که شرکتهای گوناگون تلاش می کنند که خود را در بالای رده بندیهای اینگونه سایتها قرار دهند تا بتوانند موقعیت مالی بهتری داشته باشند.
وب گسترده جهانی یک منبع غنی از داده ها میباشد که گسترش اندازه و پیچیدگی آن همواره ادامه دارد. از این رو بازیابی موثر و کارآمد صفحات وب یک چالش بزرگ میباشد. بنابراین روش ها و تکنیک هایی برای دستیابی کارا به داده، اشتراک داده، استخراج اطلاعات از داده و استفاده از این اطلاعات، مورد نیاز می باشد. مطابق با گزارش سال 2008 گوگل بیش از یک میلیارد صفحه در وب موجود است و این تعداد روز به روز افزایش مییابد. با توجه به حجم وسیع اطلاعات در وب، مدیریت آن با ابزارهای سنتی تقریبا غیر ممکن بوده و موجب مشکلات زیادی برای کاربران جهت جستجو، استخراج و محاسبه اطلاعات مناسب می شود. لذا نیاز به تکنیکهایی جهت رفع مشکلات موجود است. برخی از این مشکلات عبارتند از: -1وب بسیار بزرگ است -2صفحات وب نیمه ساختاریافته هستند.
-3اطلاعات وب در مفهوم متفاوت هستند
-4یافتن اطلاعات مرتبط
-5بدست آوردن دانش از اطلاعات استخراج شده ادامه مقاله بصورت زیر سازماندهی شده است. در بخش 2 وب کاوی معرفی شده است. در بخش 3 نواحی وب کاوی (مانند (WCM,WSM,WUM توضیح داده شده است. دربخش 4 الگوریتمهای تحلیل لینک مانند PR،WPR ، WPCR و HITS مورد بررسی و مقایسه قرار گرفته اند. در بخش 5 الگوریتمهای تحلیل لینک با استفاده از یک مثال، مقایسه شدهاند و سرانجام در بخش 6 نتایج بدست آمده بیان شده است.

2. وب کاوی
وب کاوی یک تکنیک داده کاوی است که بصورت خودکار اطلاعات را از اسناد وب، کشف و استخراج می نماید. وب کاوی شامل چهار مرحله اصلی می باشد که عبارتند از:
الف) کشف منبع:
این مرحله شامل عملیات بازیابی اسناد وب خواسته شده است. در این مرحله دادهها از منابع موجود در وب استخراج می شوند.

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

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

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

3. دسته بندیهای وبکاوی
روش های وب کاوی بر اساس آن که چه نوع داده ای را بعنوان ورودی مورد کاوش قرار می دهند، به سه دسته تقسیم می شوند:

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

3.2 ساختارکاوی وب
وب گسترده جهانی را می توان به صورت گرافی در نظر گرفت که گره های آن اسناد و یال های آن پیوندهای بین اسناد وب است.هدف ساختارکاوی وب ایجاد خلاصه ساختاریافتهای درباره صفحات وب است. این پروسه ساختار اتصال ابرلینک در سطح اسناد درونی را کشف میکند

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

4. الگوریتمهای تحلیل لینک
وب را میتوان بصورت یک گراف برچسب دار در نظر گرفت که گرههای آن اسناد یا صفحات و لبههای آن ابرلینکهای بین صفحات است. ساختار گراف جهت دار بعنوان گراف وب شناخته میشود. در این پژوهش سه الگوریتم مهم تحلیل لینک PageRank، Weighted PageRank و HITS را بررسی و مقایسه می کنیم.

4.1 الگوریتم Page Rank
الگوریتم Page Rank اولین بار در سال 1998 توسط Larry Pageو Sergey Brin در دانشگاه استنفرد ارائه شده است، این الگوریتم یک روش مستقل از پرس و جو می باشد. پیج رنک مهم ترین مهمترین و مهمترین عامل در اعتبار یک سایت می باشد. امروزه در دنیای اقتصادی وب سایت هایی که پیج رنک بالا دارند با مبالغ هنگ مفتی معامله می شوند و همچنین برای موتور های جستجو عامل مهم برای دادن پاسخ به درخواست کاربر ها همین پیج رنک است. این روش یک بار به هر سند وب امتیاز اختصاص داده و از این امتیاز، با در نظر گرفتن معیاری با توجه به پرس و جوی کاربر جهت رتبه بندی اسناد استفاده می کند. این الگوریتم رتبه هر صفحه را با اختصاص وزن به پیوندی که به آن صفحه داده شده است به دست می آورد که مقدار این وزن به کیفیت صفحهای که پیوند در آن قرار گرفته، بستگی دارد. در این صورت پیوندهای صفحات مهمتر وزن بیشتری می گیرند. جهت مشخص کردن کیفیت صفحه های رجوع کننده، درPage Rank از رتبه آن صفحه که به صورت بازگشتی تعیین و مقدار اولیه آن اختیاری است، استفاده می شود. اگر n سند در دسترس باشد، مقدار اولیه رتبه سند را می توان برابر 1/n در نظر گرفت.

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

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