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

Utility-Driven Mining of High Utility Episodes

Образец

служебная таблица

сложная последовательность событий

определение

Большинство основных определений могут относиться кUP-SpanАлгоритмы, некоторые дополнительные и ключевые определения даны ниже.

• Период времени, когда произошло событие (Occurrence) Определение соответствует тому, что в UP-Span, вот дополнительное пояснение, задайте сложный сюжет$\alpha = \big< \lbrace A,D \rbrace \rightarrow B \big>$, называется сложным сюжетом, потому что он содержит набор событий, происходящих параллельно ($\lbrace A, D \rbrace$) и набор событий последовательного появления ($\lbrace A,D \rbrace, \lbrace B \rbrace$), то множество периодов времени возникновения событий равно$occSet(\alpha)$=$\lbrace [T_1,T_2],[T_1,T_5],[T_1,T_6],[T_3,T_5],[T_3,T_6] \rbrace$, следует отметить, что событие$A$и$D$Должны быть одновременными (то есть в один и тот же момент времени), иначе это серийное событие, и исходный сюжет$\alpha$Настройки не совпадают

• максимальный срок (Maximum time duration) похоже на скользящее окно в более ранних алгоритмах извлечения эпизодов, но требует ограничения по времени, определяемого пользователем (MTD), чтобы избежать увеличения объема вычислений и уменьшения корреляции между событиями из-за слишком большого промежутка времени.$\alpha$промежуток времени, чтобы удовлетворить$T_{\rm e} - T_{\rm s} \le MTD$, очевидно, минимальный промежуток времени появления$mo(\alpha)$Константа удовлетворяет этому неравенству.

  P.S. Здесь следует отметить, что,UP-SpanОпределение в$T_{\rm e} - T_{\rm s} + 1 \le MTD$, причина, по которой алгоритм UMEpi разработан таким образом, заключается в том, чтобы обеспечить более точную границу и упростить понимание

• Значение полезности веса графика (Episode-Weighted Utilization) Есть две формулы расчета:

  • ВВЕРХ:$EWU(\alpha, mo(\alpha)) = \sum_{\rm i=1}^{\rm k-1}u(E_{\rm i}, T_{\rm i})+\sum_{\rm i=T_e}^{T_s+MTD}u(SE_{\rm i}, T_{\rm i})$
  • TSpan:$EWU(\alpha, mo(\alpha)) = \sum_{\rm i=1}^{\rm k}u(E_{\rm i}, T_{\rm i})+\sum_{\rm i=T_e}^{T_s+MTD}u(SE_{\rm i}, T_{\rm i})$

  в$\alpha = \big< (E_1),\ldots,(E_{\rm k}) \big>, \; T_{\rm i}(1 \le i \le k)$, TSpan в момент времени$T_{\rm e}$Событие, установленное выше, будет засчитано дважды, что приведет к неточному EWU, можно привести пример:

  Предполагать$\alpha = \big<\lbrace A,D \rbrace \rightarrow B\big>, \, mo(\alpha) = [T_1, T_2]$, можно получить следующие два результата расчета

  $$UP-Span: EWU(\alpha, mo(\alpha)) = u(\lbrace A,D \rbrace, T_1)+u(\lbrace B,C \rbrace, T_2)+u(\lbrace A,D,E \rbrace, T_3) \\ TSpan: EWU(\alpha, mo(\alpha)) = u(\lbrace A,D \rbrace, T_1)+u(B, T_2)+u(\lbrace B,C \rbrace, T_2)+u(\lbrace A,D,E \rbrace, T_3)$$

  Отчетливо видно, что$T_2$события в определенный момент времени$B$Расчет повторяется, что приводит к расчету конечного результата слишком большим.Алгоритм UMEpi использует метод расчета UP-Span

  Следует дополнительно указать, что EWU отличается от TWU и SWU, его можно использовать только какместная обрезкаВозникает ситуация, вместо того, чтобы иметь возможность обрезать с нуля на месте, как два других, одновременно (из-за разных вхождений и методов расширения). Например, установить$MTD = 2, \; minUtil = 50\%, \; TU = 94$участок$\alpha = \big<A,B,D\big>$из$EWU(\alpha)$= 24 доллара используются недостаточно и должны быть сокращены, но его расширенный участок$\big<E \rightarrow B \rightarrow \lbrace A,B,D \rbrace \big>$(48 долларов США),$\big<\lbrace D,E \rbrace \rightarrow B \rightarrow \lbrace A,B,D \rbrace \big>$($51) — участок с высокой полезностью.$\\$Таким образом, в эпизодическом майнинге полезных ископаемых существует «Сценарии с низкой полезностью могут быть расширены до сценариев с высокой полезностью.явление, которое также является трудностью в процессе раскопок

• Постройте остаточную полезность (Remaining utility of an episode)$ru(\alpha, T_{\rm i}) = \sum_{\rm e^\prime \not\in \alpha \land \alpha \prec e^\prime}u(e^\prime, T_{\rm i})$в$e^\prime$являются событиями, и эти события расположены в определенные моменты времени$T_{\rm i}$на участке$\alpha$После этого это ключ к расчету EWU, потому что EWU можно считать граничным значением только в том случае, если учитывается остаточная полезность участка (потенциально расширяемый набор событий), и обратите внимание, что сумма остаточной полезности участка вычисляется над сложной последовательностью событий. Промежуток времени$T_{\rm e}+1 \le T_{\rm i} \le T_{\rm s} + MTD$

  В соответствии с остаточной полезностью графика мы можем оптимизировать EWU, чтобы получить новую формулу:

  $$EWU(\alpha, mo(\alpha)) = u(\alpha, mo(\alpha)) + ru(E_{\rm k}, T_{\rm e}) + \sum_{\rm i=T_{e}+1}^{T_{\rm s}+MTD}tu(T_{\rm i}) \\ = \sum_{\rm i=1}^{\rm k}u(E_{\rm i}, T_{\rm i}) + ru(E_{\rm k}, T_{\rm e}) + \sum_{\rm i=T_{\rm e}+1}^{T_{\rm s}+MTD}tu(T_{\rm i})$$

  в$T_{\rm e} \le T_{\rm i} \le T_{\rm s]}+MTD$

• Участок с высокой полезностью (High-utility episode) учитывая сложную последовательность событий$S$, максимальный срокMTDи установленные пользователем порогиminUtil,когда$S$Событие (набор) в удовлетворяет$u(\alpha) \ge minUtil \times TU$, мы называем событие (множество) какHUE

Стратегия

Episode-Weighted Downward Closure Property

• Дерево словарной последовательности (Lexicographic sequence tree) на основе корневого узла префиксного дерева пусто, а все дочерние узлы родительского узла (также называемого префиксным узлом) формируются путем соединения (строкового, параллельного), и эти дочерние узлы упорядочены.

  Пс.иEHINДерево перечисления пространственного поиска в согласованном

  В дереве последовательности словаря мы можем использовать$u(\gamma) \le EWU(\gamma) \le EWU(\alpha) \le minUtil \times TU$Это неравенство используется для обрезки, где$\gamma$сюжет$\alpha$Расширенный сюжет (расширенный вSimult-ConnectionиSerial-Connection), процесс вывода можно доказать, сравнивая их определения

алгоритм

Алгоритм также разделен на два этапа: 1) сканирование для генерации HUE 1-го порядка; 2) постоянный вызовHUE-SpanВ методе используются комбинации низших порядков для генерации HUE высокого порядка.

The Span-SimultHUE procedure:

The Span-SerialHUE procedure:

Суммировать

Основными вкладами этой статьи являются: 1) продемонстрировано, что графики с низким весом можно также комбинировать с графиками с большим весом для создания графиков с большим весом, что не учитывается предыдущим алгоритмом HUEM; 2) значение остаточной полезности. используется для переопределения более компактногоEWU, что значительно повышает скорость работы; 3) По сравнению с такими алгоритмами, как UP-Span, не используется механизм прогнозирования для определения того, какие эпизоды эффективны,$moSet(\alpha)$сохраненный эпизод$\alpha$Все происходящие подпоследовательности (т. е. потенциально комбинируемые эпизоды)