# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Proposed TKAUS Algorithm  
By adopting the aforementioned mechanism and strategy, the proposed TKAUS is described as follows. The main algorithm is represented as Algorithm 1. Algorithm 2 represents a recursive procedure, and Part 3 of the whole algorithm procedure represents the updating of the set of HAUSPs and the threshold. In the beginning, a given quantitative database is read, and the number of desired HAUSPs is specified. The algorithm utilizes the variable \(minau\) to keep the current minimum average-utility threshold (Line 1) and engages the \(TKList\), which is a sorted list of size \(k\) to maintain the top-\(k\) HAUSPs (Line 2). From lines 3 to 7, scan the original database once, calculate the utility value of each item (1-sequences), and construct the projected databases of all items. In line 8 and line 9, following the SAUR strategy, the algorithm increases \(minau\) to the \(k\)th highest average-utility value. From lines 10 to 14, for each item whose utility is greater than \(minau\), update to the \(TKList\). Then, adopting the upper bound, for each \(promising\) item, the \(projection\)-TKAUS algorithm is called recursively (Lines 15 to 19). When the TKAUS algorithm is over, the \(TKList\) is returned, which stores all the HAUSPs. ```
0: A quantitative database, \(D\). The number of desired HAUSPs, \(k\). 0: Top-\(k\) HAUSPs in \(D\). 1: initializing \(minau=0\)
2: initializing \(TKList=\varnothing\)
3: //First scanning (for the original database)
4:for each sequence \(Q\) in \(D\)
5: (1) calculating and storing the average utility of all 1-sequences
6: (2) constructing projected databases of all 1-sequences
7:endfor
8: sorting the average-utility values of all 1-sequences in descending order, then getting the \(k\)th highest average-utility value \(minau_{0}\)
9:\(minau=minau_{0}\)
10:for each sequence \(S\in 1\)-sequences
11:if\(S.au\geqslant minau\)
12: update \(TKList\)
13:endif
14:endfor
15:for each sequence \(S\in 1\)-sequences
16:if\(PEAU(S)\geqslant minau\)
17: calling \(projection\)-TKAUS \((S,D_{S})\)
18:endif
19:endfor
20:return\(TKList\)
```  
**Algorithm 1** The TKAUS algorithm ```
0: A sequence as prefix, \(S\). The projected database of \(S\), \(D_{S}\). 0: Top-\(k\) HAUSPs in \(D\). 1: scanning \(D_{S}\) once to:
2: (1) adding \(I\)-Extension items of \(S\) to \(\mathit{ilist}\)
3: (2) adding \(S\)-Extension items of \(S\) to \(\mathit{slist}\)
4:for each item \(i\in\mathit{ilist}\)
5: \(S^{\prime}\leftarrow\langle S\oplus i\rangle\)
6:if\(\mathit{RSAU}(S^{\prime})<\mathit{minau}\)
7: removing \(i\) from \(\mathit{ilist}\) (Pruning the unpromising item in \(\mathit{ilist}\))
8:endif
9: constructing projection database of \(S^{\prime}\),\(D_{S^{\prime}}\)
10:if\(\mathit{S^{\prime}.au\geqslant\mathit{minau}}\)
11: calling \(\mathit{update}(S^{\prime},\mathit{minau},\mathit{TKList})\)
12: putting \(S^{\prime}\) to \(\mathit{seqlist}\)
13:endif
14:endfor
15:for each item \(i\in\mathit{slist}\)
16: \(S^{\prime}\leftarrow\langle S\otimes i\rangle\)
17:if\(\mathit{RSAU}(S^{\prime})<\mathit{minau}\)
18: removing \(i\) from \(\mathit{slist}\) (Pruning the unpromising item in \(\mathit{slist}\))
19:endif
20: constructing projection database of \(S^{\prime}\), \(D_{S^{\prime}}\)
21:if\(\mathit{S^{\prime}.au\geqslant\mathit{minau}}\)
22: calling \(\mathit{update}(S^{\prime},\mathit{minau},\mathit{TKList})\)
23: putting \(S^{\prime}\) to \(\mathit{seqlist}\)
24:endif
25:endfor
26:for each sequence \(S^{\prime}\in\mathit{seqlist}\)
27:if\(\mathit{PEAU}(S^{\prime})\geqslant\mathit{minau}\)
28: Calling \(\mathit{Projection}\)-\(\mathrm{TKAUS}(S^{\prime},D_{S^{\prime}})\)
29:endif
30:endfor
31:return\(\mathit{TKList}\)
```

**Algorithm 2**_projection_-TKAUS algorithm

As shown in Algorithm 2, in line 1, the _projection_-TKAUS algorithm identifies items that can be extended by scanning the projected database. Each input sequence is regarded as a prefix of a pattern.