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

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

Версия от 09:20, 19 апреля 2018; AIM (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Аннотация

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

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

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

Зачёт

В соответствии с расписанием аспирантов ВМК и магистров ФКИ зачёт состоится в понедельник 14 мая. Для получения зачёта учащийся должен защитить работу по одной из предложенных в ходе учебного курса тем. Работа может быть представлена на занятии как доклад (до 20 мин) или как реферат. Защиты будут проходить 7 и 14 мая.

Материалы

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

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

Efficient point-to-point shortest path algorithm

Graph-to-Graph Mapping Survey

Личные инструменты