وبلاگ

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

 

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

 

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

 

• چندین طرح کلی کدگذاری برای نمایش قوانین به شکل رشته­ای از بیت­ها ارائه می­دهد.

 

• یک تابع برازش برای ارزیابی کارایی اعضا یا همان قوانین فازی تعریف می­ کند.

 

• تصحیحی در عملگر­های الگوریتم رقابت استعماری برای استفاده بهینه در سیستم­های فازی ارائه می­دهد.

 

• زیرفضای تخصیص­داده­شده برای هر قانون را توسعه می­دهد و درنتیجه افزایش نسبی عمومی­سازی را منجر می­ شود.

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

 

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

 

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

 

فصل چهارم. در فصل چهارم نتایج به­دست آمده ارائه می­ شود.

 

فصل پنجم. کار­های پیش رو و اهداف آینده بررسی می­ شود.