Combinatorial machine learning. A rough set approach. (Q545918)

This book starts with a discussion of basic ideas such as decision tables, decision rule systems, and decision trees. The text is divided into two parts: tools and applications. In the first chapter of the part on tools, the authors study tests (subsets of the attribute set \(A\) such that they hold the same information about the classes as the set \(A\)), decision rule systems, and decision trees. In the next chapter bounds on complexity of tests, decision rules and trees are given. Then some algorithms for computation of tests, decision rules and decision trees are cited. In the next chapter, decision tables with many-valued decisions (also known as non-deterministic tables) are discussed. In the last chapter of this part of the book, the authors discuss approximate tests, rules and trees, which should be used when the exact tests, rules and trees are too complicated. In the part dealing with applications, the authors present a study of classifiers based on decision rules using finite or infinite sets of attributes. The chapter about local and global approaches to rules and trees starts from the definition of the information system: a triple \(U = (A, B, F)\), where \(A\) and \(B\) are nonempty sets, \(B\) has at least two elements, and \(F\) is a set of functions from \(A\) to \(B\), is called an information system. In the local approach attributes listed in a problem description may be used in rules or trees, in the global approach any attribute from \(F\) may be used. A special case of information systems, called linear and quasilinear, is considered in the next chapter. In the last chapter of this part, recognition of words and diagnosis of constant faults in circuits are discussed.