VQ: Vector Quantization

principal component analysis )pca)

تحلیل مولفه‌های اصلی(pca)

قبل از وارد شدن به بحث اصلی  ، بهتر است با بعضی از مفاهیم آشنا شویم.

انواع تصویر:

یک تصویر به شیوه های مختلفی میتواند ثبت  شود:

1-    انالوگ

2-    رقمی (دیجیتالی) :هر پیکسل بیانگر یک مقدار خاصی از منطقه است. هرپیکسل دارای یک ارزش عددی است که بیانگر میزان تابندگی تصویر در آن نقطه است. به این نوع تصاویر، تصاویر رستری هم می‌گویند. تصاویر رستری دارای سطر و ستون میباشند.

3-    تصاویر وکتوری

4-    مقدارپیکسلی

پردازش تصویر : انجام یکسری فرایند به روی تصویر، که امروزه بیشتر به روی تصاویر دیجیتالی انجام می شود اما پردازش نوری و آنالوگ تصویر ، پردازش اصوات و .. هم وجود دارند.

در پردازش ،به تصویر به عنوان یک سیگنال ورودی دو بعدی نگاه میشود.

هدف از انجام پردازش: بهبود کیفیت ،مشخص شدن یک قسمتهایی از تصویر، تشخیص الگو و ... .

پردازش تصویر میتواند بصورت مرزی انجام شود (تشخیص لبه) و یا به روی محتویات .

 

 هدف از انجام پردازش: بهبود کیفیت ،مشخص شدن یک قسمتهایی از تصویر، تشخیص الگو و ... .

پردازش تصویر میتواند بصورت مرزی انجام شود (تشخیص لبه) و یا به روی محتویات .

تکنیک های پردازش تصویر:

ترکیبهای رنگی کاذب( composite  color    False)   

 تــصاویر نــسبتی  (Ration Image)

 آنــالیز اجــزاء اصــلی   (principal component Analysis)


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

استخراج ویژگی :  ( Feature Extraction)فرایندی است که در آن با انجام عملیاتی بر روی داده‌ها (به عنوان مثال،تصویر)، ویژگی‌های بارز و تعیین‌کننده آن مشخص و یافت می‌شود.

انتخاب ویژگی :انتخاب مناسبترین ویژگی(ویژگی) ها از میان ویژگی های استخراج شده.  این مرحله بسیار مهم می باشد و باید از روشی استفاده کرد که بهترین انتخاب را ارائه دهد.

طبقه بندی ویژگی: میتوانید پست مربوطه را مطالعه فرمایید.

به منظور انجام فرایندهای استخراج و انتخاب ویژگی به روی تصویری که در اختیار داریم روشهایی متعددی وجود دارد که باید بسته به معیارها، بهترین روش را انتخاب نمود تا در پی آن با سرعت و کیفیت بالاتری بهترین انتخاب و در نهایت بهترین نتیجه را داشت.

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

یکی از دلایل کاهش ابعاد اینست که برای یافتن جواب (ویژگی یا ویژِگی های مطلوب،) به وجود تمام ابعاد نیاز نیست.

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

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

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

از روشهای خطی میتوان به DFT، DWT، PCA و FA اشاره کرد.

از روشهای غیرخطی نیز میتوان به موارد زیر اشاره کرد:
Principal Curves
Self Organizing Maps 
Vector Quantization 
Genetic and Evolutionary Algorithms 
Regression

 

روشهای مبتنی بر انتخاب ویژگی :

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

  • بهترین ویژگی های فردی (Best Individual d Features)
  • جستجوی مستقیم ترتیبی (Sequential Forward Search – SFS)
  • جستجوی معکوس ترتیبی (Sequential Backward Search – SBS)
  • جستجوی افزودن l، حذف r یا (Plus r Minus l Search)
  • جستجوی مستقیم ترتیبی تعمیم یافته (Generalized Sequential Forward Search)
  • جستجوی معکوس ترتیبی تعمیم یافته (Generalized Sequential Backward Search)
  • جستجوی شناور (Floating Search)

 


PCA (Principal Component Analysis)   

 

درمواردی که بـا حجـم زیـادی از داده هـا سـر و کـار داریـم میتوان با استفاده از روشهای آماری متعددی، بـه کـاهش بعد و دسته بنـدی داده هـا پرداخـت ،یکی از روشهای کاربردی در این زمینه،PCA می باشد.

PCA روش آماری خطی است  که میتوان در زمینه های تشخیص الگو،پردازش تصویر،فشرده سازی تصویر و... از آن استفاده کرد.

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

 

روند کاهش ابعاد با PCA :

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

پس می توان بجای دو محور ،یک محور مانند y در نظر گرفت. (متغیر y1 بجای دو متغیر x1 و x2) . در سمت محور y2 داده زیادی وجود ندارد.

اگر محورهای x1 و x2 را به سمت  پراکندگی داده ها بچرخانیم به محور y1 و y2 می رسیم. بعبارتی دیگر، میتوان بجای متغیرهای x1 و x2 ، فقط متغیر y1  را در برای کاهش فضای مازاد و حتی کاهش بعد، در نظر گرفت. در ریاضی  برای چرخاندن و یا تغییر مقیاس -  Scaling محورها ،از ضرب ماتریسی استفاده می شود.

 Qیک نگاشت خطی است که از فضای x به فضای y میرسیم.

Q  و y هر دو فضایی دو بعدی هستند اما از یکسری ابعاد کم اهمیت تر صرفنظر شده است.


تعیین ماتریس  :



X  ماتریسی شامل اطلاعات می باشد و اعضای آن،مشاهدات.

T نماد عمودی بودن بردارهاست. X1,x2,.. برادارهای عمودی هستند.

 

می توان فرض کرد که میانگین یا امید ریاض x صفر است بعبارتی فرض میگیریم که داده ها حول محور مبدأ پراکنده شده اند.

E{x}=0

همانطور که گفته شد میخواهیم  با بدست آوردن ماتریس Q فضای x را به سمت فضای و یژگی (y) جابه جا کنیم.

 

M : تعداد ابعاد

درشکل یک، هرکدام از توپکها ،یک xi  (بردار)محسوب می شود.

در نگاشت ، میخواهیم یک بردار مترادفی برای هریک از xi ها در فضای y پیداکنیم

q1 ,q2 و... بردارهای عمودی هستند.

transform   :T 

 

X  ماتریسی شامل اطلاعات می باشد و اعضای آن،مشاهدات.

T نماد عمودی بودن بردارهاست.

X1,x2,.. برادارهای عمودی هستند.

 

می توان فرض کرد که میانگین یا امید ریاض x صفر است بعبارتی فرض میگیریم که داده ها حول محور مبدأ پراکنده شده اند.

E{x}=0

همانطور که گفته شد میخواهیم  با بدست آوزدن ماتریس Q فضای x را به سمت فضای ویژگی (y) جابه جا کنیم.



Yij  ،متغیر جدیدی است( در فضای جدید y ) مترادف با متغیرXi (در فضای x).

Y=QT*X

( Xi=(x1,x2,…,xn :ماتریس ورودی

    (  Y=(y1,y2,…,yn:ماتریس ویژگی

n :تعداد ورودی

در ابتدا فرض کردیم که E{x}=0، با این فرض متوجه می شویم که امید ریاضی (میانگین) برای جابه جایی به فضای ویژگی ها مناسب نیستند، لذا همانطور که در ابتدا اشاره شد برای کاهش ابعاد می توان یک محور در جهتی که پراکندگی داده ها بیشتر است (به سمت کواریانس ماکسیمم) در نظر گرفت.


واریانس :

واریانس معیاری است برای پراکندگی مجموعه داده ها است. واریانس مربع انحراف معیار است. فرمول کلی واریانس به صورت زیر می باشد. 


بدست آوردن واریانس بیشینه:

برای داشتن بهترین یا بیشترین واریانس باید،به دنبال یافتن بیشترین qj باشیم.کاهش ابعاد در راستای بیشترین پراکندگی یعنی به سمت بیشترین واریانس.

 

کوواریانس:

انحراف معیار و واریانس فقط بر روی یک بعد عمل می کنند.کوواریانس همیشه بین دو بعد اندازه گیری می شود.

اگر یک سری داده سه بعدی (X,Y,Z) موجود باشد می توان کوورایانس را بین دو بعدX,Y ،دو بعد X,Z و دو بعدY,Z حساب کرد.



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

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

ماتریس کواریانس:

 بردار ویژه و مقدار ویژه:

 قبلاگفتیم که در پی یافتن متغیری در جهت پراکندگی بیشتر یا همان واریانس بیشترهستیم تا بتوانیم متغیرهای اولیه (xi) را به روی متغیرهای جدید (yj) ها نگاشت کنیم.

در این بحث، مطمئنا،بردارهای زیادی می توانند وجود داشته باشند اما باید بهترین متغیر(بهترین محور) یعنی بردار ویژه را یافت تا بتوان بیشترین آنالیز و تفکیک پذیری را انجام داد. با توجه به شکل زیر y1 بهتر از y2 می باشد چون  بیشترین توزیع را در آن داریم.


محاسبه بردار ویژه و مقدار ویژه:

A یک ماتریس تبدیل محسوب میشود، لاندا  یک مقدار ویژه و X  یک بردار ویژه. یک ماتریس n×n میتواند دارایn   بردار ویژه باشد ،اما بردار ویژه ای مد نظر است که در واقع با ضرب  در ماتریس تبدیل ،فقط اندازه تغییر کند و راستای بردار بدون تغییر باقی بماند.

 

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

 تحلیل مولفه‌های اصلی در تعریف ریاضی یک تبدیل خطی متعامد است که داده را به دستگاه مختصات جدید می ‌برد به طوری که بزرگترین واریانس داده بر روی اولین محور مختصات، دومین بزرگترین واریانس برروی دومین محور مختصات قرار می‌گیرد و همین طور برای بقیه .تحلیل مولفه‌های اصلی می‌تواند برای کاهش ابعاد داده مورد استفاده قرار بگیرد، به این ترتیب مولفه‌هایی از مجموعه داده را که بیشترین تاثیر در واریانس را دارند حفظ می‌کند.برای ماتریس    XT  با میانگین تجربی صفر، که هر سطر یک مجموعه مشاهده و هر ستون داده‌های مربوط به یک شاخصه است، تحلیل مولفه‌های اصلی به صورت معادله شماره 1 تعریف می شود و ما در قسمت مربوطه  این فرمول را بصورت  معادله شماره 2 نشان دادیم.


 منابع:

1-تکنیک آنالیز اجزای اصلی  (PCA)،شهرام کبیر،  Twww.ECA.ir

2-بررسی روش های استخراج ویژگی های تصویر به منظور استفاده درکاربردهای تشخیص اشیا
محمدرضا محمودوند(دانشجوی کارشناسی ارشد دانشگاه صنعتی مالک اشتر)، مجتبی حسینی  
(استاد یار دانشگاه صنعتی مالک اشتر)،کد مقاله:0940-Com

 3-ارزیابی و مقایسه چهار روش کاهش بعد ویژگیها برای سیستم تشخیص نفوذ مبتنی بر ماشین بردار پشتیبان

حمید رضا شجاع مودب ،محمد مهدی همایونپور،چهارمین کنفرانس رمز انجمن ایران،1386

 4-معرفی و نحوه استفاده از فیلتر PCAدر متلب،محمد نحوی،کنفرانس مهندسی کامپیوتر و توسعه پایدار،1392

5-آنالیز اجزای اصلی (principal components analysis) در آمار

 6-تحلیل مؤلفه‌های اصلی(wikipedia)

7-محاسبه مقدار ویژه و بردار ویژه (wikipedia)

8-فیلم آموزشی تحلیل مولفه اساسی یا PCA در متلب - بخش 1

9-فیلم آموزشی جامع کاهش ابعاد یا Dimensionality Reduction

نظرات (0)
نام :
ایمیل : [پنهان میماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)