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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Материалы)
(переработка, дополнение)
Строка 1: Строка 1:
* Спецкурс для магистров
* Спецкурс для магистров
* Преподаватели: [[Участник:AIM|Майсурадзе Арчил Ивериевич]].
* Преподаватели: [[Участник:AIM|Майсурадзе Арчил Ивериевич]].
-
* В 2018 году занятия проходят по понедельникам с 14:35 до 16:10 в 612 аудитории.
+
* Весной 2018 года занятия проходят по понедельникам с 14:35 до 16:10 в 612 аудитории.
== Аннотация ==
== Аннотация ==
-
Рассматриваются задачи и методы анализа систем, описание которых базируется на попарном или множественном взаимодействии объектов. Эти объекты могут быть однотипными или разнотипными. Когда важно само наличие или отсутствие взаимодействия, формализация проводится на языке теории графов. Расширении графового описания количественными характеристиками приводит к сетям. Если же считается, что каждый набор объектов может быть численно охарактеризован, говорят о расстояниях или сходствах. Представлена теоретическая основа для формализации задач и построения, реализации и анализа широкого спектра моделей и методов ИАД. Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД — так называемые метрические методы. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс приёмов, предназначенный для эффективного представления и обработки метрической информации вычислительными системами. Рассматриваются характеристики графов, активно используемые при их анализе. Изучаются алгоритмы на графах — как теоретически, так и с точки зрения эффективной реализации. Различные модели роста графов. Построение репрезентативных выборок на графах. Генерация графов с заданными характеристиками. Существенное внимание в курсе уделено многочисленным формализациям кластерного анализа. Показано, какие задачи решают распространённые методы. Проведена типологизация широкого спектра задач кластеризации для гомогенных и гетерогенных систем (бикластеризация, кокластеризация).
+
Рассматриваются модели, задачи и методы анализа систем, описание которых базируется на попарном или множественном взаимодействии объектов. Эти объекты могут быть однотипными (гомогенные системы) или разнотипными (гетерогенные системы). В математике приняты 3 основные способа формализации упомянутого взаимодействия.
 +
# Когда важно само наличие или отсутствие взаимодействия, формализация проводится на языке теории графов. Расширении графового описания различными характеристиками вершин и рёбер приводит к сетям.
 +
# Если считается, что каждый набор объектов может быть охарактеризован численно, говорят о расстояниях или сходствах.
 +
# Также описанием взаимодействия объектов может быть порядок на них.
 +
Представлена теоретическая основа для формализации задач и построения, реализации и анализа широкого спектра моделей и методов ИАД. Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД — так называемые метрические методы. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс приёмов, предназначенный для эффективного представления и обработки метрической информации вычислительными системами. Рассматриваются характеристики графов, активно используемые при их анализе. Изучаются алгоритмы на графах — как теоретически, так и с точки зрения эффективной реализации. Различные модели роста графов. Построение репрезентативных выборок на графах. Генерация графов с заданными характеристиками. Существенное внимание в курсе уделено многочисленным формализациям кластерного анализа. Показано, какие задачи решают распространённые методы. Проведена типологизация широкого спектра задач кластеризации для гомогенных и гетерогенных систем (бикластеризация, кокластеризация).
== Материалы ==
== Материалы ==
 +
[https://docs.google.com/document/d/1CD2g7EN6smt40GPpCnfsaJ346ipAW39DwH0MrgLzLfk/edit?usp=sharing Программа курса]
 +
[https://drive.google.com/open?id=1VXZxt_v8ZTJe7YEzmtKdlHB5rcaA9QwN Ускорение поиска кратчайшего пути]
[https://drive.google.com/open?id=1VXZxt_v8ZTJe7YEzmtKdlHB5rcaA9QwN Ускорение поиска кратчайшего пути]

Версия 07:14, 20 марта 2018

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

Аннотация

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

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

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

Материалы

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

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

Efficient point-to-point shortest path algorithm

Graph-to-Graph Mapping Survey

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