# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Upper Bounds and Pruning Strategies
We have  
\[au(S^{\prime}) =\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}(u(S,p,Q)+u( i_{k},j_{k},Q))}{|S|+1}\] \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\] \[\leqslant\frac{u(S)+u(i_{k})}{|S|+1}\] \[=\frac{u(S)+(u_{INCR}(i_{k})+minau)}{|S|+1}\] \[\leqslant\frac{u(S)+(u_{INCR}(rs^{\prime})+minau)}{|S|+1}\] \[=\frac{(u_{INCR}(S)+minau\times|S|)+(u_{INCR}(rs^{\prime})+minau)}{ |S|+1}\] \[=\frac{u_{INCR}(S)+u_{INCR}(rs^{\prime})}{|S|+1}+minau\] \[\leqslant\frac{u_{INCR}(S)+u_{INCR}(rs^{\prime})}{|S|}+minau\] \[=\frac{u_{INCR}(S)+u_{INCR}(rs^{\prime})+minau\times|S|}{|S|}\] \[=\frac{(u_{INCR}(S)+minau\times|S|)+u_{INCR}(rs^{\prime})}{|S|}\] \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]0 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]1(2) if \(rs^{\prime}\) is null, but \(rs\) is not null, then \(u_{rs^{\prime}}(S,j_{m},Q)=0\) and \(|rs^{\prime}|=0\). Consider an item \(i_{k}\) in \(rs\) and \(i_{k}<minau\), we obtain  
\[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]2 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]3 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]4 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]5 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]6 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]7 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]8 \[\leqslant\frac{\sum_{S\subseteq\Omega\setminus\Omega\in D}\max \{u(S,p,Q)+u(i_{k},j_{k},Q)\}}{|S|+1}\]9 \[\leqslant\frac{u(S)+u(i_{k})}{|S|+1}\]0 \[\leqslant\frac{u(S)+u(i_{k})}{|S|+1}\]1 \[\leqslant\frac{u(S)+u(i_{k})}{|S|+1}\]2  
Therefore, we obtain \(PEAU(S)\geqslant au(S^{\prime})\). Based on the above derivation, the average utility of any sequence extended from \(S\) is less than \(PEAU(S)\). Then, the \(PEAU(S)\) is the maximum average-utility upper bound of \(S\) and its descendant. Thus, if the value of \(PEAU(S)\) is less than \(minau\), any descendants of \(S\) will not be the high average-utility sequential pattern, and these descendants could be safely pruned. **Definition 13** (\(RSAU\) Upper Bound). : _Let \(PEAU(S)\) be the prefix extension average utility of \(S\) in database \(D\). Assume that a sequence \(S^{\prime}\) is extended from \(S\) through one \(I\)-Extension or \(S\)-Extension operation, i.e., consider the node representing \(S\) in LQS-tree, the node representing \(S^{\prime}\) is its child node. The reduced sequence average utility of \(S^{\prime}\) in \(q\)-sequence database \(D\), denoted as \(RSAU(S^{\prime})\), is defined as_  
\[RSAU(S^{\prime})=\left\{ \begin{array}{cc}PEAU(S),&S\sqsubseteq Q\wedge S^{ \prime}\sqsubseteq Q\wedge Q\in D\\ 0,&otherwise\end{array} \right.\]  
Proof. : Assume the sequence \(S^{\prime}\) is a prefix of \(S^{\prime\prime}\) or \(S^{\prime\prime}=S^{\prime}\), and the sequence \(S^{\prime}\) could be extended from sequence \(S\) through one \"_extension_\" operation, such that the sequence \(S\) is also a prefix of \(S^{\prime\prime}\). Based on the Definition 11, we obtain  
\[au(S^{\prime\prime})\geqslant PEAU(S).\]  
According to the Definition 12, we have  
\[RSAU(S^{\prime})=PEAU(S),\]such that the average of the sequence is  
\[au(S^{\prime\prime})\geqslant RSAU(S^{\prime}).\]  
\(\square\)  
Thus, if the value of \(RSAU(S^{\prime})\) is less than \(minau\), any descendants of \(S\) are not the high average-utility sequential pattern, and these descendants could also be safely pruned. But RSAU still overestimates the upper bound. This upper bound is similar to RSU in HUS-Span, and more details can be found in Ref. [46].