Давайте рассмотрим некоторые из основных алгоритмов решения сложных задач принятия решений, на которые влияют несколько критериев. Мы обсудим, зачем нам такие методы, и исследуем доступные алгоритмы в крутом пакете python skcriteria.

Вступление

Предположим, вам нужно принять решение - например, купить дом, машину или даже гитару. Вы не хотите выбирать случайным образом или поддаваться предвзятости из-за чьего-либо предложения, но хотите принять обоснованное решение. Для этого вы собрали некоторую информацию о объекте, который хотите купить (допустим, это автомобиль). Итак, у вас есть список N cars с информацией об их ценах. Как обычно, мы не хотим тратить больше, мы можем просто отсортировать машины по их цене (в порядке возрастания) и выбрать лучшую (с наименьшей ценой), и готово! Это было принятие решения по единому критерию. Но увы, если жизнь так проста :) Мы также хотели бы, чтобы у машины был хороший пробег, лучший двигатель, более быстрый разгон (если вы хотите участвовать в гонках) и еще кое-что. Здесь вы хотите выбрать автомобиль с наименьшей ценой, но с наибольшим пробегом, ускорением и т. Д. Эту проблему не так легко решить простой сортировкой. Введите многокритериальные алгоритмы принятия решений!

Набор данных

Давайте выберем один набор данных, чтобы было легче визуализировать результат, понять, что на самом деле происходит за кулисами, и, наконец, развить интуицию. Для этого я выбираю набор данных автомобилей. Для каждого автомобиля мы сосредоточимся на подмножестве атрибутов и выберем только 10 рядов (уникальных автомобилей), чтобы облегчить нашу жизнь. Посмотрите на выбранные данные,

Объясняя некоторые атрибуты,

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

Здесь обратите внимание на некоторые моменты,

  1. Единица и распределение атрибутов не совпадают. Цена играет в тысячи долларов, разгон в десятки секунд и так далее.

2. Логика наилучшего качества для каждого атрибута также различается. Здесь мы хотим найти автомобиль с высокими значениями миль на галлон, смещения и ускорения. В то же время низкие значения в весе и цене. Это понятие высокого и низкого уровня может быть выведено как максимизирующее и минимизирующее атрибуты, соответственно.

3. Может быть дополнительное требование, согласно которому мы не считаем все атрибуты равными. Например, если я хочу машину для гонок и говорю, что меня спонсирует миллиардер, то меня не так сильно заботят расход топлива на галлон и цена. Я хочу самую быструю и легкую машину. Но что, если я студент (а значит, скорее всего, у меня ограниченный бюджет) и много путешествую, то внезапно миль на галлон и цена становятся наиболее важными атрибутами, и мне наплевать на перемещение. Эти понятия важных атрибутов могут быть выведены как веса, присвоенные каждому атрибуту. Скажем, цена важна на 30%, а смещение всего на 10% и так далее.

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

Общая методология

Большинство основных средств принятия решений по нескольким критериям имеют общую методологию, которая пытается:

  1. Рассматривайте один атрибут за раз и старайтесь максимизировать или минимизировать его (в соответствии с требованиями), чтобы получить оптимальную оценку.
  2. Введите веса для каждого атрибута, чтобы получить оптимизированные взвешенные оценки.
  3. Объедините взвешенные оценки (каждого атрибута), чтобы получить окончательную оценку для объекта (здесь автомобиль).

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

Развернуть и свернуть

Помните первый пункт из раздела наборов данных, атрибуты имеют очень разные единицы и распределения, с которыми нам нужно работать. Одно из возможных решений - нормализовать каждый атрибут в одном диапазоне. И мы также хотим, чтобы направление добра было одинаковым (независимо от логики). Следовательно, после нормализации значения, близкие к максимальному диапазону (скажем, 1), должны означать, что автомобиль хорош по этому атрибуту, а более низкие значения (скажем, около 0) означают, что они плохие. Мы делаем это по следующей формуле,

Посмотрите на первое уравнение для максимизации, одним из примеров является обновление миль на галлон каждого автомобиля путем деления его на сумму миль на галлон всех автомобилей (нормализация суммы). Мы можем изменить логику, просто рассматривая максимальное значение миль на галлон или другие формулы. Намерение состоит в том, что после применения этого к каждому атрибуту диапазон каждого атрибута будет таким же, а также мы можем сделать вывод, что значение, близкое к 1, означает хорошее.

Формула минимизации почти такая же, как и формула максимизации, мы просто инвертируем ее (1 делится на максимизацию) или зеркалируем (вычитая ее из 1), чтобы фактически изменить направление совершенства (в противном случае 1 будет означать плохое, а 0 - хорошее. ). Посмотрим, как это выглядит на практике,

Применить веса

Нам просто нужно наложить вес на оптимизированные оценки, что можно легко сделать, умножив веса на оптимизированные оценки. Здесь мы также можем ввести различные типы нормализации,

  • как есть: напрямую умножайте веса для получения оптимизированной оценки
  • сумма: нормализовать веса по логике суммирования (обсуждалось выше), затем умножить.
  • max: нормализовать по максимальной логике, затем умножить.

Объедините результаты

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

  • сумма: сложить все индивидуальные оценки вместе
  • product: умножьте все индивидуальные оценки вместе. Фактически, многие реализации добавляют логарифм значения вместо того, чтобы брать произведения, это делается для обработки очень меньшего результата при умножении малых значений.

Реализация

Существует очень хороший пакет Python под названием skcriteria, который предоставляет множество алгоритмов для решения задач, связанных с принятием решений по нескольким критериям. Фактически два алгоритма внутри модуля skcriteria.madm.simple:

  • WeightedSum - логика объединения индивидуальных оценок - это сумма
  • WeightedProduct - логика объединения индивидуальных оценок - это произведение (сумма журнала)

И оба эти метода принимают на вход два параметра:

  • mnorm - определить логику нормализации максимизации значения (минимизация всегда является обратной по отношению к той же самой логике максимизации).
  • wnorm - определить логику нормализации веса

Чтобы выполнить ранжирование наших данных, сначала нам нужно загрузить их как их skcriteria.Data объект,

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

Мы даже можем экспортировать окончательный результат на dec.e_.points и ранги на dec.rank_.

Сравнение

Давайте сравним результат различных алгоритмов принятия решений (с разными параметрами) в нашем наборе данных. Для этого я использую реализации weightedSum и weightedProduct (сначала с max, а затем с sum нормализацией значений). Я также реализовал функцию normalize_data, которая по умолчанию выполняет minmax и вычитает нормализацию. Затем я применяю суммирование к выходу.

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

Некоторые моменты,

  • Ford Torino занимает 1-е место (автомобиль с наивысшим баллом) для 4/5 решателей. Minmax отдает предпочтение Chevrolet Malibu.
  • Импала - универсальный игрок низкого ранга :(
  • Обе реализации weightedProduct дают одинаковый рейтинг для всех автомобилей. Здесь ничего интересного.
  • Высокая разница в рейтингах обоих weightedSum реализаций.
  • MinMax дает самые разные рейтинги для 4 лучших парней.

Основная причина расхождения результата при изменении нормализации (от суммы до максимума) связана с переводом исходных данных. Этот перевод изменяет диапазон данных (например, масштабирует все между x и y), а в случае инверсии также изменяет линейность (скажем, равные шаги 1 в исходных данных несовместимы в преобразованных данных). Это станет более ясным из следующего результата:

Здесь входные данные состоят из чисел от 1 до 9 (обратите внимание, разница между любыми двумя последовательными числами равна 1, т.е. шаг такой же). Первый подход (minmax) переводит данные между 0 и 1, и шаг остается прежним. Теперь посмотрим на логику минимизации (_inverse) подходов 2 и 3. Здесь в начале (низкие исходные значения) шаг составляет почти половину последнего элемента, но ближе к концу (высокое исходное значение) шаг очень мал, даже хотя в исходных данных мы движемся с тем же шагом 1.

Из-за этого в случае минимизации очень высокий балл присваивается «хорошим» автомобилям (с низкими значениями) и даже небольшим примесям (в минимальном случае высокое значение = низкий балл), что приводит к резкому снижению оценки. Как будто мы очень разборчивы: либо ты лучший, либо получаешь половину баллов :) С другой стороны, для более высоких значений мелкие примеси не имеют значения. Если машина уже плохая по этому атрибуту, то нам все равно, будет ли его значение 7, 8 или 9, и снижение оценки будет намного меньше! Мы можем использовать это понимание, чтобы выбрать правильное решающее устройство с правильным параметром в соответствии с нашими потребностями.

Заключение

Эта статья только что коснулась поверхности области принятия решений по нескольким критериям. Даже в пакете skcriteria есть намного больше алгоритмов, таких как TOPSIS и MOORA, у которых совершенно другая интуиция для решения этих проблем. Но даже тогда понятие добра и идея обрабатывать отдельные атрибуты, чтобы в конечном итоге объединить их все вместе, используются во многих из них. Так что, возможно, мы рассмотрим больше алгоритмов в другой статье.

Но основные выводы из этой статьи должны заключаться в том, чтобы понять, почему и что принимают решения. Что каждым таким решением можно манипулировать по нескольким критериям. А также то, что у нас могут быть разные представления о добродетели и важности, приписываемые каждому критерию. Наконец, у нас есть различные разновидности решателей, которые можно построить путем перестановки логики и параметров, и почти все они дают разные и интересные результаты в зависимости от наших потребностей!

использованная литература

[1] Пакет Python Skcriteria

Код и данные из статьи доступны здесь.

Чтобы читать больше подобных статей, подпишитесь на меня в LinkedIn или посетите мой сайт.

Ваше здоровье.