Distance–Constrained Data Clustering by Combined k–means Algorithms and Opinion Dynamics Filters

Abstract

Data clustering algorithms represent mechanisms for partitioning huge arrays of multidimensional data into groups with small in–group and large out–group distances. Most of the existing algorithms fail when a lower bound for the distance among cluster centroids is specified, while this type of constraint can be of help in obtaining a better clustering. Traditional approaches require that the desired number of clusters are specified a priori, which requires either a subjective decision or global meta–information knowledge that is not easily obtainable. In this paper, an extension of the standard data clustering problem is addressed, including additional constraints on the cluster centroid distances. Based on the well–known Hegelsmann–Krause opinion dynamics model, an algorithm that is capable to find admissible solutions is given. A key feature of the algorithm is the ability to partition the original set of data into a suitable number of clusters, without the necessity to specify such a number in advance. In the proposed approach, instead, the maximum distance among any pair of cluster centroids is specified.