Application of table constraint satisfaction methods for modeling reasoning of JSM-type

Abstract

The article continues the series of works that deal with the topic of data mining using methods of inference on table constraints. Previously, the author’s methods of clustering, discovering patterns of the required type, and mining association rules were presented. The developed methods relate to the methods of interpreted artificial intelligence. The disadvantages of most existing data mining methods are primarily related to the difficulties of flexible accounting and analyzing the knowledge of domain experts, user constraints. Usually, a rather consuming modification of the basic data mining methods is required to account for each type of such constraints. The article develops an approach to the implementation of data mining methods based on the Constraint Programming Paradigm, which is free from the mentioned disadvantages and allows for sufficient flexibility to organize accounting and analysis of additional conditions of the data mining problem without fundamental changing the scheme of its solving. The originality of the author’s approach lies in the fact that to represent the training sample, it is proposed to use a special type of table constraints — compressed tables of the D-type, and the data mining problems are proposed to be solved as problems of satisfying table constraints using the original method of branching the search tree and the author’s rules for reducing compressed tables. In the presented work, using the example of solving the binary classification problem, the possibilities of applying the author’s approach to modeling reasoning of JSM-type are considered for the first time. The article considers the case when the properties of objects are atomic and have no internal structure. The problem of generating JSM hypotheses is proposed to be reduced to frequent closed pattern discovery, and each of the patterns should not be included as a fragment in a set of counterexamples. Within the framework of the approach proposed in the article, adding additional types of constraints to the problem not only does not reduce the performance of their solution methods, but also contributes to a deeper reduction of the search space by using specialized logical inference methods for each of the constraint types.