Sub-One Quasi-Norm-Based k-Means Clustering Algorithm and Analyses
Qi An, Shan Jiang · Neural Processing Letters · 2024
Abstract Recognizing the pivotal role of choosing an appropriate distance metric in designing the clustering algorithm, our focus is on innovating the k -means method by redefining the distance metric in its distortion. In this study, we introduce a novel k -means clustering algorithm utilizing a distance metric derived from the $$\ell _p$$ ℓ p quasi-norm with $$p\in (0,1)$$ p ∈ ( 0 , 1 ) . Through an illustrative example, we showcase the advantageous properties of the proposed distance metric compared to commonly used alternatives for revealing natural groupings in data. Subsequently, we present a novel k -means type heuristic by integrating this sub-one quasi-norm-based distance, offer a step-by-step iterative relocation scheme, and prove the convergence to the Kuhn-Tucker point. Finally, we empirically validate the effectiveness of our clustering method through experiments on synthetic and real-life datasets, both in their original form and with additional noise introduced. We also investigate the performance of the proposed method as a subroutine in a deep learning clustering algorithm. Our results demonstrate the efficacy of the proposed k -means algorithm in capturing distinctive patterns exhibited by certain data types.