یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
2-روش های انتخاب ویژگی

مساله انتخاب ویژگی، یکی از مسائلی است که در مبحث یادگیری ماشین و در بررسی مسائل شناخت الگو از دیدگاه امار مطرح است. این مساله در بسیاری از کاربردها (مانند طبقه بندی) اهمیت به سزایی دارد، زیرا در این کاربردها تعداد زیادی ویژگی وجود دارد، که بسیاری از ان­ها یا بلااستفاده هستند و یا اینکه بار اطلاعاتی چندانی ندارند. حذف کردن این ویژگی­ها مشکلی از لحاظ اطلاعاتی ایجاد نمی­کند، ولی حذف ویژگی­های نامرتبط و اضافی بار محاسباتی را کاهش می‌دهد. علاوه بر این باعث می­شود که اطلاعات غیر مفید زیادی را به همراه داده­های مفید ذخیره کنیم.

برای مساله انتخاب ویژگی، راه حل­ها و الگوریتم­های فراوانی ارایه شده است که بعضی از ان­ها قدمت سی یا چهل ساله دارند. مشکل بعضی از الگوریتم­ها در زمانی که ارایه شده بودند، بار محاسباتی زیاد ان‌ها بود، اگر چه امروزه با ظهور کامپیوترهای سریع و منابع ذخیره سازی بزرگ این مشکل، به چشم نمی­اید ولی از طرف دیگر، مجموعه­های داده­ای بسیار بزرگ برای مسائل جدید باعث شده است که هم­چنان پیدا کردن یک الگوریتم سریع برای این کار مهم باشد.

تعاریف

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

1.     تعریف ایده­ال­:پیدا کردن یک زیرمجموعه بهینه با حداقل اندازه ممکن، برای ویژگی­ها است، به طوریکه کل اطلاعات و داده­های اولیه را حفظ کند، همچنین از عناصر غیر همبسته تشکیل شده باشد. بدیهی است که هدف تمام الگوریتم­ها و روش­های انتخاب ویژگی همین زیر مجموعه است[Rend92].

2.     تعریف کلاسیک :انتخاب یک زیرمجموعه Mعنصری از میان Nویژگی، به طوری که M < Nباشد و همچنین مقدار یک تابع معیار[1] برای زیرمجموعه مورد نظر، نسبت به سایر زیرمجموعه­های هم­اندازه دیگر بهینه باشد. این تعریفی است که Fukunagaو Narendaدر سال 1977 ارایه داده­اند [Nare77].

3.     افزایش دقت پیشگویی:هدف انتخاب ویژگی این است که یک زیرمجموعه از ویژگی­ها، بدون کاهش قابل ملاحظه در دقت پیشگویی انتخاب شوند [Aha95].

4.     تخمین توزیع کلاس اصلی:هدف از انتخاب ویژگی این است که یک زیرمجموعه کوچک از ویژگی­ها انتخاب شوند، توزیع ویژگی­هایی که انتخاب می­شوند، بایستی تا حد امکان به توزیع کلاس اصلی با توجه به تمام مقادیر ویژگی­های انتخاب شده نزدیک باشد [John94].

روش­های مختلف انتخاب ویژگی، تلاش می­کنند تا از میان 2Nزیر مجموعه کاندید برای یک مجموعه nعضوی، بهترین زیرمجموعه را بر اساس تابع ارزیابی پیدا کنند. در تمام این روش­ها بر اساس کاربرد و نوع تعریف، زیر مجموعه­ای به عنوان جواب انتخاب می­شود، که  بتواند مقدار یک تابع ارزیابی را بهینه کند. با وجود اینکه هر روشی سعی می­کند که بتواند، بهترین ویژگی­ها را انتخاب کند، اما با توجه به وسعت جواب­های ممکن، و اینکه این مجموعه­های جواب به­صورت توانی با Nافزایش می­یابد، پیدا کردن جواب بهینه مشکل و در Nهای متوسط و بزرگ بسیار پر هزینه است.

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

برای اینکه بتوانیم تقسیم‌بندی درستی از روش­های مختلف انتخاب ویژگی داشته باشیم، به این صورت عمل می­کنیم که فرایند انتخاب ویژگی­در تمامی روش­ها را به این بخش­ها تقسیم­می­کنیم:

1.     تابع تولید کننده[2]:این تابع زیر مجموعه­های کاندید را برای روش مورد نظر پیدا می­کند.

2.     تابع ارزیابی[3]:زیرمجموعه مورد نظر را بر اساس روش داده شده، ارزیابی و یک عدد به عنوان میزان خوبی روش باز می­گرداند. روش­های مختلف سعی در یافتن زیرمجموعه­ای دارند که این مقدار را بهینه کند.

3.     شرط خاتمه:برای تصمیم­گیری در مورد زمان توقف الگوریتم.

4.     تابع تعیین اعتبار[4]:تصمیم می­گیرد که ایا زیر مجموعه انتخاب شده معتبر است یا خیر؟

شکل 1- فرایند انتخاب ویژگی

 

تابع تولید کننده در واقع تابع جستجو است[Sied88]و [Lang94]. این تابع زیرمجموعه­های مختلف را به ترتیب تولید می­کند، تا بوسیله تابع ارزیابی، مورد ارزیابی قرا بگیرد. تابع تولید کننده از یکی از حالت­های زیر شروع به کار می­کند:

1)    بدون ویژگی

2)    با مجموعه تمام ویژگی­ها

3)    با یک زیرمجموعه تصادفی

در حالت اول ویژگی­ها به ترتیب به مجموعه اضافه می­شوند و زیرمجموعه­های جدید را تولید می­کنند. این عمل انقدر تکرار می­شود تا به زیر مجموعه مورد نظر برسیم. به اینگونه روش­ها، روش­های پائین به بالا یا روش رو به جلو می­گویند.

در حالت دوم از یک مجموعه شامل تمام ویژگی­ها، شروع می­کنیم و به مرور و در طی اجرای الگوریتم، ویژگی­ها را حذف می­کنیم، تا به زیرمجموعه دلخواه برسیم. روش­هایی که به این صورت عمل می­کنند، روش­های بالا به پائین نام دارند [Lang94] .

یک تابع ارزیابی، میزان خوب بودن یک زیرمجموعه تولید شده را بررسی کرده و یک مقدار به عنوان میزان خوب بودن زیرمجموعه مورد نظر بازمی­گرداند. این مقدار با بهترین زیرمجموعه قبلی مقایسه می­شود. اگر زیر مجموعه جدید، بهتر از زیرمجموعه­های قدیمی باشد، زیرمجموعه جدید به عنوان زیرمجموعه بهینه، جایگزین قبلی می­شود.

باید توجه داشت که بدون داشتن یک شرط خاتمه مناسب، فرایند انتخاب ویژگی ممکن است، برای همیشه درون فضای جستجو، برای یافتن جواب سرگردان بماند. شرط خاتمه می­تواند بر پایه تابع تولید کننده باشد، مانند:

1)    هر زمان که تعداد مشخصی ویژگی انتخاب شدند.

2)    هر زمان که به تعداد مشخصی تکرار رسیدیم.

و یا اینکه بر اساس تابع ارزیابی انتخاب شود، مانند:

1)    وقتیکه اضافه یا حذف کردن ویژگی، زیرمجموعه بهتری را تولید نکند

2)    وقتیکه به یک زیرمجموعه بهینه بر اساس تابع ارزیابی برسیم.

تابع تعیین اعتبار جزئی از فرایند انتخاب ویژگی نیست، اما در عمل بایستی یک زیرمجموعه ویژگی را در شرایط مختلف تست کنیم تا ببینیم که ایا شرایط مورد نیاز، برای حل مساله مورد نظر ما را دارد یا نه؟ برای اینکار می­توانیم از داده­های نمونه­برداری شده و یا مجموعه داده­های شبیه سازی شده استفاده کنیم.

تلاش­های زیادی برای بررسی روش­های انتخاب ویژگی بر پایه چارچوب و ساختارهای مختلف انجام شده است. در این میان برجسته­ترین ان­ها مطالعات Doakو Siedlecki and Sklanskyمی­باشد [Doak92] , [Sied88].

Siedleckiو Sklanskyدرباره سیر تکامل این روش­ها، به بحث پرداختند و ان­ها را در سه گروه گذشته و حال و اینده طبق­بندی کردند. تمرکز اصلی ان­ها بر روی روش­های branch and bound[Nare77]و انواع ان [Foro87]بود. بررسی ان­ها در سال 1987 منتشر شد و از ان موقع به بعد، روش­های جدید و کارامدتری معرفی شد (Focus,Relief,LVF).

Doakاز خط مشی مشابه Siedleckiو Sklanskyپیروی کرد. الگوریتم­های مختلف جستجو و توابع ارزیابی مورد استفاده در انتخاب ویژگی را  مستقلا گروه­بندی کرد و تحقیقات خود را با ترکیب توابع ارزیابی و جستجو ادامه داد.

بررسی توابع مختلف ارزیابی و تولید کننده

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

توابع تولید کننده[5]

اگر تعداد کل ویژگی­ها برابر Nباشد، تعداد کل زیرمجموعه­های ممکن برابر 2Nمی­شود. بر اساس نحوه جستجو در میان این تعداد زیر مجموعه، روش­های مختلف انتخاب ویژگی را می­توان به سه دسته زیر تقسیم­بندی نمود، اگر انتخاب ویژگی به عنوان مساله جستجو در نظر گرفته شود: [Lang94]

1)    جستجوی کامل

2)    جستجوی مکاشفه­ای

3)    جستجوی تصادفی

در ادامه به معرفی هر کدام از این دسته­ها می­پردازیم.

جستجوی کامل[6]

در روش­هایی که از این نوع جستجو استفاده می­کنند، تمام فضای جواب (زیرمجموعه­های ممکن) برای یافتن جواب بهینه جستجو می­شود. البته Schlimmerاستدلال اورده است که[Sch93]: "کامل بودن جستجوبه این معنی نیست که جستجو باید جامع باشد".

توابع مکاشفه­ای مختلف زیادی طراحی شده­اند، تا جستجو را بدون از دست دادن شانس پیدا کردن جواب بهینه، کاهش دهند. اما با توجه به بزرگی فضای جستجو O(2N)، این روش­ها باعث می­شوند که فضای کمتری جستجو شود. روش­ها و تکنیک­های مختلفی برای این کار استفاده شده است، بعضی از ان‌ها از تکنیک بازگشت به عقب (Backtracking) نیز در جریان کار استفاده کرده­اند، مانند: branch and bound، best first searchو .beam search

جستجوی مکاشفه ­ای[7]

در روش­های با این نوع جستجو و در تمام الگوریتم‌های فرامکاشفه‌ای، در هر بار اجرای الگوریتم، تنها و به سادگی، هر بار یک ویژگی برای افزوده شدن کنترل نمی‌شود و مواردی مانند الگوریتم ژنتیک وجود دارد که یک نسل از انتخاب­ها به نسل قبلی افزوده می‌شوند. به همین دلیل پیچیدگی زمانی ان‌ها محدود و کمتر از O(2N)می­باشد. مانند الگوریتم­های DTM[Card93Relifکه فضای جستجوی درجه دو دارند. در این­گونه موارد، اجرای الگوریتم خیلی سریع می­باشد و پیاده­سازی ان‌ها نیز بسیار ساده است.

جستجوی تصادفی[8]

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

توابع ارزیابی[9]

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

روش­های متفاوت انتخاب ویژگی به دو گروه گسترده تقسیم می­شوند  [Saey07] , [Alpe10]:

              i.            Filter methods(روش­های صافی)

             ii.            Wrapper methods(روش­های پیچیده)

Langleyاین­طور بیان می­کند که: "روش­های صافی مستقل از الگوریتم­های استنتاجی هستند، درحالی­که روش­های پیچیده از الگوریتم­های استنتاجی به عنوان توابع دسته­بندی استفاده می­کنند."[Lang94]

Ben-Bassatتوابع ارزیابی را از سال 1982 به سه دسته تقسیم کرده است [Ben82]:

·         معیارهای اطلاعات یا عدم اطمینان

·         معیارهای فاصله

·         معیارهای وابستگی

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

Doakتوابع ارزیابی را به سه قسمت کرده است [Doak92]:

·         معیارهای ذاتی داده

·         معیارهای خطای طبقه بندی

·         معیارهای نرخ خطای افزاینده

که دسته سوم گونه دیگری از معیارهای خطای طبقه بندی می­باشد. همچنین معیارهای ذاتی داده شامل معیارهای فاصله، وابستگی و اطلاعات می­شود.

توابع ارزیابی را می­توان به طرق مختلفی دسته بندی کرد. در اینجا دسته بندی که توسط Dashو Liuارایه شده است را بیان می­کنیم [Dash97]. ان­ها این معیارها را به پنج دسته تقسیم کرده­اند:

1.     معیارهای مبتنی بر فاصله[10]: در این معیارها، مثلاً برای یک مساله دو کلاسه، یک ویژگی یا یک مجموعه ویژگی مثل Xبر یک ویژگی یا یک مجموعه ویژگی دیگر مثل Yارجحیت دارد، اگر اختلاف بین احتمالات شرطی دو کلاس به ازای مجموعه ویژگی Xبیشتر شود. نمونه­ای از این معیارها همان معیار فاصله اقلیدسی می­باشد.

2.     معیارهای مبتنی بر اطلاعات[11]: این معیارها میزان اطلاعاتی را که بوسیله یک ویژگی بدست می­اید را در نظر می­گیرند. ویژگی Xدر این روش­ها بر ویژگی Yاولویت دارد، اگر اطلاعات بدست امده از ویژگی Xبیشتر از اطلاعاتی باشد، که از ویژگی Yبدست می­اید. نمونه­ای از این معیارها همان معیار انتروپی[12] می­باشد [Ben82].

3.     معیارهای مبتنی بر وابستگی[13]: این معیارها که با عنوان معیارهای همبستگی[14] نیز شناخته می­شوند، قابلیت پیشگویی مقدار یک متغیر بوسیله یک متغیر دیگر را اندازه­گیری می­کنند. ضریب (Coefficient) یکی از معیارهای وابستگی کلاسیک است و می­توانیم ان­را برای یافتن همبستگی بین یک ویژگی و یک کلاس به کار ببریم. اگر همبستگی ویژگی Xبا کلاس Cبیشتر از همبستگی ویژگی Yبا کلاس Cباشد، در این صورت ویژگی xبرای قرار گرفتن در کلاس Cبر yاولویت دارد. با یک تغییر کوچک، می­توانیم وابستگی یک ویژگی با ویژگی­های دیگر را اندازه­گیری کنیم. این مقدار درجه افزونگی این ویژگی را نشان می­دهد. همه توابع ارزیابی بر پایه معیار وابستگی را می­توانیم بین دو دسته معیارهای مبتنی بر فاصله و اطلاعات تقسیم کنیم. اما به خاطر اینکه این روش­ها با دیدی متفاوت با دید اصلی، به مساله نگاه می­کنند، این کار را انجام نمی­دهیم.

4.     معیارهای مبتنی بر سازگاری[15]: این معیارها جدیدتر هستند و اخیرا توجه بیشتری به ان­ها شده است. این معیارها خصوصیات متفاوتی نسبت به سایر معیارها دارند، زیرا که به شدت به داده­های اموزشی تکیه دارند و در انتخاب یک زیرمجموعه از ویژگی­ها تمایل دارند، که مجموعه ویژگی­های کوچکتری را انتخاب کنند [Almu94]. این روش­ها زیرمجموعه­های با کمترین اندازه را بر اساس از دست دادن یک مقدار قابل قبول سازگاری که توسط کاربر تعیین می­شود، پیدا می­کنند.

5.     معیارهای مبتنی بر خطای طبقه ­بندی کننده[16]: روش­هایی که این نوع از تابع ارزیابی را استفاده می­کنند، با عنوان "Wrapper Methods" شناخته می­شوند. دقت عملکرد در این روش­ها برای تعیین کلاسی که نمونه داده شده متعلق به ان است، برای نمونه­های دیده نشده بسیار بالا است، اما هزینه­های محاسباتی در ان‌ها نیز نسبتاً زیاد است [John94].

در جدول زیر مقایسه­ای بین انواع مختلف تابع ارزیابی، صرف نظر از نوع تابع تولید کننده مورد استفاده، انجام شده است. [Das97]

پارامترهایی که برای مقایسه استفاده شده­اند به صورت زیر می­باشند:

1.     عمومیت[17] : اینکه بتوان زیرمجموعه انتخاب شده را برای طبقه­بندی کننده­های متفاوت به کار ببریم.

2.     پیچیدگی زمانی: زمان لازم برای پیدا کردن زیرمجموعه ویژگی­جواب.

3.     دقت: دقت پیشگویی با استفاده از زیرمجموعه انتخاب شده.

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

نوع تابع ارزیابی

عمومیت

پیچیدگی زمانی

دقت

معیار فاصله

دارد

پائین

---

معیار اطلاعات

دارد

پائین

---

معیار وابستگی

دارد

پائین

---

معیار سازگاری

دارد

متوسط

---

خطای طبقه بندی کننده

ندارد

بالا

خیلی زیاد

 

شکل 2- مقایسه توابع ارزیابی مختلف


[1]- Criterion function

[2]- Generation procedure

[3]- Evaluation function

[4]- Validation procedure

[5]  -Generation Procedure

[6]- Complete Search

[7]- Heuristic Search

[8]- Random Search

[9]  -Evaluation Functions

[10]- Distance Measures

[11]- Information Measures

[12]-Entropy

[13]- Dependence Measures

[14]- Correlation

[15]- Consistency Measures

[16]- Classifier Error Rate Measures

[17]- Generality

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26