Label Propagation؛ انتشار برچسب‌ها در خوشه

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

y_train_propagated = np.empty(len(X_train), dtype=np.int64)
for i in range(k):
    y_train_propagated[kmeans.labels_ == i] =         y_representative_digits[i]

>>> log_reg = LogisticRegression()
>>> log_reg.fit(X_train, y_train_propagated)
>>> log_reg.score(X_test, y_test)
0.8942065491183879

این کار جهش دیگری در دقت ایجاد می‌کند و آن را به حدود ۸۹٫۴٪ می‌رساند. می‌توان باز هم بهتر شد: یک درصد نمونه‌هایی را که بیشترین فاصله را از مرکز خوشهٔ خود دارند کنار بگذاریم تا بخشی از Outlierها حذف شوند. کد زیر ابتدا فاصلهٔ هر نمونه تا Centroid خوشهٔ خودش را پیدا می‌کند، سپس در هر خوشه ۱٪ دورترین نمونه‌ها را با مقدار −۱ علامت می‌زند و در پایان آن‌ها را از دادهٔ آموزشی منتشرشده حذف می‌کند.

percentile_closest = 99

X_cluster_dist = X_digits_dist[
    np.arange(len(X_train)),
    kmeans.labels_
]
for i in range(k):
    in_cluster = (kmeans.labels_ == i)
    cluster_dist = X_cluster_dist[in_cluster]
    cutoff_distance = np.percentile(
        cluster_dist,
        percentile_closest
    )
    above_cutoff = (X_cluster_dist > cutoff_distance)
    X_cluster_dist[in_cluster & above_cutoff] = -1

partially_propagated = (X_cluster_dist != -1)
X_train_partially_propagated = X_train[partially_propagated]
y_train_partially_propagated =     y_train_propagated[partially_propagated]

آموزش Logistic Regression روی این دادهٔ پالایش‌شده نتیجهٔ زیر را می‌دهد:

>>> log_reg = LogisticRegression(max_iter=10_000)
>>> log_reg.fit(
...     X_train_partially_propagated,
...     y_train_partially_propagated
... )
>>> log_reg.score(X_test, y_test)
0.9093198992443325

با فقط ۵۰ نمونهٔ برچسب‌خورده ــ به‌طور متوسط تنها ۵ نمونه برای هر کلاس ــ دقت ۹۰٫۹٪ به دست آمده است؛ حتی کمی بالاتر از ۹۰٫۷٪ آموزش روی مجموعهٔ کاملاً برچسب‌خورده. بخشی از این بهبود به حذف Outlierها و بخشی به کیفیت بالای برچسب‌های منتشرشده مربوط است:

>>> (
...     y_train_partially_propagated
...     == y_train[partially_propagated]
... ).mean()
0.9755555555555555

دقت خودِ برچسب‌های منتشرشده تقریباً ۹۷٫۵٪ است.

Active Learning

برای بهبود بیشتر مدل و مجموعهٔ آموزشی می‌توان چند دور یادگیری فعال اجرا کرد؛ در این روش کارشناس انسانی با الگوریتم تعامل می‌کند و فقط نمونه‌هایی را که الگوریتم درخواست می‌کند برچسب می‌زند. یکی از راهبردهای متداول Uncertainty Sampling است:

1. مدل روی نمونه‌های برچسب‌خوردهٔ موجود آموزش داده می‌شود و برای همهٔ نمونه‌های بدون برچسب پیش‌بینی انجام می‌دهد.
2. نمونه‌هایی که مدل دربارهٔ آن‌ها کمترین اطمینان را دارد، یعنی احتمال تخمینی پایین‌تری برای کلاس انتخاب‌شده دارند، به کارشناس داده می‌شوند تا برچسب بخورند.
3. این فرایند تا زمانی تکرار می‌شود که بهبود عملکرد دیگر ارزش هزینهٔ برچسب‌گذاری را نداشته باشد.

راهبردهای دیگر Active Learning شامل انتخاب نمونه‌هایی است که بیشترین تغییر را در مدل ایجاد می‌کنند، بیشترین افت را در خطای Validation به وجود می‌آورند، یا مدل‌های مختلف ــ مثلاً SVM و Random Forest ــ دربارهٔ آن‌ها اختلاف نظر دارند.

DBSCAN

Density-Based Spatial Clustering of Applications with Noise یا DBSCAN خوشه‌ها را به‌صورت نواحی پیوسته با چگالی زیاد تعریف می‌کند. الگوریتم به این ترتیب کار می‌کند:

• برای هر نمونه تعداد نمونه‌هایی که در فاصلهٔ کوچکی به اندازهٔ ε از آن قرار دارند شمرده می‌شود. این ناحیه ε-neighborhood نام دارد.
• اگر یک نمونه حداقل min_samples نمونه، با احتساب خودش، در ε-neighborhood داشته باشد، Core Instance محسوب می‌شود؛ یعنی در ناحیه‌ای متراکم قرار دارد.
• تمام نمونه‌های همسایهٔ یک Core Instance عضو همان خوشه‌اند. اگر همسایه شامل Core Instance دیگری باشد، زنجیره‌ای از Coreهای مجاور می‌تواند یک خوشهٔ بزرگ و با شکل دلخواه بسازد.
• نمونه‌ای که Core نیست و در همسایگی هیچ Coreای هم قرار ندارد، به‌عنوان ناهنجاری شناخته می‌شود.

این روش زمانی خوب کار می‌کند که خوشه‌ها با نواحی کم‌چگالی از هم جدا شده باشند.

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=1000, noise=0.05)
dbscan = DBSCAN(eps=0.05, min_samples=5)
dbscan.fit(X)

برچسب همهٔ نمونه‌ها در labels_ قرار دارد:

>>> dbscan.labels_
array([0, 2, -1, -1, 1, 0, 0, 0, 2, 5, [...], 3, 3, 4, 2, 6, 3])

برچسب −۱ به معنی ناهنجاری است. شاخص Core Instanceها در core_sample_indices_ و خود آن نمونه‌ها در components_ ذخیره می‌شوند:

>>> dbscan.core_sample_indices_
array([0, 4, 5, 6, 7, 8, 10, 11, [...], 993, 995, 997, 998, 999])

>>> dbscan.components_
array([[-0.02137124, 0.40618608],
       [-0.84192557, 0.53058695],
       [...],
       [ 0.79419406, 0.60777171]])

در سمت چپ شکل ۹-۱۴ با eps=0.05 تعداد زیادی ناهنجاری و هفت خوشه پیدا شده است. اگر شعاع همسایگی را با eps=0.2 افزایش دهیم، نتیجهٔ سمت راست بسیار بهتر و دو ساختار ماه‌شکل به‌درستی تشخیص داده می‌شوند.

پیش‌بینی خوشه برای نمونه‌های جدید

کلاس DBSCAN متد predict() ندارد، هرچند fit_predict() موجود است. دلیل این طراحی آن است که بسته به مسئله ممکن است طبقه‌بند متفاوتی برای انتساب نمونه‌های جدید مناسب باشد. پیاده‌سازی آن نیز دشوار نیست؛ مثلاً می‌توان KNeighborsClassifier را فقط روی Core Instanceها آموزش داد:

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=50)
knn.fit(
    dbscan.components_,
    dbscan.labels_[dbscan.core_sample_indices_]
)

اکنون برای چند نمونهٔ جدید هم خوشه و هم احتمال هر خوشه قابل تخمین است:

>>> X_new = np.array([
...     [-0.5, 0], [0, 0.5], [1, -0.1], [2, 1]
... ])
>>> knn.predict(X_new)
array([1, 0, 1, 0])

>>> knn.predict_proba(X_new)
array([[0.18, 0.82],
       [1.  , 0.  ],
       [0.12, 0.88],
       [1.  , 0.  ]])

در این مثال طبقه‌بند فقط روی Coreها آموزش دیده است، اما بسته به کاربرد می‌شد همهٔ نمونه‌ها یا همهٔ نمونه‌های غیرناهنجار را نیز استفاده کرد.

از آنجا که KNN در دادهٔ آموزشی خود کلاس «ناهنجاری» ندارد، حتی نمونهٔ بسیار دور را هم مجبور است به یکی از خوشه‌ها نسبت دهد. برای حل این مشکل می‌توان حداکثر فاصله تعریف کرد. متد kneighbors() فاصله و شاخص نزدیک‌ترین همسایه‌ها را برمی‌گرداند:

>>> y_dist, y_pred_idx = knn.kneighbors(
...     X_new,
...     n_neighbors=1
... )
>>> y_pred = dbscan.labels_[
...     dbscan.core_sample_indices_
... ][y_pred_idx]
>>> y_pred[y_dist > 0.2] = -1
>>> y_pred.ravel()
array([-1, 0, 1, -1])

در مجموع DBSCAN الگوریتمی ساده و قدرتمند است که می‌تواند هر تعداد خوشه با شکل‌های دلخواه را پیدا کند و نسبت به Outlierها مقاوم است. فقط دو فراپارامتر اصلی eps و min_samples دارد. بااین‌حال اگر چگالی خوشه‌ها بسیار متفاوت باشد، یا بین بعضی خوشه‌ها ناحیهٔ کم‌چگالی کافی وجود نداشته باشد، ممکن است نتواند ساختار را درست تشخیص دهد. پیچیدگی تقریبی آن O(m²n) است و برای داده‌های بسیار بزرگ مقیاس‌پذیر نیست.

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

Agglomerative Clustering

یک سلسله‌مراتب خوشه از پایین به بالا ساخته می‌شود. ابتدا هر نمونه خوشهٔ مستقلی است و در هر تکرار نزدیک‌ترین جفت خوشه به هم متصل می‌شوند. درخت حاصل یک ساختار دودویی دارد که برگ‌هایش نمونه‌های منفردند. این روش شکل‌های مختلف خوشه را می‌پذیرد، درخت خوشه‌ای انعطاف‌پذیری می‌سازد و به انتخاب یک مقیاس ثابت مجبور نیست. می‌تواند از هر Pairwise Distance استفاده کند. با یک Connectivity Matrix تنک m×m که همسایگی نمونه‌ها را مشخص می‌کند، برای تعداد نمونهٔ زیاد بهتر مقیاس می‌گیرد؛ بدون این ماتریس برای مجموعه‌های بزرگ مناسب نیست.

BIRCH

Balanced Iterative Reducing and Clustering Using Hierarchies برای داده‌های بسیار بزرگ طراحی شده و تا زمانی که تعداد ویژگی‌ها خیلی زیاد نباشد، تقریباً کمتر از ۲۰، می‌تواند از Batch k-means سریع‌تر و با نتایج مشابه باشد. در آموزش ساختاری درختی می‌سازد که فقط اطلاعات لازم برای نسبت دادن سریع نمونهٔ جدید به خوشه را نگه می‌دارد، نه همهٔ نمونه‌ها؛ بنابراین با حافظهٔ محدود دادهٔ حجیم را مدیریت می‌کند.

Mean-Shift

در ابتدا دایره‌ای حول هر نمونه قرار می‌گیرد. در هر تکرار میانگین نمونه‌های داخل هر دایره محاسبه و مرکز دایره به سمت آن میانگین جابه‌جا می‌شود. این فرایند تا توقف حرکت دایره‌ها ادامه می‌یابد و مراکز به سمت بیشینه‌های محلی چگالی حرکت می‌کنند. نمونه‌هایی که دایره‌هایشان در محل‌های یکسان یا نزدیک متوقف می‌شود در یک خوشه قرار می‌گیرند. مانند DBSCAN تعداد و شکل خوشه‌ها از پیش ثابت نیست و به تخمین چگالی محلی تکیه دارد؛ فراپارامتر اصلی آن Bandwidth یا شعاع دایره‌هاست. در مقابل، تغییرات چگالی داخل یک خوشه ممکن است آن را به چند تکه تقسیم کند و پیچیدگی O(m²n) آن برای داده‌های بزرگ مناسب نیست.

Affinity Propagation

نمونه‌ها مرتب به یکدیگر پیام می‌فرستند تا هر نمونه یک نمونهٔ دیگر یا خودش را به‌عنوان نماینده یا Exemplar انتخاب کند. هر Exemplar و نمونه‌هایی که آن را انتخاب کرده‌اند یک خوشه می‌سازند. الگوریتم معمولاً نماینده‌هایی نزدیک مرکز خوشه پیدا می‌کند، اما برخلاف k-means لازم نیست تعداد خوشه‌ها از قبل مشخص شود و می‌تواند با خوشه‌های اندازه‌های متفاوت خوب کار کند. پیچیدگی O(m²) آن مانع استفاده در داده‌های بسیار بزرگ است.

Spectral Clustering

این روش از ماتریس شباهت نمونه‌ها یک Embedding کم‌بعد می‌سازد و سپس در آن فضا الگوریتم خوشه‌بندی دیگری را اجرا می‌کند؛ پیاده‌سازی Scikit-Learn از k-means استفاده می‌کند. Spectral Clustering می‌تواند ساختارهای پیچیده را پیدا کند و برای برش Graph، مثلاً یافتن گروه دوستان در شبکهٔ اجتماعی، مناسب است؛ اما با تعداد نمونهٔ بسیار زیاد یا خوشه‌های با اندازه‌های خیلی متفاوت خوب عمل نمی‌کند.

Gaussian Mixture Models

Gaussian Mixture Model یا GMM یک مدل احتمالاتی است که فرض می‌کند نمونه‌ها از ترکیبی از چند توزیع گاوسی با پارامترهای ناشناخته تولید شده‌اند. نمونه‌های تولیدشده از یک توزیع گاوسی یک خوشه را تشکیل می‌دهند که معمولاً شکلی بیضوی دارد. خوشه‌ها می‌توانند شکل، اندازه، چگالی و جهت متفاوتی داشته باشند.

وقتی نمونه‌ای مشاهده می‌شود می‌دانیم از یکی از توزیع‌ها آمده، اما نمی‌دانیم کدام توزیع و پارامترهای آن چیست. در ساده‌ترین نوع GMM که کلاس GaussianMixture پیاده‌سازی می‌کند، تعداد k توزیع گاوسی باید از پیش مشخص باشد. فرایند احتمالاتی فرض‌شده چنین است:

• برای هر نمونه یکی از k خوشه به‌طور تصادفی انتخاب می‌شود. احتمال انتخاب خوشهٔ j برابر وزن آن خوشه ϕ(j) است و شمارهٔ خوشهٔ انتخاب‌شده برای نمونهٔ i با z(i) نمایش داده می‌شود.
• اگر نمونهٔ i به خوشهٔ j تخصیص یافته باشد، مکان x(i) از توزیع گاوسی با میانگین μ(j) و ماتریس کوواریانس Σ(j) نمونه‌برداری می‌شود: x(i) ~ N(μ(j), Σ(j)).

از روی دادهٔ X باید وزن‌های ϕ، میانگین‌های μ و کوواریانس‌های Σ تخمین زده شوند. Scikit-Learn این کار را با GaussianMixture ساده می‌کند:

from sklearn.mixture import GaussianMixture

gm = GaussianMixture(n_components=3, n_init=10)
gm.fit(X)

>>> gm.weights_
array([0.39025715, 0.40007391, 0.20966893])

>>> gm.means_
array([[ 0.05131611, 0.07521837],
       [-1.40763156, 1.42708225],
       [ 3.39893794, 1.05928897]])

>>> gm.covariances_
array([[[ 0.68799922,  0.79606357],
        [ 0.79606357,  1.21236106]],

       [[ 0.63479409,  0.72970799],
        [ 0.72970799,  1.16103510]],

       [[ 1.14833585, -0.03256179],
        [-0.03256179,  0.95490931]]])

در دادهٔ مصنوعی کتاب دو خوشه ۵۰۰ نمونه و خوشهٔ سوم ۲۵۰ نمونه دارند، بنابراین وزن‌های واقعی تقریباً ۰٫۴، ۰٫۴ و ۰٫۲ هستند؛ خروجی مدل بسیار نزدیک به این مقادیر است. میانگین‌ها و کوواریانس‌های تخمینی نیز به مقادیر واقعی نزدیک‌اند.

الگوریتم Expectation-Maximization

GaussianMixture از الگوریتم Expectation-Maximization یا EM استفاده می‌کند. این الگوریتم شباهت‌هایی با k-means دارد: پارامترهای خوشه ابتدا تصادفی مقداردهی می‌شوند و سپس تا همگرایی دو مرحله تکرار می‌شود:

1. Expectation: با پارامترهای فعلی، احتمال تعلق هر نمونه به هر خوشه تخمین زده می‌شود.
2. Maximization: پارامترهای هر خوشه با استفاده از همهٔ نمونه‌ها به‌روزرسانی می‌شوند، اما سهم هر نمونه با احتمال تعلق آن به خوشه وزن‌دهی می‌شود.

این احتمال‌ها Responsibilities خوشه‌ها نسبت به نمونه‌ها نام دارند. در مرحلهٔ Maximization هر خوشه بیشتر تحت تأثیر نمونه‌هایی است که Responsibility بالاتری برای آن‌ها دارد. می‌توان EM را تعمیمی از k-means دید که علاوه بر مرکز خوشه‌ها، اندازه، شکل، جهت و وزن نسبی آن‌ها را نیز پیدا می‌کند و به‌جای Hard Assignment از Soft Assignment استفاده می‌کند.

همگرایی و تعداد تکرارها قابل بررسی است:

>>> gm.converged_
True
>>> gm.n_iter_
4

پس از برآورد پارامترها می‌توان برای Hard Clustering از predict() و برای Soft Clustering از predict_proba() استفاده کرد:

>>> gm.predict(X)
array([0, 0, 1, ..., 2, 2, 2])

>>> gm.predict_proba(X).round(3)
array([[0.977, 0.   , 0.023],
       [0.983, 0.001, 0.016],
       [0.   , 1.   , 0.   ],
       ...,
       [0.   , 0.   , 1.   ],
       [0.   , 0.   , 1.   ],
       [0.   , 0.   , 1.   ]])

GMM یک مدل مولد است؛ یعنی می‌تواند نمونه‌های تازه نیز تولید کند. نمونه‌گیری و تخمین چگالی در مقالهٔ بعدی ادامه پیدا می‌کند.