الگوریتم ماشین بردار پشتیبان (SVM)

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

الگوریتم‌های SVM بسیار مؤثر هستند زیرا ما در تلاشیم برای یافتن هایپرپلان جداکننده‌ی حداکثری بین کلاس‌های مختلف موجود در ویژگی هدف.

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

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

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

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

بیایید دو متغیر مستقل x1 و x2 و یک متغیر وابسته که یا یک دایره آبی یا یک دایره قرمز است را در نظر بگیریم.

از شکل بالا بسیار واضح است که چندین خط (هایپرپلان ما در اینجا یک خط است زیرا ما فقط دو ویژگی ورودی x1 و x2 را در نظر می‌گیریم) وجود دارند که نقاط داده‌های ما را جدا می‌کنند یا طبقه‌بندی بین دایره‌های قرمز و آبی انجام می‌دهند. پس چگونه می‌توانیم بهترین خط یا به طور کلی بهترین هایپرپلانی را که نقاط داده‌های ما را جدا می‌کند، انتخاب کنیم؟

چگونه SVM کار می‌کند؟

یک انتخاب منطقی به عنوان بهترین هایپرپلان، آن است که بیشترین جدایی یا حاشیه را بین دو کلاس نمایندگی کند.

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

در اینجا ما یک توپ آبی در مرز توپ‌های قرمز داریم. پس SVM چگونه داده‌ها را طبقه‌بندی می‌کند؟ ساده است! توپ آبی در مرز توپ‌های قرمز یک ناهنجاری برای توپ‌های آبی است. الگوریتم SVM ویژگی نادیده گرفتن ناهنجاری‌ها و یافتن بهترین هایپرپلانی که حاشیه را بیشینه می‌کند را دارد. SVM نسبت به ناهنجاری‌ها مقاوم است.

در این نوع داده‌ها، SVM بیشترین فاصله ممکن را مانند داده‌های قبلی پیدا می‌کند، و همزمان برای هر بار که نقطه‌ای از حاشیه عبور می‌کند، جریمه‌ای در نظر می‌گیرد. به همین دلیل، در این موارد به حاشیه‌ها “حاشیه‌های نرم” گفته می‌شود.

وقتی حاشیه‌ی نرم برای مجموعه داده‌ها وجود دارد، SVM سعی می‌کند مجموعه‌ی زیر را کاهش دهد.

(1/margin+∧(∑penalty))

اتلاف هینج (Hinge loss)، یک نوع جریمه رایج است. اگر تخلفی نباشد، هیچ اتلاف هینجی وجود ندارد. در صورت وجود تخلفات، اتلاف هینج متناسب با فاصله‌ی تخلف خواهد بود.

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

فرض کنید داده‌های ما در شکل بالا نشان داده شده‌اند. SVM این مسئله را با ایجاد یک متغیر جدید با استفاده از یک کرنل حل می‌کند. ما به نقطه‌ای به نام xi روی خط اشاره می‌کنیم و یک متغیر جدید yi را به عنوان تابعی از فاصله تا مبدأ o ایجاد می‌کنیم. پس اگر این را نمایش دهیم، چیزی شبیه به آنچه در زیر نشان داده شده است، به دست می‌آوریم.

در این حالت، متغیر جدید y به عنوان تابعی از فاصله تا مبدأ ایجاد می‌شود. یک تابع غیرخطی که یک متغیر جدید ایجاد می‌کند، به عنوان یک کرنل شناخته می‌شود.

اصطلاحات ماشین بردار پشتیبان

1. هایپرپلان: هایپرپلان مرز تصمیم‌گیری است که برای جداسازی نقاط داده‌های کلاس‌های مختلف در فضای ویژگی استفاده می‌شود. در مورد طبقه‌بندی‌های خطی، این یک معادله خطی خواهد بود، یعنی wx+b = 0.

2. بردارهای پشتیبان: بردارهای پشتیبان نزدیک‌ترین نقاط داده به هایپرپلان هستند که نقش حیاتی در تعیین هایپرپلان و حاشیه دارند.

3. حاشیه: حاشیه فاصله بین بردار پشتیبان و هایپرپلان است. هدف اصلی الگوریتم ماشین بردار پشتیبان بیشینه کردن حاشیه است. حاشیه وسیع‌تر نشان دهنده عملکرد بهتر طبقه‌بندی است.

4. کرنل: کرنل یک تابع ریاضی است که در SVM برای تصویرکردن نقاط داده ورودی اصلی به فضاهای ویژگی با بعد بالا استفاده می‌شود، به طوری که هایپرپلان حتی اگر نقاط داده در فضای ورودی اصلی به صورت خطی جداپذیر نباشند، به راحتی پیدا شود. برخی از توابع کرنل رایج عبارتند از خطی، چندجمله‌ای، تابع پایه شعاعی (RBF) و سیگموئید.

5. حاشیه سخت: هایپرپلان حاشیه حداکثر یا هایپرپلان حاشیه سخت، هایپرپلانی است که نقاط داده مختلف را بدون هیچ طبقه‌بندی اشتباهی به درستی جدا می‌کند.

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

7. C: پارامتر تنظیم C در SVM، بیشینه‌سازی حاشیه و جریمه‌های طبقه‌بندی اشتباه را متعادل می‌کند. این پارامتر تعیین می‌کند که جریمه برای عبور از حاشیه یا طبقه‌بندی اشتباه چقدر باشد. با افزایش مقدار C، جریمه سخت‌تری اعمال می‌شود که منجر به حاشیه کوچک‌تر و احتمالاً طبقه‌بندی اشتباه کمتر می‌شود.

8. اتلاف هینج: اتلاف هینج یک تابع ضرر معمول در SVM‌ها است. این تابع طبقه‌بندی‌های اشتباه یا تخلفات حاشیه را جریمه می‌کند. تابع هدف در SVM اغلب با ترکیب این تابع با شرط تنظیم شکل می‌گیرد.

9. مسئله دوگانه: مسئله دوگانه مسئله بهینه‌سازی است که نیاز به یافتن ضرایب لاگرانژ مرتبط با بردارهای پشتیبان دارد و می‌تواند برای حل SVM استفاده شود. فرمول‌بندی دوگانه امکان استفاده از ترفندهای کرنل و محاسبات کارآمدتر را فراهم می‌کند.

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

یک مسئله طبقه‌بندی دودویی با دو کلاس، که با +1 و -1 برچسب‌گذاری شده‌اند، در نظر بگیرید. ما یک مجموعه داده آموزشی شامل بردارهای ویژگی ورودی X و برچسب‌های کلاس متناظر Y داریم.

معادله برای هایپرپلان خطی می‌تواند به صورت زیر نوشته شود:

بردار W نشان دهنده بردار عمود بر هایپرپلان است، یعنی جهتی عمود بر هایپرپلان. پارامتر b در معادله نشان دهنده offset یا فاصله هایپرپلان از مبدأ در امتداد بردار عمود w است.

فاصله بین یک نقطه داده x_i و مرز تصمیم‌گیری می‌تواند به صورت زیر محاسبه شود:

که در آن ||w|| نشان دهنده نُرم اقلیدسی بردار وزن w است. نرم اقلیدسی بردار عمود W

برای طبقه‌بند SVM خطی:

بهینه‌سازی

– برای طبقه‌بند SVM خطی با حاشیه سخت:

متغیر هدف یا برچسب برای i^th امین نمونه آموزشی با نماد t_i در این بیانیه نشان داده شده است و t_i = -1 برای موارد منفی (وقتی y_i = 0) و (t_i = 1) برای موارد مثبت (وقتی y_i = 1) به ترتیب. زیرا ما به مرز تصمیم‌گیری نیاز داریم که محدودیت زیر را برآورده کند:

– برای طبقه‌بند SVM خطی با حاشیه نرم:

– مسئله دوگانه: مسئله دوگانه مسئله بهینه‌سازی است که نیاز به یافتن ضرایب لاگرانژ مرتبط با بردارهای پشتیبان دارد و می‌تواند برای حل SVM استفاده شود. ضرایب لاگرانژ بهینه \(α(i)\) که تابع هدف دوگانه زیر را بیشینه می‌کنند:

که در آن،

– α_i ضریب لاگرانژ مرتبط با i^thامین نمونه آموزشی است.

k(x_i,x_j) تابع کرنل است که شباهت بین دو نمونه x_i و x_j را محاسبه می‌کند. این امکان را به SVM می‌دهد تا با نگاشت ضمنی نمونه‌ها به یک فضای ویژگی با بعد بالاتر، مسائل طبقه‌بندی غیرخطی را مدیریت کند.

– اصطلاح α_i∑ نماینده جمع همه ضرایب لاگرانژ است.

مرز تصمیم‌گیری SVM می‌تواند از نظر این ضرایب لاگرانژ بهینه و بردارهای پشتیبان توصیف شود، پس از حل مسئله دوگانه و یافتن ضرایب لاگرانژ بهینه. نمونه‌های آموزشی که α_i > 0 هستند بردارهای پشتیبان می‌باشند، در حالی که مرز تصمیم‌گیری توسط فرمول زیر ارائه می‌شود:

انواع ماشین بردار پشتیبان

بر اساس ماهیت مرز تصمیم‌گیری، ماشین‌های بردار پشتیبان (SVM) به دو بخش اصلی تقسیم می‌شوند:

SVM خطی

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

SVM غیرخطی

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

توابع کرنل محبوب در SVM

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

مزایای SVM

– در مواردی که ابعاد داده‌ها بالاست، مؤثر است.

– حافظه کارآمد دارد زیرا از یک زیرمجموعه از نقاط آموزشی در تابع تصمیم‌گیری به نام بردارهای پشتیبان استفاده می‌کند.

– می‌توان توابع کرنل مختلفی را برای توابع تصمیم‌گیری مشخص کرد و امکان مشخص کردن کرنل‌های سفارشی وجود دارد.

پیاده‌سازی SVM در پایتون

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

مراحل:

1. بارگذاری مجموعه داده سرطان سینه از sklearn.datasets

2. جداسازی ویژگی‌های ورودی و متغیرهای هدف.

3. ساخت و آموزش طبقه‌بندهای SVM با استفاده از کرنل RBF.

4. رسم نمودار پراکندگی ویژگی‌های ورودی.

5. رسم مرز تصمیم‌گیری.

6. رسم مرز تصمیم‌گیری.

# Load the important packages
from sklearn.datasets import load_breast_cancer
import matplotlib.pyplot as plt
from sklearn.inspection import DecisionBoundaryDisplay
from sklearn.svm import SVC

# Load the datasets
cancer = load_breast_cancer()
X = cancer.data[:, :2]
y = cancer.target

#Build the model
svm = SVC(kernel="rbf", gamma=0.5, C=1.0)
# Trained the model
svm.fit(X, y)

# Plot Decision Boundary
DecisionBoundaryDisplay.from_estimator(
		svm,
		X,
		response_method="predict",
		cmap=plt.cm.Spectral,
		alpha=0.8,
		xlabel=cancer.feature_names[0],
		ylabel=cancer.feature_names[1],
	)

# Scatter plot
plt.scatter(X[:, 0], X[:, 1], 
			c=y, 
			s=20, edgecolors="k")
plt.show()