ارائه مدل ترکیبی با استفاده از الگوریتم ژنتیک جهت پیش بینی پیوندها در شبکه اجتماعی

ارائه مدل ترکیبی با استفاده از الگوریتم ژنتیک جهت پیش بینی پیوندها در شبکه اجتماعی

چکیده

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

روش پیشنهادی

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

استخراج ویژگی

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

مدل ترکیبی

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

مقاومتر خواهد شد.برای انجام دسته بندی و ترکیب دسته بندهای پایه از نرم فزار RapidMinerاستفاده می شود.

ارزیابی

به منظور تفکیک داده های آموزشی و آزمایشی از روش 10Fold Cross Validation استفاده شده است. دراین روش کل مجموعه دادهها به 10 قسمت مساوی تقسیم میشوند. از 3 قسمت به عنوان مجموعه داده های آموزشی استفاده میشود و بر اساس آن مدل ساخته میشود و با یک قسمت باقی مانده عملیات ارزیابی انجام می شود. فرآیندمزبور به تعداد 10 مرتبه تکرار خواهد شد، به گونه ای که از هرکدام از 10 قسمت تنها یکبار برای ارزیابی استفاده شده ودر هر مرتبه یک دقت برای مدل ساخته شده، محاسبه میشود. در این روش ارزیابی دقت نهایی دسته بند برابر با میانگین دقت محاسبه شده خواهد بود. بدیهی است که در این شیوه ارزیابی، دقت محاسبه شده برای دسته بند قابل اعتماد بوده و دانش حاصل شده جامع خواهد بود.

مجموعه داده ها

جهت ارزیابی روش پیشنهادی از مجموعه داده های دو شبکه ی اجتماعی واقعی Hi5 و Facebook استفاده شده تاکارایی روش پیشنهادی بررسی شود. مشخصات کامل این مجموعه داده در جدول زیر آمده است.

نتابج حاصل از هر یک دسته بندهای پایه با استفاده از کلیه معیارهای شباهت مطرح شده و به ازای هر یک از مجموعه دادهه ای Facebook و Hi5 در جدول زیر آمده است.

نتایج در جدول بالا بیانگر آن است که با ترکیب چند الگوریتم یادگیری و ایجاد یک مدل ترکیبی، یادگیری دسته جمعی فراهم خواهد شد و مقدار AUC دسته بند ترکیبی افزایش خواهد یافت. شکل های زیرمصداق این مطلب است.

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

همانگونه که جدول بالا نشان میدهد با اعمال الگوریتم ژنتیک، AUC حاصل از مدل ترکیبی افزایش یافته است بنابراین ترکیب نتایج سه دسته بند که هر یک به تنهایی نسبت به سایر دسته بندها نتایج بهتر و AUC بالاتری را نتیجه داده اند و بهبود نتیجه نهایی با در نظر گرفتن الگوریتم ژنتیک نشان دهنده کارایی مناسب روش ارائه شده در این تحقیق است.شکل زیر تعداد دفعات استفاده از ویژگیهای مطرح شده در مدل ترکیبی طی 12 بار اجرا را نشان میدهد. معیار دوستان مشترک و معیار سالتون و معیار مجموع وزن دو گره در گراف، 11 بار و معیار ضریب جاکارد و معیار HPI و معیارضریب همبستگی، 10 بار در مدل ترکیبی استفاده شده که این نشان از کارایی خوب این ویژگیها نسبت به سایر ویژگیها در پیش بینی است.

نتیجه گیری

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