<p>&nbsp;</p>

مقدار Positive predictive value یا precision به صورت فرمول زیر است:

مقدار 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 وPrecision_u@K مقدار Precision در k امین موقعیت در لیست پیشنهادات برای u است.توجه کنید که MAP هردو مقدار precision و recall را در خود دارد و از نظر هندسی ناحیه زیر منحنی precision-recall است.[۴۸ , ۴۹]
۴-۴-شاخص های مورد استفاده در پیش بینی لینک
پیش بینی لینک از طریق تجزیه و تحلیل توپولوژیک با محاسبه معیارهای مختلف انجام میشود.یک معیار، یک مقدار محاسبه شده از یک گراف میباشد که به توصیف گراف در بعضی از راهها میپردازد.برای مثال ، دو گره که درجه بیشتری دارند بیشترین شباهت را دارند(تعداد همسایگان) بیشتر شبیه شکل گرفتن یک لینک جدید از دو گره با پایین ترین درجه میباشد.بیشتر معیارهای تحلیل شبکه های اجتماعی پرکاربرد به شرح زیر میباشندو در شکل ۴-۳ نتایج حاصل از دسته بندی با استفاده از این سه شاخص آورده شده است.
جدول ۴-۳ شاخص های دسته بندی کننده

شکل ۴-۳ منحنی ROCبرای مقایسه سه شاخص همسایگان مشترک,کاتز و آدامیک آدار
۴-۵-پیش بینی لینک با استفاده از شبکه بیزین
شبکه های بیزین تکنولوژی ایده آلی را به منظور ترکیب منابع اجتماعی فراهم میسازد شبکه های بیزین در زمینه استدلال احتمالی به طور گسترده مورد استفاده قرار می گیرند شبکه های بیزین به درخت متصل بر روی احتمالات استدلال شده تبدیل می شوند.
اخیرا شبکه های بیزین به)) تجزیه زیرگراف اصلی ماکزیمم درخت متصل((تبدیل می شوند و بیشتر از درخت های متصل کاربرد دارند .
شبکه بیزین یک مدل گرافیکی برای نمایش احتمالات ما بین متغیرهای مورد نظر می باشد از طرفی شبکه های بیزین روشی برای نمایش توزیع احتمالی پیوسته بزرگ به صورت نمایی و روش فشرده می باشند که اجازه محاسبات احتمالی به طور موثر را می دهند . آنها از ساختار مدل گرافیکی برای ضوابط مستقل ما بین متغیر های تصادفی استفاده می کنند . شبکه های بیزین اغلب برای شرایط مدل احتمالی استفاده می شوند و به استدلالهای تحت شرایط نامشخص)احتمالی ، عدم قطعیت ( کمک می کنند.
این شبکه شامل بخش کیفی )مدل ساختاری ( است که نمایش بصری از فعل و انفعالات در میان متغیرها و بخش کمی) مجموعه ای از مشخصات احتمال محلی(را فراهم می کند ، که مجاز به استنتاج احتمالات و اندازه گیری عددی است که متغیرها یا مجموعه ای از متغیرها را تحت تاثیر قرار می دهد .بخش کیفی به صورت توزیع احتمالی پیوسته که منحصر به فرد می باشد بر روی کلیه متغیرها تعریف می شود[۵] به عبارت دیگر شبکه بیزین یک گراف جهت دار غیر حلقوی است که شامل موارد زیر است :
نودها ) دوایر کوچک(: برای نمایش متغیرهای تصادفی ، کمانها)پیکانهای نوک تیز ( برای نمایش روابط احتمالی ما بین متغیرها
برای هر نود توزیع احتمال محلی وجود دارد که به نود وابسته است و از وضعیت والدین مستقل می باشد.
هر گره یک ماتریس احتمالی شرطی دارد که برای ذخیره کردن احتمالات شرطی میباشد و در طول زمان انباشته میشود.
اساس این روش بر این اصل استوار است که برای هر کمیتی یک توزیع احتمال وجود دارد که با مشاهده یک داده جدید و استدلال در مورد توزیع احتمال آن می‌توان تصمیمات بهینه‌ای اتخاذ کرد.در معادله زیر تعریف دسته بندی بیزین تعریف شده است:
با ترکیب تئوری های احتمال در دسته بندی بیزین ساده^[۸۱] میتوان دسته بندی ها را بهبود داردهمانطور که در شکل ۵-۲نشان داده شده است که مدل های Naive Bayes به عنوان یک شبکه بیزین ساده عمل میکنند.
شکل ۴-۲ نمایی از یک مدل بیزی ساده که به عنوان یک شبکه بیزین عمل مینماید^[۸۲]
یادگیری بیزین به عنوان “استخراج"از شبکه و محاسبه متریک های احتمالی شرطی از داده های تاریخی تعریف میشود.داده ها ممکن است ناکامل باشد و ساختار شبکه بیزین نیز ناشناخته باشد.
برای تفکیک داده های آموزشی و آزمایشیبا استفاده از متد اعتبار سنجی(cross validation method) 10 درصد از رکوردها را به صورت تصادفی از داده ای آزمایشی استخراج میکنیم که به عنوان یکی ازمراحل پیش پردازش مجموعه مورد آزمایشی و آموزش از داده ها میباشددر هر مرحله از بین داده های موجود در شبکه تعداد ۲۰۰۰ گره را به طور تصادفی انتخاب میکنیم و در این انتخاب بیشترین درجه راس^[۸۳] ها تعداد ۵۰ میباشد. مانریس در همریختگی در شکل ۴-۳ نشان داده شده است.نتایج حاصل از پیش بینی لینک برای داده های شبکه اجتماعی مذکور با استفاده از شبکه بیزی ساده در جدول۴-۳ نشان داده شده است.و نمودار های حاصل در شکل نشان داده شده است.
جدول ۴-۳-Confusion matrix

دومعیار استاندارد دیگر برای ارزیابی صحت الگوریتم های پیش بینی لینک وجود دارند: ^[۷۸]AUCمعادل ناحیه زیر منحنی ^[۷۹]ROCاست. این معیار به این صورت محاسبه می شود که از n مقایسه مستقل، اگر n’ بار تعداد پیوندهای اشتباه امتیاز بالاتری داشته باشند و n'’ بار پیوندهای اشتباه و پیوندهایی که وجود ندارند دارای امتیاز یکسانی باشند، مقدار AUC به صورت زیر تعریف می شود:

AUC امتیاز همه ی لینک های مشاهده نشده را میدهد.مقدارAUC به عنوان احتمال انتحاب تصادفی لینک های گم شده یا لینک های داده های آزمایشی تفسیر میشودکه امتیاز بالاتری در برابر انتخاب تصادفی لینک هایی که موجود نیستند دارند.اگر همه ی امتیازها به صورت مناسب تخصیص یابد مقدار AUC باید حدودا ۰٫۵ باشد.اگر این مقدار از ۰٫۵ بیشتر شود نشان میدهد که الگوریتم بهتر عمل میکند.
معیار بعدی Precision میباشد که امتیاز لینک های مشاهده نشده رامیدهد.و در شکل ۴-۱ چگونگی محاسبه مقدارPrecision و AUC نشان داده شده است.
شکل ۴-۲-مثالی در مورد محاسبه مقدارPrecision و AUC
در این شکل نشان میدهد که چگونه مقدارPrecision و AUC محاسبه میشود.در این گراف ۵ گره وجود دارد ،۷لینک مشاهده شده و ۳ لینک مشاهده نشده(((۱، ۲)، (۱، ۴) و (۳، ۴)) داریم.برای آزمایش کردن صحت الگوریتم نیاز به انتخاب لینک های مشاهده شده به طور نمونه لینکهای ۳) ، (۱ و (۴,۵)که با بهره گرفتن از خط تیره نشان داده شده میباشیم.بنابراین الگوریتم فقط از اطلاعات گراف آموزشی (با خط های پررنگ در شکل نشان داده شده)استفاده میکند. برای محاسبه AUCنیاز به مقایسه امتیاز لینک های مشاهده شده و مشاهده نشده میباشیم.
از معیار ^[۸۰]MAP برای اثبات کارایی روش ها و معیارها استفاده کرده ایم، تا در بررسی کارایی الگوریتم مورد نظر، تاکید بیشتری بر روی ترتیب دوستان پیشنهاد داده شده با این روش ها، داشته باشیم. معادله MAP به صورت زیر تعریف می شود:
که N تعداد کاربران در مجموعه داده آزمایشی و تعداد کاربران مرتبط با کاربر u وPrecision_u@K مقدار Precision در k امین موقعیت در لیست پیشنهادات برای u است.توجه کنید که MAP هردو مقدار precision و recall را در خود دارد و از نظر هندسی ناحیه زیر منحنی precision-recall است.[۴۸ , ۴۹]
۴-۴-شاخص های مورد استفاده در پیش بینی لینک
پیش بینی لینک از طریق تجزیه و تحلیل توپولوژیک با محاسبه معیارهای مختلف انجام میشود.یک معیار، یک مقدار محاسبه شده از یک گراف میباشد که به توصیف گراف در بعضی از راه ها میپردازد.برای مثال ، دو گره که درجه بیشتری دارند بیشترین شباهت را دارند(تعداد همسایگان) بیشتر شبیه شکل گرفتن یک لینک جدید از دو گره با پایین ترین درجه میباشد.بیشتر معیارهای تحلیل شبکه های اجتماعی پرکاربرد به شرح زیر میباشندو در شکل ۴-۳ نتایج حاصل از دسته بندی با بهره گرفتن از این سه شاخص آورده شده است.
جدول ۴-۳ شاخص های دسته بندی کننده

شکل ۴-۳ منحنی ROCبرای مقایسه سه شاخص همسایگان مشترک,کاتز و آدامیک آدار
۴-۵-پیش بینی لینک با بهره گرفتن از شبکه بیزین
شبکه های بیزین تکنولوژی ایده آلی را به منظور ترکیب منابع اجتماعی فراهم میسازد شبکه های بیزین در زمینه استدلال احتمالی به طور گسترده مورد استفاده قرار می گیرند شبکه های بیزین به درخت متصل بر روی احتمالات استدلال شده تبدیل می شوند.
اخیرا شبکه های بیزین به)) تجزیه زیرگراف اصلی ماکزیمم درخت متصل((تبدیل می شوند و بیشتر از درخت های متصل کاربرد دارند .
شبکه بیزین یک مدل گرافیکی برای نمایش احتمالات ما بین متغیرهای مورد نظر می باشد از طرفی شبکه های بیزین روشی برای نمایش توزیع احتمالی پیوسته بزرگ به صورت نمایی و روش فشرده می باشند که اجازه محاسبات احتمالی به طور موثر را می دهند . آنها از ساختار مدل گرافیکی برای ضوابط مستقل ما بین متغیر های تصادفی استفاده می کنند . شبکه های بیزین اغلب برای شرایط مدل احتمالی استفاده می شوند و به استدلالهای تحت شرایط نامشخص)احتمالی ، عدم قطعیت ( کمک می کنند.
این شبکه شامل بخش کیفی )مدل ساختاری ( است که نمایش بصری از فعل و انفعالات در میان متغیرها و بخش کمی) مجموعه ای از مشخصات احتمال محلی(را فراهم می کند ، که مجاز به استنتاج احتمالات و اندازه گیری عددی است که متغیرها یا مجموعه ای از متغیرها را تحت تاثیر قرار می دهد .بخش کیفی به صورت توزیع احتمالی پیوسته که منحصر به فرد می باشد بر روی کلیه متغیرها تعریف می شود[۵] به عبارت دیگر شبکه بیزین یک گراف جهت دار غیر حلقوی است که شامل موارد زیر است :
نودها ) دوایر کوچک(: برای نمایش متغیرهای تصادفی ، کمانها)پیکانهای نوک تیز ( برای نمایش روابط احتمالی ما بین متغیرها
برای هر نود توزیع احتمال محلی وجود دارد که به نود وابسته است و از وضعیت والدین مستقل می باشد.
هر گره یک ماتریس احتمالی شرطی دارد که برای ذخیره کردن احتمالات شرطی میباشد و در طول زمان انباشته میشود.
اساس این روش بر این اصل استوار است که برای هر کمیتی یک توزیع احتمال وجود دارد که با مشاهده یک داده جدید و استدلال در مورد توزیع احتمال آن می‌توان تصمیمات بهینه‌ای اتخاذ کرد.در معادله زیر تعریف دسته بندی بیزین تعریف شده است:
با ترکیب تئوری های احتمال در دسته بندی بیزین ساده^[۸۱] میتوان دسته بندی ها را بهبود داردهمانطور که در شکل ۵-۲نشان داده شده است که مدل های Naive Bayes به عنوان یک شبکه بیزین ساده عمل میکنند.
شکل ۴-۲ نمایی از یک مدل بیزی ساده که به عنوان یک شبکه بیزین عمل مینماید^[۸۲]
یادگیری بیزین به عنوان “استخراج"از شبکه و محاسبه متریک های احتمالی شرطی از داده های تاریخی تعریف میشود.داده ها ممکن است ناکامل باشد و ساختار شبکه بیزین نیز ناشناخته باشد.
برای تفکیک داده های آموزشی و آزمایشیبا استفاده از متد اعتبار سنجی(cross validation method) 10 درصد از رکوردها را به صورت تصادفی از داده ای آزمایشی استخراج میکنیم که به عنوان یکی ازمراحل پیش پردازش مجموعه مورد آزمایشی و آموزش از داده ها میباشددر هر مرحله از بین داده های موجود در شبکه تعداد ۲۰۰۰ گره را به طور تصادفی انتخاب میکنیم و در این انتخاب بیشترین درجه راس^[۸۳] ها تعداد ۵۰ میباشد. مانریس در همریختگی در شکل ۴-۳ نشان داده شده است.نتایج حاصل از پیش بینی لینک برای داده های شبکه اجتماعی مذکور با بهره گرفتن از شبکه بیزی ساده در جدول۴-۳ نشان داده شده است.و نمودار های حاصل در شکل نشان داده شده است.
جدول ۴-۳-Confusion matrix