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

الگوریتم پیشنهادی با طبقه بندی کننده­ های پایه غیرفازی مانند SVM، C4.5، 1NN و Naive Bayes و الگوریتم­های طبقه بندی کننده فازی که توضیح داده خواهد شد مقایسه و ارزیابی می­ شود.

واژه­ های کلیدی: طبقه ­بندی، تشخیص الگو، الگوریتم رقابت استعماری، طبقه بندی کننده­ های فازی، طبقه بندی کننده­ های غیر فازی، وزن­دهی قوانین.

 فهرست مطالب

  عنوان             صفحه

فصل اول

1-مقدمه…. 2

   1-1- مقدمه……. 2

. 1-2- انگیزه            3

… 1-3- شرح مسئله            4

 1-4- چالش­ها            5

   1-5- اهداف پایان نامه……. 7

 فصل دوم.

2- پیشینه تحقیق. 9

2-1- مقدمه            10

 2-2- حوزه تکامل قوانین فازی            11

 2-3-یادگیری سیستم­های طبقه بندی کننده فازی            12

   2-3-1- یادگیری سیستم­های طبقه بندی کننده فازی بر اساس الگوریتم ژنتیک            12

 2-3-2- الگوریتم­های تکامل همزمان            22

  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]و کمبود عمومی­سازی توابع فازی می­گردد. در مقابل، الگوریتم یادگیری استعماری از تخصیص یک قانون به یک زیرفضای خاص جلوگیری کرده و حتی زیرفضاهایی که یک مستعمره از قوانین درباره آن تصمیم می­گیرند، دارای ابعاد بسیار وسیع­تری نسبت به زیرفضای تخصیص­شده به هر قانون در مقایسه با روش­های قبلی دارد. ضمنأ هنگامی­که قوانین به­صورت دسته­های مختلفی از مستعمره­های متفاوت بر روی کل فضا عمل می­ کنند، می­توان آن را جزو الگوریتم­های توزیع­شده در نظر گرفت. توانایی بهینه­سازی این الگوریتم نسبت به الگوریتم­های بهینه­سازی پیشین هم­تراز و یا حتی بالاتر است و سرعت رسیدن به جواب بهینه نیز مناسب است.

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

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

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

مطالب مربوط به این رساله در پنج فصل به شرح زیر می‌باشد.

فصل دوم. در این فصل تحقیقات انجام شده را بحث می­ کند و برای هر روش مزایا و معایب آن­ها را به­صورت جداگانه برمی­شمرد.‌

فصل سوم. در این فصل متدولوژی که عبارتند از روش­های ارائه شده و روش­های پیشین را به صورت فرمولی و شبه کد توضیح می­دهد.