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

An Efficient Algorithm for Mining High Utility Sequential Patterns

Образец

quality of items

sequence database

определение

определение ценности полезности иHUI-MinerТаким же образом рассчитываются значения полезности предметов, наборов предметов, элементов транзакций и наборов данных, только здесь делаются некоторые дополнения:

• Пункт определяется как$i_{\rm k} \in I$ ($1 \le k \le n$), значение полезности отдельного предмета определяется как$p(i_{\rm k})$, номер которого в последовательности равен$(i_{\rm k}, q)$

• Набор элементов определяется как$l = [(i_{\rm j_1}, q_1), \ldots, (i_{\rm j_{\rm n}}, q_{\rm n})]$, следует отметить, что выражение набора элементов длиной всего 1 в статье без квадратных скобок, и каждый элемент в наборе элементов расположен в алфавитном порядке.

• Последовательность состоит из набора наборов элементов,$s = \big< l_1, l_2, \ldots, l_{\rm m} \big>$

• База данных последовательностей состоит из нескольких последовательностей.Чтобы различать последовательности, каждой последовательности присваивается уникальный идентификатор, как показано в таблице 2 в приведенном выше примере.

• Порядок между элементами, наборами элементов и последовательностями обычно в алфавитном порядке, с I-Concatenate (параллельное расширение, без изменения размера последовательности) и S-Concatenate (последовательное расширение, размер последовательности плюс один).

  Примеры из статьи следующие:

  1. исходная последовательность -$\big<ea\big>$размер 2,$\big<e(ab)\big>$: I-Concatenate, размер последовательности после расширения по-прежнему равен 2;$\big<eab\big>$: S-Concatenate, размер расширенной последовательности равен 3
  2. когда последовательность$t_{\rm a}$это последовательность$t$На основе I-Concatenate,$t_{\rm b}$получается на основе S-конкатената, то$t_{\rm a} < t_{\rm b}$
  3. когда последовательность$t_{\rm a}$и$t_{\rm b}$Он получается на основе того же метода расширения, и элементы в двух последовательностях сравниваются в алфавитном порядке, например$\big<(ab)\big> < \big<(ab)b\big>, \, \big<(ab)c\big> < \big<(ab)d\big>$

• Лексикографическое дерево q-последовательности (LQS-Tree) строится по следующим правилам:

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

  • Любой узел получается с помощью I-Concatenate или S-Concatenate родительского узла.

  • Все дочерние элементы любого узла перечислены в возрастающем алфавитном порядке.

    

• Последовательный шаблон с высокой полезностью по-прежнему отличается от набора элементов с высокой полезностью (HUI), потому что в последовательности будет несколько повторяющихся q-подпоследовательностей, например, в$s_5$Последовательность нейтронов$\big<ea\big>$имеют$\big<(e, 3)(a, 6)\big>, \, \big<(e,3)(a,2)\big>$и$\big<(e,3)(a,2)\big>$, алгоритм предусматривает, что максимальное значение элемента полезности используется в качестве значения полезности подпоследовательности, т. е.$u_{\rm max}(\big<ea\big>, \, s_5) = \lbrace 3 \times 1 + 6 \times 2 \rbrace = \lbrace 15 \rbrace$, общая формула$u_{\rm max}(t) = \sum max \lbrace u(s^\prime) \mid s^\prime \sim t \land s^\prime \subseteq s \land s \in S \rbrace$,Сейчас$u_{\rm max}(\big< ea \big>) = u_{\rm max}(\big< ea \big>, s_2)+u_{\rm max}(\big< ea \big>, s_4)+u_{\rm max}(\big< ea \big>, s_5) = 41$. когда$u_{\rm max}(t) \ge minUtil$тогда последовательность является последовательностью с высокой полезностью

  Ps. Почему бы не использовать накопительный метод? Не потому ли, что это упорядоченная последовательность и накопление не имеет никакого смысла? подумай об этом

• Оставшаяся полезность предметов относится к сумме значений полезностей всех предметов в текущей последовательности после текущего предмета, то есть следующихutility matrixЗначение справа от каждой записи в круглых скобках ($u_{\rm rest}(k, s_{\rm i})$)

  Ps. Оригинальная статья подробно описана в Разделе 4.4.

Стратегия

utility matrix

С помощью этой матричной таблицы мы можем получить информацию о комбинации (поскольку за раз расширяется только один бит, поэтому унарные элементы образуют двоичные наборы элементов, а двоичные элементы формируют троичные наборы элементов...) Например: элемент$быть$Выполните расширение I-Concatenation, чтобы получить$\big< (be) \big>$, просто поместите два столбца q-itemset 1 и q-itemset 3$b$и$e$Полезные значения , можно сложить, т. е.$v(\big< (be) \big>, s_4) =\lbrace 10+2, \, 5+2 \rbrace$; Если да$\big< (be) \big>$Разверните S-конкатенацию, чтобы получить$\big<(be)a\big>$, q-itemset 2 можно найти из таблицы 3:$\big<[(b, 2)(e, 2)](a, 7)\big>$и q-элемент 3:$\big<[(b, 2)(e, 2)](a, 4)\big>$,Сейчас$v(\big< (be)a \big>, s_4) = \lbrace 12+14, \, 12+8 \rbrace$(почему нет$\lbrace 7+14 \rbrace$Это потому, что существует порядок между q-наборами элементов, если вычисление$\lbrace 7+8 \rbrace$Тогда вы должны получить$\big<(abe)\big>$последовательность)

width pruning

Основная функция состоит в том, чтобы отфильтровать как можно меньше наборов элементов-кандидатов для дальнейшей фильтрации, чтобы получить реальную последовательность набора элементов с высокой полезностью на основе взвешенного по последовательности свойства замыкания вниз (SDCP), то есть использования взвешенного по последовательности (SWU, метод расчета соответствует TWU), например$SWU(\big< ea \big>) = u(s_2) + u(s_4) + u(s_5) = 41 + 50 + 37$)

Теорема: когда последовательность$t$имеют$SWU(t) < minUtil$, то все расширенные последовательности, основанные на этой последовательности, являются последовательностями с низкой полезностью и могут быть сокращены (см. Раздел 4.3 исходной статьи для процесса доказательства)

depth pruning

в последовательности$t$и$S$в, есть$u_{\rm max}(t) < \sum _{\rm i \in s^\prime \land s^\prime \sim t \land s^\prime \subseteq s \land s \in S}(u_{\rm rest}(i, s) + u(s^\prime))$, так когда$u_{\rm rest}(i, s) + u(s^\prime) < minUtil$, мы можем перестать углубляться в текущий узел и вместо этого вернуться к предыдущему узлу. в$s^\prime$это первая совпадающая подпоследовательность в последовательности$t$последовательности, а пары подпоследовательностей$t$Расширение также соответствует с первого$s^\prime$Для начала поместите последние элементы один за другим, используя I-конкатенацию или S-конкатенацию, чтобы получить более длинную расширенную подпоследовательность. Если расширение начинается со второй совпавшей подпоследовательности, ее значение полезности всегда ниже, чем расширение первой совпавшей подпоследовательности (поскольку элементов для расширения не так много).

алгоритм

Суммировать

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