باشگاه دانشجویی کارشناسی ارشد دانشگاه امیرکبیر

خلاصه درس تدریس یار خوشه بندی – ۹۲/۰۹/۱۶
فیشر دو کلاسه را جلسه قبل گفتیم

هم واریانس بین کلاسی و هم واریانس درون کلاسی را محاسبه می کردیم

از لاگرانژ استفاده نکردیم و مستقیم مشتق گرفتیم ( چون صورت و مخرج با هم ساده می شد)
که رابطه ۴٫۲۹ بدست آمد

برای خوشه بندی کافیست روی داده ها یک میانگین های تصویر شده را محاسبه کنیم
متوسط میانگین های تصویر شده

——————————————
فیشر چند کلاسه :

مثلا روی داده های IRIS که چهار بعدی هست که می خواهیم به دو یا سه بعد کاهش می دهیم

فیشر حالت چند کلاسه – تعداد ابعاد از D بعد به به بیشتر از یک بعد و کمتر از D بعد هست

می خواهیم ‘D ویژگی خطی بدست بیاوریم

اگر ۴ بعد داریم می خواهیم به دو بعد کاهش بدهیم یعنی ‘D مساوی ۲ هست دوبردار باید داشته باشیم w1 و w2 داریم

رابطه ۴٫۳۹

S Within جمع روی k کلاس واریانس درون کلاسی

یک ماتریس نسبت به دو کلاسه بیشتر داریم به اسم :
S total ماتریس کواریانس کل نمونه ها ( پراکندگی کل داده ها صرف نظر از کلاسشون )

ماتریس کواریانس کل را می توان به صورت جمع ماتریس درون کلاسی و ماتریس بین کلاسی نوشت

متوسط هر کلاس با متوسط همه کلاس ها S Bitween

Trace : اعضای قطر اصلی را با هم جمع کنیم

برای اینکه مساله فیشر را حل کنیم Sw , Sb را باید محاسبه کنیم
S^-1w*Sb

y1 , y2 در کنار هم بردار دو بعدی کاهش یافته می شود

نکته : Rank ماتریس ( درجه ماتریس )
می خواهیم ببینیم که حداکثر به چند بعد می توانیم کاهش بدهیم

هر ماتریس درون کلاسی Rank آن ۱ است
و k تا ماتریس را که با هم جمع می کنیم Rank آن K می شود

چون تمام متوسط ها به m ربط پبدا کردند Rank k-1 می شود

پس برای IRIS به دو بعد می توانیم کاهش دهیم چون ۳ تا کلاس دارد

——————————–
تمرین : فیشر ۳ کلاسه IRIS را انجام دهید
——————————–

تمرین مهم :
موضوع اول : K-means
Search کنید در موضوعات k-means که به آن VQ یا LBG هم می گویند
می خواهیم انواع حالت های آنرا بگویید ( weighted VQ )
مقاله های جدید را پیدا کنید
۱- انواع روش های VQ را بگویند
۲- روش دوم VQ را بهبود دادند
۳- روشهای VQ را Weighted را گفته اند
Wave Distance – چه تابع هایی را می توان به جای Distance اقلیدسی ، معیار فاصله جدید استفاده کرده

به جای تابع نرم اقلیدسی چه تابع های دیگری را گذاشته است
ترجیحا مقالاتی را پیدا کنید که Cost Function های جدید ارائه کرده اند

————————————
موضوع GMM

————————————
موضوع Kernel

————————————
موضوع Fisher

نمونه سوال امتحانی پایان ترم درس خوشه بندی و تصویر سازی – دکتر زارع – دانشگاه امیر کبیر -زمستان ۹۱

خلاصه درس تدریس یار خوشه بندی – آقای برادران – ۹۲/۰۹/۰۹
تمرین که تا پنج شنبه ۱۴/۰۹/۹۲ تمدید شد

Fisher Linear Discriminant
جدا ساز خطی فیشر

فیشر ۲ کلاسه (C1 , C2) داریم
D بعدی هستند و می خواهیم به فضای ۱ بعدی کاهش دهیم

y=W’*X
w محور خروجی فیشر هست
y داده های تصویر شده

در جدا سازی خطی به روش فیشر، نگاشت با دید کلاسه بندی انجام می شود و شامل ۲ مرحله است :
مرحله ۱ : نگاشت در فضای D بعدی به یک بعدی یا چند بعدی
مرحله ۲ : طبقه بندی بر اساس محور های جدید

در این روش نگاشت به صورتی انجام شود که کلاس ها در دستگاه مختصات جدید متمایز هستند

(m2-m1=w'(m2-m1

m2-m1 سمت چپ میانگین داده های تصویر شده هستند
m2-m1 سمت راست میانگین داده های اصلی هستند

چون نمی توانیم m2-m1 سمت راست را تغییر دهیم بایستی w را تغییر دهیم تا m2-m1 زیاد شود

برای اینکه فاصله بین کلاس ها بیشتر باشد

اگر واریاس را لحاظ کنیم :

پراکندکی بین دو کلاس زیاد شده
ولی پرکندگی داخل کلاس ها کم شده
که این از اهداف فیشر است

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

—————————–
– Bitween – Inter Class – ماتریس بین کلاسی Sb=(m2-m1)-(m2-m1)transpose
– Within – Intra Class ماتریس درون کلاسی

برای محاسبه w این را لحاظ می کنیم که با جهت w سر و کار داریم و نه اندازه اش

دانلود کلاس ضبط شده جلسه حضوری آقای برادران پنج شنبه ۹۲/۰۹/۰۷

جزوه روز پنج شنبه ۰۷/۰۹/۹۲ که خانم مهندس صحت زحمت کشیدند

خلاصه مباحث درس خوشه بندی – دکتر زارع – ۹۲/۰۹/۰۴

مبحث Kernel
و روش فیشر

نکته : یک فایل ورد یک صفحه ای Topic مقاله به همراه سال Journal بفرستید
که در موضوع کلاس باشید

تغییرات را با ماتریس کواریانس نشان می دادیم
با استفاده از تابع لاگرانژ انجام می دادیم

خلاصه PCA: اول ماتریس را Centralize می کردیم ماتریس S را می سازیم ، مقدار
ویژه و بردار ویژه را بدست می آوریم

میشه ثابت کرد اگر بخواهیم کمترین میزان Reconstruction را داشته باشیم
نگاشت تولید شده توسط PCA کمترین خطای بازیابی را می دهد
PCA یک روش Unsupervised هست
ولی روش های جدید Supervised آن هم آمده است
دقیقترین نمایش داده ها در فضای با بعد کمتر (مثل مپ کردن تصویر )
————————————–
Kernel Trick
افزایش بعد برای جدا سازی خطی

PCA را بر اساس Dot Product می خواهیم بنویسیم

کتاب Principal Component Analysis
—————————————–
بحث بعدی : fisher LDA کاهش بعد با در نظر گرفتن کلاس ها است

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

روش فیشر :

فرمولاسیون ماکزیمم واریانس

بحث PCA
و بحث Kernel

ورودی مساله : N تا داد ها ی D بعدی
یک زیر فضا را می خواهیم بدست بیاوریم که بعد داده های جدید از بعد داده های اصلی
کمتر باشد.

پراکندگی داده های تصویر شده حداگثر شود
Max ( Variance )
بردار U فقط جهتش مهم بود

برای تصویر داده روی بردار ، داده را در بردار ضرب می کنیم
اگر اندازه یک برداری بزرگ باشد ، داده را که ضرب میکنیم مقدار بزرگتری بدست می آید

اگر فضای تصویر M بعدی را در نظر بگیریم
تصویر خطی بهینه ای که برای آن واریانس داده های تصویر شده بیشینه شود.
————————————————
Kernel Method
ابزار خیلی پر کاربرد در مسایل غیر خطی
در مساله که داده ها در فضا قرار گرفته اند که با یک خط نمی توانیم جدا کنیم
مثل دو تا شکل ماه که ترکیب شده اند

از یک سری منحنی های غیر خطی باید استفاده کنیم که Kernel این امکان را فراهم
میکند

Kernel داده ها را به فضایی با بعد بالاتر تصویر می کند (فضای وِیژگی)

Motivations – Kernet Definiation – Mercer’s Theorem – Kernel Matrix – Kernel
Construction

یکسری Classifier خطی داریم ، یکسری Label داریم
کلاس ضربدر و کلاس دایره
شکل سمت چپ کلاس اولیه است

اگر خطی جدا می شد روش های SVM می شد استفاده کرد
به دنبال راهی می گردیم که به صورت خطی بتوانیم جدا کنیم

داده ها را از فضای ۲ بعدی به فضای ۳ بعدی تبدیل می کنیم

روش شکل تبدیل یافته سمت راست می توانیم classifier خطی بزنیم

فضای توسعه یافته را فی می گوییم

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

جلسه حضوری پنج شنبه ۷ آذر
مهلت تمرین تا جمعه ۸ آذر