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

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

چکیده

شناخت هرچه بیشتر مکانیزم رفتاری انسان ها در شبکه ها، بر فهم ما از نحوه تکامل و رشد شبکه ها تاثیر بسزایی دارد. در یک شبکه آنلاین رفتار انسان ها را می توان همچون یک گراف دو بخشی user-object در نظر گرفت که در آن کاربران توسط لینک هایی به اشیا متصل هستند. پیشبینی لینک از روش هایی است که توسط آن می توان رفتار آینده افراد را پیشبینی کرد. در این مقاله پیش بینی لینک از دیدگاه تفکیک زمانی مورد بررسی قرار می گیرد. در تفکیک زمانی نشان می دهیم که دنباله پیمایشات هر فرد را می توان به چندین دنباله پیمایش با بازه زمانی مختلف تبدیل کرد. همچنین بحث سالخوردگی لینک ها را بیان می کنیم و تاثیر گذر زمان بر توانایی لینک ها برای پیش بینی لینک های آینده نشان خواهیم داد. از اطلاعات زمانی برای ساخت شبکه دو بخشی وزن دار زمانی (TWBN) استفاده می کنیم و سپس با استفاده از فیلترهای مشارکتی سعی در ساخت یک سیستم پیش بینی لینک خواهیم داشت.

تفکیک زمانی و ساخت گراف TWBN:

تفکیک زمانی:

کاربران در میان منابع موجود در سایت های اطلاعاتی به دنبال علایق خود می گردند. علایق کاربران در طول زمان تغییر می کند. سابقه پیمایش کاربران در واقع از زیر دنباله هایی تشکیل شده که هر کدان بیانگر علاقه کاربر در یک دوره خاصل است. در جدول 1 سابقه پیمایشات پنج کاربر شبکه نشان داده شده است. همانطور که می بینید دنباله پیمایشات کاربر از روز 3 شروع و تا روز 10 ادامه می یابد. در این بازه گاهی کاربر در مدت زمان محدودی چندین انتخاب داشته و سپس تا چندین روز بعد انتخاب دیگری ندارد. برای نمونه کاربر 1 از بازه زمانی 3 تا 4 سه انتخاب و از بازه 9 تا 10 دو انتخاب دارد. فاصله زمانی میان این دو بازه به 5 روز می رسد. مسلما آیتم های انتخاب شده توسط کاربر که در یک بازه بودند رابطه بیشتری نسبت به آیتم هایی که در بازه زمانی متفاوت بوده اند دارند. در شبکه های واقعی اختلاف این بازه ها بیشتر است. اگر بتوان آیتم های پیموده شده نزدیک به هم را تفکیک کرد بهتر می توان شباهت میان آنها را مشخص کرد. در این مقاله ما دنباله پیمایشات کاربران را به بازه های مختلف تفکیک می کنیم. برای تفکیک سازی پیمایشات اینگونه عمل می شود که اگر فاصله بین دو انتخاب متوالی کاربر از k روز بیشتر باشد. این امر نشان دهنده این است که کاربر علاقه اش عوض شده است. مثلا اگر k=5 در نظر بگیریم پیمایشات کاربر 1 به دو زیر پیمایش تقسیم می شود. بعد از تفکیک سازی سابقه پیمایشات هر کاربر به زیر دنباله های متناظر، از این زر دنباله ها برای ساخت سطرهای ماتریس پیمایش استفاده کنیم. (هر زیر دنباله یک سطر را نشان می دهد). ماتریس پیمایش A[m*n] از m کاربر و n آیتم تشکیل شده و درایه [i,j] این ماتریس مخالف صفر است اگر کاربر i، آیتم j را پیموده باشد. سطرهای این ماتریس دنباله پیمایشات کاربران را نشان می دهد. انتخاب اندازه K از اهمیت بالایی برخوردار است. اگر K خیلی کوچک باشد موجب می شود که ماتریس پیمایش تنگ شود. اگر K بزرگ باشد باعث می شود که تفکیک زمانی رخ ندهد. پیدا کردن مقدار مناسب برای K خیلی مهم است.

ساخت گراف TWBN

با گذشت زمان از ارش لینک موجود برای پیشبینی لینک های آینده کاسته می شود. هرچه فاصله شکل گیری یک لینک با زمان فعلی بیشتر باشد (لینک پیر) تاثیر آن در پیش بینی لینک های فعلی کمتر خواهئ بود و بلعکس/ برای اینکه تاثیر گذر زمان را بر لینکها مدل کنیم ما از فاصله زمانی در جهت وزن دار کردن لینک ها استفاده می کنیم. این وزن بیانگیر اهمیت لینک در پیش بینی لینک های آینده است. ما از فرمول ارائه شده در مقاله 6 به عنوان معیاری در جهت وزن دهی لینک ها استفاده می کنیم.

در اینجا Tu,i زمانی را که کاربر U، آیتم I را پیموده و Now Time زمان فعلی را بیان می کند. الگوریتم پیشگو باید بالهای موجود در زمان و Now Time را پیشبینی کند. ضریب تاثیر اختلاف زمانی است و مقدار ≥ 0 است. یک مقدار ثابت و مقدار آن <1   0< است. اگر زیاد باشد، i  و Wu بیشتر می شود. (تاثیر فاصله زمان کم خواهد شد). و بلعکس، هرچه توان بزگتر باشد مقدار Wu,i کوچکتر خواهد بود. در این مقاله ما مقدار را برابر با                       و =0.5 در نظر گرفته شده است.

ما از فرمول فوق برای وزن دهی بال های موجود در گراف استفاده می کنیم. نتیجه کار تشکیل گراف TWBN است.

فیلترهای مشارکتی:

یکی از موفق ترین رویکردها در بحث سیستم های پیش بینی لینک، فیلترهای مشارکتی (CF) هستند که با استفاده از تجربه وب سعی در پیشبینی لینک های آینده دارد. ایده اصلی CF این است که اگر دو کاربر x و y آیتم های مشابه ای را پیموده باشند امید است که در آینده عملکرد مشابه ای نیز داشته باشند. CF ها با استفاده از دیتا بیسی از پیمایشات قبلی کاربران سعی در پیشبینی عملکرد آینده کاربران جدید دارد. یکی گروهی از فیلترهای مشارکتی ها تکنیک های model- base CF هستند. این روش ها از ماتریس پیمایش کاربران برای ساخت یک مدل خاص بهره می جویند و سپس از این مدل برای پیشبینی عملکرد کاربران جدید استفاده می کند. مدل می تواند یک فرایند داده کاوی با یادگیری ماشین باشد. از نمونه های این روش می توان به Bayesian Belief net CF [16] و Clustering CF [14] و Item-base CF [18,17] اشاره کرد. در این مقاله ما از روش Item- base CF استفاده خواهیم کرد. ایده این روش بر این اصل استوار است که آیتم هایی که کاربر در آینده انتخاب می کند رابطه نزدیکی به آیتم هایی که او قبلا انتخاب کرده دارد. هرچه ارتباط میان یک آیتم با آیتم های پیموده شده قبلی کاربر بیشتر احتمال انتخاب آن بیشتر است. در این روش ماتریس مربعی I[n*n] ساخته می شود که درایه [I,j] آن شباهت آیتم i و j را نشان می دهد. برای سنجش میزان شباهت میان دو آیتم معیارهای متنوعی همچون کسینوس، فاصله اقلیدسی و همبستگی وحود دارد که ما از قانون همبستگی گیرسون استفاده می کنیم. این معیار وابستگی خطی میان دو متغیر را نشان می دهد. طبق این معیار، همبستگی (تغییرات همسو) میان دو متغیر تصادفی برابر است با

E عملگر امید ریاضی، cov کوواریانس، و نماد انحراف معیار استاندارد است. برای ساخت ماتریس I ما از ماترس مجاورت گراف TWBN استفاده می کنیم.

ارزیابی:

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

تفسیر آزمایش

همانطور که در شکل a.4 می بینید الگوریتم TWCF قادر بوده پیشبینی هایی با دقت بالاتری داشته باشد. این امر نشان دهنده این است که استفاده از تفکیک زمانی و بحث سالخوردگی لینکها توانسته تاثیر مثبتی در پشیبینی داشته باشد. نمودارها روندی نزولی دارند به این علت که هرچه اندازه مجموعه آموزش بیشتر می شود میزان پراکندگی ماتریس پیمایشات کمتر شده و در نتیجه شباهت میان آیتم ها بهتر تشخیص داده می شود. در جدول 2 مقادیر عددی ناشی از آزمایش نشان داده شده است .در شکل b.4 عملکرد الگوریتم ها بر حسب مقدار r نشان داده ایم. در این شکل محور افقی مقدار r و محور عمودی تعداد پیشبینی های درست را نشان می دهد. همانطور که می بینید روش پیشنهادی در مقایسه با دیگر الگوریتم ها از دقت بالاتری برخوردار است. روش های TWCF و TCF و CF همگی بر پایه همبستگی میان آیتم ها کار می کنند. در CF ما تاثیرات زمانی را در محاسبه همبستگی میان آیتم ها بکار نبردیم. در TCF ما تنها بحث سالخوردگی را در محاسبه همبستگی بکار بردیم و در TWCF ما هم بحث سالخوردگی و هم تفکیک زمانی را بکار بردیم و نشان دادیم که تفکیک زمانی موجب بهبود عملکرد می شود.

نتیجه گیری

در این مقاله ما از فیلترهای مشارکتی به منظور پیشبینی لینک استفاده کردیم. از تفکیک زمانی به عنوان ابزاری در جهت غنی سازی اطلاعات شبکه (استفاده از لینک های سیاه) استفاده شد. همچنین نشان دادیم که استفاده از تفکیک ها موجب بهبود عملکرد فیلترهای مشارکتی در پیشبینی لینک ها می شود. در تفکیک زمانی از معیار K استفاده کردیم. اگر K خیلی کوچک باشد موجب می شود که ماتریس پیمایش تنگ شود. اگر Kبزرگ باشد باعث می شود که تفکیک زمانی رخ ندهد. پیدا کردن K مناسب برای هر دیتاست از اهمیت بالایی برخوردار است. همچنین در این مقاله ما از بحث سالخوردگی لینک ها استفاده کردیم. تابعی برای مشخص کردن وزن لینک ها بر حسب زمان ارائه شد که دارای پارامتر کنترلی بود. اگر زیاد باشد تاثیر فاصله زمان کم خواهد شد و بلعکس. اگر تاثیر فاصله زمانی را خیلی زیاد یا خیلی کم درنظر بگیریم موجب کاهش عملکرد خواهیم شد.