استخراج طبقهبندهای عام[1] و قابل فهم از داده، نقش مهمی در بسیاری از حوزهها و مسائل است. تاکنون روشهای متعددی برای طبقهبندی[2] و تشخیص الگو[3] معرفی شده است. یکی از شیوههای موفق و منحصربهفرد در حوزه طبقهبندی و تشخیص الگوی دادههای ورودی، استفاده از تکنیکهای فازی برای تقسیمبندی نرم فضای ویژگی و بالطبع استفاده از یک معماری مؤثر در متصل کردن این زیرفضاها برای تصمیمگیری و طبقهبندی بهصورت فازی میباشد. اینکه بتوان بهترین و کارا ترین قوانین فازی را از روی داده استخراج کرد هنوز زمینه بسیار مهمی برای محققان است.در این مطالعه یک روش نوین برای وزندهی به قوانین فازی با استفاده از الگوریتم تکاملی رقابت استعماری ارائه شده است تا بتوان قوانین مهمتر را با استفاده از وزنهای بهینه شده بیشتر در نظر گرفت. در این پایاننامه، عملگرهای الگوریتم رقابت استعماری برای ساختن مناسب قوانین فازی مجددا تعریف میشونددرواقع تکنیک Ishibuchiبرای فاز اول یعنی تولید قوانین و تکنیک رقابت استعماری برای فاز دوم یعنی وزندهی به آنها ارائه شده است. در گام بعدی، تولید و تکامل قوانین فازی با الگوریتم رقابت استعماری پیشنهاد شده است. این روش باعث افزایش کارایی طبقهبندی کننده برای نرخ طبقه بندی میشود. درنهایت، هدف، ساختن یک مجموعه قانون فشرده با تعداد کم قوانین است که این قوانین دارای طول کوتاه و در نتیجه تفسیرپذیری بالا هستند.الگوریتم پیشنهادی با طبقه بندی کنندههای پایه غیرفازی مانند SVM، C4.5، 1NN و Naive Bayes و الگوریتمهای طبقه بندی کننده فازی که توضیح داده خواهد شد مقایسه و ارزیابی میشود. واژههای کلیدی: طبقهبندی، تشخیص الگو، الگوریتم رقابت استعماری، طبقه بندی کنندههای فازی، طبقه بندی کنندههای غیر فازی، وزندهی قوانین. فهرست مطالب عنوان صفحهفصل اول1-مقدمه.......................................... 21-1- مقدمه....................................... 21-2- انگیزه..................................... 31-3- شرح مسئله.................................. 41-4- چالشها..................................... 51-5- اهداف پایان نامه........................... 7 فصل دوم. 2- پیشینه تحقیق.................................. 92-1- مقدمه..................................... 102-2- حوزه تکامل قوانین فازی.................... 112-3-یادگیری سیستمهای طبقه بندی کننده فازی...... 122-3-1- یادگیری سیستمهای طبقه بندی کننده فازی بر اساس الگوریتم ژنتیک.......................................... 122-3-2- الگوریتمهای تکامل همزمان............. 222-3-3-یادگیری سیستمهای طبقه بندی کننده فازی با استفاده از الگوریتم ازدحام ذرات .......................... 242-3-4- یادگیری سیستمهای طبقه بندی کننده فازی با استفاده از الگوریتم زنبور عسل............................. 25 2-3-5- یادگیری سیستمهای طبقه بندی کننده فازی با استفاده از الگوریتم مورچگان ........................... 262-4- الگوریتم رقابت استعماری................... 262-4-1- ویژگیهای الگوریتم رقابت استعماری......... 282-4-2-کاربردهای الگوریتم رقابت استعماری........ 282-5-جمع بندی .............................. 30فصل سوم3- روش تحقیق ................................... 323-1- مقدمه .................................... 333-2- سیستمهای فازی............................. 343-2-1-سیستمهای استنتاج فازی.................. 34سیستمهای فازیMamdani............................................................. 34سیستمهای فازی Sugeno..................... 35سیستمهای فازی Tsukamato................... 353-2-2- طبقه بندی کنندههای فازی............... 36تابع استدلال فازی.......................... 36معیار ارزیابی قوانین ................ 383-3- الگوریتم CORE ............................ 393-4- الگوریتم جزیره ای Ishibuchi برای استخراج قوانین 393-5- الگوریتم GBML-IVFS-amp .................... 413-6- الگوریتم GNP برای وزندهی به قوانین فازی ... 423-7- الگوریتم TARGET .......................... 423-8- الگوریتم SGERD ........................... 433-9- الگوریتم رقابت استعماری .................... 443-9-1- مقدرادهی اولیه امپراطوریها.............. 453-9-2- عملگر Assimilation........................ 463-9-3- استراتژیهای بهینه سازی میتنی بر تکامل اجتماعی-سیاسی 473-10- الگوریتمهای پیشنهادی .................... 483-10-1- هدف استفاده از ICA برای الگوریتم پیشنهادی 483-10-2- وزندهی به قوانین فازی................ 483-10-3- الگوریتم پیشنهادی برای تکامل قوانین فازی52قوانین خاص و عام................. 52روش پیشنهادی برای تولید قوانین فازی 53تابع برازش پیشنهادی............. 543-11-جمع بندی .............................. 57 فصل چهارم نتایج آزمایشات................................. 584-1- معیارهای ارزیابی.......................... 594-2-مجموعه دادهها ............................. 604-2-1-مجموعه داده KEEL....................... 604-2-2-مجموعه داده UCI.......................... 614-3- الگوریتم پیشنهادی برای وزندهی به قوانین.... 614-3-1-پارامترها و تنظیمات سیستم در پیاده سازی614-3-2-مقایسه الگوریتم پیشنهادی با طبقه بندی کنندههای فازی624-3-3-مقایسه الگوریتم پیشنهادی با طبقه بندی کنندههای غیر فازی664-4- الگوریتم پیشنهادی برای تولید قوانین فازی بهینه 684-4-1-پارامترها و تنظیمات سیستم در پیاده سازی یادگیری ساختار قوانین فازی..................................... 684-4-2-انتخاب ویژگی............................. 694-4-3-ارزیابی الگوریتم یادگیری ساختار قوانین با روشهای فازی 704-4-4-ارزیابی الگوریتم با روشهای غیر فازی...... 724-5- جمع بندی ............................... 73فصل پنجمجمع بندی و پیشنهادات............................ 76اختصارات............................................................................................................................................................. 78 واژهنامه فارسی به انگلیسی........................................................................................................................................................ 79واژه نامه انگلیسی به فارسی............................................................ 80فهرست منابع.....................................................................................................................................................82 فهرست جداول عنوان صفحهجدول 2-1-مقایسه خطای الگوریتم . 16جدول 2-2-ارزیابی SGERD. 20جدول 2-3-نرخ طبقه بندی، تعداد قوانین و زمان محاسباتی در SLAVE 21جدول 2-4-نتایج ارزیابی الگوریتم . 21جدول 2-5MSE و R2 برای ICA و ICA-NN 29جدول 4-1-مجموعه داده KEEL 60جدول 4-2-مجموعه داده UCI 61جدول 4-3-پارامترهای استفاده شده در الگوریتم وزن دهی به قوانین 62جدول 4-4-مقایسه الگوریتم وزن دهی پیشنهادی با دیگر الگوریتمهای تکاملی 63جدول 4-5-نتایج نرخ خطای روش پیشنهادی در مقایسه با الگوریتمهای TARGET و Chi-IVFS-Amp 64جدول 4-6-مقایسه الگوریتم وزندهی با چندین تابع فازی 65جدول 4-7-میانگین رتبه بندی برای 4 روش مقایسه شده روی 11 مجموعه داده 66جدول 4-8-نتایج تست فردمن و تست تعقیبی Bonferoni-Dunn 66جدول 4-9-نتایج خطای بدست آمده از ارزیابی الگوریتم پیشنهادی با چندین تابع غیرفازی 67جدول 4-10-میانگین رتبه بندی برای 4 روش مقایسه شده روی 8 مجموعه داده67جدول 4-11--نتایج تست فردمن و تست تعقیبی Bonferoni-Dunn 67جدول 4-12پارامترهای مورد استفاده در الگوریتم پیشنهادی یادگیری سیستم فازی............................................ 69جدول 4-13-مقایسه نرخ خطای الگوریتم یادگیری قوانین فازیبا توابع فازی70جدول 4-14-طول قوانین و تعداد قوانین بدست آمده در الگوریتم پیشنهادی یادگیری 71جدول 4-15میانگین رتبه بندی برای روشهای مقایسه شده روی 10مجموعه داده71جدول 4-16-نتایج تست فردمن و تست تعقیبی Bonferoni-DunN71جدول 4-17نتایج بدست آمده از ارزیابی الگوریتم پیشنهادی با توابع غیرفازی72جدول 4-18میانگین رتبه بندی برای 4 روش مقایسه شده روی 8 مجموعه داده72جدول 4-19نتایج تست فردمن و تست تعقیبی Bonferoni-DunN73 فهرست شکل ها عنوان صفحهشکل 2-1-نمودار نرخ dont care در داده Wine13شکل 2-2-نمودار نرخ طبقه بندی در داده Wine. 13شکل 2-3-نحوه کدینگ اعضای جمعیت در راهکار Michigan و Pittsburgh.. 14شکل 2-4- میانگین نرخ طبقه بندی.. 15شکل 2-5-IVFS در الگوریتم ژنتیک و IVFS در الگوریتم Herrera. 17شکل 2-6-کارایی SGERD روی داده Wine. 19شکل 2-7- کارایی SGERD روی داده iris. 19شکل 2-8-ساختار جمعیت و لینک های تکامل در الگوریتم CORE 23شکل 2-9-نمودار نرخ خطای داده satimage. 24شکل 2-10-شبه کد الگوریتم M-PSO.. 25شکل 2-11-نمودار برازش بهینه و متوسط برازش در الگوریتم ژنتیک، PSO و الگوریتم رقابت استعماری.......................... 27شکل 3-1-نحوه بخش بندی فضای ویژگی و قوانین فازی تولید شده روی دادهها 38شکل 3-2-شبه کد الگوریتمCORE.. 39شکل 3-3-شبه کد الگوریتم جزیره ایIshibuchi40شکل 3-4-شبه کد الگوریتمGBML-IVFS-Amp. 41شکل 3-5-فلوچارت الگوریتم GNP برای یافتن عبارات بهینه.. 42شکل 3-6-بخش بندیهای متفاوت برروی یک مشخصه.. 43شکل 3-7-شبه کد الگوریتمSGERD.. 44شکل 3-8-فلوچارت الگوریتم رقابت استعماری.. 47شکل 3-9-شبه کد الگوریتم پیشنهادی وزندهی.. 50شکل 3-10-بخش بندیهای متفاوت برروی یک مشخصه.. 53شکل 3-11-شبه کد الگوریتم پیشنهادی برای یادگیری قوانین فازی 55 شکل 4-1-فازی ستهای مورد استفاده روی هر مشخصه...... 69 مقدمه شکل 1-1.(1-1) 1. مقدمهدر این فصل به شرح کلیاتی پیرامون انگیزه ی انتخاب موضوع، طبقهبندی کنندههای فازی و همچنین شرحی بر مسئله و کاربردها و چالش های میپردازد. در انتهای فصل نیز اهداف پایاننامه به صورت خلاصه ذکر میشود.1-1. مقدمهتاکنون دانشمندان حوزه داده کاوی تلاشهای بسیاری برای جداسازی صحیح نمونههای مشابه کردهاند. استخراج طبقهبندهای عام[4] و قابل فهم از داده، نقش مهمی در بسیاری از حوزهها و مسائل است. تاکنون روشهای متعددی برای طبقهبندی[5] و تشخیص الگو[6] معرفی شدهاست. یکی از شیوههای موفق و منحصربهفرد در حوزه طبقهبندی و تشخیص الگوی دادههای ورودی، استفاده از تکنیکهای فازی برای تقسیمبندی نرم فضای ویژگی و بالطبع استفاده از یک معماری مؤثر در متصل کردن این زیرفضاها برای تصمیمگیری و طبقهبندی بهصورت فازی میباشد. طبقهبندی فازی پروسه گروه بندی عناصر داخل مجموعههای فازی با یک تابع عضویت[7] است[1]. در واقع، ابتدا فضای جستجو به بخشهایی قسمت بندی میشود به گونه ای که تمام فضا پوشش داده شود و سپس بر روی هرکدام از این زیرفضاها مجموعه فازی قرار میگیرد. اجتماعی از مجموعههای فازی که فضای فازی نامیده میشود، مقادیر زبانی فازی یا کلاسهای فازی را تعریف میکند که یک شی میتواند به آنها تعلق داشته باشد. پس از آن قوانین فازی اگر و آنگاه[8] با توجه به نحوه تخصیص تولید میشوند. مدلسازی سیستمهای فازی بصورت مجموعهای از این قوانین نمایش داده میشود.1-2. انگیزهطبقهبندیکنندههای فازیدارای ویژگی منحصربفرد تفسیرپذیری هستند و قادرند دانش چگونگی تشخیص الگوها را برای یک فرد خبره بصورت یک دستورالعمل بازنمایی کنند. طبقهبندیکنندههای فازی چهار هدف اساسی را دنبال میکنند. دقت طبقهبندیکننده را بیشینه کنند، طبقهبندیکنندهی با بیشترین قابلیت تفسیرپذیری را ایجاد نمایند، پایداری طبقهبندیکننده را بیشینه کنند و حساسیت به نویز را کاهش دهند. تاکنون روشهای متفاوتی برای ایجاد قوانین، نحوه تخصیص زیرفضاها، نحوه استنتاج در هر قانون و در نهایت ادغام قوانین ارائهشده است. بدیهی استزبان طبیعی[9] محور بودن ساختار قوانین فازی علیرغم استخراج دانش، مشکل اثبات ریاضی کارایی طبقهبندیکننده از جمله ارائه یک کران بالا[10] برای خطای آموزش[11] و خطای تست[12] است. بهعبارتی افزایش عمومیسازی[13] این طبقهبندیکنندهها بصورت ریاضی مانند طبقهبندی کننده تقویتی گروهی[14] کار بسیار دشواری است. از اینرو اغلب از روشهای مکاشفهای[15]و فوق مکاشفهای[16] بهصورت سعی و خطا در تدوین قوانین و ادغام آنها استفاده میگردد، به این دلیل که زیرفضا را برای بهدستآوردن بهترین ترکیب قوانین جستجو میکنند [2]-[4] . ایشیبوشی[17][5] روشی را برای تخصیص فضا بهصورت تقسیمبندی منظم و تکراری ارائه کرد که میتوان از این روش بهعنوان یکی از موثرترین روشهای طبقهبندیکننده فازی که مبنای بسیاری از تحقیقات بعدی در این زمینه نیز شد، نام برد.1-3. شرح مسئلهپروسه یادگیری یک سیستم طبقهبندی فازی باید مسایل مختلفی را حل کند تا یک سیستم طبقهبندی زبانی را با یک رفتار صحیح ایجاد نماید. از جمله اینکه بتواند، 1- مجموعهای از قوانین فازی را ایجاد کند که دارای یک سطح لازم همکاری بین این قوانین فازی باشد. 2- انتخاب یک تابع استنتاج که روشی را برای ترکیب اطلاعات بهدست آمده از قوانین فازی در کلاسهبندی نمونهها انتخاب میکند. 3- در مسایل با ابعاد بالا، قوانین فازی از رشد نمایی در سایزشان رنج میبرند. دو مسئله اول، مربوط به پروسه استخراج دانش میشود که با پردازشهای یادگیری مختلف براساس الگوریتمهای تکرارشونده مانند شبکههای عصبی مصنوعی[5-6] یا الگوریتم ژنتیک[2-4]قابل حل است. گزینه سوم از دو جهت میتوان مدیریت کرد: با فشردهسازی و کاهش مجموعه قوانین، قوانین غیرضروری را با هدف ایجاد یک سیستم طبقهبندی با کارایی بالاتر حذف کرد. و راهکار دوم با پروسه انتخاب ویژگی انجام میگیرد.به طور کلی، هدف مسئله، فراهم کردن یک چارچوب کلی برای تکامل قوانین فازی است. راهکارهای بسیاری در این زمینه ارائه شده، اما همه آنها حداقل در یکی از موارد زیر تفاوت دارند، تعداد قوانینی که در هر عضو جمعیتکد میشود، نوع بیان قوانین کدشده در هر عضو و نوع و هدف پروسه تکاملی .[7-8] اين الگوريتم‌ها شامل الگوريتم‌هاي ژنتيک[18]، بهينه‌سازي گروه ذرات[19]، گداختگی شبيه‌سازي شده[20] و... مي‌باشند.از آنجایی که الگوریتمهای تکاملی[21] بهصورت چندعاملی[22] جستجو را در فضای ویژگی انجام میدهند، نحوه گردش آنها تا حد ممکن بهصورت تصادفی میباشد. این خواص، الگوریتمهای تکاملی را به ابزار قوی برای انواع مسائل بهینهسازی تبدیل نموده است.[2], [4] از جمله مسائل مطرح در زمینه بهینهسازی، بهینهسازی ساختار و پارامترهای طبقهبندیکنندهها میباشد. بدیهی است هرچه یک طبقهبندیکننده پارامترهای بیشتری داشته باشد، تنظیم بهینه این پارامترها بهصورت دستی کاری بسیار دشوار، و در بعضی حالات غیرممکن میباشد. بدین خاطر از الگوریتمهای تکاملی برای یادگیری پارامترها و تعیین ساختار طبقهبندیکنندههای متفاوت بهصورت فراوان استفاده شده است. از جمله این تحقیقات میتوان به بهبود ساختار شبکه عصبی توسط الگوریتم ژنتیک اشاره کرد [9] که الگوریتم ژنتیک سعی در هرس کردن ارتباط بین نورونها و بهنوعی لایهبندی آنها به منظور بهبود کارایی طبقهبندی، دارد.