یادگیری سریع داده کاوی با مطالعه 10 الگوریتم برتر به همراه شبه کد

الگوريتم C4.5 دامنه دسته xadبندي را علاوه بر صفات قياسي در انواع صفات عددي نيز توسعه ميxadدهد. برای جلوگیری از اتصالات بیشتر ، درخت تصمیم اولیه باید هرسشود. برای هرس کردن درخت C4.5 پس از ساختن درخت، یک بار به عقب برمیxadگردیم و انشعابxadهای بیxadفایده را با جایگزین کردن گره برگ بجای آنها، حذف میxadکنیم. الگوریتم هرس بر اساس یک برآورد بدبینانه از میزان خطا(E) در ارتباط با مجموعهxadای با N نمونه است که در آن E متعلق به یک کلاس پرتکرار نمیxadباشد، است. C4.5 بجای E/N ، که E واقعه در N آزمایش مشاهده شدهxadاند، حد بالایی از احتمال دو جملهxadای را با استفاده از اطمینان که توسط کاربر مشخص شده است و مقدار پیشxadفرض آن 0.25 است، تعیین می xadکند.

هرس کردن از برگ به ریشه انجام میxadشود. خطای برآورد شده در یک برگ با N نمونه و E خطا، همانگونه که در بالا مشاهده شد، N برابر نسبت خطای بدبینانه است. C4.5 برای یک زیر درخت، خطاهای تخمینی شاخه xadها را جمع میxadکند و آنرا با خطای تخمینی مقایسه میxadکند در صورتی زیر درخت با یک برگ جایگزین میxadشود که: اگر دومی بیشتر از اولی نباشد آنگاه زیر درخت هرس میxadشود. بطور مشابه C4.5 خطاهای تخمینی را بررسی میxadکند و در صورتی یک زیر درخت با یکی از شاخهxadهایش جایگزین میxadشود که آن به نفع درخت باشد. الگوریتم هرس کردن در یک گذر از درخت کامل میxadشود.

3 الگوریتم k میانگین

1-3 مقدمه

این الگوریتم یک متد ساده تکرار شونده است، برای خوشهxad بندی مجموعهxadای از دادهxadهای در اختیار در تعداد مشخصی خوشه (k) که کابر تعیین میxadکند. این الگوریتم توسط محققین مختلف و به صورتxadهای مختلفی ارائه شده است . در این الگوریتم دادهxadها در گروهxadهای مجزا خوشهxadبندی میxadشوند. این الگوریتم تعداد مشخصی خوشه را تعریف میxadکند و به طور مکرر دادهxadها را درون این خوشهxadها قرار میxadدهد و مرکز خوشه را هر بار تعیین میxadکند تا جایی که دیگر امکان بهبود بیشتری وجود نداشته باشد. به جای پیشxadبینی کردن مقدار خروجی، الگوریتم kمیانگین از پروسهxadای استفاده میxadکند که به دنبال یافتن الگوهایی در بین داده xadهای ورودی است.

در اجرای الگوریتم kمیانگین اولین کار مشخص کردن k یا همان تعداد خوشه xadها در الگوریتم k میانگین است. براي اين الگوريتم شکلهاي مختلفي بيان شده است. ولي همة آنها داراي روالي تکراري هستند که براي تعدادي ثابت از خوشهها سعي در تخمين موارد زير دارند:

• بدست آوردن نقاطي به عنوان مراکز خوشهها; اين نقاط در واقع همان ميانگين نقاط متعلق به هر خوشه هستند.
• نسبت دادن هر نمونه داده به يک خوشه; که آن داده کمترين فاصله تا مرکز آن خوشه را دارا باشد.

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

در ماشین بردار پشتیبان یک داده به صورت یک بردار P بعدی (یا یک لیست از P عدد) دیده میxadشود و ما میxadخواهیم بدانیم که آیا میxadتوان چنین نقاطی را با یک ابرصفحه P-1 بعدی جدا کرد. این عمل، جداسازی خطی نامیده میxadشود. ابرصفحهxad های بسیاری وجود دارند که میxadتوانند داده xadها را جدا کنند. سوال اینجاست که چه ابرصفحه ای را انتخاب کنیم.

مفهوم آموزشی که اشیا بتوانند به عنوان نقاط در یک فضای با ابعاد بالا دستهxadبندی شوند و پیدا کردن خطی که آنها را جدا کند منحصر به فرد نیست. آنچه ماشین بردار پشتیبان را از سایر جداکنندهxadها متمایز میxadکند چگونگی انتخاب ابرصفحه است. در ماشین بردار پشتیبان، ماکزیمم کردن حاشیه بین دو کلاس مدنظر است. بنابراین ابرصفحهxadای را انتخاب میxadکند که فاصلهxadی آن از نزدیکترین دادهxadها در هر دو طرف جداکنندهxadی خطی، ماکزیمم باشد. اگر چنین ابرصفحهxadای وجود داشته باشد، به عنوان ابرصفحه ماکزیمم حاشیه شناخته میxadشود. شکل (4-1) این مفهوم را به صورت بصری نشان میxadدهد. برای ساخت ماکزیمم حاشیه، دو صفحه مرزی موازی با صفحه جداکننده رسم کرده آن دو را آنقدر از هم دور میxadکنیم که به دادهxadها برخورد کنند. صفحه جداکنندهxadای که بیشترین فاصله را از صفحات مرزی داشته باشد، بهترین جداکننده خواهد بود.تابع تصمیمxad گیری برای جداکردن دادهxadها با یک زیرمجموعهxadای از مثالxadهای آموزشی، که بردارهای پشتیبان (نزدیکxadترین دادهxadهای آموزشی به ابرصفحه جداکننده) نامیده میxadشوند، تعیین میxadشود. در واقع ابرصفحه بهینه در ماشین بردار پشتیبان که در شکل (4-2) نشان داده شده است، جداکنندهxadای بین بردارهای پشتیبان است.

در صورت استفاده مناسب از ماشین بردار پشتیبان این الگوریتم قدرت تعمیم خوبی خواهد داشت. علی رغم ابعاد زیاد، از سرریز شدن پرهیز میxadکند. همچنین به دلیل استفاده از بردارهای پشتیبان به جای کل دادهxadها، این الگوریتم فشرده سازی اطلاعات را نیز انجام میxadدهد. هدف این دسته از الگوریتمxadها تشخیص و متمایز کردن الگوهای پیچیده در دادهxadها (از طریق کلاسترینگ، دسته بندی، رنکینگ، پاکسازی و غیره) و پيدا کردن تمام صفحات در فضاي p بعدي است که نمونههاي مثبت و منفي را با بيشترين حاشيه از هم جدا میxadكنند.

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

یک ابرصفحه، یک زیرفضای k بعدی در یک فضای n بعدی تعریف میxadکند که k<n. مثلا خط یک ابرصفحه یک بعدی در یک فضا با هر تعداد بعد است. در سه بعد، صفحه یک ابرصفحه دوبعدی است و به همین ترتیب برای فضاهای با ابعاد بالاتر ابرصفحه تعریف میxadشود. بطور هندسی مرز با کمترین فاصله بین نزدیکترین داده و نقطهxadای روی ابرصفحه مطابقت میxadکند. همین ترتیب هندسی به ما اجازه میxadدهد تا کشف کنیم که چگونه مرزها را بیشینه کنیم.

4-4 ماشین بردار پشتیبان غیر خطی

مجموعه دادهxadهایی که به طور خطی قابل جداسازی هستند با مقداری نویز خوب کار میxadکنند. اما اگر مجموعه داده ما خیلی پیچیده بود چه؟

این مجموعه داده را نمیxadتوان به سادگی با یک خط دستهxadبندی کرد. در این موارد از نگاشت به فضایی با ابعاد بالاتر (شکل (4-6)) استفاده میxadشود.

ایدهxadی اصلی نگاشت به فضای بالاتر( فضای ویژگی) انتقال x به فضای بالاتر برای راحتی جداسازی است:

• فضای ورودی: فضای x
• فضای ویژگی : فضای j(xi)

چرا انتقال می دهیم؟

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

برای انتقال ابتدا تابع j(x)را برای نگاشت به فضای دیگر، پیدا میxadکنیم. سپس فرمول ماشین بردار پشتیبانی به صورت زیر تغییر میxadیابد:

فضای نگاشت اصلی همواره میxadتواند به فضای ویژگی با ابعاد بالاتر دیگری که در آن، مجموعه آموزشی قابل جداسازی باشد، نگاشت یابد. انجام محاسبات در فضای ویژگی چون ابعاد بیشتری دارد میxadتواند پرهزینه باشد. در حالت کلی این فضا بیxadنهایت است. برای غلبه بر این مشکل از حقه کرنل^[1] استفاده میxadشود.

4-5 تابع کرنل

تابع کرنل، یک جداکننده خطی متکی بر ضرب داخلی بردارهاست که به صورت :

میxadباشد. اگر نقاط با استفاده از انتقال به فضای ویژگی (فضای با ابعاد بالاتر) انتقال یابند، ضرب داخلی آنها به صورت :

تبدیل خواهد شد.

یک تابع کرنل تابعی است که مطابق یک ضرب داخلی در فضای ویژگی است. بنابراین ما از محاسبهxadی (x)φخودxadداری کرده و به جای آن از تابع کرنل استفاده میxadکنیم.

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

4-6 ماشین بردار پشتیبان چند کلاسی^[1]

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

4-7 کاربردهای ماشین بردار پشتیبان

• در اقتصاد
• پیشxadبینی رکود
• تشخیص صورت
• دستهxadبندی و کاهش ویژگی برای تشخیص سریع صورت
• انتخاب ژن در دستهxadبندی سرطان
• شناسایی گفتار
• شناسایی الگو
• ...

4-8 خلاصه

1. ماتریس الگو را آماده میxadکنیم.
2. تابع کرنلی را برای استفاده انتخاب میxadکنیم.
3. پارامتر تابع کرنل و مقدار C را انتخاب می کنیم.
4. برای محاسبهxadی مقادیرa_i ، الگوریتم آمورشی را با استفاده از حل کنندهxadهای برنامه نویسی درجه دو اجرا میxadکنیم.
5. دادهxadهای جدید با استفاده از مقادیر a_i و بردارهای پشتیبان میxadتوانند دستهxadبندی شوند.

4-9 مزایا و معایب ماشین بردار پشتیبان

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

5 الگوریتم اپریوری

5-1 مقدمه

بسیاری از الگوریتمxadهای الگویاب، از قبیل الگوریتمxadهایی که برای ساختن درخت تصمیمxadگیری، استنتاج قوانین دستهxadبندی و جمعxadبندی دادهxadها که زیاد در استخراج اطلاعات استفاده میxadشوند، در جامعه تحقیق یادگیری ماشین گسترش یافتهxadاند. الگوی مکرر و استخراج قوانین مرتبط، یکی از معدود استثنائات این شیوه است ]2[. این الگوریتم در سال 1996 توسط چنگ ابداع شد و یکی از مهمترین یافتهxadها در تاریخ استخراج قوانین وابستگی میxadباشد. یکی از محبوبxadترین دیدگاهxadهای استخراج اطلاعات، یافتن یک الگوی مکرر از یک مجموعه داده اجرایی و استخراج قوانین مرتبط است. یافتن الگوی مکرر (الگویی با فراوانی برابر یا بیشتر از حداقل پشتیبانی) ساده نیست و این بدلیل پیچیدگی محاسبات حاصل از انفجارهای ترکیبی است. وقتی یکبار الگوی مکرر بدست آید، ایجاد قوانین مرتبط با اطمینانی برابر یا بیشتر از حداقل اطمینان آسان خواهد بود.

5-2 الگوریتم

فرض کنید ابتدا باید تمام مجموعهxadهای تک عضوی مکرر را پیدا کنید، سپس براساس آن مجموعهxadهای دو عضوی مکرر را پیدا کنید و ... .

بنابراین در هر مرحله باید کل فضا جستجو شود اما این الگوریتم از یک خصوصیت به نام خصوصیت اپریوری استفاده میxadکند، به این صورت xadکه اگر یک مجموعهxadای از عناصر مکرر باشد، تمام زیر مجموعهxadهای غیر تهی آن نیز مکرر خواهند بود. مثلا" اگر مجموعه A نامبرده شده در زیر مکرر باشد، آنxadگاه مجموعهxadهای زیر نیز مکرر هستند.

A= {Milk, Bread, Cigarettes}, {Milk, Bread}, {Milk, Cigarettes}, {Bread, Cigarettes} {Milk},{Bread},{Cigarettes}

این خصوصیت را اینxadگونه نیز میxadتوان توصیف کرد که اگر مجموعهxadی I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعهxadی جدید از تعداد تکرار مجموعهxadی قبلی بیشتر نخواهد بود. پس اگر اولی مکرر نباشد دومی هم مکرر نخواهد بود. اما این الگوریتم چگونه از این خصوصیت استفاده میxadکند؟ در اینجا عملکرد آنxadرا شرح میxadدهیم:

میxadدانیم که از L_K-1یعنی یک زیرمجموعه K-1 عضوی برای بدست آوردن L_K، یعنی مجموعهxadهای K عضوی استفاده میxadشود. این کار در دو مرحله صورت میxadگیرد، ابتدا باید مجموعهxadای از اعضا پیدا شود، که با L_K-1 برای به دست آوردن L_K ترکیب شود. این مجموعه از عناصر را C_K نامیده و مرحله به دست آوردن آن را مرحله پیوست میxadنامیم. مرحله بعد اضافه کردن این عناصر به مجموعهxadهای قبلی است که آن را مرحله هرس میxadنامیم ]1[.

• ·مرحله پیوست

ابتدا باید مطمئن شویم که عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. L_K-1 ها را با l_i و اعضای آنها را به صورت l_i[j] نشان میxadدهیم. اگر K-2 عنصر اول آنها با یکدیگر برابر باشند، آنگاه دو مجموعهxadی L_K-1 با یکدیگر قابل پیوست هستند، یعنی داشته باشیم:

)l₁[1] = l₂[1] ) ^ (l₁[2] = l₂[2]) ^ … (l₁[k-2] = l₂[k-2]) ^ (l₁[k-1] < l₂[k-1])

توجه کنید که دو عنصر آخر به ترتیب مرتب شدهxadاند و از وجود عناصر تکراری جلوگیری میxadکنند. اجتماع دو مجموعهxadی قابل پیوست، ترکیب را به وجود میxadآورد (البته مرتب از نظر الفبایی).

با این روش ترکیب، مجموعه حاصل K عضو خواهد داشت، که البته عنصر آخر از نظر ترتیبی از مجموعه دوم خواهد بود.

6 الگوریتم بیشینهxadسازی امیدواری

6-1 مقدمه

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

ترکیب توابع تعمیم یافتهxadی متناهی، یک روش انعطافxadپذیر ریاضی را برای مدلسازی و دستهxadبندی دادهxadهایی که به عنوان پدیده تصادفی مشاهده شدهxadاند، ارائه میxadدهد. در اینجا به استفادهxadی بیشینه سازی امیدواریجهت پردازش ترکیب توابع تعمیم یافتهxadی متناهی از طریق روش حداکثر احتمال متمرکز میxadشود ]2 .[

6-2 توصیف الگوریتم بیشینه سازی امیدواری

مجموعه دادهxadهای مشاهده شده را به صورت که مستقل از هم هستند و مجموعه دادهxadهای نامرئی را به صورت و کل دادهxadها را به صورت در نظر میxadگیریم. الگوریتم بیشینه سازی امیدواری با فرض بیشینه نزدیکی (ML) میxadگردد که را بیشینه کند. این امید ریاضی روی توزیع احتمال X که توسط پارامترهای معلوم اندازه گیری میxadشود. الگوریتم بیشینه سازی امیدواری برای تخمین توزیع احتمالی روی X به جای پارامترهای واقعی از فرض فعلی استفاده میxadکند. تابع را به گونهxadای تعریف میxadکنیم که را به صورت تابعی از تعریف کند. با فرض و اینکه دادهxadهای Y از کل دادهxadهای X مشاهده شدهxadاند، داریم :

(6-1)

الگوریتم بیشینه سازی امیدواری یک الگوریتم تکراری است که هر تکرار آن دو مرحله دارد: مرحله تخمین[1] و مرحله بیشینه سازی[2][1] .

مرحله 1 : مرحله تخمین: با استفاده از مقدار فرض فعلی و دادهxadهای مشاهده شده Y مقدار را محاسبه میxadکند تا توزیع احتمالی روی X را تخمین زند .

مرحله 2 : مرحله بیشینه سازی: فرض را با فرض ای جایگزین میxadکند که تابع Q را بیشینه کند.

(6-2)

در چارچوب دادهxadهای ناقص الگوریتم بیشینه سازی امیدواری، نشان دهنده بردار دادهxadهای مشاهده شده و z نشان دهنده بردار دادهxadهای ناقص است، بردارxadهای کامل به این صورت بیان میxadشود که در آن توان T ، نشان دهنده بردار ترانهاده است:

(6-3)

الگوریتم بیشینه سازی امیدواری به مشکل حل عملیات اطلاعات ناقص معادله ممکن نزدیک میxadشود. این کار را غیر مستقیم و با پیشرفت تکراری، با توجه به عملیات ممکن "داده های کامل" یا عملیات انجام میxadدهد. از آنجائیکه این کار به وضوح به دادهxadهای غیر قابل مشاهده z بستگی دارد، مرحله تخمین طوری صورت میxadگیرد که در آن لگاریتم توسط عملیات Q جایگزین میxadشود و از اندازه اخیر استفاده میxadکند. بطور ویژه در (k+1) امین تکرار الگوریتم بیشینه سازی امیدواری، مرحله تخمین به این صورت عمل می کند:

(6-4)

که در آن امید ریاضی را با استفاد از بردار واحد نشان میxadدهد. مرحله بیشینه سازی، تخمین Ψ را بوسیلهxadی ارزش ^(k+1)Ψ بروز میxadکند. مراحل تخمین و بیشینه سازی بطور متوالی جابجا میxadشوند تا تغییرات ارزشxadهای الگوریتم محتمل کمتر از برخی آستانهxadهای مشخص شده باشند.

همانطور که اشاره شد، الگوریتم بیشینه سازی امیدواری، برای افزایش تکرار هر یک از بیشینه سازیxadهای امید ریاضی، ثابت و به صورت زیر است:

(6-5)

میxadتوان نشان داد که مراحل تخمین و بیشینه سازی شکلxadهای سادهxadای دارند در حالیکه عملیات چگالی محتمل دادهxadهای کامل از یک خانواده نمایی است. معمولا در عمل، راهxadحل مرحله بیشینه سازی به شکل محدود وجود دارد. در آن نمونهxadها که این راهxadحل وجود ندارد ممکن است نتوان برای یافتن ارزش Ψ که در کل، عملیات را حداکثر میxadکند تلاش کرد. برای چنین شرایطی ممکن است یک الگوریتم بیشینه سازی امیدواری کلی[3] انتخاب شود که در آن مرحلهxadی تخمین نیازمند این باشد که ^(k+1) Ψ طوری انتخاب شود که ^(k+1) Ψ عملیات Q، را بر ارزش موجود در ^(k)Ψ =Ψ افزایش دهد یعنی

برخی ازموانع الگوریتم بیشینه سازی امیدواری عبارتند از:

• این الگوریتم خود بخود اندازه ماتریس واریانس اندازهxadهای واحد را تولید نمیxadکند. با این حال این مشکل را میxadتوان به سادگی از روش درست مربوط به الگوریتم بیشینه سازی امیدواری از بین برد.
• گاهی اوقات همگرایی بسیار آهسته صورت میxadگیرد.
• در برخی مسائل، مراحل تخمین و بیشینه سازی میxadتوانند از هم جدا شوند.

تاکنون نمونهxadهای زیادی از الگوریتم بیشینه سازی امیدواری دیدهxadایم، که هرکدام شامل محاسبة مقادیر موردانتظار متغیرهای پنهان برای هر مثال و سپس محاسبة دوباره مقدار پارامترها بوده است. برای انجام این کار از مقادیر موردانتظاری استفاده کردیم که گویی مشاهده شده بودند.

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

رتبهxadبندی صفحه یک رتبهxadدهی استاتیک به صفحات وب است که مقدار مربوط به هر صفحه به صورت آفلاین محاسبه میxadشود و همچنین این الگوریتم مستقل از پرسxadوxadجو است. محاسبهxadی رتبهxadبندی یک صفحه بر اساس ایدهxadی محاسبه اعتبار[1] یک عامل در شبکه اجتماعی[2] است.

پیوند ورودی[3] صفحه i، پیوندهایی است که از صفحات دیگر به صفحه i اشاره میxadکند. معمولا پیوندهایی که از صفحات درون سایت صفحه i میxadرسند، محاسبه نمیxadشود.

پیوند خروجی[4] صفحه i، پیوندهایی است که از صفحه i به سایر صفحات اشاره میxadکند. معمولا پیوندهای به صفحات درون سایت صفحه i محاسبه نمیxadشود.

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

1. وجود یک پیوند از یک صفحه به صفحه دیگر بطور ضمنی نشانxadدهنده نفوذ^[5] صفحه مقصد است. بنابراین پیوند ورودی بیشتر برای صفحه i نشانxadدهنده نفوذ بیشتر این صفحه است.

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

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

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

(7-1)

1/Oi if (i,j) E

همچنین A را به عنوان ماتریس همسایگی گراف وب در نظر میxadگیریم که:

0 otherwise

A_ij=

حال سیستم n معادله را میxadتوان به صورت زیر نوشت:

(7-2)