# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Upper Bounds and Pruning Strategies  
There is an inherent time order between items in the sequence database. The process of HUSPM must deal with the critical combinatorial explosion of the search space [48]. If the maximum sequence utility is much lower than the minimum utility threshold, even the sum of sequence utility and utilities of items in the _remaining sequence_ still cannot reach the threshold. The sequence is \"\(unpromising\)\". [PERSON] et al. [48] proposed the upper bound and corresponding strategy to reduce unpromising patterns and unnecessary operations. Several existing studies have proposed some sequence pattern mining upper bounds. Three typical upper bounds: sequence extension utility (SEU) [22], sequence projected utilization (SPU) [29], and sequence-weighted utilization (SWU) [19] had been introduced compared in ref. [23]. SWU is a loose upper bound and is an overestimation, SPU loses some real HUSPs, and SEU, which is a modified real upper bound, could further limit the search scope. [PERSON] et al. [46] proposed PEU upper bound and RSU upper bound to speed up HUSPM. The PEU upper bound was defined as \(PEU(t,p,s)=u(t,p,s)+ru(s/(t,p))\). The existing research work is instructive to improve the performance of HAUSPM by reducing the \(unpromising\) pattern. The transaction-maximum average-utility upper bounds designed by [PERSON] et al. [59] or proposed by [PERSON] et al. [55] need to sort the set of remaining items by utility descending order. However, in a quantitative sequence database, each \(q\)-itemset has a special order, so sorting among \(q\)-items that contain different \(q\)-itemsets is not an effective method. In fact, each item in _remaining sequence_ is helpful to add up to higher sequence utility by the \"\(extension\)\" operation for HUSPM and algorithm TKUS. The item is \(promising\) if the value of PEAU is not lower than the minimum average-utility threshold. However, in HAUSPM and our proposed algorithm, the average utility of the sequence, which is generated by the \"\(extension\)\" operation, is not higher than one of its prefixes if the utility of the appending item is lower than the average utility of the prefix. **Definition 11** (**Increment of Sequence Utility**). : _Let \(u(s)\) be the sequence utility of \(s\). If \(u(s)\) is in excess of the minimum average-utility threshold minau, let \(u_{INCR}(s)\) be the rising proportion of the excess sequence-utility value in \(u(s)\), and is calculated as follows:_  
\[u_{INCR}(s)=u(s)-minau\times|s|,\]  
Assume that there is an \(instance\) of sequence \(S\) at the \(extension\)\(position\)\(p:\)\(<\)\(j,\)\(j,\)\(\cdots,\)\(j_{m}\)\(>\) in \(q\)-sequence \(Q\), the corresponding \(remaining\)\(sequence\) is \(rs\) which is the rest after \(p\) to theend. Let the \(rs^{\prime}\) be a subsequence consisting of items that have a higher utility value than \(minau\) in \(rs\). The rising proportion of the excess sequence-utility value in \(rs\) is denoted as \(u_{INCR}(rs)\), and is calculated as follows:  
\[u_{INCR}(rs^{\prime})=\sum_{Q\in D\wedge S\subseteq Q}u_{rs^{\prime}}(S,j_{m},Q )-minau\times|rs^{\prime}|,\]  
where the \(|rs^{\prime}|\) is the maximum length of \(rs^{\prime}\) of the prefix \(S\) in database \(D\). Please note that \(j_{m}\) is determined by the \(extension\)\(position\) of sequence \(S\). Therefore, we define the \(u_{INCR}(rs^{\prime})\). It is a measure for the promotion of the \(remaining\)\(sequence\) utility on the utility of the generated candidates. The concept of \"\(unpromising\)\", which has been mentioned at the beginning of this section, can be redefined. The appending item is \(unpromising\) if the average utilities of all the generated sequences containing this item still are lower than \(minau\), i.e., all the promotion of its prefix and its \(remaining\)\(sequence\) will not increase the sequence average utility to the value of \(minau\). We will, therefore, give the following upper bounds and pruning strategies. **Definition 12** (PEAIU Upper Bound).