A variance-guided resampling framework for better K-medoids clustering

One of the limitations of the k-medoids clustering algorithm is its susceptibility to local optimization and the potential for identical or similar objects to be assigned to different initial clusters. This study proposes ResConeK method, a modification of the block-based k-medoids algorithm that integrates a resampling strategy into the selection of representative object blocks formed according to similar variances. The method is validated using six external clustering criteria-Rand Index, Adjusted Rand Index, Hubert Similarity Statistic, Jaccard Similarity, Fowlkes-Mallows Index, and Rogers-Tanimoto Index-together with an internal criterion based on cluster homogeneity. Performance is benchmarked against four clustering methods: fast k-medoids, block-based k-medoids, Ward's method, and hierarchical clustering with complete linkage. Experiments show that the average validity score of ResConeK is comparable to all benchmark methods on three and four clusters, and significantly higher than block-based k-medoid on seven clusters and has comparable homogeneity for real data. The proposed algorithm: • Applicable to all data types, with greater benefits for datasets containing many identical objects or objects exhibiting similar distance variance. • Introduces a resampling strategy on representative object blocks within the k-medoids framework. • Reduces the risk of local optima and improves cluster homogeneity and stability.