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.

خوشه‌بندی — بخش ۲

English · فارسی

خوشه‌بندی — بخش ۲

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

خوشه‌بندی k-means

تعریف خوشه‌بندی

خوشه‌بندی مجموعه‌ای از نقاط داده {x1,x2,…,xn}\{x_1, x_2, \ldots, x_n\}، افراز آن نقاط به kk زیرمجموعهٔ جدا از هم (یا خوشه) است، C={C1,C2,…,Ck}\mathcal{C} = \{C_1, C_2, \ldots, C_k\}، به‌طوری‌که نقاط درون یک گروه، به یک معنا که تحلیلگر تعیین می‌کند، به هم شبیه‌تر باشند تا به نقاط گروه‌های دیگر.

خوشه‌بندی نماینده‌بنیان

داده‌ای با nn نقطه در فضای dd-بُعدی، D={xi}i=1n\textbf{D} = \{\textbf{x}_i\}_{i=1}^n، و تعداد خوشهٔ دلخواه kk را در نظر بگیرید. هدف خوشه‌بندی نماینده‌بنیان، افراز داده به kk گروه یا خوشه است که خوشه‌بندی نامیده و با C={C1,C2,…,Ck}\mathcal{C} = \{C_1, C_2, \ldots, C_k\} نشان داده می‌شود.

برای هر خوشهٔ CiC_i یک نقطهٔ نماینده وجود دارد که خوشه را خلاصه می‌کند؛ انتخاب رایج، میانگین (یا مرکز) μi{\mu}_i همهٔ نقاط آن خوشه است:

μi=1ni∑xj∈Cixj\begin{align*} {\mu_i} = {1\over n_i} \sum_{x_{j} \in C_i} \textbf{x}_{j} \end{align*}

که در آن ni=∣Ci∣n_i = |C_i| تعداد نقاط خوشهٔ CiC_i است.

خوشه‌بندی k-means

خوشه‌بندی k-means یک خوشه‌بندی نماینده‌بنیان است که نقاط را بر اساس شباهتشان به مرکز هر خوشه، به kk خوشه افراز می‌کند. هدف، یافتن افرازی C\mathcal{C} است که مجموع مجذور فاصلهٔ هر نقطه تا مرکز خوشهٔ خودش را کمینه کند.

لم ۱: مجموع مجذور فاصله‌ها تا یک نقطهٔ دلخواه

فرض کنید {x1,x2,…,xn}\{x_1, x_2, \ldots, x_n\} مجموعه‌ای از نقاط و μ\mu مرکز آن‌ها باشد. مجموع مجذور فاصلهٔ نقاط تا هر نقطهٔ دلخواه zz، برابر است با مجموع مجذور فاصله‌ها تا مرکز، به‌اضافهٔ nn برابر مجذور فاصلهٔ zz تا مرکز:

∑i=1n∣xi−z∣2=∑i=1n∣xi−μ∣2+n∣μ−z∣2\sum_{i=1}^n |x_i - z|^2 = \sum_{i=1}^n |x_i - \mu|^2 + n |\mu - z|^2

اثبات:

∑i=1n∣xi−z∣2=∑i=1n∣xi−μ+μ−z∣2=∑i=1n∣xi−μ∣2+2(μ−z)⋅∑i=1n(xi−μ)+n∣μ−z∣2=∑i=1n∣xi−μ∣2+n∣μ−z∣2\begin{align*} \sum_{i=1}^n |x_i - z|^2 &= \sum_{i=1}^n |x_i - \mu + \mu - z|^2 \\ &= \sum_{i=1}^n |x_i - \mu|^2 + 2(\mu - z) \cdot \sum_{i=1}^n (x_i - \mu) + n |\mu - z|^2 \\ &= \sum_{i=1}^n |x_i - \mu|^2 + n |\mu - z|^2 \end{align*}

زیرا ∑i=1n(xi−μ)=0\sum_{i=1}^n (x_i - \mu) = 0.

نتیجهٔ ۱: مرکز، مجموع مجذور فاصله‌ها را کمینه می‌کند

چون جملهٔ دوم، n∣μ−z∣2n |\mu - z|^2، همیشه نامنفی است، مجموع مجذور فاصله‌ها در z=μz=\mu کمینه می‌شود.

اثبات: مستقیم از لم ۱ نتیجه می‌شود.

لم ۲: مجموع مجذور فاصله‌ها بین همهٔ جفت‌نقاط

فرض کنید {x1,x2,…,xn}\{x_1, x_2, \ldots, x_n\} مجموعه‌ای از نقاط و μ\mu مرکز آن‌ها باشد. مجموع مجذور فاصله‌ها بین همهٔ جفت‌نقاط، برابر است با nn برابر مجموع مجذور فاصله‌های نقاط تا مرکز:

∑i=1n∑j>i∣xi−xj∣2=n∑i=1n∣xi−μ∣2\sum_{i=1}^n \sum_{j>i} |x_i - x_j|^2 = n \sum_{i=1}^n |x_i - \mu|^2

اثبات:

∑i=1n∑j>i∣xi−xj∣2=12∑i=1n∑j=1n∣xi−xj∣2=12∑j=1n(∑i=1n∣xi−xj∣2)=12∑j=1n(∑i=1n∣xi−μ∣2+n∣μ−xj∣2)=12(∑j=1n(∑i=1n∣xi−μ∣2)+n∑j=1n(∣μ−xj∣2))=12(n∑i=1n∣xi−μ∣2+n∑i=1n∣xi−μ∣2))=n∑i=1n∣xi−μ∣2\begin{align*} \sum_{i=1}^n \sum_{j>i} |x_i - x_j|^2 &= \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n |x_i - x_j|^2 \\ &= \frac{1}{2} \sum_{j=1}^n (\sum_{i=1}^n |x_i - x_j|^2) \\ &= \frac{1}{2} \sum_{j=1}^n (\sum_{i=1}^n |x_i - \mu|^2 + n |\mu - x_j|^2) \tag{لم ۱}\\ &= \frac{1}{2} \left(\sum_{j=1}^n (\sum_{i=1}^n |x_i - \mu|^2) + n \sum_{j=1}^n(|\mu - x_j|^2)\right)\\ &= \frac{1}{2} \left(n\sum_{i=1}^n |x_i - \mu|^2 + n\sum_{i=1}^n |x_i - \mu|^2)\right)\\ &= n \sum_{i=1}^n |x_i - \mu|^2 \end{align*}

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

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

  1. kk مرکز اولیهٔ μ1,…,μk\mu_1, \ldots, \mu_k را تصادفی مقداردهی کن.

  2. در هر تکرار:

    1. هر نقطهٔ xix_i را به خوشهٔ CjC_j با نزدیک‌ترین مرکز μj\mu_j نسبت بده.

    2. مرکزهای μ1,…,μk\mu_1, \ldots, \mu_k را میانگین نقاط هر خوشه بگذار.

  3. گام ۲ را تا همگرایی تکرار کن.

همگرایی الگوریتم k-means

الگوریتم همیشه همگرا می‌شود، ولی ممکن است به کمینهٔ محلی برسد. برای اثبات همگرایی، نشان می‌دهیم هزینهٔ خوشه‌بندی — مجموع مجذور فاصلهٔ هر نقطه تا مرکز خوشه‌اش — در هر گام بهتر می‌شود (گام نسبت‌دهی و گام به‌روزرسانی هر دو این هزینه را کاهش می‌دهند)، پس دنبالهٔ مقادیر هزینه یک دنبالهٔ نزولی کران‌دار است و الگوریتم در تعداد متناهی گام متوقف می‌شود.

پیاده‌سازی پایتونی زیر همین الگوریتم است:

پیاده‌سازی شیءگرا از k-means

این نوت‌بوک ابتدا دادهٔ نمونه می‌سازد و سپس کلاسی به نام KMeansClustering تعریف می‌کند که الگوریتم k-means را پیاده می‌کند. متد fit مرکزها را تصادفی مقداردهی می‌کند و سپس تا همگرایی آن‌ها را به‌روز می‌کند.

اسکریپت زیر یک نمونه از کلاس KMeansClustering می‌سازد، مدل را روی داده برازش می‌کند و داده را همراه با مرکزها و برچسب‌ها رسم می‌کند.

<Figure size 640x480 with 1 Axes>

حالا با لم ۲ نشان می‌دهیم که مرکز، مجموع مجذور فاصله‌ها را کمینه می‌کند:

∑i=1n∑j>i∣xi−xj∣2=n∑i=1n∣xi−μ∣2\sum_{i=1}^n \sum_{j>i} |x_i - x_j|^2 = n \sum_{i=1}^n |x_i - \mu|^2

تابع lemma_2 لم ۲ را پیاده می‌کند: مجموع مجذور فاصله‌های همهٔ جفت‌نقاط برابر است با nn برابر مجموع مجذور فاصله‌ها تا مرکز. نوت‌بوک این اتحاد را روی زیرمجموعه‌ای از داده (خوشهٔ ۰) می‌آزماید و دو عدد چاپ‌شده باید تقریباً برابر باشند.

1812.8736866847603 1812.8736866847605

تمرین‌ها

  1. الگوریتم لوید را در کلاسی با متدهای fit و predict بسته‌بندی کنید و در یک آزمون بررسی کنید که دنبالهٔ SSE نزولی است. پیاده‌سازی اعشاری در کجا می‌تواند این ادعا را بشکند؟

  2. زمان یک تکرار را برای (n,K,d)=(103,5,2)(n,K,d) = (10^3,5,2) اندازه بگیرید و سپس با دو برابر کردن nn و KK تکرار کنید. پیش‌بینی O(nKd)O(nKd) را تأیید کنید و بگویید چه چیز دیگری با KK رشد می‌کند.

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