Написано впереди: Прошло много времени с момента предыдущего изучения алгоритма USpan. На этот раз я изучу анализ последовательности. Эта статья решает связь вывода правила ассоциации и продвигает предыдущую работу по шаблонам последовательности интеллектуального анализа на шаг вперед; стратегия, используемая алгоритмом HUSRM Есть еще, нужно потратить некоторые усилия на исследование

Efficient Mining of High-Utility Sequential Rules

Образец

sequence dataset

utility table

определение

Основное определение может относиться кUSpanПримечание к этому алгоритму, здесь только некоторые дополнения

• Предполагается, что последовательное правило существует в двух наборах элементов.$X$и$Y$имеют$X, Y \subseteq I$,$X \cap Y = \empty$и$X, Y \not= \empty$, правило последовательности$X \rightarrow Y$связанные средствав той же последовательности, набор$X$набор элементов после появления$Y$также происходит, размер правила последовательности$\mid X \mid \times \mid Y \mid$, использовать одновременно$seq(r)=\lbrace s \mid s \in SDB \land r \subseteq s \rbrace$Указывает правило включения$r$все последовательности ,$ant(r)=\lbrace s \mid s \in SDB \land X \subseteq s \rbrace$Указывает правило включения$r$Все последовательности фронта
• Поддержка правила (support of rule) правила ассоциации$r$Поддержка в наборе данных также выражается в виде соотношения, а расчетное выражение имеет вид$sup_{SDB}(r)=\frac{\mid seq(r) \mid}{\mid SDB \mid}$
• Доверие к правилу (достоверность правила) правило ассоциации$r$Достоверность набора данных также выражается в виде отношения, а расчетное выражение имеет вид$conf_{SDB} = \frac{\mid seq(r) \mid}{\mid ant(r) \mid}$
• Полезность последовательного правила, когда правило$r: X \rightarrow Y$в последовательности$s_c$Когда существует в , его значение полезности рассчитывается как$u(r, s_c) = \sum_{(i \in X \cup Y) \land (r \subseteq s_c)}u(i, s_c)$,если$r \not\subseteq s_c$час,$u(r, s_c) = 0$; аналогичное рассуждение может быть получено, общая полезность правила во всем наборе данных равна$u_{SDB}(r) = \sum_{s \in SDB}u(r, s)$
• высокоэффективный последовательный анализ правил с учетом трех пороговых значений$minsup$,$minconf$и$minutil$, когда значение, соответствующее правилу, одновременно превышает пороговое значение, мы рассматриваем правило как правило последовательности с высокой полезностью (то есть ограничений больше)

Одна вещь, которую следует отметить в отношении правил майнинга, — это метод расширения, который также объясняется в тексте размером$1 \times 1$Правила постепенно расширяются влево и вправо, чтобы получить более длинные интересные правила, но следует отметить, что порядок расширения влево и вправо и рекурсивный метод сильно повлияют на окончательные результаты майнинга; например, правила$r$:$\lbrace a \rbrace \rightarrow \lbrace c \rbrace$Вы можете либо развернуть влево, а затем развернуть вправо, либо наоборот, чтобы получить новые правила$r^\prime$:$\lbrace a, b \rbrace \rightarrow \lbrace c, d \rbrace$, есть возможность сгенерировать два новых правила, другой случай$\lbrace b \rbrace \rightarrow \lbrace e \rbrace$и$\lbrace c \rbrace \rightarrow \lbrace e \rbrace$можно расширить слева$c$и$b$получить такие же новые правила$\lbrace b, c \rbrace \rightarrow \lbrace e \rbrace$, решение описано в определении ниже

• расширяемость

  • левое расширение для правил$X \rightarrow Y$и пункт$i \in I$, когда для$\forall j \in X$имеют$i \succ_{lex} j$и$i \not\in Y$, который продолжается влево до$X \cup \lbrace i \rbrace \rightarrow Y$

  • То же верно и для правого расширения, когда для$\forall j \in Y$имеют$i \succ_{lex} j$и$i \not\in X$, право которого распространяется на$X \rightarrow Y \cup \lbrace i \rbrace$

  • Следует добавить, что,$\succ_{lex}$Это относится к лексикографическому расположению между элементами, которое используется для решения проблемы, заключающейся в том, что разные правила генерируют одни и те же новые правила из-за расширения; поскольку элемент может быть расширен как влево, так и вправо, это обычно используется по умолчанию. сначала, затем правое расширение и левое расширение могут продолжаться в правом расширении, но только правое расширение может быть выполнено в левом расширении, чтобы решить проблему новых правил, когда одно и то же правило повторяется из-за разных порядков расширения.

• Оцененная последовательностью полезность предмета имеет тот же эффект, что иTWU, расчетное выражение$SEU(i)$=$\sum_{(s_c \in SDB) \land (\lbrace i \rbrace \subseteq s_c)}SU(s_c)$,в$SU$да$s_c$Общая полезность последовательности, такая же, какTU, что означает, что расчет ведется по всему набору данных, все включения$i$Сумма значений полезности последовательности ; аналогично для правил, состоящих из разных терминов$r$Таким же образом рассчитывается предполагаемая полезность ,$SEU(r)$=$\sum_{s_c \in seq(r)}SU(s_c)$, роль этих оценок состоит в том, чтобы помочь определить, является ли текущий элемент/правило потенциально интересным, если они не меньше множества$minutil$, то мы думаем, что эти пункты/правила могут быть расширены и, вероятно, будут эффективными.

• Запись полезной таблицы (utility-table) Это новая структура хранения, разработанная отдельно для записи всех задействованных правил.$r$Информация о полезности использования$ut(r)$Представление (структура служебного списка), в нем много фрагментов данных, формат$(sid, iutil, lutil, rutil, lrutil)$,в:

  • sid: Указывает, что он содержит$r$серийный номер ($S_{sid} \in seq(r)$)
  • iutil:Выражать$r$значение полезности в текущей последовательности
  • lutil: Указывает те элементы в текущей последовательности, которые можно использовать для$r$провестиЛевыйсумма значений полезности развернутых терминов
  • rutil: Указывает те элементы в текущей последовательности, которые можно использовать для$r$провестиправильносумма значений полезности развернутых терминов
  • lrutil: Указывает те элементы в текущей последовательности, которые можно использовать для$r$провестиоСумма расширенных значений полезности

  Значения полезности последних трех расширений записи действительно могут использоваться как часть оценочной стоимости, что удобно для$r$Провести обрезку, в процессе использования необходимо уточнить, какой способ расширения в данный момент осуществляется, и усвоить элементы расширения.$i$и расширенные предметы/наборы предметов$j$Отношения между ними легко понять; далее мы продолжаем знакомить вас с тем, как рассчитать правила расширения с помощью таблицы полезности, учитывая расширенные правила.$r^\prime$, правило$r$, расширение$i \succ_{lex} j \in s_c$а также$ut(r)$и$ut(r^\prime)$:

  • sid: Это должно быть согласовано, потому что правило расширения должно быть в той же последовательности, что и исходное правило.
  • iutil':$iutil^\prime(r^\prime)$=$iutil(r)$+$u(\lbrace i \rbrace, s_{sid})$
  • lutil':$lutil^\prime(r^\prime)$=$lutil(r)$-$u(j, s_{sid})$-$u(i, s_{sid})$, какой срок$j$не может быть правилом$r^\prime$изЛевыйрасширения, но правила$r$изЛевыйэлемент расширения, параллельный элемент$i$если бы это было правилом$r$изЛевыйрасширения, то также вычтите его значение полезности, в противном случае нет необходимости вычитать термин$i$та часть стоимости
  • rutil':$rutil^\prime(r^\prime)$=$rutil(r)$-$u(j, s_{sid})$-$u(i, s_{sid})$, ограничения такие же, как и выше, просто поставьтеЛевыйрасширяться доправильнорасширять
  • lrutil':$lrutil^\prime(r^\prime)$=$lrutil(r)$-$u(j, s_{sid})$-$u(i, s_{sid})$, какой срок$j$не может быть правилом$r^\prime$изорасширения, но правила$r$изорасширение, параллельный элемент$i$если бы это было правилом$r$изорасширения, то также вычтите его значение полезности, в противном случае нет необходимости вычитать термин$i$та часть стоимости

  Необходимость расширенного набора после вычитания предметов$i$и$j$Полезная ценностьправильноснова расширитьЛевыйрасширять

• Достоверность правила расширения с использованием битового вектора$b(i)$представлять предмет$i$в какой последовательности они появились, используйте$1$значит появиться,$0$Указывает на отсутствие; затем побитовый берется битовый вектор каждого элемента в наборе элементовиоперация, в конце концов$1$Количество - это набор$\mid ant(X) \mid$, правило$r$Метод расчета тот же, а поддержку можно получить интуитивно через таблицу полезностей, например$bv(a)$=1111 $\land$ $bv(b)$=1011 $\Rightarrow$ $bv(ab)$=1011

  Ps. Хотя документ выглядит так, как будто он использует длинный массив для хранения этих 0 и 1, в коде он фактически использует хэш-карту для хранения соответствующих пар ключ-значение и напрямую вычисляет битовый вектор нового правила, сравнивая ключи

Стратегия

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

utility-table

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

• потому что каждое правило$r$Составьте список отдельно, который записывает все вхождения правила, так что, естественно, есть$u(r)$=$\sum_{i \in sid}iutil(r_i)$
• Аналогично, для правил$r$Формула для расчета степени поддержки:$sup_{SDB}(r)$=$\frac{\mid ut(r) \mid}{\mid SDB \mid}$
• $iutil(r)$+$rutil(r)$+$lutil(r)$+$lrutil(r) \le SEU(r)$, поэтому таблица полезности на самом деле предоставляет более компактное граничное значение (оценочное значение, которое можно получить, уточнив формулу)
• Если правило$r$после одного разаоРасширение получает новые правила$t$,имеют$u(t) \le iutil(r)$+$rutil(r)$+$lutil(r)$+$lrutil(r)$(Потому что с каждым расширением существует меньше последовательностей, содержащих это новое правило)
• если правило$r$после одного разаЛевыйРасширение получает новые правила$t$,имеют$u(t) \le iutil(r)$+$lutil(r)$+$lrutil(r)$

compact utility-table

В ходе эксперимента авторы наблюдали две закономерности:

• существуетЛевыйВо время расширения:

  • $rutil$Он не всегда используется, поэтому вам не нужно вычислять значение
  • $lutil$и$lrutil$Сумма всегда используется, поэтому их сумму можно использовать вместо двух значений.

  Очевидно, что это сделает таблицу меньше и займет меньше времени на построение.

• В любой последовательности, в правилепервый разМесто появленияпослепредметы можно использовать какправильнорасширяться, соответственно, вДоможно использовать какЛевыйрасширять

алгоритм

HUSRM algorithm

Left Expension

Right Expension

Суммировать

Вышеизложенное представляет собой полное содержание алгоритма HUSRM. Он основан на идее списка полезностей и строит правила более высокого уровня непосредственно через список без обхода набора данных. Это также прорывная работа в области высокоуровневых вычислений. интеллектуальный анализ правил последовательности утилит. Лично мне очень интересно, что автор разбил исходный алгоритм на четыре оптимизированные версии разной степени для экспериментального сравнения. Самая большая проблема этого типа алгоритма заключается в том, что время выполнения слишком велико.Из-за сложного процесса построения экспериментальные результаты многих алгоритмов не очень хороши, и необходимы дополнительные исследования, чтобы определить, существует ли более эффективная структура хранения. для упрощения процесса строительства или нового строительства идеи.