انتخاب تعداد مناسب ابعاد در PCA

در مثال قبلی حدود ۷۶٪ واریانس داده روی مؤلفهٔ اصلی اول و حدود ۱۵٪ روی مؤلفهٔ دوم قرار داشت و تقریباً ۹٪ برای مؤلفهٔ سوم باقی می‌ماند. به‌جای اینکه تعداد ابعاد نهایی را به‌صورت دلخواه انتخاب کنیم، معمولاً بهتر است کمترین تعداد مؤلفه‌ای را انتخاب کنیم که روی‌هم سهم کافی از واریانس، مثلاً ۹۵٪، را حفظ کنند. استثنا زمانی است که هدف بصری‌سازی باشد؛ در آن حالت معمولاً می‌خواهیم داده را به دو یا سه بُعد کاهش دهیم.

کد زیر MNIST را بارگذاری و به آموزش و آزمون تقسیم می‌کند، سپس PCA را بدون کاهش ابعاد Fit می‌کند و حداقل تعداد مؤلفه‌های لازم برای حفظ ۹۵٪ واریانس را محاسبه می‌کند:

from sklearn.datasets import fetch_openml

mnist = fetch_openml('mnist_784', as_frame=False)
X_train, y_train = mnist.data[:60_000], mnist.target[:60_000]
X_test, y_test = mnist.data[60_000:], mnist.target[60_000:]

pca = PCA()
pca.fit(X_train)
cumsum = np.cumsum(pca.explained_variance_ratio_)
d = np.argmax(cumsum >= 0.95) + 1  # d equals 154

می‌توان مقدار به‌دست‌آمدهٔ d=154 را مستقیماً به n_components داد، اما Scikit-Learn راه ساده‌تری دارد: اگر n_components را یک عدد اعشاری بین صفر و یک قرار دهید، این مقدار به‌عنوان نسبت واریانس مورد نظر تفسیر می‌شود.

pca = PCA(n_components=0.95)
X_reduced = pca.fit_transform(X_train)

>>> pca.n_components_
154

راه دیگر رسم مجموع تجمعی واریانس توضیح‌داده‌شده برحسب تعداد ابعاد است. منحنی معمولاً یک نقطهٔ خم یا Elbow دارد که از آن به بعد افزودن مؤلفه‌های بیشتر افزایش واریانس توضیح‌داده‌شده را کند می‌کند. در مثال MNIST، شکل ۸-۸ نشان می‌دهد که کاهش به حدود ۱۰۰ بُعد نیز بخش زیادی از واریانس را حفظ می‌کند.

تنظیم تعداد مؤلفه‌ها همراه مدل نهایی

اگر کاهش ابعاد مرحلهٔ Preprocessing یک مسئلهٔ نظارت‌شده مانند طبقه‌بندی باشد، تعداد ابعاد را می‌توان درست مانند هر فراپارامتر دیگری تنظیم کرد. مثال زیر یک Pipeline دو مرحله‌ای می‌سازد: نخست PCA و سپس Random Forest؛ بعد RandomizedSearchCV ترکیب مناسبی از تعداد مؤلفه‌های PCA و تعداد درخت‌های جنگل را جست‌وجو می‌کند.

from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import RandomizedSearchCV
from sklearn.pipeline import make_pipeline

clf = make_pipeline(
    PCA(random_state=42),
    RandomForestClassifier(random_state=42)
)
param_distrib = {
    "pca__n_components": np.arange(10, 80),
    "randomforestclassifier__n_estimators": np.arange(50, 500)
}
rnd_search = RandomizedSearchCV(
    clf, param_distrib, n_iter=10, cv=3, random_state=42
)
rnd_search.fit(X_train[:1000], y_train[:1000])

>>> print(rnd_search.best_params_)
{'randomforestclassifier__n_estimators': 465,
 'pca__n_components': 23}

در این جست‌وجوی سریع، دادهٔ ۷۸۴بعدی به تنها ۲۳ بُعد کاهش یافت. دلیل مهم این نتیجه قدرت زیاد Random Forest است. اگر به‌جای آن یک مدل خطی مانند SGDClassifier به کار رود، جست‌وجو معمولاً تعداد بیشتری مؤلفه، در حدود ۷۰، را لازم می‌داند.

PCA برای فشرده‌سازی

پس از کاهش ابعاد، مجموعهٔ آموزشی فضای بسیار کمتری اشغال می‌کند. در MNIST با حفظ ۹۵٪ واریانس، تعداد ویژگی‌ها از ۷۸۴ به ۱۵۴ کاهش می‌یابد؛ یعنی اندازهٔ نمایش داده کمتر از ۲۰٪ حالت اولیه می‌شود، در حالی که فقط ۵٪ واریانس کنار گذاشته شده است. چنین فشرده‌سازی‌ای می‌تواند الگوریتم طبقه‌بندی را به‌شکل محسوسی سریع‌تر کند.

می‌توان دادهٔ کاهش‌یافته را با تبدیل معکوس دوباره به ۷۸۴ بُعد برگرداند. خروجی دقیقاً برابر دادهٔ اصلی نیست، زیرا در فرافکنی بخشی از اطلاعات حذف شده است، اما معمولاً به آن نزدیک است. میانگین فاصلهٔ مربعی بین دادهٔ اصلی و دادهٔ بازسازی‌شده خطای بازسازی نام دارد.

X_recovered = pca.inverse_transform(X_reduced)

شکل ۸-۹ چند رقم اصلی را در سمت چپ و نسخه‌های فشرده و سپس بازسازی‌شدهٔ آن‌ها را در سمت راست نشان می‌دهد. افت کیفیت کمی وجود دارد، اما شکل ارقام عمدتاً حفظ شده است.

Randomized PCA

اگر فراپارامتر svd_solver="randomized" باشد، Scikit-Learn از الگوریتم تصادفی Randomized PCA استفاده می‌کند که تقریبی سریع از نخستین d مؤلفهٔ اصلی به دست می‌آورد. پیچیدگی آن تقریباً O(m × d²) + O(d³) است، در حالی که SVD کامل حدود O(m × n²) + O(n³) هزینه دارد؛ بنابراین وقتی d بسیار کوچک‌تر از n باشد روش تصادفی بسیار سریع‌تر است.

rnd_pca = PCA(
    n_components=154,
    svd_solver="randomized",
    random_state=42
)
X_reduced = rnd_pca.fit_transform(X_train)

Incremental PCA

پیاده‌سازی‌های معمول PCA برای Fit شدن به کل مجموعهٔ آموزشی در حافظه نیاز دارند. Incremental PCA یا IPCA اجازه می‌دهد داده به Mini-Batch تقسیم و هر بخش جداگانه وارد الگوریتم شود. این ویژگی هم برای مجموعه‌های بزرگ و هم برای PCA آنلاین، یعنی پردازش نمونه‌ها هنگام ورود، مفید است.

کد زیر MNIST را به ۱۰۰ Mini-Batch تقسیم می‌کند و با partial_fit() به IncrementalPCA می‌دهد:

from sklearn.decomposition import IncrementalPCA

n_batches = 100
inc_pca = IncrementalPCA(n_components=154)
for X_batch in np.array_split(X_train, n_batches):
    inc_pca.partial_fit(X_batch)

X_reduced = inc_pca.transform(X_train)

راه دیگر استفاده از np.memmap است. این کلاس آرایهٔ بزرگی را در یک فایل دودویی روی دیسک نگه می‌دارد و آن را مانند آرایه‌ای در حافظه در اختیار برنامه می‌گذارد، اما فقط بخش مورد نیاز را در زمان لازم وارد RAM می‌کند.

filename = "my_mnist.mmap"
X_mmap = np.memmap(
    filename,
    dtype='float32',
    mode='write',
    shape=X_train.shape
)
X_mmap[:] = X_train  # in practice this could be written chunk by chunk
X_mmap.flush()

سپس فایل memory-mapped را دوباره باز می‌کنیم و با توجه به اینکه IPCA هر بار بخش کوچکی را می‌خواند، می‌توان حتی fit() معمولی را به کار برد:

X_mmap = np.memmap(
    filename,
    dtype="float32",
    mode="readonly"
).reshape(-1, 784)

batch_size = X_mmap.shape[0] // n_batches
inc_pca = IncrementalPCA(
    n_components=154,
    batch_size=batch_size
)
inc_pca.fit(X_mmap)

برای داده‌های بسیار پُربعد حتی Randomized PCA نیز ممکن است کند باشد، زیرا پیچیدگی آن همچنان به d² و d³ وابسته است. اگر ده‌ها هزار ویژگی یا بیشتر دارید، مثلاً در داده‌های تصویری، Random Projection می‌تواند گزینهٔ مناسب‌تری باشد.

Random Projection

Random Projection داده را با یک فرافکنی خطی تصادفی به فضای کم‌بعد می‌برد. در نگاه نخست عجیب به نظر می‌رسد، اما لم مشهور Johnson–Lindenstrauss نشان می‌دهد که یک فرافکنی تصادفی با احتمال زیاد فاصله‌ها را تا حد خوبی حفظ می‌کند. بنابراین نمونه‌های مشابه بعد از تبدیل همچنان نزدیک می‌مانند و نمونه‌های بسیار متفاوت نیز همچنان از هم دور خواهند بود.

هرچه ابعاد بیشتری حذف شود، اطلاعات بیشتر از دست می‌رود و فاصله‌ها بیشتر اعوجاج پیدا می‌کنند. Johnson و Lindenstrauss حداقلی برای تعداد ابعاد ارائه کردند که با احتمال زیاد تضمین می‌کند فاصله‌ها بیش از یک تلورانس مشخص تغییر نکنند. اگر m=5,000 نمونه، n=20,000 ویژگی و ε=10% داشته باشیم، باید داده را حداقل به ابعاد زیر ببریم:

برای این مثال مقدار d برابر ۷۳۰۰ است. نکتهٔ مهم این است که فرمول به n وابسته نیست و فقط به تعداد نمونه‌ها m و تلورانس ε بستگی دارد.

>>> from sklearn.random_projection import johnson_lindenstrauss_min_dim
>>> m, ε = 5_000, 0.1
>>> d = johnson_lindenstrauss_min_dim(m, eps=ε)
>>> d
7300

سپس می‌توان ماتریس تصادفی P با Shape برابر [d,n] ساخت؛ هر عنصر از توزیع گاوسی با میانگین صفر و واریانس 1/d نمونه‌برداری می‌شود:

n = 20_000
np.random.seed(42)
P = np.random.randn(d, n) / np.sqrt(d)

X = np.random.randn(m, n)  # generate a fake dataset
X_reduced = X @ P.T

این روش به آموزش واقعی روی مقدار داده نیاز ندارد؛ برای ساخت ماتریس تصادفی فقط Shape مجموعه لازم است.

GaussianRandomProjection و SparseRandomProjection

GaussianRandomProjection همین فرایند را انجام می‌دهد. هنگام fit() از johnson_lindenstrauss_min_dim() برای تعیین بُعد خروجی استفاده می‌کند، ماتریس تصادفی را در components_ می‌سازد و هنگام transform() فرافکنی را انجام می‌دهد. eps مقدار ε را کنترل می‌کند و با n_components می‌توان d را به‌طور صریح تعیین کرد.

from sklearn.random_projection import GaussianRandomProjection

gaussian_rnd_proj = GaussianRandomProjection(
    eps=ε,
    random_state=42
)
X_reduced = gaussian_rnd_proj.fit_transform(X)

Scikit-Learn همچنین SparseRandomProjection را دارد. تفاوت مهم آن این است که ماتریس تصادفی تنک است. در مثال کتاب، حافظهٔ مورد نیاز از نزدیک ۱٫۲ گیگابایت به حدود ۲۵ مگابایت کاهش می‌یابد و تولید ماتریس و کاهش ابعاد تقریباً ۵۰٪ سریع‌تر می‌شود. اگر ورودی تنک باشد، خروجی نیز تنک باقی می‌ماند، مگر اینکه dense_output=True تعیین شود. کیفیت حفظ فاصله‌ها مشابه روش گاوسی است و برای داده‌های بزرگ یا تنک معمولاً انتخاب بهتری است.

نسبت عناصر ناصفر ماتریس تنک، Density یا r نام دارد و مقدار پیش‌فرض آن 1/√n است. با ۲۰٬۰۰۰ ویژگی تقریباً فقط یک سلول از هر ۱۴۱ سلول ناصفر خواهد بود. هر سلول با احتمال r ناصفر می‌شود و مقدار ناصفر با احتمال مساوی −v یا +v است، که در آن v = 1/√(d r).

برای تبدیل معکوس باید شبه‌معکوس ماتریس مؤلفه‌ها را محاسبه کرد:

components_pinv = np.linalg.pinv(
    gaussian_rnd_proj.components_
)
X_recovered = X_reduced @ components_pinv.T

در مجموع Random Projection روشی ساده، سریع، کم‌حافظه و به‌طور شگفت‌آوری قدرتمند است، به‌خصوص برای داده‌های با ابعاد بسیار زیاد.

LLE؛ Locally Linear Embedding

LLE یک روش غیرخطی کاهش ابعاد و از خانوادهٔ Manifold Learning است که برخلاف PCA و Random Projection به فرافکنی خطی متکی نیست. ایده این است که ابتدا رابطهٔ خطی هر نمونه با نزدیک‌ترین همسایگانش اندازه‌گیری شود و سپس نمایش کم‌بعدی‌ای پیدا شود که این روابط محلی را تا حد ممکن حفظ کند. به همین دلیل LLE برای باز کردن منیفلدهای پیچیده، به‌ویژه با نویز کم، مناسب است.

from sklearn.datasets import make_swiss_roll
from sklearn.manifold import LocallyLinearEmbedding

X_swiss, t = make_swiss_roll(
    n_samples=1000,
    noise=0.2,
    random_state=42
)
lle = LocallyLinearEmbedding(
    n_components=2,
    n_neighbors=10,
    random_state=42
)
X_unrolled = lle.fit_transform(X_swiss)

متغیر t موقعیت هر نمونه را روی محور رول‌شدهٔ Swiss Roll نگه می‌دارد و در این مثال استفاده نمی‌شود؛ اما می‌تواند Target یک مسئلهٔ رگرسیون غیرخطی باشد. شکل ۸-۱۰ خروجی را نشان می‌دهد: رول کاملاً باز شده و فاصله‌های محلی نسبتاً خوب حفظ شده‌اند، هرچند ساختار فاصله‌ای در مقیاس بزرگ به‌طور کامل حفظ نشده است.

دو مرحلهٔ بهینه‌سازی LLE

برای هر نمونهٔ x(i)، الگوریتم k نزدیک‌ترین همسایه را پیدا می‌کند و تلاش می‌کند خود نمونه را به‌صورت ترکیب خطی همسایه‌ها بازسازی کند. وزن‌های w(i,j) طوری انتخاب می‌شوند که خطای بازسازی مربعی کمینه شود؛ اگر نمونهٔ j جزو k همسایهٔ نزدیک i نباشد وزن آن صفر است و مجموع وزن‌های هر نمونه برابر یک می‌شود.

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

پیچیدگی پیاده‌سازی Scikit-Learn برای یافتن همسایه‌ها تقریباً O(m log(m) n log(k))، برای بهینه‌سازی وزن‌ها O(m n k³) و برای ساخت نمایش کم‌بعدی O(d m²) است. وجود m² در مرحلهٔ آخر باعث می‌شود LLE برای مجموعه‌داده‌های بسیار بزرگ مقیاس‌پذیری خوبی نداشته باشد. بااین‌حال در دادهٔ غیرخطی می‌تواند نمایش‌هایی بسیار بهتر از روش‌های Projection بسازد.

روش‌های دیگر کاهش ابعاد

sklearn.manifold.MDS

Multidimensional Scaling هنگام کاهش ابعاد تلاش می‌کند فاصلهٔ بین نمونه‌ها را حفظ کند. Random Projection برای دادهٔ پُربعد همین هدف را دنبال می‌کند، اما MDS برای دادهٔ کم‌بعد مناسب‌تر است.

sklearn.manifold.Isomap

Isomap با اتصال هر نمونه به نزدیک‌ترین همسایه‌هایش یک Graph می‌سازد و هنگام کاهش ابعاد فاصله‌های ژئودزیک روی Graph را حفظ می‌کند؛ یعنی فاصله‌ای که از کوتاه‌ترین مسیر بین گره‌ها حاصل می‌شود.

sklearn.manifold.TSNE

t-SNE تلاش می‌کند نمونه‌های مشابه نزدیک و نمونه‌های متفاوت دور بمانند. کاربرد اصلی آن بصری‌سازی خوشه‌های داده‌های پُربعد است؛ در تمرین‌های این فصل از آن برای نقشهٔ دوبعدی MNIST استفاده می‌شود.

sklearn.discriminant_analysis.LinearDiscriminantAnalysis

LDA یک الگوریتم خطی طبقه‌بندی است که در زمان آموزش محورهایی را یاد می‌گیرد که بیشترین تمایز را میان کلاس‌ها ایجاد می‌کنند. سپس می‌توان داده را روی ابرصفحهٔ ساخته‌شده از این محورها فرافکنی کرد تا کلاس‌ها تا حد ممکن از هم جدا بمانند. بنابراین LDA می‌تواند پیش از یک طبقه‌بند دیگر به‌عنوان کاهش ابعاد استفاده شود، مگر آنکه خود LDA برای مسئله کافی باشد.

شکل ۸-۱۱ خروجی MDS، Isomap و t-SNE را روی Swiss Roll مقایسه می‌کند. MDS رول را بدون حذف انحنای کلی صاف می‌کند، Isomap انحنای کلی را از بین می‌برد و t-SNE ضمن صاف‌کردن نسبی، خوشه‌ها را برجسته و بخش‌هایی از رول را از هم جدا می‌کند. اینکه حفظ یا حذف ساختار بزرگ‌مقیاس مفید باشد به مسئلهٔ بعدی بستگی دارد.

تمرین‌های فصل ۸

1. انگیزه‌های اصلی کاهش ابعاد یک مجموعهٔ داده چیست؟ معایب اصلی آن کدام‌اند؟
2. نفرین ابعاد چیست؟
3. پس از کاهش ابعاد، آیا می‌توان عملیات را معکوس کرد؟ اگر بله چگونه، و اگر نه چرا؟
4. آیا می‌توان از PCA برای کاهش ابعاد یک مجموعهٔ بسیار غیرخطی استفاده کرد؟
5. فرض کنید PCA را روی مجموعه‌ای ۱۰۰۰بعدی با نسبت واریانس توضیح‌داده‌شدهٔ ۹۵٪ اجرا می‌کنید. خروجی چند بُعد خواهد داشت؟
6. در چه شرایطی از PCA معمولی، Incremental PCA، Randomized PCA یا Random Projection استفاده می‌کنید؟
7. چگونه عملکرد یک الگوریتم کاهش ابعاد را روی دادهٔ خود ارزیابی می‌کنید؟
8. آیا زنجیره‌کردن دو الگوریتم متفاوت کاهش ابعاد منطقی است؟
9. MNIST را به ۶۰٬۰۰۰ نمونهٔ آموزش و ۱۰٬۰۰۰ نمونهٔ آزمون تقسیم کنید. Random Forest را روی دادهٔ اصلی آموزش دهید، زمان آموزش و عملکرد آزمون را ثبت کنید. سپس PCA با حفظ ۹۵٪ واریانس اجرا کرده و یک Random Forest جدید روی دادهٔ کاهش‌یافته بسازید. زمان و عملکرد را مقایسه کنید. آزمایش را با SGDClassifier نیز تکرار کنید و بررسی کنید PCA در این حالت چقدر کمک می‌کند.
10. با t-SNE نخستین ۵۰۰۰ تصویر MNIST را به دو بُعد کاهش دهید و با Matplotlib رسم کنید. می‌توانید برای ۱۰ کلاس از رنگ‌های متفاوت استفاده کنید، یا به‌جای نقطه رقم کلاس ۰ تا ۹ را بنویسید، یا نمونه‌ای از تصاویر کوچک‌شده را رسم کنید. برای جلوگیری از شلوغی، نمونه‌برداری کنید یا تنها زمانی تصویری را بکشید که نمونهٔ بسیار نزدیک قبلاً رسم نشده باشد. سپس PCA، LLE یا MDS را نیز آزمایش و بصری‌سازی‌ها را مقایسه کنید.

راه‌حل تمرین‌ها در Notebook انتهای فصل کتاب ارائه شده است: https://homl.info/colab3.