Search

The size of information gathered from real world applications today is staggering. To make matters worse, this information may also be incomplete, due to errors in measurement or lack of discipline. The two phenomena give rise to a big incomplete information system (IIS). The processing of a big IIS is difficult because of its two problems, big size and incompleteness, and the present work introduces an approach that addresses both. Specifically, we develop an efficient rough set theoretic (RST) algorithm to compute the approximation space of the IIS, which addresses the incompleteness problem. Then we distribute the computational chores of the algorithm using the MapReduce framework, which addresses the size problem. The approach is explained fully, and a detailed illustrative example is provided. For validation and performance analysis, the approach has been implemented and tested on four publicly-accessible big IISs for many metrics including sizeup, scaleup, and speedup. The experimental results attest to its validity, accuracy and efficiency. A comparison test with similar approaches shows that it has superior performance.

Considering data from different perspectives (views or granulations) is very common in several applications nowadays. Unfortunately, Rough Sets lack of effective tools for handling multiple granulation in mixed and incomplete information systems. This paper introduces a novel approach for dealing with such information systems: The Parameterized Granulation. The demonstration of some of the properties of such granulation approach, as well as the theoretical and experimental analysis carried out, show the capabilities of this novel granulation, and result in great utility in the study of mixed and incomplete information systems, not only in the context of a single granulation, but in the context of multiple granulations.

We propose the notion of probabilistic information system (PIS) to capture situations where information regarding attributes of objects are not precise, but given in terms of probability. Notions of indistinguishability relations and corresponding approximation operators based on PISs are proposed and studied. It is shown that the deterministic information systems (DISs), incomplete information systems (IISs) and non-deterministic information systems (NISs) are all special instances of PISs. Moreover, the approximation operators defined on DIS (relative to indiscernibility), IISs and NISs (relative to similarity relations) are all originated from a single approximation operator defined on PISs. Further, a logic LPIS for PISs is proposed that can be used to reason about the proposed approximation operators. A sound and complete deductive system for the logic is given. Decidability of the logic is also proved.

To extract and express the knowledge hidden in information systems, discernibility matrix and its extensions were introduced and applied successfully in many real life applications. Binary discernibility matrix, as a representative approach, has many interesting superior properties and has been rapidly developed to find intuitive and easy to understand knowledge. However, at present, the binary discernibility matrix is mainly adopted in the complete information system. It is a challenging topic how to achieve the attribute reduction by using binary discernibility matrix in incomplete information system. A form of generalized binary discernibility matrix is further developed for a number of representative extended rough set models that deal with incomplete information systems. Some useful properties and criteria are introduced for judging the attribute core and attribute relative reduction. Thereafter, a new algorithm is formulated which supports attribute core and attribute relative reduction based on the generalized binary discernibility matrix. This algorithm is not only suitable for consistent information systems but also inconsistent information systems. The feasibility of the proposed methods was demonstrated by worked examples and experimental analysis.

Multigranulation rough sets are desirable features in the field of rough set, where this concept is approximated by multiple granular structures. In this study, we employ belief and plausibility functions from evidence theory to characterize the set approximations and attribute reductions in multigranulation rough set theory. First, we show that in an incomplete information system, the pessimistic multigranulation approximations can be measured by belief and plausibility functions, whereas the optimistic multigranulation approximations do not possess this characteristic in general. We also give a sufficient and necessary condition for the numerical measurement of optimistic multigranulation approximations by belief and plausibility functions. Second, in an incomplete decision system, the pessimistic multigranulation approximations are also measured by belief and plausibility functions. In the end, an attribute reduction algorithm for multigranulation rough sets is proposed based on evidence theory, and its efficiency is examined by an example. Thus, belief and plausibility functions can be employed to numerically characterize the attribute reductions and to construct an attribute reduction algorithm for multigranulation rough sets.

In this paper, we consider some topological properties of generalized rough sets induced by binary relations and show that1.Any serial binary relation can induce a topology. 2.Let R be a binary relation on a universe U. t(R) and e(R) denote the transitive closure and the equivalence closure of R, respectively. If R is a reflexive relation on U, then R and t(R) induce the same topology, i.e. T(R)=T(t(R)). The interior and closure operators of the topology T(R) induced by R are the lower and upper approximation operators t(R) and t(R)@?, respectively. Moreover, R(T(R))=t(R), where R(T(R)) is the relation induced by the topology T(R). 3.When R is a reflexive and symmetric relation, R and e(R) induce the same topology, i.e. T(R)=T(e(R)). The interior and closure operators of the topology T(R) induced by R are the lower and upper approximation operators e(R) and e(R)@?, respectively. Moreover, R(T(R))=e(R). 4.Based on the above conclusions, the notion of topological reduction of incomplete information systems is proposed, and characterizations of reduction of consistent incomplete decision tables are obtained.

Zou et al. (2008) [21] presented weighted-average of all possible choice values approach of soft sets under incomplete information system in decision making. However, the approach is hard to understand and involves a great amount of computation. In order to simplify the approach, we present the simplified probability to directly instead of the incomplete information, and demonstrate the equivalence between the weighted-average of all possible choice values approach and the simplified probability approach. Finally, comparison results show that the proposed approach involves relatively less computation and is easier to implement and understand as compared with the weighted-average of all possible choice values approach.

There are mainly two methodologies dealing with uncertainty measurement issue in rough set theory: pure rough set approach and information theory approach. Pure rough set approach is based on the concepts of accuracy, roughness and approximation accuracy proposed by Pawlak. Information theory approach is based on Shannon's entropy or its variants. Several authors have extended the information theory approach into incomplete information systems. However, there are few studies on extending the pure rough set approach to incomplete information systems. This paper focuses on constructing uncertainty measures in incomplete information systems by pure rough set approach. Three types of definitions of lower and upper approximations and corresponding uncertainty measurement concepts including accuracy, roughness and approximation accuracy are investigated. Theoretical analysis indicates that two of the three types can be used to evaluate the uncertainty in incomplete information systems. Experiments on incomplete real-life data sets have been conducted to test the two selected types (the first type and the third type) of uncertainty measures. Results show that the two types of uncertainty measures are effective.

Neighborhood system formalized the ancient intuition, infinitesimals, which led to the invention of calculus, topology and non-standard analysis. In this paper, the neighborhood system is researched from the view point of knowledge engineering and then each neighborhood is considered as a basic unit with knowledge. By using these knowledge in neighborhood system, the rough approximations and the corresponding properties are discussed. It is shown that in the incomplete information system, the smaller upper approximations can be obtained by neighborhood system based rough sets than by the methods in [Y. Leung, D.Y. Li, Maximal consistent block technique for rule acquisition in incomplete information systems, Information Sciences 115 (2003) 85-106] and [Y. Leung, W.Z. Wu, W.X. Zhang, Knowledge acquisition in incomplete information systems: a rough set approach, European Journal of Operational Research 168 (2006) 164-180]. Furthermore, a new knowledge operation is discussed in the neighborhood system, from which more knowledge can be derived from the initial neighborhood system. By such operations, the regions of lower and upper approximations are further expanded and narrowed, respectively. Some numerical examples are employed to substantiate the conceptual arguments.

In the recent years, the method to expand Pawlak's rough set model in different kinds of information systems has become a hot topic. This article presents explorative research focusing on the transition from the traditional information system to a complex system—the incomplete information system. In such information system, “do not care” and lost unknown attribute values coexist. With a further investigation of Grzymala-Busse's characteristic relation in the incomplete information system, two unreasonable situations in the analysis of the classified problem are presented. To conduct sound classification in the incomplete information system, a new characteristic relation is proposed and by use of this new characteristic relation, the complete covering on the universe is formed. Based on the maximal complete compatible classes in the complete covering, two notions of the knowledge representation system are presented and some important properties associated with these knowledge representation systems are discussed. For further illustration, an example is analyzed. The research is meaningful both in theory and in applications for the extension of the rough set theory in incomplete information systems.

Set-valued information systems are generalized models of single-valued information systems. Incomplete information systems can be viewed as disjunctively interpreted set-valued information systems. Since some objects in set-valued information systems may have more than one value for an attribute, so we define tolerance relation and use the maximal tolerance classes to classify the universe of discourse. In order to derive optimal decision rules from set-valued decision information systems, we propose the concept of relative reduct of maximal tolerance classes, and define a kind of discernibility function to compute the relative reduct by Boolean reasoning techniques. Finally, we define three kinds of relative reducts for set-valued information systems and used them to evaluate the significance of attributes.

This paper deals with knowledge discovering in incomplete information systems (IIS).By an IIS, we mean a system with unknown data or partly-known data. This kind of system can be regarded as a set-valued system. The selections of an IIS are considered. The relationships between the reducts in the source system and in its selections are investigated. We also present the concept of maximum distribution reducts and optimal selections, from which we provide an approach to acquire decision rules from incomplete decision tables (IDT).

In this paper, the concept of a maximal consistent block is applied to formulate a new approximation to an object set in incomplete information systems with higher level of accuracy. Similar to the method in [Inform. Sci. 112 (1998) 39, 113 (1999) 271], the proposed rough-set-based rule acquisition method does not require change in the size of the original incomplete system. It, however, has the additional advantage of using a set of simpler discernibility functions of an incomplete system. This means that it can provide a more efficient computation for knowledge acquisition, especially in large incomplete systems.

In this paper we propose a method of extracting rules in Incomplete Information System based on an irregular decision table. Need not to make estimation of missing attribute value, we get the rule set contains no missing attribute value. The experiment justify, the accuracy of obtained rule set is almost same with the highest accuracy among those of the estimating missing attribute value methods.

A new method of computing all optimal certain rules from an incomplete information system is presented and proved. The method does not require changing the size of the original incomplete system. Additionally, several existing rough set methods of computing decision rules from incomplete information systems are analyzed and compared. We show which of these methods are capable of generating all optimal certain rules or a class of optimal certain rules and which methods may lead to generation of false rules.