Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Скачать 251.01 Kb.

Название	Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования
Тип	Самостоятельная работа

rykovodstvo.ru > Руководство эксплуатация > Самостоятельная работа

Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Национальный исследовательский университет

«Высшая школа экономики»
Факультет БИЗНЕС-ИНФОРМАТИКИ

Отделение ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Программа дисциплины
Системы разработки данных и машинного обучения
для направления 010500.62 «Прикладная математика и информатика» подготовки бакалавров

Автор Игнатов Д.И. (dignatov@hse.ru)

Рекомендована секцией УМС «Прикладная математика и информатика» Председатель __________________ Кузнецов С.О. «_____» __________________ 20____ г.	Одобрена на заседании кафедры Анализа данных и искусственного интеллекта Зав. кафедрой __________________ Кузнецов С.О. «_____» __________________ 20____ г.
Утверждена УС факультета бизнес-информатики Ученый секретарь __________________ Фомичев В.А. « ____» ___________________20____ г.

Москва

Тематический план учебной дисциплины

№	Название темы	Всего часов	Аудиторные часы		Самостоятельная работа
№	Название темы	Всего часов	Лекции	Сем. и практ. занятия	Самостоятельная работа
1.	Введение в разработку данных и машинное обучение.	9	3		6
2.	Исследование объектно-признаковых данных с помощью программных средств Анализа Формальных Понятий	15	3	4	8
3.	Поиск ассоциативных правил и частых (замкнутых) множеств признаков	14	3	3	8
4.	Деревья решений	14	3	3	8
5.	Задачи кластеризации: иерархическая кластеризация; метод k-средних; спектральная кластеризация	14	3	3	8
6.	Неточные множества (Rough Sets)	14	3	3	8
7.	ДСМ-метод в системе QuDa	14	3	3	8
8.	Наивная байесовская классификация (Naive Bayes Classifier)	14	3	3	8
	Итого:	108	24	22	62

---------------------------------------------------------------------------------------------------------------------------------------------------------

Базовый учебник (и) или ридер (ы)
Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с.

---------------------------------------------------------------------------------------------------------------------------------------------------------

Формы контроля:

текущий контроль – ответы студента во время допуска к выполнению лабораторной работы и отчеты о выполнении работ
промежуточный контроль – контрольная работа (60 мин.)
итоговый контроль – зачет

Перед выполнением лабораторной работы студент отвечает на вопросы и выполняет задания допуска к практикуму (простые модельные расчеты, выполняемые вручную). Итоговая оценка, выставляемая по 10 балльной шкале, складывается из нескольких компонент:
1) ответ студента во время допуска к работе – 10%;

2) учебно-аналитический отчет о выполнении работы студентом, содержащий, как минимум, три нетривиальных вывода и подробный протокол проведения экспериментов – 40%;

3) контрольная работа – 20%

4) защита студентом выполненной лабораторной работы на зачете – 30%.
Для пункта 1) оценивается уровень понимания студентом выбранной модели или метода, правильность расчетов для учебного примера вручную. В пункте 2) оценивается соблюдений формальных требований к отчету, правильность выполнения работы (обработка данных, спецификация модели, оценка качества результатов и т.п.), адекватность и значимость выводов, приемлемость предлагаемой интерпретации результатов (пункт 2 не требует непосредственного взаимодействия со студентом). Для пункта 4) характерна проверка знаний студентов по материалам предоставленных ими отчетов с учетом замечаний и ошибок, выявленных преподавателем ранее. Вопросы для пункта 4 приближены по уровню к устному экзамену.

Содержание программы
Тема 1. Введение в разработку данных и машинное обучение.
Вопросы лекционной части курса

Машинное обучение и разработка данных: основные задачи и методы, история возникновения.

Основная литература

Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с. (Глава 4)
J. Han and M. Kamber, Data Mining: Concepts and Techniques, Second Edition, Morgan Kaufman, 2006. (Глава 1)
Tom Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 1)
Ian H. Witten and Eibe Frank. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, San Francisco, 2 edition, 2005. (Главы 1, 2, 3)

Дополнительная литература

Николенко, С.И., Тулупьев, А.Л., Самообучающиеся системы. – М.: МЦНМО, 2009. – 288 с. (Введение)

Тема 2. Исследование объектно-признаковых данных с помощью программных средств анализа формальных понятий (АФП)
Вопросы лекционной части курса

Частичные порядки и решетки. Диаграммы порядка. Объектно-признаковые данные и формальные контексты. Операторы Галуа. Решетки формальных понятий. Признаковые импликации.

Вопросы практической части курса

Concept Explorer – программная система анализа данных на основе АФП.
Основная литература

Ридер по курсу «Упорядоченные множества для анализа данных»/Кузнецов С.О., Игнатов Д.И., 2009.
B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999.
S.Yevtushenko. Concept Explorer. The User Guide, 2006 (поставляется в составе ПО Concept Expolorer).

Дополнительная литература

Биркгоф Г. Теория решеток. - M.: Наука, 1984.
С. A. Евтушенко. Система анализа данных "Concept Explorer". Труды 7-ой национальной конференции по искусственному интеллекту КИИ-2000. – М.:Физмалит, 2000, стр. 127-134,

Тема 3. Поиск ассоциативных правил и частых (замкнутых) множеств признаков
Вопросы лекционной части курса

Задача анализа данных о покупках и её роль в разработке данных. Частые (замкнутые) множества признаков (ЧМП). Ассоциативные правила (АП). Меры «интересности» АП: поддержка и достоверность. Алгоритм Априори. Связь ЧЗМП с решетками формальных понятий. Импликации в АФП как ассоциативные правила.

Вопросы практической части курса

Coron – система поиска частых множеств признаков и ассоциативных правил.
Основная литература

Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с. (Глава 6)
J. Han and M. Kamber, Data Mining: Concepts and Techniques, Second Edition, Morgan Kaufman, 2006. (Глава 5)
Szathmary, L. Symbolic Data Mining Methods with the Coron Platform. PhD thesis, University Henri Poincaré -- Nancy 1, France, Nov 2006. (глава The Coron User Tooolkit, распространяется вместе с ПО Coron)

Тема 4. Деревья решений.
Вопросы лекционной части курса

Задача классификации в контексте машинного обучения. Деревья решений. Информационная энтропия и прирост информации. Алгоритмы ID3 и С4.5. Критерии остановки и отсечения. Меры и методы оценки качества обучения (скользящий контроль).

Вопросы практической части курса

Системы машинного обучения WEKA и Orange и ее средства для работы с деревьями решений. Средства оценки качества классификации в этих системах.
Основная литература

Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с. (Глава 5)
Николенко, С.И., Тулупьев, А.Л., Самообучающиеся системы. – М.: МЦНМО, 2009. – 288 с.(Глава 1)
Remco R. Bouckaert, Eibe Frank, Mark Hall, Richard Kirkby, Peter Reutemann, Alex Seewald, David Scuse. WEKA Manual for Version 3-6-3, July 27, 2010

Дополнительная литература

Tom Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 3)
Ian H. Witten and Eibe Frank. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, San Francisco, 2 edition, 2005. (Главы 9, 10)
Janez Demsar, Blaz Zupan, Gregor Leban, Tomaz Curk: Orange: From Experimental Machine Learning to Interactive Data Mining. J.-F. Boulicaut et al. (Eds.): PKDD 2004, LNAI 3202, pp. 537–539, Springer, 2004

Тема 5. Задачи кластеризации
Вопросы лекционной части курса

Задача кластеризации. Определение меры расстояния между объектами (Евклидова, Минковского, Махаланобиса). Иерархические агломеративные методы группировки («ближнего соседа», «дальнего соседа», средней связи, центроидный). Метод k-средних. Спектральная кластеризация. Индексы качества кластеризации.

Вопросы практической части курса

Методы кластеризации в системах Weka и Orange. Спектральная кластеризация средствами пакета MatLab и библиотеки NumPy для языка Python.
Основная литература

Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с. (Глава 7)
Николенко, С.И., Тулупьев, А.Л., Самообучающиеся системы. – М.: МЦНМО, 2009. – 288 с. (Глава 6)
L. Zhukov, Spectral Clustering of Large Advertiser Datasets. Technical report, Overture R&D, 2003.

Дополнительная литература

B. Mirkin, Clustering for Data Mining: A Data Recovery Approach, Chapman and Hall/CRC, 2005.

Тема 6. Неточные множества
Вопросы лекционной части курса

Понятие информационной системы и отношения неразличимости. Приближенные множества: верхнее и нижнее приближение, граничная область. Неточные множества (Rough Sets). Редукты и таблицы решений. Признаковые зависимости.

Вопросы практической части курса

Rough Set Exploration System (RSES) – программная система для исследования объектно-признаковых данных на основе неточных множеств.
Основная литература

Вагин В.Н., Головина Е.Ю., Загорянская А.А, Фомина М.В., Достоверный и правдоподобный вывод в интеллектуальных системах, М.: Физматлит, 2004. (Глава 14, раздел 14.3)
RSES 2.2 User’s Guide, Warsaw University, http://logic.mimuw.edu.pl/~rses, January 19, 2005 (поставляется в составе ПО RSES).

Дополнительная литература

J. Komorowski, L. Polkowski, A. Skowron. Rough Sets: A tutorial.

Тема 7. ДСМ-метод в системе QUDA
Вопросы лекционной части курса

Метод сходств и различий по Дж. С. Миллю. ДСМ-метод как индуктивный метод машинного обучения. ДСМ-метод в терминах решеток формальных понятий.

Вопросы практической части курса

QUDA – система разработки данных и машинного обучения. ДСМ-метод в системе QUDA.
Основная литература

Автоматическое порождение гипотез в интеллектуальных системах/ Сост. Е.С. Панкратова, В.К. Финн; Под общ. ред. В.К.Финна. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 528 с. (Главы 1,2)
Grigoriev P.A., Yevtushenko S.A. and Grieser G. QuDA, a data miner's discovery environment // Technical Report AIDA 03 06, FG Intellektik, FB Informatik, Technische Universität Darmstadt, September 2003 (в комплекте с ПО на диске с материалами по курсу).
С.О. Кузнецов, Методы теории решеток и анализа формальных понятий в машинном обучении, Новости Искусственного Интеллекта, 2004, N 3, стр.19-31

Дополнительная литература

Гладкий А.В. Введение в современную логику. – М.: МЦНМО, 2001. – 200 с.(Глава 12)

Тема 8. Наивная байесовская классификация (Naive Bayes Classifier)
Вопросы лекционной части курса

Условная вероятность и формула Байеса. Наивная байесовская классификация. Задачи фильтрации спама и классификации (категоризации) текстов.

Вопросы практической части курса

Наивная байесовская классификация в системе Orange. Реализация наивная байесовской классификации на языке Python..

Основная литература

Барсегян, А. А., Куприянов М.С., Степаненко В.В., Холод А.А., Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004. - 336 с. (Глава 7)
Николенко, С.И., Тулупьев, А.Л., Самообучающиеся системы. – М.: МЦНМО, 2009. – 288 с. (Глава 5)
Сегаран Т. Программируем коллективный разум. М.: Символ-Плюс, 2008. (Глава 6)

Дополнительная литература

T. Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 6)

---------------------------------------------------------------------------------------------------------------------------------------------------------
Тематика заданий по различным формам текущего контроля:
Лабораторные работы по курсу
Лабораторная работа №1. Исследование объектно-признаковых данных с помощью программных средств Анализа Формальных Понятий.

Лабораторная работа №2. Поиск ассоциативных правил и частых (замкнутых) множеств признаков.

Лабораторная работа №3. Деревья решений.

Лабораторная работа №4. Задачи кластеризации: иерархическая кластеризация; метод k-средних; спектральная кластеризация.

Лабораторная работа №5. Неточные множества (Rough Sets).

Лабораторная работа №6. ДСМ-метод в системе QuDa.

Лабораторная работа №7. Наивная байесовская классификация (Naive Bayes Classifier).
---------------------------------------------------------------------------------------------------------------------------------------------------------

Вопросы для оценки качества освоения дисциплины
Примеры вопросов и расчетных задач для допуска к выполнению лабораторных работ.
Задачи

Для заданного формального контекста:

	a	b	c	d
1	x	x		x
2			x
3		x		x
4	x			x
5	x	x	x

а) найдите множество формальных понятий;
б) постройте диаграмму решётки формальных понятий;

в) приведите примеры трех нетривиальных импликаций.

По заданной объектно-признаковой таблице с помощью алгоритма Apriori найдите все частые множества признаков при значении минимальной поддержки minsupp=0,5.

	a	b	c	d
1	x		x	x
2		x		x
3	x	x
4	x		x	x
5		x	x

По объектно-признаковой таблице найдите множество ассоциативных правил при значении минимальной поддержки minsupp=0,5 и минимальной достоверности minconf=0,6.

	a	b	c	d
1		x	x
2	x			x
3	x		x
4		x		x
5		x	x	x

Для заданной объектно-признаковой таблицы о результатах футбольных матчей с целевым признаком «Победа» постройте дерево решений и классифицируйте объект матч, значение целевого признака для которого неизвестно.
Для заданной объектно-признаковой таблицы с помощью алгоритма k-средних постройте 3 кластера, используя расстояние Евклида.
Для заданной таблицы решений найдите нижнее и верхнее приближение целевого класса «Играть?» со значении «Да» и «Нет» , т.е.для множеств X={1,2,6,8,14} и Y={3,4,5,7,9,10,11,12,13}, на следующих подмножествах признаков:

B1 = {«Температура», «Влажность»}

B2 = {« Облачность», «Ветер»}

	Облачность	Температура	Влажность	Ветер	Играть?
1	Солнечно	Жарко	Высокая	Слабый	Нет
2	Солнечно	Жарко	Высокая	Сильный	Нет
3	Облачно	Жарко	Высокая	Слабый	Да
4	Дождь	Умеренно	Высокая	Слабый	Да
5	Дождь	Холодно	Нормальная	Слабый	Да
6	Дождь	Холодно	Нормальная	Сильный	Нет
7	Облачно	Холодно	Нормальная	Сильный	Да
8	Солнечно	Умеренно	Высокая	Слабый	Нет
9	Солнечно	Холодно	Нормальная	Слабый	Да
10	Дождь	Умеренно	Нормальная	Слабый	Да
11	Солнечно	Умеренно	Нормальная	Сильный	Да
12	Облачно	Умеренно	Высокая	Сильный	Да
13	Облачно	Жарко	Нормальная	Слабый	Да
14	Дождь	Умеренно	Высокая	Сильный	Нет

Для таблицы решений (U,A,d) подмножество BA называется решающим суперредуктом решения (decision super-reduct), если оно имеет нижнее и верхнее приближение целевого признака, как и само множество всех признаков A. Найдите все суперредукты решения.
Для заданного многозначного контекста найдите множество положительных и отрицательных гипотез. Предскажите значение целевого признака объектов …
Проведите классификацию объектов с неизвестным значением целевого признака, используя метод Naïve Bayes.

Вопросы

Опишите и объясните способы вычисления расстояние между объектами в задачах кластеризации?
Опишите и объясните способы измерения расстояний между кластерами.
Объясните идею метода К-средних.
Объясните работу алгоритма Apriori.
Объясните принцип наивной классификации Байеса.
Опишите меры оценки качества в машинном обучении и объясните работу метода скользящего контроля.

Примеры заданий для контрольной работы.

(4 балла из 10) Для многозначного контекста заданного объектно-признаковой таблицей:
- провести номинальное шкалирование признаков и найти формальные понятия для контекстов положительных и отрицательных примеров (целевой признак при шкалировании рассматривается только как пометка + и - примеров);
- построить диаграммы решеток понятий положительного и отрицательного контекста;
- найти максимально общие нефальсифицированные положительные и отрицательные гипотезы;
- классифицировать недоопределенные примеры.

Автоугон
	Цвет	Тип	Производство	Повреждения	Угоняют?
1	Красный	Спортивный	США	нет	+
2	Желтый	Спортивный	Япония	нет	+
3	Желтый	Джип	Япония	нет	+
4	Красный	Спортивный	Япония	есть	+
5	Желтый	Спортивный	США	есть	-
6	Желтый	Джип	США	нет	-
7	Красный	Джип	Япония	есть	-
8	Зеленый	Спортивный	США	нет	
9	Красный	Спортивный	Германия	нет	
10	Черный	Джип	Япония	нет	

(1 балл из 10). Для заданного контекста, найдите:

три нетривиальных импликации (импликация A→B называется тривиальной, если BA);
приведите примеры трех ассоциативных правил, не являющихся импликациями, укажите для них меры поддержки (support) и достоверности (confidence).

(4 балла из 10) С помощью метода Naïve Bayes предскажите целевой класс для объектов 8-10 из 10 задачи.
Любая из задач для допуска к выполнению лабораторных работ.

Вопросы к зачету

Основные задачи разработки данных и машинного обучения.
Анализ формальных понятий в контексте разработки данных. Примеры практических задач.
Поиск частых (замкнутых) множеств признаков. Алгоритм Apriori.
Поиск ассоциативных правил. Примеры практических задач.
Деревья решений. Алгоритмы ID3 и С4.5. Примеры практических задач.
Кластеризация. Метод K-средних. Агломеративная кластеризация. Примеры практических задач.
Спектральная кластеризация. Примеры практических задач.
Неточные множества. Основные определения и прикладное значение.
ДСМ-метод в терминах АФП. Прикладные задачи.
Байесовский подход в задачах классификации. Классификация текстов и фильтрация спама.
Меры и методы оценки качества результатов в разработке данных и машинном обучении.

---------------------------------------------------------------------------------------------------------------------------------------------------------
Автор программы: _____________________________/ Игнатов Дмитрий Игоревич/

Приложение 1
Методические материалы преподавателю и студентам:
Практическая часть курса организована в виде лабораторного практикума, состоящего из 7 лабораторных работ. Каждая лабораторная работа имеет типовую структуру.
Лабораторная работа №1

Исследование объектно-признаковых данных с помощью программных средств Анализа Формальных Понятий

Цель работы:

Необходимое программное обеспечение:

Теоретические сведения

Краткое описание ПО

Вопросы для допуска к работе

Задания для модельных расчетов

Задания для выполнения работы

Требования к отчету

Контрольные вопросы

Основная литература

Дополнительная литература
Успешное выполнение лабораторной работы предполагает написание студентом типового отчета. Отчет обязан содержать следующие элементы:

1. Титульный лист с указанием ФИО и номера группы, номера лабораторной работы.

2. Цель работы.

3. Ход работы с описанием выполнения лабораторной работы по заданиям. Необходимо включать таблицы результатов, промежуточные выводы и графики.

4. Выводы. Как минимум работа должна содержать три нетривиальных вывода.
Отчет о выполнении лабораторной работы проверяется преподавателем и предполагает его защиту в устной или письменной форме с выставлением оценки по 10 балльной шкале. Оценки затем суммируются и усредняются по всем запланированным к выполнению лабораторным работам.
Необходимое для выполнения работ программное обеспечение, как правило, находится в свободном доступе и его можно загрузить в сети Интернет или скопировать с диска, прилагающегося к курсу. В лабораторных работах курса используются следующие открытые программные системы:

Weka 3 – Data Mining Software in Java (разработана командой специалистов Университета Вайкато, Новая Зеландия); http://www.cs.waikato.ac.nz/ml/weka/
Orange – Data Mining Fruitful & Fun (пакет создан лабораторией искусственного интеллекта Университета Любляни, Словения); http://www.ailab.si/orange/
QuDA – Data Miner’s Discovery Environment (разработана в техническом Университете города Дармштадта, Германия); http://sourceforge.net/projects/quda/
Coron System – платформа раскопок данных (разработана коллегами из группы Orpailleur в лаборатории LORIA Университета Нанси, Франция); http://coron.loria.fr/
Concept Explorer – один из основных инструментов анализа формальных понятий (разработана в техническом Университете города Дармштадта, Германия); http://conexp.sourceforge.net/
RSES2 – Rough Set Exploration System (разработана в институте математики Университета Варшавы, Польша). http://logic.mimuw.edu.pl/~rses/

Дополнительно к каждой из тем прилагаются слайды лекций, изложение которых адаптировано с учетом используемых программных пакетов.

	Программа дисциплины «Сценарный трейдинг» Правительство Российской... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Tom Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 1)

Tom Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 3)

Janez Demsar, Blaz Zupan, Gregor Leban, Tomaz Curk: Orange: From Experimental Machine Learning to Interactive Data Mining. J.-F. Boulicaut et al. (Eds.): PKDD 2004, LNAI 3202, pp. 537–539, Springer, 2004

T. Mitchell, Machine Learning, McGraw Hill, 1997. (Глава 6)

Похожие: