بخشی از مقاله
مثال داده شده در طول شاخه ها حرکت رو به پائین انجام می دهد. این [2] انجام شده است. در همین مرجع نشان داده شده است که یکی ازفرآیند براي گرههاي زیردرختان گره جدید تکرار می شود. مهمترین مرحله الگوهاي مفید مستطیل است.تاکنون،مقالات زیادي درزمینه تفکیکپذیري براي مستطیل ارائه شده است. تفکیک کامل با یک مستطیل در [3] مورد بررسی قرار گرفته است. در این مساله، مستطیل فقط داراي نقاط از یک رنگ است و نقاط از رنگ دیگر، خارج از مستطیل واقع میشوند . ممکن است تفکیک با یک مستطیل بطور کامل امکانپذیر نباشد. تفکیک با یک مستطیل با هدف حداکثر تعداد نقاط از یک رنگ داخل مستطیل، به نحوي که نقطهاي از رنگ دیگر، داخل مستطیل واقع نباشد در [4] مورد بررسی قرار گرفته است . تفکیک با یک مستطیل با هدف حداکثر اختلاف دورنگ، بین نقاط از یک رنگ و رنگ دیگر داخل مستطیل نیز در [5,6] بررسی گردیده است - در این حالت مستطیل داراي نقاط از هر دو رنگ میباشد - .
تفکیک با دو مستطیل بطوریکه دو مستطیل طوري در صفحه قرار گیرند که اضلاع آنها موازي یکدیگر بوده و نقاطی که در یک مستطیل قرار میگیرند - که در مستطیل دیگر قرار ندارند - تکرنگ باشند، مساله دیگري است که در [7,8] بررسی شده است. به عبارتی اگر R را مستطیل دربرگیرنده نقاط قرمز و B را مستطیل در برگیرنده نقاط آبی تعریف کنیم، نقاط داخل B-R باید فقط از رنگ آبی و نقاط داخل R-B فقط از رنگ قرمز باشند. در این مساله هدف ماکزیمم کردن تعداد نقاط داخل - R B - – - R B - است یعنی نقاطی که در فصل مشترك دو مستطیل و خارج از دو مستطیل واقع می شوند از مجموعه نقاط حذف خواهند شد.تفکیک با دو مربع واحد مجزا و تکرنگ موازي با محور x، با هدف حفظ بزرگترین زیرمجموعه از نقاط در [9,10] بررسی گردیده است.ارتباط روشنی بین مسایل تفکیکپذیري نقاط در هندسه محاسباتی و مساله درخت تصمیم در یادگیري ماشین وجود دارد.
در [11] وابستگی برخی از این مسائل به مساله درخت تصمیم شرح داده شده است. ما در این مقاله سعی میکنیم از ابرمستطیل با حداکثر اختلاف دورنگ براي دستهبندي دادهها استفاده میکنیم. این مساله را در یک، دو، سه و d بعد پیادهسازي میکنیم. از بین کلیه آزمایشهاي انجام شده، بهترین نتیجه با پیادهسازي این مساله در یک بعد حاصل شد. نتایج پیادهسازي این مساله در یک بعد در مقایسه با درخت تصمیم C4.5 بیانگر آن است که دقت این الگوریتم به اندازه 3,56 درصد از الگوریتم C4.5 کمتر است.در ادامه، ابتدا در بخش 2 الگوریتم محاسبه ابرمستطیل با حداکثر اختلاف دورنگ و ارتباط آن با درخت تصمیم را مطرح میکنیم. در بخش 3 نتایج پیاده سازي آزمایشهاي مختلف به کمک الگوریتم مطرح شده آورده میشود. این نتایج با نتایج بدست آمده توسط الگوریتم C4.5 مقایسه میگردد. در آخر در بخش 4 نیز نتیجه گیري و مسایل باز آورده می شود.
ابرمستطیل با حداکثر اختلاف دورنگ
در این بخش پس از معرفی مساله محاسبه ابرمستطیل با حداکثر اختلاف دورنگ، ارتباط این مساله با درختهاي تصمیم مطرح میگردد. سپس الگوریتم حل این مساله را در حالت یکبعدي بیان میکنیم. با ترکیب الگوریتم مطرح شده در حالت یکبعدي و استفاده از تکنیک خط جاروب [12] ، الگوریتم دوبعدي پیادهسازي میگردد. این الگوریتم قابل تعمیم به ابعاد بالاتر نیز خواهد بود.
-1-2 تعریف
چنانچه گفته شد دادههاي آموزشی به صورت نقاطی در فضاي d بعدي نگاشت میشوند. این نقاط سري S را مشخص میکنند. همچنین فرض کردیم کلیه دادههاي آموزشی داراي دو رده مثبت و منفی هستند. حال تفاوت بین این دادهها را با رنگ آنها نمایش میدهیم. کلیه دادههاي مثبت داراي رنگ آبی و کلیه دادههاي منفی داراي رنگ قرمز هستند. در این بخش هدف، حداکثرسازي درجه خلوص دادههاي آموزشی پوشش داده شده با یک فرضیه مستطیلشکل و موازي محورهاي مختصات است. این فرضیههاي مستطیلشکل به دلیل سادگی در مسائل یادگیري ماشین کاربردي بسیار رایج هستند.
در الگوریتم محاسبه ابرمستطیل با حداکثر تمایز دورنگ سعی میکنیم ابرمستطیلی را در فضاي d بعدي بدست آوریم بطوریکه داراي بیشترین تعداد نقاط آبی و کمترین نقاط قرمز باشد. به عبارتی ابرمستطیل بدست آمده داراي بیشترین اختلاف دورنگ است. به شکل 1 توجه کنید:ابتدا از تابع نگاشت زیر براي مشخص کردن هریک از دادههاي مثبت و منفی استفاده میکنیم.سپس - R - به صورت زیر تعریف میشود:در واقع - R - به نوعی بیانگر اختلاف تعداد دادههاي مثبت پوشیده شده توسط فرضیه مستطیل- شکل R و دادههاي منفی به اشتباه پوشیده شده توسط این فرضیه میباشد. در مساله محاسبه ابرمستطیل با حداکثر تمایز دورنگ به دنبال برآورده کردن رابطه 3 هستیم.
