Анализ графов, сетей и функций сходства (курс лекций, А.И. Майсурадзе)/2018H1, ВМК

Материал из MachineLearning.

Версия 09:14, 19 апреля 2018

• Спецкурс для магистров факультета ВМК МГУ.
  • Аспиранты факультета ВМК МГУ слушают его как «Метрические методы интеллектуального анализа данных».
• Экзамен с оценкой.
• Преподаватели: к.ф.-м.н. Арчил Ивериевич Майсурадзе.
• Весной 2018 года занятия проходят по понедельникам с 14:35 до 16:10 в аудитории 612.

Аннотация

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

1. Когда важно само наличие или отсутствие взаимодействия, формализация проводится на языке теории графов. Расширении графового описания различными характеристиками вершин и рёбер приводит к сетям.
2. Если считается, что каждый набор объектов может быть охарактеризован численно, говорят о расстояниях или сходствах.
3. Также описанием взаимодействия объектов может быть порядок на них.

Представлена теоретическая основа для формализации задач и построения, реализации и анализа широкого спектра моделей и методов ИАД. Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД — так называемые метрические методы. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс приёмов, предназначенный для эффективного представления и обработки метрической информации вычислительными системами. Рассматриваются характеристики графов, активно используемые при их анализе. Изучаются алгоритмы на графах — как теоретически, так и с точки зрения эффективной реализации. Различные модели роста графов. Построение репрезентативных выборок на графах. Генерация графов с заданными характеристиками. Существенное внимание в курсе уделено многочисленным формализациям кластерного анализа. Показано, какие задачи решают распространённые методы. Проведена типологизация широкого спектра задач кластеризации для гомогенных и гетерогенных систем (бикластеризация, кокластеризация).

Материалы

Программа курса

Ускорение поиска кратчайшего пути

Efficient point-to-point shortest path algorithm

Graph-to-Graph Mapping Survey