# Automated Exploratory Clustering to Democratize Clustering Analysis
## 3 Materials and Methods
### Similarity-Based Tradeoff  
As we have now seen two variants, which optimize the two different goals of Definition 4, we will now propose a third Interestingness function that exactly balances the  
Figure 5: Two-dimensional evaluations of a dataset. The blue objects are dominated by the red objects. The area, which is dominated by the red objects, is marked in light red. aforementioned tradeoff. While it will still use the skyline to get a high coverage, we will prune similar clusterings to ensure a much smaller resulting set. **Definition 9** (Similarity-pruned interestingness). : _Using the skyline defined in Definition 7 and a similarity function \(\sin:\mathrm{C}\mapsto[0,1]\), we can define the following:_  
\[I(C,\varepsilon)= \begin{cases}|C|&,C=S(C)\wedge\forall o\
eq c\in C:sim(c,o)< \varepsilon\\ -1&,else\end{cases}  \tag{10}\]  
We will get the biggest possible subset of the skyline, in case there are no two elements which have a higher similarity value than \(\varepsilon\). Using this, we can control the tradeoff between minimality and coverage by adapting \(\varepsilon\), as a value close to zero will eliminate most clusterings and only leave a small subset, while a high value of \(\varepsilon\) will retain the complete skyline. It can be seen that both methods mentioned earlier are in fact only special parametrisations of this approach. Setting the \(\varepsilon=1\) will lead to all clusterings in the skyline being selected, while setting \(\varepsilon=0\) will grant only one clustering (provided an apt method to handle ties is added). The choice of the similarity function of two clusterings will have a significant impact on this result. Possible choices include the ARI [58] or the AMI [51]. However, any external CVI can be used. The creation of this set is similar to the motley algorithm used in the field of diversification [50,59]. However, in that field, the size of the resulting set is fixed instead of the threshold parameter. This set can be approximated more efficiently by a greedy algorithm shown in Algorithm 1. We start to build the set with the skyline element with the minimal highest similarity to any other clustering in the skyline. Following this, we expand the resulting set with the clustering, which has the minimal highest similarity to any selected clustering. We stop this once no clustering is left. In l. 1-3, the skyline set \(S\) is built, and for every clustering, the highest similarity to any other clustering is stored. In l.4-7, the starting element is selected and stored in the target set \(t\), while the remaining set \(rest\) is initialized and the current minimal maximal similarity \(sim\) to any object in the rest set is initialized to 0. While this similarity is smaller than \(\varepsilon\) (hence there still are clusterings in \(rest\) with a similarity less than \(\varepsilon\) to all clusterings to \(t\)), an addition of new clusterings to the target set is evaluated (l. 8-16). The array \(max_{s}ims\) is updated to reflect the maximal similarity to any object in the \(t\) set for every object in \(rest\), and the clustering with the minimal maximum similarity is selected for as the next new element \(new\_index\) (l. 9-10). If the similarity of this object to any object in \(t\) is smaller than \(\varepsilon\), the element is added to set \(t\) (l. 11-15); otherwise, the resulting set is returned (l. 17). The time complexity lies in \(\mathcal{O}(n^{3}+n^{2}\cdot\mathcal{O}(s))\). The first part (l.1-7) has a complexity of \(\mathcal{O}(n^{2}\cdot\mathcal{O}(s))\), as every similarity between two clusterings must be computed. The following while loop (l. 8-16) can happen up to \(n\) times, as all clusterings can be less similar than the threshold. The time complexity of assigning each element in the remaining set the maximum similarity of a set in the target set (l. 9) is in \(\mathcal{O}(n^{2})\). For this reason, the complexity of the for loop is in \(\mathcal{O}(n^{3})\). The main space requirement for this algorithm are the pairwise similarities.