Проклятие на размерността

Проклятието на размерността (на английски: curse of dimensionality) се отнася до различни явления, които се наблюдават при анализирането и организирането на данни в многомерни пространства, които явления не се проявяват в по-малко на брой размерности. Терминът е въведен от Ричард Белман в негов труд, дискутиращ проблемите на динамичното програмиране.

Проклятие на размерността се наблюдава в проблеми от областите числен анализ, комбинаторика, машинно обучение, извличане на знания от данни (data mining), управление на бази данни. Общото в тези проблеми е, че с нарастването на размерността, обемът на пространството нараства толкова бързо, че наличните данни се оказват "разредени" (sparse), а разредеността е проблем за всеки метод, който изисква статистическа значимост, за да бъде надежден. За получаването на статистически коректен и достоверен резултат, количеството данни, необходими за подкрепяне на резултата, често нарастват експоненциално с нарастване на размерността. Също така, организирането на данните и търсенето в тях често зависи от откриването на области, в които обектите се групират по сходни свойства; в условията на многомерни данни обаче всички обекти изглеждат "разредени" и разнородни помежду си, което ограничава ефективността на обичайните стратегии за организиране на данните.

Области

Комбинаторика

В някои задачи всяка променлива може да приеме една от няколко дискретни стойности или областта на допустимите стойности се разделя, за да се получат краен брой възможности. Когато се вземат всички промениливи заедно, трябва да бъде разгледан огромен брой възможни комбинации от стойностите им – ефект известен и като комбинаторен взрив (combinatorial explosion). Дори в най-простия случай на ${\displaystyle d}$ двоични променливи, броят възможни комбинации вече е ${\displaystyle 2^{d}}$, експоненциално спрямо размерността. Най-просто казано, добавянето на нова размерност удвоява усилието, необходимо да се проверят всички комбинации.

Откриване на аномалии

В едно свое проучване от 2012 г. Zimek et al. идентифицират следните проблеми при търсенето на аномалзии в многомерни данни:

• Концентрация на стойности и мерки: откритите стойности, например разстояния, са числово сходни.
• Нерелевантни атрибути: в многомерните данни, голям брой атрибути на данните могат да останат неизползваеми.
• Дефиниране на референтни множества: за локалните методи референтните множества често са базирани на най-близкия съсед.
• Несъпоставими стойности по различине размерности: различните подпространства генерират несъпоставими стойности.
• Интерпретируемост на стойностите: стойностите често не съдържат никаква семантика
• Експоненциално търсене: пространството на търсене вече не може систематично да бъде претърсвано.
• Data snooping bias (ловуване на данни): предвид огромното пространство на търсене, за всяка желана статистическа значимост може да се открие подходяща хипотеза.
• Hubness (възелност): определени обекти се срещат по-често в списъците със съседи, отколкото други.

Много от анализираните специализирани методи се справят с един или друг от тези проблеми, но не всичките.

Тази страница частично или изцяло представлява превод на страницата Curse of dimensionality в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​