Incomplete Information: Rough Set Analysis

In this chapter the major principles and the methodology of the rough set—style analysis of data are presented and discussed. A survey of various formalisms that provide the tools of this analysis is given. We discuss the aspects of incompleteness of information that can be handled in the presented formalisms. The formalisms are related to the methods and/or structures presented in this volume, in each case we point out a relevant link and we give the reference to the respective chapter.

We discuss two applications of logic to the problem of object classification. The first is related to an application of multi-modal logics to the automatic feature extraction. The second is concerned with inductive reasoning for discovering an optimal feature set with respect to the precision of classification and for improving the performance of decision algorithms. We also present an exemplary system for recognizing handwritten digits based on Boolean reasoning, rough set methods and feature discovery by applying multi-modal logic.

The paper studies multi-concept learning from inconsistent examples. The main assumption is that knowledge is acquired in the form of production rules, while induced rules represent minimal discriminant description. The paper presents an approach to the elimination of irrelevant attributes in the concept description, or, to be more specific, a new method for determining coverings, the minimal sets of relevant attributes. This method is based on a new tool created within rough set theory. In the presented approach to learning rules from examples, methods of rough set theory are used twice: first, in defining lower boundaries, and then, to deal with inconsistencies. Inconsistent representation of examples is a kind of uncertainty in input data, resulting from gathering information from inconsistent experts or lack of sufficient number of attributes to describe input data.

This report presents results of experiments on two algorithms of machine learning: LEM1 and LEM2. Both algorithms belong to the LEM (Learning from Examples Module) family developed at the Department of Computer Science, University of Kansas.

For LEM1, two different approaches to test attribute dependence were compared: partition and lower boundaries. The two different versions of the algorithm were developed and their run times on a set of test files were compared.

For LEM2 a number of experiments were made to find the best search method of the description space. Some heuristics used within the algorithm to pick the “best” attribute-value pairs for the generation of rules were selected and tested. The quality of different methods has been compared on the basis of the total number of conditions, the total number of rules, and the average length of rules.

A survey of results is presented on relationships between the algebraic systems derived from the approximation spaces induced by information systems and various classes of algebras of relations. Rough relation algebras are presented and it is shown that they form a discriminator variety. A characterisation of the class of representable rough relation algebras is given. The family of closure operators derived from an approximation space is abstractly characterised as certain type of Boolean algebra with operators. A representation theorem is given which says that every such an algebra is isomorphic with a similar algebra that is derived from an information system.

A general model is introduced and investigated of a great variety of finite structures studied in computer science. The model is referred to as dependence space. The main feature of the model is that it enables us to deal with the indiscernibility-type incompleteness of information that a modelled structure might be burdened with. The model provides a general framework for expressing the concept of independence of a set and the concept of dependency between sets with respect to a dependence space. It is shown that these concepts lay the foundation on which many applied structures rest. The theory of dependence spaces is developed aimed at providing tools for studying the problems relevant for the modelled structures.

The dependence space models are applied to representation and investigation of domains with incomplete information. It is shown that various models of these domains can be uniformly. treated within the framework of the theory of dependence spaces. In particular, dependence spaces are constructed for contexts ([Wi1]), information systems ([Pa7]), decision tables. The problems are studied that arise in connection with discovery of knowledge from indiscernibility-type incomplete information. The algorithms are given for realisation of various relevant tasks. Among others, an algorithm for finding reducts of sets of attributes in an information system and an algorithm for reduction of a set of conditions in a decision table are presented.

Various classes of data constraints in information systems are modelled by means of indiscernibility relations induced by sets of attributes. A relational logic is presented that enables us to express these constraints. A proof system for the logic is given and its completeness is proved with respect to a class of algebras of relations generated by indiscernibility relations. Some other classes of models for the logic are defined that correspond to typical kinds of constraints in information systems. Decidability of the validity problem with respect to these classes of models is discussed and some classes of formulas with the decidable validity problem are given.

A variety of forms of dependencies in empirical data is studied. It is shown how the existing models can be extended in order to capture the revelant features of data. In particular, scaling of data in the context-style models is investigated and an algebraic framework is proposed for processing scales. A deduction system for providing data dependencies in scaled context is given.

In this paper we explain the role of indiscernibility in the analysis of vagueness of concepts and in concept learning. We develop deduction methods that enable us making inferences from incomplete information in the presence of indiscernibility.

In this article the relationship between the identity relation and the indiscernibility relation is discussed. A generalization of the standard definition of the indiscernibility relation considered in the theory of rough sets is given, and some basic theorems about it are formulated and proved.

We present two theories that emerge in connection with rough set-based methods for classifying dynamic populations of objects. The first theory, referred to as rough mereology aims at the analysis of complex objects in terms of properties of their parts. The second theory — analytical morphology of rough sets is a generalization of mathematical morphology obtained by imposing a geometrical structure on the attributes in information systems.

There are presently two kinds of fuzzy set-based theories of approximate reasoning: possibilistic logic, and similarity-based logic. This paper is devoted to a comparison between the two lines of research, both at the formal and interpretation level. Similarity calculus, initiated by Ruspini, exploits the idea that interpretations of a formal classical propositional language are more or less close to each other. This is done by equipping this set of interpretations with a metric-like structure, under the form of a fuzzy similarity relation. Then “p approximately implies q” means that p is “not far” from implying q, where “not far” is evaluated by the amount of stretching applied to the models of q so as to make the conditional statement true. On the contrary, in possibilistic logic, the set of interpretations is equipped with a preference relation encoded as a possibility distribution. This possibility distribution expresses that some worlds are more plausible than others. Then “p approximately implies q” means that q is true in the most plausible worlds where p is true. Similarity-based reasoning is also compared with rough set theory, and it is pointed out that while the two approaches are strongly connected at the formal level, the former is devoted to casting interpolation in a logical setting while the latter focuses on incomplete information systems where objects cannot be distinguished.

A similarity relation is a reflexive and symmetric, but in general not transitive binary relation between objects. Similarity can be regarded as a relative notion parametrised by the set of classification attributes used as a basis for determining similarity or dissimilairty of objects. In the paper we present a polymodal formal language for reasoning about such a relative notion of similarity. For each subset of a given set of attributes, we have two modalities, corresponding semantically to so-called upper and lower approximations of a set of objects with respect to that set of attributes; intuitively, the latter approximations could be described as the interior and completion of a set of objects with respect to the similarity relation generated by the considered set of attributes, respectively. Formulae of the language evaluate to sets of objects, and a formula is said to be true if it evaluates to the whole universe of the model. The language is given a sound and complete deduction system in Rasiowa-Sikorski style: it consists of fundamental sequences of formulae which represent axioms of the system, and decomposition rules for sequences of formulae which represent inference rules.

In the paper we study two types of information systems: ontological and logical. Systems of ontological type are Property systems and Attribute systems, where the information is represented in terms of the ontological concepts of object, property and attribute. Systems of logical type are Consequence systems and Bi-consequence systems where the information is represented by a collection of sentences, equipped with some inference mechanism. We prove that each Consequence system can be embedded into a certain Property system. The similar results hold for Bi-consequence systems and Attribute systems. These representation theorems are used to give an abstract characterization (by means of a finite set of first-order sentences) of some information relations in Property systems and Attribute systems, including various kinds of similarity relations. Several modal logics with modalities corresponding to some collections of information relations are introduced and their “query meaning” is discussed. One of the main results of the paper are the completeness theorems for the introduced modal logics with respect to their standard semantics.

This paper presents a systematic study of the logics based on Kripke models with relative accessibility relations as well as a general method for proving their completeness. The Kripke models with relative accessibility relations come out in the context of the analysis of indiscernability in the information systems.

This article surveys syntactic and semantic formalizations of various notions that have arisen in the course of development of rough set theory. To be more specific, the first order theories proposed so far in this connection have been brought into discussion. In the process, comparisons of these systems are made. Some new ideas in this regard have been offered at the end.

The main aim of this paper is to present a survey of results on the logic with rough quantifier. Besides, a classification of simplicity of formulas of the logic with rough quantifier is defined and a criterion for placing a formula on the exact simplicity level is given.