Application of smart-tables and estimates of objective functions to reduce the dimension and accelerate the solution of the constrained clustering problems

Abstract

The article presents an integrated approach to the accurate solution of Constrained Clustering problems, that is clustering problems involving analysis, in additional to distance matrix, of background knowledge about necessity/infeasibility of the occurrence of some objects into a particular cluster. The approach is implemented in the framework of Constraint Programming Paradigm, focused on the constructions of systematic search procedures (traversal of the search tree) for solving complex combinatorial problems. Moreover, all the initial information about the problem is expressed with constraints, that is, qualitative and quantitative relations. A significant complexity lies in the fact that in today’s environments and libraries of constraint programming the processing of qualitative constraints, which in particular, are the rules for assigning objects to one or different clusters, is not done efficiently enough. Thus, it seems relevant to develop ways to accelerate the processing of such constraints. The article proposes to represent and process the qualitative constraints in the form of table constraints of a new type, namely smart-tables of D-type. For the smart-tables of D-type high efficient constraint inference procedures have been developed that perform early pruning unpromising branches of the search tree. Another area of work, which is actively developing in this research, is related with reducing the number of constraints used to represent the problem and simplifying their form. It is proposed to generate the constraints only for some pairs of objects based on an interval estimate for the optimal value of the clustering criterion. To obtain this estimate, the hierarchical clustering method previously proposed by the authors is used, which allows you to analyze the constraints for the combinations of pairs of objects within a cluster. The proposed approach allows you to find all the partitions variants that provide global optimum of objective function for the considered Constrained Clustering problems of high dimension. The developed approach is illustrated by example of the problem of identifying zones of rock mass with different seismic activity.