بخشی از مقاله
چکیده :
تکنیک خوشهبندی از مهمترین تکنیکهای دادهکاوی و روشی برای گروهبندی دادههای مشابه در خوشههای یکسان است. با بزرگتر شدن بانکهای دادهای، تلاش محققان برای یافتن روشهای خوشهبندی کارا و موثز متمرکز شده است تا از این راه بتوانند زمینه تصمیمگیری سریع و منطبق با واقعیت را فراهم آورند. بدین منظور در این مقاله تکنیک خوشهبندی با ترکیب الگوریتم رقابت استعماری و آشوب با هدف ارائه الگوریتمی کارا و با دقت بالا پیشنهاد شده است. نتایج حاصل از اجرای الگوریتم بر روی 5 مجموعه داده معروف بیانگر دقت الگوریتم پیشنهادی است.
کلید واژهها: آشوب، الگوریتم رقابت امپریالیستی، خوشهبندی
-1 مقدمه
خوشهبندی از افرازبندی یک گروه متنوع به تعداد زیرگروه مشابه یا گروهبندی مجموعهای از اشیاء به کلاسی از اشیاء مشابه به وجود میآید، در هر خوشه باید دادههایی شبیه به هم قرار گیرند و کمترین شباهت را با دادههای موجود در دیگر خوشهها دارا باشند. روشهای مختلف خوشهبندی با توجه به رویکردی که برای گروه-بندی دادهها از آن استفاده میکنند، به انواع مختلفی تقسیم می-شوند که از آن میان میتوان به روشهای مبتنی بر افراز دادهها، روشهای سلسه مراتبی، روشهای شبکهای، روشهای مبتنی بر تراکم و روشهای مبتنی بر مدل اشاره نمود .[2-1] در این مقاله روی خوشهبندی افرازی متمرکز میشویم. معروفترین الگوریتم-های خوشهبندی افرازی، الگوریتمهای خوشهبندی مرکز محور هستند که در میان آنها به الگوریتم k-means میتوان اشاره کرد. با توجه به سادگی و کارایی، الگوریتم k-means در سالهای گذشته مورد توجه قرار گرفته است.
با این حال، از کاستیهای آن میتوان به موارد زیر اشاره کرد: الگوریتم به انتخاب نقاط اولیه حساس است و به راحتی در مینیمم محلی گرفتار میشود .[14] به منظور غلبه بر این مشکل الگوریتمهای خوشهبندی اکتشافی معرفی شدهاند. برای مثال Koa و همکارانش با ترکیب دو الگوریتم ژنتیک و PSO روشی را ابداع نموده که در آن از عملگر جهش و تقاطع برای ژنتیک بهره گرفتهاند، این روش توانست مشکلات توابع پیوسته را رفع نماید. همچنین در یافتن جواب بهینه سراسری و سبب همگرایی تغییرات چشمگیری حاصل شده است .[3] یکی دیگر از روشهای جدید برای مسائل دادهکاوی، ترکیب الگوریتم PSO تطبیقی فازی با دو الگوریتم کلونی مورچه و k-means میباشد.
این روش توسط نیکنام و همکارانش در سال 2010 مطرح گردید. نتایج حاصله از این تکنیک در راستای بهبود عملکرد خوشهبندی اطلاعات بسیار جالب توجه میباشد از مزیت کلونی مورچگان، توانایی پیشبینی تعداد خوشهها را میتوان ذکر نمود و اینکه نتایج حاصله برتری کیفیت عملکرد ارزیابی را تضمین مینماید .[4] در سال 2015، Zheng و همکارانش روشی مبتنی بر ترکیب الگوریتم کلونی مورچگان و آشوب ارائه نمودهاند. این الگوریتم بر پایه زندگی اجتماعی مورچهها بنا شده است که در حوزه هوش مصنوعی می-باشد. در این الگوریتم از آشوب برای تعیین مسیر مورچه ها استفاده شده است و برای خوشهبندی تصاویر ار این الگوریتم بهره گرفته شده است . [5]
یک الگوریتم خوشهبندی از ترکیب الگوریتم رقابت کشورهای استعماری، آبکاری فولاد و k-means در سال 2012 نیکنام و همکارانش برای مساله خوشهبندی ارائه کردهاند. عملکرد این الگوریتم که K-MICA ترکیبی نام دارد در مقایسه با الگوریتمهای k-means ، رقابت استعماری، K-MICA و MICA-K قابل ملاحظه میباشد .[6] پورسیاه ناوی و همکارانش در سال 2014 الگوریتم PSO را با تابع برازندگی cmeans فازی کارآمدتر کردهاند و سپس برای تولید جمعیت اولیه الگوریتم را با آشوب ترکیب کردهاند و در نهایت برای رفع مشکل همگرایی زودرس یک جهش و تابع برازندگی مبتنی بر وزن اینرسی پیشنهاد کردهاند .[7] در سال Maheshwar 2015 و همکارانش یک الگوریتم ترکیبی از الگوریتمهای ژنتیک و کرم شبتاب برای مساله خوشه-بندی ارائه کردهاند، در روش پیشنهادی الگوریتم کرم شبتاب برای انتخاب جمعیت اولیه از الگوریتم ژنتیک کمک میگیرد.[8]
الگوریتمهای تکاملی از مکانیزمها و عملیات ابتدایی برای حل مساله استفاده میکنند و در طی یک سری از تکرارها به راه حل مناسب مسئله میرسند. این الگوریتمها غالباً از یک جمعیت حاوی راهحلهای تصادفی شروع میکنند و در طی هر مرحله تکرار، سعی در بهتر کردن مجموعه راهحلها دارند .[9] لذا با بهرهگیری از ترکیب تئوری آشوب و الگوریتمهای تکاملی بهعنوان روشهای بهینهسازی نوین، این محدودیت مرتفع میشود. قابل توجه است که نسخههای اصلی الگوریتمهای تکاملی به تنهایی در رفع این مشکل کارساز نبوده است. تئوری آشوب مطالعه رفتار سیستمهای دینامیکی است که به انتخابهای اولیه حساسیت بالایی دارند و تفاوتهای کوچک در انتخابهای اولیه - مثل خطای گرد گردن در محاسبات ریاضی - باعث واگرایی نتایج حاصل از سیستمهای آشوبی میشود و در نتیجه پیشبینیهای بلند مدت را غیرممکن میکند.
بنابراین از ایده دنبالههای آشوبی، شبه تصادفی بودن جمعیت اولیه، برای بهبود عملکرد الگوریتم استفاده میشود تا احتمال همگرایی به نقاط بهینه محلی کاهش یابد. هدف مقاله این است که با بررسی الگوریتمهای موجود در زمینه خوشهبندی، راهکاری برای ایجاد تغییرات در الگوریتمهای موجود برای بالا بردن سرعت همگرایی و بهبود کیفیت خوشهبندی ارائه گردد به-گونهای که محدودیت های موجود از جمله کارایی برای پایگاه دادههای با حجم بالا، کشف خوشهها با اشکال مختلف، عدم حساسیت به ترتیب دادههای ورودی، قابلیت تفسیر و استفاده را پوشش دهد. در ادامه، مقاله به این صورت سازمان یافته است: در بخش 2 م ساله تحلیل خو شهای معرفی شده ا ست. در بخش 3 الگوریتم پیشنهادی شرح داده خواهد شد. در بخش 4 نتایج خوشه بندی با الگوریتمهای تکاملی آشوبگونه نشان داده شده است. در نهایت بخش 5 شامل خلاصه و نتیجه است.
-2 الگوریتم پیشنهادی
در روش پیشنهادی از مزایای تئوری آشوب و الگوریتم ICA بهره گرفته خواهد شد؛ به طوری که معایب الگوریتمها پوشش داده خواهد شد. در واقع هدف ارائه راهکاری است که توسط آن دادهها را با حداقل خطا خوشهبندی نمود. زمانی خوشهبندی ایدهآل میسر میگردد و هدف نهایی برآورده خواهد شد؛ که حداقل شباهت بین دادههای موجود در دستههای مجزا، همچنین حداکثر شباهت بین دادههای موجود در یک د سته برقرار با شد. در این راستا، روش k-means علیرغم معایبش - وابستگی به شرایط اولیه، همگرایی به نقاط بهینه محلی - ، به دلیل سادگی و سهولت شبیهسازی آن بسیار کاربرد دارد.جهت مرتفع نمودن این معایب، در تحقیقات اخیر ایدههای متفاوتی بیان گردیده است که تا حد قابل قبولی کارساز بوده است. در ادامه ترکیبی از الگوریتمICA و پدیده آشوب ارائه شده است.
در فرمول u - 1 - یک عدد تصادفی در محدوده 1]و[0 است. در الگوریتم رقابت استعماری تا از بهترین اعضای جمعیت - ک شورهای دارای کمترین مقدار تابع هزینه - را به عنوان امپریالیست انتخاب میکنیم. با قیمانده تا کشورها، مستعمراتی را تشکیل میدهند که هر کدام به یک امپراطوری تعلق دارند. برای تق سیم م ستعمرات اولیه بین امپریالی ستها، به هر امپریالیست، تعدادی از مستعمرات را که این تعداد متناسب با قدرت آن است، میدهیم. برای انجام اینکار، با داشتن هزینه همه امپریالیستها، هزینه نرمالیزه شده آنها را به صورت زیر در نظر میگیریم:
که در فرمول - 2 - هزینه امپریالیست -ام، max{ } بیشترین هزینه میان امپریالیستها و هزینه نرمالیزه شده این امپریالیست میباشد. هر امپریالیستی که دارای هرینه بیشتری باشد - امپریالیست ضعیفتری باشد - ، دارای هزینه نرمالیزه کمتری خواهد بود. با داشتن هزینه نرمالیزه، ندرت نسبی نرمالیزهی هر امپریالیست، به صورت زیر محاسبه شده و بر مبنای آن، کشورهای مستعمره، بین امپریالیستها تقسیم میشوند:
از یک دید دیگر، قدرت نرمالیزه شده یک امپریالیست، نسبت مستعمراتی است که توسط آن امپریالیست اداره میشود. بنابراین، تعداد اولیهی مستعمرات تمام امپریالیست برابر خواهد بود با: که در فرمول - 5 - ، تعداد اولیه مستعمرات یک امپراطوری و تعداد کل کشورهای مستعمره موجود در جمعیت کشورهای اولیه است. نیز تابعی است که نزدیکترین عدد صحیح به یک عدد اعشاری را میدهد.پس از شکلگیری امپراطوریها رقابت بین کشورها آغاز می شود. ابتدا، م ستعمرات در هر یک از امپراطوریها شروع به حرکت به سمت دولت امپریالی ستی مربوطه کرده و به موقعیت جدید تغییر مکان میدهند. در طول حرکت اگر هزینه مستعمره از امپریالی ست خود بی شتر با شد موقعیتهای آنها تغییر میکند. سپس الگوریتم با امپریالیست جدید ادامه مییابد. قدرت هر امپراطوری با استفاده از تابع هزینه امپریالیست و مستعمرات آنها ساخته میشود که فرمول آن در ادامه آمده است:
در جریان رقابتهای امپریالیستی، خواه ناخواه امپراطوریهای ضعیف به تدریج سقوط کرده و مستعمراتشان به دست امپراطوری های قویتر میافتد. الگوریتم تا برآورده شدن یک شرط همگرایی و یا تا اتمام تعداد کل تکرارها، ادامه مییابد. پس از مدتی، همه امپراطوریها، سقوط کرده و تنها یک امپراطوری خوااهیم داشت و بقیه کشورها تحت کنترل این امپراطوری واحد، قرار میگیرند .[13-12] با ترکیب ICA و آ شوب نیز 3 الگوریتم پی شنهادی Chaotic ICA، CGA رائه شده است. الگوریتم Chaotic ICA جمعیت اول یه و ت مامی مول فه های تصادفی موجود در الگوریتم ICA، همچون رقابت امپریالیستها و انقلاب - حرکت مستعمرات به سمت امپریالیست جدید - با استفاده از فرمول - 1 - به فرمت آ شوبگونه تبدیل شده اند. در الگوریتم CICA فقط جمعیت اولیه با استفاده از فرمول - 1 - به صورت آشوبگونه تولبد میگردد.
در فرمول - 6 - هزینه کل n امین امپراطوری است.یک ضریب تضعیف برای کاهش تاثیر هزیته مستعمرات است رقابت میان امپراطوریها بخش مهمی از ICA است. این رقابت براساس قدرت امپراطوریها است. در این حالت امپراطوری که ضعیفتر از دیگر امپراطوریها است مستعمرات خود را تا زمانی که هیچ م ستعمره دیگری ندا شته با شد از د ست میدهد. نتایج این عمل باعث انقراض امپراطوری ضعیف می شود. پس از آن امپریالیست ضعیف بهعنوان مستعمره بهترین امپراطوری درنظر گرفته میشود. در فرمول - 7 - ، . هرینه کل نرمالیزه شده امپراطوریام است و احتمال تصاحب مستعمره توسط هر امپراطوری است که در فرمول - 8 - آمده است. با داشتن احتمال تصاحب هر امپراطوری، مکانیزمی همانند چرخ رولت در الگوریتم ژنتیک مورد نیاز ا ست تا م ستعمره مورد رقابت را با احتمال متناسب با قدرت امپراطوریها در اختیار یکی از آنها قرار دهد.
-3 نتایج شبیه سازی
-1-3 مجموعه داده
به منظور سنجش روشهای پیشنهادی از مجموعه دادههای واقعی موجود در بانک اطلاعاتی UCI ا ستفاده شده ا ست .[14] در جدول 1 خلاصهای از ویژگی های مجموعه داده های مورد استفاده در این مقاله نشان داده شده است.
-2-3 پارامترها
در ت مام الگوریتم ها ت عداد جمع یت اول یه 200 و ت عداد تکرارهای اصلی الگوریتمها 100 در نظر گرفته شده است ابعاد هر یک از افراد جمعیت است که با توجه به مجموعه دادههای متفاوت تغییر میکند. ابعاد هر ذره در ادامه نشان داده شده است:
