# Agglomerative Clustering with Threshold Optimization via Extreme Value Theory
## 4 Approach  
### PEACE Parameter Selection  
Our Provable Extreme-value Agglomerative Clustering-threshold Estimation (PEACE) uses threshold \(\tau_{w}\) computed by fitting a Weibull. We note, however, that the fitting and threshold selection still requires a choice of parameters: amount of data to trim, tail-size, and confidence threshold. Thus, unlike FINCH, our approach is not parameter-free. However, we believe our parameters, which are about generic data quality, are more intuitive and better subject to defaults than choosing the actual number of clusters (K in K-Means), choosing between a partition of clusters (FINCH), or estimating maximum point separation within a cluster (\(\epsilon\) in DBSCAN). Our free parameters for Weibull fitting are about the quality of the data. For example, in most of the experiments herein, we use (6) with a tail-size of 1% of the data, which reduces the impact of stray outliers even without trimming the tail. For confidence to select that actual threshold given the fit, we use \(p=0.99\). If one has a rough estimate of the frequency of outliers, i.e., points that should not cluster, of say \(q>1\%\), then one can trim \(q\%\) of the data and use the remaining default parameters for the Weibull fitting. This type of approach is sufficient for many applications, and for most problems where one expects to cluster nearly all the data, our defaults (drop 1%, tail 1%, confidence 99%) will work. In general, slight overestimation of outliers is not a problem as results are stable for variations in \(\tau_{w}\); see plots in Supplemental Material. However, we observed that some datasets have way more than 1% outliers, and searching for the amount to trim would require some feedback on outliers or fit quality. We tried basic goodness-of-fit measures, such as sample-based Kolmogorov-Smirnov (KS). Unfortunately, those measures were still too weak--with 1000 generated samples from the Weibull fit, none of the distributions in experiments failed a KS test even with the many outliers in Labeled Faces in the Wild (LFW), where we have >50% outliers. Thus, for problems where one is uncertain about the potential for outliers, we developed a heuristic approach to normalize for outliers without a prior guess on the fraction of outliers. Recognizing that outliers also impact the raw distribution of all pair distances, we set up an equivalent relation to estimating a robust version of our threshold. If we let \(d(\mathcal{S})\) be a set of pairwise distances, our equivalent relation for robust threshold estimate \(\tau_{r}\) divided by our raw Weibull estimate \(\tau_{w}\) should equal the ratio of the median (a robust operator on all points) divided by the outlier-sensitive maximum distance on all points:  
\[\frac{\tau_{r}}{\tau_{w}}=\frac{\text{median}\{d(\mathcal{S})\}}{\text{max} \{d(\mathcal{S})\}} \tag{7}\]  
Solving that relation for \(\tau_{r}\) gives our normalization factor. We can apply this with EVT estimates of the ANN. We normalize by \(\omega\) as follows:\[\omega=\frac{\text{median}\{d(\mathcal{S})\}}{\max\{d(\mathcal{S})\}};\quad\tau_{r} =\omega\cdot\tau_{w}; \tag{8}\]  
where \(\tau_{w}\) employs (6) with 99% of the data and \(p=0.999\) then is scaled yield robust \(\tau_{r}\). While approximate nearest neighbors can be computed quickly, if \(\mathcal{S}\) includes all points, the normalizations would require all pairs, which would require complexity \(O(N^{2})\). The normalization, however, does not really need all pairs, and \(\mathcal{S}\) as a random sample of a few thousand points produces a good normalization, keeping total complexity to \(O(N\log N)\). While this is just a heuristic, our experiments find it works well, often even better than our theoretically justified approach with default parameters.