Написано ранее: непрерывный последовательный анализ шаблонов является очень распространенной задачей в нашей повседневной жизни, такой как веб-журналы, анализ последовательности ДНК, траектории движения объектов и т. д., но существующие алгоритмы анализа не могут вводить данные для эффективного анализа, потому что последовательности, которые они обычно get находятся в состоянии разъединения и фрагментации между элементами, поэтому этот алгоритм предлагает лучшее решение проблемы постоянного извлечения сложных последовательностей.

Utility-driven Mining of Contiguous Sequences

мотивация

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

определение

• пункт(item): наименьшая единица в наборе данных, с$x_i$значит, ограниченное количество

• наборы предметов (itemset): состоит из конечного числа элементов, непустых, с$X$представляет, а лексикографический порядок по умолчанию между каждым элементом композиции

• последовательность(sequence): состоит из конечного числа наборов элементов, непустых, с$S$представлены, а сформированные наборы товаров упорядочены

• Количественный термин (quantitative item): Чтобы присвоить элементам атрибуты полезности и количества, используйте ($x_i$:$q$) или$q$-предмет означает

• Наборы квантованных элементов (quantitative itemset): то же, что и выше, ограничено$q$-элементы составляются, а составные элементы упорядочены

• последовательность квантования (quantitative sequence): то же, что и выше, ограничено$q$-наборы предметов составлены, упорядочены и имеют уникальные меткиSID

• непрерывная последовательность (contiguous sequence): учитывая две разные последовательности$S_m$и$S^\prime_n$(нижний индекс указывает количество различных наборов элементов, содержащихся в последовательности), для любого$1 \le k \le n-m+1$,имеют$X_1 \subseteq X^\prime_{k}$, $X_2 \subseteq X^\prime_{k+1}$, $\ldots$, $X_m \subseteq X^\prime_{k+m-1}$установлено, то$S$да$S^\prime$непрерывная подпоследовательность ; в свою очередь,$S^\prime$да$S$Последовательные суперпоследовательности [например, $a$}, {$af$}> и $c$}, {$ab$}, {$aef$}>】

• совпадение(matching): данный набор элементов$X$и квантованные наборы элементов$Y$, когда есть и только для любого$1 \le k \le m$,имеют$x_k$ = $y_k$, это называется$X$совпадение$Y$, Упоминается как$X \sim Y$; Последовательность такая же, очевидно, в зависимости от атрибута количества,$X$может соответствовать нескольким$Y$

• пример (instance): данная последовательность$S_m$и последовательность квантования$Q_n$(Нижний индекс указывает количество различных наборов элементов, содержащихся в последовательности,$m \le n$),как$\exists p$, $m \le p \le n$и$\forall k$, $1 \le k \le m$,имеют$X^\prime_k \sim Y_{p-m+k}$и$X_k \subseteq X^\prime_k$установлено,$Q_n$в крайний срок$p$имеют$S_m$Экземпляр , в зависимости от того, где находится отсечка, по-видимому, существует$Q_n$правильно$S_m$несколько разных экземпляров

  Ps. В статье множество положений отсечки специально обозначено как EP(S, Q), и когда в Q есть хотя бы один экземпляр S, говорят, что Q содержит S, обозначенное как$S \sqsubseteq Q$

• полезность (utility): Для последовательностей в квантовании$Q$Первый$j$квантованные элементы в наборе квантованных элементов$x_i$, его значение полезности рассчитывается как$u(x_i, j, Q)$ = $q(x_i, j, Q) \times p(x_i)$[То есть количество * прибыль]; это рассуждение,

  • Включают$x_i$квантованные наборы элементов$X$Формула расчета ценности полезности:$u(X, j, Q)$ = $\sum_{x_i \in X}u(x_i, j, Q)$;
  • $Q$о$S$Полезность экземпляра$u(S, p, Q)$ = $\sum^m_{j=1}u(X_j, p-m+j, Q)$;
  • Поскольку существует несколько экземпляров, в качестве оценки берется максимальное значение.$u(S, Q)$ = max{$u(S, p, Q) \mid \forall p \in EP(S, Q)$};
  • Наконец, последовательность$S$в наборе данных$D$Значение полезности в$u(S)$ = $\sum_{Q \in D}u(S, Q)$

• значение полезности веса последовательности (sequence-weighted utilization, SWU): это оценочное значение с замыканием вниз, которое можно использовать в качестве условия оценки для сокращения, и его выражениеSWU($S$) = $\sum_{S \sqsubseteq Q \land Q \subseteq D}u(Q)$[Но это очень приблизительная оценка, объясненная в разделе «Стратегия сокращения GUIP»]

• Высокоэффективный режим непрерывной последовательности (high-utility contiguous sequential pattern): Согласно определению ценности полезности в предыдущем пункте, последовательность$S$даHUCSPтогда и только тогда, когда значение полезности не меньше$\xi \times u(D)$,$\xi$минимальный порог, установленный пользователем в виде процента

• расширение (extension): Любые наборы элементов низкого порядка могут быть объединены в наборы элементов высокого порядка с помощью определенных методов. При анализе последовательностей обычно одновременно расширяется только один элемент.$S$и пункт$x_i$, в этой статье представлены два метода расширения:

  • расширение элемента (I-extension):будет$x_i$непосредственно расширять$S$На последнем наборе элементов , обозначенном как $S \oplus x_i$> обратите внимание, что эта операция не увеличивает длину последовательности,
  • расширение последовательности (s-extension):будет$x_i$Поскольку новый набор предметов расширяется в$S$в конце помечается как $S \otimes x_i$>, это сделает$S$длина плюс 1

• расширение ((extension item):данный$S$, $Q$и$x_i$,в$x_i$да$S$последний срок,$EP(S, Q)$ = {$ep_1$, $\ldots$, $ep_n$},Так,

  • о$S$существует$Q$ВверхI-extensionНабор обозначается какIitem($S$, $Q$); аналогично, в$D$Набор выше обозначается какIitem($S$) = $\bigcup_{Q \in D}$Iitem($S$, $Q$)
  • о$S$существует$Q$ВверхS-extensionНабор обозначается какSitem($S$, $Q$); аналогично, в$D$Набор выше обозначается какSitem($S$) = $\bigcup_{Q \in D}$Sitem($S$, $Q$)

• Остаточная последовательность (remaining sequence):существуетаккуратныйПо правилам предполагается, что$Q$существует$S$из$p$Есть экземпляр на локации, о$Q$существует$S$Оставшаяся последовательность на обозначается как$Q / _{(S, p)}$, который также можно назвать$Q$Последовательность суффиксов ; соответственно, формула полезности оставшейся последовательности имеет вид$ru(Q / _{(S, p)})$ = $\sum_{x_i \in Q / _{(S, p)}}u(x_i)$

• расширенная полезность предмета (item-extension utilization):данный$S$, $S^\prime$, $Q$,В том числе$S \subseteq S^\prime$, $S \oplus/\otimes x_i$ = $S^\prime$, $Q$да$S$экземпляр ,$Q^p$выраженный в$Q$в$p$наборы предметов,$p \in EP(S, Q)$,Так,

  • Для I-расширения ($S^\prime$ = $S \oplus x_i$), с и только$x_i \in Q^p$час,IEU($S^\prime, p, Q$) = $u(S, p, Q)$ + $u(x_i, p, Q)$ + $ru(Q/_{(x_i, p)})$;Напротив,IEU($S^\prime, p, Q$) = 0
  • Для S-расширения ($S^\prime$ = $S \otimes x_i$), с и только$x_i \in Q^{p+1}$час,IEU($S^\prime, p, Q$) = $u(S, p, Q)$ + $u(x_i, p+1, Q)$ + $ru(Q/_{(x_i, p+1)})$;Напротив,IEU($S^\prime, p, Q$) = 0
  • Для нескольких I-расширений или S-расширенийIEU($S^\prime, p, Q$) = $max_{p \in (S, Q)}$IEU($S^\prime, p, Q$); дальше,IEU($S$) = $\sum_{S \sqsubseteq Q \land Q \subseteq D}$IEU($S, Q$)

• Список информации о последовательности (sequence information list, SIL): аналогичноСписок утилит (utility list), каждый список хранит$Q$, хотя бы одна из квантованных последовательностей$q$-itemset, в каждом наборе элементов хранится как минимум один кортеж ($q$-предмет, реальная полезность и остаточная полезность), схема структуры выглядит следующим образом

  

• цепочка экземпляров (instance-chain, IChain): хранитEP($S$, $Q$) информация и экземпляр в соответствующем положении отсечки$p$Полезное значение , по сути, представляет собой информацию об экземпляре сжатого хранилища, структурная диаграмма выглядит следующим образом.

  

Стратегия обрезки

GUIP strategy

в соответствии с$u(S)$определение может знатьSWU($S$) на самом деле намного больше, чем реальное значение полезности, и прямым результатом этого является увеличение числа недействительных кандидатов; поэтому статья в оригиналеSWUНа основе стратегии обрезки каждый раз отсеиваются неэффективные$x_i$, затем обновите$Q$и соответствующее оставшееся значение полезности, пока все элементы с низкой полезностью не будут полностью удалены

LUIP strategy

Первоначальная статья давала подробное доказательство и процесс рассуждений, поэтому я не буду здесь слишком подробно останавливаться;IEU($S$), когда он меньше минимального порога,$S$и его последовательности расширения неэффективны и могут быть удалены напрямую

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

FUCPM algorithm

Recursive search

Суммировать

Алгоритм использует жадную идею при сокращении элементов с низкой полезностью и повторяет цикл до оптимального решения.Одна из проблем, возникающих в связи с этим, заключается в том, каково потребление ресурсов при работе с различными наборами данных? С точки зрения производительности затрат памяти он хорошо работает на плотных наборах данных, но потребляет значительно больше на разреженных наборах данных, даже не так хорошо, как эталонный алгоритм для сравнения; но преимущества, которые дает это, также очень очевидны, то есть затраты времени явно малы, поскольку большое количество элементов с низкой полезностью удаляется на ранней стадии, количество сгенерированных наборов элементов высокого порядка будет намного меньше, что также подтверждается экспериментальным графиком сравнения кандидатов в статье ( за исключением разреженных наборов данных), и Экспериментальные данные сравнения стратегий также могут проиллюстрировать; в последнем эксперименте по сравнению между алгоритмом HUSPM и алгоритмом UCSPM видно, что количество смежных последовательностей слишком мало, что может уменьшить сложность анализа данных в определенной степени. Лично я считаю, что UCSPM является очень хорошим направлением исследований, и областей его применения также много.