بخشی از مقاله
چکیده
طراحی سیستمهای پیشنهاددهنده از جمله زمینههای پرکاربرد است که توجه محققین زیادی را به خود معطوف کرده است. یکی از مهمترین اهداف محققین این زمینه، افزایش دقت این سیستمهاست. درنظر گرفتن آیتم زمان و استفاده از روش خوشهبندی باعث افزایش دقت پیشنهادها میشود. به کارگیری روشهای بهینهسازی هوشمند دقت خوشهبندی را بهبود میدهد.
ایده اصلی این مقاله استفاده از الگوریتم رقابت استعماری آشوبگون برای افزایش کارایی خوشهبندی است. در این مقاله، هدف ارائهی یک سیستم پیشنهاددهندهی آگاه بازمان است که بر پایهی روش خوشهبندی بهبودیافته با الگوریتم رقابت استعماری آشوبگون طراحی شده است. چنین سیستمی میتواند برای ارائه پیشنهاد در وبسایتهای تجارت الکترونیک با زمینههای کاری مختلف به کار رود.
با توجه به پیچیدگی مسئله و اهمیت طراحی این سیستم، از تلفیق علوم دادهکاوی، محاسبات هوشمند و نظریهی آشوب استفاده شده است. به کارگیری روش خوشهبندی با در نظر گرفتن آیتم زمان و استفاده از الگوریتم رقابت استعماری آشوبگون منجر به پیدایش سیستمی با کارایی مناسب شده است.
در طراحی الگوریتم رقابت استعماری به جای مولدهای تصادفی از مولدهای آشوبگون برای نمونهبرداری از دادهها استفاده شده است،که این انتخاب به دلیل پوشش یکنواختتر فضای نمونهبرداری و افزایش تنوع انتخاب منجر به افزایش دقت الگوریتم میگردد. به علاوه سیستم طراحی شده توانایی مواجهه با چالشهای شروع سردکاربر و شروع سرد آیتم را نیز دارد. سیستم پیشنهادی بر روی مجموعهدادهی استاندارد movielense تست و دقت92 را کسب کرده است.
مقدمه
یک سیستم پیشنهاددهنده [1] با قابلیتی که در جمعآوری اطلاعات مربوط به سلایق، علایق و اولویتهای کاربران، دستهبندی و تفسیر آنها دارد، امکانی فراهم میآورد که کاربران با صرف زمان و انرژی کمتر به اطلاعات مورد نظر خود دسترسی پیدا کنند. یکی از پرکاربردترین الگوریتمهای بکار رفته در این سیستمها، روش پالایش مشارکتی مبتنی بر کاربر است. روش پیشنهادی مقاله بر این پایه بنا شده است.
هدف این مقاله ارائهی یک سیستم پیشنهاددهندهی آگاه بازمان است که بر پایهی روش خوشهبندی بهبودیافته با الگوریتم رقابت استعماری آشوبگون طراحی شده است. با توجه به پیچیدگی مسئله و اهمیت طراحی این سیستم، از تلفیق علوم دادهکاوی، محاسبات هوشمند و نظریهی آشوب استفاده شده است.
به کارگیری روش خوشهبندی با در نظر گرفتن آیتم زمان و استفاده از الگوریتم رقابت استعماری آشوبگون منجر به پیدایش سیستمی با کارایی مناسب شده است. ایدهی اصلی مقاله بهکارگیری الگوریتم رقابت استعماری برای افزایش دقت خوشهبندی است. در[11] ثابت شده است که استفاده از مولدهای آشوبگون در طراحی الگوریتم رقابت استعماری به جای مولدهای تصادفی به دلیل پوشش یکنواختتر فضای نمونهبرداری و افزایش تنوع انتخاب منجر به افزایش دقت نتایج میگردد.
از جمله چالشهای این سیستمها مشکل شروع سرد کاربر و شروع سرد آیتم است. شروع سرد کاربر به این معناست که سیستم باید قادر باشد در هنگام ورود یک کاربر جدید که هیچگونه سابقهای از علایق او موجود نیست، نیز پیشنهادات مناسب ارائه کند. شروع سرد آیتم نیز زمانی رخ میدهد که آیتم تازهای به مجموعه آیتمهای موجود اضافه شود.
در چنین مواقعی هم هیچگونه اطلاعی از علاقمندی کاربران به این آیتم موجود نیست. سیستم بایستی قادر به ارائه پیشنهاد مناسب در این مواقع نیز باشد. سیستم طراحی شده توانایی مواجهه با چالشهای شروع سردکاربر با به کارگیری اطلاعات دموگرافیک کاربر و برای شروع سرد آیتم، با استخراج ویژگیهای آیتم و پیشنهاد آن به کاربران علاقمند به این ویژگیها را دارد. سیستم پیشنهادی بر روی مجموعهدادهی استاندارد movielense تست و دقت92 را کسب کرده است.
روشهای پیشین
از جمله روشهای مورد مطالعه در این حوزه به روش مبتنی بر تجزیهی ماتریس غیرمنفی پالایش همکارانه برای سیستمهای پیشنهاددهنده[2] اشاره کرد. این روش به تجزیهی ماتریس رتبه بندی پرداخته است. تمرکز این مقاله بر روی یک مدل پالایش همکارانه مبتنی بر تجزیه ماتریس غیرمنفی با رویکرد مبتنی بر تک عنصر است. ایده این است که به جای ماتریسهای ویژگی، فرایند به روزرسانی غیرمنفی وابسته به هریک از ویژگی-های درگیر با استفاده از قوانین به روزرسانی مبتنی بر تک عنصر غیرمنفی بررسی شود.
همچنین در[3] روش ترکیبی جدیدی به نام HU-FCF++ برای مواجهه با چالشهای محدودیتهای مجموعه دادهی مورد استفاده، تعیین تعداد بهینهی خوشهها، متریک شباهت، کاربران بیربط و انتخاب مقادیر عضویت پیشنهاد شده است. این روش از ترکیب روشهای موجود استفاده کرده است. به عبارت دیگر به منظور ترکیب مزایای گروههای مختلف و از بین بردن معایب آنها توسط برخی روشهای خاص چندین گروه از روشهایی که تاکنون پیشنهاد شدهاند، را ادغام میکند.
با توجه به اهمیت اندازه گیری شباهت میان کاربران در این حوزه و همچنین روش پیشنهادی این پایان نامه مقاله [4] که مدل جدید شباهت کاربر برای بهبود صحت پالایش همکارانه را پیشنهاد کرده است نیز مورد بررسی قرار گرفته است. در [5] یک مطالعه مروری در مورد برخورد با مسئلهی شروع سرد کاربر جدید در سیستمهای پیشنهاددهنده صورت گرفته است.
در این مقاله، برای اولین بار یک طبقهبندی انجام شده است و مطالعات مرتبط با مسئلهی شروع سرد کاربر جدید را در 3گروه اصلی تقسیم بندی شده است و مزایا و معایب هریک را در قالب جدول خلاصه شده است. در پژوهشی دیگر در[6] خوشه بندی تکاملی را مبتنی بر زمان انجام می دهد که با کاربر یا آیتم شروع سرد مقابله نمی کند.
در [7] یک الگوریتم جدید مبتنی بر الگوریتم ممتیک و روش های متاهیوریستیک ارائه می کند، که در آن به کمک روش SA، کارایی را بهبود می دهد ولی پارامتر زمان را در نظر نمی گیرد؛ در صورتیکه در روش پیشنهادی، علاوه بر استفاده از الگوریتم ممتیک، از پارامتر زمان نیز جهت بهبود خوشه بندی استفاده می کند . در مقاله [8] نیز در مورد کاربران شروع سرد که سیستم اطلاعاتی راجع به آنها ندارد؛ مدلی پیشنهاد شده که الگوریتم های خوشه بندی را با ترکیب تکنیک های شباهت و مکانیزم پیش بینی، برای تولید پیشنهادات استفاده می کند.
روش پیشنهادی
از دیدگاه کلی روش پیشنهادی از چهار بخش تشکیل شده است. این بخشها در ادامه تشریح میشود. فلوچارت روش پیشنهادی در شکل - 1 - و - 2 - نمایش داده شده است.
شکل :1فلوچارت روش پیشنهادی
شکل: 2 ادامه فلوچارت روش پیشنهادی
معمولا، الگوریتم های خوشه بندی سنتی، در بهینه سازی یک تابع هدف سراسری، شکست می خورند. در اینجا یک تابع هزینه برای بهینه سازی تابع هدف، پیشنهاد شده است، که نتایج دقیق خوشه بندی را، به ویژه برای مجموعه داده تکاملی تولید می کند. از دید و نقطه نظر یک کاربر نتایج مربوط به محاسبات تکاملی، که یک دوره ی تغییرات را در اولویت های کاربر به تصویر می کشد، با تولید خوشه تکامل می یابد. چهارچوب روش پیشنهادی به این صورت است که در ابتدا کاربر را بررسی می کند، اگر کاربر شروع سرد نیست، ماتریس کاربر آیتم تشکیل می شود و زمان که صفر است، یکی به آن اضافه می شود.
در مرحله زمانیt 1، که حال یکی به آن اضافه شده است، اعضا را استخراج میکند وارد الگوریتم رقابت استعماری آشوبگون می شود، سر خوشه ها را انتخاب میکند و بر اساس آن خوشه بندی را انجام می دهد. برای تعداد خوشههای مشخص شده، جمعیت اولیه را تشکیل میدهد و از الگوریتم رقابت استعماری آشوبگون استفاده می کند. برای یافتن بهترین خوشه بندی از فاصله اقلیدسی استفاده میکند. تابع هدف را برای تمام مراحل زمانی، جهت خوشه بندی تکاملی محاسبه میکند.
خروجی فاز خوشه بندی را بدست آورده و شباهت کاربران را بر اساس فرمول پیرسون حساب می کند. سپس امتیاز کاربر هدف، به آیتم را پیش بینی می کند و ماتریس پیش بینی را به صورت نزولی مرتب می کند. n آیتم برتر را بر اساس الگوریتم top-N به کاربر پیشنهاد می دهد. برای خوشه بندی آیتم ها، کاربران علاقه مند را از فاز الگوریتم رقابت استعماری آشوبگون استخراج نموده و آیتم مورد نظر را به کاربران مشابه پیشنهاد میدهد.
از آنجایی که در این مقاله، با مسئله شروع سرد کاربر و آیتم هم مقابله می شود، برای شروع سرد کاربر از اطلاعات دموگرافیک کاربران برای تعیین خوشه کاربر شروع سرد، استفاده می شود؛ و بر اساس اطلاعات کاربران هم خوشه به کاربر شروع سرد پیشنهاد می دهد. همچنین، برای خوشه بندی آیتم سرد،ویژگی های آیتم را استخراج می کند و بر اساس خوشه های موجود کاربری و ژانرهای مورد علاقه آنها آیتم شروع سرد را به کاربران مربوطه پیشنهاد می دهد.
برای پیاده سازی چنین سیستم پیشنهاددهنده ای، یک چارچوب خوشه بندی، به نام CICA2 ارائه می گردد. خوشه بندی تکاملی، که در [4]، ارائه شده است، بعد زمان را استفاده نمی کند. در روش پیشنهادی خوشه ها بر اساس بازه ی زمانی، داده ها را دسته بندی می کند. در هر بازه زمانی یک خوشه جدید، بوسیله بهینه سازی دو پارامتر جدید به نام کیفیت نمایش لحظه ای3 و هزینه پیشینه4 تولید می شود.
کیفیت نمایش لحظه ای، به کیفیت خوشه بندی و صحت آن بستگی دارد. هزینه پیشینه بیان می کند که خوشه جدید با خوشه قبلی چقدر تفاوت دارد. در این چارچوب تمرکز روی انتقالات خوشه ای است که به مرور زمان، به وسیله افزایش کیفیت نمایشی لحظه ای و کاهش هزینه پیشینه، تامین می شود. مجموع کیفیت این توالی توسط فرمول - - 1 نشان داده می شود:
در هر بازه زمانی t ، که 1 ≤ ≤ است، یک مجموعه داده جدید وارد می شود. در اینجا فرض شده است، داده ها می توانند به وسیلهی یک ماتریس با سایز n*m نمایش داده شوند، که این ماتریس، وابستگی بین هر جفت از هدف های داده، را بیان میکند.خوشه های تکاملی را به عنوان گروهی از آیتم ها، در بازه زمانی t تعریف شده است. فرض کنید = {1,2,3, … , } یک مجموعه متناهی از بازه های زمانی میباشد و =
{ 1, 2, … , }مجموعه ای از mآیتم و = { 1, 2, … , }، nکاربر تازه وارد، در بازه های زمانی مختلف می باشد. پس فرض کنید کهC1 ، خوشه ایجاد شده در بازه زمانی T1 باشد، هنگامی که آیتم جدید it، در بازه زمانی t اضافه می شود، یا یک آیتم قدیمی، سطح اولویت و امتیاز خودش، نیز متفاوت است و در اینجا تابع CICA، یک خوشه بندی جدیدCt، که دارای کیفیت خوشه بندی بهینه است، را تولید میکند.
یک گروه از خوشه ها به نامCt، شناخته می شوند، که = { 1, 2, … , }، و در آن K - تعداد آیتم های خوشه می باشد - ، Ct گروهی از آیتم هاست، که در هر بازه زمانی داده شده اند و بخش بندی آیتم ها باید طوری باشد، که در هر خوشه، بالاترین درجه شباهت و کمترین تفاوت را داشته باشند. این هدف را میتوان، به وسیله الگوریتم خوشه بندی و به کمک تعریف تابع هزینه، که به کیفیت خوشه ها اشاره می کند، بدست آورد. در این الگوریتم،M1'…'0t، ماتریس های ورودی در هر بازه زمانیt است و C1'…'&t، خوشه های تولید شده در زمان t می باشد، که براساس ماتریس های جدید و پیشینه های جدید، به وجود می آید.
تابع هدف استفاده شده[4] ، دو هدف رقابتی کیفیت نمایش لحظه ای SQ و هزینه پیشینه HC را بهینه می کند. معیار کیفیت نمایش لحظه ای، چگونگی یک نمایش خوب از خوشه ها را، در بازه زمانی t، بر روی داده ها، نشان می دهد. ما این معیار را به کمک مقیاسی که واریانس نام دارد، تعریف میکنیم که این واریانس تفاوت بین آیتم ها را در هر خوشه کمینه و شباهت آنان را پیشینه می کند. پیاده سازی واریانس در [9] و [10] انجام شده و در [4] نیز کیفیت لحظه ای موثر ارائه گردیده است.
تفاوت واریانس امتیاز 5، بین دسته بندی آیتم ها در یک خوشهی خاص در یک نقطه از زمان است. بیشتر بودن ارزش واریانس، پایین بودن کیفیت نمایش لحظه ای است. در اینجا بازه زمانی t انتخاب شده است، که حداکثر کمک را به این مسئله بیان می کند. برای محاسبه این دو از فرمول - - 2 و - 3 - استفاده می شود:
که SQ، کیفیت نمایش لحظه ای است و میزان کیفیت خوشه بندی داده ها،در مرحله زمانیt است، که روش ها با واریانس امتیاز نشان داده می شود و تفاوت بین آیتم های خوشه را کمینه و شباهت بین دو خوشه را بیشینه می کند و توسط اختلاف امتیازهای آیتمها در یک خوشهی خاص، در مرحله زمانی خاص محاسبه می شود.
VScore امتیاز واریانس که نشان دهنده ی تفاوت هر داده از میانگین، برایK همسایه است، که به آیتمi ، در بازه زمانی t، در ماتریس Mt، امتیاز داده است. - , - امتیاز k کاربر همسایه nام، به آیتم i در مرحله زمانی t است که در ماتریس Mt قرار می گیرد، همچنین - ̅ - میانگین امتیازات کاربران همسایه nام به آیتم i در مرحله زمانی t می باشد.
Mt یک ماتریس n*n است، که آیتم های وارد شده در این مرحله زمانی را نشان می دهد. این ماتریس نشان دهنده ارتباط بین هر جفت آیتم داده ای است و می توان آن را براساس شباهت یا فاصله دو آیتم، در مرحله زمانی t بدست آورد.
