Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»
Скачать 247.39 Kb.
|
Государственное образовательное бюджетное учреждение высшего профессионального образования Государственный университет – Высшая школа экономики Факультет БИЗНЕС-ИНФОРМАТИКИ Программа дисциплины Упорядоченные множества для анализа данных для направления 010500.68 – Прикладная математика и информатика подготовки магистра Автор Кузнецов С.О. (skuznetsov@hse.ru)
Москва Программа дисциплины «Упорядоченные множества для анализа данных» для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование») I. Пояснительная записка Автор программы: Доктор физико-математических наук С.О. Кузнецов Требования к студентам: Изучение курса «Упорядоченные множества для анализа данных» требует предварительных знаний по элементарной теории множеств и отношений, булевой алгебре и теории алгоритмов (курс «Дискретная математика»). Аннотация. Дисциплина «Упорядоченные множества для анализа данных» предназначена для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование») Теория решеток замкнутых множеств и зависимостей предоставляет математические основы современных методов поиска зависимостей в данных – импликаций и ассоциативных правил на множествах признаков. Поиск ассоциативных правил находится в центре внимания методов разработки данных (data mining). Изложение курса начинается с повторения основных понятий теории отношений, теории графов, теории упорядоченных множеств и решеток. Одним из разделов современной теории решеток является анализ формальных понятий, исходным объектом которого служит бинарное отношение на множествах объектов и их свойств (признаков). На основе отношения определяется соответствие Галуа и оператор замыкания. Замкнутые множества объектов (признаков) образуют решетку (понятий), которая, с одной стороны, позволяет наглядно представлять иерархию классов объектов, а с другой – зависимости на признаках, определяемых в терминах импликаций и ассоциативных правил (частичных импликаций). Решетки формальных понятий дают удобный формализм для описания ряда моделей машинного обучения, таких как пространства версий, деревья решений, ДСМ-гипотезы, а также онтологий – современного средства представления знаний. Серьезным ограничением в применении решеток понятий является сложность вычислительных задач, связанных с алгоритмическим порождением решеток и базисов импликаций. В связи с этим важно изучение сложности задач и сложности различных алгоритмов порождения решеток и базисов импликаций. Учебные задачи курса. Данный курс позволит студентам овладеть математическими основами важнейшей области разработки данных (Data mining) - построения иерархий классов объектов, импликаций, ассоциативных правил и зависимостей других типов на признаках. Студенты получат навыками автоматического построения иерархическую модель предметной области, и находить зависимости в данных, а также анализировать алгоритмическую сложность такого рода задач и строить эффективные алгоритмы порождения иерархий классов объектов и систем зависимостей на множествах признаков объектов. II. Тематический план курса "«Упорядоченные множества для анализа данных»"
Базовый учебник по курсу – ридер «Дискретные структуры», составленный по следующим источникам: 1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с. 2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с. 3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с. 4. B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999. 5. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006. 6. А.А. Зыков, Основы теории графов, М., Наука, 1987. 7. О. Оре, Теория графов, М., Мир, 1965. 8. Ф. Харари, Теория графов, М., Мир, 1973. Дополнительная литература по курсу 1. V. Duquenne and J.-L. Guigues, Familles minimales d'implications informatives resultant d'un tableau de donnees binaires, Math. Sci. Humaines, vol. 95, pp. 5-18, 1986. 2. U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press, 1996. 3. S.O. Kuznetsov, On Computing the Size of a Lattice and Related Decision Problems, Order, 2001, vol. 18 (4), pp. 313-321. 4. S.O. Kuznetsov, S.A. Obiedkov, Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 2002, vol. 14, 2-3, pp. 189-216. 5. M. Luxenburger, Implications partielle dans un contexte, Math. Sci. Hum., 1991. 6. Кузнецов С.О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика. 2001. - N 10. - с. 3-27. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972. 7. P. Buitelaar, P. Cimiano, B. Magnini, Eds., Ontology Learning from Text: Methods, Evaluation and Applications, IOS Press, 2005. 8. C. Carpineto and G. Romano, Concept Data Analysis: Theory and Applications, Wiley, 2004. 9. B. Ganter, G. Stumme, R. Wille, Eds., Formal Concept Analysis: Foundations and Applications, Lecture Notes in Artificial Intelligence, State-of-the Art Series (2005), vol. 3626, pp. 196-225. 10. T. Mitchell, Machine Learning, Mc Graw Hill, 1997. 11. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990. Формы контроля и структура итоговой оценки. Текущий контроль - 2 письменные контрольные работы (90 мин) и 2 домашних задания. Промежуточный контроль - зачет в конце первого и второго модуля; Итоговый контроль – письменный экзамен в конце третьего модуля (120 мин.) Итоговая оценка складывается из следующих элементов:
Программа курса Упорядоченные множества в анализе данных. Тема 1. Введение: обзор курса. Отношения и графы. Бинарные отношения. Графы, подграфы, части, циклы, клики, деревья, двудольные графы. Графы бинарных отношений. Свойства бинарных отношений (рефлексивность, симметричность, асимметричность, антисимметричность, транзитивность, связность, ацикличность, полнота) и их теоретико-графовое выражение. Важные виды бинарных отношений: эквивалентность, толерантность, частичный порядок. Дополнительное отношение, обратное (дуальное) отношение, кодуальное отношение, симметрическое дополнение. Свойства бинарных отношений: рефлексивность, транзитивность, симметричность, асимметричность, антисиметричность. Иллюстрация свойств на графе отношения. Важные виды отношений: эквивалентность (классы эквивалентности), толерантность (классы толерантности), Основная литература 1. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с. 2. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006. 3. А.А. Зыков, Основы теории графов, М., Наука, 1987. 4. О. Оре, Теория графов, М., Мир, 1965. 5. Ф. Харари, Теория графов, М., Мир, 1973. Тема 2. Частично-упорядоченные множества и графы. Частичный порядок, строгий порядок, квазипорядок, линейный порядок, отношение покрытия (доминирования), ориентированный граф порядка, диаграмма (Хассе) порядка. Частичный порядок как транзитивное замыкание отношения покрытия (также через произведение матриц), квазипорядок, отношение несравнимости, частичный порядок на элементах фактор-множества по отношению эквивалентности в квазипорядке. Примеры порядков в математике и приложениях: порядок на мультимножествах, порядок на разбиениях, (квази)порядок на помеченнных (раскрашенных) графах. Размерность упорядоченного множества (порядковая и мультипликативная). Топологическая сортировка Основная литература 1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с. 2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с. 3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с. 4. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006. 5. А.А. Зыков, Основы теории графов, М., Наука, 1987. 6. О. Оре, Теория графов, М., Мир, 1965. Дополнительная литература 1. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990. 2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972. Тема 3. Решетки и полурешетки. Инфимум, супремум, полурешетки, квазирешетки, два определения решеток. Диаграммы полурешеток решеток. Виды решеток (полные, модулярные, матроиды, дистрибутивные, булевы) и их диаграммы. (Порядковые) фильтры и идеалы решеток. Пополнения частичных порядков до решеток (пополнение Дедекинда-Макнила) и дистрибутивных решеток (Теорема Биркгофа). Основная литература 1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с. 2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с. 3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с. 4. О. Оре, Теория графов, М., Мир, 1965. Дополнительная литература 1. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990. 2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972. Тема 4. Бинарные отношения и соответствия Галуа. Соответствия Галуа и их свойства. Соответствие Галуа, основанное на бинарном отношении. Оператор замыкания и система замыканий (семейство Мура). Замкнутые множества, решетка замкнутых множеств. Основная литература 1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с. 2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с. 3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с. 4. О. Оре, Теория графов, М., Мир, 1965. Дополнительная литература 1. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 1990. 2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
