پیشنهاد دادن آنچه مخاطب از آن استقبال خواهد کرد، برعهده سامانه‌های توصیه‌گر است. این سامانه‌ها که امروز ما کاربر بسیاری از آنها هستیم، سعی می‌کنند از روی علاقه‌مندی‌های ما و دیگران، مثلا اینکه ما چه کتاب‌هایی را خوانده‌ایم و دیگران که علایقی مشابه ما داشته‌اند، مثلا چه کتاب‌هایی را خوانده‌اند، پیشنهاد مناسبی به ما بدهند.

Git Hub

۱. مقدمه

Recommender System

سامانه توصیه‌گر (به انگلیسی: Recommender System) یا سامانه پیشنهادگر، با تحلیل رفتار کاربر خود، اقدام به پیشنهاد مناسب‌ترین اقلام
(داده، اطلاعات، کالا و...)می‌نماید.
این سیستم رویکردی است که برای مواجهه با مشکلات ناشی از حجم فراوان و رو به رشد اطلاعات ارائه شده‌است و به کاربر خود کمک می‌کند تا در میان حجم عظیم اطلاعات سریع‌تر به هدف خود نزدیک شوند. برخی سامانه پیشنهادگر را معادل پالایش گروهی (به انگلیسی: Collaborative filtering) می‌دانند.
پیش بینی می‌شد که تا اوایل سال ۲۰۰۷ میلادی در سایت دانشنامه اینترنتی ویکی‌پدیا چیزی حدود ۵٫۱ میلیون مقاله به ثبت رسیده باشد و یا سایت مدیریت و به اشتراک‌گذاری تصاویر فلیکر بالغ بر ۲۵۰ میلیون تصویر را در خود جای دهد.
از این رو، می‌توان گفت که ما در میان حجم عظیمی از داده و اطلاعات قرار گرفته‌ایم که بدون راهنمایی و ناوبری درست ممکن است انتخاب‌هایی غلط و یا غیر بهینه از میان آن‌ها داشته باشیم.
سیستم‌های توصیه‌گر سیستم‌های تأثیرگذار در راهنمایی و هدایت کاربر، در میان حجم عظیمی از انتخاب‌های ممکن، برای رسیدن به گزینه مفید و مورد علاقه وی هستند به گونه‌ای که این فرایند، برای نفس همان کاربر، شخصی‌سازی شده باشد.
تعاریف متفاوتی برای سیستم‌های توصیه‌گر ارائه شده‌است. از آن جمله، تعریف کلی‌نگر و خلاصه آقای Ting-peng liang در سال ۲۰۰۷ است که RS را زیرمجموعه‌ای از DSSها می‌داند و آن‌ها را سیستم‌های اطلاعاتی تعریف می‌کند که، توانایی تحلیل رفتارهای گذشته و ارائه توصیه‌هایی برای مسائل جاری را دارا هستند. به زبان ساده‌تر در سیستم‌های توصیه‌گر تلاش بر این است تا با حدس زدن شیوه تفکر کاربر (به کمک اطلاعاتی که از نحوه رفتار وی یا کاربران مشابه وی و نظرات آن‌ها داریم) به وی مناسب‌ترین و نزدیک‌ترین کالا به سلیقه او را شناسایی و پیشنهاد کنیم.
این سیستم‌ها در حقیقت همان فرایندی که ما در زندگی روزمره خود به کار می‌بریم و طی آن تلاش می‌کنیم تا افرادی با سلایق نزدیک به خود را پیدا کرده و از آنها در مورد انتخاب‌هایمان نظر بخواهیم. توصیه‌هایی که از سوی سیستم‌های توصیه‌گر ارائه می‌شوند به طور کلی می‌توانند دو نتیجه در برداشته باشند :

  • کاربر را در اخذ تصمیمی یاری می‌کنند (که مثلاً از میان چندین گزینه پیش رو کدام بهتر است و آن را انتخاب کند و ... ).
  • موجب افزایش آگاهی کاربر، در زمینه مورد علاقه وی می‌شود (مثلاً در حین ارائه توصیه به کاربر موجب می‌شود تا وی با اقلام و اشیاء جدیدی را قبلاً آنها را نمی‌شناخته، آشنا شود).
سیستم‌های توصیه‌گر برای هر دو طرف یک تعامل (تجاری یا غیرتجاری)، مفید هستند و مزایایی را فراهم می‌آورد. برای نمونه در یک تعامل تجاری، مشتری‌ها از این جهت که عمل جستجو در میان حجم زیاد اطلاعات برای آن‌ها تسهیل و تسریع می‌شود، استفاده از سیستم‌های توصیه‌گر را مفید می‌دانند؛ فروشندگان به کمک این سیستم‌ها می‌توانند رضایت مشتریان را بالا برده و نیز فروش خود را افزایش دهد.

کارهای مرتبط

سیستم‌های توصیه‌گر کاربردهای فراوانی دارند که برخی از زمینه‌های کاربردی آن به شرح زیر است:

  • تجارت الکترونیک : برای توصیه محصولات و خدمات مختلف.
  • اینترانت‌های بنگاهی : برای پیدا کردن افراد خبره در یک زمینه خاص و یا افرادی که در رویارویی با شرایط مشابه، تجاربی کسب کرده و راه حل‌هایی یافته‌اند(بیشتر داخل یک سازمان کاربرد دارد).
  • کتابخانه دیجیتال: پیدا کردن کتاب، مقاله و ...
  • کاربردهای پزشکی: انتخاب پزشک متناسب با شرایط (مکان، نوع بیماری، زمان و ...) بیمار، انتخاب دارو و ...
  • مدیریت ارتباط با مشتری CRM : برای ارائه راهکارهایی برای حل مشکلات تولیدکننده و مصرف‌کننده در زنجیره تأمین.

می‏توان گفت که پیدایش اصطلاح "سیستم‏های توصیه ‏گر" تقریبا به اواسط دهه 1990 برمی گردد. در آن زمان، محققان بر روی ساختار‏های نرخ‏گذاری، متمرکز شده بودند. از اواسط دهه 90 تا کنون تعداد زیادی سیستم توصیه‏ گر برای کمک به کاربران در رسیدن به اطلاعات مورد علاقه شان پیاده سازی شده اند. سیستم GCBR و سیستم GroupLens، توصیه‏ گر مقالات و اخبار یوزنت وBellcore Video Recommender سیستم پیشنهاد فیلم نیز در ادامه طراحی و پیاده سازی شدند.
سیستم پیشنهاد آهنگ که با استفاده از تعاملات کاربر درون شبکه‏های اجتماعی و دیگر داده ‏های انتشار یافته درون حوزه داده‏های پیوندی باز، همچنین با بهره گیری از تکنولوژی وب معنایی، استخراج سه‏تایی‏های RDF از وب سایت‏های آهنگ و پرس‏وجوی معنایی روی آنها، پیشنهادات خود را ارائه می‏دهد، نیز یکی از این سیستم‏ها می‏باشد.
شیوه پیشنهاد دهی جدید گفته شده در ترجیحات دیگر کاربران در سیستم اشتراکی چندرسانه‏ای را بر اساس دانش کشف شده در شبکه اجتماعی چند بعدی(MSN)، فراهم می‏کند. این سیستم، فعالیت‏های کاربران را در لایه های جداگانه‏ی MSN در نظر می‏گیرد. این روند و وزن-دهی شخصی‏ به هر لایه، توصیه‏ها را شخصی می‏کند. علاوه بر این سیستم‏های عملیاتی، تحقیقاتی نیز در زمینه ی ترکیب سیستم‏های توصیه‏گر و ساخت کاراترین سیستم ممکن توسط
Bruke[1][2] ,Balabanovi [3] , Nquyen[4] انجام شده است.
برخی کارها به دسته ‏بندی برچسب‏ های کاربران در شبکه‏های اجتماعی پرداخته‏اند. سیستم توصیه‏گر اجتماعی معرفی شده در به تقسیم برچسب‏ها به چهار دسته می‏پردازد. این سیستم ابتدا فرض می‏کند که مفهوم برچسب، در پایگاه‏های دانشی مثل Yago موجود است و سپس آن را به معنی مرتبط نگاشت می‏کند.
اگر مفهوم برچسب در هیچ پایگاهی موجود نبود، با استفاده از تکنیک‏های پردازش زبان، جداکردن برچسب‏ها و سپس تشخیص نقش برچسب مانند اسم و فعل و غیره، آن را به یک واحد معنایی‏‏ موجود در پایگاه دانش نگاشت و سپس دسته ی معادل آن واحد را بدست می‏آورد.
سیستم های توصیه گر به عنوان نمونه ای از سیستم های پشتیبانی تصمیم یا تصمیم یار شناخته می شوند که در دهه ی 90 میلادی به عنوان یک شاخه ی مستقل پا به عرصه ی تحقیق و پژوهش گشودند. از این سیستم ها به عنوان یکی از راه حل های رویارویی با مساله ی سربار اطلاعات در وب یاد می شود. اگر چه دامنه ی کاربرد استفاده از سیستم های توصیه گر بسیار گسترده می باشد ولی کاربرد آن در زمینه تجارت الکترونیک بیشتر به چشم می آید.
از یک سو کسب و کارهای فعال در زمینه ی تجارت الکترونیک برای جذب مشتری بیشتر در بازار پر رقابت مذکور نیازمند این سیستم ها هستند و از سوی دیگر مشتری نیازمند یاری رسانی در خیل عظیم و رو به رشد کالا و به همان نسبت اطلاعات مربوط به آنها است تا بتواند از میان تعداد گزینه های پیش رو مناسب ترین آنها را برگزیند. [5]
سیستم های توصیه گر عمده ترین فناوری بازیابی شخصی سازی شده ی اطلاعات هستند که غالبا به دو شکل عمل می کنند [6]:
(1) پیش بینی اینکه آیا یک کالای خاص مورد علاقه یک کاربر (مشتری) خاص هست یا خیر؟
(2) پیش بینی دسته ای کالا که احتمالا مورد پسند یک کابر قرار خواهد گرفت. به این ترتیب سیستم های توصیه گر از یک سو موجب جلب رضایت مشتری و از سوی دیگر افزایش فروش خواهند شد. [7]

تکنیک‏های بکار رفته از پردازش زبان طبیعی


برای بهبود معیار بازیابی (Recall) و درستی (Precision) سیستم، باید کلمات کلیدی متعلق به یک ریشه ی زبانی تشخیص داده شوند و یا به عبارت دیگر، ریشه‏ یابی یا ریخت‏شناسی شوند.
ریخت‏شناسی بخشی از علم پردازش زبان طبیعی است که به بررسی ساختار کلمات و ریشه‏یابی واژگان می‏پردازد. به عمل بیرون آوردن ریشه اصلی یک واژه، ریشه ‏یابی (stemming) گویند.
ریشه ‏یابی باعث بهبود چشمگیر پیشنهادات سیستم می‏شود. برای مثال، "نتایج" و "نتیجه ‏ها" یک معنی دارند؛ اما با مقایسه مستقیم توسط ماشین، دو کلمه متفاوت تشخیص داده می‏شوند. با ریشه‏یابی، هر دو به کلمه ی یکسان "نتیجه" تبدیل خواهند شد و میزان شباهت اسناد دربرگیرنده خود به یکدیگر را بالا خواهند برد. پس بهتر است با تبدیل هر دو کلمه به ریشه‏شان، آنها را دو کلمه یکسان در نظر گرفت.
در ریشه یابی کلمات کلیدی، از یک ریشه یاب معنایی بهره گرفته شده است. بدین صورت که فرهنگ لغتی شامل تمامی لغات فارسی تهیه گردیده و در ریشه یابی لغات، حذف پسوندها به ترتیبی خاص صورت پذیرفته و صحت نتیجه ی جاری از طریق معنادار بودن کلمه و وجود آن در فرهنگ لغت، مورد بررسی قرار می گیرد. لغاتی مانند جمع های مکسر جزو استثنائات محسوب می گردند؛ بنابراین فرهنگ لغتی نیز حاوی جمع های مکسر تهیه شده و ریشه ی این لغات مستقیماً بیان می گردد.
پس از مرحله ی یافتن ریشه ی هر لغت، مرحله ی نگاشت کلمه کلیدی به یک واحد معنایی در شبکه ی واژگان فردوس‏نت می‏باشد. نحوه‏ی کار به این صورت است که شبکه واژگان، لغات را در گروه‏های هم ‏خانواده قرار می‏دهد.
هر کدام از این گروه‏ها شامل لغاتی است که در یک متن می‏توانند به جای یکدیگر استفاده شوند و بیانگر یک مفهوم خاص هستند که به وسیله مفاهیم معنایی و روابط لغوی به یکدیگر مرتبط می‏شوند که نتیجه این کار شبکه‏ای است متشکل از لغات و مفاهیم که از نظر معنایی با یکدیگر ارتباط دارند. بنابراین می‏توان به جستجو در بین لغات یک شبکه واژگان، هم از نظر املایی و هم از نظر معنایی پرداخت.

سیستم توصیه‏ گر پیشنهادی


در هر سیستم توصیه ‏گری هدف نهایی، تصمیم به توصیه یا عدم توصیه یک آیتم به یک کاربر می‏باشد. سیستم توصیه‏گر پیشنهادی با بررسی تعدادی مقاله ی جدید ورودی، توصیه یا عدم توصیه آنها به کاربر جاری را تصمیم‏گیری می‏کند. به بیان دقیق‏تر این سیستم با بررسی مقالات خوانده شده توسط کاربر و تشخیص دسته ی آنها که مشخص کننده دسته ‏های مورد علاقه کاربر می‏باشد؛ پس از تشخیص دسته ی یک مقاله ی جدید، در مورد پیشنهاد به خواندن این مقاله به کاربر تصمیم می‏گیرد.
یکی از ویژگی‏های اصلی هر مقاله، کلمات کلیدی هستند؛ زیرا آنها موضوع اصلی مقاله را بیان می‏کنند. بنابراین با تشکیل برداری از کلمات کلیدی مقالات و مقایسه ی بردار دو مقاله، می‏توان شباهت موضوعی مقالات را تشخیص داد. برای رسیدن به دقت بالاتر بایستی حوزه معنایی کلمات کلیدی مقاله مشخص شوند. بدون این کار دو کلمه کلیدی هم‏خانواده ظاهراً متفاوت، مانند "سیستم پیشنهادکننده" و "سیستم توصیه ‏گر"، غیرمتشابه می‏باشند.
برای تشخیص حوزه معنایی یک کلمه باید آن را به واحد معنایی مربوطه‏اش نگاشت داد. برای تحقق این امر، استفاده از ریشه کلمه به جای خود آن، نتایج بسیار مناسب‏تری را به ‏همراه خواهد داشت. در سیستم توصیه‏گر پیشنهادی با گرفتن کلمات کلیدی هر مقاله و ریشه‏یابی آنها و سپس نگاشت به واحد معنایی موجود در شبکه واژگان فردوس‏نت، در واقع دسته یک مقاله به طور معنایی مشخص می‏شود. با انجام عملیات گفته شده در فوق، مثلاً دو مقاله "سطوح دسترسی در شبکه‏های Ad-Hoc" و "امنیت در شبکه‏های بی‏سیم" (به ‏درستی) در یک دسته قرار خواهند گرفت. اما با بررسی صرفاً خود کلمات کلیدی بصورت خام، تشابه بسیار کمتری برای آنها درنظر گرفته خواهد شد که در نتیجه ی آن، به کاربری که یکی را خوانده، دومی از طرف سیستم (به غلط) توصیه نخواهد شد.
عملکرد سیستم توصیه‏گر پیشنهادی متشکل از دو قسمت است: یادگیری و تست. در بخش یادگیری، تعدادی مقاله به عنوان ورودی به سیستم داده شده و حوزه معنایی و تمام کلمات هم‏خانواده کلمات کلیدی آنها، با ثبت دسته‏ی مقاله، درون پایگاه داده ذخیره می‏شوند.
در بخش تست نیز ورودی، مقاله ی جدیدی است که سیستم می‏خواهد روی توصیه‏کردن یا نکردن آن به کاربر، تصمیم بگیرد. در این بخش، کلمات کلیدی مقاله ی جاری پس از طی مراحل پردازش زبانی و معنایی گفته شده در بخش یادگیری، با کلمات و عبارات هر دسته که در پایگاه داده ذخیره شده‏اند، مقایسه می‏شوند. در این مقایسه، زاویه بین برداری از کلمات کلیدی مقاله جدید با بردار کلمات کلیدی دسته ی موجود در پایگاه داده، با استفاده از شباهت کسینوسی محاسبه می‏شود. با توجه به این نوع شباهت معنایی، هر چه کسینوس زاویه ی بین دو بردار کمتر باشد، آن دو بردار تطابق بیشتری داشته و در نتیجه شباهت بیشتری دارند.
پس از مقایسه فوق به ازای هر دسته، دسته ی با بیشترین مقدار شباهت به مقاله ی جدید، به عنوان حوزه ی موضوعی آن، تشخیص داده می‏شود.
پس اگر دسته ی تشخیص داده شده، جزو دسته‏های مورد علاقه کاربر بود (یعنی دسته‏ هایی که کاربر سابقه خواندن چندین مقاله ی آنها را دارد)، این مقاله به او برای خواندن پیشنهاد می‏شود.

ارزیابی سیستم


در سیستم پیشنهادی، تکنولوژی‏های وب معنایی، مانند داده‏های پیوندی، برای حل مشکل "شروع آهسته" و یا به‏طورکلی "پراکندگی داده" به ‏کار می‏روند.
بنابراین مجموعه داده‏ای که پراکندگی بسیاری را در ماتریس نرخ‏گذاری کاربر-آیتم خود داشته باشد، محک خوبی برای ارزیابی این نوع سیستم خواهد بود. از طرف دیگر به دلیل موجود نبودن مجموعه داده‏ای مناسب به زبان فارسی، جهت ارزیابی سیستم‏های توصیه‏گر همراه با داده‏ها و ارتباطات بین کاربری در شبکه‏ای اجتماعی، تصمیم به مونتاژ کردن سیستم پیشنهادی به زبان انگلیسی و ارزیابی آن در بستری به این زبان گرفته شد. به همین دلیل، مجموعه داده Epinions انتخاب شده است.
این مجموعه توسط Paolo Massa در یک خزش تولید شده است و شامل حدود 132هزار کاربر با تعداد 13,668,319 نرخ روی حدود 1,560,144 مقاله/کتاب می‏باشد. بنابراین پراکندگی داده در جدول نرخ‏های کاربر-آیتم طبق فرمول (2) حدود 0.99993 می‏باشد و چون این عدد نزدیک به یک است، پراکندگی این مجموعه داده، بسیار زیاد می‏باشد.
در فرمول فوق نماد R بیانگر مجموعه نرخ‏ها، I مجموعه آیتم‏ها و U مجموعه کاربران می‏باشد. نماد || نیز اندازه مجموعه را بیان می‏کند. به‏عنوان نمونه |R| یعنی تعداد نرخ‏ها.
علاوه بر پراکندگی بسیار داده در این مجموعه، دلیل دیگر انتخاب آن برای ارزیابی، موجود بودن ارتباط بین کاربران می‏باشد. همان‏طور که قبلا نیز توضیح داده شد، در سیستم پیشنهادی از روی روابط بین کاربران و شباهت سلایق آنها به یکدیگر، اقدام به تکمیل پروفایل‏ها می‏شود که با این‏کار حوزه‏های بیشتر مورد علاقه کاربران تشخیص داده می‏شوند.
این روابط بین کاربری در یک شبکه اجتماعی و توسط خود کاربران ایجاد شده است. به دلیل موجود بودن ارتباطات بین کاربران، مجموعه Epinions یک شبکه اجتماعی نیز می‏باشد و با استفاده از آن می‏توان تاثیر تکمیل پروفایل کاربران را از روی کاربران مشابه مرتبط با آنها در افزایش صحت پیشنهادات سیستم مشاهده کرد.
کاربران در این شبکه اجتماعی با بازدید نرخ‏ها و توضیحات دیگر کاربران روی آیتم‏هایی که خودشان قبلاً بازبینی کرده‏اند، اقدام به برقراری ارتباط اعتماد از خود به کاربران مشابه خود می‏کنند. به عنوان نمونه فرض کنید که کاربر A پس از خواندن کتابی به آن نرخ 5 (بالاترین میزان علاقه) را می‏دهد. این کاربر وقتی با مشاهده نظرات و نرخ کاربر B متوجه می‏شود که او نیز به همان کتاب یا چندین کتاب مشابه دیگر ابراز علاقه بالا کرده‏ است، به آن کاربر اعتماد کرده و سعی می‏کند سایر کتبی که کاربر B به آنها علاقه دارد را نیز بخواند.
در واقع کاربر A کاربر B را در نظرات و علاقه‏ها و روحیات شبیه خودش تشخیص می‏دهد. بنابراین از اعتماد کاربر A به کاربر B می‏توان در جهت تکمیل پروفایل A و تشخیص بیشتر علاقه‏های وی استفاده کرد.
در این مجموعه، 841,372 ارتباط بین کاربری (717,667 اعتماد و 123,705 عدم اعتماد) وجود دارد که حدود 85 هزار کاربر این اعتماد/عدم ‏اعتماد را دریافت کرده‏اند؛ که به ازای هر یک می‏توان به تکمیل خودکار پروفایل وی از روی علاقه‏های کاربران مورد اعتماد او اقدام کرد و در نتیجه، کتابهایی را (بدرستی) به وی توصیه کرد که مشابه کتب خوانده شده او نباشند اما مورد علاقه ی کاربران مورد اعتماد وی باشند. پس می‏توان گفت که با استفاده از تکنولوژی شبکه‏های اجتماعی و ارتباط بین کاربران، میزان معیار Recall بالاتر خواهد رفت و سیستم توصیه‏گر دقیق‏تری را خواهیم داشت.
در زیر معیارهایی برای ارزیابی "صحت پیش‏بینی‏ها"ی سیستم در مورد آیتم‏های مورد علاقه کاربران و "صحت دسته‏بندی" آیتم‏ها (به دو دسته آیتم‏های مورد توصیه و عدم توصیه به کاربر) توسط سیستم، بیان خواهند شد.

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

سامانه‌های توصیه‌گر به طور کلی به سه دسته تقسیم می‌شوند؛ در رایج‌ترین تقسیم‌بندی، آنها را به سه گروه ۱.محتوا محور ۲.دانش محور و ۳.صافی سازی تجمعی، تقسیم می‌کنند، که البته گونه چهارمی تحت عنوان Hybrid RS هم برای آنها قائل می‌شوند.

یک رویکرد به سیستم‌های توصیه‌گر، استفاده از الگوریتم‌های CF یا صافی سازی تجمعی است. در این رویکرد به جای استفاده از محتوای (Content) اقلام، از نظرات و رتبه‌بندی‌های انجام شده توسط کاربران برای ارائه پیشنهاد، استفاده می‌شود.

در روش محتوا محور، اقلام پیشنهادی، به این دلیل که با اقلامی که کاربر فعال (کاربری که قرار است به او توصیه کنیم) نسبت به آنها ابراز علاقه کرده‌است شباهت‌هایی دارند، به کاربر توصیه می‌شوند ولی در CF، لیست اقلام پیشنهادی، بر اساس این اصل که، کاربرانی، مشابه کاربر فعال، از آنها رضایت داشته‌اند تهیه می‌شود. از این رو واضح است که در روش محتوامحور، تمرکز بر روی یافتن شباهت بین اقلام بوده، در حالی که در CF، تمرکز روی یافتن شباهت بین کاربران است؛ بدین ترتیب که پیشنهادات در CF، بر اساس تشابه رفتاری کاربرفعال با کاربران دیگر صورت می‌گیرد و نه بر اساس تشابه ویژگی کالاهای پیشنهادی با ویژگی‌های کالاهای مورد علاقه وی (کاربر فعال).

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

گونه چهارم سیستم‌های ترکیبی هستند. طراحان این نوع سیستم‌ها دو یا چند گونه از انواع سه‌گانه مذکور را غالباً به دو منظور با هم ترکیب می‌کنند؛ ۱- افزایش عملکرد سیستم ۲- کاهش اثر نقاط ضعفی که آن سیستم‌ها وقتی به تنهایی به کار گرفته شوند، دارند. از میان سه روش موجود (CF و CB و KB)، غالباً روش CF یک پای ثابت این ترکیبات است.

۲. آزمایش‌ها

برای به دست آوردن یک سیستم توصیه گر راه های مختلفی وجود دارد که یکی از این روشها استفاده از روش clustering است.
به این صورت که تمام instance های موجود در دیتا ست دسته بندی میشوند و در صورت ایجاد شدن instance جدید با ارائه دسته ای که آن instance در آن جای میگیرد به مخاطب یک سری موارد جدید نشان داده ایم که تا حد زیادی به درخواست او نزدیک است.
ساده ترین راه یادگیری plain memorization یا حفظ کردن ساده میباشد. به این صورت که فقط تمام instance ها را ذخیره میکنیم و instance های جدید را با مقایسه کردن با موارد موجود کلاس بندی میکنیم.
البته در واقع تمام روش های learning هم به همین صورت عمل میکنند.
و اما روش انتخابی ما استفاده از روش instance based learning است .
در این روش هر instance جدید با instance های موجود با استفاده از یک تابع فاصله مقایسه شده و از نزدیک ترین instance موجود برای اضافه کردن به کلاس مورد نظر استفاده میشود.
در این روش مثال های یادگیری به صورت کاملا دقیق و یکسان در دیتابیس ذخیره شده و تابع فاصله مشخص میکند که کدام instance به کدام کلاس تعلق دارد.
تنها مشکلی که باقی میماند مشخص کردن یک تابع فاصله است.
اگرچه امکانات دیگری هم وجود دارد اما بیشتر instance based learners ها از تابع فاصله ی اقلیدسی استفاده میکنند.

{\sqrt{(a1.1-a1.2)^2+(a2.1-a2.2)^2+...+(ak.1-ak.2)^2}}

به صورت که k در اینجا تعداد attribute ها و a مقدار attribute در هر distance میباشد.
هر چه قدر مقدار توان را از 2 افزایش دهیم میزان تاثیر اختلاف زیاد بین instance ها را افزایش داده ایم.

A kD-Tree

در آزمایش انجام شده در این پروژه ( کد برنامه در لینک گیت هاب بالای صفحه وجود دارد) یک دیتاست از رتبه ی 5 سایت ارزیابی فیلم به 13000 مثال train شده است. [10]
که رتبه ی 3 سایت از 5 سایت از 100 بوده و امتیاز یک سایت از 5 و سایت دیگر از 10 میباشد.
به اینصورت که کاربر نظر خود را بین اعداد 0 تا 100 بیان میکند و سیستم سعی میکند نزدیک ترین فیلم به نظر کاربر را در میان دیتاست به او معرفی کند.
بعد از انجام چندین آزمایش توسط زبان پایتون میانگین زمان طول کشیده برای بدست آوردن جواب بهینه 13.76 ثانیه میباشد.

اگر چه instance based learning ساده و موثر است اما مقایسه کردن هر instance با instance های موجود کاری بسیار سخت و کند است.
و مرتبه ی زمانی آن از مرتبه ی تعداد instance های dataset است.

به همین منظور ما از روش بهینه تر Kd-Tree که روش بهینه تر برای instance based learning است استفاده خواهیم کرد.
که یک درخت باینری است که فضای ورودی را تقسیم میکند و این کار را تا جایی که هر instance در یک بخش قرار گیرد , به صورت بازگشتی ادامه میدهد.
همه ی برش ها به صورت موازی با محورهای نمودار k-dimensional است که در اینجا k نشان دهنده ی تعداد attribute های ما میباشد.
به طور مثال در تصویر زیر نقاط (7,4) , (2,2) , (6,7) , (3,8) در یک فضای حالت 2 بعدی ( 2 اتریبیوت ) ترسیم شده اند.

A kD-Tree

بعد از تقسیم کردن فضای حالت درخت تصمیم ما به صورت شکل زیر تولید میشود.

A kD-Tree

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

بعد از انجام تقسیم بندی هر ناحیه فقط شامل یک نقطه میشود به این صورت که هر نقطه از training set مطابق با شکل زیر به یک نود از درخت مرتبط میشود.

A kD-Tree

  • نقطه ی هدف در این شکل به صورت ستاره نمایش داده شده است.
  • برگی از درخت که شامل نود تارگت است به صورت سیاه نمایش داده شده است که البته به صورت لزوم نزدیک ترین نقطه به نقطه ی هدف نیست ولی به هر حال یک تقریب بسیار خوب است.
  • در هر صورت اگر قرار باشد نقطه ای نزدیک تر به هدف وجود داشته باشد باید در داخل دایره ی نقطه چین قرار داشته باشد.

برای اینکه متوجه شد که آیا نقطه ی بهتری وجود دارد یا نه باید نود sibling یا همسایه نود هدف هم بررسی شود.
نود سیبلینگ نود سیاه به صورت سایه دار نمایش داده شده است که چون دایره تماسی با آن ندارد شامل نقطه ی نزدیک تر نمیباشد , پس دوباره به نود پدر مراجعه میشود و سیبلینگ این نود هم مقایسه میشود.

امتیازات


این الگوریتم به مراتب سریع تر از الگوریتم nearest neighbour مطرح شده است.
با توجه به عمق درخت این الگورتم در اوردر لوگاریتم از تعداد train ها جواب بهینه را به ما میدهد.
مزیت دیگر این الگوریتم این است که example های جدید به راحتی و در هر زمانی میتوانند به درخت حالت اضافه شوند.
نتیجه ی زمانی به دست آمده از این الگوریتم روی همان دیتاست مطرح شده در بالا به میزان متوسط 9.03 ثانیه کاهش پیدا کرد.

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

۳. کارهای آینده

۴. مراجع

[1]Burke, R. The Wasabi Personal Shopper: A Case-Based Recommender System. In Proceedings of the 11th National Conference on Innovative Applications of Artificial Intelligence, pages 844-849. AAAI, 1999.
[2] Burke, R. Knowledge-based Recommender Systems. To appear in the Encyclopedia of Library and Information Science.
[3] Marko Balabanovic , Yoav Shoham .Content-based, collaborative recommendation (1997)
[4]Olga Averjanova, Francesco Ricci, Quang Nhat Nguyen , The Second International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies Map-based Interaction with a Conversational Mobile Recommender System , Discovery Science, 2007.
[5] Felfering A., Friedrich G., and Schmidt-Thieme L., "Recommender systems," IEEE Intelligent systems, vol. 22, pp. 18-21, 2007.
[6] Cornelis C., Lu J., Guo X., and Zhang G., "One-and-only item recommendation with fuzzy logic techniques," Information sciences, vol. doi:10.1016/j.ins.2007.07.001, 2007.
[7] Li Y., Lu L., and Xuefeng L., "A hybrid collaborative filtering method for multiple-interests and multiplecontent recommendation in E-Commerce," Expert systems with applications, vol. 28, pp. 67-77, 2005.
[8] B. Mobasher, H. Dai, T. Luo, M. Nakagawa, "Effective personalization based on association rule discovery from web usage data", Proceedings of the 3rd ACM Workshop on Web Information and Data Management, 2001 .
[9] B. Mobasher, R. Cooley, J. Srivastava, "Automatic Personalization Based on Web Usage Mining", Communications of the ACM, Vol. 43, No. 8, 2000 .
[10] دیتا ست بررسی شده
Machine Learning Course - Recommender Systems
Data Mining: Practical Machine Learning Tools and Techniques داده های ارزیابی نمونه

علیرضا نوریان
  • در نوشته شما هیچ ارزیابی کمی یا کیفی از نحوه عملکرد سیستم ارائه نشده است و فقط شما به زمان اجرا پیاده‌سازی با KNN و Kd-tree اشاره کرده‌اید. ما انتظار داشتیم که شما نشان دهید که چقدر دقت دارید و چقدر مثلا فیلم‌هایی که به مخاطب پیشنهاد می‌کنید، مورد اقبال او خواهد بود. در واقع شما از آموزش صحبت کرده‌اید اما از آزمون نه.

  • به نظر می‌رسد که شما Kd-tree را از اول پیاده‌سازی کرده‌اید. این کار اشکالی ندارد، ولی اگر از کتابخانه‌های موجود هم استفاده می‌کردید اصلا بد نبود. در آن صورت، می‌توانستید همین زمان را صرف بهبود نتایج یا پیاده‌سازی روش‌های مختلف کنید.

رد شده

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