Впереди написано: это новейший алгоритм высокоэффективного интеллектуального анализа последовательностей в 2020 году. Он основан на общем LQS-дереве в сочетании со структурой списка, дополненном двумя эффективными стратегиями сокращения, LAR и IIP, что значительно сокращает майнинг. , Ресурсы, потребляемые в процессе, и по сравнению с тремя алгоритмами USpan, HUS-Span и ProUM в ходе экспериментов, производительность алгоритма HUSP-ULL является лучшей.

Fast Utility Mining on Sequence Data

Следует подчеркнуть, что анализ последовательности должен основываться на упорядоченном состоянии всех элементов (по причинам, которые можно найти вАлгоритм SPADEиАлгоритм HUSRMПримечания), конкретные правила сортировки задаются в соответствии с особенностями самого алгоритма, единого принципа нет.

определение

• Символ «q-» относится к «количественному», например, «q-последовательность» относится к последовательности, содержащей количественный параметр ($a$, 2)($b$, 1)}, {($c$, 3)}>), "последовательность" относится к $ab$}, {$c$}>, то же, что и "q-itemset", "q-item"
• установить "q-последовательность"$s$ = <$v_1$, $v_2$, $\ldots$, $v_d$>, "последовательность"$t$ = <$w_1$, $w_2$, $\ldots$, $w_{d^\prime}$> если$d$ = $d^\prime$и составляют$v_k$элементы с$w_k$Если элементы одинаковы, то это называется$t$совпадение$s$($t \sim s$); очевидно, последовательности могут соответствовать несколько q-последовательностей (количество является переменной), таких как $a$, 1}, {$b$, 1}> или $a$, 3}, {$b$, 2}> $\sim$ <{$a$}, {$b$}>
• событие$w$да$w^\prime$Подсобытия хорошо оценены, но для "q-itemset"$v \subseteq v^\prime$, тогда и только тогда, когда он составляет$v$Элементы состоят из$v^\prime$Подмножество элементов и соответствующее количество должны быть согласованы, что отличается от определения отношения включения набора элементов; аналогично, последовательность$s$и$w$тот же критерий
• Потому что есть несколько$s$совпадение$t$, поэтому при вычислении "последовательности"$t$Когда значение полезности , возьмите самое длинное совпадающее значение полезности ($u(t, s)$ = max{$u(s_k) \mid t \sim s_k \land s_k \subseteq s$}),дальше,$t$Полное значение полезности в наборе данных рассчитывается как$u(t)$ = $\sum_{s \in D}${$u(t, s) \mid t \subseteq s$}; Для простоты позиция последнего элемента каждого совпадения определяется как точка соединения, где первая точка соединения называется начальной точкой, например пусть$t$= , то в$S$ = <{($a$, 2)(c, 3)}, {($a$, 3)($b$, 1)($c$, 2)}, {($a$, 4)($b$, 5)($d$, 4)}, {($e$, 3)}> Точки соединения — 4, 7, 7, а начальная точка соединения — 4 (Ps.потому что в заказанном состоянии она из$b$начать соединение вместо$a$)
• для "последовательности"$t$Существует два метода расширения (I-конкатенация и S-конкатенация): I-конкатенация эквивалентна$i_j$Расширение последовательности по вертикали не увеличивает длину исходной последовательности ($t \oplus i_j$>$_{I-Concatenation}$); S-конкатенация эквивалентна помещению элемента$i_j$Расширение последовательности по горизонтали увеличит длину исходной последовательности на 1 ($t \oplus i_j$>$_{S-Concatenation}$)
• Чтобы сократить время сопоставления последовательностей и уменьшить их количество, для каждой подходящей последовательности создается новая структура данных Utility-Linked-List Structure, конкретное содержание которой показано на следующем рисунке:

, по сравнению со структурой данных, используемой другими алгоритмами, структура UL-List более компактна и не хранит много ключевой информации (с использованием технологии проецирования)

Стратегия

свойство замыкания вниз

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

утилита расширения последовательности

В соответствии с концепцией остаточной полезности в алгоритме HUI-Miner для последовательности сумма значений полезности ее расширяемых элементов представляет максимальную степень расширения последовательности. "последовательность"$t$Расширение определяется как$I(t)_{rest}$ = {$i_j \mid i_j \in <s - t>_{rest} \land t \subseteq s \land s \in D$}, утилита расширения последовательности$SEU(t)$ = $\sum_{s \in D}${$u(t, s)$ + $u(<s-t>_{rest})$ $\mid$ $t \subseteq S$}, то имеет место теорема$SEU(t^\prime) \le SEU(t)$,$u(t) \le SEU(t)$установлено, то можно сделать вывод, что если "последовательность"$t$из$SEU$меньше порога, нет необходимости$t$быть расширенным (процесс доказательстваАлгоритм ProUMв деталях)

утилита расширения префикса

$SEU$Недостаток очевиден, он не доказывает$t$сама по себе неэффективная последовательность, и если вычислить ее вручную$SEU$Можно обнаружить, что она намного выше, чем реальная величина полезности (Ps.Повторный расчет значения t). Поэтому в статье используется более компактная верхняя граница$PEU(t)$ = $\sum_{s \in D}${$PEU(t, s) \mid t \subseteq s$},$PEU(t, s)$ = max{$u(s_k)$ + $u(<s - s_k>_{rest})$ $\mid$ $t \sim s_k \land s_k \subseteq s$}(Ps. Принятие максимального значения на самом деле является верхней границей); по той же причине существуют теоремы$PEU(t^\prime) \le PEU(t)$,$u(t) \le PEU(t)$учредил (Ps. Процесс доказательства подробно описан в статье)

в соответствии с$PEU$, в документе предлагаются две новые стратегии обрезки:

• LAR pruning strategy: Для двух различных способов соединения последовательности устанавливаются следующие неравенства: 1) max{$u(<t \oplus i_j>_{I-Concatenation})$} $\le$ $\sum_{s \in D}${$PEU(t, s)$ $\mid$ $<t \oplus i_j>_{I-Concatenation} \subseteq s$}; 2) макс{$u(<t \oplus i_j>_{S-Concatenation})$} $\le$ $\sum_{s \in D}${$PEU(t, s)$ $\mid$ $<t \oplus i_j>_{S-Concatenation} \subseteq s$},в$i_j$это "последовательность"$t$Кандидаты под разные способы подключения (Ps.Это не сложно понять, сам ПЭУ рассчитывается по максимальному значению) когда верхнее граничное значение меньше порога, можно сделать вывод о кандидате$i_j$является малополезным предметом и не может быть использован для$t$для масштабирования эта стратегия позволяет избежать избыточных$PEU$рассчитать
• IIP pruning strategy: данная "последовательность"$t$и любой предмет$i_j \in I(t)_{rest}$,если$\sum_{s \in D}${$PEU(t, s)$ $\mid$ ($<t \oplus i_j>_{I-Concatenation} \subseteq s$) $\lor$ ($<t \oplus i_j>_{S-Concatenation} \subseteq s$)} меньше порога, то можно сделать вывод, что$i_j$да$t$Нерелевантный член , в последующей паре$t$и его расширения$t^\prime$можно игнорировать непосредственно в процессе обработки$i_j$, эта стратегия может еще больше уменьшить значение оставшегося члена полезности и сузить диапазон расширения последовательности

Поддельный код

Main algorithm

PGrwoth procedure

Judge procedure

Суммировать

Алгоритм HUSP-ULL основан на предыдущем$PEU$Concept разрабатывает две новые стратегии обрезки и подробно анализирует их.$SWU$,$SEU$и$PEU$отношения между тремя. Основное внимание в статье уделяется анализу того, как уменьшить размер LQS-дерева с помощью новой стратегии обрезки.Структура данных UL-списка не такая, как предполагалось, и не создается для каждой подпоследовательности (она действительно невозможно подумать об этом, слишком много кандидатов на последовательность), но для каждого элемента транзакции (полная последовательность), и в статье было проведено большое количество экспериментов и подробных сравнительных обсуждений, которые очень стоит изучить и исследовать. Кроме того, чтобы отличить его от задачи интеллектуального анализа эпизодов, алгоритм выполняет служебный интеллектуальный анализ, при этом каждый элемент транзакции не зависит друг от друга.