Анализ оболочки данных, также известный как DEA, представляет собой непараметрический метод проведения граничного анализа. Он использует линейное программирование для оценки эффективности нескольких единиц, принимающих решения, и обычно используется в производстве, управлении и экономике. Впервые методика была предложена Чарнс, Купер и Родс в 1978 году. и с тех пор он стал ценным инструментом для оценки производственных границ.

Обновление: платформа машинного обучения Datumbox теперь имеет открытый исходный код и бесплатна для скачать. Ознакомьтесь с пакетом com.datumbox.framework.algorithms.dea, чтобы увидеть реализацию Data Envelopment Analysis в Java.

Когда я впервые столкнулся с методом 5-6 лет назад, я был поражен оригинальностью алгоритма, его простотой и остроумием использованных в нем идей. Я был еще более поражен, увидев, что этот метод хорошо работает за пределами его обычных приложений (финансы, исследования операций и т. д.), поскольку его можно успешно применять в онлайн-маркетинге, рейтинге поисковых систем и для создания составных показателей. Несмотря на это, сегодня DEA почти исключительно обсуждается в контексте бизнеса. Вот почему в этой статье я расскажу об основных идеях и математической структуре DEA, а в следующем посте я покажу вам некоторые новые применения алгоритма в веб-приложениях.

Чем интересен анализ оболочки данных?

Анализ оболочки данных — это метод, который позволяет нам сравнивать и ранжировать записи (магазины, сотрудники, фабрики, веб-страницы, маркетинговые кампании и т. д.) на основе их характеристик (веса, размера, стоимости, доходов и других показателей или ключевых показателей эффективности) без каких-либо предварительных предположений о важность или вес признаков. Самая интересная часть этого метода заключается в том, что он позволяет нам сравнивать записи, состоящие из нескольких признаков, которые имеют совершенно разные единицы измерения. Это означает, что мы можем иметь записи с функциями, измеряемыми в километрах, килограммах или денежных единицах, и при этом иметь возможность сравнивать, ранжировать их и находить записи с лучшими/худшими и средними показателями. Звучит интересно? Продолжай читать.

Описание и допущения анализа оболочки данных

Как мы обсуждали ранее, DEA — это метод, который был изобретен для измерения производительности в бизнесе. Таким образом, некоторые из его идей исходят из того, как производительность измеряется в этом контексте. Одной из основных характеристик метода является разделение признаков записи на две категории: входные и выходные. Например, если мы измеряем эффективность автомобиля, мы могли бы сказать, что входные данные — это литры бензина, а выходные данные — количество километров, которые он проезжает.

В DEA все признаки должны быть положительными, и предполагается, что чем выше их значение, тем больше их вход/выход. Кроме того, Data Envelopment Analysis предполагает, что функции могут линейно комбинироваться как взвешенная сумма неотрицательных весов и формировать соотношение между входными и выходными данными, которое будет измерять эффективность каждой записи. Чтобы запись была эффективной, она должна давать нам «хороший» результат по сравнению с предоставленным вводом. Эффективность измеряется соотношением между выходом и входом, а затем сравнивается с соотношением других записей.

Гениальная идея DEA

То, что мы рассмотрели до сих пор, является здравым смыслом/практикой. Мы используем ввод и вывод, взвешенные суммы и отношения для ранжирования наших записей. Умная идея DEA заключается в том, как рассчитываются веса признаков. Вместо того, чтобы задавать веса функций и принимать решения об их важности перед запуском анализа, анализ оболочки данных вычисляет их на основе данных. Более того, веса НЕ одинаковы для каждой записи!

Вот как DEA выбирает веса: мы пытаемся максимизировать отношение каждой записи, выбирая соответствующие веса признаков; в то же время мы должны гарантировать, что если мы будем использовать те же веса для вычисления отношений всех других записей, ни одна из них не станет больше 1.

Идея поначалу звучит немного странно. Не приведет ли это к расчету разновзвешенных коэффициентов? Ответ положительный. Не означает ли это, что мы на самом деле вычисляем отношения для каждой записи по-разному? Ответ снова да. Так как же это работает? Ответ прост: Для каждой записи, учитывая ее характеристики, мы пытаемся найти «идеальную ситуацию» (веса), при которой ее отношение было бы максимально высоким и, таким образом, максимально эффективным. НО в то же время, учитывая эту «идеальную ситуацию», ни одно из соотношений выход/вход других записей не должно быть больше 1, а это означает, что они не могут быть эффективнее 100%! Как только мы вычислим отношения всех записей в каждой «идеальной ситуации», мы используем их отношения для их ранжирования.

Таким образом, основную идею DEA можно резюмировать следующим образом: «Найдите идеальную ситуацию, в которой мы можем достичь наилучшего показателя отношения на основе характеристик каждой записи. Затем вычислите это идеальное соотношение каждой записи и используйте его для сравнения их эффективности».

Давайте посмотрим на пример

Давайте посмотрим на пример, где мы могли бы использовать DEA.

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

Чтобы применить DEA, мы должны определить, что является нашим входом и выходом. В этом случае результатом, очевидно, является объем продаж и количество клиентов, которых они обслуживают. Входными данными является количество сотрудников и размер магазина. Если мы запустим DEA, мы оценим отношение выхода к входу для каждого магазина при идеальных весах (как обсуждалось выше). Как только мы получим их соотношения, мы ранжируем их в соответствии с их эффективностью.

Пришло время математики!

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

Коэффициент эффективности конкретной записи i с входом x и выходом y (оба вектора признаков с положительными значениями) оценивается по следующей формуле:

Где u и v — веса каждого выхода и входа записи, s — количество выходных признаков, а m — количество входных признаков.

Задача нахождения наилучших/идеальных весов для конкретной записи i может быть сформулирована следующим образом:

Опять же, приведенное выше — это просто математический способ нахождения весов u и v, которые максимизируют эффективность записи i, при условии, что эти веса не сделают никакие другие записи более эффективными, чем 100%.

Чтобы решить эту проблему, мы должны использовать линейное программирование. К сожалению, линейное программирование не позволяет нам использовать дроби, поэтому нам нужно преобразовать формулировку задачи следующим образом:

Мы должны подчеркнуть, что приведенная выше задача линейного программирования даст нам наилучшие веса для записи i и вычислит ее эффективность при этих оптимальных весах. То же самое нужно повторить для каждой записи в нашем наборе данных. Итак, если у нас есть n записей, нам нужно решить n отдельных линейных задач. Вот псевдокод того, как работает DEA:

ratio_scores = ();
for every record i {
    i_ratio = get_maximum_effectiveness();
    ratio_scores(i) = i_ratio;
}

Ограничения анализа оболочки данных

DEA — отличный метод, но у него есть свои ограничения. Вы должны понимать, что DEA подобен черному ящику. Поскольку веса, которые используются в коэффициенте эффективности каждой записи, различны, пытаться объяснить, как и почему рассчитывалась каждая оценка, бессмысленно. Обычно мы ориентируемся на ранжирование записей, а не на фактические значения показателей эффективности. Также обратите внимание, что наличие экстремумов может привести к тому, что оценки будут иметь очень низкие значения.

Имейте в виду, что DEA использует линейные комбинации функций для оценки отношений. Таким образом, если их линейное комбинирование не подходит для нашего приложения, мы должны применить преобразования к функциям и сделать возможным их линейное комбинирование. Еще один недостаток этого метода заключается в том, что нам приходится решать столько задач линейного программирования, сколько записей, что требует больших вычислительных ресурсов.

Другая проблема, с которой сталкивается DEA, заключается в том, что он плохо работает с многомерными данными. Для использования DEA количество измерений d = m + s должно быть значительно меньше, чем количество наблюдений. Запуск DEA, когда d очень близко или превышает n, не дает полезных результатов, поскольку, скорее всего, все записи будут признаны оптимальными. Обратите внимание, что при добавлении новой выходной переменной (измерения) все записи с максимальным значением в этом измерении будут признаны оптимальными.

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

В следующей статье я покажу вам, как разработать реализацию Data Envelopment Analysis в JAVA, и мы будем использовать этот метод для оценки популярности веб-страниц и статей в социальных сетях.

Если вам понравилась статья, поделитесь ею в Twitter или Facebook. 🙂