تفاوت تکنیک یکی در مقابل همه با تکنیک یکی در مقابل یکی


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

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

صورت مسئله و ابزار

برای اینکه درک مباحث راحت باشد با یک مسائل ساده دو تکنیک را توضیح میدهیم. فرض کنید یک مسئله سه کلاسه داریم که داده‌های هر کلاس به صورت  زیر در فضای ویژگی دو بعدی توزیع شده اند.

تکنیک یکی در مقابل همه و مسئله چندکلاسه

و ابزاری که داریم یک مدلی هست که میتواند مرز خطی(یا غیرخطی) بین دو کلاس را پیدا کند. به عبارتی تنها یک مرز تفکیک کننده بین دو کلاس میتواند پیدا کند. حال چطور از این مدل دو کلاسه برای پیدا کردن مرز بین داده های سه کلاس استفاده کنیم؟ فرض براین است که این الگوریتم توان حل مستقیم مسائل چندکلاسه را ندارد. مثل طبقه‌بند SVM.

 

تکنیک یکی در مقابل همه (one versus rest)

در تکنیک یکی در مقابل همه برای حل یک مسئله چندکلاسه از چند تا طبقه‌بند دو کلاسه استفاده می‌کنند. در این تکنیک برای هر طبقه‌بند یک وظیفه خاص تعیین می‌کنند.

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

در این تکنیک به ازای هر کلاس، یک طبقه‌بند دو کلاسه نیاز هست. یعنی اگر یک مسئله سه کلاسه داشته باشیم، سه تا طبقه‌بند دو کلاسه نیاز هست.

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

تکنیک یکی در مقابل همه

پروسه آموزش طبقه‌بندها در تکنیک یکی در مقابل همه

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

  • داده‌ کلاس یک برای طبقه‌بند اول:  داده‌ی کلاس یک
  • داده کلاس دو برای طبقه‌بند اول:  داده ی سایر کلاسها (2-3)
  • داده ی کلاس یک برای طبقه‌بند دوم:  داده‌ی کلاس 2
  • داده کلاس دو برای طبقه‌بند دوم:  داده ی سایر کلاسها (3-1)
  • داده ی کلاس یک برای طبقه‌بند سوم:  داده‌ی کلاس 3
  • داده کلاس دو برای طبقه‌بند سوم:  داده ی سایر کلاسها (2-1)

حال هر کدام از طبقه‌بند براساس پایگاه داده‌ای که دارند مرز تفکیک کننده بین دو کلاس را پیدا می‌کنند.

تکنیک یکی در مقابل همه

پروسه تصمیم‌گیری در تکنیک یکی در مقابل همه

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

تکنیک یکی در مقابل همه

برای اینکار در تکینک یکی در مقابل همه نمونه به ترتیب به تک تک طبقه‌بندها ارائه می‌شود. برای مثال در ابتدا به طبقه‌بند اول ارائه می‌شود. اگر طبقه‌بند اول تشخیص دهد که داده مربوط به کلاس یک هست. در این صورت همانجا پروسه تصمیم‌گیری تمام می‌شود و داده به کلاس 1 تعلق دارد. ولی اگر طبقه‌بند اول لیبل 2 برگرداند معنیش این هست که به کلاس یک تعلق ندارد و مربوط به سایر کلاسها هست. در این صورت نمونه به طبقه‌بند دوم ارائه می‌شود، اگر طبقه‌بند دوم لیبل یک برگرداند معنیش این است که نمونه‌ی جدید مربوط به کلاس دو هست در غیراینصورت مربوط به کلاس سه و یا نمونه ناشناخته هست. در ادامه نمونه جدید به طبقه‌بند سوم ارائه میشود. اگر طبقه‌بند سوم لیبل یک برگرداند معنیش این است که داده مربوط به کلاس 3 است و در غیراینصورت داده ناشناخته هست و جزء هیچ کدام از کلاسها نیست.

 

ناحیه تصمیم‌گیری در تکنیک یکی در مقابل همه

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

ناحیه تصمیم گیری تکنیک یکی در مقابل همه

مزیت تکنیک یکی در مقابل همه

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

معایب تکنیک یکی در مقابل همه

همانطور که در شکل هم مشخص هست تکنیک یکی در مقابل همه دارای دو مشکل اساسی است:

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

 

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

 

تکنیک یکی در مقابل یکی(one versus one)

تکینک یکی در مقابل یکی همانند تکنیک یکی در مقابل همه از چندین طبقه‌بند دو کلاسه برای حل مسئله استفاده می‌کند. منتهی در این تکنیک هر طبقه‌بند دو وظیفه مشخص دارد و به عبارتی یک مسئله دو کلاسه را حل می‌کند. برای مثال طبقه‌بند اول وظیفه دارد که مشخص کند داده مربوط به کلاس یک هست یا دو. یا طبقه‌بند دوم وظیفه‌‍اش این است که مشخص کند نمونه جدید مربوط به کلاس یک هست یا سه. به همین ترتیب سایر طبقه‌بندها هم چنین وظیفه ای دارند.

در تکنیک یکی در مقابل یکی، برای هر مسئله دو کلاسه یک طبقه‌بند دو کلاسه نیاز هست. برای مثال اگر مسئله ما سه کلاس باشد، سه تا طبقه‌بند دو کلاس نیاز هست.: طبقه‌بند اول: (1-2)، طبقه‌بند دوم: (1-3)، طبقه‌بند سوم: (2-3)

تکنیک یکی در مقابل یکی

اگر مسئله چهار کلاسه باشد در این صورت 6 تا مسئله دو کلاسه خواهیم داشت و برای همین به 6 تا طبقه‌بند دو کلاسه نیاز داریم.

[1-2], [1-3], [1-4], [2-3], [2-4], [3-4]

همانطور که میبیند در این تکنیک به ازای هر مسئله دو کلاسه یک طبقه بند دو کلاسه نیاز هست. و واضح است که هر چقدر تعداد کلاس زیاد شود، به مراتب تعداد طبقه بند ها زیاد خواهد شد.

برای مثال فرض کنید مسئله 10 کلاسه هست. الان به چند تا طبقه بند نیاز هست؟؟

 

پروسه آموزش طبقه‌بندها در تکنیک یکی در مقابل یکی

در پروسه آموزش برای هر طبقه‌بند یک داده اموزش دو کلاسه در نظر می‌گیرند و به ترتیب اموزش می‌دهند. برای مثال در این مسئله سه کلاسه، طبقه‌بند اول را با کمک داده کلاس یک و دو آموزش می دهند تا بتواند تشخیص دهد که داده ورودی مربوط به کلاس یک هست یا دو. ، طبقه‌بند دوم را با کمک داده کلاس یک و 3 آموزش می‌دهند تا بتواند تشخیص دهد که داده ورودی مربوط به کلاس یک هست یا 3. طبقه‌بند سوم را با کمک داده کلاس 2 و 3 آموزش می‌دهند تا این طبقه‌بند بتواند تشخیص دهد که داده ورودی مربوط به کلاس 2 هست یا 3.

تکنیک یکی در مقابل یکی

پروسه تصمیم‌گیری در تکنیک یکی در مقابل یکی

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

تکنیک یکی در مقابل یکی

ناحیه تصمیم‌گیری در تکنیک یکی در مقابل یکی

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

ناحیه تصمیم گیری در تکنیک یکی در مقابل یکی

مزایا

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

معایب

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


 


دیدگاه ها

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

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

*

code