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

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

در این پست به بحث انتخاب ویژگی با ACO برای NB یعنی استفاده از الگوریتم کلونی مورچگان Ant Colony Optimization یا (ACO) را برای انتخاب ویژگی (Feature Selection) برای الگوریتم یادگیری ماشین نیو بیزین (Naive Bayesian) یا همان NB می‌پردازیم. در این بحث با توجه به خاصیت الگوریتم الگوریتم مورچه به انتخاب ویژگی با ACO از دیتاست‌ها پرداخته می‌شود. کدهای برنامه به‌صورت دقیق بر روی دیتاست موجود نوشته شده و به‌صورت روان قابل در است. انتخاب یا استخراج ویژگی با ACO برای NB در نرم افزار متلب ۲۰۱۴ نوشته شده است در ادامه به تشریح موضوع می‌پردازیم. (استخراج ویژگی با الگوریتم کلونی مورچه در متلب)

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

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

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

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

روش نیو بیزین naive bayesian

الگوریتم نیو بیزین naive bayesian یک الگوریتم یادگیری ساده است که از قاعده بیز به همراه فرض محکمی که صفات با توجه به کلاس از نظر شرطی مستقل هستند، استفاده می‌کند. اگرچه این فرض استقلال در عمل اغلب نقض می‌شود، با این وجود، اغلب الگوریتم نیو بیزین naive bayesian صحت دسته‌بندی قابل رقابتی ارائه می‌کند. این ویژگی به همراه کارایی محاسباتی و ویژگی‌های مطلوب بسیار دیگری، سبب شده naive bayesians در عمل به صورت گسترده مورد استفاده قرار بگیرد.

انگیزه و پس‌زمینه naive bayesian

الگوریتم نیو بیزین naive bayesian مکانیزمی برای استفاده از اطلاعات داده‌های نمونه برای تخمین احتمال موخر P(y|x) هر کلاس y با توجه به شی x فراهم می‌کند. هنگامی که چنین تخمین‌هایی داشته باشیم، می‌توانیم از آن‌ها برای دسته‌بندی یا دیگر کاربردهای پشتیبان تصمیم استفاده کنیم.

برخی از ویژگی‌های مطلوب بسیار الگوریتم نیو بیزین naive bayesian موارد زیر است:

• کارایی محاسباتی: زمان آموزش با توجه به تعداد نمونه‌های آموزشی و هم تعداد صفات خطی بوده و زمان دسته‌بندی با توجه به تعداد صفات خطی است و از تعداد نمونه‌های آموزشی تاثیر نمی‌پذیرد.
• واریانس کم: به دلیل این که الگوریتم نیو بیزین naive bayesian از جستجو استفاده نمی‌کند، واریانس پایینی دارد که البته هزینه آن سوگیری بالاست.
• یادگیری تدریجی: الگوریتم نیو بیزین naive bayesian از تخمین‌های داده‌های آموزشی عمل می‌کند. این موارد ی‌توانند زمانی که داده‌های جدید گردآوری شد، به راحتی به روزرسانی بشوند.
• پیش‌بینی مستقیم احتمالات موخر.
• مقاومت در برابر نویز: همواره naive bayesian از تمام صفات برای پیش‌بینی استفاده می‌کند، بنابراین در مقابل نویز در نمونه‌هایی که باید دسته‌بندی شوند، نسبتا غیر حساس است. از آن‌جا که از احتمالات استفاده می‌کند، نسبتا به نویز در داده‌های آموزشی نیز نسبتا غیر حساس است.
• مقاومت در برابر مقادیر مفقود: از آن‌جا که الگوریتم نیو بیزین naive bayesian از تمام صفات برای پیش‌بینی استفاده می‌کند، اگر یک مقدار صفت از دست برود، اطلاعات دیگر صفات استفاده می‌شود، که نتیجه آن افت شدید عملکرد است. هم‌چنین نظر به چارچوب احتمال آن، در مقابل مقادیر مفقود صفت در داده‌های آموزشی بی تفاوت است.

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

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

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

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

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

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

نمونه‌ای از سورس کد مربوط به NB _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, :);

% amade kardan e shabake
nb = NaiveBayes.fit(usedFeatures', trn_Outputs');
y_hat_tst=nb.predict(tst_Inputs(selectedFeatures, :)');

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

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

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