====== Аналитика больших данных ====== === Главацкий С.Т., Бурыкин И.Г., Айдагулов Р.Р. === ---- **Аннотация курса**: Map-Reduce как инструмент для создания параллельных алгоритмов, эффективных для больших объемов данных; обработка наборов документов, поиск по сходству, методы ключевого хеширования (minhashing) и локально чувствительного хеширования; алгоритмы кластеризации многомерных массивов данных; методы поддержки систем принятия решений (recommendation systems); предложенный Google алгоритм определения значимости веб-страниц PageRank; методы понижения размерности массивов данных. ---- == Тематическое содержание курса == == 1 семестр == == Аналитика больших данных: основные алгоритмы == - Введение в DataMining. - Технология MapReduce распараллеливания вычислений. - Алгоритмы, использующие MapReduce. - Операции реляционной алгебры. Матричные вычисления. - Алгоритмы обнаружения схожих элементов. Сходство по Жаккару. - Сходство по Жаккару. Методы сжатия больших файлов. - Хеширование, подписи больших файлов. - Локально-чувствительное хеширование документов. - Техника группировок. Построение семейств функций. - Метрики на пространствах данных. - Локально-чувствительные семейства функций хеширования. - Методы высоких степеней сходства. Индексация. - Методы высоких степеней сходства. Использование позиции и длины. - Методы кластеризации в обработке больших данных. - Кластеризация в различных метрических пространствах. - In-Memory базы данных как технологическая платформа для обработки больших данных. - Алгоритмы In-Memory. ---- == 2 семестр == == Аналитика больших данных: дополнительные главы == - Анализ ссылок в Интернет. - Вычисление PageRank. - Модифицированные алгоритмы вычисления PageRank. - Базы данных NoSQL как технологическая платформа для обработки больших данных. - Управление бизнес-процессами. - Интеллектуальный анализ процессов. - Алгоритмы анализа процессов. - Анализ данных с помощью интеллектуального анализа процессов. - Анализ данных (продолжение). - Анализ данных (завершение). - Моделирование и анализ процессов. - Сети Петри. - Сети Петри (продолжение). - Методы обнаружения бизнес-процессов. - Альфа-алгоритм. - Эвристические алгоритмы обнаружения бизнес-процессов. - Эвристические алгоритмы обнаружения бизнес-процессов (продолжение). ---- == Типовые контрольные задания == * Матричное представление множеств * Хеширование * Хешированные подписи * Вычисление хешированных подписей * Локально-чувствительное хеширование документов. * LSH для хешированных подписей * Анализ техники группировок (S-кривые) * Использование методов хешированных подписей и LSH для определения вероятно схожих документов * Метрики * Евклидовы метрики * Расстояние по Жаккару * Расстояние по косинусу * Расстояние редактирования * Расстояние Хемминга * Теория локально-чувствительных функций * Локально-чувствительные семейства для расстояния по Жаккару * Усиление локально-чувствительного семейства (AND-конструкции и OR-конструкции) * LSH-семейства для расстояния Хемминга * Случайные гиперплоскости и расстояние по косинусу * Эскизы векторов * LSH-семейства для евклидова расстояния (размерность 2) * Другие LSH-семейства для евклидовых пространств ---- **Задача 1**: Универсальное множество U содержит n элементов. Случайным образом выбираются подмножества S и T, содержащие m элементов каждое. Каково ожидаемое значение коэффициента сходства по Жаккару этих множеств? **Задача 2**: Дана характеристическая матрица множества S1, S2, S3 и S4. {{:speckursy:big-data-matrix.png?200|}} a. вычислите матрицу подписей, используя следующие три хеш-функции : h1(x) = 2x + 1 (mod 6); h2(x) = 3x + 2 (mod 6); h3(x) = 5x + 2 (mod 6). b. какие из этих функция являются реальными перестановками строк характеристической матрицы? c. насколько близка оценка сходства по Жаккару этих множеств (с помощью вычисленных подписей) к его истинному значению? **Задача 3**: На пространстве неотрицательных чисел какие их следующих функций задают метрику (доказать справедливость, либо привести пример нарушения свойств). a. max(x, y); b. diff(x, y) = |x − y|; c. sum(x, y) = x + y. **Задача 4**: Докажите, что расстояние по косинусу между двумя векторами (одной длины), чьи компоненты принимают значения 0 или 1, составляет не более 90º. **Задача 5**: Пусть эскизы вычисляются следующим набором «случайных» векторов: v1 = [+1,+1,+1,−1], v2 = [+1,+1,−1,+1], v3 = [+1,−1,+1,+1] и v4 = [−1,+1,+1,+1]. Вычислите эскизы следующих векторов: a. [2, 3, 4, 5]. b. [−2, 3,−4, 5]. c. [2,−3, 4,−5]. Для каждой из пар этих трех векторов какова оценка расстояния по косинусу и каково его истинное значение? **Задача 6**: Есть 100 корзин, пронумерованных числами 1,2, ..., 100, и 100 элементов, также являющихся числами от 1 до 100. Элемент i находится в корзине j тогда и только тогда, когда i делит j без остатка. Например, корзина 24 – это набор элементов {1,2,3,4,6,8,12,24}. Опишите все ассоциативные правила, имеющие достоверность (confidence) = 100%. Какие из следующих правил имеют 100% достоверность (confidence)? – {4,6} → 24; – {8} → 16; – {3,4,5} → 42; – {8,10} → 20. **Задача 7**: Пусть {A,B,C} – часто встречающийся набор элементов, а {B,C,D,E} – не часто встречающийся набор элементов. Верны ли следующие утверждения: – {B,C,E} – не часто встречающийся набор элементов. – {B,C} – часто встречающийся набор элементов. – {A,B,C,D,E,F} может быть как часто встречающимся набором элементов, так и не часто встречающимся набором элементов. – {B,C,F} – не часто встречающийся набор элементов. ---- == 2 семестр == * Дерево принятия решений, понятие энтропии. * Ассоциативные правила: support, confidence, lift. * Кластерный анализ в  интеллектуальном анализе процессов. * Оценка результатов для дерева решений. * Применение журналов событий в моделировании процессов: play-in, play-out, replay. * Сети Петри как инструмент анализа процессов. * WF-сети и понятие бездефектности (soundness). * Альфа-алгоритм. * Обнаружение процессов (рrocess discovery): 4 критерия качества. * Модель бизнес-процессов (BPMN). * Анализ графа зависимостей. * Transition system: методы исследования. * Обнаружение процессов: двухфазный алгоритм. * Обнаружение процессов: альтернативная техника. * Идея NoSQL. * Теорема CAP. * Типы размещения данных в NoSQL базах данных. **Задача 1**: Рассмотрим вершину в дереве решений с 80 экземплярами типа A и 70 экземплярами типа B. Вычислить энтропию данной вершины. **Задача 2**: В сети Петри на рисунке (прилагается) найти достижимую маркировку, из которой никакой переход невозможен. **Задача 3**: Дан журнал событий L (прилагается). С помощью альфа-алгоритма нарисуйте сеть Петри, соответствующую журналу L. **Задача 4**: Рассмотрим журнал событий L (прилагается). Постройте матрицу следа и найдите коэффициент подтверждения на основе матрицы следа). **Задача 5**: Рассмотрим модель процесса РN  (прилагается) и след < a,b,c,h,i >. Найти коэффициент подтверждения на основе выравнивания для этого следа, предполагая, что стоимость переходов для всех активностей равна 1. ---- == Перечень учебной литературы == * Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman. Mining of Massive Datasets. (c) 2010, 2011, 2012, 2013, 2014 Anand Rajaraman, Jure Leskovec, and Jeffrey D. Ullman. Stanford Univ., USA. * Wil M. P., van der Aalst. Process Mining Discovery, Conformance and Enhancement of Business Processes. ISBN: 978-3-642-19344-6 (Print) 978-3-642-19345-3 (Online). * Hasso Plattner. A Course in In-Memory Data Management. The Inner Mechanics of In-Memory Databases. ISBN:  978-3-642-55269-4 (Print)  978-3-642-55270-0 (Online). * MongoDB Data Modeling. Focus on data usage and better design schemas with the help of MongoDB. Wilson da Rocha França. 2015, Packt Publishing. ISBN 978-1-78217-534-6.