سامانه توصیه‌گر

سامانه توصیه‌گر به کمک هوش‌مصنوعی و داده‌های بزرگ به تشکیل پرسونای تک تک کاربران می‌پردازد. سلیقه کاربران را بدون سوال‌ و جواب کشف کرده و آنها را به سمت آنچه می‌جویند راهنمایی می‌کند.
# مقدمه
با توجه به گسترش فضای اینترنت، مطالب، محصولات فروشگاه ها که درنتیجه باعث افزایش قابل توجه حق‌انتخاب کاربر می‌شود، نیاز به طبقه‌بندی و کوچک‌کردن فضای جستجو برای رسیدن به نتیجه بسیار حس می‌شود. چه‌بسا بسیاری از کاربران به دلیل این گستردگی قادر به یافتن نتیجه‌ی خود نبوده و از ادامه‌ی جستجو صرف‌نظر می‌کنند. سامانه‌ی توصیه‌گر با کوچک‌کردن فضای جستجوی‌کاربران این‌مشکل را حل می‌کند. این سامانه با روش‌های متفاوت محتوای شخصی‌سازی شده‌ی هر کاربر را باتوجه به مشخصات، پیشینه جستجو و علایق به او پیشنهاد می‌دهد[1].در این‌مقاله به بررسی روش‌های موجود، نقاط ضعف و قوت و پیاده‌سازی آن(ها) می‌پردازیم.  
# کارهای مرتبط
![تصویر ۱[2]](https://boute.s3.amazonaws.com/304-basic_types.png)
سامانه‌های توصیه‌گر برای کمک به تصمیم‌گیری و ارائه‌ی رهنمود برای انتخاب محتوای مناسب هرشخص تعریف شده‌اند و در راستای این‌هدف از روش‌های متفاوتی استفاده می‌کنند. در ابتدا به توضیح اجمالی هریک از این روش‌ها اکتفا می‌کنیم(تصویر ۱) و در آینده به صورت تخصصی‌تر و جزئی‌تر به آن‌ها میپردازیم. سعی داریم در این مقاله از روش مارپیچ برای توضیح روش‌های پیاده‌سازی سامانه‌ی توصیه‌گر استفاده کنیم.[3]
یکی از روش‌های پیاده‌سازی توصیه‌گر تکنیک   Collaborative filtering [4] نام دارد. به طور خلاصه این روش با شناسایی کاربران دیگر با ذائقه یکسان شما، محتوای مناسب را پیشنهاد می‌دهد[5] (تصویر ۲).  
![تصویر ۲ [6] ](https://upload.wikimedia.org/wikipedia/commons/5/52/Collaborative_filtering.gif)
پیاده‌سازی این تکنیک به شیوه‌های متفاوتی انجام می‌شود که در آینده به طور کامل به آن اشاره می‌کنیم. از نمونه‌های استفاده‌کننده از این تکنیک می‌توان به RINGO[7] اشاره کرد که البته سامانه‌‌ای قدیمی در این‌حوزه است. پس از آن می‌توان به Amazon [8] اشاره کرد. آمازون از روش item-to-item که یکی از زیرمجموعه‌های تکنیک Collaborative filtering است استفاده می‌کند [9] . علاوه بر آن می‌توان به سامانه‌ی توصیه‌گر last.fm[10] اشاره کرد.این سایت موزیک هارا با توجه سلیقه‌ی کاربر دسته‌بندی و به او پیشنهاد می‌دهد. لازم به ذکر است این سایت،  توصیه‌گر خود را Audioscrobbler نام‌گذاری کرده است [11]. 
![تصویر ۳ [12] ](https://www.ntt-review.jp/archive_html/200804/images/le1_fig02.gif)
روش دیگر پیاده‌سازی توصیه‌گر تکنیک Content-base filtering نام دارد [13] . در این‌روش ذائقه‌ی کاربر باتوجه به مشخصات‌ خود شخص و تشابه محتوای انتخاب‌شده‌ی قبلی با نمونه‌های مشابه انتخاب‌نشده تشخیص داده‌می‌شود و محتوای مشابه پیشنهاد می‌گردد(تصویر ۳). در این‌روش تعامل و تشابه ذائقه بین کاربران مختلف نادیده گرفته می‌شود و تشابهات براساس تشابهات بین محتوا و محصولات بررسی می‌شود که تفاوت اصلی این تکنیک با تکنیک Collaborative filtering است [14]. از نمونه‌های استفاده‌کننده از این تکنیک می‌توان به سامانه‌توصیه‌گر Pandora [15] اشاره کرد. این‌سامانه با بررسی مشخصات موزیک و هنرمند، موزیک‌های مشابه را پیدا و به کاربر پیشنهاد می‌دهد [16].
برای مقایسه‌ی این‌دو روش اصلی می‌توان به مقایسه last.fm و Pandora پرداخت. last.fm و دیگر‌سامانه‌های استفاده‌کننده از Collaborative filtering از مشکل شروع سرد(cold start [17]) رنج می‌برند. برای شناخت موزیک‌های مشابه ، یک موزیک برای قابل پیشنهاد شدن باید به سطح حداقلی از محبوبیت برسد تا از آستانه‌ی( [18] threshold) صافی موزیک‌ها عبور کند. البته Pandora نیز از معایبی مشابه رنج می‌برد. برای اضافه شدن یک موزیک جدید لازم است تا کارمندان Pandora آن‌را از تنگنای کلاسه‌بندی([19] classification) توصیه‌گرشان عبور دهند تا مشخصات موزیک‌ و هنرمند به‌درستی بررسی و ثبت‌گردد. مقاله nature vs nurture به صورت جزئی به اختلافات و نقاط ضعف و قوت هریک از این سامانه‌ها می‌پردازد [20].
![تصویر ۴](http://dataconomy.com/wp-content/uploads/2015/03/Introduction-What-is-a-Recommendation-Engine-Hybrid-Recommender-Systems.jpg)
باتوجه به ضعف‌ها و نقاط‌ قوت ذکر‌شده در هر‌روش، روشی تلفیقی به نام تکنیک Hybrid filtering به‌وجود‌ آمد. باتوجه به قدرت Collaborative filtering و سرعت ابتدایی Content-base filtering با ترکیب نقاط قوت این‌دو‌تکنیک، تکنیکی قوی‌تر و کارآمدتر به‌وجود می‌آید . این ترکیب میتواند شامل عبور‌دادن خروجی نتیجه CF به Content-base filtering باشد یا برعکس یا از تلفیق نتیجه مستقل هریک به‌وجود‌آید(تصویر ۴).[21,22] از مثال‌های استفاده‌کننده از این تکنیک‌ می‌توان به Netflix [23] اشاره کرد. Netflix با ترکیب قدرت بالای CF و کاهش هزینه‌ی محاسباتی باتوجه به نیازمندی‌های کم Content-base filtering سامانه‌ی توصیه‌گر خود را پیاده‌سازی کرده‌است[25, 24]
در آینده به بررسی جزئی تر هر‌یک از این تکنیک ها در فاز پیاده‌سازی می‌پردازیم.
# آزمایش‌ها
برای پیاده‌سازی سامانه‌ی توصیه‌گر دو روش اساسی وجود دارد و روش سومی که از تلفیق این دو روش به‌وجود می‌آید. پیاده‌سازی مدل Content-base filtering به زمان زیاد برای اضافه‌‌کردن محصولات نیاز دارد. باید مشخصات کاربر ثبت شود و برای هریک از محصولات ، مشخصات آن‌محصول استخراج و تهیه شود و سپس محصولات مشابه یافت شود. پس این‌روش کنار می‌رود.
روش دیگر پیاده‌سازی یعنی Collaborative filtering را برای پیاده‌سازی این‌فاز انتخاب کردیم. این‌روش انواعی دارد که هریک را توضیح‌میدهیم و سپس مناسب‌ترین را با ذکر دلیل پیاده‌ میکنیم.
![تصویر ۵ [26]](https://ars.els-cdn.com/content/image/1-s2.0-S1110866515000341-gr2.jpg)
دو تقسیم‌بندی اساسی در این‌ روش وجود دارد. Memory-based filtering و Model-based filtering. 

**روش Memory-based filtering**
در این‌روش با توجه به نمره‌دهی های کاربران در گذشته، محصولات مشابه شناسایی شده و پیشنهاد می‌شوند[27].
![تصویر ۶ [28]](http://www.salemmarafi.com/wp-content/uploads/2014/04/collaborativeFiltering-960x540.jpg)
 یکی از تقسیم‌بندی‌های ریز این بخش سامانه‌ی user-based است. در این‌نوع پیاده‌سازی افراد مشابه باتوجه به امتیازاتی که به محصولات داده‌اند استخراج می‌شوند و با توجه به سلایق یکسانشان، محصولات پیشنهادی انتخاب می‌شود. به عبارت دیگر: "اگر فرد ب تشابه زیادی در انتخاب محصول یا امتیازدهی با شما داشته باشد، کالاهایی که مورد پسند او است احتمالا برای شما جذاب باشد."
 قسمت دوم تقسیم‌بندی این بخش، تکنیک item-based است. در این‌تکنیک محصولات مشابه برحسب امتیازاتی که کاربران فعال به آن داده‌اند استخراج می‌شوند و سپس به‌جای هم پیشنهاد می‌شوند. به عبارت دیگر: "اگر محصول الف تشابه زیادی با محصول ب داشته‌باشد، اگر از الف خوشتان بیاید احتمالا از ب نیز خوشتان بیاید و باالعکس." این‌روش در خصوص دیتاست های امتیازدار به‌خوبی نتیجه می‌دهد. در بخش پیاده‌سازی اولیه، ما این تکنیک را انتخاب کرده‌ایم. پس از توضیح دیگر تکنیک‌ها به بررسی ریزتر این‌تکنیک می‌پردازیم [30, 29].

**تکنیک‌های Model-based **
![تصویر ۷ [31] ](https://boute.s3.amazonaws.com/304-cf.jpg)
در این‌نوع تکنیک، با به‌کارگیری نتایج روش قبلی، الگویی استخراج می‌شود که با‌استفاده از آن محصول جدید به کاربر پیشنهاد می‌شود. برای شناسایی الگو از روش‌های بسیاری استفاده می‌شود که اکثر آن‌ها زیرمجموعه روش های خوشه‌بندی [32] و کلاسه‌بندی [33] هستند.
![تصویر ۸ [34]](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e5/KMeans-Gaussian-data.svg/279px-KMeans-Gaussian-data.svg.png)
در تکنیک‌های خوشه‌بندی، محصولات باتوجه به امتیازات و درصدتشابهاتی که دارند بدون هیچ‌گونه برچسبی به دسته‌های مختلف تقسیم‌می‌شوند. دسته‌های مختلف با توجه به مشخصات مشابهی  (که از روش‌های متفاوتی این معیار اندازه‌گیری می‌شود) که دارند، با انتخاب میزان دقت به چند دسته متفاوت تقسیم می‌شوند که محصولات هردسته، مشابع یکدیگرند و به‌جای هم پیشنهاد می‌شوند(تصویر ۸).
در تکنیک‌های کلاسه‌بندی، ما دسته‌های مختلف را از ابتدا می‌دانیم و قسمتی از داده‌ی خود را در این دسته‌ها قرار‌ داده‌ایم. با توجه به الگوی استخراج‌شده از این نوع برچسب‌گذاری، داده‌ی جدید بدون برچسب را برچسب‌گذاری می‌کنیم و پیش‌بینی می‌کنیم هریک در کدام یک از این‌دسته‌ها قرار می‌گیرند.
حال که انواع تکنیک‌های Collaborative filtering آشنا شدیم، جهت انتخاب تکنیک مناسب ابتدا باید به آنالیز مجموعه‌داده‌مان بپردازیم.

**مجموعه‌داده**
مجموعه‌داده ما، قسمتی از مجموعه‌داده فروشگاه آمازون است. این‌مجموعه‌ی داده، خام و بدون هیچ‌گونه نمونه‌برداری آموزشی یا برچسب‌گذاری تهیه‌شده است و بررسی‌های مشابهی روی این‌دیتاست یافت نشد. بنابراین تمامی مراحل لازم  پیش‌پردازش و پردازش باید از ابتدا طی شود. 
ابتدا به بررسی ستون‌های موجود در این دیتاست می‌پردازیم:
+ کاربر (user):در این‌ستون id کاربر فروشگاه قرار دارد. مقداری یکتا که هرکاربر را از دیگری متمایز می‌کند.
+ محضول (item): در این‌ستون id محصول وجود دارد. مقداری یکتا که هرمحصول را از محصول دیگر متمایز می‌کند.
+ امتیاز (rating): در این‌ستون امتیاز داده شده‌ی کاربر به آن‌محصول وجود دارد که مقداری از ۱ تا ۵ را می‌گیرد.
+ زمان (timestamp): در این‌ستون زمان امتیاز داده شده موجود می‌باشد. از عدد موجود برای مقایسه‌زمان ها می‌توان استفاده نمود. 
حجم داده‌های موجود، باتوجه به انتخاب دسته‌ی مورد نظر متفاوت می‌باشد. دسته‌های مختلف (کتاب، فیلم، و ...) حجم های متفاوتی دارند که از ۵۰۰۰۰۰ سطر تا ۲۲۰۰۰۰۰۰ سطر قرار دارند. 
اولین‌چالش حجم بالای اطلاعات‌ است. در سامانه‌های توصیه‌گر دو نوع پردازش به طور عمومی وجود‌ دارد: پردازش آفلاین و آنلاین. پردازش آفلاین در هرزمانی امکان دارد و نتایج این‌پردازش در زمانی که کاربر یک محصول را مشاهده می‌کند، ارائه می‌شود. پردازش آنلاین درلحظه صورت میگیرد و هنگامی که کاربر در حال مشاهده‌ی یک محصول است، سامانه‌ی توصیه‌گر به محاسبه‌ی محصولات و تشابه بین آن‌ها می‌پردازد تا نتیجه‌ی مناسب را به کاربر نشان دهد. هدف ما انتخاب روشی است که حداکثر پردازش آفلاین و حداقل پردازش آنلاین را دارد و در عین حال نتیجه با دقت خوبی به کاربر ارائه شود.
روش‌های سنتی Collaborative filtering معمولا پردازش آفلاینی ندارند و یا میزان آن بسیار ناچیز است. در این‌روش ها که شباهت کاربر با کاربران دیگر درخصوص یک‌محصول به صورت آنلاین محسابه می‌شود، با توجه به نیاز به جواب در لحظه، سیستم‌های پردازشی قوی‌ای را می‌طلبد و همچنین روی دیتاست‌های بزرگی چون دیتاست آمازون به‌خوبی نتیجه نمی‌دهد. بنابراین این روش را از فاز پیاده‌سازی حذف می‌کنیم
روش های خوشه‌بندی مشکل طبقه‌بندی آنلاین را تا حد خوبی رفع می‌کنند. در این روش‌ها اکثر محاسبات به صورت آفلاین انجام می‌شود، اما دقت زیادی ندارد. برای افزایش دقت نیاز به افزایش تعداد‌ دسته‌ها است که افزایش قابل توجه هزینه را درپی دارد . همچنین برای افزودن دسته‌های جدید و استفاده از روش‌های کلاسه‌بندی user-based پردازش آنلاین را می‌طلبد که مشکلات روش قبل را درپی‌ خواهد داشت [35].  
روش باقی‌مانده، تکنیک item-based است که زیرمجموعه‌ی تکنیک memory based می‌باشد. یعنی محصولات مشابه را پیدا می‌کنیم و سپس به‌جای یکدیگر پیشنهاد می‌دهیم. کدهای پیاده سازی آماده‌ی بسیاری در این‌زمینه وجود دارند که نیاز به پیاده‌سازی مجدد را برطرف می‌کنند [36]. اما متاسفانه همه‌ی آن‌ها از روش‌های معمول item-based استفاده می‌کنند که سوال‌های زیر را ایجاد می‌کند:
با توجه به زیاد بودن محصولات فروشگاه آمازون، استفاده از روش‌های معمول item-based به صرفه است؟ اکثر آنان به بررسی تشابه میان تک‌تک محصولات می‌پردازند که پیچیدگی فضای آن از مرتبه O(n^2) می‌باشد که  n تعداد محصولات است. همچنین پیچیدگی زمانی آن ترکیبی پیچیده‌تر از پیچیدگی فضای‌حافظه آن است چون باتوجه به معیار مقایسه تشابه، تعداد کاربران را نیز درگیر می‌کند. حال با این حجم عظیم داده چگونه با این‌پیچیدگی محاسبات را انجام دهیم؟ فرض کنید به نمونه‌برداری محصولات معروف بپردازیم. محصولات دیگر هیچوقت پیشنهاد نمی‌شوند. با محصولات جدید چه کنیم؟ فرض کنید برای کم کردن پیچیدگی زمانی به نمونه برداری کاربران فعال بپردازیم. با پیچیدگی حافظه چه‌ کنیم؟
با توجه به روبروشدن با این‌سوال ها روش های معمول item-based را کنار گذاشتیم و به سراغ روش منحصربه‌فرد فروشگاه آمازون یعنی item to item Collaborative filtering رفتیم. الگوریتم کلی این روش را با استفاده از شبه‌کد توضیح می‌دهیم:
![تصویر ۹ [37]](https://boute.s3.amazonaws.com/304-Capture.PNG)
در ابتدا برای کم‌کردن میزان پیچیدگی، سامانه‌ی توصیه‌گر توصیه های خود را از دسته‌بندی مشابه انتخاب می‌کند. به عنوان مثال در صورت انتخاب یک نوع کتاب خاص کتاب‌های مشابه به شما پیشنهاد می‌شود و در صورت انتخاب یک فیلم خاص، فیلم های مشابه. بدین صورت به جای محاسبه تشابه میان کل محصولات، کافیست محصولات هر دسته را جداگانه بررسی کنیم و همین روند در بهبود سرعت کار بسیار تاثیرگزار خواهد بود. درون یک دسته نیز ما تمام محصولات را تشابهشان را با هم محاسبه نمی‌کنیم. بسیاری از محصولات هستند که یک کاربر به هردوی آن‌ها امتیاز نداده است. در نتیجه بسیاری از هزینه زمانی و حافظه صرف محاسبه و نگهداری تشابهاتی می‌شود که از ابتدا میزان ۰ بودن آن‌ها مشخص است. بنابراین فقط به بررسی تشابهات غیر ۰ می‌پردازیم. روش‌های محاسبه تشابه (similarity) بسیار زیاد و متنوعند. استفاده‌ی نادرست از این روش‌ها با وجود دانستن کم بودن دقت( precision and recall [38](توضیح در منبع) ) یک اشتباه است. برای استفاده از روش اندازه‌گیری تشابه مناسب باید به نوع متغیر توجه کرد. متغیرها انواعی دارند :
+ غیر عددی مانند سبز و قرمز و ...
+ عددی باینری متقارن که جابه‌جایی  ۰ و ۱ ها تاثیری در تحلیل ندارد.
+ عددی باینری نامتقارن که جابه‌جایی  ۰ و ۱ ها در تحلیل تاثیرگزار است.
+ عددی غیر باینری
+ ترتیبی مانند بد، خوب و عالی
متغیرهای ما به نوعی ترتیبی هستند که هرکدام از صفت‌هارا به یک‌عدد نسبت دادیم. یکی از بهترین‌انواع  محاسبه similarity برای این نوع متغیر شباهت مثلثاتی (Cosine similarity [39] )(تصویر ۱۰) است.
![تصویر ۱۰](https://boute.s3.amazonaws.com/304-1.PNG)
به‌علت انتخاب بسیار ریز‌ ما در روش پیاده‌سازی، بسیاری از مراحل می‌بایست شخصی‌سازی می‌شدند تا پیچیدگی زمانی و حافظه رعایت شود. نمونه اولیه این محاسبه شباهت در گیت‌هاب موجود است. در پیاده‌سازی این‌روش از ماژول‌های زیر استفاده شده‌است:
+ ماژول pandas: برای دسته بندی و فیلترینگ داده‌ها به صورت جدولی
+ ماژول scipy:برای محاسبات آماری
در فاز بعدی، به بررسی دقت روش‌مان میپردازیم. برای این‌کار باید داده‌ی تست را از داده خام تولید کنیم. همچنین به بهبود سرعت و پیچیدگی زمانی الگوریتم پیاد‌ه شده‌ می‌پردازیم تا به پیچیدگی استاندارد فروشگاه آمازون برسد. باوجود انتخاب درست و دقیق روش محاسبه شباهت، به بررسی دقیق‌تر روش های مشابه شباهت مثلثاتی نیز می‌پردازیم. 

در این فاز روند اجرای کار را اندکی تغییر می‌دهیم . ابتدا به بررسی دلایل تغییر روند می‌پردازیم.
داده استفاده شده‌ی ما داده‌ی اصلی سایت آمازون بود. برای بررسی دقیق‌تر مشکل ابتدا به تعریف برخی مفاهیم می‌پردازیم:

1. ** پراکندگی (sparsity)**
فرض کنید برای مدل کردن اطلاعات موجود در مجموعه‌داده، داده را به صورت گراف نشان می‌دهیم . به شکل یک گراف دوبخشی که یکی از بخش های آن مشتری‌ها و بخش دیگر کالا باشد . یال‌های این‌گراف ارتباط بین فرد با کالا را مشخص می‌کند. این رابطه می‌تواند نظردادن، امتیازدهی یا خرید باشد. به‌صورت شهودی گراف sparse در اینجا گرافی است که همسایه‌های مشترک افراد و کالاها کم و گراف dense گرافی است که همسایه‌ی مشترک کالا‌ها با افراد زیاد باشد. تفاوت گراف دوبخشی dense با sparse را در شکل زیر مشاهده می‌کنید(تصویر۱۱). گراف بالایی چگال و گراف پایینی پراکنده است.
![تصویر ۱۱](https://boute.s3.amazonaws.com/304-Figure-3-Graph-its-corresponding-adjacency-matrix-plotted-on-the-right-with-different.png). 
2. **نمونه‌برداری (sampling)**
نمونه‌برداری یا sampling یکی از عملیات‌های لازم و ضروری برای شروع کار با داده است.نمونه‌برداری عبارت‌ است از انتخاب زیرمجموعه‌ای از جامعه‌ی آماری برای تخمین زدن خصوصیات جامعه اصلی[40]. وقتی حجم داده زیاد باشد باید به گونه‌ای نمونه‌برداری کرد نتایج آزمایش‌های اعمال شده روی داده‌ی نمونه‌برداری شده را بتوان به جامعه‌ی اصلی تعمیم داد.

در مجموعه‌ی داده ما به‌دلیل حجم بالای داده امکان تست از کل داده وجود نداشت. درنتیجه برای تست نیاز به نمونه‌برداری از داده بود. همچنین گراف داده‌ما گرافی sparse بود . بدین صورت که عده‌ی زیادی وجود داشتند که تنها یک کالا خریده بودند و کالاهای بسیاری که فقط توسط یک‌نفر خریداری شده بودند. این عمل کار تست را با مشکل مواجه می‌کند . در نتیجه ما به نمونه برداری‌ای dense، از گراف sparse خود نیاز داریم . که این با توجه به حجم بالای اطلاعات بسیار زمان‌گیر خواهد بود . درنتیجه مجموعه‌ی داده خود را عوض کردیم تا مشکلات ذکر شده حل گردد [41].

مجموعه‌داده انتخابی جدید مجموعه‌داده‌ی سایت movieLens است. ستون‌های این دیتاست عبارتند از:

1. ستون uid که id افراد بین عدد۱ تا ۹۴۳ می‌باشد.
2. ستون itemid که ۱۶۸۲ کالا را شامل می‌شود.
3. ستون امتیاز که بین ۱ تا ۵ مقدار می‌گیرد.
4. ستون زمان 

یکی از نکات مثبت این مجموعه‌داده dense بودن گراف دوبخشی آن می‌باشد چون هرکاربر حداقل به ۲۰ کالا امتیاز داده است.
برای فرایند پیش‌بینی و ارزشیابی از زبان پایتون و ماژول های زیر استفاده شده است:
1. ماژول numpy که یک ماژول قدرتمند در زمینه محاسبات علمی در زبان پایتون است[42] .
2. ماژول tabulate که برای زیباسازی نمایش داده‌های جدولی به کار می‌رود[43].
3.  ماژول surprise به عنوان هسته‌ی کلیدی که روش های پیاده‌سازی سامانه‌توصیه‌گر را برعهده دارد[44].
4. ماژول های متداول زمان و دسته‌بنده اطلاعات.

برای توضیح الگوریتم‌های استفاده شده ابتدا نیاز به تعریف برخی متغیرهایی داریم که از‌آن استفاده‌ میکنیم:
![تصویر12](https://boute.s3.amazonaws.com/304-notation.PNG)
درخصوص امتیاز baseline، امتیازی است که از تقریب میانگین امتیازات با جابه‌جایی به اندازه‌ی اختلاف کالای i نسبت به دیگر کالاها و اندازه اختلاف میانگین امتیازات شخص u به دیگر کاربران بدست می‌آید(تصویر ۱۳).
![تصویر13](https://boute.s3.amazonaws.com/304-baseline.JPG)
 برای مثال فرض کنید امتیاز فیلم dunkirk را توسط علی طبق این این روش می‌خواهیم بدست آوریم. میانگین امتیازات کل فیلم ها 3.7 است. درنتیج مقدار میانگین را 3.7 می‌گذاریم. درثانی dunkirk امتیازاتش 0.5 امتیاز بالاتر از میانگین فیلم هاست . و در آخر علی بسیار حساس است در امتیازدهی بنابراین 0.3 امتیاز نسبت به میانگین کمتر امتیاز می‌دهید. درنتیجه برای امتیاز baseline علی برای این فیلم داریم: 0.5+0.3-3.7. اطلاعات جامع‌تر در منبع موجود است[45].

برای پیش‌بینی امتیازات از روش‌های زیر استفاده شده است که هریک را به اختصار توضیح می‌دهیم:
1. **الگوریتم BaselineOnly**
در این روش، امتیاز پیش‌بینی شده‌، همان امتیاز baseline می‌باشد(تصویر ۱۴).
![تصویر14 [46]](https://boute.s3.amazonaws.com/304-baselineonly.JPG)
2. **الگوریتم NormalPredictor**
در این‌روش امتیاز پیش‌بینی شده‌ی شخص u برای کالای i از توزیع نرمال بدست‌آمده از داده‌ی آموزشی به صورت زیر استخراج می‌شود(تصویر ۱۵):
![تصویر ۱۵[47]](https://boute.s3.amazonaws.com/304-normal.PNG). 
3.  **الگوریتم KNNBasic**
در این‌روش، روی مجموعه‌ای از همسایگی k شخص u یک میانگین وزن دار از امتیازات افراد به کالای i می‌گیریم که وزن آن برابر میزان شباهت u و شخص دوم است(تصویر ۱۶).
![تصویر16[48]](https://boute.s3.amazonaws.com/304-knnbasic.JPG)
4. **الگوریتم KNNWithMeans**
این الگوریتم نیز مشابه الگوریتم پیشین است با این تفاوت که میانگین امتیازات کاربر را هم در فرمول دخیل می‌کند(تصویر ۱۷).
![تصویر 17[49]](https://boute.s3.amazonaws.com/304-knnwithmeans.JPG)
5. **الگوریتم KNNBaseline** 
این الگوریتم نیز مانند الگوریتم KNNWithMeans است با این تفاوت که امتیاز baseline را در فرمول دخیل می‌کند(تصویر ۱۸).
![تصویر 18[50]](https://boute.s3.amazonaws.com/304-knnwithbaseline.JPG)

----------

همچنین برای ارزیابی نتایج ۵ سنجشگر را انتخاب کرده ایم:
1. **سنجشگر MAE** 
می‌دانیم که داده‌ی ما از دوبخش داده‌ی آموزشی و داده‌ی تست تشکیل شده است. در مجموعه‌ی داده‌ی تست به میانگین اختلاف امتیاز پیش‌بینی شده با امتیاز اصلی MAE (Mean Absolute Error) می‌گویند(تصویر ۱۹).
![تصویر 19](https://boute.s3.amazonaws.com/304-mea.JPG)
2. **سنجشگر RMSE**
در سنجشگر قبلی فرض کنید اختلاف امتیاز پیش‌بینی شده با امتیاز اصلی حول ۰ به صورت متقارن پراکنده شده باشد. درنتیجه سنجشگر MAE نتیجه‌ی کمی را نشان می‌دهد با اینکه دقت توصیه‌گرمان پایین بوده. برای حل این مشکل از RMSE (Root Mean Squared Error)استفاده می‌شود که به نوعی اختلاف اندازه را محاسبه می‌کند نه اختلاف مقدار را (تصویر ۲۰).
![تصویر 20](https://boute.s3.amazonaws.com/304-rmse.JPG)
3. **سنجشگر precision**
افراد از تعدادی از کالاها خوششان می‌آید (که در کد آستانه این انتخاب را امتیاز ۴ لحاظ کردیم) و توصیه‌گر به هر کاربر تعداد محدودی محصول را پیشنهاد می‌دهد (که در اینجا ۵ محصول را لحاظ کردیم). نسبت توصیه هایی که کاربر آن‌هارا می‌پسندد به کل کالاهای توصیه شده‌مان precision نامیده‌می‌شود(تصویر ۲۱).
4. **سنجشگر recall**
نسبت کالاهای پیشنهاد‌شده به تمامی کالا‌هایی که کاربر می‌پسندد(امتیاز بالای ۳ داده‌است) recall نامیده‌می‌شود(تصویر ۲۱).
![تصویر 21 [51]](https://upload.wikimedia.org/wikipedia/commons/2/26/Precisionrecall.svg)


----------


+  **روند اجرای برنامه**
برای تست دقت الگوریتم‌ها از k-fold cross validation  استفاده شده‌است [52]. در این‌روش داده‌ی کلی را چند مرحله تست می‌کنیم (که در اینجا ۵ مرحله است) و در هرمرحله قسمتی از داده به عنوان تست و باقی‌مانده‌ی آن به عنوان داده‌ی آموزشی درنظر گرفته می‌شود (تصویر ۲۲).
![تصویر 22 [52]](https://upload.wikimedia.org/wikipedia/commons/1/1c/K-fold_cross_validation_EN.jpg)  
در هرمرحله زمان را محاسبه کرده و پس از اجرای الگوریتم طول زمان اجرای آن را بدست می‌آوریم، rmse  و mea را همراه آن ذخیره کرده و precision و recall را از میانگین مقادیر‌ آن برای تمامی اشخاص محاسبه می‌کنیم و سپس ذخیره می‌کنیم.
پس از تکرار چندباره‌ی تست(در اینجا ۵ بار) میانگین مقادیر ذخیره شده برای سنجش را محاسبه و ارائه می‌دهیم.
نکته ای دیگر اینست که برای محاسبه precision و recall با گرفتن مقادیر پیش‌بینی شده و آستانه‌ی پسند کاربر و تعداد توصیه‌ها طبق تعریفی که از این دو سنجشگر ارائه کردیم، محسابات را برای هرکاربر انجام دادیم.
 خروجی نهایی برنامه به صورت زیر می‌باشد(تصویر ۲۳):
![تصویر 23](https://boute.s3.amazonaws.com/304-result.JPG)
که با یک نمودار برای ساده‌کردن مقایسه این‌چنین می‌شود(تصویر ۲۴):
![تصویر 24](https://boute.s3.amazonaws.com/304-test_result.JPG)

# بهبود نتایج
در اینجا الگوریتم‌هایی را استفاده‌کرده‌ایم که از همسایگی و شباهت‌سنج ها استفاده‌ می‌کردند. در این‌قسمت به بررسی جزئی تر این شباهت‌سنج ها و همسایگی ها می‌پردازیم. مقدار همسایگی برای توصیه‌گیر های مبتنی بر KNN ،  مقدار ۴۰ همسایه بود که که ما‌ آن را متغیری بین ۴۰ تا ۹۴۰ قرار دادیم. درخصوص محاسبات شباهت‌سنج نیز دو‌حالت اساسی وجود دارد: حالت user_based و حالت item_based که قبلا به آن اشاره شده است. به صورت پیشفرض محاسبات شباهت بر اساس شباهت بین افراد محاسبه می‌شود. اگر به حالت item_based تغییر دهیم، KNNBasic  و KNNWithMeans و KNNBaseline به صورت زیر تغییر می‌کنند(تصاویر ۲۵ ،۲۶ و ۲۷):
![تصویر 25 . KNNBasic](https://boute.s3.amazonaws.com/304-knnbasic2.JPG)
![تصویر 26. KNNWithMeans](https://boute.s3.amazonaws.com/304-knnwithmeans2.JPG)
![تصویر 27. KNNBaseline](https://boute.s3.amazonaws.com/304-knnwithbaseline2.JPG)
همچنین شباهت‌سنج‌هایی که استفاده کردیم همه مقادیر پیشفرض (MSD) بودند. در این مرحله شباهت‌سنج‌های مختلفی را تعریف و از آن‌ها استفاده‌ می‌کنیم.
1. ** شباهت‌سنج MSD**
شباهت‌سنج Mean Squared Difference میانگین اختلاف مربعات امتیازات را با توجه به user_based یا item_based بودن محاسبه می‌کند[53]. ابتدا msd را بدست می‌آورد(تصویر ۲۸):
![تصویر 27 ](https://boute.s3.amazonaws.com/304-msd.JPG)
سپس برا تبدیل آن از dissimilarity به similarity بدین‌صورت تغییر می‌دهد(تصویر ۲۹):
![تصویر 28](https://boute.s3.amazonaws.com/304-msd_sim.JPG)
2. **شباهت‌سنج Cosine**
باتوجه به توضیح پیشین‌ دراین مورد، به آوردن فرمول آن(user_based و item_based) کفایت می‌کنیم(تصویر ۲۹):
![تصویر 29 [54]](https://boute.s3.amazonaws.com/304-cosine.JPG)
3. **شباهت‌سنج  Pearson**
این شباهت‌سنج را می‌توان به نوعی تعمیم یافته‌ی شباهت‌سنج Cosine نامید با دخالت دادن میانگین در فرمول. فرمول آن(user_based و item_based) بدین‌صورت است(تصویر ۳۰):
![تصویر 30 [55]](https://boute.s3.amazonaws.com/304-pearson.JPG)
4. **شباهت‌سنج Pearson_baseline**
این شباهت‌سنج شباهت زیادی به شباهت‌سنج Pearson دارد با تفاوت آن که به‌جای میانگین، از امتیاز baseline استفاده‌کرده است(تصویر ۳۱):
![تصویر 31 [56]](https://boute.s3.amazonaws.com/304-pearson_baseline.JPG)

با تغییر دادن تمامی این‌متغیر‌ها به نتایج زیر دست‌یافتیم:
1. با تغییر متغیر تعداد عضو همسایگی، تغییر خاصی در نتیجه ملاحظه نشد. این‌مورد می‌تواند در‌ داده‌های بزرگتر تاثیر خود را نشان‌دهد. پس با همسایگی ۴۰ به ادامه‌ی بررسی‌ها می‌پردازیم. بنابراین حال می‌توان نتایج را در جدولی نشان داد(تصویر ۳۲):
![تصویر 32](https://boute.s3.amazonaws.com/304-result_all.JPG)
2. با توجه به اینکه ۸ آزمایش برای هر الگوریتم انجام شده است، با مقایسه های سنجشگر‌ها ، الگوریتم دقیق‌تر را شناسایی می‌کنیم:
![تصویر 33](https://boute.s3.amazonaws.com/304-rmse_compare.JPG)
![تصویر 34](https://boute.s3.amazonaws.com/304-mea_result.JPG)
با مقایسه RMSE و MEA(تصاویر ۳۳ و ۳۴) اختلاف بسیار KNNBasic با دیگر الگوریتم ها مشهود است. در اینجا KNNBaseline دقت بیشتری دارد.
![تصویر 35](https://boute.s3.amazonaws.com/304-precision_result.JPG)
![تصویر 36](https://boute.s3.amazonaws.com/304-recall_result.JPG)
با مقایسه کردن Precision و Recall(تصاویر ۳۵ و ۳۶) به نتایج جالبی می‌رسیم. KNNBasic باز هم عموما دقت کمتری نسبت به سایر گزینه‌ها دارد. روند تغییر جالب KNNBaseline و KNNWithMeans کاملا مخالف هم است. در مقادیر زوج precision الگوریتم KNNWithMeans برتری دارد با آنکه در همین مقادیر در Recall برعکس است. لازم به ذکر است آزمایش های مقادیر زوج همگی آزمایش‌های user_based اند(طبق جدول نتایج). در نتیجه در احتمالا کاربر از کالاهای پیشنهادی در این الگوریتم خوشش خواهد‌ آمد اما کالاهای بیشتری نیز وجود دارند که کاربر‌ آن‌ها را نیز می‌پسندد. در خصوص آزمایش‌های item_based نتیجه برعکس است.
3. برای هرکدام از روش‌های item_based و user_based، تعداد آزمایش‌ها برابر ۱۲ است. این آزمایش‌ها را با هم مقایسه می‌کنیم:
![تصویر 37](https://boute.s3.amazonaws.com/304-mea_u.JPG) 
![تصویر 38](https://boute.s3.amazonaws.com/304-rmse_u.JPG)
با توجه به یکسانی روند رشد نمودارهای MEA و RMSE ، بهتر است از RMSE به تنهایی استفاده شود که خلا‌های MEA را نیز پر کند(تصاویر ۳۷ و ۳۸).
![تصویر 39](https://boute.s3.amazonaws.com/304-precision_u.JPG)
![تصویر 40](https://boute.s3.amazonaws.com/304-recall_i.JPG)
با توجه به تصاویر، اختلاف اختلاف تقریبا ناچیز است به جز مواردی که در آزمایش ۵،۶،۷ و ۸ وجود دارد. این آزمایش‌ها مربوط به آزمایش‌های KNNBasic می‌باشد. که در نتیجه‌گیری قبل با توجه به نمودار‌ها، دقت کمی‌ داشت. پس با درنظر‌گرفتن این‌مورد، می‌توان با اختلاف اندک آزمایش‌های مبتنی بر اشخاص را دقیق‌تر نامید.
4.  این‌بار به بررسی الگوریتم شباهت‌سنج می‌پردازیم. برای هر‌الگوریتم ۶ آزمایش‌ داریم. آن‌ها را با یکدیگر مقایسه می‌کنیم:
![تصویر 41](https://boute.s3.amazonaws.com/304-precision_m.JPG)
در مقایسه precision ها(تصویر ۴۱) msd با اختلافی اندک دقیق‌تر است.
![تصویر 42](https://boute.s3.amazonaws.com/304-recall_m.JPG)
در این‌آزمایش نتایج نزدیک است به جز آزمایش شماره ۳ که برای مقایسه‌ی الگوریتم KNNBasic با روش item_based است که در نتایج قبل از دقت کمتری برخوردار بودند. 
![تصویر 43](https://boute.s3.amazonaws.com/304-rmse_m.JPG)
با این نمودار دقت بالای msd تایید می‌شود.

**نتیجه‌گیری نهایی**
برای اجرای الگوریتم با دقت بالا بهتر است از روش KNNBaseline با متود user_based و شباهت‌سنج msd  استفاده‌کنید. نکته‌ی بسیار جالب این است که نتیجه‌ی حاصل، همان تنظیمات پیشفرض KNNbaseline در این ماژول می‌باشد!
# کارهای‌ آینده
بهتر است در قسمت ساختن توصیه‌گر جدید ماژول surprise ، توصیه‌گر آمازون که در ابتدا قصد پیاده‌سازی آن را داشتیم‌ را اضافه‌کنیم. روش‌های دیگری به جز روش‌های مبتنی بر شباهت‌سنج و KNN نیز وجود‌ دارند که بهتر است آن‌ها نیز در مقایسه سهیم شوند. همچنین پیشنهاد‌ می‌شود از نتایج این‌پروژه برای آزمایش‌های بعدی استفاده شود تا برای آزمایش‌ها هزینه‌ی زمانی کمتری مصرف شود. 



 

 


 


# مراجع
[1] http://www.sciencedirect.com/science/article/pii/S1110866515000341  
[2] http://www.sciencedirect.com/science/article/pii/S1110866515000341
[3] https://en.wikipedia.org/wiki/Spiral_model
[4] http://recommender-systems.org/collaborative-filtering/
[5] http://www.sciencedirect.com/science/article/pii/S1110866515000341  
[6] https://en.wikipedia.org/wiki/Collaborative_filtering#/media/File:Collaborative_filtering.gif
[7] http://jolomo.net/ringo.html
[8] https://www.amazon.com/
[9] https://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf
[10] https://www.last.fm/
[11] https://en.wikipedia.org/wiki/Last.fm
[12] http://findoutyourfavorite.blogspot.com/2012/04/content-based-filtering.html
[13] http://recommender-systems.org/content-based-filtering/
[14] http://www.sciencedirect.com/science/article/pii/S1110866515000341 
[15] https://www.pandora.com/
[16] https://en.wikipedia.org/wiki/Recommender_system
[17] https://en.wikipedia.org/wiki/Cold_start
[18] https://en.wikipedia.org/wiki/Threshold_model
[19] https://en.wikipedia.org/wiki/Statistical_classification
[20] http://blog.stevekrause.org/2006/01/pandora-and-lastfm-nature-vs-nurture-in.html
[21] http://www.sciencedirect.com/science/article/pii/S1110866515000341 
[22] https://en.wikipedia.org/wiki/Recommender_system 
[23] https://www.netflix.com/
[24] https://rpubs.com/kismetk/Netflix-recommendation
[25] https://dl.acm.org/citation.cfm?id=2843948
[26] http://www.sciencedirect.com/science/article/pii/S1110866515000341
[27] Zhao ZD, Shang MS. User-based collaborative filtering recommendation algorithms on Hadoop. In: 
Proceedings of 3rd international conference on knowledge discovering and
 data mining, (WKDD 2010), IEEE Computer Society, Washington DC, USA; 
2010. p. 478–81. doi: [10.1109/WKDD.2010.54](https://doi.org/10.1109/WKDD.2010.54).

[28] http://www.salemmarafi.com/code/collaborative-filtering-with-python/ 
[29] Melville P, Mooney-Raymond J, Nagarajan R. Content-boosted collaborative filtering for improved recommendation. In: Proceedings of the eighteenth
 national conference on artificial intelligence (AAAI), Edmonton, Canada; 2002. p. 187–92.
 [30] D. Jannach, M. Zanker, A. Felfernig, G. Friedrich**Recommender systems – an introduction**
Cambridge University Press (2010)
 [31] https://abgoswam.wordpress.com/2016/06/13/recommendation-systems-approaches/
 [32] https://en.wikipedia.org/wiki/Cluster_analysis
 [33] https://en.wikipedia.org/wiki/Statistical_classification
 [34] https://en.wikipedia.org/wiki/Cluster_analysis
 [35] https://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf
 [36] http://www.salemmarafi.com/code/collaborative-filtering-with-python/
 [37] https://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf
 [38] https://en.wikipedia.org/wiki/Precision_and_recall
 [39] https://en.wikipedia.org/wiki/Cosine_similarity
 [40] https://en.wikipedia.org/wiki/Sampling_(statistics)
 [41] https://grouplens.org/datasets/movielens/100k/
[43] https://pypi.python.org/pypi/tabulate
[44] http://surprise.readthedocs.io/en/stable/index.html
 [45] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. 2008. URL: http://www.cs.rochester.edu/twiki/pub/Main/HarpSeminar/Factorization_Meets_the_Neighborhood-_a_Multifaceted_Collaborative_Filtering_Model.pdf.
 [46]http://surprise.readthedocs.io/en/stable/basic_algorithms.html#surprise.prediction_algorithms.baseline_only.BaselineOnly
 [47]http://surprise.readthedocs.io/en/stable/basic_algorithms.html#surprise.prediction_algorithms.random_pred.NormalPredictor
 [48] http://surprise.readthedocs.io/en/stable/knn_inspired.html#surprise.prediction_algorithms.knns.KNNBasic
 [49] http://surprise.readthedocs.io/en/stable/knn_inspired.html#surprise.prediction_algorithms.knns.KNNWithMeans
 [50] http://surprise.readthedocs.io/en/stable/knn_inspired.html#surprise.prediction_algorithms.knns.KNNBaseline
 [51] https://en.wikipedia.org/wiki/Precision_and_recall
[52] https://en.wikipedia.org/wiki/Cross-validation_(statistics)#k-fold_cross-validation
[53] http://surprise.readthedocs.io/en/stable/similarities.html#surprise.similarities.msd
[54] http://surprise.readthedocs.io/en/stable/similarities.html#surprise.similarities.cosine
[55] http://surprise.readthedocs.io/en/stable/similarities.html#surprise.similarities.pearson
[56] http://surprise.readthedocs.io/en/stable/similarities.html#surprise.similarities.pearson_baseline
 

# پیوندهای مفید
+ [مجموعه داده](http://shuaizhang.tech/2017/03/15/Datasets-For-Recommender-System/)
+ [پروژه گیت‌هاب](https://github.com/amirmohammadkz/recommender)