Написано впереди: этот алгоритм представляет собой топ-k алгоритм майнинга, разработанный на основе структуры списка полезностей HUI-Miner, и многие стратегии с самовозрастанием порога заслуживают нашего изучения.Цель написания этой заметки — представить эти стратегии и личные мысли

An efficient algorithm for mining the top-k high utility itemsets, using novel threshold raising and pruning strategies

Образец

External utility of items

Example database

определение

Большая часть содержания может быть отнесена кHUI-MinerПримечания к этому алгоритму, здесь только некоторые дополнительные дополнения

Estimated Utility Co-occurrence Structure (EUCS)

в диссертацииEUCSопределяется как кортеж ($\{(a;\ b;\ TWU(ab) )$,$a,b \in I^*$,$TWU(ab) \in R^+\}$),в$a$и$b$все элементы (по умолчанию неповторяющиеся)$R^+$Это показывает, что алгоритм не учитывает идею отрицательной полезности. Для удобства понимания автор рисует несколько матричных диаграмм для иллюстрации (Ps. На самом деле для хранения этой информации используется hashmap, а не матричная структура).Конкретный процесс построения выглядит следующим образом:

Utility list construction

• Значение полезности набора элементов: В построенном списке полезности формула для определения значения полезности набора элементов выглядит следующим образом:$\sum_{\rm ul \in UL(X)}ul.iutil$,в$UL(X)$Относится к списку полезностей набора элементов X (как построить, см.HUI-Miner)

Transitive extension upper-bound utility

Учитывая любой набор предметов$X$и его расширяемость$x$, новая формула расчета граничного значения$teu(X, y)$ = $\sum_{\rm ul \in UL(X)}ul.iutil$ + $\sum_{\rm ul \in UL(y)}ul.iutil$ + $u(y)$

Coverage

когда два предмета$i$и$j$Отношения существования$g(i) \subseteq g(j)$, мы называем термин$j$Включают(cover)пункт$i$, можно сделать вывод, что$i$покрытие$C(i) = \{g(i) \subseteq g(x) \land x \in I\}$,в$g(x)$Указывает на включение$x$Номера всех транзакционных позиций (TID),который$g(x) = \{tid \mid x \subseteq T_{\rm tid}\}$

Дальнейшее расширение, есть и между наборами предметовcoverageотношения, когда наборы элементов$X = x_1x_2 \ldots x_{\rm n}$,$x_{\rm i} \in C(x_1) (2 \le i \le n)$При установлении$X$даcoverage itemset

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

• свойство 1: элемент команды$i$и$j$имеют$j \in C(i)$отношения, есть$u(ij) \ge u(i) + \mid g(i) \mid \times p(j) > 0$, где набор элементов$ij$расширяется комбинацией двух терминов
• природа 2: элемент команды$i$и$j$имеют$j \in C(i)$отношения, есть$TWU(i) = TWU(ij)$
• свойство 3: пусть набор предметов$X = x_1x_2 \ldots x_{\rm n}$,но$u(X) = \sum_{2 \le i \le n}u(x_1x_{\rm i}) - (n-1) \times u(x_1)$
• природа 4:в соответствии ссвойство 3, мы можем получить новый способ расчета значения полезности: установить терм$x$,$x_i$и наборы предметов$Y$имеют$x_i \in C(x)$,$Y \subset C(x)$и$x_i \not\in Y$,Доступный$u(xYx_i)$=$u(xY) + u(xx_i)-u(x)$, и мы знаем, что$u(xYx_i) > u(xY)$(Ссылаться насвойство 1можно предположить)
• свойство 5:в соответствии сприрода 4, легко подумать$minUtil \le u(xY) < u(xYx_i)$Всегда установлено (можно ли это объяснить замкнутостью?), нормативное выражение в статье: установить срок$j$, набор$X$и$Y$имеют$Y \subseteq C(j)$,$X \cap Y = \varnothing$и$j \not\in X$Если отношения постоянны, то$minUtil \le u(jX) < u(jXY)$должны быть установлены

Стратегия

The estimated utility co-occurrence pruning strategy (EUCP)

в содержании по определениюEUCSПосле построения удалите те$TWU(xy) < minUtil$Двоичный член после сортировки можно получитьEUCSTСтруктурная схема, как показано на следующем рисунке:

Хорошо видно, что количество бинарных наборов элементов намного меньше исходного, и тогда на основе этих бинарных наборов элементов будут добыты наборы элементов более высокого порядка с высокой полезностью.Ядро этой стратегии сокращения по-прежнему использует традиционную$TWU$Однако большинство предыдущих алгоритмов обеспечивают отсечение наборов элементов первого порядка, и этот алгоритм может успешно использовать это свойство для наборов элементов второго порядка, что имеет большую справочную ценность для других алгоритмов.

The efficient utility-list pruning strategy

В соответствии с двумя определениями расчета значения полезности набора элементов и расчета остаточной полезности набора элементов можно получить новую стратегию сокращения, то есть$\sum_{\rm ul \in UL(X)}ul.iutil + \sum_{X \succ i}U(i) < minUtil$время, набор предметов$X$И ни один его набор расширений не может быть набором элементов с высокой полезностью. Причина в том, что в уже отсортированном элементе транзакции (транзакции) он ранжируется в наборе элементов$X$Все последующие элементы станут$X$Если совокупное значение полезности всех расширенных элементов меньше порогового значения, то значение полезности отдельной комбинации будет меньше порогового значения, поэтому его можно напрямую удалить (процесс подтверждения находится в процессе).HUI-Minerподробно обсуждается)

Ранний отказ от дополнительной стратегии (EA)

• Свойство LA: дано два набора предметов$X$и$Y$,когда$\sum_{\rm \forall T_i \in D}U(X, T_{\rm i}) + RU(X, T_{\rm i}) - \sum_{\rm \forall T_j \in D, X \subseteq T_{\rm j} \land Y \not\subseteq T_{\rm j}}U(X, T_{\rm j}) + RU(X, T_{\rm j}) < minUtil$когда есть$\forall X \subseteq X^\prime \land Y \subseteq Y^\prime \Rightarrow X^\prime Y^\prime \not\in HUIs$

EAОсновная идея стратегии состоит в том, чтобы прекратить построение списка полезности набора элементов при встрече с определенным набором элементов для свойства LA, чтобы сэкономить место и время, и доказать, что процесс деривации подробно описан. в газете

Transitive extension pruning strategy (TEP)

в соответствии сTransitive extension upper-bound utilityСодержимое определения имеет следующие два свойства:

• $teu(X, y) \ge u(Xy)$
• $teu(X, y) \ge \sum_{\rm ul \in UL(Xy)}(ul.iutil + ul.rutil)$

Процесс доказательства подробно описан в статье, и здесь упоминается только заключение. Согласно этой природе, когда$teu(X, y) < minUtil$, развернуть набор$Xy$и его последующие расширения представляют собой наборы элементов с низкой полезностью, вы можете не создавать для них список полезности (в сочетании сThe efficient utility-list pruning strategy)

Real item utilities threshold raising strategy (RIU)

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

The co-occurrence threshold raising strategy (CUD)

На основе EUCST, используя информацию 2-элементных наборов для повышения порога, можно рассмотреть вопрос о построении CUDM для хранения этой информации в других алгоритмах (есть ли способ избежать результатов вычислений, полученных при двукратном сканировании набора данных )

The coverage threshold raising strategy (COV)

Основная цель состоит в том, чтобы построить список COV для улучшения порога.Процесс показан в следующем псевдокоде.Лично я считаю этот метод более применимым, поскольку задействованы только одномерные элементы.

алгоритм

construct utility list

существуетHUI-MinerВ нем есть подробные введения. Ключом к этому методу является то, что у каждого кандидата есть "общий префикс» можно сплайсировать, но этот метод сплайсинга на самом деле очень неэффективен и создаст много бесполезных кандидатов, поэтому перед операцией сплайсинга заставьте кандидатов вырезать эти неэффективные элементы как можно больше

iConstruct algorithm

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

kHMC algorithm

Псевдокод всего алгоритма выглядит следующим образом:

Суммировать

kHMCВ алгоритме используется множество стратегий повышения порога, и он вращается только вокруг структуры списка полезностей.В первый раз, когда я столкнулся с этой статьей, я просто просмотрел ее грубо, и у меня не было подробного понимания методов. и используемые характеристики. Автор также провел множество сравнительных экспериментов, чтобы проверить превосходство алгоритма kHMC с различных аспектов, а также упомянул в конце, что концепция покрытия действительно может использоваться в утилитарном майнинге в других областях. Лично я считаю, что этот алгоритм все еще имеет относительно большое справочное значение и достоин изучения. Единственный минус - нет возможностиspmfНайдите соответствующий код на...