Разработка модели и метода линейной многокритериальной стратификации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Орлов Михаил Анатольевич

• Орлов Михаил Анатольевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Орлов Михаил Анатольевич

Введение

Глава 1. Разработка модели многокритериальной линейной стратификации

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

1.1.1. Использование собственного вектора

1.1.2. Разбиение по Парето

1.1.3. Правило Борда

1.1.4. Модифицированный метод к-средних

1.1.5. Пороговое агрегирование

1.1.6. Оптимизация линейных весов

1.2. Модель автоматической линейной многокритериальной стратификации и ее свойства

1.2.1. Модель и пример линейной стратификации

1.2.2. Аппроксимационная задача формирования линейной комбинации критериев

1.2.3. Влияние шкалы критериев на веса в задаче линейной многокритериальной стратификации

1.2.4. Отличие линейной стратификации от задачи кластер анализа

1.2.5. Отличие линейной стратификации от упорядочения по главной компоненте

Выводы по главе

Глава 2. Разработка и экспериментальная верификация алгоритмов линейной стратификации

2.1.1. Решение задачи линейной стратификации на основе эволюционного подхода

2.1.2. Решение задачи линейной стратификации на основе квадратичной оптимизации: алгоритм ЛинСтрат

2.1.3. Свойства алгоритма ЛинСтрат

2.2. Организация вычислительных экспериментов по сравнению алгоритмов стратификации и ранжирования

2.2.1. Методы стратификации, используемые в экспериментах

2.2.2. Генерация синтетических данных

2.2.3. Предобработка реальных данных

2.2.4. Оценка качества результатов стратификации

2.3. Эксперименты по сравнительной оценке методов стратификации на синтетических данных

2.3.1. Валидация алгоритма ЛинСтрат на синтетических данных

2.3.2. Влияние размерности данных

2.3.3. Влияние количества сгенерированных объектов

2.3.4. Влияние интенсивностей страт

2.3.5. Влияние размаха страт

2.3.6. Влияние зашумленности (толщины) страт

2.4. Экспериментальное сравнение методов стратификации и ранжирования на реальных данных

2.4.1. Библиометрические показатели публикационной активности

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

2.5. Использование линейной стратификации для приоритизации базовых станций

Выводы по главе

Глава 3. Применение метода ЛинСтрат в проблеме оценки научного вклада ученого (на примере разделов, связанных с анализом данных и машинным обучением)

3.1. Обзор подходов к оценке научного вклада ученых

3.2. Таксономический ранг ученого

3.3. Разработка тестовой базы для оценки таксономического ранга ученого

3.3.1. Таксономия разделов, связанных с анализом данных и машинным обучением

3.3.2. Формирование выборки ученых и вычисление их таксономических рангов83

3.3.3. Косвенные характеристики: показатели цитируемости и авторитетности... 86 3.4. Агрегированные критерии, соответствующие стратификации и их сравнение

Выводы по главе

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

4.1. Программная реализация алгоритмов решения задачи линейной стратификации

4.2. Программы для генерирования синтетических стратифицированных данных

4.3. Комплекс программ для проведения вычислительных экспериментов по сравнению методов стратификации и ранжирования

4.4. Сравнение программных реализаций алгоритмов по вычислительной производительности

Выводы по главе

Заключение

Список литературы

Приложение. Таксономия разделов, связанных с анализом данных и машинным обучением, по классификации ACM CCS

Введение диссертации (часть автореферата) на тему «Разработка модели и метода линейной многокритериальной стратификации»

Введение

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

- ранжирование университетов по уровню преподавания и научных разработок [2, 3, 4];

- ранжирование академических журналов по уровню цитируемости (с разбиением на квартили) [4, 5, 6, 7];

- многокритериальная ABC классификация ресурсов [8, 9, 10];

- ранжирование стран по уровню инноваций [11] и др.

Необходимость использования ранжированных разбиений возникает не только в задачах принятия решений, но и в других областях. Например, в социологии рассматривается так называемая социальная стратификация [22] населения на классы по уровню богатства/бедности; а в минералогии -стратификация пород по уровню залегания [12]. Поэтому удобно называть ранжированное разбиение стратификацией [13].

В большинстве приведенных задач стратификации рассматриваемые критерии сводятся воедино путем вычисления среднего или средневзвешенного среднего, причем веса критериев определяются экспертным путем, «вручную», либо же с помощью эвристической процедуры. Примером являются такие авторитетные рейтинги как World University Ranking (Times Higher Education), Technology Achievement Index (United Nations) и др.

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

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

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

- Страты упорядочены направлением «оси» вектора нормали, а кластеры -

нет.

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

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

Предметом исследования является разработка и обоснование методики построения многокритериальной линейной стратификации.

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

Эта цель предполагает решение следующих задач:

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

2. Провести анализ критерия этой модели с точки зрения его сходства и различия с другими критериями агрегирования.

3. Разработать эффективные численные методы построения (локально) оптимальной линейной стратификации и оценки параметров предложенной модели;

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

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

6. Использовать разработанный комплекс программ при решении значимых практически ориентированных задач многокритериальной стратификации.

Методы, использованные в исследовании:

1. Методы теории принятия решений, включая правило Борда, границы Парето и др.

2. Методы системного анализа, включая ABC-классификацию ресурсов и ранжирование по влиянию (Authority ranking).

3. Теоретические разработки в области кластер-анализа, включая аппроксимационную трактовку метода к-средних.

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

5. Методы разработки и проведения контролируемого вычислительного эксперимента.

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

1. Предложена геометрическая модель линейной стратификации, аппроксимирующая данные в виде совокупности «параллельных» гиперплоскостей - страт.

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

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

4. Разработан комплекс программ для численного решения задачи стратификации, генерации синтетических данных и проведения вычислительных экспериментов.

5. С использованием разработанного математического обеспечения проведены расчеты по верификации метода ЛинСтрат на синтетических данных и выявлены границы его применимости.

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

7. Проведен анализ различных компонент научного вклада (научный уровень результатов, цитируемость, авторитетность) на примере дисциплины «Анализ данных и машинное обучение».

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

Практическая значимость работы заключается в создании комплекса программ, реализующего алгоритмы линейной стратификации и предназначенного для решения исследовательских и прикладных задач. Этот комплекс программ применен для решения задачи приоритизации базовых станций в компании ПАО «МТС».

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

Апробация работы. Основные результаты работы докладывались на следующих семинарах и конференциях:

1. The Second International Conference on Information Technology and Quantitative Management (ITQM-2014), Москва, июнь 2014 г. Доклад на тему: «A concept of multicriteria stratification: definition and solution».

2. Conference «Optimization, Control, and Applications in the Information Age», July 2014, Chalkidiki, Greece. Доклад на тему: «Three aspects of the research impact by a scientist: measurement methods and an empirical evaluation».

3. Conference of the International Federation of Classification Societies, Bologna, Italy, July 2015. Доклад на тему: «Using taxonomies and aggregate rankings for measuring research impact».

4. Общемосковский постоянный научный семинар «Теория автоматического управления и оптимизации», Москва, октябрь 2015 г. Доклад на тему: «Проблема оценки научного вклада (на примере исследований по анализу данных и машинному обучению».

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

Личный вклад. Автором разработаны:

1. Математическая модель линейной стратификации на основе аппроксимации данных совокупностью «параллельных» гиперплоскостей - страт.

2. Численный метод ЛинСтрат для автоматического формирования линейной свертки критериев и стратификации на заданное число страт.

3. Методика и алгоритм генерации синтетических линейно стратифицированных данных.

4. Комплекс программ, реализующий алгоритм линейной стратификации, алгоритм генерации синтетических страт.

Автором проведена верификация разработанного метода стратификации на реальных и синтетических данных, а также его сравнение с популярными методами многокритериального ранжирования. Автор принимал участие в проекте по оценке составляющих научного вклада ученого на основе таксономии предметной области, в котором на практике успешно был применен разработанный алгоритм стратификации. Метод и комплекс программ были применены для решения задачи приоритизации базовых станций в компании ПАО «МТС».

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

Во введении раскрывается актуальности темы исследования. Ставятся цели и задачи исследования. Описывается объект и предмет исследования, а также теоретическая значимость и новизна.

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

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

В третьей главе метод линейной стратификации применяется в проблематике оценки научного вклада ученого. Рассматриваются три различных составляющие научного вклада. Один из них использует таксономию предметной области. Уровень результатов оценивается в соответствии с рангами тех понятий таксономии, которые возникли или были существенно преобразованы благодаря этим результатам. Другие два - по уровню цитируемости и по уровню авторитетности. Для агрегирования отдельных критериев внутри этих подходов используется предлагаемый метод многокритериальной линейной стратификации. Для того, чтобы сравнить все три подхода, используется выборка 30 специалистов в области анализа данных и машинного обучения из разных стран. В качестве таксономии предметной области используется соответствующую часть многоуровневой классификации компьютерных наук, разработанной всемирной Ассоциацией вычислительных машин в 2012 г. несколько модифицированная, чтобы точнее отобразить результаты, полученные учеными из выборки.

Исследуемый метод позволяет получить агрегированные критерии по всем трем аспектам.

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

В заключении описаны основные результаты работы:

1. Предложена математическая модель многокритериальной линейной стратификации.

2. Разработан численный метод формирования многокритериальной линейной стратификации.

3. Разработан метод генерации линейных стратифицированных данных.

4. Разработан комплекс программ для численного решения задачи стратификации, генерации синтетических данных и проведения вычислительных экспериментов.

5. Модель, метод и комплекс программ верифицированы на синтетических и реальных данных.

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

7. Метод и комплексы программ были применены для задачи приоритезации базовых станций в компании ПАО «МТС».

Основные результаты диссертационного исследования опубликованы в 6 работах общим объемом 7,5 п.л.; личный вклад автора составляет 3,7 п.л.

Работы, опубликованные автором в рецензируемых научных изданиях, входящих в международные реферативные базы данных и системы цитирования (Web of Science, Scopus Web of Science, Scopus Astrophysics, Data System, PubMed, MathSciNet, zbMATH, Chemical Abstracts, Springer, Agris, GeoRef):

1. Orlov M.A. A concept of multicriteria stratification: a definition and solution / М.А. Orlov, B.G. Mirkin // Procedia Computer Science. - 2014. - Vol. 31. - P. 273-280. -0,75 п.л. (личный вклад автора - 0,5 п.л.).

2. Orlov M.A. Three aspects of the research impact by a scientist: measurement methods and an empirical evaluation / М.А. Orlov, B.G. Mirkin // Optimization, Control, and Applications in the Information Age. - Springer International Publishing, 2015. - P. 233-259. - 0,8 п.л. - (личный вклад автора - 0,5 п.л.).

Публикации в ведущих научных рецензируемых журналах, рекомендованных ВАК Министерства образования и науки РФ:

1. Орлов М.А. Алгоритм формирования многокритериальной стратификации // Бизнес-информатика. - 2014. - №. 4 (30). - С. 24-35. - 0.77 п. л.

Другие публикации:

1. Орлов М.А. Методы многокритериальной стратификации и их экспериментальное сравнение. WP7/2013/03. / М.А. Орлов, Б.Г.Миркин // М.: Изд. Дом Высшей школы экономики. - 2013. - 32 c. - 1,9 п.л. (личный вклад автора - 0,7 п.л.).

2. Orlov M.A. Research Impact: level of results, citation, merit. WP7/2014/09. / Mirkin B.G., Orlov M.A // М.: Изд. дом Высшей школы экономики. - 2014. - 40 p. - 2,4 п.л. (личный вклад автора - 0,9 п.л.).

3. Orlov M. Qualitative Judgement of Research Impact: Domain Taxonomy as a Fundamental Framework for Judgement of the Quality of Research / F. Murtagh, M. Orlov, B. Mirkin // arXiv preprint arXiv:1607.03200. - 2016. - 22 p. - 0,9 п.л. (личный вклад автора - 0,3 п.л.).

Глава 1. Разработка модели многокритериальной линейной стратификации

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

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

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

Ранжированию объектов с заданным числом рангов в литературе не уделяется внимание. Обычно строят полное упорядочивание рассматриваемых

вариантов и лишь потом присваивают объектам ранги, на основе некоторого эвристического правила. Например, распространенной практикой при ранжировании научных журналов является разбиение множества журналов на квартили и присвоение объектам первой квартили ранга 1, второй квартили ранга 2 и так далее. Или присваивают ранг 1 первым 20%, ранг 2 следующим 30%, а оставшимся - ранг 3, как принято в ABC-классификации, в маркетинге. Поэтому будем рассматривать методы ранжирования и их возможные модификации для получения необходимого количества страт. При заданном интегральном критерии разбиение на фиксированное число страт легко найти, например, применением одномерной процедуры к-средних к интегральному критерию. Это позволяет включить в рассмотрение и методы упорядоченного ранжирования.

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

1. Ранжирование по одному агрегированному критерию, являющемуся линейной сверткой критериев [14, 15, 16]. В основе метода лежит постулат о том, что уменьшение одного критерия может быть «погашено» увеличением другого критерия («замещение») [17]. При этом коэффициенты замещения критериев являются постоянными (не зависят от объектов).

2. Ранжирование на основе индивидуальных критериев путем использования соответствующего отношения многомерного упорядочения. При этом индивидуальные критерии рассматриваются как несравнимые, так что нельзя заместить один другим.

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

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

этот подход был разработан в статье [18]. Другим примером линейного метода, является метод согласования экспертных оценок [19], в этом подходе начальные оценки ранжирований и весов задаются экспертно, а затем эти оценки корректируются таким образом, чтобы полученные веса и ранжирования были согласованы друг с другом.

Ко второму типу можно отнести ряд методов теории коллективного выбора [20, 21], которые позволяют упорядочивать варианты, используя ранжирования по отдельным критериям.

К третьему типу относятся, например, методы, разработанные в статьях [ 8, 9] применительно к задаче разделения ресурсов фирмы на группы по степени важности (ABC-анализ), весовые коэффициенты здесь находятся из решения задачи линейной оптимизации. Хотя ранг объекта в данном случае вычисляется путем линейной свертки с весами, но для каждого объекта набор весов индивидуален, т.е. зависит от местоположения сравниваемых вариантов. В работе [10] для решения задачи ABC-анализа были предложены методы разбиения на основе критерия сходства результирующей многомерной классификации с результатами классификаций по каждому из критериев. Также к третьему типу принадлежат некоторые методы ранжирования с использованием информации о предпочтениях лица, принимающего решения (ЛПР) [22, 23, 24, 25, 26]. В работе [1 ] предложен расширенный вариант алгоритма к-средних, который использует метрику, учитывающую предпочтения ЛПР. В [27] ранжирование вариантов и их объединение в кластеры производится на основе матрицы парных сравнений вариантов. Также в работе [28] предлагается метод строящий ранжирующую функцию, на основе нелинейного общения метода главных компонент.

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

являются параллельными гиперплоскостями, ортогональными вектору весовых коэффициентов.

Сначала рассмотрим популярный метод первого типа, под названием ранжирование по влиянию (authority ranking), использующий линейную свертку весов, получаемых с использованием собственного вектора, сродни подходу page rank, используемому поисковой системой Гугл. Затем методы второго типа, т.е. ранжирование по несравнимым критериям: разбиение Парето (partition via maximal elements), правило Борда [29] (Borda count), модифицированный метод к-средних (extended k-means) и метод порогового агрегирования. И наконец, метод линейной оптимизации весов (linear weight optimization), который можно отнести к третьему типу в рассматриваемой классификации методов.

1.1.1. Использование собственного вектора

Этот метод был предложен в [18] для построения ранжирования авторов научных публикаций, участвующих в различных конференциях, как дальнейшее развитие методов, основанных на вычислении собственного вектора, соответствующего максимальному собственному числу определенной матрицы см., например, [30, 31, 32]. Правило, по которому строится ранг, опирается на два положения:

1. Объекты, имеющие высокий ранг, имеют высокую оценку по критериям с большими весами.

2. Вес критерия тем выше, чем больше его значения для объектов с высокими рангами.

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

Г = Х^ + Xi2W1 +-----+ i = 1 ... П

= ХljГl +Х2jr2 + - + Хп)гп^ = 1 ...т

В первых п уравнениях системы (1) исходные переменные заменим нормированными а^ = —. Полученную из данных коэффициентов матрицу

обозначим А, а в оставшихся т уравнениях произведем замену = —

¿¿=1

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

г = аш ш = вг

(2)

Подставляя ш из второго уравнения в первое, получаем, что искомый ранг г является собственным вектором матрицы ЛБ, соответствующим ее максимальному собственному значению, равному единице [18].

1.1.2. Разбиение по Парето

Рассмотрим векторное отношение R «больше» такое, что для двух вариантов х, у £ X имеет место xRy если и только если Х} > у для всех у, причем хотя бы одно неравенство строгое. На каждом шаге находим множество недоминируемых объектов х = {Ь £ Х|3у £ X:yRb} , которые объединяются в класс Сг . Полученный класс исключается из рассмотрения, и процедура повторяется для оставшихся объектов Х\Сг пока множество X не пусто [33].

Чтобы получить страты из слоев несравнимых по Парето объектов, можно воспользоваться идеей агломеративной кластеризации и расстояния до границы Парето. Заметим, что идея границ Парето использовалась также в [34] для задачи упорядоченной классификации (целевая переменная задана). Будем объединять

группы объектов, находящиеся близко друг к другу с точки зрения некоторой метрики d(Ci,Cj), задающей расстояние между группами точек Ct и Cj. Чтобы расстояние между стратами было наибольшим, а расстояние внутри страт наименьшим, необходимо найти две пары соседних классов, имеющих максимальное расстояние d(Ci,Ci+1) и d(Cj, CJ+1),затем построить страты S1 =

{Ci, С2, •••, С{\, S2 = {Ci+1, С2,..., Cj}, S3 = {Cj+i, С2,..., cs}.

Процедура получения страт из слоев недоминируемых по Парето вариантов: На входе: объекты X = (xi, %2, • ■■, х^) На выходе: страты S = {51,52,53}

1. Найти разбиение Парето C1,C2,.,CS.

2. Найти расстояния между соседними классами Rk = d(Ck, Ск+1),р = 1, ...,s — 1.

3. Вычислить индексы i = argmax(Rk), j = argmax(Rp),p > i.

4. Построить страты S1 = {С1, C2,..., C^}, S2 = {Ci+1, C2,..., Cj}, S3 = {Cj+1, C2, •■■, Cs}.

Список литературы диссертационного исследования кандидат наук Орлов Михаил Анатольевич, 2017 год

Список литературы

1. De Smet Y., Guzman L. M. Towards multicriteria clustering: An extension of the k-means algorithm // European Journal of Operational Research. - 2004. - Vol. 158. - №. 2. - P. 390-398.

2. The Complete University League Guide. URL: http://www.thecompleteuniversityguide.co.uk/leaguetables/ (дата обращения: 25.10.2014).

3. QS World University Rankings - Methodology. URL: https://www.topuniversities.com/university-rankings (дата обращения: 16.02.2017).

4. Liebowitz S.J., Palmer J.P. Assessing the relative impacts of economics journals // Journal of Economic Literature. - 1984. - Vol. 22. - №. 1. - P. 77-88.

5. SCImago Journal & Country Rank. URL: http://www.scimagojr.com (дата обращения: 14.02.2014).

6. Gonzalez Pereira B., Guerrero Bote V., Moya Anegon F. A new approach to the metric of journals scientific prestige: The SJR indicator // Journal of Informetrics. - 2010. - P. 379-391.

7. Cornillier F., Charles V. Measuring the attractiveness of academic journals: A direct influence aggregation model // Operations Research Letters. - 2015. -Vol. 43. - №. 2. - P. 172-176.

8. Ng W.L. A simple classifier for multiple criteria ABC analysis // European Journal of Operational Research. - 2007. - Vol. 177. - №. 1. - P. 344-353.

9. Ramanathan R. ABC inventory classification with multiple-criteria using weighted linear optimization // Computers & Operations Research. - 2006. - Vol. 33. -№. 3. - P. 695-700.

10. Белов В.В., Коричнева Ю.Л. Многомерная abc-классификация. Критерии качества и канонические алгоритмы // Бизнес-информатика. - 2012. -№. 1 (19). - C. 9-16.

11. The Bloomberg Innovation Index - Bloomberg Business. URL: https://www.bloomberg.com/graphics/2015-innovative-countries/ (дата обращения: 19.02.2017).

12. Montenari M. Stratigraphy and Timescales. - Amsterdam: Academic Press (Elsevier), 2016. - 518 p.

13. Greenwell R.N., Krauze T., Raymond N. Partially ordered sets and stratification // Mathematical Social Sciences. - 2013. - Vol. 66. - №. 3. - P. 307-315.

14. Подиновский В.В., Потапов М.А. Метод взвешенной суммы критериев в анализе многокритериальных решений: pro et contra // Бизнес-информатика. - 2013. - №. 3 (25) - С. 307-315.

15. Choo E.U., Schoner B., Wedley W.C. Interpretation of criteria weights in multicriteria decision making // Computers & Industrial Engineering. - 1999. - Vol. 37.

- №. 3. - С. 527-541.

16. Fishburn P.C. Letter to the editor - additive utilities with incomplete product sets: application to priorities and assignments // Operations Research. - 1967. -Vol. 15. - №. 3. - P. 537-542.

17. Keeney R.L., Raiffa H. Decisions with multiple objectives: preferences and value trade-offs. - Cambridge: Cambridge university press, 1993. - 569 p.

18. Sun Y., Han J., Zhao P., Yin Z., Cheng H. Rankclus: integrating clustering with ranking for heterogeneous information network analysis // Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. - 2009. - P. 565-576.

19. Kuznetsov M.P., Strijov V.V. Methods of expert estimations concordance for integral quality estimation // Expert Systems with Applications. - 2014. - Vol. 41. -№. 4. - P. 1988-1996.

20. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. - М.: Изд. дом НИУ ВШЭ, 2016. - 300 c.

21. Arrow K.J. Social choice and individual values. Vol. 12. - New York: Willey, 1963. -124 p.

22. Figueira J.R., Gerco S., Roy B. An overview of ELECTRE methods and their recent extensions // Journal of Multi-Criteria Decision Analysis. - 2013. - Vol. 20.

- №. 1-2. - P. 61-85.

23. Радаев В.В., Шкаратан О.И. Социальная стратификация. - М: Аспект Пресс, 1996. - 318 с.

24. Brans J.P., Vincke P. Note - A Preference Ranking Organisation Method: The PROMETHEE Method for Multiple Criteria Decision-Making // Management science. - 1985. - Vol. 31. - №. 6. - P. 647-656.

25. Koksalan M., Mousseau V., Ozpeynirci Ô. A new outranking-based approach for assigning alternatives to ordered classes // Naval Research Logistics (NRL). - 2009. - Vol. 56. - №. 1. - P. 74-85.

26. Zopounidis C., Doumpos M. Multicriteria classification and sorting methods: A literature review // European Journal of Operational Research. - 2002. -Vol. 138. - №. 2. - P. 229-246.

27. De Smet Y., Nemery P., Selvaraj R. An exact algorithm for the multicriteria ordered clustering problem // Omega. - 2012. - Vol. 40. - №. 6. - P. 861869.

28. Li C.G., Mei X., Hu B.G. Unsupervised ranking of multi-attribute objects based on principal curves // IEEE Transactions on Knowledge and Data Engineering. -2015. - Vol. 27. - №. 12. - P. 3404-3416.

29. de Borda J.C. Mémoire sur les élections au scrutin // Memoires de l'Academie Royale des Sciences. - 1781. - P. 657-665. (English trans.: de Grazia A // Isis. - 1953. - 44 p.).

30. Берж К. Теория графов и ее применения. - М: Издательство иностранной литературы, 1962. - 320 c.

31. Page L., Brin S., Motwani R., Winograd T. The PageRank citation ranking: Bringing order to the web. Technical Report. - Stanford InfoLab - 1999. URL: http://ilpubs.stanford.edu:8090/422/ (дата обращения: 15.09.2017).

32. Миркин Б.Г. Проблема группового выбора. - М: Наука. Гл. ред. физ.-мат. лит, 1974. - 256 c.

33. Aleskerov F., Ersel H., Yolalan R. Multicriterial ranking approach for evaluating bank branch performance // International journal of information technology & decision making. - 2004. - Vol. 3. - №. 02. - P. 321-335.

34. Stenina M.M., Kuznetsov M.P., Strijov V.V. Ordinal classification using Pareto fronts // Expert Systems with Applications. - 2015. - Vol. 42. - №. 14. - P. 5947-5953.

35. Saaty T.L. How to make a decision: the analytic hierarchy process // European journal of operational research. - 1990. - Vol. 48. - №. 1. - P. 9-26.

36. Подиновский В.В., Подиновская О.В. О некорректности метода анализа иерархий // Проблемы управления.- 2011.- №. 1. - С. 8-13.

37. Подиновская О.В. Метод анализа иерархий как метод поддержки принятия многокритериальных решений // Информационные технологии моделирования и управления. - 2010. - №. 1 (60). - С. 71-80.

38. Aleskerov F.T., Chistyakov V.V., Kalyagin V.A. The threshold aggregation // Economics Letters. - 2010. - Vol. 107. - №. 2. - P. 261-262.

39. Алескеров Ф.Т., Катаева Е.С., Писляков В.В., Якуба В.И. Оценка вклада научных работников методом порогового агрегирования // Управление большими системами. - 2013. - № 44 - С. 172-189.

40. Aleskerov F.T, Chistyakov V.V., Kalyagin V.A. Multiple criteria threshold decision making algorithms. Препринт WP7/2010/02 // М.: Изд. дом ГУ ВШЭ. -2010. - 40 p.

41. Charnes A., Cooper W, Lewin A.Y., Seiford L.M. Data Envelopment Analysis: Theory, Methodology and Applications. - Boston: Kluwer Academic Publishers, 1994. - 513 p.

42. QS Best Student Cities. URL: https://www.topuniversities.com/best-student-cities (дата обращения: 16.02.2017).

43. QS Best Student Cities 2016: Methodology. URL: https://www.topuniversities.com/best-student-cities/methodology (дата обращения: 16.02.2017).

44. Nardo M., Saisana M., Saltelli A., Tarantola S., Hoffman A., Giovannini E. Handbook on Constructing Composite Indicators: Methodology and User Guide // OECD Publishing. - 2005. - 108 с.

45. Корф В.П. Оценка конкурентоспособности ведущих российских университетов с использованием метода главных компонент // Бизнес-информатика. - 2014. - №. 2 (28). - С. 63-71.

46. Mirkin B. Core Concepts in Data Analysis: Correlation, Summarization, Visualization. - London: Springer, 2011. - 410 p.

47. Fogel D.B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence // The Institute of Electrical Engineers. - New York - 1995.

48. Kennedy J. F., Eberhart R. C., Shi Y. Swarm intelligence. - San Francisco, USA: Morgan Kaufmann Publishers, 2001. - 512 p.

49. Byrne W. Alternating minimization and Boltzmann machine learning // IEEE Transactions on Neural Networks. - 1992. - Vol. 3. - №. 4. - P. 612-620.

50. Gunawardana A., Byrne W. Convergence theorems for generalized alternating minimization procedures // Journal of Machine Learning Research. - 2005. -Vol. 6. - №. Dec. - P. 2049-2073.

51. MacQueen J. Some methods for classification and analysis of multivariate observations // Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. - 1967. - Vol. 1. - №. 14. - P. 281-297.

52. Mirkin B. Clustering: a data recovery approach. - Boca Raton: CRC Press, 2012. - 374 p.

53. Gill P.E., Murray W., Wright M. H. Numerical linear algebra and optimization. Vol. 1. - Redwood City, CA: Addison-Wesley, 1991. - 74 p.

54. Bradley P.S., Mangasarian O.L. K-plane clustering // Journal of Global Optimization. - 2000. - Vol. 16. - №. 1. - P. 23-32.

55. Huang J.Z., Ng M.K., Rong H., Li Z. Automated variable weighting in k-means type clustering // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2005. - Vol. 27. - №. 5. - P. 657-668.

56. De Amorim R.C., Mirkin B. Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering // Pattern Recognition. - 2012. -Vol. 45. - №. 3. - P. 1061-1075.

57. Milligan G.W., Isaac P.D. The validation of four ultrametric clustering algorithms // Pattern Recognition. - 1980. - Vol. 12. - №. 2. - P. 41-50.

58. Kemeny J.G., Snell J.L. Mathematical models in the social sciences. - New York; Toronto; London: Blaisdell Publishing Company, 1962. - 145 p.

59. Mirkin B.G., Fenner T.I. Tied rankings, ordered partitions, and weak orders: Distance and consensus. Working paper WP7/2016/08 // Moscow: Higher School of Economics Publ. House. - 2016. - 32 p.

60. Scimago Lab: Research and Web Analytics. URL: http://www.scimagolab.com/ (дата обращения: 14.01.2014).

61. Scopus. URL: http://www.scopus.com (дата обращения: 22.01.2014).

62. Mañana-Rodríguez J. A critical review of SCImag Journal & Country Rank // Research Evaluation. - 2014 - №. 23(2). - P. 1-12.

63. Siebelt M., Siebelt T., Pilot P., Bloem R.M., Bhandari M., Poolman R.W. Citation analysis of orthopaedic literature; 18 major orthopaedic journals compared for Impact Factor and SCImago // BMC Musculoskeletal Disorders. - 2010. - Vol. 11. -№. 1. URL: https://bmcmusculoskeletdisord.biomedcentral.com/articles/10.1186/1471-2474-11-4 (дата обращения: 16.09.2017).

64. Spreckelsen C., Deserno T.M., Spitzer K. Visibility of medical informatics regarding bibliometric indices and databases // BMC medical informatics and decision making. - 2011. - Vol. 11. - №. 1. URL: https://bmcmedinformdecismak.biomedcentral.com/articles/10.1186/1472-6947-11-24 (дата обращения: 16.09.2017).

65. Алескеров Ф.Т, Писляков В.В, Субочев А.Н, Чистяков А.Г. Построение рейтингов журналов по менеджменту с помощью методов теории коллективного выбора. Препринт WP7/2011/04 // М.: Изд. дом ВШЭ. - 2011. - 44 с.

66. Hirsch J. E. An index to quantify an individual's scientific research output // Proceedings of the National academy of Sciences of the United States of America. -2005. - P. 16569-16572.

67. Using The Thomson Reuters Impact Factor - Clarivate Analytics. URL: http://wokinfo.com/essays/using-impact-factor/ (дата обращения: 16.09.2017).

68. Миркин Б.Г. О понятии научного вклада и его измерителях // Управление большими системами. - 2013. - № 44 - С. 292-307.

69. Canavan J., Gillen A., Shaw A. Measuring research impact: developing practical and cost-effective approaches // Evidence & Policy: A Journal of Research, Debate and Practice. - 2009. - Vol. 5. - №. 2. - P. 167-177.

70. Engels T.C.E. Goose P., Dexters N., Spruyt E.H.J.. Group size, h-index, and efficiency in publishing in top journals explain expert panel assessments of research group quality and productivity // Research Evaluation. - 2013. - P. 224-236.

71. Чеботарев П.Ю. Оценка ученых: пейзаж перед битвой // Управление Большими Системами. - 2013. - №. 44. - С. 506-537.

72. Поляк Б.Т. Наукометрия: кого мы лечим? // Управление большими системами: сборник трудов. - 2013. - №. 44. - C. 161-170.

73. Hicks D., Wouters P., Waltman L., De Rijcke S., Rafols I. The Leiden Manifesto for research metrics // Nature. - 2015. - Vol. 520. - №. 7548. - P. 429-431.

74. Thompson Reuters intellectual property and science. URL: http://ipscience.thomsonreuters.com/ (дата обращения: 16.10.2016).

75. Григорьев Ю. Д. Некоторые проблемы перехода к современной системе управления вузовской наукой // Управление большими системами: сборник трудов. - 2013. - №. 44. - C 83-105.

76. Орлов А. И. Наукометрия и управление научной деятельностью // Наукометрия и экспертиза в управлении наукой. - М.: ИПУ РАН, 2013. - С. 538567.

77. Alberts B. Impact factor distortions // Science. - 2013. - Vol. 340. - №. 6134. - P. 787-787.

78. Bollen J., van de Sompel H., Hagberg A. & Chute R. A principal component analysis of 39 scientific impact measures // PloS one. - 2009. - Vol. 4. - №. 6. - P. e6022.

79. Aragón A.M. A measure for the impact of research. - Scientific reports. -2013. - Vol. 3. URL: https://www.nature.com/articles/srep01649 (дата обращения: 16.09.2016).

80. Eisen J.A., MacCallum C.J., Neylon C. Expert failure: re-evaluating research assessment // PLoS Biol. - 2013. - Vol. 11. - №. 10. - P. e1001677.

81. Lee, F.S., Pham, X., Gu, G. The UK research assessment exercise and the narrowing of UK economics // Cambridge Journal of Economics. - 2013. - №. 37(4). -P 693-717.

82. Abramo G., Cicero T., D'Angelo C. A. National peer-review research assessment exercises for the hard sciences can be a complete waste of money: the Italian case // Scientometrics. - 2013. - Vol. 95. - №. 1. - P. 311-324.

83. San Francisco Declaration on Research Assessment (DORA). URL: http://www.am.ascb.org/dora/ (дата обращения: 16.10.2014).

84. CARM Dictionary of Science. URL: http://carm.org/dictionary-taxonomic-rank (дата обращения: 15.02.2017).

85. The 2012 ACM Computing Classification System. URL: http://www.acm.org/about/class/2012 (дата обращения: 17.10.2014).

86. The 1998 ACM Computing Classification System. URL: http://www.acm.org/about/class/1998/ (дата обращения: 17.10.2014).

87. Han J., Pei J., Kamber M. Data mining: concepts and techniques. -Waltham, USA: Elsevier, 2011. - 703 p.

88. Дуда Р. Распознавание образов и анализ сцен. - М.: Книга по Требованию, 2013. - 508 с.

89. Osterloh M., Frey B. S. Ranking games // Evaluation review. - 2015. -Vol. 39. - №. 1. - P. 102-129.

90. Van Raan A.F.J. Comparison of the Hirsch-index with standard bibliometric indicators and with peer judgment for 147 chemistry research groups // Scientometrics. - 2006. - Vol. 67. - №. 3. - P. 491-502.

91. Игра в цыфирь, или как теперь оценивают труд учёного (сборник статей о библиометрике). - М: МЦНМО, 2011. - 72 c.

92. Matlab, Optimization Toolbox. URL: https://www.mathworks.com/help/optim/ (дата обращения: 15.02.2017).

93. Matlab, Statistics Toolbox. URL: https://www.mathworks.com/help/stats/ (дата обращения: 15.02.2017).

94. Matlab, Quadratic programming, URL: https: //www. mathworks .com/help/optim/ug/quadprog.html (дата обращения: 15.02.2017).

Приложение. Таксономия разделов, связанных с анализом данных и машинным обучением, по классификации ACM CCS 2012

Таблица 1. Таксономия ACM CCS 2012 (на языке оригинала)

Индекс Название предмета

Theory of

1. computation

1.1. Theory and algorithms for application domains

1.1.1. Machine learning theory

1.1.1.1. Sample complexity and generalization bounds

1.1.1.2. Boolean function learning

1.1.1.3. Unsupervised learning and clustering

1.1.1.4. Kernel methods

1.1.1.4.1. Support vector machines

1.1.1.4.2. Gaussian processes

1.1.1.4.3.* Modelling

1.1.1.5. Boosting

1.1.1.6. Bayesian analysis

1.1.1.7. Inductive inference

1.1.1.8. Online learning theory

1.1.1.9. Multi-agent learning

1.1.1.10. Models of learning

1.1.1.11. Query learning

1.1.1.12. Structured prediction

1.1.1.13. Reinforcement learning

1.1.1.13.1. -

1.1.1.13.6

1.1.1.14. Active learning

1.1.1.15. Semi-supervised learning

1.1.1.16. Markov decision processes

1.1.1.17. Regret bounds

1.1.2. Database theory

1.1.2.1.-1.1.2.12.

2. Mathematics of computing

2.1. Probability and statistics

2.1.1. Probabilistic representations

2.1.1.1. Bayesian networks

2.1.1.2. Markov networks

2.1.1.3. Factor graphs

2.1.1.4. Decision diagrams

2.1.1.5. Equational models

2.1.1.6. Causal networks

Индекс Название предмета

2.1.1.7. Stochastic differential equations

2.1.1.8. Nonparametric representations

2.1.1.8.1. Kernel density estimators

2.1.1.8.2. Spline models

2.1.1.8.3. Bayesian nonparametric models

2.1.2. Probabilistic inference problems

2.1.2.1.-2.1.2.6.

2.1.3. Probabilistic reasoning algorithms

2.1.3.1. Variable elimination

2.1.3.2. Loopy belief propagation

2.1.3.3. Variational methods

2.1.3.4. Expectation maximization

2.1.3.5. Markov-chain Monte Carlo methods

2.1.3.5.1.-

2.1.3.5.4.

2.1.3.6. Sequential Monte Carlo methods

2.1.3.7. Kalman filters and hidden Markov models

2.1.3.7.1* Factorial HMM

2.1.3.8. Resampling methods

2.1.3.8.1. Bootstrapping

2.1.3.8.2. Jackknifing

2.1.3.9. Random number generation

2.1.4. Probabilistic algorithms

2.1.5. Statistical paradigms

2.1.5.1. Queueing theory

2.1.5.2. Contingency table analysis

2.1.5.3. Regression analysis

2.1.5.3.1. Robust regression

2.1.5.4. Time series analysis

2.1.5.5. Survival analysis

2.1.5.6. Renewal theory

2.1.5.7. Dimensionality reduction

2.1.5.8. Cluster analysis

2.1.5.9. Statistical graphics

2.1.5.10. Exploratory data analysis

2.1.6. Stochastic processes

2.1.6.1. Markov processes

2.1.7. Nonparametric statistics

2.1.8. Distribution functions

2.1.9. Multivariate statistics

3. Information systems

3.1. Data management systems

3.1.1. Database design and models

Индекс Название предмета

3.1.1.1. Relational database model

3.1.1.2. Entity relationship models

3.1.1.3. Graph-based database models

3.1.1.3.1. Hierarchical data models

3.1.1.3.2. Network data models

3.1.1.4. Physical data models

3.1.1.5. Data model extensions

3.1.1.5.1. Semi-structured data

3.1.1.5.2. Data streams

3.1.1.5.3. Data provenance

3.1.1.5.4. Incomplete data

3.1.1.5.5. Temporal data

3.1.1.5.6. Uncertainty

3.1.1.5.7. Inconsistent data

3.1.2. Data structures

3.1.2.1. Data access methods

3.1.2.1.1. Multidimensional range search

3.1.2.1.2. Data scans

3.1.2.1.3. Point lookups

3.1.2.1.4. Unidimensional range search

3.1.2.1.5. Proximity search

3.1.2.2. Data layout

3.1.2.2.1.-

3.1.2.2.3.

3.1.3. Database management system engines

3.1.3.1.-3.1.3.12.

3.1.4. Query languages

3.1.4.1. Relational database query languages

3.1.4.1.1. Structured Query Language

3.1.4.2. XML query languages

3.1.4.2.1 XPath

3.1.4.2.2. XQuery

3.1.4.3. Query languages for non-relational engines

3.1.4.3.1. MapReduce languages

3.1.4.4. Call level interfaces

3.1.5. Information integration

3.1.5.1.-3.1.5.9.

3.2. Information systems applications

3.2.1. Data mining

3.2.1.1. Data cleaning

3.2.1.2. Collaborative filtering

3.2.1.2.1* Item-based

3.2.1.2.2* Scalable

Индекс Название предмета

3.2.1.3. Association rules

3.2.1.3.1* Types of association rules

3.2.1.3.2* Interestingness

3.2.1.3.3* Parallel computation

3.2.1.4. Clustering

3.2.1.4.1* Massive data clustering

3.2.1.4.2* Consensus clustering

3.2.1.4.3** Fuzzy clustering

3.2.1.4.4* Additive clustering

3.2.1.4.5* Feature weight clustering

3.2.1.4.6* Conceptual clustering

3.2.1.4.7* Biclustering

3.2.1.5. Nearest-neighbor search

3.2.1.6. Data stream mining

3.2.1.7* Graph mining

3.2.1.7.1* Graph partitioning

3.2.1.7.2* Frequent graph mining

3.2.1.7.3* Graph based conceptual clustering

3.2.1.7.4* Anomaly detection

3.2.1.7.5* Critical nodes detection

3.2.1.8.* Process mining

3.2.1.11* Text mining

3.2.1.11.1* Text categorization

3.2.1.11.2* Key-phrase indexing

3.2.1.10.* Data mining tools

3.2.1.9* Sequence mining

3.2.1.9.1.* Rule and pattern discovery

3.2.1.9.2.* Trajectory clustering

3.2.1.9.3* Market graph

3.2.1.12* Formal concept analysis

3.3. World Wide Web

3.3.1. Web mining

3.3.1.2. Site wrapping

3.3.1.3. Data extraction and integration

3.3.1.3.1-

3.3.1.3.3.

3.3.1.4. Web log analysis

3.3.1.5. Traffic analysis

3.3.1.6* Knowledge discovery

3.4. Information retrieval

3.4.1. Document representation

3.4.1.1. Document structure

Индекс Название предмета

3.4.1.2. Document topic models

3.4.1.3. Content analysis and feature selection

3.4.1.4. Data encoding and canonicalization

3.4.1.5. Document collection models

3.4.1.6. Ontologies

3.4.1.7. Dictionaries

3.4.1.8. Thesauri

3.4.2. Information retrieval query processing

3.4.2.1.-3.4.2.5.

3.4.3. Users and interactive retrieval

3.4.3.1.-3.4.3.4.

3.4.4. Retrieval models and ranking

3.4.4.1. Rank aggregation

3.4.4.2. Probabilistic retrieval models

3.4.4.3. Language models

3.4.4.4. Similarity measures

3.4.4.5. Learning to rank

3.4.4.6. Combination, fusion and federated search

3.4.4.7. Information retrieval diversity

3.4.4.8. Top-k retrieval in databases

3.4.4.9. Novelty in information retrieval

3.4.5. Retrieval tasks and goals

3.4.5.1.-3.4.5.10.

3.4.6. Evaluation of retrieval results

3.4.6.1.-3.4.6.5.

3.4.7. Specialized information retrieval

3.4.7.1.-3.4.7.3.

4.+0 Human-centered computing

4.1. Visualization

4.1.2. Visualization techniques

4.1.2.1. Treemaps

4.1.2.2. Hyperbolic trees

4.1.2.3. Heat maps

4.1.2.4. Graph drawings

4.1.2.5. Dendrograms

4.1.2.6. Cladograms

4.1.2.7* Elastic maps

4.1.3. Visualization application domains

4.1.3.1.-4.1.3.4.

4.1.4. Visualization systems and tools

4.1.4.1. Visualization toolkits

4.1.5. Visualization theory, concepts and paradigms

4.1.6. Empirical studies in visualization

Индекс Название предмета

4.1.7. Visualization design and evaluation methods

5.+0 Computing methodologies

5.1. Artificial intelligence

5.1.1. Natural language processing

5.1.1.2. Information extraction

5.1.1.3. Machine translation

5.1.1.4. Discourse, dialogue and pragmatics

5.1.1.5. Natural language generation

5.1.1.6. Speech recognition

5.1.1.7. Lexical semantics

5.1.1.7.1* Wikipedia based semantics

5.1.1.8. Phonology / morphology

5.1.1.9. Language resources

5.1.2. Knowledge representation and reasoning

5.1.2.1. Description logics

5.1.2.2. Semantic networks

5.1.2.3. Nonmonotonic, default reasoning and belief revision

5.1.2.4. Probabilistic reasoning

5.1.2.5. Vagueness and fuzzy logic

5.1.2.6. Causal reasoning and diagnostics

5.1.2.7. Temporal reasoning

5.1.2.8. Cognitive robotics

5.1.2.9. Ontology engineering

5.1.2.10. Logic programming and answer set programming

5.1.2.11. Spatial and physical reasoning

5.1.2.12. Reasoning about belief and knowledge

5.1.3. Computer vision

5.1.3.1. Computer vision problems

5.1.3.1.1. Interest point and salient region detections

5.1.3.1.2. Image segmentation

5.1.3.1.3. Video segmentation

5.1.3.1.4. Shape inference

5.1.3.1.5. Object detection

5.1.3.1.6. Object recognition

5.1.3.1.7. Object identification

5.1.3.1.8. Tracking

5.1.3.1.9. Reconstruction

5.1.3.1.10. Matching

5.1.3.2. Computer vision representations

5.1.3.2.1. Image representations

5.1.3.2.1.1**

5.1.3.2.2. Shape representations

5.1.3.2.3. Appearance and texture representations

Индекс Название предмета

5.1.3.2.4. Hierarchical representations

5.2. Machine learning

5.2.1. Learning paradigms

5.2.1.1. Supervised learning

5.2.1.1.1. Ranking

5.2.1.1.2. Learning to rank

5.2.1.1.3. Supervised learning by classification

5.2.1.1.4. Supervised learning by regression

5.2.1.1.5. Structured outputs

5.2.1.1.6. Cost-sensitive learning

5.2.1.2. Unsupervised learning

5.2.1.2.1. Cluster analysis

5.2.1.2.2. Anomaly detection

5.2.1.2.3. Mixture modeling

5.2.1.2.4. Topic modeling

5.2.1.2.5. Source separation

5.2.1.2.6. Motif discovery

Dimensionality reduction and manifold

5.2.1.2.7. learning

5.2.1.2.7.1*

5.2.1.2.7.2*

5.2.1.3. Reinforcement learning

5.2.1.3.1.-

5.2.1.3.5.

5.2.1.4. Multi-task learning

5.2.1.4.1.-

5.2.1.4.3.

5.2.2. Learning settings

5.2.2.1. Batch learning

5.2.2.2. Online learning settings

5.2.2.3. Learning from demonstrations

5.2.2.4. Learning from critiques

5.2.2.5. Learning from implicit feedback

5.2.2.6. Active learning settings

5.2.2.7. Semi-supervised learning settings

5.2.2.7.1* Kernel approach

5.2.3. Machine learning approaches

5.2.3.1. Classification and regression trees

5.2.3.1.1* Parallel implementation

5.2.3.1.2* Splittting criteria

5.2.3.1.3* Model trees

5.2.3.2. Kernel methods

5.2.3.2.1.* Kernel support vector machines