اهمیت مسائل چند کلاسه در یادگیری ماشین

اکثر تحقیقات در زمینه یادگیری ماشین متمرکز بر مسائل دوکلاسه هستند. شماری از تکنیک‌های موفق و معروف یادگیری ماشین، نظیر طبقه‌بندی‌کننده‌های تقویتی[1]، بردارهای پشتیبان[2] ^[5] و روش RIPPER [6] در اصل برای مسائل دوکلاسه طراحی شده‌اند [7]. البته لازم به ذکر است که روش RIPPER با هدف حل مسائل چندکلاسه تعریف شد اما این روش در واقع حاصل ترکیب دو روشREP [8] وIREP [9] می‌باشد که هر دوی این روش‌ها در حوزه‌ی مسائل دوکلاسه تعریف شده‌اند. اما واقعیت این است که بسیاری از مسائل طبقه‌بندی در دنیای واقعی ابدا دوکلاسه نیستند بلکه متعلق به مسائل چندکلاسه می‌باشند. احتمال طبقه‌بندی نادرست در مسائل چند‌کلاسه بسیار بالاست و این احتمال با بالا رفتن تعداد کلاس‌ها، به سرعت افزایش می‌یابد [7]. بنابراین واضح است که رسیدن به دقت بالا، در مسائل چندکلاسه، بسیار مشکل‌تر از مسائل دوکلاسه است.

تاکنون روش‌های موثر متفاوتی برای حل مسائل چندکلاسه ارائه شده است. این روش‌ها را می توان به دو دسته کلی تقسیم کرد:

روش‌های مبتنی بر تقسیم-و-تسخیر[3]

روش‌های مبتنی بر تفکیک-و-تسخیر[4]

دسته روش‌های تقسیم-و-تسخیر بر مبنای ایجاد درخت تصمیم‌گیری[5] بر روی داده‌های آموزشی استوار هستند. به این صورت که نقاط تصمیم‌گیری[6] در هر لایه از درخت تصمیم‌گیری، بر اساس آزمایش بر انواع ویژگی‌های[7] داده، محاسبه می‌شود و داده‌ها بر اساس این آزمایش، طبقه‌بندی می‌شوند. این روند به صورت بازگشتی[8] آنقدر انجام می‌شود تا زمانی که دقت مورد نظر کسب شود. از جمله الگوریتم‌های متعلق به این دسته، می‌توان بهCART  [10]،ID3  [11]، C4.5 [6] و توسعه یافته آن C5.0 اشاره کرد که پیچیده‌ترین روش‌های القای درختی[9] در دو دهه اخیر هستند [12].

در روش‌های مبتنی بر تفکیک-و-تسخیر، الگوریتم در هر زمان فقط بر یک کلاس تمرکز می‌کند. به بیان دیگر الگوریتم‌های این دسته سعی دارند که در هر زمان، قوانینی[10] را تولید کنند که بیشترین تعداد داده متعلق به کلاس جاری را به درستی پیدا کرده و تا حد ممکن داده‌های غیر از آن کلاس را نادیده بگیرند. پس از هر دور تولید قانون به روش مذکور، داده‌هایی که درست دسته‌بندی شده‌اند از داده‌های آموزشی حذف شده، سپس مابقی داده‌ها در دورهای آینده به صورت تکرار شونده[11]، با روالی مشابه، مورد آموزش قرار می‌گیرند. الگوریتم‌هایی نظیرPRISM [13]، IREP [9] و RIPPER [6] از معروف‌ترین و موثرترین الگوریتم‌های این دسته می‌باشند.

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

فرنک و ویتن در سال 1998 سعی کردند که دو روش تقسیم-و-تسخیر و تفکیک-و-تسخیر را از طریق استفاده از روش القای جزئی درخت تصمیم‌گیری[12]، ترکیب کنند [14]. روش آنها در واقع یک روش مبتنی بر تفکیک-و-تسخیر بود که تفاوت اصلی آن با سایر روش‌های این دسته در چگونگی تولید قوانین در هر دور از اجرای الگوریتم بود. الگوریتم آنها بر ساختن درخت تصمیم‌گیری هرس شده[13]  در هر دور بر داده‌های موجود و برگزیدن برگ با بیشترین پوشش[14]، استوار بود. این روش ترکیبی، بیش‌هرس‌شدگی[15] را  تخفیف می‌دهد اما نیاز به بهینه‌سازی سراسری[16] دارد [2].

سایر روش‌های اتخاذ شده در راستای حل مسائل چندکلاسه، از روش‌های موفق در زمینه مسائل دوکلاسه بهره می‌جویند؛ به این صورت که سعی دارند این روش‌ها را بر مسائل چندکلاسه به گونه‌ای تطبیق دهند. این در حالی است که به کار گرفتن این استراتژی ساده نیست و در بسیاری از مواقع کاملا غیر عملی است [15]. اچ اس یو و لین [16] طی تحقیقی نشان دادند که استفاده از بردارهای پشتیبان در این شرایط موجب بالا رفتن هزینه آموزش به طرز قابل توجهی می‌شود. بنابر دلایل ذکر شده، یکی از روش‌های متداول، به جای تطبیق دادن الگوریتم‌های حوزه دوکلاسه برای شرایط چندکلاسه، شکستن مساله چندکلاسه به تعدادی مساله دوکلاسه می‌باشد [17]. مزیت استفاده از این روش این است که پیچیدگی برای القای یک طبقه‌بندی‌کننده[17] در این شرایط کاهش می‌یابد. همچنین وقتی که دو برچسب کلاس[18] در هر مقطع زمانی با هم مقایسه می‌شوند امکان جداسازی خطی[19] آنها بسیار بالاست؛ این در حالیست که چنین امکانی در زمانی که همه برچسب‌های کلاس‌ها با هم در نظر گرفته شوند، وجود ندارد.

بنابر تحقیقات و مطالعات اخیر متخصصان در حوزه طبقه‌بندی مسائل چندکلاسه، استفاده از طبقه‌بندی‌کننده‌های سریال[20] برای مواجهه با چالش‌های موجود، هنوز به صورت یک مساله حل نشده و باز پابرجاست [18]. از جمله روش‌های متداول ارائه شده در زمینه طبقه‌بندی‌کننده‌های سریال برای حل مسائل چندکلاسه، می توان به ساخت طبقه‌بندی‌کننده‌های سریال برای هر کلاس و استفاده جداگانه و موازی هر یک از این طبقه‌بندی‌کننده‌های سريال و همچنین ساختن درخت‌های ردیاب سريال[21] اشاره کرد.

[1] Modularized

[2] SVM (Support Vector Machine)

[3] Divide-and-conquer

[4] Separate-and-conquer

[5] Decision tree

[6] Decision point

[7] Feature types

[8] Recursively

[9] Tree Induction

[10] Rules

[11] Iterative

[12] Partial decision-tree induction

[13] Pruned decision tree

[14] Coverage

[15] Over pruning

[16] Global optimization

[17]  Classifier

[18] Class label

[19] Linear separation

[20] Cascaded classifiers

[21] Cascaded detector trees

 

 

بر روی هر تصویر کلیک کنید تا توضیحات کامل هر قسمت را مشاهده فرمایید