STWSVR/Structural twin Support Vector Regression

مجموعه نمونه های مجموعه آموزشی در l بردار سطری تحت عنوان ، ( )، در فضای n بعدی در نظر گرفته می شود. نشان دهنده i امین نمونه آموزشی، مجموعه نمونه آموزشی و بردار پاسخ نمونه های آموزشی که در فضای R خواهد بود.

۱) Twin Support Vector Regression_ TSVR

در این قسمت رگرسیون بردار پشتیبان دو قلو را معرفی کنیم.

رگرسیون بردار پشتیبان دو قلو بسیار شبیه ماشین بردار پشتیبان دو قلو است، همچنین بر اساس استنتاج یک جفت طرح غیر موازی در اطراف نقاط داده ای ارائه شده است. با این حال تفاوت هایی بین این دو روش وجود دارد.

۱) اهداف TSVR و TSVM با هم متفاوت است، هدف TSVR ، یافتن رگرسور مناسب و هدف TSVM، یافتن طبقه بندی مناسب می باشد.

۲) هر دو QPP در TSVM از نمونه فرمول SVM استفاده می کنند به جز الگوهایی در محدودیت های مسئله در همان زمان صدق می کنند، در حالی که تمام نقطه های داده دارای محدودیت هر دو QPP در جفت TSVR استفاده می شود.

۳) هدف TSVM پیدا کردن دو ابر صفحه است به طوری که هر یک از طرح ها به یکی از دو کلاس نزدیک و تا جایی که امکان پذیر است از کلاس دیگر دور باشد. در حالی که هدف TSVR یافتن دو تابع کران بالا و پایین برای رگرسور نهایی می باشد.

TSVR با حل دوQPP زیر به دست می آید:

به عنوان پارامترهای ثابت و به عنوان بردار شلSlack vector در نظر گرفته می شود.

الگوریتم TSVR دو تابع و را می یابدکه هر کدام رگرسور کران بالا و پایین ،را تعیین می نمایند.با داشتن نقاط داده آموزشی ، تابع رگرسور کران پایین و تابع ، Regressor کران بالای را تعیین می کند. رگرسور نهایی توسط میانگین این دو تابع تعیین می شود. دو خط و الزاما با هم موازی نمی باشد. نمای هندسی TSVR در شکل زیر نشان داده می شود.

اولین عبارت در تابع هدف ۱ و ۲ مجموع مربعات فواصل از توابع منتقل شده و به نقاط مجموعه داده های آموزشی است.بنابراین به حداقل رساندن آن منجر به ایجاد یا متناسب با رگرسور ایده آل کران پایین یا کران بالا پایین خواهد شد. محدودیت ها نیازمند تخمین توابع یا در حداقل فاصله یا از مجموعه نقاط داده ای آموزشی است.بنابراین مجموعه داده های آموزشی باید بزرگ تر از تابع با حداقل مقدار و کوچک تر از تابع با حداقل مقدار می باشد.

و slack vector /بردارهای شل به عنوان معیار اندازه گیری خطا در فواصل نزدیک به یا در نظر گرفته می شود. عبارت دوم در تابع هدف به منظور به حداقل رساندن مجموع متغیرهای خطا و تلاش برای over fit نمودن نقاط آموزشی است. به طور خلاصه TSVR شامل یک جفت QPP به طوری که هر یک تابع کران بالا و پایین با استفاده از تنها یک گروه از محدودیت ها در مقایسه با SVR استاندارد می باشد. از این رو TSVR از یک جفت QPP با اندازه کوچک تر سوق پیدا می کند و فرمول یه دست آمده حدود ۴ برابر سریع تر از SVR استاندارد می باشد. دلیل سرعت مذکور ممکن است به دلیل معادله های دوگانه QPP (روابط ۲۱ و۲۲) باشد که در آنها هیچ قید برابری در مقایسه با SVR استاندارد دیده نمی شود.

برای به دست آوردن دوگانه QPP ابتدا تابع لاگرانژ را برای معادله ۱ به صورت زیر تعریف می کنیم:

 

در رابطه فوق به عنوان بردارهای ضریب لاگرانژ در نظر گرفته می شود. شرایط KKT برای رسیدن به نتیجه مطلوب برای معادله ۳ به شرح ذیل محاسبه می شود :

با توجه به رابطه ۶ و شرط ، معادله ۱۰ به صورت زیر به دست می آید:

 

روابط۱۰و ۱۱ را به منظور به دست آوردن مقدار و با هم ترکیب می شود :

 

متغیرهای موجود در رابطه ریاضی قبل را به صورت کلی تر در نظر می گیریم :

 

با جایگذاری مقادیر فوق در رابطه ۱۷، رابطه ۱۹ به صورت زیر حاصل خواهد شد :

 

توجه داشته باشید که همیشه دارای مقدار معین و مثبت می باشد. البته این امکان وجود دارد که برخی مواقع شرایط مقدار بهینه و مطلوبی well conditionنباشد. برای غلبه بر مشکل ذکر شده، عبارت تنظیم کننده تعریف می شود. به گونه ای که یک عدد بسیار کوچک مانند ۱e-7 بوده و معادله ۱۱ به صورت زیر تغییر می یابد.

با جایگذاری معادله ۱۱، شرایط kkt در معادله لاگرانژ، دوگانه رابطه ۱ به صورت زیر به دست می آید:

 

به طور مشابه دوگانه رابطه ۲ به صورت زیر به دست می آید:

 

در رابطه فوق در نظر گرفته می شود. همچنین در موارد مقدار از معادله زیر به دست می آید:

 

شایان ذکر است که در معادله QPP دوگان ۱۳و ۱۴ وارون ماتریس با اندازه محاسبه می شود. به طور کلی مقدار n بسیار کم تر از تعداد نمونه های آموزشی می باشد. علاوه بر این با مقایسه دو QPP بالا با QPP دوگانه معادله (۴) SVR استاندارد، معادله محدودیت دیگری را می یابیم که نشان می دهد TSVR در مقایسه با SVR راه حل بهینه را سریع تر می یابد. علاوه بر این دو پارامتر و در TSVR برای یادگیری وزن در نظر گرفته شده است. بردار در معادله ۱۲، بردار معادله ۱۵ تابع تعیین کننده کران بالا و پایین می باشد.

رگرسور برآورد شده از رابطه زیر به دست می آید :

۲) رگرسیون بردار پشتیبان دو قلو غیر خطی

به منظور گسترش نتایج به رگرسور غیرخطی، توابع ایجاد هسته زیر به جای توابع خطی در نظر گرفته می شود.

مشابه بخش قبل دو مسائل بهینه سازی به صورت زیر ساخته می شود:

 

 

تحت عنوان پارامترهای ثابت و به عنوان بردار شلSlack vector در نظر گرفته می شود. تابع لاگرانژ برای معادله ۱۹ به صورت زیر تعریف می شود:

شرایط KKT برای معادله ۲۰ به شرح ذیل به دست می آید:

 

روابط۲۱ و ۲۲ را به منظور به دست آوردن مقدار و با هم ترکیب می شود :

متغیرهای موجود در رابطه قبل را به صورت کلی تر در نظر می گیریم :

 

با جایگذاری مقادیر فوق در رابطه ۲۷، رابطه ۲۹ به صورت زیر حاصل خواهد شد :

 

در حالت هایی با شرایط نامطلوب از رابطه (۳۰) استفاده می شود.

با جایگذاری شرایط KKT و رابطه (۳۷) در تابع لاگرانژ (۲۸)، دوگان رابطه (۲۶) به صورت زیر استخراج می شود:

 

به طور مشابه معادله (۱۹) را در نظر گرفته و دوگان آن به صورت زیر به دست می آید:

 

که در آن از متغیر به صورت رابطه زیر استفاده شده است.

 

با حل دوگان QPP روابط (۳۱) و (۳۲)، می توان توابع کرانهای بالا و پایین رابطه (۱۷) را به دست آورد، سپس رگرسور نهایی به صورت زیر حاصل می شود:

در موارد غیر خطی ما باید از ماتریس معکوس با مرتبه به جای مرتبه در حالت خطی استفاده می کنیم.می توان از روش Rectagular Kernel برای کاهش ابعاد روابط ۳۱ و ۳۲ استفاده نمود.

این قسمت از مقاله An efficient Twin Support Vector Machine for regression استخراج شده است.

۳) دانه بندی خوشه ای(Cluster granularity)

این دانه بندی ها، زیر مجموعه هایی از داده ها در داخل هر کلاس هستند.در واقع هر کلاس به تعدادی خوشه افراز می شود.میانه و ماتریس کواریانس خوشه iام عبارت است از:

۴) خوشه بندی

خوشه بندی جهت توزیع ذاتی داده ها در هر کلاس استفاده می شود.پس از خوشه بندی، اطلاعات ساختاری به داخل مسئله بهینه سازی اضافه می شود. برای خوشه بندی از الگوریتم سلسله مراتبی ward linkage استفاده می شود.

اگر A و B دو خوشه باشند، W(A,B) (ward’s linkage) به صورت زیر محاسبه می شود:

 

که و میانه های دو خوشه می باشند. هنگامیکه دو خوشه A و B با هم ادغام و خوشه جدید A` را تولید کنند در اینصورت W(A`,C) به صورت زیر محاسبه می شود:

 

در این خوشه بندی، باید در یک مرحله الگوریتم خوشه بندی با رسیدن به تعداد خوشه مورد نظر متوقف شود. بنابراین تخمین تعداد خوشه در این خوشه بندی بسیار مهم است. در مقاله از روش distance curve استفاده شده است. Structural Regularized Support Vector Machine:

AFramework for Structural Large Margin

Classifier∗

 

 

STWSVR/Structural twin Support Vector Regression

TSVR دارای دو تابع و هر کدام کران بالا و پایین ، Regressor را تعیین می نماید.با داشتن نقاط داده ای که ، تابع Regressor کران پایین و تابع ، Regressor کران بالای را تعیین می کند.تابع نهایی Regressor به وسیله میانگین دو تابع ۱ و ۲ تصمیم گیری می شود. دو خط و الزاما با هم موازی نمی باشد.

 

نمونه های مجموعه آموزشی در l بردار n سطری تحت عنوان در فضای n بعدی حقیقی ،

هر کدام از داده ها و

بردار پاسخ نمونه های آموزشی و

ثابت و و به عنوان Slack vector

e : بردار واحد با ابعاد مناسب

: ماتریس کواریانس مرتبط با خوشه ها

با داشتن نقاط داده ای تابع کران بالا و پایین Regressor را تعیین می کند. با حل معادله ۴، با حل معادله ۵ به دست می آید. تابع لاگرانژ معادله ۴ به صورت زیر می باشد:

شرایط KKT به شرح ذیل محاسبه می شود :

 

 

 

با توجه به رابطه ۹ و شرط ، شرط زیر حاصل می شود:

 

به عنوان بردارهای ضریب لاگرانژی در نظر گرفته می شود.

روابط ۷و۸ را به منظور به دست آوردن مقدار و با هم ترکیب می شود :

متغیرهای موجود در رابطه ریاضی قبل را به صورت کلی تر در نظر می گیریم :

 

 

ماتریس ماتریس معین و مثبت است. در محاسبه ، f، G و J مشخص و α نامشخص است. منظور از همان است.

 

با جایگذاری رابطه ۱۳، شرایط KKT در معادله ۶، دوگان رابطه ۶ به صورت زیر حاصل خواهد شد :

از رابطه ۹ به این نتیجه می توان رسید که ،

 

به طور مشابه دوگان معادله (۵) به صورت زیر به دست می آید:

در معادله زیر از متغیرهایی به شرح ذیل استفاده شده است :

 

ماتریس ماتریس معین و مثبت است. در محاسبه ، h، G و J مشخص و γ نامشخص است. منظور از همان است.

 

 

 

شایان ذکر است روابط فوق در حالت غیر خطی نیز تعمیم پذبر است.