بایگانی برچسب برای: Support vector machines

ماشین بردار پشتیبان (svm) قسمت 2

یادگیری ماشین – SVM یا ماشین بردار پشتیبان به زبان ساده

سید مجتبی بنائی ۱۳۹۴/۰۵/۱۶ مفاهیم پایه نظرات 31,220 مشاهده

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

آشنایی با مفهوم دسته بندی

فرض کنید مجموعه داده ای داریم که ۵۰٪ افراد آن مرد و ۵۰٪ افراد آن زن هستند. این مجموعه داده می تواند مشتریان یک فروشگاه آنلاین باشد. با داشتن یک زیرمجموعه از این داده ها که جنسیت افراد در آن مشخص شده است، می خواهیم قوانینی ایجاد کنیم که به کمک آنها جنسیت بقیه افراد مجموعه را بتوانیم با دقت بالایی تعیین کنیم. تشخیص جنسیت بازدیدکنندگان فروشگاه، باعث می شود بتوانیم تبلیغات جداگانه ای را برای زنان و مردان نمایش دهیم و سودآوری فروشگاه را بالا ببریم . این فرآیند را در علم تحلیل داده، دسته بندی می نامیم .

برای توضیح کامل مسأله، فرض کنید دو پارامتری که قرار است جنسیت را از روی آنها تعیین کنیم، قد و طول موی افراد است . نمودار پراکنش قد و طول افراد در زیر نمایش داده شده است که در آن جنسیت افراد با دو نماد مربع (مرد) و دایره (زن) به طور جداگانه نمایش داده شده است .

SVM-1

 

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

  1. مردان در این مجموعه، میانگین قد بلندتری دارند.
  2. زنان از میانگین طول موی بیشتری برخوردار هستند.

اگر یک داده جدید با قد ۱۸۰cm و طول موی ۴cm به ما داده شود، بهترین حدس ما برای ماشینی این شخص، دسته مردان خواهد بود .

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

بردارهای پشتیبان به زبان ساده، مجموعه ای از نقاط در فضای n بعدی داده ها هستند که مرز دسته ها را مشخص می کنند و مرزبندی و دسته بندی داده ها براساس آنها انجام می شود و با جابجایی یکی از آنها، خروجی دسته بندی ممکن است تغییر کند . به عنوان مثال در شکل فوق ، بردار (۴۵,۱۵۰) عضوی از بردار پشتیبان و متعلق به یک زن است . در فضای دوبعدی ،‌بردارهای پشتیبان، یک خط، در فضای سه بعدی یک صفحه و در فضای n بعدی یک ابر صفحه را شکل خواهند داد.

SVM یا ماشین بردار پشتیبان ، یک دسته بند یا مرزی است که با معیار قرار دادن بردارهای پشتیبان ، بهترین دسته بندی و تفکیک بین داده ها را برای ما مشخص می کند.

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

چگونه یک ماشین بر مبنای بردارهای پشتیبان ایجاد کنیم ؟

به ازای داده های موجود در مثال فوق، تعداد زیادی مرزبندی می توانیم داشته باشیم که سه تا از این مرزبندی ها در زیر نمایش داده شده است.

 

SVM-2

 

سوال اینجاست که بهترین مرزبندی در این مسأله کدام خط است ؟

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

توزیع غیر خطی داده ها و کاربرد ماشین بردار پشتیبان

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

 

SVM-3

 

در این حالت، ما نیاز داریم داده ها را به کمک یک تابع ریاضی (Kernel functions) به یک فضای دیگر ببریم (نگاشت کنیم ) که در آن فضا، داده ها تفکیک پذیر باشند و بتوان SVM آنها را به راحتی تعیین کرد. تعیین درست این تابع نگاشت در عملکرد ماشین بردار پشتیبان موثر است که در ادامه به صورت مختصر به آن اشاره شده است.

با فرض یافتن تابع تبدیل برای مثال فوق،‌ فضای داده ما به این حالت تبدیل خواهد شد :

 

SVM-4

 

در این فضای تبدیل شده، یافتن یک SVM به راحتی امکان پذیر است .

نگاهی دقیق تر به فرآیند ساخت SVM

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

در شکل زیر داده ها در دو دوسته آبی و قرمز نمایش داده شده اند و خطوط نقطه چین ، بردار های پشتیبان متناظر با هر دسته را نمایش می دهند که با دایره های دوخط مشخص شده اند و خط سیاه ممتد نیز همان SVM است . بردار های پشتیبان هم هر کدام یک فرمول مشخصه دارند که خط مرزی هر دسته را توصیف می کند.

SVM-5

SVM‌ در پایتون

برای استفاده از ماشین بردار پشتیبان در پایتون، توصیه بنده استفاده از کتابخانه یادگیری ماشین پایتون به نام scikit–learn است که تمام کرنل ها و توابع نگاشت را به صورت آماده شده دارد. سه تا تابعSVC , NuSVC , LinearSVC وظیفه اصلی دسته بندی را برعهده دارند . (SVC = Support Vector Classifier) . نمونه ای از دسته بندی با این توابع را در زیر می توانید مشاهده کنید :

 

SVM-6

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

برای استفاده از SVM در مورد داده های واقعی ، چندین نکته را باید رعایت کنید تا نتایج قابل قبولی را بگیرید

  1. ابتدا داده ها را پالایش کنید (نقاط پرت ،‌ داده های ناموجود و …..)
  2. داده را عددی و نرمال کنید . این مباحث را در مقالات پیش پردازش داده ها دنبال کنید. به طور خلاصه ، داده هایی مانند جنسیت، رشته تحصیلی و … را به عدد تبدیل کنید و سعی کنید مقادیر همه صفات بین یک تا منهای یک [۱,-۱] نرمال شوند تا بزرگ یا کوچک بودن مقادیر یک ویژگی داده ها،‌ ماشین را تحت تاثیر قرار ندهد .
  3. کرنل های مختلف را امتحان و به ازای هر کدام، با توجه به مجموعه داده آموزشی که در اختیار دارید و دسته بندی داده های آنها مشخص است، دقت SVM را اندازه گیری کنید و در صورت نیاز پارامتر های توابع تبدیل را تغییر دهید تا جواب های بهتری بگیرید. این کار را برای کرنل های مختلف هم امتحان کنید . می توانید از کرنل RBF شروع کنید .

نقاط ضعف ماشین بردار پشتیان

  • این نوع الگوریتم ها، محدودیت های ذاتی دارند مثلا هنوز مشخص نشده است که به ازای یک تابع نگاشت ، پارامترها را چگونه باید تعیین کرد.
  • ماشینهای مبتنی بر بردار پشتیبان به محاسبات پیچیده و زمان بر نیاز دارند و به دلیل پیچیدگی محاسباتی، حافظه زیادی نیز مصرف می کنند.
  • داده های گسسته و غیر عددی هم با این روش سازگار نیستند و باید تبدیل شوند.

با این وجود، SVM‌ ها دارای یک شالوده نظری منسجم بوده و جواب های تولید شده توسط آنها ، سراسری و یکتا می باشد. امروزه ماشینهای بردار پشتیبان، به متداول ترین تکنیک های پیش بینی در داده کاوی تبدیل شده اند.

سخن پایانی

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

ساختار اصلی این نوشتار از روی یک مقاله سایت آنالیتیکزویدیا برداشته شده است و برای دو بخش پایانی مقاله هم از کتاب «داده کاوی پیشرفته : مفاهیم و الگوریتم ها» دکتر شهرابی استفاده شده است .

منبع

آشنایی با ماشین بردار پشتیبان (SVM) – مرور کلی

SVM دقیقا چه چیزی هست؟

SVM یک مدل یادگیری نظارت شده است.

پس قبل از این که به سراغ آن برویم باید یک مجموعه داده(Dataset) که از قبل برچسب‌گذاری شده(Labeled) را داشته باشیم.

مثال: فرض کنیم من صاحب یک کسب‌وکار هستم و هر روز تعداد زیادی ایمیل از مشتری‌ها دریافت می‌کنم. بعضی از این ایمیل‌ها شکایت‌ها و نارضایتی‌هایی هستند که من هرچه سریع‌تر باید به آن‌ها پاسخ بدهم و به آن‌ها رسیدگی کنم. در غیر این صورت کسب‌وکار من با ضرر روبرو خواهد شد.

من به دنبال راهی هستم که این ایمیل‌ها را هرچه سریع‌تر تشخیص بدهم(پیدا کنم) و پاسخ آن‌ها را زودتر از بقیه ارسال کنم.

رویکرد اول: من می‌توانم برچسب‌هایی با عنوان‌های: اورژانسی، شکایت و راهنمایی در جیمیل(GMail) خود ایجاد کنم.

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

رویکرد دوم: من می‌توانم از یک الگوریتم یادگیری ماشین نظارت شده استفاده کنم.

قدم اول: به تعدادی ایمیل نیاز دارم.(هرچه بیشتر بهتر)

قدم دوم: عنوان ایمیل‌های قدم اول رو می‌خوانم و آن‌ها را در یکی از دو گروه «شکایت است» و یا «شکایت نیست» طبقه‌بندی می‌کنم. اینجوری می‌توانم ایمیل‌ها را برچسب ‌گذاری کنم.

قدم سوم: روی این مجموعه داده، مدلی را آموزش می‌دهم.

قدم چهارم: کیفیت یا صحت پیش‌بینی های مدل آموزش داده‌شده را ارزیابی می‌کنم.(با استفاده از روش Cross Validation)

قدم پنجم: از این مدل برای پیش‌بینی این که ایمیل‌های جدیدی که رسیده‌اند، شکایت هستند یا نه، استفاده می‌کنم.

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

همچنین باید به این نکته هم توجه داشته باشیم که قدم دوم اهمیت زیادی دارد و دلیلش این است که اگر در شروع کار، ایمیل‌های برچسب‌گذاری نشده را به SVM بدهیم، کار خاصی را نمیتواند انجام دهد.

SVM یک مدل خطی را یاد می‌گیرد

در مثال قبل دیدیم که در قدم سوم یک الگوریتم یادگیری نظارت شده مثل SVM به کمک داده‌هایی که از قبل برچسب‌گذاری شده‌اند آموزشداده شد. اما برای چه چیزی آموزش داده شد؟ برای این که چیزی را یاد بگیرد.

چه چیزی را یاد بگیرد؟

در مورد SVM، یک مدل خطیرا یاد میگیرد.

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

اگر داده‌های شما خیلی ساده و دو بعدی باشند، در این صورت SVM خطی را یاد می‌گیرد که آن خط می‌تواند داده‌ها را به دو بخش تقسیم کند.

 

svm

SVM قادر است که خطی را پیدا کند که داده‌ها را جدا می‌کند.

 

خب پس اگر SVM فقط یک خط است، پس چرا ما داریم راجع به مدل خطی صحبت می‌کنیم؟

برای این که ما همینطوری نمی‌توانیم به یک خط چیزی را آموزش بدهیم.

در عوض:

  1. در نظر می‌گیریم که داده‌هایی که می‌خواهیم طبقه‌بندی کنیم، می‌توانند به وسیله یک خط از هم تفکیک شوند.
  2. می‌دانیم که یک خط می‌تواند به کمک معادله y=wx+by=wx+b نمایش داده شود.(این همان مدل ما است)
  3. می‌دانیم با تغییر دادن مقدار w و b بی‌نهایت خط وجود خواهد داشت.
  4. برای تعیین این که کدام مقدار w و b بهترینخط جداکننده داده‌ها را به ما می‌دهد، از یک الگوریتم استفاده می‌کنیم.

SVM یکی از این الگوریتم‌ها هست که می‌تواند این کار را انجام دهد.

الگوریتم یا مدل؟

در شروع این پست من نوشتم که SVM یک مدل یادگیری نظارت شده است، و الآن می‌نویسم که آن یک الگوریتم است. چه شده؟ از واژه الگوریتم معمولا آزادانه استفاده می‌شود. برای نمونه، ممکن است که شما جایی بخوانید یا بشنوید که  SVM یک الگوریتم یادگیری نظارت شده است. اگر این نکته را در نظر بگیریم که الگوریتم مجموعه‌ای از فعالیت‌ها است که انجام می‌شوند تا به نتیجه مشخصی دست یابیم، می‌بینیم که استفاده از این واژه در اینجا صحیح نیست(منظور از واژه الگوریتم اینجا الگوریتمی است که برای آموزش از آن استفاده می‌کنیم). بهینه‌سازی متوالی کمینه(Sequential minimal optimization) پر استفاده ترین الگوریتم برای آموزش SVM است. با این حال می‌توان از الگوریتم‌های دیگری مثل کاهش مختصات(Coordinate descent) هم استفاده کرد. در کل بیشتر به جزییاتی مثل این علاقمند نیستند، در نتیجه ما هم برای ساده‌تر شدن فقط از واژه الگوریتم SVM استفاده می‌کنیم(بدون ذکر جزییات الگوریتم آموزشی که استفاده می‌کنیم).

SVM یا SVMها؟

بعضی وقت‌ها می‌بینیم که مردم راجع به SVM و بعضی وقت‌ها هم راجع به SVMها صحبت می‌کنند.

طبق معمول ویکی‌پدیا در روشن و شفاف کردن چیزها به ما کمک می‌کند:

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

پس حالا ما این را می‌دانیم که چندین مدل‌ متعلق به خانواده SVM وجود دارند.

SVMها – ماشین‌های بردار پشتیبان

بر اساس ویکی‌پدیا SVMها همچنین می‌توانند برای دو چیز استفاده شوند، طبقه‌بندی و رگرسیون.

  • SVM برای طبقه‌بندی استفاده می‌شود.
  • SVR یا(Support Vector Regression) برای رگرسیون.

پس گفتن ماشین‌های بردار پشتیبان هم دیگه الآن منطقی به نظر میاد. با این وجود این پایان داستان نیست!

طبقه‌بندی

در سال ۱۹۵۷ یک مدل خطی ساده به نام پرسپترون توسط فردی به نام فرانک روزنبلت برای طبقه‌بندی اختراع شد(که در واقع اساس شبکه‌های عصبی ساده‌ای به نام پرسپترون چند لایه است).

چند سال بعد، واپنیک و چروننکیس مدل دیگری به نام «طبقه‌بندی کننده حداکث حاشیه» پیشنهاد دادند و همان‌جا بود که SVM متولد شد.

در سال ۱۹۹۲ واپنیک و همکارانش ایده‌ای داشتند که یک چیزی به نام کلک کرنل(Kernel Trick) را به روش قبلی اضافه کنند تا به آن‌ها اجازه دهد که حتی داده‌هایی که به صورت خطی تفکیک‌پذیر نیستند را هم طبقه‌بندی کنند.

سرانجام در سال ۱۹۹۵، کورتز و واپنیک، طبقه‌بندی کننده حاشیه نرم را معرفی کردند که به SVM اجازه می‌دهد تا بعضی از اشتباهات در طبقه‌بندی را هم بپذیرد.

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

  1. طبقه‌بندی کننده حاشیه حداکثر.
  2. نسخه‌ای که از کلک کرنل استفاده می‌کند.
  3. نسخه‌ای که از حاشیه نرم استفاده می‌کند.
  4. نسخه‌ای که ترکیب همه موارد قبلی است.

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

به همین دلیل است که وقتی از یک زبان برنامه‌‌نویسی استفاده می‌کنید می‌پرسید از کدام کرنل باید استفاده کنیم(بخاطر کرنل‌های مختلفی که وجود دارند) و یا کدام مقدار ابرپارامتر C را باید استفاده کنید(برای کنترل تاثیر حاشیه نرم).

رگرسیون

در سال ۱۹۹۶، واپنیک و همکارانش، نسخه‌ای از SVM را پیشنهاد دادند که به جای طبقه‌بندی، عمل رگرسیون را انجام می‌دهد. این مورد به Support Vector Regression یا SVR معروف است. همانند SVM در این مدل نیز از کلک کرنل و ابرپارامتر C  استفاده می‌شود.

در آینده مقاله ساده‌ای در مورد توضیح چگونگی استفاده از  SVR در زبان R خواهم نوشت و آدرس آن را همین‌جا قرار خواهم داد.

اگر علاقمند هستید که راجع به SVR بیشتر بدانیند، می‌توانید به این آموزش خوب که نوشته Smola and Schölkopft است، مراجعه کنید.

خلاصه تاریخچه

  • طبقه‌بندی کننده حاشیه حداکثر (۱۹۶۳ یا ۱۹۷۹)
  • کلک کرنل (۱۹۹۲)
  • طبقه‌بندی کننده حاشیه نرم (۱۹۹۵)
  • رگرسیون بردار پشتیبان (۱۹۹۶)

در صورتی که مایلید بیشتر راجع به تاریخچه بدانید، می‌توانید به مقاله مرور همراه با جزییات از تاریخچه مراجعه کنید.

انواع دیگری از ماشین‌های بردار پشتیبان

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

  • ماشین بردار پشتیبان ساخت‌یافتهکه توانایی پیش‌بینی اشیای ساخت‌یافته را دارد.
  • ماشین بردار پشتیبان حداقل مربعکه در طبقه‌بندی و رگرسیون استفاده می‌شود.
  • خوشه‌بندی بردار پشتیبانکه در تحلیل خوشه استفاده می‌شود.
  • ماشین بردار پشتیبان هدایتیکه در یادگیری نیمه نظارت‌شده استفاده می‌شود.
  • SVM رتبه‌بندیبرای مرتب کردن نتایج.
  • ماشین بردار پشتیبان تک کلاسهکه برای تشخیص ناهنجاری استفاده می‌شود.

نتیجه‌گیری

دیدیم که سختی در درک کردن این که SVMها دقیقا چه چیزی هستند، امری طبیعی است. علتش هم این است که چندین SVM برای چندین منظور وجود دارند. مثل همیشه تاریخ به ما اجازه می‌دهد که دید بهتری راجع به چگونگی به وجود آمدن SVMهایی که امروزه وجود دارند، داشته باشیم.

امیدوارم این مقاله دید وسیع‌تری از چشم‌انداز  SVM به شما داده باشد و کمک کرده باشد که بهتر این ماشین‌ها را بشناسید و درک کنید.

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

/0 دیدگاه /توسط

ماشین بردار پشتیبان (svm) قسمت 1

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

ماشین بردار پشتیبان (Support vector machines – SVMs) یکی از روش‌های یادگیری بانظارت است که از آن برای طبقه‌بندی و رگرسیون استفاده می‌کنند.

این روش از جملهٔ روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاریدسته‌بندی کنندۀ SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های QP که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد. قبل از تقسیمِ خطی برای اینکه ماشین بتواند داده‌های با پیچیدگی بالا را دسته‌بندی کند داده‌ها را به وسیلهٔ تابعِ phi به فضای با ابعاد خیلی بالاتر می‌بریم. برای اینکه بتوانیم مسئله ابعاد خیلی بالا را با استفاده از این روش‌ها حل کنیم از قضیه دوگانی لاگرانژ برای تبدیلِ مسئلهٔ مینیمم‌سازی مورد نظر به فرم دوگانی آن که در آن به جای تابع پیچیدهٔ phi که ما را به فضایی با ابعاد بالا می‌برد، تابعِ ساده‌تری به نامِ تابع هسته که ضرب برداری تابع phi است ظاهر می‌شود استفاده می‌کنیم. از توابع هسته مختلفی از جمله هسته‌های نمایی، چندجمله‌ای و سیگموید می‌توان استفاده نمود.

یکی از معروفترین خودآموزها مربوط به است.

کاربردهای SVM

الگوریتم SVM، جز الگوریتم‌های تشخیص الگو دسته بندی می‌شود.از الگوریتم SVM، در هر جایی که نیاز به تشخیص الگو یا دسته بندی اشیا در کلاس‌های خاص باشد می‌توان استفاده کرد.در ادامه به کاربردهای این الگوریتم به صورت موردی اشاره می‌شود:

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

تاریخچه

الگوریتم SVM اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شدو در سال ۱۹۹۵ توسط Vapnik و Corinna Cortes برای حالت غیرخطی تعمیم داده شد.

خلاصه استفاده عملی از SVM

ماتریس الگو را آماده می کنیم. تابع کرنلی را برای استفاده انتخاب می کنیم. پارامتر تابع کرنل و مقدار C را انتخاب می کنیم. برای محاسبه ی مقادیرα_i الگوریتم آموزشی را با استفاده از حل‌کننده‌های QP اجرا می کنیم. داده‌های جدید با استفاده از مقادیرα_i و بردارهای پشتیبان می‌توانند دسته بندی شوند.

مزایا و معایب SVM

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

ماشین بردار پشتیبان خطی

شکل 1

ما مجموعه داده‌های آزمایش {\displaystyle {\mathcal {D}}} شامل n عضو(نقطه)را در اختیار داریم که به صورت زیر تعریف می‌شود:

{\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}

جایی که مقدار y برابر ۱ یا -۱ و هر {\displaystyle \mathbf {x} _{i}} یک بردار حقیقی p-بعدی است. هدف پیدا کردن ابرصفحه جداکننده با بیشترین فاصله از نقاط حاشیه‌ای است که نقاط با {\displaystyle y_{i}=1} را از نقاط با {\displaystyle y_{i}=-1} جدا کند. هر ابر صفحه می‌تواند به صورت مجموعه‌ای از نقاط {\mathbf {x}} که شرط زیر را ارضا می‌کند نوشت:

{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,\,} جایی که . علامت ضرب است. {\displaystyle {\mathbf {w} }} بردار نرمال است، که به ابرصفحه عمود است. ما می خواهیم {\displaystyle {\mathbf {w} }} و {\displaystyle {\mathbf {b} }} را طوری انتخاب کنیم که بیشترین فاصله بین ابر صفحه‌های موازی که داده‌ها را از هم جدا می‌کنند، ایجاد شود. این ابرصفحه‌ها با استفاده از رابطه زیر توصیف می‌شوند.
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=1\,}

و

شکل 2
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=-1.\,}
اگر داده‌های آموزشی جدایی پذیر خطی باشند، ما می‌توانیم دو ابر صفحه در حاشیه نقاط به‌طوری‌که هیچ نقطه مشترکی نداشته باشند، در نظر بگیریم و سپس سعی کنیم، فاصله آن‌ها را، ماکسیمم کنیم. با استفاده از هندسه، فاصله این دو صفحه {\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}} است. بنابراین ما باید {\displaystyle \|\mathbf {w} \|} را مینیمم کنیم. برای اینکه از ورود نقاط به حاشیه جلوگیری کنیم، شرایط زیر را اضافه می کنیم: برای هر i
of the first class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad {\text{ for }}\mathbf {x} _{i}}

یا

of the second class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad {\text{ for }}\mathbf {x} _{i}}

این می‌تواند به صورت زیر نوشته شود:

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.\qquad \qquad (1)}

با کنار هم قرار دادن این دو یک مسئله بهینه‌سازی به دست می‌آید:

Minimize (in {\displaystyle {\mathbf {w} ,b}})

{\displaystyle \|\mathbf {w} \|}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,}

فرم اولیه

مسئله بهینه‌سازی مشاهده شده در قسمت قبل، مسئله سختی، برای حل کردن است، زیرا به||w|| وابسته است (نرم w ) . خوشبختانه می‌توانیم، بدون تغییر در مسئله||w|| را با{\displaystyle {\tfrac {1}{2}}\|\mathbf {w} \|^{2}}جانشین کنیم( عبارت ½ برای آسودگی در محاسبات ریاضی آورده شده). این یک مسئله بهینه سازی (OP)برنامه‌ریزی غیرخطی(QP) است. به‌طور واضح تر :

Minimize (in {\displaystyle {\mathbf {w} ,b}}) c

{\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.}

می توان عبارت قبل را با استفاده از ضرایب نا منفی لاگرانژ به صورت زیر نوشت که در آن ضرایب لاگرانژ هستند {\displaystyle \alpha _{i}}:

{\displaystyle \min _{\mathbf {w} ,b,{\boldsymbol {\alpha }}}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

اما فرمول فوق اشتباه است . فرض کنید ما بتوانیم خانواده‌ای از ابرصفحات که نقاط را تقسیم می‌کنند پیدا کنیم . پس همه {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1\geq 0} . بنا بر این ما می‌توانیم مینیمم را با فرستادن همه {\displaystyle \alpha _{i}} به{\displaystyle +\infty } پیدا کنیم. با این حال شرط پیش گفته می‌تواند به صورت پایین بیان شود:

{\displaystyle \min _{\mathbf {w} ,b}\max _{\boldsymbol {\alpha }}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

ما به دنبال نقاط saddle میگردیم.حالا می‌توان این مسئله را به کمک برنامه‌ریزی غیرخطی استاندارد حل کرد. جواب می‌تواند به صورت ترکیب خطی از بردارهای آموزشی بیان شود :

{\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }}

تنها چند{\displaystyle \alpha _{i}} بزرگتر از صفر خواهد بود.{\displaystyle \mathbf {x_{i}} } متناظر، دقیقاً همان بردار پشتیبان خواهد بود و به شرط را ارضا خواهد کرد. از این می‌توان نتیجه گرفت که بردارهای پشتیبان شرط زیر را نیز ارضا می‌کنند: {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1} که اجازه می دهد مفدار b تعریف شود. در عمل الگوریتم مقاوم تر خواهد بود اگر از تمام {\displaystyle N_{SV}} بردار پشتیبان میانگین گرفته شود:

{\displaystyle b={\frac {1}{N_{SV}}}\sum _{i=1}^{N_{SV}}{(\mathbf {w} \cdot \mathbf {x_{i}} -y_{i})}}

فرم دوگان

استفاده از این واقعیت که {\displaystyle \|\mathbf {w} \|^{2}=w\cdot w} و جانشینی {\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }} می‌توان نشان داد که دوگان SVM به مسئله بهینه‌سازی زیر ساده می‌شود:

Maximize (in {\displaystyle \alpha _{i}} )

{\displaystyle {\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}\mathbf {x} _{i}^{T}\mathbf {x} _{j}=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})}

subject to (for any}{\displaystyle i=1,\dots ,n})

{\displaystyle \alpha _{i}\geq 0,\,}

and to the constraint from the minimization in {\displaystyle b}

{\displaystyle \sum _{i=1}^{n}\alpha _{i}y_{i}=0.}

در اینجا هسته به صورت {\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}} تعریف می‌شود. عبارت \alpha  تشکیل یک دوگان برای بردار وزن‌ها مجموعه آموزشی می دهد:

{\displaystyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\mathbf {x} _{i}.}

ماشین بردار پشتیبان چند کلاسی

SVM اساساً یک جداکننده دودویی است. در بخش قبلی پایه‌های تئوری ماشین‌های بردار پشتیبان برای دسته بندی دو کلاس تشریح شد. یک تشخیص الگوی چند کلاسی می‌تواند به وسیله ی ترکیب ماشین‌های بردار پشیبان دو کلاسی حاصل شود. به‌طور معمول دو دید برای این هدف وجود دارد. یکی از آن‌ها استراتژی “یک در مقابل همه ” برای دسته بندی هر جفت کلاس و کلاس‌های باقی‌مانده‌است. دیگر استراتژی “یک در مقابل یک” برای دسته بندی هر جفت است. در شرایطی که دسته بندی اول به دسته بندی مبهم منجر می‌شود.برای مسائل چند کلاسی٬رهیافت کلی کاهش مسئله ی چند کلاسی به چندین مسئله دودویی است. هریک از مسائل با یک جداکننده دودویی حل می‌شود. سپس خروجی جداکننده‌های دودویی SVM با هم ترکیب شده و به این ترتیب مسئله چند کلاس حل می‌شود.

ماشین‌های بردار پشتیبان غیرخطی

شکل 3

ابرصفحه جداکننده بهینه اولین بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که یک دسته‌کننده خطی بود. در سال ۱۹۹۲ ،Bernhard Boser ، Isabelle GuyonوVapnik راهی را برای ایجاد دسته بند غیرخطی، با استفاده قرار دادن هسته برای پیدا کردن ابرصفحه با بیشتر حاشیه، پیشنهاد دادند. الگوریتم نتیجه شده ظاهراً مشابه است، به جز آنکه تمام ضرب‌های نقطه‌ای با یک تابع هسته غیرخطی جایگزین شداند. این اجازه می‌دهد، الگوریتم، برای ابرصفحه با بیشترین حاشیه در یک فضای ویژگی تغییرشکل داده، مناسب باشد. ممکن است، تغییرشکل غیرخطی باشد و فضای تغییر یافته، دارای ابعاد بالاتری باشد. به هر حال دسته‌کننده، یک ابرصفحه در فضای ویژگی با ابعاد بالا است، که ممکن است در فضای ورودی نیز غیرخطی باشد.

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

  • چندجمله‌ای (همگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} )^{d}}
  • چندجمله‌ای (ناهمگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} +1)^{d}}
  • گوسیین Radial Basis Function:  {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\exp(-\gamma \|\mathbf {x_{i}} -\mathbf {x_{j}} \|^{2})}، for {\displaystyle \gamma >0.} Sometimes parametrized using {\displaystyle \gamma =1/{2\sigma ^{2}}}
  • تانژانت هذلولی: {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x_{i}} \cdot \mathbf {x_{j}} +c)}، for some (not every) {\displaystyle \kappa >0} and {\displaystyle c<0}

هسته با انتقال {\displaystyle \varphi (\mathbf {x_{i}} )} با تساوی {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\varphi (\mathbf {x_{i}} )\cdot \varphi (\mathbf {x_{j}} )} در ارتباط است. همچنین مقدار wدر فضای انتقال یافته برابر{\displaystyle \textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i}).} است. ضرب نقطه‌ای با w می‌تواند توسط هسته محاسبه شود یعنی {\displaystyle \textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}. به هر حال در حالت عادی w’ وجود ندارد، به‌طوری‌که {\displaystyle \mathbf {w} \cdot \varphi (\mathbf {x} )=k(\mathbf {w'} ,\mathbf {x} ).}

 

منبع

 

 

ماشین بردار پشتیبان (svm) قسمت 1
ماشین بردار پشتیبان (svm) قسمت 2
ماشین بردار پشتیبان (svm) قسمت 3

/0 دیدگاه /توسط