پیوست: چرا k-means با مشتقگیری تنها حل نمیشود — و چگونه به روند دوگامی شبیه EM میرسیم
1. تابع هدف و دو نوع مجهول آن¶
بگذارید نقطههای داده را بهصورت ستون در خود داشته باشد، مراکز خوشهها را بهصورت ستون، و ماتریس تخصیص با
تابع هدف k-means چنین است
با قید
پس k-means دو نوع کاملاً متفاوت مجهول دارد:
مراکز متغیرهای پیوسته در هستند.
تخصیصها متغیرهای گسستهٔ دودوییِ یکداغاند.
همین ساختار آمیختهٔ پیوسته–گسسته منبع ریاضی دشواری است. تابع هدف نسبت به مشتقپذیر است، ولی بخش تخصیص یک انتخاب ترکیبیاتی است.
2. مشتقگیری نسبت به مراکز کار میکند¶
اگر ماتریس تخصیص را ثابت بگیریم، تابعی درجهدو از است. با
به دست میآید
صفر گذاشتن این مشتق میدهد
و بنابراین
چون قطری است و اندازهٔ خوشهها روی قطرش میآید، این دقیقاً همان بهروزرسانی مرکز است:
پس مشتقگیری برای یک جواب بستهٔ تمیز میدهد، به شرط آنکه از پیش معلوم باشد.
3. مشتقگیری نسبت به تخصیصها مسئله را حل نمیکند¶
اکنون را ثابت بگیرید. آنگاه
برای ثابت، این تابع نسبت به درایههای خطی است. مشتق جزئی چنین است
صفر گذاشتن این مشتق به
برای همهٔ نیاز دارد که در حالت کلی ناممکن است. مهمتر اینکه متغیرهای تخصیص با
مقید شدهاند.
چون تابع هدف نسبت به هر ستون خطی است، کمینهاش روی سیمپلکس در یک رأس رخ میدهد. برای هر نقطهٔ دادهٔ تخصیص بهینه چنین است
این همان قاعدهٔ تخصیص به نزدیکترین مرکز است. یک argmin گسسته است، نه جوابی که از صفر گذاشتن یک مشتق آمده باشد. عملگر به معنای معمول مشتقپذیر نیست و در نقطههایی که دو مرکز به یک اندازه نزدیکاند حتی یکتا هم تعریف نمیشود.
اگر قیدهای دودویی را نادیده بگیریم و از عبارت ماتریسی نسبت به مشتق بگیریم، میرسیم به
صفر گذاشتن آن میدهد
این یک جواب پیوستهٔ کمترین مربعات است. در حالت کلی دودویی نیست، ستونهایش به یک جمع نمیشوند و خوشهبندی معتبری را نشان نمیدهد. پس مشتقگیری سادهلوحانه از ماتریس تخصیص، یک مسئلهٔ رگرسیون تسهیلشده را حل میکند، نه k-means را.
4. نگاه تجزیهٔ ماتریسی¶
همین دشواری در شکل تجزیهٔ ماتریسی هم دیده میشود. چون
میتوان را با فرمول مرکز بهینه حذف کرد. با جایگذاری
در تابع هدف، مسئلهٔ کاهشیافته به دست میآید
با قید
این نشان میدهد k-means یک مسئلهٔ تجزیهٔ ماتریسی رتبه پایین با قید است. ولی متغیر باقیمانده هنوز گسسته و یکداغ است. تابع هدف کاهشیافته غیرمحدب است و مجموعهٔ شدنی ترکیبیاتی. یافتن تخصیص بهینهٔ کلی در حالت عمومی NP-سخت است. پس هرچند عبارت ماتریسی جمعوجور است و به معنای تسهیلشده مشتقپذیر، مشتقگیری تنها خوشهبندی را تولید نمیکند.
5. جواب متناوب دوگامی¶
چون مسئله دو بلوک متغیر دارد، راهبرد ریاضی طبیعی کاهش مختصات بلوکی است که به آن کمینهسازی متناوب هم میگویند. یکی در میان یک بلوک را بهینه میکنیم و بلوک دیگر را ثابت نگه میداریم.
گام 1: گام تخصیص — را ثابت کن، را بهینه کن¶
با مراکز جاری ، هر نقطه را به نزدیکترین مرکز تخصیص بده:
این همان بهینهسازی گسسته روی است: گام تخصیص سخت.
گام 2: گام بهروزرسانی — را ثابت کن، را بهینه کن¶
با تخصیص جاری ، هر مرکز را به میانگین نقطههای تخصیصیافته به آن بهروز کن:
بهطور معادل،
این همان بخش مشتقپذیر مسئله است.
الگوریتم این دو گام را تا وقتی تخصیصها عوض نشوند یا تغییر تابع هدف زیر یک تحمل برود تکرار میکند. هیچ گامی نمیتواند تابع هدف را زیاد کند:
چون افرازهای نقطه به خوشه متناهیاند، روند در تعداد متناهی گام و در یک بهینهٔ محلی پایان مییابد.
6. چرا این روند شبیه EM است¶
ساختار دوگامی دقیقاً همان الگوریتم EM است:
گام تخصیص مانند گام E است: عضویت خوشهٔ پنهان هر نقطه را با توجه به پارامترهای جاری مدل استنتاج میکند.
گام بهروزرسانی مرکز مانند گام M است: پارامترهای مدل را با توجه به تخصیصهای استنتاجشدهٔ جاری بهروز میکند.
در مدل مخلوط گاوسی با گاوسیهای همسانگرد و واریانس برابر ، گام E مسئولیتهای نرم
را حساب میکند.
با این مسئولیتهای نرم روی نزدیکترین مرکز متمرکز میشوند و به تخصیصهای یکداغی که k-means به کار میبرد همگرا میشوند. در این معنای حدی، k-means یک EM با تخصیص سخت یا EM دستهبندی است.
پس دلیل ریاضی الگوریتم دوگامی یک انتخاب دلبخواه الگوریتمی نیست. مستقیماً از ساختار آمیختهٔ گسسته–پیوستهٔ تابع هدف برمیآید:
مشتقگیری، مراکز بهینه را برای تخصیص ثابت میدهد؛
بهینهسازی گسسته، تخصیصهای بهینه را برای مراکز ثابت میدهد؛
تناوب میان این دو، الگوریتمی یکنوا و شبیه EM میسازد.
به کوتاهی: k-means با یک گام مشتقگیری حل نمیشود، چون متغیرهای تخصیص گسسته و ترکیبیاتیاند. مشتقگیری نیمهٔ مرکز مسئله را حل میکند؛ نیمهٔ تخصیص به یک argmin نزدیکترین مرکز نیاز دارد. جمع کردن این دو جواب، دقیقاً همان روند k-means / EM سخت است.