پیشنهاد دادن آنچه مخاطب از آن استقبال خواهد کرد، برعهده سامانه‌های توصیه‌گر است. این سامانه‌ها که امروز ما کاربر بسیاری از آنها هستیم، سعی میکنند از روی علاقه‌مندی‌های ما و دیگران، مثلا اینکه ما چه کتابهایی را خوانده‌ایم و دیگران که علایقی مشابه ما داشته‌اند، مثلا چه کتابهایی را خوانده‌اند، پیشنهاد مناسبی به ما بدهند.
مقدمه
سامانه توصیه‌گر (به انگلیسی: 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 ها را افزایش داده ایم.  در آزمایش انجام شده در این پروژه ( کد برنامه در لینک گیت هاب بالای صفحه وجود دارد) یک دیتاست از رتبه ی 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 اتریبیوت ) ترسیم شده اند.  بعد از تقسیم کردن فضای حالت درخت تصمیم ما به صورت شکل زیر تولید میشود.  یک روش مناسب برای اتخاب یک محور برای برش محاسبه ی واریانس نقاط دیتا در طول هر محور میباشد. و یک روش خوب برای پیدا کردن نقطه ی برش پیدا کردن میانه نقاط روی آن محور است. برای جلو گیری از ایجاد اشکال لاغر و دراز بهترین راه این است که تقسیم ها در محورهای مختلف انجام گیرد. بعد از انجام تقسیم بندی هر ناحیه فقط شامل یک نقطه میشود به این صورت که هر نقطه از Training Set مطابق با شکل زیر به یک نود از درخت مرتبط میشود. - نقطه ی هدف در این شکل به صورت ستاره نمایش داده شده است.
- برگی از درخت که شامل نود تارگت است به صورت سیاه نمایش داده شده است که البته به صورت لزوم نزدیک ترین نقطه به نقطه ی هدف نیست ولی به هر حال یک تقریب بسیار خوب است.
- در هر صورت اگر قرار باشد نقطه ای نزدیک تر به هدف وجود داشته باشد باید در داخل دایره ی نقطه چین قرار داشته باشد.
امتیازات
این الگوریتم به مراتب سریع تر از الگوریتم Nearest Neighbour مطرح شده است. با توجه به عمق درخت این الگورتم در اوردر لوگاریتم از تعداد Train ها جواب بهینه را به ما میدهد. مزیت دیگر این الگوریتم این است که Example های جدید به راحتی و در هر زمانی میتوانند به درخت حالت اضافه شوند. نتیجه ی زمانی به دست آمده از این الگوریتم روی همان دیتاست مطرح شده در بالا به میزان متوسط 9.03 ثانیه کاهش پیدا کرد. برای این الگوریتم هم بازهم روش های بهینه سازی زیادی وجود دارد که در قسمت بهینه سازی به آن اشاره خواهد شد.بهینه سازی
همانطور که مشاهده کردیم , درخت های Kd ساختمان های داده های بسیار خوبی برای پیدا کردن نزدیک ترین همسایه به صورت بهینه هستند. اما این الگوریتم مطلق کامل نیست . دیتا ست های ناموزون (skewed datasets) یک تناقض کامل را بین تمایل به بالانس بودن درخت و ایجاد شدن ناحیه های مربعی ایجاد میکنند . در واقع ما همیشه به دنبال این هستیم که ناحیه تقسیم بندی شده ی دیتاست کاملا موزون بوده و اشکال به مربع نزدیکتر باشند در این صورت است که میتوان گفت Instance ها به صورت همگن پخش شده اند. مهم تر از آن مستطیل ها - حتی مربع ها - به خاطر گوشه هایشان بهترین اشکالی نیستند که میتوان استفاده کرد . اگر دایره ی هاشور زده شده در شکل بالا کمی بزرگتر بود ممکن بود با گوشه ی راست و پایین مستطیل واقع در قسمت چپ و بالای شکل تداخل داشته باشد , که البته این امکان وجود داشت اگر Instance سیاه کمی از نقطه ی هدف دورتر بود , در این صورت باید آن مستطیل هم برای امکان وجود داشتن نزدیکترین همسایه مورد جستجو قرار میگرفت . راه حل این است که به جای استفاده از Hyperrectangle ( ابر مکعب مستطیل ) از Hyperspheres ( ابر کره ) استفاده شود. کره های همسایه ممکن است با هم اشتراک داشته باشند , ولی این مساله مشکلی به وجود نمی آورد به این دلیل که الگوریتم Nearest Neighbor برای درخت های kD-Trees به منطقه های گسسته وابسته نیستند . یک Data Structure به نام ball tree کره ( ball ) های k بعدی را تعریف میکند که دیتا های Train شده را پوشش میدهند و در نهایت آنها را در درخت مورد نظر قرار میدهد. تصویر زیر نشان دهنده ی 16 Training Instance در یک فضای دو بعدی است که به وسیله ی یک Pattern از دایره های دارای اشتراک پوشش داده شده .  و تصویر زیر نشان دهنده ی درخت تولید شده توسط این دایره ها است . - دایره ها در لایه های مختلف از درخت توسط اشکال مختلف هاشور مشخص شده اند .
- دایره های کوچکتر توسط سایه ی خاکستری نمایان شده اند .
- هر نودی از درخت نمایانگر یک ball (دایره) است .
- نود ها به صورت انجمنی رنگ زده شده اند تا کار تشخیص لایه نود ها آسان شود
نتایج
همانطور که پیش تر گفته شد هر دو الگوریتم kNN , kD-Tree الگوریتم های کامل هستند و همواره بهترین نتیجه را به ما برمیگردانند. در نتیجه نمیتوان میزان دقت این الگوریتم های مطرح شده را سنجید زیرا هر دو در حالت بهینه شده یک جواب را به ما میدهند. در تنها حالت موجود میتوان میزان رضایت مخاطب را در نظر گرفت در حالی که این کار نیز در مجال پروژه ما نیست زیرا به طور مثال برای دیتا ست بررسی شده در بالا محاسبه کردن میزان رضایت مخاطب نیاز مند یک پایگاه داده بسیار بزرگ از فیلم ها و یک سایت ارزیابی فیلم است که تعداد بالایی از کاربرها بتوانند در آن سایت ثبت نام کرده و بعد از وارد کردن نظر خود درخواست مشاهده Recommendation کنند و بعد نظر خود را در مورد موارد پیشنهاد شده داده تا بتوان دقت الگوریتم ها را سنجید . به هر حال ما در این قسمت میزان زمان اجرا و جواب نهایی و فاصله ی این جواب تا Instance ورودی را در الگوریتم های بررسی و پیاده سازی شده در نظر میگیریم. 3 الگوریتم بررسی شده عبارتند از :- k-nearest neighbor
- kD-tree اولیه
- kD-tree بهینه شده
نتایج الگوریتم k-nearest neighbor
| Instance ورودی | خروجی | جواب بهینه | فاصله تا جواب بهینه | زمان الگوریتم | درصد خطا |
|---|---|---|---|---|---|
| [45,45,45,45,45] | [46, 47, 40, 46, 40] | [46, 47, 40, 46, 40] | 0 | ثانیه 1.22 | 0% |
| [72,72,72,72,72] | [68, 72, 80, 75, 70] | [68, 72, 80, 75, 70] | 0 | ثانیه 1.22 | 0% |
| [67,67,67,67,67] | [67, 71, 60, 71, 70] | [67, 71, 60, 71, 70] | 0 | ثانیه 1.18 | 0% |
| [13,13,13,13,13] | [10, 13, 20, 13, 10] | [10, 13, 20, 13, 10] | 0 | ثانیه 1.23 | 0% |
| [23,23,23,23,23] | [28, 23, 20, 23, 20] | [28, 23, 20, 23, 20] | 0 | ثانیه 1.17 | 0% |
توجه شود که الگوریتم فقط از کاربر درخواست یک عدد میکند که نشان دهنده ی نظر کاربر به فیلم مورد نظر از 1 تا 100 است و خود الگوریتم Instance نمونه را به صورت لیست 5 تایی از عدد وارد شده میسازد.
نتایج الگوریتم kD-tree اولیه
| Instance ورودی | خروجی | جواب بهینه | فاصله تا جواب بهینه | زمان الگوریتم | درصد خطا |
|---|---|---|---|---|---|
| [45,45,45,45,45] | [44, 35, 60, 35, 50] | [46, 47, 40, 46, 40] | 27.730 | ثانیه 0.98 | 0.011% |
| [72,72,72,72,72] | [72, 82, 40, 62, 80] | [68, 72, 80, 75, 70] | 44.553 | ثانیه 1.03 | 0.039% |
| [67,67,67,67,67] | [67, 74, 80, 64, 70] | [67, 71, 60, 71, 70] | 21.400 | ثانیه 0.95 | 0.023% |
| [13,13,13,13,13] | [14, 21, 0, 7, 20] | [10, 13, 20, 13, 10] | 24.819 | ثانیه 0.83 | 0.013% |
| [23,23,23,23,23] | [24, 29, 40, 18, 30] | [28, 23, 20, 23, 20] | 24.020 | ثانیه 0.74 | 0.105% |
نتایج الگوریتم kD-tree بهینه شده
| Instance ورودی | خروجی | جواب بهینه | فاصله تا جواب بهینه | زمان الگوریتم | درصد خطا |
|---|---|---|---|---|---|
| [45,45,45,45,45] | [46, 47, 40, 46, 40] | [46, 47, 40, 46, 40] | 0 | ثانیه 1.01 | 0% |
| [72,72,72,72,72] | [68, 72, 80, 75, 70] | [68, 72, 80, 75, 70] | 0 | ثانیه 1.07 | 0% |
| [67,67,67,67,67] | [67, 71, 60, 71, 70] | [67, 71, 60, 71, 70] | 0 | ثانیه 1 | 0% |
| [13,13,13,13,13] | [10, 13, 20, 13, 10] | [10, 13, 20, 13, 10] | 0 | ثانیه 0.92 | 0% |
| [23,23,23,23,23] | [28, 23, 20, 23, 20] | [28, 23, 20, 23, 20] | 0 | ثانیه 0.87 | 0% |
کارهای آینده
روش های دارای جزییات بیشتر و الگوریتم های دیگری هم برای تقسیم کردن یک ball وجود دارد که دایره های تنگ تر (tighter) را تولید میکنند و در نتیجه دقت الگوریتم را افزایش میدهند ولی این الگوریتم ها نیاز مند محاسبات بیشتر هستند .
که در اینجا مجال صحبت کردن در مورد االگوریتم های پیچیده برای ساختن ball tree ها یا update کردن آنها در حین ورود Instance جدید , نیست .
یکی دیگر از کارهایی که میشود در این مورد انجام داد این است که به جای ذخیره کردن تمام Training Instance ها میتوان آنها را به منطقه هایی فشرده کرد.
و کار ما فقط ذخیره کردن range ای از مقادیر است که برای هر attribute دیده شده اند .
یک روش دیگر ساختن interval (فاصله) برای هر attribute است تا از training set استفاده شود تا تعدادی که هر کلاس برای هر interval در هر attribute اتفاق می افتد را بشمارد . این روش به نام voting feature intervals معروف است.
مراجع
[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
داده های ارزیابی نمونه