w.x+b = -1
w.x+b = 0
SV
SV
SV
کلاس ۱-
کلاس ۱
شکل ۲- ۶: دسته‌بند ماشین بردار پشتیبان [۲۶]
همان‌طور که در شکل (۲-۶) مشاهده می‌شود فراصفحه‌هایی که از نزدیکی داده‌های آموزش می‌گذرند حساس به خطا می‌باشند و احتمال اینکه برای داده‌های خارج از مجموعه آموزش قدرت تعمیم دهی خوبی داشته باشند بسیار کم است. در عوض، به نظر می‌رسد فراصفحه ای که بیشترین فاصله را از تمام نمونه‌های آموزشی دارد قابلیت‌های تعمیم دهی مناسبی را فراهم آورد. نزدیک‌ترین داده‌های آموزشی به فراصفحه‌های تفکیک کننده را بردار پشتیبان (SV^[13]) نامیده می‌شوند [۲۶]. اگر مجموعه داده به صورت  نشان داده شود. Y_i می‌تواند مقدار ۱ و ۱- دریافت کند که توسط این ثابت‌ها دسته‌ه ای نقاط X_i مشخص می‌گردد که هر X_i یک بردار n بعدی است. هنگامی که داده‌های آموزشی که در دسته‌ه ای صحیح دسته‌بندی شده‌اند را در اختیار داریم، SVM توسط تقسیم‌بندی فراصفحه ای آن‌ها را از هم جدا کرده و در دسته‌ه ای جداگانه قرار می‌دهد به طوری که  ، بردار W نقاط عمودی فراصفحه‌ها را جدا می‌کند و b میزان حاشیه را مشخص می‌کند. فراصفحه‌های موازی را می‌توان به صورت  و  تعریف کرد.

اگر داده‌های آموزشی به صورت خطی جدایی پذیر باشند، می‌توان فراصفحه‌ها را به طوری انتخاب نمود که هیچ نمونه‌ای میان آن‌ها نباشد و سپس تلاش کرد تا فاصله آن‌ها را به حداکثر رسانید. برای هر نمونه i از داده‌ها رابطه زیر را داریم:
(۲-۵)  or
(۲-۶)
فاصله بین دو فراصفحه را از طریق تحلیل هندسی با رابطه  می‌توان بدست آورد. بنابراین مسأله بهینه‌سازی ما به صورت زیر خواهد بود:
(۲-۷)  or
می‌توان تصور کرد SVM بین دو دسته داده صفحه‌ای را ترسیم می‌کند و داده‌ها را در دو طرف این صفحه تفکیک می کند. این فراصفحه به گونه‌ای قرار می‌گیرد که ابتدا دو بردار از یکدیگر دور می‌شوند و به گونه‌ای حرکت می‌کنند که هر یک به اولین داده نزدیک به خود برسد. سپس صفحه‌ای که در میان حد واسط این دو بردار رسم می‌شود از داده‌ها حداکثر فاصله را خواهد داشت و تقسیم کننده بهینه است.
تا اینجا، با این فرض که نمونه‌های آموزشی به صورت خطی جدایی پذیرند به استفاده از الگوریتم ماشین بردار پشتیبان پرداختیم. همان‌طور که می‌دانیم در عمل توزیع داده‌های دسته‌ه ای مختلف ممکن است به راحتی جدایی پذیر نبوده و دارای تداخل باشد [۲۶]. در این صورت، تفکیک سازی دقیق نمونه‌ها ممکن است سبب تعمیم دهی ضعیف گردد.
یک راه حل این است که مقداری خطا در دسته‌بندی را بپذیریم. این کار با معرفی متغیر بی دقت^[۱۴] (ξ_i) انجام می‌شود که نشانگر نمونه‌هایی است که توسط تابع  غلط ارزیابی می‌شوند. این روش که به SVM با حاشیه‌ی نرم^[۱۵] معروف است که اجازه می‌دهد بعضی از نمونه‌ها در ناحیه اشتباه قرار گیرند سپس آن‌ها را جریمه می‌کند؛ لذا این روش برخلاف SVM حاشیه‌ی سخت^[۱۶] برای مواردی که نمونه‌های آموزشی به صورت خطی جدایی پذیر نیستند قابل استفاده است.
با معرفی متغیر ξ_i محدودیت‌های قبلی ساده‌تر شده و رابطه (۲-۳) به صورت زیر تغییر می‌کند:
(۲-۸)
شکل ۲- ۷: دسته‌بند ماشین بردار پشتیبان با حاشیه نرم [۲۶]
w
ξ_i
ξ_i

در این صورت مسأله بهینه‌سازی تبدیل می‌شود به یافتن w به نحوی که معادله زیر مینیمم شود:
(۲-۹)
ماشین بردار پشتیبان با حاشیه نرم تلاش می‌کند ξ_i را صفر نگه دارد در حالی که حاشیه‌های دسته‌بند را حداکثر می‌کند. SVM تعداد نمونه‌هایی که به اشتباه دسته‌بندی شده‌اند را کمینه نمی‌کند بلکه سعی دارد مجموع فواصل از حاشیه‌ی فراصفحه‌ها را کمینه نماید [۲۶]. مقادیر بزرگ برای c سبب می‌شود که رابطه (۲-۶) مانند روش با حاشیه سخت عمل کند. ماشین بردار پشتیبان با حاشیه نرم همیشه یک راه حل پیدا می‌کند و در مقابل مجموعه داده‌هایی که دارای یک عضو جدا^[۱۷] هستند مقاوم است و به خوبی عمل می‌کند.

۲-۴-۶- روش‌های مبتنی بر قانون

روش‌های دسته‌بندی مبتنی بر قانون دانش خروجی را به صورت یک مجموعه از قوانین اگر-آنگاه ارائه می‌دهد. این قوانین به صورت زیر می‌باشند:
If <Conditions> then <Class>
که Condition شامل یک مجموعه از شرایط می‌باشد که با عملگرهای منطقی به یکدیگر متصل می‌شوند. هر شرط شامل یک سه‌تایی مرتب <Att_i, Opp, Val_j> می‌باشد که Att_i i امین صفت، Opp عملگر مورد استفاده برای مقایسه یک صفت با یک مقدار است و Val_j نشان دهنده‌ی j امین مقدار دامنه صفت Att_i می‌باشد. به عنوان مثال عبارت <Gender=Male> بررسی می‌کند که آیا مقدار صفت Gender برابر با Male هست یا خیر. در یک مجموعه شرایط نباید دو ترم متناقض وجود داشته باشد. یک قانون تنها در صورتی ارضا می‌شود که کلیه ترم‌های آن ارضا شوند که در این صورت کلاس متناظر رویت می‌شود.
مهم‌ترین مزیت روش‌های دسته‌بندی مبتنی بر قانون، قابلیت تفسیر بسیار مناسب آن‌ها می‌باشد. این قابلیت مهم سبب شده که در سال‌های اخیر توجه بسیاری از پژوهشگران به روش‌های مبتنی بر قانون جلب شود. کاربرانی که از این سیستم‌ها استفاده می‌کنند بیشتر افرادی هستند که در حوزه‌های دیگر فعالیت می‌کنند. به عنوان مثال نباید انتظار داشت که یک پزشک که می‌خواهد از یک سیستم دسته‌بندی استفاده کند، دارای اطلاعات تخصصی در مورد سیستم‌های دسته‌بندی باشد. بنابراین این پزشک نیازمند یک سیستم دسته‌بند است که دانش خروجی را به ساده‌ترین روش ممکن به او نمایش دهد. دیگر مزیت مهم این روش‌ها، نرخ دسته‌بندی قابل قبول سیستم‌های دسته‌بندی که از روش‌های مبتنی بر قانون استفاده می‌کنند می‌باشد. هر چند ممکن است روش‌های دسته‌بندی معروفی مانند SVM و ANN دقت بهتری را فراهم کنند ولی در این روش‌ها کاربر در تفسیر دانش خروجی دچار مشکل می‌شود [۲۷]. در نتیجه روش‌های مبتنی بر قانون که دارای قابلیت تفسیر و دقت مناسبی هستند، می‌توانند بسیار مورد توجه قرار گیرند.
روش‌های گوناگون دسته‌بندی مبتنی بر قانون مانند AQ15، CART، CN2، ID3 و C4.5 را می‌توان به دو دسته کلی تقسیم نمود؛ الگوریتم‌های پوششی ترتیبی و الگوریتم‌های پوششی آنی. الگوریتم‌های پوششی آنی مانند C4.5 و ID3 کل مجموع قوانین را در یک زمان و به صورت گروهی استخراج می‌کنند. این روش‌ها از تقسیم و غلبه برای کشف قوانین استفاده می‌کنند. به این صورت که ابتدا مجموعه آموزش را به زیر مجموعه‌هایی تقسیم نموده سپس برای هر زیرمجموعه یک درخت ایجاد می‌کنند. در مرحله بعدی ساختار هر درخت به قوانین معادل ترجمه می‌شود. الگوریتم‌های پوششی ترتیبی مانند CN2 و AQ15 به صورت افزایشی قوانین دسته‌بندی را کشف می‌کنند. یعنی برای هر قسمت از داده‌های آموزش یک مجموعه از قوانین استخراج شده و از بین این قوانین بهترین قانون انتخاب شده و نمونه‌هایی که توسط این قانون پوشش داده شده‌اند از مجموعه آموزش حذف می‌شوند.
در استخراج مجموعه قوانین از مجموعه داده‌ها با یک مسأله بهینه‌سازی رو به رو هستیم. الگوریتم‌های تکاملی روال‌های جستجوی تصادفی الهام گرفته شده از طبیعت هستند که به عنوان روش‌های بهینه‌سازی استفاده می‌شوند. الگوریتم‌های تکاملی بر روی یک جمعیت از رشته‌ها که بیانگر راه‌ حل ‌های ممکن برای یک مسأله می‌باشند، کار می‌کنند. جمعیت اولیه می‌تواند تصادفی یا به کمک دانش قبلی ایجاد شود. الگوریتم هر یک از رشته راه ‌حل ‌ها را با یک تابع هدف که وابسته به مسأله است ارزیابی می‌کند. رشته‌هایی با کارایی بهتر برای ایجاد رشته‌های جدید مورد استفاده قرار می‌گیرند. الگوریتم‌های تکاملی رشته‌های جدید را با بهره گرفتن از عملگرهای ساده و تصادفی نظیر تبادل و جهش ایجاد می‌کنند و آن‌ها مورد ارزیابی قرار می‌دهند. چرخه انتخاب و ایجاد راه‌ حل ‌های جدید ادامه می‌یابد تا اینکه راه‌حل مطلوب یافت شود و یا یک شرط از پیش تعیین شده برای پایان الگوریتم تکاملی ارضا شود. از روش‌های مهم یادگیری تکاملی می‌توان به الگوریتم ژنتیک، الگوریتم بهینه‌سازی ازدحام ذرات، الگوریتم کلونی مورچه‌ها^[۱۸]، الگوریتم زنبور عسل BA^[19]، الگوریتم رقابت استعماری ICA^[20] و روش SA^[21] اشاره کرد.
الگوریتم ژنتیک یکی از مطرح‌ترین روش‌ها برای استخراج قوانین بوده است. این الگوریتم ابتدا مجموعه از قوانین اولیه را استخراج و سپس با بهره گرفتن از عملگرهای جهش و تبدیل به مرور زمان این قوانین را تکامل می‌دهد تا مجموعه بیشتری از نمونه‌ها را پوشش دهند [۲۸]. شرط پایانی برای این الگوریتم می‌تواند یک تعداد مشخص از تکرارها باشد و یا یک مقدار مشخص از تابع برازش باشد.
الگوریتم ژنتیک به دو دسته عمده پیتسبورگ^[۲۲] و میشیگان^[۲۳] تقسیم می‌شود [۲۸]. در روش پیتسبورگ مجموعه‌ای از قوانین اگر-آنگاه در یک قالب رشته کد می‌شوند در حالی که در روش میشیگان یک قانون اگر-آنگاه به صورت یک رشته کد می‌شود.
روش پیتسبورگ کارایی هر مجموعه از قوانین را به عنوان درجه شایستگی در نظر می‌گیرد. بنابراین جستجو به دنبال مجموعه‌هایی با کارایی بالاتر است. تعدادی از قوانین بدون هیچ تغییری به عنوان قوانین ممتاز از جمعیت کنونی به نسل بعد انتقال می‌یابند. در روش پیتسبورگ یک قانون درون مجموعه خود حائز اهمیت است. چه بسا که قوانین خوبی در مجموعه ضعیفی قرار بگیرند و در روند به روز رسانی یک نسل، نادیده گرفته شوند. از آنجایی که جمعیت شامل تعدادی مجموعه می‌باشد و هر مجموعه نیز شامل تعدادی قانون است، لذا زمان اجرای آن طولانی و فضای حافظه زیادی نیز نیاز می‌باشد.
از سوی دیگر در روش میشیگان یک قانون اگر-آنگاه در قالب یک رشته کد می‌شود و کارایی یک قانون به عنوان درجه شایستگی آن مورد استفاده قرار می‌گیرد. در اینجا نیز تعدادی از قوانین بدون تغییری به عنوان قوانین ممتاز به نسل بعد منتقل می‌شوند. از آنجایی که در روش میشیگان جمعیت مورد بررسی در هر لحظه فقط شامل تعدادی قانون است، بنابراین زمان محاسبات و فضای حافظه‌ی مورد نیاز بسیار کم‌تر از روش پیتسبورگ است. در واقع می‌توان روش یادگیری به صورت آنی را معادل روش پیتسبورگ و روش یادگیری ترتیبی را معادل روش میشیگان دانست.
یکی از شاخه‌های مهم الگوریتم‌های تکاملی روش‌های هوش جمعی می‌باشند که شامل الگوریتم‌هایی نظیر الگوریتم بهینه‌سازی ازدحام ذرات، الگوریتم کلونی مورچه‌ها و الگوریتم رقابت استعماری می‌باشند. این الگوریتم‌ها قادر هستند یک جواب مناسب را برای مسأله با ابعاد بالا پیدا کنند. مهم‌ترین تفاوت این الگوریتم‌ها با سایر الگوریتم‌های تکاملی، ارتباط عامل‌ها با یکدیگر است که به صورت غیر مستقیم است [۱۳]. این قابلیت به آن‌ها اجازه می‌دهد تا به صورت توزیع شده بخش اعظمی از فضای جستجو را پوشش دهند و در نتیجه شانس الگوریتم برای یافتن یک راه‌حل مناسب افزایش یابد.

۲-۵- الگوریتم بهینه‌سازی ازدحام ذرات

الگوریتم بهینه‌سازی ازدحام ذرات و کلا الگوریتم‌هایی که از مفهوم حرکت دسته جمعی حیوانات نظیر دسته‌ه ای ماهی و پرندگان الگو گرفته‌اند، سعی در به کار بردن ذراتی با هوش کم و در عین حال استفاده از هوش گروهی برخاسته از جمعیت دارند [۲۹]. از زمان معرفی PSO در سال ۱۹۹۵ [۳۰]، الگوریتم بهینه‌سازی ازدحام ذرات کاربردها و بهبودهای زیادی پیدا کرده است. بسیاری تغییرات در PSO اولیه، باعث بهبود همگرایی^[۲۴] PSO و افزایش تنوع پراکندگی^[۲۵] ازدحام ذرات شده است.
یک الگوریتم PSO، اجتماعی از ذرات با خصوصیات مربوطه را نگهداری می‌کند، که هر ذره نشان دهنده یک راه‌حل بالقوه است. در قیاس با نمونه‌های محاسبات تکاملی، یک ازدحام، تشکیل شده از تعدادی ذرات می‌باشد که شبیه به یک جمعیت است در حالی که ذرات، همان افراد را تشکیل می‌دهند. به عبارت ساده‌تر، ذرات در یک فضای جستجوی چندبعدی حرکت می‌کنند که موقعیت هر ذره، به وسیله‌ی دانش خود ذره و دانش همسایگانش تنظیم می‌شود. اگر x_i(t) نشان دهنده‌ی موقعیت فعلی ذره‌ی i ام در فضای جستجو در زمان t باشد، موقعیت آتی ذره i ام به وسیله‌ی جمع سرعت جدید همان ذره v_i(t+1)، با موقعیت فعلی آن، طبق رابطه‌ی زیر محاسبه می‌شود:
(۲-۱۰)
الگوریتم بهینه‌سازی ازدحام ذرات مانند هر الگوریتم تکاملی دیگر دارای دو فاز مقدار دهی اولیه^[۲۶] و تکامل^[۲۷] است. در شروع، مکان اولیه ذرات با رابطه‌ی توزیع تصادفی نرمال  مقداردهی اولیه می‌شود. در مرحله تکامل، ذرات در فضای راه‌حل با به روز کردن خود بر طبق وضعیت فعلی خود و اطلاعات گذشته به سمت مقادیر بهینه حرکت می‌کنند تا شرایط پایانی رخ دهد.
به طور کلی، متغیر سرعت است که فرایند بهینه‌سازی را به جلو می‌راند و نشان دهنده‌ی دانش تجربی ذره و تبادل اطلاعات اجتماعی از همسایگان ذره است. دانش ذره، که نشأت گرفته از تجربه‌ی شخصی آن می‌باشد، معمولاً به مولفه‌ی ادراکی ذره اشاره می‌کند که متناسب با فاصله ذره از بهترین موقعیت پیدا شده از لحظه شروع فرایند است که به بهترین خاطره شخصی ذره معروف است. تبادل اطلاعات اجتماعی هر ذره به مولفه‌ی اجتماعی معادله‌ی سرعت اشاره می‌کند. مولفه‌ی اجتماعی به دانش جمعی که می‌تواند از تمام ذرات یا بخشی از ذرات نشأت گرفته باشد اشاره دارد، که متناسب با فاصله ذره از بهترین موقعیت پیدا شده توسط تمام ذرات از لحظه شروع فرایند است که به بهترین خاطره جمعی معروف است.
(۲-۱۱)
که در آن  ضریبی از حرکت در جهت قبلی یا اینرسی، v_ij(t) سرعت ذره i ام در بُعد j=1,…,n در زمان t و x_ij(t) موقعیت ذره i ام در بعد - j ام در زمان t است و c1 و c2 فاکتورهای افزایش سرعت هستند که به ترتیب برای سنجش سهم مولفه‌های ادراکی و اجتماعی می‌باشند. r₁(t), r₂(t) ~ U(0,1) به صورت تصادفی با توزیع یکنواخت به دست می‌آید. این مقادیر تصادفی، معرف بخش اتفاقی در این الگوریتم است. بهترین موقعیت شخصی y_i، مربوط به ذره i ام، بهترین موقعیت مشاهده شده توسط ذره از ابتدای فرایند است. بهترین موقعیت سراسری یا جمعی  ، بهترین موقعیت مشاهده شده توسط تمام ذرات از ابتدای فرایند است. الگوریتم بهینه‌سازی ازدحام ذرات در شکل (۲-۸) خلاصه شده است.
Algorithm PSO
Create and initialize an n_x-dimensional swarm;