# Agglomerative Clustering with Threshold Optimization via Extreme Value Theory
## 3 Threshold Estimation Using Extreme Value Theory  
The idea that a single threshold can be determined for agglomerative clustering may be rather unexpected and unreasonable. However, there are many properties of deep networks that were initially unexpected and unreasonable to expect [14; 45; 46; 47]. There is much we do not understand about deep networks and deep features; in this paper, we will add their unreasonable ability to support good clustering threshold determinations to that list. In a deep feature space, the feature mapping was trained to reduce a loss that results in points with similar semantics, as implicitly defined by the loss function, and which will be mapped closer together. It also produces a continuous space with a data-dependent but normalized dimensional value. If we consider non-degenerate points, i.e., a point that should be clustered with at least one other point, then its nearest neighbors are, with high probability, points with which it should cluster. This observation explains part of the power of FINCH [4], which clusters the first nearest neighbors. In our analysis, we use approximate (first) nearest neighbors a subset of points that should cluster. The set of approximate nearest neighbors form a distribution from which we will estimate our threshold for the clustering algorithm such as AHC. We note that, since the approach can use Approximate Nearest-Neighbors (ANN), our complexity can be sub-quadratic since first ANN pairs can be found in \(O(N\log N)\) time [48], while true nearest neighbors take \(O(N^{2})\). Let us formalize our model and then state our core theorems. Let \(s_{n,m}\in\mathbb{R}^{S},1\leq m\leq M,1\leq n\leq N_{m}\); be a set of \(N_{m}\) points drawn from \(M\) classes, which represent the ideal cluster label for each input. Let mapping function \(f:\mathbb{R}^{S}\mapsto\mathbb{R}^{D}\) be a continuous well-behaved feature extraction function. Let \(p_{i}=f(s_{n,m})\) be a mapped sample (Since we do not use the label \(m\) during clustering, we here remove class information from the sample index.). Let \(\mathcal{P}\) be the set of all mapped points \(p_{i}\). Allowing for but not assuming clustering in rounds (as in FINCH), we let \(C_{j}^{(r)}\in C^{(r)}\) be a cluster formed from at least one point in round \(r\), with \(C^{(r)}\) being the set of all clusters after round \(r\). Let \(d_{ij}=d(p_{i},p_{j})\) be the dissimilarity or distance between points \(p_{i}\) and \(p_{j}\). Let \(g_{ij}^{(r)}=d(C_{i}^{(r)},C_{j}^{(r)})\) be the dissimilarity or distance gap between clusters \(C_{i}^{(r)}\) and \(C_{j}^{(r)}\) at round \(r\), e.g., distance between their centroids or other cluster distances (linkages) as nearest distances, maximum distances, and average distances. Let the set \(\ell_{i}^{(r)}\) be the set of link distances of points added in round \(r\). Let \(\eta_{i}^{(r)}\) be the set of ground-truth correct link distances of connections that ideally should have been added between ANNs in round \(r\); note this is known only to an oracle. In agglomerative clustering, we initially consider each point \(p_{i}\) a cluster of size one, and then we merge \(p_{i}\) and \(p_{j}\) into a cluster if their gap distance \(d_{ij}\) is sufficiently small. In later rounds, these clusters get further merged if their link distance \(g_{ij}^{(r)}\leq\tau\). **Theorem 1** (Extreme-Linkage Theorem). : _The distribution of the sets of both the ideal link distances \(\eta_{i}^{(r)}\) and the observed link distance \(\ell_{i}^{(r)}\) are governed by the Fisher-Tippet (Extreme Value) theory, and because they are sets of minima and are bounded from below, the limiting distribution is a Weibull._  
Proof. : We consider \(\ell_{i}^{(r)}\), and the proof for \(\eta_{i}^{(r)}\) is similar. We start by noting that, at each level, we choose the (approximate) smallest link distances out of the much larger set of pairwise distances.