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

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

المجالات

التوافقية

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

أخذ العينات

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

الاقوي

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

التفهم الالي

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

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

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

تتمثل إحدى الطرق لتوضيح "اتساع" مساحة الإقليدية عالية الأبعاد في مقارنة نسبة منطقة فرط الغلاف المدرج بنصف القطر r والبعد d إلى نسبة فائق السرعة ذي الحواف الطولية 2r. حجم مثل هذا المجال هو${\displaystyle \frac{2r^d{\mathrm{\pi <!--\; \pi \; -->}}^{d/2}}{d\mathrm{\Gamma <!--\; \Gamma \; -->}(d/2)}}$

${\displaystyle {\frac {V_{\mathrm {hypersphere {V_{\mathrm {hypercube ={\frac {\pi ^{d/2 {d2^{d-1 \Gamma (d/2) \rightarrow 0$ مثل ${\displaystyle d\rightarrow \infty$ .

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

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

.

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

${\displaystyle \lim _{d\to \infty E\left({\frac {\operatorname {dist _{\max (d)-\operatorname {dist _{\min (d) {\operatorname {dist _{\min (d) \right)\to 0$ .

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

أقرب درس جار

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

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

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

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

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

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

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

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

انظر أيضا

معادلة بيلمان

تجميع البيانات عالية الأبعاد

هجريز التدبير

تخفيض البعد

نموذج طلب الحد

البرمجة الديناميكية

تحويلات فورييه ذات الصلة

أقل المربعات الخطية

متعدد الخطوط PCA

متعدد الفضاء التفهم الفرعي

تحليل المكون الرئيسي

تحلل القيمة المفرد

المراجع