دانشکده آموزشهای الکترونیکی
پایاننامه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات
(مدیریت سیستمهای اطلاعاتی)
ارائه مدلی برای سیستمهای توصیه گر در شبکه های مبتنی بر اعتماد
توسط :
هومن رفعت صفایی
استاد راهنما :
دکتر ستار هاشمی
شهریور ماه 1392
به نام او که هرچه هست از اوست
به نام خدا
ارائه مدلی برای سیستمهای توصیهگر در شبکههای مبتنی بر اعتماد
به وسیلهی :
هومن رفعت صفایی
پایان نامه
ارائه شده به تحصیلات تکمیلی دانشگاه به عنوان بخشی
از فعالیتهای تحصیلی لازم برای اخذ درجه کارشناسی ارشد
در رشته :
مهندسی فناوری اطلاعات – مدیریت سیستمهای اطلاعاتی
از دانشگاه شیراز
شیراز
جمهوری اسلامی ایران
ارزیابی شده توسط کمیته پایاننامه با درجه :
دکتر ستار هاشمی، استادیار بخش مهندسی و علوم کامپیوتر (رئیس کمیته) ……………………………
دکتر منصور ذوالقدری جهرمی، استاد بخش مهندسی و علوم کامپیوتر …………………………………..
دکتر اقبال منصوری، استادیار بخش مهندسی و علوم کامپیوتر …………………………………………………..
شهریور ماه 1392
به نام خدا
اظهارنامه
اینجانب هومن رفعت صفایی دانشجوی رشتهی مهندسی فناوری اطلاعات گرایش مدیریت سیستمهای اطلاعاتی دانشکدهی آموزشهای الکترونیکی اظهار میکنم که این پایان نامه حاصل پژوهش خودم بوده و در جاهایی که از منابع دیگران استفاده کردهام، نشانی دقیق و مشخصات کامل آن را نوشتهام. همچنین اظهار میکنم که تحقیق و موضوع پایان نامهام تکراری نیست و تعهد مینمایم که بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده یا در اختیار غیر قرار ندهم. کلیه حقوق این اثر مطابق با آیین نامه مالکیت فکری و معنوی متعلق به دانشگاه شیراز است.
نام و نام خانوادگی : هومن رفعت صفایی
تاریخ و امضا :
تقدیم به
همسر و فرزند عزیزم، که همواره و در همه حال، انگیزه و امید من به زندگی و ادامه تحصیل بوده و هستند.
سپاسگزاری
از خداوند متعال به سبب الطاف و نعمات بیدریغش و ارزانی داشتن نعمت و فرصت آموختن سپاسگذاری میکنم و در ادامه از استاد راهنمای گرانقدر جناب آقای دکتر هاشمی که در طی مراحل انجام پایاننامه همواره مشوق و یاری دهنده اینجانب بودهاند کمال تشکر و قدردانی میگردد .
همچنین از اساتید گرانقدر، جناب آقایان دکتر ذوالقدری و دکتر منصوری که بر اینجانب منت نهاده و اساتید مشاور بنده در این رساله بودهاند، سپاسگزاری مینمایم.
چکیده
ارائه مدلی برای سیستمهای توصیهگر در شبکههای مبتنی بر اعتماد
به کوشش
هومن رفعت صفایی
امروزه با گسترش و رشد روز افزون اطلاعات در فضای مجازی و وجود انبوهی از کالا یا خدماتی که در وب سایتهای تجاری و خدماتی ارائه میگردند کاربران را با این مشکل مواجه نموده است که چگونه کالا یا خدمت مورد نظر خود را به راحتی و با صرف کمترین زمان ممکن بیابند. در این میان سیستمهای توصیهگر با هدف تسهیل و یاری رساندن به کاربران در زمینه انتخاب و یافتن کالای مورد نیاز ایشان با استفاده از علوم و روشهای مبتنی بر داده کاوی اطلاعات، ایجاد و توسعه یافتهاند. همچنین در سالهای اخیر ظهور و گسترش شبکههای اجتماعی و شبکههای مبتنی بر رابطه اعتماد میان کاربران، باعث گشوده شدن افق جدیدی در ارائه سیستمهای توصیهگر و توسعه نسل جدیدی از اینگونه سیستمها گردیده است و آنرا به یکی از موضوعات جذاب و مورد توجه محققان تبدیل نموده است.
از میان روشها و مدلهای موجود در زمینه سیستمهای توصیهگر روش پالایش گروهی به لحاظ سادگی پیادهسازی از محبوبیت قابل ملاحظهای برخوردار است اما این روش در ارائه پیشنهادات مناسب و قابل قبول به کاربران تازه وارد دارای ضعفهای جدی میباشد. سیستمهای توصیهگر مبتنی بر اعتماد، با بهرهگیری از رابطه اعتماد میان کاربران، در جهت رفع نقاط ضعف بیان شده و خصوصا ارائه پیشنهادات مناسب به کاربران تازه وارد گامهای موثری برداشتهاند. در این تحقیق سعی شده است تا از تلفیق و ترکیب روشهای موجود در زمینه پالایش گروهی و همچنین مدلهای مبتنی بر اعتماد و بررسی نقاط ضعف و قوت آنها مدلی نوین و توسعه یافته ارائه گردد که در آن نتایج از خطای کمتر و دقت بالاتری برخوردار بوده و با افزایش معیار پوشش بتوان به درصد بیشتری از کاربران پاسخ مناسب ارائه نمود. برای این منظور در میان انواع روشهای پالایش گروهی، روش مبتنی بر آیتم و برای پیمایش شبکه اعتماد میان کاربران نیز از روش پیمایش تصادفی بهره گرفته شده است، همچنین با تفسیر و تعدیل نظرات کاربران و اتخاذ شیوهای مناسب جهت محاسبه مقدار دقیق اعتماد میان کاربران و تغییر در نحوه پیمایش شبکه اعتماد میان ایشان سعی در بهبود و کاهش خطاهای نتایج گردیده است. در نهایت، جهت ارزیابی و برآورد مدل ترکیبی ارائه شده، نتایج و آمارهای حاصل از اجرای مدل پیشنهادی بر روی مجموعه داده های Epinions و Movielens و مقایسه آنها با نتایج مدل پایه TrustWalkerبه عنوان یکی از بهترین مدلهای ترکیبی ارائه شده در زمینه سیستمهای توصیه گر مبتنی بر اعتماد، ارائه میگردد.
واژههای کلیدی: دادهکاوی1، شبکههای اجتماعی2، شبکههای مبتنی بر اعتماد3، سیستمهای توصیهگر4، پالایش گروهی5، اعتماد6، پیمایش تصادفی7، ترکیب سازی8
فهرست مطالب
عنوان…………………………………………………………………………………………………………….صفحه
فصل اول : مقدمهای بر انواع سیستم توصیهگر…………………………………………………1
1-1- مقدمه…………………………………………………………………………………………………………………..2
1-2- سیستمهای توصیهگر…………………………………………………………………………………………..3
1-3- انواع سیستمهای توصیهگر از لحاظ عملکردی……………………………………………………4
1-4- مزایا و اهمیت یک سیستم توصیهگر کارآمد………………………………………………………5
1-5- معایب و مشکلات کلی سیستمهای توصیهگر……………………………………………………..6
1-6- انواع رویکردها و مدلهای موجود در زمینه پیادهسازی سیستمهای توصیهگر…….7
1-7- تشریح و بیان مسئله………………………………………………………………………………………….11
1-8- اهداف تحقیق…………………………………………………………………………………………………….12
1-9- سوالات و فرضیههای تحقیق…………………………………………………………………………….13
1-10- مراحل تحقیق…………………………………………………………………………………………………14
1-11- فصول پایان نامه……………………………………………………………………………………………..15
فصل دوم : مروری بر ادبیات تحقیق و مبانی نظری تحقیق………………………………17
2-1- مقدمه ……………………………………………………………………………………………………………….18
2-2- پالایش گروهی (Collaborative Filtering)…………………………………………….19
2-2-1- پالایش گروهی مبتنی بر حافظه(Memory Based)……………………………..20
2-2-1-1- روش پالایش گروهی مبتنی بر آیتم ………………………………………………………22
2-2-1-2- امتیازدهی به صورت پیش فرض……………………………………………………………..24
2-2-1-3- تشدید حالت(Case Amplification)……………………………………………….24
2-2-2- پالایش گروهی مبتنی بر مدل(Model Based)……………………………………..25
2-3- پالایش محتوایی (Content Based Filtering) ………………………………………26
2-4- تکنیکهای ترکیبی……………………………………………………………………………………………..27
2-5- سیستمهای توصیهگر مبتنی بر رابطه اعتماد میان کاربران……………………………..28
2-5-1- چگونگی کارکرد سیستم توصیهگر مبتنی بر اعتماد……………………………………30
2-5-2- مزایا و معایب………………………………………………………………………………………………..31
2-5-3- انتشار اعتماد و تجمیع اعتماد………………………………………………………………………33
2-6- چالش ها و محدودیتهای موجود………………………………………………………………………33
2-6-1- نقصان و کاستی اطلاعات……………………………………………………………………………..34
2-6-2- مشکل کاربران تازه وارد………………………………………………………………………………..34
2-6-3- کلاهبرداری و تقلب………………………………………………………………………………………35
2-6-4- پیچیدگیهای محاسباتی و زمانی…………………………………………………………………..36
2-7- معیارهای ارزیابی سیستمهای توصیهگر……………………………………………………………37
2-7-1- خطای جذر میانگین مربعات (RMSE)…………………………………………………….37
2-7-2- معیار درصد پوشش………………………………………………………………………………………38
2-7-3- معیار دقت…………………………………………………………………………………………………….39
2-7-4- معیار F-Measure…………………………………………………………………………………….39
فصل سوم : مروری بر مطالعات و تحقیقات پیشین…………………………………………..41
3-1- مقدمه………………………………………………………………………………………………………………..42
3-2- مرور کارهای گذشته………………………………………………………………………………………….42
3-2-1- مدل MoleTrust………………………………………………………………………………………45
3-2-2- مدل TidalTrust………………………………………………………………………………………47
3-2-3- مدل دانه سیب……………………………………………………………………………………………..48
3-2-4- مدل ارائه شده توسط Anderson……………………………………………………………48
3-2-5- مدل ارائه شده توسط O’Donovan………………………………………………………..49
3-2-6- مدل TrustWalker………………………………………………………………………………….50
3-2-6-1- ساختار مدل TrustWalker…………………………………………………………………51
3-2-6-2- تشابه آیتم ها……………………………………………………………………………………………51
3-2-6-3- خصوصیات ویژه مدل TrustWalker…………………………………………………..52
3-2-6-3-1- فراگیری و عمومیت مدل…………………………………………………………………….52
3-2-6-3-2- اطمینان به نتایج حاصل………………………………………………………………………53
3-2-6-3-3- تفسیرپذیری و قابل توضیح بودن نتایج………………………………………………54
3-2-6-4- نمایش ماتریسی مدل TrustWalker………………………………………………….54
3-2-6-5- نتیجه گیری در خصوص مدل TrustWalker…………………………………….55
فصل چهارم : تشریح مدل ترکیبی پیشنهادی و چگونگی توسعه و بهبود مدل پایه.56
4-1- مقدمه………………………………………………………………………………………………………………..57
4-2- تشریح مدل کلی TrustWalker…………………………………………………………………..57
4-2-1- علائم نشانه گذاری و متغیرهای مدل…………………………………………………………..57
4-2-2- روند یک پیمایش تصادفی در شبکه…………………………………………………………….58
4-2-3- انتخاب تصادفی یک کاربر …………………………………………………………………………..59
4-2-4- انتخاب یک آیتم مشابه…………………………………………………………………………………59
4-2-5- تشابه آیتم ها…………………………………………………………………………………………………60
4-2-6- محاسبه احتمال ماندن در یک گره شبکه اعتماد (∅_(u,i,k))………………………..61
4-2-7- چگونگی انجام پیشبینی امتیاز……………………………………………………………………62
4-2-8- چگونگی محاسبه احتمال P(XY_(u,i)=(v,j))………………………………………….63
4-2-9- چگونگی محاسبه عملی r ̂_(u,i)……………………………………………………………………….64
4-2-10- شرط اتمام کلی مدل………………………………………………………………………………….64
4-3- بهبود و توسعه مدل TrustWalker………………………………………………………………65
4-3-1- استفاده از فرمول jaccard جهت محاسبه تشابه آیتمها…………………………….66
4-3-2- حذف میانگین از فرمول پیرسون………………………………………………………………….67
4-3-3- استفاده از تکنیک مبتنی بر آیتم خالص………………………………………………………67
4-3-4- تعدیل و تفسیر نظرات کاربران……………………………………………………………………..68
4-3-5- محاسبه دقیق مقدار اعتماد یا امتیاز رابطه میان دو کاربر…………………………..71
4-3-6- محاسبه ترکیبی امتیاز رابطه میان کاربران………………………………………………….73

فصل پنجم : تشریح روند انجام آزمایشات و نتایج حاصل………………………………76
5-1- مقدمه………………………………………………………………………………………………………………..77
5-2- معرفی مجموعه داده epinions……………………………………………………………………..77
5-2-1- ویژگیهای مجموعه داده epinions……………………………………………………………79
5-2-2- آماده سازی و نحوه پالایش دادهها……………………………………………………………….81
5-2-3- ایجاد مجموعه داده نمونه……………………………………………………………………………..83
5-3- مجموعه داده movielens……………………………………………………………………………..84
5-3-1- ویژگیهای مجموعه داده movielens………………………………………………………..84
5-4- نیازمندیهای نرم افزاری…………………………………………………………………………………….85
5-5- نیازمندیهای سخت افزاری………………………………………………………………………………..85
5-6- متدولوژی نرم افزاری…………………………………………………………………………………………86
5-7- پارامترهای پیش فرض انجام آزمایشات…………………………………………………………….86
5-8- نتایج اجرای آزمایشات با مجموعه داده epinions و movielens……………..87
5-8-1- بررسی تاثیر عمق پیمایش بر روی نتایج حاصل در خصوص کاربران تازه وارد……………………………………………………………………………………………………………………………….87
5-8-2- بررسی تاثیر تاریخ اعلام نظرات توسط کاربران……………………………………………88
5-8-3- بررسی تاثیر تغییر فرمول محاسبه تشابه آیتمها………………………………………….89
5-8-4- بررسی تاثیر بکارگیری مکانیزم تفسیر و تعدیل نظرات کاربران………………….90
5-8-5- بررسی تاثیر بکارگیری انواع روشهای ترکیبی برای انتخاب کاربران و پیمایش شبکه…………………………………………………………………………………………………………………………….93
5-8-5-1- نحوه محاسبه امتیاز رابطه موجود میان کاربران……………………………………..93
5-8-5-2- بررسی تاثیر بکارگیری روشهای ترکیبی در عملکرد سیستم برای تمامی کاربران………………………………………………………………………………………………………………………….94
5-8-5-3- بررسی تاثیر بکارگیری روشهای ترکیبی در عملکرد سیستم برای کاربران تازه وارد ………………………………………………………………………………………………………………………99
5-8-6- بررسی تاثیر بکارگیری توام مکانیزم تفسیر امتیازات کاربران به همراه استفاده از روشهای ترکیبی انتخاب کاربران و پیمایش شبکه اعتماد……………………………………101
5-9- انجام آزمایشات با مجموعه داده movielens……………………………………………..107
5-9-1- نتایج حاصل از اجرای روشهای ترکیبی مورد استفاده در مدل توسعه یافته…………………………………………………………………………………………………………………………..107
فصل ششم : نتیجه گیری نهایی و کارهای آینده…………………………………………….110
6-1- مقدمه………………………………………………………………………………………………………………111
6-2- عملکرد مدل توسعه یافته……………………………………………………………………………….112
6-2-1- عملکرد مدل توسعه یافته در خصوص تمامی کاربران………………………………112
6-2-2- عملکرد مدل توسعه یافته در خصوص کاربران تازه وارد…………………………..114
6-3- نتیجه گیری نهایی …………………………………………………………………………………………115
6-3-1- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده epinions………………………………………………………………………………………………………………..116
6-3-2- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده movielens…………………………………………………………………………………………………………….118
6-4- پیشنهادات کارهای آینده……………………………………………………………………………….118
اختصارات…………………………………………………………………………………………………..120
فهرست منابع……………………………………………………………………………………………..121
فهرست جداول
عنوان………………………………………………………………………………………………………………….صفحه
جدول 3-1 : دستهبندی مدلهای اعتماد…………………………………………………………………………………..44
جدول 4-1 : ماتریس پراکندگی نحوه امتیازدهی دو کاربر u_1 و u_2……………………………………70
جدول 4-2 : تفسیر نظرات کاربر u_2……………………………………………………………………………………..70
جدول 5-1 : ساختار جدول reviews……………………………………………………………………………………81
جدول 5-2 : ساختار جدول WOT…………………………………………………………………………………………82
جدول 5-3 : ساختار جدول cold_start_users………………………………………………………………..82
جدول 5-4 : ساختار جدول ratings………………………………………………………………………………………83
جدول 5-5 : مقادیر پیش فرض پارامترها و متغیرهای مورد استفاده در مدل پیشنهادی………86
جدول 5-6 : نتایج بررسی تاثیر عمق پیمایش در خصوص کاربران تازه وارد………………………….88
جدول 5-7 : نتایج حاصل از بررسی تاثیر تاریخ اعلام نظرات کاربران……………………………………..89
جدول 5-8 : نتایج حاصل از تغییر فرمول محاسبه تشابه آیتمها…………………………………………….90
جدول 5-9 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران…………………….91
جدول 5-10 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران در خصوص کاربران تازه وارد…………………………………………………………………………………………………………………………91
جدول 5-11 : نتایج حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه……………………………………………………………………………………………………………………………………………..96
جدول 5-12 : نتایج حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد…………………………………………………………………………………………………………99
جدول 5-13 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………102
جدول 5-14 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد…………………………………………………………………………………………………………………………………………..104
جدول 5-15 : نتایج حاصل از اجرای روشهای ترکیبی انتخاب کاربران و پیمایش شبکه……107
جدول 5-16 : نتایج حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روشهای ترکیبی انتخاب کاربران و پیمایش شبکه…………………………………………………………………108
جدول 6-1 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه …………………………………………………………………………………………………………………………………………………113
جدول 6-2 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه در خصوص کاربران تازه وارد………………………………………………………………………………………………………..114
فهرست اشکال و نمودارها
عنوان………………………………………………………………………………………………………………….صفحه
شکل 2-1 : چگونگی کارکرد روش پالایش گروهی (Collaborative Filtering)……………20
شکل 2-2 : نمایش یک شبکه اعتماد به همراه امتیازات بیان شده توسط کاربران در خصوص آیتمهای مختلف…………………………………………………………………………………………………………………………31
شکل 3-1 : معماری مدل MoleTrust ارائه شده توسط Massa……………………………………….46
شکل 5-1 : بنر صفحه اصلی سایت epinions………………………………………………………………………78
نمودار 5-1 : مقایسه نتایج خطای RMSE و درصد پوشش مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران ……………………………………………………………………………………………………………………………………………………92
نمودار 5-2 : مقایسه نتایج معیارF-measure مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران…………93
نمودار 5-3 : مقایسه نتایج معیاردرصد پوششحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………97
نمودار 5-4 : مقایسه نتایج خطای RMSEحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………98
نمودار 5-5 : مقایسه نتایج معیار F-measureحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه……………………………………………………………………………………………….98
نمودار 5-6 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..100
نمودار 5-7 : مقایسه نتایج خطای RMSE حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………….100
نمودار 5-8 : مقایسه نتایج معیار F-measureحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..101
نمودار 5-9 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..103
نمودار 5-10 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه …………………………………………………………………………………………………………………………………………………103
نمودار 5-11 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..104
نمودار 5-12 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………105
نمودار 5-13 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد……………………………………………………………………………………………………………..106
نمودار 5-14 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………106
نمودار 5-15 : مقایسه نتایج خطای RMSE حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روشهای ترکیبی انتخاب کاربران و پیمایش شبکه………………..109
نمودار 6-1 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه از نظر تمام معیارهای ارزیابی……………………………………………………………………………………………………………………………………..113
نمودار 6-2 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه برای کاربران تازه وارد از نظر تمام معیارهای ارزیابی………………………………………………………………………………………………….115
فصل اول
مقدمه ای بر انواع سیستمهای توصیهگر
1- مقدمهای بر انواع سیستمهای توصیهگر
1-1- مقدمه
گسترش سریع و روز افزون اطلاعات ارائه شده بر روی شبکه جهانی اینترنت، کاربران را با مشکلات عدیده و قابل تاملی در خصوص انتخاب منابع و اطلاعات مورد نیاز ایشان مواجه نموده است و چه بسا که بدون راهنمایی و هدایت صحیح، کاربران در اخذ تصمیمات صحیح یا انتخاب کالا و خدمات مورد نیازشان دچار اشتباه شده که این امر تبعات عدیدهای از جمله نارضایتی، سلب اطمینان کاربران و مشتریان سایتهای موجود بر روی اینترنت را به همراه خواهد داشت. از اینرو وجود ابزار و سیستمهایی برای کمک به کاربران در انتخاب اطلاعات مناسب و مورد نیاز ایشان کاملا ضروری به نظر میرسد. در سالهای اخیر برای برآورده سازی این نیازها سیستمهای توصیهگرمطرح و توسعه یافتهاند و الگوریتمها ، مقالات و متون علمی بسیار متنوع و مختلفی در این زمینه مطرح گردیده است .
در این میان، ایجاد و گسترش شبکههای اجتماعی، شبکههای اعتماد و وجود انواع روابط میان کاربران این شبکهها افق جدیدی را برروی محققان و توسعه دهندگان سیستمهای توصیهگر گشوده است تا با بهرهگیری از علوم اجتماعی و علوم روان شناختی حاکم در این شبکهها و خصوصا وجود رابطه اعتماد میان کاربران بتوانند نسل جدیدی از سیستمهای توصیهگر را تحت عنوان “سیستمهای توصیهگر مبتنی بر اعتماد9″معرفی و عرضه نمایند. این سیستمها قادر هستند تا به درصد بیشتری از کاربران پاسخ مناسب را ارائه دهند و همچنین نتایج آنها از دقت بالاتری برخوردار میباشد.
با توجه به کثرت کاربران و افراد عضو شبکههای مبتنی بر اعتماد و شبکههای اجتماعی، همچنین تنوع رفتار و ویژگیهای ایشان، تنها یک شیوه یا یک مدل قادر به پاسخگویی و ارائه پیشنهادات دقیق و قابل قبول نمیباشد که این امر باعث ظهور سیستمهای توصیهگر ترکیبی10گردیده است. در این سیستمها سعی شده است تا با ترکیب انواع مختلفی از سیستمهای توصیهگر بتوان سیستمی تولید نمود که دارای مزایای حداکثری و معایب حداقلی باشد.
در این پایاننامه سعی شده است تا با تغییر، اصلاح، تلفیق و ترکیب تعدادی از روشها و الگوریتمهای مطرح و قابل قبول در سطح جهانی، مدلی ارائه گردد که نسبت به مدلهای پیشین دارای دقت و درصد پوشش بالاتری باشد و همچنین بتواند نقایص مدلهای پیشین خصوصا در رابطه با ارائه پیشنهاد به کاربران تازه وارد11 را تا حد قابل قبولی مرتفع نماید.
1-2- سیستمهای توصیهگر
تعاریف متفاوتی برای سیستم‌های توصیه‌گر ارائه شده‌است. عدهای از محققان سیستمهای توصیهگر را زیرمجموعه‌ای از سیستمهای تصمیمیار12 می‌دانند و آنها را سیستم‌های اطلاعاتی13 تعریف می‌کنند که توانایی تحلیل رفتارهای گذشته و ارائه توصیه‌هایی برای مسائل جاری را دارا میباشند[1]. به زبان ساده‌تر در سیستم‌های توصیه‌گر تلاش بر این است تا با حدس زدن شیوه تفکر کاربر به کمک اطلاعاتی که از نحوه رفتار وی یا کاربران مشابه و نظرات آنها داریم مناسب‌ترین و نزدیک‌ترین کالا یا خدمت به سلیقه او را شناسایی و پیشنهاد کنیم. این سیستم‌ها در حقیقت سعی دارند فرایندی را که ما در زندگی روزمره خود بکار می‌بریم و طی آن تلاش می‌کنیم تا افرادی با سلایق نزدیک به خود را پیدا کرده و از آنها در مورد انتخاب‌هایمان نظر بخواهیم را شبیه سازی نمایند.
به صورت کلیتر سیستمهای توصیهگر زیر مجموعهای از سیستمهای پالایش اطلاعات14هستند که وظیفه آنها جستجو برای بیان پیشبینی امتیاز(درجه)15 یا بیان سلایق و ترجیحات16 یک کاربر در خصوص یک موضوع17 ( مانند موسیقی، کتاب یا فیلم) یا یک عنصر اجتماعی مانند افراد و گروهها میباشد[2]–[4].
1-3- انواع سیستمهای توصیهگر از لحاظ عملکردی
سیستمهای توصیهگر به لحاظ نحوه ارائه نتایج و پیشنهادات به کاربران خود، به شیوه های متفاوتی عمل می نمایند که در ذیل به پارهای از آنها به صورت فهرست وار اشاره میگردد:
پیشنهاد لیستی متشکل از n کالا یا محصول برتر (معمولا n برابر 10 است )
پیشنهادات فصلی و موردی مانند پیشنهاد یک هتل دارای تخفیف جهت تعطیلات
بیان درصد علاقهمندی سایر کاربران به یک محصول خاص، به عنوان مثال: “80 درصد کاربران از خرید این محصول راضی بوده اند ”
پیش بینی میزان امتیازی که یک کاربر به یک محصول خاص خواهد داد
در این تحقیق سعی در ایجاد مدلی است که بتواند نظر و امتیاز تخصیص داده شده توسط یک کاربر خاص به یک محصول یا آیتم خاص را پیشبینی نماید.
1-4- مزایا و اهمیت یک سیستم توصیهگر کارآمد
طبق آمار رسمی ارائه شده توسط سایت فروش کتاب Amazon18 ، 35 درصد از فروش این سایت به واسطه وجود سیستم توصیهگر و ارائه پیشنهادات مناسب به علاقهمندان کتاب می باشد[5] همچنین سایت اجاره فیلم Netflix برای بهبود 10 درصدی دقت سیستم توصیهگر خود موسوم به Cinematch19جایزه ای بالغ بر یک میلیون دلار برای محققان در نظر گرفته است. هر دو مثال فوق نشان دهنده اهمیت سیستمهای توصیهگر و نقش آنها در تجارت میباشد. در ذیل تعدادی از دلایل اهمیت وجود یک سیستم توصیهگر مناسب و کارآمد در یک سایت تجارت الکترونیک برشمرده میگردد:
راهنمایی کاربران و بازدید کنندگان در انتخاب کالا ، محصول یا خدمت مناسب
تسریع در زمان انتخاب کالای مورد نظر مشتری مانند انتخاب یک فیلم مناسب در میان میلیونها فیلم موجود در سایت
جمعآوری اطلاعات ارزشمند در خصوص سلایق و رفتار کاربران جهت برنامهریزیهای آتی
جذب مشتریان و بازدید کنندگانی که برای اولین بار است از سایت بازدید میکنند
افزایش میزان رضایتمندی کاربران و طبیعتا افزایش سود سرمایه گذاران تجاری
ایجاد احساس اطمینان در مشتری با ارائه آمار نظرات سایر کاربران
بهبود معیارهای سنجش رتبه و درجه پورتال یا سایت
توجه به جنبههای روانشناختی کاربران
افزایش آگاهی کاربر در زمینه مورد علاقه وی
1-5- معایب و مشکلات کلی سیستمهای توصیهگر
در مقابل مزایای بیان شده، این سیستمها دارای نواقص و محدودیتهایی نیز می باشند که در ذیل به پاره ای از آنها اشاره میشود:
عدم امکان بررسی همه جانبه مشخصات کاربران و عدم ارائه یک جواب کاملا منطبق و سازگار با نظر ایشان
عدم اطمینان مشتریان به نظرات و پیشنهادات ارائه شده توسط سیستم
عدم وجود دقت مطلوب در پیشنهادات ارائه شده توسط سیستم
عدم پاسخگویی در برخی شرایط خاص، خصوصا در مورد کاربران تازه وارد یا مشتریان جدید (در فصل آینده در خصوص این مورد توضیحات کاملتری ارائه میگردد)
مشکلات فنی و موانع عدیدهای نیز در خصوص پیادهسازی و ارائه الگوریتم برای سیستمهای توصیهگر وجود دارد که پارهای از آنها عبارتند از:
پیادهسازی این سیستمها به دلیل وجود فاکتورهای بسیار متعدد و تاثیرگذار بر روی روند تصمیمگیری مکانیزه، بسیار پیچیده میباشد.
وجود امکان نفوذ متجاوزان و کلاهبرداران به اینگونه سیستمها و ایجاد دادههای غیرصحیح در سیستم، که ممکن است نتیجه خروجی سیستم را به نحوی تغییر یا منحرف نمایند.
پیچیدگی زمانی الگوریتمهای موجود و سرعت پاسخگویی کند این سیستمها خصوصا در ارائه پیشنهادات برخط20
پیچیدگی پیادهسازی الگوریتمهای موجود در این زمینه به لحاظ برنامهنویسی و مباحث نرمافزاری
وجود مشکلات عدیده در خصوص مدیریت دادههای بسیار سنگین و گاها به صورت توزیعشده21
پیچیدگیهای ناشی از وجود یک شبکه گرافی بسیار حجیم و درهم با تعداد گرههای بسیار زیاد خصوصا در مورد شبکههای اجتماعی
عدم وجود امکانات زمانی و سختافزاری در زمینه بررسی کل شبکههای مبتنی بر اعتماد برای یافتن بهترین جواب و با بالاترین دقت ممکن(به عنوان مثال اجرای برخی از الگوریتمها ممکن است چندین روز به طول بیانجامد)
1-6- انواع رویکردها و مدلهای موجود در زمینه پیادهسازی سیستمهای توصیهگر
در سالهای اخیر شیوهها، رویکردها، الگوریتمها و مدلهای متنوع و گوناگونی در زمینه توسعه انواع سیستمهای توصیه گر مطرح گردیده است که از ابعاد مختلف و با نگاههای متفاوتی به مسئله ارائه پاسخ و پیشنهاد مناسب به کاربران پرداختهاند که در این میان، پارهای از مهمترین و معروفترین روشهای موجود به اختصار معرفی میگردند.
یکی از متداولترین شیوه های مطرح”پالایش گروهی”میباشد[6]. این شیوه با جمعآوری و آنالیز دادههای موجود در مورد رفتار گذشته کاربران، فعالیتهای ایشان، سلایق آنها و امتیازاتی که به آیتمهای مختلف توسط ایشان داده شده است و همچنین بر اساس تشابه کاربران یا موضوعات با یکدیگر، مدلی ایجاد مینماید و سپس از آن مدل برای پیشبینی آیتمهای مورد علاقه کاربر یا پیشبینی امتیازدهی یک کاربر به یک آیتم خاص استفاده مینماید[7]. یکی دیگر از شیوههای موجود در این زمینه “پالایش محتوایی22” میباشد که در این شیوه، مجموعهای از خصوصیات یک آیتم، برای پیشنهاد آیتمهای جدید با خصوصیات مشابه با آن مورد استفاده قرار میگیرد[8]. از هر دو روش فوق نسخههایی نیز به صورت تجاری پیادهسازی شده است که به عنوان مثال سیستم توصیهگر موسیقی بکار رفته در سایت Last.fm23 بر اساس شیوه پالایش محتوایی پیادهسازی شده است در حالیکه در سایت 24PandoraRadio از شیوه پالایش گروهی استفاده شده است.
یکی دیگر از شیوههای موجود درخصوص تولید سیستمهای توصیهگر، ترکیب هر دو رویکرد فوق تحت عنوان “سیستمهای توصیهگر ترکیبی” میباشد[4]. مطالعات اخیر نشان داده است که در برخی موارد استفاده از ترکیب هر دو شیوه میتواند نتایج موثرتری را ایجاد نماید. این ترکیب میتواند در اشکال و انواع مختلفی صورت گیرد که هر کدام نتایج خاصی را تولید مینمایند[9]. تحقیقات نشان داده است که ترکیب این دو شیوه می تواند برخی از مشکلات هر کدام از روشها را برطرف نموده و نتایج با دقت بالاتری ایجاد نماید، به عنوان مثال، سیستم توصیهگر ایجاد شده در سایتNetflix25 از یک سیستم ترکیبی بهره میبرد که در آن عادات مشاهده فیلم، توسط کاربران مشابه (شیوه پالایش گروهی)، در کنار ارائه فیلمهایی که به لحاظ مشخصات، مشابه فیلمهایی هستند که توسط کاربر امتیاز بالاتری اخذ نمودهاند (شیوه پالایش محتوایی) در نظر گرفته شده است.
با ظهور شبکههای اجتماعی و شبکههای مبتنی بر اعتماد، رویکردها و ایدههای جدیدی در خصوص ایجاد و بهبود سیستمهای توصیهگر، با توجه به ارتباطات میان کاربران و به صورت خاص، وجود رابطه اعتماد میان آنها مطرح گردیدکه منجر به تولید سیستمهای توصیه گر مبتنی بر اعتماد شده است[10].
یک شبکه اجتماعی در واقع یک ساختار اجتماعی متشکل از مجموعهای از بازیگران (شامل کاربران و سازمان آنها) و ارتباطات دوتایی میان این عناصر میباشد[11] که به عنوان نمونه برجستهای از آن می تواند به شبکه اجتماعی facebook اشاره نمود. این ارتباطات میتواند در قالب انواع گوناگون یا بر اساس معیارهای مختلفی مانند: قیمتها، تبادلات مالی، دوستی، خویشاوندی، تجارت، سرایت بیماری یا مسیرهای هواپیمایی و غیره بیان گردند[12]. بررسی ابعاد و زوایای مختلف یک شبکه اجتماعی روش مشخصی برای آنالیز و تحلیل ساختار کلیه عناصر تشکیل دهنده آنرا فراهم میکند. مطالعه این ساختارها از روش “آنالیز شبکه اجتماعی” برای شناسایی الگوهای محلی و سراسری ، یافتن عناصر و موجودیتهای تاثیرگذار در شبکه و بررسی دینامیک شبکه استفاده مینماید[13]. شبکههای اجتماعی و تحلیل آنها یکی از موضوعات میان رشتهای است که به صورت آکادمیک در حوزههای روانشناسی اجتماعی، جامعه شناسی، آمار و تئوری گراف مطرح میباشد.
از دیدگاه تئوری گراف[14] یک شبکه اجتماعی متشکل از تعدادی گره و یال میباشد که گرهها در واقع همان افراد، سازمانها و گروهها میباشند و یالها نیز بیانگر رابطه میان هر دو گره موجود در این گراف میباشند. نکته حائذ اهمیت، پیچیدگی این گرافها به لحاظ تعداد بسیار زیاد گرهها و همچنین یالهای میان آنها میباشد.
یکی از انواع خاص شبکههای اجتماعی وجود یک شبکه مبتنی بر اعتماد میان کاربران میباشد که در آن کاربران عقیده و نظر خود در خصوص اعتماد به دیگران را صراحتا و آشکارا بیان می نمایند و این اعتماد را در قالب امتیازی که به افراد مختلف می دهند بیان میکنند[15]. یک شبکه مبتنی بر اعتماد در واقع یک گراف جهتدار است که میتواند متمایز کننده آن از یک شبکه اجتماعی گردد. گرهها کاربران میباشند و یالهای گراف بیانکننده وجود رابطه اعتماد میان دو کاربر میباشند[16]. به عنوان مثال می توان به سایت Epinions26 اشاره نمود. این سایت تجارت الکترونیک27 مثال بارزی از شبکه مبتنی بر اعتماد می باشد که در آن کاربران در خصوص محصولات، نظرات خود را مطرح می نمایند و می توانند برای محصولات یا نظر سایر کاربران امتیازی در محدوده 1 تا 5 را انتخاب نمایند. نکته مهم در خصوص این سایت این است که کاربران می توانند بر اساس کیفیت و تشابه نظر سایر افراد با خودشان، ایشان را به شبکه اعتماد خود اضافه نمایند و شبکهای از افراد مورد اعتماد خود را تشکیل دهند و یا افراد ناشناس را که نظرات آنها مورد تایید نمی باشد را در لیست سیاه28 خود قرار دهند.
سیستم توصیهگری نیز که بر اساس شبکه اعتماد ایجاد میگردد به کاربران بر اساس نظرات افراد موجود در شبکه اعتماد29 ایشان و یا بر اساس نظرات افرادی که مورد اعتماد اعضای شبکه اعتماد باشند پیشنهاداتی را ارائه مینماید.
یکی از مباحث مهم و مطرح در اینگونه شبکهها نحوه بیان و ارزیابی معیار اعتماد میان کاربران میباشد که روشهای بسیار متنوع و مختلفی در این خصوص موجود است که طبیعتا منتج به نتایج متفاوتی میگردند[17]. به عنوان مثال تعداد ارتباطات مستقیم و غیرمستقیم میان یک کاربر با کاربر دیگر می تواند بیان کننده میزان اعتماد میان ایشان باشدکه این امر به صورت کلی باعث ارائه جوابهای قابل قبولتری میگردد[18]. نحوه بیان معیار اعتماد و اندازه گیری آن، خود یکی از موضوعات قابل تحقیق و بررسی است که از محدوده این تحقیق خارج بوده و در این تحقیق وجود یک شبکه مبتنی بر اعتماد میان کاربران به عنوان یکی از فرضیه های تحقیق در نظر گرفته میشود و به منظور محاسبه اندازه و مقدار اعتماد میان کاربران از نتایج تحقیق صورت گرفته در این خصوص بهرهبرداری میگردد[19].
1-7- تشریح و بیان مسئله
در یک سیستم توصیهگر بطور معمول مجموعهای از کاربران30 وجود دارد که به صورت مجموعهU={u1,u2,…,uN} نمایش داده میشود و مجموعهای از موضوعات و اشیا31 موجود میباشد که به صورت مجموعهI={i1,i2,…,iM} نمایش داده میشود بطوریکه هر کاربر به تعدادی از اشیا یا موضوعات امتیازی تخصیص میدهد که به صورت مجموعه RIu={iu1,iu2,…,iuk} نمایش داده می شود و امتیاز کاربر u به آیتمi به صورت ru,i بیان میگردد. ru,i میتواند یک عدد اعشاری باشد ولی در اکثر مواقع این عدد به صورت صحیح و در بازه ]5,1[ بیان میگردد.
در یک سیستم توصیهگر مبتنی بر شبکه اعتماد، علاوه بر مطالب فوق رابطه اعتماد میان دو کاربر u و v، با متغیر tu,v نمایش داده می شود و مقدار آن عددی اعشاری در بازه ]1,0[ میباشد. مقدار صفر برای متغیر tu,v نشان دهنده عدم وجود اعتماد میان دو کاربر و مقدار یک بیانگر وجود رابطه اعتماد کامل میان دو کاربر میباشد. در اکثر شبکههای اعتماد همچون32eBay، مقدار رابطه اعتماد به صورت مقدار دوتایی صفر و یک در نظر گرفته میشود. مجموعه TUu نشان دهنده مجموعه کاربرانی میباشد که به صورت مستقیم مورد اعتماد کاربر u میباشند و به صورتTUu={v ϵU | tu,v =1} تعریف میگردد.
با توجه به تعاریف فوق، شبکه اعتماد را می توان به صورت یک گرافG=<U,TU> تعریف نمود که در آنTU={(u,v)| u ϵ U , v ϵ TUu}میباشد و در واقع هر گره در این گراف بیانگر یک کاربر و یال میان هر دو گره بیانگر رابطه اعتماد میان ایشان میباشد و مقدار یال بیانگر اندازه اعتماد میان دو فرد خواهد بود. وظیفه سیستم توصیهگر با توجه به تعاریف و مفاهیم فوق به صورت زیر بیان میشود:
“در صورتیکه کاربر u عضو مجموعه U و آیتمi عضو مجموعه I باشد به صورتیکه ru,i نامشخص باشد، پیشبینی امتیازدهی کاربر u به آیتمi وظیفه سیستم توصیهگر میباشد. به کاربر u کاربر مبدا33 و به آیتم i آیتم مقصد34 اطلاق میگردد و امتیاز پیشبینی شده توسط سیستم با r ̂_(u,i) نمایش داده میشود”[20].
در اکثر مواقع، کاربران به درصد اندکی از آیتم ها امتیاز می دهند و در خصوص آنها نظرات خود را بیان می کنند که این امر باعث می گردد برای اکثر زوجهای <u,i>مقدار ru,i نامشخص باشد که این مسئله یکی از مسائل قابل تامل و مهم در خصوص طراحی مدل سیستم توصیهگر میباشد.
1-8- اهداف تحقیق
با توجه به مطالعات انجام شده و همچنین بررسی روشها، الگوریتمها، مقالات ژورنالها و کنفرانسهای معتبر در زمینه سیستمهای توصیهگر و با توجه به زمینه اصلی موضوع پایان نامه در رابطه با بهبود و پیادهسازی یک سیستم ترکیبی مبتنی بر شبکه اعتماد، مهمترین اهداف و دستاوردهای این تحقیق عبارتند از:
بررسی نقاط ضعف و قوت مدلهای ترکیبی موجود
ترکیب روش مبتنی بر اعتماد با یکی از روشهای موجود در زمینه پالایش گروهی
پیاده سازی و بهبود مدل TrustWalker[20] به عنوان یک مدل ترکیبی نوین و برتر از طریق ایجاد تغییر در نحوه پیمایش شبکه اعتماد میان کاربران
بهبود دقت پیشبینی امتیازات کاربران به آیتمهای مختلف به کمک پیادهسازی و بکارگیری مکانیزمی جهت تفسیر و تعدیل نظر کاربران
کاهش خطا و افزایش درصد پوشش در زمان ارائه پیشنهاد به کاربران تازه وارد
محاسبه میزان دقیق اعتماد میان کاربران عضو شبکه اعتماد به صورت اعشاری با بکارگیری روشها و دیدگاه های مختلف در این زمینه[19] به جهت افزایش و بهبود دقت و در نظر گرفتن مقدار محاسبه شده بجای مقدار صفر یا یک
پالایش شبکه اعتماد گسترده میان کاربران به نحوی که مدل پیشنهاد شده بر روی داده های کمتری اجرا گردد.
1-9- سوالات و فرضیههای تحقیق
فرضیههای موجود در این تحقیق عبارتند از:
وجود یک شبکه مبتنی بر اعتماد میان کاربران
بیان اعتماد میان کاربران در قالب یک عدد صحیح یا اعشاری در بازه ]1,0[
مبنا و اساس قراردادن پیاده سازی شخصی انجام گرفته از مدل TrustWalker به عنوان یکی از مدلهای برتر در زمینه موضوع تحقیق
اعتماد و تکیه بر نتایج تحقیقات و مقالات معتبر مورد ارجاع قرار گرفته در زمینه سیستمهای توصیهگر مبتنی بر شبکه اعتماد میان کاربران
وجود دادهها و نتایج تحقیقات قبلی صورت گرفته بر روی مجموعه داده Epinions35
سوالات مطرح نیز عبارتند از:
آیا ترکیب روش پالایش گروهی و روش مبتنی بر اعتماد باعث بهبود عملکرد سیستم توصیهگر میگردد؟
آیا عمق پیمایش شبکه اعتماد میان کاربران تاثیری بر روی نتایج دارد؟
آیا بکارگیری روش مبتنی بر آیتم در مقابل روش مبتنی بر کاربر باعث بهبود نتایج میگردد؟
آیا تعدیل و تفسیر نظرات کاربران باعث افزایش دقت و بهبود نتایج میگردد؟
از میان انواع روشهای محاسبه اندازه اعتماد میان کاربران کدام روش نتایج قابل قبولتری را ارائه مینماید؟
ترکیب روشهای موجود چه تاثیری بر روی درصد پوشش خواهد گذاشت؟
وجود شبکه اعتماد میان کاربران تا چه حد به حل مشکل ارائه توصیه به کاربران تازه وارد کمک مینماید؟
چه معیارهایی برای محاسبه تشابه دو کاربر یا دو آیتم مد نظر قرار گیرند؟
ترکیب روش مبتنی بر اعتماد با کدامیک از سایر روشهای موجود در زمینه سیستمهای توصیهگر می تواند باعث بهبود نتایج گردد؟
مکانیزم پیمایش شبکه عظیم میان هزاران کاربر چگونه خواهد بود؟
1-10- مراحل تحقیق
مراحل پیشنهادی برای انجام تحقیق عبارتند از:
بررسی و مطالعه روشهای دادهکاوی مورد استفاده در سیستمهای توصیهگر
مطالعه و بررسی روشها، مدلها و الگوریتم های موجود در زمینه سیستمهای توصیهگر مبتنی بر اعتماد
جستجو و یافتن یکی از مدلهای برتر در زمینه سیستمهای توصیهگر ترکیبی مبتنی بر اعتماد
پیادهسازی مدل انتخاب شده به کمک یکی از زبانهای برنامه نویسی به جهت آشکار شدن نقاط ضعف و قوت آن و بررسی چگونگی امکان بهبود یا تغییر مدل مذکور
جمع آوری و یکپارچه نمودن داده های مربوط به مجموعه دادههای مورد استفاده جهت انجام آزمایشات در یک پایگاه داده مستقل
آنالیز، پالایش و استخراج دادههای مورد نیاز برای انجام آزمایشات از پایگاه داده ایجاد شده
تحقیق و بررسی نتایج مدل پیاده سازی شده با نتایج موجود از تحقیقات قبلی
تلاش در جهت رفع نقایص و بهبود نتایج بدست آمده از طریق انجام اصلاحات در روش پایه یا ترکیب آن با سایر روشهای مطالعه شده
آزمایش میزان دقت، خطا و درصد پوشش مدل جدید با دادههای واقعی، بررسی نتایج، رفع نقایص و تکرار آزمایشات
مدون نمودن نتایج مدل جدید و ارائه علمی آنها
جمع بندی و بحث پیرامون نتایج
1-11- فصول پایاننامه
این پایان نامه در پنج فصل تنظیم و مدون شده است .در ادامه مقدمه که در فصل اول بیان گردید در فصل دوم ادبیات تحقیق مورد استفاده در زمینه سیستمهای توصیهگر، انواع روشها و مدلهای دادهکاوی موجود، با ذکر جزئیات و چگونگی عملکرد آنها و مباحث موجود در خصوص هر کدام از روشها و الگوریتمها تشریح میگردند. در فصل سوم مروری بر سیر تکاملی و تحقیقات گذشته انجام شده در زمینه سیستمهای توصیهگر ترکیبی و مبتنی بر اعتماد و بحث پیرامون نقاط ضعف و قوت آنها مطرح میگردد. در فصل چهارم جزئیات مدل ترکیبی پیشنهادی، مکانیزم الگوریتم و چگونگی عملکرد آن به صورت کامل تشریح میگردد و سعی در بررسی نکات و پاسخگویی به سوالاتی میشود که در این تحقیق به دنبال یافتن راهکار و پاسخی مناسب برای آنها هستیم. در فصل پنجم مجموعه دادههای مورد استفاده جهت انجام آزمایشات معرفی و چگونگی آماده سازی دادههای مورد نیاز جهت انجام آزمایشات بیان میگردند و نتایج بدست آمده از انجام آزمایشات مختلف و اجرای مدل پیشنهادی در شرایط گوناگون جمعآوری و مورد آنالیز، تحلیل و بحث قرار میگیرد و نهایتا در فصل آخر ضمن جمعبندی و ارائه نتایج کلی، پیشنهاداتی نیز برای تحقیقات آینده ارائه خواهد شد.
فصل دوم
مروری بر ادبیات تحقیق و مبانی نظری تحقیق
2- مروری بر ادبیات تحقیق و مبانی نظری تحقیق
2-1- مقدمه
در سالهای اخیر از تکنیکها و روشهای مختلف آماری، دادهکاوی، هوش مصنوعی و الگوریتمهای ریاضی در پیادهسازی سیستمهای توصیهگر استفاده شده است که از معروفترین و مهمترین این روشها و تکنیکها می توان به روش پالایش گروهی، پالایش محتوایی، گرافکاوی، روشهای مبتنی بر اعتماد و روش های ترکیبی نام برد .
در ادامه به تفصیل به معرفی و شرح هر کدام از روشهای فوق پرداخته میشود و نحوه کاربرد، نقاط ضعف و قوت آنها بیان میگردد. روشها و مدلهای فوق به صورت کلی به دو دسته مبتنی بر مدل36 و مبتنی بر حافظه37 تقسیم بندی میگردند که به لحاظ سرعت، هزینه اجرا، دقت، تک هدفی یا چند هدفی بودن، در نظر گرفتن نیازهای کوتاه مدت و بلند مدت کاربران با یکدیگر تفاوت دارند و هریک در پارهای از موضوعات کاربرد مناسبتر و راندمان بهتری دارند.
از میان روشهای فوق روش پالایش گروهی و پالایش محتوایی از سابقه نسبتا زیادی برخوردار میباشند و تحقیقات بسیار زیادی توسط محققان در خصوص موضوعات مرتبط با آنها، بهبود و بکارگیری در محیطهای مختلف مطرح گردیده است و بخش عمده ای از مطالب را به خود اختصاص میدهند، اما در مقابل، موضوع سیستمهای توصیهگر مبتنی بر اعتماد به تازگی مورد توجه محققان قرار گرفته است و از سابقه نسبتا کمی برخوردار است لذا به نسبت روشهای پیشین، تحقیقات اندکی در این حوزه صورت گرفته است و حجم اندکی از تحقیقات را به خود اختصاص می دهد. در ادامه، در هریک از بخشها به بررسی و مطالعه یکی از این روشها پرداخته می شود.
2-2- پالایش گروهی (Collaborative Filtering)
پالایش گروهی از بررسی رفتار گذشته کاربران و تشابه آنها با یکدیگر مدلی ایجاد مینماید[21] و سپس از آن مدل برای پیشبینی آیتمهای مورد علاقه کاربر یا پیشبینی امتیازدهی یک کاربر به یک آیتم خاص استفاده مینماید. این روش در واقع سعی در مدل نمودن پروسه اجتماعی نظرخواهی از دوستان و توجه به توصیههای آشنایان و اطرافیان دارد. یکی از مزایای اصلی این روش عدم وابستگی به محتوای قابل آنالیز به صورت مکانیزه میباشد و بنابراین بدون نیاز به داشتن اطلاعات کافی و درک دقیق از ماهیت یک آیتم پیچیده همچون “فیلم” امکان ارائه پیشنهاداتی در زمینه فیلم را دارا می باشد.
رفتار گذشته کاربر می تواند شامل تراکنشهای گذشته کاربر یا نظرات بیان شده وی در خصوص یک محصول خاص باشد، به عنوان مثال کاربر x به 4 فیلم امتیاز 5 را اختصاص داده است، یک سیستم توصیهگر با تکیه بر شیوه پالایش گروهی، اطلاعات در دسترس را پردازش میکند و کلیه کاربرانی را که به همان 4 فیلم امتیاز 5 را اختصاص دادهاند را جستجو نموده و لیست سایر فیلمهای مورد علاقه ایشان را به کاربر x توصیه میکند.
دیاگرامی از چگونگی کارکرد روش پالایش گروهی در شکل2-1 نشان داده شده است. همان طور که در تصور قابل مشاهده است سطرهای ماتریس m×n نشان دهنده کاربران و ستونها بیانگر آیتمها میباشند و هر سلول ماتریس بیانگر امتیازی است که توسط کاربر m به آیتم n داده شده است. مقدار هر سلول عددی در بازه ]5,1[ می باشد که مقدار 0 بیانگر این است که کاربر به آیتم مورد نظر امتیازی تخصیص نداده است [22].

شکل 2-1 : چگونگی کارکرد روش پالایش گروهی (Collaborative Filtering)[22]
پالایش گروهی خود به دو روش “مبتنی بر همسایگی38” و “مبتنی بر مدل39” تقسیمبندی میگردد. در اصطلاح رایج مدل “مبتنی بر همسایگی” به عنوان مدل “مبتنی بر حافظه40” نیز مورد ارجاع قرار می گیرد [23].
2-2-1- پالایش گروهی مبتنی بر حافظه(Memory Based)
در این تکنیک زیر مجموعهای از کاربران بر اساس تشابه آنها با کاربر مقصد انتخاب میگردند و ترکیبی وزندار41 از مجموعه نظرات ایشان، پیشنهاد مورد نظر کاربر مقصد را تولید میکنند. روند این تکنیک را می توان مطابق مراحل زیر بیان نمود[24]:
به تمامی کاربران بر اساس میزان تشابه آنها با کاربر مقصد وزنی تخصیص مییابد.
تعداد n کاربر که دارای بیشترین تشابه با کاربر مقصد میباشند انتخاب میگردد که به این مجموعه “همسایگان” گفته میشود.
از ترکیب وزندار نظرات کاربران مجموعه همسایگی، پیش بینی نظر کاربر مقصد در خصوص یک آیتم محاسبه میگردد.
در مرحله اول وزن wa,u بیانگر میزان تشابه میان کاربر مقصد a و کاربر u می باشد. متداولترین روش محاسبه تشابه استفاده از فرمول “پیرسون42” می باشد[25] که در ذیل این فرمول قابل مشاهده می باشد .
(1)
در این فرمول I مجموعه آیتمهایی میباشد که هر دو کاربر مشترکا به آنها امتیاز دادهاند و ru,i امتیازی می باشد که توسط کاربر u به آیتم i داده شده است و r ̅_u میانگین امتیازات کاربر u به مجموعه آیتمهای مجوعه I میباشد.
در مرحله سوم امتیازی که توسط کاربر مقصد a به آیتم i داده خواهد شد با متغیر Pa,i نشان داده میشود و جهت محاسبه آن، از میانگین وزنی انحراف از میانگین نظرات مجموعه همسایگان استفاده میگردد که این امر در فرمول شماره 2 قابل مشاهده میباشد.
(2)
در این فرمول wa,u مقدار تشابه میان کاربر a و u می باشد و K مجموعه کاربران موجود در مجوعه همسایگی می باشند. محاسبه تشابه بر اساس فرمول پیرسون بر اساس وجود وابستگی خطی میان دو متغیر عمل می نماید.
از دیدگاه دیگر می توان امتیاز داده شده توسط دو کاربر را به عنوان دو بردار در یک فضای m بعدی در نظر گرفت و تشابه میان دو کاربر را بر اساس کسینوس زاویه میان این دو بردار محاسبه نمود[26] در فرمول شماره 3 نحوه محاسبه این روش بیان شده است.
(3)
بر اساس قوانین حاکم بر فرمولهای ریاضی، در زمان محاسبه تشابه دو کاربر بر اساس فرمول تشابه کسینوسی، امتیاز یک کاربر به یک آیتم نمیتواند منفی باشد و امتیاز آیتمهایی که به آنها توسط کاربر امتیازی تخصیص داده نشده است صفر در نظر گرفته میشود. مطالعات تجربی[21] نشان داده است که دقت فرمول پیرسون در محاسبه تشابه از دقت فرمول کسینوسی بیشتر است. روشهای محاسبه تشابه دیگری نیز در تحقیقات مختلف بیان شده است که می توان به پارهای از آنها اشاره نمود[27][28]:
Spearman rank correlation
Kendall’s τ correlation
mean squared differences
entropy
adjusted cosine similarity
2-2-1-1- روش پالایش گروهی مبتنی بر آیتم43
بکارگیری روش پالایش گروهی مبتنی بر حافظه در شرایطی که در محیطهای واقعی میلیونها کاربر و آیتم وجود دارد به دلیل پیچیدگیهای محاسباتی جستجوی کاربران مشابه، از بازده مناسبی برخوردار نیست لذا روش پالایش گروهی مبتنی بر آیتم مطرح گردید که در این روش علاوه بر تشابه میان کاربران، تشابه میان آیتم هایی که توسط کاربر مقصد امتیاز داده شدهاند با آیتمهای مشابه نیز، در نظر گرفته میشود. در عمل و تحقیقات انجام شده، ثابت شده است که این روش در سیستمهای توصیهگر برخط از سرعت بالاتری برخوردار است و در اکثر مواقع جواب بهینهتر و با خطای کمتری تولید میکند[29][22].
در این روش تشابه میان دو آیتم i و j در پس زمینه و از طریق فرمول پیرسون، مطابق فرمول شماره 4 محاسبه میگردد.
(4)
در این فرمول U مجموعه تمام کاربرانی می باشد که به هر دو آیتم i و j امتیاز دادهاند و ru,i بیانگر امتیاز کاربر u به آیتم i میباشد و r ̅_i بیانگر میانگین امتیازاتی است که توسط کاربران مجموعه U به آیتم i داده شده است. با توجه به تعاریف و مطالب فوق پیشبینی امتیاز کاربر a به آیتم i از طریق محاسبه میانگین وزنی و مطابق فرمول شماره 5 محاسبه میگردد.
(5)
در این فرمول K مجموعه آیتمهایی می باشد که بیشترین تشابه با آیتم i را دارند و توسط کاربر a به آنها امتیازی تعلق گرفته است. برای روش مبتنی بر آیتم نیز میتوان از روش کسینوسی مانند adjusted cosine similarity استفاده نمود که مقایسه دقیق و عملی میان انواع متدهای موجود در این زمینه، توسط برخی از محققان انجام و منتشر گردیده است[22].
2-2-1-2- امتیازدهی به صورت پیش فرض
یکی از روشهای حل مشکل محاسبه تشابه میان دو کاربر که دارای آیتمهای مشترک اندکی هستند، استفاده از یک مقدار امتیاز پیش فرض برای آیتمهایی می باشد که صراحتا توسط کاربران امتیازی به آنها داده نشده است، در این حالت از فرمول شماره 1 می توان جهت محاسبه میزان تشابه دو کاربر استفاده نمود. تحقیقات نشان داده است که در نظر گرفتن مقدار پیش فرض می تواند باعث بهبود نتایج گردد[21].
2-2-1-3- تشدید حالت(Case Amplification)
جهت اهمیت دادن به نظرات کاربرانی که دارای تشابه بیشتری با کاربر مقصد میباشند محققان ضریبی را تحت نام “تشدید حالت” تعریف نمودهاند که مقدار تشابه محاسبه شده از طریق فرمول شماره 2 را تغییر میدهد. در فرمول شماره 6 ، p فاکتور تشدید می باشد و مقدار آن بزرگتر مساوی 1 است.
(6)
روشها و متدهای بسیار زیاد دیگری نیز در زمینه بهبود روش کلی پالایش گروهی مطرح میباشد که در ذیل به صورت فهرست وار اسامی این روشها بیان میگردد و به دلیل خروج از محدوده تحقیق، جزئیات آنها بیان نمیگردد:
Significance Weighting[27]
Inverse User Frequency[21]
weighted majority prediction[30]
imputation-boosted CF[31]
2-2-2- پالایش گروهی مبتنی بر مدل(Model Based)
در این تکنیک به کمک تخمین پارامترهای مدل آماری که بر اساس نظرات کاربران ایجاد گردیده است، ارائه پیشنهاد به کاربران یا پیشبینی امتیازدهی کاربر مقصد به یک آیتم خاص صورت می پذیرد به عنوان مثال یکی از ابتداییترین روشها، روش تبدیل پالایش گروهی به یک مسئله “طبقهبندی44” میباشد. در این حالت یک “تمایز دهنده45” برای کاربر مقصد به صورتی ایجاد میگردد که در آن آیتمها به عنوان بردار معیارها روی کاربران تعریف و امتیازهای موجود به صورت برچسب کلاس در نظر گرفته میشود و به کمک تکنیکهای “کاهش بعد46” مشکل کمبود اطلاعات47 نیز برطرف میگردد. در سالهای اخیر تکنیکهای “فاکتور نهان48” و “مدل فاکتورگیری ماتریسی49 “به عنوان بهترین روشهای موجود در این زمینه شناخته و عرضه شدهاند[32].
بر خلاف مدلهای مبتنی بر حافظه که بر اساس تشابه میان کاربران یا آیتمها و اطلاعات آماری موجود، نسبت به تولید پیشنهاد، اقدام مینمایند تکنیکهای مبتنی بر مدل تشابه میان کاربران یا آیتمها را، نتیجه وجود یک ساختار سطح پایین نهفته درون دادهها میدانند. در این تحقیق سعی در استفاده از تکنیکهای مبتنی بر حافظه می باشد لذا از ارائه توضیحات بیشتر در این خصوص پرهیز شده است.
2-3- پالایش محتوایی (Content Based Filtering)
سیستمهای توصیهگر تولید شده با استفاده از تکنیکهای پالایش گروهی، تنها بر اساس ماتریس امتیازات کاربران به آیتمهای مختلف یا بر اساس یک مدل تولید شده از اطلاعات موجود، نسبت به محاسبه و ارائه پیشنهاد اقدام میکنند همچنین کاربران و آیتمها به صورت موجودیتهای مجزا در نظر گرفته میشوند و خصوصیات و مشخصههای کاربران و آیتمها تاثیری در نتیجه پیشنهادات نخواهند داشت در حالیکه با کسب اطلاعات بیشتر در خصوص یک کاربر و شناخت علایق و سلایق وی، می توان پیشنهادات دقیق تر و مناسبتری را به وی ارائه نمود[8] به عنوان مثال با داشتن اطلاعات در خصوص کارگردان یا سبک یک فیلم سینمایی میتوان پیشنهادات مناسبتری را به کاربر مقصد ارائه نمود[33]. این تکنیک که در آن با توجه به خصوصیات و علایق یک کاربر یا مشخصات و ویژگیهای یک آیتم و با توجه به محتوا و مفاهیم، پیشنهاداتی ارائه میگردد تحت عنوان “سیستمهای توصیهگر مبتنی بر محتوا” یا “پالایش محتوایی50” نامگذاری شدهاند.
تحقیقات بسیار زیادی در این زمینه، خصوصا در مورد پیشنهاد آیتمهایی که اطلاعات متنی بسیاری در مورد آنها موجود میباشد مانند کتابها، فیلمها و صفحات وب انجام گردیده است و به این مسئله از دیدگاه “بازیابی اطلاعات51” نگاه شده است و



قیمت: تومان

دسته بندی : مقاله و پایان نامه

دیدگاهتان را بنویسید

دانشکده آموزشهای الکترونیکی
پایاننامه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات
(مدیریت سیستمهای اطلاعاتی)
ارائه مدلی برای سیستمهای توصیه گر در شبکه های مبتنی بر اعتماد
توسط :
هومن رفعت صفایی
استاد راهنما :
دکتر ستار هاشمی
شهریور ماه 1392
به نام او که هرچه هست از اوست
به نام خدا
ارائه مدلی برای سیستمهای توصیهگر در شبکههای مبتنی بر اعتماد
به وسیلهی :
هومن رفعت صفایی
پایان نامه
ارائه شده به تحصیلات تکمیلی دانشگاه به عنوان بخشی
از فعالیتهای تحصیلی لازم برای اخذ درجه کارشناسی ارشد
در رشته :
مهندسی فناوری اطلاعات – مدیریت سیستمهای اطلاعاتی
از دانشگاه شیراز
شیراز
جمهوری اسلامی ایران
ارزیابی شده توسط کمیته پایاننامه با درجه :
دکتر ستار هاشمی، استادیار بخش مهندسی و علوم کامپیوتر (رئیس کمیته) ……………………………
دکتر منصور ذوالقدری جهرمی، استاد بخش مهندسی و علوم کامپیوتر …………………………………..
دکتر اقبال منصوری، استادیار بخش مهندسی و علوم کامپیوتر …………………………………………………..
شهریور ماه 1392
به نام خدا
اظهارنامه
اینجانب هومن رفعت صفایی دانشجوی رشتهی مهندسی فناوری اطلاعات گرایش مدیریت سیستمهای اطلاعاتی دانشکدهی آموزشهای الکترونیکی اظهار میکنم که این پایان نامه حاصل پژوهش خودم بوده و در جاهایی که از منابع دیگران استفاده کردهام، نشانی دقیق و مشخصات کامل آن را نوشتهام. همچنین اظهار میکنم که تحقیق و موضوع پایان نامهام تکراری نیست و تعهد مینمایم که بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده یا در اختیار غیر قرار ندهم. کلیه حقوق این اثر مطابق با آیین نامه مالکیت فکری و معنوی متعلق به دانشگاه شیراز است.
نام و نام خانوادگی : هومن رفعت صفایی
تاریخ و امضا :
تقدیم به
همسر و فرزند عزیزم، که همواره و در همه حال، انگیزه و امید من به زندگی و ادامه تحصیل بوده و هستند.
سپاسگزاری
از خداوند متعال به سبب الطاف و نعمات بیدریغش و ارزانی داشتن نعمت و فرصت آموختن سپاسگذاری میکنم و در ادامه از استاد راهنمای گرانقدر جناب آقای دکتر هاشمی که در طی مراحل انجام پایاننامه همواره مشوق و یاری دهنده اینجانب بودهاند کمال تشکر و قدردانی میگردد .
همچنین از اساتید گرانقدر، جناب آقایان دکتر ذوالقدری و دکتر منصوری که بر اینجانب منت نهاده و اساتید مشاور بنده در این رساله بودهاند، سپاسگزاری مینمایم.
چکیده
ارائه مدلی برای سیستمهای توصیهگر در شبکههای مبتنی بر اعتماد
به کوشش
هومن رفعت صفایی
امروزه با گسترش و رشد روز افزون اطلاعات در فضای مجازی و وجود انبوهی از کالا یا خدماتی که در وب سایتهای تجاری و خدماتی ارائه میگردند کاربران را با این مشکل مواجه نموده است که چگونه کالا یا خدمت مورد نظر خود را به راحتی و با صرف کمترین زمان ممکن بیابند. در این میان سیستمهای توصیهگر با هدف تسهیل و یاری رساندن به کاربران در زمینه انتخاب و یافتن کالای مورد نیاز ایشان با استفاده از علوم و روشهای مبتنی بر داده کاوی اطلاعات، ایجاد و توسعه یافتهاند. همچنین در سالهای اخیر ظهور و گسترش شبکههای اجتماعی و شبکههای مبتنی بر رابطه اعتماد میان کاربران، باعث گشوده شدن افق جدیدی در ارائه سیستمهای توصیهگر و توسعه نسل جدیدی از اینگونه سیستمها گردیده است و آنرا به یکی از موضوعات جذاب و مورد توجه محققان تبدیل نموده است.
از میان روشها و مدلهای موجود در زمینه سیستمهای توصیهگر روش پالایش گروهی به لحاظ سادگی پیادهسازی از محبوبیت قابل ملاحظهای برخوردار است اما این روش در ارائه پیشنهادات مناسب و قابل قبول به کاربران تازه وارد دارای ضعفهای جدی میباشد. سیستمهای توصیهگر مبتنی بر اعتماد، با بهرهگیری از رابطه اعتماد میان کاربران، در جهت رفع نقاط ضعف بیان شده و خصوصا ارائه پیشنهادات مناسب به کاربران تازه وارد گامهای موثری برداشتهاند. در این تحقیق سعی شده است تا از تلفیق و ترکیب روشهای موجود در زمینه پالایش گروهی و همچنین مدلهای مبتنی بر اعتماد و بررسی نقاط ضعف و قوت آنها مدلی نوین و توسعه یافته ارائه گردد که در آن نتایج از خطای کمتر و دقت بالاتری برخوردار بوده و با افزایش معیار پوشش بتوان به درصد بیشتری از کاربران پاسخ مناسب ارائه نمود. برای این منظور در میان انواع روشهای پالایش گروهی، روش مبتنی بر آیتم و برای پیمایش شبکه اعتماد میان کاربران نیز از روش پیمایش تصادفی بهره گرفته شده است، همچنین با تفسیر و تعدیل نظرات کاربران و اتخاذ شیوهای مناسب جهت محاسبه مقدار دقیق اعتماد میان کاربران و تغییر در نحوه پیمایش شبکه اعتماد میان ایشان سعی در بهبود و کاهش خطاهای نتایج گردیده است. در نهایت، جهت ارزیابی و برآورد مدل ترکیبی ارائه شده، نتایج و آمارهای حاصل از اجرای مدل پیشنهادی بر روی مجموعه داده های Epinions و Movielens و مقایسه آنها با نتایج مدل پایه TrustWalkerبه عنوان یکی از بهترین مدلهای ترکیبی ارائه شده در زمینه سیستمهای توصیه گر مبتنی بر اعتماد، ارائه میگردد.
واژههای کلیدی: دادهکاوی1، شبکههای اجتماعی2، شبکههای مبتنی بر اعتماد3، سیستمهای توصیهگر4، پالایش گروهی5، اعتماد6، پیمایش تصادفی7، ترکیب سازی8
فهرست مطالب
عنوان…………………………………………………………………………………………………………….صفحه
فصل اول : مقدمهای بر انواع سیستم توصیهگر…………………………………………………1
1-1- مقدمه…………………………………………………………………………………………………………………..2
1-2- سیستمهای توصیهگر…………………………………………………………………………………………..3
1-3- انواع سیستمهای توصیهگر از لحاظ عملکردی……………………………………………………4
1-4- مزایا و اهمیت یک سیستم توصیهگر کارآمد………………………………………………………5
1-5- معایب و مشکلات کلی سیستمهای توصیهگر……………………………………………………..6
1-6- انواع رویکردها و مدلهای موجود در زمینه پیادهسازی سیستمهای توصیهگر…….7
1-7- تشریح و بیان مسئله………………………………………………………………………………………….11
1-8- اهداف تحقیق…………………………………………………………………………………………………….12
1-9- سوالات و فرضیههای تحقیق…………………………………………………………………………….13
1-10- مراحل تحقیق…………………………………………………………………………………………………14
1-11- فصول پایان نامه……………………………………………………………………………………………..15
فصل دوم : مروری بر ادبیات تحقیق و مبانی نظری تحقیق………………………………17
2-1- مقدمه ……………………………………………………………………………………………………………….18
2-2- پالایش گروهی (Collaborative Filtering)…………………………………………….19
2-2-1- پالایش گروهی مبتنی بر حافظه(Memory Based)……………………………..20
2-2-1-1- روش پالایش گروهی مبتنی بر آیتم ………………………………………………………22
2-2-1-2- امتیازدهی به صورت پیش فرض……………………………………………………………..24
2-2-1-3- تشدید حالت(Case Amplification)……………………………………………….24
2-2-2- پالایش گروهی مبتنی بر مدل(Model Based)……………………………………..25
2-3- پالایش محتوایی (Content Based Filtering) ………………………………………26
2-4- تکنیکهای ترکیبی……………………………………………………………………………………………..27
2-5- سیستمهای توصیهگر مبتنی بر رابطه اعتماد میان کاربران……………………………..28
2-5-1- چگونگی کارکرد سیستم توصیهگر مبتنی بر اعتماد……………………………………30
2-5-2- مزایا و معایب………………………………………………………………………………………………..31
2-5-3- انتشار اعتماد و تجمیع اعتماد………………………………………………………………………33
2-6- چالش ها و محدودیتهای موجود………………………………………………………………………33
2-6-1- نقصان و کاستی اطلاعات……………………………………………………………………………..34
2-6-2- مشکل کاربران تازه وارد………………………………………………………………………………..34
2-6-3- کلاهبرداری و تقلب………………………………………………………………………………………35
2-6-4- پیچیدگیهای محاسباتی و زمانی…………………………………………………………………..36
2-7- معیارهای ارزیابی سیستمهای توصیهگر……………………………………………………………37
2-7-1- خطای جذر میانگین مربعات (RMSE)…………………………………………………….37
2-7-2- معیار درصد پوشش………………………………………………………………………………………38
2-7-3- معیار دقت…………………………………………………………………………………………………….39
2-7-4- معیار F-Measure…………………………………………………………………………………….39
فصل سوم : مروری بر مطالعات و تحقیقات پیشین…………………………………………..41
3-1- مقدمه………………………………………………………………………………………………………………..42
3-2- مرور کارهای گذشته………………………………………………………………………………………….42
3-2-1- مدل MoleTrust………………………………………………………………………………………45
3-2-2- مدل TidalTrust………………………………………………………………………………………47
3-2-3- مدل دانه سیب……………………………………………………………………………………………..48
3-2-4- مدل ارائه شده توسط Anderson……………………………………………………………48
3-2-5- مدل ارائه شده توسط O’Donovan………………………………………………………..49
3-2-6- مدل TrustWalker………………………………………………………………………………….50
3-2-6-1- ساختار مدل TrustWalker…………………………………………………………………51
3-2-6-2- تشابه آیتم ها……………………………………………………………………………………………51
3-2-6-3- خصوصیات ویژه مدل TrustWalker…………………………………………………..52
3-2-6-3-1- فراگیری و عمومیت مدل…………………………………………………………………….52
3-2-6-3-2- اطمینان به نتایج حاصل………………………………………………………………………53
3-2-6-3-3- تفسیرپذیری و قابل توضیح بودن نتایج………………………………………………54
3-2-6-4- نمایش ماتریسی مدل TrustWalker………………………………………………….54
3-2-6-5- نتیجه گیری در خصوص مدل TrustWalker…………………………………….55
فصل چهارم : تشریح مدل ترکیبی پیشنهادی و چگونگی توسعه و بهبود مدل پایه.56
4-1- مقدمه………………………………………………………………………………………………………………..57
4-2- تشریح مدل کلی TrustWalker…………………………………………………………………..57
4-2-1- علائم نشانه گذاری و متغیرهای مدل…………………………………………………………..57
4-2-2- روند یک پیمایش تصادفی در شبکه…………………………………………………………….58
4-2-3- انتخاب تصادفی یک کاربر …………………………………………………………………………..59
4-2-4- انتخاب یک آیتم مشابه…………………………………………………………………………………59
4-2-5- تشابه آیتم ها…………………………………………………………………………………………………60
4-2-6- محاسبه احتمال ماندن در یک گره شبکه اعتماد (∅_(u,i,k))………………………..61
4-2-7- چگونگی انجام پیشبینی امتیاز……………………………………………………………………62
4-2-8- چگونگی محاسبه احتمال P(XY_(u,i)=(v,j))………………………………………….63
4-2-9- چگونگی محاسبه عملی r ̂_(u,i)……………………………………………………………………….64
4-2-10- شرط اتمام کلی مدل………………………………………………………………………………….64
4-3- بهبود و توسعه مدل TrustWalker………………………………………………………………65
4-3-1- استفاده از فرمول jaccard جهت محاسبه تشابه آیتمها…………………………….66
4-3-2- حذف میانگین از فرمول پیرسون………………………………………………………………….67
4-3-3- استفاده از تکنیک مبتنی بر آیتم خالص………………………………………………………67
4-3-4- تعدیل و تفسیر نظرات کاربران……………………………………………………………………..68
4-3-5- محاسبه دقیق مقدار اعتماد یا امتیاز رابطه میان دو کاربر…………………………..71
4-3-6- محاسبه ترکیبی امتیاز رابطه میان کاربران………………………………………………….73

فصل پنجم : تشریح روند انجام آزمایشات و نتایج حاصل………………………………76
5-1- مقدمه………………………………………………………………………………………………………………..77
5-2- معرفی مجموعه داده epinions……………………………………………………………………..77
5-2-1- ویژگیهای مجموعه داده epinions……………………………………………………………79
5-2-2- آماده سازی و نحوه پالایش دادهها……………………………………………………………….81
5-2-3- ایجاد مجموعه داده نمونه……………………………………………………………………………..83
5-3- مجموعه داده movielens……………………………………………………………………………..84
5-3-1- ویژگیهای مجموعه داده movielens………………………………………………………..84
5-4- نیازمندیهای نرم افزاری…………………………………………………………………………………….85
5-5- نیازمندیهای سخت افزاری………………………………………………………………………………..85
5-6- متدولوژی نرم افزاری…………………………………………………………………………………………86
5-7- پارامترهای پیش فرض انجام آزمایشات…………………………………………………………….86
5-8- نتایج اجرای آزمایشات با مجموعه داده epinions و movielens……………..87
5-8-1- بررسی تاثیر عمق پیمایش بر روی نتایج حاصل در خصوص کاربران تازه وارد……………………………………………………………………………………………………………………………….87
5-8-2- بررسی تاثیر تاریخ اعلام نظرات توسط کاربران……………………………………………88
5-8-3- بررسی تاثیر تغییر فرمول محاسبه تشابه آیتمها………………………………………….89
5-8-4- بررسی تاثیر بکارگیری مکانیزم تفسیر و تعدیل نظرات کاربران………………….90
5-8-5- بررسی تاثیر بکارگیری انواع روشهای ترکیبی برای انتخاب کاربران و پیمایش شبکه…………………………………………………………………………………………………………………………….93
5-8-5-1- نحوه محاسبه امتیاز رابطه موجود میان کاربران……………………………………..93
5-8-5-2- بررسی تاثیر بکارگیری روشهای ترکیبی در عملکرد سیستم برای تمامی کاربران………………………………………………………………………………………………………………………….94
5-8-5-3- بررسی تاثیر بکارگیری روشهای ترکیبی در عملکرد سیستم برای کاربران تازه وارد ………………………………………………………………………………………………………………………99
5-8-6- بررسی تاثیر بکارگیری توام مکانیزم تفسیر امتیازات کاربران به همراه استفاده از روشهای ترکیبی انتخاب کاربران و پیمایش شبکه اعتماد……………………………………101
5-9- انجام آزمایشات با مجموعه داده movielens……………………………………………..107
5-9-1- نتایج حاصل از اجرای روشهای ترکیبی مورد استفاده در مدل توسعه یافته…………………………………………………………………………………………………………………………..107
فصل ششم : نتیجه گیری نهایی و کارهای آینده…………………………………………….110
6-1- مقدمه………………………………………………………………………………………………………………111
6-2- عملکرد مدل توسعه یافته……………………………………………………………………………….112
6-2-1- عملکرد مدل توسعه یافته در خصوص تمامی کاربران………………………………112
6-2-2- عملکرد مدل توسعه یافته در خصوص کاربران تازه وارد…………………………..114
6-3- نتیجه گیری نهایی …………………………………………………………………………………………115
6-3-1- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده epinions………………………………………………………………………………………………………………..116
6-3-2- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده movielens…………………………………………………………………………………………………………….118
6-4- پیشنهادات کارهای آینده……………………………………………………………………………….118
اختصارات…………………………………………………………………………………………………..120
فهرست منابع……………………………………………………………………………………………..121
فهرست جداول
عنوان………………………………………………………………………………………………………………….صفحه
جدول 3-1 : دستهبندی مدلهای اعتماد…………………………………………………………………………………..44
جدول 4-1 : ماتریس پراکندگی نحوه امتیازدهی دو کاربر u_1 و u_2……………………………………70
جدول 4-2 : تفسیر نظرات کاربر u_2……………………………………………………………………………………..70
جدول 5-1 : ساختار جدول reviews……………………………………………………………………………………81
جدول 5-2 : ساختار جدول WOT…………………………………………………………………………………………82
جدول 5-3 : ساختار جدول cold_start_users………………………………………………………………..82
جدول 5-4 : ساختار جدول ratings………………………………………………………………………………………83
جدول 5-5 : مقادیر پیش فرض پارامترها و متغیرهای مورد استفاده در مدل پیشنهادی………86
جدول 5-6 : نتایج بررسی تاثیر عمق پیمایش در خصوص کاربران تازه وارد………………………….88
جدول 5-7 : نتایج حاصل از بررسی تاثیر تاریخ اعلام نظرات کاربران……………………………………..89
جدول 5-8 : نتایج حاصل از تغییر فرمول محاسبه تشابه آیتمها…………………………………………….90
جدول 5-9 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران…………………….91
جدول 5-10 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران در خصوص کاربران تازه وارد…………………………………………………………………………………………………………………………91
جدول 5-11 : نتایج حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه……………………………………………………………………………………………………………………………………………..96
جدول 5-12 : نتایج حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد…………………………………………………………………………………………………………99
جدول 5-13 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………102
جدول 5-14 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد…………………………………………………………………………………………………………………………………………..104
جدول 5-15 : نتایج حاصل از اجرای روشهای ترکیبی انتخاب کاربران و پیمایش شبکه……107
جدول 5-16 : نتایج حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روشهای ترکیبی انتخاب کاربران و پیمایش شبکه…………………………………………………………………108
جدول 6-1 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه …………………………………………………………………………………………………………………………………………………113
جدول 6-2 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه در خصوص کاربران تازه وارد………………………………………………………………………………………………………..114
فهرست اشکال و نمودارها
عنوان………………………………………………………………………………………………………………….صفحه
شکل 2-1 : چگونگی کارکرد روش پالایش گروهی (Collaborative Filtering)……………20
شکل 2-2 : نمایش یک شبکه اعتماد به همراه امتیازات بیان شده توسط کاربران در خصوص آیتمهای مختلف…………………………………………………………………………………………………………………………31
شکل 3-1 : معماری مدل MoleTrust ارائه شده توسط Massa……………………………………….46
شکل 5-1 : بنر صفحه اصلی سایت epinions………………………………………………………………………78
نمودار 5-1 : مقایسه نتایج خطای RMSE و درصد پوشش مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران ……………………………………………………………………………………………………………………………………………………92
نمودار 5-2 : مقایسه نتایج معیارF-measure مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران…………93
نمودار 5-3 : مقایسه نتایج معیاردرصد پوششحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………97
نمودار 5-4 : مقایسه نتایج خطای RMSEحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………98
نمودار 5-5 : مقایسه نتایج معیار F-measureحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه……………………………………………………………………………………………….98
نمودار 5-6 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..100
نمودار 5-7 : مقایسه نتایج خطای RMSE حاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………….100
نمودار 5-8 : مقایسه نتایج معیار F-measureحاصل از اجرای روشهای ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..101
نمودار 5-9 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..103
نمودار 5-10 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه …………………………………………………………………………………………………………………………………………………103
نمودار 5-11 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..104
نمودار 5-12 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………105
نمودار 5-13 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد……………………………………………………………………………………………………………..106
نمودار 5-14 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روشهای ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………106
نمودار 5-15 : مقایسه نتایج خطای RMSE حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روشهای ترکیبی انتخاب کاربران و پیمایش شبکه………………..109
نمودار 6-1 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه از نظر تمام معیارهای ارزیابی……………………………………………………………………………………………………………………………………..113
نمودار 6-2 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه برای کاربران تازه وارد از نظر تمام معیارهای ارزیابی………………………………………………………………………………………………….115
فصل اول
مقدمه ای بر انواع سیستمهای توصیهگر
1- مقدمهای بر انواع سیستمهای توصیهگر
1-1- مقدمه
گسترش سریع و روز افزون اطلاعات ارائه شده بر روی شبکه جهانی اینترنت، کاربران را با مشکلات عدیده و قابل تاملی در خصوص انتخاب منابع و اطلاعات مورد نیاز ایشان مواجه نموده است و چه بسا که بدون راهنمایی و هدایت صحیح، کاربران در اخذ تصمیمات صحیح یا انتخاب کالا و خدمات مورد نیازشان دچار اشتباه شده که این امر تبعات عدیدهای از جمله نارضایتی، سلب اطمینان کاربران و مشتریان سایتهای موجود بر روی اینترنت را به همراه خواهد داشت. از اینرو وجود ابزار و سیستمهایی برای کمک به کاربران در انتخاب اطلاعات مناسب و مورد نیاز ایشان کاملا ضروری به نظر میرسد. در سالهای اخیر برای برآورده سازی این نیازها سیستمهای توصیهگرمطرح و توسعه یافتهاند و الگوریتمها ، مقالات و متون علمی بسیار متنوع و مختلفی در این زمینه مطرح گردیده است .
در این میان، ایجاد و گسترش شبکههای اجتماعی، شبکههای اعتماد و وجود انواع روابط میان کاربران این شبکهها افق جدیدی را برروی محققان و توسعه دهندگان سیستمهای توصیهگر گشوده است تا با بهرهگیری از علوم اجتماعی و علوم روان شناختی حاکم در این شبکهها و خصوصا وجود رابطه اعتماد میان کاربران بتوانند نسل جدیدی از سیستمهای توصیهگر را تحت عنوان “سیستمهای توصیهگر مبتنی بر اعتماد9″معرفی و عرضه نمایند. این سیستمها قادر هستند تا به درصد بیشتری از کاربران پاسخ مناسب را ارائه دهند و همچنین نتایج آنها از دقت بالاتری برخوردار میباشد.
با توجه به کثرت کاربران و افراد عضو شبکههای مبتنی بر اعتماد و شبکههای اجتماعی، همچنین تنوع رفتار و ویژگیهای ایشان، تنها یک شیوه یا یک مدل قادر به پاسخگویی و ارائه پیشنهادات دقیق و قابل قبول نمیباشد که این امر باعث ظهور سیستمهای توصیهگر ترکیبی10گردیده است. در این سیستمها سعی شده است تا با ترکیب انواع مختلفی از سیستمهای توصیهگر بتوان سیستمی تولید نمود که دارای مزایای حداکثری و معایب حداقلی باشد.
در این پایاننامه سعی شده است تا با تغییر، اصلاح، تلفیق و ترکیب تعدادی از روشها و الگوریتمهای مطرح و قابل قبول در سطح جهانی، مدلی ارائه گردد که نسبت به مدلهای پیشین دارای دقت و درصد پوشش بالاتری باشد و همچنین بتواند نقایص مدلهای پیشین خصوصا در رابطه با ارائه پیشنهاد به کاربران تازه وارد11 را تا حد قابل قبولی مرتفع نماید.
1-2- سیستمهای توصیهگر
تعاریف متفاوتی برای سیستم‌های توصیه‌گر ارائه شده‌است. عدهای از محققان سیستمهای توصیهگر را زیرمجموعه‌ای از سیستمهای تصمیمیار12 می‌دانند و آنها را سیستم‌های اطلاعاتی13 تعریف می‌کنند که توانایی تحلیل رفتارهای گذشته و ارائه توصیه‌هایی برای مسائل جاری را دارا میباشند[1]. به زبان ساده‌تر در سیستم‌های توصیه‌گر تلاش بر این است تا با حدس زدن شیوه تفکر کاربر به کمک اطلاعاتی که از نحوه رفتار وی یا کاربران مشابه و نظرات آنها داریم مناسب‌ترین و نزدیک‌ترین کالا یا خدمت به سلیقه او را شناسایی و پیشنهاد کنیم. این سیستم‌ها در حقیقت سعی دارند فرایندی را که ما در زندگی روزمره خود بکار می‌بریم و طی آن تلاش می‌کنیم تا افرادی با سلایق نزدیک به خود را پیدا کرده و از آنها در مورد انتخاب‌هایمان نظر بخواهیم را شبیه سازی نمایند.
به صورت کلیتر سیستمهای توصیهگر زیر مجموعهای از سیستمهای پالایش اطلاعات14هستند که وظیفه آنها جستجو برای بیان پیشبینی امتیاز(درجه)15 یا بیان سلایق و ترجیحات16 یک کاربر در خصوص یک موضوع17 ( مانند موسیقی، کتاب یا فیلم) یا یک عنصر اجتماعی مانند افراد و گروهها میباشد[2]–[4].
1-3- انواع سیستمهای توصیهگر از لحاظ عملکردی
سیستمهای توصیهگر به لحاظ نحوه ارائه نتایج و پیشنهادات به کاربران خود، به شیوه های متفاوتی عمل می نمایند که در ذیل به پارهای از آنها به صورت فهرست وار اشاره میگردد:
پیشنهاد لیستی متشکل از n کالا یا محصول برتر (معمولا n برابر 10 است )
پیشنهادات فصلی و موردی مانند پیشنهاد یک هتل دارای تخفیف جهت تعطیلات
بیان درصد علاقهمندی سایر کاربران به یک محصول خاص، به عنوان مثال: “80 درصد کاربران از خرید این محصول راضی بوده اند ”
پیش بینی میزان امتیازی که یک کاربر به یک محصول خاص خواهد داد
در این تحقیق سعی در ایجاد مدلی است که بتواند نظر و امتیاز تخصیص داده شده توسط یک کاربر خاص به یک محصول یا آیتم خاص را پیشبینی نماید.
1-4- مزایا و اهمیت یک سیستم توصیهگر کارآمد
طبق آمار رسمی ارائه شده توسط سایت فروش کتاب Amazon18 ، 35 درصد از فروش این سایت به واسطه وجود سیستم توصیهگر و ارائه پیشنهادات مناسب به علاقهمندان کتاب می باشد[5] همچنین سایت اجاره فیلم Netflix برای بهبود 10 درصدی دقت سیستم توصیهگر خود موسوم به Cinematch19جایزه ای بالغ بر یک میلیون دلار برای محققان در نظر گرفته است. هر دو مثال فوق نشان دهنده اهمیت سیستمهای توصیهگر و نقش آنها در تجارت میباشد. در ذیل تعدادی از دلایل اهمیت وجود یک سیستم توصیهگر مناسب و کارآمد در یک سایت تجارت الکترونیک برشمرده میگردد:
راهنمایی کاربران و بازدید کنندگان در انتخاب کالا ، محصول یا خدمت مناسب
تسریع در زمان انتخاب کالای مورد نظر مشتری مانند انتخاب یک فیلم مناسب در میان میلیونها فیلم موجود در سایت
جمعآوری اطلاعات ارزشمند در خصوص سلایق و رفتار کاربران جهت برنامهریزیهای آتی
جذب مشتریان و بازدید کنندگانی که برای اولین بار است از سایت بازدید میکنند
افزایش میزان رضایتمندی کاربران و طبیعتا افزایش سود سرمایه گذاران تجاری
ایجاد احساس اطمینان در مشتری با ارائه آمار نظرات سایر کاربران
بهبود معیارهای سنجش رتبه و درجه پورتال یا سایت
توجه به جنبههای روانشناختی کاربران
افزایش آگاهی کاربر در زمینه مورد علاقه وی
1-5- معایب و مشکلات کلی سیستمهای توصیهگر
در مقابل مزایای بیان شده، این سیستمها دارای نواقص و محدودیتهایی نیز می باشند که در ذیل به پاره ای از آنها اشاره میشود:
عدم امکان بررسی همه جانبه مشخصات کاربران و عدم ارائه یک جواب کاملا منطبق و سازگار با نظر ایشان
عدم اطمینان مشتریان به نظرات و پیشنهادات ارائه شده توسط سیستم
عدم وجود دقت مطلوب در پیشنهادات ارائه شده توسط سیستم
عدم پاسخگویی در برخی شرایط خاص، خصوصا در مورد کاربران تازه وارد یا مشتریان جدید (در فصل آینده در خصوص این مورد توضیحات کاملتری ارائه میگردد)
مشکلات فنی و موانع عدیدهای نیز در خصوص پیادهسازی و ارائه الگوریتم برای سیستمهای توصیهگر وجود دارد که پارهای از آنها عبارتند از:
پیادهسازی این سیستمها به دلیل وجود فاکتورهای بسیار متعدد و تاثیرگذار بر روی روند تصمیمگیری مکانیزه، بسیار پیچیده میباشد.
وجود امکان نفوذ متجاوزان و کلاهبرداران به اینگونه سیستمها و ایجاد دادههای غیرصحیح در سیستم، که ممکن است نتیجه خروجی سیستم را به نحوی تغییر یا منحرف نمایند.
پیچیدگی زمانی الگوریتمهای موجود و سرعت پاسخگویی کند این سیستمها خصوصا در ارائه پیشنهادات برخط20
پیچیدگی پیادهسازی الگوریتمهای موجود در این زمینه به لحاظ برنامهنویسی و مباحث نرمافزاری
وجود مشکلات عدیده در خصوص مدیریت دادههای بسیار سنگین و گاها به صورت توزیعشده21
پیچیدگیهای ناشی از وجود یک شبکه گرافی بسیار حجیم و درهم با تعداد گرههای بسیار زیاد خصوصا در مورد شبکههای اجتماعی
عدم وجود امکانات زمانی و سختافزاری در زمینه بررسی کل شبکههای مبتنی بر اعتماد برای یافتن بهترین جواب و با بالاترین دقت ممکن(به عنوان مثال اجرای برخی از الگوریتمها ممکن است چندین روز به طول بیانجامد)
1-6- انواع رویکردها و مدلهای موجود در زمینه پیادهسازی سیستمهای توصیهگر
در سالهای اخیر شیوهها، رویکردها، الگوریتمها و مدلهای متنوع و گوناگونی در زمینه توسعه انواع سیستمهای توصیه گر مطرح گردیده است که از ابعاد مختلف و با نگاههای متفاوتی به مسئله ارائه پاسخ و پیشنهاد مناسب به کاربران پرداختهاند که در این میان، پارهای از مهمترین و معروفترین روشهای موجود به اختصار معرفی میگردند.
یکی از متداولترین شیوه های مطرح”پالایش گروهی”میباشد[6]. این شیوه با جمعآوری و آنالیز دادههای موجود در مورد رفتار گذشته کاربران، فعالیتهای ایشان، سلایق آنها و امتیازاتی که به آیتمهای مختلف توسط ایشان داده شده است و همچنین بر اساس تشابه کاربران یا موضوعات با یکدیگر، مدلی ایجاد مینماید و سپس از آن مدل برای پیشبینی آیتمهای مورد علاقه کاربر یا پیشبینی امتیازدهی یک کاربر به یک آیتم خاص استفاده مینماید[7]. یکی دیگر از شیوههای موجود در این زمینه “پالایش محتوایی22” میباشد که در این شیوه، مجموعهای از خصوصیات یک آیتم، برای پیشنهاد آیتمهای جدید با خصوصیات مشابه با آن مورد استفاده قرار میگیرد[8]. از هر دو روش فوق نسخههایی نیز به صورت تجاری پیادهسازی شده است که به عنوان مثال سیستم توصیهگر موسیقی بکار رفته در سایت Last.fm23 بر اساس شیوه پالایش محتوایی پیادهسازی شده است در حالیکه در سایت 24PandoraRadio از شیوه پالایش گروهی استفاده شده است.
یکی دیگر از شیوههای موجود درخصوص تولید سیستمهای توصیهگر، ترکیب هر دو رویکرد فوق تحت عنوان “سیستمهای توصیهگر ترکیبی” میباشد[4]. مطالعات اخیر نشان داده است که در برخی موارد استفاده از ترکیب هر دو شیوه میتواند نتایج موثرتری را ایجاد نماید. این ترکیب میتواند در اشکال و انواع مختلفی صورت گیرد که هر کدام نتایج خاصی را تولید مینمایند[9]. تحقیقات نشان داده است که ترکیب این دو شیوه می تواند برخی از مشکلات هر کدام از روشها را برطرف نموده و نتایج با دقت بالاتری ایجاد نماید، به عنوان مثال، سیستم توصیهگر ایجاد شده در سایتNetflix25 از یک سیستم ترکیبی بهره میبرد که در آن عادات مشاهده فیلم، توسط کاربران مشابه (شیوه پالایش گروهی)، در کنار ارائه فیلمهایی که به لحاظ مشخصات، مشابه فیلمهایی هستند که توسط کاربر امتیاز بالاتری اخذ نمودهاند (شیوه پالایش محتوایی) در نظر گرفته شده است.
با ظهور شبکههای اجتماعی و شبکههای مبتنی بر اعتماد، رویکردها و ایدههای جدیدی در خصوص ایجاد و بهبود سیستمهای توصیهگر، با توجه به ارتباطات میان کاربران و به صورت خاص، وجود رابطه اعتماد میان آنها مطرح گردیدکه منجر به تولید سیستمهای توصیه گر مبتنی بر اعتماد شده است[10].
یک شبکه اجتماعی در واقع یک ساختار اجتماعی متشکل از مجموعهای از بازیگران (شامل کاربران و سازمان آنها) و ارتباطات دوتایی میان این عناصر میباشد[11] که به عنوان نمونه برجستهای از آن می تواند به شبکه اجتماعی facebook اشاره نمود. این ارتباطات میتواند در قالب انواع گوناگون یا بر اساس معیارهای مختلفی مانند: قیمتها، تبادلات مالی، دوستی، خویشاوندی، تجارت، سرایت بیماری یا مسیرهای هواپیمایی و غیره بیان گردند[12]. بررسی ابعاد و زوایای مختلف یک شبکه اجتماعی روش مشخصی برای آنالیز و تحلیل ساختار کلیه عناصر تشکیل دهنده آنرا فراهم میکند. مطالعه این ساختارها از روش “آنالیز شبکه اجتماعی” برای شناسایی الگوهای محلی و سراسری ، یافتن عناصر و موجودیتهای تاثیرگذار در شبکه و بررسی دینامیک شبکه استفاده مینماید[13]. شبکههای اجتماعی و تحلیل آنها یکی از موضوعات میان رشتهای است که به صورت آکادمیک در حوزههای روانشناسی اجتماعی، جامعه شناسی، آمار و تئوری گراف مطرح میباشد.
از دیدگاه تئوری گراف[14] یک شبکه اجتماعی متشکل از تعدادی گره و یال میباشد که گرهها در واقع همان افراد، سازمانها و گروهها میباشند و یالها نیز بیانگر رابطه میان هر دو گره موجود در این گراف میباشند. نکته حائذ اهمیت، پیچیدگی این گرافها به لحاظ تعداد بسیار زیاد گرهها و همچنین یالهای میان آنها میباشد.
یکی از انواع خاص شبکههای اجتماعی وجود یک شبکه مبتنی بر اعتماد میان کاربران میباشد که در آن کاربران عقیده و نظر خود در خصوص اعتماد به دیگران را صراحتا و آشکارا بیان می نمایند و این اعتماد را در قالب امتیازی که به افراد مختلف می دهند بیان میکنند[15]. یک شبکه مبتنی بر اعتماد در واقع یک گراف جهتدار است که میتواند متمایز کننده آن از یک شبکه اجتماعی گردد. گرهها کاربران میباشند و یالهای گراف بیانکننده وجود رابطه اعتماد میان دو کاربر میباشند[16]. به عنوان مثال می توان به سایت Epinions26 اشاره نمود. این سایت تجارت الکترونیک27 مثال بارزی از شبکه مبتنی بر اعتماد می باشد که در آن کاربران در خصوص محصولات، نظرات خود را مطرح می نمایند و می توانند برای محصولات یا نظر سایر کاربران امتیازی در محدوده 1 تا 5 را انتخاب نمایند. نکته مهم در خصوص این سایت این است که کاربران می توانند بر اساس کیفیت و تشابه نظر سایر افراد با خودشان، ایشان را به شبکه اعتماد خود اضافه نمایند و شبکهای از افراد مورد اعتماد خود را تشکیل دهند و یا افراد ناشناس را که نظرات آنها مورد تایید نمی باشد را در لیست سیاه28 خود قرار دهند.
سیستم توصیهگری نیز که بر اساس شبکه اعتماد ایجاد میگردد به کاربران بر اساس نظرات افراد موجود در شبکه اعتماد29 ایشان و یا بر اساس نظرات افرادی که مورد اعتماد اعضای شبکه اعتماد باشند پیشنهاداتی را ارائه مینماید.
یکی از مباحث مهم و مطرح در اینگونه شبکهها نحوه بیان و ارزیابی معیار اعتماد میان کاربران میباشد که روشهای بسیار متنوع و مختلفی در این خصوص موجود است که طبیعتا منتج به نتایج متفاوتی میگردند[17]. به عنوان مثال تعداد ارتباطات مستقیم و غیرمستقیم میان یک کاربر با کاربر دیگر می تواند بیان کننده میزان اعتماد میان ایشان باشدکه این امر به صورت کلی باعث ارائه جوابهای قابل قبولتری میگردد[18]. نحوه بیان معیار اعتماد و اندازه گیری آن، خود یکی از موضوعات قابل تحقیق و بررسی است که از محدوده این تحقیق خارج بوده و در این تحقیق وجود یک شبکه مبتنی بر اعتماد میان کاربران به عنوان یکی از فرضیه های تحقیق در نظر گرفته میشود و به منظور محاسبه اندازه و مقدار اعتماد میان کاربران از نتایج تحقیق صورت گرفته در این خصوص بهرهبرداری میگردد[19].
1-7- تشریح و بیان مسئله
در یک سیستم توصیهگر بطور معمول مجموعهای از کاربران30 وجود دارد که به صورت مجموعهU={u1,u2,…,uN} نمایش داده میشود و مجموعهای از موضوعات و اشیا31 موجود میباشد که به صورت مجموعهI={i1,i2,…,iM} نمایش داده میشود بطوریکه هر کاربر به تعدادی از اشیا یا موضوعات امتیازی تخصیص میدهد که به صورت مجموعه RIu={iu1,iu2,…,iuk} نمایش داده می شود و امتیاز کاربر u به آیتمi به صورت ru,i بیان میگردد. ru,i میتواند یک عدد اعشاری باشد ولی در اکثر مواقع این عدد به صورت صحیح و در بازه ]5,1[ بیان میگردد.
در یک سیستم توصیهگر مبتنی بر شبکه اعتماد، علاوه بر مطالب فوق رابطه اعتماد میان دو کاربر u و v، با متغیر tu,v نمایش داده می شود و مقدار آن عددی اعشاری در بازه ]1,0[ میباشد. مقدار صفر برای متغیر tu,v نشان دهنده عدم وجود اعتماد میان دو کاربر و مقدار یک بیانگر وجود رابطه اعتماد کامل میان دو کاربر میباشد. در اکثر شبکههای اعتماد همچون32eBay، مقدار رابطه اعتماد به صورت مقدار دوتایی صفر و یک در نظر گرفته میشود. مجموعه TUu نشان دهنده مجموعه کاربرانی میباشد که به صورت مستقیم مورد اعتماد کاربر u میباشند و به صورتTUu={v ϵU | tu,v =1} تعریف میگردد.
با توجه به تعاریف فوق، شبکه اعتماد را می توان به صورت یک گرافG=<U,TU> تعریف نمود که در آنTU={(u,v)| u ϵ U , v ϵ TUu}میباشد و در واقع هر گره در این گراف بیانگر یک کاربر و یال میان هر دو گره بیانگر رابطه اعتماد میان ایشان میباشد و مقدار یال بیانگر اندازه اعتماد میان دو فرد خواهد بود. وظیفه سیستم توصیهگر با توجه به تعاریف و مفاهیم فوق به صورت زیر بیان میشود:
“در صورتیکه کاربر u عضو مجموعه U و آیتمi عضو مجموعه I باشد به صورتیکه ru,i نامشخص باشد، پیشبینی امتیازدهی کاربر u به آیتمi وظیفه سیستم توصیهگر میباشد. به کاربر u کاربر مبدا33 و به آیتم i آیتم مقصد34 اطلاق میگردد و امتیاز پیشبینی شده توسط سیستم با r ̂_(u,i) نمایش داده میشود”[20].
در اکثر مواقع، کاربران به درصد اندکی از آیتم ها امتیاز می دهند و در خصوص آنها نظرات خود را بیان می کنند که این امر باعث می گردد برای اکثر زوجهای <u,i>مقدار ru,i نامشخص باشد که این مسئله یکی از مسائل قابل تامل و مهم در خصوص طراحی مدل سیستم توصیهگر میباشد.
1-8- اهداف تحقیق
با توجه به مطالعات انجام شده و همچنین بررسی روشها، الگوریتمها، مقالات ژورنالها و کنفرانسهای معتبر در زمینه سیستمهای توصیهگر و با توجه به زمینه اصلی موضوع پایان نامه در رابطه با بهبود و پیادهسازی یک سیستم ترکیبی مبتنی بر شبکه اعتماد، مهمترین اهداف و دستاوردهای این تحقیق عبارتند از:
بررسی نقاط ضعف و قوت مدلهای ترکیبی موجود
ترکیب روش مبتنی بر اعتماد با یکی از روشهای موجود در زمینه پالایش گروهی
پیاده سازی و بهبود مدل TrustWalker[20] به عنوان یک مدل ترکیبی نوین و برتر از طریق ایجاد تغییر در نحوه پیمایش شبکه اعتماد میان کاربران
بهبود دقت پیشبینی امتیازات کاربران به آیتمهای مختلف به کمک پیادهسازی و بکارگیری مکانیزمی جهت تفسیر و تعدیل نظر کاربران
کاهش خطا و افزایش درصد پوشش در زمان ارائه پیشنهاد به کاربران تازه وارد
محاسبه میزان دقیق اعتماد میان کاربران عضو شبکه اعتماد به صورت اعشاری با بکارگیری روشها و دیدگاه های مختلف در این زمینه[19] به جهت افزایش و بهبود دقت و در نظر گرفتن مقدار محاسبه شده بجای مقدار صفر یا یک
پالایش شبکه اعتماد گسترده میان کاربران به نحوی که مدل پیشنهاد شده بر روی داده های کمتری اجرا گردد.
1-9- سوالات و فرضیههای تحقیق
فرضیههای موجود در این تحقیق عبارتند از:
وجود یک شبکه مبتنی بر اعتماد میان کاربران
بیان اعتماد میان کاربران در قالب یک عدد صحیح یا اعشاری در بازه ]1,0[
مبنا و اساس قراردادن پیاده سازی شخصی انجام گرفته از مدل TrustWalker به عنوان یکی از مدلهای برتر در زمینه موضوع تحقیق
اعتماد و تکیه بر نتایج تحقیقات و مقالات معتبر مورد ارجاع قرار گرفته در زمینه سیستمهای توصیهگر مبتنی بر شبکه اعتماد میان کاربران
وجود دادهها و نتایج تحقیقات قبلی صورت گرفته بر روی مجموعه داده Epinions35
سوالات مطرح نیز عبارتند از:
آیا ترکیب روش پالایش گروهی و روش مبتنی بر اعتماد باعث بهبود عملکرد سیستم توصیهگر میگردد؟
آیا عمق پیمایش شبکه اعتماد میان کاربران تاثیری بر روی نتایج دارد؟
آیا بکارگیری روش مبتنی بر آیتم در مقابل روش مبتنی بر کاربر باعث بهبود نتایج میگردد؟
آیا تعدیل و تفسیر نظرات کاربران باعث افزایش دقت و بهبود نتایج میگردد؟
از میان انواع روشهای محاسبه اندازه اعتماد میان کاربران کدام روش نتایج قابل قبولتری را ارائه مینماید؟
ترکیب روشهای موجود چه تاثیری بر روی درصد پوشش خواهد گذاشت؟
وجود شبکه اعتماد میان کاربران تا چه حد به حل مشکل ارائه توصیه به کاربران تازه وارد کمک مینماید؟
چه معیارهایی برای محاسبه تشابه دو کاربر یا دو آیتم مد نظر قرار گیرند؟
ترکیب روش مبتنی بر اعتماد با کدامیک از سایر روشهای موجود در زمینه سیستمهای توصیهگر می تواند باعث بهبود نتایج گردد؟
مکانیزم پیمایش شبکه عظیم میان هزاران کاربر چگونه خواهد بود؟
1-10- مراحل تحقیق
مراحل پیشنهادی برای انجام تحقیق عبارتند از:
بررسی و مطالعه روشهای دادهکاوی مورد استفاده در سیستمهای توصیهگر
مطالعه و بررسی روشها، مدلها و الگوریتم های موجود در زمینه سیستمهای توصیهگر مبتنی بر اعتماد
جستجو و یافتن یکی از مدلهای برتر در زمینه سیستمهای توصیهگر ترکیبی مبتنی بر اعتماد
پیادهسازی مدل انتخاب شده به کمک یکی از زبانهای برنامه نویسی به جهت آشکار شدن نقاط ضعف و قوت آن و بررسی چگونگی امکان بهبود یا تغییر مدل مذکور
جمع آوری و یکپارچه نمودن داده های مربوط به مجموعه دادههای مورد استفاده جهت انجام آزمایشات در یک پایگاه داده مستقل
آنالیز، پالایش و استخراج دادههای مورد نیاز برای انجام آزمایشات از پایگاه داده ایجاد شده
تحقیق و بررسی نتایج مدل پیاده سازی شده با نتایج موجود از تحقیقات قبلی
تلاش در جهت رفع نقایص و بهبود نتایج بدست آمده از طریق انجام اصلاحات در روش پایه یا ترکیب آن با سایر روشهای مطالعه شده
آزمایش میزان دقت، خطا و درصد پوشش مدل جدید با دادههای واقعی، بررسی نتایج، رفع نقایص و تکرار آزمایشات
مدون نمودن نتایج مدل جدید و ارائه علمی آنها
جمع بندی و بحث پیرامون نتایج
1-11- فصول پایاننامه
این پایان نامه در پنج فصل تنظیم و مدون شده است .در ادامه مقدمه که در فصل اول بیان گردید در فصل دوم ادبیات تحقیق مورد استفاده در زمینه سیستمهای توصیهگر، انواع روشها و مدلهای دادهکاوی موجود، با ذکر جزئیات و چگونگی عملکرد آنها و مباحث موجود در خصوص هر کدام از روشها و الگوریتمها تشریح میگردند. در فصل سوم مروری بر سیر تکاملی و تحقیقات گذشته انجام شده در زمینه سیستمهای توصیهگر ترکیبی و مبتنی بر اعتماد و بحث پیرامون نقاط ضعف و قوت آنها مطرح میگردد. در فصل چهارم جزئیات مدل ترکیبی پیشنهادی، مکانیزم الگوریتم و چگونگی عملکرد آن به صورت کامل تشریح میگردد و سعی در بررسی نکات و پاسخگویی به سوالاتی میشود که در این تحقیق به دنبال یافتن راهکار و پاسخی مناسب برای آنها هستیم. در فصل پنجم مجموعه دادههای مورد استفاده جهت انجام آزمایشات معرفی و چگونگی آماده سازی دادههای مورد نیاز جهت انجام آزمایشات بیان میگردند و نتایج بدست آمده از انجام آزمایشات مختلف و اجرای مدل پیشنهادی در شرایط گوناگون جمعآوری و مورد آنالیز، تحلیل و بحث قرار میگیرد و نهایتا در فصل آخر ضمن جمعبندی و ارائه نتایج کلی، پیشنهاداتی نیز برای تحقیقات آینده ارائه خواهد شد.
فصل دوم
مروری بر ادبیات تحقیق و مبانی نظری تحقیق
2- مروری بر ادبیات تحقیق و مبانی نظری تحقیق
2-1- مقدمه
در سالهای اخیر از تکنیکها و روشهای مختلف آماری، دادهکاوی، هوش مصنوعی و الگوریتمهای ریاضی در پیادهسازی سیستمهای توصیهگر استفاده شده است که از معروفترین و مهمترین این روشها و تکنیکها می توان به روش پالایش گروهی، پالایش محتوایی، گرافکاوی، روشهای مبتنی بر اعتماد و روش های ترکیبی نام برد .
در ادامه به تفصیل به معرفی و شرح هر کدام از روشهای فوق پرداخته میشود و نحوه کاربرد، نقاط ضعف و قوت آنها بیان میگردد. روشها و مدلهای فوق به صورت کلی به دو دسته مبتنی بر مدل36 و مبتنی بر حافظه37 تقسیم بندی میگردند که به لحاظ سرعت، هزینه اجرا، دقت، تک هدفی یا چند هدفی بودن، در نظر گرفتن نیازهای کوتاه مدت و بلند مدت کاربران با یکدیگر تفاوت دارند و هریک در پارهای از موضوعات کاربرد مناسبتر و راندمان بهتری دارند.
از میان روشهای فوق روش پالایش گروهی و پالایش محتوایی از سابقه نسبتا زیادی برخوردار میباشند و تحقیقات بسیار زیادی توسط محققان در خصوص موضوعات مرتبط با آنها، بهبود و بکارگیری در محیطهای مختلف مطرح گردیده است و بخش عمده ای از مطالب را به خود اختصاص میدهند، اما در مقابل، موضوع سیستمهای توصیهگر مبتنی بر اعتماد به تازگی مورد توجه محققان قرار گرفته است و از سابقه نسبتا کمی برخوردار است لذا به نسبت روشهای پیشین، تحقیقات اندکی در این حوزه صورت گرفته است و حجم اندکی از تحقیقات را به خود اختصاص می دهد. در ادامه، در هریک از بخشها به بررسی و مطالعه یکی از این روشها پرداخته می شود.
2-2- پالایش گروهی (Collaborative Filtering)
پالایش گروهی از بررسی رفتار گذشته کاربران و تشابه آنها با یکدیگر مدلی ایجاد مینماید[21] و سپس از آن مدل برای پیشبینی آیتمهای مورد علاقه کاربر یا پیشبینی امتیازدهی یک کاربر به یک آیتم خاص استفاده مینماید. این روش در واقع سعی در مدل نمودن پروسه اجتماعی نظرخواهی از دوستان و توجه به توصیههای آشنایان و اطرافیان دارد. یکی از مزایای اصلی این روش عدم وابستگی به محتوای قابل آنالیز به صورت مکانیزه میباشد و بنابراین بدون نیاز به داشتن اطلاعات کافی و درک دقیق از ماهیت یک آیتم پیچیده همچون “فیلم” امکان ارائه پیشنهاداتی در زمینه فیلم را دارا می باشد.
رفتار گذشته کاربر می تواند شامل تراکنشهای گذشته کاربر یا نظرات بیان شده وی در خصوص یک محصول خاص باشد، به عنوان مثال کاربر x به 4 فیلم امتیاز 5 را اختصاص داده است، یک سیستم توصیهگر با تکیه بر شیوه پالایش گروهی، اطلاعات در دسترس را پردازش میکند و کلیه کاربرانی را که به همان 4 فیلم امتیاز 5 را اختصاص دادهاند را جستجو نموده و لیست سایر فیلمهای مورد علاقه ایشان را به کاربر x توصیه میکند.
دیاگرامی از چگونگی کارکرد روش پالایش گروهی در شکل2-1 نشان داده شده است. همان طور که در تصور قابل مشاهده است سطرهای ماتریس m×n نشان دهنده کاربران و ستونها بیانگر آیتمها میباشند و هر سلول ماتریس بیانگر امتیازی است که توسط کاربر m به آیتم n داده شده است. مقدار هر سلول عددی در بازه ]5,1[ می باشد که مقدار 0 بیانگر این است که کاربر به آیتم مورد نظر امتیازی تخصیص نداده است [22].

شکل 2-1 : چگونگی کارکرد



قیمت: تومان

دسته بندی : پایان نامه ها

دیدگاهتان را بنویسید