روشی جدید در خوشه بندی اطلاعات با استفاده ازترکیب الگوریتم کشورهای استعماری و k-means – پایان نامه

خانم الهه طاهریان فرد، در پایان نامه کارشانسی ارشد خود در دانشگاه شیراز زیر نظر دکتر نیکنام و دکتر روستا، با ترکیب الگوریتم رقابت استعماری و روش k-means، روش جدید و کارآمدی برای خوشه یابی (کلاسترینگ – Clustering)، معرفی کرده است. نتایج حاصل از این کار پژوهشی در قالب چندین مقاله در معتبرترین ژورنالهای مرتبط با این حوزه منتشر شده اند. در ادامه این پست، بخشهای خلاصه شده ای از متن پایان نامه ایشان را برای علاقه مندان وبسایت محاسبات تکاملی منتشر می کنیم.

چکیده

امروزه، خوشه بندی نقش مهی را در اغلب زمینه‌های تحقیقاتی مانند مهندسی، پزشکی، زیست‌شناسی، داده کاوی و… ایفا می‌نماید. در واقع خوشـه بندی به معنای تقسیم بندی بدون نظارت می‌ باشد؛ با استفاده از آن داده‌ها به دسته‌هایی که از نظر پارامـترهای مورد علاقه، شباهـت بیشتری به یکدیگر دارند، تقسـیم می‌گردند. یکی از روش‌های معـروف در این زمینه k-means می‌باشد؛ که علی رغم وابستگی به شرایط اولیه وهمگرائی به نقاط بهیـــنه محلی، تعداد N داده را به k خوشه با سرعت بالا، دسته بندی می‌نماید. در این رساله جهت رفع مشکلات موجود از روش ترکیبی مبتنی بر الگوریتم رقابت کشــــورهای استعماری و k-means بهره گرفته خواهد شد؛ که علاوه بر رفع مشکلات ذکر شده، مستقل از تعداد متغیر‌ها نیز خواهد بود. در این رساله به منظور اعتبارسنجی، روش پیشنهادی بر روی چندین داده متفاوت مشهور پیاده سازی می‌گردد و نتــایج با روش‌های الگوریتم ژنتیک، مورچگان، اجتماع ذرات، جفت گیری زنبور عسل، آبکاری فولاد و k-means مقایسه خواهد گردید. توانایی بالا و مقاوم بودن این روش بر اساس نتایج مشهود خواهد بود.مقدمه 

پردازش داده، یکی از شاخص‌های بسیار مهم در دنیای اطلاعات است. خوشه بندی یکی از بهترین روش‌هایی است که برای کار با داده‌ها ارائه شده است. خوشه بندی قابلیت ورود به فضای داده و تشخیص ساختارش را امکان پذیر می‌نماید. لذا به عنوان یکی از ایده آل‌ترین مکانیزم‌ها، برای کار با دنیای عظیم داده‌ها محسوب می‌شود.

خوشه بندی، یافتن ساختاری در مجوعه‌ای از داده‌ها است که طبقه بندی نشده‌اند. به بیان دیگر می‌ توان گفت که خوشه بندی قراردادن داده‌ها در گروه‌هایی است که اعضای هر گروه از زاویه خاصی شبیه یکدیگرند. در نتیجه شباهت بین داده‌های درون هر خوشه حداکثر و شباهت بین داده‌های درون خوشه های متفاوت حداقل می‌باشد. معیار شباهت در اینجا، فاصله بوده یعنی نمونه‌هایی که به یکدیگر نزدیکترند در یک خوشه قرار می‌گیرند. به عنوان نمونه در خوشه بندی اسناد دوری و یا نزدیکی داده‌ها متناسب با تعداد کلمه‌های مشترکی که در دو سند وجود دارد و یا در خوشه بندی سبد خرید مشتریان، فاصله بر اساس شباهت خرید تعیین می‌شود. لذا محاسبه فاصله بین دو داده در خوشه بندی بسیار مهم می‌باشد؛ زیرا کیفیت نتایج نهایی را دستخوش تغیر قرار خواهد داد.

فاصله که‌‌ همان معرف عدم تجانس است حرکت در فضای داده‌ها را می‌سازد وسبب ایجاد خوشه‌ها می‌گردد. با محاسبه فاصله بین دو داده می‌توان فهمید که چقدر این دو داده به هم نزدیک هستند و بر این اساس در یک خوشه قرار داده می‌شود. توابع ریاضی مختلفی برای محاسبه فاصله وجود دارند؛ فاصله افلیدسی، فاصله همینگ و….هدف تحقیق
هدف در این تحقیق این است که با بررسی الگوریتم‌های موجود در زمینه خوشه بندی، الگوریتمی را که تا‌حد قابل قبولی بتواند محدودیت‌های موجود را پوشش دهد، ارائه گردد. از نمونه محدودیت‌های موجود می‌توان موارد زیر را برشمرد:

گفتارهای پایان نامه
این پایان نامه بصورت زیر تنظیم شده است.

در ادامه، فصل چهارم که در واقع کارر پیشنهادی این پایان نامه می‌باشد و فصل پنجم نتیجه گیری آورده شده است.4-2 روش‌های متفاوت ترکیب الگوریتم پیشنهادی
در این بخش ابتدا به طور اجمالی روش‌های موجود تشریح می‌گردد، سپس به تفصیل در مورد تکنیک‌های ترکیب آن‌ها توضیحات لازم ارائه خواهد گردید.

4-2-1 خوشه بندی اطلاعات به روش ترکیبی MICA-k
ابتدا جمعیت اولیه به صورت تصادفی تولید می‌گردد؛ الگوریتم رقابت کشورهای استعماری توسعه یافته بر روی این جمعیت تولید شده، شروع به کار می‌نماید و تا جایی ادامه می‌یابد که تنها یک عضو به عنوان بهترین باقی بماند. جواب نهایی، به عنوان مقدار اولیه الگوریتم k-means در نظر گرفــته می‌-شود. دراین روش به دلیــل انتخاب مناسب مقدار اولیـــه برای الگوریتم k-means، جواب بهتـری حاصـل می‌گردد. این روش که به اختـصار MICA-k نامیـده می‌شود، شکل ۴-۱ کد الگوریتم را نشان می‌دهد.

4-2-2 خوشه بندی اطلاعات به روش ترکیبی k-MICA
در این روش بعد از تولید جمعیت اولیه به صورت تصادفی، الگوریتم k-means بر روی داده‌های موجود اجرا می‌گردد. بنا به تعداد جمعیت مورد نظر، در تکرارهای متوالی مراکز خوشه بدست خواهد آمد؛ که به عنوان جمعیت اولیه الگوریتم رقابت کشورهای استعماری توسعه یافته در نظر گرفته خواهد شد و با این فرض الگوریتم موجود ادامه می‌یابد. به اختصار این روش k-MICA نامگذاری می‌گردد. شکل ۴-۲ فلوچارت مراحل کار را نشان می‌دهد.

4-2-3 خوشه بندی اطلاعات به روش Hybrid k-MICA
در حالت آخر، الگوریتم رقابت کشورهای استعماری توسعه یافته بر روی جمعیت تصادفی انتخاب شده آغاز می‌گردد؛ باید متذکر شد که در این روش، قبل از حرکت مستعمره به سمت استعمارگر، الگوریتم k-means روی تمام اعضا جهت بهبود عملکرد اجرا می‌گردد. این مسئــله باعث می‌شود امپراطور و مستعمره در موقعیت مناسب تری قرار گیرند. در ‌‌نهایت الگوریتم بهبود یافته رقابت کشورهای استعماری تایافتن جواب بهینه ادامه خواهد یافت.

یک تغیر دیگر که در الگوریتم پیشنهادی انجام گرفته است این می‌باشد که ضعیف‌ترین امپراطوری بعد از اینکه کل مستعــمرات خود را در روند رقابت از دست داد، خودش نابود نمی‌گردد؛ بلکه به عنوان مستعمره، قوی‌ترین امپراطور در نظر گرفته می‌شود. روش آخر، مطلوب‌ترین حالت به شمار می‌آید. در ادامه به تفصیل این روش تشریح خواهد شد.

4-3 خوشه بندی اطلاعات مبنی بر روش ترکیبی پیشنهادی
در این روش کاربرد الگوریتم پیشنهادی که مبتنی بر ترکیب الگوریتم بهبود یافته رقابت کشورهای استعماری و k-means می‌باشد جهت خوشه بندی اطلاعات توضیح داده خواهد شد. هدف این است که داده‌های موجود در خوشه‌های مناسب دسته بندی شده و در این راستا نیز مراکز خوشه تعیین گردند.

4-6-1-1 مجموعه داده Iris
این مجموعه در واقع مجموعه‌ای از داده‌ها می‌باشد که شامل سه نمونه گل زنبق است؛ که توسط فیشر در سال ۱۹۳۶، برای نشان دادن تکنیک‌های خطی تفکیک پذیر معرفی گردید. از این رو به نام مجموعه داده گل زنبق فیشر نیز خوانده می‌شود. از طرف دیگر، به دلیل اینکه ادگار اندرسون نیز این مجموعه را به دلیل کیفیت تنوع جغرافیایی در شبه جزیره گاسپه، گردآوری کرده است، به مجموعه داده زنبق اندرسون نیز مشهور می‌باشد.

این مجموعه شامل ۵۰ نمونه از سه نوع گل زنبق با نام‌های سیتوسا، وریجینیکا و ورسیکولار می‌باشد. شاخصه‌هایی که در این مجموعه جهت اندازه گیری مدنظر می‌باشند؛ پهنای گلبرگ، طول گلبرگ، پهنای کاسبرگ و طول کاسبرگ [۴۹]، [۵۰]، [۵۱].

شکل ‏۴ ۵ مشخصه همگرایی بهترین جواب MICA-k و Hybrid k-MICA برای مجموعه داده Iris.

 

امروزه کاربرد داده کاوی در اکثر علوم به طور چشم گیر مشاهده می‌گردد. واضح است در صورتی که بستر مناسبی جهت استفاده از این علم مهیا نگردد، از تکنولوژی روز و بهره گیری از پیشرفت‌های به دست آمده دور خواهیم ماند.

خوشه بندی یکی از ابزار داده کاوی محسوب می‌گردد لذا سهم به سزای از تحقیقات اخیر معطوف به این روش می‌باشد. الگوریتـم k-means که جزء روش هـای خوشـه بندی افـرازی به حساب می‌آید. در نتیجه از آن برای نیل به اهداف این پایان نامه مورد استفاده قرار گرفت. الگوریتم k-means به عنوان یادگیری بدون نظارت می‌باشد که تعداد خوشه‌ها از قبل تعیین نشده‌اند و خوشه‌ها با یکدیگر فصل مشترکی ندارند.

در صورتی که مقدار اولیه برای الگوریتم k-means مناسب انتخاب گردد باز هم امکان همگرایی به نقاط بهینه وجود دارد. لذا با بهره گیری از الگوریـتم رقابت کـشورهای استعماری به عنوان روش بهینه-سازی نوین، این محدودیت مرتفع گردید. قابل توجه است که نسخه اصل الگوریتم رقابت کشورهای استعماری به تنهایی در رفع این مشکل کارساز نبود. بنابراین از ایده روش بهینه سازی تفاضلی استفاده گردید و عملکرد این الگوریتم را بهبود بخشیدیم. در نتیجه احتمال همگرایی به نقاط بهینه کاهش یافت. روند عملگر جهش، قبل از حرکت مستعمره به سمت استعمارگر اتفاق افتد. در صورتی که مستعمره جدید بوجود آمده نسبت به مستعمره قبل وضعیت بهتری را دارا بود جایگزین می‌گردید و در غیر این صورت‌‌ همان مستعمره قبل باقی می‌ماند. یکی دیگر از تغیراتی که باعث افزایش کارایی این الگوریتم گردید نحوه اختصاص مستعمـرات به استعمارگر در روند تشکـیل امپراطوری بود. اختصاص مستعمره به استعمارگر بر اساس قدرت امپراطور انجام نگرفت لذا مستعمراتی که قدرت بیشتر را دارا بودند لزوماً به استعمارگر قوی‌تر تخصیص داده نشدند. بلکه مستعمرات به روشی که مرتب گردیده بودند، به ترتیب جز قلمرو استعمارگر‌ها قرار گرفتند. این رویکرد نیز سبب گردید تا پاسخ نهایی الگوریتم روندی رو به رشد را طی نماید.

به این صورت نتایج به دست آمده از ترکیب این دو الگوریتم علاوه بر نوآوری، محدودیت‌ها را پوشش داد. با توجه به مقایسه نتایج و اعتبارسنجی آن به وسیله روش T-test مقاوم بودن و کارایی این روش تضمین گردید.

با توجه به شبیه سازی‌های انجام گرفته در اغلب موارد روش آخر بهترین جواب را با حداکثر دقت و سرعت نتیجه می‌دهد. در این روش‌های ترکیبی، علاوه براینکه محدودیت وابستگی به شرایط اولیه تاحدود بسیار زیادی خنثی گردیده است؛ مشکل همگرایی دائمی به پاسخ بهینه محلی نیز تا حد قابل قبولی از بین رفته است.

شبیه سازی بر روی مجموعه داده‌های متنوع اجرا گردیده است لذا پاسخ‌های نهایی به دست آمده گویای این مطلب می‌باشد که، وابستگی به تعداد نمونه‌ها، تعداد خوشه‌ها و تعداد پارامتر‌ها وجود ندارد و الگوریتم ترکیبی عملکرد مناسبی دارد. لذا این الگوریتم را می‌توان بر مجموعه داده‌ها مشابه اعمال نمود و نتیجه مناسب را به دست آورد.

عدم وابستگی الگوریتـم به پارامترهای موجود،، یکــی دیگر از برتری‌های روش ارائه شده می‌باشد. همچنین با توجه به اجرای الگوریتم پیشنهادی روی تمام مجموعه داده‌ها، مقادیر به دست آمده برای انحراف معیار حاکی ازاین است که، داده‌های هر خوشه به نحو مناسبی، توزیع گردیده‌اند.

با توجه به مقدار سطح معنی دار بودن در روشT-test، ادعای اینکه پاسخ نهایی به دلیل ماهیت تصادفی مسئله به دست آمده (فرض صفر) رد شد. لذا وابستگی پاسخ نهایی به ماهیت تصادفی مسئله، لغو گردید.

Title: Human Socio-political Evolution and Imperialistic Competitive Algorithm Application in Optimize the Huge-Combinatorial problem
Authors: Taher Niknam, ElaheTaherianFard, NargesPourjafarian, AlirezaRousta
Publication Year: 2011
Journal Title: Engineering ApplicationsofArtificialIntelligence24(2011)306–317
Paper download links: Science Direct (+)

اگر به لینک دانلود فوق دسترسی ندارید، به بخش مقالات سایت مراجعه نمایید.