A robust modification of the K-means method for clustering under interval-valued data
A robust modification of the K-means method for solving a clustering problem under interval-valued training data is proposed. The existing methods of clustering are mainly based on the replacement of interval-valued data with their point-valued representations, for example, with centers of intervals, or they use some special distance metrics between hyper-rectangles (multi-dimensional intervals) or between points and hyper-rectangles, for example, the Hausdorff distance. In contrast to the existing methods, the first idea underlying the proposed algorithm is transferring of interval uncertainty to sets of example weights and to an extension of the training set. At that, new elements of the training set, being points approximating intervals, have imprecise weights assigned such that they do not change an initial structure of training data and do not introduce additional unjustified information. The second idea is to use the minimax strategy for providing the robustness. It is shown in the paper that the new algorithm differs from the standard K-means algorithm by a step of solving a simple linear programming problem. It is also shown in the paper that in the simplest case when all elements of the training set have identical weights, the proposed algorithm is reduced to the choice of a point inside hyper-rectangles, which are located on the largest distance from the center of a cluster. The obtained results can be considered also in the framework of Dempster-Shafer theory. The proposed algorithm is useful when the intervals of data are rather large and when the training set is small.