فرایندی است که در آن داده‌ها در فضای با بعد بالا به فضای با بعد کمتر نگاشت می‌شوند. این نگاشت می‌تواند خطی (مانند روش تحلیل مؤلفه‌های اصلی) یا غیر خطی باشد.

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

تعداد متغیرهایی که برای هر مشاهده باید اندازه گیری شود ابعاد داده نامیده می­شود. عبارت “متغیر” (variable) بیشتر در آمار استفاده می­شود در حالی که در علوم کامپیوتر و یادگیری ماشین بیشتر از عبارات “ویژگی” (feature) و یا “صفت” (attribute) استفاده می­گردد.

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

روشهای کاهش ابعاد داده به دو دسته تقسیم می­شوند:

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

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

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

 


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

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

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

در مقاله [۳] نگاهی اجمالی به کلیه­ی روشهای کاهش ابعاد داده­ی مبتنی بر استخراج ویژگی شده است. در بخش ۲-۱ تبدیل فوریه گسسته و در بخش ۲-۲ تبدیل wavelet گسسته را شرح خواهیم داد. برای تهیه­ی بیشتر مطالبی که در این دو بخش ارائه شده از منبع [۴] که یک پایان نامه دکتری در زمینه­ی داده­کاوی برروی سریهای زمانی می­باشد استفاده شده است. در بخش ۲-۳ روش PCA که بهترین تبدیل خطی به حساب می­آید را بیان خواهیم کرد. برای تهیه­ی این بخش نیز از منبع [۵] استفاده کرده­ایم که یک tutorial بسیار عالی می­باشد. در بخش ۲-۴ روش Factor Analysis را بیان کرده­ایم. مطالب این بخش نیز از سایت اینترنت زیر تهیه شده است.

http://en.wikipedia.org/wiki/Factor_analysis

 

۱-۱-       Discrete Fourier Transform (DFT)

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

 

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

 

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

تعریف DFT – بردار را در نظر بگیرید. تبدیل فوریه گسسته­ی این بردار از رابطه­ی زیر بدست می­آید.

که در آن:

معکوس تبدیل فوریه گسسته نیز از این رابطه بدست می­آید:

توجه داشته باشید که دو بردار و هم­اندازه هستند.

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

برای کاهش ابعاد داده می­توان ابتدا را بدست آورده و سپس ضرایب کم اهمیت را حذف نمود. بعنوان مثال بردار که سری زمانی مربوط به قیمت روزانه­ی سهام شرکت IBM در سال ۲۰۰۱ می­باشد را در نظر بگیرید. این بردار که از ۲۵۶ مؤلفه تشکیل شده است را در شکل زیر نشان داده­ایم.

 

شکل ۲- قیمت روزانه سهام شرکت IBM در سال ۲۰۰۱

 

اکنون بردار را محاسبه می­کنیم. مسلماً نیز دارای ۲۵۶ مؤلفه خواهد بود. اگر فقط ۱۰ ضریب پر اهمیت­تر در را نگه داشته و بقیه را حذف نماییم، نموداری شبیه به اولین نمودار در شکل ۲ بدست خواهیم آورد. در این شکل مشاهده می­کنید که هرچه تعداد ضرایب بیشتری را نگه داری نماییم، جزئیات نمودار بیشتر حفظ خواهد شد.

 

شکل ۳- بازسازی نمودار قیمت روزانه سهام شرکت IBM با ضرایب بدست آمده از DFT

این نمودارها از بالا به پایین به ترتیب با حفظ ۱۰، ۲۰، ۴۰ و ۸۰ ضریب DFT بدست آمده­اند

 

۱-۲-     Discrete Wavelet Transform (DWT)

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

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

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

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

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

(۴, ۱۶, ۲۵, ۱)

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

(-۲, -۶, -۱, -۱)

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

 

شکل ۴- مراحل اجرای تبدیل Haar Wavelet برروی یک رشته به طول ۸

 

مراحل اجرای این تبدیل برروی رشته S را می­توانید در شکل زیر مشاهده کنید.

 

شکل ۵- مراحل اجرای تبدیل Haar Wavelet برروی رشته S

 

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

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

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

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

برای اینکه درک شهودی بهتری نسبت به حذف ضرایب کم اهمیت و تأثیر آن در از دست رفتن اطلاعات داشته باشید به شکل ۶ توجه کنید. در این شکل یک سری زمانی را که با نقطه چین نشان داده شده، به همراه تبدیل Haar Wavelet با حذف ضرایب کم اهمیت را مشاهده می­کنید.

 

[۱] Global flat subspace

[۲] Locally flat subspace

[۳] Fast Fourier Transform