پیاده سازی انتخاب ویژگی با ACO برای DT در متلب + سورس کد

در این پست به بحث استفاده از الگوریتم کلونی مورچگان Ant Colony Optimization یا (ACO) را برای انتخاب ویژگی (Feature Selection) برای الگوریتم یادگیری ماشین درخت تصمیم (Discussion Tree)  یا همان DT می‌پردازیم. انتخاب ویژگی با ACO برای DT در نرم افزار متلب پیاده سازی شده است در ادامه به تشریح موضوع می‌پردازیم.

الگوریتم کلونی مورچه ACO

الگوریتم بهینه سازی کلونی مورچه  Ant Colony Optimization یا به اختصار ACO مورچگان تحت عنوان الگوریتم‌های هوش ازدحامی (هوش گروهی) شناخته شده و به مدل سازی رفتار مورچه‌های واقعی می‌پردازد. مورچه‌ها حشراتی هستند که می‌توانند گروه‌ها (کلونی ها) را شکل دهند. چنین رویکرد جمعیت محوری این امکان را برای الگوریتم ACO ایجاد می‌کند تا به حل مسائل بهینه سازی پویا به طور کاملا کارآمد بپردازد. مورچه‌ها به عنوان مخلوقات خودسازمانده می‌باشند.

از آنجایی که مورچه‌ها اصلا چشم ندارند، تعاملات آن‌ها از طریق ماده شیمیایی فرومون که از آن برای نشان گذاری مسیر استفاده می‌شود، انجام می‌گیرد. هرچه فرومن‌های بیشتری در مسیر قرار گیرد مابقی مورچه‌ها از این مسیر بیشتر استفاده می‌کنند؛ بنابراین، چنین کمیتی نشان می‌دهد که این مسیر به عنوان یکی از بهینه‌ترین و کوتاه‌ترین راه می‌باشد. اکنون نگاهی به یک نمونه عینی می‌اندازیم. هدف پیدا کردن بهترین راه از نقطه آغازی N (آشیانه) به نقطه مقصد F (منبع غذا) می‌باشد.

ممکن است این حدس زده شودکه احتمال برای مورچه‌ای که مسیر درست را می‌پیماید برابر با همان احتمالی می‌باشد که مسیر اشتباه را انتخاب کند. نکته در اینجا اینست که مورچه‌ای که کوتاه‌ترین مسیر را می‌پیماید، اولین مورچه‌ای است که به نقطه مقصد رسیده و سپس به اشیانه ( نقطه مبدا حرکت) بر می‌گردد، بنابراین در این کوتاه‌ترین مسیر فرمون‌های بیشتری وجود دارد. از این رو فرمون دقیقا همان چیزی است که نشان می‌دهد که مورچه باید از چه مسیری برود و در پایان کوتاه ترین راه، بهترین مسیر می‌باشد.

روش درخت تصمیم

درخت تصمیم، یک الگوریتم دسته‌بندی است که ساختارش بر اساس قوانین دسته‌بندی “if-then” است. در این روش ابتدا باید رخدادهای ممکن را تعیین کنیم و درخت را از گره ریشه ترسیم کنیم. هر گره مقداری که از تابع gain گرفته‌اند را توضیح می‌دهد. در ساختار یک درخت تصمیم برگ‌ها نشان‌دهنده‌ی دسته مشابه از اسناد و شاخه‌ها نشان‌دهنده‌ی پیوستگی ویژگی‌های مربوط به آن دسته است. یک درخت تصمیم خوب سازمان‌دهی شده می‌تواند دسته‌ی یک سند را به‌راحتی در گره ریشه درخت قرار داده و اجازه دهد که ساختار پرس‌وجو تا رسیدن به یک برگ معین اجرا شود که هدف دسته‌بندی سند را نشان دهد .

روش دسته‌بندی درخت تصمیم نسبت به سایر ابزارهای پشتیبانی تصمیم‌گیری دارای مزیت‌های برجسته است. مزیت اصلی درخت تصمیم، حتی برای کاربران غیرمتخصص سادگی‌ آن در فهم و تفسیر است. علاوه بر این تفسیر، نتایج به‌دست‌آمده می‌تواند به‌راحتی با استفاده از تکرار الگوریتم‌های ساده ریاضی انجام گیرد. درخت تصمیم می‌تواند به‌صورت تجربی نشان دهد که تکرار کار دسته‌بندی متن شامل تعداد زیادی از ویژگی‌های مناسب و مربوطه است. یک کاربرد از درخت تصمیم برای شخصی کردن تبلیغات در صفحات وب است. خطر عمده در پیاده‌سازی یک درخت تصمیم‌گیری over fit شدن داده‌های آموزشی است.

انتخاب ویژگی با ACO برای DT

برای انتخاب ویژگی با ACO برای DT به‌صورت جزئی‌ می‌توان گفت ابتدا یک بردار ویژگی دودویی با طول n (به تعداد پارامترهای ورودی) از F1 تا Fn به‌صورت تصادفی تولید می‌شود هرکدام از این بیت‌های این رشته‌ی دودویی متناظر با یک ویژگی در ماتریس آموزش است. اگر بیت متناظر با هر ویژگی صفر باشد آن ویژگی حذف‌شده و اگر یک باشد آن ویژگی در آموزش دخالت داده می‌شود پس از اجرای یک دور از الگوریتم کلونی مورچه با ویژگی تصادفی مقدار برازندگی برای هر بردار ویژگی دودویی تولید می‌شود.

برازندگی نیز مقدار خطای آموزش و تعداد ویژگی‌ها است که می‌خواهیم در هر دور کمینه شود بر این اساس هر بار یک دسته جدید از ویژگی‌های انتخاب می‌شود و رفته‌رفته به سمت کمترین خطای آموزشی در الگوریتم می‌رویم بهترین دسته انتخاب‌شده نهایی می‌شود و همان هدف یعنی انتخاب ویژگی‌های بهتر آشکار می‌شود.
الگوریتم ACO یک روش جستجوی تصادفی است که به کلاس الگوریتم‌های مبتنی بر جمعیت تعلق دارد. این تکنیک از تشابه میان شیوه جستجوی غذای مورچه‌ها در طبیعت و شیوه جستجوی بهینه مسئله بهینه‌سازی ترکیبی توسط الگوریتم‌های بهینه‌سازی استفاده می‌نماید.

سورس کد انتخاب ویژگی با ACO برای DT در متلب

سورس کد انتخاب ویژگی با ACO برای DT در متلب ۲۰۱۴ نوشته شده است. این سورس کد بر روی دیتاست کوچکی انجام شده است. فقط با جایگذاری دیتاست خودتان می‌توانید از این سورس کد برای دیتاست جدید استفاده کنید. سورس انتخاب ویژگی با ACO برای DT دارای دو بخش است بخش اول توسط فایل DT.m اجرا می شود که این قسمت فقط الگوریتم DT یا درخت تصمیم را اجرا می کند و بدون در نظر گرفتن انتخاب ویژگی است. بخش دوم توسط فایل  DT_with_selection_ACO.m اجرا می شود که توسط الگوریتم کلونی مورچگان برای انتخاب ویژگی (فیوچر) می پردازد. کل فایل‌های موجود ۷ فایل می‌باشد که ۴ فایل مربوط به الگوریتم کلونی مورچگان و مابقی برای اجرای پیاده سازی است.

• Dataset.mat: دیتاست مربوط به پیاده سازی می‌باشد.
• DT.m: اجرای پیاده سازی برای دسته بندی بدون انتخاب ویژگی یا خصیصه است.
• DT_with_selection_ACO.m: اجرای پیاده سازی برای دسته بندی بدون انتخاب ویژگی یا خصیصه است.

نمونه ای از سورس کد مربوط به DT_with_selection_ACO.m به شرح زیر است:

clc, clear, close all

global trn_Inputs tst_Inputs trn_Outputs tst_Outputs 
addpath(genpath('ACO'))

load Dataset

Inputs = Dataset(:,1:end-1)';
Output = Dataset(:,end)';
Output(Output==2) = 0;
Output(Output==4) = 1;

% sakhtan e dade haye amoozesh va test
[trn_Inputs,valP,tst_Inputs,trainInd,valInd,testInd] = dividerand(Inputs,0.6,0,0.4);
[trn_Outputs,valT,tst_Outputs] = divideind(Output,trainInd,valInd,testInd);

dim = size( Dataset , 2) - 1;


%aco(MaxIteretion,nAnt,dim)
bestParams = aco(20,20,dim);

bestParams = round( bestParams );
selectedFeatures = find( bestParams == 1 );
disp('Selected Features: ')
disp(num2str(selectedFeatures'))


%% Test the results


 usedFeatures = trn_Inputs(selectedFeatures, :);

برای دانلود محصول آن را خریداری کنید.

خروجی پیاده سازی

درباره اثر

سورس برنامه پیاده سازی انتخاب ویژگی با ACO برای DT در متلب در متلب عنوان اثری است که در این پست به آن پرداخته شده است. فایل در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر مذکور آن را خریداری کنید.