Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

پیوست: چرا k-means با مشتق‌گیری تنها حل نمی‌شود — و چگونه به روند دوگامی شبیه EM می‌رسیم

English · فارسی

1. تابع هدف و دو نوع مجهول آن

بگذارید X∈Rm×nX\in\mathbb{R}^{m\times n} نقطه‌های داده xj∈Rmx_j\in\mathbb{R}^m را به‌صورت ستون در خود داشته باشد، M∈Rm×kM\in\mathbb{R}^{m\times k} مراکز خوشه‌ها μi\mu_i را به‌صورت ستون، و Z∈Rk×nZ\in\mathbb{R}^{k\times n} ماتریس تخصیص با

zij={1,if xj is assigned to cluster i,0,otherwise.z_{ij}= \begin{cases} 1, & \text{if } x_j \text{ is assigned to cluster } i,\\ 0, & \text{otherwise}. \end{cases}

تابع هدف k-means چنین است

J(M,Z)=∑i=1k∑j=1nzij∥xj−μi∥2=∥X−MZ∥F2,J(M,Z) = \sum_{i=1}^{k}\sum_{j=1}^{n} z_{ij}\|x_j-\mu_i\|^2 = \|X-MZ\|_F^2,

با قید

zij∈{0,1},∑i=1kzij=1for every j.z_{ij}\in\{0,1\}, \qquad \sum_{i=1}^{k} z_{ij}=1 \quad\text{for every }j.

پس k-means دو نوع کاملاً متفاوت مجهول دارد:

  1. مراکز MM متغیرهای پیوسته در Rm×k\mathbb{R}^{m\times k} هستند.

  2. تخصیص‌ها ZZ متغیرهای گسستهٔ دودوییِ یک‌داغ‌اند.

همین ساختار آمیختهٔ پیوسته–گسسته منبع ریاضی دشواری است. تابع هدف نسبت به MM مشتق‌پذیر است، ولی بخش تخصیص یک انتخاب ترکیبیاتی است.


2. مشتق‌گیری نسبت به مراکز کار می‌کند

اگر ماتریس تخصیص ZZ را ثابت بگیریم، J(M,Z)J(M,Z) تابعی درجه‌دو از MM است. با

J(M,Z)=tr⁡[(X−MZ)T(X−MZ)],J(M,Z) = \operatorname{tr}\bigl[(X-MZ)^T(X-MZ)\bigr],

به دست می‌آید

∂J∂M=2(MZZT−XZT).\frac{\partial J}{\partial M} = 2\left(MZZ^T-XZ^T\right).

صفر گذاشتن این مشتق می‌دهد

MZZT=XZT,MZZ^T = XZ^T,

و بنابراین

M=XZT(ZZT)−1.M = XZ^T(ZZ^T)^{-1}.

چون ZZTZZ^T قطری است و اندازهٔ خوشه‌ها روی قطرش می‌آید، این دقیقاً همان به‌روزرسانی مرکز است:

μi=1ni∑xj∈Cixj,ni=∣Ci∣.\mu_i = \frac{1}{n_i}\sum_{x_j\in C_i}x_j, \qquad n_i=|C_i|.

پس مشتق‌گیری برای MM یک جواب بستهٔ تمیز می‌دهد، به شرط آنکه ZZ از پیش معلوم باشد.


3. مشتق‌گیری نسبت به تخصیص‌ها مسئله را حل نمی‌کند

اکنون MM را ثابت بگیرید. آن‌گاه

J(M,Z)=∑j=1n∑i=1kzij∥xj−μi∥2.J(M,Z) = \sum_{j=1}^{n}\sum_{i=1}^{k} z_{ij}\|x_j-\mu_i\|^2.

برای MM ثابت، این تابع نسبت به درایه‌های zijz_{ij} خطی است. مشتق جزئی چنین است

∂J∂zij=∥xj−μi∥2.\frac{\partial J}{\partial z_{ij}} = \|x_j-\mu_i\|^2.

صفر گذاشتن این مشتق به

∥xj−μi∥2=0\|x_j-\mu_i\|^2=0

برای همهٔ i,ji,j نیاز دارد که در حالت کلی ناممکن است. مهم‌تر اینکه متغیرهای تخصیص با

zij∈{0,1},∑izij=1.z_{ij}\in\{0,1\}, \qquad \sum_i z_{ij}=1.

مقید شده‌اند.

چون تابع هدف نسبت به هر ستون ZZ خطی است، کمینه‌اش روی سیمپلکس در یک رأس رخ می‌دهد. برای هر نقطهٔ دادهٔ xjx_j تخصیص بهینه چنین است

zij=1fori=arg⁡min⁡i∥xj−μi∥2.z_{ij}=1 \quad\text{for}\quad i=\arg\min_i \|x_j-\mu_i\|^2.

این همان قاعدهٔ تخصیص به نزدیک‌ترین مرکز است. یک argmin گسسته است، نه جوابی که از صفر گذاشتن یک مشتق آمده باشد. عملگر arg⁡min⁡\arg\min به معنای معمول مشتق‌پذیر نیست و در نقطه‌هایی که دو مرکز به یک اندازه نزدیک‌اند حتی یکتا هم تعریف نمی‌شود.

اگر قیدهای دودویی را نادیده بگیریم و از عبارت ماتریسی نسبت به ZZ مشتق بگیریم، می‌رسیم به

∂∂Z∥X−MZ∥F2=−2MTX+2MTMZ.\frac{\partial}{\partial Z}\|X-MZ\|_F^2 = -2M^TX+2M^TMZ.

صفر گذاشتن آن می‌دهد

Z=(MTM)−1MTX.Z=(M^TM)^{-1}M^TX.

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


4. نگاه تجزیهٔ ماتریسی

همین دشواری در شکل تجزیهٔ ماتریسی هم دیده می‌شود. چون

J(M,Z)=∥X−MZ∥F2,J(M,Z)=\|X-MZ\|_F^2,

می‌توان MM را با فرمول مرکز بهینه حذف کرد. با جای‌گذاری

M=XZT(ZZT)−1M=XZ^T(ZZ^T)^{-1}

در تابع هدف، مسئلهٔ کاهش‌یافته به دست می‌آید

min⁡Z∥X−XZT(ZZT)−1Z∥F2\min_{Z} \left\| X-XZ^T(ZZ^T)^{-1}Z \right\|_F^2

با قید

zij∈{0,1},∑izij=1.z_{ij}\in\{0,1\}, \qquad \sum_i z_{ij}=1.

این نشان می‌دهد k-means یک مسئلهٔ تجزیهٔ ماتریسی رتبه پایین با قید است. ولی متغیر باقی‌مانده ZZ هنوز گسسته و یک‌داغ است. تابع هدف کاهش‌یافته غیرمحدب است و مجموعهٔ شدنی ترکیبیاتی. یافتن تخصیص بهینهٔ کلی در حالت عمومی NP-سخت است. پس هرچند عبارت ماتریسی جمع‌وجور است و به معنای تسهیل‌شده مشتق‌پذیر، مشتق‌گیری تنها خوشه‌بندی را تولید نمی‌کند.


5. جواب متناوب دوگامی

چون مسئله دو بلوک متغیر دارد، راهبرد ریاضی طبیعی کاهش مختصات بلوکی است که به آن کمینه‌سازی متناوب هم می‌گویند. یکی در میان یک بلوک را بهینه می‌کنیم و بلوک دیگر را ثابت نگه می‌داریم.

گام 1: گام تخصیص — MM را ثابت کن، ZZ را بهینه کن

با مراکز جاری MM، هر نقطه را به نزدیک‌ترین مرکز تخصیص بده:

zij={1,if i=arg⁡min⁡i′∥xj−μi′∥2,0,otherwise.z_{ij}= \begin{cases} 1, & \text{if } i=\arg\min_{i'} \|x_j-\mu_{i'}\|^2,\\ 0, & \text{otherwise}. \end{cases}

این همان بهینه‌سازی گسسته روی ZZ است: گام تخصیص سخت.

گام 2: گام به‌روزرسانی — ZZ را ثابت کن، MM را بهینه کن

با تخصیص جاری ZZ، هر مرکز را به میانگین نقطه‌های تخصیص‌یافته به آن به‌روز کن:

μi=1ni∑xj∈Cixj,ni=∣Ci∣.\mu_i = \frac{1}{n_i}\sum_{x_j\in C_i}x_j, \qquad n_i=|C_i|.

به‌طور معادل،

M=XZT(ZZT)−1.M=XZ^T(ZZ^T)^{-1}.

این همان بخش مشتق‌پذیر مسئله است.

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

J(Mt,Zt)≥J(Mt,Zt+1)≥J(Mt+1,Zt+1).J(M^t,Z^t) \ge J(M^t,Z^{t+1}) \ge J(M^{t+1},Z^{t+1}).

چون افرازهای nn نقطه به kk خوشه متناهی‌اند، روند در تعداد متناهی گام و در یک بهینهٔ محلی پایان می‌یابد.


6. چرا این روند شبیه EM است

ساختار دوگامی دقیقاً همان الگوریتم EM است:

در مدل مخلوط گاوسی با گاوسی‌های همسانگرد و واریانس برابر σ2I\sigma^2 I، گام E مسئولیت‌های نرم

rij∝exp⁡(−∥xj−μi∥22σ2).r_{ij} \propto \exp\left(-\frac{\|x_j-\mu_i\|^2}{2\sigma^2}\right).

را حساب می‌کند.

با σ2→0\sigma^2\to 0 این مسئولیت‌های نرم روی نزدیک‌ترین مرکز متمرکز می‌شوند و به تخصیص‌های یک‌داغی که k-means به کار می‌برد همگرا می‌شوند. در این معنای حدی، k-means یک EM با تخصیص سخت یا EM دسته‌بندی است.

پس دلیل ریاضی الگوریتم دوگامی یک انتخاب دلبخواه الگوریتمی نیست. مستقیماً از ساختار آمیختهٔ گسسته–پیوستهٔ تابع هدف برمی‌آید:

به کوتاهی: k-means با یک گام مشتق‌گیری حل نمی‌شود، چون متغیرهای تخصیص گسسته و ترکیبیاتی‌اند. مشتق‌گیری نیمهٔ مرکز مسئله را حل می‌کند؛ نیمهٔ تخصیص به یک argmin نزدیک‌ترین مرکز نیاز دارد. جمع کردن این دو جواب، دقیقاً همان روند k-means / EM سخت است.