В интеллектуальном анализе данных увеличение числа переменных, используемых при построении моделей, обычно повышает их точность. Однако при этом может возникать эффект «проклятия размерности», который ухудшает работу моделей в многомерных пространствах. Обнаружение и снижение его влияния является актуальной задачей аналитики данных.
Проклятие размерности в машинном обучении и анализе данных — это термин, обозначающий неблагоприятные последствия, возникающие при работе с многомерными данными. Он описывает ситуацию, когда производительность и эффективность многих алгоритмов машинного обучения значительно ухудшаются по мере увеличения количества измерений.
В первую очередь это касается экспоненциального роста необходимого числа обучающих примеров в зависимости от размерности пространства признаков в задачах распознавания образов, классификации, кластеризации, дискриминантного анализа и др., где используется машинное обучение. В более широком смысле термин применяется по отношению ко всем «неудобным» или необычным свойствам многомерных пространств и к трудностям их исследования.
Впервые термин «проклятие размерности» был введен американским математиком Ричардом Беллманом применительно к задачам линейного программирования.
Интеллектуальный анализ данных связан с обработкой огромных объемов информации. Благодаря прогрессу в области технологий ее сбора и хранения стоимость этих процессов значительно снизилась. Как следствие, компании получили возможность накапливать и хранить огромные объемы данных, не задумываясь о том, понадобятся ли они вообще.
Рост объемов собираемых данных проявляется не только в числе наблюдений, но и в количестве признаков, значения которых одновременно регистрируются в процессе сбора. Логика тут проста: если нет проблем с регистрацией и хранением большого количества данных, то почему бы не собрать все доступные признаки, даже если некоторые из них впоследствии окажутся бесполезными?
Наблюдения в структурированных данных образуют векторы в пространстве признаков, размерность которых соответствует количеству одновременно регистрируемых атрибутов бизнес-процесса. Под данными высокой размерности обычно понимают наборы, содержащие большое число признаков, которые расположены в столбцах таблиц. При этом даже может складываться ситуация, когда число признаков превышает число наблюдений.
Сложность аналитической обработки многомерных данных возрастает из-за сочетания двух факторов. Во-первых, пространства большой размерности обладают геометрическими свойствами, которые противоречат интуиции и далеки от тех, которые можно наблюдать в двух- или трехмерных случаях. Во-вторых, инструменты анализа чаще всего разрабатываются с учетом интуитивных свойств и примеров в низкоразмерных пространствах.
Проблема в том, что эти инструменты используются и тогда, когда данные являются многомерными и сложными. В подобных ситуациях происходит искажение интуитивных представлений о работе аналитических инструментов и может произойти неправильная интерпретация результатов.
При анализе данных большой размерности возникают следующие проблемы:
Пусть задано множество X m-мерных векторов и мощность |X|=n. Тогда вычислительные затраты на формирование матрицы расстояний D будут O(n^{2}\cdot m), поскольку почти для всех мер расстояний вычисление d_{ij}требует перебора всех координат i и j
Снижение точности обучаемых моделей для фиксированного набора данных по мере увеличения размерности пространства задачи известно как феномен Хьюза. Он заключается в том, что с ростом числа признаков точность предсказания сначала возрастает, пока не будет достигнуто некоторое их оптимальное количество. После чего добавление дополнительных измерений приведет к ее снижению на выборке одного размера.
По этим причинам при разработке инструментов анализа данных необходимо учитывать особенности многомерных пространств.
Инструменты анализа данных, использующие машинное обучение, извлекают знания из большого числа обучающих примеров. Очевидно, что модель будет корректно работать только в той части пространства, где расположены данные, на которых она обучалась. Какой бы хорошей она ни была, ее способность к обобщению распространяется только на новые данные, расположенные в той же области пространства, где и обучающие. Другими словами, обобщение возможно на основе интерполяции, но не экстраполяции.
Таким образом, одним из ключевых элементов успешного построения обучаемой модели является наличие достаточного количества обучающих данных: чтобы они были локализованы в области пространства, где модель должна быть состоятельной. При прочих равных условиях количество примеров должно расти экспоненциально с увеличением размерности. Например, если 10 наблюдений кажутся разумными для обучения 1-мерной модели, то для 2-мерной необходимы уже 100, а для 3-мерной — 1000 и т.д. Этот экспоненциальный рост является первым следствием проклятия размерности.
Проиллюстрируем эффект разрежения точек данных при росте числа измерений пространства признаков на конкретном примере. Пусть в одномерном случае на оси имеются две точки A и Bс координатами 2 и 4 соответственно. Тогда расстояние между этими точками d_{AB}=4-2=2.
Теперь рассмотрим 2-мерный случай, когда расстояние должно быть пройдено по двум осям. Полагая, что используется евклидово расстояние (норма L_{2}), получим:
2d_{AB}=\sqrt{(4-2)^{2}+(4-2)^{2}}=\sqrt{2^{2}+2^{^{2}}}=\sqrt{8}\approx 2.83.
Таким образом, в результате добавления единственного измерения, расстояние между точками «растянулось» почти на треть! Рассмотрим 3-мерный случай:
3d_{AB}=\sqrt{(4-2)^{2}+(4-2)^{2}+(4-2)^{2}}=\sqrt{2^{2}+2^{^{2}}+2^{2}}=\sqrt{12}\approx 3.46.
Получается, что при переходе от одного измерения к трем пространство «растянулось» в 1.73 раза. Из сказанного можно сделать два неприятных вывода:
Например, пусть с помощью алгоритма кластеризации k-средних была построена модель из 3-х кластеров на основе 4-х признаков, которая показала хорошую эффективность. Впоследствии появилась возможность использовать еще 5 признаков при том же количестве обучающих примеров, чтобы повысить информативность модели. При этом попытка снова использовать три кластера, скорее всего, окажется несостоятельной, поскольку из-за разрежения точек данных произошло перераспределение их групповой структуры, для которой оптимальное число кластеров может оказаться другим.
Даже если не рассматривать проклятие размерности в контексте анализа данных, высокоразмерные пространства обладают специфическими геометрическими свойствами, которые в некоторых случаях кажутся противоречащими здравому смыслу.
Например, на рисунке иллюстрируется четыре таких свойства.
Геометрические особенности многомерных пространств
На рисунке (а) показан график зависимости объема сферы единичного радиуса от размерности пространства. Видно, что при увеличении числа измерений от 1 до 5 (5-мерная гиперсфера) ее объем увеличивается, а затем уменьшается и достигает почти 0, когда оно превышает 20. Объем 20-мерной гиперсферы с единичным радиусом, таким образом, почти равен нулю!
На рисунке (б) показан график зависимости отношения объема сферы единичного радиуса к объему куба с длиной ребра, равной 2 (таким образом, сфера оказывается вписанной в куб). В двумерном случае соотношение, очевидно, равно \pi /4. Это означает, что большая часть объема куба также содержится в сфере. Когда размерность увеличивается, это соотношение быстро уменьшается до 0 и достигает пренебрежимо малого значения, как только она достигает 10. С точки зрения плотности наблюдений в пространстве это означает, что если точки данных в кубе распределены случайно и равномерно, вероятность того, что они окажутся вблизи его углов, почти равна единице!
На рисунке (в) показано отношение объемов двух вложенных сфер с радиусами, равными 1 и 0.9, в зависимости от размерности пространства. С ее ростом отношение уменьшается экспоненциально. Но что еще более удивительно, так это то, что даже если радиусы отличаются всего на 10%, соотношение между объемами почти равно 0 при размерности 10. Если данные случайным образом и равномерно распределены в объеме большей сферы, это означает, что почти все они попадут в зазор между сферами!
Наконец, можно рассмотреть многомерное распределение Гаусса, масштабированное так, чтобы его интеграл (площадь под кривой распределения) был равен 1. На рисунке (г) показана доля площади, попадающей в радиус от центра распределения r=1.65. Хорошо известно, что она равна 90% для 1-мерного случая. Рисунок (г) показывает, что этот процент быстро уменьшается почти до 0 в размерности всего десять! Другими словами, при этом почти весь объем функции Гаусса содержится в ее «хвостах», а не вблизи центра, что противоречит общепринятому представлению!
Эти четыре примера показывают не только геометрические свойства, но и то, что даже равномерно распределенные данные концентрируются в неожиданных частях пространства, что нормы векторов не следуют интуитивным распределениям и что функции, считающиеся локальными, больше не являются таковыми. Эти свойства обязательно следует учитывать при разработке аналитических инструментов.
Более непосредственно с анализом данных связан феномен концентрации нормы. На рисунке ниже это явление иллюстрируется для случая распределения Гаусса со стандартными отклонениями, равными 1. Для нескольких измерений пространства (1, 2, 3, 5, 10 и 20) на рисунке показаны функции плотности вероятности, позволяющие найти точку, нарисованную в соответствии с распределением Гаусса, на расстоянии r от центра этого распределения.
При размерности d=1 эта функция представляет собой монотонно убывающую функцию. При d=2 оно имеет форму колокола с пиком около 1. Это иллюстрирует тот факт, что на расстоянии r=1 от центра находится больше точек, чем на расстоянии r=0.2 или r=2. При увеличении размера колоколообразная форма сохраняется, но смещается вправо. Например, при d=20 процент точек данных, лежащих на расстоянии менее r=2 от центра, настолько мал, что его невозможно увидеть в масштабе фигуры (несмотря на то, что стандартное отклонение распределения Гаусса равно 1).
Эффект концентрации нормы в многомерных пространствах
Это означает, что расстояния между всеми точками и центром распределения сосредоточены в небольшом интервале. Относительные различия между этими расстояниями исчезают, они расстояния становятся все менее различимыми, и поэтому не позволяют качественно представлять зависимости в данных.
Иными словами, при увеличении размерности расстояние между точками данных стремится стать одинаковым. В результате происходит размывание групповых структур, что приводит к ухудшению работы алгоритмов классификации и кластеризации, использующих расстояния.
По мере роста размерности доля входного пространства, охватываемая обучающим набором данных фиксированного размера, уменьшается. Многие методы требуют значительного количества примеров в каждой его области для подтверждения гипотезы или обучения модели. Поскольку доступные данные становятся разреженными из-за увеличения объема пространства, методы, использующие статистическую значимость, терпят неудачу.
В машинном обучении для построения модели (например, классификатора) требуется определенное количество обучающих примеров, которого может просто не оказаться в задачах большой размерности. Аналогичным образом в статистическом анализе для подтверждения гипотезы требуется определенный размер выборки, которого тоже не окажется при большом числе измерений.
Например, пусть имеются данные о 1000 клиентов, для которых составлен рейтинг, содержащий дискретные балльные оценки 0, 25, 50, 75, 100 в двух сегментах c_{1} и c_{2}. Тогда существует всего 5^{2}=25 различных комбинаций баллов. Если 1000 клиентов случайным образом распределены по каждой комбинации баллов, то в среднем имеется 40 клиентов с каждой возможной комбинацией, что является достаточно репрезентативной выборкой.
Теперь предположим, что имеется 4 сегмента, тогда будет получено 5^{4}=625 комбинаций, и тогда среднее число клиентов на одну из них будет 1.6. А для 10 сегментов эта величина составит уже 0.0001024, т.е. почти все возможные комбинации никогда не будут наблюдаться.
Классическим примером, демонстрирующим проблему высокой размерности данных, является задача поиска ближайшего соседа. Базовый подход к решению этой задачи заключается в использование структуры, которая разбивает входное пространство на ячейки. И чтобы определить ближайшего соседа некоторой точки, нужно найти соседнюю ячейку и выбрать множество всех точек в ней.
При этом оказывается, что окрестность соседства для многомерных пространств окажется выше, чем для маломерных.
Предположим n точек в X выбраны равномерно и случайно в [0,1]^{m} (так называемый m-куб). Для точки q формируется гиперкуб вокруг нее, чтобы он содержал f фракций точек k=fn в X. Можно показать, что куб (пространство поиска для q) вырастет очень большим, охватывающим почти все входное пространство, при большом числе измерений.
Ожидаемая длина ребра куба E_{m}(f)=f^{1/m} т.е. в 10d, чтобы получить 10% точек вокруг q требуется куб с ребром 0.8, т.е. 80% исходного.
Аналогично, чтобы получить только 1% точек, нужно расширить куб поиска на 0.63 единицы по каждому измерению. Рассмотрим пример, демонстрирующий это явление нелокальности окрестностей в более высоких размерностях.
Предположим, что 5000 точек случайно расположены на [0,1]^{m} и q=0. В одномерном пространстве мы должны пройти расстояние 5/5000=0.001 для захвата 5 ближайших соседей.
В 2-мерном случае требуется в среднем пройти дистанцию \sqrt{5/5000}=0.031 единиц вдоль обоих измерений, чтобы получить 5 ближайших соседних точек (т.е. 3% исходного куба).
В 3-мерном случае же нужно пройти \sqrt[3]{5/5000}=0.1=10% единиц вдоль трех измерений, чтобы получить 5 ближайших соседних точек (т.е. 10% исходного куба).
Для 4-мерного случая получим \sqrt[4]{5/5000}=0.177=17.7%. Для 10-мерного уже 50.1%. А в общем случае для m-мерного \sqrt[m]{5/5000}.
Для выражения этого явления используется фраза «в многомерном пространстве никто не услышит ваш крик».
Столкнувшись с трудностями, возникающими из-за большой размерности пространства признаков, можно попытаться уменьшить ее без потери значимой информации в данных. Сокращение размерности используется в качестве предварительной обработки перед применением аналитических моделей.
Наиболее традиционным инструментом уменьшения размерности входного пространства является метод главных компонент (PCA). Он проецирует данные в пространство меньшей размерности, выбирая оси, сохраняющие максимальную начальную дисперсию. К сожалению, PCA — линейный инструмент и при обработке с его помощью нелинейные зависимости могут быть потеряны. И если в дальнейшем процессе анализа предполагается обработка с помощью нелинейных инструментов, то применение PCA нецелесообразно.
Для нелинейного проецирования могут быть использованы методы сохранения расстояния. Принцип их работы состоит в том, чтобы найти представление меньшей размерности, в котором попарные расстояния соблюдаются в максимально возможной степени по отношению к исходному пространству данных. К этому классу методов относится нелинейное отображение Саммона. Предпочтительны короткие расстояния в исходном пространстве, позволяющие разворачивать большие нелинейные поверхности и объемы.
Следует упомянуть и о других инструментах нелинейного проецирования. Например, самоорганизующиеся карты (SOM) или карты Кохонена можно рассматривать как инструменты нелинейного проецирования с сохранением топологического подобия. SOM широко используются в задачах визуализации, где размерность проекционного пространства ограничена 3d.
Однако нет никаких технических трудностей, чтобы распространить использование SOM на проекционные пространства более высокой размерности. SOM используются, когда требуется комбинация векторного квантования, кластеризации и проецирования. Однако качество биекции с исходным пространством (без потери информации при преобразовании) ограничено по сравнению с методами сохранения расстояния.
Работа с данными, в которых присутствует большое число признаков, делает необходимым оценить, в какой степени «сбывается» проклятие размерности. Для этого возможно применение несколько методов:
В настоящее время наблюдается устойчивая тенденция к усложнению бизнес-процессов, протекающих в современной высоко динамичной рыночной среде. Как следствие, для их глубокого анализа требуется все больше признаков, поэтому работа аналитических алгоритмов смещается в пространства с большим числом измерений, где неосторожного аналитика подстерегает проклятие размерности. Поэтому разработка и применение технологий борьбы с ним становится все более значимым фактором достижения успеха.
Другие материалы по теме:
Построение единой аналитической системы для компаний среднего бизнеса и производств
Теория ограничений: как расширить «узкие места» в анализе данных
