پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA وPSO)

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA  وPSO™)

چکیده

پیشگویی پیوند در شبکه های اجتماعی یکی از فعالیت های مهم در تحلیل شبکه های اجتماعی است. اهمیت پیشگویی پیونددر شبکه های اجتماعی به دلیل طبیعت دینامیک آن هاست. اعضا و پیوندهای ارتباطی بین آن ها در این شبکه ها مدام در حال افزایش است و این پیوندها ممکن است به دلایل گوناگون از دست برود؛ لذا با پیشگویی این پیوندها امکان گسترش وتکمیل این شبکه ها و بازیابی اطلاعات و موارد از دست رفته را می توان به دست آورد. برای کشف و پیشگویی این پیوندها نیاز به اطلاعاتی است که غالباً از ساختار گرافی شبکه استخراج می شوند و به عنوان معیارهایی برای پیشگویی مورد استفاده قرار می گیرند. در این مقاله پس از معرفی دو معیار جدید که کارایی مؤثری در پیشگویی و نیز ارائۀ پیشنهادات از خود نشان داده اند روش جدیدی ارائه شده است که با ترکیب چند دسدته بندی کننده و با بهره گیدری از روش ها ی تکاملی الگوریتم ژنتیک و الگوریتم رقابت استعماری( عمل پیشگویی پیوند را به انجام می رساند. برای اثبات کار از دو مجموعهEpinions و Facebook استفاده شده است. ما نشان داده ایم که روش پیشدنهاد ی می تواند کار ا یی و دقت پیشگویی را افزایش دهد.

روش مورد استفاده در پیشگویی پیوند

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

دسته بندی برای پیشگویی پیوند

هدف در پیشگویی پیوند، دسته بندی یال هایی که هنوز تشکیل نشده اند، به دو گروه مثبت و منفی است . یال ها ی مثبت یال هایی هستند که احتمال تشکیل آن ها در آینده وجود دارد و یال های منفی یال هایی هستند که براساس پیشگویی صورت گرفته، احتمال ایجاد آن ها وجود ندارد. در این مقاله برای دسته بندی یال ها به دو گروه مثبت و منفی، از ترکیب دسته بندی کننده ها استفاده شده است . برای تکمیل کار وافزایش کارایی و بالا بردن دقت پیشگویی از روش های تکاملی بهره گرفته شده است . دلیل استفاده از ترکیب دسته بندی کننده ها این است که هنگام طراحی یک سیستم یادگیر و ازجمله یک دسته بندی کننده ، انتخابها ی فراوانی وجود دارد. این تنوع انتخاب باعث می شود که نوعی ازواریانس در عملکرد سیستم وجود داشته باشد. درنتیجه اگر سیستم های مختلفی داشته و از نتایج آن ها استفاده شود ، این امکان وجود دارد که توزیع خطا حول هدف متمرکز شده و باافزایش نمونه گیری از این توزیع به نتیجه بهتری برسیم . درواقع به بیان دیگر باید گفت هیچ الگوریتمی وجود ندارد که برای تمامی مسایل و در تمامی زمانها بهترین دقیق ترین یادگیر را به وجود آورد. بنابراین اگر تعدادی یادگیر پایه داشته باشی ، می توان با ترکیب نتایج آن ها به دقت بالاتری رسید.در این کار، از ظرفیت ها ی روشهای تکاملی الگوریتم ژنتیک و الگوریتم رقابت استعماری برای انتخاب در ابعاد مختلف، ترکیب دسته بندی کننده ها استفاده کرده ایم . دلیل استفاده از روش های تکاملی این است که این روشها ، راه حل های مختلفی از یک مسئله را به صورت همزمان بررسی می کنند و خود را به راه حل های خاص یا معیارهای ویژه ای محدود نمی کنند. به همین دلیل می توانند در همۀ شرایط خود را با مسئله وفق دهند و براساس شرایط مسئله پارامترهای خود را تنظیم کرده، پاسخ بهینه را به دست آورند . البته آنچه مسلم است ترکیب دسته بندی کننده هاست که در واقع دسته بندی درچندین مرحله است زمان محاسباتی نسبتاً بالایی خواهد داشت و این نوع روش ها، در کاربردهای برخط از قبیل ارائه پیشنهاد دوست و پیشنهاد کالا چندان مفید فایده نخواهد بود. اما کاربردهای غیربرخط زیادی وجود دارند که دقت و کارایی در آن نسبت به زمان محاسباتی، اهمیتی بسیارتری دارد.ازجمله این کاربردها می توان تشخیص و شناسایی گروه ها ی مجرم و تروریسم را نام برد که اشتباه در تشخیص می تواندهزینه های جبران ناپذیری را بر جامعه تحمیل کند.

روش های تکاملی مورد استفاده در دسته بندی

در این کار از دو الگوریتم از الگوریتم های روشها ی تکاملی استفاده شده است : اولی که الگوریتم ژنتیک است برای انتخاب ویژگیها مورد استفاده قرار گرفته  و دومی که الگوریتم رقابت استعماری است ، برای وزن دهی نتایج دسته بندی در ترکیب دسته بندی ها به کار گرفته شده است .

 روش ترکیب دسته بندی کننده ها

فرایند انتخاب با انتخاب دسته بندی کننده ها به پایان نمی رسد ،بلکه باید پس از تعیین تعدادی دسته بندی کننده بهینه، تعداد ی از روش های ترکیب مورد بررسی قرار گرفته و روش دارای بهترین کارایی انتخاب شود. برای این مقاله، روش های مختلفی مورد آزمون قرار گرفته اند و از میان روش های موجود ترکیب،روش رأی گیری حداکثری به عنوان مبنای کار قرار گرفته که البته با بهره گیری از روش های تکاملی، نتایج ترکیب را بهبود داده شده است .در این کار، الگوریتم رقابت استعماری به عنوان یکی  ازتکنیک های جست وجوی مبتنی بر جمعیت ، در ترکیب دسته بندی کننده ها، به روش رأی گیری حداکثری مورد استفادقرار گرفته است . این روش به این ترتیب انجام می شهود که یک ترکیب خطی از خروجی دسته بندی کننده ها را محاسبه کرده و سپس با رأی گیری، نتیجۀ نهایی را مشخص می کنیم . به این صورت که خروجی مربوط به کلاس i ام از طریق جمع خطی وزن دار خروجی مربو بط به کلاس i ام هر دسته بندی کننده j برای همۀ دسته بندی کننده ها به دست می آید:

که در آن N تعداد دسته بندی کننده ها و c تعداد کلاس هاست  zi j خروجی برای کلاس i از دسته بندی کنند j است. wi ضریب وزنی معادل همین خروجی است . ازآنجایی که ما در پیشگویی پیوند با دو کلاس صفر و یک مواجهیم ، دوyمحاسبه می شود. در این روش، خروجی هر دسته بندی کننده رادرz1 و متمم صفر یا یک آن را  در z2قرار می دهیم. کلاس برنده برای هریک از داده ها هریک از یالها کلاسی است که بیشترین مقدار y را دارد. بدین معنی که پس از محاسبۀ yi ها کلاس مورد نظربرابرمقداراندیس y بزر گتر است .

بنابراین مسلم است هه در این قسمت ، مسئله اصلی پیداکردن وزن های wi برای شرکت در ترکیب خطی است. هریک از c دسته بندی کننده که قرار است با یکدیگر ترکیب شوند دارای وزن هایی برای هریک m از کلاس خود هستند. بنابراین m×c وزن داریم که باید به طریقی مقادیر آن رابیابیم . روشی که در این مقاله برای محاسبۀ وزن های مورد نیازاستفاده شده، الگوریتم رقابت استعماری است . در الگوریتم رقابت استعماری که پیش از این شرح داده شد، هر عنصرجمعی یک کشور نامیده می شود که ابعادی به اندازۀ تعداد عناصر مسئله عناصری که به دنبال یافتن آنها هستیم دارد . بنابراین در این روش ، ابعاد هریک از کشورها برابر m×cاست که مقادیر هریک از آن ها بین 25 و 25 - در نظر گرفته شده است . تابع شایستگی در این روش منطق با کارایی نهایی ترکیب دسته بندی کننده ها تعریف، می شود که این کارایی در این قسمت نیز مقدار AUC خروجی است در سایر مقادیر این الگوریتم ، از مقادیر پیش فرض الگوریتم استفاده کرده ایم .پس از این  وزن های مربوط به هریک از دسته بندی کننده هابا استفاده از الگوریتم رقابت استعماری محاسبه شد، باجایگذاری این مقادیر در معادلۀ خطی می تهوان کلاس مربوط به هریک از نمونه های داده ورودی را تعیین کرد.

با توجه به روش پیشنهادی و توضیحات ارائه شده درمقاله، مراحل کار را می توان به صورت زیر خلاصه کرد:

ابتدا با استفاده از گراف شبکه و داده ها ی موجود ویژگی های مربوط به هر یال را محاسبه می کنیم .چند دسته بندی کننده را که از نظر کیفیت قابل قبول هستند، در نظر می گیریم .با استفاده از الگور یتم ژنتیک برای هر دسته بندی کننده، ویژگیهایی کهبهتر ین پاسخ را تولید می کنند، تعیین می کنیم .با توجه به نتایج الگوریتم ژنتیک و کروموزوم ها ی به دست آمده، برای هر دسته بنهدی کننده ، ویژگی ها یی نامناسب را حذف کرده، دسته بندی ها انجام می دهیم.نتایج هریک از دسته بندی کننده ها و متمم آنها را به ازای داده های آموزشی به دست می آوریم .با استفاده از الگوریتم رقابت استعمار ی و دادهای به دست آمده از مرحلۀ قبل ، وزن ها ی مربوط رابه دست می آوریم .با توجه به وزن های به دست آمده و با استفاده از جمع وزن دار خطی و رأی گیری بین نتایج ، کلاسهای مربوط به داده های آزمایشی تعیین می شود.

نتایجی که با توجه به مراحل ذکرشده، بهرای دو مجموعه دادۀ واقعی مورد استفاده در این مقاله به دست آمد، در جداول زیر آورده شده است . جدول زیر نتایج مربوط به مجموعه داده FaceBook را در خود دارد.

درجدول زیر نتایج مربوط به دسته بندی داده ها ی مربوط به مجموعه دادۀ Epinionsنشان داده شده است:

نتیجه گیری

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

منایع

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها اعظم کی پور مرتضی براری  حسین شیرازی