الگوریتم KNN در متلب

الگوریتم K نزدیک ترین همسایه (KNN)

یکی از ساده ترین روش های بازشناسی الگو مبتنی بر یادگیری ماشین ، به منظور دسته بندی (Classification) و رگرسیون داده ها، می توان به الگوریتم K نزدیک ترین همسایگی اشاره نمود. سادگی الگوریتم K Nearest Neighbors از نظر پیاده سازی مورد توجه می باشد. اما این سادگی به قیمت تحمیل زمان زیاد محاسبات بلاخص در داده های حجیم، خواهد بود.

روند کلی الگوریتم
- مرحله اول: مدل سازی
- مرحله دوم: تعیین فاصله
  - فاصله اقلیدسی
  - فاصله منتهن
  - فاصله مینکوفسکی
- مرحله سوم: کلاس بندی داده
الگوریتم KNN در متلب
انتخاب پارامتر طراحی k
knnclassify in matlab

توجه اصلی این الگوریتم بر روی k تعداد، از نزدیک ترین داده ها به داده ناشناخته می باشد. اگر مقدار k برابر با یک فرض شود، در واقع اشاره به الگوریتم نزدیک ترین همسایگی خواهد داشت. در این حالت تنها یکی از نزدیک ترین داده ها به داده ناشناخته مبنای مشخص کردن کلاس داده خواهد بود.

روند کلی الگوریتم

به طور کی الگوریتم شامل سه فاز زیر می باشد:

دریافت داده‌های اولیه: که شامل بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته می‌باشند.
فاز یادگیری: الگوریتم، شامل ذخیره‌سازی بردارهای ویژگی و برچسب دسته نمونه‌های اولیه است.
فاز دسته بندی: که داده های ناشناخته و بدون برچسب با توجه به فاصله اش از k نزدیک‌ترین همسایه برچسب گذاری می شوند.

به منظور درک الگوریتم کافیست مراحل مثال زیر را برای اختصاص داده ناشناخته به دو کلاس شناخته شده به صورت مساله knn تعمیم دهیم:

مرحله اول:

مدل سازی مساله و داده های اولیه:
در این مثال دو دسته داده آموزشی با برچسب مشخص، داریم. قرار است با این داده ها، کلاس داده جدید را مشخص کنیم. داده جدید یا عضو کلاس A یا کلاس B خواهند بود.

مرحله دوم :

تعیین فاصله تمامی داده ها از داده ناشناخته :
در این بخش باید فاصله داده ی جدید با تمام داده های آموزشی مشخص شود. معیار محاسبه فاصله می تواند متفاوت باشد، که ذکر خواهد شد.

برای تعیین عدم شباهت داده ها از تابع فاصله (Distance Functions) استفاده می کننند. انواع مختلف توابع در زیر اشاره شده است:

فاصله اقلیدسی (Euclidean Distance)

D_{e u c} = (\sum_{i = 1}^{p} (x_{i} - y_{i})^{2})^{\frac{1}{2}}

فاصله منهتن (Manhattan Distance)

D_{m a n} = \sum_{i = 1}^{p} | x_{i} - y_{i} |

فاصله مینکوفسکی (Minkowski Distance)

D_{m i n k} (A, B; d) = (\sum_{i = 1}^{p} | x_{i} - y_{i} |^{d})^{\frac{1}{d}}

مرحله سوم:

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

choosing knn and calsification — انتخاب k همسایگی نزدیک

در نهایت نوبت به تصمیم گیری برای تعیین کلاس داده جدید می رسد. معیار تصمیم گیری نهایی بر مبنای کلاس k داده گلچین شده می باشد.

مشابه مثال بالا، اکثریت k داده گلچین شده مربوط به کلاس B است (دو تا سبز و یک قرمز )، در نتیجه داده جدید کلاس B خواهد بود. در نهایت می توان نتیجه گرفت با در نظر گرفتن اکثریت کلاس های K داده گلچین شده، می توان دسته بندی داده ها را مشخص نمود.

برای این مثال از داده های فیشر ایریس استفاده شده است. این 4 نوع ویژگی برای 150 داده گل را در سه دسته {'setosa' 'versicolor' 'virginica'} دسته بندی می کند. داده ها را به دو دسته آموزشی و تست دسته بندی می کنیم.
حلقه فور نوشته شده برای محاسبه فاصله هر داده تست از مجموعه داده های آموزشی می باشد. با دستور dist فاصله اقلیدسی محاسبه شده است. نتایج در نهایت با شمارش کل داده هایی که درست تشخیص داده شده اند به پایان می رسد.

load fisheriris
X = meas;
Y = cell2mat(species);
XLrn=X(1:2:150,1:4);
CLrn=Y(1:2:150,5);
XTst=X(2:2:150,1:4);
CTst=Y(2:2:150,5);
Correct=0;
for i=1:75
    d=dist(XLrn,XTst(i,:)');
    [m, Idx]=min(d);
    Cout=CLrn(Idx);
    if(Cout==CTst(i)) 
        Correct=Correct+1;
    end
end

دراین مثال تنها نزدیکترین همسایگی در نظر گرفته شده است. با دستور min کمترین فاصله را مشخص می کنیم. ( مقدار k برابر با یک در نظر گرفته ایم.)

انتخاب پارامتر طراحی k

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

تابع knnclassify در متلب

همانطور که در کد بالا ذکر شد شما می توانید به صورت کد نویسی برنامه ای بنویسید که دسته بندی داده ها را برای حالت k بزرگتر از یک نیز حساب کند. اما متلب کار شما را با ارائه یک فانکشن با نام fitcknn راحت می کند. به عنوان مثال برای داده های زیر می توان از تابع به این صورت استفاده نمود:

%% generate train data
n = 25; % tedad data
x1 = [ randi([1 10],[1 n]) ; randi([1 10],[1 25])];
plot (x1(1,:),x1(2,:),'r*')
x2 = [ randi([11 20],[1 n]) ; randi([1 10],[1 n])];
hold on
plot (x2(1,:),x2(2,:),'b*')

Input =  [x1,x2]';
y1 = ones(1,n);
y2 = -ones(1,n);
Target = [y1,y2];
title('train data')
%% classifier knn
k = 1
knnmodel = fitcknn(Input,Target ,'NumNeighbors',k );

در کد بالا برای یک همسایگی مورد بررسی قرار گرفته است شما می توانیدبا دادن k های بیشتر از یک نیز همسایگی های بالاتر را مورد بررسی قرار دهید. خروجی دستور اخر کلاس داده های آموزشی را برای شما مشخص خواهد کرد.