MCDM-Project. Часть 1. Концепция

в 19:16, , рубрики: api, агрегатор, альфа-версия, будущее здесь, веб-сервис, демонстрация прототипа, искусственный интеллект, каталог, многокритериальный поиск, многофакторная сортировка, поисковые технологии, Разработка веб-сайтов, экспертная оценка

MCDM-Project. Часть 1. Концепция - 1

Предисловие

Все-таки в душе я фантазер и мечтатель, на деле (в мире программирования) максимум «парень из гаража», но после «раскручивания гаек» не мог не удержаться от идеи явить Хабражителям на справедливый суд концепцию проекта MCDM-Project в целом и игрушечную тестовую версию в частности (несколько опасаюсь Хабраэффекта, если будут проблемы — прощения просим). Ссылка на сайт проекта ждет читателя в конце публикации (вместе с опросом), для ознакомления рекомендуется пройти предлагаемый на сайте тур, а в идеале — предварительно ознакомиться с основными идеями под катом.

Почему нелинейность?

Эта история началась с ряда публикаций на тему многокритериального оценивания объектов со слабосвязанными (неочевидно связанными) параметрами и работы с экспертами, которые должны были формировать правила оценивания рассматриваемых объектов. Довольно быстро стало понятно, что пользоваться линейными критериями оценивания при работе с экспертами нельзя. Человек мыслит неаддитивно. Представьте, что вы собираетесь выбрать ноутбук (публике с Хабра данный пример должен быть очень близок) и рассматриваете какой-то определенный вариант (упрощая многие особенности): пусть это будет i5 с частотой 3ГГц, 8Гб оперативной памяти, и видеокарта 10й серии с 4Гб памяти. Предположим, что имеющиеся альтернативы для покупки (с тем же бюджетом) будут следующими:

  1. i5 с частотой 3ГГц, 8Гб оперативной памяти, и видеокарта 10й серии с 4Гб памяти;
  2. i5 с частотой 3.5ГГц, 4Гб оперативной памяти, и видеокарта 10й серии с 4Гб памяти;
  3. i5 с частотой 2.5ГГц, 8Гб оперативной памяти, и видеокарта 10й серии с 6Гб памяти;
  4. i5 с частотой 3.5ГГц, 8Гб оперативной памяти, и видеокарта 10й серии с 2Гб памяти.

Обратите внимание на то, что в данном примере все значения параметров изменяются линейно (уменьшение/увеличение значения какого-то одного параметра на некоторую константу относительно опорного варианта приводит к увеличению/уменьшению другого параметра на другую константу). Но будет ли это означать, что ваше предпочтение остается неизменным? Вовсе нет! На вскидку вы всегда сможете указать наиболее предпочтительный вариант для себя, а значит его оценка выше, чем у других. Продолжая мысль, докажем на этом примере, что линейный критерий предпочтения для оценки альтернатив тоже не подходит. Предположим, что это не так. В качестве примера мы будем выбирать ноутбук для работы (т.е. играть не предполагаем, но для расчетов нас интересуют производительность и объем оперативной памяти). Введем новый вариант: i5 с частотой 3.5ГГц, 16Гб оперативной памяти, и видеокарта с 0Гб памяти. Выделим три альтернативы (нумерация сохраняется для удобства восприятия):

2) i5 с частотой 3.5ГГц, 4Гб оперативной памяти, и видеокарта 10й серии с 4Гб памяти;
4) i5 с частотой 3.5ГГц, 8Гб оперативной памяти, и видеокарта 10й серии с 2Гб памяти;
5) i5 с частотой 3.5ГГц, 16Гб оперативной памяти, и видеокарта с 0Гб памяти.

С учетом нашего предпочтения лучшей альтернативой очевидно является №5. Применение линейного критерия оценивания предполагает, что вклад единицы значения параметра линейно связан со значением критерия (например, увеличение параметра на единицу приводит к увеличению критерия на некоторую другую единицу). В этом случае при том, что альтернатива №4 условно хуже на X, альтернатива №2 должна быть хуже на 2X (мы не учитывали видеокарту). Но стоит нам захотеть играть в не слишком требовательные игры после работы — какой вариант следует выбрать? Здесь мнения могу разойтись, но большинство убедительно выберут альтернативу №4. Все дело в том, что эксперт в своем суждении учитывает неявные взаимосвязи совместного вклада параметров на качество альтернативы. Так, для нашего правила выбора совместная значимость частоты процессора и объема оперативной памяти важнее, чем совместная значимость объема оперативной памяти и объема видеопамяти.

В случае, когда параметров выбора больше 3, то и от эксперта требуется оценивать влияние не только пар, но и троек параметров и т.д., что характеризует не только гибкость подобной настройки поиска предпочтительной альтернативы, но и, к сожалению, трудоемкость этого процесса для эксперта (формирование СЛОЖНЫХ ПРАВИЛ).

На момент выхода статьи в нашей тестовой версии имеется только базовый функционал, который не позволяет также гибко настраивать правила выбора. Пока что он ограничен (условно 1м) уровнем сложности, который в дальнейшем будем называть ПРОСТЫЕ ПРАВИЛА. Стоит отметить, что простые правила уже дают больше удобства, чем любой (из широкоизвесных) существующий каталог. Либо мы плохо знаем то, что хотим найти в каталоге, и тогда вынуждены буквально листать каталог вдоль и поперек (используемые сортировки традиционно просты — по цене, по новизне и т.п.) выискивая что-то, что нам приглянется, либо же мы очень хорошо знаем то, что хотим найти, и тогда пользуемся фильтрами = сильно сужаем область поиска, рискуя пропустить интересные варианты, которые не сильно выходят за рамки области поиска, но которые могли бы быть интересны для нас, или же, сделав кучу надоедливых кликов, вдруг понять, что каталог ничего не может нам предложить. С последним немного проще — многие каталоги при применении фильтров показывают число вариантов.

Мы предлагаем подход, который объединяет в себе сложную сортировку и диапазонные фильтры. Для сайта-каталога это означает дополнение уже имеющегося функционала внешней надстройкой, которая берет на себя работу с предпочтениями пользователей (формирование правил выбора, хранение и использование удачных правил). В дальнейшем предполагается разработка варианта «all in box», возможно СУБД на новых принципах, но в данной статье об этом речь вести не будем.

От оценивания к сортировке

Появление многофакторной сортировки обусловлено тем, что сформированные пользователем (экспертом) правила выбора можно «свернуть» в математическую нелинейную функцию. Это означает, что с помощью такой функции может быть оценен каждый элемент каталога (каждому элементу каталога ставится в соответствие степень соответствия предпочтению пользователя). С одной стороны, это означает принципиальную возможность отсортировать весь каталог по предпочтению пользователя (т.е. так, чтобы первыми элементами были наиболее предпочтительные). Это существенно упрощает жизнь пользователя и должно позитивно сказаться на повышении интереса к такому сайту-каталогу. С другой стороны — вызывает дополнительные накладные расходы на саму сортировку, не дает делать частичные выборки по 10-20-50 и далее элементов на страницу. И здесь у нас вопросов к существующим СУБД нет. Так исторически сложилось — требуется «отбивать» вал «кусочных» запросов пользователей к СУБД как можно быстрее (чтобы пользователь не ждал слишком много). Но давайте задумаемся на момент: а не потому ли этих запросов так много, что мы не можем найти то, что ищем с помощью существующего интерфейса? Не желание ли разгрузить серверную часть заставляет нас (пользователей) тыкать все больше и больше? Мы делаем огромный процент бесполезных запросов, но мы ли виноваты в этом… Предлагаем дать возможность пользователям делать сложные запросы и честно предупредить, что придется подождать. Может конкретно вас бы это устроило: меньше кликов и больше толку = сэкономить силы на поиске и потратить их на анализ вариантов и т.п.

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

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

В сухом остатке

На сегодняшний день мы готовы показать альфа-тестовую версию с базовыми возможностями сортировки на примере проблемы покупки жилья. Стоит отметить главные особенности представляемого функционала:

  1. Сортировка реализована на стороне клиента (браузер).
  2. Удаленное формирование функции сортировки происходит БЕЗ обращений к каталогу. Требуются лишь общие сведения о диапазонах возможных значений параметров сортируемых объектов.
  3. Функция сортировки — анонимная функция JS (тот самый редкий случай формирования из строки «на лету»).
  4. Сортировка ВСЕГО каталога предполагает «прогон» через анонимную функцию (п.3) КАЖДОГО элемента каталога (реализовано перегрузкой встроенной функции сортировки).

О том, как пользоваться предлагаемым функционалом, лучше всего расскажет интерактивный тур на сайте проекта.

Ближайшие планы и перспективы

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

В грядущих публикациях планируется подробнее осветить процесс формирования СЛОЖНЫХ правил выбора с интерактивным тестовым функционалом, планируем новую тестовую версию с формированием СЛОЖНЫХ правил и/или введением условного каталога ноутбуков в качестве усложненного примера, а также учесть ваш feedback в дальнейшем развитии проекта. Спасибо за внимание! P.S. конструктивная критика идеи и тестовой (демонстрационной) версии проекта приветствуется :)

UPD: кажется, сервер оказался слабоват, если у кого вылетает «Connection error», пожалуйста попробуйте несколько позже (желательно обновить страницу)…

Ссылки

Сайт проекта: mcdm-project.org

Научные публикации по теме:

  • Pavlov, A.N. The Technique of Multi-Criteria Decision-Making in the Study of Semi-Structured Problems / A.N. Pavlov, D.A. Pavlov, A.A. Pavlov, A.A. Slin’ko // Proceedings of the 6th Computer Science On-line Conference 2017 (CSOC2017). April 2017. — Springer International Publishing Switzerland 2017, Vol 2: Cybernetics and Mathematics Applications in Intelligent Systems. P.131-140. DOI 10.1007/978-3-319-57264-2_13
  • Павлов, А.Н. Комбинированный метод многокритериального выбора управленческих решений на основе моделей представления знаний и планирования эксперимента / А.Н. Павлов, А.А. Павлов, Д.А. Павлов, А.А. Слинько // «Труды Военно-космической академии имени А.Ф. Можайского». – СПб.: ВКА им. А.Ф.Можайского, 2017. – Вып. 656. – C. 9-17
  • Павлов А.Н., Методология и технологии многокритериального анализа критичности отказов функциональных элементов общесудовых систем / А.Н. Павлов, А.Ю. Кулаков, Д.А. Павлов // Вторая международная научно-практическая конференция «Имитационное и комплексное моделирование морской техники и морских транспортных систем» (ИКМ МТМТС 2013), 3 июля 2013 г., Санкт-Петербург: Труды конференции / ОАО «Центр технологии судостроения и судоремонта» – СПб, 2013, С. 78-85
  • Павлов А.Н., Зеленцов В.А. Многокритериальный анализ влияния отдельных элементов на работоспособность сложной системы // Информационно-управляющие системы. — 2010, №6 (49), С.7-12
  • Павлов А.Н., Комбинированный метод многокритериального анализа критичности отказов элементов сложных объектов / А.Н. Павлов, В.А. Зеленцов, Е.А. Копытов, // 10-я Международная конференция “Reliability and Statistics in Transportation and Communication” (RelStat’10), 20–23 октября 2010, Рига, Латвия, ISBN 978-9984-818-34-4 — Рига: Transport and Telecommunication Institute, с. 353-360

Автор: Palich239

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js