# Agglomerative Clustering with Threshold Optimization via Extreme Value Theory
## 2 Related Work
### Evaluation Metrics  
While generally, clustering has no explicit way to be evaluated, some evaluation protocols provide the ground truth for the clusters, e.g., when clusters should be formed for separate classes in a classification task. Here, we report the metrics that are often applied in these cases:  
**Normalized Mutual Information (NMI)** Ref. [38] makes it possible to compare the performance of two algorithms that produce different numbers of clusters. Particularly, we compare the obtained clusters \(C\) with ground-truth classes \(G\). The NMI provides values between 0 (no overlap between clusters) and 1 (perfect clustering).  
Let \(C\) be the clustering result for samples \(X\), with \(C_{i}\) representing a specific cluster and \(G\) be the ground-truth set, with \(G_{j}\) representing all samples belonging to class \(j\). Then, the NMI is computed as [39]:  
\[\text{NMI}(C,G)=\frac{\sum\limits_{C_{i}\in C}\sum\limits_{G_{j}\in G}|C_{i} \cap G_{j}|\log\frac{|C_{i}\cap G_{j}||X|}{|C_{i}||G_{j}|}}{\sqrt{\sum\limits_{ C_{i}\in C}|C_{i}|\log\frac{|C_{i}|}{|X|}+\sum\limits_{G_{j}\in G}|G_{j}|\log \frac{|G_{j}|}{|X|}}} \tag{1}\]  
**Adjusted Rand Index (ARI)**[40; 41; 42] is a variant of the Rand Index (RI) that is corrected for chance. Such a correction establishes a baseline by using the expected similarity of all pairwise comparisons between clustering results specified by a random model [43]. To understand ARI, assume \(G\) is the ground-truth and \(C\) the clustering result. Then, \(a\), \(b\), and \(c\) are defined as:  
1. the number of pairs of samples that are in the same set in \(G\) and in the same set in \(C\).
2. the number of pairs of samples that are in different sets in \(G\) and in different sets in \(C\).
3. the total number of possible pairs in the dataset (without ordering).  
The unadjusted RI can be described as:  
\[RI=\frac{a+b}{c}. \tag{2}\]  
To guarantee that random label assignments obtain a value close to zero, the expected \(RI\) of random clustering results is discounted by defining the ARI:  
\[ARI=\frac{RI-E[RI]}{\max(RI)-E[RI]} \tag{3}\]  
One severe drawback of ARI is that it is strongly impacted by outliers; thus, it may not have a good reflection on the quality of the clusters. In some cases, ARI scores are increased with a decreasing number of detected clusters. Nevertheless, we provide ARI measures so other researchers can compare with our results in the future.  
**B-Cubed (\(B^{3}\)) F-measure \(F_{b}\)**[44] is the harmonic mean of \(B^{3}\) precision \(P_{b}\) and \(B^{3}\) recall \(R_{b}\), and it can be used to evaluate clustering algorithms that yield a different number of clusters. \(B^{3}\) precision \(P_{b}\) calculates the fraction of points in the same cluster that belongs to the same class. \(B^{3}\) recall \(R_{b}\) calculates the fraction of points in the same class that is assigned to the same cluster. To compute \(P_{b}\), \(R_{b}\), and \(F_{b}\), a correctness indicator \(B(x_{i},x_{j})\) is defined as 1 when a pair of samples of the same class are in the same cluster, or when a pair of samples of different classes are in different clusters and 0 otherwise. Using this indicator, precision, recall, and F-measure are evaluated as:  
\[P_{b}=\frac{1}{|X|}\sum\limits_{x_{i}\in X}\sum\limits_{x_{j}\in C(x_{i})} \frac{B(x_{i},x_{j})}{|C(x_{i})|}\hskip 14.226378 ptR_{b}=\frac{1}{|X|}\sum \limits_{x_{i}\in X}\sum\limits_{x_{j}\in G(x_{i})}\frac{B(x_{i},x_{j})}{|G(x _{i})|}\hskip 14.226378 ptF_{b}=\frac{2P_{b}R_{b}}{P_{b}+R_{b}} \tag{4}\]  
where \(C(x_{i})\) is the cluster that contains sample \(x_{i}\) and \(G(x_{i})\) is the set of all samples that belong to the same class as \(x_{i}\).