بخشی از مقاله
چکیده
این مقاله یک معیار برای اندازهگیری شباهت بین کاربران ارائه میکند که در سیستمهای توصیهگر مبتنی بر پالایش مشارکتی قابل استفاده است. روش پیشنهادی از یک ترکیب خطی ساده از مقادیر و وزنها استفاده میکند . مقادیر برای هر جفت از کاربران که بین آنها شباهت، به دست آمده محاسبه میشود درحالیکه وزنها فقط یکبار محاسبه میشوند از آنجا که روشهای بهینهسازی، رویکردهای قوی و کارآمد برای حل مسائل پیچیده در دنیای واقعی فراهم میکنند
با استفاده از الگوریتم ازدحام ذرات و ژنتیک، وزن بهینه از سیستم توصیهگر استخراج میشود و از آن در محاسبه تابع شباهت استفاده میشود و برای پیشبینی آیتمهای سیستم توصیهگر از الگوریتم نزدیکترین همسایه استفاده میشود، تعیین تعداد همسایهها یک پارامتر مهم است. نتایج نشان میدهد که انتخاب تعداد میانی برای همسایهها جهت تعیین شباهت مناسب میباشد و الگوریتم ژنتیک نسبت به الگوریتم ازدحام ذرات دارای دقت بهتری در توصیه است و زمان اجرای این الگوریتم نیز کوتاهتر میباشد.
-1 مقدمه
درعصر جدید حجم فراوانی از دادهها در اینترنت، مانند فیلم،موسیقی، وب سایتها، فرصتی مناسب در پیش روی کاربران قرار داده است اما روند رو به رشد اطلاعات بر روی اینترنت که "پدیدهی سربار اطلاعات" نامیده میشود فرایند تصمیمگیری و انتخاب دادهها و اطلاعات را برای بسیاری از کاربران دشوار ساخته است برای رفع این مشکل پژوهشگران استفاده از سیستمهای توصیهگر را پیشنهاد نمودند . این سیستمها به گونهای عمل میکنند که با استفاده از جمعآوری مشخصات کاربران، دستهبندی علایق و آمارگیری از علاقهمندیهای آنها به کاربران پیشنهادهایی میدهند که احتمالاً مورد علاقه آنها خواهد بود.
متداولترین الگوریتمیکه در سیستمهای توصیهگر استفاده میشود الگوریتم پالایش مشارکتی است که این الگوریتم به تعیین شباهت بین کاربران میپردازد. انتخاب صحیح یک تابع شباهت برای تعیین شباهت میان کاربران یک فاکتور مهم در الگوریتمهای پالایش مشارکتی است زیرا دقت توصیه را به شدت تحت تأثیر قرار میدهد.
-2 پیشینه تحقیق
در سالهای اخیر معیارهای شباهت متفاوتی در سیستمهای توصیهگر استفاده شده است نظیر ضریب همبستگی پیرسون، این معیار از امتیازات کاربران به طور مستقیم استفاده میکند. اسپیرمن، ترتیب رتبهبندیها را در نظر میگیرد. معیار تفاضل مربعات میانگین، در مقایسه با ضریب همبستگی پیرسون محدود میباشد؛ زیرا همبستگیهای منفی بین ترجیحات کاربر یا درک آیتمهای مختلف را در نظر نمیگیرد؛ در حالی که وجود چنین همبستگیهای منفی ممکن است باعث بهبود دقت پیشبینی رتبه بندی شود. معیار شباهت جاکارد برای استفاده از دیتا ستهایی مناسب میباشد که بسیار پراکنده است، ضریب همبستگی پیرسون به عنوان یک معیار شباهت، بهتراز سایر دیدگاههای سنتی عمل میکند.
یکی از چالشهای الگوریتم پالایش مشارکتی که از معیارهای شباهت سنتی برای محاسبه شباهت بین دو کاربر
استفاده میکند این است که ارزش تمامی امتیازهای کاربران به آیتمها، یکسان فرض میشود در صورتیکه در واقعیت امتیازهای کاربران روی آیتمهای مختلف ارزشهای متفاوت دارد. برای رفع این مشکل میتوان از معیار شباهتی استفاده نمود که وزنی را برای امتیازات کاربران در نظر میگیرد.
-3 معرفی تابع شباهت
انتخاب صحیح یک تابع شباهت، برای تعیین شباهت میان کاربران یک فاکتور مهم در الگوریتمهای پالایش مشارکتی است زیرا دقت توصیه را به شدت تحت تأثیر قرار میدهد. تابع شباهت پیشنهادی برای محاسبه شباهت میان هر دو کاربر در پایگاه داده، به صورت رابطه - 1 - تعریف شده است که با استناد به مقالهی [6] استخراج شده است:
در رابطه - 1 - ،M، بالاترین رتبه و m پایینترین رتبه تعریف شده در سیستم است که کاربر میتواند به هر یک از آیتمها بدهد. Va,u بردار مقادیر برای هر زوج کاربر a,u است و W بردار وزن و هم اندازه با بردار V است که در ادامه روش محاسبه هر دو بردار تشریح میشود.
-1-3 بردار وزن
بر طبق این تابع شباهت به ازای هر بردارV یک بردار W با همان اندازه باید تعریف شود که هر عنصر w - i - ، نشان دهنده اهمیت عنصر - - در محاسبه شباهت میان دو کاربر است.
ویژگی هر عنصر بردار W= - w - 0 - '…'Z - M-m - - که عناصر آن در بازه >-1'1 قرار دارند را میتوان با در نظر گرفتن یک بردار نمونه W = - 1,0.5,0,-0. 5,-1 - به صورت زیر تشریح کرد:
w - 0 - = 1، آیتمهایی که مشابه هم رتبهدهی شدند را در محاسبه شباهت بسیار مثبت ارزیابی میکند.
w - 1 - = 0.5، آیتمهایی را که اختلاف بین رتبههای آنها 1 است را با یک مقدار متوسط مثبت ارزیابی میکند.
w - 2 - = 0، آیتمهایی را که اختلاف رتبهدهی دو کاربر به آنها 2 است را در محاسبه شباهت در نظر نمیگیرد.
w - 3 - = - 0.5، آیتمهایی را که اختلاف رتبه آنها 3 است را با یک مقدار متوسط منفی ارزیابی میکند.
w - 4 - = -1، آیتمهایی که متضاد هم رتبهدهی شدند را در محاسبه شباهت بسیار منفی ارزیابی میکند.
به این ترتیب، میتوانیم به طور منطقی انتظار داشته باشیم که تابع شباهت، یک مقدار مثبت بالای w - 0 - و یک مقدار منفی بالا از w - M-m - داشته باشد.
موضوع اصلی، تعیین مناسبترین بردارW که تابع شباهت بهینه را ارائه میدهد میباشد از میان کلیهی بردارهایW تولید شده برداری انتخاب میشود که تابع هدف یعنی میانگین خطای مطلق - MAE - را کمینه کند؛ بنابراین برای یافتن بهینهترین بردارW که مناسبترین تابع شباهت را ارائه میدهد از الگوریتم تکاملیGAوPSO استفاده میشود.
-4 معرفی الگوریتم GA
به منظور پیدا کردن بردار وزن بهینه و در نهایت یک تابع شباهت مطلوب، simw، از الگوریتم ژنتیک استفاده میشود الگوریتم ژنتیک از قانون گزینش طبیعت برای یافتن جواب بهینه استفاده میکند. طبق این قانون تنها گونههایی از یک جمعیت ادامه نسل می دهند که بهترین خصوصیات را جهت سازگاری با طبیعت داشته باشند.
-1-4 جمعیت اولیه
جمعیت اولیه با استفاده از مقادیر تصادفی بدست میآید.با توجه به اینکه[ ] است طول هر بازه با در نظر گرفتن M=5 و m=1 برابر 0/4 محاسبه شده و محدودههای مناسب برای قرار گرفتن جمعیت اولیه به صورت زیر تعیین میشود:
بهینهترین بردارW، برداری خواهد بود که مناسبترین وزنها را برای هر یک از عناصر بردار V در نظر بگیرد تا با محاسبه دقیقتر میزان شباهت میان کاربران بتواند مقدار خطای میان رتبههای واقعی داده شده توسط کاربران و رتبههای پیشبینی شده توسط سیستم را کاهش داده ؛ در نتیجه دقت و صحت توصیهها را در سیستم توصیهگر افزایش دهد؛ بنابراین برای یافتن بهینهترین بردار W توسط الگوریتم GA باید یک تابع برازش مناسب برای الگوریتم GA تعریف شود.
-2-4 تابع برازش
در این مسئله، تابع برازش میانگین خطای مطلق - - MAE در نظر گرفته میشود زیرا MAE یکی از مهمترین معیارها برای سنجش دقت توصیه است.
الگوریتم GA سعی میکند از میان تمام بردارهای W که در واقع جمعیت اولیه ی الگوریتم را تشکیل میدهندW ای را پیدا کند که منجر به کم ترین میانگین خطای مطلق - - MAE شود. در واقع تابع برازندگی استفاده شده در الگوریتم، تابع MAE است که به صورت معادله - 3 - تعریف میشود:
در معادله - 3 - ، #U و #Iu به ترتیب تعداد کاربران آموزشی و تعداد آیتم های آموزشی رتبه بندی شده به وسیله کاربر u است. و به ترتیب رتبه واقعی کاربر u به آیتم i و رتبه پیشبینی شده توسط سیستم برای آیتم i است.
MAE، میزان خطای رتبه های واقعی کاربران با رتبه های پیش بینی شده سیستم می باشدکه مسلماً هر چه این مقدار کمتر باشد عملکرد سیستم دقیقتر میشود.
الگوریتم GA برای محاسبه MAE، گامهای زیر را برای هر کاربر هدف - - a نیاز دارد:
1. بر اساس تابع شباهت - simw - تعریف شده در معادله - 1 - ، شباهت میان کاربر هدف - a - و سایر کاربران محاسبه میشود؛ در حقیقت مجموعه همسایههای کاربر a، با عنوانk - ka تعداد همسایه شبیهتر به کاربر هدف است - بدست میآیند که با تغییر مقدار k، تعداد k همسایه برای کاربر a، از میان کاربرانی با بالاترین مقدار شباهت، انتخاب میشوند.
2. پیشبینی رتبهبندی کاربر a روی آیتم i، با عنوان است. این پیشبینی از طریق رابطه انحراف از میانگین - DFM - که در رابطه - 4 - با استفاده از رتبهای که همسایگان کاربر a به آیتم i دادهاند بدست میآید.
در معادله - 4 - ، ̅ متوسط رتبه های ایجاد شده توسط کاربر a است،رتبه ای است که کاربر u به آیتم i داده است، شباهت کاربر هدف با همسایه اش میباشد.
-1-2-4 الگوریتم نزدیکترین همسایه
این نوع الگوریتمها در پیش بینی علاقهی یک کاربر به یک آیتم خاص از امتیازهایی که کاربران مشابه او به آن آیتم دادهاند استفاده میکنند.این کاربران مشابه، اصطلاحاً همسایگان کاربر نامیده میشوند. اگر کاربر n، مشابه کاربر u باشد، گفته میشود که n همسایهی u است. برای پیدا کردن همسایهها روشهای متفاوتی وجود دارد یکی از این روشها استفاده از رابطه - 1 - میباشد.
-2-2-4 روش تعیین تعداد همسایهها
مناسبترین تعداد همسایهها، با روش سعی و خطا مربوط به کمترینMAE محاسبه میشود با محاسبه تابع شباهت simw بین هر زوج کاربر و مشخص شدن kتا از شبیهترین همسایهها به کاربر هدف و با توجه به امتیازات همسایهها برای تک تک آیتمهای کاربر هدف، پیشبینی انجام میشود؛ سپس MAE با استفاده از معادله - 3 - بدست میآید. برای یافتن MAE کمینه حاصل از بهترین بردار وزن از الگوریتمهای ژنتیک و ازدحام ذرات استفاده میشود.
GA،کارخود را با یک جمعیت اولیه تصادفی از کروموزومها شروع میکند، هر کروموزوم رشتهای از ژنها است. جمعیت ایجاد شده توسط یک تابع برازش، ارزیابی میشود؛ سپس الگوریتم ژنتیک - GA - با استفاده از عملگرهای ژنتیکی انتخاب، ترکیب و جهش، اقدام به حل مسائل میکند[1] که در بخشهای بعدی معرفی میشوند.
-3-4 نمایش کروموزومها
در این مسئله هر کروموزوم به صورت بردار w با مقادیر اعشاری تصادفی در نظر گرفته می شود که شامل پنج ژن می باشد. که بازه مقادیر هر ژن نیز تصادفی و متفاوت است
-4-4 عملگر انتخاب
انتخابی که در اینجا مورد استفاده قرار گرفته، انتخاب نخبه گرا است. با استفاده از این عملگر بهترین عضو هر جمعیت، زنده می ماند و در جمعیت بعد حضور می یابد. به عبارت دیگر عضوی که بالاترین تطابق را دارد به طور خودکار به جمعیت جدید منتقل می شود. اعمال نخبه سالاری در الگوریتم ژنتیک،معمولاً باعث بهبود کارایی آن میشود.
-5-4 عملگر ترکیب
از عملگر ترکیب محاسباتی، برای تولید فرزندان استفاده می شود.
