# Agglomerative Clustering with Threshold Optimization via Extreme Value Theory
## 3 Threshold Estimation Using Extreme Value Theory
Thus, each \(g_{ij}\in\ell_{i}^{(r)}\) can be viewed as a minimum over a set of distances that are associated with some sampling of the distance between the initial set of points if \(r=1\) and from clusters from the prior level if \(r\geq 2\). If we view the merging of the clusters in level \(r\) in decreasing order of pair distance \(g_{ij}\), then each new linkage distance can be seen as a new minimum over an increasing set of items. We can view the set over which we consider the actual minimum as excluding a few items as ignored by the ANN algorithm. Since the Fisher-Tippet Theorem [49] applies to maxima, we perform a change of variables to use the negative of each distance and then consider the distribution of a maximum set of values \(\zeta_{i}=-\ell_{i}^{(r)}\). Let \(\phi\) be the associated distribution of the maximum of \(\zeta_{i}\) in the Fisher-Tippet Theorem (see supplemental material based on [50; 51; 52]) and, combined with the knowledge that distances are bounded (\(-\ell_{i}^{(r)}\leq 0\)), yields that \(\phi\) converges to a reversed Weibull, as it is the only one of the EVT distributions that are bounded. Changing the variable back yields that the distribution of link distances follows a Weibull distribution. Given the Extreme-Linkage Theorem to estimate a threshold, we use a three-parameter Weibull distribution:  
\[\mathrm{W}(x;\mu,\sigma,\xi)= \begin{cases}\frac{\xi}{\sigma}\left(\frac{x-\mu}{ \sigma}\right)^{\xi-1}e^{-\left(\frac{x-\mu}{\sigma}\right)^{\xi}}&x<\mu-\frac {\sigma}{\xi}\\ 0&\text{otherwise}\end{cases}  \tag{5}\]  
where \(\mu\in\mathbb{R}\), \(\sigma\in\mathbb{R}^{+}\), and \(\xi\in\mathbb{R}^{-}\) are locations, scale, and shape parameters [53]. This theorem applies to any clustering algorithm using approximate nearest-neighbor merging, e.g., it applies to both FINCH [4] and any AHC algorithm. This theorem allows us to \"reject\" any potential linkage that is unlikely. Given the distributional parameters \(\mu,\sigma,\xi\), to compute the merge distance threshold \(\tau_{w}\) that yields a given probability \(0<p<1\) such that probability \(P(d_{ij}<\tau_{w})\geq p\), we use the inverse CDF to derive:  
\[\tau_{w}=\mu+\sigma\cdot\left(-\ln(1-p)\right)^{\frac{1}{5}} \tag{6}\]  
Since the Extreme-Linkage Theorem shows that both the true linkages and the computed linkages follow Weibull distributions, we contend that selecting \(\tau_{w}\) to reject improper linkages comes down to fitting the distribution to the set of minima, i.e., the ANN distances. Given the desired level of confidence, such as 99%, a pair merges when consistent with that distribution, we select \(\tau_{w}\) as in (6), i.e., \(\tau_{w}\) is considered the maximum ANN distance which should merge. Considering correct links, the associated, linked points would still be ANN for some set of points within that cluster. Thus, all valid links should be ANNs and a single \(\tau_{w}\) computed from an initial set of ANNs is sufficient since ANN of points within a cluster is still subject to that distribution. In Figures 1 and 2, and figures in the Supplemental Material, we fit and compute \(\tau_{w}\) to show that the performance is stable for moderate variations in \(\tau_{w}\). Figure 1: _EVT-based Clustering Threshold Selection._ We prove that nearest-neighbor distances and valid cluster link distances will follow an EVT distribution, and show how that leads to a good threshold selection for clustering. Yellow shows the data frequency histrogram, blue the probability density function, and green the cumulative density fit of a Weibull distribution to the approximate nearest-neighbor distance for IJB-B (protocol 512, see Section 5). While noisy, it is a good fit and supports choosing the threshold \(\tau_{r}/\tau_{w}\) at for the Cumulative Distribution Function (CDF) of the Weibull for 99% probability. With \(\tau_{w}\) being defined, we can now state our main conjecture:  
**Conjecture 1** (Unreasonable Clusterability of Deep Features).