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

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

چکیده:

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

ماشین بردار پشتیبان در پیش بینی لینک

الگوریتم SVM اولیه در 1963 توسط Vladimir Vapnik ابداع شد و در سال 1995 توسط Vapnik و Corinna Cortes برای حالت غیر خطی تعمیم داده شد. ماشین بردار پشتیبانی (Support vector machines) یکی از روش های یادگیری با نظارت (Supervised learning) است که از آن برای طبقه بندی و رگرسیون استفاده می کنند.

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

مدلسازی رفتار داده ها در شبکه های اجتماعی با استفاده از روش SVM

فرض کنید که اطلاعات حاصل از رفتارهای مختلف یک شبکه اجتماعی را به صورت مجموعه زیر نمایش دهیم:

{(x₁,C₁),(x₂,C₂)…, (x_n,C_n)}

X_i یک نمونه از گره را نشان می دهد. به عنوان مثال x_i می تواند یک نمونه الگوی رفتاری یک گره در شبکه باشد. C_i کلاس یا طبقه مربوط به نمونه x_i را مشخص می کند. به عنوان مثال C_i می تواند نشان دهنده یک نمونه الگوی رفتاری x_i باشد.

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

روش طبقه بندی در این مدل

فرض کنیم مجموعه نقاط داده {(x₁,C₁),(x₂,C₂)…, (x_n,C_n)} را در اختیار داریم و می خواهیم آنها را به دو طبقه C_i=(-1,1) تفکیک کنیم. هر X_i یک بردار p بعدی از اعداد حقیقی است که در واقع همان متغیرهای بیانگر رفتار نرم افزار هستند.

روشهای طبقه بندی خطی، سعی دارند که با ساختن یک ابرسطح (که عبارت است از یک معادله خطی)، داده ها را از هم تفکیک کنند. روش طبه بندی ماشین بردار پشتیبان که یکی از روش های طبقه بندی خطی است، بهترین ابرسطحی را پیدا می کند که با حداکثر فاصله (maximum margin) داده های مربوط به دو طبقه را از هم تفکیک کند. به منظور درک بهتر مطلب، در شکل 1 تصویری از یک مجموعه داده متعلق به دو کلاس نشان داده شده که روش ماشین بردار پشتیبان بهترین ابرسطح را برای جداسازی آنها انتخاب می کند.

در شکل داده ها دو بعدی هستند یعنی هر داده تنها از دو متغیر تشکیل شده است.

نحوه تشکیل ابرسطح جداکننده توسط ماشین بردار پشتیبان

در این بخش می خواهیم نحوه ساخت ابرسطح جداکننده را بر روی یک مثال با جزئیات شرح دهیم. تصویر دقیقی از نحوه تشکیل ابرسطح جداکننده توسط ماشین بردار پشتیبان در شکل 2 نشان داده شده است.

ابتدا یک پوسته محدب در اطراف نقاط هر کدام از کلاسها در نظر بگیرید. در شکل 2 در اطراف نقاط مربوط به کلاس 1- و نقاط مربوط به کلاس 2+ پوسته محدب رسم شده است. خط p خطی است که نزدیکترین فاصله بین دو پوسته محدب را نشان می دهد.

h که در واقع همان ابرسطح جداکننده است، خطی است که p را از وسط نصف کرده و بر آن عمود است.

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

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

(1)      W.x-b=1

(2)      w.x-b=-1

نکته قابل توجه این است که اگر داده های تعلیمی به صورت خطی تفکیک پذیر باشند، می توان دو ابر سطح مرزی را به گونه ای انتخاب کرد که هیچ داده ای بین آنها نباشد و سپس فاصله بین این دو ابرسطح موازی را به حداکثر رساند. با به کارگیری قضایای هندسی، فاصله این دو ابرسطح عبارت است 2/lwl، پس باید lwl را به حداقل رساند. همچنین باید از قرار گرفتن نقاط داده در ناحیه درون مرز جلوگیری کرد. برای این کار یک محدودیت ریاضی به تعریف فرمال اضافه می شود. برای هر i، با اعمال محدودیت های زیر اطمینان حاصل می شود که هیچ نقطه ای در مرز قرار نمی گیرد:

(3)      برای داده های مربوط به طبقه اول w.x_i-b≥1

(4)      برای داده های مربوط به طبقه دوم w.x_i-b≤-1

می توان این محدودیت را به صورت رابطه زیر نشان داد:

لذا این مساله بهینه سازی بدین شکل تعریف می شود:

به حداقل رساندن w، با درنظر گرفتن محدودیت زیر می باشد.

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

نتایج

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