بخشی از مقاله
چکیده
امروزه به دلیل گستردگی رقابت در دنیای تجارت الکترونیک، یافتن روشهای مؤثر در جذب مشتریان و کاربران از اهمیت ویژهای برخوردار است. یکی از این روشها استفاده از الگوریتمهای مربوط به سیستمهای توصیهگر در وبگاههای تجاری است و بدین ترتیب امکان استخراج علایق مشتریان و پیشنهاد مناسبترین محصولات به آنان با بهکارگیری شیوههای دادهکاوی میسر میگردد.
با توجه به مطالعات فراوانی که بر روی این نوع الگوریتمها انجامشدهاند، مسئله پیشبینی امتیازات و حل مشکلات این الگوریتمها که به دلیل کمبود اطلاعات اولیه ورودی توسط مشتریان به مشکل شروع سرد معروف هستند، یکی از عمدهترین چالشهای موجود در الگوریتمهای پالایش مشارکتی میباشند.
سیستم پیشنهادی از تکنیک استخراج قوانین انجمنی و فیلترینگ مشارکتی برای پیشنهادهای شخصیسازیشده بهمنظور به حداقل رساندن مشکلات شروع سرد و پراکندگی دادهای که درروش فیلترینگ مشارکتی وجود دارند، استفاده مینماید.
استخراج قوانین انجمنی در این روش، بر اساس الگوریتم اپریوری و خوشهبندی غنیشده با الگوریتمهای تکاملی است ،استفاده میشود.در این روش با توجه به اینکه قوانین انجمنی فقط روی اعضای یک خوشه که توسط الگوریتم ترکیبی ازدحام ذرات و ژنتیک بهبودیافته انجام میشود، پیدا کردن قوانین انجمنی نسبت به روشهای دیگر سریعتر و قوانین کاراتر استخراج میشوند.
در سیستم پیشنهادی از مدلسازی کاربر، مدل فیلترینگ مشارکتی و قوانین انجمنی استفاده میشودو کارایی روش توصیهشده با روشهای سنتی مقایسه میشود و نشان داده میشود که این سیستم میتواند به کارایی بهتری دست یابد.
-1 مقدمه
نسل جدید برنامههای تحت وب بهعنوان سیستمهای پیشنهاددهنده شناخته میشوند.یک سیستم پیشنهاددهنده با گردآوری مداوم اطلاعات از رفتار هزاران هزاران کاربر و بهکارگیری شیوههای دادهکاوی1 میتواند روندها را تشخیص داده و به کاربر پیشنهاد کند که به چه موسیقی گوش دهد یا چه مطلبی بخواند. این فرآیند میتواند به حفظ و یا جذب کاربران جدید برای هر وبسایت رقابتی منجر شود.
یکی از مهمترین و پراستفادهترین روشهای پالایش در سیستمهای پیشنهاددهنده روش پالایش مشارکتی میباشد که پایه و مبنای کار در بسیاری از راهکارهای دیگر نیز به شمار میرود. روش کار این الگوریتم درواقع به همان صورتی است که ما در تصمیمگیریهای روزمرهمان عمل مینماییم. ×بهعنوانمثال کالایی را میخریم که بیشتر موردپسند دیگران واقعشده باشد.
توجه داشته باشید که در این راهکار سیستم بر مبنای امتیازات، آیتمها را رتبهبندی میکند و آیتمهایی با بیشترین امتیاز را به کاربر پیشنهاد میدهد. یکی از مشکلات اساسی و مهم در اینگونه سیستمهاست که با عنوان شروع سرد2 شناخته میشود.درراستای حل مشکل شروع سرد تحقیقاتی صورت گرفته که در ادامه به بررسی آنها میپردازیم. در [ 1] رویکرد جدیدی ارائهشده است که روشهای گرفتن ویژگی و خوشهبندی را بهمنظور توجیه مشکل شروع سرد به کار میگیرد. در این مقاله از روش بردار کسینوسی و خوشهبندی کاربران در گروههای متفاوت استفادهشده است. هنگامیکه کاربران جدید وارد سیستم میشوند، به گروههای مختلفی بر اساس ویژگیهای ثبتشده - مانند سن، جنسیت و... - طبقهبندی میشوند.
بنابراین یک کاربر جدید میتواند پیشنهادهایی برای گروه خود به دست آورد. ایرادهای این روش شباهت سنجی کسینوسی در محاسبه مراکز جدید خوشه است. زیرا مانند روش اقلیدسی بهراحتی نمیتوان با گرفتن میانگین مرکز خوشه جدید را محاسبه کرد و افزایش حجم دیتاست زمان را بهشدت افزایش میدهد. در [2] سیستمی ارائهشده است که در آن از الگوریتم طبقهبندی در ترکیب با روشهای شباهت و مکانیسمهای پیشبینی استفادهشده است. سیستم پیشنهادی، نتایج پیشنهادهای شخصیسازیشده را برای کاربران جدید با استفاده از ویژگیهای جمعیت شناختی آنها ارائه میکند.
در [3]از فیلترینگ مبتنی بر محتوا و فیلترینگ مشارکتی بهعنوان دو فناوری اصلی بهبود سیستمهای پیشنهاد دهنده استفادهشده است. با استفاده از فیلترینگ مبینی بر محتوا علاقهمندیهای کاربران را به دست آورده و با آنالیز ویژگیهای اقلام یا کاربران پیشنهادهایی را تولید میکند.
در [4]نگاه جدیدی به مسئله شروع سرد در سیستمهای پیشنهاد گر فراهمشده است که شروع سرد را بهعنوان یک مسئله Contextual-bandit در نظر میگیرد که هیچ اطلاعات اضافی در مورد کاربران جدید و آیتمهای جدید لازم نیست. مقادیر گذشته کاربران قبل را بهعنوان اطلاعات مفهومی که باید در چارچوب پیشنهاد ادغام شوند در نظر میگیرد. برای حل این نوع مسائل شروع سرد یک روش کارآمد جدید پیشنهاد میکند که بر اساس الگوریتم جدید LinUCB برای مسائل Contextual-bandit میباشد.
در این مقاله سیستم پیشنهاددهنده ای ارائه میشودکه برروی حل مشکل شروع سرد کاربر متمرکز شده است.برای این منظوردرسیستم پیشنهادی از ترکیب دو الگوریتم تکاملی ژنتیک و ازدحام ذرات جهت خوشهبندی افرادبراساس اطلاعات دموگرافیک و شناسایی بهتر آیتم های تکراری مناسب که واجد شرایط بر اساس حداقل آستانهی پشتیبانی3 را ارضا میکند، استفاده میشود. برای ارزیابی عملکرد الگوریتم پیشنهادی از مجموعه داده استاندارد استفاده شده است.مقایسه نتایج بدست آمده با روش CFبه ازای Nهای متفاوت ،نشان می دهد با استفاده از روش پیشنهادی میتوان آیتم های بهتری را به کاربران سرد پیشنهاد داد.
در بخش دوم الگوریتم خوشه بندی ترکیبیGA-PSOوروشهای موجود استفادهشده در آنها همچون خوشهبندی4 و قواعد انجمنی5 به اختصار بیان میگردد. در بخش سوم الگوریتم پیشنهادی مورد بررسی قرار خواهد گرفت و در بخش چهارم نتایج بدست آمده از الگوریتم پیشنهادی برروی داده ها ارائه می گرددو در بخش آخر به جمع بندی و نتیجه گیری پرداخته میشود.
-2 الگوریتم خوشه بندی ترکیبیGA-PSO
برای توضیح الگوریتم ترکیبی فوق ابتدا خوشه بندی و سپس هر یک از الگوریتم های PSO و GA را به طور خلاصه شرح میدهیم وسپس به توصیف الگوریتم GA-PSOمیپردازیم.
-1-2خوشه بندی
خوشهبندی ابزاری برای کلاسبندی غیر نظارتشده دادهها میباشد. در حقیقت یک تکنیک جداسازیدونب نظارت است که معمولاً دادهها را بهصورت بردارهایی در یک فضای چندبعدی دریافت کرده و آنها را در دستهها یا خوشههایی قرار میدهد. با این ویژگی که الگوهای یک کلاستر یا خوشه از یک تشابهی سود میبرند درحالیکه الگوهای کلاسترهای مختلف بالعکس تشابهی باهم ندارند. بنابراین باید به دنبال معیاری برای مشابهت دستهای از الگوها باشیم بهگونهای که این الگوها در خوشه یکسانی جای بگیرند .بهعنوان نمونه یک معیار مشابهت میتواند فاصله اقلیدسی دو الگوی X و Z باشد
-2-2 بهینه سازی گروهی ذرات - - PSO
الگوریتم PSO که توسط EberhartوKennedy پیشنهاد شده است، یک تکنیک بهینه سازی تصادفی بر مبنای جمعیت می باشد که از رفتارهای اجتماعی دسته پرندگان و ماهی ها الهام می گیرد. در الگوریتم PSO ابتدا سیستم با یک جمعیتی از جواب های تصادفی مقدار دهی اولیه می شود و سپس با به روز رسانی نسل ها جواب بهینه جستجو می شود.
در الگوریتم تعدادی از موجودات وجود دارند، که به آنها ذره گفته میشود و در فضای جستجوی تابعی که قصد کمینه کردن - و یا بهینه کردن - مقدار آن راداریم، پخششدهاند. هر ذره مقدار تابع هدف را در موقعیتی از فضا که در آن قرارگرفته است، محاسبه میکند. سپس با استفاده از ترکیب اطلاعات محل فعلیاش و بهترین محلی که درگذشته در آن بوده است و همچنین اطلاعات یک یا چند ذره از بهترین ذرات موجود در جمع، جهتی را برای حرکت انتخاب میکند. همهی ذرات جهتی برای حرکت انتخاب میکنند و پس از انجام حرکت، یک مرحله از الگوریتم به پایان میرسد. این مراحل چندین بار تکرار میشوند تا آنکه جواب موردنظر به دست بیاید.
در الگوریتم خوشهبندی مبتنی برPSO موقعیت هر ذره بهصورت = - - 1 - , … , - - - نشان داده میشود. بهطوریکه - - مرکز خوشه k ام را نشان میدهد[7,6] مراحل این الگوریتم بهصورت زیر است :
گام اول: هر ذره بهطور تصادفی k مرکز خوشه را از میان دادهها انتخاب میکند . گام دوم: به تعداد تکرارهای مناسب برای هر ذره عملیات زیر انجام میگیرد . برای هر بردار داده فاصله اقلیدسی با تمام مراکز محاسبه میشود و داده به نزدیکترین مرکز خوشه منتسب میشود .
تابع شایستگی محاسبه میشود .
بهترین مکان کلی و بهترین مکان محلی برای هر ذره محاسبه میشود . مراکز خوشهها با توجه به فرمولهای - 1 - و - - 2بهروز میشوند.
-3-2 الگوریتم ژنتیک
الگوریتمهای ژنتیک6 - با نماد اختصاری - GA تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکاملی است که از تکنیکهای زیستشناسی فرگشتی مانند وراثت و جهش استفاده میکند. این الگوریتم برای اولین بار توسط جان هلند معرفی شد.
در دو دهه اخیر تحقیقات بسیاری بر مبنای الگوریتم ژنتیک انجام شده است تا بتوان احتمال پیدا کردن نقاط بهینه سراسری را بالا برد.
در سال 2008 الگوریتم خوشهبندی تحت عنوان k-means توسط زالیک[8] 7 ارائه شد ،ایده اصلی این مقاله کمینه کردن تابع هزینه است.در سال 2010 جینگ و همکارانش[9] 8برای برطرف کردن مشکلات الگوریتم k-meansالگوریتم ژنتیکی کوانتومی ارائه دادند.
الگوریتم ژنتیک می تواندیک راه حل بهینه کلی را پیدا کند که تحت ثاثیر نقاط جدا شده نمی باشد. ولیکن هنگامی که این الگوریتم با تعداد زیادی از داده ها و انواع مختلفی از آنها مواجه می شود، زمان اجرا بسیار طولانی و زمان همگرایی راضی کننده و کافی نیست درواقع برای داشتن ثبات خود، همگرایی را فدا می کند. با این وجود هنوز هم نتایج تحقیقی زیادی در ارتباط با خوشه بندی با استفاده از الگوریتم ژنتیک وجود دارد.
4-2 الگوریتم ترکیبی PSO و GA
در سالهای اخیر جهت رفع اشکال الگوریتمهای خوشهبندی در تولید جوابهای مینیمم محلی، با ترکیب الگوریتمهای فرا ابتکاری الگوریتم جدیدی طراحیشده است که کارایی و اثربخشی الگوریتمهای خوشهبندی را بهبود دادهاند. بهبود الگوریتمهای خوشهبندی به روشهای ذیل انجام میگردد:
-1 تعیین روش انتخاب پارامترهای اولیه
-2 تغییر در الگوریتم پایه
-3 بهبود خوشهبندی با ترکیب الگوریتمهای فرا ابتکاری
هیوا و همکاران[11] الگوریتم خوشهبندی GAPSOرا پیشنهاد کردندسه مرحله از الگوریتم ژنتیک درون الگوریتم GAPSO وجود دارد: -1هنگام محاسبه تناسب در افراد، موقعیتهایی از بهترین ذرات کلی باید بررسی و نظارتشده و نیز ثبتشده باشند.
-2 الگوریتمPSO، بعد از اجرای اپراتورهایGA، پردازش میشود.
-3 الگوریتم خوشهGAPSOنیاز به تعیین اندازه جمعیت، انتخاب شدت، احتمال تقاطع و جهش، و همچنین پارامترهایPSOمربوطه دارد.
این روش هر دو الگوریتم PSO و GA را باهم ترکیب کرده و ویژگیهایشان را بررسی کرده و سپس الگوریتم نهایی GAPSO را ارسال میکند.این روش، دارای هر دو مشخصه کارایی عمومی و قابلیت ثبات الگوریتم ژنتیک و نیز قابلیت باﻻ در اثر همگرایی در الگوریتم PSO است
. این روش میتواند نفوذ ذرات با مقادیر شایستگی بالاتر را بهبود بخشد و موجب همگرایی سریعتر گردد.
-3 الگوریتم پیشنهادی
سیستم توصیه دادهشده از سه لایه تشکیل میشود و عملکردهای کلیدی هر سه لایه بهصورت زیر میباشد:
- 1مدیریت پروفایل کاربری: این مدیر اطلاعات شخصی تماشاگران تلویزیون را مدیریت میکند. این اطلاعات شخصی شامل علاقهمندیهای مربوط به فیلمهای خاصی را که یک کاربر تماشا میکند و اطلاعاتپایه مانند جنسیت، سن و شغل هستند که اطلاعات شخصی یک فرد را، شامل میشود.
- 2 لایه مدلسازی کاربر: این لایه شامل 2 مدل برای پیشبینی علاقهمندی به آیتم هائی است که کاربران هنوز مشاهده نکردهاند
