Написано впереди: анализ шаблонов эпизодов отличается от анализа шаблонов наборов элементов. Его сложность намного больше, чем набор элементов. Прежде всего, «сюжет» означает возникновение серии событий. Несколько наборов элементов генерируются в течение определенного периода времени, и эти наборы элементов могут генерироваться последовательно, возникать и, возможно, в одно и то же время. То есть анализ эпизодов должен учитывать не только горизонтальную последовательность событий, но и объединять вертикальный набор событий.

Mining High Utility Episodes in Complex Event Sequences

определение

Добыча эпизодов начинается с расчета частоты, поэтому вот несколько основных определений.

Частый класс

• Простая последовательность событий (Simple event sequence):Предполагать$\varepsilon = \{E_1, E_2, \dots, E_{\rm m}\}$это конечное множество событий, простая последовательность событий$SS = <(E_1, T_1), (E_2, T_2), \dots, (E_{\rm m}, T_{\rm m})>$это набор событийаккуратныйпоследовательность, где каждое событие$E_{\rm i} \in \varepsilon$все в один момент времени$T_{\rm i} \in N^+$Связанный. Например, на следующем рисунке (Рис. 1.):

  

• Простой сюжет (Simple episode): простой сюжет$\alpha$представляет собой множество непустыхаккуратныйКоллекция событий. Например, на рисунке (Рис. 1.)$<(A), \, (C)>$просто простой сюжет

• Набор одновременных событий (Simultaneous event set): набор одновременных событий$SE = (E_1, E_2, \dots, E_{\rm m})$в тот же момент времени$T_{\rm i}$Набор событий, произошедших в.

• сложная последовательность событий (Complex event sequence): сложная последовательность событий$CS = <(SE_1, T_1), (SE_2, T_2), \dots,$ $(SE_{\rm n}, T_{\rm n})>$это серияаккуратныйНабор событий содержит несколько одновременных наборов событий, и каждый одновременный набор событий формирует последовательность событий. Например, как показано на следующем рисунке (Рисунок 2.):

  

• длина и размер (Length and Size): сюжет события$\alpha$Длина определяется как (фактически количество событий в наборе), называемое$k$-эпизод; при этом сюжет события$\alpha$Размер равен количеству одновременных наборов событий в эпизоде. Например:$<(AB), (C)>$представляет собой 3-серийный размер 2

• происходить(Occurrence): Учитывая сюжет , когда 1) сюжет$\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm m})>$произошло в период времени [$T_{\rm s}, T_{\rm e}$]; 2) сюжет$\alpha$первый одновременный набор событий$SE_1$произошло в$T_{\rm s}$момент времени, последний набор одновременных событий$SE_{\rm m}$произошло в$T_{\rm e}$момент времени, так называемый сюжет$\alpha$происходит в промежутке времени [$T_{\rm s}, T_{\rm e}$] начальство. Среди них сюжет$\alpha$Множество всех периодов времени возникновения$occSet(\alpha)$. Например: на рисунке (Рисунок 2.)$occSet(<(AB), (C)>) = \{[1,2], [1,3], [1,6], [1,7], [5,6], [5,7]\}$

• Кратчайший срок (Minimal occurrence): учитывая сюжет$\alpha$два временных интервала [$T_{\rm s}, T_{\rm e}$], [$T_{\rm s}', T_{\rm e}'$], [$T_{\rm s}', T_{\rm e}'$] Да [$T_{\rm s}, T_{\rm e}$] : когда 1) сюжет$\alpha$произошло в [$T_{\rm s}, T_{\rm e}$] период времени; 2) [$T_{\rm s}', T_{\rm e}'$] Подмножество не существует. Кратчайший период времени возникновения записывается как$mo(\alpha)$. Среди них сюжет$\alpha$Множество всех кратчайших периодов времени появления$moSet(\alpha)$. Например: сюжет$<(AB), (C)>$Кратчайший период времени появления [1,2] из , и$moSet(<(AB), (C)>) = \{[1,2], [5,6]\}$

• поддержка сюжета (Support of an episode):участок$\alpha$служба поддержки$SC(\alpha)$Определяется как набор периодов времени, которые происходят в кратчайшем$moSet(\alpha)$Количество кратчайших периодов времени появления в (Ps.то есть это произошло один раз за этот период времени), скорость поддержки определяется как в CS$SC(\alpha)$Отношение к моменту времени

• частые приступы (Frequent episode): когда поддержка участка не ниже заданного пользователем порога поддержки ($minSup$), то эпизод называют частым эпизодом.

В документе также упоминается, почему следует разработать новую утилиту майнинга, которая заменит частотный майнинг: во-первых, значение частотного выражения слишком узкое (например, в случае с бриллиантами и хлебом), а во-вторых, что трудно обсуждать события. параллелизм на основе частоты (одновременное возникновение (определяется как возникновение только одного события в один и тот же момент времени)

Класс полезности

Предполагать$CS = <(t_{SE_1}, T_1), (t_{SE_2}, T_2), \dots, (t_{SE_{\rm n}}, T_{\rm n})>$,в$T_{\rm i} \in N^+$, каждое событие$E_{\rm i} \in \varepsilon$обе сопутствующие прибыли$p(E_{\rm i}, CS)$(внешняя полезность) и количество$q(E_{\rm i}, T_{\rm i})$(внутренняя утилита). В следующей таблице (Таблица 1) и на рисунке (Рисунок 3) представлена ​​внешняя полезность и внутренняя полезность каждого события соответственно.

• полезность события в определенный момент времени (Utility of an event at a time point): в какой-то момент времени$T_{\rm i} \in N^+$следующее событие$E_{\rm i}$Полезность определяется как$u(E_{\rm i}, T_{\rm i}) = p(E_{\rm i}, CS) \times q(E_{\rm i}, T_{\rm i})$(выгода$\times$количество)

• Полезность набора событий, происходящих параллельно в определенный момент времени (Utility of a simultaneous event set at a time point): в какой-то момент времени$T_{\rm i} \in N^+$Следующий набор параллельных (одновременных) событий$SE = (E_1, E_2, \dots, E_{\rm n})$Полезность определяется как$u(SE, T_{\rm i}) = \sum_{j = 1}^{n}u(E_{\rm j}, T_{\rm i})$

• Общая полезность на основе комплексных наборов данных последовательности событий (Total utility of database complex event sequence): на основе сложной последовательности событий$CS$Полная полезность определяется как$u(CS) = \sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i})$

• Построить график полезности по кратчайшему периоду появления (Utility value of an episode w.r.t its minimal occurrence):Предполагать$mo(\alpha) = [T_{\rm s}, T_{\rm e}]$сюжет$\alpha = <(SE_1, SE_2, \dots, SE_{\rm n})>$кратчайший период времени возникновения, в течение которого каждый набор событий происходит параллельно$SE_{\rm i} \in \alpha$в определенный момент времени$T_{\rm i} \in N^+$Связанный. Полезность сюжета по отношению к кратчайшему периоду появления определяется как$u(\alpha, mo(\alpha)) = \sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i})$

• Полезность сюжетов, основанных на сложных последовательностях событий (Utility of an episode in a complex event sequence):Предполагать$moSet(\alpha) = [T_{\rm I_1}, T_{\rm I_2}, \dots, T_{\rm I_n}]$это о сюжете$\alpha$Минимальный набор вхождений . на основе сложных временных рядов$CS$Полезность сюжета определяется как$uv(\alpha, CS) = \sum_{i = 1}^{n}u(\alpha, T_{\rm I_n})$, и имеет$u(\alpha) = uv(\alpha) / u(CS)$

• максимальная продолжительность (Maximum time duration):Предполагать$MTD$максимальная продолжительность, заданная пользователем,$mo(\alpha) = [T_{\rm s}, T_{\rm e}]$сюжет$\alpha$кратчайший период возникновения. когда$(T_{\rm e} - T_{\rm s} + 1) \le MTD$,сказать$mo(\alpha)$от$MTD$Ограничения (или выполняются) из (Ps.МПД играет роль временного окна, потому что мы должны определить диапазон, если мы хотим вычислить, иначе бесконечный период времени или бесконечно малый не способствует нашему исследованию)

• Параллельные и последовательные соединения (Simultaneous and serial concatenations):Предполагать$\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm x})>,$ $\beta = <(SE_1'), (SE_2'), \dots, (SE_{\rm y}')>$,$\alpha$и$\beta$Параллельная конкатенация определяется как$simul$-$concat(\alpha, \beta) = <(SE_1),(SE_2),$ $\dots, (SE_{\rm x} \cup SE_1'), (SE_2'), (SE_{\rm y}')>$,$\alpha$и$\beta$Последовательное соединение определяется как$serial$-$concat(\alpha, \beta) = <(SE_1), (SE_2),$ $\dots, (SE_{\rm x}), (SE_1'), (SE_2'), \dots, (SE_{\rm y}')>$(Ps. Оба являются расширенными наборами предметов, но их комбинация отличается.)

• Участок с высокой полезностью (High Utility Episode): когда сюжет$E_{\rm i}$полезность$u(E_{\rm i}) \ge minUtil$, он считается нужным нам узором (ОТТЕНОК), в противном случае он не

• эпизодические веса полезности (Episode-Weighted Utilization of an episode):Предполагать$moSet(\alpha) = [T_{\rm I_1}, T_{\rm I_2}, \dots, T_{\rm I_n}]$,и$T_{\rm I_i} \in moSet(\alpha)$удовлетворить$MTD$ограничение. Затем на основе сложной последовательности событий$CS$Сюжет$\alpha$полезный вес$EWU(\alpha) = \sum_{i = 1}^{n}EWU(\alpha, T_{\rm I_i}) / u(CS)$. Например: пусть$MTD = 3, \alpha = <(A), (C)>$,Так$EWU(<(A), (C)>) = [u((AB), T_1) + u((BC), T_2) + u((C), T_3)] + [u((AB), T_5) + u((CD), T_6) + u((C), T_7)] / u(CS) = 40 / 40$

  

• Полезность, взвешенная по графику, по отношению к кратчайшему периоду появления (Episode-Weighted Utilization of an episode w.r.t a minimal occurrence):Предполагать$mo(\alpha) = [T_{\rm s}, T_{\rm e}]$сюжет$\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm n})>$Кратчайший период времени возникновения, когда$mo(\alpha)$от$MTD$ограничения. затем в [$T_{\rm s}, T_{\rm e}$] следующий эпизод$\alpha$Полезность веса сюжета$EWU(\alpha, mo(\alpha)) =$ $\sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i}) + \sum_{i = e}^{(s + MTD - 1)}u(t_{SE_{\rm i}}, T_{\rm i})$,в$t_{SE_{\rm i}}$в$CS$Момент времени в наборе одновременных событий в$T_{\rm i}$. Например: пусть$MTD = 4, \alpha = <(C), (A)>, mo(<(C), (A)>) = [3,5]$,Так$EWU(<(C), (A)>, [3, 5]) = [u((C), T_3)] + [u((AB), T_5) + u((CD), T_6)] = 25$

• Участки полезного назначения с большим весом (High Weighted Utilization Episode): когда сюжет$\alpha$из$EWU(\alpha) \ge minUtil$, эпизод называется эпизодом полезности с большим весом (HWUE), который является событием-кандидатом следующего определения.

• события-кандидаты (Promising event):когда$EWU(e) \ge minUtil$, событие$e$является событием-кандидатом, и его полезность эпизода необходимо дополнительно рассчитать для точного суждения. В противном случае бесперспективное мероприятие, когда$\alpha$является некандидатным событием, для любого сюжета$\beta$, их надмножество$\gamma$все неэффективны.

• Нисходящее замыкание графиков весов (Episode-Weighted Downward Closure property (EWDC)):Предполагать$\alpha$и$\beta$участки, и$\gamma = simul$-$concat(\alpha, \beta)$или$serial$-$concat(\alpha, \beta)$,когда$EWU(\alpha) < minUtil$час,$\gamma$это неэффективный сценарий

Стратегия

Discarding Global unpromising Events(DGE)

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

Discarding Local unpromising Events(DLE)

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

алгоритм

Идея основного алгоритма заключается в старом правиле: найти участок длиной 1, затем использовать это событие в качестве префикса и добавить другие события, чтобы проверить, может ли оно стать HEWU.Следует отметить, что каждый раз, когда событие продлено, время этого события не может совпадать с временем префикса, разница превышает МПД

UP-Span:

MiningSimultHUE:

В основном отвечает за интеллектуальный анализ параллельных событий текущего набора событий.

MiningSerialHUE:

В основном отвечает за анализ последовательных событий текущего набора событий.

Персональное резюме

Изучив алгоритм High-Utility Pattern Mining, понять его несложно.Большинство определений добавляет измерение времени. С точки зрения псевдокода, алгоритм в целом не очень сложен, и идея примерно такая же, как у алгоритма HUI-Miner, но текущие исследования в этой области относительно невелики, и места еще много. для расширения. В этой статье впервые предлагается и успешно реализована основанная на сценариях концепция добычи полезных ископаемых. Недостатком является то, что использование только предложенного EWU в качестве граничного значения неизбежно будет слишком расплывчатым и приведет к созданию множества наборов кандидатов, которые изначально не нужны. Также необходимо использовать лучшие алгоритмы обрезки, такие как те, что используются в FHM, или изменить структуру хранения данных для повышения эффективности поиска.