## 3 The Optimized Agglomerative Approach
### Optimization on Traditional Agglomerative Approach  
Traditional agglomerative approach starts with each transaction staying in its own cluster, and then merges pairs of clusters to move up the hierarchy [13]. However, the cluster merge operation could not be undone, namely transactions could not be taken away from one cluster. It is required to perform merge operations on as optimal clusters as possible. For a single cluster, the best candidates should be picked out to be merged with. The following example expresses a situation of unsuitable candidates. **Example 2. **_Suppose there are three initial clusters \(\left\{i\colon\{abc\},j\colon\{abd\},\ h\colon\{bd\}\right\}\), we have \(c_{i}\Rightarrow c_{j}\), \(c_{j}\Rightarrow c_{k}\) and \(\mathrm{M}(c_{i})<\mathrm{M}(c_{j})\)._  
In Example 2, \(c\)i is the merge candidate of \(c\)i, and \(c\)i is the merge candidate of \(c\)i. Although \(c\)i and \(c\)i comes before \(c\)i, \(c\)i should be merged with \(c\)i rather than \(c\)i, as the former would produce larger profit value for the current clustering. In other case, if \(\mathrm{M}(c\)i) and \(\mathrm{M}(c\)i) are both maximum among all the delta values, it is obvious that \(c\)i, \(c\)i and \(c\)i could be merge together to achieve optimal profit value. To deal with this phenomenon, we define a Global Maximum (\(GM\)) Delta value for all the Delta values. \[GM=\max\left\{M(c_{i})\,|\,k\in\llbracket 1,\cdots,p\rrbracket\right\} \tag{9}\]  
If \(\mathrm{M}(c_{i})=\mathrm{M}(c_{j})=GM\), it is sure that merging \(c_{i}\) with \(c_{j}\) is best, denoting as \"\(c_{i}\Leftrightarrow c_{j}\)\", as well as merging \(c_{j}\) with \(c_{h}\). On this basis, we could make improvement on the traditional agglomerative approach. Traditional agglomerative approach could only perform merge operation on two clusters at a time, which would not stop until all the transactions are in one cluster or the number of result clusters is specified. However, in this optimized approach, all the clusters linked with the \(GM\) value are able to merge at once, which saves a lot of time. Agg-CLOPE would automatically terminate until all Delta values are no more than zero and no further merge operations could be performed. We define the cluster graph to support this feature. **Definition 9** (Cluster Graph): A cluster graph is an undirected graph \(G=\left(V,E\right)\) where \(V\) is a set of vertices each of which representing a cluster and \(E\) contains edges that connect two vertices (clusters) with Delta value equals to \(GM\). Figure 2 illustrates the clustering process on the transactions {_ab_, _ac_, _bc_, _abd_, _acd_, _bcd_} using Agg-CLOPE with \(r=2.0\). At the very beginning, each transaction is a cluster symbolized as a vertex in graph \(G\) (see Figure 2a). By calculating the Delta values of each two clusters, those meeting with the \(GM\) value are linked and to be merged (see Figure 2b). So at the end of the first round and the beginning of the second round, there are three new clusters remaining (see Figure 2c). The second  
Figure 2: **(a)** Initial state of \(G\) with each transaction in a cluster; **(b)** clusters meeting with Global Maximum (\(GM\)) value are linked; **(c)** Linked clusters are merged; **(d)** The remaining clusters are linked; **(e)** The final result contains only one cluster. round actually does the same as those in the first round. As all Delta values equal to _GM,_ the clusters are linked with each other for the further merge operation (see Figure 2d). After that, there are no more clusters to be merged, and the algorithm ends with a final cluster including all the transactions (see Figure 2e).