لعنة الأبعاد

تشير لعنة الأبعاد إلى العديد من الظواهر التي تنشأ عند تحليل وتنظيم البيانات في فضاءات متعددة الأبعاد لا تحدث في البيئات منخفضة الأبعاد مثل الفضاء المادي ثلاثي الأبعاد المعتاد يومياً.

تحدث الظواهر الملعونة في مجالات مثل التحليل العددي، أخذ العينات، التوافيقيات، التعلم الآلي، استخراج البيانات وقواعد البيانات. السمة الشائعة لهذه المسائل هي أنه عندما يزداد البعد، يزداد حجم الفضاء بسرعة كبيرة بحيث تصبح البيانات المتاحة قليلة. هذا التفرقة يمثل مشكلة بالنسبة لأي طريقة تتطلب دلالة إحصائية. من أجل الحصول على نتيجة إحصائية سليمة وموثوق بها، فإن كمية البيانات اللازمة لدعم النتيجة غالبا ما تنمو باطراد مع البعد. أيضًا، يعتمد تنظيم البيانات والبحث عنها غالبًا على اكتشاف المناطق التي تشكل فيها الكائنات مجموعات لها نفس الخصائص؛ ومع ذلك، في البيانات عالية الأبعاد، تبدو جميع الكائنات متناثرة ومختلفة في نواح كثيرة، مما يمنع استراتيجيات تنظيم البيانات الشائعة من أن تكون فعالة.

المجالات

التوافقية

في بعض المسائل، يمكن أن يأخذ كل متغير واحدة من عدة قيم منفصلة، أو يتم تقسيم مجموعة القيم الممكنة لإعطاء عدد محدود من الاحتمالات. عند أخذ المتغيرات معًا، يجب مراعاة عدد كبير من مجموعات القيم. يُعرف هذا التأثير أيضًا باسم الانفجار التوافيقي. حتى في أبسط الحالات ل $d$ من المتغيرات الثنائية، يكون عدد التراكيب الممكنة بالفعل $O(2^d)$ ، أسي البعد. ببساطة، يضاعف كل بُعد إضافي الجهد اللازم لتجربة كل التراكيب .

أخذ العينات

هناك زيادة هائلة في الحجم مرتبطة بإضافة أبعاد إضافية إلى الفضاء الرياضي. على سبيل المثال، 10²=100 من نقاط العينة المتباعدة بشكل متساو تكفي لتمثيل مجال وحدة ("مكعب أحادي البعد") بمسافة لا تزيد عن 10⁻²=0.01 بين النقاط، أي ما يعادل أخذ العينات من وحدة مكعب فائق ذي 10 أبعاد مع شبيكة لها تباعد 10⁻²=0.01 بين نقطتين متجاورتين يتطلب 10²⁰=[(10²)¹⁰] نقطة عينة. بشكل عام، بمسافة تباعد تبلغ 10⁻ⁿ ، يبدو أن المكعب الفائق ذي 10 أبعاد "أكبر" بعامل 10^{n (10-1)}=[(10ⁿ)¹⁰/(10ⁿ)] من المكعب الفائق أحادي البعد، وهو الذي يمثل فترة الوحدة. في المثال أعلاه n=2: عند استخدام مسافة عينة 0.01 يبدو المكعب الفائق ذي 10 أبعاد «أكبر» بعامل 10¹⁸ من فترة الوحدة. هذا التأثير هو مزيج من المشاكل التوافقيه المذكورة أعلاه ومسائل دالة المسافة هو موضح أدناه.

الاستمثال

عند حل مشاكل التحسين الديناميكي عن طريق الاستقراء الرجعي العددي، يجب حساب الوظيفة الموضوعية لكل مجموعة من القيم. هذه عقبة كبيرة عندما يكون بُعد «متغير الحالة» كبيرًا.

التعلم الالي

في مشاكل التعلم الآلي التي تتضمن تعلم «حالة طبيعية» من عدد محدود من عينات البيانات في فضاء سمات عالي الأبعاد حيث كل سمة لها مجموعة من القيم المحتملة، عادة ما تكون هناك حاجة إلى كمية هائلة من بيانات التدريب لضمان أن هناك عدة عينات مع كل مجموعة من القيم. هناك قاعدة نموذجية تتمثل في أنه ينبغي أن يكون هناك 5 أمثلة تدريبية على الأقل لكل بُعد في التمثيل. مع وجود عدد ثابت من عينات التدريب، تزداد القوة التنبؤية لأحد المصنفين أو التراجع أولاً مع زيادة عدد الأبعاد / الميزات المستخدمة ولكن بعد ذلك تتناقص، والتي تعرف باسم ظاهرة هيوز أو الظواهر القصوى.

وظائف المسافة

عندما يتم تحديد مقياس مثل المسافة الإقليدية باستخدام العديد من الإحداثيات، هناك اختلاف بسيط في المسافات بين أزواج مختلفة من العينات.

تتمثل إحدى الطرق لتوضيح «اتساع» مساحة الإقليدية عالية الأبعاد في مقارنة نسبة منطقة فرط الغلاف المدرج بنصف القطر r والبعد d إلى نسبة فائق السرعة ذي الحواف الطولية 2r. حجم مثل هذا المجال هو$\frac{2r^d{\pi }^{d/2}}{d\mathrm{\Gamma }(d/2)}$, أين $\mathrm{\Gamma }$توجد وظيفة جاما، في حين أن حجم المكعب هو مع زيادة البعد من الفضاء، يصبح الفضاء الفائق حجمًا ضئيلًا بالنسبة إلى حجم المكعب الزائد. يمكن رؤية ذلك بوضوح من خلال مقارنة النسب حيث أن البعد يذهب إلى ما لا نهاية:

$\frac{V_{\mathrm{h}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{p}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}}}{V_{\mathrm{h}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{b}\mathrm{e}}}=\frac{{\pi }^{d/2}}{d{2}^{d-1}\mathrm{\Gamma }(d/2)}\to 0$ مثل $d\to \mathrm{\infty }$ .

وعلاوة على ذلك فإن المسافة بين المركز والزوايا هو $r\sqrt{d}$الذي يزيد من دون متجهة ثابتة r. في هذا المعنى، تقريبا كل من عالية الأبعاد الفضاء «بعيدا» من المركز. لوضع الأمر بطريقة أخرى، عالية الأبعاد وحدة المكعب الزائدي يمكن القول أن تتكون بالكامل تقريبا من «زوايا» المكعب الزائدي، مع ما يقرب من أي «الأوسط».

هذا يساعد أيضًا على فهم التوزيع التربيعي. في الواقع، يكون التوزيع التربيعي (غير المركزي) المرتبط بنقطة عشوائية في الفاصل الزمني [-1، 1] هو نفس توزيع الطول التربيعي لنقطة عشوائية في المكعب d. بموجب قانون الأعداد الكبيرة، يركز هذا التوزيع في نطاق ضيق حول d أضعاف الانحراف المعياري (σ2) للاشتقاق الأصلي. هذا ينير التوزيع التربيعي ويوضح أيضًا أن معظم حجم المكعب d يتركز بالقرب من سطح دائرة نصف قطرها

.

وهناك تطور آخر لهذه الظاهرة على النحو التالي. أي توزيع ثابت على ℝ يحفز توزيع المنتج على النقاط في ℝ ^d . للحصول على أي الثابتة ن، تبين أن الحد الأدنى والحد الأقصى للمسافة بين Q نقطة مرجعية عشوائي وقائمة ن عشوائية نقاط البيانات P _1. . . ف _ن تصبح غير قابلة للفهم بالمقارنة مع الحد الأدنى للمسافة:

$\underset{d\to \mathrm{\infty }}{lim}E(\frac{{\mathrm{d}}_{\mathrm{i}}(d)-{\mathrm{d}}_{\mathrm{i}}(d)}{{\mathrm{d}}_{\mathrm{i}}(d)})\to 0$ .

غالبًا ما يتم الاستشهاد بهذا كوظائف عن بُعد تفقد فائدتها (بالنسبة لمعيار الجوار الأقرب في خوارزميات مقارنة الميزات، على سبيل المثال) بأبعاد عالية. ومع ذلك، فقد أظهرت الأبحاث الحديثة أن هذا لا يتم إلا في السيناريو المصطنع عندما تكون التوزيعات أحادية البعد ℝ مستقلة و موزعة بشكل متطابق. عندما تكون السمات مرتبطة، يمكن أن تصبح البيانات أسهل وتوفر تباينًا أعلى للمسافة، ووجد أن نسبة الإشارة إلى الضوضاء تلعب دورًا مهمًا، وبالتالي يجب استخدام اختيار الميزة.

بحث الجار الأقرب

يعقد التأثير بحث الجار الأقرب في فضاء كثير الأبعاد. لا يمكن رفض المرشحين بسرعة باستخدام الفرق في إحداثي واحد كحد أدنى للمسافة بناءً على جميع الأبعاد.

ومع ذلك، فقد لوحظ مؤخرًا أن مجرد عدد الأبعاد لا يؤدي بالضرورة إلى صعوبات، نظرًا لأن الأبعاد الإضافية ذات الصلة يمكن أن تزيد أيضًا من التباين. بالإضافة إلى ذلك، بالنسبة للترتيب الناتج، يظل من المفيد تمييز الجيران القريبين والبعيدين. ومع ذلك، فإن الأبعاد غير ذات الصلة («الضوضاء») تقلل من التباين بالطريقة الموضحة أعلاه. في تحليل السلاسل الزمنية، حيث تكون البيانات عالية الأبعاد بطبيعتها، تعمل وظائف المسافة أيضًا بشكل موثوق طالما كانت نسبة الإشارة إلى الضوضاء مرتفعة بدرجة كافية.

ك أقرب تصنيف الجار

تأثير آخر من الأبعاد عالية على مسافة وظائف المخاوف k-أقرب جار (ك-ن ن) الرسوم البيانية التي شيدت من مجموعة البيانات باستخدام المسافة وظيفة. كما البعد يزيد، توزيع شكل ك-ن ن يصبح منحرفا مع الذروة على الحق بسبب ظهور عدد غير متناسب من المحاور ، وهذا هو، نقاط البيانات التي تظهر في العديد من ك-ن ن قوائم البيانات الأخرى نقاط من المتوسط. هذه الظاهرة يمكن أن يكون لها أثر كبير على مختلف تقنيات التصنيف (بما في ذلك <i id="mwmA">ك</i>-ن ن المصنف), شبه إشراف التعلمو المجموعات، كما أنه يؤثر على استرجاع المعلومات.

إكتشاف عيب خلقي

في دراسة حديثة، Zimek et al. تحديد المشاكل التالية عند البحث عن الشذوذ في بيانات عالية الأبعاد:

1. تركيز النقاط والمسافات: تصبح القيم المشتقة مثل المسافات متشابهة عدديًا
2. سمات غير ذات صلة: في البيانات عالية الأبعاد، قد يكون عدد كبير من السمات غير ذي صلة
3. تعريف مجموعات المراجع: بالنسبة للطرق المحلية، غالبًا ما تكون مجموعات المراجع قائمة على الجوار
4. درجات لا تضاهى للأبعاد المختلفة: تنتج المساحات الفرعية المختلفة درجات لا تضاهى
5. قابلية تفسير النتائج: في الغالب، لم تعد النتائج تنقل معنى دلاليًا
6. مساحة البحث الأسية: لم يعد من الممكن مسح مساحة البحث بشكل منهجي
7. تحسس البيانات المتطفل: بالنظر إلى مساحة البحث الكبيرة، يمكن العثور على فرضية لكل دلالة مطلوبة
8. محور نيس: كائنات معينة تحدث بشكل متكرر في قوائم الجوار أكثر من غيرها.

تعالج العديد من الطرق المتخصصة التي تم تحليلها مشكلة أو أخرى من هذه المسائل، ولكن لا يزال هناك العديد من الأسئلة البحثية المفتوحة.