# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 3 Mining Top-\(k\) High Average-Utility Pattern
Similarly, the \(q\)-sequence \(Q\):\(\langle Y_{1},Y_{2},\cdots,Y_{n}\rangle\) matches the sequence \(S\):\(\langle X_{1},X_{2},\cdots,X_{m}\rangle\), denoted as \(S\sim Q\) or \(Q\sim S\), if and only if \(n=m\) such that \(Y_{k}\sim X_{k}\), \((1\leqslant k\leqslant m=n)\)._  
**Definition 5** (Contain). : _Consider the \(q\)-itemset \(Y\):\(\{(i^{\prime}\text{:}q_{1})(i^{\prime}\text{:}q_{2})\cdots(i^{\prime}\text{:}q _{n})\}\) and the itemset \(X\):\(\{i_{1},i_{2},\cdots,i_{m}\}\), we say that \(Y\) contains \(X\) or \(X\) is contained in \(Y\), denoted as \(Y\sqsupseteq X\) or \(X\sqsubseteq Y\), if and only if \(X\) is a subset of itemset and the itemset matches the \(q\)-itemset \(Y\)._  
\begin{table}
\begin{tabular}{l l  
For instance, from Tables 1 and 2, the itemset \(\{a,b,f\}\)_matches_ the \(q\)-itemset \(\{(a\):\(2)\), \((b\):\(2)\), \((f\):\(2)\}\) in the sequence \(Q_{3}\). In \(Q_{5}\), the \(q\)-itemset \(\{(a\):\(1)\), \((b\):\(1)\), \((f\):\(1)\), \((g\):\(3)\}\)_contains_ the itemset \(\{a,b,f\}\). **Definition 6** (Instance of Q-sequence). : _Consider the \(q\)-sequence \(Q\):\(\langle Y_{1},Y_{2},\cdots,Y_{n}\rangle\) and the sequence \(S\):\(\langle X_{1},X_{2},\cdots,X_{m}\rangle\), where \(n\geqslant m\), we say that there is an instance of \(S\) at position \(p\):\(\langle j_{1},j_{2},\cdots,j_{m}\rangle\) in \(Q\), if and only if there exists positive integers \(1\leqslant j_{1}<j_{2}<\cdots<j_{m}\leqslant n\), so that \(X_{v}\sqsubseteq Y_{j_{v^{\prime}}}(1\leqslant v\leqslant m\leqslant n)\). Also, we can say \(Q\) contains \(S\), denoted as \(S\sqsubseteq Q\)._  
For instance, there are two _instances_ of sequence \(\langle\{a,b\},\{g\}\rangle\), \(\langle\{(a\):\(1)\), \((b\):\(1)\}\), \(\{(g\):\(3)\}\rangle\) and \(\langle\{(a\):\(2)\), \((b\):\(2)\}\rangle\), \(\{(g\):\(3)\}\rangle\), at positions \(\langle 2,4\rangle\) and \(\langle 3,4\rangle\) in \(Q_{3}\). Therefore, we could also say the \(q\)-sequence \(\langle\{(a\):\(1)\), \((b\):\(1)\}\), \(\{(g\):\(3)\}\rangle\) or \(\langle\{(a\):\(2)\), \((b\):\(2)\}\), \(\{(g\):\(3)\}\rangle\)_contains_ the sequence \(\langle\{a,b\},\{g\}\rangle\). **Definition 7** (Sequence Utility). : _Assume that the \(q\)-sequence \(\langle Y_{j_{1}},Y_{j_{2}},\cdots,Y_{j_{m}}\rangle\) is an instance of sequence \(S\):\(\langle X_{1},X_{2},\cdots,X_{m}\rangle\) at position \(p\):\(\langle j_{1},j_{2},\cdots,j_{m}\rangle\) in \(Q\):\(\langle Y_{1},Y_{2},\cdots,Y_{n}\rangle\). The sequence utility of \(S\) in \(Q\) is the sum of the utilities of the \(q\)-items within \(S\), denoted as \(u(S,p,Q)\) and calculated as follows:_  
\[u(S,p,Q)=\sum_{v=1}^{m}u(X_{v},j_{v},Q)=\sum_{v=1}^{m}u(Y_{j_{v^{\prime}}}j_{ v},Q)\]  
Generally, a sequence appears in one \(q\)-sequence more than once. Given \(P(S,Q)\) denote the set of all the positions of \(S\) in \(Q\). The sequence utility of \(S\) in \(Q\) is the maximum value of instance utility at different positions and is defined as follows:  
\[u(S,Q)=\max_{p\in P(S,Q)}u(S,p,Q)\]  
Assume that the sequence \(S\) has _instances_ within different \(Q\) in \(q\)-sequence database \(D\). The sequence utility of \(S\) in \(D\) can be defined as follows:  
\[u(S)=\sum_{Q\in D\cap S\sqsubseteq Q}u(S,Q)\]  
For example, in Table 1, \(Q_{1}\) has an _instance_ of \(\langle\{e,f\},\{g\}\rangle\) at position: \(\langle 2,4\rangle\). Then, we can calculate \(u(\langle\{e,f\},\{g\}\rangle,\langle 2,4\rangle,Q_{1})=31+16=47\). For another case, in Table 1, \(Q_{1}\) has five _instances_ of \(s_{1}\):\(\langle a,d\rangle\), \(P(s_{1},Q_{1})=\{\langle 1,4\rangle,\langle 1,6\rangle,\langle 3,4\rangle, \langle 3,6\rangle,\langle 5,6\rangle\}\), \(u(s_{1},\langle 1,4\rangle,Q_{1})=4+8=12\), \(u(s_{1},\langle 1,6\rangle,Q_{1})=4+4=8\), \(u(s_{1},\langle 3,4\rangle,Q_{1})=1+8=9\), \(u(s_{1},\langle 3,6\rangle,Q_{1})=1+4=5\), and \(u(s_{1},\langle 5,6\rangle,Q_{1})=1+4=5\). The utility of the sequence \(s_{1}\) in \(Q_{1}\) is \(u(s_{1},Q_{1})=\max\{12,8,9,5,5\}=12\), and \(u(s_{1})=u(s_{1},Q_{1})+u(s_{1},Q_{2})=12+11=23\).