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

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

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

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

1-3   مقدمه

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 4-5             تابع کرنل

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

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

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

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

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

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

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

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

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

4-8   خلاصه

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

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

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

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

5-1  مقدمه

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

5-2  الگوریتم

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

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

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

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

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

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

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

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

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

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

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

6-1    مقدمه

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

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

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

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

(6-1)

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

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

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

                                     (6-2)

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

(6-3)                           

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

(6-4)

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

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

(6-5)         

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

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

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

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

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

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

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

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

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

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

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

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

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

                        (7-1)                                                                                                                 

1/Oi if (i,j) E

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

0   otherwise

A_ij=

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

(7-2)