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

High Utility Episode Mining Made Practical and Fast

Образец

Complex Event Sequence

External Utility of Events

определение

Большинство основных определений могут относиться кUP-SpanЭтот алгоритм, вот лишь некоторые дополнения:

• Полезность эпизода определяется как$u(\alpha) = \sum_{mo(\alpha) \in moSet(\alpha)}u(\alpha, \, mo(\alpha)) / u(CES)$,в$mo(\alpha)$ссылаясь на сюжет$\alpha$Минимум повторений во всей последовательности событий (например, человек тратит одинаковое количество времени на прием пищи в три разных времени дня);$u(CES)$Относится к общей ценности полезности всей сложной последовательности событий, здесь в виде коэффициента для повышения достоверности.

• MTD (maximum time duration) — это временное окно, а это значит, что специально учитываются только правила ассоциации между событиями, которые происходят в пределах этого отрезка времени, иначе нагрузка будет бесконечной, а своевременность результатов не будет такой сильной

• Полезность, взвешенная по эпизодам, похожа наTWU, один участок$\alpha$из$EWU(\alpha)$Формула расчета:

  $$EWU(\alpha, mo(\alpha)) = \sum_{\rm i = 1}^{\rm n}u(SE_{\rm i}, \, T_{\rm i}) + \sum_{\rm i = e}^{\rm s+MTD-1}u(CES_{\rm i}, \, T_{\rm i}) \\ EWU(\alpha) = \sum_{\rm i=1}^{\rm k}EWU(\alpha, \, mo(\alpha)_{\rm i}) / u(CES)$$

  пс потому что$mo(\alpha) = [T_{\rm s}, \, T_{\rm e}]$,так$s$является начальным моментом времени,$e$это момент окончания времени, вы должны понять$EWU(\alpha, mo(\alpha))$Вычислительный смысл (можно понять по аналогии с TWU/SWU)

• Способ расширения сюжета — добавлять события в хвост по одному, когда временной отрезок не меняется, это называетсяI-Concatenation, когда промежуток времени становится длиннее, называетсяS-Concatenation

• Лексикографическое префиксное дерево строит дерево с полной информацией из корневого узла в соответствии с методом расширения, определенным в предыдущей статье.Каждый узел упорядочен.Схема выглядит следующим образом:

  

  Ps. Хорошо видно, что это дерево очень большое без обрезки.Для этого мы можем разделить процесс построения и разбить большое дерево на четыре локальных маленьких дерева (корневой узел a, b, c, d), и тогда тот же метод можно использовать для каждого маленького дерева (эквивалентно пространству во времени) Черная сплошная линия — эффект предварительного сокращения с использованием EWU, а красная пунктирная линия — новая верхняя граница, используемая алгоритмом Эффект сокращения стратегия

Стратегия

Improved EWU for I-Concatenation

Сокращенно «IEIC», это новая верхняя граница, полученная до метода I-конкатенации. Благодаря этой верхней границе I-конкатенация может избежать графика$\alpha$Значение полезности рассчитывается повторно, и формула расчета выглядит следующим образом:

в,$IES(\alpha)$рассчитывается на графике$\alpha$, общая полезность оставшихся событий после текущего события,$SES(\alpha)$это расчетный график$\alpha$Полезность событий в последующей последовательности событий (полезность событий в последующей,$CES_{\rm i}$)

Improved estimation of EWU for S-Concatenation

Сокращенно "IESC", это новая верхняя граница, полученная до метода S-конкатенации. Через эту верхнюю границу S-конкатенация может дать тот же эффект. Поскольку это последовательное соединение, необходимо учитывать меньше факторов. формула следующая:

алгоритм

I-Concatenation

Это можно рассматривать как параллельное соединение, этот процесс проще, пока новое событие$\beta$висеть прямо на участке$\alpha$Хвост может быть, нужно обратить внимание на время их окончания$T_{\rm e}$должны быть последовательными

S-Concatenation

Его можно рассматривать как последовательное соединение, но оно более сложное, необходимо отфильтровывать пересекающиеся периоды времени, чтобы избежать повторных вычислений, идеи других процессов согласуются с параллельными соединениями.

Prefix-Growth

другое имя в газете$TSpan$, что также является аббревиатурой этого алгоритма

Суммировать

Некоторые доказательства алгоритма TSpan опущены (то, что я нашел, может быть версией конференции). Судя по экспериментальным результатам, он намного лучше, чем UP-Span, и две предложенные новые верхние границы действительно могут сыграть большую роль в экранировании (но я смотрю, насколько он похожHUI-MinerиEFIMОставшаяся верхняя граница утилиты) и я заметил, что когда средняя длина набора тестовых данных слишком велика, количество сгенерированных узлов-кандидатов и время выполнения резко увеличиваются, что показывает, что обрезки все еще недостаточно. Самое сложное это что составление событий не так просто, как составление наборов элементов. Я думаю, что можно рассматривать только последовательную или параллельную оптимизацию отсечения, но не повлияет ли это на другой процесс майнинга, потому что некоторые узлы обрезаются?