جزوه دوره یادگیری ماشین دکتر مهدیه سلیمانی - جلسه بیستم - ادامه روش PCA و شروع Clustering

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

محتوای این جلسه

در ابتدا ادامه بحث PCA رو خواهیم دید، مقایسه‌ای با روش LDA خواهیم داشت و روش SVD رو هم به صورت کلی بررسی خواهیم کرد. سپس به خوشه‌بندی (Clustering) خواهیم پرداخت.

مروری بر جلسه گذشته

به صورت کلی با روش PCA آشنا شدیم. آخرین بحثی که در جلسه گذشته مورد بررسی قرار دادیم این بود که اگر بخواهیم در فضا برداری را پیدا کنیم که داده‌ها روی آن تصویر شوند و بیشترین میزان واریانس را داشته باشد، آن بردار متناظر با برداری با بیش‌ترین مقدار ویژه ماتریس کواریانس داده‌ها است. در آخر هم یک مثال از تصویر افراد و نتیجه PCA را روی آن دیدیم.

ادامه مطالب

همونطور که در جلسه گذشته هم گفتیم، اگر مقادیر ویژه متناظر با بردارهای ویژه رو بدونیم و بدونیم که این مقادیر ویژه از یه جایی به بعد خیلی کوچیک می‌شن می‎‌تونیم اون‌هارو با خیال راحت کنار بذاریم و در یک فضایی با ابعاد پایین‌تر کارمون رو انجام بدیم.

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

این راهکار شبیه همون کرنل می‌مونه که در جلسات گذشته بررسی‌ش کردیم. حالا اگه بخوایم روابط PCA رو به صورت کرنل طور نشون بدیم باید چه کنیم؟ اول باید نشون بدیم که بردارهای ویژه (V) رو می‌تونیم به صورت ترکیب خطی نقاط بنویسیم. از طرفی ماتریس C رو هم باز می‌کنیم. حالا برای اینکه به فرم کرنل در بیاد نیاز داریم تا ضرب داخلی رو توش به وجود بیاریم. برای این کار کافیه طرفین رابطه زیر رو در یک XT ضرب کنیم. به این ترتیب میشه PCA رو به فرم کرنل بنویسیم.

این کار مثل این می‌مونه که انگار به یک فضای جدید رفتیم و اونجا داریم PCA می‌زنیم.

مقایسه PCA و LDA

روش PCA کاملا به‌صورت unsupervised هست. ممکنه گاهی این کار یک سری اطلاعات مفید رو از بین ببره. الان تو مثال پایین اگر PCA بزنیم تمام داده‌ها تو هم قاطی میشن. در حالیکه LDA به صورت supervised است و تو مثال پایین می‌تونه خیلی بهتر عمل کنه.

حالا وقتی می‌خوایم دسته‌بندی کنیم چرا اصلا از LDA استفاده نکنیم؟ PCA اینجا چه کاربردی برامون داره؟ LDA تو حالت دو کلاسه تمامی ابعاد رو به یک بعد می‌رسونه. ممکنه گاهی اوقات نخوایم از فضای 1000 بعدی به فضای یک بعدی برسیم. از طرفی ممکنه به اندازه کافی سمپل برچسب‌دار نداشته باشیم و این خودش هم محدودیت ایجاد می‌کنه.

یک سری روش‌ها هم وجود داره که میاد PCA و LDA رو ترکیب می‌کنه و ازشون باهم استفاده می‌کنه. یعنی وقتی که یه سری از داده‌ها برچسب دارن و یه سری‌شون ندارن میشه این کار رو کرد.

روش SVD

یک ماتریس مثل X رو در نظر بگیرید. می‌تونه حتی مربعی هم نباشه. این روش میاد ماتریس X رو به سه ماتریس دیگه میشکنه. ماتریسی که وسط هست (S) یک ماتریس قطریه. یعنی درایه‌های خارج از قطرش صفره. ماتریس U و ماتریس V ستون‌هاشون بردارهای عمود بر همه.

حالا این چه ربطی به PCA داره اصلا؟ تو روش PCAمیومدیم از ماتریس کواریانس که از روی داده‌ها به دست میومد استفاده می‌کردیم. روابط زیر رو در نظر بگیرید. از قبل هم می‌دونیم که قوانین زیر رو در مورد ماتریس‌ها داریم:

(AB)T = BT AT --> منظور ترانهاده است

ST = S --> اگر ماتریس قطری باشد

UTU = I --> اگر ستون‌هاش بر هم عمود باشن و نرمال باشه

اومدیم ماتریس C رو بدون در نظر گرفتن ضریب یک بر روی N به صورت زیر نوشتیم و بعد با استفاده از قوانین بالا و روابط زیر به شکل زیر در اومد. از طرفی دیگه برای XXT هم همین کار رو کردیم و به رابطه دیگه‌ای براش رسیدیم.

میشه نشون داد که مقادیر ویژه‌ای که برای XXT به‌دست میاد با مقادیر ویژه‌ای که برای XTX به‌دست میاد یکی میشه.

به صورت کلی اگه ماتریس X رو به صورت سه ماتریس مختلف USVT دیکامپوز کنیم، ماتریس U برابر میشه با برداهای ویژه ماتریس XXT و ماتریس V برابر میشه با بردارهای ویژه ماتریس XTX. تبدیل یافته نقاط در فضای جدید هم برابر میشه با US. محاسبه ماتریس U کار سختی نیست و چون ابعادش کمه به راحتی محاسبه میشه. به صورت کلی گاهی اوقات به جای محاسبه مستقیم PCA از روش‌های دیگه، مثل همین SVD استفاده میشه تا پیچیدگی محاسبات رو کم کنیم.

روش ICA

در کنار PCA روش دیگری به نام ICA وجود داره که به صورت کلی بررسی خواهیم کرد. این روش دنبال این هست که ابعادی رو پیدا کنه که اگه داده‌ها روشون مپ بشه، ابعاد از هم مستقل باشن. در روش PCA به دنبال ابعاد عمود برهم بودیم و با استقلال ابعاد کاری نداشتیم و کلا تلاشمون بر این بود که کورلیشن بین ابعاد رو تو PCA از بین ببریم.

اگه داده‌ها از توزیع گاوسی بیان، روش PCA شبیه روش ICA میشه. چون در این حالت ماتریس کواریانس به صورت قطری میشه و ابعاد باهم کورلیشن ندارن. عدم داشتن کورلیشن ابعاد در گاوسی، برابر با مستقل بودن ابعاد هست. ولی در حالت کلی همیشه این برقرار نیست و گاهی ممکنه به جای PCA از ICA استفاده کنیم.

مسئله Cocktail Party

فرض کنید در یک مهمانی تعدادی میکروفون داریم و به تعداد میکروفون‌ها شخص وجود دارد. صدای اشخاص فقط برای یک میکروفون نیست و میتونه رو چند میکروفون اثر بذاره. حالا صدای ضبط شده از طریق میکروفون‌هارو داریم و می‌خوایم سیگنال صوت افرادی که صحبت کردن رو استخراج کنیم. فرض کنید صداهایی که در میکروفون‌ها ضبط شده رو با X نشون بدیم. X1 یعنی صدای ضبط شده در میکروفون اول که خودش شامل ترکیب خطی صداهای افراد دیگه‌ای هست که تو بقیه میکروفون‌ها صحبت کردن. هر فرد صحبت‌کننده رو با S نشون میدیم و تعداد افراد n تا بوده. چیزایی که گفتیم رو میشه به شکل زیر نوشت:

X1 = α11 S1 + α12 S2 + ... + α1n Sn

X2 = α21 S1 + α22 S2 + ... + α2n Sn

Xn = αn1 S1 + αn2 S2 + ... + αnn Sn

رابطه بالا رو با ضرب ماتریس‌ها میشه به صورت X = AS نشون داد که A و S هر کدوم یک ماتریس هستن. ما صداهای ضبط شده (X)ها رو داریم، ولی نمی‌دونیم کدوم افراد (S)ها این صداهارو ساختن و می‌خوایم اون‌ها رو پیدا کنیم.

ما به دنبال تبدیلی روی S هستیم که Mutual Information رو کم کنه. چرا؟ چون با این کار می‌تونیم ابعاد رو نسبت بهم مستقل کنیم.

روش ICA کاهش ابعاد نداره. روش‌های مختلفی برای حل ICA وجود داره و توابع هزینه متفاوتی میشه براش در نظر گرفت.

خوشه‌بندی (Clustering)

تو کلاسترینگ به صورت کلی داده‌ها برچسب ندارن و هدف اینکه اون‌هارو گروه‌بندی کنیم. تا الان هرچی مثال دیده بودیم همشون به صورت کلسیفیکیشن بودن و برچسب داشتن.

اینجا که هیچ برچسبی نداریم با چه معیاری می‌تونیم داده‌هارو دسته‌بندی کنیم؟ به صورت کلی دنبال این هستیم که داده‌های داخل یک کلاس واریانس کم داشته باشن و خیلی بهم شبیه باشن، ولی داده‌های کلاس‌های مختلف واریانس زیاد داشته باشن و از هم کاملا متمایز باشن.

نگاه دومی هم وجود داره که میاد داده‌هارو جدا میکنه ولی نگاه اول محبوب‌تره. اینجوریه که اگه داده‌ها بوسیله یک مسیر بهم متصل باشن میاد اون‌هارو یک کلاس در نظر می‌گیره.

اهداف کلاسترینگ

اولین مورد کمپرس کردن دیتا هست. یه مثال ساده ببینیم. فرض کنید سه تا کلاس داریم برای داده‌ها و فضامون N بعدی هست. می‌تونیم به‌جای اینکه هردفعه N بعد داده رو جابجا کنیم، بیایم فقط شماره دسته اون داده رو بفرستیم و اینجوری خیلی راحت‌تر مشخص میشه که داده به کدوم دسته تعلق داره.

برای کاهش ابعاد فضا هم میشه از کلاسترینگ استفاده کرد.

مهم‌ترین هدفی که کلاسترینگ دنبال می‌کنه، کلاس‌بندی داده‌ها بدون برچسب هست.

کاربردها‌ی کلاسترینگ

یکی از کاربردهاش بازیابی اطلاعات هست.

مثلا سایت‌های خبری برای گروه‌بندی اخبار خیلی از این کار استفاده می‌کنن.

یکی دیگه از مثال‌هاش در سوشال مدیا هست. مثلا در توییتر افرادی که بهم متصل هستن یک شبکه رو تشکیل میدن. برای اینکه بتونیم افرادی که بهم متصل هستن رو شناسایی کنیم و گروه‌های بینشون رو در بیاریم، می‌تونیم از کلاسترینگ استفاده کنیم.

مثال دیگه بحث بیوانفورماتیک هست که برای دسته‌بندی ژن‌ها می‌تونه بهمون کمک کنه.

یک مثال دیگه از کاربردهاش برای بحث‌های مارکتینگی هست. مثلا فرض کنید می‌خوایم با توجه به مخاطب و گروه‌های مختلفی که داریم به یه سری افراد خاص پیامک بزنیم.

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

• سلسله مراتبی
• افرازی

در ادامه الگوریتم‌های کلاسترینگ رو بررسی خواهیم کرد.

روش K-means

صورت مسئله این طوره که N داده بدون برچسب داریم و قراره اون‌هارو کلاس‌بندی کنیم و تو K تا کلاس مختلف قرار بدیم. هر داده فقط به یک کلاس اساین میشه و هیچ کلاسی بدون داده نمی‌تونه باشه.

با روش Objective base و مبتنی بر تابع هدف شروع می‌کنیم. روش کلی K-means اینطوره که میاد از مجذور فاصله اقلیدسی استفاده می‌کنه و می‌خواد جوری دسته‌بندی رو انجام بده که هر داده به مرکز دسته نزدیک بشه. یعنی به ازای هر کلاس یک مرکز دسته داریم و قراره داده‌هایی که تو اون کلاس قرار بگیرن که فاصلشون از مرکز دسته کم هست.

روش‌های دیگه‌ای هم وجود دارن که تابع هدف‌های دیگه‌ای دارن ولی چیزی که اینجا الان مد نظر ما هست k-means هست.

پس الان یک سری داده بدون برچسب بعنوان ورودی داریم و قراره در خروجی این داده‌هارو به یک سری کلاس (K تا) که از هم جدا هستن و اشتراکی باهم ندارن اساین کنیم.

تابع هدفی که برای K-means در نظر گرفته شده جزو مسائل NP-Hard هست به جز دو حالت.

یک حالت زمانی هست که k=1 باشه. یک کلاستر داریم و میانگین کلی داده‌ها مرکز دسته میشه. حالت دوم حالتی هست که d=1 باشه. یعنی فضامون یک بعدی باشه. تو بقیه حالت‌ها این مسئله NP-Hard هست و ما نمی‌تونیم براش بهینه سراسری پیدا کنیم. پس با یک تابع هیوریستیک دنبال بهینه محلی می‌خوایم بگردیم.

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

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

شکل زیر مراحل مختلف این روش رو نشون میده.

بقیه مطالب مرتبط با این مبحث در جلسه آینده بررسی خواهد شد.

جمع‌بندی مطالب گفته شده

به صورت خیلی کلیات‌وار با روش ICA آشنا شدیم و با PCA مقایسه‌ش کردیم. کاربردهای کلاسترینگ و کلا هدف ازش رو دیدیم و یه دید کلی نسبت به الگوریتم K-means پیدا کردیم.

اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.

اسلایدهای این جلسه (بخش روش PCA)

اسلایدهای این جلسه (بخش Clustering)

ویدیو این جلسه

جزوه جلسه قبلی (جلسه نوزدهم)

جزوه جلسه بعدی (جلسه بیست‌ویکم)