بخشی از مقاله
چکیده
به موازات گسترش وب و افزایش حجم اطلاعات موجود در پایگاههای داده، همواره روشهای استخراج اطلاعات و روندهای سودمند از این پایگاهها رو به افزایش بوده است. از این رو در پژوهش حاضر سعی شده است تا الگوریتمی جدید برای بهبود الگوریتم بسیار کاربردی و سادهی K-Means ارائه شود. یکی از بزرگترین ایراداتی که به الگوریتم K-Means وارد است، انتخاب مراکز اولیهی خوشهها به صورت تصادفی است، که همواره پاسخ نهایی این الگوریتم را تحت تأثیر قرار میدهد، در نتیجه در الگوریتم حاضر سعی شده است تا با بهرهگیری از الگوریتم کرم شبتاب این نقص را بهبود داد. هر دو الگوریتم پیشنهادی و K-Means بر روی پایگاه دادهی عمومی و معتبر MovieLens پیادهسازی شدند. نتایج حاصل از شاخص اعتبارسنجی دیویس بولدین نیز نشان دهندهی بهبود چشمگیر این الگوریتم میباشد.
کلمات کلیدی:خوشهبندی، K-Means، الگوریتم کرم شبتاب
-1 مقدمه
در دنیای امروز حجم وسیعی از دادهها بر روی هم انباشته شدهاندو جستوجوی دانش از میان این حجم عظیم دادهها یکی از اساسیترین ویژگیهای علم دادهکاوی1 است.[1] دادهکاوی تنها به جمعآوری و مدیریت دادهها محدود نمیشود، بلکه تجزیه و تحلیل و پیشبینی را نیز در بر میگیرد. بهطور کلی روشهای مختلف دادهکاوی در دو دسته روشهای یادگیری با نظارت - نظارتی - و روشهای یادگیری بدون نظارت قرار میگیرند. [2]در روشهای یادگیری با نظارت هدف از دادهکاوی مشخص است و میدانیم که به دنبال چه نوع دانشی هستیم، همانند انواع روشهای طبقهبندی، اما در روشهای یادگیری بدون نظارت، هدف کاملا تعریف شده نیست، که از این میان میتوان به روشهای مختلف خوشهبندی اشاره کرد.[2] خوشهبندی به دنبال سازماندهی مجموعهای از اقلام داده به خوشهها، به طریقی است که اقلام موجود در یک خوشه بسیار" مشابه " هم باشند و این شباهت با اقلام موجود در خوشههای دیگر بسیار کاهش یابد.[3]
خوشهبندی معمولا زمانی مورد استفاده قرار میگیرد که هیچ اطلاعاتی در رابطه با عضویت اقلام داده در کلاسهایی - طبقههایی - از پیش تعریف شده، وجود نداشته باشد. به همین دلیل، خوشهبندی به طور سنتی، به عنوان جزئی از یادگیری بدون نظارت در نظر گرفته میشود.[4] در این میان الگوریتم خوشهبندی K-Means رویهی خوشهبندی است که به طور گسترده مورد استفاده قرار میگیرد. این روش به دنبال یک جدا سازی نزدیک به بهینه با تعداد ثابتی از خوشهها میباشد. این روش از یک الگوریتم تپه- نوردی2 تکرار شونده استفاده میکند.[5]الگوریتم K-Means به دلیل عملکرد آسان و ساده بسیار محبوب است.[6] با این وجود این الگوریتم دارای اشکالاتی نیز میباشد. اول آن که این الگوریتم با همپوشانی خوشهها به خوبی مقابله نمیکند و خوشهها میتوانند از طریق دور افتادهها به خارج از مراکز کشیده شوند.
همچنین حاصل خوشهبندی ممکن است به فرزندان اولیه بستگی داشته باشد، با این وجود سازوکاری به منظور بهینهسازی فرزندان اولیه وجود ندارد.[7] علاوه بر موارد فوق، این الگوریتم ممکن است به یک بهینهی محلی تحت شرایط خاصی همگرا شود، چرا که این الگوریتم همچون یک استراتژی تپه-نوردی عمل میکند.[8] درنتیجه در سالهای اخیر به منظور بهبود این الگوریتم در تعدادی از پژوهشها از الگوریتمهای تکاملی بهره گرفته شده است.کیم و اهن در سال 2008، یک الگوریتم خوشهبندی جدید مبتنی بر الگوریتمهای ژنتیک - GAs - 3، به منظور بخشبندی کارآمد و موثر بازار خرید آنلاین ارائه کردند. این پژوهشگران روش خوشهبندی K-Meansرا که پاسخهای اولیه آن توسط GA بهینهسازی شده است و آن را GA K-Means نام نهادهاند، به یک مورد بخشبندی بازار خرید آنلاین دنیای واقعی، اعمال کردند.[8]
یوکریت، نیپن و سنسنیی در سال 2014 یک الگوریتم خوشهبندی جدید بر اساس الگوریتمهای ممتیک4 و K-Means ارائه کردند.[9]شمس فرد، مویدی کیا و فرصتی در سال 2015 یک الگوریتم خوشهبندی جدید مبتنی بر الگوریتمهای جستجوی هارمونی و الگوریتم K-Means تحت عنوان الگوریتم خوشهبندی جستوجوی هارمونی - HSC - ارائه کردند.[10]از آن جا که در پژوهشهای اخیر استفاده از الگوریتمهای تکاملی به دلیل عملکرد مناسب در اغلب حوزهها، گسترش یافته است و از طرفی مطالعات اولیه، برتری الگوریتم کرم شبتاب 5 - FA - را نسبت به الگوریتمهای ژنتیک و ازدحام ذرات6 نشان میدهد[11]، در پژوهش حاضر، از این الگوریتم به منظور بهبود الگوریتم K-Means در انتخاب مراکز اولیهی خوشهها، استفاده شده است.
در الگوریتم پیشنهادی از ادغام ویژگیهای میزان سازی دقیق الگوریتم K-Means و دید قدرتمند سراسری الگوریتم کرم شبتاب به منظور یافتن خوشههایی نزدیک به بهینه استفاده شده است. به این صورت که ابتدا الگوریتم کرم شبتاب به تعداد مطلوب انجام شده و سپس خروجی این الگوریتم به عنوان خوشههای اولیهی الگوریتم K-Means مورد استفاده قرار میگیرند.در ادامه این پژوهش، نخست به تشریح مبانی پژوهش پرداخته و الگوریتمهای K-Means و کرم شبتاب معرفی میشوند. پس از آن الگوریتم پیشنهادی FA-K-Means به تفصیل بیان میشود. به دنبال آن، شاخص ارزیابی دیویس بولدین 7 - DB - توضیح داده شده و در پایان، به بررسی نتایج آزمایشها، تحلیلهای مربوطه و جمعبندی دستاوردهای پژوهش پرداخته میشود.
-2 مبانی پژوهش
در این بخش، الگوریتمهای مورد استفاده در مدل پیشنهادی یعنی الگوریتمهای K-Means و کرم شبتاب معرفی میشوند.
-2-1 الگوریتم خوشهبندی K-Means
فرایند خوشهبندی K-Means به شرح زیر میباشد.
·فرزندان اولیه با تعداد منتخب خوشهها، K، انتخاب میشوند و یک جداسازی اولیه با استفاده از فرزندان به عنوان مراکز ثقل خوشههای اولیه صورت میگیرد.
·هر رکورد به مرکز ثقلی که نزدیکترین است، تخصیص داده میشود. در نتیجه یک خوشه شکل میگیرد.
·به منظور نگهداشتن همان تعداد مشخص شده از خوشهها، مرکز ثقل جدید هر یک از خوشهها محاسبه میشود.
·گامهای دوم و سوم تا زمانی که که خوشهها دیگر تغییر نکنند یا شرایط توقف برآورده شود، تکرار میشوند.[8]
-2-2 الگوریتم کرم شب تاب
الگوریتم کرم شبتاب به ابزار به طور فزاینده مهم هوش جمعی8 که قابل اعمال در اغلب حوزههای بهینهسازی و همچنین کاربردهای مهندسی است، تبدیل شده است. بسیاری از مسائل از حوزههای مختلف، به طور موفقیتآمیزی از طریق به کارگیری الگوریتم کرم شبتاب و انواع مختلف آن حل شدهاند. به منظور استفاده از این الگوریتم برای حل مسائل گوناگون، الگوریتم کرم شبتاب اصلی نیاز به تغییر و یا اصلاح و ترکیب دارد.[12]بر اساس پژوهش صورت گرفته توسط فیستر و همکاراناش در سال 2013 بر روی اصول زندگی و تکامل این هوش جمعی، نشان داده شد که الگوریتم کرم شبتاب قابل اعمال به تمامی مسائل دنیای واقعی میباشد. این الگوریتم اغلب تضمین میکند که نتایج حاصل انتظارات را برآورده خواهند کرد.[13]
نسخه اصلی الگوریتم کرم شبتاب به این ترتیب قابل توصیف است: شدت نور I حاصل از تابیدن کرم شبتاب همان طور که فاصله از منبع r افزایش مییابد، بر حسبI ∝ 1/ کاهش پیدا میکند. علاوه بر این، قابلیت جذب هوا9 سبب میشود که همان طور که فاصله از منبع افزایش پیدا میکند، نور ضعیفتر و ضعیفتر شود. این تابش نور، عامل الهام بخش برای توسعهی الگوریتم کرم شبتاب - FA - ، توسط یانگ در سال 2008 شده است.[14]در این جا، شدت نور متناسب است با تابع هدف مسألهای که میبایست بهینهسازی شود. - به عبارت دیگر، I - s - ∝ F - s - است، که در آن s = S - x - نشان دهندهی یک پاسخ نامزد است. - [13]به منظور مدلسازی الگوریتم FA، برخی از ویژگیهای تابش کرمهای شبتاب ایدهآل در نظر گرفته شدند، که عبارتند از:
·تمامی کرمهای شبتاب تک جنسیتی میباشند.
·جذابیت آنها با شدت نورشان متناسب است.
·درخشندگی یک کرم شبتاب متأثر و یا تعیین شده با مقدارتابع هدف میباشد.
دقت شود که، شدت نور I و جذابیت به طریقی مترادف هستند. در حالی که شدت نور به عنوان معیار سنجشی مطلق از نور ساطع شده توسط کرم شبتاب، در نظر گرفته میشود، جذابیت به عنوان معیار سنجشی نسبی از نوری است، که میبایست در چشم بیننده دیده شود و توسط دیگر کرمهای شبتاب مورد قضاوت قرار گیرد.[14]شدت نور I با فاصلهی r تغییر میکند، که از طریق معادلهی - 1 - بیان میشود. - 1 - که در آن 0 به شدت نور در منبع اشاره دارد و ضریب ثابت جذب نور است. به طور مشابه، جذابیت که به فاصله r بستگی دارد، بر اساس معادلهی تعمیم یافتهی - 2 - محاسبه میشود. فاصلهی بین کرمهای شبتاب i و j از طریق فاصلهی اقلیدسی - 3 - نمایش داده میشود.که در آن ، K امین عنصر i امین موقعیت کرم شبتاب در فضای جستوجو، میباشد و D به ابعاد مسأله اشاره دارد. هر کرم شبتاب i به سمت کرم شبتاب j جذابتر به صورت رابطهی - 4 - ، حرکت میکند.معادلهی فوق از سه اصل تشکیل شده است، که عبارتند از:
·اصل اول تعیین کنندهی موقعیت i امین کرم شبتاب است.
·اصل دوم به جذابیت اشاره دارد.
·اصل سوم مربوط به حرکت تصادفی i امین کرم شبتاب در فضای جستوجو میباشد. این اصل دربرگیرندهی پارامترهای تصادفی سازی ∝ و اعداد تصادفی - 0 ,1 -
