سه خانوادهٔ الگوریتمهای خوشهبندی
جای این صفحه در درس¶
بندهای ۱۴.۳.۴ و ۱۴.۳.۵ از hastie2009esl (صص ۵۰۷–۵۰۹) پل میان ماتریس نامتشابهی و الگوریتمهاست. دو کار میکنند: روشهای خوشهبندی را بر پایهٔ آنچه هر روش دربارهٔ داده فرض میکند به سه خانواده دسته میکنند، و بعد خانوادهٔ ترکیبیاتی را بهصورت یک مسئلهٔ بهینهسازی صریح مینویسند، همان صورتی که هر روش صفحههای بعد حالت خاصی از آن است.
این بهینهسازی جواب دقیق دارد — شمردن همهٔ افرازها — که بهطور بیفایدهای گران است. آنچه میماند فرود است، و فرود هم قوت و هم ضعف K-means را توضیح میدهد.
در پایان باید بتوانید¶
بگویید یک الگوریتم دادهشده به کدام یک از سه خانواده میرسد و در نتیجه چه فرضی میگذارد؛
پراکندگی درونخوشهای و میانخوشهای را بنویسید و را اثبات کنید؛
بگویید چرا کمینهکردن همان بیشینهکردن است؛
توضیح دهید چرا هر روش عملی یک فرود حریص است که میتواند در کمینهٔ محلی بایستد.
۱. سه خانواده¶
| خانواده | چه فرضی میکند | چه چیزی برآورد میشود | مثالها |
|---|---|---|---|
| ترکیبیاتی | چیزی بیش از نامتشابهیها | انتساب هر مشاهده | K-means، K-medoids، ادغام سلسلهمراتبی |
| مدل مخلوط | داده نمونهای i.i.d. از مخلوطی از چگالیهاست | پارامترهای چگالیهای مؤلفه | مخلوطهای گاوسی، خوشهبندی مدلبنیان |
| جستوجوی مُد | چگالی نامعلوم است ولی مُدهای مشخص دارد | مُدها، و سپس نقطههای نزدیک هر مُد | PRIM («شکار برجستگی»)، mean-shift، DBSCAN |
این تقسیم دربارهٔ فرضهاست، نه کیفیت. روش ترکیبیاتی هرگز نمیپرسد داده از کجا آمده؛ مدل مخلوط مدلی احتمالاتی میگوید و آن را با درستنمایی بیشینه برآورد میکند؛ جستوجوی مُد چگالی را ناپارامتری برآورد و همسایگی هر مُد را یک خوشه مینامد. خانوادهٔ اول در عمل بسیار بزرگترین است و همان است که این درس گسترش میدهد؛ مدل مخلوط در ادامهٔ درس جداگانه میآید و جستوجوی مُد فقط بهعنوان ایدهٔ پشت روشهای چگالیبنیان ظاهر میشود.
۲. صورتبندی ترکیبیاتی¶
هر مشاهده با عدد صحیح و هر خوشه با برچسب میخورد، با که از پیش داده شده است. یک خوشهبندی یک کدگذار است:
نگاشتی چندبهیک که هر مشاهده را به یک و تنها یک خوشه میفرستد. پارامترهای مسئله همان برچسباند. مدلی برای برازش و چیزی برای مشتقگیری نیست؛ مجموعهای متناهی از انتسابهای نامزد و یک تابع زیان هست که میگوید هرکدام چقدر بد است.
زیان طبیعی، مجموع نامتشابهی درون خوشههاست:
همان «پراکندگی نقطهای درونخوشهای»: وقتی نقطههایی که با هم در یک خوشهاند نزدیک باشند کوچک است. شکستن پراکندگی کل به بخش درونی و بخش میانخوشهای میدهد:
فقط به داده بستگی دارد، پس کمینهکردن دقیقاً بیشینهکردن است. این دو بیان در جاهای مختلف به کار میآیند: «خوشهها را جمعوجور کن» و «خوشهها را از هم دور کن» یک دستورند.
سلول زیر این اتحاد را روی مجموعهدادهای شبیهسازیشده و انتسابی تصادفی بررسی میکند.
import numpy as np
import matplotlib.pyplot as plt
rng = np.random.default_rng(0)
centres = [(-3.0, 0.0), (3.0, 0.0), (0.0, 4.0), (0.0, -4.0)] # four groups
X = np.vstack([rng.normal(c, 0.7, size=(15, 2)) for c in centres])
N = len(X)
dist = ((X[:, None, :] - X[None, :, :]) ** 2).sum(-1) # squared Euclidean
def W_of(C):
same = C[:, None] == C[None, :]
return 0.5 * dist[same].sum()
def B_of(C):
different = C[:, None] != C[None, :]
return 0.5 * dist[different].sum()
C_random = rng.integers(0, 3, size=N)
T = 0.5 * dist.sum()
print(f"W(C) = {W_of(C_random):9.2f}")
print(f"B(C) = {B_of(C_random):9.2f}")
print(f"W(C) + B = {W_of(C_random) + B_of(C_random):9.2f}")
print(f"T = {T:9.2f}")W(C) = 15566.41
B(C) = 33990.16
W(C) + B = 49556.56
T = 49556.56
جزئیاتی که ارزش دانستن دارد: و inertia در sklearn¶
با فاصلهٔ اقلیدسی مجذور، صورت جفتی (۱۴.۲۸) را میتوان برحسب میانگینهای خوشه بازنویسی کرد و همین است که K-means را ارزان میکند:
سمت چپ هر جفت را یکبار میشمارد؛ سمت راست مجموع مربعات خوشه را در اندازهاش ضرب میکند. پس همان عددی نیست که KMeans.inertia_ گزارش میکند — آن است، بدون — و لازم نیست کمینهساز یکسان داشته باشند. هر دو پراکندگی درونخوشهایاند، هر دو با جمعوجورتر شدن خوشهها کم میشوند، و کتاب از (۱۴.۳۱) بهره میبرد چون جمعی تایی را به جمعی تایی تبدیل میکند. این ضریب را وقتی عددهای منابع مختلف را مقایسه میکنید در یاد نگه دارید.
def means_form(C):
total = 0.0
for k in np.unique(C):
members = X[C == k]
total += len(members) * ((members - members.mean(axis=0)) ** 2).sum()
return total
plain_ss = sum(((X[C_random == k] - X[C_random == k].mean(axis=0)) ** 2).sum()
for k in np.unique(C_random))
print("pairwise W(C) :", round(W_of(C_random), 2))
print("sum_k N_k * SS_k, form (14.31) :", round(means_form(C_random), 2))
print("sum_k SS_k, the sklearn inertia :", round(plain_ss, 2))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
۳. شمردن دقیق است و بیفایده¶
تعداد راههای شکستن مشاهدهٔ برچسبدار به خوشهٔ ناتهی همان عدد استرلینگ نوع دوم است:
برای و این است که یک لپتاپ میتواند بشمارد. برای از قبل 1010 است، و مسئلههای خوشهبندی از صدها مشاهده آغاز میشوند. شمارش، کد شمردن و هرسکردنی که نمونههای کوچک را قابلحل میکند در صفحهٔ خوشهبندی فراگیر کار شده است؛ اینجا فقط پیامد مهم است:
from math import comb, factorial
def stirling2(n, k):
return sum((-1) ** (k - j) * comb(k, j) * j ** n for j in range(k + 1)) // factorial(k)
for n, k in [(10, 4), (19, 4), (50, 3)]:
print(f"S({n:>2}, {k}) = {stirling2(n, k):.3e}")S(10, 4) = 3.410e+04
S(19, 4) = 1.126e+10
S(50, 3) = 1.196e+23
۴. آنچه میماند: فرود حریص¶
یک روش عملی از افرازی آغازین شروع میکند و تا وقتی تغییری را بهتر میکند برچسبها را عوض میکند. وقتی هیچ تغییر تکی آن را بهتر نکند، الگوریتم میایستد و انتساب کنونی را برمیگرداند. این یک کمینهٔ محلی از تابعی است که روی مجموعهای متناهی ولی نجومی تعریف شده و هیچچیز در رویه نمیگوید کمینهٔ جهانی نزدیک است.
کد زیر دقیقاً همین کار را میکند، با حرکت خام «اگر کم شود، یک نقطه را به خوشهٔ دیگری ببر»، که روی ماتریس جفتی کامل ارزیابی میشود. برای دادهٔ واقعی بسیار کند است — از همین رو K-means آن را با حرکت دوگامی «میانگینها، بعد نزدیکترین میانگین» جانشین میکند — ولی شکل هر روش این فصل را نشان میدهد.
def wcss(X, C):
"""Sum over clusters of the sum of squared distances to the cluster mean."""
return sum(((X[C == k] - X[C == k].mean(axis=0)) ** 2).sum() for k in np.unique(C))
def wcss_moves(X, C, K):
cur = wcss(X, C)
for i in range(len(X)):
for k in range(K):
if k == C[i]:
continue
trial = C.copy()
trial[i] = k
if len(np.unique(trial)) < K: # keep K non-empty clusters
continue
if wcss(X, trial) < cur - 1e-9:
return i, k
return None
def greedy(X, K, seed, max_steps=400):
rng = np.random.default_rng(seed)
C = rng.integers(0, K, size=len(X))
history = [wcss(X, C)]
for _ in range(max_steps):
move = wcss_moves(X, C, K)
if move is None:
break
C[move[0]] = move[1]
history.append(wcss(X, C))
return C, history
for seed in range(5):
C, history = greedy(X, 3, seed)
print(f"start {seed}: steps {len(history) - 1:3d} "
f"W from {history[0]:8.2f} to {history[-1]:8.2f}")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-means همین طرح است با فاصلهٔ اقلیدسی مجذور و حرکتی هوشمندانهتر: با میانگینهای کنونی، هر نقطه به نزدیکترین میانگین میرود، که فقط محاسبهٔ فاصله میخواهد نه . معیاری که پایین میآورد همان پراکندگی درونخوشهای (۱۴.۳۱) است؛ بهای حرکت ارزانتر این است که تنها زیرمجموعهٔ کوچکی از بازبرچسبگذاریهای ممکن را میبیند، پس آن هم میتواند زود بایستد. خوشهبندی فراگیر این دو را روی مسئلهای مقایسه میکند که بهاندازهٔ کافی کوچک است تا بهینهٔ جهانیاش حساب شود.
خلاصه¶
روشهای خوشهبندی بر پایهٔ آنچه فرض میکنند به خانوادههای ترکیبیاتی، مدل مخلوط و جستوجوی مُد تقسیم میشوند؛ روش ترکیبیاتی فقط نامتشابهیها را فرض میکند.
در خانوادهٔ ترکیبیاتی پارامترها خودِ انتسابها هستند و زیان، پراکندگی درونخوشهای از (۱۴.۲۸) است.
با ثابت، پس کمینهکردن و بیشینهکردن یک مسئلهاند.
جواب دقیق ارزیابی میخواهد، که از قبل در و برابر 1010 است.
روشهای عملی فرودهای حریصاند که در کمینهٔ محلی میایستند، و نقطهٔ شروع تعیین میکند کدام یکی.
تمرینها¶
را از تعریفها اثبات کنید و آن را برای و بررسی کنید.
(۱۴.۳۱) را برای خوشهای سهنقطهای دستی و بعد با دو خط numpy بررسی کنید.
نشان دهید وقتی همهٔ خوشهها اندازهٔ یکسان دارند، و مجموع مربعات بیوزن مقدار یکسان میدهند. کِی دو افراز را متفاوت رتبهبندی میکنند؟
را از (۱۴.۳۰) حساب کنید و با خوشهبندی فراگیر مقایسه کنید.
greedyرا چنان تغییر دهید که نخستین حرکت بهبوددهنده را بپذیرد نه بهترین را. اجراها گام کمتری برمیدارند؟ پایینتر میایستند یا بالاتر؟دو مجموعهداده مثال بدهید که برای هر افراز یکسان داشته باشند ولی جواب «کدام خوشهبندی درست است» در آنها متفاوت باشد.
منابع¶
سه خانواده، صورتبندی کدگذار، (۱۴.۲۸)–(۱۴.۳۱) و جملهٔ همگرایی به کمینههای محلی: بندهای ۱۴.۳.۴–۱۴.۳.۵ از hastie2009esl، صص ۵۰۷–۵۰۹.
شمردن افرازها و هرسی که جستوجوی فراگیر را روی نمونههای کوچک ممکن میکند: خوشهبندی فراگیر.
اتحاد پشت (۱۴.۳۱) لم ۲ از خوشهبندی بخش ۲ است.
