Extended Quality (eQual): Radial threshold clustering based on n-ary similarity

Abstract

We are transforming Radial Threshold Clustering (RTC), an O(N 2) algorithm, into Extended Quality Clustering, an O(N) algorithm with several novel features. Daura et als RTC algorithm is a partitioning clustering algorithm that groups similar frames together based on their similarity to the seed configuration. Two current issues with RTC is that it scales as O(N 2) making it inefficient at high frame counts, and the clustering results are dependent on the order of the input frames. To address the first issue, we have increased the speed of the seed selection by using k-means++ to select the seeds of the available frames. To address the second issue and make the results invariant with respect to frame ordering, whenever there is a tie in the most populated cluster, the densest and most compact cluster is chosen using the extended similarity indices. The new algorithm is able to cluster in linear time and produce more compact and separate clusters.