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

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

در این پست به بحث انتخاب ویژگی با ACO برای KNN یا بطور کامل استفاده از الگوریتم کلونی مورچگان Ant Colony Optimization یا (ACO) را برای انتخاب ویژگی (Feature Selection) برای الگوریتم یادگیری ماشین K همسایه نزدیک (k-Nearest Neighbors) یا همان KNN می پردازیم. در این بحث با توجه به خاصیت الگوریتم الگوریتم مورچه به انتخاب ویژگی با ACO از دیتاست ها پرداخته می شود. کدهای برنامه بصورت دقیق بر روی دیتاست موجود نوشته شده و بصورت روان قابل در است. انتخاب یا استخراج ویژگی با ACO برای KNN در نرم افزار متلب 2014 نوشته شده است در ادامه به تشریح موضوع می پردازیم.(استخراج ویژگی با الگوریتم کلونی مورچه در متلب)

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

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

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

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

روش k همسایه‌ی نزدیک k-nearest neighbors algorithm

روش k همسایه‌ی نزدیک یا k-nearest neighbors algorithm یک روش یادگیری موردی ‌است و ازجمله ساده‌ترین الگوریتم‌های یادگیری ماشین است. در این الگوریتم یک نمونه با رأی اکثریت از همسایه‌هایش دسته‌بندی می‌شود و این نمونه در عمومی‌ترین کلاس مابین k همسایه نزدیک تعیین می‌شود. متغیر K یک مقدار مثبت صحیح و عموماً کوچک است. اگر k=1 باشد نمونه به‌سادگی در کلاس همسایگان نزدیکش تعیین می‌گردد. فرد بودن مقدار k مفید است چون با این کار جلوی آراء برابر گرفته می‌شود.

روش k همسایه‌ی نزدیک، برای بسیاری از روش‌ها کاربرد دارد، زیرا اثربخش، غیرپارامتریک و دارای پیاده‌سازی راحت است. شکل زیر مثالی از الگوریتم دسته‌بندی روش k همسایه‌ی نزدیک، با استفاده از بردار ویژگی چندبعدی است که مثلث‌ها کلاس اول و مربع‌ها کلاس دوم رانشان می‌دهند. دایره کوچک در داخل دوایر، نمونه تستی را نشان می‌دهد. حال اگر مقدار k=3‌ باشد (3 همسایه‌ی نزدیک به نمونه) نمونه تستی متعلق به کلاس مثلث و اگر k=5 باشد نمونه متعلق به کلاس مربع است.

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

سه فاکتور مهم در این الگوریتم روش k همسایه‌ی نزدیک، به شرح زیر است:

• معیار فاصله یا شباهت، برای پیداکردن k همسایه نزدیک استفاده می‌شود.
•  K تعداد همسایه‌های نزدیک است.
• قانون تصمیم‌گیری برای تعیین (شناسایی) یک کلاس برای سند تستی از k همسایه نزدیک است.

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

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

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

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

سورس کد انتخاب ویژگی با ACO برای KNN در متلب 2014 نوشته شده است. این سورس کد بر روی دیتاست کوچکی انجام شده است. فقط با جایگذاری دیتاست خودتان می توانید از این سورس کد برای دیتاست جدید استفاده کنید. سورس انتخاب ویژگی با ACO برای KNN دارای دو بخش است بخش اول توسط فایل KNN .m اجرا می شود که این قسمت فقط الگوریتم KNN یا k همسایه نزدیک را اجرا می کند و بدون در نظر گرفتن انتخاب ویژگی است.

بخش دوم توسط فایل  KNN _with_selection_ACO.m اجرا می شود که توسط الگوریتم کلونی مورچگان برای انتخاب ویژگی (فیوچر) می پردازد. کل فایل های موجود 7 فایل می باشد که 4 فایل مربوط به الگوریتم کلونی مورچگان و مابقی برای اجرای پیاده سازی است.

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

نمونه ای از سورس کد مربوط به KNN _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 برای KNN در متلب در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید.