2-3-3- یادگیری سیستم­های طبقه بندی کننده فازی با استفاده از الگوریتم ازدحام ذرات              24

 

 2-3-4- یادگیری سیستم­های طبقه بندی کننده فازی با استفاده از الگوریتم زنبور عسل……. 25

 

    2-3-5- یادگیری سیستم­های طبقه بندی کننده فازی با استفاده از الگوریتم مورچگان             26

 

 2-4- الگوریتم رقابت استعماری            26

 

     2-4-1- ویژگی­های الگوریتم رقابت استعماری            28

 

  2-4-2-کاربرد­های الگوریتم رقابت استعماری            28

 

. 2-5-جمع بندی            30

 

فصل سوم

 

3- روش تحقیق  32

 

 3-1- مقدمه            33

 

 3-2- سیستم­های فازی            34

 

  3-2-1- سیستم­های استنتاج فازی            34

 

   سیستم­های فازی Mamdani.. 34

 

سیستم­های فازی Sugeno…………. 35

 

    سیستم­های فازی Tsukamato… 35

 

  3-2-2- طبقه بندی کننده­های فازی            36

 

  تابع  استدلال فازی…….. 36

 

 معیار ارزیابی قوانین ……… 38                     

 

   3-3- الگوریتم CORE            39

 

3-4- الگوریتم جزیره ای Ishibuchi برای استخراج قوانین            39

 

 3-5- الگوریتم GBML-IVFS-amp            41

 

 3-6- الگوریتم GNP برای وزن­دهی به قوانین فازی            42

 

  3-7- الگوریتم TARGET            42

 

 3-8- الگوریتم SGERD            43

 

   3-9- الگوریتم رقابت استعماری            44

 

 3-9-1- مقدرادهی اولیه امپراطوری­ها            45

 

   3-9-2- عملگر Assimilation            46

 

  3-9-3- استراتژی­های بهینه سازی میتنی بر تکامل اجتماعی-سیاسی            47

 

   3-10- الگوریتم­های پیشنهادی            48

 

   3-10-1- هدف استفاده از ICA برای الگوریتم پیشنهادی            48

 

 3-10-2- وزن­دهی به قوانین فازی            48

 

3-10-3- الگوریتم پیشنهادی برای تکامل قوانین فازی…. 52

 

  قوانین خاص و عام…… 52

 

 روش پیشنهادی برای تولید قوانین فازی …….. 53

 

 تابع برازش پیشنهادی…….. 54

 

  3-11-جمع بندی            57

 

فصل چهارم

 

 نتایج آزمایشات.. 58

 

  4-1- معیار­های ارزیابی            59

 

 4-2-مجموعه داده­ها            60

 

  4-2-1-مجموعه داده KEEL            60

 

  4-2-2-مجموعه داده UCI            61

 

 4-3- الگوریتم پیشنهادی برای وزن­دهی به قوانین            61

 

  4-3-1-پارامتر­ها و تنظیمات سیستم در پیاده سازی            61

 

  4-3-2-مقایسه الگوریتم پیشنهادی با طبقه بندی کننده­های فازی            62

 

  4-3-3-مقایسه الگوریتم پیشنهادی با طبقه بندی کننده­های غیر فازی            66

 

 4-4- الگوریتم پیشنهادی برای تولید قوانین فازی بهینه            68

 

4-4-1-پارامتر­ها و تنظیمات سیستم در پیاده سازی یادگیری ساختار قوانین فازی            68

 

  4-4-2-انتخاب ویژگی            69

 

 4-4-3-ارزیابی الگوریتم یادگیری ساختار قوانین با روش­های فازی            70

 

.   4-4-4-ارزیابی الگوریتم با روش­های غیر فازی            72

 

.. 4-5- جمع بندی             73

 

فصل پنجم

 

 

جمع بندی و پیشنهادات………….. 76

 

اختصارات………….. 78

 

 واژه­نامه فارسی به انگلیسی……………………………… 79

 

واژه نامه انگلیسی به فارسی…………. 80

 

فهرست منابع………….82

 

 

1. مقدمه

    

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

 

 

• مقدمه

 

تاکنون دانشمندان حوزه داده کاوی تلاش­های بسیاری برای جدا­سازی صحیح نمونه­های مشابه کرده­اند. استخراج طبقه­بند­های عام[1] و قابل فهم از داده، نقش مهمی در بسیاری از حوزه­ها و مسائل است. تاکنون روش­های متعددی برای طبقه­بندی[2] و تشخیص الگو[3] معرفی شده­است. یکی از شیوه­های موفق و منحصربه­فرد در حوزه طبقه­بندی و تشخیص الگوی داده­های ورودی، استفاده از تکنیک­های فازی برای تقسیم­بندی نرم فضای ویژگی و بالطبع استفاده از یک معماری مؤثر در متصل کردن این زیر­فضاها برای تصمیم­گیری و طبقه­بندی به­صورت فازی می­باشد. طبقه­بندی فازی پروسه گروه بندی عناصر داخل مجموعه­های فازی با یک تابع عضویت[4] است[1]. در واقع، ابتدا فضای جستجو به بخش­هایی قسمت بندی می­شود به گونه ای که تمام فضا پوشش داده شود و سپس بر روی هرکدام از این زیر­فضا­ها مجموعه فازی قرار می­گیرد. اجتماعی از مجموعه­های فازی که فضای فازی نامیده می­شود، مقادیر زبانی فازی یا کلاس­های فازی را تعریف می­کند که یک شی می­تواند به آن­ها تعلق داشته باشد. پس از آن قوانین فازی اگر و آنگاه[5] با توجه به نحوه تخصیص تولید می­شوند. مدل­سازی سیستم­های فازی بصورت مجموعه­ای از این قوانین نمایش داده می­شود.

 

 

• انگیزه

 

 طبقه­بندی­کننده­های فازی دارای ویژگی منحصربفرد تفسیرپذیری هستند و قادرند دانش چگونگی تشخیص الگو­ها را برای یک فرد خبره بصورت یک دستورالعمل بازنمایی کنند. طبقه­بندی­کننده­های­ فازی چهار هدف اساسی را دنبال می­کنند. دقت طبقه­بندی­کننده را بیشینه کنند، طبقه­بندی­کننده­ی با بیش­ترین قابلیت تفسیر­پذیری را ایجاد نمایند، پایداری طبقه­بندی­کننده را بیشینه کنند و حساسیت به نویز را کاهش دهند. تاکنون روش­های متفاوتی برای ایجاد قوانین، نحوه تخصیص زیرفضاها، نحوه استنتاج در هر قانون و در نهایت ادغام قوانین ارائه­شده است. بدیهی است زبان طبیعی[6] محور بودن ساختار قوانین فازی علیرغم استخراج دانش، مشکل اثبات ریاضی کارایی طبقه­بندی­کننده از جمله ارائه یک کران­ بالا[7] برای خطای آموزش[8] و خطای تست[9] است. به­عبارتی افزایش عمومی­سازی[10] این طبقه­بندی­کننده­ها بصورت ریاضی مانند طبقه­بندی کننده تقویتی گروهی[11] کار بسیار دشواری است. از این­رو اغلب از روش­های مکاشفه­ای[12] و فوق مکاشفه­ای[13] به­صورت سعی و خطا در تدوین قوانین و ادغام آن­ها استفاده می­گردد، به این دلیل که زیرفضا را برای به­دست­آوردن بهترین ترکیب قوانین جستجو می­کنند [2]-[4] . ایشیبوشی[14][5] روشی را برای تخصیص فضا به­صورت تقسیم­بندی منظم و تکراری ارائه کرد که می­توان از این روش به­عنوان یکی از موثرترین روش­های طبقه­بندی­کننده فازی که مبنای بسیاری از تحقیقات بعدی در این زمینه نیز شد، نام برد.

 

 

• شرح مسئله

 

پروسه یادگیری یک سیستم طبقه­بندی فازی باید مسایل مختلفی را حل کند تا یک سیستم طبقه­بندی زبانی را با یک رفتار صحیح ایجاد نماید. از جمله اینکه بتواند، 1- مجموعه­ای از قوانین فازی را ایجاد کند که دارای یک سطح لازم همکاری بین این قوانین فازی باشد. 2- انتخاب یک تابع استنتاج که روشی را برای ترکیب اطلاعات به­دست آمده از قوانین فازی در کلاسه­بندی نمونه­ها انتخاب می­کند. 3- در مسایل با ابعاد بالا، قوانین فازی از رشد نمایی در سایزشان رنج می­برند. دو مسئله اول، مربوط به پروسه استخراج دانش می­شود که با پردازش­های یادگیری مختلف براساس الگوریتم­های تکرار­شونده  مانند شبکه­های عصبی مصنوعی[5-6] یا الگوریتم ژنتیک [2-4]قابل حل است. گزینه سوم از دو جهت می­توان مدیریت کرد: با فشرده­سازی و کاهش مجموعه قوانین، قوانین غیرضروری را با هدف ایجاد یک سیستم طبقه­بندی با کارایی بالاتر حذف کرد. و راهکار دوم با پروسه انتخاب ویژگی انجام می­گیرد.

 

به طور کلی، هدف مسئله، فراهم کردن یک چارچوب کلی برای تکامل قوانین فازی است. راهکار­های بسیاری در این زمینه ارائه شده، اما همه آن­ها حداقل در یکی از موارد زیر تفاوت دارند، تعداد قوانینی که در هر عضو جمعیت کد می­شود، نوع بیان قوانین کد­شده در هر عضو و نوع و هدف پروسه تکاملی .[7-8] این الگوریتم‌ها شامل الگوریتم‌های ژنتیک[15]، بهینه‌سازی گروه ذرات[16]، گداختگی شبیه‌سازی شده[17] و… می‌باشند.

 

از آنجایی که الگوریتم­های تکاملی[18] به­صورت چند­عاملی[19] جستجو را در فضای ویژگی انجام می­دهند، نحوه گردش آن­ها تا حد ممکن به­صورت تصادفی می­باشد. این خواص، الگوریتم­های تکاملی را به ابزار قوی برای انواع مسائل بهینه­سازی تبدیل نموده است.[2], [4]  از جمله مسائل مطرح در زمینه بهینه­سازی، بهینه­سازی ساختار و پارامتر­های طبقه­بندی­کننده­ها می­باشد. بدیهی است هرچه یک طبقه­بندی­کننده­ پارامتر­های بیش­تری داشته باشد، تنظیم بهینه این پارامتر­ها به­صورت دستی کاری بسیار دشوار، و در بعضی حالات­ غیرممکن می­باشد. بدین خاطر از الگوریتم­های تکاملی برای یادگیری پارامتر­ها و تعیین ساختار طبقه­بندی­کننده­های متفاوت به­صورت فراوان استفاده شده است. از جمله این تحقیقات می­توان به بهبود ساختار شبکه عصبی توسط الگوریتم ژنتیک اشاره کرد [9] که الگوریتم ژنتیک سعی در هرس کردن ارتباط بین نورون­ها و به­نوعی لایه­بندی آن­ها به منظور بهبود کارایی طبقه­بندی، دارد.

 

مزیت ترکیب قوانین فازی و الگوریتم­های تکاملی این است که مجموعه قوانین ایجاد­شده دارای تفسیر­پذیری بیش­تری هستند و می­توانند با عدم قطعیت[20] و ابهام مقابله کنند و همچنین می­توانند به صورت اکتشافی فضای ویژگی را جستجو کنند. به عنوان مثال در بخش ورودی نحوه تخصیص­بندی فضاها و همچنین تعیین پارامتر­های توابع عضویت (مانند شیب و واریانس)، از الگوریتم­های تکاملی استفاده شده است[10].

 

چالش­ها

 

با توجه به این که اغلب روشهای عمده و شناخته شده محاسبات تکاملی، شبیه‌سازی کامپیوتری فرایندهای طبیعی و زیستی هستند، در این نوشتار، از یک روش ترکیبی برای بهبود طبقه­بندی­کننده­های فازی ارائه می­شود که برای بهبود یادگیری پارامتر­های آن الگوریتم تکاملی رقابت استعماری [11] اقتباس شده است. این پایان­نامه، الگوریتم رقابت امپریالیستی [21]را برای هدف استخراج کلاسه­بند­های عام و قابل فهم از داده در شکل یک سیستم قانون ارائه می­کند. در این تحقیق سعی در ارائه ساختار جدیدی بر روی بستر فازی هستیم که در آن ساختار، توزیع قوانین از الگوریتم رقابت استعماری[22] اقتباس شده و لیکن روح قوانین به­صورت فازی است. ضمنأ به­دلیل ایجاد هارمونی مناسب در بهینه­سازی ساختار قوانین و همچنین ادغام قوانین، استفاده از الگوریتم بهینه­سازی رقابت استعماری پیشنهاد می­شود.

 

در این الگوریتم چند نمونه که دارای میزان برازندگی[23] بالایی می­باشند (امپریالیست[24]) و مرکز امپراطوری­ها هستند، سعی در کشاندن بقیه نمونه­ها (مستعمره)[25] به سمت خود دارند. این الگوریتم را می­توان نوع بهبود یافته الگوریتم ازدحام ذرات در نظر گرفت. لازم به ذکر است که الگوریتم ازدحام ذرات علیرغم سرعت همگرایی بالای آن، احتمال بایاس شدن آن بسیار زیاد می­باشد. چون میزان تصادفی بودن[26] آن در حین جستجو پایین بوده و بسیار بایاس­دار حرکت می­کند. درصورتیکه الگوریتم رقابت استعماری این مسئله را به این شیوه حل کرده است که هر نمونه به­جای حرکت در جهت برآیند دو نقطه با برازندگی­های مناسب، به یکی از چند نقطه­ای اختصاص داده می­شود که بهینه محلی (امپریالیست) اطلاق می­شوند.

 

 از آن­جا که ساختار این الگوریتم به­صورت چند­حوزه­ای می­باشد، بکارگیری آن برای ساختار­بندی قوانین فازی این خاصیت را به­همراه خواهد داشت که یک مجموعه قوانین بر روی یک زیرفضا کار کند نه تنها روی یک قانون. به­عبارت دیگر استفاده از یک قانون برای تصمیم­گیری درمورد یک زیرفضا حتی با داشتن هم­پوشانی[27] با زیرفضاهای همسایه باعث خاص[28] شدن آن قانون و به­نوعی بایاس قانون و آن زیرفضای خاص شده و در مورد سایر نمونه­هایی که دور از آن زیرفضا هستند، نمی­تواند تصمیم­گیری مناسبی را به­عمل آورد که همین امر باعث بیش­سازگاری[29]و کمبود عمومی­سازی توابع فازی می­گردد. در مقابل، الگوریتم یادگیری استعماری از تخصیص یک قانون به یک زیرفضای خاص جلوگیری کرده و حتی زیرفضاهایی که یک مستعمره از قوانین درباره آن تصمیم می­گیرند، دارای ابعاد بسیار وسیع­تری نسبت به زیرفضای تخصیص­شده به هر قانون در مقایسه با روش­های قبلی دارد. ضمنأ هنگامی­که قوانین به­صورت دسته­های مختلفی از مستعمره­های متفاوت بر روی کل فضا عمل می­کنند، می­توان آن را جزو الگوریتم­های توزیع­شده در نظر گرفت. توانایی بهینه­سازی این الگوریتم نسبت به الگوریتم­های بهینه­سازی پیشین هم­تراز و یا حتی بالاتر است و سرعت رسیدن به جواب بهینه نیز مناسب است.

 

اهداف پایان­نامه

 

در این رساله می­خواهیم یک مجموعه از قوانین انعطاف­پذیر فازی را با استفاده از الگوریتم رقابت استعماری که پیش از این ذکر شد، ایجاد نماییم. با این هدف که کارایی طبقه­بندی­کننده و تفسیر پذیری قوانین تولید شده حداکثر شود و در عین­حال نویز پذیری کمینه نسبت به طبقه­بندی­کننده­های آماری و نیز عمومی­سازی بسیار مناسبی را ارائه نماید. در واقع در این مسئله می­خواهیم مجموعه­ای از بهترین قوانین با انعطاف پذیری بالا که بیانگر انتخاب بهترین ویژگی­هاست را با استفاده از الگوریتم نوپای رقابت استعماری به­دست آوریم. نکته مهم در این رساله، نحوه تخصیص زیرفضا، ساخت قوانین و در نهایت ادغام آن­ها در یک پروسه بهینه­سازی استعماری است. به­طور­کلی در این پژوهش: