ادامهٔ k-means++

در مرحلهٔ نخست k-means++ یک Centroid به‌صورت یکنواخت و تصادفی انتخاب شد. ادامهٔ مقداردهی اولیه به این صورت است:

2. Centroid جدید c(i) با انتخاب یک نمونهٔ x(i) و با احتمالی متناسب با مربع فاصلهٔ آن نمونه تا نزدیک‌ترین Centroid انتخاب‌شدهٔ قبلی برگزیده می‌شود. اگر D(x(i)) فاصلهٔ نمونه تا نزدیک‌ترین مرکز موجود باشد، احتمال انتخاب با D(x(i))² / Σ_j=1..mD(x(j))² متناسب است. بنابراین نمونه‌های دورتر از مراکز فعلی شانس بیشتری برای تبدیل‌شدن به Centroid دارند.
3. مرحلهٔ قبل تکرار می‌شود تا هر k Centroid انتخاب شوند.

کلاس KMeans در Scikit-Learn به‌طور پیش‌فرض از همین روش مقداردهی اولیه استفاده می‌کند.

k-means شتاب‌یافته و Mini-Batch k-means

Charles Elkan در سال ۲۰۰۳ روشی برای سریع‌تر کردن k-means روی برخی مجموعه‌های بزرگ با خوشه‌های زیاد پیشنهاد کرد. ایده این است که بسیاری از محاسبات فاصلهٔ غیرضروری حذف شوند. روش Elkan از نامساوی مثلث استفاده می‌کند و کران‌های بالا و پایین فاصلهٔ نمونه‌ها تا Centroidها را نگه می‌دارد. این روش همیشه سریع‌تر نیست و روی بعضی داده‌ها حتی می‌تواند آموزش را کندتر کند. برای آزمایش آن می‌توان algorithm="elkan" را تنظیم کرد.

David Sculley در سال ۲۰۱۰ نوع مهم دیگری از k-means را معرفی کرد: به‌جای استفاده از کل مجموعه در هر تکرار، الگوریتم از Mini-Batch استفاده می‌کند و Centroidها را در هر مرحله اندکی جابه‌جا می‌کند. این کار معمولاً آموزش را سه تا چهار برابر سریع‌تر می‌کند و امکان خوشه‌بندی داده‌هایی را می‌دهد که در RAM جا نمی‌شوند.

from sklearn.cluster import MiniBatchKMeans

minibatch_kmeans = MiniBatchKMeans(
    n_clusters=5,
    random_state=42
)
minibatch_kmeans.fit(X)

اگر داده در حافظه جا نشود، می‌توان مانند Incremental PCA از memmap استفاده کرد. گزینهٔ دیگر ارسال Mini-Batchها یکی‌یکی به partial_fit() است، اما در آن صورت انجام چند مقداردهی اولیه و انتخاب بهترین نتیجه بر عهدهٔ شما خواهد بود.

Mini-Batch k-means بسیار سریع‌تر از k-means معمولی است، اما Inertia آن معمولاً اندکی بدتر است. شکل ۹-۶ سمت چپ Inertia دو روش را برای مقادیر مختلف k مقایسه می‌کند و سمت راست نشان می‌دهد که در این داده Mini-Batch تقریباً ۳٫۵ برابر سریع‌تر است.

پیدا کردن تعداد بهینهٔ خوشه‌ها

تا اینجا k را ۵ در نظر گرفتیم، زیرا پنج تودهٔ داده با نگاه کردن قابل تشخیص بود. در مسائل واقعی انتخاب k معمولاً روشن نیست و مقدار نادرست می‌تواند خوشه‌بندی ضعیفی بسازد. شکل ۹-۷ نشان می‌دهد که k برابر ۳، چند خوشهٔ جدا را با هم ادغام می‌کند، و k برابر ۸ برخی خوشه‌های طبیعی را به چند قطعه می‌شکند.

نمی‌توان صرفاً مدلی را انتخاب کرد که کمترین Inertia را دارد، زیرا با افزایش k فاصلهٔ هر نمونه تا نزدیک‌ترین Centroid معمولاً کمتر می‌شود و در نتیجه Inertia پیوسته کاهش می‌یابد. برای مثال Inertia با k=3 حدود ۶۵۳٫۲، با k=5 حدود ۲۱۱٫۶ و با k=8 فقط ۱۱۹٫۱ است؛ این به معنی بهتر بودن k=8 نیست.

اگر Inertia را برحسب k رسم کنیم، منحنی اغلب یک نقطهٔ خم یا Elbow دارد. در شکل ۹-۸ کاهش Inertia تا k=4 بسیار سریع است و پس از آن کند می‌شود؛ بنابراین اگر اطلاعات دیگری نداشتیم، k=4 انتخاب معقولی بود.

Silhouette Score

روش Elbow نسبتاً تقریبی است. روش دقیق‌تر، اما محاسباتی‌تر، استفاده از Silhouette Score است که میانگین ضریب Silhouette همهٔ نمونه‌هاست. ضریب هر نمونه برابر است با:

در این رابطه، a میانگین فاصلهٔ نمونه تا سایر نمونه‌های همان خوشه، یعنی فاصلهٔ درون‌خوشه‌ای، و b میانگین فاصله تا نزدیک‌ترین خوشهٔ دیگر است. ضریب بین −۱ و +۱ تغییر می‌کند. مقدار نزدیک +۱ یعنی نمونه عمیقاً داخل خوشهٔ خودش و از خوشه‌های دیگر دور است؛ مقدار نزدیک صفر یعنی نمونه نزدیک مرز خوشه قرار دارد؛ و مقدار نزدیک −۱ نشان می‌دهد احتمالاً نمونه به خوشهٔ اشتباه تخصیص یافته است.

>>> from sklearn.metrics import silhouette_score
>>> silhouette_score(X, kmeans.labels_)
0.655517642572828

شکل ۹-۹ Silhouette Score را برای تعدادهای مختلف خوشه مقایسه می‌کند. k=4 بسیار خوب است، اما k=5 نیز مناسب و به‌وضوح بهتر از ۶ یا ۷ است؛ نکته‌ای که فقط از Inertia قابل مشاهده نبود.

Silhouette Diagram

نمایش اطلاعاتی‌تر آن است که ضریب Silhouette تک‌تک نمونه‌ها را به تفکیک خوشه و به ترتیب مقدار رسم کنیم. این نمودار Silhouette Diagram نام دارد. برای هر خوشه شکلی شبیه تیغه دیده می‌شود؛ ارتفاع آن تعداد نمونه‌ها و عرض آن ضرایب مرتب‌شده را نشان می‌دهد. هرچه عرض به سمت ۱ بیشتر باشد، خوشه بهتر است.

خط عمودی خط‌چین، میانگین Silhouette Score را نشان می‌دهد. اگر بسیاری از نمونه‌های یک خوشه پیش از رسیدن به این خط تمام شوند، آن خوشه ضعیف است. شکل ۹-۱۰ نشان می‌دهد k=3 و k=6 خوشه‌های نامناسبی می‌سازند، در حالی که k=4 و k=5 خوب‌اند. در k=4 یکی از خوشه‌ها بسیار بزرگ است، ولی در k=5 اندازه‌ها متعادل‌ترند؛ بنابراین با وجود کمی بالاتر بودن امتیاز کلی k=4، مقدار ۵ برای داشتن خوشه‌هایی با اندازهٔ مشابه می‌تواند انتخاب بهتری باشد.

محدودیت‌های k-means

k-means سریع و مقیاس‌پذیر است، اما محدودیت دارد: باید برای کاهش احتمال جواب زیر‌بهینه چند بار اجرا شود، تعداد k از پیش مشخص شود، و روی خوشه‌هایی با اندازه‌ها یا چگالی‌های بسیار متفاوت یا شکل‌های غیرکروی خوب عمل نمی‌کند. شکل ۹-۱۱ سه خوشهٔ بیضوی با ابعاد، چگالی و جهت متفاوت را نشان می‌دهد. هیچ‌یک از دو جواب k-means خوب نیستند؛ حتی جواب سمت راست با وجود Inertia کمتر، از نظر ساختار واقعی بسیار بدتر است. برای چنین خوشه‌های بیضوی، Gaussian Mixture معمولاً مناسب‌تر است.

استفاده از خوشه‌بندی برای قطعه‌بندی تصویر

Image Segmentation یعنی تقسیم یک تصویر به چند Segment. چند نوع رایج آن عبارت‌اند از:

• Color Segmentation: پیکسل‌های با رنگ مشابه در یک Segment قرار می‌گیرند. برای نمونه در تصویر ماهواره‌ای می‌توان از آن برای برآورد سطح جنگل استفاده کرد.
• Semantic Segmentation: همهٔ پیکسل‌های متعلق به یک نوع شیء در یک Segment قرار می‌گیرند؛ مثلاً تمام عابران پیاده در تصویر سامانهٔ خودروی خودران در Segment «pedestrian» قرار می‌گیرند.
• Instance Segmentation: هر شیء منفرد Segment مستقل دارد؛ بنابراین هر عابر پیاده Segment جداگانه‌ای می‌گیرد.

در زمان نگارش کتاب، روش‌های پیشرفتهٔ Semantic و Instance Segmentation عمدتاً بر معماری‌های پیچیدهٔ شبکهٔ عصبی کانولوشنی تکیه دارند. این فصل فقط Color Segmentation ساده را با k-means بررسی می‌کند.

ابتدا با Pillow تصویر ladybug.png بارگذاری می‌شود:

>>> import PIL
>>> image = np.asarray(PIL.Image.open(filepath))
>>> image.shape
(533, 800, 3)

تصویر آرایه‌ای سه‌بعدی است: بُعد اول ارتفاع، بُعد دوم عرض و بُعد سوم کانال‌های رنگی است. اینجا سه کانال RGB داریم و برای هر پیکسل یک بردار سه‌بعدی شدت قرمز، سبز و آبی با مقادیر ۸بیتی بدون علامت بین ۰ تا ۲۵۵ ذخیره می‌شود. تصاویر خاکستری ممکن است یک کانال داشته باشند، برخی تصاویر کانال Alpha برای شفافیت دارند و تصاویر ماهواره‌ای می‌توانند کانال‌های فرکانسی اضافی مانند فروسرخ داشته باشند.

کد زیر آرایه را به فهرست بلندی از رنگ‌های RGB تبدیل و آن‌ها را با هشت خوشه k-means گروه‌بندی می‌کند. سپس رنگ هر پیکسل با رنگ Centroid خوشهٔ آن جایگزین و شکل آرایه به اندازهٔ اصلی تصویر بازگردانده می‌شود:

X = image.reshape(-1, 3)
kmeans = KMeans(n_clusters=8, random_state=42).fit(X)
segmented_img = kmeans.cluster_centers_[kmeans.labels_]
segmented_img = segmented_img.reshape(image.shape)

شکل ۹-۱۲ خروجی با تعدادهای مختلف خوشهٔ رنگی را نشان می‌دهد. وقتی تعداد خوشه‌ها کمتر از ۸ می‌شود، رنگ قرمز درخشان کفشدوزک خوشهٔ مستقل خود را از دست می‌دهد و با رنگ‌های محیط ادغام می‌شود؛ زیرا k-means تمایل دارد خوشه‌هایی با اندازه‌های نسبتاً مشابه ایجاد کند و کفشدوزک بخش کوچکی از تصویر است.

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

یادگیری نیمه‌نظارتی زمانی مطرح است که تعداد زیادی نمونهٔ بدون برچسب و تعداد کمی نمونهٔ برچسب‌دار داریم. مثال کتاب از مجموعهٔ digits استفاده می‌کند؛ داده‌ای شبیه MNIST شامل ۱۷۹۷ تصویر خاکستری ۸×۸ از ارقام ۰ تا ۹.

from sklearn.datasets import load_digits

X_digits, y_digits = load_digits(return_X_y=True)
X_train, y_train = X_digits[:1400], y_digits[:1400]
X_test, y_test = X_digits[1400:], y_digits[1400:]

فرض می‌کنیم فقط ۵۰ نمونه برچسب دارند. یک Logistic Regression فقط روی همین ۵۰ نمونه آموزش می‌دهیم:

from sklearn.linear_model import LogisticRegression

n_labeled = 50
log_reg = LogisticRegression(max_iter=10_000)
log_reg.fit(X_train[:n_labeled], y_train[:n_labeled])

>>> log_reg.score(X_test, y_test)
0.7481108312342569

دقت فقط ۷۴٫۸٪ است؛ در حالی که آموزش روی کل مجموعهٔ برچسب‌دار حدود ۹۰٫۷٪ می‌دهد. برای استفادهٔ بهتر از بودجهٔ برچسب‌گذاری، ابتدا داده را به ۵۰ خوشه تقسیم می‌کنیم و از هر خوشه نمونه‌ای را انتخاب می‌کنیم که به Centroid نزدیک‌تر است؛ این نمونه‌ها Representative Images هستند.

k = 50
kmeans = KMeans(n_clusters=k, random_state=42)
X_digits_dist = kmeans.fit_transform(X_train)
representative_digit_idx = np.argmin(
    X_digits_dist,
    axis=0
)
X_representative_digits = X_train[representative_digit_idx]

اکنون فقط همین ۵۰ تصویر نماینده به‌صورت دستی برچسب می‌خورند:

y_representative_digits = np.array(
    [1, 3, 6, 0, 7, 9, 2, ..., 5, 1, 9, 9, 3, 7]
)

با همان تعداد ۵۰ نمونه، اما این بار نمونه‌های نماینده به‌جای نمونه‌های تصادفی، عملکرد به‌وضوح بهتر می‌شود:

>>> log_reg = LogisticRegression(max_iter=10_000)
>>> log_reg.fit(
...     X_representative_digits,
...     y_representative_digits
... )
>>> log_reg.score(X_test, y_test)
0.8488664987405542

دقت از ۷۴٫۸٪ به ۸۴٫۹٪ رسیده است، در حالی که هنوز فقط ۵۰ نمونه برچسب‌گذاری شده‌اند. وقتی برچسب‌گذاری دستی پرهزینه و نیازمند متخصص است، انتخاب نمونه‌های نماینده به‌جای نمونه‌های تصادفی می‌تواند بسیار ارزشمند باشد.