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