Что такое «проклятие размерности» и как с ним бороться

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И ГОСУДАРСТВЕННОЙ СЛУЖБЫ»

( Волгоградский филиал )

 

Экономический факультет

 

Кафедра информационных систем и математического моделирования

 

 

 

 

 

Что такое «проклятие размерности» и как с ним бороться

 

 

 

Эссе

По дисциплине «Компьютерные  методы исследования систем управления»

 

                                                                        Выполнил:

                                                                       

                                                                              

                                                                        Проверил:

                                                                       

 

 

Волгоград 2013

 

СОДЕРЖАНИЕ:

 

ВВЕДЕНИЕ………………………………………………………………….……3

ОСНОВНАЯ ЧАСТЬ……………………………………………………………4

1. Определение и проблемы…………...…………………………………………4

2. Примеры………………………………………………………………………..5

3. Способы устранения «проклятия размерности»…………………………….6

4. Мое понимание эффекта  на примере (2)……………………………………..6

ЗАКЛЮЧЕНИЕ………………………………………………………………….8

СПИСОК ИСТОЧНИКОВ……………………………………………………..9 

ВВЕДЕНИЕ

Проклятие размерности весьма интересный эффект, который может появиться во время анализа данных в многомерных пространствах, например, при кластерном анализе¹ или при обнаружении аномалий².

Казалось бы, чем больше мы знаем об объектах (чем больше у них атрибутов), тем лучше: есть больше информации, по которой можно  понять, насколько объекты похожи (отнести их к одному кластеру) или насколько они отличаются (отличить кластеры, найти аномалию). Да и вообще, чем больше о чем-то знаешь, тем лучше это контролируешь. 
"Проклятие размерности" приводит к обратному.

Необходимо узнать, что же такое «проклятие размерности» и как с ним бороться. Рассмотрим это ниже.

 

ОСНОВНАЯ ЧАСТЬ

1. Определение и проблемы.

 

Проклятие размерности  — проблема, связанная с экспоненциальным возрастанием количества данных из-за увеличения размерности пространства. Термин «проклятие размерности» был введен Ричардом Беллманом в 1961 году.

Проблема «проклятия размерности» часто возникает в машинном обучении, например, при применении метода ближайших соседей (простейший метрический классификатор, основанный на оценивании сходства объектов; классифицируемый объект относится к тому кластеру, которому принадлежат ближайшие к нему объекты обучающей выборки) и метода парзеновского окна (метод классификации, основанный на непараметрическом восстановлении плотности по имеющейся выборке; после ввода метрики, метод парзеновского окна можно использовать, не опираясь на вероятностную природу данных).

 

Проблемы, возникающие при проявлении «проклятия размерности».

«Проклятие размерности», как уже было указано во введении, особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.

Это влечет за собой следующие трудности:

• Трудоемкость вычислений;
• Необходимость хранения огромного количества данных;
• Увеличение доли шумов;
• В линейных классификаторах увеличение числа признаков ведет к проблемам мультиколлинеарности (тесная корреляционная взаимосвязь между отбираемыми для анализа факторами, совместно воздействующими на общий результат, которая затрудняет оценивание регрессионных параметров) и переобучения (нежелательное явление, возникающее при решении задач обучения по прецедентам, когда вероятность ошибки обученного алгоритма на объектах тестовой выборки оказывается существенно выше, чем средняя ошибка на обучающей выборке ; переобучение возникает при использовании избыточно сложных моделей).

 

2. Примеры.

 

Самый простой пример (1) "проклятия размерности" связан с изобретателем шахмат. Согласно легенде, один богатый человек настолько был восхищен этой игрой, что предложил изобретателю продать доску с фигурами. Хитрый изобретатель сказал, чтобы покупатель клал на каждую клеточку шахматной доски в два раза больше зернышек, чем на предыдущую, начиная с одного зернышка. Богатый человек рассмеялся и сказал, что с легкостью исполнит это желание. Здесь он и попал под "проклятье размерности" - не смог оценить конечное количество зерна. Действительно, кажется, что зернышки такие маленькие, и их общий вес не может быть огромным.

Напомню, что шахматная доска  имеет 64 клетки.

Покупатель должен был положить 1 + 2^63 зернышек!

А это получается 9 223 372 036 854 776 001 зерен !!!

Среднее зернышко весит 0,03 грамма.

ИТОГО: 276 701 161 105 тонн зерна!

Естественно, богач не смог купить шахматы!

Вывод: Старайтесь научиться правильно оценивать величины, которыми вы оперируете. Это поможет Вам точно оценить свои возможности и избежать неловких ситуаций.

 

Следующий пример (2) посложнее:

рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.

Теперь рассмотрим 10-мерный куб. Для достижения той же степени  покрытия потребуется уже 1020 точек. То есть, по сравнению с одномерным пространством, требуется в 1018 раз  больше точек.

 

3. Способы устранения «проклятия размерности».

 

Способы устранения «проклятия размерности»:

• Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности. На этой идее, например, основан метод главных компонент.
• Нужно придумывать новые алгоритмы, основанные на тензорной математике.

 

4. Мое понимание эффекта на примере (2).

 

При кластерном анализе  или при обнаружении аномалий, объекты удобно рассматривать как  точки в пространстве своих атрибутов.

Алгоритмы, исследующие  это пространство, должны определить расположены ли объекты между собой "по соседству"  - то есть, находятся ли они на определенном расстоянии друг от друга (или от некой точки выбранной в качестве центра).

Так вот, чем больше атрибутов (чем больше размерность пространства, в котором ведется поиск соседей), тем меньше область, которая покрывается во время поиска на заданном расстоянии.

Это легко себе представить, просто оценив соотношение объема гиперсферы с объемом гиперкуба, в который она вписана. 
(Если у нас только один кластер, то гиперсфера – область, в которой объекты считаются похожими, а гиперкуб - пространство атрибутов в котором расположены объекты).

 
 
Количество охваченных объектов уменьшается  по экспоненте при увеличении размерности  пространства.

Это означает, что при  увеличении количества атрибутов, для  того чтобы охватить требуемое количество объектов, нужно по экспоненте увеличивать  расстояние  поиска.

А это, в свою очередь, приведет к тому, что в охват  попадут далекие друг от друга  объекты - совсем не "соседи".

То есть теперь, в один кластер могут попасть совсем не похожие между собой объекты, или возможен провал в определении "далекой" аномалии, так как, за счет увеличения радиуса поиска, она будет отнесена к основной группе объектов.

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

В данном исследовании мы получили ответ на поставленный вопрос: проклятие размерности – это проблема, связанная с экспоненциальным возрастанием количества данных из-за увеличения размерности пространства. То есть, чем выше размерность пространства, тем меньше область, которая покрывается во время поиска объектов, расположенных на заданном расстоянии.

Чтобы избежать подобного  эффекта, необходимо правильно оценивать величины, которыми мы оперируем; понизить размерность данного пространства известными и доступными алгоритмами; придумать новые алгоритмы, избавляющие нас от «проклятия».

Изучение такого эффекта  необходимо, так как это поможет работе ученых в таких областях как фармакология, биоинформатика, в работе с фото- и видеоматериалами, в аэродинамике и т.д.. Без этого мы не сможем упростить, облегчить, оптимизировать нашу повседневную жизнь, что может привести к колоссальным затратам времени, ресурсов и средств.

 

СПИСОК ИСТОЧНИКОВ

 

1. Интернет-источник: http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%BA%D0%BB%D1%8F%D1%82%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8

2. Интернет-источник: http://threeflower.livejournal.com/20116.html

3. Интернет-источник: http://www.strf.ru/material.aspx?CatalogId=221&d_no=45624

¹ — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы.

² — динамический метод работы антивирусов, хостовых и сетевых систем обнаружения вторжений.