دانلود مقاله الگوریتم سیستم ایمنی مصنوعی بهبود یافته در انتخاب ویژگی و بهینهسازی پارامترهای ماشین بردار پشتیبان

بخشی از مقاله

چکیده-
در سالهای اخیر الگوریتم سیستم ایمنی مصنوعی بر پایه انتخاب کلونال به عنوان یک روش محاسبه نرم الهام گرفته شده از سیسـتم ایمنی طبیعی جهت حل مسائل علمی و مهندسی معرفی شده است. ماشین بردار پشتیبان یک روش معروف در کلاسهبندی الگـو در کاربردهـای متنوع میباشد که انتخاب پارامترهای کرنل در مرحله آموزش همراه با انتخاب ویژگیها در این کلاسهبند تأثیر قابل تـوجهی بـر محاسـبه میـل ترکیبی در الگوریتم سیستم ایمنی مصنوعی دارد. روش پیشنهادی با انجام عمل فراجهش و کلونیسازی متناسب با میـل ترکیبـی در الگـوریتم انتخاب کلونال، نتیجه مطلوبی را در زمینه کاهش ویژگی ارائه میدهد. نتایج شبیهسازی روی برخی مجموعه دادههای معروف پایگـاه داده UCI،
کارایی این روش را نشان میدهد.

کلید واژه- الگوریتم انتخاب کلونال، الگوریتم سیستم ایمنی مصنوعی بهبود یافته، انتخاب ویژگی، بهینهسازی پارامترها، کلاسهبند ماشین بردار پشتیبان.

-1 مقدمه

به دلیل وجود شباهتهایی بین مفاهیم پایه تئوریهای محاسباتی در الگوریتمهای تکاملی و سیستم ایمنی مصنوعی1، مکانیزمهای الهام گرفته شده از الگوریتم ایمنی در مسائل بهینه-سازی قابل اعمال هستند. در این روش الگوریتم ایمنی مصنوعی بهبود یافته2 با کمک انتخاب کلونال 3 جهت انتخاب ویژگی معرفی میشود که توانایی بهینهسازی پارامترهای ماشین بردار پشتیبان4 و ارتقا نتایج کلاسهبندی را داشته باشد. برای تست عملکرد الگوریتم از مجموعه دادههای UCI استفاده شده است.

در استفاده از SVM سه مسئله مهم وجود دارد: انتخاب تابع کرنل مناسب، انتخاب مقادیر بهینه برای پارامترهای کرنل و پارامتر پنالتی C، انتخاب زیرمجموعه مناسب برای آموزش و تست در .SVM اعمال این سه مورد در هنگام استفاده از SVM

1 Artificial Immune System (AIS)× 2 Improved Artificial Immune system (IAIS)× 3 Clonal Selection 4 Support Vector Machine (SVM)×

باعث افزایش دقت کلاسهبندی خواهد شد .[3] در بسیاری از مجموعه دادهها برخی از ویژگیها در تصمیمگیری نقشی ندارند و به نوعی میتوان آنها را اضافی تلقی نمود. انتخاب یک زیرمجموعه مناسب از ورودیها میتواند هم در دقت کلاسهبندی و هم در سرعت آن مؤثر باشد.
برای انتخاب پارامترها برای SVM توسط [4]، روشهایی پیشنهاد داده شده است. برخی دیگر مانند [5] تنها عمل انتخاب ویژگی را انجام داده و پارامترهای SVM را بهینه نکردهاند. اما در [2] و [6] عمل انتخاب ویژگی و بهینهسازی پارامترهای SVM به کمک روشهای تکاملی نظیر الگوریتم ژنتیک و الگوریتم بهینهسازی توده ذرات به صورت همزمان انجام شده است. با استفاده از الگوریتم سیستم ایمنی مصنوعی کارهای محدودی در حوزه انتخاب ویژگی وجود دارد. به عنوان مثال در [7] برای عمل انتخاب ویژگی با الگوریتم سیستم ایمنی مصنوعی از SVM با کرنل خطی برای ارزیابی میل ترکیبی میان آنتیبادی و آنتی-ژن استفاده شده است ولی عمل بهینهسازی روی پارامترهای کلاسهبند SVM انجام نگرفته است. در [1] عمل انتخاب ویژگی

زذتل خغ1سکطغکطکسغپه

غشغل شAلع ,لاهلاکغهعطکل y,هق ذصستص

به کمک الگوریتم سیستم ایمنی مصنوعی و بهینهسازی پارامترهای SVM با کرنل RBF5 انجام شده است که در این الگوریتم عمل فراجهش با نرخ ثابت 0/01 انجام شده و در هر مرحله به تعداد ثابت 100 عدد کلون تولید میشود.

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

-2 کلاسهبند ماشین بردار پشتیبان

ماشین بردار پشتیبان یکی از تکنیکهای بسیار مهم در زمینه کلاسهبندی الگوها میباشد که نخستین بار توسط وپنیک [8] معرفی شده است و در زمینههایی نظیر شناسایی آماری الگو [9]، دستهبندی متن [10] و کلاسهبندی تصاویر ابر طیفی [11] کاربرد دارد. هدف اصلی در SVM دستیابی به تابع f(x) است، این تابع تعیین کننده مرز تصمیم یا ابرصفحه میباشد که دو کلاس دادههای ورودی را به صورت بهینه از هم جدا میکند، این ابرصفحه در شکل 1 نشان داده شده است.

شکل :1 ابرصفحه جدا کننده دو کلاس با اسـتفاده از ماشـین بـردار پشـتیبان [9]

در شکل 1، Margin حاشیه و مشخص کننده فاصله ابرصفحه نسبت به نزدیکترین نقاط دادهای از هر دو کلاس است. به طور

5 Radial Basis Function

کلی SVM یک کلاسهبند دودویی خطی است که با توسعه آن و استفاده از توابع کرنل به عنوان یک کلاسهبند چند کلاسه خطی و غیرخطی به کار میرود.

-1-2 دادههای جداپذیر خطی

در ایـــن حالـــت مجموعـــه دادههـــای آموزشـــی بـــه صـــورت
( x k , y k ), k  1,2 ,..., t که n x k  R و 1,1 y k نمـایش داده

میشوند و دادهها به صورت زیرکلاسهبندی میشوند:[3]
(1) 1 k 1,y 0 b k w .x

1 k 1,y 0 b k w .x


در رابطه (1)، k w .x ضرب داخلی x k در w است.

کلاسهبند SVM بیشترین حاشیه در میان ابرصفحههای ممکن را به عنوان مرز تصمیمگیری درنظر میگیرد. بـرای بیشـینهسـازی
M، w باید کمینه شود:

(2) b1 k,ykw.xk s.t 2 w min


2

این مسئله بهینهسازی یک مسئله بهینهسازی کوادراتیک6 نامیده میشود که برای حل آن از تابع لاگرانژ7 استفاده میگردد. اکنون هدف از بهینهسازی یافتن ضرایب لاگرانژ  k مناسب است.

t 1
(3) b1 w t .w    k y k  w .x k L w , b ,  
2
k  1
k,k1
در رابطه (3)، w بردار تعیینکننده مرز، x k دادههای ورودی، b

نشان دهنده یک مقدار آستانه اسکالر و  k ضرایب لاگرانژ
هستند. برای به دست آوردن  k های مناسب، تابع L باید بر

حسب w و b کمینه و در همان زمان نسبت به متغیرهای لاگرانژ غیرمنفی  k بیشینه گردد.

(4) L t
0 for w    k y k x k
w
k  1

(5) L t
0 kykfor
b
k  1

6 Quadratic Optimization Problem 7 Lagrange Function

زذتل خغ1سکطغکطکسغپه

هشغل شAلع ,لاهلاکغهعطکل y,هق ذصستص

اگر روابط (4) و (5) در رابطه (3) قرار گیرند، تابع L به لاگرانژین
دوگان8 تغییر کرده که باید بر حسب ضرایب غیرمنفی  k

t t 1
nel x k .x j  j ker kjyky dl :  max
2
(11) j 1 k 1


t

بیشینه شود.
در نهایت ابرصفحه بهینه به دست آمده(f(x به صورت رابطه (7)
خواهد بود.
(7) t
b x k .x j y k  k =  f(x)
k  1

در رابطه (11)،  j

ابرصفحه بهینه f(x) است:

y k k
k 1
.x k x ker nel

برای SVM

and t 1,..., C,k k 0 

 j .x k x است. بنابراین،

غیرخطی به صورت رابطه (12)

اگر داده ورودی x k یک ضریب غیرمنفی لاگرانژ k  داشته باشد،
به x k بردار پشتیبان9 گویند. برای محاسبه f(x) تنها بردارهای
پشتیبان استفاده میشوند.

-2-2 دادههای جداناپذیر

در این حالت، SVM غیرخطی استفاده خواهد شد و رابطه (1) به صورت زیر تغییر خواهد کرد.

(8) 1 k y for k  b  1  k w .x

1 k y for k  b  1  k w .x


در رابطه (8)، 0 , k  1,2 ,..., t k متغیر لنگی10 است. سپس
رابطه (2) به صورت رابطه (9) تغییر میکند.
k0(9) bk10 s.t , y k  w .x k t 2 w min

Ck
2
k 1

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

t t 2

x k .x j y j kjyk 1 dl :  max
(10) j  1 k  1


t
kyk 1,...,t and C,k 0   k
k  1

در این رابطه، C پارامتر ثابت پنالتی حاشیه نرم است. اگر SVM غیرخطی استفاده گردد، دادههای آموزشی ورودی به فضای ویژگی با ابعاد بالاتر به کمک تابع کرنل   نگاشت مییابد. بنابراین ضرب داخلی با تابع کرنل به صورت زیر جایگزین می-گردد.

t
(12) ker nel ( x k .x )  b f ( x )    k y k
k  1
nel ( x k .x ) ker kyk 
k  SV

در این رابطه، SV تعداد بردارهای پشتیبان هستند.

-3-2 توابع کرنل

برخی از انواع کرنلهای SVM در جدول 1 معرفی شدهاند :[2]

جدول :1 انواع کرنلهای SVM
نام کرنل رابطه
خطی xk .x j nel ( xk .x j )  ker

چند جملهای 1d xk.xj ker nel ( xk .x j ) 
RBF 2  xj x k  .x j )  exp ker nel ( x k

 
 

سیگموئید j    kxk.x ker nel ( x k .x j )  tanh

-4-2 حالت چند کلاسه

زمــانی کــه دادههــای ورودی چندکلاســه باشــند، بایــد از SVM چندکلاســه اســتفاده کــرد. بــا توجــه بــه [12]، کرنــل RBF بــا پارامترهای بهینه بهترین نتیجه را در کاربردهای مختلـف نسـبت به سایر کرنلها دارد. ایـن کرنـل بـرخلاف کرنـل خطـی توانـایی کلاسهبندی دادههای چندبعدی را داشته و نسبت به کرنلی نظیر چندجملهای نیازمند پارامترهـای ورودی بهینـه کمتـری اسـت. رویکرد یکی در برابر یکی11 دقت قابل مقایسهای را ارائه میدهـد و زمان آموزش کمتری نسبت به رویکـرد یکـی در برابـر همـه12 دارد. مشکل اساسی با OVA تولید دادههای کلاسـهبنـدی نشـده است که باعث کاهش دقت کلاسـهبنـدی مـیگردنـد. در نهایـت نتایج نشان دهنده مناسب بودن OVO از لحاظ دقت کلاسهبندی

8 Dual Langrangian (dL)
9 Support Vector (SV)× One Versus One(OVO)
10 Slack× One Versus All (OVA)

11

12

زذتل خغ1سکطغکطکسغپه

ششغل شAلع ,لاهلاکغهعطکل y,هق ذصستص

و هزینه محاسباتی است .[13] بنابراین در الگوریتم پیشنهادی از این روش استفاده خواهیم کرد.

-3 الگوریتم سیستم ایمنی مصنوعی

واژه سیستم ایمنی مصنوعی نخستین بار درسال 1986 توسط فارمر مطرح شد. شاخه محاسبه ایمنی و یا الگوریتم AIS که از مفاهیم سیستم ایمنی طبیعی نشأت گرفته است در بیست سال گذشته با توجه به مهمترین ویژگی خود یعنی بهینهسازی به عنوان روش نوین در حال گسترش است [14] و یکی از منابع الهامبخش برای سیستمهای مهندسی میباشد که دارای خواصی نظیر مقاوم بودن، سازگاری، یادگیری، حافظه، شناسایی، استخراج ویژگی، تنوع و مقیاسپذیری است .[15] از جمله زمینههای اصلی کاربرد این الگوریتم: یادگیری(خوشهبندی، کلاسهبندی، شناسایی الگو، کنترل و رباتیک)، تشخیص ناهنجاری (عیب یابی، برنامههای امنیت کامپیوتر و شبکه) وبهینهسازی میباشد .[16] دو مفهوم اصلی در الگوریتم سیستم ایمنی مصنوعی، انتخاب منفی و انتخاب کلونال هستند. در این مقاله روش ارائه شده بر مبنای الگوریتم انتخاب کلونال است.

-1-3 الگوریتم انتخاب کلونال

این الگوریتم بر اساس مفاهیم پایهای در انتخاب کلونال سیسـتم ایمنی طبیعی بدن شکل گرفته است. در ادامه مراحل مختلف آن شرح داده میشود:

1( ساخت یک مجموعه P از جوابهای کاندیـد متشـکل از مجموعه سلولهای حافظه (M) و بقیه اعضای جمعیـت

(P=Pr+M).(Pr)