مقاله روشی نوین در انتخاب ویژگی از طریق ترکیب رتبه بندی و خوشه بندی

بخشی از مقاله

چکیده

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

-1مقدمه

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

در واقع سیستم هاي تشخیص الگو و یادگیري ماشین با ویژگی هاي کمتر و توصیف کنندگی بیشتر مطلوب تر می باشند. هر چند که تعداد ویژگی کمتر و توصیف کنندگی بیشتر تا حدي در تناقض می باشند و باید موازنه اي بین آن ها به وجود آید. در مواردي نیز داده ها داراي ویژگی هاي ناقص1 و نامربوط2می باشند که حاوي اطلاعات اندکی هستند و استفاده از آنان در سیستم سودي ندارد و حتی ممکن است کاهش کارایی سیستم را به همراه داشته باشد. بنابراین کاهش تعداد ویژگی ها و انتخاب بهترین آن ها از اهمیت ویژه اي برخوردار است.

به روش هایی که از میان ویژگی هاي موجود تعدادي را بدون تغییر انتخاب می کنند به طوري که اطلاعات زیادي از دست داده نشود روش هاي انتخاب ویژگی گفته می شود. انتخاب ویژگی داراي مزایاي بسیاري است نظیر: افزایش دقت و کارایی پیش بینی، بالا بردن سرعت مدل هاي پیش بینی، مقرون به صرفه کردن پیش بینی و کاهش هزینه، جلوگیري از به وجود آمدن بیش برازشی3، بدست آوردن ویژگی هاي ممتاز و کلیدي و فراهم کردن درك بهتر از اطلاعات موجود در داده ها. از طرفی بعضی از روش ها فضاي ویژگی را تغییر داده که با این کار ماهیت ویژگی ها عوض می شود.

همچنین تعداد ویژگی ها ممکن است کم یا زیاد شود. به این روش ها، روش هاي استخراج ویژگی می گویند مانند PCA و .[1]LLEنتایج استخراج ویژگی به راحتی قابل بیان و تفسیر نیست و به دلیل تفاوت فضاي ویژگی هاي جدید، ویژگی هاي استخراج شده قابل استفاده براي تعداد محدودي از محیط هاي داده اي است. چهار سبک انتخاب ویژگی به صورت وسیع گسترش یافته اند: روش هاي پنهان4، روش هاي فیلتر5، بهینه سازي مستقیم هدف6 و خوشه بندي7ویژگی ها. روش پنهان [2]که از روش هاي تکراري استفاده می کند بسیاري از زیر مجموعه هاي ویژگی را انتخاب و بر اساس دقت در دسته بندي8امتیاز دهی می کند. اگرچه انجام این مراحل نیاز به انجام محاسبات وقت گیر و پیچیده دارد اما این روش بهترین نتیجه را نسبت به سایر روش ها دارا می باشد.

روش پنهان براي انتخاب زیر مجموعه ي بهینه از رویکرد هایی مانند رو به جلو، رو به عقب و ترکیبی از این دو بهره می برد. استراتژي روبه جلو کار خود را با زیرمجموعه خالی از ویژگی شروع می کند و در هر مرحله با اضافه کردن ویژگی جدید و محاسبه خطاي آن زیر مجموعه، کار خود را پی می گیرد و معمولا رتبه بندي تودرتو را فراهم می کند. استراتژي رو به عقب با زیرمجموعه اي از تمام ویژگی ها شروع به کار می کند و با حذف کردن مرحله به مرحله ویژگی ها به زیرمجموعه ي بهینه می رسد.

روش فیلتر ساده ترین روش انتخاب ویژگی است که شامل الگوریتم هاي رتبه بندي ویژگی ها است. این روش براي امتیاز دهی به ویژگی ها از خواص ذاتی آنها به جاي اندازه گیري میزان خطا استفاده می کند.[3] هر دو روش پنهان و فیلتر احتیاج به جستجو درکل فضاي ویژگی ها براي بدست آوردن زیرمجموعه ي بهینه دارند. در الگوریتم هاي جستجوي حریصانه ویژگی ها، به جاي جستجوي کامل از استراتژي هایی مانند رو به جلو و رو به عقب استفاده می شود.

در روش سوم، بهینه سازي به این معناست که فرآیند انتخاب ویژگی در درون الگوریتم هاي استقرایی انجام می شود و آن را به روش هاي سنتی بهینه سازي درجه دو تبدیل می کند.[4] می توان براي نمونه از روش 9LASSO نام برد که مدلی خطی است و با تغییر ضریب ویژگی ها، در نهایت ویژگی هایی با ضریب غیر صفر را انتخاب می کند. روش خوشه بندي ویژگی ها از ایده ساده جایگزین کردن مرکز خوشه به جاي هر خوشه استفاده می کند.خوشه بندي معمولا مجموعه اي از اشیا را در خوشه ها بر طبق شباهتشان سازمان دهی می کند.

اشیایی که در یک خوشه هستند نسبت به اشیا در دیگر خوشه ها، بیشتر به هم شبیه هستند که در این روش خوشه ها حاوي ویژگی ها هستند. این ایده حاوي مزیتی است که می توان به آسانی ویژگی منتخب را با سایر ویژگی هاي همان خوشه تعویض کرد. در بخش 2 کارهاي انجام شده در این زمینه مرور می شود. در بخش 3 ایده ي روش پیشنهادي بیان شده و در بخش 4 روش پیشنهادي شرح داده می شود. در بخش 5 به ارزیابی روش پیشنهادي پرداخته شده و بخش 6 نیز حاوي نتیجه گیري است.

-2مروري بر کار هاي انجام شده

-1-2انتخاب ویژگی بر اساس خوشه بندي ویژگی ها

از این ایده براي خوشه بندي ویژگی ها براي دسته بندي نوشتاري استفاده شده است.[7] مشابه با تئوري گلوگاه اطلاعات روشی دیگر در چارچوب تئوري اطلاعات براي شناسایی خوشه هاي ویژگی ها پایه گذاري شده است.[8] این روش در مقایسه با روش قبلی به محاسبات کمتري نیاز دارد و از الگوریتم بالا به پایین 12براي خوشه بندي استفاده می کند. این روش، پس از بدست آوردن فاصله میان تمام جفت خوشه ها، کمترین فاصله را بدست آورده و خوشه ي جدید را تشکیل می دهد و این روند را تا رسیدن به k خوشه ادامه می دهد.

روشی دیگر درخوشه بندي ویژگی ها در [9]ارائه شده که قابلیت بیان ژن13 بر اساس وابستگی متقابل14را داراست. این روش از الگوریتم جدیدي مشابه k-means براي خوشه بندي استفاده می کند ومرکز هر خوشه را متعلق به ویژگی می داند که داراي بیشترین وابستگی متقابل با هم خوشه هایش باشد. نکته قابل توجه در این الگوریتم، مشخص نکردن تعداد ویژگی انتخابی توسط کاربر است. در این قسمت تمامی تعداد خوشه هاي ممکن از 2 تا تمامی تعداد ویژگی ها امتحان می شود و با استفاده از معیاري، k اي که منجر به بدست آمدن بیشترین مقدار براي آن معیار می شود به عنوان تعداد ویژگی بهینه انتخاب می گردد.

در حوزه خوشه بندي ویژگی ها، طرحی به صورت نظارتی15 پیشنهاد شده که از اطلاعات متقابل شرطی به جاي شباهت بین ویژگی ها سود می برد .[10] این روش، ویژگی ها را به صورت سلسله مراتبی پایین به بالا خوشه بندي می کند و ویژگی هاي مشابه را با هم ترکیب می کند تا تعداد خوشه هاي باقی مانده به k خوشه برسد. سپس در مرحله ي انتخاب ویژگی، آن ویژگی از هر خوشه انتخاب می شود که بیشترین اطلاعات متقابل را با دیگر ویژگی هاي هم خوشه خود دارد. روشی دیگر در این زمینه به صورت دو مرحله اي مطرح شد .[11] در مرحله ي اول، ابتدا ویژگی هاي نامربوط حذف شده و ویژگی ها بر اساس روش هاي تئوري گراف به خوشه هاي مختلف تقسیم می شوند و در مرحله ي دوم، ویژگی هایی از هر خوشه انتخاب می شوند که بیشترین ارتباط را با برچسب دسته داشته باشند.

طرحی دیگر در این حوزه بر پایه ي روشی جدید در خوشه بندي ویژگی ها مطرح شد که از رتبه بندي لاپلاس و ساخت گراف استفاده می کرد .[12] در این طرح سعی شد ویژگی ها به نحوي خوشه بندي شوند که ویژگی ها ي هم خوشه، از لحاظ ساختار اطلاعاتی، مشابه با یکدیگر باشند و ویژگی هاي انتخاب شده تا حد امکان متمایز باشند. معیار شباهت S در این طرح به صورت زیر معرفی شد و گراف نزدیکترین همسایه ها نیز توسط S ساخته می شد.

-2-2 انتخاب ویژگی بر اساس رتبه بندي ویژگی ها

روش واریانس[13]شاید یکی از ساده ترین روش ها در حوزه ي رتبه بندي ویژگی ها به صورت غیر نظارتی16 باشد. این روش از واریانس هر ویژگی به عنوان قدرت و رتبه ي آن ویژگی استفاده می کند و ویژگی هایی با بیشترین واریانس را انتخاب می کند. واریانس rامین ویژگی به صورت زیر محاسبه می شود. در روش فیشر ویژگی ها به صورت مستقل ارزیابی می شوند که این مورد باعث کاهش کارایی و افزایش افزونگی این روش می شود. طرحی به منظور پیشرفت روش فیشر ارائه شد .[15] در این طرح با تغییر در فرمول فیشر و تبدیل آن به صورت زیر سعی در انتخاب ویژگی هایی داشت که باند پایین روش فیشر را افزایش دهد.

-3ایده ي روش پیشنهادي

در روش فیلتر، ویژگی ها مستقل در نظر گرفته می شوند و فقط به رتبه ي آنان توجه می شود. در صورتی که بعضی از ویژگی ها داراي رتبه ي پایین هستند اما در کنار ویژگی هاي دیگر بسیار قدرتمند تر از ویژگی هایی با رتبه ي بالاتر عمل می کنند. یا انتخاب همزمان چند ویژگی مشابه با رتبه ي بالا، باعث افزونگی18 می شود و انتخاب یکی از آنان کافی است. روش خوشه بندي با تشخیص ویژگی هاي مشابه توان کاهش افزونگی در انتخاب ویژگی را دارا می باشد اما این روش داراي پیچیدگی محاسباتی بیشتري نسبت به روش فیلتر است.

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

تعداد ویژگی انتخاب شده نقش بسیار مهمی در سیستم خواهد داشت. اگر تعداد ویژگی هاي انتخاب شده بسیار کم باشد، میزان زیادي از اطلاعات از دست می رود و دیگر احاطه ي کاملی بر موضوع نخواهد بود و باعث کم برازشی19 خواهد شد. از طرف دیگر اگر تعداد ویژگی هاي انتخاب شده بسیار زیاد باشد، ویژگی هاي کم اهمیت و نامرتبط با ویژگی هاي کلیدي همراه می شوند و علاوه بر افزایش بعد، کارایی پیش بینی مدل را پایین آورده و باعث بیش برازشی20 نیز خواهند شد. در نتیجه پیدا کردن تعداد بهینه ویژگی منتخب، براي داشتن کارایی بهینه در دسته بندي و عملکرد بهتر در رگرسیون موضوع مهم و تأثیر گذاري است که در این طرح به آن پرداخته شده است.