Support-Vector-Machines

ماشین بردار پشتیبان SVM

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

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

عملکرد سایر روش های کلاسیفیکشن

SVM با انتخاب نقاط یا بردار پشتیبان (Support Vector) به ایجاد ابرصفحه بهینه کمک می کنند. از این رو الگوریتم را ماشین بردار پشتیبان می نامند. نمودار زیر را در نظر بگیرید که در آن دو دسته مختلف وجود دارد که با استفاده از مرز تصمیم یا ابر صفحه طبقه بندی می شوند:

SVM Support vector
عملکرد SVM

بردار های پشتیبان تضمین کننده این است که معادله ابر صفحه از هر دو دسته بیشینه فاصله را داشته باشد.

انواع SVM

به طور کلی SVM شامل دو نوع می باشد:

  • SVM خطی: SVM خطی برای داده‌های قابل جداسازی خطی استفاده می‌شود، به این معنی که اگر یک مجموعه داده را بتوان با استفاده از یک خط مستقیم به دو کلاس طبقه‌بندی کرد، آن‌گاه این داده‌ها به عنوان داده‌های جداپذیر خطی نامیده می‌شوند .
  • SVM غیر خطی: SVM غیر خطی برای داده‌های جدا شده غیرخطی استفاده می‌شود، به این معنی که اگر یک مجموعه داده را نتوان با استفاده از یک خط مستقیم طبقه‌بندی کرد، این داده‌ها را داده‌های غیر خطی و طبقه‌بندی‌کننده استفاده شده را غیرخطی می‌نامند.

SVM خطی دسته بندی دو کلاسه Hard Margin

با فرض داشتن دو دسته با قابلیت جداسازی خطی، هر دسته دارای دو بردار ویژگی x1 , x2 مساله بهینه سازی را توضیح می دهیم.

svm problem hard margin
مساله SVM

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

prim hard margin svm
تابع اولیه مساله SVM

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

formula svm hard margin
معادله لاگرانژ SVM

پس از جایگزینی دو رابطه به دست آمده در فرمول اصلی مساله بهینه سازی به صورت زیر ساده سازی می شود:

cost function hard margin svm
ساده سازي لاگرانژ SVM

مساله لاگرانژ از نوع مسايل زيني مي باشد که نسبت به دو پارامتر w,b به دنبال کمينه سازي و نسبت به پارامتر ضريب لاگرانژ به دنبال بيشينه کردن تايع هزينه است. براي حل اينجور مسايل با حذف دو پارامتر w,b با روابط ذکر شده به تابع هزينه دوگان ميرسيم که تنها هدف آن بيشينه کردن نسبت به پارامتر ضرايب لاگرانژ مي باشد.

dual svm hard margin
تابع هزينه دوگان SVM

حال مساله به يک مساله بهينه سازي درجه دوم تبديل شده و مي شود آن را با quadprog آن را محاسبه نمود. و مقادير ضرايب لاگرانژ را با آن محاسبه کرد. مقدار ضرايب لاگرانژ براي اعضاي عضو بردار هاي پشتيبان داراي مقدار و براي باقي اعضا معادل صفر خواهد بود.

پس از بدست اوردن مقادير alpha نوبت به محاسبه w و b براي بدست آوردن معادله خط (ابرصفحه) مي باشد. محاسبه w از روي رابطه که قبلا ذکر شده محاسبه مي شود.

kkt hard margin svm
محاسبه b

اما براي محاسبه b از شرايط KKT استفاده مي کنيم. اما به ازاي هر عضو بردار پشتيبان مقادير متفاوت b مقادير مختلف داريم بنابراين به ازاي تمام انها مقدار b متوسط گيري مي شود.

SVM خطی دسته بندی دو کلاسه Soft Margin

همانطور که در شکل بالا مي بينيم اين دسته بندي خطي براي داده هايست که يه صورت کامل از هم مجزا باشد و به اصطلاح داده هاي نويزي وجود نداشته باشد. اما در اين بخش حاشیه نرم روابط را براي مدل واقعي تر بررسي کنيم.

soft margin svm
svm براي داده هاي نويزي

همانطور که در شکل مشخص شده است در این حالت داده ها حتی در قسمت حاشیه هم وجود دارند که باید در تابع هزینه این دسته از داده ها با یک ضریبی (C) جریمه شوند. تابع هدف به صورت زیر تغییر می یابد:

prim optimizer soft margin svm
مساله اولیه

بنابراین مساله لاگراژ با اعمال ضریب به قیود به صورت زیر اصلاح می شود

cost function soft margin svm
مساله لاگرانژ SVM

اما پس از اینکه معادله را نسبت به سه پارامتر مشتق گیری کنیم

optimizer soft margin svm
بهینه سازی پارامتر های بهینه سازی

می بینیم که معادله دوگان آن با حالت حاشیه سخت تفاوتی ندارد. تنها تفاوت در بازه ضرایب لاگرانژ می باشدکه حد بالای آن با میزان ضریب جریمه محدود شده است.

dual optimizer soft margin svm
تابع هزینه دوگان

بنابراین مجدد با روش بهینه سازی مرتبه دو حل شده و مقادیر الفا محاسبه می شود. حتما محدوده تغییرات الفا باید در مقادیر به دست آمده چک شود. حال نوبت محاسبه w,b که دقیقا مشابه حالت قبل می باشد.

SVM در متلب

در اینجا بخشی از کد دسته بندی دیتاست های تولیدی با روش SVM خطی مشاهده می کنید.

%% 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 svm
SVMmodel = fitcsvm(Input,Target);

پس از اینکه دو دسته از داده ها را جدا کردیم و به این دو دسته خروجی های یک و منفی یک اختصاص دادیم. حال از fitcsvm می توانیم برای بهینه سازی به روش svm استفاده کنیم. ساختار SVMModel شامل بایاس، مقادیر الفا و .. خواهد شد. توجه کنید این تابع به صورت پیش فرض از کرنل خطی استفاده می کند که معادل تئوری توضیح داده شده است.

در نهایت برای رسم شکل ازین مقادیر بهره گرفته و شکل بالا برای درک بصری، رسم شده است. در شکل بالا هم خطوط اصلی و هم بردارهای پشتیبان مشخص شده است.
در پست بعدی در مورد نحوه اعمال کرنل در svm بحث خواهد شد.

[دریافت کد کامل این پست آموزشی.]

نظر برای “SVM در متلب

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *