.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "auto_examples/miscellaneous/plot_johnson_lindenstrauss_bound.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. or to run this example in your browser via JupyterLite or Binder .. rst-class:: sphx-glr-example-title .. _sphx_glr_auto_examples_miscellaneous_plot_johnson_lindenstrauss_bound.py: ===================================================================== حدود جونسون-ليندستراوس للانغماس مع الإسقاطات العشوائية ===================================================================== تنص مبرهنة جونسون-ليندستراوس على أنه يمكن إسقاط أي مجموعة بيانات ذات أبعاد عالية بشكل عشوائي إلى فضاء إقليدي ذي أبعاد أقل مع التحكم في التشوه في المسافات الزوجية. .. _`Johnson-Lindenstrauss lemma`: https://en.wikipedia.org/wiki/ Johnson%E2%80%93Lindenstrauss_lemma .. GENERATED FROM PYTHON SOURCE LINES 12-28 .. code-block:: Python # المؤلفون: مطوري سكايت-ليرن # معرف الترخيص: BSD-3-Clause import sys from time import time import matplotlib.pyplot as plt import numpy as np from sklearn.datasets import fetch_20newsgroups_vectorized, load_digits from sklearn.metrics.pairwise import euclidean_distances from sklearn.random_projection import ( SparseRandomProjection, johnson_lindenstrauss_min_dim ) .. GENERATED FROM PYTHON SOURCE LINES 29-52 الحدود النظرية ================== التشوه الذي يسببه الإسقاط العشوائي 'p' يتم تأكيده من خلال حقيقة أن 'p' تحدد غرس eps مع احتمال جيد كما هو محدد بواسطة: .. math:: (1 - eps) \|u - v\|^2 < \|p(u) - p(v)\|^2 < (1 + eps) \|u - v\|^2 حيث 'u' و 'v' هما أي صفين مأخوذين من مجموعة بيانات ذات شكل (n_samples، n_features) و 'p' هو إسقاط بواسطة مصفوفة غاوسية عشوائية 'N(0, 1)' ذات شكل (n_components، n_features) (أو مصفوفة Achlioptas نادرة). الحد الأدنى لعدد المكونات لضمان غرس eps هو معطى بواسطة: .. math:: n\_components \geq 4 log(n\_samples) / (eps^2 / 2 - eps^3 / 3) يظهر المخطط الأول أنه مع زيادة عدد العينات "n_samples"، يزداد الحد الأدنى لعدد الأبعاد "n_components" بشكل لوغاريتمي لضمان غرس "eps". .. GENERATED FROM PYTHON SOURCE LINES 52-72 .. code-block:: Python # نطاق التشوهات المسموح بها eps_range = np.linspace(0.1, 0.99, 5) colors = plt.cm.Blues(np.linspace(0.3, 1.0, len(eps_range))) # نطاق عدد العينات (الملاحظة) لإدراجها n_samples_range = np.logspace(1, 9, 9) plt.figure() for eps, color in zip(eps_range, colors): min_n_components = johnson_lindenstrauss_min_dim(n_samples_range, eps=eps) plt.loglog(n_samples_range, min_n_components, color=color) plt.legend([f"eps = {eps:0.1f}" for eps in eps_range], loc="lower right") plt.xlabel("عدد الملاحظات لإدراجها") plt.ylabel("الحد الأدنى لعدد الأبعاد") plt.title("حدود جونسون-ليندستراوس:\nn_samples مقابل n_components") plt.show() .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_001.png :alt: حدود جونسون-ليندستراوس: n_samples مقابل n_components :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 73-76 يظهر المخطط الثاني أنه مع زيادة التشوه المسموح به "eps" يسمح بخفض الحد الأدنى بشكل كبير عدد الأبعاد "n_components" لعدد معين من العينات "n_samples" .. GENERATED FROM PYTHON SOURCE LINES 76-95 .. code-block:: Python # نطاق التشوهات المسموح بها eps_range = np.linspace(0.01, 0.99, 100) # نطاق عدد العينات (الملاحظة) لإدراجها n_samples_range = np.logspace(2, 6, 5) الألوان = plt.cm.Blues(np.linspace(0.3, 1.0, len(n_samples_range))) plt.figure() for n_samples, color in zip(n_samples_range, colors): min_n_components = johnson_lindenstrauss_min_dim(n_samples, eps=eps_range) plt.semilogy(eps_range, min_n_components, color=color) plt.legend([f"n_samples = {n}" for n in n_samples_range], loc="upper right") plt.xlabel("التشوه eps") plt.ylabel("الحد الأدنى لعدد الأبعاد") plt.title("حدود جونسون-ليندستراوس:\nn_components مقابل eps") plt.show() .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_002.png :alt: حدود جونسون-ليندستراوس: n_components مقابل eps :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_002.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 96-114 التحقق التجريبي ==================== نتحقق من الحدود أعلاه على مجموعة بيانات وثائق الأخبار العشرين (ترددات الكلمات TF-IDF) أو على مجموعة بيانات الأرقام: - لمجموعة بيانات الأخبار العشرين، يتم إسقاط بعض الوثائق 300 الميزات في المجموع باستخدام مصفوفة عشوائية نادرة إلى مساحات إقليدية أصغر مع قيم مختلفة للعدد المستهدف من الأبعاد "n_components". - لمجموعة بيانات الأرقام، يتم إسقاط بعض بيانات البكسل بمستوى رمادي 8x8 لصور 300 أرقام مكتوبة بخط اليد بشكل عشوائي إلى مساحات لمختلف عدد أكبر من الأبعاد "n_components". مجموعة البيانات الافتراضية هي مجموعة بيانات الأخبار العشرين. لتشغيل المثال على مجموعة بيانات الأرقام، قم بتمرير حجة سطر الأوامر "use-digits-dataset" إلى هذا البرنامج النصي. .. GENERATED FROM PYTHON SOURCE LINES 114-120 .. code-block:: Python if "--use-digits-dataset" in sys.argv: data = load_digits().data[:300] else: data = fetch_20newsgroups_vectorized().data[:300] .. GENERATED FROM PYTHON SOURCE LINES 121-127 لكل قيمة من "n_components"، نحن نرسم: - توزيع ثنائي الأبعاد لأزواج العينات مع المسافات الزوجية في المساحات الأصلية والمشروعة كمحور سيني ومحور صادي على التوالي. - مخطط ترددي أحادي البعد لنسبة تلك المسافات (مشروعة / أصلية). .. GENERATED FROM PYTHON SOURCE LINES 127-187 .. code-block:: Python n_samples, n_features = data.shape print( f"Embedding {n_samples} samples with dim {n_features} using various " "random projections" ) n_components_range = np.array([300, 1_000, 10_000]) dists = euclidean_distances(data, squared=True).ravel() # حدد فقط أزواج العينات غير المتطابقة nonzero = dists != 0 dists = dists[nonzero] for n_components in n_components_range: t0 = time() rp = SparseRandomProjection(n_components=n_components) projected_data = rp.fit_transform(data) print( f"Projected {n_samples} samples from {n_features} to {n_components} in " f"{time() - t0:0.3f}s" ) if hasattr(rp, "components_"): n_bytes = rp.components_.data.nbytes n_bytes += rp.components_.indices.nbytes print(f"Random matrix with size: {n_bytes / 1e6:0.3f} MB") projected_dists = euclidean_distances(projected_data, squared=True).ravel()[nonzero] plt.figure() min_dist = min(projected_dists.min(), dists.min()) max_dist = max(projected_dists.max(), dists.max()) plt.hexbin( dists, projected_dists, gridsize=100, cmap=plt.cm.PuBu, extent=[min_dist, max_dist, min_dist, max_dist], ) plt.xlabel("المسافات الزوجية المربعة في المساحة الأصلية") plt.ylabel("المسافات الزوجية المربعة في المساحة المشروعة") plt.title("توزيع المسافات الزوجية لـ n_components=%d" % n_components) cb = plt.colorbar() cb.set_label("عدد أزواج العينات") rates = projected_dists / dists print(f"Mean distances rate: {np.mean(rates):.2f} ({np.std(rates):.2f})") plt.figure() plt.hist(rates, bins=50, range=(0.0, 2.0), edgecolor="k", density=True) plt.xlabel("معدل المسافات المربعة: مشروعة / أصلية") plt.ylabel("توزيع أزواج العينات") plt.title("مخطط ترددي للمسافات الزوجية لـ n_components=%d" % n_components) # TODO: حساب القيمة المتوقعة لـ eps وإضافتها إلى المخطط السابق # كخطوط عمودية / منطقة plt.show() .. rst-class:: sphx-glr-horizontal * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_003.png :alt: توزيع المسافات الزوجية لـ n_components=300 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_003.png :class: sphx-glr-multi-img * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_004.png :alt: مخطط ترددي للمسافات الزوجية لـ n_components=300 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_004.png :class: sphx-glr-multi-img * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_005.png :alt: توزيع المسافات الزوجية لـ n_components=1000 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_005.png :class: sphx-glr-multi-img * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_006.png :alt: مخطط ترددي للمسافات الزوجية لـ n_components=1000 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_006.png :class: sphx-glr-multi-img * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_007.png :alt: توزيع المسافات الزوجية لـ n_components=10000 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_007.png :class: sphx-glr-multi-img * .. image-sg:: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_008.png :alt: مخطط ترددي للمسافات الزوجية لـ n_components=10000 :srcset: /auto_examples/miscellaneous/images/sphx_glr_plot_johnson_lindenstrauss_bound_008.png :class: sphx-glr-multi-img .. rst-class:: sphx-glr-script-out .. code-block:: none Embedding 300 samples with dim 130107 using various random projections Projected 300 samples from 130107 to 300 in 0.387s Random matrix with size: 1.296 MB Mean distances rate: 1.17 (0.23) Projected 300 samples from 130107 to 1000 in 1.248s Random matrix with size: 4.313 MB Mean distances rate: 1.02 (0.10) Projected 300 samples from 130107 to 10000 in 12.371s Random matrix with size: 43.275 MB Mean distances rate: 1.01 (0.03) .. GENERATED FROM PYTHON SOURCE LINES 188-207 يمكننا أن نرى أنه بالنسبة للقيم المنخفضة من "n_components" التوزيع واسع مع العديد من الأزواج المشوهة وتوزيع منحرف (بسبب الحد الصلب نسبة الصفر على اليسار حيث تكون المسافات دائمًا إيجابية) في حين أنه بالنسبة للقيم الأكبر من 'n_components' يتم التحكم في التشوه وتحفظ المسافات جيدًا بواسطة الإسقاط العشوائي. ملاحظات ======= وفقًا لمبرهنة JL، سيتطلب إسقاط 300 عينة بدون تشوه كبير سيتطلب ذلك الآلاف من الأبعاد، بغض النظر عن عدد ميزات مجموعة البيانات الأصلية. وبالتالي، لا معنى لاستخدام الإسقاطات العشوائية على مجموعة بيانات الأرقام التي تحتوي فقط على 64 الميزات في مساحة الإدخال: لا تسمح تقليل الأبعاد في هذه الحالة. على مجموعة الأخبار العشرين من ناحية أخرى، يمكن تقليل الأبعاد من 56,436 إلى 10,000 مع الحفاظ بشكل معقول على المسافات الزوجية. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 18.355 seconds) .. _sphx_glr_download_auto_examples_miscellaneous_plot_johnson_lindenstrauss_bound.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: binder-badge .. image:: images/binder_badge_logo.svg :target: https://mybinder.org/v2/gh/scikit-learn/scikit-learn/main?urlpath=lab/tree/notebooks/auto_examples/miscellaneous/plot_johnson_lindenstrauss_bound.ipynb :alt: Launch binder :width: 150 px .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../lite/lab/index.html?path=auto_examples/miscellaneous/plot_johnson_lindenstrauss_bound.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_johnson_lindenstrauss_bound.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_johnson_lindenstrauss_bound.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_johnson_lindenstrauss_bound.zip ` .. include:: plot_johnson_lindenstrauss_bound.recommendations .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_