Extended Quality (eQual): Radial Threshold Clustering Based on n-ary Similarity

Area of Science:

• Computational science
• Data science
• Algorithm development

Background:

• Radial Threshold Clustering (RTC) is an O(N^2) partitioning algorithm for grouping similar frames.
• RTC suffers from inefficiency with large datasets and order-dependent results during ties.
• Existing clustering methods may lack scalability and consistency.

Purpose of the Study:

• To transform the O(N^2) Radial Threshold Clustering (RTC) algorithm into an efficient O(N) algorithm named Extended Quality Clustering (eQual).
• To enhance clustering by improving speed and ensuring order-invariant results.
• To produce more compact and distinct clusters.

Main Methods:

• Implemented k-means++ for faster seed selection in frame clustering.
• Introduced extended similarity indices to select the densest and most compact cluster, ensuring order invariance.
• Developed Extended Quality Clustering (eQual) with a linear time complexity.

Main Results:

• Achieved O(N) time complexity, significantly improving efficiency over RTC's O(N^2).
• Ensured clustering results are invariant to the order of input frames.
• Demonstrated the generation of more compact and well-separated clusters.

Conclusions:

• Extended Quality Clustering (eQual) provides a scalable and consistent alternative to Radial Threshold Clustering (RTC).
• The enhanced algorithm addresses key limitations of RTC, offering improved performance and reliability.
• eQual is suitable for large-scale frame clustering tasks requiring efficiency and robust results.