بخشی از مقاله
*** اين فايل شامل تعدادي فرمول مي باشد و در سايت قابل نمايش نيست ***
بهبود دقت الگوریتم ماشین بردار پشتیبان (SVM) با تکنیک انتخاب ویژگی
خلاصه
بشر با پیشرفت فناوري در ثبت و ذخیره سازي داده ها و پردازش آنها گامی بزرگ جهت کسب دانش برداشته است. در واقع داده نمایش از واقعیت ها، معلومات، مفاهیم، رویدادها یا پدیده ها براي براقراري ارتباط، تفسیر یا پردازش، توسط انسان یا ماشین است. از داده کاوي، به عنوان مرحله اي از فرایند کشف دانش که الگوها و یا مدل ها را در میان انبوهی از داده ها پیدا می کند، یاد می شود. یکی از مهمترین وظایف داده کاوي، طبقه بندي است. طبقه بندي فرآیند یافتن مدلی که کلاس ها یا مفهوم داده را براي پیش بینی نمونه هایی با برچسب نامشخص، تشخیص و تشریح کند . روش هاي بسیاري جهت ساختن مدل هاي طبقه بندي وجود دارد از جمله طبقه بندي بیزین، ماشین بردار پشتیبان، نزدیک ترین همسایگی و...می باشند. هدف این تحقیق، بهبود دقت الگوریتم ماشین بردار پشتیبان( SVM) 3 است. SVM ابزاري کارامد در یادگیري ماشین می باشد اما قادر به انتخاب ویژگی هاي مهم نیست. در این مقاله، با ترکیب ماشین بردار پشتیبان پروگزیمال(PSVM) 4 و استراتژي انتخاب ویژگی سعی بر انتخاب ویژگی هاي مهم و استفاده آن براي طبقه بندي می باشد.
کلمات کلیدي: داده کاوي، ماشین بردار پشتیبان پروگزیمال (PSVM)، انتخاب ویژگی
-1 مقدمه
بشر با پیشرفت فناوري در ثبت و ذخیره سازي دادهها و پردازش آنها گامی بزرگ جهت کسب دانش برداشته است. در واقع داده نمایشی از واقعیتها، معلومات، مفاهیم، رویدادها یا پدیده ها براي برقراري ارتباط، تفسیر یا پردازش، توسط انسان یا ماشین است. از طرف دیگر واژه اطلاعات، به معنی دانشی که از طریق خواندن، مشاهده و آموزش بدست میآید اطلاق میشود و در حقیقت میتوان گفت اطلاعات دادههایی هستند که پس از جمعآوري پردازش شدهاند و شکل مفهومی تولید کردهاند. به بیان دیگر اطلاع حاصل تکامل دادهها است. به این ترتیب بین دادهها و اطلاعات یک شکاف وجود دارد که اندازه این شکاف با حجم دادهها ارتباط مستقیم دارد. هرچه دادهها حجیمتر باشند، این شکاف بیشتر خواهد بود و هر چه حجم دادهها کمتر وروشها و ابزار پردازش دادهها کاراتر باشد، فاصله بین دادهها و اطلاعات کمتر است .[1] امروزه افزایش سریع حجم پایگاه دادهها به شکلی است که توانایی انسان براي درك این دادهها بدون ابزار پرقدرت میسر نمیباشد. در این وضعیت، تصمیمگیري ها به جاي تکیه بر اطلاعات بر درك مدیران و کاربران تکیه دارند، چرا که تصمیم گیرندگان ابزار قوي براي استخراج اطلاعات با ارزش را در دست ندارند. در واقع شرایط فعلی توصیف کننده حالتی است که ما از لحاظ داده غنی، اما از لحاظ اطلاعات ضعیف هستیم.[2]
مبناي ارزیابی الگوریتمهاي یادگیري دقت دستهبندي، صحت راه حل و کیفیت آن و سرعت عملکرد میباشد. دادهکاوي5 فرآیندي است که در آغاز دهه 90 مطرح شد و با نگرشی نو، به مسئلهي استخراج اطلاعات از پایگاه دادهها6 میپردازد. از سال 1995 داده کاوي به صورت جدي وارد مباحث آمارشد. محققانی نظیر Bracman و (1996) Anand کلیه مراحل واقعگرایانه و رو به جلو کشف دانش از پایگاه دادهها را تشخیص دادند. طبقهبندي یکی از عملیات رایج مورد استفاده در داده کاوي است. طبقه بندي عملیاتی است که سازمانها را قادر می سازد که در حل مسائل خاص در مجموعههاي بزرگ و پیچیده به کشف الگوها دست یابند. طبقهبندي فرآیندي می باشد که مجموعه دادهها را به قسمتهاي مشخص تقسیم میکند.[3]
در این مقاله، از برنامهریزي ریاضی و روشهاي مبتنی بر بهینه سازي، به منظور بررسی و ایجاد مدل یادگیري هدایت شده جهت طبقهبندي دادهها استفاده میکنیم. مدل مورد استفاده ترکیب ماشین بردار پشتیبان پروگزیمال((PSVM و یکی از استراتژيهاي انتخاب ویژگی میباشد که از طریق ایجاد زیر مجموعه اولیه از ویژگیها با استراتژي جستجو وحل مدل بر اساس معیار تعریف شده، می باشد.
-2 مرور ادبیات
اولین الگوریتم براي طبقهبندي و دستهبندي الگوها در سال 1936 توسط Fisher ارائه شد و معیار آن براي بهینه بودن، کم کردن خطاي طبقهبندي الگوهاي آموزشی بوده است. بسیاري از الگوریتمها و روشهایی نیز که تا کنون براي طراحی طبقه بندي کنندههاي الگو طراحی شده است، از همین استراتژي پیروي می کنند .[4]
محقق روسی بنام Vapnik در سال 1965 گامی بسیار مهم در طراحی دستهبندي کنندهها برداشت و نظریه آماري یادگیري را به صورت مستحکمتري بنا نهاد و ماشین بردار پشتیبان((SVM را بر این اساس ارائه داد.
در سال 1965، Mangasarian یک طبقهبندي کننده با حاشیهي بزرگ را با استفاده از تکنیک هاي بهینهسازي به صورت مدل برنامهریزي خطی تنظیم و ارائه کرد و نشان داد که دستهکنندههاي خطی و غیرخطی بوسیلهي برنامهریزي خطی قابل دست یابی هستند.[5] بین سالهاي 1980 تا 1990 ، Freed وGlover چند مدل برنامه ریزي خطی را به منظور حل مسائل تفکیککننده با نمونه کوچک دادهها ارائه نمودندSVM .[6] به شکل نزدیک به روش فعلی، براي اولین بار در قالب یک مقاله در سال 1992 توسطBoser و همکاران معرفی شد .آنها همچنین در این مقاله راهی را براي ساخت طبقهبندي کنندههاي غیر خطی با حداکثر حاشیه با استفاده از کاربرد حقه کرنل در نگاشت غیرخطی ابرصفحههاي بهینه به فضاي ویژگی(با ابعاد بیشتر) ارائه کردند. براي این منظور الگوریتم Chunking جهت حل مدل ارائه گردید .[ 7] در سال 1995، Cortes وVapnik ، ایدهي حداکثر حاشیهي اصلاح شده را مطرح نمودند. در این روش خطاي طبقهبندي نادرست در مدلSVM در نظر گرفته شده است و الگوریتم حداکثر حاشیه با تعریف متغیر کمبود در مدل سازي، به مسائلی که بصورت خطی جداپذیر نیستند، تعمیم داده شد.
Fung و Mangasarian در سال 2001 مدلی را با عنوان PSVM ارائه دادند. این مدل به جاي ماشین بردار پشتیبان استاندارد، که دادهها را با اختصاص آنها به یکی از دو ابر صفحه مجزا طبقهبندي میکند، آنها را بوسیلهي اختصاصشان به نزدیکترین دو صفحه ي موازي (در فضاي ورودي یا ویژگی) که تا حد امکان از هم فاصله گرفتهاند (حداکثر حاشیه) دستهبندي میکند. این فرمول که می تواند به عنوان حداقل مربعات منظم تفسیر شود و در بسیاري از زمینههاي عمومی شبکههاي منظم در نظر گرفته شود، منجر به الگوریتم بسیار سریع و ساده براي ایجاد دسته کنندهي خطی یا غیرخطی که صرفا مستلزم حل سیستم واحد معادلات خطی میشود . نتایج محاسباتی روي پایگاه داده هاي در دسترس نشان میدهد که دسته کنندهيPSVM داراي مجموعه آزمون قابل مقایسهي صحت نسبت به SVM استاندارد است اما با زمان محاسباتی بسیار سریعتر میباشد. همچنین Fung وMangasarian در این تحقیق نشان دادند که PSVM خطی مجموعه دادههاي بزرگ را براي مثال 2 میلیون نقطه با 10 ویژگی را در 20.8 ثانیه طبقهبندي میکند .[8]
Peng و همکاران در سال 2002 بهبود یافته روش برنامه ریزي خطی Shi را براي طبقهبندي چند گروهی پیشنهاد دادند .[9]
Chen و همکاران در سال 2010 روش آماري دو مرحلهایی را براي برنامهریزي بارش روزانه ارائه دادند. قدم اول طبقهبندي جهت تعیین اینکه روز خشک یا مرطوب است؟ و دوم رگرسیون براي تخمین میزان بارش شرطی در دقت یک روز مرطوب است. پیش بینی کنندههاي مدلهاي رگرسیون و طبقه بندي از متغیرهاي بزرگ مقیاس آب و هوا در آزمونهاي آماري انتخاب شدهاند. روش آماري پیشنهاد شده با توجه به دو روش توسعه یافته است. روش اول SVM است که شامل طبقه بندي بردار پشتیبان (SVC) و رگرسیون بردار پشتیبان((SVR است و دیگري تحلیل چند متغیري شامل تحلیل مجزا براي SVM و رگرسیون مضاعف است .[10]
-3 طبقه بندي در داده کاوي
الگوریتمهاي دادهکاوي سه رویکرد یادگیري مختلف را دنبال میکنند: بانظارت، بدون نظارت و نیمه نظارتی. در یادگیري با نظارت الگوریتم با مجموعهاي از مثالها که برچسب کلاس شان مشخص است کار میکند . برچسبها میتوانند ارزش اسمی در حالت طبقهبندي و ارزش عددي در حالت رگرسیون داشته باشند. در مقابل، در یادگیري بدون نظارت برچسبهاي نمونهها در مجموعه دادهها نامشخص است و الگوریتم تلاش میکند که نمونهها را براساس شباهت ارزشهاي ویژگیشان گروهبندي کند. در نهایت، یادگیري نیمه نظارتی زمانی استفاده میشود که زیر مجموعهي کوچکی از نمونههاي برچسبشدهبا تعداد زیادي از نمونههاي بدون برچسب موجود باشد.[11]
طبقهبندي را میتوان به عنوان یک روش بانظارت که در آن هر نمونه متعلق به یک کلاس با ویژگی خاص میباشد، دانست. هر نمونه شامل دوقسمت است: مجموعه مقادیر ویژگی پیشبینی کننده و مقدار ویژگی هدف. اولین مورد براي پیشبینی ارزش بعدي استفاده میشود. ویژگیهاي پیشبینی کننده باید براي پیشبینی کلاس یک مورد مناسب باشد. در طبقهبندي مجموعه نمونههاي استخراج شده به دو مجموعهي انحصاري متقابل و جامع که مجموعهي آموزش و آزمایش گفته میشوند، تقسیم
میشود. دانش کشف شده بوسیلهي الگوریتم طبقهبندي را میتوان از طریق راههاي مختلف بیان کرد که شامل: قوانین7، درخت هاي تصمیم، شبکهي بیزین8، .[12] SVM
- 1 – 3 ماشین بردار پشتیبان پروگزیمال((PSVM
ماشین بردار پشتیبان استاندارد که ابزار قوياي براي طبقهبندي دادهها است، دادهها را با اختصاص شان به یکی از دو ابرصفحهي مجزا، طبقهبندي میکند. این ابرصفحهها، هم در فضاي ورودي اصلی مسئله براي دستهکنندههاي خطی و یا در فضاي ویژگی با ابعاد بالاتر براي دستهکنندههاي غیرخطی، هستند. چنین SVM استانداردي نیازمند حل مسئلهي خطی و یا درجهي دو است. در مقابل، PSVM داده ها را با توجه به نزدیکی شان به یکی از دو صفحات موازي که تا حد امکان از هم فاصله گرفتهاند (حداکثر حاشیه) طبقهبندي میکند. تحدب قوي و زمان محاسباتی سریع، نقش کلیدي را در PSVM بازي میکند. بدست آوردن دستهکنندة PSVM خطی و غیرخطی نیازمند هیچ چیز پیچیدهتري غیر از حل یک سیستم واحد از معادلات خطی (1) و (2) نیست.
لازم به ذکر است که هیچ محدودیت غیرمنفی براي مورد نیاز نیست زیرا اگر هر مؤلفهي منفی باشد، آنگاه تابع هدف میتواند با مساوي صفر قرار دادن کاهش یابد، در حالیکه محدودیت نامساوي مربوطه را برآورده میکند.
دقت شود که بردار خطاي در (1) مینیمم میشود و حاشیهي بین صفحات مرزي باتوجه به بردار قائم wو مکان مربوطه نسبت به مبدأ b ماکزیمم میشود. نتایج محاسباتی نشان داده است که این فرمولبندي، به خوبی فرمولبندي SVM کلاسیک با مزایاي بیشتري مانند تحدب قوي تابع هدف میباشد.[13]
باتوجه به شکل ( 1) صفحات دیگر صفحات مرزي نیستند اما میتوان به عنوان صفحات "پروگزیمال" حوالی نقاط دستهبندي شدهاي که بوسیلهي تابع هدف تا جاي ممکن از هم دور شده اند در نظر گرفت که نرم دو مجذور فاصله متقابل بین دو صفحه در (w,b) فضاي است.
-4 انتخاب ویژگی
هنر یادگیري ماشین با طراحی تضمینی اطلاعات مناسب شروع میشود. عملکرد بهتر اغلب با استفاده از ویژگیهاي بدست آمده از ورودي اصلی نتیجه میشود. ساختن یک نمونه از ویژگی، فرصتی است براي ترکیب دانش تخصصی با داده که بسیار کاربردي میباشد. این تکنیک چه در عمل و چه در تئوري تأثیر خود را در افزایش کارایی یادگیري، افزایش دقت پیشبینی و کاهش پیچیدگی نتایج آموزش داده شده، نشان داده است. هدف اصلی انتخاب ویژگی، انتخاب زیرمجموعهي متغیرهاي ورودي با حذف متغیرهاي نامربوط و یا متغیرهایی که فاقد اطلاعات پیشگویانه هستند، می باشد .[14]
انتخاب ویژگیهاي بهینه، لایهي اضافی پیچیدگی را در مدلسازي می افزاید، به جاي پیدا کردن پارامترهاي بهینه براي مجموعه کامل ویژگیها، ابتدا زیرمجموعهي ویژگی بهینه یافت میشود و سپس پارامترهاي مدل بهینه میشوند. انتخاب ویژگی تمرکز بسیاري از تحقیقات در زمینههاي کاربردي براي مجموعه دادههایی با دهها، صدها و هزاران متغیر را شامل میشود .[15]
هدف از انتخاب ویژگی، بهبود عملکرد پیشبینی، ارائهي پیشبینی سریعتر و مقرون به صرفهتر و ارائهي درك بهتر از روند اطلاعات تولید شده است.
