Метрические методы интеллектуального анализа данных (курс лекций, А.И. Майсурадзе)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Страница создана по материалам сборника спецкурсов ВМК)
м
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
Автор курса: доц. каф. [[ММП]] к.ф.-м.н. [[Участник:AIM|Майсурадзе Арчил Ивериевич]].
Автор курса: доц. каф. [[ММП]] к.ф.-м.н. [[Участник:AIM|Майсурадзе Арчил Ивериевич]].
-
== Аннотация ==
+
Здесь находится архив курса.
-
Рассматриваются методы и технологии, применяющиеся в интеллектуальном анализе данных (ИАД, data mining) и базирующиеся на понятиях сходства, близости, аналогии. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД, среди которых основное внимание в курсе уделено классификации, восстановлению регрессии, кластеризации, восстановлению пропущенных данных.
+
== До 2017 года включительно ==
-
+
[[Метрические методы интеллектуального анализа данных (курс лекций, А.И. Майсурадзе)/до 2017, ВМК|ссылка]]
-
Представлена теоретическая основа для построения, реализации и анализа широкого спектра моделей и методов ИАД. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс технологий, предназначенный для эффективного представления и обработки метрической информации вычислительными системами.
+
Спецкурс для студентов и аспирантов факультета ВМК МГУ.
-
+
-
Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели.
+
-
Длительность курса 64 часа. Курс рассчитан на студентов 3-5 курсов.
+
== Весна 2018 года ==
 +
[[Метрические методы интеллектуального анализа данных (курс лекций, А.И. Майсурадзе)/2018H1, ВМК|ссылка]]
 +
Спецкурс для аспирантов факультета ВМК МГУ.
-
== Содержание курса ==
+
[[Категория:Кафедра Математические методы прогнозирования ВМиК МГУ]][[Категория:Учебные курсы]]
-
+
-
'''Основные подходы к заданию сходства.''' Функциональный подход: двуместные функции, удовлетворяющие аксиомам. Геометрический подход: определение в пространстве множеств точек. Табличный подход: матрицы попарного сходства над конечными множествами.
+
-
+
-
'''Классическое определение метрики и метрического пространства.''' Аксиоматическое задание метрики. Построение топологии по метрике. Пространства сходящихся последовательностей. Фундаментальные последовательности и полные пространства. Роль аксиомы треугольника и непрерыв-ность метрики. Роль аксиомы сепарабельности и единственность предела сходящейся последовательности. Сопоставление метрик и отношений эквива-лентности, 0,1-метрики. Различные модификации системы аксиом метрики и их интерпретация: расстояние, полуметрика, ультра-метрика, квази-метрика, неравенство Птолемея.
+
-
+
-
'''Локальные метрики и их продолжение на всё пространство.''' Формализация понятия «между» в метрическом пространстве. Выпуклость метрического пространства по Менгеру. Аксиомы существования и единственности точек между заданными точками. Аксиомы существования и единственности продолжения луча. Теорема о единственности продолжения локально совпадающих метрик. Практический пример проверки аксиом и использования локального продолжения метрики.
+
-
+
-
'''Геометрические подмножества общих метрических пространств.''' Понятия открытого и замкнутого шара, их согласованность с топологией метрического пространства. Понятия открытого и замкнутого обобщенного эллипсоида. Клетки Дирихле («сферы влияния»), автоматическое исправление ошибок. Геометрическое место точек, равноудаленных от заданных точек, проблема меры указанного подмножества. Понятие кривой в метрическом пространстве, длина кривой. Геодезическая линия, кривая наименьшей длины, сегмент. Свойство совпадения геодезических с множествами равноудаленных точек в обобщенных евклидовых пространствах.
+
-
+
-
'''Примеры метрических пространств.''' Пространство изолированных точек, дискретная топология. Метрики <tex>l_1</tex> (городских кварталов), <tex>l_2</tex> (евклидова), <tex>l_\infty</tex> (Чебышёва). Их физический смысл. Метрика <tex>l_p</tex> (Минковского). Форма шаров, вложенность единичных шаров. Зависимость объема шара от размерности пространства. Проблема сопоставления объема шаров в разных метриках с ростом размерности. Проблема единственности кратчайшего пути. Хаусдорфова метрика и другие метрики между подмножествами метрического пространства, индуцированные исходной метрикой между точками. Расстояния между функциями (графиками). Метрики на декартовом произведении метрических пространств. Случай конечного и бесконечного числа сомножителей, метрики на последовательностях.
+
-
+
-
'''Классификация функций сходства.''' Сопоставление значений: номинальные, порядковые, арифметические (интервальные, относительные, разностные, абсолютные) шкалы. Понятие о граничных объектах. Аксиомы сходства, главный и вспомогательный аргументы. Классификация мер сходства по одному свойству (признаку). Функции сходства на декартовом произведении пространств со значениями в различных шкалах.
+
-
+
-
'''Характеристики метрик.''' Инвариантность расстояния относительно сдвига, поворота. Инвариантность формы шаров относительно положения центра и направления на центр. Инвариантность объема шаров относительно положения центра и направления на центр. Ограниченность метрики. Ограниченность шаров. Понятие полностью абсолютных и полностью относительных метрик, промежуточные метрики. Выпуклость шаров. Односвязность шаров. Существование и единственность сегментов, непрерывность сегментов.
+
-
+
-
'''Преобразования метрик.''' Изометрические преобразования пространств. Преобразования функций, сохраняющие метрические свойства. Некоторые достаточные условия преобразований, сохраняющих метрические свойства. Ограничение значений метрики (range companders). Примеры универсальных компандеров. Возможность монотонного преобразования произвольной функции в метрику. Возможность линейного преобразования произвольной ограниченной функции в метрику. Нормализация метрик, зависимость от точки отсчета. Переход от булеанов конечных множеств к пространствам бинарных векторов, соответствие мощности множества и длины вектора.
+
-
+
-
'''Реализация метрик.''' Реализация конечных метрик точками ЛВП, точечные конфигурации. Алгоритмическая сложность решения задачи точного вложения в линейные пространства с метриками. Примеры МК, имеющих или не имеющих точную реализацию. Задача поиска оптимальной точечной конфигурации в пространстве малой размерности, методы метрического и неметрического многомерного шкалирования. Реализация многомерных данных элементами функциональных пространств. Методы визуализации многомерных данных: параллельные координатные оси, графики Эндрюса, шкалирование и иерархии, таблицы проекций, параметризованные глифы (звезды, лица Чернова).
+
-
+
-
'''Принцип самоорганизации.''' Принцип самоорганизации при построении эвристических информационных моделей. Понятие представителей, мера сходства между объектами и представителями. Функции представительства и назначений, структура метода. Самоорганизация в задаче кластеризации. Самоорганизация и задача факторного анализа, самоорганизация и задача дискриминантного анализа. Модификация прецедентной информации, понятие типологического дискриминантного анализа. Самоорганизация и задача восстановления пропусков.
+
-
+
-
'''Метрики на конечных множествах.''' Представление метрик таблицами по-парных расстояний. Метрическая конфигурация (МК). Специальное линейное пространство метрических конфигураций. Система неравенств треугольника как определение полиэдрального конуса полуметрик. Грани и экстремальные лучи полуметрического конуса, проблема их определения. Векторное представление метрических конфигураций. Достаточные условия сохранения метрических свойств покомпонентными корректорами метрических конфигураций. Примеры использования достаточных условий. Несовместимость метрических свойств и ортогональности метрических конфигураций.
+
-
+
-
'''Разложение МК по конечным системам МК.''' Полные системы, базисы МК. Проблема использования переполненных систем МК. Гомогенные базисы, интерпретация коэффициентов разложения. Ранг МК. Ранговые и полуметрические ранговые базисы. Неполные системы, оптимальная аппроксимация МК. Разложение по системе «отдельных объектов», метрика попарных сумм, эффективное вычисление признака «общая удаленность» для индивидуальных объектов.
+
-
 
+
-
== Литература ==
+
-
=== Основная литература ===
+
-
# Воронин Ю.А. Начала теории сходства. Новосибирск: Наука. СО. 1991.
+
-
# Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО. 2001.
+
-
# Майсурадзе А.И. Гомогенные и ранговые базисы в пространствах метрических конфигураций // Ж. вычисл. матем. и матем. физ. (ЖВМиМФ). 2006. Т.46, № 2. С.344-361.
+
-
# Basalaj W. Proximity Visualization of Abstract Data. Dissertation work. 2001.
+
-
+
-
=== Дополнительная литература ===
+
-
# Буземан Г. Геометрия геодезических. М.: Физматгиз. 1962.
+
-
# Воронин Ю.А. Теория классификации и её приложения. Новосибирск: Наука. СО. 1985.
+
-
# Дидэ Э. Методы анализа данных. М.: Финансы и статистика. 1985.
+
-
# Дэйвисон М. Многомерное шкалирование. М.: Финансы и статистика. 1988.
+
-
# Кочетков Д.В. О функциях близости. Сообщения по прикл. матем. ВЦ АН СССР. 1978.
+
-
# Кочетков Д.В. Построение алгоритма вычисления расстояний для одного класса метрических пространств. Сообщения по прикл. матем. ВЦ АН СССР. 1978.
+
-
# Майсурадзе А.И. О поиске оптимального коллективного слагаемого для набора метрических конфигураций // Искусственный интеллект (ИИ). 2006. №2. С.183-187.
+
-
# Майсурадзе А.И. О свойствах оптимальных точечных конфигураций для одного семейства функционалов сравнения метрических конфигураций // ЖВМиМФ. 2005. Т. 45, № 9. С. 1741-1748.
+
-
# Майсурадзе А.И. Об оптимальных разложениях конечных метрических конфигураций в задачах распознавания образов // ЖВМиМФ. 2004. Т. 44, № 9. С. 1697-1707.
+
-
# Скворцов В.А. Примеры метрических пространств. М.: МЦНМО. 2002.
+
-
# Тылкин М.Е. О геометрии Хэмминга единичных кубов // Доклады АН СССР. 1960. Т.134. С. 1037-1040.
+
-
# Тылкин М.Е. О реализуемости матриц расстояний в единичных кубах // Проблемы кибернетики. 1962. Т. 7. С. 31-42.
+
-
# Шрейдер Ю.А. Что такое расстояние? М.: Физматгиз. 1963.
+
-
# Yianilos P.N. Normalized Forms for Two Common Metrics. Princeton: NEC Re-search Institute. 2002.
+
-
 
+
-
[[Категория:Учебные курсы]]
+

Текущая версия

Автор курса: доц. каф. ММП к.ф.-м.н. Майсурадзе Арчил Ивериевич.

Здесь находится архив курса.

До 2017 года включительно

ссылка Спецкурс для студентов и аспирантов факультета ВМК МГУ.

Весна 2018 года

ссылка Спецкурс для аспирантов факультета ВМК МГУ.

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