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.

مدل‌های مخلوط گاوسی، بخش 2

English · فارسی
English · فارسی

مطالب این بخش از فصل 13 کتاب Data Mining and Machine Learning نوشتهٔ محمد ج. زکی و واگنر مِیرا جونیور (2020) گرفته شده است Zaki & Meira (2020).

الگوریتم K-Means: مرور

تابع امتیاز مجموع مربع خطا چنین تعریف می‌شود

SSE(C)=∑i=1k∑xj∈Ci∥xj−μi∥2SSE(\mathcal{C}) = \sum_{i=1}^{k}\sum_{\mathbf{x}_{j} \in C_{i}}\|\mathbf{x}_{j}-\mathbf{\mu}_i\|^2

هدف یافتن خوشه‌بندی‌ای است که امتیاز SSE را کمینه کند:

C∗=arg⁡min⁡C{SSE(C)}\mathcal{C}^* = \arg \min_{\mathcal{C}} \{ SSE(\mathcal{C}) \}

K-means رویکردی تکراری و حریصانه برای یافتن خوشه‌بندی‌ای دارد که تابع هدف SSE را کمینه کند. از این‌رو می‌تواند به بهینهٔ محلی برسد، نه خوشه‌بندی بهینهٔ کلی.


الگوریتم K-Means: گام‌ها

K-means میانگین خوشه‌ها را با تولید تصادفی kk نقطه در فضای داده مقداردهی می‌کند. هر تکرار دو گام دارد:

  1. تخصیص خوشه: هر نقطهٔ xj∈D\mathbf{x}_{j} \in \mathbf{D} به نزدیک‌ترین میانگین تخصیص می‌یابد و خوشه‌بندی‌ای می‌سازد که در آن هر خوشهٔ CiC_i نقطه‌های نزدیک‌تر به μi\mathbf{\mu}_i را دارد:

    i∗=arg⁡min⁡i=1k{∥xj−μi∥2}i^* = \arg \min_{i=1}^k \Bigl\{\|\mathbf{x}_{j} - \mathbf{\mu}_i\|^2\Bigr\}
  2. به‌روزرسانی مرکز: مقدارهای میانگین تازه برای هر خوشه از نقطه‌های CiC_i حساب می‌شود.

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


الگوریتم K-Means


خوشه‌بندی با امید-بیشینه‌سازی

XaX_a متغیر تصادفی متناظر با صفت aaام باشد. X=(X1,X2,…,Xd)\mathbf{X} = (X_1, X_2, \dots, X_d) متغیر تصادفی برداری روی dd صفت باشد و xj\mathbf{x}_{j} نمونه‌ای داده از X\mathbf{X}.

فرض می‌کنیم هر خوشهٔ CiC_i با توزیعی نرمال چندمتغیره مشخص می‌شود:

fi(x)=f(x∣μi,Σi)=1(2π)d2∣Σi∣12exp⁡{−(x−μi)TΣi−1(x−μi)2}f_i(\mathbf{x}) = f(\mathbf{x}|\mathbf{\mu}_i,\mathbf{\Sigma}_i) = \frac{1}{(2\pi)^\frac{d}{2}|\mathbf{\Sigma}_i|^\frac{1}{2}} \exp\left\{-\frac{(\mathbf{x}-\mathbf{\mu}_{i})^{T} \mathbf{\Sigma}_i^{-1} (\mathbf{x}-\mathbf{\mu}_{i})}{2}\right\}

که μi∈Rd\mathbf{\mu}_i \in \mathbb{R}^d میانگین خوشه و Σi∈Rd×d\mathbf{\Sigma}_i \in \mathbb{R}^{d \times d} ماتریس کوواریانس است.

تابع چگالی احتمال X\mathbf{X} به‌صورت یک مدل مخلوط گاوسی روی همهٔ kk خوشه داده می‌شود:

f(x)=∑i=1kfi(x)P(Ci)=∑i=1kf(x∣μi,Σi)P(Ci)f(\mathbf{x}) = \sum_{i=1}^k f_i(\mathbf{x}) P(C_i) = \sum_{i=1}^k f(\mathbf{x} \mid \mathbf{\mu}_i, \mathbf{\Sigma}_i) P(C_i)

که احتمال‌های پیشین P(Ci)P(C_i) را پارامترهای مخلوط می‌نامند و باید شرط زیر را برآورده کنند:

∑i=1kP(Ci)=1\sum_{i=1}^k P(C_i) = 1

برآورد بیشترین درست‌نمایی

مجموعهٔ همهٔ پارامترهای مدل را به‌صورت فشرده چنین می‌نویسیم:

θ={μ1,Σ1,P(C1),…,μk,Σk,P(Ck)}\mathbf{\theta} = \left\{\mathbf{\mu}_1,\mathbf{\Sigma}_1,P(C_1), \dots, \mathbf{\mu}_k, \mathbf{\Sigma}_k, P(C_k)\right\}

با داشتن مجموعه‌دادهٔ D\mathbf{D}، درست‌نمایی θ\mathbf{\theta} چنین است:

P(D∣θ)=∏j=1nf(xj)P(\mathbf{D} | \mathbf{\theta}) = \prod_{j=1}^n f(\mathbf{x}_{j})

MLE پارامترهای θ\mathbf{\theta} را چنان برمی‌گزیند که درست‌نمایی را بیشینه کنند:

θ∗=arg⁡max⁡θ{ln⁡P(D∣θ)}\mathbf{\theta}^* = \arg\max_{\mathbf{\theta}} \{\ln P(\mathbf{D} | \mathbf{\theta})\}

که تابع لگاریتم درست‌نمایی چنین است:

ln⁡P(D∣θ)=∑j=1nln⁡f(xj)=∑j=1nln⁡(∑i=1kf(xj∣μi,Σi)P(Ci))\ln P(\mathbf{D} | \mathbf{\theta}) = \sum_{j=1}^n \ln f(\mathbf{x}_{j}) = \sum_{j=1}^n \ln \biggl( \sum_{i=1}^k f(\mathbf{x}_{j} | \mathbf{\mu}_i, \mathbf{\Sigma}_i)P(C_i)\biggr)

بیشینه کردن لگاریتم درست‌نمایی با امید-بیشینه‌سازی (EM)

بیشینه کردن مستقیم لگاریتم درست‌نمایی روی θ\mathbf{\theta} دشوار است چون جمع درون لگاریتم هست:

ln⁡P(D∣θ)=∑j=1nln⁡(∑i=1kf(xj∣μi,Σi)P(Ci))\ln P(\mathbf{D} | \mathbf{\theta}) = \sum_{j=1}^n \ln \left( \sum_{i=1}^k f(\mathbf{x}_{j} | \mathbf{\mu}_i, \mathbf{\Sigma}_i) P(C_i) \right)

اگر تابع درست‌نمایی فقط یک گاوسی تنها داشت، مشتق‌گیری مستقیم سرراست بود. ولی در مدل مخلوط گاوسی، حضور چند گاوسی درون جمع مشتق‌گیری را پیچیده می‌کند. چون هر نقطهٔ دادهٔ xj\mathbf{x}_j به‌طور قطع به یک خوشه تعلق ندارد و به‌جای آن احتمالی برای تعلق به چند خوشه دارد، حل تحلیلی پارامترها دشوار است.

EM چگونه کمک می‌کند؟

امید-بیشینه‌سازی رویکردی ساخت‌یافته برای بیشینه کردن غیرمستقیم درست‌نمایی می‌دهد، با وارد کردن متغیرهای پنهان — تخصیص‌های خوشه wij=P(Ci∣xj)w_{ij} = P(C_i | \mathbf{x}_j). گام امید این احتمال‌ها را حساب می‌کند و عملاً عضویت‌های پنهان را برآورد می‌کند، و گام بیشینه‌سازی پارامترها را با این وزن‌ها به‌روز می‌کند.

با تکرار میان این گام‌ها، EM از پیچیدگی مشتق‌گیری مستقیم عبارت لگاریتمِ جمعِ تودرتو دوری می‌کند و برآورد پارامترها را شدنی می‌سازد.


امید-بیشینه‌سازی برای مدل‌های مخلوط گاوسی

حالت یک‌بعدی: خوشه‌بندی نرمال تک‌متغیره

D\mathbf{D} شامل یک صفت XX باشد که هر نقطهٔ xj∈Rx_{j} \in \mathbb{R} نمونه‌ای تصادفی از XX است. مدل مخلوط برای هر خوشه از توزیع‌های نرمال تک‌متغیره استفاده می‌کند:

fi(x)=f(x∣μi,σi2)=12πσiexp⁡{−(x−μi)22σi2}f_i(x) = f(x | \mu_i, \sigma_i^2) = \frac{1}{\sqrt{2\pi}\sigma_i} \exp \left\{-\frac{(x - \mu_i)^2}{2\sigma_i^2} \right\}

که پارامترهای خوشه شامل μi\mu_{i} (میانگین)، σi2\sigma_{i}^2 (واریانس) و P(Ci)P(C_i) (احتمال پیشین) است.

مقداردهی اولیه

هر خوشهٔ CiC_i (برای i=1,2,…,ki = 1, 2, \dots, k) به‌طور تصادفی با پارامترهای μi\mu_{i}، σi2\sigma_{i}^2 و P(Ci)P(C_i) مقداردهی می‌شود.

گام امید

با میانگین μi\mu_i، واریانس σi2\sigma_i^2 و احتمال پیشین P(Ci)P(C_i) هر خوشه، احتمال پسین خوشه با قضیهٔ بیز حساب می‌شود:

wij=P(Ci∣xj)=f(xj∣μi,σi2)⋅P(Ci)∑a=1kf(xj∣μa,σa2)⋅P(Ca)w_{ij} = P(C_{i}|x_{j}) = \frac{f(x_{j}|\mu_i,\sigma_i^2) \cdot P(C_{i})} {\sum_{a=1}^k f(x_{j} |\mu_a, \sigma_a^2) \cdot P(C_{a})}

گام بیشینه‌سازی

با wij w_{ij} ، پارامترهای به‌روزشدهٔ خوشه چنین حساب می‌شوند:

  • به‌روزرسانی میانگین (میانگین وزنی نقطه‌ها):

    μi=∑j=1nwij⋅xj∑j=1nwij\mu_{i} = \frac{\sum_{j=1}^n w_{ij} \cdot x_{j}} {\sum_{j=1}^n w_{ij}}
  • به‌روزرسانی واریانس (واریانس وزنی نقطه‌ها):

    σi2=∑j=1nwij(xj−μi)2∑j=1nwij\sigma_{i}^{2} = \frac{\sum_{j=1}^n w_{ij}(x_{j}-\mu_{i})^2} {\sum_{j=1}^n w_{ij}}
  • به‌روزرسانی احتمال پیشین (کسر وزن‌هایی که به خوشه سهم می‌دهند):

    P(Ci)=∑j=1nwijnP(C_{i}) = \frac{\sum_{j=1}^n w_{ij}}{n}

حالت چندمتغیره: مدل مخلوط گاوسی با کوواریانس کامل

در حالت چندمتغیره، هر خوشهٔ CiC_i با توزیعی نرمال چندمتغیره مدل می‌شود و از حالت یک‌بعدی فراتر می‌رود:

fi(x)=f(x∣μi,Σi)=1(2π)d2∣Σi∣12exp⁡{−(x−μi)TΣi−1(x−μi)2}f_i(\mathbf{x}) = f(\mathbf{x}|\mathbf{\mu}_i,\mathbf{\Sigma}_i) = \frac{1}{(2\pi)^\frac{d}{2}|\mathbf{\Sigma}_i|^\frac{1}{2}} \exp\left\{-\frac{(\mathbf{x}-\mathbf{\mu}_{i})^{T} \mathbf{\Sigma}_i^{-1} (\mathbf{x}-\mathbf{\mu}_{i})}{2}\right\}

که μi∈Rd\mathbf{\mu}_i \in \mathbb{R}^d میانگین خوشه و Σi∈Rd×d\mathbf{\Sigma}_i \in \mathbb{R}^{d \times d} ماتریس کوواریانس است.

گام امید (چندمتغیره)

مانند حالت تک‌متغیره، احتمال پسین خوشه با قضیهٔ بیز حساب می‌شود:

wij=P(Ci∣xj)=fi(xj)⋅P(Ci)∑a=1kfa(xj)⋅P(Ca)w_{ij} = P(C_i | \mathbf{x}_{j}) = \frac{f_i(\mathbf{x}_{j}) \cdot P(C_{i})} {\sum_{a=1}^k f_a(\mathbf{x}_{j}) \cdot P(C_{a})}

گام بیشینه‌سازی (چندمتغیره)

  • به‌روزرسانی میانگین (میانگین وزنی نقطه‌ها):

    μi=∑j=1nP(Ci∣xj)⋅xj∑j=1nP(Ci∣xj)\mathbf{\mu}_{i} = \frac{\sum_{j=1}^n P(C_i | \mathbf{x}_j) \cdot \mathbf{x}_{j}} {\sum_{j=1}^n P(C_i | \mathbf{x}_j)}
  • به‌روزرسانی کوواریانس (ماتریس کوواریانس وزنی روی ابعاد):

    Σi=∑j=1nP(Ci∣xj)(xj−μi)(xj−μi)T∑j=1nP(Ci∣xj)\mathbf{\Sigma}_{i} = \frac{\sum_{j=1}^n P(C_i | \mathbf{x}_j) (\mathbf{x}_j - \mathbf{\mu}_i)(\mathbf{x}_j - \mathbf{\mu}_i)^T} {\sum_{j=1}^n P(C_i | \mathbf{x}_j)}
  • به‌روزرسانی احتمال پیشین (کسر سهم کل در خوشه):

    P(Ci)=∑j=1nP(Ci∣xj)nP(C_{i}) = \frac{\sum_{j=1}^n P(C_i | \mathbf{x}_j)}{n}

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

K-Means به‌عنوان حالت خاصی از امید-بیشینه‌سازی (EM)

K-means را می‌توان نسخهٔ ساده‌شدهٔ الگوریتم امید-بیشینه‌سازی (EM) دانست که در آن تخصیص‌های خوشه قطعی‌اند نه احتمالاتی. به‌ویژه در K-means هر نقطهٔ دادهٔ xj\mathbf{x}_{j} بر پایهٔ کمترین مربع فاصله تا مرکز خوشه، انحصاراً به یک خوشه تعلق دارد:

P(xj∣Ci)={1if Ci=arg⁡min⁡Ca{∥xj−μa∥2}0otherwiseP(\mathbf{x}_{j} | C_i) = \begin{cases} 1 & \text{if } C_i = \arg\min_{C_a} \left\{ \|\mathbf{x}_{j} - \mathbf{\mu}_a\|^2\right\}\\ 0 & \text{otherwise} \end{cases}

احتمال پسین تخصیص خوشه با قضیهٔ بیز حساب می‌شود:

P(Ci∣xj)=P(xj∣Ci)P(Ci)∑a=1kP(xj∣Ca)P(Ca)P(C_i | \mathbf{x}_{j}) = \frac{P(\mathbf{x}_{j} | C_i) P(C_i)} {\sum_{a=1}^k P(\mathbf{x}_{j} | C_a) P(C_a)}

چون K-means هر نقطه را قطعی به دقیقاً یک خوشه تخصیص می‌دهد، این به حالت‌های زیر ساده می‌شود:

  • اگر P(xj∣Ci)=0P(\mathbf{x}_{j} | C_i) = 0، آن‌گاه P(Ci∣xj)=0P(C_i | \mathbf{x}_{j}) = 0.

  • اگر P(xj∣Ci)=1P(\mathbf{x}_{j} | C_i) = 1، آن‌گاه برای همهٔ a≠ia \neq i داریم P(xj∣Ca)=0P(\mathbf{x}_{j} | C_a) = 0، پس:

    P(Ci∣xj)=1⋅P(Ci)1⋅P(Ci)=1.P(C_i | \mathbf{x}_{j}) = \frac{1 \cdot P(C_i)}{1 \cdot P(C_i)} = 1.

پس در K-means عضویت خوشه دودویی است:

P(Ci∣xj)={1if xj∈Ci,i.e., if Ci=arg⁡min⁡Ca{∥xj−μa∥2}0otherwiseP(C_i | \mathbf{x}_{j}) = \begin{cases} 1 & \text{if } \mathbf{x}_{j} \in C_i, \text{i.e., if } C_i = \arg\min_{C_a} \left\{ \|\mathbf{x}_{j} - \mathbf{\mu}_a\|^2\right\}\\ 0 & \text{otherwise} \end{cases}

برخلاف EM که ماتریس‌های کوواریانس را برای مدل کردن توزیع خوشه‌ها به کار می‌برد، K-means فقط مرکزهای خوشه μi\mathbf{\mu}_i و نسبت‌های خوشه P(Ci)P(C_i) را برآورد می‌کند.

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367