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

از روشهای خطی می­توان به 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 مؤلفه­ی اولیه بدست آورند.

که Wk×p ماتریس وزنهای نگاشت خطی می­باشد.

Discrete Fourier Transform (DFT)

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

 

شکل ۱- تبدیل فوریه سعی می­کند یک تابع را بصورت توابع پایه­ای سینوسی نشان دهد

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

 Discrete Wavelet Transform (DWT)

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

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

Principal Component Analysis (PCA)

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

 

 

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

  • Singular Value Decomposition (SVD)
  • Karhunen Loeve Transform (KLT)
  • Hotelling Transform
  • Empirical Orthogonal Function (EOF)

Factor Analysis (FA)

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