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

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

---

Версия 15:58, 6 марта 2018

• Спецкурс для магистров
• Преподаватели: Майсурадзе Арчил Ивериевич.
• В 2018 году занятия проходят по понедельникам с 14:35 до 16:10 в 612 аудитории.

Аннотация

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

Материалы

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

[Efficient point-to-point shortest path algorithm]