Підручник з аналізу охоплення даних

• 24 Лютого, 2014
• Василіс Врініотис
• . 3 коментарі

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

Оновлення: Система машинного навчання Datumbox тепер є відкритою та безкоштовною скачати. Перегляньте пакет com.datumbox.framework.algorithms.dea, щоб побачити реалізацію аналізу охоплення даних у Java.

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

Чому аналіз охоплення даних цікавий?

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

Опис і припущення аналізу охоплення даних

Як ми обговорювали раніше, DEA – це метод, який був винайдений для вимірювання продуктивності в бізнесі. Таким чином, кілька його ідей походять із способу вимірювання продуктивності в цьому контексті. Однією з основних характеристик методу є поділ характеристик запису на дві категорії: вхідні та вихідні. Наприклад, якщо ми вимірюємо ефективність автомобіля, ми можемо сказати, що вхідний показник – це літри бензину, а вихідний – це кількість кілометрів, які він проїхав.

У DEA всі характеристики повинні бути позитивними, і передбачається, що чим вище їх значення, тим більше їх вхід/вихід. Крім того, аналіз охоплення даних припускає, що функції можна об’єднати лінійно як зважену суму невід’ємних ваг і сформувати співвідношення між входом і виходом, яке вимірюватиме ефективність кожного запису. Щоб запис був ефективним, він повинен давати нам «хороший» вихід відносно наданого введення. Ефективність вимірюється співвідношенням між виходом і входом, а потім порівнюється зі співвідношенням інших записів.

Геніальна ідея 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 може бути хорошим рішенням, коли неможливо зробити будь-які припущення щодо важливості функцій, але якщо ми маємо будь-яку попередню інформацію або ми можемо кількісно визначити їхню важливість, тоді рекомендується використовувати альтернативні методи.

У наступній статті я покажу вам, як розробити реалізацію Аналіз охоплення даних у JAVA і ми будемо використовувати метод для оцінки популярності веб-сторінок і статей у соціальних мережах.

Якщо вам подобається стаття, знайдіть час, щоб поділитися нею в Twitter або Facebook. 🙂