۲-۷-۱- معیار همبستگی پیرسون……………………………………………………………………………………………۲۸
۲-۷-۲- معیار اندازه گیری کسینوس………………………………………………………………………………………..۲۹
۲-۸- انتخاب همسایه……………………………………………………………………………………………………………….۳۰
۲-۸-۱- استفاده از حد آستانه………………………………………………………………………………………………….۳۰
۲-۸-۲- انتخاب تعداد ثابتی از همسایگان……………………………………………………………………………….۳۰
۲-۹- پیش بینی و تخمین رتبه…………………………………………………………………………………………………۳۱
۲-۹-۱- استفاده از امتیازهای خام……………………………………………………………………………………………۳۱
۲-۹-۲- استفاده از امتیازهای نرمال شده………………………………………………………………………………..۳۱
۲-۱۰- مشکلات فیلترینگ اشتراکی………………………………………………………………………………………..۳۲
۲-۱۰-۱- پراکنده بودن داده…………………………………………………………………………………………………….۳۲
۲-۱۰-۲- مقیاس پذیری………………………………………………………………………………………………………….۳۲
۲-۱۰-۳- اقلام مشابه……………………………………………………………………………………………………………….۳۳
۲-۱۰-۴- گریشیپ…………………………………………………………………………………………………………………۳۳
۲-۱۱- بررسی چگونگی کارکرد سایت آمازون…………………………………………………………………………۳۳
فصل ۳ : روش محتوا محور………………………………………………………………………………………………………۳۶
۳-۱- پیشگفتار………………………………………………………………………………………………………………………….۳۷
۳-۲- روند کار روش محتوا محور……………………………………………………………………………………………..۳۷
۳-۲-۱- تحلیلگر محتوا…………………………………………………………………………………………………………..۳۸
۳-۲-۲- یادگیرنده نمایه …………………………………………………………………………………………………..۳۹
۳-۲-۳- جزء فیلترینگ…………………………………………………………………………………………………………….۴۲
۳-۳- مزایای روش محتوا محور………………………………………………………………………………………………..۴۲
۳-۳-۱- استقلال کاربر……………………………………………………………………………………………………………..۴۲
۳-۳-۲- شفافیت……………………………………………………………………………………………………………………….۴۲
۳-۳-۳- قلم جدید…………………………………………………………………………………………………………………….۴۳
۳-۴- معایب روش محتوا محور…………………………………………………………………………………………………۴۳
۳-۴-۱- کمبود محتوا……………………………………………………………………………………………………………….۴۳
۳-۴-۲- خصوصی سازی افزون…………………………………………………………………………………………………۴۳
۳-۴-۳- کاربر جدید………………………………………………………………………………………………………………….۴۴
فصل ۴ : روش پیشنهادی………………………………………………………………………………………………………….۴۵
۴-۱- پیشگفتار………………………………………………………………………………………………………………………….۴۶
۴-۲- مروری بر کارهای انجام شده در این راستا……………………………………………………………………..۴۶
۴-۳- مقدمهای بر روش پیشنهادی…………………………………………………………………………………………..۴۸
۴-۴- روش پیشنهادی………………………………………………………………………………………………………………۴۸
۴-۴-۱- پیش پردازش………………………………………………………………………………………………………………۴۹
۴-۴-۱-۱- پیش پردازش بر روی پایگاه داده MovieLens………………………………………………..49
۴-۴-۱-۲- پیش پردازش بر روی پایگاه داده EachMovie………………………………………………..50
۴-۴-۲- وزندهی به اقلام…………………………………………………………………………………………………………۵۱
۴-۴-۳- انتخابهمسایگی…………………………………………………………………………………………………………۵۳
۴-۴-۴- پیش بینی……………………………………………………………………………………………………………………۵۴
فصل ۵ : آزمایشها و نتایج……………………………………………………………………………………………………….۵۶
۵-۱- پایگاه داده های مورد استفاده…………………………………………………………………………………………..۵۷
۵-۲- نحوه اجرای روش پیشنهادی روی پایگاه داده MovieLens……………………………………….57
۵-۳- نحوه اجرای روش پیشنهادی روی پایگاه داده ٍEachMovie……………………………………….58
۵-۴- معیارهایارزیابی………………………………………………………………………………………………………………۵۸
۵-۴-۱- میانگین خطای مطلق…………………………………………………………………………………………………۵۸
۵-۴-۲- دقت و فراخوانی………………………………………………………………………………………………………….۵۹
۵-۴-۳- معیار ارزیابیF1…………………………………………………………………………………………………………60
۵-۵- ارزیابی روش پیشنهادی توسط معیارهای معرفی شده…………………………………………………..۶۱
فصل ۶ : بحث و نتیجه گیری…………………………………………………………………………………………………….۶۶
۶-۱- بحث…………………………………………………………………………………………………………………………………۶۷
۶-۲- نتیجه گیری……………………………………………………………………………………………………………………..۶۷
۶-۴- پیشنهادات……………………………………………………………………………………………………………………….۶۸
مراجع………………………………………………………………………………………………………………………………………..۶۹
فهرست جدول ها
عنوان و شماره صفحه
جدول شماره ۱ : نمونههایی از سیستمهای پیشنهادگر و اقلام پیشنهادی آنها…………………………۷
جدول شماره ۲ : مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………61
جدول شماره ۳ : مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر EachMovie……………………………………………………………………………………………………………………………61
جدول شماره ۴ : مقایسه معیار دقت روش پایه و روش پیشنهادی، اعمال شده بر
MovieLens……………………………………………………………………………………………………………………………61
جدول شماره ۵ : مقایسه معیار دقت روش پایه و روش پیشنهادی، اعمال شده بر
EachMovie …………………………………………………………………………………………………………………………..62
جدول شماره ۶ : مقایسه معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………62
جدول شماره ۷ : مقایسه معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر EachMovie……………………………………………………………………………………………………………………………62
جدول شماره ۸ : مقایسه معیارF1 روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………62
جدول شماره ۹ : مقایسه معیارF1 روش پایه و روش پیشنهادی، اعمال شده بر
EachMovie……………………………………………………………………………………………………………………………62
جدول شماره ۱۰ : مقایسه میانگین خطای مطلق روش پیشنهادی با روشهای[۱۹] و [۲۰]…………………………………………………………………………………………………………………………………………..۶۵
فهرست تصاویر
عنوان و شماره صفحه
شکل شماره ۱: نمونههایی از موتورهای جستجوگر………………………………………………………………….۵
شکل شماره ۲ : نمونه صفحهای از سایت Movielens………………………………………………………….11
شکل شماره ۳ : نمونه صفحه درخواست امتیازدهی Movielens از کاربر…………………………….۱۲
شکل شماره ۴ : نمونه صفحه فیلمهای پیشنهادی از سوی Movielens به کاربر………………۱۳
شکل شماره ۵ : نمونه ماتریس امتیازدهی کاربران - اقلام………………………………………………………۲۲
شکل شماره ۶: فیلترینگ اشتراکی مبتنی بر اقلام………………………………………………………………..۲۵
شکل شماره ۷ : فیلترینگ اشتراکی مبتنی بر کاربران…………………………………………………………….۲۵
شکل شماره ۸ : روند تولید پیشنهاد در آمازون……………………………………………………………………….۳۴
شکل شماره ۹ : نمونه صفحهای از سایت آمازون…………………………………………………………………….۳۵
شکل شماره ۱۰ : ارائه پیشنهاد بر اساس کارت خرید مشتری……………………………………………….۳۵
شکل شماره ۱۱ : روند کار روش محتوا محور………………………………………………………………………….۳۸
شکل شماره ۱۲ : نمونه صفحهای از سایت آمازون…………………………………………………………………۴۰
شکل شماره ۱۳ :استفاده از روش محتوا محور در سایت آمازون…………………………………………..۴۱
شکل شماره ۱۴ : نمایش مفاهیم دقت و فراخوانی در حوزه بازیابی اطلاعات………………………..۵۹
شکل شماره ۱۵: رابطه معیار فراخوانی با معیار دقت……………………………………………………………..۶۰
شکل شماره ۱۶: مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر
MovieLens……………………………………………………………………………………………………………………………63شکل شماره ۱۷: مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر
EachMovie…………………………………………………………………………………………………………………………...63
شکل شماره ۱۸: مقایسه معیار دقت، فراخوانی و F روش پایه و روش پیشنهادی، اعمال شده بر EachMovie……………………………………………………………………………………………………………………...64
شکل شماره ۱۹: مقایسه معیار دقت، فراخوانی و F روش پایه و روش پیشنهادی، اعمال شده بر MovieLens………………………………………………………………………………………………………………………..64
فصل اول
مقدمه
۱- مقدمه
۱-۱- پیشگفتار
پیدایش اینترنت و وب جهان گستر[۱] موجب شده است که در رابطه با هر موضوع قابل تصور، حجم بسیار زیادی از اطلاعات وجود داشته باشد که کاربران[۲] بتوانند با بهره گرفتن از آن نیاز اطلاعاتی خود را برطرف سازند. افزایش روز افزون اطلاعات باعث شد که مشکل سربار اطلاعات[۳] به وجود آید و کاربران به تنهایی قادر به برطرف کردن نیازهای خود نباشند. . زیرا کاربران مجبور بودند به صورت بر خط[۴] تمامی صفحات را جستجو کنند تا بتوانند آن قسمتی را که مورد نیازشان است پیدا کنند. به همین دلیل موتورهای جستجوگر[۵] به وجود آمدند تا کاربران بتوانند با بهره گرفتن از آنها بدون نیاز به بررسی تعداد زیادی از صفحات به اطلاعات مورد نظرشان دسترسی پیدا کنند.
۱-۲- موتورهای جستجوگر
به عبارت دیگر یک موتور جستجوگر وب سایتی است که میتوان از آن برای پیدا کردن صفحات وب استفاده کرد. وقتی کاربر درخواست خود را در قالب کلمات کلیدی وارد موتور جستجوگر می کند موتور جستجوگر در بین بیلیونها صفحه وب جستجو کرده و به کاربر کمک می کند اطلاعاتی که به دنبال آن است را بیابد. با بهره گرفتن از این ابزار سرعت و دقت در جستجو بسیار افزایش یافت و کاربران توانستند به سادگی و در کمترین زمان به بهترین نتایج دست یابند.
انواع زیادی از موتورهای جستجوگر توسط کمپانیهای مختلف ساخته شده است که معروفترین آنها بینگ[۶]، یاهو[۷] و گوگل[۸] میباشد (شکل شماره ۱).
هر موتور جستجوگر راه و روش خود را برای سازماندهی اطلاعات دارد، پس نتیجه از یک موتور جستجوگر تا دیگری متفاوت خواهد بود.
موتورهای جستجوگر به دو دسته کلی تقسیم میشوند : موتورهای جستجوگر پیمایشی[۹] و فهرستهای تکمیل دستی[۱۰]. موتورهای جستجوگر ترکیبی[۱۱] نیز حاصل ترکیب دو نوع بالا میباشند. گونه ای جدید از موتورهای جستجوگر نیز تحت عنوان ابر جستجوگرها[۱۲] وجود دارد که در ادامه به طور خلاصه به توضیح هر کدام از این موارد خواهیم پرداخت.
۱-۲-۱- موتورهای جستجوگر پیمایشی
این موتورهای جستجوگر، وب را پیمایش و اطلاعاتی را ذخیره می کنند. سپس کاربران از میان این اطلاعات آنچه را که میخواهند جستجو می کنند. اگر در صفحه وب تغییراتی اعمال شود موتورهای جستجوگر پیمایشی به طور خودکار آنها را مییابند و تغییرات مذکور را در فهرستها اعمال می کنند. نمونههایی ازموتورهای جستجوگر پیمایشی گوگل و یاهو میباشند.
۱-۲- ۲- فهرستهای تکمیل دستی
فهرستهای تکمیل دستی وابسته به کاربرانی میباشد که آن را تکمیل می کنند. یا کاربر خودش صفحه مورد نظر را به همراه توضیحی کوتاه در فهرست ثبت می کند یا این کار توسط ویراستارهایی که برای آن فهرست در نظر گرفته شده صورت میپذیرد. در این حالت عمل جستجو تنها بر روی توضیحات ثبت شده انجام میگیرد و اگر تغییری روی صفحه وب به وجود آید در فهرست تغییر به وجود نخواهد آمد. نمونه ای از فهرستهای تکمیل دستی
Open Directoryمیباشد[۱۳].
۱-۲-۳- موتورهای جستجوگر ترکیبی
این موتورهای جستجوگر نتایج حاصل از جستجوی هر دو نوع بالا را با هم ترکیب می کنند و نشان می دهند. علاوه بر این میتوانند برای نتایج یک نوع، اولویت قائل شوند. مثلا موتور جستجوی MSN اولویت را روی نتایج حاصل از فهرستهای تکمیل دستی قرار میدهد. ولی برای درخواستهای پیچیده، نتایج حاصل از جستجوی پیمایشی را نیز بررسی می کند.
۱-۲-۴- ابر جستجوگرها
این نوع جدید از موتورهای جستجوگر نتایج حاصل از چند موتور جستجوگر را ترکیب نموده و نشان میدهد. به عبارتی دیگر درخواست کاربر را در چندین موتور جستجوگر جستجو کرده، سپس نتایج یافته شده را با هم ترکیب نموده و یک نتیجه کلی در اختیار کاربر قرار میدهد. به عنوان مثال موتور جستجوگر dogpile[14] نتایج حاصل از موتورهای جستجوگرGoogle ، Yahoo، MSN و ASK را با هم ترکیب میکند و به کاربر ارائه میدهد.
شکل شماره ۱ : نمونههایی از موتورهای جستجوگر
۱-۳- سیستمهای پیشنهادگر
مطالعات اخیر نشان دادهاند که عمده موتورهای جستجوگر با نرخ پایین موفقیت مواجه هستند. این نرخ با میزان دریافت نتایج مرتبط، نسبت به میانگین کاربران جستجو کننده تعیین می شود. به عنوان مثال در یکی از مطالعات[۱] بیش از ۲۰۰۰۰ درخواست جستجو بررسی شده و مشخص گردیده که به طور میانگین در ۴۸% موارد، کاربر در نتایجی که به او ارائه شده حداقل یک مورد مرتبط با جستجویش که ارزش انتخاب داشته باشد پیدا می کند. به بیان دیگر در ۵۲% موارد، کاربر هیچ کدام از مواردی را که به عنوان نتیجه جستجو به او بازگشت داده می شود انتخاب نمیکند. البته این مشکل همان قدر که به موتور جستجوگر بستگی دارد به میزان دانش کاربر جستجو کننده در چگونگی نحوه جستجو نیز بستگی دارد. زیرا درخواست جستجو ممکن است منجر به ابهام شود و به ندرت می تواند به روشنی نیاز کاربر جستجو کننده را بیان کند. در این مواقع کاربر با لیست نتیجهای که نمیتواند نیاز اطلاعاتی او را برطرف سازد روبرو می شود. او در این شرایط معمولا درخواست خود را تعویض یا اصلاح می کند تا نتیجه دلخواهش به او ارائه شود.
در [۲] نشان داده است که ۱۰% از درآمد کسانی که با اطلاعات کار می کنند به دلیل تلف شدن زمانشان در جستجو از بین میرود. همچنین در بدترین حالت درصد قابل توجهی از جستجو کنندهها ممکن است در پیدا کردن اطلاعاتی که مورد نیازشان است با شکست روبرو شوند. این مسائل نشان میدهد که جستجوی وب بسیار ناکارامدتر از آن است که انتظار می- رود. همچنین علاوه بر افزایش تعداد صفحات وب تعداد کاربران اینترنت نیز به شدت افزایش یافت. کاربران هم میخواستند نیاز اطلاعاتیشان را بر طرف کنند و هم مایل به تولید و اشتراک گذاری اطلاعات، علائق و نیازمندیهای خود بودند. بنابراین شبکه های اجتماعی مانند Facebook و Twitter تاسیس شدند. همچنین سایتهایی مانند YouTube راه اندازی شد که محلی برای اشتراک گذاری فیلمها و مشاهده فیلمهای به اشتراک گذاشته میباشد.
در این بین برای برطرف نمودن ناکارامدیهای موتورهای جستجوگر و نیازهای کاربران سیستمهای پیشنهادگر به وجود آمدند.
سیستمهای پیشنهادگر برای انتخاب و ارائه اطلاعات مورد نیاز کاربران نقش قابل توجهی را ایفا نموده اند. این سیستمها میتوانند حتی بدون اینکه کاربر درخواست جستجو بدهد تعدادی از اقلام را به او پیشنهاد یا اطلاعات مورد نیازش را به او ارائه دهد. اقلام میتوانند فیلم، موزیک، صفحه وب و… باشند (جدول شماره ۱). همچنین کاربر پیشنهاداتی را از طریق یک جستجوی هوشمندانه دریافت خواهد کرد. بنابراین تاثیر به سزایی در صرفه جویی زمان و دست یابی به هدف مورد نظر کاربر دارد. زیرا از این طریق می تواند از میان این حجم بالا آن قسمت که مورد نیازش است را در اختیار داشته باشد. بدین ترتیب از سردرگم شدن کاربر هنگام تصمیم گیری جلوگیری به عمل می آید.
جدول شماره ۱ : نمونههایی از سیستمهای پیشنهادگر و اقلام پیشنهادی آنها
| SYSTEM | Content |
| Amazon | Books, CDS, Others |
| Epinions | Books, CDS, Others |
| MovieLens | Movie |
| Netflix | DVD |
| Yahoo! Music | Music |
| Grundy | Books |
| Video Recommender | Video |
| Ringo | Music |
| PHOAKS | Textual Information |
| Jester | Jokes |
| Fab System | Web page |
با افزایش روز افزون اطلاعات، نیاز به وجود این سیستمها بیشتر احساس شده است. این سیستمها پیشنهادات را با بهره گرفتن از انواع مختلف دانش و داده جمع آوری شده در مورد کاربران و اقلام و همچنین بررسی تراکنشهایی مانند بازخوردی[۱۵] که کاربران در گذشته ایجاد کرده اند تولید می کنند. در سادهترین فرم، این پیشنهادات به صورت یک لیستی که بر اساس علائق و نیازهای کاربر مرتب شده به او عرضه خواهد شد.
در [۳] سیستمهای پیشنهادگر براساس فیلترینگ اشتراکی[۱۶]، محتوا[۱۷]، آمارگیری[۱۸]، سود[۱۹]، دانش[۲۰]،و ترکیبی[۲۱] کلاسبندی شدهاند.
۱-۳-۱- سیستم پیشنهادگر بر اساس فیلترینگ اشتراکی
فیلترینگ اشتراکی یکی از رایجترین راهکارها در سیستمهای پیشنهادگر است .[۴] این راهکار اقلامی که کاربران مشابه با کاربر فعال در گذشته به آنها علاقه داشته اند را به او پیشنهاد می کند. شباهت بین کاربران بر اساس نحوه امتیازدهیشان در گذشته محاسبه می شود.
این پایان نامه بر اساس این نوع از سیستمهای پیشنهادگر میباشد که در فصل دوم به تفصیل توضیح داده خواهد شد.
۱-۳-۲- سیستم پیشنهادگر محتوا محور
یکی از پر کاربردترین راهکارها در سیستمهای پیشنهادگر روش محتوا محور میباشد. سیستمهای محتوا محور بر اساس ویژگیهای اقلام تعریف میشوند. آنها بررسی می کنند که کاربر در گذشته چه اقلامی مورد علاقهاش بوده، سپس اقلام مشابه را به او پیشنهاد می دهند. مثلا اگر کسی در گذشته به فیلمی از نوع کمدی امتیار مثبت داده است این سیستم در آینده فیلمهایی از این نوع را به او پیشنهاد می کند. از آنجا که روش پیشنهادی در این پایان نامه از روش محتوا محور استفاده می کند، در فصل پنجم به طور مفصل در مورد سیستم پیشنهادگر محتوا محور بحث خواهد شد.
۱-۳-۳- سیستم پیشنهادگر بر اساس آمارگیری
تکنیک پیشنهاد براساس آمارگیری مبتنی بر اطلاعات آماری کاربران میباشد. دادههایی که در نمایه[۲۲] کاربر وجود دارد مانند جنسیت، سن، وضعیت خانوادگی و … نمونههایی از اطلاعات آماری کاربر میباشد. کاربران بر اساس خصوصیاتشان کلاس بندی میشوند و پیشنهادات بر اساس این کلاسها صورت میپذیرد.
۱-۳-۴- سیستم پیشنهادگر بر اساس سود
سیستمهای بر اساس سود، تابع سود[۲۳] که توسط کاربر تولید می شود را به کار میبرند. به عنوان مثال درقالب پرسشنامه این کار صورت میپذیرد. سپس بر اساس اینکه هر قلم[۲۴] چه مقدار سود برای کاربر دارد پیشنهادات صورت میگیرد. این نوع از سیستمها تکنیکهای ارضای محدودیت[۲۵] را به کار میبرند تا بهترین قلم را پیشنهاد کنند.
۱-۳-۵- سیستم پیشنهادگر بر اساس دانش
سیستمهای پیشنهادگر بر اساس دانش، از دانشی که از خصوصیات اقلام و کاربران استخراج میگردد بهره برداری می کنند. آنها بررسی می کنند که چطور یک قلم بهخصوص می تواند نیازهای کاربر را بر آورده سازد. در سادهترین فرم، دانش مذکور می تواند در فرم درخواست توسط کاربر تولید شود.
۱-۳-۶- سیستم پیشنهادگر ترکیبی
سیستمهای پیشنهادگر ترکیبی دو یا چند تکنیک را ترکیب می کنند تا کارایی سیستم پیشنهادگر را افزایش دهند. مثلا دو تکنیک A وB را ترکیب می کنند که از مزایای تکنیک اول برای بر طرف سازی معایب تکنیک دوم استفاده کنند. مثلا متد فیلترینگ اشتراکی با مشکل قلم جدید و کاربر جدید مواجه میباشد. یعنی قلمی که تا کنون هیچ کس به آن امتیازی نداده است را نمیتواند پیشنهاد کند. در عین حال متد بر اساس محتوا به دلیل اینکه پیشنهادات بر اساس محتوا و ویژگیهای اقلام میباشد نه امتیازات داده شده به آنها، چنین مشکلی را ندارد. پس میتوان از ترکیب این دو متد در برطرف کردن نواقص یکدیگر استفاده نمود.
۱-۴- بررسی سایت Movielens
MovieLens یک سیستم پیشنهادگر فیلم است (شکل شماره ۲). راهکار این سیستم به این صورت است که از کاربر میخواهد به فیلم هایی که تا کنون دیده است در بازه ۱ تا ۵ امتیازدهی کند (شکل شماره ۳). پس از آن امتیازات داده شده از سوی کاربر را ذخیره کرده و از کاربر یک مدل میسازد. زمانی که کاربر درخواست می کند که سیستم فیلمهایی را به او پیشنهاد کند، سیستم مدل کاربر فعال[۲۶] و همچنن مدل کاربرانی که شبیه به او میباشند را استخراج کرده و امتیاز فیلمهایی که کاربر فعال تا کنون ندیده است را از روی مدل کاربران شبیه به او پیش بینی می کند. سپسفیلمهایی که برای آنها امتیاز بالایی پیش بینی شده است را به کاربر فعال پیشنهاد می کند. کاربر لیست پیشنهاد شده از سوی سیستم را مشاهده کرده و فیلمهای مورد علاقهاش را انتخاب می کند (شکل شماره ۴).
شکل شماره ۲ : نمونه صفحهای از سایت Movielens [5]
شکل شماره ۳: نمونه صفحه درخواست امتیازدهی Movielens از کاربر [۵]
شکل شماره ۴ : نمونه صفحه فیلمهای پیشنهادی از سوی Movielens به کاربر [۵]
۱-۵- اهداف پایان نامه
روشهای محتوا محور و فیلترینگ اشتراکی از راهکارهای موفق در سیستمهای پیشنهادگر میباشند. روش محتوا محور بر اساس ویژگیهای اقلام تعریف می شود. این روش بررسی می کند که اقلام مورد علاقه کاربر دارای چه ویژگیهایی بوده اند، سپس اقلام دارای ویژگیهای مشابه را به او پیشنهاد می کند. روش فیلترینگ اشتراکی بر اساس تعیین اقلام مشابه یا کاربران مشابه کار می کند که به ترتیب فیلترینگ اشتراکی مبتنی بر اقلام و مبتنی بر کاربران نامیده می شود.
روش پایه فیلترینگ اشتراکی مبتنی بر کاربر، به منظور پیش بینی امتیاز قلم هدف، هیچ تمایزی بین اقلام قائل نمی شود. به عبارت دیگر امتیازهای تمامی اقلام به طور یکسان در انتخاب همسایگی (کاربران مشابه) و پیش بینی تاثیر میگذارند. در این پایان نامه یک سیستم پیشنهادگر فیلترینگ اشتراکی مبتنی بر کاربر، مجهز به مکانیزم تخصیص پویای وزن به اقلام، ارائه شده است. مبنای این مکانیزم، تخصیص وزن به اقلام بر اساس میزان شباهت آنها با قلم هدف میباشد. میزان شباهت اقلام توسط یک روش محتوا محور سنجیده می شود. از آنجا که پایگاه داده مورد استفاده در این پایان نامه مربوط به فیلم است، برای بالا بردن کارایی این روش علاوه بر استفاده از ویژگی ژانرها، از ویژگیهای دیگری از جمله کارگردانان و بازیگران به عنوان داده های مکمل استفاده شده است.
۱-۶- ساختار پایان نامه
از آنجا که اساس روش پیشنهادی در این پایان نامه فیلترینگ اشتراکی میباشد در فصل دوم به تفصیل به شرح این روش و تاریخچهای از کارهای انجام شده در این زمینه پرداخته می شود.
پس از آن به دلیل استفاده از روش محتوا محور به جهت ارتقا روش فیلترینگ اشتراکی، مبانی این روش در فصل سوم توضیح داده می شود.
در فصل چهارم روش پیشنهادی که تلفیقی از روشهای فیلترینگ اشتراکی و محتوا محور میباشد و کارهای انجام شده در این زمینه ارائه می شود.
در فصل پنجم آزمایشهای انجام شده بر روش پیشنهادی و نتایج حاصل از این آزمایشها ارائه میگردد.
در فصل ششم به جمعبندی مطالب، نتیجه گیری و ارائه پیشنهادهایی برای آینده پرداخته می شود.
فصل دوم
روش فیلترینگ اشتراکی
۲- روش فیلترینگ اشتراکی
۲-۱- پیشگفتار
این پایان نامه بر فیلترینگ اشتراکی که نوعی از سیستمهای پیشنهادگر میباشد متمرکز شده است. این نوع از سیستم های پیشنهادگر نقش قابل توجهی را در پیدا کردن سلیقه و علائق کاربر ایفا می کند. انگیزه پیدایش فیلترینگ اشتراکی از اینجا به وجود آمد که مردم معمولا بهترین پیشنهادات را از کسانی میگیرند که سلیقهشان مشابه با خودشان است. این متد، کاربران با سلیقه شبیه به هم را پیدا می کند و بر این اساس پیشنهادات را ارائه میدهد.
۲-۲- مروری بر کارهای انجام شده در این راستا
در [۶] اولین سیستم پیشنهادگر رسمی که tapestry نامیده می شود ارائه شد. این یک سیستم برای مدیریت ایمیل بود و تصدیق کرد که یک لیست ایمیل ساده نمیتواند به تمام کاربرانی که علاقهمند به محتوای یک ایمیل هستند اطمینان دریافت آن را بدهد. بنابراین به کاربران اجازه شرح پیام ایمیلها را داد تا دیگران با ساختن پرسش بتوانند آنها را فیلتر کنند. اندکی بعد محققان دریافتند که این لیست ایمیل و فیلترینگ بر اساس محتوا در رابطه با نیازهای اطلاعاتی پیچیده کاربر کافی نیست. بنابراین، این عقیده مطرح شدکه سیستم با به کاربردن عامل انسان ارتقاء خواهد یافت. عبارت فیلترینگ اشتراکی به منظور توصیف اینکه چطور کاربران میتوانند با تولید کردن بازخورد به فیلترینگ پیام ها کمک کنند به کار برده شد. این بازخورد شامل ارسال، دریافت پیام و … میباشد.
در [۷]تحقیق در مورد فیلترینگ اشتراکی با بهره گرفتن از الگوریتم مبتنی بر همسایگی برای اخبارUsenet انجام شده است. قابل ذکر است که Usenet نوعی شبکه اینترنتی میباشد. این کار توسط سیستمی که GroupLensنامیده می شود انجام پذیرفت[۸] . GroupLens که سیستمی پیشنهادگر بر اساس کاربر است به منظور ارزیابی و پیشنهاد دادن اقلام به کاربر از امتیازهای ۱ تا ۵ که دیگر کاربران به این اقلام نسبت دادهاند استفاده می کند. اکنون MovieLens که یک سیستم پیشنهادگر فیلم است راه اندازی شده است. سیستم Grouplens از معیار همبستگی پیرسون[۲۷] برای نشان دادن میزان شباهت کاربران به یکدیگر استفاده می کند (فرمول شماره ۱).
(۱)
نشانگر امتیاز پیش بینی شده برای قلم i ام میباشد. n تعداد همسایهها را نشان میدهد، امتیاز کاربر uبه قلم iام و میانگین امتیازهای کاربر فعال میباشد. میزان شباهت بین کاربر فعال و همسایه u را نشان میدهد که به صورت همبستگی پیرسون در فرمول شماره ۲ تعریف شده است.
(۲)
در سال ۱۹۹۶ تکنولوژی GroupLens تحت NetPerceptionبه صورت تجاری درآورده شد. یکی از اولین کاربران تجاری GroupLens سرویس الکترونیکی خرده فروشی آمازون بود که به عنوان فروشگاه کتاب برخط راه اندازی شد.
در [۹]سیستم پیشنهادگر موزیک [۲۸]Ringoبراساس الگوریتم اصلی Grouplens توسعه یافت. Ringo اقلام را بر اساس امتیازهایی که کاربران مشابه به آنها داده بودند فیلتر میکرد. زمانی که کاربر در سیستم ثبت نام مینمود یک لیست از ۱۲۵ موسیقیدان محبوب که به طور تصادفی انتخاب شده بودند را در اختیار او قرار میداد و از کاربر میخواست که به اعضای این لیست امتیازهای بین ۱ تا ۷ بدهد. سپس ازکاربر یک نمایه میساخت. Ringo میزان شباهتها را با بهره گرفتن از همبستگی پیرسون محدود شده محاسبه کرد و برای تولید پیشنهاد میانگین تمامی کاربران موجود در همسایگی را به کار برد و مدعی کارایی بهتر شد. همانطور که در فرمول شماره ۳ نشان داده شده است عدد ۴ به این دلیل انتخاب شده که حد وسط بازه امتیازهای ۱ تا ۷ است. Ringo عضویت در همسایگی را فقط با انتخاب همسایگانی که همبستگی آنها بیشتر از یک حد آستانه ثابت است محدود کرد. با بزرگتر شدن حد آستانه دقت بیشتر می شود ولی تعداد اقلامی که سیستم پیشنهادگر قادر به پیش بینیشان است کاهش مییابد.
(۳)
به تدریج این سیستم به صورت تجاری در آورده شد و در سال ۱۹۹۵ نام آن به Firefly تغییر یافت. این سیستم حاوی یک رابط به صورت صفحه وب و فروشگاه دیسک فشرده[۲۹] رویخط بود و همچنین قادر بود برای انواع فیلم پیشتهاد تولید کند. این سیستم گسترش وسیعی کرد تا جایی که درسال ۱۹۹۸ توسطMicrosoft پذیرفته شد و به
Microsoft Passport تغییر یافت.
در [۱۰]سیستم پیشنهادگر ویدیو [۳۰]Bellcoreنیز بر اساس الگوریتم اصلی Grouplens توسعه یافت. سیستم پیشنهادگر ویدیو Bellcore از همبستگی پیرسون برای وزندهی تعدادی از همسایهها که به طور تصادفی انتخاب شده بودند استفاده نمود. سپس بهترین همسایگان را انتخاب و برای پیش بینی یک رگرسیون[۳۱] کامل چندگانه روی آنها اعمال کرد.
مهمترین اتفاق اخیر در رابطه با سیستمهای پیشنهادگر اعلام جایزهی Netflix در اواخر سال ۲۰۰۶ بوده است.Netflix انجمن کرایه DVDاز آمریکا، پایگاه دادهای از امتیازهایی که کاربران به فیلمها اختصاص دادهاند منتشر کرد که به روز بود و همچنان به عنوان بزرگترین مجموعه امتیازدهی کاربران باقی مانده است. آنها اجتماع وسیعی را برای بهترکردن پیش بینی سیستمشان به میزان حداقل ۱۰% به رقابت طلبیدند و جایزه یک میلیون دلاری برای آن درنظر گرفتند. بیشتر از ۲۰۰۰۰ تیم درطی ۳ سال به این موضوع پرداختند و طی این رقابت مسائلی ازقبیل فاکتورگیری ماتریس[۳۲]، متدهای جمعی[۳۳] و دینامیکهای موقتی[۳۴] یاد گرفته شد[۱۱] .
در [۱۲] یک تحلیل تجربی روی الگوریتمهای فیلترینگ اشتراکی مبتنی بر همسایگی انجام شد. برای تعیین میزان شباهت معیارهای همبستگی پیرسون و کسینوس[۳۵] با هم مقایسه شدند و دریافته شد که همبستگی پیرسون بهتر کار می کند. اگرچه پس از آن در [۱۲] اظهار شد که این دو معیار ممکن است یکسان عمل کنند.
در [۱۳] راهکار امید بخش تشخیص هویت[۳۶] برای سیستمهای فیلترینگ اشتراکی ارائه شده که مدل Bayesian و روشهای مبتنی بر همسایگی را ترکیب می کند. خصوصیت خوبی که این راهکار دارد این است که یک توزیع احتمالی از امتیاز به جای مقدار واقعی امتیاز تولید می کند. این توزیع می تواند برای مشخص کردن میزان اعتماد به پیش بینی استفاده شود. همچنین ادعا شده است که این راهکار برای داده های فیلم که شبیه به دادههایی است که ما در پژوهشها استفاده میکنیم در انتخاب نزدیکترین همسایهها دقیقتر از همبستگی عمل می کند.
در [۱۴] روشی ارائه شده که با بهره گرفتن از آن میتوان پارامترهای مربوط به فیلترینگ اشتراکی را برای هر کاربر شخصیسازی کرد. از جمله این پارامترها تعداد افرادی میباشد که در گروه همسایگی هر کاربر شرکت می کنند. این کار توسط شبیهسازی تکراری مجموعه داده های آموزشی و درستی سنجی برای هر کاربر به طور جداگانه صورت میگیرد.
در [۱۵] روشی برای حل مشکل پراکندگی امتیازها در ماتریس کاربران- اقلام ارائه شده است. این مشکل زمانی به وجود می آید که تعداد اقلام بدون امتیاز بسیار بیشتر از تعداد اقلام امتیازدهی شده باشد. در این روش ابتدا مدلهایی از فیلترینگ اشتراکی به کار برده میشوند تا امتیازهای اقلام بدون امتیاز پیش بینی شوند. سپس با بهره گرفتن از نتایج حاصل شده امتیاز قلم مورد نظر با اطمینان بیشتر تعیین میگردد.
در [۱۶]راه حلی برای مشکل شروع سرد[۳۷] در سیستمهای فیلترینگ اشتراکی ارائه شده است. مشکل شروع سرد زمانی به وجود می آید که سیستم بخواهد برای کاربری جدید که تا کنون امتیازی به اقلام نداده و یا قلمی جدید که تا کنون امتیازی از کاربران دریافت نکرده پیش بینی نماید. این روش به جای استفاده از بردار امتیازدهی به تنهایی، از ترکیب خطی یا آبشاری بردارهای شخصیت و بردارهای امتیازدهی برای تعیین میزان شباهت کاربران به یکدیگر استفاده می کند. بردار شخصیت، برداری دو قطبی است که هر مولفه آن تعیین کننده یک خصوصیت از شخصیت کاربر مورد نظر میباشد.
در [۱۷] راهکاری ارائه شده که توسط آن میتوان به گروهی از کاربران گروهی از اقلام را پیشنهاد کرد. در سیستمهای فیلترینگ اشتراکی معمولی اقلامی که برای پیشنهاد به هر کاربر میتوانند مناسب باشند به طور جداگانه مشخص و سپس از نتایج حاصل شده اشتراک گرفته می شود. در روش پیشنهاد شده از نزدیکترین همسایگان تمامی کاربران موجود در گروه موردنظر اشتراک گرفته می شود. حاصل یک مجموعه مشترک از همسایگان برای تمام کاربران موجود در گروه میباشد. سپس با بهره گرفتن از این همسایگان مشترک قلم یا اقلامی به گروه مذکور پیشنهاد میگردد.
در [۱۸] یک معیار جدید برای اندازه گیری میزان شباهت کاربران در سیستمهای فیلترینگ اشتراکی ارائه شده است. در این روش مشکل اختلاف ابعاد بین بردارهای امتیازدهی کاربران حل شده است. به بیان دیگر میزان شباهت دو کاربر با توجه به تعداد اقلامی که هر دو به آنها رای دادهاند تعیین میگردد. در صورتی که واحدهای اندازه گیری مانند همبستگی پیرسون این اختلاف ابعاد را در نظر نمیگیرند.
در [۱۹]راهکاری جدید برای فیلترینگ اشتراکی مبتنی بر حافظه ارائه شده است. در این روش پیشنهاد اقلام مستقل از بازه امتیازات کاربر و بر اساس احتمال[۳۸] پیش بینی است و بررسی شده است که چطور این احتمالات میتوانند برای جمع آوری انواع مختلف وابستگیها-ی بین امتیازها در راستای انتخاب نزدیکترین همسایهها مورد استفاده قرار گیرند. در این روش معیار انتخاب همسایگی به توانایی کاربر در پیش بینی امتیازهای گذشته بستگی دارد. فرضیه این بوده است که اگر کاربری در پیش بینی امتیازهای گذشته کاربر مورد نظرخوب بوده است در آینده هم برای پیش بینی امتیازهای او خوب خواهد بود.
در [۲۰] یک راهکار مبتنی بر هسته ارائه شده است. ایده اصلی این راهکار یافتن یک نگاشت چند خطی بین دو فضای برداری است. این راهکار بر اساس کاربران و بر اساس اقلام و همچنین تلفیق این دو مورد ارائه شده است. همچنین نشان داده شده است که چگونه میتوان اطلاعات تکمیلی نظیر ژانر فیلمها را در این راهکار استفاده و چگونه پیشنهاداتی قابل اعتماد با وجود مشکلاتی مانند پراکندگی و شروع سرد به کاربران ارائه نمود.
۲-۳- مبانی فیلترینگ اشتراکی
فیلترینگ اشتراکی یکی از بهترین راهکارها در سیستمهای پیشنهادگر میباشد. این روش به خاطر استفادهاش در سایتهای تجارت الکترونیک مانند AMAZOONو NETFLIX به خوبی شناخته شده است. این متد کاربرانی که علائقشان شبیه به کاربر فعال میباشند را پیدا کرده و از این طریق پیشنهادات را به او ارائه میدهد. یعنی فرض بر این است که کاربرانی که در گذشته تمایلاتی شبیه به هم داشته اند احتمالا در آینده هم تمایلات مشابه دارند و چون قبلا به اقلام به طور مشابه ابراز علاقه کرده اند به اقلامی که تا کنون ندیدهاند نیز به طور مشابه علاقه نشان خواهند داد. فیلترینگ اشتراکی معمولا به مشارکت داشتن کاربران فعال، راهی برای نشان دادن سلیقه کاربران به سیستم و الگوریتمی که کاربران با سلیقه مشابه را شناسایی کند نیازمند میباشد.
به طور کلی فضای اطلاعاتی در فیلترینگ اشتراکی مبتنی بر یک ماتریس M * N است که ماتریس کاربران - اقلام نام دارد. M نشان دهنده تعداد کاربران و N نشان دهنده تعداد اقلام میباشد. همانطور که در (شکل شماره ۵) مشاهده میکنید rm,n نشان دهنده نمرهای میباشد که کاربر m ام به قلم n ام اختصاص داده است.
شکل شماره ۵ : ماتریس امتیازدهی کاربران- اقلام
۲-۴- وظایف فیلترینگ اشتراکی
وظایف فیلترینگ اشتراکی به دو دسته ارائه پیشنهاد به کاربران و پیش بینی امتیاز اقلام دیده نشده تقسیم میشوند که در ادامه هر کدام را به تفکیک توضیح خواهیم داد.
۲-۴-۱- پیشنهاد
در این حالت لیستی از اقلام به کاربران ارائه می شود که بر حسب میزان مفید بودنشان برای کاربر مرتب شده اند. یعنیN مورد از بهترین پیشنهادات را به او ارائه میدهد. برای تولید پیشنهاد، اطلاعات مربوط به تمام اقلام نیاز نمی باشد.
۲-۴-۲- پیش بینی
در این حالت پیش بینی می شود که کاربر به قلمی که تا کنون ندیده است چه امتیازی خواهد داد. برای پیش بینی اطلاعات مربوط به تمام اقلام حتی آنهایی که به ندرت امتیازدهی شده اند مورد نیاز است. همچنین الگوریتمهایی که سیستم برای پیش بینی به کار میبرد به حافظه و زمان محاسباتی بیشتری نسبت به الگوریتمهای تولید پیشنهاد نیاز دارد.
۲-۵- دسته بندی متدهای فیلترینگ اشتراکی
متدهای فیلترینگ اشتراکی به دو گروه کلی فیلترینگ اشتراکی مبتنی بر همسایگی[۳۹] یا مبتنی بر حافظه[۴۰] و فیلترینگ اشتراکی مبتنی بر مدل[۴۱] تقسیم میشوند.[۱۲]
الگوریتمهای موجود در گروه فیلترینگ اشتراکی مبتنی بر همسایگی یا مبتنی بر حافظه نسبت به الگوریتمهای موجود در فیلترینگ اشتراکی مبتنی بر مدل رایجتر میباشند اما قابل ذکر است که این الگوریتمها نیازمند حافظه بیشتری هستند. از نظر کارایی الگوریتمهای موجود در گروه مدل محور نتایج قابل توجهی را ارائه می دهند. اما از نظر دقت به جز تحقیقات اخیر[۲۱] نتایج خوبی به دست نیاوردهاند. الگوریتمهای حافظه محور به طور عمده بر الگوریتم KNN استوار میباشند.
از تلفیق دو دسته مدل محور و حافظه محور مدل تلفیقی به وجود می آید که هدف آن تلفیق مزیت هر دو دسته است . [۲۲]هم اکنون تحقیقات در راه پیشروی به سمت مدل تلفیقی میباشد .[۲۳]
در راهکار مبتنی بر حافظه پیش بینی به دو صورت براساس کاربران و براساس اقلام انجام میپذیرد .[۲۴]اختلاف نظرهایی در مورد اینکه پیش بینی بر اساس اقلام مبتنی بر حافظه و یا مبتنی بر مدل است وجود دارد ؛ در [۲۵] اعلام شده است که الگوریتمهای بر اساس اقلام همیشه مبتنی بر حافظه هستند و در [۲۶] این الگوریتمها بر اساس مدل کلاس بندی شده اند.
۲-۵-۱- فیلترینگ اشتراکی مبتنی بر حافظه
در فیلترینگ اشتراکی مبتنی بر همسایگی یا مبتنی بر حافظه سرتاسر ماتریس کاربران - اقلام بررسی می شود (شکل شماره ۶). در این ماتریس که در حافظه ذخیره شده است امتیازهایی که کاربران به اقلام مختلف دادهاند وجود دارد. این ماتریس به صورت مستقیم برای پیش بینی نمره اقلامی که تا کنون هیچ امتیازی دریافت نکرده اند به کار میرود [۱۹]. یعنی این محاسبات به صورت برون خط[۴۲] انجام نمیپذیرد و همه چیز به صورت بر خط انجام می شود و همواره کل داده ها مورد نیاز میباشد. مزیت این روش این است که در هر زمان کل اطلاعات در دسترس میباشد اما با بزرگ شدن ماتریس یعنی تعداد کاربران و اقلام، فضای جستجو، حافظه مورد نیاز و زمان محاسبه افزایش مییابد.
همانطور که گفته شد در راهکار مبتنی بر حافظه پیش بینی به دو صورت پیش بینی بر اساس کاربران[۴۳] و پیش بینی براساس اقلام[۴۴] انجام می شود.
۲-۵-۱-۱- فیلترینگ اشتراکی مبتنی بر حافظه با پیش بینی براساس کاربران
در سیستمهای مبتنی برکاربر پیش بینی بر اساس ارزیابی امتیازهایی که توسط کاربران مشابه با کاربر فعال به اقلام مورد نظر تخصیص یافته انجام میپذیرد [۲۷]. کاربران شبیه آنهایی هستند که الگوی امتیازدهیشان شبیه به کاربر فعال باشد (شکل شماره ۶(.
یکی از چالشهای اصلی در این مدل نحوه پیدا کردن میزان شباهت بین کاربران میباشد. زیرا با بهره گرفتن از معیار شباهت شبیهترین همسایگان به کاربر فعال انتخاب و در پیش بینی استفاده میشوند.
۲-۵-۱-۲- فیلترینگ اشتراکی مبتنی بر حافظه با پیش بینی براساس اقلام
سیستمهای مبتنی بر اقلام امتیاز یک قلم خاص را بر اساس امتیازهایی که کاربر به اقلام مشابه داده است پیش بینی می کنند [۲۸] . دو قلم در صورتی به هم شبیه هستند که چند کاربر به طور مشابه به آنها رای داده باشند (شکل شماره ۷).
شکل شماره ۶: فیلترینگ اشتراکی مبتنی بر قلم شکل شماره ۷ : فیلترینگ اشتراکی مبتنی بر کاربر
۲-۵-۱- ۳- تفاوت فیلترینگ اشتراکی بر اساس کاربران و بر اساس اقلام
فیلترینگ اشتراکی بر اساس اقلام زمانی به کار میرود که روند افزایش اقلام کندتر از روند افزایش کاربران باشد [۲۸]. ولی در زمانی که روند افزایش اقلام سریعتر از روند افزایش کاربران باشد فیلترینگ اشتراکی بر اساس کاربران به کار می رود .[۲۹] به عنوان مثال اگر اقلامی مانند اخبار، مورد پژوهش باشد استفاده از روش قلم مبنا نامناسب خواهد بود و در صورتی که از این روش به عنوان مدل محور استفاده گردد به علت افزایش بسیار سریع اقلام مشکل سربار زیاد محاسباتی برای به روز رسانی مدل به وجود خواهد آمد. بر عکس اگر اقلامی مانند فیلم یا کتاب مورد پژوهش باشد استفاده از این روش مناسب خواهد بود.
۲-۵-۲- فیلترینگ اشتراکی مبتنی بر مدل
برخلاف سیستمهای مبتنی بر حافظه که امتیازهای ذخیره شده را به طور مستقیم درپیشبینی به کار میبرند، سیستمهای مبتنی بر مدل از این امتیازها برای یادگیری یک مدل پیش بینی استفاده می کنند. یعنی پارامترهای مدل به صورت برون خطی یاد گرفته میشوند و دیگر نیازی نیست که هر بار ماتریس امتیازدهی کاربران- اقلام بررسی شود. این مدل بر اساس داده های موجود آموزش[۴۵] داده می شود و در آینده برای پیش بینی امتیازهایی که کاربران به اقلام جدید خواهند داد به صورت روی خط به کار میرود [۴]. به همین دلیل نسبت به فیلترینگ اشتراکی مبتنی بر حافظه از سرعت بیشتری برخوردار است. این مدل می تواند یک الگوریتم یادگیری ماشین[۴۶] یا داده کاوی[۴۷] باشد [۳۰]. در گذشته الگوریتمهای موجود در حوزه یادگیری ماشین مانند شبکه های بیز[۴۸] [۸] و خوشه بندی[۴۹] [۳۱,۳۲] بسیار مورد توجه بوده اند .[۲۸] اگر چه امروزه الگوریتمهای فاکتورسازی ماتریس بسیار مورد توجه واقع شده اند اما همچنان الگوریتمهای خوشه بندی جایگاه خود را حفظ کرده اند.
۲-۶- نحوه تشخیص علائق کاربران
تشخیص میزان علائق کاربران نسبت به اقلام متفاوت یکی از مهمترین وظایف فیلترینگ اشتراکی میباشد. هر بار که کاربری در مورد قلمی خاص ابراز علاقه می کند مقدار جدیدی در نمایه او اضافه می شود. به دو صورت صریح و ضمنی میتوان علائق کاربر را استخراج نمود.
۲-۶-۱- تشخیص علائق به صورت صریح
برای این منظور سیستمهای پیشنهادگر تمایلی که کاربر به صورت واضح و آشکار نسبت به محصولات نشان میدهد مثل نمرههایی که به اقلام نسبت داده است را در یک پایگاه داده جمع آوری می کند. کاربر می تواند علائق خود را به طور صریح در غالب تک بیتی باینری یک و صفر به معنای خوب و بد و یا به صورت بازهای از اعداد که نشان دهنده میزان تمایل کاربر به قلم است نشان دهد. .به عنوان مثال اگر بازه امتیازدهی، اعداد ۱ تا ۵ باشد نسبت دادن امتیاز ۱ از سوی کاربر به معنای عدم علاقه و اختصاص دادن امتیاز ۵ به معنای علاقه کاربر به قلمی خاص میباشد [۷,۹].
۲-۶-۲- تشخیص علائق به صورت ضمنی
برای این منظور سیستم به صورت ضمنی بعضی رویدادها مثل حرکت اشارهگر به سمت محصولی خاص را در نظر میگیرد [۲۴]. در این روش کاربر تمایلاتش را به طور صریح و در قالب امتیاز نشان نمیدهد بلکه از رفتارش علائقاو محاسبه می شود .[۳۳,۳۴,۳۵,۳۶]
این پایان نامه فقط بر استنباط علائق به طور صریح متمرکز شده است. یعنی تمایلات کاربران باید به صورت نسبت دادن امتیاز به اقلام مشخص شده باشد.
۲-۷- محاسبه شباهت
برای پیش بینی یا ارائه پیشنهاد توسط فیلترینگ اشتراکی میبایست شبیهترین کاربران به کاربر فعال را پیدا کرد و به عنوان مجموعه همسایگی کاربر فعال در نظر گرفت. برای اندازه گیری میزان شباهت بین دو کاربر راهکارهای متفاوتی ارائه شده است که در اینجا دو مورد از معیارهای شباهت رایج که در فیلترینگ اشتراکی استغاده میشوند را معرفی میکنیم.
۲-۷-۱- معیار همبستگی پیرسون
این معیار میزان وابستگی بین الگوهای امتیازدهی دو کاربر (دو قلم) را میسنجد (فرمول شماره ۴). نتیجه حاصل از این فرمول عددی بین ۱ و ۱- میباشد. عدد ۱ نشان دهنده بیشترین شباهت، ۱- نمایانگر کمترین شباهت میباشد و اگر نتیجه عدد ۰ باشد یعنی دو موجودیت مورد مقایسه با هم هیچ ارتباطی ندارند.
(۴)
از فرمول فوق برای اندازه گیری میزان شباهت دو کاربر u و v استفاده می شود. نشان دهنده امتیازی که کاربر u به قلم j ام اختصاص داده میباشد. میانگین کل امتیازهایی که کاربر u به اقلام نسبت داده است میباشد.
فرمول زیر با کمی تغییر شباهت بین دو قلم i و j را اندازه گیری می کند.
(۵)
۲-۷-۲- معیار اندازه گیری کسینوس
معیار شباهت کسینوسی در حوزه بازیابی اطلاعات بسیار رایج است و برای اندازه گیری شباهت بین دو سند به کار میرود [۳۷]. این معیار میزان شباهت دو کاربر (دو قلم) را با بهره گرفتن از کسینوس زاویه بین بردارهای امتیازدهی آنها مشخص می کند (فرمول شماره ۶). نتیجه حاصل عددی بین ۱- و ۱ میباشد. هر چه عدد حاصل شده بزرگتر باشد یعنی دو موجودیت مورد مقایسه بیشتر به هم شبیه هستند و هر چه این عدد کوچکتر باشد یعنی دو موجودیت کمتر به هم شبیه هستند.
(۶)
اگرچه این معیار در حوزه بازیابی اطلاعات به خوبی کار می کند [۳۷,۳۸]اما برای محاسبه شباهت در فیلترینگ اشتراکی کاربر مبنا به خوبی معیار همبستگی پیرسون عمل نمیکند [۱۲].
در این پایان نامه با کمی تغییر از معیار همبستگی پیرسون برای اندازه گیری میزان شباهتها استفاده شده که در فصل ۴ به تفصیل توضیح داده شده است.
۲-۸- انتخاب همسایه
وقتی میزان شباهت تمام کاربران با کاربر فعال به دست آمد هم از نظر صحت و هم از نظر کارایی بهتر است زیر مجموعه ای از شبیهترین آنها را انتخاب و با بهره گرفتن از آنها امتیاز قلم دیده نشده را پیش بینی کرد [۱۸,۳۴]. برای این کار دو راه استفاده از حد آستانه و انتخاب تعداد ثابتی از همسایگان وجود دارد.
۲-۸-۱- استفاده از حد آستانه
در این روش یک حد آستانه تعیین می شود. کاربرانی که میزان شباهتشان بیشتر یا مساوی با این حد آستانه باشد به عنوان بهترین همسایهها انتخاب میشوند .[۹]تعیین این حد آستانه مقداری مشکل میباشد چون در یک مسئله با توجه به کاربران فعال مختلف این حد آستانه باید مدام تغییر کند.
۲-۸-۲- انتخاب تعداد ثابتی از همسایگان
در این روش کاربران با توجه به میزان شباهتشان به کاربر فعال مرتب شده سپسN تا از شبیهترین آنها به عنوان بهترین همسایهها انتخاب میشوند [۷] در [۱۶] بیان شده است که انتخاب تعداد ثابتی از همسایگان (معمولا بین ۲۰ تا ۶۰) نسبت به استفاده از حد آستانه منجر به نتیجه بهتری خواهد شد.
در این پایان نامه فقط از روش دوم یعنی انتخاب تعداد ثابتی از همسایگان استفاده شده است.
۲-۹- پیش بینی و تخمین رتبه
پس از انتخاب همسایهها نوبت به پیش بینی امتیاز قلم دیده نشده میرسد. روشهای متفاوتی برای تخمین رتبه وجود دارد که در اینجا به اختصار به بررسی دو مورد از آنها میپردازیم.
۲-۹-۱- استفاده از امتیازهای خام
(۷)
با بهره گرفتن از فرمول بالا میانگین وزن دارk تا از نزدیکترین همسایهها به کاربر فعال را به دست می آید. وزن هر همسایه معادل با میزان شباهت به دست آمده با بهره گرفتن از معیار همبستگی پیرسون میباشد. در نهایت نتیجه به دست آمده امتیاز پیش بینی شده میباشد.
۲-۹-۲- استفاده از امتیازهای نرمال شده
(۸)
توسط فرمول بالا این مسئله در نظر گرفته می شود که کاربران مختلف ممکن است بازههای امتیازدهی متفاوتی برای نشان دادن یک درجه اهمیت داشته باشند. در فیلترینگ اشتراکی مبتنی بر کاربر به طور استاندارد از این فرمول برای پیش بینی استفاده می شود .[۷]
۲-۱۰- مشکلات فیلترینگ اشتراکی
فیلترینگ اشتراکی علاوه بر کاربرد وسیع آن و مزایایی که از آن برخوردار است شامل معایبی نیز میباشد که در ادامه به توضیح تعدادی از آنها میپردازیم.
۲-۱۰-۱- پراکنده بودن داده[۵۰]
وقتی ماتریس کاربران - اقلام پراکنده و سایز آن بزرگ باشد این مشکل به وجود می آید. کاربرانی هستند که به همه اقلام امتیاز ندادهاند و تنها به تعداد کمی از آنها امتیاز دادهاند. بنابراین اقلامی وجود دارند که به اندازه کافی امتیازدهی نشدهاند. در این حالت اندازه گیری شباهت روی تعداد امتیازهای ابراز شده اندکی صورت میپذیرد که قابل اعتماد نمی باشد. یکی از مشکلاتی که به دلیل پراکنده بودن داده به وجود می آید شروع سرد است. یعنی برای کاربری که به تازگی وارد سیستم شده و به اندازه کافی امتیازی به اقلام نداده است نمی توان پیشنهاد قابل اعتمادی ارائه کرد. همچنین قلم جدیدی که وارد سیستم می شود نیز همین مشکل را دارد. اقلامی که به اندازه کافی امتیاز دریافت نکرده اند برای پیشنهاد قابل اعتماد نمیباشند. به عنوان مثال Movielens برای اجتناب از بروز چنین مشکلی برای کاربران جدید شرط امتیاز دهی به حداقل ۱۵ قلم را در نظر گرفته است.
پژوهشهای زیادی برای رفع این مشکل انجام شده است. که بسیاری از آنها از روشهای موجود در مدل محتوا محور برای پر کردن خانههای بدون رتبه ماتریس امتیازدهی استفاده می کنند .[۳۹,۴۰,۴۱,۴۲,۴۳]
۲-۱۰-۲- مقیاس پذیری[۵۱]
با زیاد شدن تعداد کاربران و اقلام منابع محاسباتی برای برطرف کردن درخواستهای جدید با کمبود مواجه می شود.
۲-۱۰-۳- اقلام مشابه[۵۲]
بعضی اقلام شبیه به هم هستند ولی به دلیل تفاوت در نامشان سیستم پیشنهادگر یکسان بودن آنها را نمیتواند تشخیص دهد. بنابراین با آنها به طور متفاوت برخورد می کند.
۲-۱۰-۴- گری شیپ[۵۳]
کاربرانی هستند که سلیقهشان موافق یا مخالف با هیچ گروه از کاربران نمی باشد. بنابراین سیستم پیشنهادگر فیلترینگ اشتراکی نمیتواند هیچ منفعتی به آنها برساند.
۲-۱۱- بررسی چگونگی کارکرد و تولید پیشنهاد سایت آمازون
سایت آمازون یکی از معروفترین سایتهای تجارت الکتونیک میباشد که در سال ۱۹۹۵ فعالیت خود را با فروش بر خط کتاب شروع کرد و اکنون در آن محصولاتی مانند ساعت، کتاب، سی دی، تلویزیون و… به فروش میرسد.
آمازون از متد فیلترینگ اشتراکی استفاده می کند و پیشنهادات را بر اساس اقلام تولید می کند. زیرا تعداد اقلام از تعداد کاربران به نسبت کمتر است. روند کار آمازون به این صورت است که لیست اقلام دیده شده توسط هر کاربر در یک ماتریس ذخیره می شود. سپس با بهره گرفتن از معیار شباهت کسینوس میزان شبیه بودن بردارهای اقلام در این ماتریس محاسبه میگردد. بعد از آن شبیهترین اقلام به اقلامی که کاربر تا کنون دیده است به او پیشنهاد می شود. نسخه سادهای از چگونگی تولید پیشنهاد در (شکل شماره ۸) قابل مشاهده میباشد.
شکل شماره ۸: روند تولید پیشنهاد در آمازون [۴۴]
همانطور که مشاهده میکنید کاربر ۳ اخیرا به سیستم وارد شده و قلمA را مشاهده کرده است. سیستم میزان شباهت بردار قلم َA را با سایر اقلام BوC و D با بهره گرفتن از معیار کسینوس به دست می آورد و شبیهترین اقلام که در اینجا B و C میباشند را به او پیشنهاد می کند.
در (شکل شماره ۹) صفحهای از سایت آمازون قابل مشاهده است. در این صفحه کاربر می تواند با کلیک روی لینک Your Recommendation وارد صفحهای شود که می تواند پیشنهاداتی که به او ارائه می شود را توسط موضوع و خط تولید مورد دلخواهش فیلتر کند. همچنین می تواند محصولاتی که قبلا خریداری نموده یا به او پیشنهاد شده است را امتیازدهی کند[۴۵] .
شکل شماره ۹ : نمونه صفحهای از سایت آمازون[۴۵]
(شکل شماره ۱۰) ارائه پیشنهاد بر اساس کارت خرید مشتری را نشان میدهد. یعنی بر اساس محصولاتی که تا کنون خریداری نموده است برای او پیشنهاد تولید می شود [۴۵].
شکل شماره ۱۰: ارائه پیشنهاد بر اساس کارت خرید مشتری [۴۵]
فصل سوم
روش محتوا محور
۳- روش محتوا محور
۳-۱-پیشگفتار
در این پایان نامه از روش محتوا محور جهت ارتقاء روش فیلترینگ اشتراکی استفاده شده است. روش محتوا محور بر اساس ویژگیهای اقلام تعریف می شود. این روش بررسی می کند که اقلام مورد علاقه کاربر دارای چه خصوصیاتی بوده اند، سپس اقلام دارای خصوصیات مشابه را به او پیشنهاد می کند. محتوای اقلام بر حسب نوع آنها می تواند متفاوت باشد. مثلا ژانر فیلم، نوع کتاب و مختصات جغرافیایی رستوران را به ترتیب به عنوان محتوای اقلام فیلم، کتاب یا رستوران در نظر گرفت. به عنوان مثال اگر اکثر فیلمهایی که کاربر دیده است متعلق به ژانر مستند باشند بدین معناست که او به این گونه فیلمها علاقهمند است.
سیستمهای محتوا محور نیاز به تکنیکی جهت نمایش خصوصیات اقلام، ایجاد نمایه از کاربر بر اساس علاقه مندیهایش و یک استراتژی جهت مقایسه نمایه کاربر با خصوصیات اقلام میباشد.
۳-۲- روند کار روش محتوا محور
روند کار سیستمهای محتوا محور به این صورت است که ابتدا براساس نحوه امتیازدهی کاربر به اقلام مختلف، نمایهای از علائق او ساخته می شود. سپس بر اساس میزان تطابق خصوصیات اقلام با نمایه ساخته شده از کاربر، پیشنهادها به کاربر ارائه می شود.
ساختار سیستمهای پیشنهادگر محتوا محور در شکل زیر نشان داده شده است.
شکل شماره ۱۱: روند کار روش محتوا محور [۲۴]
همانگونه که در شکل بالا قابل مشاهده است روند کار در متد محتوا محور متشکل از سه مرحله به شرح زیر می باشد [۲۴]:
۳-۲-۱- تحلیلگر محتوا (Content Analyzer)
در این مرحله محتوای اقلام نشان داده می شود. بدین منظور معمولا از تکنیکهای بازیابی اطلاعات استفاده می شود. اطلاعات توصیفی سازماندهی نشده مربوط به اقلام از قسمت منبع اطلاعات (Information Source) استخراج شده و در این مرحله سازماندهی می شود. یعنی هر قلم توسط اطلاعات سازماندهی شده نمایش داده می شود. مثلا اگر سیستم پیشنهادگر مربوط به فیلم باشد هر فیلم می تواند توسط ویژگیهای مربوط به بازیگران، کارگردانان و…. نمایش داده شود. یا اگر سیستم پیشنهادگر مربوط به صفحه وب باشد هر صفحه وب می تواند توسط برداری از کلمات کلیدی نمایش داده شود. به این صورت که ریشه کلمات به عنوان خصوصیات و مقدار tf/idf مربوط به هر ریشه به عنوان مقدار آن در نظر گرفته شود.
نتیجه حاصل شده از این مرحله در قسمت اقلام نمایش داده شده
(Represented Items) ذخیره می شود.
۳-۲-۲- یاد گیرنده نمایه (Profile Learner)
در این مرحله بر اساس عکس العملی که کاربر در برابر اقلام مختلف نشان داده و در قسمت بازخورد (Feedback) ذخیره شده است، نمایهای از علائق او ساخته می شود. این کار معمولا توسط تکنیکهای موجود در حوزه یادگیری ماشین انجام می شود.
عکس العملی که کاربر در مقابل اقلام از خود نشان میدهد به دو صورت صریح و ضمنی میباشد. عکس العمل صریح به این صوت است که کاربر علاقه یا عدم علاقه خود نسبت به اقلام را توسط امتیازدهی یا توصیفی کوتاه نشان دهد. در عکس العمل ضمنی کاربر هیچ دخالتی ندارد و خود سیستم توسط کنترل و تحلیل رفتار و فعالیتهای کاربر، علائق او را استخراج می کند.
با توجه به اینکه سلیقه افراد در طول زمان تغییر می کند، نمایه ساخته شده از کابر نیز باید با توجه به این تغییرات به روز شود. برای این منظور ابراز علاقه و یا عدم علاقه کاربر به اقلامی که در لیست به او پیشنهاد شده اند به عنوان باز خورد ذخیره و برای به روز کردن نمایه او استفاده می شود.
درست است که سایت پیشنهادگر آمازون بر اساس روش فیلترینگ اشتراکی است. ولی همانطور که در شکل شماره ۱۲ قابل مشاهده است در این نمونه صفحه از سایت آمازون گزینهای به نام Youre Favoites وجود دارد که با بهره گرفتن از این گزینه قسمتی از نمایه کاربر می تواند بر اساس روش محتوا محور ساخته شود. همانگونه که در شکل شماره ۱۳ قابل مشاهده است در این صفحه انواع کتابهایی که مطابق با علائق کاربر است نمایش داده شده است. انواعی که در این قسمت قابل مشاهده است یا به صورت ضمنی بر گرفته شده، مانند بررسی اقلامی که کاربر تا کنون خریداری کرده است، یا به صورت دستی توسط خود کاربر وارد شده است. این قسمت توسط کاربر قابل ویرایش و تطبیق پذیر با سلایق و علائق او میباشد.
شکل شماره ۱۲ : نمونه صفحهای از سایت آمازون
شکل شماره ۱۳ : استفاده از روش محتوا محور در سایت آمازون
۳-۲-۳- جزء فیلترینگ (filtering component )
در این مرحله میزان شباهت پروفایل ساخته شده از کاربر با اطلاعات توصیفی سازماندهی شده اقلام مورد نظر سنجیده می شود. این کار می تواند توسط یکی از معیارهای اندازه گیری شباهت مانند معیار اندازه گیری کسینوس صورت گیرد. بر این اساس مشخص می شود که کدام یک از این اقلام مورد علاقه کاربر است. نتیجه حاصل شده از این مرحله یک لیست پیشنهادی از اقلام میباشد که بر اساس علائق کاربر مرتب شده است.
۳-۳- مزایای روش محتوا محور
متد محتوا محور در مقایسه با متد فیلترینگ اشتراکی دارای مزایایی به شرح زیر است:
۳-۳-۱- استقلال کاربر
متد محتوا محور به امتیازهای کاربر فعال برای ساختن نمایه از او احتیاج دارد. در حالی که متد فیلترینگ اشتراکی به امتیازهای کاربران همسایه برای تشکیل مجموعه همسایگی کاربر فعال نیاز دارد.
۳-۳-۲-شفافیت
به عنوان دلیل برای پیشنهاد یک قلم به کاربر در سیستمهای محتوا محور میتوان ویژگیهای آن قلم را ارائه داد. در حالی که متد فیلترینگ اشتراکی جعبه سیاه است و تنها دلیل برای پیشنهاد قلم به کاربر فعال این است که کاربرانی ناشناس که سلیقهشان مشابه با کاربر فعال بوده آن قلم را دوست داشته اند.
۳-۳-۳- قلم جدید
روش محتوا محور مشکل شروع سرد که در متد فیلترینگ اشتراکی موجود میباشد را ندارد. و می تواند قلمی را که تا کنون توسط هیچ کاربری امتیازدهی نشده است، به کاربر فعال پیشنهاد دهد.
۳-۴- معایب روش محتوا محور
متد محتوا محور دارای معایبی نیز میباشد که در ادامه شرح داده شده اند:
۳-۴-۱- کمبود محتوا
اگر اطلاعات توصیفی مربوط به اقلام کافی نباشد نمی توان به درستی اقلام مورد علاقه کاربر را از اقلامی که به آنها علاقهای ندارد متمایز کرد. بنابراین نمی توان توسط این متد پیشنهادات صحیح و مناسبی ارائه نمود
۳-۴-۲- خصوصی سازی افزون
متد محتوا محور اقلامی که مطابق با نمایه ساخته شده از علاقه مندیهای کاربر است را به او پیشنهاد میدهد. اقلامی که پیشنهاد میشوند شبیه به اقلامی هستند که در گذشته کاربر به آنها امتیاز بالایی داده است. بنابراین در این سیستمها هیچ گاه تازگی وجود ندارد.
۳-۴-۳- کاربر جدید
در متد محتوا محور کاربر باید به تعداد قابل ملاحظهای از اقلام امتیاز داده باشد تا نمایهای صحیح از علاقه مندیهای او ساخته شود. بنابراین پشنهاد ارائه شده به کاربر جدیدی که به تعداد کافی اقلام رای نداده است، قابل اطمینان نمی باشد.
فصل چهارم
روش پیشنهادی
۴- روش پیشنهادی
۴-۱- پیشگفتار
مبنای کار این پایان نامه، روش فیلترینگ اشتراکی مبتنی بر کاربران میباشد. در این روش، روند کار به این صورت است که کاربران مشابه بر اساس نحوه امتیازدهیشان به اقلام شناسایی شده سپس امتیاز اقلامی که تا کنون دیده نشدهاند پیش بینی و در نهایت اقلامی که امتیاز بالا دارند به کاربر پیشنهاد می شود. در این روش، تمامی اقلام به طور یکسان در تعیین میزان شباهت بین کاربران تاثیر گذارند. ولی در واقعیت برای پیش بینی امتیاز قلم هدف، شباهت نحوه امتیازدهی کاربران به اقلام شبیه به قلم هدف، دارای اهمیت بیشتری نسبت به سایر اقلام میباشد. راهکارهای گوناگونی برای تعیین میزان تاثیر گذاری اقلام در فیلترینگ اشتراکی ارائه شده است که در ادامه به اختصار شرح داده شده اند.
۴-۲- مروری بر کارهای انجام شده در این راستا
در [۴۷] از معیار فرکانس معکوس سند[۵۴] که معیاری معروف در بازیابی اطلاعات میباشد، برای وزندهی به اقلام در سیستمهای فیلترینگ اشتراکی استفاده شده است. ایده اصلی این راهکار فرکانس معکوس کاربر نام دارد. یعنی اقلامی که در بین عموم کاربران دارای محبوبیت هستند نمی توانند به درستی بیانگر علائق یک کاربر باشند. بنابراین باید به این اقلام وزن کمتری نسبت به سایر اقلام اختصاص داد.
در [۴۸] نیز ایده مشابه با ایده قبل مطرح شده است. در این روش برای کاهش وزن اقلام محبوب از راهکار پراکندگی استفاده شده است. بدین صورت که به اقلامی که از لحاظ امتیاز، پراکندگی بیشتری دارند وزن بیشتر اختصاص مییابد.
در [۴۹] راهکاری مبتنی بر تئوری اطلاعات ارائه شده است. در این راهکار با بهره گرفتن از معیار اطلاعات متقابل[۵۵] و آنتروپی[۵۶]، میزان وابستگی بین قلم هدف و اقلام دیگر تعیین و بر این اساس به اقلام وزن تخصیص داده می شود.
در [۵۰] یک روش وزندهی اتوماتیک ارائه شده است که از ایده مربوط به سیستمهای مبتنی بر مدل استفاده می کند. این روش توسط ماکزیمم کردن میانگین شباهت بین کاربران، به اقلام وزن میدهد. به گونه ای که کاربر را به کسانی که با او سلیقه مشابه دارند شبیهتر و از کسانی که با او اختلاف سلیقه دارند متمایزتر می کند.
به دلیل متناقض بودن نتایج گزارش شده از انواع روشهای ارائه شده، در [۵۱] مقایسه ای بین انواع روشهای وزندهی به اقلام انجام شده است. همچنین سه روش برای فیلتر کردن اقلام بر اساس وزنهای تخصیص یافته به آنها معرفی شده است.
در [۵۲]مشکل یکسان بودن وزن اقلام و پراکندگی سیستمهای فیلترینگ اشتراکی توسط شباهت محلی و سراسری کاربران حل شده است. بدین صورت که شباهت محلی بین کاربران با کاستن تاثیر اقلام محبوب در بین عموم محاسبه می شود. این کار با در نظر گرفتن امتیازهای هر قلم به عنوان یک متغیر تصادفی از توزیع لاپلاس انجام می شود.
در [۵۳] راهکاری نوین برای وزندهی به اقلام و غلبه بر مشکل پراکندگی ارائه شده است. این راهکار بر اساس تجزیه و تحلیل معنایی نهفته[۵۷] و استفاده از روش تجزیه منحصر به فرد[۵۸] میباشد.
در [۵۴] مشکل شروع سرد در خلال وزندهی به اقلام مورد بررسی قرار گرفته است. وزندهی به اقلام بر اساس کاهش تاثیر اقلام محبوب توسط دو روش فرکانس معکوس کاربر و وزندهی خطی انجام شده است.
۴-۳- مقدمهای بر روش پیشنهادی
اکثر روشهایی که تا کنون برای تخصیص وزن به اقلام ارائه شده اند از اطلاعات آماری اقلام یعنی امتیازهای تخصیص داده شده به آنها استفاده کرده اند. در حالی که میتوان از محتوای مربوط به اقلام برای تعیین شباهت و وزندهی به آنها استفاده نمود. به دلیل اینکه پایگاه داده های مورد استفاده در این پایان نامه MovieLens و EachMovie است و هر دو مربوط به فیلم میباشند، منظور از اقلام همان فیلمهای موجود در این پایگاه داده میباشد. در این پایان نامه به منظور استفاده از روش محتوا محور، ویژگی ژانرها، کارگردانان و بازیگران هر فیلم مورد بررسی قرار گرفته است. ژانر هر فیلم مشخص کننده دسته فیلم است. بعنوان مثال اگر ژانر فیلمی کمدی- درام باشد یعنی آن فیلم به دو دسته کمدی و درام تعلق دارد. در پایگاه داده های مذکور، اطلاعات مربوط به ژانر هر فیلم موجود میباشد. بعنوان مثال در پایگاه داده MovieLens، ۱۹ ژانر وجود دارد که هر فیلم حداقل ۱ و حداکثر ۳ ژانر دارد. علاوه بر ویژگی ژانر هر فیلم از داده های دیگر نظیر ویژگیهای کارگردانان و بازیگران هر فیلم نیز استفاده شده است. این ویژگیها در پایگاه داده وجود ندارند و باید از پایگاه داده های Linked Open Data(LOD)، نظیر DBpedia استخراج گردند. شایان ذکر است استفاده از داده های تکمیلی به منظور وزندهی دقیقتر اقلام توسط روش محتوا محور و به دنبال آن بالا بردن دقت پیش بینی در سیستمهای فیلترینگ اشتراکی میباشد.
۴-۴- روش پیشنهادی
روش ارائه شده از ۳ مرحله مجزا تشکیل شده است:
۱- پیش پردازش
۲- تخصیص وزن به اقلام بر اساس روش محتوا محور
۳- استفاده از وزنهای تخصیص داده شده به اقلام در دو فاز انتخاب همسایگی و پیش بینی، در روش فیلترینگ اشتراکی
در ادامه شرح مراحل بالا به تفصیل توضیح داده شده است.
۴-۴-۱- پیش پردازش
همانگونه که در قبل بیان شد برای استفاده از ویژگیهای بازیگران و کارگردانان مربوط به هر فیلم در روش محتوا محور ، نیازمند به استخراج آنها میباشیم. از آنجا که پایگاه داده های مورد استفاده در این پایان نامه MovieLensو EachMovie میباشد، در ادامه نحوه استخراج اطلاعات مورد نیاز مربوط به فیلمهای موجود در هر یک از این دو پایگاه داده توضیح داده شده است.
۴-۴-۱-۱- پیش پردازش بر روی پایگاه داده MovieLens
DBPedia اطلاعات موجود در WikiPedia را به صورت سازماندهی شده استخراج کرده و در دسترس قرار داده است. به منظور استفاده از اطلاعات سازماندهی شده مربوط به فیلمها، یک درخواست براساس عنوان فیلم در زبان SPARQL طراحی و با بهره گرفتن از متد PostURL به سرور DBPedia[59] ارسال می شود. نمونهای از درخواست طراحی شده در ادامه قابل مشاهده میباشد:
SELECT ?film_title ?star_name ?nameDirector {
{
SELECT DISTINCT ?movies ?film_title
WHERE {
?movies rdf:type
<http://dbpedia.org/ontology/Film>;
rdfs:label ?film_title.
}
}.
?movies dbpedia-owl:starring ?star;
dbpedia-owl:director ?director.
?director foaf:name ?nameDirector.
?star foaf:name ?star_name.
FILTER ( (str(?film_title) IN ("Film Name"))
&&(LANGMATCHES(LANG(?film_title),"en")))
}
ORDER BY ?film_title
این سرور در جواب، اطلاعات مربوط به فیلم مورد نظر را در قالب XML ارسال می کند. این کار برای تمام فیلمهای موجود در پایگاه داده MovieLens انجام می شود. لازم به ذکر است که اطلاعات استخراج شده برای هر فیلم شامل نام همه کارگردانان و فقط نام بازیگران مهم آن میباشد. اطلاعات مربوط به فیلمهایی که در DBPedia موجود نمی باشد به صورت دستی از سایت WikiPedia[60] و در صورت عدم وجود از سایتIMDB[61] استخراج می شود. در مواردی که اطلاعات از سایت IMDB استخراج می شود، به طور ثابت نام مربوط به۷ بازیگر برتر انتخاب میگردد.
۴-۴-۱-۲- پیش پردازش بر روی پایگاه داده EachMovie
برای هر فیلم موجود در پایگاه داده EachMovieتوسط زبان برنامه نویسی C#.net بر اساس لینک مربوط به آن یک درخواست به سرور IMDB فرستاده می شود. توسط این درخواست قالب HTML صفحه مربوط به آن فیلم در این سایت، در دسترس قرار میگیرد که میتوان اطلاعات مربوط به بازیگران و کارگردانان را که با TAG های مربوطه شناسایی میشوند، از آن استخراج نمود.
URLمربوط به تعدادی از فیلمها در این پایگاه داده معتبر نمی باشد. برای این دسته از فیلمها درخواست بر اساس نام و تاریخ انتشار آنها به فیلد جستجوی سایت IMDB ارسال می شود و در صورت عدم موفقیت در یافتن هر فیلم، اطلاعات مربوط به آن به صورت دستی از این سایت یا سایتWikiPedia استخراج میگردد.
۴-۴-۲- وزندهی به اقلام
پس از جمع آوری اطلاعات مربوط به ژانرها، کارگردانان و بازیگران تمام فیلمهای موجود در پایگاه داده در مرحله قبل، اکنون نوبت به وزندهی آنها بر اساس روش محتوا محور میرسد. توجه شود اطلاعات مربوط به هر فیلم، نمایه آن فیلم را تشکیل میدهد. بنابراین وزن هر فیلم بر اساس میزان شباهت نمایه آن با نمایه فیلم هدف تعیین میگردد. این میزان شباهت توسط معیار کسینوس سنجیده می شود. این معیار در حالت کلی، دو بردار را به عنوان ورودی دریافت و میزان شباهت آنها را بر اساس زاویه بین آن دو اندازه گیری می کند. برای اندازه گیری میزان شباهت بین نمایه دو فیلم بر اساس این معیار، اطلاعات موجود در نمایه هر دو قلم باید در قالب بردارهایی با طول یکسان نشان داده شود. به این منظور برای هر ویژگی ژانر، کارگردان و بازیگر متعلق به نمایه هر کدام از دو فیلم مورد مقایسه، مولفهای در بردار در نظر گرفته می شود. سپس از مقادیر ۰ و ۱ برای مشخص کردن وجود و عدم وجود آن ویژگی در هر یک از فیلمها استفاده میگردد. فرض کنید Gi نشانگر ژانر i ام، Di نمایانگر کارگردانi ام و Ai مشخص کننده بازیگر i ام فیلم باشد. فیلم M و T را با مجموعه ویژگیهای زیر در نظر بگیرید:
اجتماع مجموعه ویژگیهای این دو فیلم برابر است با:
بنابراین بردار ساخته شده برای هر فیلم به صورت زیر میباشد:
طبق آنچه که در مرحله پیش پردازش توضیح داده شد، تعداد بازیگران استخراج شده برای هر فیلم متفاوت میباشد. بنابراین در هنگام مقایسه هر فیلم با فیلم هدف، فقط بازیگران مشترک بین آنها در نظر گرفته می شود. بدین منظور در مثال بالا بازیگر A1 از بردار فیلمهای M و T حذف خواهد شد:
اکنون که توانستیم نمایه هر فیلم را در قالب بردار نشان دهیم، از معیار کسینوس برای تعیین میزان شباهت دو بردارM و T به صورت زیر استفاده میکنیم:
(۹)
نشان دهنده مولفه ام از بردار M و نشان دهنده مولفه i ام از بردار میباشد. توجه شود که حاصل این کسر عددی بین ۰ و ۱ است. عدد ۱ به معنای تشابه کامل و عدد ۰ به معنای عدم تشابه کامل است.
از آنجا که مولفههای دو بردار مورد مقایسه ۰ و ۱ میباشد، مقدار محاسبه شده در صورت کسر بالا، برابر با تعداد یکهای مشترک و به بیان دیگر برابر با تعداد ویژگیهای مشترک بین دو فیلم است. بنابراین برای اقلامی که هیچ ویژگی مشترکی با قلم هدف ندارند وزن صفر در نظر گرفته می شود. از سوی دیگر مبنای فیلترینگ اشتراکی محاسبه میزان شباهت بین کاربران میباشد که بعضی از این کاربران به تعداد محدودی از اقلام امتیاز دادهاند. بنابراین اقلامی وجود دارند که به اندازه کافی امتیازدهی نشدهاند. و این باعث مشکل پراکندن بودن ماتریس کابران- اقلام شده است. در این حالت اندازه گیری شباهت روی تعداد امتیازهای ابراز شده اندکی صورت میپذیرد که قابل اعتماد نمی باشد. حال با صفر در نظر گرفتن وزن اقلامی که ویژگی مشترک با قلم هدف ندارند، این مشکل تشدید می شود. برای جلوگیری از این مسئله، برای این اقلام وزنی کوچکتر از سایر اقلام در نظر گرفته شده است. بنابراین اعمال وزن به اقلام به صورت زیر انجام می شود:
(۱۰)
مشخص کننده تعداد ویژگیهای مشترک بین دو قلم (تعداد یکهای مشترک بین دو بردار) است. نمایانگر فیلمی است که دارای بیشترین تعداد ویژگی (برداری با بیشترین تعداد یک) میباشد
۴-۴-۳- انتخاب همسایگی
بر طبق آنچه توضیح داده شد، نتیجه حاصل شده از مرحله قبل، وزن مربوط به هر قلم بر اساس میزان شباهت آن با قلم هدف میباشد. برای پیش بینی یا ارائه پیشنهاد توسط روش فیلترینگ اشتراکی ابتدا میبایست شبیهترین کاربران به کاربر فعال را پیدا کرد و به عنوان مجموعه همسایگی او در نظر گرفت. کاربر فعال کاربری است که هدف پیش بینی امتیاز قلم هدف برای او میباشد. برای ایجاد مجموعه همسایگی، فقط کاربرانی که به قلم هدف رای دادهاند مورد بررسی قرار میگیرند. معیار همبستگی پیرسون پایه برای سنجیدن میزان وابستگی بین الگوی امتیازدهی کاربر فعال و سایر کاربران استفاده میگردد و به صورت زیر محاسبه می شود:
(۱۱)
و میانگین کل امتیازهایی هستند که به ترتیب کاربران و به اقلام نسبت دادهاند. و امتیازهایی هستند که به ترتیب کاربران و به قلم ام نسبت دادهاند.
در این مرحله، برای سنجیدن میزان وابستگی بین الگوی امتیازدهی کاربر فعال و سایر کاربران از معیار همبستگی پیرسون وزندار استفاده می شود. تنها تفاوت این معیار با معیار همبستگی پیرسون پایه این است که در زمان مقایسه نحوه امتیازدهی دو کاربر به هر قلم، وزن آن قلم نیز دخیل می شود. این وزن میزان اهمیت مشابه عمل کردن دو کاربر را در امتیازدهی به این قلم مشخص می کند. معیار همبستگی پیرسون وزندهی شده به صورت زیر میباشد:
(۱۲)
نشان دهنده قلم هدف است که پیش بینی امتیاز آن مورد نظر میباشد. نشان دهنده وزن قلم ام و به عبارت دیگر میزان شباهت قلم ام با قلم هدف است.
علاوه بر این، با ادغام یک وزن دهی مفید و کاهش دادن همبستگی بر اساس تعداد اقلامی که دو کاربر مشترکا به آنها امتیاز دادهاند، میتوان دقت پیش بینی را به شکل قابل توجهی افزایش داد.
با فرض اینکه تعداد اقلامی است که کاربران و به طور مشترک به آنها رای دادهاند، در نهایت شباهت دو کاربر مذکور به صورت زیر به دست می آید:
(۱۳)
پس از اینکه شباهت تمامی کاربران با کاربر فعال سنجیده شد نوبت به انتخاب مجموعه همسایگی میرسد. برای این منظور کاربران بر اساس میزان شباهتشان به طور نزولی مرتب میشوند. سپس با انتخاب تعداد ثابتی از بهترین آنها، مجموعه همسایگی کاربر فعال تشکیل داده می شود.
همچنین میتوان برای انتخاب مجموعه همسایگی کاربر فعال از فرمول زیر استفاده نمود. به صورتی که مقدار موجود در فرمول شماره ۱۲ از فرمول شماره ۹ به دست آمده و نهایتا حاصل از این فرمول جایگزین در فرمول شماره ۱۳ می شود.
(۱۴)
که بهترین نتیجه با تنظیم و حاصل می شود.
۴-۴-۴- پیش بینی
نتیجه به دست آمده از مرحله قبل مجموعه همسایگی کاربر فعال میباشد. در این مرحله با بهره گرفتن از امتیازهایی که توسط کاربران موجود در مجموعه همسایگی به قلم هدف تخصیص یافته، امتیاز مربوط به قلم هدف پیش بینی می شود. برای این منظور از فرمول شماره ۱۵ که به طور معمول در فیلترینگ اشتراکی مبتنی بر کاربر به کار برده می شود[۹] ، استفاده میگردد.
(۱۵)
Nt(a)مجموعه همسایگی کاربر فعال میباشد. و میانگین کل امتیازهایی هستند که به ترتیب کاربران و به اقلام نسبت دادهاند. نمرهای است که کاربر به قلم هدف اختصاص داده است.
فصل پنجم
آزمایشها و نتایج
۵- آزمایشها و نتایج
۵-۱- پایگاه داده های مورد استفاده
MovieLensو EachMovie دو پایگاه داده[۶۲] معروف و رایج هستند که هر دو مربوط به سایتهای پیشنهادگر فیلم میباشند .روش پیشنهادی روی هر دوی این پایگاه داده ها مورد آزمایش و بررسی قرار گرفته است.
۵-۲- نحوه اجرای روش پیشنهادی روی پایگاه داده MovieLens
MovieLens متشکل از ۲۰۹,۰۰۰,۱ امتیاز میباشد که توسط ۰۴۰,۶ کاربر به ۹۵۲,۳ فیلم اختصاص یافته است. این پایگاه داده توسط پروژه پژوهشی GroupLens در دانشگاه Minnesota تهیه شده است.
برای آزمایش روش ارائه شده از روش اعتبار سنجی پنج قسمت برابر[۶۳] استفاده کردهایم. به این صورت که امتیازهای داده شده به هر فیلم را به ۵ قسمت تقریبا مساوی تقسیم کرده سپس یک قسمت یعنی حدود %۲۰ را برای تست[۶۴] و مابقی را برای آموزش[۶۵] جدا کردهایم. یعنی با بهره گرفتن از %۸۰ امتیازها، %۲۰ باقی مانده امتیازها را با این روش پیش بینی میکنیم. در کل مجموعه تست تقریبا شامل ۷۱۰,۱۹۲ امتیاز و مجموعه آموزش تقریبا شامل ۴۹۹,۸۰۷ امتیاز میباشد.
۵-۳- نحوه اجرای روش پیشنهادی روی پایگاه داده EachMovies
EeachMovie متشکل از ۹۸۳,۸۱۱,۲ امتیاز میباشد این پایگاه داده شامل ۹۱۶,۷۲ کاربر میباشد که به ۶۲۸,۱ فیلم امتیاز دادهاند. برای آزمایش روش ارائه شده بر روی این پایگاه داده نیز از روش اعتبار سنجی پنج قسمت برابر استفاده کردهایم. در کل مجموعه تست تقریبا شامل ۳۹۶,۵۶۲ امتیاز و مجموعه آموزش تقریبا شامل ۵۸۷,۲۴۹,۲ امتیاز میباشد.
۵-۴- معیارهای ارزیابی
معیارهای ارزیابی سیستمهای پیشنهادگر بر اساس وظیفه ای که به عهده دارند انتخاب میشوند. در اینجا چون هدف ارزیابی توانایی سیستم پیشنهادگر در پیش بینی امتیاز اقلام دیده نشده میباشد، معیارهای زیر برای سنجش روش پیشنهادی به کار برده شده اند.
۵-۴-۱- میانگین خطای مطلق[۶۶] :
این معیار بر اساس دقت است و فاصله بین امتیازهای پیش بینی شده و امتیازهای واقعی را اندازه گیری می کند که با فرمول زیر محاسبه می شود. توجه کنید امتیاز واقعی و امتیاز پیش بینی شده میباشد.
(۱۶)
۵-۴-۲- دقت[۶۷] و فراخوانی[۶۸]
در سیستمهای پیشنهادگر آنچه که برای کاربر فعال مهم است این میباشد که یک لیست اقلام مرتب شده بر اساس تمایلاتش دریافت کند. این دو معیار، معیارهای ارزیابی بازیابی اطلاعات[۶۹] میباشند که برای ارزیابی سیستمهای پیشنهادگر نیز به کار میروند.
در حیطه بازیابی اطلاعات توسط موتورهای جستجوگر، دقت، نسبت تعداد اسناد[۷۰] بازیابی شده مرتبط به تعدا کل اسناد بازیابی شده است. فراخوانی، نسبت تعداد اسناد بازیابی شده مرتبط نسبت به تعداد کل اسناد مرتبط میباشد. این مفاهیم در شکل شماره ۱۴ نشان داده شده اند.
شکل شماره ۱۴: نمایش مفاهیم دقت و فراخوانی در حوزه بازیابی اطلاعات
دقت در سیستمهای پیشنهادگر یعنی نسبت پیشنهاداتی که خوب هستند و به کاربر ارائه شده اند به کل پیشنهاداتی که در لیست وجود دارند. فراخوانی یعنی نسبت پیشنهاداتی که خوب هستند و به کاربر ارائه شده اند به تعداد کل پیشنهادات خوب که در لیست ظاهر شده- اند. اینجا شرط خوب یا مربوط بودن پیشنهادات که همان اقلام هستند داشتن امتیاز ۴ و ۵ میباشد و شرط خوب نبودن یا نا مربوط بودن اقلام، داشتن امتیازهای ۱ ، ۲ و ۳ میباشد.
با توجه به مطالبی که گفته شد مقدار دقت ۱ یعنی تمام پیشنهاداتی که ارائه شده اند خوب هستند (نه اینکه تمام پیشنهادات خوب به کاربر ارائه شده اند) و مقدار فراخوانی ۱ یعنی تمام پیشنهادات خوب در لیست به کاربر ارائه شده اند (بدون توجه به اینکه چه تعداد پیشنهادات بد نیز در لیست وجود دارد).
دقت و فراخوانی با هم رابطه معکوس دارند یعنی هر چقدر دقت بالا رود فراخوانی پایین می آید و هر چقدر دقت پایین آید فراخوانی بالا میرود مانند آنچه که در شکل شماره ۱۵ میبینید.
شکل شماره ۱۵: رابطه معیار فراخوانی با معیار دقت
۵-۴-۳- معیار ارزیابی F
این معیار برای ترکیب معیارهای دقت و فراخوانی و تبدیل آنها به یک معیار به کار میرود و مقدار آن توسط فرمولی که در ادامه قابل مشاهده است محاسبه می شود.
(۲۸)
۵-۵- ارزیابی روشهای پیشنهادی توسط معیارهای معرفی شده
معیارهایی که در بالا معرفی شد برای سنجش روش ارائه شده روی هر دو پایگاه داده به کار برده شده اند. توجه شود که WPC روش پیشنهادی است که باPC که همان روش پایه ذکر شده در [۴۶]میباشد مورد مقایسه قرار گرفته است. توجه شود که روش پایه از فرمول شماره ۲۶ برای انتخاب همسایگان و از فرمول شماره ۹ برای پیش بینی استفاده می کند.
در ادامه اعداد به دست آمده از هر معیار ابتدا در جداول مربوطه مشخص گردیده، سپس نتایج در قالب نمودار نشان داده شده اند.
جدول شماره ۲ : مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده برMovieLens
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۷۰۴۶ | ۰٫۷۰۵۵ | ۰٫۷۰۷۶ | ۰٫۷۱۷۹ | ۰٫۷۴۶۳ | PC |
| ۰٫۶۷۹۳ | ۰٫۶۸۰۴ | ۰٫۶۸۳۴ | ۰٫۶۹۶۷ | ۰٫۷۲۵۶ | WPC |
جدول شماره ۳ : مقایسه میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر EachMovie
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۹۴۵۸ | ۰٫۹۵۶۶ | ۰٫۹۶۸۷ | ۱٫۰۰۷ | ۱٫۰۵۳۵ | PC |
| ۰٫۸۷۸۶ | ۰٫۸۸۲۲ | ۰٫۸۸۶۲ | ۰٫۹۰۳۹ | ۰٫۹۴۰۴ | WPC |
جدول شماره ۴ : مقایسه معیار دقت روش پایه و روش پیشنهادی، اعمال شده بر MovieLns
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۸۳۶۱ | ۰٫۸۳۴۱ | ۰٫۸۳۱۷ | ۰٫۸۲۶۲ | ۰٫۸۱۲۶ | PC |
| ۰٫۸۴۷۶ | ۰٫۸۴۵۱ | ۰٫۸۴۲۷ | ۰٫۸۳۴۳ | ۰٫۸۲۰۴ | WPC |
جدول شماره ۵ : مقایسه معیار دقت روش پایه و روش پیشنهادی، اعمال شده بر EachMovie
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۸۷۳۲ | ۰٫۸۷۰۶ | ۰٫۸۶۸۲ | ۰٫۸۶۰۹ | ۰٫۸۵۰۷ | PC |
| ۰٫۸۸۷۴ | ۰٫۸۸۷۲ | ۰٫۸۸۶۲ | ۰٫۸۸۳۴ | ۰٫۸۷۹۳ | WPC |
جدول شماره ۶ : مقایسه معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر MovieLens
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۵۳۷۰ | ۰٫۵۴۲۲ | ۰٫۵۴۵۸ | ۰٫۵۴۹۷ | ۰٫۵۵۲۶ | PC |
| ۰٫۵۴۲ | ۰٫۵۴۷۲ | ۰٫۵۵۰۸ | ۰٫۵۵۴۷ | ۰٫۵۵۳۳ | WPC |
جدول شماره ۷ : مقایسه معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر EachMovie
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۷۴۴۶ | ۰٫۷۴۱۱ | ۰٫۷۳۷۵ | ۰٫۷۲۶۱ | ۰٫۷۰۹۵ | PC |
| ۰٫۷۷۴۰ | ۰٫۷۷۳۵ | ۰٫۷۷۲۱ | ۰٫۷۶۷۰ | ۰٫۷۵۸۱ | WPC |
جدول شماره ۸ : مقایسه معیار F روش پایه و روش پیشنهادی، اعمال شده بر MovieLens
| ۵۰ | ۳۰ | ۲۰ | ۱۰ | ۵ | # Neighbours |
| ۰٫۶۵۴۰ | ۰٫۶۵۷۲ | ۰٫۶۵۹۱ | ۰٫۶۶۰۱ | ۰٫۶۵۷۸ | PC |
| ۰٫۶۶۱۱ | ۰٫۶۶۴۲ | ۰٫۶۶۶۲ | ۰٫۶۶۶۴ | ۰٫۶۶۰۸ | WPC |
جدول شماره ۹ : مقایسه معیار F روش پایه و روش پیشنهادی، اعمال شده بر EachMovie
