Sub-one Quasi-norm-based k-means Clustering Algorithm and Analyses

Abstract In this paper, we investigate the impact of distance metrics on the performance of the k-means algorithm, which is one of the most popular clustering schemes. Our focus is on the sub-one ℓp quasi-norm-based distance metric, which has recently gained attention due to its ability to better leverage similarities between data-items while avoiding overemphasizing the dissimilarities. Through an illustrative example, we demonstrate the superiority of the proposed distance metric over commonly used metrics in revealing natural groupings in data. To validate the effectiveness of the proposed sub-one ℓp distance based k-means method, we conduct experiments on synthetic datasets as well as real-life datasets from the UCI machine learning repository both in their original form and with additional noise introduced. Overall, our results demonstrate the effectiveness of the ℓp quasi-norm-based distance metric in improving the performance of the k-means algorithm in various situations, particularly in noisy data.