Суперпозиция в задачах анализа данных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Швыдун Сергей Владимирович

• Швыдун Сергей Владимирович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Швыдун Сергей Владимирович

Введение

Глава 1. Задача суперпозиции: обзор литературы

1.1 Задачи выбора и суперпозиции

1.2 Суперпозиция как 13-я проблема Гильберта

1.3 Суперпозиция функций выбора и ее свойства

1.3.1 Исследование двухступенчатых моделей выбора

1.3.2 Нормативные свойства функций выбора

1.3.3 Замкнутость функций выбора относительно суперпозиции

Заключение по Главе

2. Свойства суперпозиций функций выбора, порождаемых многокритериальными процедурами

2.1 Процедуры многокритериального выбора

2.2 Нормативные свойства известных процедур многокритериального выбора

2.3 Нормативные свойства суперпозиций известных процедур многокритериального выбора

2.4 Вычислительная сложность известных процедур многокритериального выбора и их суперпозиций

Заключение по Главе

Глава 3. Суперпозиция в задачах анализа данных

3.1 Суперпозиция в задаче предсказания возникновения торнадо

3.1.1 Описание проблемы и методов ее решения

3.1.2 Описание исходных данных и их анализ

3.1.3 Суперпозиция надпороговых процедур выбора (модель 1)

2

3.1.4 Результаты прогнозирования

3.2 Суперпозиция в задаче поиска

3.2.1 Задача информационного поиска

3.2.2 Описание исходных данных и их анализ

3.2.3 Суперпозиция надпороговых процедур выбора (модель 2)

3.2.4 Результаты прогнозирования

3.3 Суперпозиция в задаче распределения спорных территорий в Арктическом регионе

3.3.1 Описание проблемы

3.3.2 Оценка уровня интереса стран и уровня удовлетворенности

3.3.3 Модели распределения спорных территорий и их сравнение

Заключение по Главе

Заключение

Приложение А. Описание правил многокритериального выбора

Приложение Б. Свойства известных процедур многокритериального выбора

Приложение С. Свойства суперпозиций известных процедур многокритериального выбора

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

Литература

Введение диссертации (часть автореферата) на тему «Суперпозиция в задачах анализа данных»

Введение

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

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

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

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

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

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

Задачи диссертационного исследования:

1. провести анализ зарубежных и отечественных работ, посвященных изучению различных моделей суперпозиции функций выбора;

2. определить список нормативных свойств, характеризующих рациональность функций выбора;

3. исследовать нормативные свойства существующих функций

выбора, лежащих в основе построенных моделей суперпозиции;

5

4. исследовать нормативные свойства моделей суперпозиции, а также их вычислительную сложность;

5. построить эффективную модель поиска релевантных страниц, основанную на суперпозиции функций выбора;

6. построить эффективную модель предсказания возникновения торнадо, основанную на суперпозиции функций выбора;

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

Степень разработанности проблемы. Задача представимости функций нескольких переменных посредством суперпозиции функций от меньшего числа переменных была сформулирована Д. Гильбертом в 1900 г. и называется 13-й проблемой Гильберта [5]. Самим Гильбертом была выдвинута гипотеза о невозможности данного представления и показано, что аналитические функции трех аргументов в общем случае не являются суперпозициями аналитических функций двух аргументов. В 1950-х гг. В.И. Арнольдом и А.Н. Колмогоровым была показана неоднозначность решения 13-й проблемы Гильберта. В ряде своих работ А.Н. Колмогоров и В.И. Арнольд получили теоремы, опровергающие гипотезу Гильберта в классе непрерывных функций [7-11]. В работе М. А. Айзермана и Ф. Т. Алескерова 1990 г. особое внимание было уделено различным функциям выбора, а также операциям (их композиции для создания новых функций) над ними [1]. Авторами исследована замкнутость областей, содержащих различные функции выбора, относительно операции суперпозиции. Помимо прочего, рассмотрены различные типы двухступенчатых процедур выбора, а также определены условия, при которых данные процедуры сводятся к одноступенчатым. Ряд других работ М. А. Айзермана, А. В. Малишевского, В. И. Вольского, Ф. Т Алескерова и Е. Чинара посвящен исследованию свойств некоторых двухступенчатых моделей выбора [13-14, 20]. Тем не

менее, на данный момент рассмотрены лишь некоторые общие свойства

6

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

Объектом исследования является принцип суперпозиции, предметом исследования - класс моделей, основанных на суперпозиции известных функций выбора.

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

Научная новизна. В рамках диссертационного исследования получены следующие новые научные результаты:

1. впервые исследованы свойства 28 известных правил многокритериального выбора и их суперпозиций на предмет удовлетворения существующим нормативным условиям;

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

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

Теоретическая значимость работы заключается в

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

2. определении списка нормативных свойств, которым удовлетворяют двухступенчатые модели суперпозиции,

основанные на известных процедурах многокритериального выбора;

3. исследовании вычислительной сложности рассматриваемых моделей суперпозиции;

4. разработке новых математических моделей поиска релевантных страниц, предсказания возникновения торнадо и распределении спорных территорий, основанных на суперпозиции различных функций выбора.

Практическая значимость диссертационного исследования

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

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

Апробация работы. Результаты диссертационного исследования докладывались на следующих научных семинарах, школах и конференциях: 1. 3-й международный семинар "Models of Influence and Network Theory", г. Париж (Франция). Название доклада: "Over-lath superposition algorithm and its use to the ranking of options in the problem of search", 14.05.2012-15.05.2012;

2. Общемосковский семинар ИПУ РАН "Экспертные оценки и анализ данных", г. Москва (Россия). Название доклада: "Алгоритмы ранжирования, основанные на идее суперпозиции, и их применение к задаче информационного поиска", 28.11.2012;

3. Конференция ITQM 2013, г. Сучжоу (Китай). Название доклада: "Super-threshold Procedures and Their Application to the Search Problem",

16.05.2013-18.05.2013;

4. Научный семинар МЛАВР НИУ ВШЭ, г. Москва (Россия). Название доклада: "Некоторые процедуры выбора и их свойства", 10.06.2013;

5. 12-е Всероссийское совещание по проблемам управления, г. Москва (Россия). Название доклада: "Исследование нормативных свойств двухступенчатых процедур выбора", 19.06.2014;

6. Конференция IFORS 2014, г. Барселона (Испания). Название доклада: "Two-Stage Superposition Choice Procedures and their Properties",

13.07.2014-18.07.2014;

7. Общемосковский семинар ИПУ РАН "Экспертные оценки и анализ данных", г. Москва (Россия). Название доклада: "Двухступенчатые процедуры выбора и их свойства", 28.01.2015;

8. Конференция MCO 2015, г. Мец (Франция). Название доклада: "Properties and Complexity of Some Superposition Choice Procedures",

11.05.2015-13.05.2015;

9. Конференция EURO2015, г. Глазго (Великобритания). Название доклада: "Normative properties of the superposition of multi-criteria choice procedures", 12.07.2015-15.07.2015;

10. Конференция CYBCONF 2017, г. Эксетер (Великобритания). Название доклада: "A Mathematical Approach to Conflict Resolution in the Arctic Region", 21.06.2017-23.06.2017.

11.Конференция IFORS 2017, г. Квебек (Канада). Название доклада: "Conflict resolution models in the Arctic region", 17.07.2017-21.07.2017;

12.Конференция MLSD'2017, г. Москва (Россия). Название доклада: "Superposition Models of Conflict Resolution in the Arctic Region", 02.10.2017-04.10.2017;

13.UTFORSK Norwegian-Russian Workshop on Arctic Logistics, г. Молде (Норвегия). Название доклада: "Allocation of Disputable Zones in the Arctic", 10.10.2017-12.10.2017;

14.Семинар ЦЭМИ РАН "Математическая экономика", г. Москва (Россия). Название доклада: "Распределение спорных территорий в Арктическом регионе", 06.02.2018;

15.Конференция EURO2018, г. Валенсия (Испания). Название доклада: "On various solutions of areas allocation problem", 8.07.2018-11.07.2018;

16.Общемосковский семинар НИУ ВШЭ "Математические методы анализа решений в экономике, бизнесе и политике", г. Москва (Россия). Название доклада: "Модели суперпозиции в анализе данных", 17.10.2018;

17.Autumn school "Current trends in decision-making analysis", г. Москва (Россия). Название доклада: "Superposition Models in Data Analysis", 07.11.2018;

18.Школа SVF-8063 School of Society and Advanced Technology in the Arctic, г. Лонгьир (Норвегия). Название доклада: "Superposition (Composition) Models in Data Analysis", 13.10.2019-19.10.2019.

Результаты исследования использовались в следующих грантах и научно-исследовательских проектах:

1. Грант РФФИ №12-01-00226 «Модели выбора, основанные на суперпозиции», руководитель: Алескеров Ф.Т., 2012-2014 гг.

2. Исследовательский проект «Математические модели принятия решений в социальных и экономических системах», руководитель проекта: Алескеров Ф.Т., ответственное подразделение: департамент математики факультета экономических наук НИУ ВШЭ, 2010 г.

3. Исследовательский проект «Конструирование экономических механизмов», руководитель проекта: Алескеров Ф.Т., ответственное подразделение: МЛАВР НИУ ВШЭ, 2011 г.

4. Исследовательский проект «Исследование новых методов и подходов в области математического моделирования и дизайна механизмов в социальной, экономической и политической сферах», руководитель: Алескеров Ф.Т., Маскин Э., ответственное подразделение: МЛАВР НИУ ВШЭ, 2013 г.

5. Исследовательский проект «Теоретическое и численное исследование современных математических моделей в социально-экономической, политической и финансовой сферах», руководители проекта: Алескеров Ф.Т., Маскин Э., ответственное подразделение: МЛАВР НИУ ВШЭ, 2014 г.

6. Исследовательский проект «Анализ данных и принятие решений в социально-экономических и политических системах», руководители проекта: Алескеров Ф.Т., Маскин Э., ответственное подразделение: МЛАВР НИУ ВШЭ, 2015 г.

7. Исследовательский проект «Анализ, выбор и принятие решений в социально-экономической, политической и финансовой сферах: новые модели, методы и алгоритмы», руководители проекта: Алескеров Ф.Т., Маскин Э., ответственное подразделение: МЛАВР НИУ ВШЭ, 2017 г.

Основные результаты исследования и положения, выносимые на защиту:

1. исследованы нормативные свойства 28 известных процедур многокритериального выбора и 617 двухступенчатых моделей суперпозиции и оценена их вычислительная сложность;

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

распределения спорных территорий в Арктическом регионе.

11

Личный вклад

Автором лично сформулированы и доказаны Теоремы 1-2 о свойствах известных процедур многокритериального выбора, а также построенных на их основе двухступенчатых моделей. Оценка вычислительной сложности процедур многокритериального выбора, приводимых в данном исследовании, получены автором лично.

Работа по предсказанию торнадо выполнена в соавторстве с Н. Н. Байбородовым, С. С. Деминым, к.т.н. В. И. Якубой, д.т.н. Ф. Т. Алескеровым, а также профессорами Университета Оклахомы М. Ричманом и Т. Трафалисом, в рамках которой автор занимался построением моделей, основанных на суперпозиции надпороговых процедур выбора, а также оценкой их эффективности.

Работа по предсказанию релевантности страниц выполнена в соавторстве с Е. О. Митичкиным, к.т.н. В. И. Якубой, а также д.т.н. Ф. Т. Алескеровым, в рамках которой автор занимался задачей выявления ключевых показателей в исходных данных, построением моделей суперпозиции, их программной реализацией и оценкой эффективности.

Работа по распределению спорных зон в Арктике выполнена в соавторстве с д.т.н. Ф. Т. Алескеровым, в рамках которой автор занимался сбором и обработкой исходных данных, построением моделей распределения спорных зон, в том числе основанных на принципе суперпозиции, а также программной реализацией данных моделей.

Список опубликованных статей, где отражены основные научные результаты диссертации.

Публикации в международных журналах квартиля Q1, индексируемых в базах Web of Science и Scopus:

1. Aleskerov, F., Shvydun, S. Allocation of Disputable Zones in the Arctic

Region. Group Decis Negot 28, 11-42 (2019).

Публикации в журналах/изданиях, индексируемых в базах Web of Science и Scopus:

2. Shvydun S., Aleskerov F., "A Mathematical Approach to Conflict Resolution in the Arctic Region", 2017 3rd IEEE International Conference on Cybernetics (CYBCONF), Exeter, 2017, pp. 145-151.

3. Shvydun S. (2015) Properties and Complexity of Some Superposition Choice Procedures. In: Modelling, Computation and Optimization in Information Systems and Management Sciences. Advances in Intelligent Systems and Computing, vol 360. Springer, Cham. P. 475-486.

4. Aleskerov F., Mitichkin E., Shvydun S., Yakuba V. Super-threshold Procedures and Their Application to the Search Problem // Procedia Computer Science. 2013. No. 17. P. 1121-1124.

Прочие публикации:

5. Aleskerov, F., Demin, S. & Shvydun, S. Superposition of Choice Functions and Its Application to Tornado Prediction and Search Problems. SN COMPUT. SCI. 1, 68 (2020).

6. Shvydun S. V. Superposition Models of Conflict Resolution in the Arctic Region // В кн.: Материалы 10-й международной конференции "Управление развитием крупномасштабных систем (MLSD'2017)", М.: ИПУ РАН, 2017. P. 452-455.

7. Aleskerov F., Baiborodov N., Demin S., Richman M., Shvydun S., Trafalis T., Yakuba V. Построение эффективной модели машинного обучения для предсказания торнадо. [Текст]: препринт WP7/2016/05. М.: Изд. дом Высшей школы экономики, 2016.

8. Shvydun S. V. Normative properties of multi-criteria choice procedures and their superpositions: I [Электронный ресурс]: препринт WP7/2015/07 (Часть 1), М.: Изд. дом Высшей школы экономики, 2015.

9. Shvydun S. V. Normative properties of multi-criteria choice procedures and their superpositions: II [Электронный ресурс]: препринт WP7/2015/07

(Часть 2), М.: Изд. дом Высшей школы экономики, 2015.

13

10.Швыдун С. В. Исследование нормативных свойств двухступенчатых процедур выбора // В кн.: XII Всероссийское совещание по проблемам управления ВСПУ-2014. М.: ИПУ РАН, 2014. С. 7977-7985.

Авторские свидетельства, патенты:

1. Fuad T. Aleskerov, Evgeny O. Mitichkin, Vyacheslav V. Chistyakov, Sergey V. Shvydun, Viacheslav I. Iakuba. USA Patent #US10275418 B2 «Method for selecting valid variants in search and recommendation systems», дата регистрации 30.04.2019.

2. Изобретение №2543315 «Способ отбора эффективных вариантов в поисковых и рекомендательных системах (варианты)», приоритет изобретения 22.03.2013, дата регистрации 27.01.2015 (соавторы: Алескеров Ф.Т., Митичкин Е.О., Чистяков В.В., Якуба В.И.).

3. Программа для ЭВМ №2013618228 «Выбор и ранжирование вариантов с использованием суперпозиции позиционных правил», дата государственной регистрации: 04.09.2013 (соавторы: Алескеров Ф.Т., Митичкин Е.О., Якуба В.И.).

Объем и структура работы. Диссертационная работа состоит из введения, трех глав и заключения. Глава 1 носит обзорный характер, в которой приведена общая постановка задачи многокритериального выбора, обсуждается сложность решения задачи выбора при наличии большого набора вариантов и критериев, прослеживается связь принципа суперпозиции с решением 13-й проблемы Гильберта и напоминается история решения этой проблемы, а также приводится аналитический обзор работ по исследованию суперпозиций функций выбора. Глава 2 посвящена исследованию свойств моделей суперпозиций, основанных на известных процедурах многокритериального выбора. В Главе 3 рассмотрены приложения суперпозиционных моделей к решению ряда прикладных задач.

Объем диссертационной работы составляет 164 страницы с 5 рисунками. Список литературы содержит 84 наименования.

Глава 1. Задача суперпозиции: обзор литературы

1.1 Задачи выбора и суперпозиции

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

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

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

Задача выбора формулируется следующим образом [1]. Рассмотрим конечное множество А вариантов (|Л| > 2), любое подмножество которого X Е 2а может быть предъявлено для выбора (далее - предъявление). Определим функцию выбора С() как некоторое отображение С: 2^ ^ 2^ с ограничением С(Х) с X для любого предъявляемого множества. Задача выбора состоит в выделении из предъявляемого множества X с помощью функции выбора С() непустого подмножества «наилучших» вариантов.

Классическая парадигма теории выбора основана на

экстремизационном подходе, согласно которому на рассматриваемом

15

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

С(Х) = {хе е X: р(у) > <р(х)}.

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

Следующей парадигмой теории выбора является парнодоминантный подход, основанный на попарном сравнении вариантов [2]. В таком случае строится бинарное отношение Р с X х X, отражающее попарное сравнение вариантов. Другими словами, если вариант х предпочтительнее варианта у, то хРу. Согласно данному подходу любой разумный выбор может быть сведен к выбору недоминируемых вариантов при их попарном сравнении, т.е.

с(х) = [хех^уех уРх}.

Наконец, 1950-х годах Г. Саймоном был предложен подход так называемого satisficing choice (выбор выше уровня удовлетворенности), согласно которому люди принимают решения не на основе парного сравнения вариантов, а на основе некоторого уровня удовлетворенности, и все, что выше этого уровня, пригодно для выбора [3]. Данный подход был сформулирован в терминах надпорогового выбора в [1,2], согласно которому

С(Х) = [хеХ№(х) > V(X)}, где V(X) - некоторый пороговый уровень, который имеется у индивида.

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

решение (ЛПР), выбирает наиболее подходящие варианты.

16

Отметим, что если общее число критериев относительно небольшое, выбор "лучших" вариантов можно осуществить с достаточно высокой точностью с помощью известных процедур многокритериального выбора. Тем не менее, если набор данных становится очень большим, задача выбора становится крайне трудоемкой. Заметим, что здесь и далее термин "очень большой" набор данных используется в рамках понятия "Большие данные" (Big Data), когда число вариантов и критериев может исчисляться тысячами или миллионами. В таком случае возникает проблема нахождения компромисса между точностью процедур многокритериального выбора и скоростью их работы. Чем выше точность результатов, тем больше критериев необходимо включить в рассмотрение, тем более сложные с вычислительной точки зрения процедуры необходимо применять, тем больше ресурсов (времени) потребуется на обработку информации. Напротив, использование грубых (приближенных) процедур выбора позволяет значительно сократить время поиска требуемой информации, что также негативно сказывается на точности полученных результатов. Таким образом, возникает потребность в построении новых способов решения исследуемой задачи, позволяющих получить качественные результаты за приемлемое время.

На данный момент имеется большое число прикладных задач, в

которых рассматривается проблема выбора на больших данных. Например,

при выборе места проживания человек принимает во внимание большое

число всевозможных признаков - стоимость проживания, удаленность от

центра города, места работы и других важных точек, уровень шума, уровень

преступности, качество инфраструктуры, экологические показатели и т.д.

Зачастую общее число признаков, характеризующих экономическую,

экологическую, криминогенную, политическую и прочие обстановки, может

исчисляться сотнями или даже тысячами, а общее число предъявляемых

вариантов может быть в тысячу раз выше. Другим хорошим примером задачи

выбора на больших объемах данных является действующая система

профилактики пожаров в г. Нью-Йорк (США). Целью системы является

17

ежедневный мониторинг степени пожароопасности каждого здания в городе, а также выявление наиболее опасных объектов. В [4] указано, что на данный момент система производит оценку более 7500 различных факторов риска, в то время как общее число рассматриваемых объектов свыше 300 тысяч. Нахождение с высокой точностью как можно большего числа пожароопасных объектов является основной и крайне значимой задачей в данной области. Таким образом, умение анализировать большие потоки информации и принимать на их основе взвешенные решения приобретает большую ценность при решении задачи выбора.

Одним из существующих подходов к решению задачи выбора при наличии большого набора вариантов и/или критериев является применение принципа суперпозиции. Напомним, что суперпозиция функций выбора заключается в последовательном применении (композиции) различных функций таким образом, что результаты применения одной функции предъявляются на вход другой функции [1]. В задачах анализа больших данных принцип суперпозии имеет ряд преимуществ. Основным преимуществом моделей, основанных на принципе суперпозиции, является их низкая вычислительная сложность, так как, применяя на первых этапах процедуры с низкой вычислительной сложностью, можно существенно сузить исходный набор рассматриваемых вариантов. Модели, основанные на принципе суперпозиции, зачастую также имеют высокую степень интерпретируемости, поскольку представляют собой комбинацию простых методов вместо одного сложного. Наконец, используя принцип суперпозиции, можно получить требуемое число "наилучших" вариантов за счет использования дополнительных процедур выбора.

Тем не менее, изменение рассматриваемого множества вариантов, а

также их оценок по некоторым критериям зачастую приводит к изменению

полученного выбора. Учитывая также, что суперпозиция функций не

удовлетворяет условию коммутативности [1], т.е. изменение порядка

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

18

возникает вопрос, связанный с исследованием свойств моделей, основанных на суперпозиции, на предмет их применения в различных задачах анализа данных.

Список литературы диссертационного исследования кандидат наук Швыдун Сергей Владимирович, 2020 год

Литература

1. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов: основы теории. М.: Наука, 1990. - 236 с.

2. Aleskerov F. T., Bouyssou D., Monjardet B. Utility Maximization, Choice and Preference / Edition Number 2. Berlin : Springer, 2007.

3. H.A. Simon, editor, Models of man: social and rational; mathematical essays on rational human behavior in a social setting, P. 241-260. J. Wiley, New York, 1957.

4. IdeaConnection. (2020). Big Data and the Future of Firefighting - Open Innovation success stories. URL: https://www.ideaconnection.com/open-innovation-success/Big-Data-and-the-Future-of-Firefighting-00761.html (дата обращения 23 января 2020).

5. Hilbert, David. Mathematical problems. Bull. Amer. Math. Soc. 8 (1902), no. 10, 437-479. https://projecteuclid.org/euclid.bams/1183417035.

6. Витушкин А. Г., "13-я проблема Гильберта и смежные вопросы", УМН, 59:1(355) (2004), 11-24.

7. Колмогоров А.Н., О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // Докл. АН СССР, том 108, с. 2, 1956.

8. Колмогоров А. Н., О представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одной переменной и сложения // ДАН СССР. -1957.-В. 5.-Т. 114. - С. 953-956.

9. Арнольд В. И., О функциях трех переменных, ДАН СССР, т. 114, № 4 (1957), 679—681.

10.Арнольд В.И., О представлении функций нескольких переменных в виде суперпозиции функций меньшего числа переменных, Мат. Просвещение, Сер. 2, вып. 3, (1958), 41-61.

11.Арнольд В. И., О представлении непрерывных функций трех переменных суперпозициями непрерывных функций двух переменных, Матем. сб., 1959, том 48(90), номер 1, 3- 74.

12.Aleskerov F. (1999), Arrovian Aggregation Models, Kluwer Academic Publishers, Dordrecht, Boston, London.

13.Aizerman, M. and Malishevski, A. (1986), Conditions for universal reducibility of a two-stage extremization problem to one-stage problem, Journal of Mathematical Analysis and Applications 118, pp. 361-388.

14.Vol'skiy, V. I. 1982. New characteristic conditions for a class of choice functions. Systems and Control Letters 2(3): 169-173.

15.Мулен Э. "Кооперативное принятие решений: Аксиомы и модели", Пер. с англ. - М: Мир, 1991, - 464 c. ISBN: 5-03-002131-0.

16.Алескеров Ф. Т., Юзбашев Д. В., Якуба В. И. Пороговое агрегирование трехградационных ранжировок // Автоматика и телемеханика. 2007. № 1. С. 147-152.

17.Aleskerov F., Chistyakov V., Kalyagin V. 'Social threshold aggregations', Social Choice and Welfare, v. 35, # 4, 2010, 627-646.

18.Aleskerov, F. (1985), Procedures of multicriterial choice, Preprints of the IFAC/IFORS Conference on Control Science and Technology for Development, Beijing, China, 858-869.

19.Aleskerov F. (1994), Multicriterial interval choice models, Information Sciences 1, 14-26.

20.Aleskerov F., Cinar Y. 'q-Pareto-scalar' Two-Stage Extremization Model and its Reducibility to One-stage Model' Theory and Decision, 65, 2008, 291-304.

21.Алескеров Ф. Т., Хабина Э. Л., Шварц Д. А. "Бинарные отношения, графы и коллективные решения", М.: Издательский дом ГУ-ВШЭ, 2006.

22.Алескеров Ф. Т., Курбанов Э., "О степени манипулируемости правил коллективного выбора", Автомат. и телемех., 1998, № 10, 134-146.

23.Вольский В. И. Процедуры голосования в малых группах с древнейших времен до начала XX века. / Препринты. Издательский дом ВШЭ. Серия WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2014.

24.Aleskerov F. T., Subochev A. (2009) Matrix-vector representation of various solution concepts// Working papers WP7/2009/03, Moscow: HSE Publishing House.

25.Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions // Working papers WP7/2008/03, Moscow: HSE Publishing House.

26.Arrow, K.J., Sen, A.K., Suzuruma, K. Handbook of Social Choice and Welfare, Vol. 1, Elsevier, London (2002).

27.Arrow, K. J. and Hervé, R., "Social Choice and Multicriterion Decision-Making." (1986).

28.D. Coppersmith and S. Winograd, Matrix Multiplication via Arithmetic Progressions, STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of Computing, 1987.

29.Aleskerov F. T., Meshcheryakova N. G., Nikitina A., Shvydun S. Key Borrower Detection by Long-Range Interactions / National Research University Higher School of Economics. Series WP BRP "Basic research program". 2016. No. 56.

30.Бараш Л.Ю., Щур Л.Н. Генерация случайных чисел и параллельных потоков случайных чисел для расчетов Монте-Карло. Моделирование и анализ информационных систем. 2012;19(2): 145-162.

31.NOAA National Centers for Environmental Information (NCEI) U.S. (2020), Billion-Dollar Weather and Climate Disasters: Overview. URL: https://www.ncdc.noaa.gov/billions/ (дата обращения 23 января 2020).

32.Straka J.M., Rasmussen E.N., Davies-Jones R.P., Markowski P.M., 2007: An observational and idealized numerical examination of low-level

counterrotating vortices toward the rear flank of supercells. E.J. Severe Storms Met., 2(8), 1-22.

33.Markowski P.M., Richardson Y.P., 2009: Tornadogenesis: Our current understanding, forecasting considerations, and questions to guide future research. Atmospheric Research, 93, 3-10.

34.Rhodes C.L., Senkbeil J.C., 2014: Factors contributing to tornadogenesis in landfalling Gulf of Mexico tropical cyclones, Meteorological Applications, 21, 940-947.

35.Adlerman E.J., Droegemeier K.K., Davies-Jones R., 1999: A numerical simulation of cyclic mesocyclogenesis. Journal of the Atmospheric Sciences, 56, 2045-2069.

36.Adrianto I., Trafalis T. B., Lakshmanan V., 2009: Support vector machines for spatiotemporal tornado prediction. International Journal of General Systems, 38(7), 759-776.

37.Trafalis T.B., Adrianto I., Richman M.B., Lakshmivarahan S., 2014: Machine-learning classifiers for imbalanced tornado data. Computational Management Science, 11, 403-418.

38.Marzban C., 2000: A neural network for tornado diagnosis. Neural Computing and Applications, 9, 133-141.

39.Lakshmanan V., Stumpf G., Witt A., 2005: A neural network for detecting and diagnosing tornadic circulations using the mesocyclone detection and near storm environment algorithms. 21st International Conference on Information Processing Systems, San Diego, CA, Amer. Meteor. Soc.

40.Breiman L., 2001: Random Forest. Machine Learning, 45(1), 5-32.

41.Rodriguez J.J., Kuncheva L.I., Alonso C.J., 2006: Rotation forest: a new classifier ensemble method. IEEE Trans Pattern Anal Mach Intell, 28(10), 1619-1630.

42.Kingfield D. M., LaDue J. G., Ortega K. L., 2012: An evaluation of tornado intensity using velocity and strength attributes from the WSR-88D

mesocyclone detection algorithm. Preprints, 26th Conf. on Severe Local Storms, Amer. Meteor. Soc., 3.2.

43.Браверман, Э.М., Мучник, И.Б. (1983). Структурные методы обработки эмпирических данных. М.: Наука

44.Aleskerov F., Baiborodov N., Demin S., Shvydun S., Trafalis T., Richman M., Yakuba V., 2016: Constructing an efficient machine learning model for tornado prediction. arXiv:1806.05857.

45.L. Breiman, J. Friedman, R. Olshen, and C. Stone, "Classification and Regression Trees", Wadsworth, Belmont, CA, 1984.

46.Roebber P.J., 2009: Visualizing multiple measures of forecast quality. Weather Forecast, 24, 601-608.

47.Experian.com. (2011). Surprise! Bing tops Google in search accuracy. URL: http://www.experian.com/hitwise/press-release-experian-hitwise-reports-google-share-of-searche.html (дата обращения 23 января 2020).

48.H. Li, T.Y. Liu, T. Qin, J. Xu, LETOR: A Benchmark Collection for Research on Learning to Rank for Information Retrieval, Information Retrieval Journal, Vol. 13, No. 4, 346-374, 2009.

49.Li, H. (2007). Learning to Rank: A New Technology for Text Processing. Tokyo: Tokyo University.

50.Lioma, C., Schuetze, H. (2010). Introduction to Information Retrieval. Stuttgart: Institute for National Language Processing .

51.Levene, M. (2006). An Introduction to Search Engines and Web Navigation. Edinburgh: Pearson Education Limited.

52.Вайз Д.А., Малсид М. Google. Прорыв в духе времени [2-е изд. с новым предисл. и послесл. авт.] - М.: Эксмо, 2007 г. - 368 с.

53.Liu, T.Y. (2009) Learning to Rank for Information Retrieval. Foundations and Trends® in Information Retrieval, 3 (3): 225-331

54.Manning C., Raghavan P. and Schütze H. (2008), Introduction to Information Retrieval, Cambridge University Press. Section 7.1.

55.Tao Qin and Tie-Yan Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013.

56.C. Zhai and J. Lafferty. A study of smoothing methods for language models applied to Ad Hoc information retrieval. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, P. 334-342. ACM Press New York, NY, USA, 2001.

57.В. М. Золотарев, "Вероятностные метрики", Теория вероятн. и ее примен., 28:2 (1983), 264-287.

58.Backlinko. (2020). Google's 200 Ranking Factors: The Complete List (2020). URL: https://backlinko.com/google-ranking-factors# (дата обращения 23 января 2020).

59.Gautier, D.L. et. al., (2009) "Assessment of Undiscovered Oil and Gas in the Arctic," Science, May 29, Volume 324, page 1175 - 1179.

60.Bird, K. J., Charpentier, R. R., Gautier, D. L., Houseknecht, D. W., Klett, T. R., Pitman, J. K., Moore, T. E., Schenk, C. J., Tennyson, M. E. and Wandrey, C. J. (2008) Circum-Arctic resource appraisal; estimates of undiscovered oil and gas north of the Arctic Circle: U.S. Geological Survey Fact Sheet 2008-3049, 4 p.

61.Koivurova, T. and Hossain, K. (2008). Offshore Hydrocarbon. Arctic TRANSFORM. URL: http://arctic-transform.org/download/OffHydBP.pdf (дата обращения 23 января 2020).

62.Arctic Council, Conservation of Arctic Flora and Fauna Working Group (2001) Arctic Flora and Fauna: Status and Conservation. Documentation. Conservation of Arctic Flora and Fauna Working Group (CAFF).

63.The European Science Foundation (ESF). (2014). Natural Resources in Polar Oceans. URL: http://archives.esf.org/fileadmin/Public_documents/ Publications/03_Natural_Resources.pdf (дата обращения 23 января 2020).

64.UN General Assembly, Convention on the Law of the Sea (UNCLOS), 10 December 1982, URL: http://www.refworld.org/docid/3dd8fd1b4.html (дата обращения 23 января 2020).

65.Humpert, M. (2012). Arctic Ocean Exclusive Economic Zone. The Arctic Institute. URL: https://www.thearcticinstitute.org/eez-arctic-high-res/ (дата обращения 23 января 2020).

66.United Nations (2017). Submissions, through the Secretary-General of the United Nations, to the Commission on the Limits of the Continental Shelf, pursuant to article 76, paragraph 8, of the United Nations Convention on the Law of the Sea of 10 December 1982. URL: http://www.un.org/depts/los/ clcs_new/commission_submissions.htm (дата обращения 23 января 2020).

67.United Nations (2009). Continental Shelf - submission to the Commission by Norway. URL: http://www.un.org/Depts/los/clcs_new/submissions_files/ submission_nor.htm (дата обращения 23 января 2020).

68.United Nations (2014). Continental Shelf - submission to the Commission by the Kingdom of Denmark. URL: http://www.un.org/depts/los/clcs_new/ submissions_files/submission_dnk_76_2014.htm (дата обращения 23 января 2020).

69.United Nations (2019). Continental Shelf - partial submission to the Commission by Canada. URL: https://www.un.org/Depts/los/clcs_new/ submissions_files/submission_can1_84_2019.html (дата обращения 23 января 2020).

70.Aleskerov, F. and Victorova, E. (2015) An analysis of potential conflict zones in the Arctic Region. Working paper WP7/2015/05. Moscow: HSE Publishing House, 20 p.

71.The CHNL Information Office. (2016). NSR - Transit Statistics. URL: https://arctic-lio.com/category/statistics/ (дата обращения 23 января 2020).

72.Brams, S.J., Taylor, A.D. (1996) Fair division. From cake-cutting to dispute resolution. Cambridge University Press.

73.Palfrey, T., Pogorelskiy, K. (2019). "Communication Among Voters Benefits the Majority Party," Economic Journal, Royal Economic Society, vol. 129(618), pages 961-990.

74.Brams S., Fishburn P. Approval voting // American Political Science Review. 1978. Vol. 72. No. 3. P. 831-847.

75.Алескеров Ф.Т., Ордешук П. Выборы. Голосование. Партии. М.: Academia, 1995.

76.Hare T. The election of representatives, parliamentary and municipal. Longmans, Green, Reader and Dyer. L., 1873.

77.Condorcet (M.J.A.N. Caritat, marquis de Condorcet). Essai sur l'application de l'analyse a la probabilité decisions rendues a la plurarité des voix. Paris, 1785.

78.Black D. (1958), The Theory of committees and elections (Cambridge University Press, Cambridge).

79.Nanson, E.J. (1907), Methods of Elections (British Government Bloue Book Miscellaneous No. 3).

80.Coombs, C. (1964), A Theory of Data. New York: Wiley.

81.Levit V.E., Mandrescu E. (2019) Critical and Maximum Independent Sets Revisited. In: Khachay M., Kochetov Y., Pardalos P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science, vol 11548. Springer, Cham.

82.Copeland, A.N. (1951), A reasonable social welfare function. Mimeo. University of Michigan. Ann Arbor. Seminar of Application of Mathematics to the Social Sciences.

83.Henriet, D. (1985), The Copeland choice function: an axiomatic characterization. Social Choice and Welfare 2:49-63.

84.Simpson, P.B. (1969). On defining areas of voter choice: Professor Tullock on stable voting. Quarterly Journal of Economics, 83, 478-490.