به استفاده جداگانه از هر کدام از اين روش ها نشان ميدهد]18[.

فصل سوم:
روش تحقيق

3-1مقدمه
الگوريتم هاي متفاوتي براي بهبود SVM و بهبود نتايج ارائه شده است. در فصل قبل ماشين بردار پشتيبان و همچنين مفاهيم فازي و تکنيک حداقل مربعات را شرح داديم.در اين فصل به بررسي الگوريتم هاي ماشين بردار پشتيبان حداقل مربعات130(LS-SVM) و ماشين بردار پشتيبان فازي131(FSVM) ميپردازيم.
3-2 ماشين بردار پشتيبان فازي براي يادگيري عدم توازن کلاس132
مطالعات به خوبي نشان مي دهد که SVM علاوه بر عدم تعادل، به نويز و داده هاي پرت موجود در مجموعه داده نيز حساس است.بنابراين مي توان ادعا کرد که اگرچه روش هاي يادگيري عدم تعادل موجود ميتوانند باعث کاهش حساسيت الگوريتم SVM به عدم توازن شوند، اما اين الگوريتم هنوز به نويز و داده هاي پرت موجود در مجموعه داده حساس است که هنوز باعث توليد مدل هايي با بهينگي کمتر از حد مطلوب ميشود.در واقع برخي از روش هاي يادگيري عدم تعادل مانند بيش نمونه برداري تصادفي و SMOTE، با تکثير نمونه هاي نويزي و داده هاي پرت موجود، ميتوانند مشکل را بدتر کنند.
روش ماشين بردار پشتيبان فازي براي يادگيري عدم توازن کلاس(FSVM-CIL)، يک روش بهبود يافته ازSVM است که مسئوليت رسيدگي به مشکل عدم توازن کلاس و همچنين داده هاي نويزي و پرت را دارد]34[.اکنون اين روش را با جزئيات بيشتر مورد بررسي قرار ميدهيم.
3-2-1 روش SVMFuzzy
در الگوريتم SVM استاندارد، اهميت تمام نقاط داده يکسان در نظر گرفته ميشود و در تابع هدف به همه انها يک هزينه طبقه بندي اشتباه يکسان اختصاص داده ميشود که اين امر ميتواند در مجموعه داده هاي نامتوازن، منجر به توليد مدل هايي با بهينگي کمتر از حد مطلوب شود.همچنين اين امر(اختصاص اهميت يکسان به تمام نقاط داده)، ميتواند باعث حساسيت SVM به نويز و دادههاي پرت نيز شود.حضور داده هاي پرت و نمونه هاي نويزي(به خصوص در اطراف منطقه مرزي کلاس) ميتواند موقعيت و جهت ابر صفحه جدا کننده را تحت تاثيرقرار دهد و منجر به توليد مدل هايي با بهينگي کمتر از حد مطلوب شود.
به منظور کاهش حساسيت SVM نسبت به نمونه هاي نويزي و داده هاي پرت، تکنيک FSVM ارائه شده است]34[.در اين روش، به نمونه هاي مختلف، مقادير عضويت فازي متفاوتmi،(وزن) اختصاص داده ميشود که اين مقادير نشان دهنده اهميت انها در کلاس هاي خودشان است.mi0 است.بنابراين به نمونه هاي مهم تر مقادير بالاتر ، و به نمونه هايي با اهميت کمتر(مانند نويز و داده هاي پرت)، مقادير پايين تر اختصاص داده ميشود. سپس مشکل بهينه سازي حاشيه نرم SVM را ميتوان به صورت زير بازنويسي کرد :

در اين فرمول، درجه عضويت m_i نيز که مربوط به داده x_i است،در مقدار هزينه خطاي مربوطه نقش دارد و هرچه مقدار m_i کمتر باشد، تاثير متغير کمبود ?_i در تابع هدف کاهش مييابد.اگر C را به عنوان هزينه اختصاص داده شده براي طبقه بندي اشتباه(خطا) درنظر بگيريم، اکنون ديگر هزينه طبقه بندي اشتباه براي هر نقطه داده متفاوت خواهد بود.زيرا متغير m_i اضافه شده است و اين هزينه از طريق m_i C بدست ميآيد.در واقع اين هزينه، برمبناي اهميت هر نمونه در کلاس خودش است و به داده هاي مهم تر، هزينه هاي بيشتري اختصاص داده ميشود.بنابراين الگوريتم FSVM ميتواند از طريق به حداکثر رساندن حاشيه، ابرصفحه جداکننده قوي133 تري را پيدا کند. به حداکثر رساندن حاشيه به اين طريق صورت ميپذيرد که ما مقداري طبقه بندي اشتباه براي نمونه هايي با اهميت کمتر( مانند نويز و داده پرت) را بپذيريم.
به منظور حل مشکل بهينه سازي FSVM، فرمول (3-1) به مساله دوگان لاگرانژ زير تبديل ميشود:

در واقع تفاوت بين SVM فازي با SVM استاندارد در اين است که حد فوقاني ضريب لاگرانژ ?_i برابر m_i C است، در حالي که در SVM استاندارد اين حد برابر C است.با حل مشکل دوگان در فرمول (3-2)، w و b ميتوانند به همان روشي که در SVM استاندارد اعمال ميشود، بهبود يابند. از تابع تصميم گيري SVM که در فرمول (3-2) بيان شد، ميتوان براي روشهاي FSVM نيز استفاده کرد.
3-2-2متد FSVM-CIL
اگرچه روش هاي CIL 134موجود که قبلا مورد بحث قرار گرفت ميتواند بر مشکل عدم توازن غلبه کند اما اين روش ها هنوز به نويز و داده پرت حساس هستند. از سوي ديگر اگرچه روش FSVM ميتواند بر مشکل نويز غلبه کند اما از مشکل عدم توازن رنج ميبرد زيرا در اين الگوريتم براي کاهش حساسيت به عدم توازن، هيچ تغييري در مقايسه با الگوريتم SVM اصلي صورت نگرفته است و هزينه هايي که براي طبقه بندي اشتباه اختصاص داده ميشود، عدم توازن کلاس را در نظر نميگيرد. در روش FSVM-CIL، روش FSVM استاندارد با روش DEC ترکيب ميشود.اين ترکيب باعث بهبود روش FSVM استاندارد ميشود.در اين روش، مقادير عضويت به گونه اي انتخاب ميشوند که دو هدف زير ارضا شوند:
براي خنثي کردن تاثير عدم توازن کلاس
براي بازتاب اهميت داخل کلاسي نمونه هاي آموزشي مختلف، تا تاثير داده هاي پرت و نويز خنثي شود.
درجه عضويت داده مثبتx_i^+، با m_i^+ و درجه عضويت داده منفي x_i^-، با m_i^- در کلاسهاي خودشان نمايش داده ميشود.در روش FSVM-CIL ارائه شده، تابع هاي عضويت به صورت زير بيان ميشود :

f(x_(i ))مقداري بين صفر و يک را توليد ميکند که اين مقدار نشان دهنده اهميت xi در کلاس خود است. r^+و r^- بازتابي از عدم توازن کلاس است، .به طوري که r^+= 1 و .r نشان دهنده نسبت کلاس اقليت ب.ه اکثريت است(r^+r^-).(از روشDEC زماني ميتوان نتايج بهينه بدست آورد که C^-?C^+ با نسبت کلاس اقليت به اکثريت برابر باشد).
با توجه به مقادير اختصاص داده شده ، هزينه طبقه بندي اشتباه براي داده کلاس مثبت برابر با mi+C است که مقدار mi+ در فاصله ]0،1[ است.درحالي که هزينه طبقه بندي اشتباه براي داده کلاس منفي برابر با mi-C است. مقدار mi- در فاصله [0,r] است و r<1 است. تابع f(x_i) اهميت داخلي کلاس براي نمونه اموزشي را تعيين ميکند.براي تعريف اين تابع، متدهاي زير در نظر گرفته شده است]34[. 1. f(x_i)بر مبناي فاصله نمونه از مرکز کلاس خود در اين روش، f(x_i) با توجه بهdicen تعريف شده است و فاصله بين xi و مرکز کلاسي که xi در ان قرار دارد را نشان ميدهد. نمونه هايي که به مرکز کلاس نزديک تر باشند نمونه هاي مفيدتري هستند و مقدار f(x_i) بيشتري به آنها اختصاص داده ميشود.در حالي که با نمونه هاي دور از مرکز کلاس به عنوان نويز و داده پرت برخورد شده و مقدار f(x_i)کمتري به انها اختصاص داده ميشود. در اينجا براي تعريف f(x_i) از دو تابع کاهش135 جداگانه استفاده شده است که با f_(lin )^cen (xi) و f_(exp )^cen (xi) نمايش داده ميشود. تابع کاهش خطي است. ?مقدار کوچک مثبتي است که از صفر شدن تابع f(x_i) جلوگيري ميکند. يک تابع نمايي کاهش است که ? ،[0,1]?? ، شيب کاهش136 را مشخص ميکند.d_i^cen=?x_i-x ? ?^(1/2) فاصله اقليدسي xi تا مرکز کلاس خود يعني x ? است. 2. f(x_i) بر مبناي فاصله از ابرصفحه جداکننده اي که از قبل تخمين زده شده137 است. در اين روش، f(x_i)با توجه بهd_i^sph تعريف شده است و فاصله بين xi و ابرصفحه جداکننده از قبل تخمين زده شده را نشان ميدهد. در اينجا d_i^sph از طريق فاصله xi از مرکز ناحيه کروي متداول138 تخمين زده ميشود که مي تواند به صورت ابر کره اي تعريف شود که ناحيه همپوشان دو کلاس را پوشش ميدهد. براي تعريف f(x_i) از هر دو تابع کاهش نمايي و خطي استفاده ميشود، که به شکل هاي زير نمايش و محاسبه ميشوند. کهd_i^sph=?x_i-x ? ?^(1/2) و x ? مرکز ناحيه کروي است، که توسط مرکز کل مجموعه داده مثبت و منفي تخمين زده شده است. ? مقدار کوچک مثبتي است و [0,1]?? است. 3. f(x_i) بر مبناي فاصله از ابرصفحه جداکننده واقعي139 در اين روش، f(x_i) بر مبناي فاصله از ابرصفحه جداکننده واقعي تا xi است، که از طريق آموزش مدل SVM مرسوم بر مجموعه داده متوازن بدست آمده است. نمونه هايي که به ابرصفحه جداکننده واقعي نزديک تر باشند نمونه هاي مفيدتري هستند و مقدار عضويت بيشتري به انها اختصاص داده ميشود.در حالي که با نمونه هاي دور از ابرصفحه جداکننده به عنوان نمونه هاي کم اهميت برخورد شده و مقدار عضويت کمتري به انها اختصاص داده ميشود. براي تخصيص مقادير f(x_i )، رويه زير انجام ميشود : يک مدل SVM نرمال را با مجموعه داده نامتوازن اصلي آموزش دهيد. براي هر نمونه xi ، حاشيه عملکردي140d_i^(hyp ) را پيدا کنيد(در معادله (3-7) ) ، با توجه به ابر صفحه جداکننده. حاشيه عملکردي متناسب با حاشيه هندسي يک نمونه آموزشي نسبت به ابرصفحه جداکننده است. هر دو تابع کاهش نمايي و کاهش خطي را به صورت زير براي تعيين f(x_i) درنظر بگيريد ? مقدار کوچک مثبتي است و [0,1]?? است. تحقيقات نشان ميدهد که استفاده از روش FSVM-CIL در مقايسه با ساير روش هاي يادگيري عدم توازن کلاس، نتايج طبقه بندي بهتري را ايجاد ميکند]34[.کارايي بهتر اين روش ناشي از اين است که علاوه بر مشکل عدم توازن، توانايي برخورد با نويز و داده هاي پرت را نيز دارا است. 3-3 ماشين بردار پشتيبان حداقل مربعات (LS-SVM) از زماني که ماشين هاي بردار پشتيبان معرفي شدند، با توسعه بي شماري از آن ها مواجه شده ايم.دراين قسمت روي يکي از آن ها موسوم به ماشين هاي بردار پشتيبان حداقل مربعات بحث خواهيم کرد.Suykens و همکارانش ماشين هاي بردار پشتيبان حداقل مربعات L2براي مسائل دو کلاسه را در سال 1999 پشنهاد دادند. در اين نوع ماشين هاي بردار پشتيبان حل دستگاه خطي جايگزين مسائل برنامه ريزي کوادراتيک ميگردد.در واقع با تغييراتي روي ماشين هاي بردار پشتيبان حاشيه نرم L2،LS-SVM ها بوجود آمدند. دراولين تغيير، جاي در تابع هدف ،مربع را قرار دادند و در دومين تغيير، محدوديت هاي نامساوي با متغير کمبود جاي خود را به محدوديت هاي مساوي با متغير کمبود ميدهند.با اين فرمول بندي مسئله به شکل يک دستگاه خطي ظاهر ميشود که با روش هاي تکراري مانند روش گراديان مزدوج ميتوانيم آن را حل نمائيم.از طرفي مطالعات تجربي گسترده نشان دهنده برتري محاسباتيLS-SVM نسبت به L1-SVM در عملکرد تعميم ميباشد.اين ويژگي ها از LS-SVM اين الگوريتم را نسبت به L1-SVM موفق تر ميگرداند که در زير اين فرمولبندي را ارائه ميدهيم: مانند آنچه قبلاً گفته شد چون حل اين مسئله سخت است به خاطر همين با کمک قضيه لاگرانژ شکل ديگر آن را مينويسيم: - امين ضريب لاگرانژ است.مسئله موجود به يک مسئله پيچيده تر تبديل شده است که در آن مسئله بايد به ازاي متغير بايد ماکزيمم و به ازاي متغيرهايو بايد مينيمم شود. بنابراين براي حل اين مسئله بايدو را از مسئله حذف کرد(اگررا از مسئله حذف کنيم دقيقاً شبيه معادله (3-10)ميشود). در واقع يک مسئله دوگان مسئله (3-11) را حل ميکنيم و بعد از طريق آن مقادير متغيرهاي اصلي را بدست ميآوريم.براي حذف متغير هاي گفته شده بايد: سيستم بدست آمده از شرايط KKT خطي است.راه حل آن است که سيستم را توسط دستگاه معادلات خطي که توسط ماتريس زير بيان ميشود حل کرد.روابط بدست آمده را در مسئله (3-11) قرار ميدهيم. که، ماتريس واحد، برداري -بعدي با درايه هاي 1 ، و است]37[. در مساله بالا از ضرايب لاگرانژ استفاده شده است .تابع لاگرانژ ثابت است و قابليت تغيير ندارد . ما در اينجا از تابع جديدي به نام تابع جريمه استفاده مي کنيم.تابع جريمه تغيير ميکند و با تغيير آن ميتوان به بهبود نتايج کمک کرد.با استفاده از تابع جريمه ميتوان مسائل مقيد را به نامقيد تبديل کرد. روشهاي بکارگيري توابع جريمه يک مساله مقيد را به يک مساله نامقيد منحصر به فرد و يا اينکه به يک دنباله از مسائل نامقيد تبديل ميکند.در چنين روشي که هرگونه تخطي از قيود را جريمه ميکند، قيود همراه با يک پارامتر جريمه در تابع هدف واقع ميشوند. براي تفهيم توابع جريمه، مساله زير با يک قيد منحصر بفرد h(x)=0 را در نظر بگيريد. Min f(x) S.to: h(x)=0 فرض کنيد که مساله فوق با مساله مقيد زير جابجا شود که در آن µ>0 عدد بزرگي است.
Min f(x)+ ?h^2 (x) s.to :x?E_n

از اينکه مساله مينيمم کردن مي باشد، بايد توان مربوط به آن مثبت باشد که چنين است.توان دو به خاطر مثبت بودن ?h^2 (x) (عبارت جريمه) مي باشد.
اگر مساله ماکسيمم کردن ميبود،عبارت جريمه ميبايست يک مقدار منفي درنظر گرفته ميشد.
مستقيما ميتوان ديد که يک جواب بهينه براي مسائل فوق بايد داراي h2(x) نزديک به صفر باشد.چون در غير اين صورت، مساله، جريمه زياد را متحمل خواهد شد.
مساله زير با قيد منحصر بفرد به شکل نامساوي را در نظر بگيريد:
Min f(x)
S.to : g(x)=0
واضح است که شکل f(x)+?g^2 (x) مناسب نيست چون g(x) خواه مثبت يا منفي باشد، تابع هدف مساله، جريمه اي را متحمل خواهد شد.نياز است بگوييم تنها موقعي تابع جزيمه اي را متحمل ميشود که نقطه نشدني باشد يعني g(x)0 .بنابراين يک مساله نامقيد مناسب در اين حالت به صورت زير است :
Min f(x)+ ? max??{0,g(x)} S.to :x?E_n ?

اگر g(x)=0، آنگاه max {0,g(x)}=0 .در اين صورت مساله فوق هيچگونه جريمه اي را متحمل نخواهد شد.حال اگر g(x)0 باشد(يعني x نشدني است.)، آنگاه max {0,g(x)}=g(x)0. در اين صورت عبارت جريمه ?g(x) که يک مقدار مثبت است، به تابع هدف اضافه مي شود.
به طور کلي يک تابع جريمه بايد جريمه مثبت را براي نقاط نشدني در نظر بگيرد و براي نقاط شدني هيچگونه هزينه اي در نظر نگيرد.
حال براي مسائل صورت نامقيد زير را خواهيم داشت.(براي ?0 به اندازه کافي بزرگ)
Max f(x) max??f(x)-?h^2 (x) ?
S.to : h(x)=0
Max f(x) max??f(x)-?max?{0,g(x)} ?
S.to : g(x)?0

Max f(x) max??f(x)-?[min?{0,g(x)} ]^2 ?
S.to : g(x)?0

Max f(x) min??f(x)-?[min?{0,g(x)} ]^2 ?
S.to : g(x)?0
در واقع اگر بيان رياضي مساله که در فرمول (2-17) ارائه شده است را ميتوان به صورت زير به شکلي ديگر در آورد و در ان از توابع جريمه متفاوت استفاده کنيم.
max??(-1)/2 w.w-C?_(i=)^l??m_i ?_i-?{min?{0,g(x)}}^2 ??

3-4 الگوريتم پيشنهادي
در الگوريتم پيشنهادي از ترکيب دو روش استفاده ميشود.بدين صورت که ابتدا داده ها را با استفاده از روش تبديل سريع فوريه( FFT141 )تبديل ميکنيم.سپس LS-SVM را بر روي آن اعمال مينماييم.تبديل سريع فوريه نام الگوريتمي ا‌ست براي انجام تبديلات مستقيم و معکوس گسسته فوريه به صورتي سريع و بسيار کارآمد. تعداد زيادي الگوريتم‌هاي تبديل فوريه سريع مجزا وجود دارد که شامل محدوده عظيمي از رياضيات مي‌شوند.يک تبديل فوريه سريع تجزيه يک رشته از مقادير به مولفه‌هايي با فرکانس‌هاي متفاوت است. اين عمليات در بسياري از رشته‌ها مفيد است.تبديل فوريه سريع يک راه براي محاسبه همان نتايج به طور سريع تر است.محاسبه تبديل فوريه گسسته براي n نقطه با استفاده از تعريف O(n^2) عمليات رياضي نياز دارد در حالي که تبديل فوريع سريع مي‌تواند همان نتايج را در O(n?log?^n) عمليات، محاسبه نمايد.اين تفاوت در سرعت مي‌تواند بسيار چشمگير باشد، مخصوصا براي مجموعه داده‌هاي بزرگ. در جايي که n ممکن است در عمل هزاران يا ميليون‌ها باشد، زمان محاسبه در برخي موارد مي‌تواند به اندازه چند مرتبه کاهش پيدا کند و بهبود آن در حدود n??log?^n مرتبه‌است. اين بهبود عظيم موجب شده تا بسياري از الگوريتم‌هاي عملي تبديل فوريه گسسته را به صورت تبديل فوريه سريع پياده سازي نمايند. بنابراين تبديل فوريه سريع در محدوده متنوعي از کاربردها از پردازش سيگنال ديجيتال و حل معادلات ديفرانسيل با مشتقات جزئي(پاره‌اي) تا ضرب مقادير بزرگ صحيح به کار مي‌رود.
با استفاده FFT داده هاي را به داده هاي تبديـل ميکنيم.b_j از طريق زير محاسبه ميشود.
b_j=?_(k=0)^(n-1)??a_j w^kj , j=0,1,…,n?
wيک ريشه nام واحد است. w=Cis 2?/n
b_0=a_0+a_1+…+a_(n-1)
b_1=a_0+a_1 w+…+a_(n-1) w^(n-1)
b_2=a_0+a_1 w^2+…+a_(n-1) w^(2(n-1))
b_(n-1)=a_0+a_1 w^(n-1)+…+a_(n-1) w^(?(n-1)?^2 )
الگوريتم FFT را به صورت زير تعريف ميکنيم:
FFT(a_0, a_1,…,a_(n-1),b_0,b_1,…,b_(n-1))
if(n==1) b[0]=a[0];
else {
FFT(a_0, a_2,…,a_(n-2),u_0,u_1,…,u_(n/2-1))
FFT(a_1, a_3,…,a_(n-1),v_0,v_1,…,v_(n/2-1))
Z=1;
for (j=1;jn ;j++)
{ b[j]=u[j %n/2]+z*v[j %n/2];
z*=w;
}
}

فصل چهارم:
محاسبات و يافته هاي تحقيق

4-1 مقدمه
در اين پايان نامه براي بهبود مساله شناخت الگو روش پيشنهادي با روش هاي متفاوتي مقايسه شده است.با وجود اينکه ماشين بردار پشتيبان کارايي تعميم بهتري در مقايسه با تعداد زيادي الگوريتم هاي ماشين يادگيري ديگر دارد اما به علت حل QP داراي پيچيدگي محاسباتي بالايي است و نسبت به noise حساس است و زماني که تعداد الگوهاي يک کلاس بيشتر از اندازه تعداد الگوهاي کلاس ديگر باشد در SVM مشکل ايجاد ميشود.

4-2 مجموعه داده ها
در اين تحقيق از مجموعه داده هاي UCI استفاده شده است.جزييات اين مجموعه داده ها در جدول 4-1 نشان داده شده است. Pos.نشان دهنده تعداد نمونه هاي مثب

دسته بندی : No category

دیدگاهتان را بنویسید