۱. مقدمه
۱.۱. اهمیت افراد موثر در شبکه های اجتماعی
امروزه کسی نمی تواند اهمیت افراد موثر دنیای مجازی را در زندگی نادیده بگیرد. شبکه های اجتماعی همانند توییتر، فیسبوک و صدها سایت دیگر، بخش مهمی از دنیای مجازی و پهناور اینترنت هستند که نقش مهمی در زندگی انسان ها ایفا می کنند و ساعات زیادی را از وقت کاربران را در روز به خود اختصاص می دهند. روزانه حجم بسیار زیادی از داده، در قالب توییت یا هر فرمت قابل انتشار دیگری، از طریق شبکه های اجتماعی به اشتراک گذاشته می شود.
در تعداد بسیار زیادی از این توییت ها اطلاعات صریح (explicit) و نهفته (implicit) بسیار زیادی موجود است. بدیهی است که اکثر کاربران شبکه ی اجتماعی توییتر، مطالعه ی علمی در حوزه ی داده و انتقال اطلاعات ندارند. اما تجربه و هوشمندی برخی از آنان موجب شده است که توجه افراد بیشتری را نسبت به سایر کاربران به خود معطوف سازند. علاوه بر محتوای پیام، تشخیص میزان تاثیرگذاری و دلایل آن نیز، اطلاعات قابل تاملی را در اختیار محققین قرار می دهد.
شبکه های اجتماعی خاستگاه بسیاری از جریان های فکری است و مسلما تعدادی از کاربران با آگاهی کامل از محتوای پیام های خود، اقدام به ترویج طرز فکری خاص میان افراد یک جامعه، یک کشور و ... می کنند. شناختن این افراد به ما در شناخت تمایلات جامعه کمک می کند. این شناخت کاربردهای مختلفی در حوزه ی تجارت، سیاست، فرهنگ و ... دارد. حتی در مواقعی که جامعه نیاز به روحیه ی و یکپارچگی دارد می توان از این افراد کمک خواست. به طور کلی، شناختن افراد موثر در شبکه های اجتماعی و دلایل تاثیر گذاری این افراد، به ما کمک می کند تا با الگو گرفتن از آن ها بتوانیم علاوه بر استفاده از تکنیک های آنان در رساندن پیام های خود، جریان های مخرب را به موقع شناسایی کنیم و از همه گیر شدن (viral) آنان حتی الامکان جلوگیری کنیم.
۱.۲. شرح پروژه
این پروژه بر اساس یکی از مسابقات سایت kaggle تعریف شده است. در این مسابقه، از شرکت کنندگان خواسته شده است تا مدلی طراحی کنند که از بین دو کاربر، تشخیص دهد که کدام به نظر سایر کاربران (انسان های دیگر)، شخص موثر تری در شبکه ی اجتماعی توییتر (Twitter) است. پاسخ به هر مقایسه عددی بین صفر و یک است. عدد یک به برتری مطلق شخص A و عدد صفر به برتری مطلق شخص B می پردازد. عددهای دیگر به حالت های میانی می پردازند. (هر عدد بالای 0.5 برتری A و سایر اعداد برتری B را مشخص می کند.)
۲. کارهای مرتبط
۲.۱. دانش مورد نیاز
این مسئله از سوالات مورد بحث در حوزه ی داده کاوی است.
با افزایش سرعت، تولید و انتقال اطلاعات، امروزه علم تازه متولد شده ی داده کاوی از trend های اصلی علوم کامپیوتر است. داده کاوی بخش های مختلف علوم بسیار زیادی را دربر می گیرد. در حوزه ی هوش مصنوعی، داده کاوی از انواع روش های Learning سیستم های کامپیوتری بهره می گیرد. داده ها ارزش
تحلیل آماری بسیاری دارند. لذا این علم از درس آمار که شاخه ای از ریاضیات نیز می باشد استفاده می کند. علاوه بر علوم ریاضیاتی همانند کامپیوتر و آمار، نباید اهمیت علوم انسانی یا به بیانی دقیق تر علوم شناختی را در داده کاوی فراموش کرد. برای مثال، مسئله ی مورد بررسی ما نیز خود به پرسشی اجتماعی می پردازد و شاید حتی مطرح کردن نتایج این تحقیق با دانشمندان علوم شناختی برای آن ها دلپذیر باشد. در بخش کار های مرتبط به شرح هر یک از این شاخه و اتباط آن با پروژه ی خود می پردازیم.
۲.۲. آموزش (Learning) [1]
در مسائل مربوط به Machine Learning،با توجه به نوع مسئله، دو رویکرد کلی موجود است
1)آموزش Unsupervised
هنگامی که داده های ما به جز ماهیت خود، دارای ویژگی دیگری نیستند. برای مثال هنگامی که تنها مختصات نقاطی را در یک فضای هندسی
گرفته ایم و از ماهیت نقاط خبر نداریم، از این روش برای learning استفاده می کنیم
۲) آموزش Supervised
هنگامی که داده های ما با یک سری اتریبیوت خود را معرفی می کنند. مثل دیتاست مسئله ما که تنها به ذکر شخص A و B نپرداخته و ویژگی های آنان را نیز مشخص کرده است.
در نوع اول عموما از Clustering (خوشه بندی) و در نوع دوم در اکثر موارد از Classification (دسته بندی) استفاده می کنیم. Preference Learning نیز از روش های Supervised هست که از جهاتی به Classification نزدیک است. با توجه به ماهیت مسئله ی ما Preference Learning روش مناسبی است.
2.3. Preference Learning [2]
در Preference Learning ما در پی آموزش مدلی هستیم که ارحجیت (Preference) داده ها بر یک دیگر تشخیص دهد. به بیان ریاضیاتی، ما مجموعه ازاشیا را داریم که هنگامی که آن را به مدل خود می دهیم، مدل ما اولویت و ارجحیت (می تواند نسبی یا مطلق باشد.) آن ها را برای ما تشخیص دهد. در بخش های بعد توضیح خواهیم داد که ماهیت مدل چیست و چگونه می توان آن را به دست آورد(اکنون به این مقدار توضیح کفایت می کنیم که مدل از یک سری داده ی درست ساخته می شود و بعد از تایید شدن آن، می توان آن را برای داده های ناشناخته و تحلیل شده استفاده کرد.).
در ساده ترین انواع این مسائل می بینید که مجموعه از اشیا را به ما داده اند و می خواهند که جایگشتی را از آن ها مدل به ترتیب ارجحیت تولید کرده است، به عنوان پاسخ ارائه کنیم. (شکل 1)
اکنون که به کمک یک مسئله ی ساده با Preference Learning آشنا شدیم، مسئله ی دیگری را بررسی می کنیم که شباهت بیشتری با مسئله ی ما که
مقایسه دو نفر است دارد. (شکل 2)
اگر به مسئله دقت کنید متوجه می شوید که این بار هر ورودی مدل، ترتیبی از Label های مسئله تعبیر می شود. در مسئله ی ما، ما دو ترتیب A>B و B>A را
داریم. تلاش برای حل مسئله ی دوم در واقع آغاز مسیر ما برای یافتن فرد موثر تر در هر داده به سیستم مدل ماست.
در بخش بعد منحصرا به Pair-wise Preference Learning می پردازیم.
2.4. 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] به آن نسبت دهیم با یک مسئله ی pair-wise رو به رو می شویم.
با درک ماهیت مسئله، اکنون بررسی چگونگی تشکیل مدل و ماهیت مدل بسیار ملموس تر شده است. زمان آن رسیده است که مفاهیم مدل سازی
بپردازیم تا به کمک مدل خود بتوانیم آن چه را که در ذهن انسان، از موثر بودن در شبکه های مجازی نقش بسته است، بیابیم!
۲.۵. مدل ها [3]
یک مدل (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)
۲.۵.۲. ارزیابی مدل ها [1]
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 به کار می آید.
AUC و تحلیل ROC
مخفف Area Under the Curve، به معنای ناحیه ی زیر منحنی ROC می گویند. منحنی در یک مربع 1 در 1 موجود است و مساحت زیر آن عددی بین 0 تا 1 است. البته در حالت رندوم نیز که در واقع 50 50 پیش بینی می کند، منحنی منطبق بر خط x=y است که مساحت زیر آن نیم است. (ساختن مدلی که
حتی از رندوم نیز ضعیف تر عمل کند، هنر بسیار بزرگی است!) پس هر چقدر AUC بیشتر باشد می توانیم، بیشتر به مدل خود اعتماد کنیم.
۲.۶. رویکرد ما نسبت به مسئله ی یافتن افراد موثر در شبکه های اجتماعی
با توضیحات بالا، مسیر آزمایش ها و پیاده سازی های ما مشخص شده است. در آزمایش های آینده، ما با توجه به پارامتر های مسئله به روش مناسب طراحی مدل از میان روش های معرفی شده می پردازیم و به کمک داده های train مدل خود را می سازیم و به کمک داده های تست و مفاهیم ROC و AUC صحت
آن را می سنجیم و هنگامی که AUC مورد قبول رسیدیم، از مدل برای پیش بینی بهره می بریم.
۳. آزمایش‌ها
۳.۱. مجموعه ی دادگان
مجموعه های دادگان (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 ویژگی متفاوت است، حالت های بسیار زیادی دارد. زیرا گسسته سازی اگر هر ویژگی را به سه بخش تقسیم کند، آن گاه سه به توان یازده حالت داریم!
اگر این کار را برای هر ویژگی جداگانه انجام دهیم، با فرض بالا 33 حالت داریم. یعنی اگر به کمک این 33 حالت بتوانیم تمام حالت ها را تولید کنیم پیچیدگی مدل سازی را از نمایی به حالت چند جمله ای کاهش دادیم. به کمک فرمول زیر قادر خواهیم بود که این کار را انجام دهیم:
اگر X، همه ی ویژگی ها x1 تا xn هر ویژگی باشد:
p(c|X) = p(x1|c)p(x2|c)...p(xn|c)p(c)
** من در این فاز مجال پیاده سازی را نیافتم. در قسمت بهبود آزمایش ها تمام فرمول های بالا را به کمک زبان پایتون پیاده سازی خواهم کرد.
۴. کارهای آینده
۵. لیست واژگان
۶. مراجع
[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
www.preference-learning.org/PL-Tutorial-DS-11.pdf (منبع آموزشی موجود در مسابقه ی سایت kaggle)