Алгебраические методы обработки данных (курс лекций, Журавлёв Ю.И.)
Материал из MachineLearning.
(Различия между версиями)
(Новая: {{stop|Страница курса находится в стадии формирования}} == Программа курса == ==== Повторение некоторых раз...) |
|||
(4 промежуточные версии не показаны) | |||
Строка 1: | Строка 1: | ||
- | + | __TOC__ | |
+ | |||
+ | Преподаватели: [[Участник:Dj|А.Г. Дьяконов]], [[Участник:Djukova|Е.В. Дюкова]], А.И. Майсурадзе, [[Участник:Сенько Олег|О.В. Сенько]]. | ||
+ | |||
+ | '''Оценки по курсу находятся [https://docs.google.com/spreadsheets/d/1nzNgxlJrzw2IHhJ3zjVK5ObKQzdyZReWnfYsT8nDlls/edit?usp=sharing здесь.]''' | ||
+ | |||
+ | == Система выставления оценок по курсу == | ||
+ | # В рамках курса предполагается 5 контрольных работ и экзамен. Каждая контрольная работа по курсу оценивается из 5-ти баллов. Возможные оценки за экзамен - 0, 3, 4, 5. | ||
+ | # При отсутствии положительного балла за хотя бы одну из контрольных работ максимальная возможная оценка за курс - «удовлетворительно». | ||
+ | # Необходимым условием получения положительной оценки за курс является написание не менее трёх контрольных работ на положительный балл и сдача экзамена на положительную оценку. | ||
+ | # Итоговая оценка вычисляется по формуле <tex>Mark = \frac{Exam*5+Tests}{10}</tex>, где Exam — оценка за устный экзамен (0, 3, 4, 5), Tests — баллы, набранные за контрольные работы (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, <b>превосходящего</b> дробное значение. | ||
+ | |||
+ | == Экзамен == | ||
+ | Экзамен состоится 18 января (понедельник) в ауд. 579, начало в 9-00. | ||
+ | |||
+ | [[Media:AMOD15_exam_questions.pdf|Список вопросов]] | ||
== Программа курса == | == Программа курса == | ||
Строка 14: | Строка 29: | ||
==== Алгебраический подход к решению задач классификации ==== | ==== Алгебраический подход к решению задач классификации ==== | ||
- | # Задача классификации на l классов | + | # Задача классификации на <tex>l</tex> классов |
# Алгебра над алгоритмами, линейное и алгебраическое замыкание | # Алгебра над алгоритмами, линейное и алгебраическое замыкание | ||
# База в линейном замыкании АВО | # База в линейном замыкании АВО | ||
Строка 23: | Строка 38: | ||
# Алгебро-логический подход к построению корректных процедур распознавания на базе произвольных (не обязательно корректных) элементарных классификаторов. Понятие (монотонного) корректного набора элементарных классификаторов. Общая схема работы логического корректора. Подходы к снижению вычислительной сложности на этапе обучения логического корректора. Практические модели логических корректоров. | # Алгебро-логический подход к построению корректных процедур распознавания на базе произвольных (не обязательно корректных) элементарных классификаторов. Понятие (монотонного) корректного набора элементарных классификаторов. Общая схема работы логического корректора. Подходы к снижению вычислительной сложности на этапе обучения логического корректора. Практические модели логических корректоров. | ||
# Методы повышения эффективности дискретных (логических) процедур распознавания. Оценка информативности признаков, значений признаков, выделение шумящих признаков и обучающих объектов, не являющихся типичными для своего класса. | # Методы повышения эффективности дискретных (логических) процедур распознавания. Оценка информативности признаков, значений признаков, выделение шумящих признаков и обучающих объектов, не являющихся типичными для своего класса. | ||
+ | |||
+ | ==== Модели данных и метрические методы обработки данных ==== | ||
+ | # Основные модели данных (dataframe, multidimensional, similarity tensor, transactional), краткое определение. Гомогенные и гетерогенные модели. Распределение фундаментальных задач ИАД и основных инструментов статистики по моделям данных: в разрезе исходных данных, в разрезе результатов. | ||
+ | # Модель данных «признаковое описание объектов». Понятие о шкалах значений атрибутов. Представление реляционными технологиями. Схемы «звезда» и «снежинка». Диаграммы для наборов точек из <tex>\mathbb{R}^n</tex>. | ||
+ | # Многомерная модель данных. Группирование объектов как переход к многомерной модели данных. Аналитические пространства. Измерения и категории. Показатели. Детализация. Функции агрегирования, типы показателей по агрегированию. Соответствующие диаграммы. Системы отчётности. | ||
+ | # Модель данных «метрические тензоры», гомогенные и гетерогенные многомерные матрицы сходства. Группирование объектов как кластеризация по метрическим описаниям. Гомогенная кластеризация, бикластеризация, мультикластеризация. Основные типы результатов кластеризации (плоская, иерархическая, нечёткая, стохастическая, ранговая). | ||
+ | # Задачи точной реализации метрических тензоров. Корректность задачи (разрешимость, однозначность). Алгоритмическая сложность (на примере метрик Минковского). Метрическое многомерное шкалирование, его связь с методом главных компонент. | ||
+ | # Задачи аппроксимации метрических тензоров. Неметрическое многомерное шкалирование. Функционалы стресса. Монотонные (изотонические) отображения, сохранение ранга метрического тензора. Достаточная размерность представления для неразрешимых задач. | ||
+ | # Задача кластеризации как задача аппроксимации метрического тензора. Метрики на метриках, аппроксимация метрик метриками. Метрические деревья. Ультраметрические деревья. Филогенетические деревья, интерпретация длин ребёр и нетерминальных вершин в ультраметрических деревьях, гипотеза молекулярных часов. Гарантированное получение классов эквивалентности. Общая схема вычисления ближайшей ультраметрики. | ||
==== Логико-статистические модели в распознавании ==== | ==== Логико-статистические модели в распознавании ==== | ||
Строка 31: | Строка 55: | ||
== Литература == | == Литература == | ||
- | # Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с (глава про ДНФ) | + | # [http://www.twirpx.com/file/590363/ Дискретная математика и математические вопросы кибернетики] / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с (глава про ДНФ) |
- | # Яблонский С.В. Введение в дискретную математику . 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с (в конце книги - в приложение про ДНФ). | + | # Яблонский С.В. [http://www.twirpx.com/file/260576/ Введение в дискретную математику.] 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с (в конце книги - в приложение про ДНФ). |
# Дьяконов A.Г. [http://www.machinelearning.ru/wiki/images/7/7e/Dj2010up.pdf Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования)]. — МАКСПресс, 2010. (9 глава). | # Дьяконов A.Г. [http://www.machinelearning.ru/wiki/images/7/7e/Dj2010up.pdf Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования)]. — МАКСПресс, 2010. (9 глава). | ||
# Дьяконов А.Г. [http://alexanderdyakonov.narod.ru/amalekcii.pdf Алгебраические замыкания модели АВО, операторы разметки и теория систем эквивалентностей]. Москва, 2009. (параграфы 1.1-1.2) | # Дьяконов А.Г. [http://alexanderdyakonov.narod.ru/amalekcii.pdf Алгебраические замыкания модели АВО, операторы разметки и теория систем эквивалентностей]. Москва, 2009. (параграфы 1.1-1.2) | ||
# Дюкова Е.В. [http://www.ccas.ru/frc/papers/djukova03mp.pdf Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели] // Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с. | # Дюкова Е.В. [http://www.ccas.ru/frc/papers/djukova03mp.pdf Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели] // Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с. | ||
# Сенько О.В., Докукин А.А. [http://www.mathnet.ru/links/c0edaaf223f66a8aec9c565cfa392b84/zvmmf9550.pdf Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности.] ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011 | # Сенько О.В., Докукин А.А. [http://www.mathnet.ru/links/c0edaaf223f66a8aec9c565cfa392b84/zvmmf9550.pdf Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности.] ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011 | ||
- | # Senko O.V., Dokukin A.A. Optimal forecasting based on convex correcting procedures. in New trends in classification and data mining, (2010), Sofia,Bulgaria:ITHEA | + | # Senko O.V., Dokukin A.A. [[Media:Senko_Dokukin2010.pdf|Optimal forecasting based on convex correcting procedures.]] in New trends in classification and data mining, (2010), Sofia,Bulgaria:ITHEA |
# Senko O.V., Kuznetsova A.V. [http://interstat.statjournals.net/YEAR/2006/articles/0604002.pdf The Optimal Valid Partitioning Procedures] // “InterStat”, Statistics in Inter- net. 2006. | # Senko O.V., Kuznetsova A.V. [http://interstat.statjournals.net/YEAR/2006/articles/0604002.pdf The Optimal Valid Partitioning Procedures] // “InterStat”, Statistics in Inter- net. 2006. | ||
- | # Сенько О.В Алгоритм голосования по множеству операторов вычисления оценок континуальной мощности. В сб. Вопросы кибернетики. Москва, 1989. | + | # Сенько О.В. [[Media:Senko_AVO.pdf|Алгоритм голосования по множеству операторов вычисления оценок континуальной мощности.]] В сб. Вопросы кибернетики. Москва, 1989. |
- | # Senko O., Kuznetsova A. A recognition method based on collective decision making using systems of regularities of various types // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica. Vol. 20, No. 2, 2010, pp. 152-162. | + | # Senko O., Kuznetsova A. [[Media:Senko_SWS.pdf|A recognition method based on collective decision making using systems of regularities of various types]] // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica. Vol. 20, No. 2, 2010, pp. 152-162. |
Текущая версия
Преподаватели: А.Г. Дьяконов, Е.В. Дюкова, А.И. Майсурадзе, О.В. Сенько.
Оценки по курсу находятся здесь.
Система выставления оценок по курсу
- В рамках курса предполагается 5 контрольных работ и экзамен. Каждая контрольная работа по курсу оценивается из 5-ти баллов. Возможные оценки за экзамен - 0, 3, 4, 5.
- При отсутствии положительного балла за хотя бы одну из контрольных работ максимальная возможная оценка за курс - «удовлетворительно».
- Необходимым условием получения положительной оценки за курс является написание не менее трёх контрольных работ на положительный балл и сдача экзамена на положительную оценку.
- Итоговая оценка вычисляется по формуле
, где Exam — оценка за устный экзамен (0, 3, 4, 5), Tests — баллы, набранные за контрольные работы (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, превосходящего дробное значение.
Экзамен
Экзамен состоится 18 января (понедельник) в ауд. 579, начало в 9-00.
Программа курса
Повторение некоторых разделов дискретной математики
- Булевы функции, их запись, изображения на булевом кубе
- Дизъюнктивные нормальные формы (ДНФ): сокращённые, тупиковые, кратчайшие
- Алгоритмы построения ДНФ: метод Нельсона, метод Блейка, критерий поглощения
Алгоритмы, основанные на вычислении оценок (АВО)
- Тестовые алгоритмы
- Алгоритмы с представительными наборами
- Алгоритмы вычисления оценок (АВО), обобщения АВО, эффективные формулы для оценок
Алгебраический подход к решению задач классификации
- Задача классификации на
классов
- Алгебра над алгоритмами, линейное и алгебраическое замыкание
- База в линейном замыкании АВО
Дискретные (логические) процедуры распознавания
- Постановка задачи распознавания по прецедентам. Сущность дискретного (логического) подхода к задачам распознавания. Общие принципы построения дискретных (логических) процедур распознавания в случае целочисленных данных. Понятие корректного элементарного классификатора. Модели дискретных (логических) алгоритмов распознавания, основанные на построении корректных элементарных классификаторов.
- Построение элементарных классификаторов в тестовых алгоритмах распознавания и алгоритмах голосования по представительным наборам на основе поиска покрытий булевых матриц. Построение элементарных классификаторов в алгоритмах голосования по представительным наборам на основе преобразования нормальных форм логических функций (на примере бинарных признаков). Задача дуализации. Основные подходы к оценке эффективности алгоритмов дуализации.
- Алгебро-логический подход к построению корректных процедур распознавания на базе произвольных (не обязательно корректных) элементарных классификаторов. Понятие (монотонного) корректного набора элементарных классификаторов. Общая схема работы логического корректора. Подходы к снижению вычислительной сложности на этапе обучения логического корректора. Практические модели логических корректоров.
- Методы повышения эффективности дискретных (логических) процедур распознавания. Оценка информативности признаков, значений признаков, выделение шумящих признаков и обучающих объектов, не являющихся типичными для своего класса.
Модели данных и метрические методы обработки данных
- Основные модели данных (dataframe, multidimensional, similarity tensor, transactional), краткое определение. Гомогенные и гетерогенные модели. Распределение фундаментальных задач ИАД и основных инструментов статистики по моделям данных: в разрезе исходных данных, в разрезе результатов.
- Модель данных «признаковое описание объектов». Понятие о шкалах значений атрибутов. Представление реляционными технологиями. Схемы «звезда» и «снежинка». Диаграммы для наборов точек из
.
- Многомерная модель данных. Группирование объектов как переход к многомерной модели данных. Аналитические пространства. Измерения и категории. Показатели. Детализация. Функции агрегирования, типы показателей по агрегированию. Соответствующие диаграммы. Системы отчётности.
- Модель данных «метрические тензоры», гомогенные и гетерогенные многомерные матрицы сходства. Группирование объектов как кластеризация по метрическим описаниям. Гомогенная кластеризация, бикластеризация, мультикластеризация. Основные типы результатов кластеризации (плоская, иерархическая, нечёткая, стохастическая, ранговая).
- Задачи точной реализации метрических тензоров. Корректность задачи (разрешимость, однозначность). Алгоритмическая сложность (на примере метрик Минковского). Метрическое многомерное шкалирование, его связь с методом главных компонент.
- Задачи аппроксимации метрических тензоров. Неметрическое многомерное шкалирование. Функционалы стресса. Монотонные (изотонические) отображения, сохранение ранга метрического тензора. Достаточная размерность представления для неразрешимых задач.
- Задача кластеризации как задача аппроксимации метрического тензора. Метрики на метриках, аппроксимация метрик метриками. Метрические деревья. Ультраметрические деревья. Филогенетические деревья, интерпретация длин ребёр и нетерминальных вершин в ультраметрических деревьях, гипотеза молекулярных часов. Гарантированное получение классов эквивалентности. Общая схема вычисления ближайшей ультраметрики.
Логико-статистические модели в распознавании
- Трёхкомпонентное разложение ошибки. Bias-Variance дилемма. Разложение ошибки для выпуклых комбинаций предикторов. Несократимые комбинации. Разложение ошибки для компоненты сдвига и вариационной компоненты обобщённой ошибки.
- Методы верификации закономерностей, основанные на перестановочных тестах. Метод оптимальных достоверных разбиений.
- Метод континуального голосования в модели АВО.
- Метод статистически взвешенных синдромов.
Литература
- Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с (глава про ДНФ)
- Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с (в конце книги - в приложение про ДНФ).
- Дьяконов A.Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010. (9 глава).
- Дьяконов А.Г. Алгебраические замыкания модели АВО, операторы разметки и теория систем эквивалентностей. Москва, 2009. (параграфы 1.1-1.2)
- Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели // Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с.
- Сенько О.В., Докукин А.А. Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности. ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011
- Senko O.V., Dokukin A.A. Optimal forecasting based on convex correcting procedures. in New trends in classification and data mining, (2010), Sofia,Bulgaria:ITHEA
- Senko O.V., Kuznetsova A.V. The Optimal Valid Partitioning Procedures // “InterStat”, Statistics in Inter- net. 2006.
- Сенько О.В. Алгоритм голосования по множеству операторов вычисления оценок континуальной мощности. В сб. Вопросы кибернетики. Москва, 1989.
- Senko O., Kuznetsova A. A recognition method based on collective decision making using systems of regularities of various types // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica. Vol. 20, No. 2, 2010, pp. 152-162.