همه چیز درباره ی کاهش بعد داده ها با روش PCA

دلایل زیادی برای کاهش بعد داده ها وجود دارد از جمله می توان موارد زیر را برشمرد:

-          سرعت الگوریتم ها با داده های با بعد کمتر بیشتر می شود

-          فضای ذخیره سازی کمتری نیاز است

-          احتمال overfitting کاهش می یابد و بنابراین قدرت تعمیم الگوریتم های یادگیر بیشتر می شود

-          برای ترسیم و بدست آوردن درکی از مجموعه داده ها گاهی بعد داده ها را به دو یا سه بعد تقلیل می دهند تا بتوانند نموداری از داده های با ابعاد زیاد ترسیم کنند.

به هر دلیلی که بخواهید کاهش بعد را انجام دهید یکی از مرسوم ترین روش های انجام این کار روش PCA است. در این نوشتار سعی شده تا حد ممکن روش PCA بصورت کامل معرفی و نحوه ی استفاده از آن در تئوری و عمل بیان شود.

 

مجموعه بردارهای دو بعدی زیر را در نظر بگیرید. فرض می کنیم بردارها ستونی باشند.( به همین دلیل علامت ترانهاده بالای آنها قرار دارد)

D={(1,0)T,(2,0)T,(3,0)T,(4,0)T}D={(1,0)T,(2,0)T,(3,0)T,(4,0)T}

هر عضو این مجموعه  یک بردار دو بعدی به صورت  (x1,x2)(x1,x2) است. که مولفه اول مقدار ویژگی اول و مولفه دوم مقدار ویژگی دوم را نشان می دهد.

چون این داده ها دو بعدی هستند می توانیم آنها را در نمودار نشان دهیم.

p9-1

در این مثال اگر مولفه ی x2x2 را حذف کنیم هیچ اطلاعاتی را از دست نمی دهیم چراکه این داد ها در راستای x2x2 واریانسی ندارند. حتی اگر در راستای x2x2 واریانس خیلی کمی در مقایسه با x1x1 هم وجود داشت باز هم حذف این مولفه مفید بود چرا که منجر به از بین رفتن اطلاعات زیادی نمی شد.

حالا مجموعه نقاط زیر را در نظر بگیرید

D={(1,1)T,(2,2)T,(3,3)T,(4,4)T}D={(1,1)T,(2,2)T,(3,3)T,(4,4)T}

p9-2

اگر یک مولفه از داده ها مثلا x2x2 را حذف کنیم اطلاعات را از دست می دهیم چراکه این داد ها در هر دو راستای x1x1 و x2x2 دارای واریانس قابل توجهی هستند.

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

p9-3

بنابراین چرخاندن دستگاه مختصات در جهت بیشترین واریانس داده ها می تواند به ما در کاهش تعداد ویژگی های داده ها (کاهش بعد) کمک کند. این کار مانند این است که بخواهیم داده ها را در جهت بیشترین واریانس آنها تصویر کنیم.

اما چگونه می توانیم راستا یا راستا هایی که داده ها بیشترین واریانس را در آنها دارند بیابیم؟

روش Principal Component Analysis بر اساس تعیین مولفه های اصلی یا (Principal Component ها) در داده ها این کار را انجام می دهد. مولفه های اصلی در حقیقت همان بردار ویژه های ماتریس کوواریانس داده ها هستند. بیشترین واریانس داد ها در راستایی قرار دارد که بردار ویژه ی متناظر با بزرگترین مقدار ویژه در آن راستا قرار دارد. به همین ترتیب هر چقدر مقدار ویژه کوچکتر شود واریانس داده ها در راستای بردار ویژه متناظر با آن کمتر می شود.

بنابراین برای مثال اخیر اگر بتوانیم دستگاه مختصات را طوری تغییر دهیم که در راستای بردار ویژه های ماتریس کوواریانس قرار گیرد می توانیم کاهش بعد را انجام دهیم. (دستگاه مختصات جدید)

الگوریتم PCA این کار را انجام میدهد.

الگوریتم PCA

1- نرمالیزاسیون میانگین

μ=1mmi=1x(i)μ=1m∑i=1mx(i)

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

x(i)μx(i)−μ

از این به بعد منظور از x(i)x(i) ها همین مثال هایی است که میانگین از آنها کم شده

2- محاسبه ماتریس کوواریانس داده ها

Σ=1mmi=1x(i)(x(i))TΣ=1m∑i=1mx(i)(x(i))T

3- محاسبه مقدارویژه ها و بردار ویژه های ماتریس کوواریانس داده ها

  • در ادامه درباره محاسبه آنها مفصل بحث خواهد شد فعلا می توان فرض کرد با داشتن ماتریس کوواریانس داده ها با دستور زیر در متلب می توان آنها را بدست آورد.
  •  [U,S,V]=svd(Sigma);
  • ·         S: یک ماتریس قطری-diagonal- است که عناصر روی قطر اصلی آن مقدار ویژه های ماتریس کوواریانس-ΣΣ- می باشند. در ماتریس S مقدار ویژه های از بزرگ به کوچک بصورت مرتب روی قطر اصلی قرار گرفته اند.
  • U: ماتریسی که ستون های آن بردار ویژه های متناظر با هر مقدار ویژه در ماتریس S می باشد.

4- تبدیل از n بعد به k بعد

z(i)=UTreducex(i)z(i)=UreduceTx(i)

مثال

D={(1,1)T,(2,2)T,(3,3)T,(4,4)T}D={(1,1)T,(2,2)T,(3,3)T,(4,4)T}

μ=1mmi=1x(i)=(2.5,2.5)Tμ=1m∑i=1mx(i)=(2.5,2.5)T

Σ=1mmi=1x(i)(x(i))T=(1.251.251.251.25)Σ=1m∑i=1mx(i)(x(i))T=(1.251.251.251.25)

با دستور زیر در متلب ماتریس های S و U را بدست آورید

[U,S,V]=svd(Sigma);

S=(2.5000)S=(2.5000)

U=(.7071.7071.7071.7071)U=(−.7071−.7071−.7071.7071)

تبدیل از n=2 بعد به k=1 بعد

z(i)=UTreducex(i)z(i)=UreduceTx(i)

ستون اول U را برای تشکیل UreduceUreduce استفاده کنید.

Ureduce=(0.70710.7071)Ureduce=(−0.7071−0.7071)

نتیجه نهایی حاصل از تبدیل بصورت زیر خواهد شد:

Dreduce={2.1213,0.7071,0.7071,2.1213}Dreduce={2.1213,0.7071,−0.7071,−2.1213}

بعد از این تبدیل می توان در کاربرد مورد نظر داده های یک بعدی را بجای داده های دو بعدی اولیه استفاده کرد.

بازیابی

می توانیم داده های k بعدی را با فرمول زیر دوباره تبدیل به داده های n بعدی کنیم.

x(i)approx=Ureducez(i)+μxapprox(i)=Ureducez(i)+μ

با این رابطه به ازای هر بردار ورودی x(i)x(i) تخمینی با نام x(i)approxxapprox(i) بدست می آوریم. خطای ناشی از تصویر کردن داده ها با این تبدیل با فرمول زیر قابل محاسبه است:

projection error=1mmi=1∥∥x(i)x(i)approx∥∥2projection error=1m∑i=1m∥x(i)−xapprox(i)∥2

علامت ||..|| نشان دهنده ی نرم دوم یا همان فاصله اقلیدسی است. تصویر کردن داده ها با PCA باعث کمینه شدن این تابع خطا می شود. بنابراین می توان گفت PCA روی رویه ای k بعدی داده ها را تصویر می کند بطوری که مجموع مربعات فاصله ی نقاط از آن رویه (surface) کمینه می شود.

اگر از ماتریس U بجای UreduceUreduce در تبدیل از n بعد به k بعد استفاده کنیم، داده ها از یک فضای n بعدی به فضای k=n بعدی دیگری خواهند رفت و هیچ اطلاعاتی را از دست نمی دهیم. تنها یک تغییر مختصات روی داده ها انجام شده و می توان با فرمول زیر داده های اولیه را بازیابی کرد.

x(i)=Uz(i)+μx(i)=Uz(i)+μ

همچنین اگر کاهش بعد طوری صورت گرفته باشد که صد درصد واریانس داده ها را حفظ کند داده های بازیابی شده با نسخه ی اصلی برابر خواهند بود. در مورد مثال مطرح شده در قسمت قبل کاهش بعد به این صورت انجام شده یعنی با آنکه داده ها را از فضای دو بعدی به فضای یک بعدی بردیم اگر آنها را بازیابی کنیم هیچ اطلاعاتی از دست نرفته و مجموعه داده های اولیه D دوباره بدست خواهد آمد.

اما چگونه می توان فهمید در کاهش بعد از n بعد به k بعد چند درصد واریانس داده ها حفظ شده است؟  

انتخاب k

معمولا در کاهش بعد با روش PCA مهم تر از گزارش مقدار k آن است که بگوییم در کاهش بعد چند درصد واریانس داده ها حفظ شده است. یعنی باید k بگونه ای انتخاب شده باشد که مثلا بتوانیم بگوییم 95 درصد واریانس داده ها در کاهش بعد حفظ شده است.

بطور مثال برای حفظ 99 درصد واریانس داده ها k باید بگونه ای انتخاب شود که رابطه ی زیر صادق باشد:

projection errorvariations in the data0.01projection errorvariations in the data≤0.01

projection error=1mmi=1∥∥x(i)x(i)approx∥∥2projection error=1m∑i=1m∥x(i)−xapprox(i)∥2

variations in the data=1mmi=1∥∥x(i)∥∥2variations in the data=1m∑i=1m∥x(i)∥2

انتخاب های دیگر بجای 0.01 عبارتند از 0.1 و 0.05

پس اگر k را بگونه ای انتخاب کنیم که به ازای مقدار 0.05 رابطه بالا صادق باشد می توانیم بگوییم در کاهش بعد طوری k را انتخاب کردیم که 95 درصد واریانس داده ها حفظ می شود.

در عمل ممکن است بخواهیم به ازای مقادیر مختلف k الگوریتم PCA را اجرا کنیم و برای هر کدام از مقادیر k ببینیم چقدر از واریانس داده ها حفظ می شود. در این صورت محاسبه ی فرمول بالا زمانبر است. خوشبختانه فرمول راحت تری با استفاده از ماتریس S (ماتریس قطری مقدار ویژه ها) برای این کار وجود دارد که معادل با فرمول قبلی است:

1mmi=1∥∥x(i)x(i)approx∥∥21mmi=1∥∥x(i)∥∥2=1ki=1Siini=1Sii0.011m∑i=1m∥x(i)−xapprox(i)∥21m∑i=1m∥x(i)∥2=1−∑i=1kSii∑i=1nSii≤0.01

فقط نیاز است یک مرتبه ماتریس S حساب شود آنوقت می توانیم با این فرمول برای انتخاب های مختلف k واریانس حفظ شونده توسط داده ها را بسنجیم به عبارت دیگر لازم نیست برای هر انتخاب k کل محاسبات الگوریتم PCA را تکرار کنیم.

در قسمت بعدی به خواست خدا نکات بیشتری پیرامون این روش گفته خواهد شد از جمله اینکه کجا نباید از PCA استفاده کرد ونحوه ی محاسبه ی مقادیر ویژه و بردارهای ویژه چگونه است.

دانلود کد متلب استفاده از روش PCA

لینک دائمی:

http://ashkanabbasi.ir/?p=225

دیدگاه‌ها  

0 # فاطمه 1396-04-26 07:50
با سلام و احترام؛ ضمن سپاس از مقاله تون امكانش هست فايل اصلي را برام بفرستيد.
پاسخ دادن

نوشتن دیدگاه

تصویر امنیتی
تصویر امنیتی جدید

ارتباط با ما

  • گیلان - رشت - میدان حشمت - پارک علم و فناوری گیلان - طبقه دوم  - گروه توسعه اندیشه نوین 
  • موبایل : 09117586735 (مهندس ایوبی)
  • وب سایت متن کاوی: www.tmta.ir