لعنه الأبعاد

في بعض المشكلات، يمكن أن يأخذ كل متغير واحدة من عدة قيم منفصلة، أو يتم تقسيم مجموعة القيم المحتملة لإعطاء عدد محدود من الاحتمالات. عند أخذ المتغيرات معًا، يجب مراعاة عدد كبير من مجموعات القيم. يُعرف هذا التأثير أيضًا باسم الانفجار التوافقي . حتى في أبسط الحالات ${\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¹⁸ "أكبر" من وحدة الفاصلة. هذا التأثير هو مزيج من المشاكل التوافقيه المذكورة أعلاه والمسافة وظيفة المشاكل هو موضح أدناه.

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

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

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

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

${\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. . . ، ف _ن تصبح غير قابلة للفهم بالمقارنة مع الحد الأدنى للمسافة: [1]

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

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

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

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

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

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

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

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