Аналитика больших данных

Аннотация курса: Map-Reduce как инструмент для создания параллельных алгоритмов, эффективных для больших объемов данных; обработка наборов документов, поиск по сходству, методы ключевого хеширования (minhashing) и локально чувствительного хеширования; алгоритмы кластеризации многомерных массивов данных; методы поддержки систем принятия решений (recommendation systems); предложенный Google алгоритм определения значимости веб-страниц PageRank; методы понижения размерности массивов данных.

1. Введение в DataMining.
2. Технология MapReduce распараллеливания вычислений.
3. Алгоритмы, использующие MapReduce.
4. Операции реляционной алгебры. Матричные вычисления.
5. Алгоритмы обнаружения схожих элементов. Сходство по Жаккару.
6. Сходство по Жаккару. Методы сжатия больших файлов.
7. Хеширование, подписи больших файлов.
8. Локально-чувствительное хеширование документов.
9. Техника группировок. Построение семейств функций.
10. Метрики на пространствах данных.
11. Локально-чувствительные семейства функций хеширования.
12. Методы высоких степеней сходства. Индексация.
13. Методы высоких степеней сходства. Использование позиции и длины.
14. Методы кластеризации в обработке больших данных.
15. Кластеризация в различных метрических пространствах.
16. In-Memory базы данных как технологическая платформа для обработки больших данных.
17. Алгоритмы In-Memory.

1. Анализ ссылок в Интернет.
2. Вычисление PageRank.
3. Модифицированные алгоритмы вычисления PageRank.
4. Базы данных NoSQL как технологическая платформа для обработки больших данных.
5. Управление бизнес-процессами.
6. Интеллектуальный анализ процессов.
7. Алгоритмы анализа процессов.
8. Анализ данных с помощью интеллектуального анализа процессов.
9. Анализ данных (продолжение).
10. Анализ данных (завершение).
11. Моделирование и анализ процессов.
12. Сети Петри.
13. Сети Петри (продолжение).
14. Методы обнаружения бизнес-процессов.
15. Альфа-алгоритм.
16. Эвристические алгоритмы обнаружения бизнес-процессов.
17. Эвристические алгоритмы обнаружения бизнес-процессов (продолжение).

• Матричное представление множеств
• Хеширование
• Хешированные подписи
• Вычисление хешированных подписей
• Локально-чувствительное хеширование документов.
• LSH для хешированных подписей
• Анализ техники группировок (S-кривые)
• Использование методов хешированных подписей и LSH для определения вероятно схожих документов
• Метрики
• Евклидовы метрики
• Расстояние по Жаккару
• Расстояние по косинусу
• Расстояние редактирования
• Расстояние Хемминга
• Теория локально-чувствительных функций
• Локально-чувствительные семейства для расстояния по Жаккару
• Усиление локально-чувствительного семейства (AND-конструкции и OR-конструкции)
• LSH-семейства для расстояния Хемминга
• Случайные гиперплоскости и расстояние по косинусу
• Эскизы векторов
• LSH-семейства для евклидова расстояния (размерность 2)
• Другие LSH-семейства для евклидовых пространств

Задача 1: Универсальное множество U содержит n элементов. Случайным образом выбираются подмножества S и T, содержащие m элементов каждое. Каково ожидаемое значение коэффициента сходства по Жаккару этих множеств?

Задача 2: Дана характеристическая матрица множества S1, S2, S3 и S4.

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} – не часто встречающийся набор элементов.

• Дерево принятия решений, понятие энтропии.
• Ассоциативные правила: 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. © 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.