In computer science, a rough set, first described by Polish computer scientist Zdzisław I. Pawlak, is a formal approximation of a crisp set (i.e., conventional set) in terms of a pair of sets which give the lower and the upper approximation of the original set. In the standard version of rough set theory described in Pawlak (1991), the lower- and upper-approximation sets are crisp sets, but in other variations, the approximating sets may be fuzzy sets.
Definitions The following section contains an overview of the basic framework of rough set theory, as originally proposed by Zdzisław I. Pawlak, along with some of the key definitions. More formal properties and boundaries of rough sets can be found in and cited references. The initial and basic theory of rough sets is sometimes referred to as "Pawlak Rough Sets" or "classical rough sets", as a means to distinguish it from more recent extensions and generalizations.
Information system framework Let be an information system (attribute–value system), where is a non-empty, finite set of objects (the universe) and is a non-empty, finite set of attributes such that for every . is the set of values that attribute may take. The information table assigns a value from to each attribute and object in the universe .
With any there is an associated equivalence relation :
The relation is called a -indiscernibility relation. The partition of is a family of all equivalence classes of and is denoted by (or ).
If , then and are indiscernible (or indistinguishable) by attributes from .
The equivalence classes of the -indiscernibility relation are denoted .
Example: equivalence-class structure For example, consider the following information table:
{| class="wikitable" style="text-align:center; width:30%" border="1" |+ Sample Information System ! Object !! !! !! !! !! |- ! | 1 || 2 || 0 || 1 || 1 |- ! | 1 || 2 || 0 || 1 || 1 |- ! | 2 || 0 || 0 || 1 || 0 |- ! | 0 || 0 || 1 || 2 || 1 |- ! | 2 || 1 || 0 || 2 || 1 |- ! | 0 || 0 || 1 || 2 || 2 |- ! | 2 || 0 || 0 || 1 || 0 |- ! | 0 || 1 || 2 || 2 || 1 |- ! | 2 || 1 || 0 || 2 || 2 |- ! | 2 || 0 || 0 || 1 || 0
When the full set of attributes is considered, we see that we have the following seven equivalence classes:
Thus, the two objects within the first equivalence class, , cannot be distinguished from each other based on the available attributes, and the three objects within the second equivalence class, , cannot be distinguished from one another based on the available attributes. The remaining five objects are each discernible from all other objects.
It is apparent that different attribute subset selections will in general lead to different indiscernibility classes. For example, if attribute alone is selected, we obtain the following, much coarser, equivalence-class structure:
Definition of a rough set Let be a target set that we wish to represent using attribute subset ; that is, we are told that an arbitrary set of objects comprises a single class, and we wish to express this class (i.e., this subset) using the equivalence classes induced by attribute subset . In general, cannot be expressed exactly, because the set may include and exclude objects which are indistinguishable on the basis of attributes .
For example, consider the target set , and let attribute subset , the full available set of features. The set cannot be expressed exactly, because in , objects are indiscernible. Thus, there is no way to represent any set which includes but excludes objects and .
However, the target set can be approximated using only the information contained within by constructing the -lower and -upper approximations of :
Lower approximation and positive region The -lower approximation, or positive region, is the union of all equivalence classes in which are contained by (i.e., are subsets of) the target set – in the example, , the union of the two equivalence classes in which are contained in the target set. The lower approximation is the complete set of objects in that can be positively (i.e., unambiguously) classified as belonging to target set .
Upper approximation and negative region The -upper approximation is the union of all equivalence classes in which have non-empty intersection with the target set – in the example, , the union of the three equivalence classes in that have non-empty intersection with the target set. The upper approximation is the complete set of objects that in that cannot be positively (i.e., unambiguously) classified as belonging to the complement () of the target set . In other words, the upper approximation is the complete set of objects that are possibly members of the target set .
The set therefore represents the negative region, containing the set of objects that can be definitely ruled out as members of the target set.
Boundary region The boundary region, given by set difference , consists of those objects that can neither be ruled in nor ruled out as members of the target set .
In summary, the lower approximation of a target set is a conservative approximation consisting of only those objects which can positively be identified as members of the set. (These objects have no indiscernible "clones" which are excluded by the target set.) The upper approximation is a liberal approximation which includes all objects that might be members of target set. (Some objects in the upper approximation may not be members of the target set.) From the perspective of , the lower approximation contains objects that are members of the target set with certainty (probability = 1), while the upper approximation contains objects that are members of the target set with non-zero probability (probability > 0).
The rough set The tuple composed of the lower and upper approximation is called a rough set; thus, a rough set is composed of two crisp sets, one representing a lower boundary of the target set , and the other representing an upper boundary of the target set .
The accuracy of the rough-set representation of the set can be given by the following:
That is, the accuracy of the rough set representation of , , , is the ratio of the number of objects which can positively be placed in to the number of objects that can possibly be placed in – this provides a measure of how closely the rough set is approximating the target set. Clearly, when the upper and lower approximations are equal (i.e., boundary region empty), then , and the approximation is perfect; at the other extreme, whenever the lower approximation is empty, the accuracy is zero (regardless of the size of the upper approximation).
Objective analysis Rough set theory is one of many methods that can be employed to analyse uncertain (including vague) systems, although less common than more traditional methods of probability, statistics, entropy and Dempster–Shafer theory. However a key difference, and a unique strength, of using classical rough set theory is that it provides an objective form of analysis. Unlike other methods, as those given above, classical rough set analysis requires no additional information, external parameters, models, functions, grades or subjective interpretations to determine set membership – instead it only uses the information presented within the given data. More recent adaptations of rough set theory, such as dominance-based, decision-theoretic and fuzzy rough sets, have introduced more subjectivity to the analysis.
Definability In general, the upper and lower approximations are not equal; in such cases, we say that target set is undefinable or roughly definable on attribute set . When the upper and lower approximations are equal (i.e., the boundary is empty), , then the target set is definable on attribute set . We can distinguish the following special cases of undefinability:
Set is internally undefinable if and . This means that on attribute set , there are no objects which we can be certain belong to target set , but there are objects which we can definitively exclude from set . Set is externally undefinable if and . This means that on attribute set , there are objects which we can be certain belong to target set , but there are no objects which we can definitively exclude from set . Set is totally undefinable if and . This means that on attribute set , there are no objects which we can be certain belong to target set , and there are no objects which we can definitively exclude from set . Thus, on attribute set , we cannot decide whether any object is, or is not, a member of .
Reduct and core An interesting question is whether there are attributes in the information system (attribute–value table) which are more important to the knowledge represented in the equivalence class structure than other attributes. Often, we wonder whether there is a subset of attributes which can, by itself, fully characterize the knowledge in the database; such an attribute set is called a reduct.
Formally, a reduct is a subset of attributes such that
= , that is, the equivalence classes induced by the reduced attribute set are the same as the equivalence class structure induced by the full attribute set . the attribute set is minimal, in the sense that for any attribute ; in other words, no attribute can be removed from set without changing the equivalence classes .
A reduct can be thought of as a sufficient set of features – sufficient, that is, to represent the category structure. In the example table above, attribute set is a reduct – the information system projected on just these attributes possesses the same equivalence class structure as that expressed by the full attribute set:
Attribute set is a reduct because eliminating any of these attributes causes a collapse of the equivalence-class structure, with the result that .
The reduct of an information system is not unique: there may be many subsets of attributes which preserve the equivalence-class structure (i.e., the knowledge) expressed in the information system. In the example information system above, another reduct is , producing the same equivalence-class structure as .
The set of attributes which is common to all reducts is called the core: the core is the set of attributes which is possessed by every reduct, and therefore consists of attributes which cannot be removed from the information system without causing collapse of the equivalence-class structure. The core may be thought of as the set of necessary attributes – necessary, that is, for the category structure to be represented. In the example, the only such attribute is ; any one of the other attributes can be removed singly without damaging the equivalence-class structure, and hence these are all dispensable. However, removing by itself does change the equivalence-class structure, and thus is the indispensable attribute of this information system, and hence the core.
It is possible for the core to be empty, which means that there is no indispensable attribute: any single attribute in such an information system can be deleted without altering the equivalence-class structure. In such cases, there is no essential or necessary attribute which is required for the class structure to be represented.
Attribute dependency One of the most important aspects of database analysis or data acquisition is the discovery of attribute dependencies; that is, we wish to discover which variables are strongly related to which other variables. Generally, it is these strong relationships that will warrant further investigation, and that will ultimately be of use in predictive modeling.
In rough set theory, the notion of dependency is defined very simply. Let us take two (disjoint) sets of attributes, set and set , and inquire what degree of dependency obtains between them. Each attribute set induces an (indiscernibility) equivalence class structure, the equivalence classes induced by given by , and the equivalence classes induced by given by .