بخشی از مقاله
چكیده
خوشهبندی دادهها به عنوان یكی از روشهای دسته بندی در حوزه های گوناگونی مانند پزشكی، آموزش و مهندسی کاربرد د ارد. یكی از روشهای موجود در این زمینه الگوریتم k-means میباشد، اگرچه الگوریتم از سرعت باالیی برخوردار است، اما وابسته به مراکز خوشه اولیه و امكان همگرایی به نقاط بهینه محلی وجود دارد. اخیرا الگوریتمهای بهینهسازی برای خوشهبندی با هدف یافتن مراکز بهینه به کمک توابع هدف متفاوت استفاده میشوند. در این مقاله یک الگوریتم ترکیبی جدید برای خوشهبندی دادهها با استفاده از الگوریتم فاخته والگوریتم ژنتیک پیشنهاد میدهیم. هدف از ترکیب الگوریتمها پیدا کردن مراکز بهینه برای دستهبندی دادهها و حل مشكالت موجود در الگوریتمk- means میباشد. کارایی الگوریتم پیشنهادی بر روی مجموعه داده استانداردUCI ارزیابی شد. نتایج شبیه سازی نشان میدهدکه ترکیب این دو الگوریتم نسبت به اجرای منفرد آنها و همچنین نسبت به سایر روشهای مورد مقایسه عملكرد بهتری را دارد.
کلمات کلیدی:خوشه بندی داده، الگوریتم بهینهسازی فاخته، الگوریتم ژنتیک، مجموعه داده.
-1 مقدمه
خوشهبندی به عنوان یكی از روشهای دستهبندی غیرنظارتی الگوها از اهمیت باالیی در تحلیل و پایش دادهها برخووردار موی باشود. حووزهی کاربرد دستهبندی بسیار وسیع میباشد به طوریكه علوم زیستشناسی و عكس برداریهای پزشكی تا کاربردهای نظامی و باسوتان شناسوی را دربرمیگیرد.]1[با توجه بوه حساسویتهوا و محودودیتهوای موجوود در برخوی از کاربردهای اشاره شده - ماننود کاربردهوای پزشوكی و نظوامی امكوان دستیابی به دادههایی با کالس مشخص برای به کارگیری درروشهوای دستهبندی نظارتی به راحتی امكان پذیر نمیباشد. اگر چه دسته بندی یک ابزار مفید برای متمایز کردن گروههای داده است اموا زموانی کوه برای مجموعه حجیمی از رکوردهای آموزشی به کار گرفته مویشوودفرایندی زمانبر و پرهزینه خواهد بود.
با توجوه بوه موارداشواره شوده، مساله خوشهبندی به عنوان ابزاری جهت تحلیل الگوهوا، دسوتهبنودی اطالعات، تصمیم گیری و استخراج و بازیوابی اطالعوات در دهوههوای اخیر توجه بسیاری از محققین را به خود جلب کورده و در ایون مودت روشها و دیدگاههای مختلفوی نیوز ارایوه شوده اسوت. هریوک از ایون روشها برپایهی معیارهای خاصی قرار گرفتوه و دارا ی مزایوا و معوایبی میباشد، به طوریكه میتوان گفت تاکنون یک روش و معیار جامع برای خوشهبندی بهینهی تمام انواع اطالعات ارایه نشده است.]1[یكی از الگوریتمهای هوش جمعی، الگوریتم کرمشب تاب میباشد کوه این الگوریتم را به صورت ترکیبی بوا الگووریتم تكواملی تفاضولی موورد استفاده قرار دادهاند ابتدا تعداداعضای جمعیت به صورت صعودی مرتب میشوند سپس بین هر دو الگوریتم تقسویم مویشووند.]2[
در تالشوی دیگر الگوریتم تكاملی تفاضلی برای مساله خوشه بندی به کار برده شدبا استفاده از توابع هزینهی متفاوت مورد ارزیابی قرار گرفوت بوه دلیول انعطافپذیری و خودسازمانده بودن الگوریتمهای هوشجمعی، آن را با الگوریتم خوشهبندی k-meansنیز ترکیب کرده و نتایج، بهبود کوارایی خوشهبندی را نشان میدهود. ]3[ تانو و همكوارانش ]4[ روشوی بور اساس الگوریتم جستجوی فاخته ارائه داده انود. از الگووریتم ژنتیوک و ترکیب آن با الگوریتم k-meansروشی جدید ابداع شد که برای کاهش پیچیدگی زمانی تابع برازندگی، ابتودا مراکوز هموه خوشوههاشناسوایی میشود.]5[ امیری و همكارانش ]6[ بوا اسوتفاده از الگووریتم فاختوه و فاخته فازی روشی ارائه کردهاند که با منطق فازی توالش بورای بهبوود راهحل های تولید شده توسط الگوریتم فاخته را دنبال میکنود. بوایر و همكارانش با ترکیب الگوریتمهای جستجوی فاخته و الگوریتم تكواملی تفاضلی تالش کردهاند تا از مزیت هردو الگوریتم بهورهمنود شووند و در نهایت نتایج کار خود را با چندین الگووریتم دیگور موورد مقایسوه قورار دادهاند.]7[
بابردل بناب و همكوارانش ]8[ روشوی براسواس الگووریتم مرکزدهی اولیه خوشه، الگوریتم زنبورعسل و الگوریتم تكاملی تفاضولی ارائه کرده و با استفاده از چندین مجموعه داده به ارزیابی کوارایی آنهوا پرداختهاند.در این مقاله به منظور غلبه بر مشكالت k-means، به ویژه در دام بهینه محلی، یک روش ترکیبی با استفاده از الگوریتم ژنتیک و الگوریتم بهینهسازی فاخته پیشنهاد شده است. پنج مجموعهدادهiris ، cmc ،glass ،wineو cancer نیز برای ارزیابی مورد استفاد ه قرار گر فته است. نتایج حاصل از این الگوریتم با نتایج حاصل از الگوریتم ژنتیک و الگوریتم بهینهسازی فاخته مورد مقایسه قرار میگیرد. همچنین خطای خوشهبندی برای این الگوریتم محاسبه شده و با الگوریتمهای CS,PSO,GSA,DE,BLACK holeوHCSDE مورد بررسی و مقایسه قرار میگیرد.]7[ در اد امه در بخش 2به تعریف خوشهبندی و در بخش3به الگوریتمهای مورد استفاده پرداخته شده است. در بخش 4 الگوریتم پیشنهادی جهت حل مساله خوشهبندی دادهها ارائه خواهد گردید. در بخش 5 نتایج شبیهسازی آورده شده است، در بخش 6 نتیجه گیری نهایی را خواهیم داشت.
-2 مسئله خوشهبندی
خوشهبندی به تقسیمبندی داده به گروههایی با اشیاء مشابه گفته میشود. به چنین گروههایی خوشه میگویند. در واقع اصطالح خوشوه نشان دهنده یک زیرمجموعه از اشیاء دادهای است کوه بسویار بوه هوم شبیهند و به سایر اشیاء دادهای بیشباهتند. خوشهبندی را میتوان بوه عنوان مهمترین مسئله در یادگیری بدون ناظر در نظور گرفوت. هودف اصلی هم در تحلیل خوشهای و هم در یادگیری بدون نواظر جداسوازی یک مجموعه داده به تعدادی خوشه - یوا گوروه بوا بوه کوارگیری یوک الگوریتم ریاضی است. یكی از مسوایل مهوم در فراینود خوشوهبنود ی تعیین معیاری برای محاسبه فاصله میان دادههاست. معیاری مختلفوی برای انودازهگیوری فاصوله بوین اشویا وجوود دارد کوه ازمعموولتورین وپرکاربردترین آنها میتوان فاصله اقلیدسی را نام برد. فاصله اقلیدسی برای دو نقطه x,y در فضای n بعدی از رابطه 1 - به دست میآید.
دراین مقاله نیز از معیار فاصله اقلیدسی برای اندازهگیری شباهت میان نمونهها استفاده مینماییم. یكی از الگوریتمهای معروف در حول مسئله خوشهبندی دادهها الگوریتم k-means میباشود. دلیول آن نیوز سادگی پیاده سازی و دام بهینه محلی میبلشد. در این الگوریتم هودف یافتن kمرکز خوشه می باشد. به نحووی کوه ایون مرتواکز بوه صوورتی انتخاب شوند که پس از تخصیص n نمونه به یكی از k خوشه از طریق اندازه گیری فاصله اقلیدسی، تابع هزینه کمینه شود.با وجود مزیتهوای الگووریتم k-means بوه دلیول وابسوتگی بوه مقداردهی اولیه مراکز و همچنین گیر افتوادن در دام بهینوه محلوی، از حل بسیاری از مسائل نتایج خوبی را ارائه نمی دهد.
-3 الگوریتمهای تكاملی مورد استفاده در روش پیشنهادی
-3-1 الگوریتم ژنتیک
الگوریتم ژنتیک را میتوان یک روش جستجوی کلی امید که از قوانین تكامل طبیعی تقلید مویکنود. ایون رو ش اولوین بوار در سوال 1970 توسط جان هولند - John Holland معرفی شد.]9[ یک GA برای حل یک مسئله، مجموعوه بسویار بزرگوی از راهحولهوای ممكون را تولیود میکند.به طور کلی الگوریتمهای ژنتیكی از اجزای زیر تشكیل شده است:
کروموزوم: هر کروموزوم نشان دهنده یک راهحل ممكون بورای مسوئله موردنظر است.
جمعیت: مجموعهای از کروموزومها یک جمعیت را تشكیل میدهند. با تاثیر عملگرهای ژنتیكی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشكیل خواهد شد.
تابع برازش: روشی برای انودازهگیوری میوزان برازنودگی هور عضوو از جمعیت اولیه با جوابهای جدید میباشد.
انتخاب: فرایندی برای گزینش کروموزومهای مناسوب جهوت تولیود و ترکیب مجدد است.
عملگرهای ژنتیک: برای تولید اعضای جدید و تكامل تدریجی بوه کوار میروند و عبارتند از ترکیب، جهش و بازتولید.
پس از مراحل فوق، جمعیت جدیدی جایگزین جمعیت پیشین میشود و این چرخه ادامه می یابد. هنگامی جستجو نتیجه بخش خواهود بوود که به حداکثر نسل موورد نظور رسویده باشود و یوا همگرایوی حاصول شدهباشد، یا زمان اجرای برنامه از یک مقدار معینی تجاوز کند و یوا بوا گذشت چند نسل، بهبودی در لیاقت جمعیت ایجاد شود.
-3-2 الگوریتم بهینه سازی فاخته
الگوریتم بهینهسازی فاخته COA - ارائه شده توسط رجبیون در سال ]10[ 2011، از روش زندگی پرندهای بنام فاختوه الهوام گرفتوه شوده است. روش زندگی و تخم گذاری جالب این پرنده ایوده یوک الگووریتم بهینه سازی جالب شده است. روشی که با کمترین تالش، درجن بورا بقاء با سایر حیوانات، به بقاء این این پرنده به زیبایی هر چه تمام تور سایر پرندگان را مجبور به شرکت در بقای خود مویکنود. زنودگی فاخته ها یک زندگی همراه با قتول و فریبكواری اسوت هماننود سوایر الگوریتمهای تكاملی، الگوریتم بهینهسازی فاختوه نیوز بایوک جمعیوت اولیه کار خود را آغاز میکند. جمعیتی متشوكل از فاختوههوا تعودادی تخمدارند که آنها را در النه تعدادی پرنده میزبوان خواهنود گذاشوت.
تعدادی از این تخمها که شباهت بیشتری به تخمهوای پرنوده میزبوان دارند شانس بیشتری برای رشد و تبدیل شدن به فاخته بوال خواهنود داشت، سایر تخمهوا توسوط پرنوده میزبوان شناسوایی شوده و از بوین میروند. میزان تخمهای رشد کرده مناسب بودن النههای آن منطقه را نشان میدهند. هرچه تخمهای بیشتری در یک ناحیه قادر بوه زیسوت باشند ونجات یابند به همان اندازه سود بیشتری به آن ناحیه اختصاص مییابد. بنابراین موقعیتی که درآن بیشترین تعداد تخمها نجوات یابنود پارامتری خواهد بود که COAقصد بهینهسازی آن را دارد.در طبیعت هر فاخته بین 5 تا20تخم میگذارد، این اعداد بوه عنووان حد باال و حد پایین تخصیص تخم به هر فاخته در تكرارهوای مختلوف استفاده میشود.
دیگر عادت هر فاخته حقیقی این است که آنها در یک دامنه مشخص تخمگذاری میکنند، این دامنه را شعاع تخمگذاری ELR - مینوامیم. در یک مسئله بهینهسازی به حودباالی متییرهوا varlsmhiو varlow گفته میشود. هر فلخته دارای ELR ای خواهد بوود کوه متناسوب بوا تعداد کل تخم ها، تعداد تخمهای فعلی فاخته و همچنین حدباال و حد پایین متییرهای مسئله اسوت. بنوابراین ELR بوه صوورت معادلوه 2 - تعریف میشود:آلفا متییری است که حداکثر مقدار ELR را با آن تنظیم میکنیم.فاخته برای بیشینه کردن نجات تخمهای خود دنبال بهترین منطقه میگردند. پس از آنكه جوجهها از تخم بیرون آمدند و تبدیل به فاخته بال شدند، جوامع و گروههایی تشكیل میدهند.
هر گروه منطقه سكونت خود را برای زیست دارد. بهترین منطقه سكونت مقصد بعدی تمام گروههاخواهد بود. تمام فاختهها به سمت بهترین منطقه موجود فعلی مهاجرت می کنند. هر گروه در منطقهای نزدیک بهترین موقعیت فعلی ساکن میشود. با در نظر گرفتن تعداد تخمی که هر فاخته خواهد گذاشت و همچنین فاصله فاختهها از منطقه بهینه فعلی برای سكونت، تعدادی شعاع تخمگذاری با استفاده از فرمول . 2 - سپس فاختهها شروع به تخمگذاری تصادفی در النههایی داخل شعاع مربوطه خود میکنند.این پروسه تا رسیدن به بهترین محل برای تخمگذاری ادامه مییابد. این محل بهینه جایی است که بیشترین تعداد فاختهها درآن گرد میآیند.]10[شبه کد الگوریتم COA در شكل 1 نمایش داده شده است:
