روش «یک در مقابل یک (One vs. One)» در طبقه‌بندی

مدرس: مسعود کاویانی

MasoudKaviani.ir

اگر درس قبل را خوانده باشید، می‌دانید که یکی از روش‌های طبقه‌بندی (Classification) داده‌های چند کلاسه، استفاده از روشِ «یک در مقابل همه» یا همان One vs. All است. اما این روش، در برخی از مواقع ضعف‌هایی نیز دارد. به همین دلیل روش «یک در مقابل یک» یا همان One vs. One به وجود آمد که در بسیاری از مواقع، کیفیتِ به مراتب بهتری، نسبت به روش قبلی (One vs. All) ارائه می‌دهد.

فرض کنید، مجموعه‌ی داده‌ی شما، ۱۰هزار نمونه داشته باشد. این ۱۰هزار نمونه در ۲۰ طبقه (کلاس) تقسیم بندی شده‌اند و شما به دنبال الگوریتمی هستید که بتواند بر روی این داده‌ها، طبقه‌بندی (Classification) را انجام دهد. اگر مانند درس قبلی، از روش «یک در مقابل همه» استفاده کنید، نیاز به ۲۰ مجموعه‌ی داده دارید، تا یکی یکی، هر کدام از نمونه‌های یک طبقه را در مقابل نمونه‌های بقیه‌ی طبقه‌ها قرار دهید. در واقع در هر مجموعه‌ی داده، ۵۰۰ نمونه از یک کلاس در مقابل ۹۵۰۰ نمونه از کلاس‌های دیگر قرار می‌گیرند و یک الگوریتم طبقه بند دودویی، بایستی بتواند طبقه‌بندی را برای این دو کلاس انجام دهد. به این حالت که تعداد نمونه‌های داخل یک کلاس خیلی کمتر از نمونه‌های یک کلاس دیگر باشد، حالت نامتوازن (imbalance) در طبقه‌بندی گفته می‌شود که در درسِ «داده‌های نامتوازن» در مورد آن صحبت کردیم. این عدمِ توازن، باعث می‌شود کیفیت الگوریتمِ طبقه‌بندیِ دودویی کم شوند و در نهایت الگوریتمِ نهایی که همان الگوریتم «یک در مقابل همه» است، نتواند دقت و کیفیت مورد نظر را فراهم کند.

در این دست از مسائل، می‌توان به الگوریتم «یک در مقابل یک (One vs. One)» رجوع کرد. این الگوریتم همانند الگوریتم «یک در مقابل همه (One vs. All)» عمل می‌کند با این تفاوت که در این الگوریتم، ما مجموعه داده‌ی کل را طوری تقسیم بندی می‌کنیم که نمونه‌های هر جفت از کلاس‌ها در مقابل یکدیگر قرار بگیرند. در واقع تقسیم‌بندی به گونه‌ای انجام می‌شود که در هر مجموعه‌ی داده‌ی تقسیم شده، نمونه‌های یک طبقه در مقابل نمونه‌های یک طبقه‌ی دیگر قرار داشته باشند.

اجازه بدهید به مثال درس قبل برگردیم. اگر یادتان باشد می‌خواستیم ایمیل‌ها را به سه طبقه‌ی عادی/اسپم/تبلیغاتی طبقه‌بندی کنیم. در روشِ «یک در مقابل یک (One vs. One)» نیاز به سه مجموعه‌ی داده جدا داریم:

۱. مجموعه‌ی داده‌ای که در آن ایمیل‌های عادی در مقابل ایمیل‌های اسپم باشند
۲. مجموعه‌ی داده‌ای که در آن ایمیل‌های عادی در مقابل ایمیل‌های تبلیغاتی باشند
۳. مجموعه‌ی داده‌ای که در آن ایمیل‌های اسپم در مقابل ایمیل‌های تبلیغاتی باشند

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

روشِ «یک در مقابل یک» به تعداد بیشتری زیر مجموعه داده نیاز دارد. برای مثال اگر داده‌های شما در N طبقه برچسب خورده باشند، نیاز به N*(N-1)/2 زیر مجموعه‌ای هست که به صورت جفتی، نمونه‌های هر کلاس را در مقابل نمونه‌های کلاس دیگر قرار دهد. ولی در روش «یک در مقابل همه» فقط به N زیر مجموعه داده نیاز داریم. پس برای مثال اگر داده‌های ما در ۲۰ طبقه برچسب خورده باشد، در روش «یک در مقابل یک» نیاز به ۱۹۰ زیر مجموعه داده داریم در حالی که در روش قبلی (یک در مقابل همه) فقط به ۲۰ زیر مجموعه داده نیاز داشتیم. طبیعتاً برای هر کدام از مسائل در دنیای واقعی با توجه به دقت و سرعت مورد نیاز، می‌توان از یکی از این روش‌ها استفاده کرد.