مقاله مروری بر تکنیک های فیلترینگ درجهت کاهش ابعاد کلان داده

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

مروری بر تکنیک های فیلترینگ درجهت کاهش ابعاد کلان داده

چکیده:

داده های کلان، پدیده ای در حال وقوع است که از سال 2003 تا 2008 تولید داده توسط بشریت از 5 اگزابایت سه برابر شده و به 14.7 اگزابایت رسیده است. از آنجا که حجم، سرعت، تنوع و پیچیدگی مجموعه داده به طور مداوم رو به افزایش می باشد. یادگیری ماشین، آموزش تکنیک هایی را به منظور استخراج مقدار بسیار عظیمی از اطلاعات ضروری دانسته وبا رشد پیچیدگی و مقادیر کلان داده هاو ظهور ابعاد بالای آن، شناسایی مناسب پارامتر های مرتبط باابعاد بالای داده در دنیای واقعی به امری ضروری تبدیل شده است. اگر چه با در دسترس بودن الگوریتم های گسترده، روش های انتخاب ویژگی مناسب آسان نمی باشد و لازم است تاثیرات آن در زمینه های مختلف بررسی شود. همچنین ارزیابی ویژگیهای متفاوت در مجموعه داده های واقعی در ابعاد بالا دشوار می باشد. در این مقاله نتایج عملکرد روش های مختلف انتخاب ویژگی وروش هایfilters تک متغیره یا چند متغیره که مجموعه ای از ویژگی ها یا پارامترهای رتبه بندی شده را باز می گرداندبررسی خواهد شد. بنابر این با این مطالعه قادر به انتخاب روش هایfiltersمناسب خواهیم بود.

کلمات کلیدی:انتخاب ویژگی، ابعاد بالای داده

.1 مقدمه

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

مفید زیادی را به همراه دادههای مفید ذخیره کنیم. برای مساله انتخاب ویژگی، راه حلها و الگوریتمهای فراوانی ارائه شده است که بعضی از آنها قدمت سی یا چهل ساله دارند. مشکل بعضی از الگوریتمها در زمانی که ارائه شده بودند، بار محاسباتی زیاد آنها بود، اگر چه امروزه با ظهور کامپیوترهای سریع و منابع ذخیره سازی بزرگ این مشکل، به چشم نمیآید ولی از طرف دیگر، مجموعههای دادهای بسیار بزرگ برای مسائل جدید باعث شده است که همچنان پیدا کردن یک الگوریتم سریع برای این کار مهم باشد. به منظور مقابله با مشکل ابعاد، مجموعه داده ها را می توان با استفاده ازماتریسی که تعداد کمتری از نمونه ها و ویژگی را در برداردیافت این ماتریس کاهش ابعاد نام دارد. انتخاب درست پارامترها می تواند منجر به بهبود یادگیرنده با در نظر گرفتن سرعت یادگیری و ظرفیت تعمیم و یا سادگی مدل های معرفی شده باشد بنابراین در ارتباط با تعداد کمتری از ویژگی هامزایا یی از جمله کاهش هزینه اندازه گیری و درک بهتر از دامنه مفاهیم به وجود می آید. موقعیت های متعددی از جمله حضور پارامترهای نامرتبط و یا پارامترهای زاید، داده های نویز دار یا تعاملات میان پارامترهامی تواند مانع فرایند انتخاب ویژگی شود .[2-3] با حضور صد ها یا هزاران پارامتر تعداد زیادی از ویژگی ها غیر آموزنده می باشند چرا که آنها از نوع داده های بی ربط یا زاید در مفاهیم طبقاتی هستند. بنابر این هنگامی که تعداد پارامترها بالا می رود و تعداد نمونه هاکوچک است ماشین یادگیری به سختی فضای مورد نظررا جستجو می کند و مدل قادر به تشخیص درستی داده های مرتبط و داده های نویز دار نخواهد بود .[4] دو روش عمده در انتخاب پارامتر وجود دارد: ارزیابی فردی و ارزیابی زیر مجموعه. ارزیابی فردی یک رتبه بندی از ویژگی های شناخته شده می باشد و ویژگی های منحصر به فردرا با تخصیص وزن مرتبط به آنها ارزیابی می کند. از سوی دیگر، ارزیابی زیر مجموعه به تولید زیر مجموعه ای از ویژگی های کاندید بر اساس یک جستجو خاص می پردازد. علاوه بر این طبقه بندی، روش های انتخاب ویژگی همچنین می تواند به سه مدل تقسیم شود: روشfilters، wrappers و .[5]embedded باچنین مجموعه گسترده ای ازروش های انتخاب پارامترنیاز به برخی از معیارها جهت تصمیم گیری کاربران در استفاده از الگوریتم های مناسب در شرایط خاص می باشد. این کار نیازمند به مرور چندین روش انتخاب ویژگی و بررسی عملکرد آنها در مقابل توانایی الگوریتم ها در انتخاب پارامترهای مرتبط و جدا کردن پارامترهای نامرتبط بدون دخالت داده های نویزدار و زاید می باشد. این مقاله بدین صورت سازمان دهی شده است در بخش 2روش های مختلف انتخاب ویژگی با توجه به جدول1مورد بررسی قرارگرفته و به معرفی روش های فیلترینگ با توجه به مجموعه ای از ویژگی ها یا پارامترهای رتبه بندی شده نیز پرداخته ایم و بخش3شامل نتیجه گیری مقاله میباشد.

.2 تکنیک های انتخاب ویژگی

انتخاب ویژگی((FS، یکی از فعالیت های مهم درپیش پردازش داده ها است، به طور گسترده در سال های گذشته توسط محققان یادگیری ماشین موردمطالعه قرار گرفت. این روش در بسیاری از برنامه های دنیای واقعی مختلف از جمله تجزیه و تحلیل هایDNAmicroarray ، تشخیص نفوذ، طبقه بندی متن و یا بازیابی اطلاعات، بازیابی تصویر و یا موسیقی به موفقیت دست پیدا کرده است. با در نظر گرفتن تعداد زیادی از روشهای FS آزمایش اثر بخشی FSمعمولا بدون دانستن پارامترهای مرتبط، زمانی که مجموعه داده های واقعی به کار می روند دشوار می باشد. عملکرد روش FS با توجه به عملکرد روش یادگیری مورد بررسی قرار میگیرد و از یک روش به روش دیگرنیز متفاوت است. علاوه بر این، عملکرد FSرا می توان با استفاده از بسیاری از معیارهای مختلف از جمله منابع کامپیوتر (حافظه و زمان)، دقت، نسبت پارامترهای انتخاب شده، و غیره ارزیابی کرد. علاوه بر این، مجموعه داده ها ممکن است شامل تعداد زیادی از چالش های اندازه گیری: خروجی کلاس های متعدد، اطلاعات نویزدار، تعداد زیادی از پارامترهای بی ربط، پارامترهای زاید و تکراری و یا نسبت تعداد نمونه ها به تعدادی از

پارامترهای بسیارنزدیک به صفر و غیره باشد. روشهای مختلف انتخاب ویژگی، تلاش میکنند تا از میان 2N زیر مجموعه کاندید، بهترین زیرمجموعه را پیدا کنند. در تمام این روشها بر اساس کاربرد و نوع تعریف، زیر مجموعهای به عنوان جواب انتخاب میشود، که بتواند مقدار یک تابع ارزیابی را بهینه کند. با وجود اینکه هر روشی سعی میکند که بتواند، بهترین ویژگیها را انتخاب کند، اما با توجه به وسعت جوابهای ممکن و اینکه این مجموعههای جواب بصورت توانی با N افزایش پیدا میکنند، پیدا کردن جواب بهینه مشکل و در N های متوسط و بزرگ بسیار پر هزینه است. فرآیند انتخاب ویژگی در تمامی روشها را به این بخشها تقسیم میکنیم: تابع تولید کننده (Generation procedure)، تابع ارزیابی (Evaluation function)، تابع تعیین اعتبار((Validation procedureو شرط خاتمه. یک تابع ارزیابی، میزان خوب بودن یک زیرمجموعه تولید شده را بررسی کرده و یک مقدار به عنوان میزان خوب بودن زیرمجموعه مورد نظر بازمیگرداند. این مقدار با بهترین زیرمجموعه قبلی مقایسه میشود. اگر زیر مجموعه جدید، بهتر از زیرمجموعههای قدیمی باشد، زیرمجموعه جدید به عنوان زیرمجموعه بهینه، جایگزین قبلی میشود. با توجه به ارتباط الگوریتم انتخاب ویژگی و روش های یادگیری استقرایی برای پی بردن به یک مدل سه روش عمده را می توان متمایز کرد . شکل 1 فرایند انتخاب ویژگی را نشان می دهد.

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

روش Filters در سالDash & Liu 2003 روشی را پیشنهاد کردند که به ویژگی های کلی داده های آموزشی تکیه می کند و فرایند انتخاب پارامتر را به عنوان یک گام مستقل الگوریتم القا، قبل از پیش پردازش داده ا انجام می دهد. در این روش، از هیچ تابع دسته بندی استفاده نمی شود. به عبارت دیگر از هیچ فیدبکی از الگوریتم یادگیری اعمال شده استفاده نخواهد شد. این یک روش از پیش انتخاب شده ای است که مستقل از الگوریتم یادگیری ماشین می باشد. زیرمجموعه های ویژگی بوسیله مفاهیم دیگری ارزیابی می شوند. روش فیلتر به صورت زیر کار می کند: در مرحله اول، برای هر ویژگی یک رتبه اعتبار محاسبه می شود. سپس این رتبه ها مرتب شده و ویژگی هایی با کمترین رتبه حذف می شوند. (ازیک آستانه برای رتبه های اولیه استفاده می شود)سپس نتایج زیر مجموعه ای از ویژگی ها به عنوان وروردی به یک سیستم دسته بند داده میشود. روش فیلتر، می تواند میان روش های تک متغیری و چند متغیری تمایز قائل شود. روش های تک متغیری مانند (InfoGain)سریع و مقیاس پذیر هستند، اما وابستگی های ویژگی ها را ردمیکند. از سوی دیگر Filters، چند متغیره مانند: CFS) ، INTERACT، و غیره)مدلی از وابستگی ویژگی هاست. اما ازلحاظ هزینه کندترمی باشد و مقیاس پذیری کمتری نسبت به

تکنیک های تک متغیری دارد. علاوه بر این طبقه بندی، روش های فیلترینگ را می توان به دو روش ارزیابی تقسیم کرد: ارزیابی فردی و ارزیابی زیر مجموعه . شکل 2فرایند فیلتر را نشان می دهد.

شکل.2تکنیک Filters

روش Wrappers در سالKohavi & John 1997 روشی را ارایه دادند. این روش به جعبه سیاه معروف است. در این روش از یک تابع دسته بندی برای ارزیابی شایستگی زیرمجموعه های ویژگی استفاده می شود. این روش از فیدبکی از الگوریتم یادگیری اعمال شده استفاده می کند.[15] که درآن پیش بینی به عنوان بخشی از فرآیند انتخاب می باشد. به عبارت دیگر این روش یک روش بازخورد می باشد که از الگوریتم یادگیری ماشین در فرایند انتخاب ویژگی استفاده می کند. این الگوریتم با مجموعه ای از ویژگی های خالی شروع می شود و جستجو رو به جلورا با اضافه کردن ویژگی ها تا بهبود نیافتن عملکرد انجام می دهدو ارزیابی بوسیله اجرای الگوریتم استقرایی در طول فازهای یادگیری و تست درهر انتخاب ویژگی، انجام می شود. SVM ,C4.5:دو طرح آموزشی شناخته شده از Wrappersمی باشند. شکل3فرایند Wrappers را نشان می دهد.

شکل.3تکنیک Wrappers

روشEmbedded درسالTibshirani 1996 روشی را پیشنهاد داد که درآن انتخاب پارامتر در روند آموزش و معمولا خاص ماشین آلات یادگیری تعبیه شده است. معمولا سریع تر از روش Wrapper هستند و قادر به ارائه زیر مجموعه ای از ویژگی های مناسب برای الگوریتم یادگیری می باشند.

1-2 تفاوت سه روش Embedded ، Wrappers ، : Filters

با توجه به توضیحات داده شده درروش فیلتر، انتخاب ویژگی به عنوان یک مرحله پیش پردازشی انجام می شودو بر ویژگی ها، بدون استفاده از هر گونه الگوریتم های طبقه بندی تکیه می کند و در واقع این روش مستقل از هر طبقه بندی است و اقدامات ارزیابی رابر اساس یک طبقه بندی با استفاده از پارامترهای انتخاب شده (فاصله، اطلاعات و همبستگی )انجام می دهد. یکی از معایب این روش این است که اثرات زیرمجموعه ویژگی انتخاب شده را بر روی کارآیی الگوریتم استقرایی در نظر نمی گیرد. درحالی که روش wrapperطبقه بندی از پیش تعیین شده ای برای ارزیابی پارامترهای انتخاب شده بکار می بردو جستجو اکتشافی را در فضای تمام زیر مجموعه ویژگی های ممکن انجام می دهدو از آنجاییکه می تواند خودش را با الگوریتم یادگیری ماشین استفاده شده تطبیق دهد، پس باید نتایج بهتری از روش فیلتر ارایه دهد اما این روش هزینه های محاسباتی زیادی دارد. روش هایEmbedded نیز با هدف یکپارچه سازی فرآیند انتخاب ویژگی درروند آموزشی مدل معمولا سریع تر از روشWrapper هستندو قادر به ارائه زیر مجموعه ای از ویژگی های مناسب برای الگوریتم یادگیری می باشند. جدول 1خلاصه ای از تفاوت های سه روش انتخاب ویژگی ، مزایا و معایب و همچنین چند نمونه از هر روش را نشان می دهد.

1-2-2 ارزیابی فردی:

در این روش با رتبه بندی ویژگی ها، پارامترهای منحصر به فرد با تخصیص وزن وبا توجه به درجه ارتباطی ارزیابی می شوند

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

J.R. Quinlan در سال 1969یکی از رایج ترین روش های ارزیابی ویژگی را پیشنهاد داد.[9] این روش فیلتر تک متغیری را فراهم می کند، رتبه بندی تمام ویژگی هارا انجام می دهد و سپس یک آستانه مورد نیاز است. این آستانه ویژگی هایی را که ارزش اطلاعاتی مثبتی دارند انتخاب میکند. این روش اندازه گیری وابستگی بین ویژگی و برچسب طبقاتی را اندازه گیری می کند. این الگوریتم یکی از محبوب ترین روش های انتخاب ویژگی است که برای انجام محاسبات ، آسان و ساده می باشد . در(IG ) Information Gainویژگی X با برچسب کلاسY به صورت زیر محاسبه می گردد:

آنتروپی (H) اندازه گیری نامطمئن یک متغیر تصادفی است.

H (X)آنتروپی X و H (X | Y) آنتروپی X پس از مشاهدهY است.

Kira and rendell در سال1992روشی به نام ReliefF را پیشنهاد کرد.[10] ایده اصلی در این الگوریتم این است که هر چه اختلاف بین اندازه یک ویژگی در نمونه انتخاب شده و نزدیکترین برخورد کمتر باشد، این ویژگی بهتر است و بعلاوه یک ویژگی خوب آن است که اختلاف بین اندازه آن ویژگی و نزدیکترین شکست وی بیشتر باشد. دلیل کار هم خیلی ساده است، ویژگی-هایی که به خوبی دو کلاس (یا یک کلاس از سایر کلاسها) را از هم تمییز میدهند، برای نمونههای متعلق به دو کلاس متفاوت مقادیری نزدیک بههم نمیدهند و یک فاصله معنیداری به مقادیری از نمونههای یک کلاس و مقادیری ازسایر کلاس(ها) میدهند.الگوریتم پس از تعیین نزدیکترین برخورد و نزدیکترین شکست، وزنهای ویژگیها را به روزرسانی میکند.

الگوریتم Relief برای ویژگیهای دارای نویز یا ویژگیهای دارای همبستگی خوب کار میکند و پیچیدگی زمانی آن بصورت خطی و تابعی از تعداد ویژگیها و تعداد نمونههای مجموعه نمونه میباشد. هم برای دادههای پیوسته و هم برای داده-های صوری خوب کار میکند. یکی از محدودیتهای اساسی این الگوریتم این است که ویژگیهایی که دارای افزونگی باشند را پیدا نمیکند و بنابراین مجموعههای غیر بهینه را که دارای افزونگی هستند پیدا میکند. این مشکل را میتوان با یک جستجوی تعیین جامعیت برای زیرمجموعههای تولید شده توسط الگوریتم حل کرد. علاوه بر این، مشکل دیگر این الگوریتم این است که با مسائل دو کلاسه خوب کار میکند. این محدودیت نیز با الگوریتم Relief-F مرتفع شده است، با الگوریتم جدید مشکل دادههای غیر کامل (نمونههای آموزشی غیرکامل) نیز حل شده است.

Hanchuan Pengو همکارانش روش)mRMRحداقل افزونگی - حداکثر ارتباط)را پیشنهاد کردند .[11] در این روش ویژگی هایی که دارای بالاترین ارتباط با کلاس مربوطه و همچنین حداقل افزونگی را داشته باشدانتخاب می شوند، به عنوان