Data Mining В реальном Времени. Идея Data Mining В Реальном Даптация система к общей концепции Методы Data Mining в реальном времени (или Real-Time Analytics), - презентация

1 Data Mining В реальном Времени

2 Идея Data Mining В Реальном Даптация система к общей концепции Методы Data Mining в реальном времени (или Real-Time Analytics), в основном, относятся к задаче предсказания. В отличие от статических методов они обучаются динамически и основаны на обратной связи от прогноза, полученного с помощью предсказательной модели (постоянном переобучении).

3 Возможный путь достичь этого собрать все данные (постоянно добавлять к данным, подвергаемым анализу, новые данные) и применять алгоритмы Data Mining, начиная с начального (возможно незначительного) набора данных и заканчивая имеющимся в текущий момент времени полным набором данных. Такая процедура называется накапливаемое обучение (Batch Learning). Однако накапливаемое обучение часто не эффективно, т. к. Требует запоминания больших объемов данных и приводит к длительному периоду обучения.

4 Адаптивная добыча данных сам по себе адаптивный подход не ограничивается только областью Data Mining, он находит более широкое применение во многих научных областях. Примером использования адаптивного подхода является решение дифференциальных уравнений, особенно частных дифференциальных уравнений одной из классических областей математики. Из-за их сложности, большинство дифференциальных уравнений не может быть решено аналитически, поэтому часто для их решения используют методы аппроксимации. Самые популярные схемы аппроксимации метод конечного элемента (Finite Element Method FEM) и метод конечных разностей (Finite Difference Method FDM). Методы конечного элемента аппроксимируют решением функций f дифференциальных уравнений через базисы на решетках. Чем плотнее решетка, тем лучше аппроксимация; с другой сто- роны, более плотные решетки требуют более высокого уровня вычислений

5 В результате, на практике такие проблемы часто приводят к медленной конвергенции с непригодным результатом. Для того чтобы преодолеть эти проблемы, применяются адаптивные методы конечных элементов, которые используют пошаговый подход, чтобы построить решетки и решить уравнения, появляющиеся в результате применения методов конечных элементов. Общая последовательность действий включает в себя следующие шаги: 1. Генерация начальной решетки. 2. Решение методами конечных элементов систем текущей решетки. 3. Вычисление ошибки с помощью оценки апостериорной ошибки. 4. Если ошибка меньше границы, то закончить вычисления. 5. Обновить решетку, используя реальную геометрию в областях с высоким значением ошибки. 6. Переход к шагу 2. Подобная адаптивная процедура не только гарантирует быструю конвергенцию, но и обеспечивает группировку узлов вокруг оригинала (рис).

6 Рис Пример фигуры решетки адаптивного FEM-метода

7 Статический Data mining и Data mining в реальном времени Data Mining в реальном времени представляет динамический подход, тогда как классический Data Mining является более статическим. "Динамический" звучит лучше, чем "статический" и действительно имеет много преимуществ, поэтому может возникнуть вопрос: нуждаемся ли мы в классическом Data Mining? Ответ конечно, да! Прежде всего, во многих областях может применяться только статический Data Mining, т. к. в них отсутствует автоматическое взаимодействие с клиентами. Например, оптимизация отгрузки правильных каталогов клиентам одноразовая задача и трудная для автоматизации. Кроме того, в этом случае уходят недели, чтобы получить обратную связь от клиентов.

8 Применение Data mining в реальном времени Существует много областей применения Data Mining в реальном времени и их число непрерывно растет. прием звонков в call-центрах. Если агент принимает звонок от клиента (например, запрос о продукции), агент может рекомендовать дополнительно другие продукты клиенту Этот пример иллюстрирует применение рекомендательной машины (Recommendation Engine)

9 Рекомендательные Машины Рекомендательные машины (их также называют рекомендательными системами) являются предшественниками приложений Data Mining в реальном времени. Они представляют клиенту продукты (книги, одежда, товары электроники и т. д.) или общее содержание (музыка, кинофильмы, изображения, добавляемые баннеры, связь и т. д.), которые вероятно его заинтересуют. Особенно широко рекомендательные машины используются в электронной коммерции. Диапазон их применения непрерывно растет, новые области включают стационарную розничную торговлю (PSA/PDA-устройства контроля, весы, терминалы и т. д.), Все эти области характеризуются тем фактом, что они автоматически представляют (или посылают) рекомендации пользователям и принимают от него обратную связь

10 Классификация Рекомендательныхе Машин В рекомендательных машинах используются следующие способы сбора данных: явный сбор данных система просит пользователя оценивать пункты или заполнять опросные анкеты неявный сбор данных система наблюдает за действиями пользователя (щелчки, закупки и т. д.). на основе содержания рекомендации генерируются на основе изучения содержания элементов (продуктов); на основе транзакции рекомендации генерируются на основе пользовательского поведения

11 Совместное Фильтрование Совместное фильтрование (Collaborative Filtering, CF) является одним из первых методов генерации рекомендаций. Первой системой, которая использовала совместное фильтрование, была система Информационный Гобелен (information Tapesnry) Классическая Формулировка Введем некоторую нотацию. Количество. количество пользователей (обозначенных индексом u ) n и количество элементов (на- пример, продукты, обозначенные индексом i ) m. Матрица K размерностью n × m, где каждая колонка представляет элемент, а каждый ряд пользователя. В ячейках матрицы содержится величина r, отражающая интерес пользователя к элементу (щелчки, закупки, оценки и т. д.). Пример мат- рицы K показан в табл.

12 Обозначим набором N(u, i) всех u пользователей, которые проявили интерес к элементу i. Тогда предсказание для элемента i вычисляется следующим образом:

13 где b ui базовая линия предсказания для r ui (как среднее значение по всем элементам u пользователей). S uv мера подобия между пользователями u и v. Простейшим выбором меры подобия может являться коэффициент корреляции Pearson и близко связанная мера косинуса. В данном случае коэффициент Pearson и косинус определяются как

14 Раскроем смысл данной формулы. Для предсказания интереса r ui мы выбираем всех пользователей, которые также выбрали этот элемент i, и берем взвешенное среднее число их интересов к элементу i, где вес это их подобие к пользователю u. Таким образом, если пользователь w ближе к пользователю u, чем другой пользователь v, то интерес r wi будет больше, чем интерес r vi.

15 Формулировка задачи усиления обучения На рис. показано взаимодействие в терминах агента и среды, которое используется в RL (Reinforcment Learning). Агент получает новое состояние и вознаграждение из среды, принимает решение о соответствующем действии (обычно включая изучение) и воздействует на среду. Среда отвечает на действие, переводя агента в новое состояние и передавая ему соответствующее вознаграждение и т. д.

16 Далее будем различать эпизодические задачи, которые завершаются (например, игры, завершающиеся победой или поражением), и продолжающиеся задачи, не имеющие завершения (например, передвижение робота, который может перемешаться бесконечно). Для большинства важных случаев усиление обучения основано на методах динамического программирования (ДП). Уравнение Белмана для дискретного случая представлено далее

17 Где s состояние из множества всех состояний S ; a действие из множества действий A(s), доступных в состоянии s ; π(s,a) требуемая стратегия, т. е. стохастический выбор действия a в состоянии s ; P ss a вероятности перехода из состояния s в состояние s s при выполнении действия a ; R ss a соответствующее вознаграждение перехода; V π (s) функция оценки состояния, которая связывает ожидаемое значение кумулятивного вознаграждения для каждого состояния s с учетной ставкой γ для нагрузки влияния последующих вознаграждений

18 Пример 1 Для иллюстрации уравнения Белмана, мы будем использовать пример Gridworld, представленный на рис (a).

19 Ячейки сетки соответствуют состояниям среды. Из каждой ячейки возможно 4 действия (перехода): вверх, вниз, влево, вправо. Данные действия полностью определяют передвижение агента из заданной ячейки в соответствующем направлении по сетке. Действия, которые приводят агента за пределы сетки, не изменяют его местонахождение, при этом результат вознаграждения будет равен –1. Другие действия выполняются с вознаграждением 0, за исключением тех, которые выводят агента из особенных состояний A и B. При переходе из состояния A, все четыре действия получают вознаграждение +10 и переводят агента в состояние A. При переходе из состояния B, все действия получают вознаграждение +5 и переводят агента в состояние B Предположим, что агент выбирает все четыре действия с равной вероятностью в каждом состоянии. Рис. (б) показывает функцию значений V (s) π для данной стратегии в случае, где γ = 0.9. Чтобы доказать, что функция оценки состояния, приведенная на рис.(б),

20 Теперь расширим дискретный случай на непрерывный Пусть s(t) есть состояние, а a(t) действие (или управление) в момент времени t вычислим функцию оценки состояния

21 где g динамика состояния. Для начального состояния s0 выбор действия a(t) приводит к единственной траектории s(t). Далее r(s,a) функция вознаграждения. Для простоты будем считать π(s) детерминированной стратегией, которая назначает единственное действие a состоянию в момент времени t : a(t) = π(s(t)).

22 Пример 2 Рассмотрим проблему контроля горного автомобиля (рис), сформулированную в литературе. Данная проблема является двух размерной

23 (скорость и направление скорости), поэтому s R. Автомобиль должен достигнуть вершины горы как можно быстрее и остановиться там. Автомобиль не может подниматься вверх без начальной скорости. Поэтому он должен получить ускорение перед началом движения. Также он должен быть осторожен, чтобы не попасть за левую границу. Функция вознаграждения r(s,a) равна нулю везде, кроме границы, где функция равна –1 слева, и линейно изменяется от –1 до +1 в зависимости от ускорения автомобиля, когда он есть справа. В данном случае возможны два действия: максимально положительный или отрицательный толчок.

24 Вопросы

25 В Статсческой Data Mining : нуждаемся ли мы в классическом Data Mining? Да

26 Классификация Рекомендательныхе Машин : Какая Классификация самаы важны явный сбор данных неявный сбор данных

27 В Примером 1 : Действия Вознаграждения значение положительныеотрицательныйлюблю Все