ارائه یک بهبود برای الگوریتم پیش بینی لینک آدامیک آدار

چکیده

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

خلاصه حاصل از تجزیه و تحلیل مقاله​:

روش حل مسأله

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

نحوه ی آماده سازی شبکه

شبکه مورد بررسی در این تحقیق شبکه نویسندگان همکار سایت SIDمی باشد این شبکه به صورت داده  های خام  در فرمت XML می باشد. برای هر سال یک فایلXMLوجود دارد. ابتدا این فایلها را با یکدیگر ادغام می کنیم. سپس برای استفاده از این شبکه نیاز است که گراف مجموعه ی زمان آموزش و زمان تست از این شبکه استخراج شود. گراف مجموعه ی آموزش شامل نویسندگان مقالات و لینکهای بین آنها در سالهای 79 تا 84 میباشد. گراف آزمون شامل نویسندگان مقالات و لینکهای بین آنها در سالهای 85 تا 91 است. در این مرحله انواع مختلفی از نگاشت ها انجام می شود. این نگاشتها شامل موارد زیر میشوند:نگاشت مقاله ها به فایلXMLمربوطه: از آنجایی که این شبکه به صورتXMLذخیره شده است،به کمک این نگاشت می توان محل مقاله ی مورد نظر را در فایل XMLفایل مربوطه بدست آورد به کمک این نگاشت می توان به راحتی سایر اطلاعات مربوط به مقاله از جمله کلمات کلیدی مقاله، سازمان ارائه دهند مقاله لینک PDF مقاله و زمان گرداوری مقاله دست پیدا نمود.نگاشت مقاله به نویسندگان: به کمک این نگاشت میتوان نویسنده های هر مقاله را برحسب ID آنها بدست اورد.نگاشت نویسندگان به مقالات: به کمک این نگاشت می توان مقالات نوشته شده توسط هر نویسنده را بدست اورد.نگاشت مقالات به خلاصه مقاله: به کمک این نگاشت می توان به متن خلاصه ی هر مقاله دست پیدا نمود.نگاشت مقالات به کلمات کلیدی مقالات: به کمک این نگاشت می توان به کلمات کلیدی خلاصه ی هر مقاله دست یافت.نگاشت مقالات به کلمات ریشه ی کلمات کلیدی مقالات: به کمک این نگاشت می توان به ریشه ی کلمات کلیدی مستخرج از متن خلاصه ی مقالات دسترسی پیدا نمود.برای این نگاشت ها یک سری توابع نگاشت در هم استفاده میکنیم. از طریق تعریف کلید و مقدار  برای این توابع نگاشت ها را انجام می دهیم.

پردازش زبانی محتوای شبکه

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

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

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

استخراج کلمات کلیدی

در این مرحله کلمات رایج غیر مفید از متن خلاصه ی کلمات حذف می شوند. در ابتدا تمامی اعراب و علائم نگارشی از متن حذف میگردند. سپس کلمات غیر مفید رایج از بین کلمات خلاصه حذف می گردند. برای استخراج کلمات غیرمفید مراحل مختلف طی شد. این مراحل عبارتند از:حذف کلمات رایج زبان فارسی: لیستی از کلمات فارسی رایج زبان فارسی وجود دارد که به کمک این لیست حدوداً500کلمه ای، بخشی از کلمات رایج از متن خلاصه حذف گردیدند. حذف کلمات احترام از جمله مهندس، دکتر و ... حذف برخی از افعال بدست آوردن لیستی از کلمات رایج در میان تمامی مقاله ها به کمک روشtf/idfاین مرحله برحسب محتوای متنی هر شبکه می تواند لیست متفاوتی از کلمات را به کاربر ارائه دهد.استخراج ریشه ی کلمات کلیدی: در مراحل بعدی به دو صورت از کلمات کلیدی متن خلاصه ی مقالات استفاده شده است. یک بار کلمات کلیدی بدون در نظر گرفتن ریشه ی کلمات و یک بار با در نظر گرفتن ریشه ی کلمات. می توانیم ریشه ی کلمات را به جای خود کلمات به عنوان کلمه ی کلیدی در نظر بگیریم. از این طریق کلماتی مانند موضوع وموضوع ها با یکدیگر یکسان در نظر گرفته می شوند و در محاسبه ی شباهت بردارهای زمینه ی کاری افراد تأثیر خواهندداشت.برای استخراج ریشه ی کلمات از ابزار توسعه یافته در مرکز تحقیقات مخابرات استفاده شده است. ابزار ریشه یاب در سطح دوم این جعبه ابزار، یعنی سطح ریخت شناسی، قرار گرفته است. این ابزار برای استخراج ریشه ی کلمات تنها از ساختار کلمه استفاده می کند و مستقل از محتوای آن عمل می کند.این مرحله یکی از بخش های مهم الگوریتم محسوب می شود.

استخراج موضوع مقالات

در این قسمت تمامی مقالات موجود در مجموعه ی داده ای را با موضوع های استخراج شده برچسب می زنیم. در واقع برای هر مقاله ی موجود میزان تداخل آن مقاله با موضوع ها را محاسبه می کنیم مجموعهی اسناد را با D مجموعه ی کلمات موجود در دامنه را با V نشان می دهیم. در این مرحله این مجموعه شامل کلمات کلیدی استخراج شده در مرحله ی قبل می باشد. به این دلیل که کلمات ورودی الگوریتمLDAهرچه مفیدتر باشند و بیشتر مفهوم سند را نشان دهند الگوریتم مذکور عملکرد بهتری خواهد داشت A نشان دهنده ی مجموعه ی نویسندگان و Hنشان دهنده ی مجموعه ی موضوعات استخراج شده در این بخش میباشد. هرنویسنده در نوشتن تعدادی مقاله مشارکت داشته است که جزء مجموعه یDهستند. پس هر نویسندهی عضوAدر نوشتن مجموعه ی مقالاتی همکاری داشته است که این مجموعه را با Daنشان می دهند،کهaنشان دهنده ی کد نویسنده ی مقالات این مجموعه است. برای استخراج موضوع مقاله ها از الگوریتم LDAتوسعه یافته در مقاله ی استفاده شده است. علت استفاده ازLDAبرتری این روش نسبت به روش های مشابه استخراج موضوع است. این مدل موضوعی روی مجموعه های گسسته مانند مجموعه های متنی استفاده میشودLDAبه موضوع های زیادی از قبیل فیلتر کردن همکارانه طبقه بندی متن ها، ابهام زدایی حسی کلمات، و پیشنهاد جامعه اعمال شده است. LDAدر واقع یک مدل مولد برای متن و دیگر مجموعه های گسسته ی داده ای است.در زمینه ی مدلسازی متنی، این مدل مدعی است که هر سند به صورت ترکیبی از موضوع ها تولید شده است.بنابراین این الگوریتم با گرفتن متن اسناد و تعداد موضوع های درخواستی میزان تداخل اسناد با موضوع ها را به عنوان خروجی برمی گرداند. این الگوریتم برای هر مقاله یک ماتریس تعریف میکند.درایه های این ماتریس متناسب با میزان اولیه ی ارتباط کلمات با موضوع ها می باشند. این مقادیر معمولا برای تمام موضوع ها یکسان در نظر گرفته میشوند. مقدار بهینه ی این پارامتر در فصل بعد مورد بررسی قرار گرفته است. همچنین این الگوریتم برای هر کلمه یک ماتریس با ابعاد تعریف می کند. درایه های این ماتریس متناسب با میزان اولیه ی ارتباط اسناد با موضوع ها می باشند. این مقادیرنیز معمولاً برای تمام موضوع ها یکسان در نظر گرفته می شوند. مقدار بهینه ی این پارامتر نیز در فصل بعد مورد بررسی قرارگرفته است. LDAهر سند را به صورت یک توزیع چند جمله ای روی موضوع ها در نظر می گیرد. بدین صورت که برای هر کلمه که در سند وجود دارد توزیع موضوع روی کلمات را به ما خواهد داد، یعنی ماتریسی که سطرهای آن کلمات و ستونهای آن موضوعها هستند. یکی از ورودیهای الگوریتمKاست که تعداد موضوعهایی را نشان میدهد که انتظار داریم الگوریتم استخراج نماید. اگرkموضوع تعریف کنیم،یک ماتریس تعریف می شود که توزیع موضوعها را بر روی کلمات موجود در دامنه ی کلمات نشان می دهد. در واقع احتمال اینکه کلمه یwدر موضوعkام باشد نشان داده می شود. این مقادیر احتمال با چندین بار اعمال کردن الگوریتمLDAبه ماتریس اولیه بدست می آیند. مقدار بهینه ی تعداد این تکرارها در فصل بعد مورد بررسی قرار گرفته است. سپس از طریق این توزیع، توزیع سند روی موضوعها، با استفاده از کلمات استفاده شده در این سند و توزیع موضوعها روی این کلمات،محاسبه می شود. در واقع ماتریسی با ابعاد تعریف میشود. سطرهای این ماتریس مقالات و ستونهای آن موضوع ها میباشند. در نتیجه هر درایه ی این ماتریس نشان دهنده ی احتمال تعلق یک مقاله به یک موضوع خاص میباشد. در واقع احتمال اینکه سندDiبا موضوعkام مرتبط باشد برای هر مقاله مجموع این مقادیر برابر با 1 می باشد این مقادیر احتمال نیز با چندین بار اعمال کردن الگوریتمLDAبه ماتریس اولیه بدست می آیند. مقدار بهینه ی تعداد این تکرارها نیز در فصل بعد مورد بررسی قرار گرفته است. به طور کلی ما برای هر کاربر شبکه ی اجتماعی و در واقع برای هر مقاله یک بردار تعریف میکنیم که نشان دهنده ی توزیع موضوعی آن مقاله می باشد. سپس از این توزیعهای موضوعی برای بدست آوردن زمینه های کاری نویسندگان استفاده کرده و سپس از تخمین شباهت زمینه های کاری نویسندگان برای پیشبینی لینک بین آنها استفاده میکنیم. این توزیع موضوعی در واقع به صورت ماتریسی که درایه های آن تداخل موضوعی مقالات با موضوعهای تعریف شده را نشان میدهد نمود پیدا میکند. در نهایت، به عنوان خروجی این مرحله از الگوریتم، به تعداد مقالات موجود در مجموعه ی داده ای بردار موضوع داریم، که درایه های این بردارها میزان تداخل سند مربوطه با موضوعات استخراج شده را نشان می دهند.استخراج زمینه های کاری نویسندگان در این مرحله، با استفاده از بردارهای بدست آمده در مرحله ی قبل، برای تمامی نویسندگان یک بردار علاقمندی می سازیم. درایه های این بردارها نشان دهنده ی میزان علاقمندی نویسنده ی مورد نظر به زمینه ی کاری مربوطه است. تعداد درایه های این بردارها با تعداد درایه های بردارهای موضوعی مقالات برابر میباشد. در واقع می توان به کمک موضوع های هر مقاله، زمینهی کاری هر نویسنده را نیز مشخص نمود. بر این اساس زمینه ی کاری هر نویسنده از میانگین موضوعهای تمامی مقاله های نوشته شده توسط وی بدست می اید. برای استخراج زمینه های کاری نویسندگان روشهای مختلفی ازجمله ماکزیمم گیری بین موضوعهای مقالات نویسنده نیز بررسی شد که در مجموع این روش مناسب تر از بقیه بود.لازم به ذکر است که تعداد موضوع های استخراج شده برای تمامی مقاله ها و نویسندگان یکسان و برابر بوده و علاوه برآن عنوان موضوع ها نیز یکسان می باشد. به عنوان مثال اگر 100 موضوع برای هر مقاله مشخص شود، تمامی نویسندگان نیز دارای همین 100 موضوع میباشند. میزان ارتباط هر نویسنده با هر موضوع به کمک عدد احتمال اطلاق شده به آن موضوع برای مقالات نوشته شده توسط آن نویسنده محاسبه میشود. هر فرد نویسنده ی تعدادی مقاله میباشد. برای بدست آوردن میزان فعالیت نویسنده ها در زمینه های کاری مختلف میانگین درایه های متناظر در بردارهای موضوع مقالات منتشر شده توسط این نویسنده را محاسبه میکنیم و آنها را در برداری به نام بردار علاقمندی قرار میدهیم.

 پیش بینی لینک بر اساس میزان شباهت زمینه های کاری نویسندگان

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

در این فرمولB و Aبردارهای زمینه ی کاری دو نویسنده هستندKبرابر با تعداد موضوع ها میباشد. در ادامه طبق فرمول زیر به محاسبه ی میزان شباهت میان دو نویسنده با یکدیگر پرداخته میشود، که مشاهده می شود که از ترکیب معیار آدامیک آدار و شباهت کسینوسی بردارهای بدست آمده استخراج شده است:

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

نتایج

با توجه به نتایج بدست آمده، الگوریتم های آدامیک آدار و کتز از نتایج خوبی برخوردار هستند. در مقایسه ی روشهای پیشنهادی با سایر روشها می توان به این نتایج رسید که در دو نمودار زیر مشخص است:

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

منابع

ارائه یک بهبود برای الگوریتم پیش بینی لینک آدامیک آدار دکتر سید امید فاطمی، هیئت علمی، دانشگاه تهران حسنا سلیمان نژاد، دانشجوی فناوری اطلاعات، دانشگاه تهران