میزان اهمیت شبکه های مجازی در زندگی انسان ها، روز به روز در حال افزایش است. با گسترده تر شدن تعداد و امکانات این شبکه ها، آن ها می توانند بستر مناسبی برای فعالیت های پر اهمیتی همچون: تجارت، مسائل سیاسی و غیره، باشند. در این میان افراد موثر بهتر از سایرین قادر خواهند بود تا به اهدافشان در شبکه های مجازی برسند. مطالب تبلیغاتی، اخبار و ... از دسته ی مطالبی است که بازدید زیاد آن ها، به معنی موفقیت آمیز بودن انتشار آن ها در دنیای مجازی بوده است. کاملا بدیهی است که هر چقدر که منتشر کننده ی این نوع مطالب شخص موثرتری در شبکه ی اجتماعی باشد، طبیعتا مطلب نیز پربازدید تر است و در اجتماع تاثیر بیشتری می گذارد. پس می توان گفت اگر می خواهیم بدانیم که چگونه برخی از مطالب موثر و همه گیر می شوند و بعضی دیگر اینگونه نیستند، در گام اول باید افراد موثر در شبکه های اجتماعی را شناسایی کنیم. در ادامه به یکی از مسائل در این حوزه می پردازیم.
۱. مقدمه
۱.۱. اهمیت افراد موثر در شبکه های اجتماعی
امروزه کسی نمی تواند اهمیت افراد موثر دنیای مجازی را در زندگی نادیده بگیرد. شبکه های اجتماعی همانند توییتر، فیسبوک و صدها سایت دیگر، بخش مهمی از دنیای مجازی و پهناور اینترنت هستند که نقش مهمی در زندگی انسان ها ایفا می کنند و ساعات زیادی را از وقت کاربران را در روز به خود اختصاص می دهند. روزانه حجم بسیار زیادی از داده، در قالب توییت یا هر فرمت قابل انتشار دیگری، از طریق شبکه های اجتماعی به اشتراک گذاشته می شود.
در تعداد بسیار زیادی از این توییت ها اطلاعات صریح (explicit) و نهفته (implicit) بسیار زیادی موجود است. بدیهی است که اکثر کاربران شبکه ی اجتماعی توییتر، مطالعه ی علمی در حوزه ی داده و انتقال اطلاعات ندارند. اما تجربه و هوشمندی برخی از آنان موجب شده است که توجه افراد بیشتری را نسبت به سایر کاربران به خود معطوف سازند. علاوه بر محتوای پیام، تشخیص میزان تاثیرگذاری و دلایل آن نیز، اطلاعات قابل تاملی را در اختیار محققین قرار می دهد.
شبکه های اجتماعی خاستگاه بسیاری از جریان های فکری است و مسلما تعدادی از کاربران با آگاهی کامل از محتوای پیام های خود، اقدام به ترویج طرز فکری خاص میان افراد یک جامعه، یک کشور و ... می کنند. شناختن این افراد به ما در شناخت تمایلات جامعه کمک می کند. این شناخت کاربردهای مختلفی در حوزه ی تجارت، سیاست، فرهنگ و ... دارد. برای مثال می توان در مواقعی که جامعه نیاز به روحیه ی و یکپارچگی دارد می توان از این افراد موثری که در حوزه ی مسائل اجتماعی فعالتی می کنند، کمک خواست. به طور کلی، شناختن افراد موثر در شبکه های اجتماعی و دلایل تاثیر گذاری این افراد، به ما کمک می کند تا با الگو گرفتن از آن ها بتوانیم علاوه بر استفاده از تکنیک های آنان در رساندن پیام های خود، جریان های مخرب را به موقع شناسایی کنیم و از همه گیر شدن (viral) آنان حتی الامکان جلوگیری کنیم.
۱.۲. شرح پروژه
این پروژه بر اساس یکی از مسابقات سایت kaggle[4] تعریف شده است. در این مسابقه، از شرکت کنندگان خواسته شده است تا مدلی طراحی کنند که از بین دو کاربر، تشخیص دهد که کدام به نظر سایر کاربران (انسان های دیگر)، شخص موثر تری در شبکه ی اجتماعی توییتر (Twitter) است. البته چون مسئله ی ما یافتن افراد موثر است در انتها خواهیم گفت که چگونه می توان از این مقایسه ها به افراد موثر در بین تمام اعضای جامعه ی آماری خود برسیم.
۲. پیش زمینه
۲.۱. دانش مورد نیاز
این مسئله از سوالات مورد بحث در حوزه ی داده کاوی است.
با افزایش سرعت، تولید و انتقال اطلاعات، امروزه علم تازه متولد شده ی داده کاوی از trend های اصلی علوم کامپیوتر است. داده کاوی بخش های مختلف علوم بسیار زیادی را دربر می گیرد. در حوزه ی هوش مصنوعی، داده کاوی از انواع روش های Learning سیستم های کامپیوتری بهره می گیرد. داده ها ارزش
تحلیل آماری بسیاری دارند. لذا این علم از درس آمار که شاخه ای از ریاضیات نیز می باشد استفاده می کند. علاوه بر علوم ریاضیاتی همانند کامپیوتر و آمار، نباید اهمیت علوم انسانی یا به بیانی دقیق تر علوم شناختی را در داده کاوی فراموش کرد. برای مثال، مسئله ی مورد بررسی ما نیز خود به پرسشی اجتماعی می پردازد و شاید حتی مطرح کردن نتایج این تحقیق با دانشمندان علوم شناختی برای آن ها دلپذیر باشد. در بخش کار های مرتبط به شرح هر یک از این شاخه و اتباط آن با پروژه ی خود می پردازیم.
۲.۲. آموزش (Learning)
ما در این پروژه از یادگیری بانظارت (Supervised Learning) بهره می بریم.
هنگامی که داده های ما با یک سری اتریبیوت خود را معرفی می کنند. مثلا در مجموعه ی دادگان مسئله ما که تنها به ذکر شخص A و B نپرداخته و ویژگی های آنان را نیز مشخص کرده است.[1]
۲.۳. مدل ها
یک مدل (Model) یا به بیان
دقیق تر، یک مدل پیش بینی کننده(Predictive Model)، مجموعه ی قوانین برداشت شده از نمونه های طبقه بندی شده و شناخته شده است که به کمک آن، می توانیم دسته ی داده های دسته بندی نشده ی خود را پیش بینی کنیم.[3]
۲.۳.۱. ساختن مدل
به طور کلی مدل سازی، تقریبا با هر روشی، مراحل مشخصی دارد:
1- آموزش (Train ): ما در این مرحله باید تعداد نسبتا زیادی داده ی درست (valid) را همراه با خروجی مورد نظر و درست در اختیار سیستم قرار دهیم تا از روی آن مدل را بسازد. ما در این پروژه فایل train.csv را داریم که دارای داده های آموزشی است. ستون choice حاوی پاسخ انسان به مقایسه است.
2- تست (Test) : اکنون که مدلی را در اختیار داریم، نمی توانیم بدون آزمایش بگوییم که مدل ما درست است. باید توسط یک سری داده ی دیگر آن را تست
کنیم. در این پروژه فایل test.csv برای این منظور قرار داده شده است.
3- استفاده از مدل : هنگامی که تست مدل را تایید کرد، آنگاه می توانیم آن را برای داده
هایی که پاسخش برای ما مجهول است به کار ببریم.
۲.۳.۲. ارزیابی مدل ها
ما می توانیم کارآمدی و احتمال صحت نتایج مدل خود را با قوس آر او سی (ROC) و مساحت زیر آن قوس(AUC) بسنجیم. [1]
۳. کارهای مرتبط
درباره ی افراد موثر در فضای مجازی مقالات و مطالب متعددی وجود دارد که به برخی از آنان به اختصار اشاره می کنیم.
در یکی از مقالات[6]، از گراف رابطه استفاده شده است. کاربران به عنوان راس های این گراف هستند و هر چقدر کاربری یال های ورودی بیشتری داشته باشد، شخص موثر تری است. یال ها می تواند روابط مختلف را نشان دهد.
در مقاله ای[7]، از قوانین تجمعی (Association Rule ) و به بیان ساده تر، الگو کاوی (Pattern Mining) برای حل این مسئله کمک گرفته شده است. استفاده از مفاهیم پیشتیبان (support) دو ویژگی و اطمینان (Confidence) روش اصلی آموزش در این مقاله است.
استفاده از اس وی ام (SVM) در مقاله ای که جریان همه گیر شدن آنفولانزای خوکی را در توییتر یافت می کرد نیز به چشم می خورد. [8]
این مقاله از طریق یادگیری اولویتی راه حل پیشنهادی خود را ارائه می دهد.
۴. آزمایش‌ها
یادگیری اولویتی(Preference Learning) نیز از روش های بانظارت هست که از جهاتی به دسته بندی (Classification) نزدیک است. با توجه به ماهیت مسئله ی ما یادگیری اولویتی روش مناسبی است.
۴.۱. یادگیری اولویتی
در یادگیری اولویتی ما در پی آموزش مدلی هستیم که ارحجیت (Preference) داده ها بر یک دیگر تشخیص دهد. به بیان ریاضیاتی، ما مجموعه ازاشیا را داریم که هنگامی که آن را به مدل خود می دهیم، مدل ما اولویت و ارجحیت (می تواند نسبی یا مطلق باشد.) آن ها را برای ما تشخیص دهد. در بخش های بعد توضیح خواهیم داد که ماهیت مدل چیست و چگونه می توان آن را به دست آورد(اکنون به این مقدار توضیح کفایت می کنیم که مدل از یک سری داده ی درست ساخته می شود و بعد از تایید شدن آن، می توان آن را برای داده های ناشناخته و تحلیل شده استفاده کرد.).[2]
در ساده ترین انواع این مسائل می بینید که مجموعه از اشیا را به ما داده اند و می خواهند که جایگشتی را از آن ها مدل به ترتیب ارجحیت تولید کرده است، به عنوان پاسخ ارائه کنیم. (شکل 1)
اکنون که به کمک یک مسئله ی ساده با Preference Learning آشنا شدیم، مسئله ی دیگری را بررسی می کنیم که شباهت بیشتری با مسئله ی ما که
مقایسه دو نفر است دارد. (شکل 2)
اگر به مسئله دقت کنید متوجه می شوید که این بار هر ورودی مدل، ترتیبی از Label های مسئله تعبیر می شود. در مسئله ی ما، ما دو ترتیب A>B و B>A را
داریم. تلاش برای حل مسئله ی دوم در واقع آغاز مسیر ما برای یافتن فرد موثر تر در هر داده به سیستم مدل ماست.
در بخش بعد منحصرا به Pair-wise Preference Learning می پردازیم.
۴.۱.۱. یادگیری اولویتی جفتی(Pair-wise Preference Learning)
در مسئله ی دوم بخش قبل، با داده هایی به عنوان ورودی برخورد کردیم که تحلیل مدل از آن ها موجب می شد تا مجموعه از Label ها به جایگشتی بر اساس ارحجیت آن ها با توجه به داده ی ورودی تعیین می شد. (پیش از هر توضیح بیشتری لازم می دانم که بگویم ما بیشتر به مسائلی که به یافتن افراد موثر است می پردازیم. از لحاظ علمی، ممکن است مدل ما به گونه ی طراحی شود که برخی ارجحیت ها را بگوید و در مورد ارجحیت هایی سکوت کند. لذا قادر نخواهد بود که همواره جایگشتی از Label ها را ارائه کند. اما استفاده از کلمه ی جایگشت در حوزه ی مسئله ی ما جایز و صحیح است.)
به دسته ای مسائلی که مدل به ازای هر رکورد از داده، ارجحیت دو برچسب (Label) نسبت به هم را پیشنهاد می دهد، Pair-wise می گوییم و اکنون نشان می دهیم که مسئله ی ما از این دسته مسائل است. با توجه به اینکه داده های ما به دو دسته تقسیم می شوند ، 1- دسته هایی که ارجحیت با Label اول است و 2- بالعکس ، می توان آن را با یک Pair-wise classification(or Preference) متناظر (Map) کرد. به شکل 3 و 4 توجه کنید.
اکنون می خواهیم شرایط مسئله ی فرد موثرتر را بررسی کنیم. ما دو Label A,B را داریم و تنها دو ارجحیت A>B و B<A. اگر اولی را معادل 1 و دومی را معادل صفر بگیریم، یا در حالت پیوسته به نسبت ارجحیت عددی را از [0,1] به آن نسبت دهیم با یک مسئله ی جفتی رو به رو می شویم.
در بخش بعد به شرح بیشتر مجموعه ی دادگان مسئله می پردازیم.
۴.۲. مجموعه ی دادگان
مجموعه های دادگان (Data sets) ما مربوط به شبکه ی اجتماعی توییتر هست و در هر ردیف آن ویژگی (attribute) های پروفایل دو کاربر و انتخاب انسان ذکر شده است. دو دسته دیتاست که یکی برای آموزش سیستم و دیگری برای تست سامانه است، موجود است. اشخاص با حروف A و B مشخص شده است. در صورتی که اتریبیوت انتخاب (Choice) برابر یک باشد، شخص A و اگر صفر باشد شخص B توسط انسان شخص موثری تری تشخیص داده شده است.
برای هر کاربر 11 اتریبیوت موجود است که عبارتند از: 1- دنبال کنندگان (Followers) 2- دنبال شوندگان (Followings) 3- تعداد حضور در لیست ها 4- نرخ منشن شدن ها 5- نرخ ریتوییت شدن ها 6- نرخ منشن کردن ها 7- نرخ ریتوییت کردن ها 8- نرخ پست گذاری 9-10-11 – network features
حجم داده ی آموزشی 5500 رکورد و حجم داده ی تست 5950 رکورد است.
۴.۳. ساختن مدل
۴.۳.۱. بیز ساده
روش های مدل سازی را در بخش کار های مرتبط بررسی کردیم. اکنون به ساخت مدل می پردازیم. بیز ساده (Naive Byes) یک روش دسته بندی است. این روش به دلایل زیر برای مسئله ی ما مناسب می باشد.
مناسب برای کلاسه بندی های بین صفر و یکی یا اصطلاحا دو دویی (باینری) می باشد.
یک روش آماری است و برای مسائلی که مجموعه ی دادگان آن ها به فرم رکورد (Record) است مناسب است.
آموزش دادن مدل کار سختی نیست و در مدت کوتاهی قابل انجام است.
در این روش ما باید تمامی ویژگی ها را به صورت گسسته دربیاوریم. برای این کار می توانیم، از روش های مختلف گسسته سازی (discretization) بهره بگیریم.
قاعده ی بیز، احتمال رخدادی را در صورت قطعی بودن رخداد دیگری پیش بینی می کند. گسسته سازی مجموعه دادگان، تعداد حالات ما را محدود و شمارا می کند. از این رو، به کمک داده های آموزشی می توانیم برای هر حالتی احتمالی را به آن حالت نسبت دهیم.
بعد از ساختن مدل، اکنون هر رکورد جدیدی را برحسب فرمول به دست آمده طبق بیز ساده می توانیم با احتمالی بر حسب داده های مشابه به دست آمده است، دسته بندی کنیم.
ما برای هر رکورد چند ویژگی داریم و هر ویژگی متعلق به دو کاربر است. لذا می توانیم بر حسب اختلاف ویژگی های مربوط به هر کاربر، قاعده ی بیز را اعمال کنیم.
به طور کلی فرمول قاعده ی بیز به شکل زیر است:
قاعده ی بیز
در این شکل C ویژگی مورد سوال است که در مسئله ی ما برتری A یا B مورد سوال است. x آن رخدادی است که محقق شده است. در مسئله ی ما هر x دسته ای از داده ی حاصل شده از تفاضل ویژگی های کاربران است که به وسیله ی گسسته سازی یکسان می شوند.
اکنون با چالشی رو به می شویم. به دلیل این که ویژگی x در واقع خود ترکیب 11 ویژگی متفاوت است، حالت های بسیار زیادی دارد. زیرا گسسته سازی اگر هر ویژگی را به k بخش تقسیم کند، آن گاه k به توان یازده حالت داریم!
اگر این کار را برای هر ویژگی جداگانه انجام دهیم، با فرض بالا 11k حالت داریم. یعنی اگر به کمک این 11k حالت بتوانیم تمام حالت ها را تولید کنیم پیچیدگی مدل سازی را از نمایی به حالت چند جمله ای کاهش دادیم. به کمک فرمول زیر قادر خواهیم بود که این کار را انجام دهیم:
اگر X، همه ی ویژگی ها x1 تا xn هر ویژگی باشد:
p(c|X) = p(x1|c)p(x2|c)...p(xn|c)p(c)
در مسئله ی ما شرط c، موثر بود شخص A (و نقیض آن شخص ) می باشد. X دقیقا یکی از 11k حالت است و هر یک از xi ها یکی از حالت هایی است که هر ویژگی پس از گسسته شدن به آن تصویر (mapped) شده است.
هر چقدر گسسته سازی مناسب تر باشد، مدل ما دقیق تر است و پاسخ های بهتری را به ما می دهد.
۴.۳.۲. تبدیل پاسخ مدل به یک مدل آموزش برای رتبه بندی (Learning to rank)
مدل ما یک مدل جفتی (دوتایی) برای رتبه بندی است. اما مسئله ی ما در ابتدا، پیدا کردن افراد موثر در کل جامعه ی نمونه ی ما بود. برای استفاده از نتایج مدل به دست آمده، باید تعداد نتایج به اندازه ی کافی باشد. در بهترین حالت (ایده آل و تقریبا غیر ممکن)، زمانی که کاملا اتفاقی داده های ما خود به ترتیب اولویت باشد با پیچیدگی زمانی خطی بر حسب تعداد کاربران بدون تکرار (distinct) می توان به یک رتبه بندی کلی رسید. اما بهترین حالت اصلا محتمل نیست و انتخاب زوج ها برای مقایسه و ترتیب مقایسه ها کاملا تصادفی است. در بد ترین حالت نیز با داشتن n(n-1)/2 نتیجه از مقایسه ی جفتی که در آن n تعداد تمام کاربران جامعه ی نمونه است، می توان به نتایج کافی رسید.[4]
یکی از راه های کاهش مقایسه ها گروه بندی کاربران است. سپس بالا و پایین هر گروه را با هم مقایسه می کنیم. اما در این روش نیز برای رسیدن به یک رتبه بندی مطلق (absolute) باید این کار را چند مرحله تکرار کنیم و در حالت میانگین (average case) پیچیدگی n^2 است.
۵. کارهای آینده
مهم ترین کار در آینده پیاده سازی مدل پیشنهادی در مقاله است.
همچنین برای رسیدن به مدل دقیق تر در حل این مسئله می توان:
در صورت داشتن زمان، فضا و مجموعه ی دادگان کافی مدل سازی از روش شبکه های عصبی را بررسی کرد.
روی روش های گسسته سازی مناسب تر کار کرد. برای مثال، برای داده هایی که به صورت یکسان توزیع نشده اند روش های وزن دار را به کار برد.
همانگونه که در مقدمه اشاره شد، این مسئله به دلیل آن که انسان و نظر انسان را مورد مطالعه قرار می دهد در حوزه ی علوم شناختی نیز ارزشمند است. می توان نتایج حاصل از این تحقیق را در اختیار دانشمندان علوم شناختی قرار داد تا از آن در تحقیقات خود بهره ببرد.
۶. مراجع
[1] Data Mining Concepts and Techniques (Chapter 3-7-8), J.Han and others, third edition, 2012
[2] Label ranking by learning pairwise preferences, Eyke Hüllermeier, Johannes Fürnkranz and others, 2008
[3] http://searchdatamanagement.techtarget.com/definition/predictive-modeling
[4]https://www.kaggle.com/c/predict-who-is-more-influential-in-a-social-network/
[5]Artificial Intelligence 3rd Edition Modern Approach, Stuart Russell, Peter Norving
[6]Identification of Influential Users based on Topic-Behavior Influence Tree in Social Networks,Jianjun Wu, Ying Sha, Rui Li1 and others
[7]Finding Influential Users in Social Media UsingAssociation Rule Learning ,Fredrik Erlandsson, Piotr Bródka 2 and others, 2016
[9]Using Prediction Markets and Twitter to Predict a Swine Flu Pandemic , Joshua Ritterman , Miles Osborne , Ewan Klein ,2009
www.preference-learning.org/PL-Tutorial-DS-11.pdf (منبع آموزشی موجود در مسابقه ی سایت kaggle)