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

Utility-Driven Mining of High Utility Episodes

Образец

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

External Utility

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

A Complex Event Sequence

определение

Большинство основных определений могут относиться к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 высокого порядка.

UMEpi Algorithm

The Span-SimultHUE procedure:

The Span-SimultHUE procedure

The Span-SerialHUE procedure:

The Span-SerialHUE procedure

Суммировать

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