حل مشکل classification با استفاده از برنامه نویسی ژنتیک ممتیکی همراه با درخت تصمیم برپایه جستجوی محلی

حل مشکل classification با استفاده از برنامه نویسی ژنتیک ممتیکی همراه با درخت تصمیم برپایه جستجوی محلی
در این مقاله روشی برای طبقه بندی داده ها با استفاده از برنامه نویسی ژنتیک ممتیکی و درخت تصمیم به کمک جستجوی محلی ارائه شده است (MGP) که عملکرد بهتری نسبت به مدل های قبلی خود دارد.
مواردی که در این مقاله مد نظر قرار گرفته اند عبارتند از:
1)    استفاده از روش SGDT برای برنامه ژنتیکی برو روی درخت تصمیم گیری ژنتیکی پایه
2)    ارایه  تابع جدید برای تابع فیتنس
3)    استفاده از محاسبات ممتیکی
  
همانگونه که می دانید طبقه بندی یکی از وظایف داده کاوی است که ریشه اش یادگیری ماشین است.
مدل پیشنهادی (MGP) مجهز به جستجوی محلی براساس الگوریتم های یادگیرنده برای درخت های تصمیم می باشد. در ابتدای این مقاله در مورد کاربرد دسته بندی صحبت نموده و به معرفی داده آموزشی و داده تست پرداخته است. در ادامه در مورد روش های گوناگون ایجاد طبقه بندی بحث نموده است.
برنامه نویسی ژنتیک یکی از رویکردهای یادگیری تکاملی است. کارهای زیادی روی GP انجام شده است. یکی از مزایای GP انعطاف پذیری آن در نمایش دادن آن به صورت های گوناگون می باشد (خطی، گرافیکی و ...). رایج ترین روش برای نمایش GP درخت می باشد.
ساختار درختی می تواند برای سه هدف مورد استفاده قرار گیرد:
1)    GP  برای استخراج درخت تصمیم
2)    سیستم های یادگیری مبتنی بر قانون
3)    توابع یادگیری تبعیض آمیز
سپس توضیحاتی راجع به GDT، EDDIE و FGP ارایه نموده و در مورد کاربرد و نقاط ضعف و قوتشان بحث نموده است.
به نوعی این مقاله در جهت بهبود FGP با کمک برنامه نویسی ژنتیکی ممتیکی (MGP) می باشد، که فرایند کار به صورت زیر است:
در اولین مرحله GDT به SGDT تغییر داده شده است.
در مرحله بعد تابع فیتنس تغییر داده شده است.
در آخرین مرحله ایده های ممتیک اضافه گردیده است.
همچنین عملگر تقسیم در فرایند جستجو، برای تپه نوردی در FGP بهبود داده شده است.
سپس در مورد الگوریتم های C4.5 صحبت نموده که ابزاری معروف جهت طبقه بندی می باشد. همچنین گفته شده است که درخت تصمیم سنتی از C4.5 استفاده می نماید که با استفاده از الگوریتم های حریصانه ساخته شده اند و سریعتر از سایر طبقه بندی کننده ها عمل می نماید. C4.5 برای محاسبه information gain از استراتژی های جستجوهای هیورستیک استفاده می کند که به گره های برگ خالص منجر می شود.
الگوریتم های ممتیک نه تنها به تکامل توجه دارند بلکه به یادگیری فردی نیز تأکید دارند. FGP برای بهبود روند جستجو از تپه نوردی بعنوان عملگر جستجوی محلی استفاده می کند. ساختار  C4.5یک استراتژی تقسیم بندی دارد که بیشتر بر بهره برداری عمیق متمرکز است. در این مقاله همچنین از یک استراتژی جدید برای تقسیم بندی استفاده می کند که ناحیه جستجو را به نواحی کوچکتری تقسیم می نماید. در نتیجه دارای فیتنس بهتری خواهد بود.
ساختار SGDT شبیه GDT است و تنها تفاوت آنها این است که SGDT کلاس خاصی را به نمونه تست نمی دهد. SGDT اطلاعات را در حینی که در حال آموزش است جمع آوری می نماید. هر کدام از برگ های نود تصمیم، نمونه هایی را که در آن افتاده اند را ثبت می نمایند و SGDT بر اساس این اطلاعات، احتمال نمونه های تست را تخمین می زند. در این مقاله تابع فیتنس بر همین اساس پیاده سازی شده است.
تابع فیتنس
در این قسمت به توضیحاتی در مورد تابع فیتنس پرداخته و در مورد  نقش مهم آن در الگوریتم های تکاملی صحبت نموده است.
سپس به معرفی تابع فیتنس جدید پرداخته و توضیحاتی در این باره داده است. این تابع ارتباط مثبت و قوی با AUC دارد و پیچیدگی محاسباتی آن کم می باشد. تابع فیتنس براساس روش آنتروپی از درخت های تصمیم سنتی گرفته شده است. بازه عددی این تابع بین صفر تا یک می باشد. زمانی که تابع فیتنس یک باشد، x دارای ماکزیمم AUC بوده و زمانی که برابر صفر باشد x یک طبقه بندی کننده رندم (SGDT) است. سپس به معرفی پارامترهای این تابع و پیچیدگی محاسباتی آن پرداخته است.
جستجوی محلی
برای طبقه بندی داده ها از یک کلاسیفایر مانند SGDT استفاده کرده است. این کلاسیفایر ناحیه داده ها را با استفاده از دو خط مورب به نواحی (سه ناحیه) تقسیم نموده است. دو ناحیه دارای نمونه های یکدستی هستند. ناحیه میانی ترکیبی از نمونه های مثبت و منفی است. هدف این مقاله اینست که ناحیه میانی را به نواحی کوچک تری تقسیم نماید تا هر ناحیه دارای نمونه های یکسانی باشند ضمنا به نحوی این کار صورت گیرد که تعداد نواحی مینیمم باشد.
برای پیاده سازی این هدف در مرحله نخست خطوط مورب را به داخل شیفت می دهیم تا جایی که دو ناحیه کناری دارای داده های یکسانی باشند. عمل شیفت دادن با استفاده از عملگرهای تپه نوردی صورت می گیرد. در این مقاله از عملگرهای تپه نوردی FGP جهت تنظیم آستانه استفاده شده است.
در مرحله بعد از عملگر splitting استفاده شده است. از این عملگر برای تقسیم نواحی به نواحی کوچک تر استفاده می شود. این عملگر روی یک ناحیه خاص عمل نموده و کاری با سایر نواحی ندارد. زمانی که عملگر شیفت کارایی نداشته باشد از عملگر splitting استفاده می شود. نواحی که دارای نمونه های متفاوتی اند احتمالا بیشتری جهت انتخاب برای عمل splitting دارند. اگر در نواحی که دارای نمونه های کمی اند از عملگر splitting استفاده شوند احتمال مشکل overfitting در طبقه بندی وجود دارد. از طرفی نواحی که دارای داده های یکسانی می باشند نیازی به عملگر splitting ندارند. پس الزاما نیاز است تشخیص دهیم که کدام نواحی نیاز به عملگر splitting دارند. زمانی که مقدار information gain یک ناحیه بالاتر از ST باشد، عملگر splitting فراخوانی می شود.
در نهایت الگوریتم پیشنهادی این مقاله ارایه گردیده است.

لینک دانلود