Анализ графов, сетей и функций сходства (курс лекций, А.И. Майсурадзе)/2018H1, ВМК
Материал из MachineLearning.
- Спецкурс для магистров факультетов ВМК и КИ МГУ.
- Аспиранты факультета ВМК МГУ слушают его как «Метрические методы интеллектуального анализа данных».
- Экзамен с оценкой.
- Преподаватели: к.ф.-м.н. Арчил Ивериевич Майсурадзе.
- Весной 2018 года занятия проходят по понедельникам с 14:35 до 16:10 в аудитории 612.
Аннотация
Рассматриваются модели, задачи и методы анализа систем, описание которых базируется на попарном или множественном взаимодействии объектов. Эти объекты могут быть однотипными (гомогенные системы) или разнотипными (гетерогенные системы). В математике приняты 3 основные способа формализации упомянутого взаимодействия.
- Когда важно само наличие или отсутствие взаимодействия, формализация проводится на языке теории графов. Расширении графового описания различными характеристиками вершин и рёбер приводит к сетям.
- Если считается, что каждый набор объектов может быть охарактеризован численно, говорят о расстояниях или сходствах.
- Также описанием взаимодействия объектов может быть порядок на них.
Представлена теоретическая основа для формализации задач и построения, реализации и анализа широкого спектра моделей и методов ИАД. Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД — так называемые метрические методы. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс приёмов, предназначенный для эффективного представления и обработки метрической информации вычислительными системами. Рассматриваются характеристики графов, активно используемые при их анализе. Изучаются алгоритмы на графах — как теоретически, так и с точки зрения эффективной реализации. Различные модели роста графов. Построение репрезентативных выборок на графах. Генерация графов с заданными характеристиками. Существенное внимание в курсе уделено многочисленным формализациям кластерного анализа. Показано, какие задачи решают распространённые методы. Проведена типологизация широкого спектра задач кластеризации для гомогенных и гетерогенных систем (бикластеризация, кокластеризация).
Зачёт
В соответствии с расписанием аспирантов ВМК и магистров ФКИ зачёт состоится в понедельник 14 мая. Для получения зачёта учащийся должен защитить работу по одной из предложенных в ходе учебного курса тем. Работа может быть представлена на занятии как доклад (до 20 мин) или как реферат. Защиты будут проходить 7 и 14 мая.
Материалы
Ускорение поиска кратчайшего пути