Алгебраические методы обработки данных (курс лекций, Журавлёв Ю.И.)
Материал из MachineLearning.
(Перенаправлено с Amod)
Преподаватели: А.Г. Дьяконов, Е.В. Дюкова, А.И. Майсурадзе, О.В. Сенько.
Оценки по курсу находятся здесь.
Система выставления оценок по курсу
- В рамках курса предполагается 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.