گراف کاوی - تحلیل داده های توییتر - قسمت دوم

به نام خداتو پست قبلی مختصر درباره پایان نامه کارشناسی نوشتم و قصد داشتم تو قسمت های بعدی مفصل توضیح بدم که تو هر بخش چیکار کردم.اگر پست قبل رو نخوندید توصیه میکنم حتما بخونید تا یه دورنما از پروژه ای که انجام دادم داشته باشید. https://vrgl.ir/TKNSG رفرنس اصلی این پژوهشگراف کاوی چیست؟گراف کاوی به تعریف خودمونی ، علم بررسی روابط موجود در یک جامعه هست. این یک تعریف خیلی علمی و دقیق از گراف کاوی نیست، من حس کردم به جای تعاریف خشک این مفاهیم رو با مثال شرح بدم.فرض کنید ما یک زمین کشاورزی داریم که با اینترنت اشیا آبیاری میشه و شرایط محیطی این زمین مثل رطوبت، دما، میزان باد و ... با استفاده از سنسور های مختلف سنجیده میشه. یک چالش مهمی که برای طراحی و جاگذاری این سنسورها و تجهیزات وجود داره ، مساحت زیاد زمین کشاورزی هست و نحوه ارتباط گرفتن بین سنسور ها با سرور مرکزی و پردازشگرها و انتقال پیام بین آنها. اینترنت اشیا در فضایی به مساحت یک خانه 80 متری یا دفتر کار 120 متری با تجهیزات قوی چالشی در انتخاب و جاگذاری تجهیزات ندارد. ولی زمانی که ما میخواهیم 10 هکتار زمین را با کمترین هزینه و با صرفه اقتصادی بالا تجهیز کنیم مسئله جاگذاری بسیار مهم و پر اهمیت میشود. گراف می تواند در حل این مسئله به ما کمک کند. به این صورت که به طور مثال هر سنسور دما با توجه به نوع و مدل انتخابی دارای محدویت های فاصله ای در ارتباط و توان انتقال پیام متفاوتی می باشد. میتوان تمام این تجهیزات را در قالب گراف مدل سازی کرد و مدل بهینه برای نحوه جاگذاری و فاصله بین این تجهیزات را به دست آورد. این یک مثال مرتبط از کاربرد این بحث بود و موارد متعددی رو میشه مثال زد که از علم گراف برای بهبود کارایی بشه استفاده کرد .شبکه های اجتماعی و گرافزمانی که شروع به جستجو برای پیدا کردن مسئله مناسب برای داده کاوی داده های توییتر بودم،کتاب هایی که با دو کلمه کلیدی داده کاوی و شبکه های اجتماعی مرتبط بودند رو بخش مقدمه و فصل اولشون رو خوندم. (خوبی کتاب فروشی های انقلاب اینه که میتونی اول مقدمشون رو بخونی و بعد انتخاب کنی که میخوای از چه کتابی استفاده بکنی ) اکثر کتاب هایی که در این زمینه نوشته شده بودند، بخش عمده ای از تحقیقات و مطالعاتشون زیر مجموعه گراف بود، بنابر این یکی از مهم ترین بخش هایی که میتونی که داده های شبکه اجتماعی رو به دانش تبدیل بکنه، مدل سازی شبکه اجتماعی به یک گراف و محاسبه خواص این گراف اولین گام برای تحلیل یک شبکه اجتماعی هست.اَه!! چقدر گراف ، مگه الگوریتم های کلاسیک داده کاوی چه ایرادی داره؟حقیقتی مهمی که وجود داره اینه که من الان دارم در مورد شبکه های اجتماعی صحبت میکنم، منظورم اینه که همه ی مدل های شبکه های اجتماعی، نه فقط توییتر ، نه فقط ویکیپدیا ، نه صرفا شبکه ایمیل ها و ...وقتی داریم خیلی جنرال صحبت میکنیم، عنصر مشترک بین تمام این شبکه ها صرفا گراف هستش. شاید من بخوام یه دسته بندی از آهنگ ها روی داده های اسپاتیفای داشته باشم، شاید با استفاده از بحث یادگیری عمیق بتونم یه دسته بندی با توجه به سیگنال ها و محتوای آهنگ به دست بیارم، اما نکته مهمی که وجود داره این هست که این الگوریتم فقط کاربردش در این مورد خاص هست ولی گراف یه کاربرد عمومی برای دسته بندی گره های شبکه اجتماعی داره.البته گراف محدویت های زیادی هم در پردازش کلان داده داره و وقتی وارد عمل میشیم، به شدت دست ما رو توی پوست گردو میزاره. من میتونستم از ابزار های دیگری برای کلاسترینگ استفاده بکنم ولی حس کردم با تحقیق در زمینه گراف، دانش بیشتری کسب خواهم کرد و علاقه داشتم که درباره این موضوعات تحقیق بکنم.تشخیص اجتماعات در شبکه های اجتماعیبعد از این همه مقدمه، من تازه شروع به نوشتن مسئله ای که قصد حل کردنش رو داشتم میکنم. تشخیص اجتماعات در شبکه اجتماعی توییتر، قصد من این بود که با استفاده از رابطه بین گره ها، گره ها رو دسته بندی بکنم.به طور مثال در حالت ایده آل اگر تمام مشاغل و صنف ها در توییتر حضور فعال داشتند و این افراد با هم صنف ها و دوستان خود بیشترین ارتباط رو داشتند، در نهایت به ازای هر صنف یک گروه از گره ها وجود داشتند که همه ی آنها مشغول انجام کار مشابهی است. با توجه به این که هیچ یک از شرط های بالا وجود نداره و فضای توییتر بیشتر دارای جو سیاسی هستش و اکثر افراد با هویت های جعلی مشغول فعالیت در این شبکه های اجتماعی هستند، ایده بالا نتایج متفاوتی خواهد داشت.چرا اهمیت داره؟ چطور میتونیم ازش سود ببریم؟همان طور که در بخش قبل اشاره کردم، شرایط توییتر با توجه به فضای روزمره نویسی و فضای سیاسی حاکم و فعالیت افراد با اسامی جعلی به نحوی نیست که بتوان افراد را با توجه به شغل یا شهر یا ... دسته بندی کرد و حتی اگر بتوان چنین چیزی را تشخیص داد، سود آن برای ما چیست؟من به این پژوهش صرفا به عنوان سه واحد درسی برای دریافت مدرک کارشناسی نگاه نکردم و برام خیلی مهم بود که یک پژوهش کاربردی و پر استفاده باشه بنابر این مثالی که بالا برای طبقه بندی افراد مطرح کردم صرفا جهت آشنایی شما با فضای تحقیق بود و گروه بندی مشاغل قطعا هدف این تحقیق نبود. من چندین سال هست که توییتر فارسی رو دنبال میکنم و نسبتا با این فضا آشنا هستم و معمولا توی جریان اتفاقات و طوفان های توییتری یک پیشفرض که از سوی دو طرف وجود داره ربات بودن طرف رقیب هستش و من اینجا به خاطر این که هیچ گونه سوگیری احتمالی از مطلب به وجود نیاد، اسم هیچ جناح سیاسی و هشتگ مرتبطی رو نمیارم و سعی میکنم در فضای خنثی حرکت کنم. توی جریان هشتگ اخیری که اتفاق افتاد من از هر دو جناح تحلیل های بسته ای منتشر می شد و هر دو گروه ادعا هایی درباره اون طوفان توییتری داشتند، من به هر دو بزگرواری که اون تحلیل ها رو روی داده ها انجام داده بودند پیام دادم و متاسفانه هیچ کدوم نه دیتاهاشون رو در اختیار قرار دادند و نه از روش و جزئیات کار صحبت کردند. منظورم از تحلیل بسته اینه که فقط نتایج تحلیل رو منتشر کردند و روش کار رو شرح ندادند.با توجه به توضیحاتی که عرض کردم، هدف من در این تحقیق تشخیص گروه های سیاسی توییتر و ربات های توییتری بود، ابزار این کار هم گراف بود، که میتونستیم فارغ از محتوای توییت ها و اکانت ها، دسته بندی رو انجام بدیم. اهمیت این کار در ارزیابی درست اجتماع و خواسته های افراد در توییتر هست و یک معیار بسیار خوب برای سنجش کل محتوای توییتر فارسی هست. به طور مثال اگر زمانی در توییتر توییتی وایرال شد، یا اگر طوفان توییتری وجود داشت، میتوان به تفکیک ادعا کرد که چه گروه هایی در ایجاد این هشتگ نقش داشتند، چون قبلا افراد دسته بندی شده اند و دیتای دسته بندی شده به صورت پابلیک منتشر شده است. و سود این کار در شنیدن صدای واقعی مردم است.اَه! چقدر حرف میزنی!! برو سر اصل مطلبمن تو این پست قرار بود راجع به گراف کاوی صحبت بکنم ولی کمتر به مفاهیم گراف پرداختم و بیشتر مقدمه گفتم. قطعا کسی که بخواد گراف کاوی رو یاد بگیره میره کتاب و مقاله میخونه و این پست ها تجربه من از چیزهایی که باهاشون دست و پنجه نرم کردمه، در نتیجه من صرفا به صورت تیتر وار این مفاهیم رو مرور خواهم کرد و نه خبری از فرمول هست و نه جزئیات.قطربعد از این که یه گراف تعریف میشه، اولین و ساده ترین مفهومی که محاسبه میشه قطر هستش.خیلی ساده بخوام بگم، اگر عدد a رو به عنوان قطر یک گراف در نظر بگیریم، از بین کوتاهترین مسیر بین تمام زوج گره ها ، بزرگترین عدد قطر یک گراف یا همون a هستش.ماتریس های یک گرافزمانی که داریم یک گراف رو تحلیل می کنیم. فارغ از هدف تحقیق، شاخص های آماری رو مورد ارزیابی قرار میدیم، علاوه بر قطر، ماتریس های گراف نیز جزو شاخص های آماری محسوب می شوند. این ماتریس ها خواص گراف رو خیلی راحت تر میتونند استخراج کنند و در واقع ما یک گراف رو تبدیل به یک ماتریس کردیم که محاسبات روی اون راحت تر بشه. البته چون من از کتابخونه networkx استفاده کردم این تحلیل ها رو انجام ندادم و مستقیم رفتم سر اصل مطلب.الگوریتم تشخیص اجتماعاتبرای تشخیص اجتماعات روش های متنوع و رویکرد های مختلفی وجود داره و با توجه به کتابی که دست من بود، حدود 40 صفحه مطلب راجع بهش نوشته شده و چون کتاب قدیمی مال سال 2011 بود ، الگوریتم های زیادی هم اصلا صحبتی ازش نشده بود و این سرفصل خیلی گسترده است و اگر بخوایم مفصل راجع بهش توضیح بدیم، میشه چندین کتاب صرفا در مورد این الگوریتم ها نوشت، ولی من صرفا سه تا الگوریتم رو اسمشون رو میگم که یکی از این ها رو هم پیاده سازی کردم، اگر در آینده فرصت شد، درباره این الگوریتم ها یک پست بلاگ مجزا خواهم نوشت. الگوریتم ها : الگوریتم گیروان نیومن که تقریبا معروف ترین الگوریتم هست، الگوریتم ژائو ژانگ، الگوریتم لووائین، این سه الگوریتمی که گفتم برای کلان داده ها اصلا مناسب نیست و پیچیدگی محاسباتی بالایی داره، الگوریتمی که من استفاده کردم الگوریتم LPA بود که یکی از الگوریتم های مقیاس پذیر است. البته روش های بهبود یافته ای نیز برای این الگوریتم وجود داره ولی به دلیل مدل سازی با استفاده از networkx، محدودیت هایی برای اجرای الگوریتم مطلوب داشتم.چون این پست طولانی شد و شاید خوندنش براتون خسته کننده باشه، من سایر مطالب این حوزه رو خیلی تیتروار میگم و دربارشون توضیحی نمیدم. در این پژوهش از مفاهیمی که بالا توضیح دادم استفاده شده ولی مفاهیمی که در ادامه به صورت تیتروار میگم برای علاقه مندان این حوزه هستش.قدم زن های تصادفی (Random Walker)فرگشت در شبکه های اجتماعی الگوریتم های تاثیر اجتماعیالگوریتم های مکانیابی خبرهپیش گویی لینکمصورسازی شبکه های اجتماعیبرچسب زنی و کاربردهای آنجمع بندیمن در این پست به طور خلاصه یه کاربرد از گراف کاوی رو گفتم، اهمیت این موضوعات رو مطرح کردم و نهایتا مختصری درباره گراف ها نوشتم. هدف این پست آشنایی با گراف بود و قصد آموزش دادن نداشتم و سواد زیادی هم در این زمینه ندارم که بخوام دربارش بنویسم. تو قسمت بعدی درباره API توییتر خواهم نوشت و وارد فضای کد نویسی خواهیم شد که به نظرم از این دو پستی اولیه به شدت جذاب تر خواهد بود.