# Agglomerative Clustering with Threshold Optimization via Extreme Value Theory
## 5 Experimental Results
### Timing  
As shown in Table 6, PEACH(\(\tau_{r}\)) is faster than all tested algorithms for large face clustering problems of IJB-B, with the exception of FINCH which is the fastest by far. While both PEACH and FINCH have overall time complexity of \(O(N\log N)\), PEACH has a larger constant because of a greater number of rounds of merging and its need to estimate the scaling \(\omega\) and threshold.  
For example, consider IJB-B 1024, the rough timing is FINCH\(\sim\)8 s, PEACH\(\sim\)79 s, AHC\(\sim\)100 s, BIRCH\(\sim\)102 s, K-Means\(\sim\)877 s, OPTICS\(\sim\)1255 s, and Spectral clustering was stopped after running for more than a day. While FINCH is faster, PEACH is more accurate  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multicolumn{6}{c}{**Number of Classes**} \\ \cline{2-7}  & **32** & **64** & **128** & **256** & **512** & **1024** & **1845** \\ \hline Agglomerative & **0.04** & 0.13 & 0.91 & 4.18 & 18.67 & 99.51 & 462.51 \\ \hline BIRCH & 0.11 & 0.31 & 1.51 & 5.46 & 21.31 & 102.61 & 444.20 \\ \hline K-Means & 0.84 & 2.82 & 12.43 & 57.19 & 258.74 & 877.89 & 3784.34 \\ \hline Spectral Clustering & 2.96 & 9.68 & 69.43 & 591.54 & 3238.38 & — & — \\ \hline OPTICS & 1.58 & 4.61 & 26.23 & 113.83 & 411.38 & 1254.61 & — \\ \hline Affinity Propagation & 2.71 & 11.33 & 84.59 & 265.01 & — & — & — \\ \hline FINCH & 0.06 & **0.08** & **0.27** & **0.71** & **2.16** & **7.78** & **25.71** \\ \hline PEACH & 2.32 & 3.59 & 8.84 & 18.56 & 36.13 & 79.35 & 176.92 \\ \hline \hline \end{tabular}
\end{table}
Table 6: _Running Time of IJB-B Protocols._ Running time in seconds for various clustering algorithms is provided for all IJB-B protocols. Missing values (—) indicate that results could not be obtained within one day. We mark the second-fastest and **fastest algorithms**.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multicolumn{2}{c}{**Deeper Clustering**} & \multicolumn{2}{c}{**Deep Clustering**} \\  & **NMI** & **\% Gain** & **NMI** & **\% Gain** \\ \hline K-Means & 0.447 & – & 0.446 & — \\ AHC [32] & 0.392 & \(-\)12.3\% & 0.421 & \(-\)5.8\% \\ FINCH(\(GT\)) [4] & 0.346 & \(-\)22.6\% & 0.371 & \(-\)17.0\% \\ PEACH(\(\tau_{r}\)) & **0.756** & **69.1\%** & **0.604** & **35.2\%** \\ \hline \hline \end{tabular}
\end{table}
Table 4: _PEACH Improves Unsupervised Training._ We show the NMI for various clustering algorithms used during the training process of deep clustering, and gains over [10,11], respectively. We mark the **best results**.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multicolumn{2}{c}{**MNIST/Deep Clustering Epochs**} \\  & **Epoch 100** & **Epoch 125** & **Epoch 150** & **Epoch 200** \\ \hline K-Means & 94.44\% & 93.09\% & 92.11\% & 90.56\% \\ FINCH(_Best_) [4] & 96.63\% & 96.12\% & 96.39\% & 96.07\% \\ PEACH(\(\tau_{r}\)) & **97.72\%** & **96.23\%** & **96.47\%** & **96.46\%** \\ \hline \hline \end{tabular}
\end{table}
Table 5: _Top-1 Accuracy of Linear Classifier of Deep Clustering._ We employ LeNet++ for deep clustering of MNIST, and we report the top-1 accuracy of a converged linear classifier after feature extraction. PEACH(\(\tau_{r}\)) achieves higher accuracy than K-Means and FINCH at each of the deep clustering epochs examined.  
and does not require user selection among the final partitions. For large problems, PEACH is faster than standard Agglomerative clustering since it stops merging sooner.