Спереди написано: Объект сравнения этого алгоритма — UP-Span, На самом деле я хочу знать, кто лучше алгоритма UMEpi. Поскольку стратегии и оптимизация определений, принятые обеими сторонами, очень похожи, разница заключается в структуре хранения. Лично я считаю этот алгоритм относительно важным, и ключевая информация будет выделена.

Fast High Utility Episode Mining

Образец

A complex event sequence

External utility

определение

Прежде всего, нам нужно уточнить, что такое «событие»? В Episode Mining событие может относиться к записи о предмете покупки или может быть предупреждением о риске.Событие здесь используется в широком смысле, и важно быть ясным. Конечно, каждое появление события будет иметь соответствующий момент времени, и каждое событие (набор) во временном ряду находится вупорядоченное состояние, измерение времени является необходимым условием майнинга эпизодов, которое можно рассматривать как2D система координатобсудить в.

• Сложная последовательность событий (сложная последовательность событий) дополнительно расширяется на основе простой последовательности событий (простая последовательность событий, в каждый момент времени происходит только одно событие, и событие находится в упорядоченном состоянии), а также имеется несколько событий в каждый момент времени. каждый момент времени События происходят в одно и то же время (набор событий), определяемый как$CES = \big<(tSE_{\rm t_1}, t_1), \ldots, (tSE_{\rm t_{\rm n}}, t_{\rm n})\big>$,в$tSE_{\rm t_{\rm k}}$Это относится к набору событий в каждый момент времени, а длина набора равна$0 \sim \infty$, первый в примере тоже можно увидеть

• Эпизод есть эпизодне пустойИ есть упорядоченные подпоследовательности с несколькими событиями, происходящими одновременно, выраженными в виде$\big<SE_1, \ldots, SE_{\rm k}\big>$, из-за разных способов объединения событий представление каждого сюжета также немного отличается.Если два события происходят одновременно, то мы используем$\big<(AB)\big>$означает, что если два события происходят одно за другим, то мы используем$\big<(A), (B)\big>$указать, обратить внимание на различие

• Период появления (вхождения) произвольный сюжет$\alpha$Один или несколько периодов времени, соответствующих каждому событию (промежуток времени, когда происходит каждое событие)$[t_{\rm s}, t_{\rm e}]$называется возникновением события. Чтобы было ясно, первая серия событий$SE_1$должно произойти в момент времени$t_{\rm s}$, последний набор событий$SE_{\rm k}$должно произойти в определенный момент времени$t_{\rm e}$(Это период времени, когда происходит сюжет, используйте$occSet(\alpha)$Выражать)

• Минимальный период времени возникновения (минимальное появление) Когда период времени, в котором происходит сюжет, является наименьшим, мы специально указываем период времени для последующих расчетов. пример сюжета$\big<(B), (C)\big>$Период времени$[t_2, t_3], [t_3, t_4], [t_2, t_4]$(Обратите внимание, что события B и C следуют друг за другом), а минимальный промежуток времени равен 1, поэтому$moSet(\big<(B), (C)\big>) = \lbrace [t_2, t_3], [t_3, t_4] \rbrace$

• Максимальная продолжительность времени (maximum time duration) Эта переменная является верхним пределом, устанавливаемым пользователем, потому что по мере дальнейшего роста временного промежутка не только будет увеличиваться рабочая нагрузка, но и связь между событиями будет становиться все более и более тесной. Чем слабее, тем Минимальный период времени возникновения эпизода удовлетворяет требованию максимального временного интервала.$t_{\rm e} - t_{\rm s} + 1 \le maxDur$

• Полезность события согласуется с методом расчета HUIM, то есть внутренняя полезность (количество, количество) умножается на внешнюю полезность (прибыль, прибыль) Используемые формулы расчета (шаг за шагом) следующие:

  • Значение полезности для одного события в один момент времени:$u(e, t_{\rm i}) = p(e) \times q(e, t_{\rm i})$
  • Значение полезности для набора одновременных событий в один момент времени:$u(SE_{\rm k}, t_{\rm i}) = \sum_{\rm j=1}^{\rm l}u(e_{\rm j}, t_{\rm i})$,Уведомление$SE_{\rm k} = \lbrace e_1, \ldots, e_{\rm l} \rbrace$
  • Значения полезности для одного эпизода за минимальный период времени возникновения:$u(\alpha, [t_{\rm s}, t_{\rm e}]) = \sum_{\rm i = 1}^{\rm k}u(SE_{\rm i}, t_{\rm n})$,в$t_{\rm s} \le t_{\rm n} \le t_{\rm e}$, обратите внимание, что каждое событие должно однозначно соответствовать своему моменту времени, а значение полезности события, не относящегося к соответствующему моменту времени, записывается как 0.
  • Значение полезности отдельного эпизода во всей сложной последовательности событий:$u(\alpha) = \sum_{mo \in moSet(\alpha)}u(\alpha, mo)$

  В качестве примера возьмем последнюю формулу расчета полезности, пусть$\alpha = \big< (B), (C) \big>$, то есть

  $$u(\alpha) = u(\big< (B), (C) \big>, [t_2, t_3]) + u(\big< (B), (C) \big>, [t_3, t_4]) \\ = [u((B), t_2) + u((C), t_3)] + [u((B), t_3) + u((C), t_4)] \\ = [(1 \times 2) + (3 \times 1)] + [(1 \times 3) + (3 \times 1)] = 11$$

  Уведомление$[t_2, t_4] \not\subseteq moSet(\alpha)$и событие$(B)$и$(C)$Между ними существует последовательная связь, а не одновременно

• эпизод высокой полезности, когда$u(\alpha) \ge minUtil$время, сюжет$\alpha$Это участок с высокой полезностью (для краткости «HUE»), который мы ищем, и процесс добычи HUE называется добычей участков с высокой полезностью (HUEM).

  В документе указывается, что, поскольку сюжет может иметь несколько воплощений в этой сложной последовательности событий (из-за временного промежутка вы можете обратиться к$\big<(A), (B), (A)\big>$), поэтому предыдущий расчет HUEM учитывает только значение полезности первого встречающегося эпизода, но реальность такова, что одно и то же событие в разные моменты времени может иметь разную внутреннюю полезность. Результатом этого является один и тот же график, а величина полезности, созданная в разные периоды времени, не одинакова.

Ввиду указанных выше недостатков в статье для метода расчета исходной полезности сделано следующее:исправить

• Переопределен эпизод высокой полезности с учетом двух пороговых значений ограничений.$minUtil$и$maxDur$,когда$mo \in moSet(\alpha)$,$mo \subseteq maxDur$,$u(\alpha) \ge minUtil$когда мы рассматриваем сюжет$\alpha$оттенок

  • Исправьте значение полезности одного эпизода за минимальный период времени возникновения:

    $$u(\alpha, [t_{\rm s}, t_{\rm e}]) = u(SE_1, t_{\rm s}) + \sum_{\rm i=2}^{\rm k-1}max\lbrace u(SE_{\rm i}, t_{\rm g(i)x} \mid x \in [1, j]\rbrace + u(SE_{\rm k}, t_{\rm e})$$

    Все содержание расчета можно разделить на три части: начало, сочетание максимального значения полезности в середине и конец. такой же как$\alpha = \big<(A), (B), (A)\big>$Например,

    $$u(\alpha, [t_1, t_4]) = u((A), t_1) + max\lbrace u((B), t_2), u((B), t_3)\rbrace + u((A), t_4) \\ = 2 + max(2, 3) + 4 = 9$$

  • Расчеты по другим формулам остаются без изменений.

• Параллельная конкатенация (одновременная конкатенация) В этом режиме конкатенации размах событий графика после конкатенации не увеличивается,$simul$-$concat(\alpha, \beta) = \big<SE_1, \ldots, SE_{\rm x} \cup SE_1^\prime, \ldots, SE_{\rm y}^\prime\big>$

• Последовательная конкатенация В этом режиме конкатенации диапазон событий графика после конкатенации увеличивается,$serial$-$concat(\alpha, \beta) = \big<SE_1, \ldots, SE_{\rm x}, SE_1^\prime, \ldots, SE_{\rm y}^\prime\big>$

• взвешенное по эпизодам использование иTWU,SWUТочно так же в качестве предварительного условия проверки со свойством закрытия загрузки все обсуждаемые здесь сценарии должны иметь$t_{\rm e} - t_{\rm s} + 1 \le maxDur$, для каждого одновременного события$SE_{\rm i}$имеют соответствующие моменты времени$t_{\rm g(i)}$(Ps. По крайней мере, один момент времени), используемые формулы расчета (шаг за шагом) следующие:

  • EWU для одного эпизода в течение минимального периода времени возникновения:

    $$EWU(\alpha, [t_{\rm s}, t_{\rm e}]) = \sum_{\rm i=1}^{\rm k-1}u(SE_{\rm i}, t_{\rm g(i)} + \sum_{\rm j=t_{\rm e}}^{t_{\rm s}+maxDur-1}u(tSE_{\rm j}, j))$$

    в,$tSE_{\rm j}$те, кто не принадлежит$\alpha$, но в$\alpha$Набор событий в соответствующем промежутке времени (вы можете обратиться к следующим примерам для понимания)

  • ЕСВ для одного эпизода в течение минимального периода времени возникновения: сру, реусходство,$rSE_{\rm t_{\rm e}}$значит в$t_{\rm e}$разделить на$\alpha$Оставшийся набор событий состоит из всех других событий, кроме внутреннего события, формула расчета выглядит следующим образом.

    $$ERU(\alpha, [t_{\rm s}, t_{\rm e}]) = \sum_{\rm i=1}^{\rm k}u(SE_{\rm i}, t_{\rm g(i)}) + u(rSE_{\rm t_{\rm e}}, t_{\rm e}) + \sum_{\rm j=t_{\rm e}+1}^{t_{\rm s}+maxDur-1}u(tSE_{\rm j}, j) \\ u(rSE_{\rm t_{\rm e}}, t_{\rm e}) = \sum_{x \in tSE_{t_{\rm e}} \land x \succ SE_{\rm k}}u(x, t_{\rm e})$$

  • ЕСВ для одного эпизода в сложной последовательности событий:$ERU(\alpha) = \sum_{mo \in moSet(\alpha)}ERU(\alpha, mo)$

  Аналогично возьмем последний для расчета в качестве примера, пусть$maxDur = 3$,$\alpha = \big<(A), (D)\big>$, то есть

  $$ERU(\alpha) = \lbrace[u((A), t_1) + u((D, t_2))] + u((B), t_2) + u((BC), t_3)\rbrace \\ + \lbrace u((A), t_4) + u((D), t_5)\rbrace \\ = \lbrace [2+2]+0+6 \rbrace + \lbrace 4+2 \rbrace \\ = 16$$

• Антимонотонность ЕСВ для сюжета, подлежащего продлению$\alpha$и сюжет$\beta$,имеют$\gamma = simult$-$concat(\alpha, \beta)$или$\gamma = serial$-$concat(\alpha, \beta)$, с правилами$u(\gamma) \le ERU(\gamma) \le ERU(\alpha) \le EWU(\alpha)$Константа установлена, и правило можно вывести, сравнив их расчетные формулы

• (использование окна действия эпизода) Это относительно новое вычисление, потому что$EWU, ERU$Его нельзя напрямую применить к сложным последовательностям событий, поэтому этот объем вычислений используется для фильтрации набора кандидатов.

  $$\forall mo \in moSet(\alpha), \; mo \subseteq [t_{\rm ei}-maxDur+1, t_{\rm si}+maxDur-1] \\ AWU(\alpha) = \sum_{\rm i=1}^{\rm k}\sum_{j=t_{\rm ei}-maxDur+1}^{t_{\rm si}+maxDur-1}tSE_{\rm j}$$

  Например, пусть$\alpha = (A)$,придется$AWU(\big<(A)\big>) = [0+0+2+4+6]+[4+6+7+2+0]=31$,

  как$\alpha = (AC)$,придется$AWU(\big<(AC)\big>) = [4+6+7+2+0]=19$(Обратите внимание$AC$представляет собой совокупность одновременных событий, а не$A, C$последовательность)

Стратегия

Обрезка на основе AWU

использовать$AWU$определение, чтобы заменить оригинал$EWU$Получите набор событий высокой полезности длины один. так как$EWU$не очень компактное значение верхней границы, плюс проблема ошибки вычисления (см. определение вredefined high utility episode), вызовет проблемы с точностью

EEUCS structure and EEUCP strategy

Как показано на рисунке ниже: структура EEUCS и стратегия EEUCP используются для сокращения$EWU$и$ERU$сумма расчета

алгоритм

HUE-Span algorithm

MiningSimultHUE algorithm

MiningSerialHUE algorithm

Суммировать

Отличие от предыдущего алгоритма MEU в том, что он использует$AWU$В качестве предварительной стратегии обрезки (хотя принцип еще не выяснен, почему ее можно заменить) с последующими изменениями в структуре хранения последовательное расширение и параллельное расширение легко получаются с помощью расширения вверх-вниз, влево-вправо матричный, а последующие методы сплайсинга и нет большой разницы с предыдущими алгоритмами. Тем не менее, алгоритм может получить полные HUE, изменив стратегию сокращения, что очень хорошо видно из экспериментальных данных, и я заметил, что тестовый набор, используемый алгоритмом, представляет собой базу данных транзакций, а это означает, что каждый идентификатор транзакций рассматривается как момент времени, и каждый элемент транзакции представляет собой набор одновременных событий.