Алгебраические методы обработки данных (курс лекций, Журавлёв Ю.И.)

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

Содержание 1 Система выставления оценок по курсу 2 Экзамен 3 Программа курса 3.1 Повторение некоторых разделов дискретной математики 3.2 Алгоритмы, основанные на вычислении оценок (АВО) 3.3 Алгебраический подход к решению задач классификации 3.4 Дискретные (логические) процедуры распознавания 3.5 Модели данных и метрические методы обработки данных 3.6 Логико-статистические модели в распознавании 4 Литература

Преподаватели: А.Г. Дьяконов, Е.В. Дюкова, А.И. Майсурадзе, О.В. Сенько.

Оценки по курсу находятся здесь.

Система выставления оценок по курсу

1. В рамках курса предполагается 5 контрольных работ и экзамен. Каждая контрольная работа по курсу оценивается из 5-ти баллов. Возможные оценки за экзамен - 0, 3, 4, 5.
2. При отсутствии положительного балла за хотя бы одну из контрольных работ максимальная возможная оценка за курс - «удовлетворительно».
3. Необходимым условием получения положительной оценки за курс является написание не менее трёх контрольных работ на положительный балл и сдача экзамена на положительную оценку.
4. Итоговая оценка вычисляется по формуле , где Exam — оценка за устный экзамен (0, 3, 4, 5), Tests — баллы, набранные за контрольные работы (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, превосходящего дробное значение.

Экзамен

Экзамен состоится 18 января (понедельник) в ауд. 579, начало в 9-00.

Список вопросов

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

Повторение некоторых разделов дискретной математики

1. Булевы функции, их запись, изображения на булевом кубе
2. Дизъюнктивные нормальные формы (ДНФ): сокращённые, тупиковые, кратчайшие
3. Алгоритмы построения ДНФ: метод Нельсона, метод Блейка, критерий поглощения

Алгоритмы, основанные на вычислении оценок (АВО)

1. Тестовые алгоритмы
2. Алгоритмы с представительными наборами
3. Алгоритмы вычисления оценок (АВО), обобщения АВО, эффективные формулы для оценок

Алгебраический подход к решению задач классификации

1. Задача классификации на классов
2. Алгебра над алгоритмами, линейное и алгебраическое замыкание
3. База в линейном замыкании АВО

Дискретные (логические) процедуры распознавания

1. Постановка задачи распознавания по прецедентам. Сущность дискретного (логического) подхода к задачам распознавания. Общие принципы построения дискретных (логических) процедур распознавания в случае целочисленных данных. Понятие корректного элементарного классификатора. Модели дискретных (логических) алгоритмов распознавания, основанные на построении корректных элементарных классификаторов.
2. Построение элементарных классификаторов в тестовых алгоритмах распознавания и алгоритмах голосования по представительным наборам на основе поиска покрытий булевых матриц. Построение элементарных классификаторов в алгоритмах голосования по представительным наборам на основе преобразования нормальных форм логических функций (на примере бинарных признаков). Задача дуализации. Основные подходы к оценке эффективности алгоритмов дуализации.
3. Алгебро-логический подход к построению корректных процедур распознавания на базе произвольных (не обязательно корректных) элементарных классификаторов. Понятие (монотонного) корректного набора элементарных классификаторов. Общая схема работы логического корректора. Подходы к снижению вычислительной сложности на этапе обучения логического корректора. Практические модели логических корректоров.
4. Методы повышения эффективности дискретных (логических) процедур распознавания. Оценка информативности признаков, значений признаков, выделение шумящих признаков и обучающих объектов, не являющихся типичными для своего класса.

Модели данных и метрические методы обработки данных

1. Основные модели данных (dataframe, multidimensional, similarity tensor, transactional), краткое определение. Гомогенные и гетерогенные модели. Распределение фундаментальных задач ИАД и основных инструментов статистики по моделям данных: в разрезе исходных данных, в разрезе результатов.
2. Модель данных «признаковое описание объектов». Понятие о шкалах значений атрибутов. Представление реляционными технологиями. Схемы «звезда» и «снежинка». Диаграммы для наборов точек из .
3. Многомерная модель данных. Группирование объектов как переход к многомерной модели данных. Аналитические пространства. Измерения и категории. Показатели. Детализация. Функции агрегирования, типы показателей по агрегированию. Соответствующие диаграммы. Системы отчётности.
4. Модель данных «метрические тензоры», гомогенные и гетерогенные многомерные матрицы сходства. Группирование объектов как кластеризация по метрическим описаниям. Гомогенная кластеризация, бикластеризация, мультикластеризация. Основные типы результатов кластеризации (плоская, иерархическая, нечёткая, стохастическая, ранговая).
5. Задачи точной реализации метрических тензоров. Корректность задачи (разрешимость, однозначность). Алгоритмическая сложность (на примере метрик Минковского). Метрическое многомерное шкалирование, его связь с методом главных компонент.
6. Задачи аппроксимации метрических тензоров. Неметрическое многомерное шкалирование. Функционалы стресса. Монотонные (изотонические) отображения, сохранение ранга метрического тензора. Достаточная размерность представления для неразрешимых задач.
7. Задача кластеризации как задача аппроксимации метрического тензора. Метрики на метриках, аппроксимация метрик метриками. Метрические деревья. Ультраметрические деревья. Филогенетические деревья, интерпретация длин ребёр и нетерминальных вершин в ультраметрических деревьях, гипотеза молекулярных часов. Гарантированное получение классов эквивалентности. Общая схема вычисления ближайшей ультраметрики.

Логико-статистические модели в распознавании

1. Трёхкомпонентное разложение ошибки. Bias-Variance дилемма. Разложение ошибки для выпуклых комбинаций предикторов. Несократимые комбинации. Разложение ошибки для компоненты сдвига и вариационной компоненты обобщённой ошибки.
2. Методы верификации закономерностей, основанные на перестановочных тестах. Метод оптимальных достоверных разбиений.
3. Метод континуального голосования в модели АВО.
4. Метод статистически взвешенных синдромов.

Литература

1. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с (глава про ДНФ)
2. Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с (в конце книги - в приложение про ДНФ).
3. Дьяконов A.Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010. (9 глава).
4. Дьяконов А.Г. Алгебраические замыкания модели АВО, операторы разметки и теория систем эквивалентностей. Москва, 2009. (параграфы 1.1-1.2)
5. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели // Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с.
6. Сенько О.В., Докукин А.А. Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности. ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011
7. 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
8. Senko O.V., Kuznetsova A.V. The Optimal Valid Partitioning Procedures // “InterStat”, Statistics in Inter- net. 2006.
9. Сенько О.В. Алгоритм голосования по множеству операторов вычисления оценок континуальной мощности. В сб. Вопросы кибернетики. Москва, 1989.
10. 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.