بخشی از مقاله
خلاصه
یکی از موضوعاتی که در سال های اخیر مورد توجه پژوهشگران قرار گرفته است، ماشین بردار پشتیبان دوتایی می باشد. برای جداسازی داده ها در این روش به دنبال ابرصفحاتی میگردیم که تا حدامکان به یک کلاس نزدیک و از کلاس دیگر دور باشند. در این مقاله روش ماشین بردار پشتیبان دو تایی با ابرصفحه نرم واحد که به صورت یک مساله غیرخطی مدل می گردد، مورد بررسی قرار می گیرد. روش معرفی شده با روش ماشین بردار پشتیبان دوتایی بر روی داده های استاندارد UCI مقایسه گردیده و نتایج در قالب جدول ارائه شده است.
کلمات کلیدی: جداسازی، ماشین بردار پشتیبان دوتایی، ابرصفحه جداکننده، روش نیوتن.
.1مقدمه
جداسازی داده ها1 در سالهای اخیر بسیار مورد توجه قرار گرفته است. از جمله کاربردهای آن میتوان به شناسایی اعداد و حروف، تشخیص صدا و چهره و دست خط، تشخیص بیماری وکنترل هواپیما بدون خلبان، ردیابی انحراف هواپیما، آنالیز کیفیت جوشکاری، پیش بینی کیفیت، طراحی اعضای مصنوعی، بهینه سازی زمان پیوند اعضاءو ... اشاره نمود 1]و.[2 اولین ایده در جداسازی داده ها -که ماشین بردار پشتیبان2نامیده شد- توسط واپنیک3ارائه گردید 3]و.[4 ماشین بردار پشتیبان در مقایسه با روش های دیگری - از جمله شبکه های عصبی - که برای جداسازی به کار گرفته میشود از دقت و سرعت بسیار بیشتری برخوردار است.
روش های زیادی مانند جداسازی با ابر صفحه جداکننده با بیشترین حاشیه4 برای جداسازی دوتایی، ماشین بردار پشتیبان دوتایی5 ، ابر کره جداکننده دوتایی6و ... مطرح شده اند. در اینجا با استفاده از ایده های مطرح شده در روشهای بردار پشتیبان دوتایی و ابرصفحه جداکننده دوتایی و همچنین نقایصی که مساله ابر صفحه جداکننده دوتایی دارد مدلی برای جداسازی داده ها ارائه گردیده و در بخش نتایجعددی کارایی و عملکرد روش ارائه شده در این مقاله را بررسی میکنیم . نماد ها و علائم در این مقاله به صور زیر نوشته میشوند: ترانهاده ماتریس Aرا با AT نشانمیدهیم. برای دو بردار n مولفهای x و y ، حاصلضرب نقطه ای آنها به صورت xT y تعریفمیشود. برایR x نرم2 را با x نشانمیدهیم. و برای هر،را به صورت تعریف می کنیم .بردار ستونی که تمامیمولفه های آن1باشد با eنشان میدهیم. در اینجا ماتریس همانی را به صورت I n نمایشمیدهیم.
.2ماشین بردار پشتیبان - 1 - SVM
روش ماشینهای بردارپشتیبان، از جمله روشهاسبتاًجدیدین است که درسال های اخیر مورد توجه قرار گرفته است. مبنای کاری دستهبندی کننده - - SVMدسته بندی خطی دادههااست و در تقسیم خطی دادهها سعی میکنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینهبرای دادهها به وسیله روشهای 2QPکه روشهای شناخته شدهای در حل مسائل محدودیتدار هستند، صورت میگیرد. - SVM - هاعموما برای مسائلی که در آن دو دسته وجود دارد و هدف تفکیک دو دسته به دو طبقه ی جدا از هم می باشد، استفاده می شود. - SVM - ها به عنوان یک الگوی قوی طبقه بندی، استفاده می شوند و ایده ی اصلی در - - SVM این است که با فرض جدا پذیری خطی کلاس ها از هم، ابر صفحاتی بیابیم که قادر به جدا نمودن دوکلاس از هم باشد،یک طبقه بندی کننده نه تنها باید قادر به طبقه بندی داده ها باشد بلکه باید ماکزیمم فاصله از نزدیکترین نمونه ی طبقه دیگر را داشته باشد و حاشیه ی بزرگتر قدرت طبقه بندی بیشتری دارد . - این حاشیه3 را با M نمایش می دهیم -
فرض کنیم طبقه ها به صورت خطی قابل تفکیک باشند از این رو یک ابر صفحه بعنوان یک طبقه بندی کننده در نظر گرفته می شود که معادله ی عمومی آن عبارت است از :صفحات و ابر صفحاتی هستند که از طریق نمونه های دو کلاس بدست می آیند . طبقه ای که ابر صفحه ی را براساس داده های آن بدست می آوریم طبقه ی اول و طبقه ای که ابر صفحه ی را براساس داده های آن بدست می آوریم طبقه ی دوم نامیده می شود . و تمام نمونه هایی که در نامعادله ی صدق میکنند ، به طبقه ی اول تعلق دارند و تمام نمونه هایی که در نامعادله ی صدق میکنند ،
به طبقه ی دوم تعلق دارندو تمام نمونه هایی که در نامعادله ی صدق میکنند ، به هیچ طبقه ای تعلق ندارند،،شکل .1یک نمونه در و یک نمونه در استکه نزدیک ترین نمونه به در می باشد. عرض حاشیه ی M می تواند به عنوان فاصله ی بین و با فرمول | باشد و همچنین M بر حسب W بصورت بیان می شود . لذا به ماکزیمم رساندن M معادل است با مینیمم کردن . بنابراین مساله ماشین بردار پشتیبان را با در نظر گرفتن نویزها به صورت زیر می توان فرموله کرد:
این مساله یک مساله ی درجه دوم محدب است که می تواند به روشهای مختلف حل مسائل درجه دوم حل شود .[8 ] با حل مساله - - 1وتعیین بردار w و اسکالر b ، ابر صفحه جداکننده wT x b 0 را برای جداسازی داده ها بدست میآوریم.[3,4,9,10]در بسیاری از مقالات برای حل مسالهSVMمساله دوگان آن را حل میکنند و با نوشتن شرایط1KKT جواب مساله اولیه را از روی جواب بدست آمده از روی مساله دوگان بدست میآورند.
.3ماشین بردار پشتیبان دوتایی - 2 - TWSVM
در دهه ی گذشته شاهد تکامل - SVM - ها بوده ایم یکی از این طبقه کننده ها که ماشین بردار پشتیبان دوتایی - - TWSVM نامیده می شود، به دنبال یافتن دوصفحه ی غیر موازی طبقه بندی کننده ی داده ها به دو کلاس A و B است ، به طوری که هر کدام از صفحات تا حد امکان نزدیک به یکی از دو کلاس و تا جایی که امکان دارد از کلاس دیگر دورتر باشد، شکل .2در - - TWSVMهایک جفت مساله ی برنامه ریزی درجه ی دوم - QPP - حل می شود که در هر مساله ی - QPP - ، تابع هدف متناظر با یک کلاس ویژه و محدودیت ها با الگویی از کلاس دیگر تعیین می گردد.بنابراین، - - TWSVM ها از دومساله ی کوچک - QPP - حاصل می شود.
