روش‌های مبتنی بر استخراج ویژگی

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

از روش­های خطی می‌توان به DFT، DWT، PCA و FA اشاره کرد که آنها را به ترتیب توضیح خواهیم داد. روش‌های دیگر غیرخطی عبارتند از:

Projection Pursuit (PP): برخلاف روشهای PCA و FA می‌تواند اطلاعات بالاتر از مرتبه دوم را ترکیب نماید. بنابراین روش مناسبی است برای بسترهای داده‌ای غیر گاوسی.

Independent Component Analysis (ICA): این روش نیز یک نگاشت خطی انجام می‌دهد اما بردارهای این نگاشت لزوماً بر یکدیگر عمود نیستند، در حالی که در روش­های دیگر مانند PCA این بردارها بر هم عمودند.

Random Projection (PP): یک روش ساده و در عین حال قدرتمند برای کاهش ابعاد داده است که از ماتریس­های نگاشت تصادفی برای نگاشت داده‌ها به یک فضای با ابعاد کمتر استفاده می‌کند.

از روش­های غیرخطی نیز می‌توان به موارد زیر اشاره کرد:

Principal Curves

Self Organizing Maps

Vector Quantization

Genetic and Evolutionary Algorithms

Regression

مسئله کاهش ابعاد داده را بطور ریاضی می‌توان به این صورت بیان کرد: یک متغیر تصادفی p بعدی  داریم. می‌خواهیم متغیر k بعدی را به گونه‌ای پیدا کنیم که اولاً k ≤ p باشد و ثانیاً s محتویاتی که در x وجود دارد را بر اساس معیاری خاص دارا باشد. روش‌های خطی سعی می‌کنند هر یک از این k مؤلفه را از ترکیب خطی p مؤلفه اولیه بدست آورند.

که W_k×p ماتریس وزن­های نگاشت خطی می‌باشد. در مقاله [3] نگاهی اجمالی به کلیه روش­های کاهش ابعاد داده مبتنی بر استخراج ویژگی شده است.

 Discrete Fourier Transform (DFT)

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

تبدیل فوریه یک تبدیل برگشت پذیر است. این تبدیل می‌تواند به دو صورت پیوسته یا گسسته انجام شود. در کامپیوتر و بخصوص در پردازش سیگنال معمولاً از تبدیل فوریه گسسته (DFT) استفاده می‌شود. الگوریتم­های سریعی تحت عنوان FFT برای تبدیل فوریه گسسته به وجود آمده است. در این بخش می‌خواهیم کاربرد DFT را در کاهش ابعاد داده مورد بررسی قرار دهیم.

ضرایب بدست آمده از تبدیل فوریه به گونه‌ای مرتب شده قرار می‌گیرند بطوریکه ضرایب پر اهمیت در سمت چپ و ضرایب کم اهمیت‌تر در سمت راست قرار می‌گیرند. بنابراین پر اهمیت‌ترین ضریب در X(0) و کم اهمیت‌ترین ضریب در X(N-1) ذخیره می­شوند. هرچه یک ضریب پر اهمیت‌تر باشد، بدان معنی است که آن ضریب حاوی اطلاعات مهمتری (کلی‌تری) از بردار  می‌باشد. برای کاهش ابعاد داده  می‌توان ابتدا  را بدست آورده و سپس ضرایب کم اهمیت را حذف نمود.

 Discrete Wavelet Transform (DWT)

تبدیل DWT برای اولین بار توسط شخصی به نام Alfred Haar بوجود آمد. تا کنون نسخه‌های مختلفی برای DWT ارائه شده است، مانندHaar Wavelet، Newland Transform و Undecimated Wavelet Transform. این تبدیل نیز همانند تبدیل فوریه بسیار پرکاربرد است و در بسیاری از زمینه‌های علوم و مهندسی مورد توجه قرار گرفته است. تبدیل Haar Wavelet بدلیل سادگی در پیاده سازی و سرعت اجرای بالا، از محبوبیت بیشتری نسبت به سایر نسخه‌های DWT برخوردار است.

این تبدیل به اینصورت است که یک توالی به طول 2n در ورودی داریم. این اعداد بصورت جفت جفت با هم جمع شده و این حاصل جمع‌ها به مرحله بعد فرستاده می‌شوند. همچنین اختلاف هر جفت نیز محاسبه و ذخیره می‌شود. دوباره این مرحله تکرار می‌شود با این تفاوت که در ورودی، حاصل جمع جفت­های مرحله قبل قرار می‌گیرد. این فرایند بطور بازگشتی تکرار می‌شود تا در نهایت یک عدد که حاصل جمع کل اعداد است بدست آید. این عدد به همراه 2n-1 اختلاف جفت­ها که در مراحل مختلف الگوریتم محاسبه شده بعنوان خروجی این تبدیل بازگردانده می‌شود.

بعنوان مثال فرض کنید می‌خواهیم تبدیل Haar Wavelet را برروی رشته S بطول 8 اعمال نماییم.

S = (1, 3, 5, 11, 12, 13, 0, 1)

ابتدا این اعداد را بصورت جفت جفت با هم جمع می‌کنیم.

(4, 16, 25, 1)

همچنین اختلاف این جفتها را نیز محاسبه می‌کنیم.

(-2, -6, -1, -1)

واضح است که با استفاده از حاصل جمع جفتها و نیز اختلاف جفتها می‌توان رشته S را بدون از دست دادن هیچ اطلاعاتی دوباره بازسازی کرد. اکنون با اختلاف جفت­ها کاری نداریم و فقط آنها را ذخیره می‌کنیم. سپس همین مراحل را برروی این چهار حاصل جمع تکرار می‌کنیم. درخت تجزیه تبدیل Haar Wavelet برای یک رشته به طول 8 در شکل زیر نشان داده شده است.

حاصل جمع بدست آمده در آخرین مرحله، به همراه حاصل تفریق‌هایی که در تمام مراحل ذخیره شده، بعنوان خروجی این تبدیل در نظر گرفته می‌شود. بنابراین:

DWT(S) = (46, -6, -12, 24, -2, -6, -1, -1)

می‌توان دید که پیچیدگی زمانی این الگوریتم برای یک رشته به طول n برابر با O(n) می‌باشد.

اما چگونه می‌توان با استفاده از تبدیل DWT ابعاد داده را کاهش داد؟ در اینجا نیز همانند تبدیل فوریه، ضرایب بدست آمده به ترتیب پر اهمیت تا کم اهمیت مرتب شده‌اند. در واقع ضرایب کم اهمیت همان­هایی هستند که در مراحل اولیه الگوریتم بدست می‌آیند (مثلاً در شکل 5 کم اهمیت‌ترین ضرایب مربوط به Resolution=3 هستند، یعنی -2، -6، -1 و -1). با حذف ضرایب کم اهمیت می‌توان حجم داده‌ها را کاهش داد. البته مقدار کمی از اطلاعات نیز از بین می‌رود.

Principal Component Analysis (PCA)

تکنیک PCA بهترین روش برای کاهش ابعاد داده به صورت خطی می‌باشد. یعنی با حذف ضرایب کم‌اهمیت بدست آمده از این تبدیل، اطلاعات از دست رفته نسبت به روش­های دیگر کمتر است. البته کاربرد PCA محدود به کاهش ابعاد داده نمی‌شود و در زمینه‌های دیگری مانند شناسایی الگو و تشخیص چهره نیز مورد استفاده قرار می‌گیرد. در این روش محورهای مختصات جدیدی برای داده‌ها تعریف شده و داده‌ها براساس این محورهای مختصات جدید بیان می‌شوند. اولین محور باید در جهتی قرار گیرد که واریانس داده‌ها ماکسیمم شود (یعنی در جهتی که پراکندگی داده‌ها بیشتر است). دومین محور باید عمود بر محور اول به گونه‌ای قرار گیرد که واریانس داده‌ها ماکسیمم شود. به همین ترتیب محورهای بعدی عمود بر تمامی محورهای قبلی به گونه‌ای قرار می‌گیرند که داده‌ها در آن جهت دارای بیشترین پراکندگی باشند. در شکل زیر این مطلب برای داده‌های دو بعدی نشان داده شده است.

روش PCA به نامهای دیگری نیز معروف است. مانند:

Singular Value Decomposition (SVD)

 Karhunen Loeve Transform (KLT)

 Hotelling Transform

(Empirical Orthogonal Function (EOF

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

  مفاهیم مقدماتی مورد نیاز در PCA

   مفاهیم آماری

فرض کنید X رشته‌ای از مقادیر است. میانگین این مقادیر از رابطه زیر بدست می‌آید.

انحراف از معیار نیز از رابطه زیر محاسبه می‌شود.

علت اینکه در مخرج رابطه فوق از عبارت n-1 استفاده شده (و نه n) اینست که فرض شده X شامل تمام مقادیر موجود نیست بلکه تعدادی از این مقادیر انتخاب شده‌اند و در X قرار گرفته‌اند. یعنی X مجموعه نمونه است و نه کل داده‌ها. با این فرض اگر از n-1 در رابطه فوق استفاده شود، انحراف از معیار بدست آمده به انحراف از معیار داده‌های واقعی نزدیکتر خواهد بود نسبت به اینکه از n استفاده شود. با بتوان 2 رساندن انحراف از معیار، واریانس بدست می‌آید.

معیارهایی که در بالا ذکر شد فقط اطلاعات مربوط به یک بُعد را ارائه می‌کنند و دانشی در مورد ارتباط بین ابعاد مختلف به ما نمی‌دهند. با استفاده از کواریانس می‌توانیم ارتباط بین ابعاد مختلف داده‌ها را پیدا کنیم. فرض کنید یک رشته دیگر از اعداد داریم که آن را با Y نشان می‌دهیم. کواریانس بین X و Y از رابطه زیر بدست می‌آید.

مقداری که از رابطه بالا بدست می‌آید در بازه [-1,1] قرار خواهد داشت که یکی از سه حالت زیر را بوجود می‌آورد:

اگر مقدار بدست آمده مثبت باشد آنگاه X و Y با هم افزایش یا کاهش می‌یابند.

اگر مقدار بدست آمده منفی باشد آنگاه با افزایش X مقدار Y کاهش می‌یابد و بالعکس.

اگر مقدار بدست آمده صفر باشد آنگاه X و Y از یکدیگر مستقل هستند.

کواریانس بین تمامی ابعاد داده‌ها را می‌توان دوبه‌دو محاسبه کرده و در یک ماتریس ذخیره کرد. به این ماتریس، ماتریس کواریانس می‌گویند. ماتریس کواریانس یک ماتریس مربعی متقارن است. مثلاً اگر سه بعد به نامهای x، y و z داشته باشیم، ماتریس کواریانس آن‌ها برابر است با:

 مفاهیم جبر ماتریسها

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

در مثال اول بردار بدست آمده مضرب صحیحی از بردار اولیه نیست. اما در مثال دوم، بردار بدست آمده چهار برابر بردار اولیه می‌باشد. ماتریس 2×2 که در این دو بردار ضرب کرده‌ایم را می‌توان یک ماتریس تبدیل در نظر گرفت که با ضرب آن در یک بردار می‌توان اندازه و راستای آن بردار را تغییر داد. در میان تمام بردارهایی که می‌توان ماتریس تبدیل را در آنها ضرب کرد، بردارهایی وجود دارد که پس از تبدیل راستای آنها تغییر نمی‌کند و فقط اندازه آنها ممکن است عوض شود، مانند بردار [3;2] در مثال فوق. این بردارها را بردارهای ویژه می‌نامند. برای هر بردار ویژه یک مقدار ویژه نیز وجود دارد که بیان می‌کند اندازه آن بردار (و تمام بردارهای دیگر که در راستای آن بردار هستند) پس از تبدیل، چند برابر خواهد شد. در مثال فوق مقدار ویژه برای بردار [3;2] و البته تمام بردارهای هم راستا با آن مانند [6;4] برابر با 4می‌باشد.

بردارهای ویژه و مقادیر ویژه فقط برای ماتریسهای مربعی معنی پیدا می‌کنند. یک ماتریس n×n می‌تواند دارای n بردار ویژه باشد. به منظور استاندارد کردن بردارهای ویژه، پس از یافتن بردارهای ویژه اندازه آنها را به گونه‌ای تغییر می‌دهند تا طول آنها برابر با یک شود. مثلاً برای بردار [3;2] داریم:

ویژگی مهم بردارهای ویژه اینست که آنها برهم عمودند. مثلاً ماتریس تبدیل زیر را در نظر بگیرید.

با ضرب ماتریس A در هر بردار می‌توان قرینه آن بردار نسبت به خط y=0 را بدست آورد. بردارهای ویژه این ماتریس عبارتند از [1;0] و[0;1]. مقادیر ویژه این بردارها نیز به ترتیب -1 و 1 می‌باشد. همان طور که گفتیم این دو بردار ویژه برهم عمودند. بدست آوردن بردارهای ویژه برای ماتریس‌های بزرگ‌تر از 3×3 کار نسبتاً دشواری است.

 الگوریتم PCA

در این بخش الگوریتم PCA را با ذکر یک مثال توضیح می‌دهیم.

مرحله 1- انتخاب داده

مرحله 2- کم کردن میانگین از داده‌ها

در این مرحله، میانگین هر بُعد را از مقادیر آن بُعد کم می‌کنیم تا میانگین داده‌ها در هر بُعد صفر شود.

مرحله 3- محاسبه ماتریس کواریانس

ماتریس کواریانس را به طریقی که در بالا ذکر شد برای داده‌ها بدست می‌آوریم. برای مثال ما این ماتریس، یک ماتریس 2×2 است:

مرحله 4- محاسبه بردارهای ویژه و مقادیر ویژه

اکنون بردارهای ویژه و مقادیر ویژه ماتریس کواریانس را محاسبه می‌کنیم. ماتریس کواریانس، یک ماتریس نیمه قطعی مثبت متقارن است. طبق قضایای جبر خطی، یک ماتریس متقارن n×n دارای n بردار ویژه مستقل و n مقدار ویژه می‌باشد. همچنین یک ماتریس نیمه قطعی مثبت، دارای مقادیر ویژه غیر منفی است.

مرحله 5- انتخاب مؤلفه‌ها و ساختن Feature Vector

در این مرحله مفهوم کاهش ابعاد داده وارد می‌شود. بردارهای ویژه‌ای که در مرحله قبل بدست آوردیم را بر اساس مقادیر ویژه آنها از بزرگ به کوچک مرتب می‌کنیم (توجه داشته باشید که مقادیر ویژه ماتریس کواریانس همگی بزرگتر یا مساوی صفر هستند). بدین ترتیب مؤلفه‌های داده‌ها از پر اهمیت به کم اهمیت مرتب می‌شوند. در اینجا اگر بخواهیم ابعاد داده‌ها را کاهش دهیم می‌توانیم مؤلفه‌های کم اهمیت را حذف نماییم. البته این کار با از دست دادن مقدار کمی اطلاعات همراه است.کاری که باید در این مرحله انجام دهیم ایجاد یکFeature Vector است که در واقع ماتریسی از بردارها می‌باشد. این ماتریس شامل آن بردارهای ویژگی‌ای است که ما می‌خواهیم آنها را نگه داریم.

اگر همه بردارهای ویژگی را در این ماتریس قرار دهیم، هیچ اطلاعاتی از دست نخواهد رفت و دوباره می‌توانیم دقیقاً همان داده‌های اولیه را بدست آوریم. در ادامه مثال فوق، Feature Vector را برابر با مقدار زیر در نظر می‌گیریم.

مرحله 6- بدست آوردن داده‌های جدید

در آخرین مرحله از PCA فقط باید ترانهاده ماتریس Feature Vector که در مرحله قبل بدست آوردیم را در ترانهاده داده‌های نرمالسازی شده ضرب نماییم.

که RowFeatureVector ماتریسی است که بردارهای ویژه در سطرهای آن به ترتیب مقادیر ویژه از بالا به پایین قرار گرفته‌اند، وRowDataAdjust ماتریسی است که شامل داده‌هایی است که میانگین هر بُعد از آن بُعد کم شده است. در این ماتریس، داده‌ها در ستونهای آن ذخیره شده و هر سطر آن مربوط به یک بُعد است. در مثال ذکر شده بدلیل اینکه ما فقط یکی از بردارهای ویژه را انتخاب کردیم داده‌های بدست آمده از PCA، داده‌های یک بُعدی می‌باشند.

با استفاده از رابطه زیر می‌توانیم مقادیری که از تبدیل PCA بدست آورده‌ایم را به داده‌های اولیه که مقدار میانگین از آنها کم شده بازگردانیم.

بدلیل اینکه ماتریس RowFeatureVector حاوی بردارهای ویژه یکه است، معکوس آن با ترانهاده آن برابر است. بنابراین:

با اضافه کردن میانگین، داده‌های اولیه را خواهیم داشت:

در شکل زیر داده‌هایی که پس از تبدیل PCA بازیابی شده‌اند را مشاهده می‌کنید. همانطور که می‌بینید مقدار کمی اطلاعات از بین رفته است و باعث شده داده‌ها همگی در امتداد یک خط راست قرار گیرند.

Factor Analysis (FA)

FA یکی از روش­های آماری است که می‌تواند چندین متغیر تصادفی مشاهده شده را توسط تعداد کمتری متغیر تصادفی (که در داده‌ها پنهان هستند) نمایش دهد. این متغیرهای تصادفی پنهان، فاکتور (factor) نامیده می‌شوند. این روش سعی می‌کند متغیرهای تصادفی مشاهده شده را توسط ترکیب خطی فاکتورها بعلاوه مقداری خطا مدلسازی نماید. روش FA از رشته هوش سنجی سرچشمه گرفته و در زمینه‌های علوم اجتماعی، بازاریابی، مدیریت تولید، تحقیق در عملیات و علوم کاربردی دیگر که با حجم بزرگی از داده‌ها سروکار دارند مورد استفاده قرار گرفته است. این روش برای اولین بار حدود 100 سال پیش توسط یک روانشناس به نام Charles Spearman ابداع شد. این شخص نظریه‌ای به نام g theory ارائه داد و در آن ادعا کرد که تمام توانمندیهای ذهنی افراد مانند مهارتهای ریاضی، مهارت‌های هنری، دایره لغات، توانایی استدلالهای منطقی و غیره را می‌توان توسط یک فاکتور به نام هوش عمومیبیان کرد. البته این نظریه امروزه رد شده و تحقیقات انجام شده نشان می‌دهد که توانمندیهای ذهنی حداقل از سه فاکتور به نام­های توانائی ریاضی، توانائی شفاهی و توانائی منطقی تشکیل شده است. روانشناسان زیادی بر این باورند که علاوه بر این سه فاکتور، فاکتورهای دیگری وجود دارد که می‌تواند بر توانمندیهای ذهنی افراد تأثیرگذار باشد.

[1].  Koller, D. and Sahami, M., Toward optimal feature selection. In: Proceedings of International Conference on Machine learning, 1996.

[2].  Quinlan, J.R., C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, California, 1993.

[3].  Sheinvald, J., Dom, B. and Niblack, W., A modelling approach to feature selection. In: Proceedings of Tenth International Conference on Pattern Recognition, 1:535–539, June 1990.

[4].  Rissanen, J., Modelling by shortest data description. Automatica, 14:465–471, 1978.

[5].  Mucciardi, A.N. and Gose, E.E., A comparison of seven techniques for choosing subsets of pattern recognition. IEEE Transactions on Computers, C-20:1023–1031, September 1971.

[6].  Modrzejewski, M., Feature selection using rough sets theory. In: Proceedings of the European Conference on Machine Learning (P. B. Brazdil, ed.), 213–226, 1993.