پروژه مطالعاتی درس يادگيری ماشين Dimensionality Reduction

فهرست مطالب

 

1-     مقدمه3

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

2-1-    Discrete Fourier Transform ( DFT) 6

2-2-    Discrete Wavelet Transform ( DWT) 9

2-3-    Principal Component Analysis ( PCA) 12

2-3-1-   مفاهيم مقدماتي مورد نياز در PCA. 13

2-3-2-   الگوريتم PCA. 15

2-4-    Factor Analysis (FA)20

3-   روشهای مبتنی بر انتخاب ويژگی  23

3-1-   تعاريف. 23

3-2-   روشهاي مختلف انتخاب ويژگي. 26

3-2-1-    توابع توليد کننده 26

3-2-2-   تابع ارزيابي . 27

3-2-3-    دسته بندي و تشريح الگوريتم‌هاي مختلف انتخاب ويژگي  30

3-2-4-   جمع بندي روشهاي انتخاب ويژگي . 43

4-  فهرست منابع و مراجع  45

 

 


1-  مقدمه

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

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

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

روشهاي كاهش ابعاد داده به دو دسته تقسيم مي­شوند:

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

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

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

 


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

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

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

در مقاله [3] نگاهي اجمالي به كليه­ي روشهاي كاهش ابعاد داده­ي مبتني بر استخراج ويژگي شده است. در بخش 2-1 تبديل فوريه گسسته و در بخش 2-2 تبديل wavelet گسسته را شرح خواهيم داد. براي تهيه­ي بيشتر مطالبي كه در اين دو بخش ارائه شده از منبع [4] كه يك پايان نامه دكتري در زمينه­ي داده­كاوي برروي سريهاي زماني مي­باشد استفاده شده است. در بخش 2-3 روش PCA كه بهترين تبديل خطي به حساب مي­آيد را بيان خواهيم كرد. براي تهيه­ي اين بخش نيز از منبع [5] استفاده كرده­ايم كه يك tutorial بسيار عالي مي­باشد. در بخش 2-4 روش Factor Analysis را بيان كرده­ايم. مطالب اين بخش نيز از سايت اينترنت زير تهيه شده است.

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

 

2-1-     Discrete Fourier Transform (DFT)

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

 

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

 

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

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

که در آن:

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

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

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

براي کاهش ابعاد داده  مي­توان ابتدا  را بدست آورده و سپس ضرايب کم اهميت را حذف نمود. بعنوان مثال بردار  که سري زماني مربوط به قيمت روزانه­ي سهام شرکت IBM در سال 2001 مي­باشد را در نظر بگيريد. اين بردار که از 256 مؤلفه تشکيل شده است را در شکل زير نشان داده­ايم.

 

شکل 2- قيمت روزانه سهام شرکت IBM در سال 2001

 

اکنون بردار  را محاسبه مي­کنيم. مسلماً  نيز داراي 256 مؤلفه خواهد بود. اگر فقط 10 ضريب پر اهميت­تر در  را نگه داشته و بقيه را حذف نماييم، نموداري شبيه به اولين نمودار در شکل 2 بدست خواهيم آورد. در اين شکل مشاهده مي­کنيد که هرچه تعداد ضرايب بيشتري را نگه داري نماييم، جزئيات نمودار بيشتر حفظ خواهد شد.

 

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

اين نمودارها از بالا به پايين به ترتيب با حفظ 10، 20، 40 و 80 ضريب DFT بدست آمده­اند

 

2-2-   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 در شکل زير نشان داده شده است.

 

شکل 4- مراحل اجراي تبديل Haar Wavelet برروي يک رشته به طول 8

 

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

 

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

 

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

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

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

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

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

 

شکل 6- کاهش ابعاد يک سري زماني توسط تبديل Haar Wavelet

از بالا به پايين، سطح resolution به ترتيب برابر است با 3، 4، 5 و 6

 

 

2-3-  Principal Component Analysis (PCA)

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

 

شکل 7- انتخاب محورهاي جديد براي داده­هاي دو بعدي

 

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

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

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

 

2-3-1-   مفاهيم مقدماتي مورد نياز در PCA

2-3-1-1-    مفاهيم آماري

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

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

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

http://mathcentral.uregina.ca/RR/database/RR.09.95/weston2.html

با بتوان 2 رساندن انحراف از معيار، واريانس بدست مي­آيد.

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

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

  • اگر مقدار بدست آمده مثبت باشد آنگاه X و Y با هم افزايش يا کاهش مي­يابند.
  • اگر مقدار بدست آمده منفي باشد آنگاه با افزايش X مقدار Y کاهش مي­يابد و بالعکس.
  • اگر مقدار بدست آمده صفر باشد آنگاه X و Y از يکديگر مستقلند.

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

 

2-3-1-2-   مفاهيم جبر ماتريسها

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

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

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

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

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

بدست آوردن بردارهاي ويژه براي ماتريسهاي بزرگتر از 3×3 کار نسبتاً دشواري است. اين کار توسط يک الگوريتم بازگشتي انجام مي­شود که توضيح آن خارج از حوصله­ي اين گزارش (و نيز حوصله­ي نويسنده) است. براي اطلاعات بيشتر در اين رابطه مي­توانيد به کتاب [2] مراجعه کنيد.

 

2-3-2-الگوريتم PCA

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

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

در اينجا ما قصد داريم PCA را برروي يک مجموعه داده­ي دو بعدي اعمال کنيم. اين داده­ها در شکل زير نشان داده شده است.

شکل 8- داده­هاي دوبعدي اوليه که قرار است PCA برروي آنها اعمال شود

 

مرحله 2– کم کردن ميانگين از داده­ها

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

مرحله 3– محاسبه­ي ماتريس کواريانس

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

مرحله 4– محاسبه­ي بردارهاي ويژه و مقادير ويژه

اکنون بردارهاي ويژه و مقادير ويژه­ي ماتريس کواريانس را محاسبه مي­کنيم. ماتريس کواريانس، يک ماتريس نيمه قطعي مثبت متقارن[5] است. طبق قضاياي جبر خطي، يک ماتريس متقارن n×n داراي n بردار ويژه­ي مستقل و n مقدار ويژه مي­باشد. همچنين يک ماتريس نيمه قطعي مثبت، داراي مقادير ويژه­ي غير منفي است. اين مقادير براي مثال ما برابر است با:

توجه داشته باشيد که اين دو بردار ويژه به گونه­اي انتخاب شده­اند که طول هر دو برابر با 1 باشد. اما اين دو بردار چه چيزي به ما مي­دهد؟ ما راستاي اين دو بردار را در شکل 9 نشان داده­ايم. همانطور که مي­بينيد يکي از اين دو بردار در جهتي قرار گرفته است که داده­ها در آن جهت بيشترين پراکندگي را دارند. بردار ديگر نيز عمود بر بردار اول است. و اما مقادير ويژه چه چيزي ارائه مي­دهند؟ در اين مثال برداري که در راستاي بيشترين پراکندگي داده­ها قرار گرفته داراي مقدار ويژه 1.284 و بردار ديگر داراي مقدار ويژه 0.049 مي­باشد. در واقع مقادير ويژه ميزان پراکندگي داده­ها در راستاي بردار ويژه­ي مربوطه را نشان مي­دهد. مي­توان گفت بردار ويژه­اي که داراي بزرگترين مقدار ويژه است مؤلفه­ي اصلي[6] داده­هاي موجود مي­باشد.

 

شکل 9- داده­هاي نرمالسازي شده (با کم شدن ميانگين) به همراه بردارهاي ويژگي ماتريس کواريانس

 

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

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

کاري که بايد در اين مرحله انجام دهيم ايجاد يک Feature Vector است که در واقع ماتريسي از بردارها مي­باشد. اين ماتريس شامل آن بردارهاي ويژگي­اي است که ما مي­خواهيم آنها را نگه داريم.

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

مرحله 6– بدست آوردن داده­هاي جديد

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

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

 

شکل 10- داده­هاي بدست آمده از تبديل PCA با انتخاب مهمترين بردار ويژگي

 

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

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

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

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

 

شکل 11- داده­هاي بازيابي شده از تبديل PCA با انتخاب مهمترين بردار ويژگي

 

2-4-   Factor Analysis (FA)

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

اجازه بدهيد با يک مثال اين موضوع را ادامه دهيم. فرض کنيد يک روانشناس نظريه­اي ارائه داده و در آن ادعا کرده که دو نوع هوش به نامهاي هوش شفاهي[8] و هوش رياضي[9] وجود دارد. اين نظريه از بررسي نمرات 1000 دانشجو در 10 درس مختلف بدست آمده است. اگر يک دانشجو را از اين مجموعه بطور تصادفي انتخاب نماييم، 10 نمره­ي مربوط به آن دانشجو، متغيرهاي تصادفي محسوب مي­شوند. نظريه­ي اين روانشناس مي­گويد ميانگين هر يک از اين 10 درس براي دانشجوياني که داراي هوش شفاهي در يک سطح خاص و نيز هوش رياضي در يک سطح خاص هستند برابر است با يک عدد مشخص ضرب در سطح هوش شفاهي بعلاوه­ي يک عدد مشخص ديگر ضرب در هوش رياضي. بعبارت ديگر اين مقادير را مي­توان از ترکيب خطي دو فاکتور هوش شفاهي و هوش رياضي بدست آورد. بر طبق ادعاي اين نظريه، اعدادي که در هر يک از اين دو نوع هوش ضرب شده­اند، براي تمامي دانشجويان يکسان است. به اين اعداد factor loadings مي­گويند. بعنوان مثال ميانگين (اميد رياضي) نمره يک دانشجو در درس کالبد شناسي مي­تواند از رابطه زير بدست آيد:

{10 × the student’s verbal intelligence + 6 × the student’s mathematical intelligence}

اعداد 10 و 6، factor loadingهاي درس کالبد شناسي مي­باشند. دروس ديگر ممکن factor loadingهاي متفاوتي داشته باشند. دو دانشجو که داراي هوش شفاهي برابر و نيز هوش رياضي برابر هستند لزوماً داراي نمره يکساني در درس کالبد شناسي نيستند. زيرا تک نمره با ميانگين نمرات فرق مي­کند. به اين اختلاف، خطا (error) مي­گوييم.

در اين مثال داده­هايي که قرار است FA برروي آنها اعمال شود عبارتست از 10 نمره براي هر يک از 1000 دانشجو، يعني مجموعاً 10000 عدد که داده­هاي ما را تشکيل مي­دهند. مقادير factor loading براي هر درس و سطح هر يک از دو نوع هوش براي هر دانشجو بايد از اين داده­هاي موجود استخراج شود. حتي تعداد فاکتورهاي موجود در داده­ها (که در اين مثال برابر با 2 است) را بايد از اين داده­ها بدست آورد.

مدل رياضي براي مثال فوق را مي­توان به اين صورت نوشت:

به ازاي i=1,…,1000 ، نمرات دانشجوي شماره i برابر است با

 

 

که در آن:

  • xk,i : نمره­ي دانشجوي i در درس k
  • vi : هوش شفاهي دانشجوي i
  • mi: هوش رياضي دانشجوي i
  • Lk,j : مقدار factor loading براي درس k، به ازاي j=1,2
  • k,iε : اختلاف بين نمره­ي دانشجوي شماره i در درس k و ميانگين نمرات تمام دانشجوياني که داراي هوش شفاهي و رياضي در همان سطح دانشجوي i هستند در درس k

 

عبارات فوق را با استفاده از عبارات ماتريسي مي­توان به اين صورت نوشت:

X = µ + LF + ε

که در آن:

  • X : يک ماتريس 10×1000 از متغيرهاي تصادفي مشاهده شده (در اينجا نمرات دانشجويان)
  • µ : يک ماتريس ستوني 10×1 از ثابتهاي پنهان (در واقع اين ماتريس را بايد يک ماتريس 10×1000 در نظر گرفت که در آن مقاديري که در يک سطر قرار گرفته اند با هم برابرند)
  • L : يک ماتريس 10×2 که حاوي مقادير factor loading است
  • F : يک ماتريس 2×1000 که حاوي ميزان هوش رياضي و شفاهي هر يک از دانشجويان است
  • ε : يک ماتريس 10×1000 که حاوي مقادير خطا است.

 

ماتريسهاي L، µ و واريانس خطاها در ε را بايد از ماتريس X بدست آورد.

 

 

دريافت فايل اصلي

پیام بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

+ fifty seven = sixty