تغییرات پیدا کردن افراد موثر در شبکه‌های اجتماعی(تحقیقاتی)

# مقدمه ##اهمیت شبکه های اجتماعی دنیای مجازی امروزه کسی نمی تواند اهمیت دنیای مجازی را در زندگی نادیده بگیرد. شبکه های اجتماعی همانند **توییتر**، فیسبوک و صدها سایت دیگر، بخش مهمی از دنیای مجازی و پهناور اینترنت هستند که نقش مهمی در زندگی انسان ها ایفا می کنند و ساعات زیادی را از وقت کاربران ا در روز به خود اختصاص می دهند. روزانه حجم بسیار زیادی از داده، در قالب توییت یا هر فرمت قابل انتشار دیگری، از طریق شبکه های اجتماعی به اشتراک گذاشته می شود. در تعداد بسیار زیادی از این توییت ها اطلاعات **صریح** (explicit) و **نهفته** (implicit) بسیار زیادی موجود است. بدیهی است که اکثر کاربران شبکه ی اجتماعی توییتر، مطالعه ی علمی در حوزه ی داده و انتقال اطلاعات ندارند. اما تجربه و هوشمندی برخی از آنان موجب شده است که توجه افراد بیشتری را نسبت به سایر کاربران به خود معطوف سازند. علاوه بر محتوای پیام، تشخیص میزان تاثیرگذاری و دلایل آن نیز، اطلاعات قابل تاملی را در اختیار محققین قرار می دهد. ##اهمیت یافتن افراد موثر در شبکه های اجتماعی شبکه های اجتماعی خاستگاه بسیاری از جریان های فکری است و مسلما تعدادی از کاربران با آگاهی کامل از محتوای پیام های خود، اقدام به ترویج طرز فکری خاص میان افراد یک جامعه، یک کشور و ... می کنند. شناختن این افراد به ما در شناخت تمایلات جامعه کمک می کند. این شناخت کاربردهای مختلفی در حوزه ی تجارت، سیاست، فرهنگ و ... دارد. حتی در مواقعی که جامعه نیاز به روحیه ی و یکپارچگی دارد می توان از این افراد کمک خواست. به طور کلی، شناختن افراد موثر در شبکه های اجتماعی و دلایل تاثیر گذاری این افراد، به ما کمک می کند تا با الگو گرفتن از آن ها بتوانیم علاوه بر استفاده از تکنیک های آنان در رساندن پیام های خود، **جریان های مخرب** را به موقع شناسایی کنیم و از **همه گیر شدن** (viral) آنان حتی الامکان جلوگیری کنیم. ##شرح دقیق تر پروژه و دیتاست مسابقه ما می خواهیم به کمک **preference learning** ، که در سطور بعدی بیشتر به شرح آن می پردازیم، سامانه ای را طراحی کنیم که بتواند از بین دو کاربر تشخیص دهد که از نظر انسان، کدام یک شخصی موثرتر در شبکه ی اجتماعی هست. دیتاست های ما مربوط به شبکه ی اجتماعی توییتر هست و در هر ردیف آن اتریبیوت های پروفایل دو کاربر و انتخاب انسان ذکر شده است. دو دسته دیتاست که یکی برای **آموزش** سیستم و دیگری برای **تست** سامانه است، موجود است. اشخاص با حروف A و B مشخص شده است. در صورتی که اتریبیوت انتخاب (Choice) برابر یک باشد، شخص A و اگر صفر باشد شخص B توسط انسان شخص موثری تری تشخیص داده شده است. برای هر کاربر 11 اتریبیوت موجود است که عبارتند از: 1- فالوور ها 2- فالویینگ ها 3- تعداد حضور در لیست ها 4- نرخ منشن شدن ها 5- نرخ ریتوییت شدن ها 6- نرخ منشن کردن ها 7- نرخ ریتوییت کردن ها 8- نرخ پست گذاری 9-10-11 – network features حجم داده ی آموزشی 5500 رکورد و حجم داده ی تست 5950 رکورد است. اکنون به دانش مورد نیاز برای حل مسئله می پردازیم. ##دانش مورد نیاز این مسئله از سوالات مورد بحث در حوزه ی **داده کاوی** است. با افزایش سرعت، تولید و انتقال اطلاعات، امروزه علم تازه متولد شده ی داده کاوی از trend های اصلی علوم کامپیوتر است. داده کاوی بخش های مختلف علوم بسیار زیادی را دربر می گیرد. در حوزه ی هوش مصنوعی، داده کاوی از **انواع روش های Learning** سیستم های کامپیوتری بهره می گیرد. داده ها ارزش تحلیل آماری بسیاری دارند. لذا این علم از درس **آمار** که شاخه ای از ریاضیات نیز می باشد استفاده می کند. علاوه بر علوم ریاضیاتی همانند کامپیوتر و آمار، نباید اهمیت علوم انسانی یا به بیانی دقیق تر **علوم شناختی** را در داده کاوی فراموش کرد. برای مثال، مسئله ی مورد بررسی ما نیز خود به پرسشی اجتماعی می پردازد و شاید حتی مطرح کردن نتایج این تحقیق با دانشمندان علوم شناختی برای آن ها دلپذیر باشد. در بخش کار های مرتبط به شرح هر یک از این شاخه و اتباط آن با پروژه ی خود می پردازیم. # کارهای مرتبط ## آموزش (Learning) در مسائل مربوط به **Machine Learning**،با توجه به نوع مسئله، دو رویکرد کلی موجود است 1)آموزش Unsupervised هنگامی که داده های ما به جز ماهیت خود، دارای اتریبوت دیگری **نیستند.** برای مثال هنگامی که تنها مختصات نقاطی را در یک فضای هندسی گرفته ایم و از ماهیت نقاط خبر نداریم، از این روش برای learning استفاده می کنیم ۲) آموزش Supervised هنگامی که داده های ما با یک سری اتریبیوت خود را معرفی می کنند. مثل دیتاست مسئله ما که تنها به ذکر شخص A و B نپرداخته و ویژگی های آنان را نیز مشخص کرده است. در نوع اول عموما از **Clustering** (خوشه بندی) و در نوع دوم در اکثر موارد از **Classification** (دسته بندی) استفاده می کنیم. Preference Learning نیز از روش های Supervised هست که از جهاتی به Classification نزدیک است و تفاوت هایی نیز با آن دارد. با توجه به ماهیت مسئله ی ما Preference Learning روش مناسبی است. ##Preference Learning در Preference Learning ما در پی آموزش مدلی هستیم که ارحجیت (Preference) داده ها بر یک دیگر تشخیص دهد. به بیان ریاضیاتی، ما مجموعه ازاشیا را داریم که هنگامی که آن را به مدل خود می دهیم، مدل ما اولویت و ارجحیت (می تواند نسبی یا مطلق باشد.) آن ها را برای ما تشخیص دهد. در بخش های بعد توضیح خواهیم داد که ماهیت مدل چیست و چگونه می توان آن را به دست آورد(اکنون به این مقدار توضیح کفایت می کنیم که مدل از یک سری داده ی درست ساخته می شود و بعد از تایید شدن آن، می توان آن را برای داده های ناشناخته و تحلیل شده استفاده کرد.). در ساده ترین انواع این مسائل می بینید که مجموعه از اشیا را به ما داده اند و می خواهند که جایگشتی را از آن ها مدل به ترتیب ارجحیت تولید کرده است، به عنوان پاسخ ارائه کنیم. (شکل 1) ![شکل 1](https://boute.s3.amazonaws.com/256-simple_preference.jpg) اکنون که به کمک یک مسئله ی ساده با Preference Learning آشنا شدیم، مسئله ی دیگری را بررسی می کنیم که شباهت بیشتری با مسئله ی ما که مقایسه دو نفر است دارد. (شکل 2) ![شکل 2](https://boute.s3.amazonaws.com/256-label_prefences.jpg) اگر به مسئله دقت کنید متوجه می شوید که این بار هر ورودی مدل، ترتیبی از 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 توجه کنید. ![شکل 3](https://boute.s3.amazonaws.com/256-abs_pw_classification.jpg) ![شکل 4](https://boute.s3.amazonaws.com/256-rl_pw_claasification.jpg) اکنون می خواهیم شرایط مسئله ی فرد موثرتر را بررسی کنیم. ما دو Label A,B را داریم و تنها دو ارجحیت A>B و B<A. اگر اولی را معادل 1 و دومی را معادل صفر بگیریم، یا در حالت پیوسته به نسبت ارجحیت عددی را از [0,1] به آن نسبت دهیم با یک مسئله ی pair-wise رو به رو می شویم. با درک ماهیت مسئله، اکنون بررسی چگونگی تشکیل مدل و ماهیت مدل بسیار ملموس تر شده است. زمان آن رسیده است که مفاهیم مدل سازی بپردازیم تا به کمک مدل خود بتوانیم آن چه را که در ذهن انسان، از موثر بودن در شبکه های مجازی نقش بسته است، بیابیم! ##مدل ها یک **مدل** (Model) یا به بیان دقیق تر، یک **مدل پیش بینی کننده**(Predictive Model)، مجموعه ی قوانین برداشت شده از نمونه های طبقه بندی شده و شناخته شده است که به کمک آن، می توانیم دسته ی داده های دسته بندی نشده ی خود را پیش بینی کنیم. ###ساختن مدل به طور کلی مدل سازی، تقریبا با هر روشی، مراحل مشخصی دارد. 1- آموزش (Train ): ما در این مرحله باید تعداد نسبتا زیادی داده ی درست (valid) را همراه با خروجی مورد نظر و درست در اختیار سیستم قرار دهیم تا از روی آن مدل را بسازد. ما در این پروژه فایل train.csv را داریم که دارای داده های آموزشی است. ستون choice حاوی پاسخ انسان به مقایسه است. 2- تست (Test) : اکنون که مدلی را در اختیار داریم، نمی توانیم بدون آزمایش بگوییم که مدل ما درست است. باید توسط یک سری داده ی دیگر آن را تست کنیم. در این پروژه فایل test.csv برای این منظور قرار داده شده است. 3- استفاده از مدل : هنگامی که تست مدل را تایید کرد. (چگونگی ارزشیابی (Evaluation) را در ادامه شرح خواهیم داد.) آنگاه می توانیم آن را برای داده هایی که پاسخش برای ما مجهول است به کار ببریم. روش های مرسوم ساختن مدل عبارتند از: + Neural networks در این روش ما سعی می کنیم عملکرد مغز انسان را شبیه سازی کنیم. هر Node را اصطلاحا یک نرون می نامیم و با هر داده رابطه ی بین نرون ها train می شود. شبکه ی عصبی همواره در حال train شدن است و می تواند به صورت بخش بخش پیاده سازی شود. ورودی هر بخش، خروجی بخش قبلی اش هست.مزیت این روش، دقت بسیار بالای آن پس از مدت طولانی است و مشکل عمده ی آن مدت طولانی رسیدن به یک مدل صحیح است. تعداد داده های این پروژه به اندازه ای نیست که بتوان شبکه ی عصبی قوی ای را train کرد. + Lazy learning در مقابل تمام روش هایی که مدتی را صرف آموزش مدل می کنند، در این روش به ازای هر داده ما تحلیل خود را ارائه می دهیم. به بیان دیگر هر بار مسئله را برای داده های ورودی حل می کنیم. این روش در تقابل با شبکه ی عصبی مدت زمان بسیار کوتاهی برای train نیاز دارد. اما خیلی دیر به ما جواب می دهد. زیرا زمان زیادی برای تحلیل نیاز دارد. + Decision trees به کمک اتریبیوت هایی که آنتروپی (بی نظمی) قابل قبولی در داده های ما دارند (آنتروپی بسیار زیاد هم مناسب نیست، چون از شباهت ها چشم پوشی می کند و عموما مختص ویژگی های پروفایلی است.)، یک درخت تصمیم گیری تشخیص می دهیم و هر برگ آن ما را به سمت یک دسته (class) می برد. این روش با توجه به حجم داده های ما و تعداد اتریبیوت هایمان مناسب است. روش های دیگری نیز هستند که احتمالا در آزمایشات آن ها را بیشتر بررسی می کنیم. + Naïve Bayes classifier + Support vector machines (SVM) + Discriminant analysis + Nearest neighbors (_k_NN) ###ارزیابی مدل ها ####ROC هنگامی که ما مدل خود را که یک **دسته بندی گر دودویی** (Binary Classifier) می باشد، ساختیم. پس از مرحله ی تست، داده های تست ما به چهار دسته تقسیم می شود. در این جا یکی از دو دسته را مثبت (Positive) و دسته ی دیگر را (Negative) می نامیم 1- داده های مثبتی که به درستی مثبت تشخیص داده شده اند. (True Positive) 2- داده های مثبتی که به اشتباه منفی تشخیص داده شده اند. (False Negative) 3- داده های منفی ای که به درستی منفی تشخیص داده شده اند. (True Negative) 4- داده های منفی ای که به اشتباه مثبت تشخیص داده شده اند. (False Positive) | ستون 1 | ستون 2 | ستون 3 | | ------ | ------ | --------------------- | | منفی | مثبت | واقعیت / پیش بینی مدل | | FP | TP | مثبت | | TN | FN | منفی | به کمک این جدول می توانیم مفاهیمی را تعریف کنیم که به ارزیابی مدلمان کمک می کند. حساسیت (Sensitivity) : نسبت TP به همه P ها. خاصیت (Specificity) : TN به N ها باید میان این دو تعادلی برقرار باشد که بتوانیم بگوییم که مدل ما مناسب است. این تعادل را با ROC می سنجیم. منحنی ROC (Receiver operating characteristic) نموداری است که طبق آن، به ازای هر آستانه (threshold) ی احتمالی از درستی که مدل به ما می دهد، نقطه ای را که مولفه ی افقی آن FPR (False Positive Rate) و مولفه ی عمودی آنTPR (True Positive Rate) است. دومی همان حساسیت هست و اولی تفاضل خاصیت از عدد یک است. از لحاظ شهودی مشخص است که هر چه قوس (curve) ROC از خط نیمساز ناحیه ی اول (x=y)، بالاتر باشد، مدل در این ارزیابی امتیاز بهتری کسب کرده است. شکل 5 چند ROC را نشان می دهد و شکل 6 حرکت آستانه ی احتمال را که برای رسم نقاط مختلف ROC به کار می آید. ![شکل 5](https://boute.s3.amazonaws.com/256-ROC_5.png) ![شکل 6](https://boute.s3.amazonaws.com/256-ROC_6.png) ####AUC و تحلیل ROC مخفف Area Under the Curve، به معنای ناحیه ی زیر منحنی ROC می گویند. منحنی در یک مربع 1 در 1 موجود است و مساحت زیر آن عددی بین 0 تا 1 است. البته در حالت رندوم نیز که در واقع 50 50 پیش بینی می کند، منحنی منطبق بر خط x=y است که مساحت زیر آن نیم است. (ساختن مدلی که حتی از رندوم نیز ضعیف تر عمل کند، هنر بسیار بزرگی است!) پس هر چقدر AUC بیشتر باشد می توانیم، بیشتر به مدل خود اعتماد کنیم. ##رویکرد ما نسبت به مسئله ی یافتن افراد موثر در شبکه های اجتماعی با توضیحات بالا، مسیر آزمایش ها و پیاده سازی های ما مشخص شده است. در آزمایش های آینده، ما با توجه به پارامتر های مسئله به روش مناسب طراحی مدل از میان روش های معرفی شده می پردازیم و به کمک داده های train مدل خود را می سازیم و به کمک داده های تست و مفاهیم ROC و AUC صحت آن را می سنجیم و هنگامی که AUC مورد قبول رسیدیم، از مدل برای پیش بینی بهره می بریم. # آزمایش‌ها # کارهای آینده #لیست واژگان # مراجع https://www.youtube.com/watch?v=sWAJsiVh1Gg https://en.wikipedia.org/wiki/Receiver_operating_characteristic[رفتن به مرجع](https://en.wikipedia.org/wiki/Receiver_operating_characteristic) (صرفا برای استفاده از اشکال) https://ac.els-cdn.com/S000437020800101X/1-s2.0-S000437020800101X-main.pdf?_tid=ad47a578-ca1b-11e7-93f5-00000aacb361&acdnat=1510760768_522b48a5c7b01916ec0c292dd75c79e7 http://searchdatamanagement.techtarget.com/definition/predictive-modeling Data Mining Concepts and Techniques (Chapter 3-7-8), J.Han and others, third edition, 2012 [رفتن به مرجع](www.preference-learning.org/PL-Tutorial-DS-11.pdf) www.preference-learning.org/PL-Tutorial-DS-11.pdf # پیوندهای مفید + [لینک مسابقه](https://www.kaggle.com/c/predict-who-is-more-influential-in-a-social-network/leaderboard)