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 · فارسی

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

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

جای این صفحه در درس

بندهای ۱۴.۳.۴ و ۱۴.۳.۵ از hastie2009esl (صص ۵۰۷–۵۰۹) پل میان ماتریس نامتشابهی و الگوریتم‌هاست. دو کار می‌کنند: روش‌های خوشه‌بندی را بر پایهٔ آنچه هر روش دربارهٔ داده فرض می‌کند به سه خانواده دسته می‌کنند، و بعد خانوادهٔ ترکیبیاتی را به‌صورت یک مسئلهٔ بهینه‌سازی صریح می‌نویسند، همان صورتی که هر روش صفحه‌های بعد حالت خاصی از آن است.

این بهینه‌سازی جواب دقیق دارد — شمردن همهٔ افرازها — که به‌طور بی‌فایده‌ای گران است. آنچه می‌ماند فرود است، و فرود هم قوت و هم ضعف K-means را توضیح می‌دهد.

در پایان باید بتوانید

  • بگویید یک الگوریتم داده‌شده به کدام یک از سه خانواده می‌رسد و در نتیجه چه فرضی می‌گذارد؛

  • پراکندگی درون‌خوشه‌ای W(C)W(C) و میان‌خوشه‌ای B(C)B(C) را بنویسید و T=W+BT = W + B را اثبات کنید؛

  • بگویید چرا کمینه‌کردن WW همان بیشینه‌کردن BB است؛

  • توضیح دهید چرا هر روش عملی یک فرود حریص است که می‌تواند در کمینهٔ محلی بایستد.

۱. سه خانواده

خانوادهچه فرضی می‌کندچه چیزی برآورد می‌شودمثال‌ها
ترکیبیاتیچیزی بیش از نامتشابهی‌هاانتساب C(i)C(i) هر مشاهدهK-means، K-medoids، ادغام سلسله‌مراتبی
مدل مخلوطداده نمونه‌ای i.i.d. از مخلوطی از چگالی‌هاستپارامترهای چگالی‌های مؤلفهمخلوط‌های گاوسی، خوشه‌بندی مدل‌بنیان
جست‌وجوی مُدچگالی نامعلوم است ولی مُدهای مشخص داردمُدها، و سپس نقطه‌های نزدیک هر مُدPRIM («شکار برجستگی»)، mean-shift، DBSCAN

این تقسیم دربارهٔ فرض‌هاست، نه کیفیت. روش ترکیبیاتی هرگز نمی‌پرسد داده از کجا آمده؛ مدل مخلوط مدلی احتمالاتی می‌گوید و آن را با درست‌نمایی بیشینه برآورد می‌کند؛ جست‌وجوی مُد چگالی را ناپارامتری برآورد و همسایگی هر مُد را یک خوشه می‌نامد. خانوادهٔ اول در عمل بسیار بزرگ‌ترین است و همان است که این درس گسترش می‌دهد؛ مدل مخلوط در ادامهٔ درس جداگانه می‌آید و جست‌وجوی مُد فقط به‌عنوان ایدهٔ پشت روش‌های چگالی‌بنیان ظاهر می‌شود.

۲. صورت‌بندی ترکیبیاتی

هر مشاهده با عدد صحیح i∈{1,…,N}i \in \{1,\dots,N\} و هر خوشه با k∈{1,…,K}k \in \{1,\dots,K\} برچسب می‌خورد، با K<NK < N که از پیش داده شده است. یک خوشه‌بندی یک کدگذار است:

k=C(i),k = C(i),

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

زیان طبیعی، مجموع نامتشابهی درون خوشه‌هاست:

W(C)=12∑k=1K∑C(i)=k∑C(i′)=kd(xi,xi′),(14.28)W(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k} \sum_{C(i')=k} d(x_i, x_{i'}), \qquad \text{(14.28)}

همان «پراکندگی نقطه‌ای درون‌خوشه‌ای»: وقتی نقطه‌هایی که با هم در یک خوشه‌اند نزدیک باشند کوچک است. شکستن پراکندگی کل به بخش درونی و بخش میان‌خوشه‌ای می‌دهد:

T=12∑i=1N∑i′=1Ndii′=W(C)+B(C),B(C)=12∑k=1K∑C(i)=k∑C(i′)≠kdii′.(14.29)T = \frac{1}{2}\sum_{i=1}^{N}\sum_{i'=1}^{N} d_{ii'} = W(C) + B(C), \qquad B(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k} \sum_{C(i') \ne k} d_{ii'} . \qquad \text{(14.29)}

TT فقط به داده بستگی دارد، پس کمینه‌کردن WW دقیقاً بیشینه‌کردن BB است. این دو بیان در جاهای مختلف به کار می‌آیند: «خوشه‌ها را جمع‌وجور کن» و «خوشه‌ها را از هم دور کن» یک دستورند.

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

W(C)      =  15566.41
B(C)      =  33990.16
W(C) + B  =  49556.56
T         =  49556.56

جزئیاتی که ارزش دانستن دارد: WW و inertia در sklearn

با فاصلهٔ اقلیدسی مجذور، صورت جفتی (۱۴.۲۸) را می‌توان برحسب میانگین‌های خوشه بازنویسی کرد و همین است که K-means را ارزان می‌کند:

12∑i∈Ck∑i′∈Ck∥xi−xi′∥2=Nk∑i∈Ck∥xi−xˉk∥2.(14.31)\frac{1}{2}\sum_{i \in C_k}\sum_{i' \in C_k} \lVert x_i - x_{i'} \rVert^2 = N_k \sum_{i \in C_k} \lVert x_i - \bar{x}_k \rVert^2 . \qquad \text{(14.31)}

سمت چپ هر جفت را یک‌بار می‌شمارد؛ سمت راست مجموع مربعات خوشه را در اندازه‌اش NkN_k ضرب می‌کند. پس WW همان عددی نیست که KMeans.inertia_ گزارش می‌کند — آن ∑k∑i∈Ck∥xi−xˉk∥2\sum_k \sum_{i \in C_k}\lVert x_i - \bar x_k\rVert^2 است، بدون NkN_k — و لازم نیست کمینه‌ساز یکسان داشته باشند. هر دو پراکندگی درون‌خوشه‌ای‌اند، هر دو با جمع‌وجورتر شدن خوشه‌ها کم می‌شوند، و کتاب از (۱۴.۳۱) بهره می‌برد چون جمعی N2N^2 تایی را به جمعی NN تایی تبدیل می‌کند. این ضریب را وقتی عددهای منابع مختلف را مقایسه می‌کنید در یاد نگه دارید.

pairwise W(C)                   : 15566.41
sum_k N_k * SS_k, form (14.31)  : 15566.41
sum_k SS_k, the sklearn inertia : 759.35

۳. شمردن دقیق است و بی‌فایده

تعداد راه‌های شکستن NN مشاهدهٔ برچسب‌دار به KK خوشهٔ ناتهی همان عدد استرلینگ نوع دوم است:

S(N,K)=1K!∑k=1K(−1)K−k(Kk)kN.(14.30)S(N,K) = \frac{1}{K!}\sum_{k=1}^{K}(-1)^{K-k}\binom{K}{k}k^{N} . \qquad \text{(14.30)}

برای N=10N = 10 و K=4K = 4 این 34 10534\,105 است که یک لپ‌تاپ می‌تواند بشمارد. برای N=19N = 19 از قبل 1010 است، و مسئله‌های خوشه‌بندی از صدها مشاهده آغاز می‌شوند. شمارش، کد شمردن و هرس‌کردنی که نمونه‌های کوچک را قابل‌حل می‌کند در صفحهٔ خوشه‌بندی فراگیر کار شده است؛ اینجا فقط پیامد مهم است:

S(10, 4) = 3.410e+04
S(19, 4) = 1.126e+10
S(50, 3) = 1.196e+23

۴. آنچه می‌ماند: فرود حریص

یک روش عملی از افرازی آغازین شروع می‌کند و تا وقتی تغییری WW را بهتر می‌کند برچسب‌ها را عوض می‌کند. وقتی هیچ تغییر تکی آن را بهتر نکند، الگوریتم می‌ایستد و انتساب کنونی را برمی‌گرداند. این یک کمینهٔ محلی از تابعی است که روی مجموعه‌ای متناهی ولی نجومی تعریف شده و هیچ‌چیز در رویه نمی‌گوید کمینهٔ جهانی نزدیک است.

کد زیر دقیقاً همین کار را می‌کند، با حرکت خام «اگر WW کم شود، یک نقطه را به خوشهٔ دیگری ببر»، که روی ماتریس جفتی کامل ارزیابی می‌شود. برای دادهٔ واقعی بسیار کند است — از همین رو K-means آن را با حرکت دوگامی «میانگین‌ها، بعد نزدیک‌ترین میانگین» جانشین می‌کند — ولی شکل هر روش این فصل را نشان می‌دهد.

start 0: steps  36   W from   748.54 to   258.19
start 1: steps  47   W from   793.17 to   245.77
start 2: steps  49   W from   814.64 to   245.77
start 3: steps  33   W from   790.05 to   245.77
start 4: steps  54   W from   814.08 to   245.77

هر سطر کاهش می‌یابد و سطرها همه به یک مقدار نمی‌رسند: با چهار گروه و K=3K = 3، یکی از پنج شروع روی خوشه‌بندی‌ای ایستاد که هیچ حرکت تکی بهترش نمی‌کند و با این حال از آنچه بقیه یافتند بدتر است. این یک کمینهٔ محلی از معیاری با چند حوضهٔ جذب است، و مهم‌ترین واقعیت عملی دربارهٔ خوشه‌بندی: نقطهٔ آغاز بخشی از جواب است؛ از همین رو هر پیاده‌سازی الگوریتم را از چند شروع اجرا می‌کند و بهترین را نگه می‌دارد — و از همین رو تعداد شروع‌ها بخشی از چیزی است که گزارش می‌کنید.

K-means همین طرح است با فاصلهٔ اقلیدسی مجذور و حرکتی هوشمندانه‌تر: با میانگین‌های کنونی، هر نقطه به نزدیک‌ترین میانگین می‌رود، که فقط NN محاسبهٔ فاصله می‌خواهد نه N2N^2. معیاری که پایین می‌آورد همان پراکندگی درون‌خوشه‌ای (۱۴.۳۱) است؛ بهای حرکت ارزان‌تر این است که تنها زیرمجموعهٔ کوچکی از بازبرچسب‌گذاری‌های ممکن را می‌بیند، پس آن هم می‌تواند زود بایستد. خوشه‌بندی فراگیر این دو را روی مسئله‌ای مقایسه می‌کند که به‌اندازهٔ کافی کوچک است تا بهینهٔ جهانی‌اش حساب شود.

خلاصه

  • روش‌های خوشه‌بندی بر پایهٔ آنچه فرض می‌کنند به خانواده‌های ترکیبیاتی، مدل مخلوط و جست‌وجوی مُد تقسیم می‌شوند؛ روش ترکیبیاتی فقط نامتشابهی‌ها را فرض می‌کند.

  • در خانوادهٔ ترکیبیاتی پارامترها خودِ انتساب‌ها هستند و زیان، پراکندگی درون‌خوشه‌ای W(C)W(C) از (۱۴.۲۸) است.

  • T=W+BT = W + B با TT ثابت، پس کمینه‌کردن WW و بیشینه‌کردن BB یک مسئله‌اند.

  • جواب دقیق S(N,K)S(N,K) ارزیابی می‌خواهد، که از قبل در N=19N = 19 و K=4K = 4 برابر 1010 است.

  • روش‌های عملی فرودهای حریص‌اند که در کمینهٔ محلی می‌ایستند، و نقطهٔ شروع تعیین می‌کند کدام یکی.

تمرین‌ها

  1. T=W+BT = W + B را از تعریف‌ها اثبات کنید و آن را برای K=1K = 1 و K=NK = N بررسی کنید.

  2. (۱۴.۳۱) را برای خوشه‌ای سه‌نقطه‌ای دستی و بعد با دو خط numpy بررسی کنید.

  3. نشان دهید وقتی همهٔ خوشه‌ها اندازهٔ یکسان دارند، WW و مجموع مربعات بی‌وزن مقدار یکسان می‌دهند. کِی دو افراز را متفاوت رتبه‌بندی می‌کنند؟

  4. S(N,2)=2N−1−1S(N,2) = 2^{N-1} - 1 را از (۱۴.۳۰) حساب کنید و با خوشه‌بندی فراگیر مقایسه کنید.

  5. greedy را چنان تغییر دهید که نخستین حرکت بهبوددهنده را بپذیرد نه بهترین را. اجراها گام کمتری برمی‌دارند؟ پایین‌تر می‌ایستند یا بالاتر؟

  6. دو مجموعه‌داده مثال بدهید که برای هر افراز WW یکسان داشته باشند ولی جواب «کدام خوشه‌بندی درست است» در آن‌ها متفاوت باشد.

منابع

  • سه خانواده، صورت‌بندی کدگذار، (۱۴.۲۸)–(۱۴.۳۱) و جملهٔ همگرایی به کمینه‌های محلی: بندهای ۱۴.۳.۴–۱۴.۳.۵ از hastie2009esl، صص ۵۰۷–۵۰۹.

  • شمردن افرازها و هرسی که جست‌وجوی فراگیر را روی نمونه‌های کوچک ممکن می‌کند: خوشه‌بندی فراگیر.

  • اتحاد پشت (۱۴.۳۱) لم ۲ از خوشه‌بندی بخش ۲ است.