۱۹۵

 

Categories (Number of groups)

 

 

 

۸۰،۵۱۳

 

Nodes

 

 

 

۵،۸۹۹،۸۸۲

 

Links

 

 

 

۱.۸ ×۱۰−۳

 

Network density

 

 

 

۵،۷۰۶

 

Maximum degree

 

 

 

۱۴۶

 

Average degree

 

 

 

۰.۶۱

 

Clustering coefficient

 

 

 

۴-۳-معیارهای ارزیابی
اگر در حالت کلی گراف G(V, E)، را در نظر بگیریم.vمجموعه ای از گره ها و E مجموعه ای از یال ها میباشد .عموما ما نمیخاهیم بدانیم که آیا لینک ها گم شده اند یا لینک های آینده چیست زیرا این عمل به صورت قطعی غیر ممکن است و فقط ما صحت نتایج را میتوانیم بررسی کنیم. بنابراین برای آزمایش صحت الگوریتم ، لینک های مشاهده شده یعنی E به صورت تصادفی به دو بخش تقسیم میشود: مجموعه آموزشی [۷۵] و مجموعه آزمایشی[۷۶] .مجموعه آزمایشی برای تست انجام میشود و هیچ اطلاعاتی در این مجموعه اجازه ندارد برای پیش بینی استفاده شود در صورتی که در مجموعه داده های آموزشی اطلاعات مشخص میباشد.در این صورت اجتماع داده های آزمایشی و آموزشی مجموع داده ها میباشد.
پایان نامه - مقاله - پروژه
مزیت این متد اعتبارسنجی تصادفی در این است که تعداد تکرارها بر روی داده های آموزشی تاثیری ندارد ولی در این روش بعضی از لینک ها ممکن است ظاهر نشده و بعضی از لینک های دیگر در زمان دیگری ظاهر شوند و ممکن است در این روش بعضی از اشکالات آماری رخ دهد و این معایب با بهره گرفتن از روش K-fold cross-validation که لینک های مشاهده شده به k زیرمجموعه به صورت تصادفی بخش بندی میشوند برطرف میشود و به تعداد k مرتبه تکرار میشود.با بهره گرفتن از این متد همه ی لینک ها برای اعتبار سنجی استفاده شده و هر لینک برای پیش بینی واقعی مورد استفاده قرار میگیرد.در این حالت هر چه مقدار k بیشتر باشد لینک های بیشتری بررسی شده و در نتیجه محاسبات نیز افزایش می یابد،مناسب ترین ۱۰-fold cross-validation میباشد که از نظر زمان و کارایی به نتیجه خوبی میرسد.
ماتریس در همریختگی[۷۷] که نشان دهنده مقدارهای درست و غلط حاصل از پیش بینی ها میباشد در جدول ۴-۲نشان داده شده است.
جدول ۴-۲-ماتریس در همریختگی:شامل معیارهایی برای محاسبه نتایج پیش بینی ها
مطابق جدول ۴-۲ مقدار ≡Sensitivity true positive rate≡Recallبه صورت زیر است:
مقدار Accuracy نیز به صورت زیر است:
مقدار Positive predictive value یا precision به صورت فرمول زیر است:
دومعیار استاندارد دیگر برای ارزیابی صحت الگوریتم های پیش بینی لینک وجود دارند: [۷۸]AUCمعادل ناحیه زیر منحنی [۷۹]ROCاست. این معیار به این صورت محاسبه می شود که از n مقایسه مستقل، اگر n’ بار تعداد پیوندهای اشتباه امتیاز بالاتری داشته باشند و n'’ بار پیوندهای اشتباه و پیوندهایی که وجود ندارند دارای امتیاز یکسانی باشند، مقدار AUC به صورت زیر تعریف می شود:
AUC امتیاز همه ی لینک های مشاهده نشده را میدهد.مقدارAUC به عنوان احتمال انتحاب تصادفی لینک های گم شده یا لینک های داده های آزمایشی تفسیر میشودکه امتیاز بالاتری در برابر انتخاب تصادفی لینک هایی که موجود نیستند دارند.اگر همه ی امتیازها به صورت مناسب تخصیص یابد مقدار AUC باید حدودا ۰.۵ باشد.اگر این مقدار از ۰.۵ بیشتر شود نشان میدهد که الگوریتم بهتر عمل میکند.
معیار بعدی Precision میباشد که امتیاز لینک های مشاهده نشده رامیدهد.و در شکل ۴-۱ چگونگی محاسبه مقدارPrecision و AUC نشان داده شده است.
شکل ۴-۲-مثالی در مورد محاسبه مقدارPrecision و AUC
در این شکل نشان میدهد که چگونه مقدارPrecision و AUC محاسبه میشود.در این گراف ۵ گره وجود دارد ،۷لینک مشاهده شده و ۳ لینک مشاهده نشده(((۱، ۲)، (۱، ۴) و (۳، ۴)) داریم.برای آزمایش کردن صحت الگوریتم نیاز به انتخاب لینک های مشاهده شده به طور نمونه لینکهای ۳) ، (۱ و (۴,۵)که با بهره گرفتن از خط تیره نشان داده شده میباشیم.بنابراین الگوریتم فقط از اطلاعات گراف آموزشی (با خط های پررنگ در شکل نشان داده شده)استفاده میکند. برای محاسبه AUCنیاز به مقایسه امتیاز لینک های مشاهده شده و مشاهده نشده میباشیم.
از معیار [۸۰]MAP برای اثبات کارایی روش ها و معیارها استفاده کرده ایم، تا در بررسی کارایی الگوریتم مورد نظر، تاکید بیشتری بر روی ترتیب دوستان پیشنهاد داده شده با این روش ها، داشته باشیم. معادله MAP به صورت زیر تعریف می شود:
که N تعداد کاربران در مجموعه داده آزمایشی و تعداد کاربران مرتبط با کاربر u وPrecisionu@K مقدار Precision در k امین موقعیت در لیست پیشنهادات برای u است.توجه کنید که MAP هردو مقدار precision و recall را در خود دارد و از نظر هندسی ناحیه زیر منحنی precision-recall است.[۴۸ , ۴۹]
۴-۴-شاخص های مورد استفاده در پیش بینی لینک
پیش بینی لینک از طریق تجزیه و تحلیل توپولوژیک با محاسبه معیارهای مختلف انجام میشود.یک معیار، یک مقدار محاسبه شده از یک گراف میباشد که به توصیف گراف در بعضی از راه ها میپردازد.برای مثال ، دو گره که درجه بیشتری دارند بیشترین شباهت را دارند(تعداد همسایگان) بیشتر شبیه شکل گرفتن یک لینک جدید از دو گره با پایین ترین درجه میباشد.بیشتر معیارهای تحلیل شبکه های اجتماعی پرکاربرد به شرح زیر میباشندو در شکل ۴-۳ نتایج حاصل از دسته بندی با بهره گرفتن از این سه شاخص آورده شده است.
جدول ۴-۳ شاخص های دسته بندی کننده

 

 

آدامیک /آدار

 

 

 

 

 

شاخص کاتز

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...