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

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

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

ادامه جزییات روش k-means رو خواهیم دید و با دیگر روش‌های کلاسترینگ آشنا خواهیم شد.

آخرین مطلبی که در جلسه پیش ارائه شد الگوریتم k-means بود. به این صورت بود که اولش میومد تعدادی داده رندوم رو بعنوان شاخص یا مرکز دسته در نظر می‌گرفت. بعد تو هر مرحله داده‌های نزدیک به هر شاخص رو به اون کلاس تخصیص میداد و مجددا شاخص رو با توجه به داده‌های جدید آپدیت می‌کرد.

الگوریتم k-means درسته که گلوبال مینمم نداره ولی با همون روش‌های iterative به هم‌گرایی می‌رسه حتما. حالا تو نمودار پایین دو گامی که داخل حلقه داشتیم، اساین کردن داده‌ها به مرکز دسته‌هارو با رنگ ابی مشخص کرده و اپدیت کردن مرکز دسته‌هارو با رنگ قرمز. همون‌طور که نمودار هم داره نشون میده، هر دوی این مراحل باعث میشه که تابع هزینه کم بشه. از جایی که تابع هزینه ثابت می‌مونه و کم نمیشه به بعد، دیگه هیچوقت کاهش رخ نمیده. به این دلیل که دیگه میانگین عوض نمیشه و ثابت میشه و به یک مینمم محلی هم‌گرا میشه.

حالا در ادامه چندتا مثال ببینیم از اینکه اگر مینمم محلی پیدا شده بد باشه چی میشه. فرض کنید تو مرحله اول 8 تا داده داریم که به صورت زیر هستن.

تو مرحله بعدی نقاط ابی و قرمز رو بعنوان دو مرکز دسته رندوم در نظر می‌گیریم.

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

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

حالا چجوری جلوی گیر افتادن تو لوکال مینمم رو بگیریم؟

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

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

منتها این کار یه مشکلی داره. مثال زیر رو در نظر بگیرید. اومده یک مرکز دسته در نظر گرفته به صورت رندوم، بعدش اون سه نقطه آبی و سبز و قرمز رو بعنوان سه تا از دورترین داده‌ها در نظر گرفته. بعد که میاد دسته‌بندی می‌کنه به صورت شکل دوم میشه. حالا ایراد چیه؟ outlier ها!

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

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

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

حالا اگه حالتی باشه که بعد از مسئله کلاسترینگ اولیه، یک لایه دیگه داشته باشیم که بخوایم رو داده‌ها کلسیفیکیشن بزنیم، می‌تونیم مقدار k رو تنظیم کنیم. اینجوری که از cross-validation استفاده می‌کنیم و مقدار k رو می‌تونیم ست کنیم. ولی اگه حالتی باشه که بعد از کلاسترینگ اولیه دیگه هیچ لایه دیگه‌ای نداشته باشیم که به‌صورت سوپروایزد روش کاری بکنیم دیگه نمی‌تونیم مقدار k رو ست کنیم.

یک سری متدهای دیگه از جنس هیوریستیک هم وجود داره. بعضیاشون میان تابع هدف رو تغییر میدن و مثلا بهشون یک جمله اضافه می‌کنن که مقدار k توش هست. چرا اینجوری در نظر گرفته شده؟ بخاطر اینکه با زیاد کردن کلاسترها همواره تابع هزینه مقدارش کم و کمتر میشه و با این کار می‌خوایم بهینه‌ترین مقدار کلاستر رو پیدا کنیم به جای اینکه بیشترین تعداد کلاستر رو پیدا کنیم.

یه روش دیگه هم اینکه از روی نمودار تصمیم بگیریم که مقدار k چی باشه. مثلا تو نمودار بالا در یک نقطه تغییرات خیلی زیاد بوده و لی تو بقیه نقاط تغییرات محسوسی وجود نداشته. اون نقطه‌ای که تغییرات زیاد داره رو می‌تونیم بعنوان تعداد کلاسترها در نظر بگیریم. مثلا تو شکل بالا عدد 2 می‌تونه باشه.

نقاط قوت و ضعف k-means

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

تنظیم مقدار k چالشی هست. مینمم گلوبال نداره و ممکنه تو مینمم‌های محلی گیر بیفتیم. چون داره فاصله اقلیدسی در نظر می‌گیره ممکنه گاهی اوقات نتیجه خوب نباشه. اگر داده‌ها کم باشه تحت تاثیر داده‌های پرت می‌تونه قرار بگیره.

الگوریتم k-means حدودا 60 سال پیش معرفی شده و یکی از پر استفاده‌ترین الگوریتم‌ها تو بحث کلاسترینگ هست.

روش‌های خوشه‌بندی سلسله مراتبی

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

الگوریتم‌های سلسله‌ مراتبی دو دسته دارن. دسته Divisive و Agglomerative.

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

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

یک مثال ببینیم. خطوط عمودی تو نمودار پایین میزان شباهت رو نشون میده. هرچی خط بزرگ‌تر باشه شباهت داده‌های بین کلاسترها کمتره.

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

دیدگاه Single-link میاد فاصله دو کلاستر رو از روی دو تا داده نزدیک به هم حساب میکنه. یعنی اینکه نزدیک‌ترین نقاط هر کلاستر بهم رو در نظر میگیره. پل بین کلاسترهارو به‌دست میاره. دیدگاه Complete-link دقیقا برعکس دیدگاه اول هست و میاد دورترین نقاط رو در هر کلاستر فاصله‌ش رو حساب می‌کنه. روش Ward's میاد از فاصله مرکز دسته‌ها استفاده می‌کنه. دیدگاه Average-link میاد دو به دو همه نقاط رو فاصله‌ش رو حساب می‌کنه و بینشون میانگین میگیره. حالا در ادامه هر دیدگاه به صورت دقیق‌تر بررسی خواهیم کرد.

دیدگاه Single-link

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

الان تو شکل پایین اول 1 و 4 رو مرج کرده، بعد 5 و 6 رو. تو گام سوم میاد 7 رو با 5 و 6 مرج میکنه. چرا؟ چون 7 به 5 نزدیک‌تره تا 2 به 6.

دیدگاه Complete-link

این دیدگاه تمایل داره که قطر کلاسترها رو به نحوی کم کنه و داده‌ها تو هر کلاستر متراکم‌تر میشن.

حالا همون مثال بالا رو برای این مورد هم بررسی کنیم. بعد از اینکه 5 و 6 رو با داده 7 مرج میکنه، برخلاف روش قبلی میاد 5 و 6 و 7 رو به جای مرج کردن با 2 و 3، با 1 و 4 مرج میکنه.

روش Ward's

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

پیچیدگی روش‌های HAC

در گام اول فاصله هر زوج کلاسترهارو لازم داریم که باعث میشه از اردر N به‌توان دو باشه. حالا به صورت کلی N-2 بار اگه بخوایم مرج کردن رو انجام بدیم اردر کلی (N-2) × N^2 میشه که در نهایت میشه مکعب N. میشه با پیاده‌سازی بهینه این اردر رو به N^2 در logN رسوند.

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

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

مقایسه روش‌های سلسله مراتبی و k-means

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

دیدگاه احتمالاتی مسئله کلاسترینگ

برای این کار در ابتدا نیاز به تعریف مدل‌های مخلوط داریم. فرض کنید یک توزیعی از متغیرهای تصادفی داریم و می‌خوایم با استفاده از یک توزیع گاوسی مدل‌سازی رو انجام ندیم. چرا؟ چون مسائل کلاسترینگ معمولا بیشتر از یک مُد دارن و با توزیع‌های تک قله‌ای نمی‌تونیم مدلشون کنیم. حالا پس به‌جای اینکه با یک توزیع گاوسی مدل کنیم، با جمع وزن‌دار چند تا گاوسی مدل‌سازی رو انجام میدیم. در صورتی که جمع وزن‌ها یک بشه، در نهایت با جمع گاوسی‌ها به یک گاوسی واحد می‌رسیم. تو معادله پایین P(M) وزن گاوسی‌ها و عبارت دوم خود گاوسی‌ها را مشخص می‌کند. پارامتر تتا در فضای یک بعدی میانگین گاوسی را مشخص می‌کند و در فضای چند بعدی می‌تواند مشخص‌کننده موارد دیگری مثل ماتریس کواریانس باشد.

اگه عبارت بالا رو ساده‌تر بنویسیم به فرم پایین در میاد. در این مسئله به دنبال پیدا کردن μ و Σ و π هستیم. وزن‌ گاوسی‌ها چی باشه و کجا قرار بگیره.

برای حل مسئله می‌تونیم از maximum likelihood استفاده کنیم و بعد نسبت به هر پارامتر مشتق بگیریم و برابر با 0 قرار بدیم.

اما پیدا کردن جواب به راحتی امکان پذیر نیست و پس از حل مسئله به مقادیر زیر خواهیم رسید. مشکل اینکه هر پارامتر برحسب خودش و پارامترهای دیگه به دست میاد و خیلی سخت میشه برامون که بخوایم به جواب درست برسیم.

الگوریتم EM

راهکاری که وجود داره اینکه بیایم این مسئله رو به طریق دیگه‌ای حل کنیم. فرض کنید الگوریتم زیر رو داریم. تو الگوریتم زیر گاما نشون دهنده میزان تعلق داده به کلاستر هست. کلیات کار به این صورته که اولش بعد از یک مقدار دهی اولیه و محاسبه گاما، در یک حلقه هر دفعه مقدار μ و Σ و π حساب میشه. این حلقه انقدر تکرار میشه تا به همگرایی برسه. یعنی به جایی برسه که از اونجا به بعد دیگه تغییراتی در مقدار مقادیر بوجود نیاد.

این الگوریتم چه شباهت‌هایی به k-means داره؟ از نظر شهودی تنها فرقش اینکه میاد میزان تعلق داده‌ها به هر کلاستر رو حساب میکنه که یه عدد بین 0 تا 1 هست. الگوریتم k-means به این صورت بود که داده‌ها یا به یک کلاستر تعلق داشتن یا نداشتن. ولی اینجا یک پارامتر عضویت داره که مشخص میکنه هر داده به چه میزان به هر کلاستر متعلق هست.

در ادامه یک مثال از این الگوریتم ببینیم. می‌خوایم از الگوریتم EM استفاده کنیم تا داده‌هارو دسته‌بندی کنیم. فرض کنید الگوریتم بالا رو روش اجرا کردیم. حالا چجوری داده‌هارو به هر کلاستر اساین کنیم؟ هر داده با یک احتمالی به هر کلاستر اساین شده بود. دو تا کار می‌تونیم انجام بدیم. یا به همین صورت بذاریم بمونه، یا اینکه بین اعداد ممبرشیپ‌ها ماکسیمم بگیریم و بعد به کلاستری که ممبرشیپش بیشترین هست اساین کنیم. فرض کنید 3 تا کلاستر داریم. عضویت داده x به این سه تا کلاستر به ترتیب 0.6 و 0.3 و 0.1 هست. با روش دوم داده x به کلاستر اول اساین میشه و با روش دوم به همین صورت باقی می‌مونه.

ادامه مثال در جلسه بعدی ارائه خواهد شد.

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

با روش‌های خوشه‌بندی سلسله مراتبی آشنا شدیم و نقاط قوت و ضعف k-means رو دیدیم. در نهایت مسئله کلاسترینگ رو به صورت کلی با دیدگاه احتمالاتی بررسی کردیم و الگوریتم EM رو دیدیم.

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

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

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

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

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