Solution of clusterization problem by graph optimization methods

Abstract

The rapid growth in the volume of processed information that takes place nowadays determines the urgency of the development of methods for reducing the dimension of computational problems. One of the approaches to reducing the dimensionality of data is their clustering, i.e., uniting into maximally homogeneous groups. At the same time, it is desirable that representatives of different clusters should be as much as possible unlike each other. Along with the dimension reduction, clustering procedures have an independent value. For example, we know the market segmentation problem in economics, the feature typologization problem in sociology, faces diagnostics in geology, etc. Despite the large number of known clusterization methods, the development and study of new ones remain relevant. The reason is that there is no algorithm that would surpass all the rest by all criteria (speed, insensitivity to clusters’ size and shape, number of input parameters, etc.). In this paper, we propose a clustering algorithm based on the notions of the graph theory (namely, the maximum flow (the minimum cut) theorem) and compare the results obtained by it and by four other algorithms that belong to various classes of clusterization techniques.

Keywords

• clustering
• maximal flow
• minimal cut
• ford–fulkerson theorem
• labeling method
• k-means
• hierarchical clusterization
• ward’s procedure
• dbscan method
• maxflow algorithm